# Tight Generalization Error Bounds for Stochastic Gradient Descent in Non-convex Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 23 Jun 2025.

## Builds on (most cited first, 23 of 23)

- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization](https://mlsanity.com/paper/1907.04371/) (2019)
- [The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent](https://mlsanity.com/paper/2305.17490/) (2023)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2310.01860/) (2023)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [SGD Implicitly Regularizes Generalization Error](https://mlsanity.com/paper/2104.04874/) (2021)
- [Benefits of Additive Noise in Composing Classes with Bounded Capacity](https://mlsanity.com/paper/2206.07199/) (2022)
- [Generalization Error Bounds for Optimization Algorithms via Stability](https://mlsanity.com/paper/1609.08397/) (2016)
- [Noisy Truncated SGD: Optimization and Generalization](https://mlsanity.com/paper/2103.00075/) (2021)
- [SGD method for entropy error function with smoothing l0 regularization for neural networks](https://mlsanity.com/paper/2405.18552/) (2024)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) is fundamental for training deep neural networks, especially in non-convex settings. Understanding SGD's generalization properties is crucial for ensuring robust model performance on unseen data. In this paper, we analyze the generalization error bounds of SGD for non-convex learning by introducing the Type II perturbed SGD (T2pm-SGD), which accommodates both sub-Gaussian and bounded loss functions. The generalization error bound is decomposed into two components: the trajectory term and the flatness term. Our analysis improves the trajectory term to O(n-1), significantly enhancing the previous O((nb)-1/2) bound for bounded losses, where n is the number of training samples and b is the batch size. By selecting an optimal variance for the perturbation noise, the overall bound is further refined to O(n-2/3). For sub-Gaussian loss functions, a tighter trajectory term is also achieved. In both cases, the flatness term remains stable across iterations and is smaller than those reported in previous literature, which increase with iterations. This stability, ensured by T2pm-SGD, leads to tighter generalization error bounds for both loss function types. Our theoretical results are validated through extensive experiments on benchmark datasets, including MNIST and CIFAR-10, demonstrating the effectiveness of T2pm-SGD in establishing tighter generalization bounds.