Research map / Optimization / Nonconvex and smooth optimization
Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that constant step-size SGD with Polyak-Ruppert averaging and Richardson-Romberg extrapolation achieves root-MSE bounds with leading term O(n^{-1/2}) and second-order term O(n^{-3/4}), including p-th moment bounds, via geometric ergodicity in a weighted Wasserstein semimetric.
Problem
Reducing the asymptotic bias and improving the non-asymptotic root-MSE of Polyak-Ruppert averaged constant step-size SGD for strongly convex smooth minimization, with known step size n.
Approach
Combine Polyak-Ruppert averaging of constant step-size SGD with Richardson-Romberg extrapolation between step sizes gamma and 2gamma using synchronized noise; analyze SGD iterates as a Markov chain geometrically ergodic under a weighted Wasserstein semimetric, yielding an O(n^{-3/4}) second-order term with the optimal leading covariance term.
Key results
- Root-MSE bound with leading term sqrt(Tr Sigma)/sqrt(n) and second-order term O(n^{-3/4}) for Richardson-Romberg estimator with gamma = n^{-1/2}, matching Root-SGD's best known rate.
- Extends to p-th moment bounds with O(p^{1/2}) leading constant and an n^{-3/4} second-order term via a new Rosenthal-type inequality.
- Numerical 1-D experiment (f(theta)=theta^2+cos theta, averaged over 320 runs) confirms the squared remainder scales as n^{-3/2}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Richardson-Romberg extrapolation to Polyak-Ruppert averaged constant-step-size SGD, using the same noise sequence for both chains | Polyak-Ruppert averaged SGD · Strongly convex minimization | second-order root-MSE term: \mathcal{O}(n^{-2/3}) -> \mathcal{O}(n^{-3/4}) | Helped |
| Add Richardson-Romberg extrapolation to Polyak-Ruppert averaged constant-step-size SGD | Polyak-Ruppert averaged SGD · Strongly convex minimization | p-th moment error bound second-order term: \mathcal{O}(n^{-3/4}) | Helped |
| Use the same noise sequence for the step-size-\gamma and step-size-2\gamma chains instead of different random sequences | Richardson-Romberg averaged SGD · Strongly convex minimization | leading component of the MSE | Helped |
Experimental setup
Metrics: root mean-squared error squared error scaling
Baselines: Polyak-Ruppert averaged SGD Root-SGD
Builds on: Polyak-Ruppert averaging Richardson-Romberg extrapolation Root-SGD
Closest papers by meaning
- An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias (NeurIPS 2021 · similarity 0.91)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.90)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.90)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.90)
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.90)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.