# Anytime Acceleration of Gradient Descent

arXiv: https://arxiv.org/abs/2411.17668 · HTML: https://mlsanity.com/paper/2411.17668/

## 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 (most cited first, 11 of 11)

- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule](https://mlsanity.com/paper/2309.07879/) (2023)
- [Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods](https://mlsanity.com/paper/2203.07305/) (2022)
- [Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps](https://mlsanity.com/paper/2403.14045/) (2024)
- [Accelerated Gradient Descent via Long Steps](https://mlsanity.com/paper/2309.09961/) (2023)
- [Open Problem: Anytime Convergence Rate of Gradient Descent](https://mlsanity.com/paper/2406.13888/) (2024)
- [Accelerated Gradient Descent by Concatenation of Stepsize Schedules](https://mlsanity.com/paper/2410.12395/) (2024)
- [Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions](https://mlsanity.com/paper/2406.17506/) (2024)
- [Composing Optimized Stepsize Schedules for Gradient Descent](https://mlsanity.com/paper/2410.16249/) (2024)

## Built on by (most cited first, 7 of 7)

- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [Gradient Descent's Last Iterate is Often (slightly) Suboptimal](https://mlsanity.com/paper/2604.13870/) (2026)
- [A lower bound for stepsize-based acceleration of gradient descent](https://mlsanity.com/paper/2608.10418/) (2026)
- [Improved Gradient Descent Lower Bounds Beyond Nesterov](https://mlsanity.com/paper/2609.02855/) (2026)
- [Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension](https://mlsanity.com/paper/2602.12471/) (2026)
- [Silver Rate Is (Almost) Optimal for Gradient Descent](https://mlsanity.com/paper/2609.09152/) (2026)

## 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.