# Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 7 Oct 2024.

## Builds on (most cited first, 17 of 17)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [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)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [Rosenthal-type inequalities for linear statistics of Markov chains](https://mlsanity.com/paper/2303.05838/) (2023)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize](https://mlsanity.com/paper/2405.16732/) (2024)
- [Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference](https://mlsanity.com/paper/2312.10894/) (2023)
- [Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA](https://mlsanity.com/paper/2404.06023/) (2024)

## Built on by (most cited first, 6 of 6)

- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [Refined Analysis of Federated Averaging and Federated Richardson-Romberg](https://mlsanity.com/paper/2412.01389/) (2024)
- [Accelerating Single-Pass SGD for Generalized Linear Prediction](https://mlsanity.com/paper/2603.01951/) (2026)
- [Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling](https://mlsanity.com/paper/2609.06196/) (2026)

## Abstract (arXiv)

We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We significantly extend previous results by providing an expansion of the mean-squared error of the resulting estimator with respect to the number of iterations n. We show that the root mean-squared error can be decomposed into the sum of two terms: a leading one of order O(n-1/2) with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order O(n-3/4), where the power 3/4 is best known. We also extend this result to the higher-order moment bounds. Our analysis relies on the properties of the SGD iterates viewed as a time-homogeneous Markov chain. In particular, we establish that this chain is geometrically ergodic with respect to a suitably defined weighted Wasserstein semimetric.