Acceleration with stale gradients

In an asynchronous system the gradient that arrives at step k was computed τ steps ago. This page runs momentum methods on such stale gradients and computes, exactly, how fast each one can converge. Heavy ball and Nesterov’s method, retuned as well as they can be for the delay, fall back toward the rate of gradient descent. DREAM, a generalized momentum method whose three parameters are set from the delay τ and the condition number κ by the formulas of Gürbüzbalaban, Rafi, Aybat and Bajwa (arXiv:2610.37444, 2026), keeps the accelerated √κ dependence.

What is being computed

The problem. The playground minimizes the quadratic $f(x) = \tfrac12 x^\top H x$ on the plane, where $H = R\,\mathrm{diag}(\mu, L)\,R^\top$ with $\mu = 1$ , $L = \kappa$ , and $R$ a rotation by 35°. So $f$ is $L$ -smooth and $\mu$ -strongly convex with condition number $\kappa = L/\mu$ , its minimizer is $x^\star = 0$ , and its level sets are the tilted ellipses drawn in panel A. The chips set $\kappa$ and the delay $\tau$ .

The delay. At iteration $k$ the method does not receive the gradient at its current query point but the gradient at the point it queried $\tau$ iterations earlier, $\nabla f(y_{k-\tau})$ , and it takes a step with that stale gradient at every iteration rather than waiting for a fresh one. This is the fixed-delay, non-idling model of the paper; $\tau = 0$ is the classical setting.

The methods. Every method on this page is the delayed generalized momentum method (GMM) with constant parameters:

\begin{gathered} y_k = x_k + \nu\,(x_k - x_{k-1}), \\ x_{k+1} = x_k - \alpha\,\nabla f(y_{k-\tau}) + \beta\,(x_k - x_{k-1}), \end{gathered}

where $\alpha > 0$ is the stepsize, $\beta \ge 0$ the momentum, and $\nu \ge 0$ the extrapolation: how far beyond the current iterate, along the last step, the gradient is queried. The classical methods are the special cases gradient descent ( $\beta = \nu = 0$ ), heavy ball ( $\nu = 0$ ) and Nesterov’s method ( $\nu = \beta$ ). All runs start from the constant history $x_{-\tau-1} = \dots = x_0$ at the point marked start. The table shows $\alpha L$ rather than $\alpha$ , since the stepsize is naturally measured in units of $1/L$ .

Definition: DREAM

DREAM (delay-resistant acceleration with momentum) is the delayed generalized momentum method above with the parameters introduced in Gürbüzbalaban, Rafi, Aybat and Bajwa, arXiv:2610.37444, which depend only on the delay $\tau$ , the smoothness constant $L$ and the condition number $\kappa$ :

\begin{gathered} M = 2\tau + 1, \qquad \alpha = \frac{1}{M^2 L}, \\ \beta = 1 - \frac{2}{M\sqrt{\kappa}}, \qquad \nu = M - \tfrac12 . \end{gathered}

The extrapolation is set to a little more than twice the delay, which is what keeps the gradient query ahead of the iterate despite the staleness; the paper shows that the limiting recurrence governing the rate as $\kappa \to \infty$ can be stable only when $\nu > \tau$ . With these parameters the paper proves the rate $\rho \le 1 - 1/(2M\sqrt{\kappa})$ on quadratics for all large enough $\kappa$ , and a rate of the same form, $1 - c/(M\sqrt\kappa)$ , on every $L$ -smooth, $\mu$ -strongly convex function. For $\tau = 1$ the paper also gives a sharper tuning,

\begin{gathered} \alpha = \frac{1 - q^2/2}{4L}, \qquad \beta = 1 - q + \frac{q^2}{2}, \\ \nu = \frac{2\,(1 - q + q^2/4)}{1 - q^2/2}, \qquad q = \frac{1}{\sqrt\kappa}, \end{gathered}

whose worst-case rate is exactly $1 - 1/(2\sqrt\kappa)$ for every $\kappa \ge 1$ ; it appears as DREAM, one-step tuning when $\tau = 1$ is selected. Nothing about DREAM is tuned on this page: the parameters are those formulas.

How the classical methods are tuned. To compare fairly, gradient descent, heavy ball and Nesterov’s method are each given the stepsize and momentum that minimize their worst-case rate $\rho$ (defined next) for the selected $\tau$ and $\kappa$ , found by numerical search over all stable parameters, as in the paper’s experiments. Without delay this recovers the familiar accelerated tunings; with delay it finds the best each method can do.

The rate. Along an eigenvector of $H$ with eigenvalue $\lambda$ , the error of the delayed GMM obeys a linear recurrence of order $\tau + 2$ whose characteristic polynomial is

\begin{gathered} P_{\tau,\delta}(z) = z^{\tau}(z-1)(z-\beta) + \delta\,\big((1+\nu)\,z - \nu\big), \\ \delta = \alpha\lambda . \end{gathered}

Its roots are the poles of panel B. The method converges on every quadratic with spectrum in $[\mu, L]$ if and only if the worst-case spectral radius

\rho = \max_{\lambda \in [\mu, L]}\;\max\{\,|z| : P_{\tau,\alpha\lambda}(z) = 0\,\}

is below one, and then the error decays like $\rho^k$ (up to a polynomial factor). This $\rho$ is the rate in the table, computed by finding the roots on a fine grid of curvatures $\lambda$ ; $1/(1-\rho)$ is the number of iterations per e-fold, the iterations needed to shrink the error by a factor $e$ ; and $1 - \rho$ is the spectral gap of panel C. A method is accelerated when its gap scales like $\kappa^{-1/2}$ as $\kappa$ grows, as heavy ball and Nesterov’s method do without delay, and not accelerated when it scales like $\kappa^{-1}$ , as gradient descent does. On the log–log axes of panel C these are lines of slope $-\tfrac12$ and $-1$ ; the slope fitted to each curve over $\kappa \ge 100$ is printed in the panel.

Your tuning. The sliders set $(\alpha L, \beta, \nu)$ of a delayed GMM of your own; its worst-case rate is computed live from the same polynomial, and it joins the panels as a fifth method when switched on.

What to try

The page opens at a delay of τ = 2 and κ = 100. Press Play: Nesterov and heavy ball, each with the parameters that minimize its worst-case rate at this delay, creep along the valley, and DREAM arrives first. Turn on gradient descent and it lands exactly on heavy ball: at any positive delay, the heavy ball that converges fastest has no momentum at all. Switch τ to 0 and the order changes: without delay, heavy ball and Nesterov are the accelerated methods. Then step τ up through 1, 2, 3 and watch panel C, where the slope of each curve is the exponent of κ in the spectral gap: heavy ball drops to slope −1 at the first step of delay, Nesterov holds an intermediate −2/3 at τ = 1 and then drops too, and DREAM stays near −½ at every delay.

Then make your own method. Start from DREAM, lower the extrapolation ν below τ, and watch the rate ρ reach 1: the paper proves that ν must exceed τ for the limiting recurrence to be stable at all. Start from Nesterov, which is the case ν = β, and try to buy speed by increasing the stepsize or the momentum; panel B shows the τ + 2 roots that have to stay inside the unit circle.

The quadratic f(x) = ½ xᵀHx with eigenvalues μ = 1 and L = κ, tilted by 35°; one τ-step-old gradient per update

delay τ

κ = L/μ

methods

Your tuning of the delayed momentum method:start fromρ = 0.9847

stepsize αL 0.0400momentum β 0.9600extrapolation ν 4.50

Method	αL	β	ν	worst-case rate ρ	iterations per e-fold
DREAM	0.0400	0.9600	4.500	0.9847	65.4

All rows are the delayed generalized momentum method y_k = x_k + ν(x_k − x_k−1), x_k+1 = x_k − α∇f(y_k−τ) + β(x_k − x_k−1), with different parameters (the definitions are above the playground). ρ is the worst-case spectral radius of the delayed recurrence over all curvatures in [μ, L]: the error shrinks like ρ^k, and 1/(1 − ρ) is the number of iterations per e-fold. Gradient descent (β = ν = 0), heavy ball (ν = 0) and Nesterov (ν = β) use the parameters with the smallest ρ found by numerical search for this delay and κ. DREAM uses the formulas of Gürbüzbalaban, Rafi, Aybat and Bajwa (arXiv:2610.37444) with M = 2τ + 1 = 5: αL = 1/M² = 0.0400, β = 1 − 2/(M√κ) = 0.9600, ν = M − ½ = 4.5; its guaranteed rate for large κ is 1 − 1/(2M√κ) = 0.9900.

A The race: the same stale gradients, different accelerations

k = 0 of 752

Left: iterates on the level sets of f, which the methods see only through gradients that are τ iterations old. Right: the objective error, on a log scale, against the number of updates; a straight line is a linear rate, and its slope is log ρ. The horizon is about 11.5 e-folds (an error of 10⁻⁵) for the slowest method shown; a curve that reaches the bottom has converged to that accuracy.

B The poles: roots of the characteristic polynomial at each method’s worst curvature

For each method, the roots of P_τ,δ(z) = z^τ(z − 1)(z − β) + δ((1 + ν)z − ν) at the curvature δ = αλ where its largest root is largest: DREAM at λ/L = 0.0100. The cross is the dominant root, the dashed circle through it has radius ρ, and the polynomial has τ + 2 roots, so delay adds roots that must be kept inside the unit circle too.

C Does acceleration survive the delay? The spectral gap 1 − ρ against κ, at τ = 2

Each curve is the largest spectral gap a method can reach at that κ (for GD, HB and NAG by numerical search over their parameters; for DREAM, its formula). Under any positive delay the best heavy ball has β = 0, so its curve lies on gradient descent’s, and from τ = 5 on the best Nesterov does too. On these axes a gap ∝ κ^−1/2 is a line of slope −½, the accelerated scaling, and a gap ∝ κ⁻¹has slope −1, the gradient-descent scaling; the slopes are fitted over κ ≥ 100. The dotted vertical line is the κ chosen above.

Momentum alone cannot look far enough ahead to make up for a stale gradient; extrapolating the gradient query by more than the delay can, and then acceleration survives, at the price of a factor 2τ + 1 in the rate, which no method can avoid.

The theory behind this page is in DREAM: delay-resistant acceleration with momentum by Mert Gürbüzbalaban, M. Hamza Rafi, Necdet Serhat Aybat and Waheed U. Bajwa (arXiv:2610.37444, 2026): the characterization of the delayed methods on quadratics through the characteristic polynomial, the proof that neither heavy ball nor Nesterov’s method can stay accelerated under any fixed delay, the explicit DREAM parameters with their rate, and the integral-quadratic-constraint argument that carries the rate from quadratics to all smooth strongly convex functions. The note Can momentum survive a delay? walks through the ideas; the wider thread is on the research page.

To reference this page:

@misc{gurbuzbalaban2026delayplayground,
  title  = {Acceleration with stale gradients, interactively},
  author = {G{\"u}rb{\"u}zbalaban, Mert},
  year   = {2026},
  howpublished = {\url{https://mert-g.org/playground/delay/}}
}