# Provably Faster Gradient Descent via Long Steps

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 12 Jul 2023.

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

- [Cyclical Learning Rates for Training Neural Networks](https://mlsanity.com/paper/1506.01186/) (2015)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Optimized first-order methods for smooth convex minimization](https://mlsanity.com/paper/1406.5468/) (2014)
- [Exact Worst-case Performance of First-order Methods for Composite Convex Optimization](https://mlsanity.com/paper/1512.07516/) (2015)
- [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019)
- [Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods](https://mlsanity.com/paper/2203.07305/) (2022)
- [Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions](https://mlsanity.com/paper/1803.06600/) (2018)
- [Super-Acceleration with Cyclical Step-sizes](https://mlsanity.com/paper/2106.09687/) (2021)
- [Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selection](https://mlsanity.com/paper/1812.00146/) (2018)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions](https://mlsanity.com/paper/1902.00947/) (2019)
- [Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees](https://mlsanity.com/paper/1803.06073/) (2018)
- [Provable Super-Convergence with a Large Cyclical Learning Rate](https://mlsanity.com/paper/2102.10734/) (2021)
- [On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions](https://mlsanity.com/paper/1606.09365/) (2016)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [An optimal gradient method for smooth strongly convex minimization](https://mlsanity.com/paper/2101.09741/) (2021)
- [Principled Analyses and Design of First-Order Methods with Inexact Proximal Operators](https://mlsanity.com/paper/2006.06041/) (2020)
- [Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates](https://mlsanity.com/paper/2008.07067/) (2020)
- [An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity](https://mlsanity.com/paper/1902.03373/) (2019)
- [Efficient First-order Methods for Convex Minimization: a Constructive Approach](https://mlsanity.com/paper/1803.05676/) (2018)
- [Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting](https://mlsanity.com/paper/1810.05231/) (2018)
- [First-order algorithms converge faster than O(1/k) on convex problems](https://mlsanity.com/paper/1812.08485/) (2018)
- [Accelerated first-order methods for a class of semidefinite programs](https://mlsanity.com/paper/2206.00224/) (2022)
- [SPECTRA -- a Maple library for solving linear matrix inequalities in exact arithmetic](https://mlsanity.com/paper/1611.01947/) (2016)
- [A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion](https://mlsanity.com/paper/1909.06099/) (2019)
- [Implicit regularity and linear convergence rates for the generalized trust-region subproblem](https://mlsanity.com/paper/2112.13821/) (2021)

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

- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression](https://mlsanity.com/paper/2310.01687/) (2023)
- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [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)
- [Understanding the Generalization Benefits of Late Learning Rate Decay](https://mlsanity.com/paper/2401.11600/) (2024)
- [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)
- [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)
- [ELRA: Exponential learning rate adaption gradient descent optimization method](https://mlsanity.com/paper/2309.06274/) (2023)
- [First-ish Order Methods: Hessian-aware Scalings of Gradient Descent](https://mlsanity.com/paper/2502.03701/) (2025)
- [Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension](https://mlsanity.com/paper/2602.12471/) (2026)
- [Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima](https://mlsanity.com/paper/2607.08380/) (2026)
- [Silver Rate Is (Almost) Optimal for Gradient Descent](https://mlsanity.com/paper/2609.09152/) (2026)
- [Data-induced multiscale losses and efficient multirate gradient descent schemes](https://mlsanity.com/paper/2402.03021/) (2024)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity](https://mlsanity.com/paper/2604.13393/) (2026)
- [A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions](https://mlsanity.com/paper/2609.08656/) (2026)
- [The Row Normalization Puzzle in Muon](https://mlsanity.com/paper/2609.39114/) (2026)

## Abstract (arXiv)

This work establishes new convergence guarantees for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We show that long steps, which may increase the objective value in the short term, lead to provably faster convergence in the long term. A conjecture towards proving a faster O(1/Tlog T) rate for gradient descent is also motivated along with simple numerical validation.