mlsanityData to 7 Oct 2026

Stability and Generalization of Learning Algorithms that Converge to Global Optima

arXiv 1710.08402 ↗First posted 23 Oct 2017stat.ML cs.IT cs.LGcited by 100

Not on the map. Why?

Abstract (arXiv)

We establish novel generalization bounds for learning algorithms that converge to global minima. We do so by deriving black-box stability results that only depend on the convergence of a learning algorithm and the geometry around the minimizers of the loss function. The results are shown for nonconvex loss functions satisfying the Polyak-Lojasiewicz (PL) and the quadratic growth (QG) conditions. We further show that these conditions arise for some neural networks with linear activations. We use our black-box results to establish the stability of optimization algorithms such as stochastic gradient descent (SGD), gradient descent (GD), randomized coordinate descent (RCD), and the stochastic variance reduced gradient method (SVRG), in both the PL and the strongly convex setting. Our results match or improve state-of-the-art generalization bounds and can easily be extended to similar optimization algorithms. Finally, we show that although our results imply comparable stability for SGD and GD in the PL setting, there exist simple neural networks with multiple local minima where SGD is stable but GD is not.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 21; 2023: 18; 2024: 13; 2025: 13; 2026: 14.

100 papers.

Sort:

By area:

  1. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 172
  2. 2021Dash: Semi-Supervised Learning with Dynamic Thresholdingcited by 147
  3. 2022On the Effectiveness of Parameter-Efficient Fine-Tuningcited by 140
  4. 2022Convex Analysis of the Mean Field Langevin Dynamicscited by 53
  5. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  6. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  7. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  8. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  9. 2021Improved Fine-Tuning by Better Leveraging Pre-Training Datacited by 36
  10. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  11. 2023Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidancecited by 35
  12. 2024LoRA Dropout as a Sparsity Regularizer for Overfitting Controlcited by 35
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. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  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. 2024Robust Semi-supervised Learning by Wisely Leveraging Open-set Datacited by 20
  8. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  9. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  10. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  11. 2024Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functionscited by 17
  12. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  13. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  14. 2025A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loopscited by 15
  15. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  16. 2023On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Levelcited by 14
  17. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 13
  18. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  19. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  20. 2023Generalization Guarantees of Gradient Descent for Multi-Layer Neural Networkscited by 9
  21. 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignmentcited by 9
  22. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  23. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  24. 2022Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stabilitycited by 8
  25. 2021Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stabilitycited by 7
  26. 2022Stability and Risk Bounds of Iterative Hard Thresholdingcited by 7
  27. 2024The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneitycited by 7
  28. 2023On progressive sharpening, flat minima and generalisationcited by 6
  29. 2025Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysiscited by 6
  30. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  31. 2021Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descentcited by 5
  32. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  33. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  34. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4
  35. 2023On the Convergence of the Gradient Descent Method with Stochastic Fixed-point Rounding Errors under the Polyak-Lojasiewicz Inequalitycited by 4
  36. 2023Hypothesis Transfer Learning with Surrogate Classification Losses: Generalization Bounds through Algorithmic Stabilitycited by 4
  37. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  38. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3

50 most cited of 100 All 100 (JSON)