# A lower bound for stepsize-based acceleration of gradient descent

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 32 references that are in the map.
- First posted on arXiv 11 Aug 2026.

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

- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [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)
- [Optimized first-order methods for smooth convex minimization](https://mlsanity.com/paper/1406.5468/) (2014)
- [Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods](https://mlsanity.com/paper/2203.07305/) (2022)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps](https://mlsanity.com/paper/2403.14045/) (2024)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [On the Iteration Complexity of Oblivious First-Order Optimization Algorithms](https://mlsanity.com/paper/1605.03529/) (2016)
- [Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2411.17668/) (2024)
- [Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule](https://mlsanity.com/paper/2412.05790/) (2024)
- [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)
- [The exact information-based complexity of smooth convex minimization](https://mlsanity.com/paper/1606.01424/) (2016)
- [The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions](https://mlsanity.com/paper/2104.05468/) (2021)
- [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)
- [Accelerating Proximal Gradient Descent via Silver Stepsizes](https://mlsanity.com/paper/2412.05497/) (2024)
- [Numerical Design of Optimized First-Order Algorithms](https://mlsanity.com/paper/2507.20773/) (2025)
- [Lower Bounds for Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2607.02053/) (2026)
- [On Averaging and Extrapolation for Gradient Descent](https://mlsanity.com/paper/2402.12493/) (2024)
- [A Proof of the Exact Convergence Rate of Gradient Descent](https://mlsanity.com/paper/2412.04427/) (2024)

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

- [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)
- [A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions](https://mlsanity.com/paper/2609.08656/) (2026)
- [Thinking Outside the Box: Can Language Models Rely on External Guidance Selectively?](https://mlsanity.com/paper/2609.39578/) (2026)

## Abstract (arXiv)

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of O(T-1) (where T denotes the number of iterations) to Obig(T^-log2(1+√2)big) using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical Omega(T-2) benchmark for general first-order methods. In this work, we present a new lower bound of Omega(T-1.9319) for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal O(T-2) convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.