arXiv：cs.LG· Guy Kornowski, Ohad Shamir·· 5 小时前AI 评分37
梯度下降的最后一次迭代往往（略微）次优
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
AI 导读
研究证明，Jain 等人 2019 年关于 SGD 最后迭代的猜想成立：若无法预先知道总步数 T，任何步长序列都无法保证最优误差。即使在 GD 的无噪声情形下，要获得 anytime 最后迭代保证，也无法避免 T 的多对数因子额外开销。该结果已被 NeurIPS 2026 接收。
正文
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.
| Comments: | NeurIPS 2026 |
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2604.13870 [math.OC] |
| (or arXiv:2604.13870v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2604.13870 arXiv-issued DOI via DataCite |
Submission history
From: Guy Kornowski [view email]
[v1]
Wed, 15 Apr 2026 13:33:08 UTC (15 KB)
[v2]
Fri, 2 Oct 2026 06:36:41 UTC (17 KB)
来源：arXiv：cs.LG · arxiv.org