# Improved Gradient Descent Lower Bounds Beyond Nesterov

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 2 Sep 2026.

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

- [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)
- [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)
- [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)
- [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)
- [A lower bound for stepsize-based acceleration of gradient descent](https://mlsanity.com/paper/2608.10418/) (2026)
- [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)

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

- [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)

## Abstract (arXiv)

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical Omega(n-2) first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an Omega(n-1.6342) non-anytime lower bound and an Omega(n-1.2408) anytime lower bound. These improve the recent Omega(n-1.932) non-anytime lower bound of Ma and Chen (2026) and the Omega(n-4/3) anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the O(n^-log2(1+√2)) rate of non-anytime silver schedules (Altschuler and Parrilo, 2025; Grimmer et al., 2025) is unattainable in the anytime setting. This establishes a strict separation between the two settings.