证明了梯度下降最后一步往往略差于最优，无法避免对数因子。
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
- 证明在任意时间下，标准步长无法达到最优收敛速度。
- 即使无噪声情况下，最后迭代点仍存在额外的对数因子误差。
- 适用于关注优化算法收敛性理论的研究者。
我们研究在凸Lipschitz函数上使用梯度下降（GD）或其随机变体（SGD）进行最小化时，最后迭代点的收敛性。已知标准步长选择下，经过T步后最后迭代点的收敛速率为$\log T/\sqrt{T}$。Jain等人[2019]通过构造非标准步长序列恢复了最优的$1/\sqrt{T}$速率，但该序列需预先知道总步数T。而此前猜想：若不提前知晓T，任何步长序列均无法保证SGD最后迭代点达到最优误差，这一猜想至今未被证明。本文证明了该猜想，并进一步指出：即使在无噪声的GD情形下，只要要求“随时可停”的保证，就必然存在关于T的额外多对数因子。该结果还表明，这种轻微次优的停止时间不可避免。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。