Multiclass Learnability Does Not Imply Sample Compression

Chirag Pabbaraju
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:930-944, 2024.

Abstract

A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the labels on the entire sample can be inferred. The size of the compression scheme is an upper bound on the size of the subsample produced. Every learnable binary hypothesis class (which must necessarily have finite VC dimension) admits a sample compression scheme of size only a finite function of its VC dimension, independent of the sample size. For multiclass hypothesis classes, the analog of VC dimension is the DS dimension. We show that the analogous statement pertaining to sample compression is not true for multiclass hypothesis classes: every learnable multiclass hypothesis class, which must necessarily have finite DS dimension, does not admit a sample compression scheme of size only a finite function of its DS dimension.

Cite this Paper

BibTeX
@InProceedings{pmlr-v237-pabbaraju24a, title = {Multiclass Learnability Does Not Imply Sample Compression}, author = {Pabbaraju, Chirag}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {930--944}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/pabbaraju24a/pabbaraju24a.pdf}, url = {https://proceedings.mlr.press/v237/pabbaraju24a.html}, abstract = {A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the labels on the entire sample can be inferred. The size of the compression scheme is an upper bound on the size of the subsample produced. Every learnable binary hypothesis class (which must necessarily have finite VC dimension) admits a sample compression scheme of size only a finite function of its VC dimension, independent of the sample size. For multiclass hypothesis classes, the analog of VC dimension is the DS dimension. We show that the analogous statement pertaining to sample compression is not true for multiclass hypothesis classes: every learnable multiclass hypothesis class, which must necessarily have finite DS dimension, does not admit a sample compression scheme of size only a finite function of its DS dimension.} }
Endnote
%0 Conference Paper %T Multiclass Learnability Does Not Imply Sample Compression %A Chirag Pabbaraju %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-pabbaraju24a %I PMLR %P 930--944 %U https://proceedings.mlr.press/v237/pabbaraju24a.html %V 237 %X A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the labels on the entire sample can be inferred. The size of the compression scheme is an upper bound on the size of the subsample produced. Every learnable binary hypothesis class (which must necessarily have finite VC dimension) admits a sample compression scheme of size only a finite function of its VC dimension, independent of the sample size. For multiclass hypothesis classes, the analog of VC dimension is the DS dimension. We show that the analogous statement pertaining to sample compression is not true for multiclass hypothesis classes: every learnable multiclass hypothesis class, which must necessarily have finite DS dimension, does not admit a sample compression scheme of size only a finite function of its DS dimension.
APA
Pabbaraju, C.. (2024). Multiclass Learnability Does Not Imply Sample Compression. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:930-944 Available from https://proceedings.mlr.press/v237/pabbaraju24a.html.

Related Material