A lower bound for stepsize-based acceleration of gradient descent

Gradient descent (GD) is traditionally known to converge at a rate of O(T^-1) for smooth convex functions. Recent research demonstrated that by using carefully designed, non-constant stepsize schedules, this rate can be improved to O(T^-1.2715). This paper investigates the fundamental limits of this approach, specifically asking whether such stepsize-based acceleration can ever reach the optimal O(T^-2) rate achieved by Nesterov-style momentum methods.

The authors construct a worst-case, finite-dimensional hard instance for any given predetermined stepsize schedule. By decomposing the schedule into 'capped' steps (those <= 1) and 'excess' steps (those > 1), they partition the iterations into blocks. They then use a Moreau envelope construction to create a 1-smooth convex function where the gradient trajectory is forced to move along specific orthogonal anchors. By analyzing the growth of the residual schedule mass and employing a Lyapunov potential, they derive a lower bound on the objective suboptimality that holds for any choice of stepsizes.

The study establishes a new lower bound of Omega(T^-p) for any p > 1.9319. This result confirms that while stepsize schedules can indeed accelerate plain GD, they are theoretically incapable of matching the O(T^-2) convergence rate of accelerated first-order methods. The proof technique relies on a rank-cutoff argument that demonstrates how the 'cost' of long steps prevents the algorithm from reaching the optimal convergence exponent.

This work settles a significant open question in optimization theory by providing a rigorous impossibility result for stepsize-based acceleration. It clarifies the boundary between what can be achieved by simply tuning stepsize schedules and what necessitates structural algorithmic changes like momentum. This helps researchers focus their efforts on hybrid methods or alternative modifications when seeking to optimize convergence performance.