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

Steve Hanneke, Aryeh Kontorovich
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:697-721, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-hanneke21a, title = {Stable Sample Compression Schemes: New Applications and an Optimal {SVM} Margin Bound}, author = {Hanneke, Steve and Kontorovich, Aryeh}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {697--721}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/hanneke21a/hanneke21a.pdf}, url = {https://proceedings.mlr.press/v132/hanneke21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound %A Steve Hanneke %A Aryeh Kontorovich %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-hanneke21a %I PMLR %P 697--721 %U https://proceedings.mlr.press/v132/hanneke21a.html %V 132 %X 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.
APA
Hanneke, S. & Kontorovich, A.. (2021). Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:697-721 Available from https://proceedings.mlr.press/v132/hanneke21a.html.

Related Material