mlsanityData to 7 Oct 2026

Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems

arXiv 2206.07082 ↗First posted 14 Jun 2022cs.AIcited by 25

Not on the map. Why?

Abstract (arXiv)

Stochastic optimization has found wide applications in minimizing objective functions in machine learning, which motivates a lot of theoretical studies to understand its practical success. Most of existing studies focus on the convergence of optimization errors, while the generalization analysis of stochastic optimization is much lagging behind. This is especially the case for nonconvex and nonsmooth problems often encountered in practice. In this paper, we initialize a systematic stability and generalization analysis of stochastic optimization on nonconvex and nonsmooth problems. We introduce novel algorithmic stability measures and establish their quantitative connection on the gap between population gradients and empirical gradients, which is then further extended to study the gap between the Moreau envelope of the empirical risk and that of the population risk. To our knowledge, these quantitative connection between stability and generalization in terms of either gradients or Moreau envelopes have not been studied in the literature. We introduce a class of sampling-determined algorithms, for which we develop bounds for three stability measures. Finally, we apply these discussions to derive error bounds for stochastic gradient descent and its adaptive variant, where we show how to achieve an implicit regularization by tuning the step sizes and the number of iterations.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 45 of its 78 references that are in the map. First posted on arXiv 14 Jun 2022.

Builds on

45 of 78 references.

References · 45

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2019Introduction to Online Convex Optimizationcited by 793
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2017Renyi Differential Privacycited by 643
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  7. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  8. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  10. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  12. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
33 more
  1. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  2. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  3. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  4. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  5. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  6. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  7. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  8. 2019Sharper bounds for uniformly stable algorithmscited by 91
  9. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  10. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  11. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  12. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  13. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  14. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  15. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  16. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  17. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  18. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  19. 2017Algorithmic stability and hypothesis complexitycited by 39
  20. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  21. 2021Stability and Generalization of Bilevel Programming in Hyperparameter Optimizationcited by 31
  22. 2022Generalization Bounds via Convex Analysiscited by 27
  23. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  24. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
  25. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  26. 2018Graphical Convergence of Subgradients in Nonconvex Optimization and Learningcited by 17
  27. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  28. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  29. 2019McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Boundscited by 15
  30. 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
  31. 2018Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifoldscited by 12
  32. 2022Stability and Risk Bounds of Iterative Hard Thresholdingcited by 7
  33. 2015Stochastic Dual Coordinate Ascent with Adaptive Probabilitiescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 5; 2025: 7; 2026: 10.

25 papers.

Sort:

By area:

  1. 2023Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidancecited by 35
  2. 2025A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loopscited by 15
  3. 2023Learning Trajectories are Generalization Indicatorscited by 5
  4. 2024Stability and Generalization in Free Adversarial Trainingcited by 5
  5. 2025SANet: A Semantic-aware Agentic AI Networking Framework for Cross-layer Optimization in 6Gcited by 5
  6. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  7. 2024Learning Scalable Model Soup on a Single GPU: An Efficient Subspace Training Strategycited by 3
  8. 2024Uniformly Stable Algorithms for Adversarial Training and Beyondcited by 2
  9. 2024Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)cited by 2
  10. 2025Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scalecited by 2
  11. 2025Can Hessian-Based Insights Support Fault Diagnosis in Attention-based Models?cited by 2
  12. 2026MiMuon: Mixed Muon Optimizer with Improved Generalization for Large Modelscited by 2
13 more
  1. 2026Generalization in Nonlinear Least Squares via Learned Feature Geometrycited by 1
  2. 2024Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimizationcited by 0
  3. 2025Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Abilitycited by 0
  4. 2025Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Studycited by 0
  5. 2025Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapescited by 0
  6. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  7. 2026Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysiscited by 0
  8. 2026Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysiscited by 0
  9. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0
  10. 2026HomeAdam: Adam and AdamW Algorithms Sometimes Go Home to Obtain Better Provable Generalizationcited by 0
  11. 2026On-Average Stability of Multipass Preconditioned SGD and Effective Dimensioncited by 0
  12. 2026CLion: Efficient Cautious Lion Optimizer with Enhanced Generalizationcited by 0
  13. 2026Unveiling High-Probability Generalization in Decentralized SGDcited by 0