理论研究者终于有了 AdaGrad 在重尾噪声下的收敛保证，做优化算法分析的人值得关注——它解释了为何 Adam 等自适应方法在真实场景中表现稳健，且无需额外操作。
现代机器学习优化中常出现重尾梯度噪声，传统方法需梯度裁剪或归一化来保证收敛。本文首次证明 AdaGrad（自适应梯度方法的起源）在非凸优化中，当尾指数 p 满足 4/3 < p ≤ 2 时无需任何算法修改即可收敛，且无需预先知道 p 值。研究还给出了算法相关的下界，表明 AdaGrad 无法达到重尾优化的最优 minimax 速率。对于 AdaGrad-Norm 变体，在额外温和假设下，收敛率可推广到任意 1 < p ≤ 2。
Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad
Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular $\mathtt{Adam}$ and $\mathtt{AdamW}$, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case, $\mathtt{AdaGrad}$, the origin of adaptive gradient methods. We provide the first provable convergence rate for $\mathtt{AdaGrad}$ in non-convex optimization when the tail index $p$ satisfies $4/3<p\leq2$. Notably, this result is achieved without requiring any prior knowledge of $p$ and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by $\mathtt{AdaGrad}$. Lastly, we consider $\mathtt{AdaGrad}\text{-}\mathtt{Norm}$, a popular variant of $\mathtt{AdaGrad}$ in theoretical studies, and show an improved rate that holds for any $1<p\leq2$ under an extra mild assumption.