Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound

2020-11-09 · Steve Hanneke, Aryeh Kontorovich

We analyze a family of supervised learning algorithms based on sample compression schemes that are stable, in the sense that removing points from the training set which were not selected for the compression set does not alter the resulting classifier. We use this technique to derive a variety of novel or improved data-dependent generalization bounds for several learning algorithms. In particular, we prove a new margin bound for SVM, removing a log factor. The new bound is provably optimal. This resolves a long-standing open question about the PAC margin bounds achievable by SVM.

📄 PDF Abstract BibTeX arXiv:2011.04586

Code (4)

MindCode-4/code-9/tree/main/stable-sam mindspore

MindSpore-scientific/code-14/tree/main/stable-sam mindspore

pwc-1/Paper-9/tree/main/3/stable-sam mindspore

pwc-1/Paper-9/tree/main/4/stable-sam mindspore

Tasks

Generalization BoundsOpen-Ended Question Answering

Methods 이 논문이 사용한 방법론

SVM A Support Vector Machine, or SVM, is a non-parametric supervised learning model. For non-linear classification and regression, they utilise the kernel trick to map inputs…

A New Lower Bound for Agnostic Learning with Sample Compression Schemes

2018-05-21 · Steve Hanneke, Aryeh Kontorovich

We establish a tight characterization of the worst-case rates for the excess risk of agnostic learning with sample compression schemes and for uniform convergence for agnostic sample compression schemes. In particular, w…

Form

A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension

2022-12-24 · Farnam Mansouri, Sandra Zilles

This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(\VCD^2)$ for any finite concept class, where $\VCD$ denotes the Vapnik-Chervonenkis Dimension. The construction is b…

Open-Ended Question Answering

Sample Compression Scheme Reductions

2024-10-16 · Idan Attias, Steve Hanneke, Arvind Ramaswami

We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings to binary sample compression schemes. Assuming we have a compression scheme…

Binary Classification

Sample compression schemes for balls in graphs

2022-06-27 · Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel 외

One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)…

Unlabeled sample compression schemes and corner peelings for ample and maximum classes

2018-12-05 · Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth

We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Ou…

BIG-bench Machine Learning