# Accelerated Gradient Descent via Long Steps

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2023.

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

- [From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression](https://mlsanity.com/paper/2310.01687/) (2023)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2411.17668/) (2024)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [Open Problem: Anytime Convergence Rate of Gradient Descent](https://mlsanity.com/paper/2406.13888/) (2024)
- [Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squares](https://mlsanity.com/paper/2510.17506/) (2025)
- [On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms](https://mlsanity.com/paper/2311.18431/) (2023)
- [Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima](https://mlsanity.com/paper/2607.08380/) (2026)
- [A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions](https://mlsanity.com/paper/2609.08656/) (2026)

## Abstract (arXiv)

Recently Grimmer [1] showed for smooth convex optimization by utilizing longer steps periodically, gradient descent's textbook LD2/2T convergence guarantees can be improved by constant factors, conjecturing an accelerated rate strictly faster than O(1/T) could be possible. Here we prove such a big-O gain, establishing gradient descent's first accelerated convergence rate in this setting. Namely, we prove a O(1/T1.0564) rate for smooth convex minimization by utilizing a nonconstant nonperiodic sequence of increasingly large stepsizes. It remains open if one can achieve the O(1/T1.178) rate conjectured by Das Gupta et. al. [2] or the optimal gradient method rate of O(1/T2). Big-O convergence rate accelerations from long steps follow from our theory for strongly convex optimization, similar to but somewhat weaker than those concurrently developed by Altschuler and Parrilo [3].