Acceleration Survives Heavy Tails and Generalized Smoothness

We establish high-probability accelerated convergence guarantees for convex $(L_0,L_1)$-smooth optimization with unbiased stochastic gradients under heavy-tailed noise, assuming a central $\alpha$-th noise moment bounded by ${\sigma }^{\alpha }$, $\alpha \in (1,2]$. Such guarantees are known under classical $L$-smoothness, but extending them through localization over an $O(R)$-radius ball may introduce an $e^{O(L_{1}R)}$ factor. We avoid this dependence in two ways. First, a two-phase scheme uses Clip-SGD to reach a low-curvature regime, after which clipped stochastic similar triangles (Clip-SSTM) attains, with probability at least $1-\delta$, $f(y_K)-f^{\star }\le \tilde{\mathcal{O}}(L_0{R}^2\mathrm{/}{K}^2+\sigma R{K}^{-(\alpha -1)\mathrm{/}\alpha }),$ where $R$ bounds the distance from the Phase-II starting point to a minimizer. Second, a modified deterministic weight schedule allows 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 $L_1$ 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.