# Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains

arXiv: https://arxiv.org/abs/1707.06386 · HTML: https://mlsanity.com/paper/1707.06386/

## Key facts

- Cited by 88 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2017.

## Built on by (most cited first, 30 of 88)

- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks](https://mlsanity.com/paper/2302.05882/) (2023)
- [Strength of Minibatch Noise in SGD](https://mlsanity.com/paper/2102.05375/) (2021)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning](https://mlsanity.com/paper/2106.00797/) (2021)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD](https://mlsanity.com/paper/2305.18502/) (2023)
- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?](https://mlsanity.com/paper/2307.14642/) (2023)
- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [On the generalization of learning algorithms that do not converge](https://mlsanity.com/paper/2208.07951/) (2022)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [Online Learning to Transport via the Minimal Selection Principle](https://mlsanity.com/paper/2202.04732/) (2022)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)

## Abstract (arXiv)

We consider the minimization of an objective function given access to unbiased estimates of its gradient through stochastic gradient descent (SGD) with constant step-size. While the detailed analysis was only performed for quadratic functions, we provide an explicit asymptotic expansion of the moments of the averaged SGD iterates that outlines the dependence on initial conditions, the effect of noise and the step-size, as well as the lack of convergence in the general (non-quadratic) case. For this analysis, we bring tools from Markov chain theory into the analysis of stochastic gradient. We then show that Richardson-Romberg extrapolation may be used to get closer to the global optimum and we show empirical improvements of the new extrapolation scheme.