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^{-\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 원문에서 확인하세요.
- arXiv:2610.33381v3제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.