mlsanityData to 7 Oct 2026

Stability of SGD: Tightness Analysis and Improved Bounds

arXiv 2102.05274 ↗First posted 10 Feb 2021cs.LG math.OC stat.MLcited by 33

Not on the map. Why?

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.

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

Builds on

22 of 44 references.

References · 22

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019On the Convergence of Adam and Beyondcited by 834
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  4. 2017Exploring Generalization in Deep Learningcited by 595
  5. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  6. 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 357
  7. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  8. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  9. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  10. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  11. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  12. 2017Lower Bounds for Finding Stationary Points Icited by 125
10 more
  1. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  2. 2018Privacy Amplification by Iterationcited by 97
  3. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  4. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  5. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  6. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  7. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  8. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  9. 2017Algorithmic stability and hypothesis complexitycited by 39
  10. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 13; 2024: 4; 2025: 5; 2026: 5.

33 papers.

Sort:

By area:

  1. 2023Toward Understanding Generative Data Augmentationcited by 25
  2. 2025FedSWA: Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averagingcited by 25
  3. 2023Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initializationcited by 21
  4. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  5. 2025A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loopscited by 15
  6. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  7. 2022On the generalization of learning algorithms that do not convergecited by 9
  8. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  9. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  10. 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
  11. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  12. 2023Learning Trajectories are Generalization Indicatorscited by 5
21 more
  1. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  2. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  3. 2023A Unified Framework for Generative Data Augmentation: A Comprehensive Surveycited by 4
  4. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4
  5. 2023Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learningcited by 3
  6. 2025Towards Auto-Regressive Next-Token Prediction: In-Context Learning Emerges from Generalizationcited by 3
  7. 2023Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oraclescited by 2
  8. 2024Boosting the Performance of Decentralized Federated Learning via Catalyst Accelerationcited by 2
  9. 2025Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoningcited by 2
  10. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  11. 2023AI Liability Insurance With an Example in AI-Powered E-diagnosis Systemcited by 1
  12. 2024Convex SGD: Generalization Without Early Stoppingcited by 1
  13. 2024OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancementcited by 1
  14. 2025Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneitycited by 1
  15. 2021Improved Learning Rates for Stochastic Optimizationcited by 0
  16. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  17. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0
  18. 2026Generalization error bounds for two-layer neural networks with Lipschitz loss functioncited by 0
  19. 2026Rethinking the Personalized Relaxed Initialization in the Federated Learning: Consistency and Generalizationcited by 0
  20. 2026Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameterscited by 0
  21. 2026Dangerous Liaisons of Convex Learning and Non-Affine Aggregationcited by 0