A lower bound for stepsize-based acceleration of gradient descent

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.

Disclosure

“Disclosure on the use of generative AI The main proof was developed by GPT-5.6 Sol Pro. The authors provided the model with two inputs: the research objective of proving a lower bound for plain gradient descent showing that its worst-case rate is strictly slower than 1/𝑇 2 , and a high-level resisting-oracle strategy”

PDF page 23

Classification

Substantial proof generation

Multiplier

10

Verified

2026-08-23T05:08:40.591696Z

Structural counts