A lower bound for stepsize-based acceleration of gradient descent
Jianhao Ma, Yuxin Chen
math.OC
Aug 11, 2026 · v1
cs.LG stat.ML
TL;DR
The main lower-bound proof for gradient descent with predetermined stepsizes was formalized in Lean 4 using Codex; the code is publicly available.
Abstract
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 $O\big(T^{-\log_2(1+\sqrt{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 $Ω(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $Ω(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.
Problem
Carefully designed stepsize schedules can accelerate plain gradient descent on smooth convex problems to O(T^{-1.2715}). Little was known about lower bounds for this class beyond the classical Ω(T^{-2}) bound for all first-order methods.
Approach
For any predetermined nonnegative schedule, the authors select long steps and build an adversarial trajectory across orthogonal blocks. They realize it with a smooth convex function via a Moreau envelope. A matching argument then removes the dependence on temporal order, and a cutoff/Lyapunov argument completes the bound. The proof was generated by GPT-5.6 Sol Pro under author guidance and formalized in Lean 4 with Codex.
Results
For every p > sqrt(2+sqrt(3)) ≈ 1.9319, the last iterate satisfies f(x_T)-f* ≥ c_p L R^2 (T+1)^{-p}. This shows that stepsize schedules alone cannot reach the optimal O(T^{-2}) rate. A Lean 4 formalization is released at github.com/jianhaoma/gd-lower-bound-lean.
