In machine learning, the "generalization gap"—the difference between a model's performance on training data versus unseen test data—is often viewed as a measure of how much the model has "overfit" or memorized the specific noise in its training set.
Information theory provides a natural language for this: if a model's weights contain too much information about the training labels, it likely hasn't learned a general rule. However, traditional information-theoretic bounds often fail for modern deep learning. If a neural network is deterministic, the mutual information between the input and the weights can technically be infinite, leading to "vacuous" (useless) bounds.
A growing body of research addresses this by reframing generalization through the lens of Rate-Distortion Theory. By treating the generalization gap as a form of "distortion" in a lossy compression scheme, researchers are deriving tighter, non-vacuous bounds that hold even for deterministic and high-dimensional models.
The Generalization Gap as Distortion
The core intuition behind this direction is a formal mathematical equivalence between learning and source coding. In communication, Rate-Distortion Theory describes the minimum number of bits (Rate $R$) required to transmit a signal such that it can be reconstructed within a certain allowed error (Distortion $D$).
Saeed Masiha and Amin Gohari demonstrate in f-divergences and their applications in lossy compression and bounding generalization error that the problem of bounding generalization error is mathematically equivalent to a rate-distortion problem. In this mapping:
- The "Signal" is the training dataset.
- The "Code" is the learned hypothesis or model weights.
- The "Distortion" is defined as the negative generalization gap.
By framing the generalization gap as a distortion measure, Mohammad Saeed Masiha et al. show in Learning under Distribution Mismatch and Model Misspecification that we can quantify how much an algorithm "knows" about its training data relative to its performance. This allows for the derivation of bounds that remain valid even when the training and test distributions don't perfectly match.
Solving the Vacuous Bound Problem
Why use lossy compression instead of standard mutual information? In representation learning, if you have a deterministic encoder mapping an input $X$ to a continuous latent variable $Z$, the mutual information $I(X; Z)$ is often infinite. This makes standard Information Bottleneck (IB) bounds useless for proving that a model will generalize.
To fix this, Milad Sefidgaran, Abdellatif Zaidi, and Piotr Krasnowski propose using Minimum Description Length (MDL) and lossy compression. In Minimum Description Length and Generalization Guarantees for Representation Learning, they argue that by allowing a controlled amount of "distortion" or noise in the latent representation, we can bound the precision of the variables. This ensures the complexity of the representation is measured in a way that remains finite and stable.
This perspective leads to practical algorithms. In Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors, the same authors introduce the GM-MDL regularizer. Instead of penalizing raw information, it penalizes the "compressibility" of the latent space using a data-dependent Gaussian Mixture, which naturally encourages the model to focus only on the most relevant features for the task.
Scaling to High Dimensions via Slicing
Applying these information-theoretic tools to the millions of parameters in a modern neural network is computationally daunting. Kimia Nadjahi, Justin Solomon, and colleagues address this in Slicing Mutual Information Generalization Bounds for Neural Networks.
They use a technique called slicing—projecting high-dimensional model weights onto random one-dimensional subspaces. By combining this with rate-distortion theory, they account for models that are "approximately" compressible. They measure the distance (distortion) between the actual high-dimensional weights and their lower-dimensional projections. This allows them to balance model complexity with "representational fidelity," providing a practical way to estimate generalization bounds for deep networks that were previously considered too complex for information-theoretic analysis.
Summary of the Intuition
The shift toward Rate-Distortion Theory in generalization research represents a move from counting bits to measuring trade-offs.
- Generalization is Compression: A model that generalizes well is one that has effectively compressed the training data into a simple set of rules.
- Lossiness is Necessary: To get meaningful bounds for continuous or deterministic models, we must allow for some "loss" (distortion) in how we represent the model's information.
- The Rate-Distortion Curve: There is a fundamental limit to how much we can reduce the generalization gap (distortion) for a given amount of model complexity (rate). Tighter bounds are found by better characterizing this curve for specific learning algorithms.