Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Guy Kornowski, Ohad Shamir
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 $Θ(\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$.
尚无 AI 解读，展示原文摘要