mlsanityData to 7 Oct 2026

Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent

arXiv 2006.08157 ↗First posted 15 Jun 2020cs.LG stat.MLcited by 118

Not on the map. Why?

Abstract (arXiv)

Recently there are a considerable amount of work devoted to the study of the algorithmic stability and generalization for stochastic gradient descent (SGD). However, the existing stability analysis requires to impose restrictive assumptions on the boundedness of gradients, strong smoothness and convexity of loss functions. In this paper, we provide a fine-grained analysis of stability and generalization for SGD by substantially relaxing these assumptions. Firstly, we establish stability and generalization for SGD by removing the existing bounded gradient assumptions. The key idea is the introduction of a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting using stability approach. Secondly, the smoothness assumption is relaxed by considering loss functions with Holder continuous (sub)gradients for which we show that optimal bounds are still achieved by balancing computation and stability. To our best knowledge, this gives the first-ever-known stability and generalization bounds for SGD with even non-differentiable loss functions. Finally, we study learning problems with (strongly) convex objectives but non-convex loss functions.

Key facts. Cited by 118 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 22; 2023: 25; 2024: 11; 2025: 19; 2026: 27.

118 papers.

Sort:

By area:

  1. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  2. 2022On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyondcited by 37
  3. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  4. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  5. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  6. 2023Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidancecited by 35
  7. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  8. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  9. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  10. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  11. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  12. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
38 more
  1. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  2. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  3. 2022Differentially Private SGDA for Minimax Problemscited by 23
  4. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  5. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  6. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  7. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  8. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  9. 2023Algorithmic Stability of Heavy-Tailed SGD with General Loss Functionscited by 15
  10. 2025A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loopscited by 15
  11. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  12. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  13. 2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
  14. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  15. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 10
  16. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  17. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  18. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  19. 2022On Generalization of Decentralized Learning with Separable Datacited by 8
  20. 2022Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stabilitycited by 8
  21. 2023Tight Risk Bounds for Gradient Descent on Separable Datacited by 7
  22. 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methodscited by 7
  23. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  24. 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
  25. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  26. 2022On the Algorithmic Stability and Generalization of Adaptive Optimization Methodscited by 5
  27. 2023Learning Trajectories are Generalization Indicatorscited by 5
  28. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  29. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  30. 2026Towards a Theoretical Understanding to the Generalization of RLHFcited by 5
  31. 2021Fine-grained Generalization Analysis of Structured Output Predictioncited by 4
  32. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4
  33. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  34. 2024Gentle Local Robustness implies Generalizationcited by 4
  35. 2022Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regressioncited by 3
  36. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  37. 2022Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithmscited by 3
  38. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3

50 most cited of 118 All 118 (JSON)