In the mid-1990s, Sally Floyd and Manfred Warmuth posed a deceptively simple question: if a learning algorithm can represent a massive dataset using only a tiny "representative" subset, does that guarantee the underlying pattern is learnable?
This question birthed the theory of sample compression schemes, a framework that views machine learning not as an optimization problem, but as a communication game. In this view, learning is equivalent to data reduction. If you can identify a small "kernel" of critical examples that allow you to reconstruct the labels of the entire dataset, you have captured the essence of the concept.
The Compression Game
A sample compression scheme consists of two parts: a compression function and a reconstruction function.
Imagine a dataset of 1,000,000 images. A compressor selects a tiny subset—say, 10 images—and sends them to a reconstructor. The reconstructor, using only those 10 images (and perhaps a few extra bits of information), must produce a hypothesis that correctly predicts the labels for all 1,000,000 original images.
As Sally Floyd showed in Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension, the size of this compressed subset is a fundamental "speed limit" for learning. If a concept class can always be compressed into a set of size $k$, then the error of the resulting hypothesis decreases as the ratio $k/n$ improves, where $n$ is the total sample size.
The Fundamental Equivalence
For decades, a central conjecture in computational learning theory was whether every concept class with a finite Vapnik-Chervonenkis (VC) dimension—the standard measure of a model's complexity—could be compressed.
This was finally settled by Amir Yehudayoff and Shay Moran. In Sample compression schemes for VC classes and Labeled Compression Schemes for Extremal Classes, they proved that PAC learnability is fundamentally equivalent to the existence of a sample compression scheme.
This result implies that every learnable pattern is "anchored" by a small set of critical examples. If a class has VC dimension $d$, it can be reconstructed from a subset whose size is bounded by a function of $d$. This moved the field from viewing VC dimension as an abstract combinatorial property to seeing it as a measure of a class's intrinsic "compressibility."
Beyond Binary Classification
While the theory began with binary labels, it has recently expanded to more complex domains:
- Regression: Steve Hanneke and Aryeh Kontorovich extended these ideas to real-valued functions in Sample Compression for Real-Valued Learners. They showed that for regression, learnability is equivalent to "approximate" compression, where the reconstructed function doesn't need to be perfect, just sufficiently close to the optimal fit.
- Distribution Learning: Hassan Ashtiani and Abbas Mehrabian applied this to unsupervised learning in Agnostic Distribution Learning via Compression. They demonstrated that complex distributions, like mixtures of Gaussians, can be learned by identifying a small subset of samples that act as "anchors" for the density's parameters.
- Robustness and Privacy: Idan Attias and Steve Hanneke used compression to bypass the failures of traditional uniform convergence in adversarially robust settings. Similarly, Shai Ben-David and Gautam Kamath showed in Private Distribution Learning with Public Data that a tiny amount of public data can anchor a private learning task, making previously "impossible" private learning problems solvable.
From Theory to Algorithms
The power of compression isn't just theoretical; it provides a way to calculate "distribution-free" risk certificates. Traditional machine learning often requires a separate test set to estimate performance. However, if an algorithm is a compression scheme, we can bound its error using only the training data and the size of the compressed set.
A notable modern implementation is the Pick-to-Learn (P2L) algorithm by Dario Paccagnan and Marco C. Campi. In The Pick-to-Learn Algorithm, they describe a meta-algorithm that iteratively "picks" the most informative data points to refine a model. Because the final model is defined entirely by this small subset, P2L provides extremely tight generalization bounds without needing a hold-out set, maximizing data efficiency in safety-critical applications like control systems.
Similarly, in the realm of Nearest Neighbors, Aryeh Kontorovich and Sivan Sabato developed the KSU algorithm. By using sample compression to shrink a dataset to its most representative points, KSU achieves Bayes consistency even in infinite-dimensional metric spaces where standard $k$-NN algorithms often fail.
Why It Works
The intuition behind sample compression is a formalization of Occam’s Razor. If a complex hypothesis can be "explained" by a very small number of examples, it is unlikely that the hypothesis is merely overfitting the noise in the data. The small size of the compression set acts as a certificate of simplicity, ensuring that the patterns discovered by the algorithm will generalize to unseen data.