acceptodds
Under review as a conference paper at ICLR 2027

On the Optimality of Adam under Heavy-Tailed Noise

Abstract

Adam is the canonical optimizer in deep learning, and its decoupled weight decay variant AdamW is widely used for training large language models (LLMs). Meanwhile, Muon has recently achieved strong empirical gains over AdamW. One proposed explanation is robustness to heavy-tailed gradient noise: Muon admits sharp convergence rates, whereas Adam could behave poorly in such settings. This contrast motivates a basic question of whether Adam can converge optimally under heavy-tailed noise. We answer affirmatively through a stronger result for Adam-mini, a blockwise framework that encompasses Adam and Adam-Norm. Under heavy-tailed th noise moment, we prove that Adam-mini attains the sharp rate . Our theory also supports bias correction and weight decay, thereby covering AdamW as a special case. We further establish a matching lower bound that proves minimax optimality and, as a consequence, yields the first general stochastic stationarity lower bound for smooth non-convex optimization with an unavoidable dependence, where is the problem dimension. Together, these results sharply characterize heavy-tailed convergence for Adam and its variants. Comparing the Adam directly with Muon under the same problem class, we show that, unlike prior justifications, heavy-tailed noise alone cannot explain Muon's empirical advantage.

Primary area:
optimization
Keywords:
Adam, heavy-tailed noise, Adam-mini, Muon, upper and lower bounds, nonconvex stochastic optimization, LLMs

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_rJVbOpenReview ↗
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 ℓ1\ell_1​ stationarity for smooth non-convex optimization, with an unavoidable d\sqrt{d} dependence. Together, these results show that heavy-tailed noise alone cannot explain Muon’s empirical advantage.

Critical strengths
  1. 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.

  2. This paper establishes a general lower bound on stochastic ℓ1\ell_1​ stationarity for smooth non-convex optimization, with an unavoidable d\sqrt{d}​ 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

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.


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.

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))O(T^{-(p-1)/(2p)}), which is slower than the O(T−(p−1)/(3p−2))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))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\beta<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<21<p<2, it implies a strict worst-case gap from AdamW, Muon, and normalized SGDM: T−(p−1)/(2p)T^{-(p-1)/(2p)} versus T−(p−1)/(3p−2)T^{-(p-1)/(3p-2)}, e.g., T−1/6T^{-1/6} versus T−1/5T^{-1/5} at p=3/2p=3/2 (Corollary 16). At p=2p=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.

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).

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.

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.

Reviewer_1vjmOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the convergence of Adam under heavy-tailed noise. Specifically, the authors establish convergence guarantees for Adam-mini under heavy-tailed noise, recovering Adam, Adam-Norm, and AdamW as special cases. Furthermore, they establish matching lower bounds for first-order stationarity, proving the minimax optimality of Adam and its variants. Finally, the authors show that Adam and Muon achieve the same minimax optimal convergence rate under the same oracle model, thereby challenging the claim that Muon's advantage can be explained by its robustness under heavy-tailed noise.

Critical strengths
  • The paper shows convergence guarantees under heavy-tailed gradient noise, a setting that is relevant in modern machine learning. The analysis also accommodates bias correction and decoupled weight decay, which correspond to the practical implementations of Adam. Furthermore, the convergence rate matches the established lower bound, showing the minimax optimality of Adam and its variants under heavy-tailed noise.
  • The paper provides a clear comparison with related work, highlighting the differences in the assumptions, convergence rates, and limitations, thus helping clarify the paper's contributions and its positioning relative to prior work.
  • The result on the comparison of Adam and Muon nicely complements the paper's contributions by providing further insight into existing explanations for Muon's empirical advantage.
Critical weaknesses
  • The theoretical choices of the stepsize η\eta and momentum parameter β2\beta_2 in Theorems 1 and 3 depend on the optimality gap Δ\Delta, which is generally unknown in practice. Moreover, the parameter ϵalg\epsilon_{\mathrm{alg}} (and ϵbc\epsilon_{\mathrm{bc}} in Theorem 3) depends on the noise level σ\sigma and the parameter pp, which may also be difficult to estimate. Additionally, the condition in Eq. (3) implicitly imposes a lower bound on the number of iterations TT, as discussed in Remark 3, which is not immediately apparent from the theorem statement.
  • Another theoretical limitation is that for a fixed problem dimension dd, the dimension requirement in equation (16) of Theorem 5 may not hold for arbitrarily small ϵ\epsilon.
Questions for authors

See weaknesses.

3 comments

We sincerely thank the reviewer for the careful reading and the constructive review! We address each concern below and have revised the manuscript accordingly.

The theoretical choices of the stepsize η\eta and momentum parameter β2\beta_2 depend on the optimality gap Δ\Delta ... the parameter ϵalg\epsilon_{\rm alg} depends on the noise level σ\sigma and the parameter pp, which may also be difficult to estimate.

Thank you for raising this practical issue. The tuning in Theorems 1 and 3 uses Δ\Delta and σ\sigma to balance the optimization and noise terms, which gives the optimal dependence on all problem parameters. The closest finite-variance analysis of AdamW (Li et al., 2025a, Theorem 1) makes the same choice.

Without Δ\Delta and σ\sigma. We prove a new Theorem 10 (Appendix C.9). Let Lˉ≥L\bar L\ge L and ε0>0\varepsilon_0>0 be any user-chosen values. Run Algorithm 1 with B=1B=1, λ=0\lambda=0, 1−β2≤1−β1≤2(1−β2)1-\beta_2\le1-\beta_1\le2(1-\beta_2), and set the hyperparameters as in Eq. (87). After an explicit burn-in (Eq. (88)),

\lesssim \frac{\Delta\bar L+\varepsilon_0^2+\sigma^2}{\varepsilon_0\sqrt T} +\sqrt{\left(\Delta\bar L+\varepsilon_0^2+\sigma^2\right)\left(1+\frac{\sigma}{\varepsilon_0}\right)}\\;T^{-\frac{p-1}{3p-2}}.$$ The hyperparameters use neither $\Delta$ nor $\sigma$, and the rate in $T$ is still optimal, matching Theorem 1. The price is a *weaker dependence on the problem parameters*, since the leading coefficient grows as $(\Delta\bar L)^{1/2}$ instead of $(\Delta L)^{\frac{p-1}{3p-2}}$. **Without $p$ as well.** Proposition C.1 (Appendix C.10) gives a tuning that needs none of $p$, $\Delta$, $\sigma$: $1-\beta_2=T^{-1/2}$, $\eta=\varepsilon_0(1-\beta_2)/(8\bar L\sqrt d)$, and $\epsilon_{\rm alg}=\varepsilon_0/\sqrt d$ (Eq. (93)). Its rate is $O(T^{-(5p-6)/(8p)})$ (Eq. (95)), which is valid for $p\in(6/5,2]$ and recovers the optimal $T^{-1/4}$ at $p=2$. For $p<2$ the exponent is smaller than the optimal one. Proposition C.2 (Eq. (100)) shows that this loss comes from the tuning itself and not from the analysis. On a one-dimensional instance, this tuning cannot beat $T^{-(5p-6)/(8p)}$ up to logarithmic factors. Whether other $p$-free tunings attain the optimal exponent is open, which is interesting to explore for future work. > *Additionally, the condition in Eq. (3) implicitly imposes a lower bound on the number of iterations $T$, as discussed in Remark 3, which is not immediately apparent from the theorem statement.* Thanks for the suggestion! Theorem 1 now states Eq. (3) directly as a burn-in condition on $T$, and Theorem 3 and Remark 3 are updated accordingly. In the high-accuracy regime of interest, Eqs. (6) and (12), the burn-in is implied by the leading stochastic budget, so Theorems 2, 4, and 6 need no additional condition on $T$. > *Another theoretical limitation is that for a fixed problem dimension $d$, the dimension requirement in equation (16) of Theorem 5 may not hold for arbitrarily small $\epsilon$.* The original submission *already contains a relaxed lower bound* for this case. Proposition E.1 in Appendix E.5 replaces Eq. (16) with the much milder condition $d\ge C_p\log(2+Q_\varepsilon)$ (Eq. (173)), at the price of the weaker bound in Eq. (174), which recovers Theorem 5 for large $d$. This condition needs $d$ to grow only logarithmically in $1/\varepsilon$. We added Appendix E.7 to explain why it is to some extent inherent to our lower bounds. Some algorithms can trade a worse dependence on $d$ for a better one on $1/\varepsilon$ (Carmon et al., 2020), as do the lower bounds that Theorem 5 builds on (Carmon et al., 2020; Arjevani et al., 2023). In low dimensions, the complexity can indeed differ. For example, Chewi et al. (2023) show that randomized methods with exact gradients need only $\Theta(1/\varepsilon)$ queries instead of $\Theta(1/\varepsilon^2)$ for one dimension. The fixed-dimension complexity under heavy-tailed noise is an interesting open question. We suspect that if we aim for information-theoretic lower bounds, like Theorem 5 in our paper, then the dimension requirement might be necessary. However, if we aim for algorithm-specific lower bounds, like Jiang et al. (2025a), then the dimension requirement could possibly be removed using geometry-aware constructions. **References** Li et al. On the $O(\sqrt d/K^{1/4})$ convergence rate of AdamW measured by $\ell_1$ norm. In NeurIPS 2025 Carmon et al. Lower bounds for finding stationary points I. Mathematical Programming 2020 Arjevani et al. Lower bounds for non-convex stochastic optimization. Mathematical Programming 2023 Chewi et al. On the complexity of finding stationary points of smooth functions in one dimension. In ALT 2023 Jiang et al. Provable complexity improvement of AdaGrad over SGD: Upper and lower bounds in stochastic non-convex optimization. In COLT 2025

Thank you for your efforts during the rebuttal and for the detailed explanations! My concerns have been addressed. Since my score is already positive, I will keep my score.

Thank you for your feedback and for taking the time to consider our responses. We truly appreciate your constructive comments and positive assessment of our paper.

Reviewer_MoPhOpenReview ↗
Rating
3
Confidence
3
Informativeness
3(+1)
Presentation
2(+1)
Soundness
3
Read review
Paper summary

This paper aims to refute a prior conjecture saying that Muon is empirically better than AdamW due to Muon's robustness to heavy tailed gradient noise. The authors show the refutation by proving tight upper and lower bounds for AdamW and Muon in the presence of heavy tailed gradient noise (formalized as a bounded condition on the pp-th moment of the gradient noise), and showing that both algorithms achieve the same (minimax) rate.

Critical strengths

The main strengths of the paper are in the thorough theoretical analysis:

  • the authors prove that AdamW (and block variants) achieve the optimal rate as a function of TT and pp in the presence of stochastic gradients, with bounded pp-th moments
  • the authors close an open conjecture via tight upper and lower bounds over smooth problems for Muon and AdamW. The core and tail decomposition used in thm 2 is an interesting way to approach rare outliers
Critical weaknesses

In my opinion the main weakness of this paper is that it is very hard to read. The main body is very dense, with a lot of notation, and quite result packed (the manuscript totals 68 pages). I believe a general rewriting and organization would really improve the legibility of what is otherwise a good contribution. The exposition of the theorems could also be improved: for example, in the main body the constants could be absorbed in ≲\lesssim, and referred to the full statement (with constants) in the appendix.

Moreover, given that this is a theory paper, I would have preferred to see synthetic experiments verifying the theorem results, outside of Figure 1 (such as checking the dependencies in dd, varying pp, checking if the tuned hyperparameters match the theoretical prediction).

Questions for authors
  1. Could it be that the empirical difference can be explained by the fact that under this broad class of problems (smooth non-convex) the 2 algorithms are the same (AdamW and Muon) in terms of rates as a function of T, but on a smaller class (smooth and convex, or even linear or logistic regression with heavy tailed gradient noise), there would be a gap? Do you believe there is a model that could show this?

  2. I am not sure if I understand correctly, but for the theorems, is β1\beta_1 also tuned, or is it coupled to β2\beta_2?

  3. And in general, do you think the assumption β22≤β1≤β2\beta_2^2 \leq \beta_1 \leq \beta_2 can be relaxed - if I'm not mistaken, you require this in order to ensure that large outliers are not in the EMA for an O(T) duration? As it stands, it seems very strong beause it doesn't allow (as you mentioned in line 218) general values that come out of tuning in LLM pretraining.

4 comments
AuthorsOpenReview ↗

Official Comment by Authors (Part 1/2)

We sincerely appreciate the reviewer for the careful reading and the constructive suggestions! We address each point below and have revised the manuscript accordingly. All changes are marked in blue.


Weakness 1 (readability). We are sorry that the paper felt dense, and thank you for the concrete suggestion. We have hidden the constants in the main text. All main results (Theorems 1–5, Corollary 7, and Theorem 8) are now stated with ≲\lesssim and ≳\gtrsim, and the explicit constants appear only in the appendix proofs (e.g., Eqs. (86) and (136)). We also improved the presentation and fixed several other points, all marked in blue. If you have further requests, we are happy to keep improving.


Weakness 2 (synthetic experiments). We added Appendix J with three synthetic experiments, one for each check you listed. Each uses a non-convex objective with known LL and Δ\Delta and runs Adam with the hyperparameters of Theorem 3 (B=1B=1, λ=0\lambda=0, β1=β2\beta_1=\beta_2). The metric is ST=1T∑t∣∇F(xt)∣1/dS_T=\frac1T\sum_{t}\\|\nabla F(x_t)\\|_1/\sqrt d.

  • Dimension (Figure 8). With L=Δ=σ=1L=\Delta=\sigma=1, p=1.5p=1.5, and d∈{4,16,64,256}d\in\{4,16,64,256\}, the bound on STS_T has no explicit dd factor, so dST\sqrt d S_T should grow like d\sqrt d. The log–log slope of d ST\sqrt d\,S_T against dd is 0.49970.4997 (95% CI [0.4991,0.5003][0.4991,0.5003]), and STS_T itself changes by at most 0.14%0.14\% across dimensions.
  • Heavy-tail pp (Figure 9). For p∈1.25,1.5,1.75,2p\in\\{1.25,1.5,1.75,2\\} and T=212,…,216T=2^{12},\dots,2^{16} with 512 seeds per setting, the fitted slopes of STS_T against TT are −0.142,−0.192,−0.229,−0.251-0.142,-0.192,-0.229,-0.251. The predicted slopes −(p−1)/(3p−2)-(p-1)/(3p-2) are −0.143,−0.200,−0.231,−0.250-0.143,-0.200,-0.231,-0.250, and each lies inside the 95% bootstrap interval of its fit. So the slope of our bound matches perfectly with the theoretical value −(p−1)/(3p−2)-(p-1)/(3p-2) of pp.
  • Learning rate (Figure 10, Table 11). We keep all other hyperparameters at their theoretical values and sweep only η=cηth\eta=c \eta_{\rm th}, where ηth\eta_{\rm th} is the learning rate value predicted by theory. On 24 tuning seeds, the best multiplier is c=1.125c=1.125 at T=219T=2^{19} and c=1c=1 at T=220T=2^{20}, and every c∈[0.75,1.5]c\in[0.75,1.5] is within 5% of the best value. On 64 held-out seeds, ηth\eta_{\rm th} is within 0.4%0.4\% of the best other multiplier, 1.125ηth1.125\eta_{\rm th}, at both horizons. Figure 10 further confirms that the value predicted by theory aligns closely with the best chosen empirically.

Question 1 (advantage of Muon on smaller problem classes). Yes, such a gap exists, and we prove one. Corollary 9 says only that AdamW and Muon have the same exponent of TT in the worst case over smooth nonconvex problems. On a smaller class, their behavior can differ sharply, even under heavy-tailed noise.

Example (Proposition F.2). Let W,K∈Rn×nW,K\in\mathbb R^{n\times n} with n=8sn=8s, Kij=(1−1/s)∣i−j∣K_{ij}=(1-1/s)^{|i-j|} (so K−1K^{-1} is tridiagonal), a=Δ/(2L)a=\sqrt{\Delta/(2L)}, and

F(W)=\frac{L}{4s}\left\\|K^{-1/2}(W-aK)\right\\|_{\rm F}^2 .

This FF is convex and LL-smooth, with F(0)−inf⁡F=ΔF(0)-\inf F=\Delta and condition number κ∈[7s2/32,4s2]\kappa\in[7s^2/32, 4s^2]. The oracle is ∇F(W)+n−1/2zI\nabla F(W)+n^{-1/2}zI, where zz is centered with E∣z∣p≤σp\mathbb E|z|^p\le\sigma^p. It satisfies Assumptions 1–3 with B=1B=1 and has infinite variance for p<2p<2. Start from W0=0W_0=0 and let σ≤cLΔs1−3/p(log⁡s)−1/p\sigma\le c\sqrt{L\Delta} s^{1-3/p}(\log s)^{-1/p}. Write θ=1+β2\theta=\frac{1+\beta}2 and C=21−βC=\frac2{1-\beta}.

  • Muon (exact polar factor, momentum β\beta, ηt=s2Δ/Lθt\eta_t=s\sqrt{2\Delta/L} \theta^t). For every TT, EF(WT)Δ ≤ 16C2s3θ2T+cp,βTs3−p(σLΔ)p.\frac{\mathbb E F(W_T)}{\Delta}\ \le\ 16C^2s^3 \theta^{2T} + c_{p,\beta} T s^{3-p}\left(\frac{\sigma}{\sqrt{L\Delta}}\right)^{p}. The first term decays geometrically and the second is at most 1/2001/200 in the noise regime above, so EF(WT)≤Δ/100\mathbb E F(W_T)\le\Delta/100 after T=⌈log⁡(3200C2s3)/(2log⁡(1/θ))⌉=O(log⁡κ)T=\lceil\log(3200C^2s^3)/(2\log(1/\theta))\rceil=O(\log\kappa) iterations.
  • Adam (any stepsizes, β1,β2\beta_1,\beta_2, stabilizer, bias correction, and weight decay, even history-dependent). Almost surely, F(WT)Δ ≥ 3(1−e−2)128 > 150for all 1≤T≤s,\frac{F(W_T)}{\Delta}\ \ge\ \frac{3(1-e^{-2})}{128}\ >\ \frac1{50}\qquad\text{for all }1\le T\le s, and s≥κ/2s\ge\sqrt\kappa/2, so Adam needs more than κ/2\sqrt\kappa/2 iterations to reach F≤Δ/100F\le\Delta/100. This holds even at σ=0\sigma=0.

Therefore, at least in theory, we have O(log⁡κ)O(\log\kappa) for Muon versus Ω(κ)\Omega(\sqrt\kappa) for Adam.

Consider iterations needed to reach F≤Δ/100F\le\Delta/100 (Muon values come from the formula for TT above, for ss large enough):

ssκ\kappaMuon (β=0.5\beta=0.5)Muon (β=0.9\beta=0.9)Adam
10310^32.2×1052.2\times10^5 to 4×1064\times10^655340>103>10^3
10410^42.2×1072.2\times10^7 to 4×1084\times10^867407>104>10^4
10510^52.2×1092.2\times10^9 to 4×10104\times10^{10}79474>105>10^5
10610^62.2×10112.2\times10^{11} to 4×10124\times10^{12}91542>106>10^6

See Official Comment by Authors (Part 2/2) for more.

AuthorsOpenReview ↗

Official Comment by Authors (Part 2/2)

Muon's count grows like log⁡κ\log\kappa and Adam's like κ\sqrt\kappa. The reason is geometric. In the eigenbasis of K−1K^{-1}, Muon reduces to scalar sign recursions that do not see the curvature, and the heavy-tailed noise enters only through max⁡k≤T∣zk∣\max_{k\le T}|z_k| and a truncation argument that uses only the ppth moment. Coordinatewise Adam works in the standard basis and moves information by one off-diagonal per step through the tridiagonal K−1K^{-1}. Details are in Appendix F.8.2.

Relation to prior work. Muon is already known to beat GD, SGD, or SignGD on simple models such as matrix factorization, linear in-context learning, and associative memory. See Table 4 for a summary of below.

  • Ma et al. (2026): Muon needs a number of iterations independent of κ\kappa, while SignGD needs at least (κ−1)/4(\kappa-1)/4 on some instances.
  • Wang et al. (2026c): Muon learns rare classes evenly, while SignGD does not for some embeddings.
  • Wang et al. (2026a): Muon's loss decays exponentially, against 1/t1/t for GD.
  • Wang et al. (2026b) and Kim et al. (2026): a stepwise loss advantage over GD, and a capacity gain over SGD.

However, these works have two major gaps.

  1. They compare Muon with GD, SGD, or SignGD, not directly with Adam.
  2. They use exact, population, or large-batch gradients (one adds label noise), so none allows more practical heavy-tailed noise.

Our example (Proposition F.2) addresses both. We have included the relevant discussions at the end of Section 5, while all technical details and comprehensive discussions are postponed to Appendix F.8.


Question 2 (is β1\beta_1 tuned?). No. β1\beta_1 is coupled to β2\beta_2 through the memory ratio (1−β1)/(1−β2)∈[1,C](1-\beta_1)/(1-\beta_2)\in[1,C], where C≥1C\ge1 is any constant chosen by the user (Eq. (2)). So like 1−β21-\beta_2, the admissible 1−β11-\beta_1 scales as T−p/(3p−2)T^{-p/(3p-2)}. β1\beta_1 is implicitly influenced by β2\beta_2.


Question 3 (relaxing β22≤β1≤β2\beta_2^2\le\beta_1\le\beta_2). Thanks for the suggestion! We have relaxed this dependence. Theorems 1 and 3 now hold under

1−β2 ≤ 1−β1 ≤ C(1−β2)for any constant C≥1,1-\beta_2\ \le\ 1-\beta_1\ \le\ C(1-\beta_2)\qquad\text{for any constant } C\ge1, which basically captures all the pairs in practice through the constant CC.

  • Relation to the original condition. The window β22≤β1≤β2\beta_2^2\le\beta_1\le\beta_2 is equivalent to 1−β2≤1−β1≤(1+β2)(1−β2)1-\beta_2\le1-\beta_1\le(1+\beta_2)(1-\beta_2), and (1+β2)(1−β2)<2(1−β2)(1+\beta_2)(1-\beta_2)<2(1-\beta_2). So it lies strictly inside the new condition with C=2C=2, for which the burn-in in Eq. (3) is the original one. Li et al. (2025a, Theorem 1) require the same window for AdamW, so our condition is also more permissive than theirs.
  • Cost. The rate is unchanged. A larger CC only enlarges the constants, at most linearly in CC (Eqs. (86) and (136)), and the burn-in in Eq. (3). We checked every use of the original window in Appendices C and D, and each one only needs the ratio bound.
  • Common settings. The ratio condition covers widely used pairs: (0.9,0.95)(0.9,0.95) with C=2C=2, (0.9,0.98)(0.9,0.98) with C=5C=5, and (0.9,0.999)(0.9,0.999) with C=100C=100. None of them satisfies β22≤β1\beta_2^2\le\beta_1.

On the intuition. What keeps an outlier from staying in the second moment for O(T)O(T) steps is the scale 1−β2≍T−p/(3p−2)1-\beta_2\asymp T^{-p/(3p-2)}, which gives a memory length o(T)o(T) (Section 3.3). The ratio condition keeps the two EMAs on comparable time scales. Since β1≤β2\beta_1\le\beta_2 (we believe such a requirement is natural because we are unaware of any public implementation that actually chooses β1\beta_1>β2\beta_2), the first moment forgets at least as fast as the second, so an outlier in mtm_t is always normalized by its own square in vtv_t (Lemmas C.2 and C.4). The upper bound 1−β1≤C(1−β2)1-\beta_1\le C(1-\beta_2) ensures that mtm_t still averages the noise over a window comparable to the memory of vtv_t (Lemmas C.5 and C.6).


References

Huan Li, Yiming Dong, and Zhouchen Lin. On the O(d/K1/4)O(\sqrt d/K^{1/4}) convergence rate of AdamW measured by ℓ1\ell_1 norm. In NeurIPS, pp. 132360–132387, 2025a.

Jianhao Ma, Yu Huang, Yuejie Chi, and Yuxin Chen. Preconditioning benefits of spectral orthogonalization in Muon. arXiv:2601.13474, 2026.

Kaifei Wang, Binghui Li, Han Zhong, Pinyan Lu, and Liwei Wang. Muon in associative memory learning: Training dynamics and scaling laws. In ICML, pp. 127884–127936, 2026a.

Shuche Wang, Fengzhuo Zhang, Jiaxiang Li, Dirk Bergemann, and Zhuoran Yang. Why Muon outperforms Adam: A curvature perspective. arXiv:2606.04662, 2026b.

Shuche Wang, Fengzhuo Zhang, Jiaxiang Li, Cunxiao Du, Chao Du, Tianyu Pang, Zhuoran Yang, Mingyi Hong, and Vincent Y. F. Tan. Muon outperforms Adam in tail-end associative memory learning. In ICLR, pp. 37382–37419, 2026c.

Reviewer_MoPhOpenReview ↗

Reply

Thank you for explaining!

I will keep my score and recommend acceptance, I think this paper is a useful contribution to the field. I have increased my scores for Presentation and Informativeness.

Thank you very much for your positive feedback! Your constructive suggestions have undoubtedly helped improve our paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Rebuttal Phase

We thank the AC and all reviewers for their time and constructive feedback during the review process. Reviewer rJVb states that our results "address two open problems regarding Adam's convergence" and strongly recommends acceptance. Reviewer MoPh considers the paper "a useful contribution to the field" and raised the Presentation and Informativeness scores. Reviewer 1vjm confirms that their concerns "have been addressed" and keeps the positive score.

The rebuttal adds several new theoretical results, all marked in blue in the revised manuscript.

Reviewer MoPh (can Muon beat Adam on smaller problem classes?)

  • Exponential separation between Muon and Adam (Proposition F.2). On a convex smooth problem with heavy-tailed noise, Muon needs only O(log⁡κ)O(\log\kappa) iterations. Adam with any hyperparameters, even history-dependent ones, needs Ω(κ)\Omega(\sqrt\kappa). To our knowledge, this is the first direct separation between Muon and Adam that allows heavy-tailed noise.
  • Practical momentum pairs. Theorems 1 and 3 now hold for any memory ratio (1−β1)/(1−β2)∈[1,C](1-\beta_1)/(1-\beta_2)\in[1,C] with the same rate. This covers common pairs such as (0.9,0.95)(0.9,0.95) and (0.9,0.999)(0.9,0.999).
  • Synthetic experiments (Appendix J) match the predicted rate exponent for every tested pp and confirm that the theoretical learning rate is near-optimal.

Reviewer 1vjm (dependence of the tuning on Δ\Delta, σ\sigma, pp)

  • Optimal rate without knowing Δ\Delta or σ\sigma (Theorem 10). A tuning that uses neither Δ\Delta nor σ\sigma still attains the optimal rate T−(p−1)/(3p−2)T^{-(p-1)/(3p-2)}, without logarithmic loss.
  • Tuning without pp, Δ\Delta, or σ\sigma, with a sharp rate (Propositions C.1–C.2). Without any knowledge of pp, Adam converges at O(T−(5p−6)/(8p))O(T^{-(5p-6)/(8p)}) for all p∈(6/5,2]p\in(6/5,2], recovering the optimal T−1/4T^{-1/4} at p=2p=2. A matching lower bound proves that this rate is sharp for this tuning up to a logarithmic factor. This precisely quantifies the cost of not knowing the tail index pp.

Reviewer rJVb (does SGD with momentum attain the same rate?)

  • Matching lower bound for SGDM (Theorem 15). We prove that the known SGDM rate T−(p−1)/(2p)T^{-(p-1)/(2p)} is tight for any fixed momentum. This settles the open question in Liu (2026c) of whether the gap to the optimal rate comes from a loose analysis or is inherent to SGDM. Consequently, for p<2p<2, vanilla SGDM is provably slower than AdamW and Muon, which attain the optimal T−(p−1)/(3p−2)T^{-(p-1)/(3p-2)} (Corollary 16).

These results substantially strengthen the submission. We thank the reviewers again for the suggestions that led to them.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.