跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.33381 · v3

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

Yuxing PengZhiqing TangWeijia Jia
cs.LG
首次提交 2026-10-24 08:39
版本更新 2026-11-03 14:27
雷达观测 2026-11-04 23:40
arXiv ↗PDF ↗

摘要

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, $1<p\le2$, we determine the optimal time-uniform rate of these rules. A clipped SGD 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 such rule 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$.

作者备注：44 pages, including appendices and references. Lean 4 proofs of Theorems 2, 4, and 8 and of the known-horizon bound of Theorem 1, and the script of the numerical illustration, are included as ancillary files; the Lean code is also at https://github.com/Thefootofhappiness/clipped-sgd-last-iterate-lean

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存，登录后共享已有结果。

版本差异

仅对比实际观测的元数据，不代表 PDF 正文或实验变化。版本可能不连续；带删除线为移除，下划线为新增。

摘要变化

TrainingWe isstudy oftenthe stoppedlast atiterate aof data-dependentclipped timeSGD, soand guaranteesof forevery therule lastthat queries its current iterate mustand holdsteps atalong allthe timesresulting simultaneously.stochastic Wegradient, determinewhen thetraining optimalis timestopped at a data-uniformdependent ratetime, forso thethat lastguarantees iteratemust ofhold clippedat SGDall ontimes simultaneously. On smooth convex objectives under heavy-tailed noise with a bounded central $p$th moment, $1<p\le2$, we determine the optimal time-uniform rate of these rules. A clipped SGD 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 currentsuch iteraterule 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$.

作者备注变化

4344 pages, including appendices and references. Lean 4 proofs of Theorems 2, 4, and 8(i) and of the known-horizon bound of Theorem 1, and the script of the numerical illustration, are included as ancillary files; the Lean code is also at https://github.com/Thefootofhappiness/clipped-sgd-last-iterate-lean

观测到的版本

相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-03 14:27 · 最新观测版本

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

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, $1<p\le2$, we determine the optimal time-uniform rate of these rules. A clipped SGD 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 such rule 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$.

查看此版本解读 →查看此版本原文 ↗
v2 · 2026-10-27 10:19

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

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$.

查看此版本解读 →查看此版本原文 ↗