Acceleration Survives Heavy Tails and Generalized Smoothness
En palabras de los autores
We establish high-probability accelerated convergence guarantees for convex -smooth optimization with unbiased stochastic gradients under heavy-tailed noise, assuming a central -th noise moment bounded by , . Such guarantees are known under classical -smoothness, but extending them through localization over an -radius ball may introduce an factor. We avoid this dependence in two ways. First, a two-phase scheme uses \algname{Clip-SGD} to reach a low-curvature regime, after which clipped stochastic similar triangles (\algname{Clip-SSTM}) attains, with probability at least , where bounds the distance from the Phase-II starting point to a minimizer. Second, a modified deterministic weight schedule allows \algname{Clip-SSTM} to start directly from the initial point, controlling the high-curvature transient before recovering acceleration. With the prescribed initialization, both approaches recover the classical accelerated rate, with confined to an accuracy-independent transient, up to logarithmic factors. The two-phase analysis uses two coupled potentials to preserve the low-curvature regime despite momentum; the one-phase analysis controls the initial high-curvature regime using a modified version of the classical SSTM weight schedule.
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.