← 研踪 PaperTrailarXiv:2604.13870 · v3
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
首次提交 2026-04-15 21:33
版本更新 2026-10-26 16:14
雷达观测 2026-10-29 00:36
摘要
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$.
作者备注：Substantially improved version, with new and matching upper and lower bounds
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-10-26 16:14 · 最新观测版本
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
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$.
查看此版本解读 →查看此版本原文 ↗