首次证明Adam在重尾噪声下仍能收敛,但效率不如理想情况。
The Convergence Behavior of Adam under Heavy-Tailed Noise
- 基于广义在线转非凸框架,分析Adam在重尾噪声下的表现
- 收敛至(ρ,ε)-平稳点,迭代复杂度为O(ε^{-13/2})(当p=2)
- 适用于研究Adam鲁棒性或优化理论的学者
我们首次为向量形式的原始Adam优化器在重尾随机噪声下建立了收敛保证。尽管若干Adam变体在有界方差的非光滑非凸优化中已知能达到最优迭代复杂度,但对其在随机梯度仅具有有限p阶中心矩(p∈(1,2])情形下的行为仍知之甚少,而此类情形在现代深度学习中日益普遍。为填补这一空白,我们将近期的在线转非凸转换框架推广至容纳重尾鞅差噪声。在此基础上,我们对Adam进行了无严格参数耦合的折扣后悔分析。结果表明,Adam在重尾噪声下可收敛至(ρ,ε)-平稳点。然而,其迭代复杂度次优且依赖于p值,即使在有界方差情形(p=2)下仍存在该缺陷。具体而言,达到期望平稳性的ε主导项复杂度为T=O(Δρ^{1/2}(G+σ)^{5p/(3p-4)}ε^{-(5p/(3p-4)+3/2)}),当p=2时简化为T=O(ε^{-13/2})。若已知域半径并用于控制在线学习者输出(文献常见设定),收敛速率可提升至最优,此时复杂度为T=O(Δρ^{1/2}(G+σ)^{p/(p-1)}ε^{-(p/(p-1)+3/2)}),p=2时为T=O(ε^{-7/2})。这些发现为Adam在重尾环境下的鲁棒性与局限性提供了新的理论洞见。
原文摘要 · Abstract (English)
We establish the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise. While several Adam variants are known to achieve optimal iteration complexity in bounded-variance nonsmooth nonconvex optimization, little is understood about their behavior when stochastic gradients admit only a bounded $p$-th central moment for some $p \in (1,2]$, a setting increasingly observed in modern deep learning. To address this gap, we generalize the recent online-to-nonconvex conversion framework to accommodate heavy-tailed martingale-difference noise. Building on this generalized framework, we develop a discounted regret analysis for Adam, without restrictive parameter coupling. Our results show that Adam converges to $(ρ,ε)$-stationary points under heavy-tailed noise. However, it exhibits a suboptimal iteration complexity and $p$-dependent convergence, a suboptimality that persists even in the bounded-variance case ($p=2$). Specifically, the $ε$-dominant term in the iteration complexity for reaching in-expectation stationarity is $T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{5p}{3p-4}}ε^{-\left(\frac{5p}{3p-4}+\frac{3}{2}\right)}\right)$ for $p\in(\frac{4}{3},2]$, which simplifies to $T=\mathrm{O}(ε^{-13/2})$ when $p=2$. When the domain radius is known and used to control the online-learner output, a standard setup in related literature, the convergence rate improves to match the optimal complexity. In this case, the $ε$-dominant iteration complexity is $T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{p}{p-1}}ε^{-\left(\frac{p}{p-1}+\frac{3}{2}\right)}\right)$ for $p\in(1,2]$, which simplifies to $T=\mathrm{O}(ε^{-7/2})$ when $p=2$. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。