mlsanityData to 14 Oct 2026

Convergence and concentration properties of constant step-size SGD through Markov chains

arXiv 2306.11497 ↗First posted 20 Jun 2023stat.ML cs.LG math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

We consider the optimization of a smooth and strongly convex objective using constant step-size stochastic gradient descent (SGD) and study its properties through the prism of Markov chains. We show that, for unbiased gradient estimates with mildly controlled variance, the iteration converges to an invariant distribution in total variation distance. We also establish this convergence in Wasserstein-2 distance under a relaxed assumption on the gradient noise distribution compared to previous work. Our analysis shows that the SGD iterates and their invariant limit distribution inherit sub-Gaussian or sub-exponential concentration properties when these hold true for the gradient. This allows the derivation of high-confidence bounds for the final estimate. Finally, under such conditions in the linear case, we obtain a dimension-free deviation bound for the Polyak-Ruppert average of a tail sequence. All our results are non-asymptotic and their consequences are discussed through a few applications.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 28 of its 99 references that are in the map. First posted on arXiv 20 Jun 2023.

Builds on

28 of 99 references.

References · 28

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  4. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  5. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  6. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  7. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  8. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  9. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  10. 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 97
  11. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  12. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
16 more
  1. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  2. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  3. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  4. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  5. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  6. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 48
  7. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  8. 2014Logistic Regression: Tight Bounds for Stochastic and Online Optimizationcited by 31
  9. 2018Iterate averaging as regularization for stochastic gradient descentcited by 27
  10. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 27
  11. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 26
  12. 2019An improper estimator with optimal excess risk in misspecified density estimation and logistic regressioncited by 25
  13. 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 21
  14. 2017Exponential convergence of testing error for stochastic gradient methodscited by 13
  15. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  16. 2015MCMC-Based Inference in the Era of Big Data: A Fundamental Analysis of the Convergence Complexity of High-Dimensional Chainscited by 7

Built on by

Cited by year (2026 to 14 Oct)

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

11 papers.

  1. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
  2. 2025A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regressioncited by 3
  3. 2023The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learningcited by 2
  4. 2025Statistical Guarantees for High-Dimensional Stochastic Gradient Descentcited by 2
  5. 2024Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descentcited by 0
  6. 2025Central Limit Theorems for Stochastic Gradient Descent Quantile Estimatorscited by 0
  7. 2026Accurate Large-sample Uncertainty Quantification using Stochastic Gradient Markov Chain Monte Carlocited by 0
  8. 2026Geometric Moment Contraction for Stochastic Nesterov Accelerationcited by 0
  9. 2026Sharp Stationary Gaussian Approximation for Constant-Stepsize SGDcited by 0
  10. 2026Gaussian Limits for SGD Without Stationary Momentscited by 0
  11. 2026Limit Theory for Online Expectile Estimation under Short and Long Range Dependencecited by 0