Stochastic Subgradient Last Iterate Gets Tight Bounds

The paper tightens last-iterate bounds for stochastic subgradient descent in 1D and shows variance alone is not enough.

• Research org: Unspecified in arXiv abstract
• Core data: 1/√n optimization error
• Breakthrough: Removes the extra log n factor under i.i.d. bounded-variance noise

New Bounds for the Last Iterate of the Stochastic subGradient Method looks at a very specific but important question: what does the final model iterate of stochastic subgradient descent actually guarantee after a fixed training horizon? That matters because in practice, engineers usually care about the model state they end up with, not just an averaged iterate or a theoretical sequence of intermediate points.

The paper focuses on one-dimensional convex Lipschitz objectives and the standard fixed stepsize choice η = Θ(1/√n) over a fixed horizon n. The key point is that the authors separate two cases that are often blurred together in broad convergence statements: one where the subgradient noise is additive, i.i.d., and uniformly bounded in variance, and another where the i.i.d. assumption is dropped.

What problem this paper is trying to fix

Stochastic subgradient methods are a basic tool for optimizing convex objectives when exact gradients are unavailable or expensive. The catch is that many convergence results are stated for averaged iterates or for generic bounds that carry extra factors, which can make the theory look worse than the behavior practitioners hope for.

This paper is about the “last iterate” specifically: the final parameter vector after n updates. That is the object most developers actually deploy, checkpoint, or hand off to the next stage of a pipeline. So if the last iterate has a weaker guarantee than the averaged iterate, that gap matters in real workflows.

The authors target an open problem posed by Koren and Segal at COLT 2020. The question was whether bounded-variance noise alone is enough to get the clean O(1/√n) behavior for the last iterate, or whether an extra log factor is fundamentally unavoidable.

How the method works in plain English

The setup is intentionally narrow: one-dimensional convex Lipschitz objectives, stochastic subgradient updates, and fixed stepsizes chosen as η = Θ(1/√n) for a known horizon n. In other words, the learning rate is set in advance based on how long the run will last.

Under that setup, the paper analyzes the optimization error of the last iterate. The first result shows that if the noise is additive, i.i.d., and has uniformly bounded variance, then the last iterate reaches optimization error on the order of 1/√n. That removes the extra log n factor found in existing generic bounds.

The second result deliberately breaks one assumption: if the i.i.d. condition is removed, the story changes. The paper shows that the optimization error can become (log n)/√n. So the extra logarithmic factor is not just a proof artifact in full generality; it can actually appear once independence is gone.

What the paper actually shows

The main technical message is a split verdict on the role of noise assumptions. With additive i.i.d. subgradient noise and uniformly bounded variance, the last iterate behaves better than generic bounds suggest. Without i.i.d., the last iterate can degrade to a slower rate with an extra logarithmic term.

That is enough to answer the open problem negatively under the weaker assumption set. The abstract explicitly says that under the uniformly bounded variance assumption alone, the last iterate of stochastic subgradient method is suboptimal even in dimension one.

There are no benchmark tables, datasets, wall-clock measurements, or empirical results in the abstract. So the contribution here is purely theoretical: sharper rate analysis, a separation result, and a negative resolution to a previously open question.

• Setting: 1D convex Lipschitz optimization
• Stepsize: fixed η = Θ(1/√n)
• Good case: O(1/√n) last-iterate error under additive i.i.d. bounded-variance noise
• Bad case: (log n)/√n error without i.i.d.

Why developers should care

If you use stochastic subgradient-style updates in production, this paper is a reminder that the statistical assumptions behind your noise model matter just as much as the update rule. Two training runs can look similar on paper but behave differently depending on whether the noise is truly independent across steps.

It also clarifies when you can trust the final checkpoint. If your setup matches the i.i.d. bounded-variance model, the last iterate can be analyzed at the cleaner 1/√n rate. If not, you should not assume that the final iterate inherits the same guarantee.

For practitioners, the practical takeaway is not “use this paper’s method” but “be precise about assumptions.” The result is a warning against overgeneralizing convergence guarantees from idealized noise models to real optimization pipelines where correlations, drift, or nonstationarity may creep in.

Limitations and open questions

The biggest limitation is scope. The result is for one-dimensional convex Lipschitz objectives, so it does not directly settle what happens in higher dimensions or for more complex models.

The abstract also only discusses a fixed stepsize policy tuned to the horizon n. It does not claim anything about adaptive schedules, practical heuristics, or nonconvex training. Those are natural next questions, but they are not answered here.

Still, the paper does something valuable for the optimization toolbox: it pinpoints exactly which assumption buys the clean last-iterate rate, and exactly which assumption is too weak to guarantee it. That kind of boundary-setting is useful when you are deciding how much theory to rely on for a real optimizer.

In short, this paper sharpens the theory around stochastic subgradient descent and shows that the last iterate is not universally well-behaved under bounded variance alone. For engineers, the lesson is simple: if you care about the final model state, make sure your noise assumptions are doing real work.