# Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization

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

## Key facts

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

## Built on by (most cited first, 14 of 14)

- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Learning to Generalize Provably in Learning to Optimize](https://mlsanity.com/paper/2302.11085/) (2023)
- [Towards Understanding Generalization via Decomposing Excess Risk Dynamics](https://mlsanity.com/paper/2106.06153/) (2021)
- [On the Algorithmic Stability and Generalization of Adaptive Optimization Methods](https://mlsanity.com/paper/2211.03970/) (2022)
- [Enhancing Adversarial Training via Reweighting Optimization Trajectory](https://mlsanity.com/paper/2306.14275/) (2023)
- [A Unified Analysis for Finite Weight Averaging](https://mlsanity.com/paper/2411.13169/) (2024)
- [Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles](https://mlsanity.com/paper/2307.04679/) (2023)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Why Does Multi-Epoch Training Help?](https://mlsanity.com/paper/2105.06015/) (2021)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [Mutual Information Learned Regressor: an Information-theoretic Viewpoint of Training Regression Systems](https://mlsanity.com/paper/2211.12685/) (2022)
- [Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimization](https://mlsanity.com/paper/2411.16303/) (2024)

## Abstract (arXiv)

The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in expectation. In this paper, we establish various generalization error bounds with probabilistic guarantee for the SGD. Specifically, for both general nonconvex loss functions and gradient dominant loss functions, we characterize the on-average stability of the iterates generated by SGD in terms of the on-average variance of the stochastic gradients. Such characterization leads to improved bounds for the generalization error for SGD. We then study the regularized risk minimization problem with strongly convex regularizers, and obtain improved generalization error bounds for proximal SGD. With strongly convex regularizers, we further establish the generalization error bounds for nonconvex loss functions under proximal SGD with high-probability guarantee, i.e., exponential concentration in probability.