← All papers
First page of The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

Yuxing Peng, Zhiqing Tang, Weijia Jia

cs.LG Oct 24, 2026 · v2
Lean 4 with Mathlib machine-checks the lower bounds (Theorems 5 and 11(i)) and the known-horizon last-iterate bound for clipped SGD.
Training is often stopped at a data-dependent time, so guarantees for the last iterate must hold at all times simultaneously. We determine the optimal time-uniform rate for the last iterate of clipped SGD on smooth convex objectives under heavy-tailed noise with a bounded central $p$th moment, $1<p\le2$. A schedule without horizon or confidence inputs attains $\tilde O(t^{-β_p})$ at all times, with $β_p=2(p-1)/(3p-1)$, also almost surely, and no rule that steps along the stochastic gradient at its current iterate attains $\tilde O(t^{-r})$ for any $r>β_p$, even with adaptive step sizes and thresholds. This rate lies between the optimal rate $O(T^{-α_p})$ for a known horizon $T$, $α_p=(p-1)/p$, and the previous time-uniform rate $\tilde O(t^{-2(p-1)/(3p)})$ (Chezhegov et al., ICLR 2026); under finite variance, the exponents are $1/2$, $2/5$, and $1/3$. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon (Liu; Jiang et al.) but fails without one. Querying gradients at the running average attains $\tilde O(t^{-α_p})$ at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on $β_p$.

Training runs often stop at a data-dependent time, so last-iterate guarantees must hold at all times simultaneously. The question is the optimal time-uniform high-probability rate for the last iterate of clipped SGD on smooth convex objectives under heavy-tailed noise with a bounded central pth moment, 1<p≤2.

A horizon-free and confidence-free step-size and clipping schedule is analyzed with a recursively averaged suffix potential. A matching lower bound covers all rules that step along the stochastic gradient at the current iterate. Running-average queries and heavy-ball momentum are also analyzed. Key theorems (the lower bound Theorem 5, Theorem 11(i), and the known-horizon bound Theorem 1) are machine-checked in Lean 4 with Mathlib.

The time-uniform rate Õ(t^{-β_p}) with β_p=2(p-1)/(3p-1) is attained, also almost surely, and is optimal for current-iterate gradient rules. This refutes the conjecture of Chezhegov et al. that the optimal known-horizon rate is reachable without a horizon. Querying gradients at the running average attains Õ(t^{-α_p}) at all times, while heavy-ball momentum with geometric forgetting cannot beat β_p.

Guarantee requiredGradient at current iterateGradient at running average
Known horizon TT^{-1/2}T^{-1/2}
Fixed time, confidence δ^{-1/2}t^{-1/2}t^{-1/2}
Fixed time, confidence log(1/δ)t^{-2/5}t^{-1/2}
All times (any stopping time)t^{-1/3} → t^{-2/5}t^{-1/2}
Best last-iterate error at p=2