mlsanityData to 14 Oct 2026

A lower bound for stepsize-based acceleration of gradient descent

arXiv 2608.10418 ↗First posted 11 Aug 2026math.OC cs.LG stat.MLcited by 4

Not on the map. Why?

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.

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

25 of 32 references.

References · 25

  1. 2019Adaptive Gradient Descent without Descentcited by 79
  2. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
  3. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  4. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  5. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  6. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  7. 2014Optimized first-order methods for smooth convex minimizationcited by 18
  8. 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
  9. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  10. 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
  11. 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 11
  12. 2016On the Iteration Complexity of Oblivious First-Order Optimization Algorithmscited by 9
13 more
  1. 2024Anytime Acceleration of Gradient Descentcited by 7
  2. 2024Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedulecited by 6
  3. 2024Open Problem: Anytime Convergence Rate of Gradient Descentcited by 5
  4. 2024Accelerated Gradient Descent by Concatenation of Stepsize Schedulescited by 5
  5. 2016The exact information-based complexity of smooth convex minimizationcited by 4
  6. 2021The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functionscited by 4
  7. 2024Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functionscited by 4
  8. 2024Composing Optimized Stepsize Schedules for Gradient Descentcited by 4
  9. 2024Accelerating Proximal Gradient Descent via Silver Stepsizescited by 4
  10. 2025Numerical Design of Optimized First-Order Algorithmscited by 3
  11. 2026Lower Bounds for Anytime Acceleration of Gradient Descentcited by 3
  12. 2024On Averaging and Extrapolation for Gradient Descentcited by 1
  13. 2024A Proof of the Exact Convergence Rate of Gradient Descentcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Improved Gradient Descent Lower Bounds Beyond Nesterovcited by 2
  2. 2026Silver Rate Is (Almost) Optimal for Gradient Descentcited by 1
  3. 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functionscited by 0
  4. 2026Thinking Outside the Box: Can Language Models Rely on External Guidance Selectively?cited by 0