证明了一维凸优化中随机梯度法最后迭代点误差可达到1/√n，无需额外log因子。
New Bounds for the Last Iterate of the Stochastic subGradient Method
- 使用固定步长1/√n，分析一维凸问题的最后迭代点性能
- 在独立同分布噪声下误差为1/√n，优于已有结果中的( log n)/√n
- 无独立性假设时误差退化为( log n)/√n，说明该方法在低维仍不最优
我们研究一维凸Lipschitz目标函数下随机次梯度法（SsGM）的最后迭代点。对于固定步数n，采用标准固定步长η=Θ(1/√n)，在加性i.i.d.次梯度噪声且方差有界条件下，证明最后迭代点的优化误差为1/√n，消除了现有通用界中的额外(log n)因子。另一方面，若不假设i.i.d.条件，误差可能高达(log n)/√n。因此，在仅假设方差有界的情形下，即使在一维情况下，该方法的最后迭代点仍非最优，从而负面回答了Koren和Segal（COLT, 2020）提出的一个开放问题。
原文摘要 · Abstract (English)
We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon $n$, we consider the standard fixed stepsizes $η=Θ(1/\sqrt n)$. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order $1/\sqrt n$, thereby removing the extra $(\log n)$ factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order $(\log n)/\sqrt n$. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。