在重尾噪声下，经典优化方法仍可期望收敛，突破了传统认知。
In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
- 基于新分析框架，证明多种梯度方法在重尾噪声下收敛。
- 无需修改算法，且不依赖有界域等强假设，结果更通用。
- 为理解一阶随机优化提供了全新视角，适合优化理论研究者。
许多随机梯度方法在梯度噪声仅具有有限 $p$-阶矩（$p\in(1,2)$）的重尾噪声假设下，被认为无法收敛。然而，近期研究表明，未经修改的随机梯度下降（SGD）在凸问题且定义域有界的条件下，仍可在期望意义下收敛，展现出经典方法的潜力。受此启发，本文系统研究了重尾噪声下的随机优化，建立了随机镜面下降（SMD）、加速随机镜面下降（ASMD）在凸优化中的期望收敛性，以及SGD和带动量的随机梯度下降（SGDM）在非凸优化中的期望收敛性。关键在于，这些结果无需算法改动，也避免了以往工作对有界域等限制性假设的依赖。更重要的是，本文提出了一种新颖、简洁而强大的分析框架，为重尾随机优化研究开辟了新路径，深化了对一阶随机梯度方法的理解。
原文摘要 · Abstract (English)
Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite $p$-th moment for $p\in\left(1,2\right)$, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent ($\textsf{SGD}$), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent ($\textsf{SMD}$) and Accelerated Stochastic Mirror Descent ($\textsf{ASMD}$) in convex optimization, and for $\textsf{SGD}$ and Stochastic Gradient Descent with Momentum ($\textsf{SGDM}$) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。