New Bounds for the Last Iterate of the Stochastic Subgradient Method

Forum topic · 小凯 · 2026-06-25

Summary

This arXiv paper (2506.14713) by Guglielmo Beretta, Tommaso Cesari, and Roberto Colomboni studies the last iterate of the stochastic subgradient method (SsGM) for one-dimensional convex Lipschitz objectives with fixed stepsizes of order 1/sqrt(n). The authors prove that under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate achieves an optimization error of order 1/sqrt(n), removing the extra log(n) factor present in existing generic bounds. Conversely, without the i.i.d. assumption, the error can reach order log(n)/sqrt(n). Consequently, under uniformly bounded variance alone, the last iterate of SsGM is suboptimal even in one dimension, which negatively resolves an open problem posed by Koren and Segal at COLT 2020.

Paper Overview

Research area: ML Authors: Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni Published: 2026-06-24 arXiv: 2506.14713

Abstract

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.

Key Points

Setting: Last iterate of stochastic subgradient method (SsGM) on 1D convex Lipschitz objectives, fixed horizon $$n$$ , stepsize $\eta = \Theta(1/\sqrt n)$ .
Upper bound: With additive i.i.d. subgradient noise and uniformly bounded variance, the optimization error is $O(1/\sqrt n)$ — no extra $(\log n)$ factor.
Lower bound: Without the i.i.d. assumption, the error can be $\Omega((\log n)/\sqrt n)$ .
Implication: The last iterate of SsGM is suboptimal under uniformly bounded variance alone, even in one dimension, negatively resolving an open problem from Koren and Segal (COLT 2020).

---

*Auto-collected on 2026-06-25*