Convergence and Reliability Limits of Standard Nonconvex SGD under Heavy-Tailed Noise

Whether standard SGD converges for smooth nonconvex objectives under heavy-tailed gradient noise remains unresolved under the basic combination of standard $L$-smoothness and a bounded $\alpha$-th central moment of the stochastic-gradient noise. We resolve this question and further characterize the high-probability reliability limit of the standard SGD recursion. We study smooth nonconvex optimization under unbiased stochastic gradients whose noise has a bounded $\alpha$-th central moment with $\alpha \in (1,2]$. We first prove that, under a confidence-calibrated learning rate, it holds $\frac{1}{T}{\sum }_{t<T}\Vert \nabla f({\mathbf{w}}^t){\Vert }^2=\text{OO}\left(\frac{L\Delta }{T}+\frac{\sigma \sqrt{L\Delta }}{{\delta }^{1/\alpha }{T}^{(\alpha -1)/\alpha }}\right)$ with at least $1-\delta$ probability. We then characterize the corresponding limitation of standard nonconvex SGD for optimization with heavy-tailed noise. For any deterministic learning rate schedule satisfying $0<{\gamma }_t\le 1/L$, we establish a high-probability lower bound as $\Theta \left(\frac{1}{{\delta }^{1/\alpha }{T}^{(\alpha -1)/\alpha }}\right)$ in the nontrivial regime. Such a result shows that standard nonconvex SGD cannot attain the rate achieved by gradient clipping under heavy-tailed noise, which cannot be removed by learning rate tuning alone.