When optimizing a machine learning model, training a reinforcement learning agent, or simulating a complex stochastic system, choosing the right step size (or learning rate) involves a fundamental trade-off.
Traditional stochastic approximation theory suggests we should use a diminishing step size ($\alpha_t \to 0$). While this guarantees that the algorithm will eventually converge to the exact solution, it comes at a steep cost: convergence is painfully slow, and the algorithm loses its ability to track changes in time-varying environments (Moulines et al.).
To avoid this, practitioners almost universally prefer a constant step size ($\alpha$). Constant step sizes converge exponentially fast and can track non-stationary targets. However, they hit a persistent bias floor—an asymptotic systematic error proportional to the step size itself.
Is it possible to achieve the lightning-fast convergence of a constant step size while completely eliminating this systematic bias? A rapidly growing body of research shows that the answer is yes, achieved by borrowing a classic numerical technique: Richardson-Romberg extrapolation.
The Intuition: Turning Systematic Error into a Parameter
The core insight behind Richardson-Romberg extrapolation is that the asymptotic bias of a constant-stepsize algorithm is not chaotic noise. Instead, it is a highly structured, predictable function of the step size $\alpha$.
For a wide class of stochastic algorithms, the steady-state expectation of our parameter estimate, $\theta_\alpha$, can be written as a smooth Taylor-like expansion around the true parameter $\theta^*$:
$$\mathbb{E}[\theta_\alpha] = \theta^* + \alpha B_1 + \alpha^2 B_2 + \alpha^3 B_3 + \dots$$
Here, $B_1, B_2, \dots$ are constant bias coefficients determined by the geometry of the objective function and the nature of the noise, but crucially, they do not depend on $\alpha$.
Because this error floor is predictable, we can treat $\alpha$ as a manageable parameter and set up a system of equations to cancel the error out. Imagine running two instances of your algorithm completely in parallel:
- One chain with a step size of $\alpha$, yielding an estimate $\theta_\alpha$.
- A second chain with a step size of $2\alpha$, yielding an estimate $\theta_{2\alpha}$.
If we look at their expected values, we see a clear path to cancellation:
$$\mathbb{E}[\theta_\alpha] = \theta^* + \alpha B_1 + \alpha^2 B_2 + \dots$$ $$\mathbb{E}[\theta_{2\alpha}] = \theta^* + 2\alpha B_1 + 4\alpha^2 B_2 + \dots$$
To eliminate the dominant error term ($\alpha B_1$), we simply take a weighted difference between the two parallel runs:
$$\theta_{RR} = 2\theta_\alpha - \theta_{2\alpha}$$
When we calculate the expectation of this new extrapolated estimator, the first-order bias vanishes entirely:
$$\mathbb{E}[\theta_{RR}] = 2(\theta^* + \alpha B_1 + \alpha^2 B_2) - (\theta^* + 2\alpha B_1 + 4\alpha^2 B_2) = \theta^* - 2\alpha^2 B_2 + \dots$$
By computing a simple weighted average of two parallel processes, the bias floor drops from linear ($\mathcal{O}(\alpha)$) to quadratic ($\mathcal{O}(\alpha^2)$). As shown by Huo et al., this mechanism can be generalized to $m$ distinct step sizes to systematically cancel out higher-order terms, reducing the bias floor to $\mathcal{O}(\alpha^m)$.
Trajectory 1 (Step size 2α): ◯───────◯───────◯───────◯ -> Converges to θ* + 2αB₁
Trajectory 2 (Step size α): ◯───◯───◯───◯───◯───◯───◯ -> Converges to θ* + αB₁
│ │ │
[ Weighted Combination: 2θ_α - θ_2α ]
│ │ │
▼ ▼ ▼
Extrapolated Estimator: ●───────●───────●───────● -> Converges to θ* + O(α²)
Why Does the Bias Behave So Smoothly?
The reason this expansion holds boils down to the relationship between constant-stepsize algorithms and Markov chains. When an algorithm uses a fixed step size, its updates form a homogeneous Markov chain. Under mild regularity conditions, this chain converges to a unique stationary distribution.
Durmus established a rigorous connection between constant-stepsize Stochastic Gradient Descent (SGD) and Markov chain ergodic theory, proving that the discretization error can be smoothly expanded in powers of $\alpha$. This means that the long-term behavior of the algorithm shifts smoothly as a function of the step size, guaranteeing that the $B_1, B_2$ coefficients remain stable across different scales.
This smooth structure persists even under challenging real-world conditions:
- Markovian Noise: In many applications, like reinforcement learning, data samples are sequentially correlated rather than independent. Allmeier et al. and Naumov et al. demonstrated that while dependent noise shifts the stationary distribution, the bias remains a predictable function of $\alpha$, making Richardson-Romberg extrapolation highly effective at removing the correlated noise floor.
- Nonlinearity and Memory: When nonlinearity and data memory interact, they create a complex "compound bias." However, Huo et al. proved that multi-stepsize extrapolation successfully disentangles this interaction, eliminating systematic errors where standard tail-averaging fails.
Applications Across the Stochastic Landscape
Because Richardson-Romberg extrapolation acts as a meta-wrapper around existing iterative algorithms, it has recently been applied across several distinct domains to bypass traditional performance bottlenecks.
Reinforcement Learning and Q-Learning
Constant stepsizes are vital in reinforcement learning for tracking non-stationary policies. However, algorithms like Q-learning suffer from significant asymptotic bias due to the non-smooth max operator. Xie et al. showed that Richardson-Romberg extrapolation allows agents to maintain the rapid convergence of large stepsizes while numerically canceling out the resulting error floor. For non-smooth contractive systems where the bias scales with $\sqrt{\alpha}$ rather than $\alpha$, the authors adapt the parallel scaling weights to successfully eliminate the dominant error terms (Huo et al.).
Optimization and Data Shuffling
In optimization, combining extrapolation with other algorithmic tricks yields powerful synergies. For instance, Sheshukova et al. proved that combining Polyak-Ruppert tail-averaging with Richardson-Romberg extrapolation achieves minimax-optimal convergence rates for strongly convex problems. Taking this a step further, Emmanouilidis et al. demonstrated that combining Random Reshuffling (shuffling data without replacement) with step-size extrapolation results in a synergistic "cubic" reduction in asymptotic bias ($\mathcal{O}(\gamma^3)$), reaching a closer neighborhood of the optimum than either technique could achieve independently.
Distributed and Federated Learning
In Federated Learning, algorithms like Federated Averaging (FedAvg) suffer from severe client-drift bias due to data heterogeneity across local devices. To fix this without adding heavy memory overhead, Mangold et al. introduced Federated Richardson-Romberg Extrapolation. By running parallel optimization processes with different local step sizes and combining their final parameters, the server removes the primary error term without requiring clients to store auxiliary variables.
Sampling and Physical Simulations
The principle extends naturally to Bayesian inference and continuous-time simulations. Durmus et al. applied the technique to Stochastic Gradient Markov Chain Monte Carlo (SGLD), showing that a weighted combination of two parallel chains cancels out first-order discretization bias, achieving high-order sampling precision using only simple first-order integrators. Similar multi-resolution bias cancellation principles have been successfully deployed to accelerate stochastic chemical kinetics simulations (Székely et al.) and to optimize deterministic quantization boundaries in variational inference (Dib).
Summary
Richardson-Romberg extrapolation provides a elegant solution to one of the most persistent trade-offs in stochastic optimization. By recognizing that the bias floor of constant-stepsize algorithms is a smooth, deterministic function of the step size, it allows practitioners to run simple, fast-converging algorithms in parallel and mathematically subtract their systematic errors. The result is a powerful paradigm shift: high-precision solutions achieved with the speed and simplicity of a constant learning rate.
Key Foundational Work
On recursive estimation for time varying autoregressive processes (2006) — contributed 1 concept elements to this direction.
Efficient simulation of stochastic chemical kinetics with the Stochastic Bulirsch-Stoer extrapolation method (2014) — contributed 1 concept elements to this direction.