The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
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 required | Gradient at current iterate | Gradient at running average |
|---|---|---|
| Known horizon T | T^{-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} |
