Preprint, 2026
DREAM: delay-resistant acceleration with momentum
arXiv preprint, 2026.
In asynchronous and distributed optimization the gradient that arrives at step k was computed τ steps ago. This paper shows that no retuning of heavy ball or Nesterov’s method survives such a delay: on strongly convex quadratics, both lose the accelerated √κ dependence on the condition number for every fixed delay τ ≥ 1. It then introduces DREAM, a generalized momentum method with explicit delay-dependent parameters that decouples the gradient-query extrapolation from the momentum and sets the extrapolation proportional to the delay. DREAM converges at the rate 1 − Θ(1/(τ√κ)) on all smooth strongly convex functions, matching the delayed first-order lower bound of Arjevani, Shamir and Srebro up to logarithmic factors, with an analytic Zames–Falb integral-quadratic-constraint certificate; an accelerated proximal-point wrapper extends it to smooth convex problems.
The playground Acceleration with stale gradients lets you try the ideas of this paper in the browser.
The research note Can momentum survive a delay? explains the paper informally.
@misc{gurbuzbalaban2026dream,
title = {DREAM: delay-resistant acceleration with momentum},
author = {Mert Gürbüzbalaban and M. Hamza Rafi and Necdet Serhat Aybat and Waheed U. Bajwa},
year = {2026},
howpublished = {arXiv preprint arXiv:2610.37444},
}Return to all publications, the research program, or the home page.