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

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

[Submitted on 24 Oct 2026 (v1), last revised 3 Nov 2026 (this version, v3)]

View PDF HTML (experimental)

Abstract:We study the last iterate of clipped SGD, and of every rule that queries its current iterate and steps along the resulting stochastic gradient, when training is stopped at a data-dependent time, so that guarantees must hold at all times simultaneously. On smooth convex objectives under heavy-tailed noise with a bounded central $p$th moment, $1beta_p$, even with adaptive step sizes and thresholds. This rate lies between the optimal rate $O(T^{-alpha_p})$ for a known horizon $T$, $alpha_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^{-alpha_p})$ at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on $beta_p$.

Submission history

From: Yuxing Peng [view email]
[v1] Sat, 24 Oct 2026 00:39:50 UTC (157 KB)
[v2] Tue, 27 Oct 2026 02:19:08 UTC (147 KB)
[v3] Tue, 3 Nov 2026 06:27:09 UTC (213 KB)

Related Posts