Search papers, labs, and topics across Lattice.
This paper establishes a new lower bound of $\Omega(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent using predetermined nonnegative stepsize schedules, building on previous advancements in smooth convex optimization. The significance lies in demonstrating that while stepsize schedules can improve convergence rates, they cannot achieve the optimal $O(T^{-2})$ rate without additional algorithmic enhancements. This finding provides a crucial theoretical limit that informs future research on optimization techniques in machine learning.
Stepsize schedules alone can't push gradient descent beyond a convergence rate of $\Omega(T^{-1.9319})$, challenging the pursuit of optimal acceleration.
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 $\Omega(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $\Omega(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.
