Analyzing the Generalization Capability of SGLD Using Properties of Gaussian Channels

Hao Wang, Yizhe Huang, Rui Gao, Flávio P. Calmon

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:

  1. 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.
  2. 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.

Training accuracy, generalization gap, and the proposed bound across different label corruption levels.

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

Abstract

Optimization is a key component for training machine learning models and has a strong impact on their generalization. In this paper, we consider a particular optimization method---the stochastic gradient Langevin dynamics (SGLD) algorithm---and investigate the generalization of models trained by SGLD. We derive a new generalization bound by connecting SGLD with Gaussian channels found in information and communication theory. Our bound can be computed from the training data and incorporates the variance of gradients for quantifying a particular kind of "sharpness" of the loss landscape. We also consider a closely related algorithm with SGLD, namely differentially private SGD (DP-SGD). We prove that the generalization capability of DP-SGD can be amplified by iteration. Specifically, our bound can be sharpened by including a time-decaying factor if the DP-SGD algorithm outputs the last iterate while keeping other iterates hidden. This decay factor enables the contribution of early iterations to our bound to reduce with time and is established by strong data processing inequalities---a fundamental tool in information theory. We demonstrate our bound through numerical experiments, showing that it can predict the behavior of the true generalization gap.
BibTeX
@inproceedings{wang2021analyzing,
  author = {Hao Wang and Yizhe Huang and Rui Gao and Flávio P. Calmon},
  title = {{Analyzing the Generalization Capability of SGLD Using Properties of Gaussian Channels}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=KggwUx63_t},
}
Figure