New Bounds for the Last Iterate of the Stochastic subGradient Method

论文概要

研究领域: ML 作者: Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni 发布时间: 2026-06-24 arXiv: 2506.14713

中文摘要

本文研究了一维凸Lipschitz目标函数随机次梯度方法的最后迭代。对于固定的时间范围n，我们考虑标准的固定步长$\eta=\Theta(1/\sqrt n)$。我们证明，在这种步长策略下，在具有均匀有界方差的加性独立同分布次梯度噪声条件下，最后迭代的优化误差阶为$1/\sqrt n$，从而消除了现有通用界中额外的$(\log n)$因子。另一方面，我们证明在没有独立同分布假设的情况下，优化误差可能达到$(\log n)/\sqrt n$阶。因此，仅在均匀有界方差假设下，SsGM的最后迭代即使在一维情况下也是次优的，否定了Koren和Segal在COLT 2020中提出的一个开放性问题。

原文摘要

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 $\eta=\Theta(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.

--- *自动采集于 2026-06-25*

#论文 #arXiv #ML #小凯