# Convergence and concentration properties of constant step-size SGD through Markov chains arXiv: https://arxiv.org/abs/2306.11497 ยท HTML: https://mlsanity.com/paper/2306.11497/ ## 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 (most cited first, 28 of 28) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016) - [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017) - [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017) - [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018) - [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019) - [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013) - [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013) - [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020) - [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017) - [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018) - [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017) - [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020) - [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016) - [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020) - [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023) - [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013) - [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020) - [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013) - [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014) - [Iterate averaging as regularization for stochastic gradient descent](https://mlsanity.com/paper/1802.08009/) (2018) - [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019) - [A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)](https://mlsanity.com/paper/1710.09430/) (2017) - [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019) - [High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise](https://mlsanity.com/paper/2302.05437/) (2023) - [Exponential convergence of testing error for stochastic gradient methods](https://mlsanity.com/paper/1712.04755/) (2017) - [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021) - [MCMC-Based Inference in the Era of Big Data: A Fundamental Analysis of the Convergence Complexity of High-Dimensional Chains](https://mlsanity.com/paper/1508.00947/) (2015) ## Built on by (most cited first, 11 of 11) - [Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2410.05106/) (2024) - [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025) - [The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning](https://mlsanity.com/paper/2308.03215/) (2023) - [Statistical Guarantees for High-Dimensional Stochastic Gradient Descent](https://mlsanity.com/paper/2510.12013/) (2025) - [Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent](https://mlsanity.com/paper/2412.11341/) (2024) - [Central Limit Theorems for Stochastic Gradient Descent Quantile Estimators](https://mlsanity.com/paper/2503.02178/) (2025) - [Accurate Large-sample Uncertainty Quantification using Stochastic Gradient Markov Chain Monte Carlo](https://mlsanity.com/paper/2606.00293/) (2026) - [Geometric Moment Contraction for Stochastic Nesterov Acceleration](https://mlsanity.com/paper/2609.31303/) (2026) - [Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD](https://mlsanity.com/paper/2609.39144/) (2026) - [Gaussian Limits for SGD Without Stationary Moments](https://mlsanity.com/paper/2610.05599/) (2026) - [Limit Theory for Online Expectile Estimation under Short and Long Range Dependence](https://mlsanity.com/paper/2610.16030/) (2026) ## 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.