Introduction
Modern deep neural networks (DNNs) are massively over-parameterized and can easily memorize random data, yet they still generalize remarkably well to unseen examples. Traditional statistical learning bounds, such as those based on VC-dimension, fail to explain this phenomenon because they rely on the complexity of the hypothesis class, which remains identical whether the network is trained on clean or corrupted data.
This paper derives new, computable generalization bounds for Stochastic Gradient Langevin Dynamics (SGLD) and Differentially Private SGD (DP-SGD). By treating the additive noise inherent in these algorithms as Gaussian communication channels, the authors provide bounds that successfully capture real-world deep learning phenomena—such as the impact of label corruption—and correlate highly with the true generalization gap.
The Information-Theoretic Approach
Recent theoretical work has attempted to bound the generalization gap using the mutual information between the training dataset and the final model weights. However, estimating this mutual information in practice is notoriously intractable. Furthermore, existing bounds for noisy algorithms like SGLD often rely on worst-case Lipschitz constants. These "distribution-independent" bounds are overly pessimistic and fail to capture empirical observations, such as the fact that networks trained on corrupted labels generalize worse than those trained on true labels.
To bridge optimization and information theory, the authors model the noise injected during SGLD and DP-SGD as Additive White Gaussian Noise (AWGN) channels. This connection allows them to use well-established properties of Gaussian channels to bypass intractable mutual information calculations. They introduce two main techniques:
- Bounding with Gradient Variance: Instead of using a worst-case Lipschitz constant, the authors upper-bound the mutual information using the variance of the gradients. This variance acts as a proxy for the "sharpness" of the loss landscape and can be easily estimated directly from the training data, making the bound distribution-dependent.
- Strong Data Processing Inequalities: For DP-SGD (where only the final model weights are released), the authors use strong data processing inequalities to introduce a time-decaying factor. This mathematically proves that the impact of a data point used in an early training iteration "decays" over time due to the cumulative addition of Gaussian noise in subsequent steps.
Key Results and Empirical Validation
The theoretical contributions yield tighter, computable bounds. The expected generalization bound for SGLD achieves an $O(1/n)$ sample size dependence, improving upon previous $O(1/\sqrt{n})$ PAC-Bayes bounds. For DP-SGD, the established bound features an explicit decay factor $q^{T-t}$ (where $q \in (0,1)$). This proves that as the number of steps $T \to \infty$, the generalization bound converges to 0, whereas bounds without this decay factor plateau at a large constant.
Empirically, the proposed bound vastly outperforms benchmark information-theoretic bounds in predicting the true generalization gap. In experiments on MNIST, it achieved a Kendall’s rank-correlation ($\tau$) of 0.50 (compared to a baseline of 0.25), a Granulated Kendall’s coefficient ($\Psi$) of 0.75 (vs. 0.33), and a Mutual Information test score of 0.34 (vs. 0.12).
Crucially, unlike previous bounds that remain static regardless of the data, this new bound visibly inflates when trained on corrupted labels, mirroring the actual behavior of the neural network's generalization gap.
Limitations and Future Work
While the trend of the bound correlates perfectly with the true generalization gap, the calculated numerical value of the bound is still vacuous (i.e., greater than 1), a common limitation among current generalization bounds for deep learning. Additionally, the time-decaying factor for DP-SGD relies on the assumption that the gradient updates are strictly bounded (e.g., via gradient clipping), which is standard in differential privacy but restrictive for general non-convex optimization.
Future work may focus on tightening the time-decaying factor by making it distribution-dependent. The "Gaussian channel" proof blueprint could also be extended to analyze other noisy iterative algorithms or combined with privacy amplification techniques like data subsampling and shuffling.
Summary updated