A lower bound for stepsize-based acceleration of gradient descent

TL;DR

Ma & Chen prove a new lower bound of $\Omega(T^{-1.9319})$ on the last-iterate convergence rate of gradient descent with any predetermined nonnegative stepsize schedule on smooth convex problems. This rules out the possibility that stepsize scheduling alone — without momentum or other algorithmic modifications — can push plain GD from its recently-established $O(T^{-\log_2(1+\sqrt{2})}) \approx O(T^{-1.2716})$ acceleration all the way to the optimal $\Omega(T^{-2})$ first-order rate. The gap between the new lower bound (~ $T^{-1.93}$ ) and the classical Nesterov lower bound ( $T^{-2}$ ) is small but nonzero, so this closes most (but not all) of the theoretical uncertainty about how far stepsize-only acceleration can go. Notably, the authors report that the proof was developed by GPT-5.6 Sol Pro under the authors’ guidance — one of the first filed instances of an LLM-authored optimization-theory proof appearing in the arxiv record.

Key claims

The last-iterate convergence rate of gradient descent with any predetermined nonnegative stepsize schedule on smooth convex objectives cannot be better than $\Omega(T^{-1.9319})$ [Abstract, Theorem].
Stepsize schedules alone — without momentum or other algorithmic modification — provably cannot reach the optimal $\Omega(T^{-2})$ rate that Nesterov-style accelerated methods achieve [Abstract].
The new $\Omega(T^{-1.9319})$ bound sits strictly between the previously known classical $\Omega(T^{-2})$ lower bound for general first-order methods and the recently established $O(T^{-\log_2(1+\sqrt{2})}) \approx O(T^{-1.2716})$ upper bound achievable by carefully designed stepsize schedules [Abstract].
The proof was developed by GPT-5.6 Sol Pro under the authors’ guidance [Abstract closing sentence].

Method

The paper works in the standard smooth-convex first-order oracle model: an algorithm is a predetermined sequence of nonnegative stepsizes $\{\eta_t\}_{t=1}^{T}$ applied to plain gradient descent iterations $x_{t+1} = x_t - \eta_t \nabla f(x_t)$ , and the quantity of interest is the last-iterate suboptimality $f(x_T) - f^\star$ in the worst case over $L$ -smooth convex $f$ . Existing upper-bound work (Altschuler & Parrilo, Grimmer et al.) showed that with a carefully non-uniform schedule this quantity can be pushed below the textbook $O(T^{-1})$ rate to $O(T^{-\log_2(1+\sqrt{2})})$ ; the corresponding lower bound has remained the classical $\Omega(T^{-2})$ that applies to all first-order methods (which stepsize-based GD is a subclass of). The contribution is a new lower-bound construction specific to the predetermined-schedule subclass that rules out anything faster than $\Omega(T^{-1.9319})$ . The lower-bound construction and its proof were produced by GPT-5.6 Sol Pro under human guidance [Abstract].

Results

New lower bound: $\Omega(T^{-1.9319})$ on last-iterate convergence for GD with any predetermined nonnegative stepsize schedule [Abstract, Theorem].
Gap to previously known bounds: sits above the recently-established stepsize-schedule upper bound $O(T^{-\log_2(1+\sqrt{2})}) \approx O(T^{-1.2716})$ and just below the general first-order lower bound $\Omega(T^{-2})$ , so the space of theoretically-possible improvements from smarter schedules alone is now bounded within a factor of $T^{0.07}$ -ish [Abstract].

Why it’s interesting

Two hooks for the wiki. First, this is a clean piece of scheduling-theory evidence relevant to the ongoing “how much does the LR-schedule shape matter?” question tracked on Hyperparameter scaling laws — where What do near-optimal learning rate schedules look like? argued empirically that once you have warmup + monotonic decay, the base LR dominates the shape on deep-learning workloads, and How to Set the Learning Rate for Large-Scale Pre-training? fit a closed-form $\eta^\star(N,D)$ under WSD. This paper draws a strict theoretical ceiling on how much benefit any stepsize-only schedule can extract on the convex-worst-case model that the empirical LR-schedule literature implicitly compares against — the answer is not $\Omega(T^{-2})$ acceleration, and the remaining room above the current $O(T^{-\log_2(1+\sqrt{2})})$ upper bound is at most a factor of $T^{~0.66}$ . Second — and more directly novel for the wiki — the paper is one of the earliest filed arxiv records to disclose in its abstract that the proof was developed by an LLM (GPT-5.6 Sol Pro) under author guidance, which is a concrete datapoint for AI-for-AI Research on the mathematics-proof axis alongside LEAP: Supercharging LLMs for Formal Mathematics with Agentic Frameworks (Google LEAP formalizing Knuth’s Hamiltonian-decomposition subproblem in Lean) and Hyra-results — Hunyuan Research Agent (results bundle) (Hunyuan Hyra’s autocorrelation & Erdős constant results). Unlike LEAP this is not a machine-verified Lean proof — the correctness contract is standard peer review of a natural-language proof — so it’s a different point on the “LLM-authored math” axis: less certified but broader in scope.