Id: arxiv/2608.10418 Url: https://arxiv.org/abs/2608.10418 Tags: math.OC, cs.LG, stat.ML Score: 0 Title: A lower bound for stepsize-based acceleration of gradient descent Domain: math.OC Source: arxiv Authors: Jianhao Ma, Yuxin Chen Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-11 Page: https://delphi.science/r/arxiv/2608.10418 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…