mlsanityData to 14 Oct 2026

Anytime Acceleration of Gradient Descent

arXiv 2411.17668 ↗First posted 26 Nov 2024cs.LG cs.SY eess.SYcited by 7

Not on the map. Why?

Abstract (arXiv)

This work investigates stepsize-based acceleration of gradient descent with em anytime convergence guarantees. For smooth (non-strongly) convex optimization, we propose a stepsize schedule that allows gradient descent to achieve convergence guarantees of O(T-1.119) for any stopping time T, where the stepsize schedule is predetermined without prior knowledge of the stopping time. This result provides an affirmative answer to a COLT open problem citepkornowski2024open regarding whether stepsize-based acceleration can yield anytime convergence rates of o(T-1). We further extend our theory to yield anytime convergence guarantees of exp(-Omega(T/kappa0.893)) for smooth and strongly convex optimization, with kappa being the condition number.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 11 of its 17 references that are in the map. First posted on arXiv 26 Nov 2024.

Builds on

11 of 17 references.

References · 11

  1. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
  2. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  3. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  4. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  5. 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
  6. 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
  7. 2023Accelerated Gradient Descent via Long Stepscited by 9
  8. 2024Open Problem: Anytime Convergence Rate of Gradient Descentcited by 5
  9. 2024Accelerated Gradient Descent by Concatenation of Stepsize Schedulescited by 5
  10. 2024Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functionscited by 4
  11. 2024Composing Optimized Stepsize Schedules for Gradient Descentcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 9
  2. 2025Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizescited by 7
  3. 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 4
  4. 2026A lower bound for stepsize-based acceleration of gradient descentcited by 4
  5. 2026Improved Gradient Descent Lower Bounds Beyond Nesterovcited by 2
  6. 2026Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimensioncited by 1
  7. 2026Silver Rate Is (Almost) Optimal for Gradient Descentcited by 1