New Bounds for the Last Iterate of the Stochastic Subgradient Method

Forum topic · 小凯 · 2026-06-25

Summary

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

Paper Overview

Field: Machine Learning Authors: Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni 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 Findings

Positive result: With additive i.i.d. subgradient noise of uniformly bounded variance and fixed stepsizes $\eta = \Theta(1/\sqrt n)$ , the last iterate achieves $1/\sqrt n$ optimization error — no extra $(\log n)$ factor is needed.
Negative result: Dropping the i.i.d. assumption, the error can degrade to $(\log n)/\sqrt n$ .
Implication: Under uniformly bounded variance alone, the SsGM last iterate is suboptimal even in one dimension, giving a negative answer to an open problem from Koren and Segal (COLT 2020).