# Stability of SGD: Tightness Analysis and Improved Bounds

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 10 Feb 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [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)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)

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

- [Toward Understanding Generative Data Augmentation](https://mlsanity.com/paper/2305.17476/) (2023)
- [FedSWA: Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averaging](https://mlsanity.com/paper/2507.20016/) (2025)
- [Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization](https://mlsanity.com/paper/2306.05706/) (2023)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loops](https://mlsanity.com/paper/2502.18865/) (2025)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [On the generalization of learning algorithms that do not converge](https://mlsanity.com/paper/2208.07951/) (2022)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent](https://mlsanity.com/paper/2305.12056/) (2023)
- [Towards Understanding Generalization via Decomposing Excess Risk Dynamics](https://mlsanity.com/paper/2106.06153/) (2021)
- [Learning Trajectories are Generalization Indicators](https://mlsanity.com/paper/2304.12579/) (2023)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [A Unified Framework for Generative Data Augmentation: A Comprehensive Survey](https://mlsanity.com/paper/2310.00277/) (2023)
- [Generalization Error Matters in Decentralized Learning Under Byzantine Attacks](https://mlsanity.com/paper/2407.08632/) (2024)
- [Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learning](https://mlsanity.com/paper/2310.03461/) (2023)
- [Towards Auto-Regressive Next-Token Prediction: In-Context Learning Emerges from Generalization](https://mlsanity.com/paper/2502.17024/) (2025)
- [Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles](https://mlsanity.com/paper/2307.04679/) (2023)
- [Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration](https://mlsanity.com/paper/2410.07272/) (2024)
- [Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning](https://mlsanity.com/paper/2506.18020/) (2025)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [AI Liability Insurance With an Example in AI-Powered E-diagnosis System](https://mlsanity.com/paper/2306.01149/) (2023)
- [Convex SGD: Generalization Without Early Stopping](https://mlsanity.com/paper/2401.04067/) (2024)
- [OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancement](https://mlsanity.com/paper/2410.06482/) (2024)
- [Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneity](https://mlsanity.com/paper/2506.09438/) (2025)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)
- [Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent](https://mlsanity.com/paper/2308.09430/) (2023)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)
- [Generalization error bounds for two-layer neural networks with Lipschitz loss function](https://mlsanity.com/paper/2604.06281/) (2026)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) based methods have been widely used for training large-scale machine learning models that also generalize well in practice. Several explanations have been offered for this generalization performance, a prominent one being algorithmic stability [18]. However, there are no known examples of smooth loss functions for which the analysis can be shown to be tight. Furthermore, apart from the properties of the loss function, data distribution has also been shown to be an important factor in generalization performance. This raises the question: is the stability analysis of [18] tight for smooth functions, and if not, for what kind of loss functions and data distributions can the stability analysis be improved? In this paper we first settle open questions regarding tightness of bounds in the data-independent setting: we show that for general datasets, the existing analysis for convex and strongly-convex loss functions is tight, but it can be improved for non-convex loss functions. Next, we give a novel and improved data-dependent bounds: we show stability upper bounds for a large class of convex regularized loss functions, with negligible regularization parameters, and improve existing data-dependent bounds in the non-convex setting. We hope that our results will initiate further efforts to better understand the data-dependent setting under non-convex loss functions, leading to an improved understanding of the generalization abilities of deep networks.