ECCC-Report TR15-040https://eccc.weizmann.ac.il/report/2015/040Comments and Revisions published for TR15-040en-usTue, 14 Apr 2015 14:23:54 +0300
Revision 1
| Sample compression schemes for VC classes |
Shay Moran,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2015/040#revision1Sample 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.Tue, 14 Apr 2015 14:23:54 +0300https://eccc.weizmann.ac.il/report/2015/040#revision1
Paper TR15-040
| Proper PAC learning is compressing |
Shay Moran,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2015/040We 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.Tue, 24 Mar 2015 15:48:39 +0200https://eccc.weizmann.ac.il/report/2015/040