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 #小凯