证明了原始SGD在重尾噪声下仍能收敛,无需自适应调整。
Can SGD Handle Heavy-Tailed Noise?
- 基于梯度的p阶矩有界假设,分析了不同优化问题下的收敛性。
- 在凸与强凸场景下达到最优样本复杂度,非凸时收敛到驻点。
- 适用于无方差限制的现实训练场景,为模型设计提供理论依据。
随机梯度下降(SGD)是大规模优化的核心方法,但在现代机器学习与强化学习中常见的重尾噪声环境下,其理论行为仍不明确。本文在仅假设随机梯度具有有限$p$-阶矩($p \in (1, 2]$)的前提下,严格证明了原始(投影)SGD在凸、强凸及非凸问题中的收敛性。具体而言,在凸与强凸情形下,SGD实现最小可达到的样本复杂度:$\mathcal{O}(\varepsilon^{-\frac{p}{p-1}})$ 与 $\mathcal{O}(\varepsilon^{-\frac{p}{2(p-1)}})$;在满足Hölder光滑性的非凸目标下,收敛到驻点的速率为 $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$,并给出针对任意多项式步长策略的匹配下界。此外,在标准光滑性与中心矩有界假设下,非凸小批量SGD也达到类似的 $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$ 样本复杂度,且平滑常数可能更优。这些结果挑战了重尾噪声使SGD失效的普遍认知,确立了原始SGD作为鲁棒且理论可靠的基准。
原文摘要 · Abstract (English)
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 Hölder smoothness, we prove convergence to a stationary point with rate $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$, and complement this with a matching lower bound specific to SGD with arbitrary polynomial step-size schedules. Finally, we consider non-convex Mini-batch SGD under standard smoothness and bounded central moment assumptions, and show that it also achieves a comparable $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$ sample complexity with a potential improvement in the smoothness constant. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。