Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-040 | 14th April 2015 14:23

Sample compression schemes for VC classes

RSS-Feed




Revision #1
Authors: Shay Moran, Amir Yehudayoff
Accepted on: 14th April 2015 14:23
Downloads: 1095
Keywords: 


Abstract:

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size $k$ means that given an arbitrary list of labeled examples, one can retain only $k$ of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds. We answer their question and show that every concept class $C$ with VC dimension $d$ has a sample compression scheme of size exponential in $d$. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.



Changes to previous version:

The previous version of this text contained an error; Theorem 2.1 in it is false. This error only affects the statement for multi-labeled classes, and the construction for binary-labeled classes still holds. In the new version of the text, we added a relevant discussion in Section 4.


Paper:

TR15-040 | 24th March 2015 10:09

Proper PAC learning is compressing





TR15-040
Authors: Shay Moran, Amir Yehudayoff
Publication: 24th March 2015 15:48
Downloads: 1137
Keywords: 


Abstract:

We prove that proper PAC learnability implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a sample compression scheme of size $2^{O(d)}$.
In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. This answers a question of Littlestone and Warmuth (1986). The proof uses an approximate minimax phenomenon for boolean matrices of low VC dimension.



ISSN 1433-8092 | Imprint