The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
Overview & Synopsis
Training is often stopped at a data-dependent time, as in early stopping, and the last iterate is kept. Guarantees valid at such times 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$, 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, as shown by Liu and by Jiang et al., but fails without one. Querying gradients at the running average of the iterates attains $\tilde O(t^{-α_p})$ at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on $β_p$.
arxiv.org)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise |
|---|---|
| Author / Organization | Yuxing Peng, Zhiqing Tang, Weijia Jia |
| Subject & Discipline | cs.LG |
| Categories | Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-116506 |
| Original Source Link | Visit Source Page on arxiv.org » |