Abstract
When minimizing L-smooth, µ-strongly convex objectives using exact gradients without delay, Nesterov's accelerated gradient (NAG) method achieves the optimal √ κ dependence on the condition number κ = L/µ, while the heavy-ball (HB) method achieves the same scaling on strongly convex quadratics. In asynchronous and distributed optimization, however, gradients are typically inexact and may arrive with delays that vary across workers and iterations. To isolate the effect of gradient staleness on accelerated methods in such problems, we study an idealized mathematical model with a fixed delay τ ≥ 1, in which the update at iteration k uses a stale gradient ∇f (y k−τ) instead of ∇f (y k), where y k is the gradient-evaluation point at iteration k and y k−τ is the corresponding point from τ iterations earlier. For this fixed-delay model, Arjevani, Shamir, and Srebro establish a worst-case lower bound of Ω(τ √ κ log(1/ϵ)) iterations to reach objective-value error at most ϵ as ϵ → 0, raising the question of whether NAG and HB can attain this scaling by adapting their parameters to the delay, while using the available stale gradient at every iteration. We answer negatively: under any fixed positive delay, neither NAG nor HB can retain √ κ-acceleration on strongly convex quadratics when these methods take a step in each iteration, regardless of how their constant step sizes and positive momentum coefficients are chosen to ensure stability. We then introduce delay-resistant accelerated momentum (DREAM), a generalized momentum method with explicit delay-dependent parameters that decouples gradient-query extrapolation from momentum, updates at every iteration, and achieves a linear convergence rate of 1 − Θ(1/(τ √ κ)) on all smooth strongly convex objectives, including quadratics, as κ → ∞. This rate yields an iteration complexity that matches the delayed first-order lower bound of Arjevani et al. up to logarithmic factors. Our proof combines characteristic-polynomial stability analysis of the delayed momentum recurrences on quadratics with an analytic Zames–Falb integral quadratic constraint certificate. We further extend the approach to smooth convex objectives, obtaining near-optimal iteration complexity up to logarithmic factors in the regime when the target accuracy is sufficiently small, and present numerical experiments illustrating DREAM's accelerated convergence. Numerical experiments on strongly convex quadratics and regularized logistic regression corroborate the theoretical results, demonstrating that DREAM preserves accelerated condition-number dependence under delays, unlike classical momentum methods. Additional experiments suggest that this accelerated scaling persists even when the algorithm parameters are chosen using a conservative upper bound on the actual delay. † M. Gürbüzbalaban (