arXiv:2610.33381v3 cs.LG

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

Yuxing Peng, Zhiqing Tang, Weijia Jia

제출 2026-11-04

원문 초록

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^{-\beta_p})$ at all times, with $\beta_p=2(p-1)/(3p-1)$, also almost surely, and no such rule attains $\tilde O(t^{-r})$ for any $r>\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$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.33381v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.