Loading jsMath...
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: 2687
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: 3362
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