mlsanityData to 14 Oct 2026

Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent

arXiv 2305.12056 ↗First posted 20 May 2023stat.ML cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

Algorithmic stability is an important notion that has proven powerful for deriving generalization bounds for practical algorithms. The last decade has witnessed an increasing number of stability bounds for different algorithms applied on different classes of loss functions. While these bounds have illuminated various properties of optimization algorithms, the analysis of each case typically required a different proof technique with significantly different mathematical tools. In this study, we make a novel connection between learning theory and applied probability and introduce a unified guideline for proving Wasserstein stability bounds for stochastic optimization algorithms. We illustrate our approach on stochastic gradient descent (SGD) and we obtain time-uniform stability bounds (i.e., the bound does not increase with the number of iterations) for strongly convex losses and non-convex losses with additive noise, where we recover similar results to the prior art or extend them to more general cases by using a single proof technique. Our approach is flexible and can be generalizable to other popular optimizers, as it mainly requires developing Lyapunov functions, which are often readily available in the literature. It also illustrates that ergodicity is an important component for obtaining time-uniform bounds -- which might not be achieved for convex or non-convex losses unless additional noise is injected to the iterates. Finally, we slightly stretch our analysis technique and prove time-uniform bounds for SGD under convex and non-convex losses (without additional additive noise), which, to our knowledge, is novel.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 29 of its 43 references that are in the map. First posted on arXiv 20 May 2023.

Builds on

29 of 43 references.

References · 29

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  2. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  3. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  5. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 163
  6. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  7. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 119
  8. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  9. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  10. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  11. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  12. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
17 more
  1. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  2. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  3. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
  4. 2017Algorithmic stability and hypothesis complexitycited by 39
  5. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  6. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  7. 2018Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Accelerationcited by 31
  8. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  9. 2015Perturbation theory for Markov chains via Wasserstein distancecited by 18
  10. 2019A Universally Optimal Multistage Accelerated Stochastic Gradient Methodcited by 17
  11. 2019Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distancescited by 16
  12. 2023Algorithmic Stability of Heavy-Tailed SGD with General Loss Functionscited by 15
  13. 2018Robust Accelerated Gradient Methods for Smooth Strongly Convex Functionscited by 12
  14. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  15. 2022Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methodscited by 10
  16. 2019Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networkscited by 9
  17. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3; 2025: 2.

6 papers.

  1. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4
  2. 2023Generalization Bounds for Label Noise Stochastic Gradient Descentcited by 3
  3. 2024Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clippingcited by 3
  4. 2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
  5. 2025Stability, Complexity and Data-Dependent Worst-Case Generalization Boundscited by 1
  6. 2024Aortic root landmark localization with optimal transport loss for heatmap regressioncited by 0