Data to 14 Oct 2026

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

arXiv 1707.06386 ↗First posted 20 Jul 2017stat.ML math.OCcited by 88

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 14; 2022: 10; 2023: 13; 2024: 14; 2025: 16; 2026: 21.

88 papers.

Sort:

By area:

2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 70
2023From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networkscited by 43
2021Strength of Minibatch Noise in SGDcited by 39
2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 30
2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
2021QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learningcited by 26
2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17

38 more

2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
2023Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGDcited by 15
2026A Defense of the Quadratic Modelcited by 14
2021Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterizationcited by 13
2021On Riemannian Stochastic Approximation Schemes with Fixed Step-Sizecited by 12
2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 11
2023Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?cited by 10
2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 10
2022On the generalization of learning algorithms that do not convergecited by 9
2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
2022Online Learning to Transport via the Minimal Selection Principlecited by 6
2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 6
2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
2021Exponential escape efficiency of SGD from sharp minima in non-stationary regimecited by 5
2023Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inferencecited by 5
2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
2021Repurposing Pretrained Models for Robust Out-of-domain Few-Shot Learningcited by 4
2022Tuning Stochastic Gradient Algorithms for Statistical Inference via Large-Sample Asymptoticscited by 4
2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
2023Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descentcited by 3
2024Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SAcited by 3
2025Randomised Splitting Methods and Stochastic Gradient Descentcited by 3
2025A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regressioncited by 3
2024Score-based Generative Models with Adaptive Momentumcited by 2
2024Can LLMs predict the convergence of Stochastic Gradient Descent?cited by 2
2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
2025Statistical Guarantees for High-Dimensional Stochastic Gradient Descentcited by 2
2026Convergence Rates for Distribution Matching with Sliced Optimal Transportcited by 2
2026A Polyak-Ruppert Central Limit Theorem for SA-Adam with Momentum and Non-Convergent Adaptive Preconditioningcited by 2
2021Quantifying the mini-batching error in Bayesian inference for Adaptive Langevin dynamicscited by 1
2022A Variance-Reduced Stochastic Accelerated Primal Dual Algorithmcited by 1
2022Reinforcement Teachingcited by 1

50 most cited of 88 All 88 (JSON)