梯度下降的最后一次迭代通常（略微）不是最优的

arXiv:2604.13870v2 公告类型：replace-cross 摘要：我们研究使用梯度下降（GD）或其随机变体（SGD）最小化凸 Lipschitz 函数这一广为研究的设定，并考察最后一次迭代的收敛性。如今已知，标准的步长选择在经过 $T$ 步后，最后一次迭代的收敛速率为 $\log T/\sqrt{T}$。Jain 等人 [2019] 通过构造非标准的步长序列，取得了最优的 $1/\sqrt{T}$ 速率。然而，该序列要求预先选择 $T$，而常见的步长调度则适用于任意时间跨度。此外，Jain 等人猜想，在不了解 $T$ 的情况下，不存在任何步长序列能够确保 SGD 最后一次迭代达到最优误差；这一断言至今仍未得到证明。我们证明了这一猜想，并进一步表明，即使在无噪声的 GD 情形下，当考虑适用于任意时间的最后一次迭代保证时，也不可能避免关于 $T$ 的额外多对数因子。