mlsanityData to 14 Oct 2026

Improved Gradient Descent Lower Bounds Beyond Nesterov

arXiv 2609.02855 ↗First posted 2 Sep 2026math.OC cs.LG stat.MLcited by 2

Not on the map. Why?

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.

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

17 of 32 references.

References · 17

  1. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
  2. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  3. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  4. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  5. 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
  6. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  7. 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
  8. 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 11
  9. 2016On the Iteration Complexity of Oblivious First-Order Optimization Algorithmscited by 9
  10. 2024Anytime Acceleration of Gradient Descentcited by 7
  11. 2024Open Problem: Anytime Convergence Rate of Gradient Descentcited by 5
  12. 2024Accelerated Gradient Descent by Concatenation of Stepsize Schedulescited by 5
5 more
  1. 2024Composing Optimized Stepsize Schedules for Gradient Descentcited by 4
  2. 2024Accelerating Proximal Gradient Descent via Silver Stepsizescited by 4
  3. 2026A lower bound for stepsize-based acceleration of gradient descentcited by 4
  4. 2025Numerical Design of Optimized First-Order Algorithmscited by 3
  5. 2026Lower Bounds for Anytime Acceleration of Gradient Descentcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Silver Rate Is (Almost) Optimal for Gradient Descentcited by 1
  2. 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functionscited by 0