# Open Problem: Anytime Convergence Rate of Gradient Descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 11 references that are in the map.
- First posted on arXiv 19 Jun 2024.

## Builds on (most cited first, 8 of 8)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [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 Gradient Descent via Long Steps](https://mlsanity.com/paper/2309.09961/) (2023)
- [First-order algorithms converge faster than O(1/k) on convex problems](https://mlsanity.com/paper/1812.08485/) (2018)

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

- [Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2411.17668/) (2024)
- [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)
- [Silver Rate Is (Almost) Optimal for Gradient Descent](https://mlsanity.com/paper/2609.09152/) (2026)

## Abstract (arXiv)

Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives, merely by changing the stepsize sequence. We show that this can lead to surprisingly large errors indefinitely, and therefore ask: Is there any stepsize schedule for gradient descent that accelerates the classic O(1/T) convergence rate, at any stopping time T?