Model Releases
A lower bound for stepsize-based acceleration of gradient descent
arXiv:2608.10418v1 Announce Type: cross 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})
arXiv:2608.10418v1 Announce Type: cross 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 Oig(T^{-log_2(1+sqrt{2})}ig) 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.
Related
- A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
- Convergence of Steepest Descent and Adam under Non-Uniform Smoothness
- Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates
Source: arXiv cs.LG | 2026-08-12