{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}