Can SGD Handle Heavy-Tailed Noise?

arXiv:2508.04860v2 Announce Type: replace-cross Abstract: Stochastic Gradient Descent (SGD) is a cornerstone of large-scale optimization, yet its theoretical behavior under heavy-tailed noise -- common in modern machine learning and reinforcement learning -- remains poorly understood. In this work, we rigorously investigate whether vanilla SGD, devoid of any adaptive modifications, can provably succeed under such adverse stochastic conditions. Assuming only that stochastic gradients have bounded $p$-th moments for some $p \in (1, 2]$, we establish sharp convergence guarantees for (projected) SGD across convex, strongly convex, and non-convex problem classes. In particular, we show that SGD achieves minimax optimal sample complexity under minimal assumptions in the convex and strongly convex regimes: $\mathcal{O}(\varepsilon^{-\frac{p}{p-1}})$ and $\mathcal{O}(\varepsilon^{-\frac{p}{2(p-1)}})$, respectively. For non-convex objectives, under standard smoothness and a bounded central $p$-th moment, we prove convergence to a stationary point with $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$ complexity, and complement this with a matching SGD-specific lower bound, showing that this rate cannot be improved by any deterministic positive non-increasing step-size schedule. These results challenge the prevailing view that heavy-tailed noise renders SGD ineffective, and establish vanilla SGD as a robust and theoretically principled baseline -- even in regimes where the variance is unbounded.

Title:Can SGD Handle Heavy-Tailed Noise?

Abstract:Stochastic Gradient Descent (SGD) is a cornerstone of large-scale optimization, yet its theoretical behavior under heavy-tailed noise -- common in modern machine learning and reinforcement learning -- remains poorly understood. In this work, we rigorously investigate whether vanilla SGD, devoid of any adaptive modifications, can provably succeed under such adverse stochastic conditions. Assuming only that stochastic gradients have bounded $p$-th moments for some $p \in (1, 2]$, we establish sharp convergence guarantees for (projected) SGD across convex, strongly convex, and non-convex problem classes. In particular, we show that SGD achieves minimax optimal sample complexity under minimal assumptions in the convex and strongly convex regimes: $\mathcal{O}(\varepsilon^{-\frac{p}{p-1}})$ and $\mathcal{O}(\varepsilon^{-\frac{p}{2(p-1)}})$, respectively. For non-convex objectives, under standard smoothness and a bounded central $p$-th moment, we prove convergence to a stationary point with $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$ complexity, and complement this with a matching SGD-specific lower bound, showing that this rate cannot be improved by any deterministic positive non-increasing step-size schedule. These results challenge the prevailing view that heavy-tailed noise renders SGD ineffective, and establish vanilla SGD as a robust and theoretically principled baseline -- even in regimes where the variance is unbounded.

40 pages, 5 figures, 2 tables. Extended version of a paper accepted for publication in the SIAM Journal on Optimization

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2508.04860 [math.OC]

(or arXiv:2508.04860v2 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2508.04860 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Can SGD Handle Heavy-Tailed Noise?

Related coverage