Research map / Optimization / Nonconvex and smooth optimization
High-Order Error Bounds for Markovian LSA with Richardson–Romberg Extrapolation
Ilya Levin, Alexey Naumov, Sergey Samsonov
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add Richardson-Romberg extrapolation on top of Polyak-Ruppert averaging | Markovian LSA with constant step size · 2-state Markov chain synthetic LSA (a=0.3, 400 trajectories) | MSE of averaged iterate | Improved |
| set step size eps = n^(-1/2) instead of larger step sizes (ablation) | Richardson-Romberg iterates · 2-state Markov chain synthetic LSA | error | Improved |
| use eps = n^(-1/2) with plain Polyak-Ruppert averaging (no RR) (ablation) | Polyak-Ruppert averaged LSA · 2-state Markov chain synthetic LSA | error | Hurt |
Closest papers by meaning
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.88)
- Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning (NeurIPS 2024 · similarity 0.87)
- Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference (AAAI 2024 · similarity 0.87)
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging (NeurIPS 2025 · similarity 0.87)
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.86)
- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise (NeurIPS 2024 · similarity 0.86)
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.
