# On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning

arXiv: https://arxiv.org/abs/1902.00621 · HTML: https://mlsanity.com/paper/1902.00621/

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2019.

## Built on by (most cited first, 30 of 57)

- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2109.14595/) (2021)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [On the Generalization Mystery in Deep Learning](https://mlsanity.com/paper/2203.10036/) (2022)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [BAFFLE: A Baseline of Backpropagation-Free Federated Learning](https://mlsanity.com/paper/2301.12195/) (2023)
- [Time-Independent Information-Theoretic Generalization Bounds for SGLD](https://mlsanity.com/paper/2311.01046/) (2023)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [Stochastic Anderson Mixing for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2110.01543/) (2021)
- [Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence](https://mlsanity.com/paper/2206.07892/) (2022)
- [On the Importance of Gradient Norm in PAC-Bayesian Bounds](https://mlsanity.com/paper/2210.06143/) (2022)
- [Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent](https://mlsanity.com/paper/2305.12056/) (2023)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Towards Understanding Generalization via Decomposing Excess Risk Dynamics](https://mlsanity.com/paper/2106.06153/) (2021)
- [Generalization Bounds for Gradient Methods via Discrete and Continuous Prior](https://mlsanity.com/paper/2205.13799/) (2022)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Continuous Representation Methods, Theories, and Applications: An Overview and Perspectives](https://mlsanity.com/paper/2505.15222/) (2025)
- [Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression](https://mlsanity.com/paper/2202.06054/) (2022)

## Abstract (arXiv)

Generalization error (also known as the out-of-sample error) measures how well the hypothesis learned from training data generalizes to previously unseen data. Proving tight generalization error bounds is a central question in statistical learning theory. In this paper, we obtain generalization error bounds for learning general non-convex objectives, which has attracted significant attention in recent years. We develop a new framework, termed Bayes-Stability, for proving algorithm-dependent generalization error bounds. The new framework combines ideas from both the PAC-Bayesian theory and the notion of algorithmic stability. Applying the Bayes-Stability method, we obtain new data-dependent generalization bounds for stochastic gradient Langevin dynamics (SGLD) and several other noisy gradient methods (e.g., with momentum, mini-batch and acceleration, Entropy-SGD). Our result recovers (and is typically tighter than) a recent result in Mou et al. (2018) and improves upon the results in Pensia et al. (2018). Our experiments demonstrate that our data-dependent bounds can distinguish randomly labelled data from normal data, which provides an explanation to the intriguing phenomena observed in Zhang et al. (2017a). We also study the setting where the total loss is the sum of a bounded loss and an additional ℓ2 regularization term. We obtain new generalization bounds for the continuous Langevin dynamic in this setting by developing a new Log-Sobolev inequality for the parameter distribution at any time. Our new bounds are more desirable when the noisy level of the process is not small, and do not become vacuous even when T tends to infinity.