New Bounds for the Last Iterate of the Stochastic subGradient Method

Paper: 2606.24879 Authors: Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni, Andrea Paudice Categories: math.OC, cs.LG

The Gap

The standard stochastic subgradient method (SsGM) with fixed stepsize $\eta = \Theta(1/\sqrt n)$ is known to achieve an optimization error of $O((\log n)/\sqrt n)$ for the last iterate on convex Lipschitz functions, under bounded variance subgradient noise. This log factor was widely believed to be an unavoidable penalty for using the last point instead of the averaged one. Koren and Segal (COLT 2020) explicitly asked whether this extra $(\log n)$ can be removed in general. The paper answers this question by separating two regimes: under i.i.d. noise the log factor disappears, but under only bounded variance (allowing dependence) it is intrinsic — even in one dimension.

+-----------------------------+
| Problem: last iterate error |
| of SsGM = O(log n/sqrt(n)) |
| with fixed stepsize         |
+-------------+---------------+
              |
              v
+-----------------------------+
| Question: can the log be    |
| removed? (Koren & Segal '20)|
+-------------+---------------+
              |
              v
+-----------------------------+
| Assumption split: i.i.d.    |
| subgradient noise vs. only  |
| bounded variance            |
+-------------+---------------+
              |
              v
+-----------------------------+
| Method: 1-D analysis with   |
| martingale concentration &  |
| explicit lower bound        |
+-------------+---------------+
              |
              v
+-----------------------------+
| Evidence: Upper bound       |
| O(1/sqrt(n)) under i.i.d.;  |
| Lower bound Omega(log n/sqrt|
| (n)) for non-i.i.d. bounded |
| var                          |
+-------------+---------------+
              |
              v
+-----------------------------+
| Conclusion: i.i.d. removes  |
| log; bounded var alone is   |
| insufficient. Open problem  |
| closed.                     |
+-----------------------------+

The Increment

One sentence: Before this paper, the last iterate of SsGM had a guaranteed error $O((\log n)/\sqrt n)$; after it, we know the error can be $O(1/\sqrt n)$ under i.i.d. noise, but without i.i.d. the $(\log n)$ factor is necessary, settling a concrete open problem.

Core Mechanism

The paper studies the one-dimensional SsGM update:

$x`_{t+1}` = x_t - \eta g_t, \qquad \eta = \Theta(1/\sqrt n),$

where $g_t = f'(x_t) + \xi_t$ is a noisy subgradient. The true subgradient $f'(x_t)$ exists because $f$ is convex and Lipschitz. The noise $\xi_t$ has mean zero and bounded variance $\sigma^2$.

The analysis decomposes the final error $|x`_{n+1}` - x^*|$ into two parts: a deterministic recursion that would converge if $\xi_t \equiv 0$, and a stochastic accumulation of the noise. Using martingale concentration inequalities (Azuma-Hoeffding, Doob’s inequality), one can bound the stochastic term by $O(\sqrt{n}\cdot\eta\sigma)$ = $O(1/\sqrt n)$ provided the noise variables are independent. When independence is lost, the same bounds only give $O((\log n)/\sqrt n)$ — and the authors construct a counterexample achieving precisely $\Omega((\log n)/\sqrt n)$ with only bounded variance.

x0 ---> [x1 = x0 - eta * (f'(x0) + noise0)] ---> x2 ---> ... ---> x_{n+1}
                          |                                        |
                   deterministic                               stochastic
                   drift (f')                                accumulation (noises)
                          |                                        |
                          v                                        v
               Distant to x* shrinks                     Martingale sum walks ~ sqrt(n)
               geometrically (if no noise)                but concentration depends
                                                          on independence

Structural Metaphor: A Drunk on a Straight Road Home
Imagine a drunk person (the iterate) trying to walk home (the optimal point $x^*$). Each step has two components: a conscious correction (the true subgradient $f'$) that points roughly towards home, and a random stagger (the noise $\xi_t$). The step size $\eta$ is fixed — a short pace.

• Home: The minimizer $x^**$.
• Drunk’s location: $x_t$.
• Conscious correction: $- \eta f'(x_t)$, which on average reduces the distance to home.
• Stagger: $- \eta \xi_t$, an unpredictable push in random direction.
• i.i.d. noise: Each stagger is independent of all previous ones — like a fair coin toss every step. After $n$ steps, the total drift from staggers is about $\sqrt\{n\}$ times a unit step, so the distance contributed is $O(\eta \sqrt\{n\}) = O(1/\sqrt n)$.
• Dependent noise (only bounded variance): Staggers can be correlated — e.g., a persistent gust blowing left. The total drift can be as large as $\sqrt\{n \log n\}$ times a unit step, leading to $\Omega((\log n)/\sqrt n)$ distance.

The drunk’s final distance from home is the sum of the conscious correction’s effect (which tends to zero) plus the accumulated stagger. The paper shows that under independence, the stagger accumulation is no worse than $\Theta(1/\sqrt n)$; without independence, it can be worse.

Key Concepts

• Last iterate vs. averaged iterate: In stochastic optimization, one can either output the final point $x`_{n+1}`$ or the average $\frac{1}{n}\sum`_{t=1}`^n x_t$. The average usually has better theoretical guarantees (e.g., $O(1/\sqrt n)$ without log factors) because averaging damps noise. The last iterate is more natural in practice (no memory of previous points) but harder to analyze. This paper clarifies that the gap between them is only a log factor, and that gap only appears when noise is dependent.

• Martingale concentration with dependence: When $\xi_t$ are independent, the sum $\sum \eta \xi_t$ is a martingale with bounded increments, and Azuma–Hoeffding gives a $O(1/\sqrt n)$ bound with high probability. Without independence, the same inequality does not apply; a more general bound (e.g., using Doob’s inequality) only yields $O((\log n)/\sqrt n)$. The lower bound constructs a noise process that saturates the Doob bound.

• One-dimensional reduction: The paper restricts to $d=1$ because it suffices to answer the open problem (Koren and Segal asked generally, but a counterexample in 1D is already a negative answer). It also makes the analysis transparent: in 1D, subgradients are scalars and the geometry is simple. Extensions to higher dimensions are left open, but the core distinction (i.i.d. vs. dependent) is likely to hold.

Framework Shift

Before (mainstream view):                          After (this paper):
+---------------------------------+                +---------------------------------+
| Last iterate error with fixed   |                | Last iterate error with fixed   |
| stepsize = O(log n / sqrt(n))   |                | stepsize =                      |
|                                 |                |   - O(1/sqrt(n)) under i.i.d.   |
| (believed inherent)             |                |   - Omega(log n/sqrt(n)) under  |
|                                 |                |     only bounded variance       |
+---------------------------------+                +---------------------------------+
         |                                                 |
         | (no distinction)                                | (distinguishes noise structure)
         v                                                 v
   "Last iterate is always         "Last iterate can be as good as average
    a log factor worse than         if noise is i.i.d.; otherwise the log
    the average"                    factor is real and irreducible"

One sentence: From “the last iterate is inherently a log worse than the average” to “the log factor is not inherent but depends on the independence of the noise process.”

Expert Assessment

Problem choice: Real gap — the open problem was explicit and meaningful. The answer cleanly separates two regimes. It sits at the intersection of optimization and high-dimensional probability, a sweet spot.

Method maturity: Clever insight. The proof uses standard martingale tools but the key is identifying that Doob’s inequality gives a $\log n$ factor and that independence allows Azuma–Hoeffding to remove it. The lower bound constructs a simple dependent noise process (a single random sign repeated) that forces the log factor. This is elegant, not brute force.

Experimental integrity: The paper contains no experiments (theory paper), but the lower bound construction is explicit and rigorous. No red flags.

Writing quality: Clear structure, good motivation. Could be improved by including a short intuitive explanation of why the log factor arises in the dependent bound (e.g., using a suboptimal stopping time argument). The introduction could also mention that the one-dimensional restriction is both a strength and a limitation.

Verdict: strong accept — clean, tight, and resolves a concrete open question without overclaiming.

Takeaways

• If your subgradient noise is i.i.d. (e.g., fresh independent samples each iteration), you can safely stop at the last iterate with confidence: the error is $O(1/\sqrt n)$.
• If noise may be dependent (e.g., you are running one pass over a shuffled dataset), use iterate averaging instead of the last iterate, or design a decreasing stepsize schedule that recovers $O(1/\sqrt n)$ for the last point.
• General technique: When analyzing the last iterate, decompose the error into deterministic drift plus a martingale sum. The concentration of that sum depends critically on whether the increments are independent or only bounded in variance. The paper provides a clean template for such decompositions.