Sample compression schemes for VC classes
This resolves a long-standing open problem in computational learning theory, providing a theoretical foundation for compression-based learning algorithms.
The paper addresses the question of whether every concept class with finite VC dimension has a sample compression scheme, showing that such classes have schemes of size exponential in the VC dimension, thereby confirming the reverse direction of the compression-learnability relationship.
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.