mlsanityData to 7 Oct 2026

Data-Dependent Stability of Stochastic Gradient Descent

arXiv 1703.01678 ↗First posted 5 Mar 2017cs.LGcited by 90

Not on the map. Why?

Abstract (arXiv)

We establish a data-dependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distribution-free algorithmic stability results for SGD which depend on the worst-case constants. By virtue of the data-dependent argument, our bounds provide new insights into learning with SGD on convex and non-convex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the non-convex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple data-driven strategy to stabilize SGD by pre-screening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.

Key facts. Cited by 90 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 24; 2023: 17; 2024: 9; 2025: 9; 2026: 15.

90 papers.

Sort:

By area:

  1. 2022On the Effectiveness of Parameter-Efficient Fine-Tuningcited by 140
  2. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  3. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  4. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  5. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  6. 2021Leave-one-out Unfairnesscited by 36
  7. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  8. 2023Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidancecited by 35
  9. 2024LoRA Dropout as a Sparsity Regularizer for Overfitting Controlcited by 35
  10. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  11. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  12. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
38 more
  1. 2022On the Generalization Mystery in Deep Learningcited by 25
  2. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  3. 2023Toward Understanding Generative Data Augmentationcited by 25
  4. 2022Differentially Private SGDA for Minimax Problemscited by 23
  5. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  6. 2023Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initializationcited by 21
  7. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  8. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  9. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  10. 2022AANG: Automating Auxiliary Learningcited by 12
  11. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  12. 2024Generalization Bound and New Algorithm for Clean-Label Backdoor Attackcited by 11
  13. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  14. 2022On the generalization of learning algorithms that do not convergecited by 9
  15. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  16. 2021TATL: Task Agnostic Transfer Learning for Skin Attributes Detectioncited by 8
  17. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  18. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  19. 2022Stability and Risk Bounds of Iterative Hard Thresholdingcited by 7
  20. 2022On the Importance of Gradient Norm in PAC-Bayesian Boundscited by 6
  21. 2023On progressive sharpening, flat minima and generalisationcited by 6
  22. 2021What training reveals about neural network complexitycited by 5
  23. 2021Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descentcited by 5
  24. 2022On generalization bounds for deep networks based on loss surface implicit regularizationcited by 5
  25. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  26. 2022On the Algorithmic Stability and Generalization of Adaptive Optimization Methodscited by 5
  27. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  28. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  29. 2026Towards a Theoretical Understanding to the Generalization of RLHFcited by 5
  30. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4
  31. 2023A Unified Framework for Generative Data Augmentation: A Comprehensive Surveycited by 4
  32. 2024Data-Dependent Stability Analysis of Adversarial Trainingcited by 4
  33. 2021PAC Bayesian Performance Guarantees for Deep (Stochastic) Networks in Medical Imagingcited by 3
  34. 2022Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithmscited by 3
  35. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  36. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  37. 2026Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimizationcited by 3
  38. 2022Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixturescited by 2

50 most cited of 90 All 90 (JSON)