A central paradox of modern machine learning is that massive models with millions or billions of parameters generalize remarkably well to unseen data. Classical statistical learning theory suggests that such overparameterized models possess the capacity to easily overfit and memorize noise, which should lead to poor generalization.
To resolve this paradox, researchers often turn to Occam’s Razor: the philosophical principle that simpler explanations are inherently more likely to be correct. In computational learning theory, this concept of "simplicity" can be formally mathematically defined through compression. If a model or a dataset can be compressed into a compact representation without losing its predictive power, it cannot simply be memorizing random noise. Instead, it must have captured a genuine underlying regularity.
The compression-based framework for generalization operates via two primary mechanisms: sample compression (reducing a large dataset to a tiny set of core representative examples) and model compression (reducing the description length or parameter complexity of the hypothesis itself).
Sample Compression: Learning from Key Points
Imagine a dataset containing one million labeled images. Suppose an algorithm can select a tiny subset of just ten images, such that a fixed program can look only at those ten images and correctly reconstruct the labels for the remaining 999,990 images. Intuitively, those ten images must contain the absolute essence of the entire dataset.
This is the core mechanism of a sample compression scheme, a foundational framework formalized by Floyd in Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension. A sample compression scheme consists of two components:
- A compression function that selects a small subset of informative examples (the compression set) from the training data.
- A reconstruction function that takes only this subset and outputs a hypothesis consistent with the full dataset.
Full Dataset (Size n) ───► [ Compression Function ] ───► Compression Set (Size k)
│
▼
Unseen Data Generalization ◄─── Consistent Hypothesis ◄─── [ Reconstruction Function ]
Why Sample Compression Guarantees Generalization
If the true data-generating process were entirely random noise, the probability that a hypothesis derived from a tiny subset of size $k$ would happen to correctly predict the remaining $n-k$ points by pure chance is exponentially small.
Therefore, if an algorithm successfully finds a small compression set that explains a large sample, the hypothesis is highly likely to perform well on entirely unseen data. As shown by Sokolova et al. in The Decision List Machine, generalization performance can be mathematically bounded by the size of this compression set relative to the total sample size.
Because these bounds depend on the size of the compression set rather than the complexity of the entire hypothesis space, they are completely distribution-free. This allows meta-algorithms like Pick-to-Learn, analyzed by Paccagnan et al., to compute exceptionally tight, non-vacuous reliability certificates directly from the data without requiring a separate validation set.
Model Compression and Minimum Description Length
Instead of compressing the data points used to train a model, we can evaluate generalization by compressing the model parameters themselves. This perspective is rooted in the Minimum Description Length (MDL) principle, which views learning as data compression.
If a model requires a massive number of bits to describe its parameters, it has high complexity. However, if the trained parameters can be compressed into a very short bitstring (for instance, via arithmetic coding or quantization) without losing accuracy, its effective complexity is low.
This link is rigorously formalized using PAC-Bayes theory. In a PAC-Bayes framework, the generalization gap is bounded by the informational distance (Kullback-Leibler divergence) between the trained model's parameter distribution and a data-independent prior distribution. A model that can be represented in a highly compressed format requires very few bits to specify, meaning it remains close to a simple prior.
By leveraging this insight, Finzi et al. in PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization calculated data-independent generalization bounds for deep neural networks on large-scale datasets like ImageNet. By proving that these massive networks are far more compressible than their raw parameter counts suggest, the authors provided a practical "Occam's Razor" showing that low description length prevents overparameterized models from overfitting.
Similarly, Blier et al. demonstrated that evaluating how efficiently a model compresses data during the sequential learning process (prequential coding) serves as a powerful predictor of its subsequent performance on new examples.
The Implicit Compressibility of Deep Networks
If compressibility guarantees generalization, why do uncompressed, overparameterized deep networks perform so well in the wild? The answer lies in the implicit compressibility of the models generated by standard optimization algorithms like Stochastic Gradient Descent (SGD).
Even when a neural network is structurally massive, the optimization path taken by SGD biases it toward highly regular solutions. Suzuki et al. proved that the generalization error of a large, uncompressed neural network can be bounded by decomposing it into two parts: $$\text{Generalization Error} \le \text{Complexity of a Compressed Surrogate} + \text{Approximation Error}$$
If a hypothetical, highly compressed version of the network (a surrogate) can closely mimic the full network's predictions, the original uncompressed network inherits the tight generalization guarantees of that simpler surrogate.
This implicit simplicity manifests in several ways:
- Heavy-Tailed Weight Distributions: Sefidgaran et al. showed that SGD naturally drives overparameterized networks toward weight matrices with heavy tails. This structural property makes the networks highly amenable to pruning, meaning they are effectively much simpler than their raw parameter counts indicate.
- Functional Distillation: If a complex network can be distilled into a smaller, simpler architecture with nearly identical outputs, Hsu et al. proved that the original complex network inherits the tighter generalization bounds of the distilled witness model.
- Parameter Coresets: Baykal et al. demonstrated that there almost always exists a small, sparse subset of parameters (a coreset) that can approximate the full network's mathematical function, directly bounding its Rademacher complexity.
Extending the Paradigm
The conceptual link between compression and learnability is not restricted to standard independent and identically distributed (i.i.d.) classification tasks; it extends across diverse learning paradigms.
Density Estimation
In unsupervised learning, Ashtiani et al. utilized a distribution compression framework to solve long-standing sample complexity questions for Gaussian mixture models. They proved that if a class of probability distributions can be compactly encoded using a small subset of observed samples plus a few additional information bits, it can be learned efficiently, bypassing traditional mathematical barriers.
Non-I.I.D. Data
When data points are tangled by spatial or network dependencies, standard uniform convergence arguments break down. Dagan et al. extended sample compression theory to weakly dependent data under Dobrushin's condition, demonstrating that if a small subset of dependent training data can represent the entire sample, robust generalization guarantees still hold.
Large Language Models
To analyze modern architectures like Large Language Models (LLMs), Lotfi et al. treated individual text tokens as distinct data points within a compression-based framework. By calculating generalization bounds derived from model compression on architectures as large as LLaMA2-70B, the authors showed that these information-theoretic compression metrics serve as highly accurate predictors of real-world downstream perplexity and performance.
Key Foundational Work
Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension (1995) — contributed 4 concept elements to this direction.
The Strength of Weak Learnability (1990) — contributed 2 concept elements to this direction.