paper
arXiv cs.LG
October 28th, 2026 at 4:00 AM

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

arXiv:2610.33381v2 Announce Type: new Abstract: 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 \beta_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$.

#ai

Get stories like this every Monday

The week's most important AI news in one email. Free, unsubscribe anytime.

Score: 2.82

Engagement proxy: 0

Canonical link: https://arxiv.org/abs/2610.33381