In the search for a "universal law" of machine learning, researchers have turned to information theory to explain generalization: why a model trained on a finite dataset performs well on unseen data. The core intuition is simple: if a model "memorizes" too much specific information about its training set, it will likely fail to generalize.
By measuring the Mutual Information (MI) between a model’s parameters and its training data, we should—in theory—be able to predict its performance. However, as models have grown larger and more complex, this theoretical framework has hit a wall. In many modern settings, these information-theoretic bounds become vacuous—mathematically true, but practically useless because they provide error estimates that are infinite or larger than the worst-case error.
The Information Leakage Intuition
The fundamental idea, synthesized in work by Fredrik Hellström, Benjamin Guedj, and Giuseppe Durisi, is that generalization error is driven by "information complexity."
Imagine a learning algorithm as a communication channel. The training data is the input, and the final model weights are the output. If the weights "leak" too much information about which specific samples were in the training set, the model is likely overfitting. Information-theoretic bounds attempt to quantify this leakage. If the MI is low, the model is "stable"—changing one training point wouldn't change the model much—and thus it should generalize well.
The Problem of Vacuity in High Dimensions
While elegant, this framework struggles with the reality of modern deep learning. Mahdi Haghifam, Daniel M. Roy, and Gintare Karolina Dziugaite have shown that standard MI bounds are often sensitive to the dimensionality of the model.
In overparameterized regimes—where the number of parameters far exceeds the number of data points—the mutual information can grow to infinity. Ravid Shwartz-Ziv and Alexander A Alemi demonstrated this in the limit of infinitely wide neural networks. Even though these models generalize perfectly in practice, the theoretical "information" they carry about the dataset is so vast that traditional PAC-Bayes and MI bounds fail to provide any useful limit on error.
Furthermore, Roi Livni proved a discouraging lower bound: in Stochastic Convex Optimization (SCO), any bound based purely on mutual information must depend on the dimension of the problem. This contradicts the behavior of algorithms like Stochastic Gradient Descent (SGD), which generalize at rates independent of the number of parameters.
The Memorization Paradox
A recurring theme across this research is the tension between learning and memorization. Idan Attias and colleagues argue that in certain settings, memorization is actually necessary for generalization. They showed that any algorithm achieving high accuracy in SCO must capture a significant amount of information about its training data, as measured by Conditional Mutual Information (CMI).
This creates a paradox: if high information (memorization) is required to learn, but high information makes our theoretical bounds vacuous, how do we explain why these models work? Vidya Muthukumar and Mikhail Belkin highlight a "Goldilocks" regime where a model might completely fail to predict numerical values (regression) but still perfectly categorize data (classification), even when every training point effectively becomes a support vector.
Refining the Metric: Stability and Compression
To resolve these contradictions, researchers are developing more refined information metrics that "ignore" the irrelevant high-dimensional noise.
- Jensen-Shannon Information: Gholamali Aminian, Laura Toni, and Miguel R. D. Rodrigues proposed using Jensen-Shannon (JS) information instead of KL-divergence-based MI. Unlike standard MI, JS information is always finite, providing tighter bounds even when models heavily memorize data.
- Sample-Conditioned Stability: Ziqiao Wang introduced Sample-Conditioned Hypothesis (SCH) stability. By combining algorithmic stability with information theory, this framework creates bounds that "vanish" (go to zero) as the sample size grows, even in cases where previous MI bounds remained constant.
- Projection and Quantization: Milad Sefidgaran and Abdellatif Zaidi suggest that we shouldn't look at the raw parameters. By using stochastic projection and lossy compression, they filter out the high-dimensional information that doesn't contribute to generalization, successfully resolving counter-examples where standard CMI bounds failed.
- Recognizable Information: Yilin Lyu and colleagues developed the Recognizable Information Bottleneck (RIB), which focuses on the "recognizability" of internal representations. This approach links generalization to binary hypothesis testing, providing a practical way to estimate the generalization gap in deep networks.
By shifting the focus from how much information a model carries to what kind of information it carries, this research direction aims to bridge the gap between the pessimistic predictions of classical theory and the empirical success of massive neural networks.