New Bounds for the Last Iterate of the Stochastic subGradient Method
Not on the map. Why?
Abstract (arXiv)
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 η =Theta(1/√ 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/√ 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)/√ 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 facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 8 of its 19 references that are in the map. First posted on arXiv 23 Jun 2026.
Builds on
8 of 19 references.
References · 8
- 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
- 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 35
- 2023Exact convergence rate of the last iterate in subgradient methodscited by 24
- 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
- 2023General Tail Bounds for Non-Smooth Stochastic Mirror Descentcited by 7
- 2024An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noisecited by 3
- 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 3
- 2021The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependencecited by 1
Built on by
Not cited yet.