Abstract
A grand challenge in representation learning is to learn the different explanatory factors of variation behind high-dimensional data. While encoder models are often optimized for training performance, the ultimate goal is generalization to unseen data. Although numerical evidence suggests that noise injection at the representation level improves generalization, an information-theoretic understanding of this principle has remained elusive. This paper presents a sample-dependent bound on the generalization gap of the cross-entropy loss that scales with Information Complexity (IC)—the mutual information between inputs and their representations. Empirical investigations on MNIST and CIFAR-10 suggest that SGD implicitly minimizes IC. Furthermore, we analyze the role of Dropout, showing its relationship to encoder capacity and sample distinguishability. Our results provide theoretical support for modern regularization methods.
1. Introduction
A central mystery in deep learning is why massive models, which possess the capacity to perfectly memorize training sets, generalize so effectively to unseen data. Traditional statistical tools, such as VC-dimension or Rademacher complexity, often fail to explain this because they focus on the size of the function class rather than the specific properties of the learned representations.
This paper addresses the "generalization gap"—the discrepancy between training and test error—through an information-theoretic lens. The authors propose that the key to generalization lies in how much information a representation "squeezes" out of its input, a property they term Information Complexity (IC).
2. Theoretical Framework: Information Complexity
The core of the proposed framework is the definition of Information Complexity (IC) as the mutual information $I(X; U)$ between the input $X$ and the hidden representation $U$.
2.1 The Informational Bound
The authors derive a sample-dependent bound (Theorem 1) proving that the generalization gap for cross-entropy loss is bounded by a term scaling with the square root of the IC. This suggests that if a model learns a representation that captures too much specific information about the training samples, it is mathematically more likely to overfit. The bound scales with $\frac{\log(n)}{\sqrt{n}}$, where $n$ is the number of samples, aligning with established statistical learning rates while introducing a dependence on representation content.
2.2 Encoder Capacity and Randomization
To study the effect of noise, the paper introduces "Encoder Capacity," a metric measuring the distinguishability of samples from their representations. By using randomized encoders—models that map inputs to representations with added noise, such as Dropout—the model is forced to map different versions of the same input to similar representations. This effectively reduces the IC by "squeezing out" non-essential information.
3. Empirical Analysis
The authors validated their theory using standard multi-layer neural networks on the MNIST and CIFAR-10 datasets.
3.1 Tracking the Generalization Gap
In both datasets, IC was found to track the generalization gap almost perfectly as the number of hidden units increased. As networks grew wider, both the gap and the IC increased, confirming that wider networks tend to capture more information about the training set, which can lead to higher generalization errors if not regularized.
3.2 SGD as an Implicit Regularizer
One significant finding is that Stochastic Gradient Descent (SGD) naturally selects encoders that tend to minimize IC, even without explicit regularization. This suggests that the optimization process itself has an inherent bias toward simpler, more compressed representations.
3.3 Phase Transitions and Random Labels
To test the sensitivity of the IC metric, the authors used "corrupted" datasets with random labels. They observed that IC can detect "phase transitions" in the data; when labels are randomized, the IC spikes. This indicates that the model has ceased finding regularities and has instead begun the high-complexity process of memorizing noise.
4. The Dropout Trade-off
The paper provides a formal justification for Dropout, proving the existence of a non-trivial optimal Dropout rate.
- Insufficient Noise: Leads to high IC and overfitting as the model retains too much sample-specific detail.
- Excessive Noise: Destroys the representation's utility, making it impossible to minimize training loss.
- Optimal Noise: Minimizes the generalization bound while maintaining enough information for accurate classification.
5. Conclusion and Limitations
This work provides a rigorous information-theoretic foundation for why noise injection and regularization improve deep learning performance. By quantifying the relationship between mutual information and generalization, it moves beyond heuristic explanations of model behavior.
However, the authors note several challenges for future research. The current bounds, while theoretically informative, may not be numerically tight. Additionally, estimating mutual information in extremely deep architectures like Transformers remains computationally expensive. Future work will focus on refining these constants and developing more efficient approximation methods for real-time monitoring during training.
Summary updated