arXiv preprint ·
The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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<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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
One Call Ahead: Packed Self-Speculative Decoding with Diffusion Drafting
Continual Learning Exam: Benchmarking Long-Horizon RSI and Experiential Learning in LLM Agents
A Nonconvex Framework for Joint Sparse Sample Weighting and Parameter Estimation
Faithful Federated Tabular Data Synthesis
How Do Small Coding Agents Use Code Graphs and Embeddings?
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.