























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. By now, it is known that standard stepsize choices lead to a last iterate convergence rate of $\log T/\sqrt{T}$ after $T$ steps. A breakthrough result of Jain et al. [2019] recovered the optimal $1/\sqrt{T}$ rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing $T$ in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of $T$, no stepsize sequence can ensure the optimal error for SGD's last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in $T$ when considering an anytime last iterate guarantee. Our proof further suggests that such (slightly) suboptimal stopping times are unavoidably common.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2604.13870 [math.OC] |
| (or arXiv:2604.13870v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2604.13870 arXiv-issued DOI via DataCite (pending registration) |
From: Guy Kornowski [view email]
[v1]
Wed, 15 Apr 2026 13:33:08 UTC (15 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。