# Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints

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

## Key facts

- Cited by 82 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2017.

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

- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Benign Overfitting for Two-layer ReLU Convolutional Neural Networks](https://mlsanity.com/paper/2303.04145/) (2023)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [PAC-Bayes Information Bottleneck](https://mlsanity.com/paper/2109.14509/) (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)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [AdapterGNN: Parameter-Efficient Fine-Tuning Improves Generalization in GNNs](https://mlsanity.com/paper/2304.09595/) (2023)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applications](https://mlsanity.com/paper/2308.16375/) (2023)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Learning with Gradient Descent and Weakly Convex Losses](https://mlsanity.com/paper/2101.04968/) (2021)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Generalization Error Bounds for Deep Neural Networks Trained by SGD](https://mlsanity.com/paper/2206.03299/) (2022)
- [Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares](https://mlsanity.com/paper/2206.01274/) (2022)
- [Time-Independent Information-Theoretic Generalization Bounds for SGLD](https://mlsanity.com/paper/2311.01046/) (2023)
- [Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation](https://mlsanity.com/paper/2402.03990/) (2024)
- [Information-theoretic Generalization Analysis for Expected Calibration Error](https://mlsanity.com/paper/2405.15709/) (2024)
- [Generalisation under gradient descent via deterministic PAC-Bayes](https://mlsanity.com/paper/2209.02525/) (2022)
- [Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networks](https://mlsanity.com/paper/2305.16891/) (2023)
- [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)
- [Generalization in Supervised Learning Through Riemannian Contraction](https://mlsanity.com/paper/2201.06656/) (2022)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis](https://mlsanity.com/paper/2507.03756/) (2025)
- [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)

## Abstract (arXiv)

Algorithm-dependent generalization error bounds are central to statistical learning theory. A learning algorithm may use a large hypothesis space, but the limited number of iterations controls its model capacity and generalization error. The impacts of stochastic gradient methods on generalization error for non-convex learning problems not only have important theoretical consequences, but are also critical to generalization errors of deep learning. In this paper, we study the generalization errors of Stochastic Gradient Langevin Dynamics (SGLD) with non-convex objectives. Two theories are proposed with non-asymptotic discrete-time analysis, using Stability and PAC-Bayesian results respectively. The stability-based theory obtains a bound of Oleft(frac1nL√β Tkright), where L is uniform Lipschitz parameter, β is inverse temperature, and Tk is aggregated step sizes. For PAC-Bayesian theory, though the bound has a slower O(1/√n) rate, the contribution of each step is shown with an exponentially decaying factor by imposing ℓ2 regularization, and the uniform Lipschitz constant is also replaced by actual norms of gradients along trajectory. Our bounds have no implicit dependence on dimensions, norms or other capacity measures of parameter, which elegantly characterizes the phenomenon of "Fast Training Guarantees Generalization" in non-convex settings. This is the first algorithm-dependent result with reasonable dependence on aggregated step sizes for non-convex learning, and has important implications to statistical learning aspects of stochastic gradient methods in complicated models such as deep learning.