Gradient Descent's Last Iterate is Often (slightly) Suboptimal

Abstract

We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. We prove that $\Theta (\sqrt{\log (T)/T})$ is the optimal anytime rate attainable with a fixed stepsize schedule (that does not depend on the total number of steps $T$). The upper bound holds already for SGD, and improves on the $\log (T)/\sqrt{T}$ rate of Shamir and Zhang [2013], as well as the $\sqrt{\log (T)/T}$ rate of Zamani and Glineur [2023] which was proven only for deterministic GD. The matching lower bound holds already for GD, and confirms the conjecture of Jain et al. [2019], namely that the optimal $1/\sqrt{T}$ rate for the last iterate cannot be obtained without prior knowledge of $T$.

arXiv commentSubstantially improved version, with new and matching upper and lower bounds