- Rating
- 4
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
Muon has recently achieved strong empirical gains over AdamW. Some researchers attribute this advantage to Muon’s robustness to heavy-tailed gradient noise, arguing that it admits sharper convergence rates than AdamW. This paper challenges this view by proving that AdamW and Adam-mini attain the same sharp convergence rate as Muon under heavy-tailed noise. this paper further establishes a general lower bound on stochastic stationarity for smooth non-convex optimization, with an unavoidable dependence. Together, these results show that heavy-tailed noise alone cannot explain Muon’s empirical advantage.
Critical strengths
-
This paper proves that AdamW and Adam-mini attain the same sharp convergence rate as Muon under heavy-tailed noise, thereby showing that heavy-tailed noise alone cannot explain Muon’s empirical advantage.
-
This paper establishes a general lower bound on stochastic stationarity for smooth non-convex optimization, with an unavoidable dependence, thereby showing that the existing convergence rate of Adam/AdamW is optimal under the classical finite-variance noise assumption.
These contributions address two open problems regarding Adam’s convergence, and I strongly recommend acceptance.
Critical weaknesses
I find this paper valuable and have no concerns.
Questions for authors
Question: Can we prove the same sharp convergence rate for SGD with momentum? If so, I suggest adding the new result to Table 3; otherwise, I suggest including a discussion in the appendix.
Minor suggestion regarding the comparison on lines 320–323: Li et al. (2025a) established convergence under the classical bounded-noise-variance assumption in the arXiv version (arXiv:2505.11840v4).
The above question and suggestion do not affect my appreciation of this paper.
3 comments
Thanks for the response. I keep my original score, 4.
Thank you very much for your response! We sincerely appreciate your continued support for our work.
We sincerely thank the reviewer for the encouraging review and for recognizing the contributions of our work! We appreciate both suggestions and have revised the paper accordingly. All changes are marked in blue.
The answer is negative. Prior work (Liu, 2026c; Yamada et al., 2026) has shown that the convergence upper bound for SGD with momentum (SGDM) is O(T−(p−1)/(2p)), which is slower than the O(T−(p−1)/(3p−2)) rate in Table 3. Whether this stems from a loose analysis or reflects a genuine separation between SGDM and other optimal algorithms (AdamW and Muon) remains unknown. In this rebuttal, we show that the O(T−(p−1)/(2p)) upper bound is indeed tight for SGDM, indicating that vanilla SGDM is inherently slower than AdamW and Muon under heavy-tailed noise. Our results can be found in Appendix G in the updated manuscript. Below, we outline the main idea.
We now prove a matching lower bound (new Theorem 15 in Appendix G). For any fixed momentum β<1 and any deterministic non-increasing learning rates, there is an instance in our problem class such that
\frac1T\sum_{t=1}^T\mathbb E\\|\nabla F(x_t)\\| \gtrsim\min\left\\{(1-\beta)\sqrt{L\Delta}, \sqrt{1-\beta}\,\sigma^{1/2}(L\Delta)^{1/4}T^{-\frac{p-1}{2p}}\right\\}.
The proof extends the SGD construction of Fatkhullin et al. (2025b). The core proof idea is to cope with a rare noise sample launching the iterate onto a long descending plateau, which we lengthen to absorb the residual velocity left by momentum. The result covers heavy-ball SGDM and the common EMA and PyTorch momentum-buffer implementations.
This resolves the tightness question of the known SGDM heavy-tailed upper bound (Liu, 2026c). For 1<p<2, it implies a strict worst-case gap from AdamW, Muon, and normalized SGDM: T−(p−1)/(2p) versus T−(p−1)/(3p−2), e.g., T−1/6 versus T−1/5 at p=3/2 (Corollary 16). At p=2, the exponents coincide. Since this is an algorithm-specific lower bound rather than a minimax complexity, we present it in Appendix G instead of Table 3.
Normalized SGDM. For completeness, we also added normalized SGDM (NSGDM) to Table 3, with the aim of showing how normalization helps SGDM to fight against heavy-tailed stochasticity, which is well-known within the optimization community. Hübler et al. (2025) and Liu and Zhou (2025) established its optimal convergence. Combined with our lower bound, its minimax complexity in Frobenius stationarity matches that of AdamW and Muon (Appendix G.1). A short paragraph at the end of Section 5 summarizes both points.
Thank you for pointing us to the updated version. We have corrected the corresponding lines in the updated manuscript.
References
Zijian Liu. In-expectation convergence of stochastic gradient methods under heavy-tailed noise. arXiv preprint arXiv:2606.00520, 2026c.
Ryusei Yamada, Naoki Sato, and Hideaki Iiduka. Vanilla SGD with momentum survives heavy-tailed noise: Convergence analysis without gradient clipping or normalization. In Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), pp. 7670–7700, 2026.
Ilyas Fatkhullin, Florian Hübler, and Guanghui Lan. Can SGD handle heavy-tailed noise? arXiv preprint arXiv:2508.04860, 2025b.
Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed SGD. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2413–2421, 2025
Zijian Liu and Zhengyuan Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. In International Conference on Learning Representations (ICLR), pp. 92529–92554, 2025.