acceptodds
Desk rejected at ICLR 2027

High-Confidence Stationarity of Momentum Muon: A Heavy-Tailed Separation from Adam

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

18 views

Abstract

As an emerging optimization method, Muon has been empirically shown to outperform Adam/AdamW on modern machine learning tasks, yet the mechanism underlying this advantage remains unclear. We identify a key mechanism behind Muon's high-probability advantage: its instantaneous singular-value compression provides the scale regularization sought by Adam's second-moment normalization while directly controlling unpreconditioned stationarity. By avoiding the confidence loss incurred when converting Adam's preconditioned adaptive energy into unpreconditioned stationarity, Muon achieves sharper confidence dependence under heavy-tailed noise. Specifically, under conditional -moment noise for any , we prove a finite-time high-probability theorem for exact canonical pre-polar momentum Muon, with fixed within each run. Choosing momentum and stepsize for the given horizon at fixed batch size yields the average-gradient rate , where . Even when stochastic gradients have infinite variance, the dependence on the confidence parameter remains only logarithmic. For the five-step Newton–Schulz (NS5) variant, we obtain the same rate up to an additive error floor under an explicit approximation-error condition. In contrast, for Adam with fixed , and initial moments, we construct a uniformly -moment-bounded two-dimensional family and prove a minimax stationarity lower bound with probability greater than .

Primary area:
optimization
Keywords:
Muon, Adam

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 5 reviews, above 27% of the others.
Reviewer_QkQ4OpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies high-probability convergence of momentum Muon under conditional pp-moment noise, 1<p≤21<p\le2. For exact-polar Muon with horizon-tuned parameters and fixed batch size, Theorem 1 establishes an average nuclear-gradient rate of O(T−a(1+log⁡(1/δ)))O(T^{-a}(1+\log(1/\delta))), where a=(p−1)/(3p−2)a=(p-1)/(3p-2). Theorem 2 extends this guarantee to NS5 under a pathwise inexact-LMO assumption, up to an additive approximation-error floor. For Adam with fixed β2\beta_2, Theorem 3 constructs a uniformly normalized class of 1×21\times2 instances with bounded conditional pp-th noise moments, on which average gradient stationarity has a polynomial dependence on δ\delta, uniformly over β1\beta_1 and positive constant learning rates. The paper compares the resulting worst-case confidence bounds and presents heavy-tailed noise experiments on Iris and a matched Qwen3-0.6B training comparison.

Critical strengths
  • S1. High-probability convergence without clipping. The main technical contribution is the control of heavy-tailed momentum errors. By capping the alignment deficit and tracking how past shocks decay, the authors obtain logarithmic dependence on 1/δ1/\delta without clipping or increasing the batch size. The block-supermartingale argument is interesting independently of the Adam comparison.

  • S2. Adam lower bound covering long-memory momentum. Theorem 3 covers all β1∈[0,1)\beta_1\in[0,1), including values close to one, with uniform constants across parameter-dependent instances. The rare-shock construction exploits the forgetting of second-moment information while signed first-moment information persists. This is a technically interesting extension of classical Adam counterexamples.

Critical weaknesses
  • W1. The scope and novelty of the separation need clarification. Theorem 3 assumes fixed β2\beta_2, whereas Section 3.1 also discusses β2=1−1/T\beta_2=1-1/T. The lower-bound mechanism does not directly cover this horizon-dependent regime. Moreover, Equation (C.4) already establishes a constant floor for a broad range of β1\beta_1, and the proof of Lemma C.9 appears to imply a stronger piecewise lower bound than the stated common-exponent result. The choice to emphasize the weaker formulation is therefore unclear. Finally, polar normalization on the 1×21\times2 witnesses reduces to Euclidean normalization, so the comparison does not isolate a specifically matrix-geometric advantage of Muon.

  • W2. The NS5 guarantee relies on an unverified approximation condition. Assumption 4 requires sufficient alignment whenever ∣∣Nt∣∣∗>τ||N_t||_*>\tau, but finite-step NS5 alignment depends on the input singular-value distribution and normalization. The paper does not establish nonvacuous values of K<2K<2 and τ\tau for its implementation. As a result, Theorem 2 remains conditional, and its approximation floor has no quantified practical interpretation. The layerwise update scaling used in the Qwen experiment also needs to be reconciled with the theorem.

  • W3. The experiments do not directly validate the confidence separation. The radial Iris experiment uses β=0\beta=0, so positive scalar shocks cancel exactly. The six-learning-rate Adam sweep strengthens this scale-robustness comparison but does not test the proposed momentum mechanism. The directional-noise experiment omits Adam. The Qwen comparison uses one run per optimizer with gradient clipping and does not report upper-tail stationarity. The finite-pool GPD fits characterize the observed tail range but do not establish infinite variance.

Questions for authors
  • Q1 (W1). Do the cases in Lemma C.9, together with Section C.4, yield a lower bound uniform over all γ>0\gamma>0 of cc when δ≤T−2(p+ϑ)\delta\le T^{-2(p+\vartheta)} and cmin⁡1/log⁡(eT),T−(p−1)/(2p)δ−1/(2p)c\min\\{1/\log(eT),T^{-(p-1)/(2p)}\delta^{-1/(2p)}\\} otherwise, for sufficiently small fixed ϑ>0\vartheta>0 and sufficiently small δ\delta? If so, please state this stronger result and explain the role of the common-exponent envelope. Can the separation cover β2=1−1/T\beta_2=1-1/T with constants uniform in TT?

  • Q2 (W2). What spectral conditions guarantee the required NS5 alignment, and how do KK and τ\tau depend on the input normalization and εNS\varepsilon_{\mathrm{NS}}? Can the authors justify nonvacuous values for their implementation and explain how Assumption 4 relates to existing NS approximation-error analyses?

  • Q3 (W3). Can the authors compare upper-tail stationarity for Adam and nonzero-momentum Muon under the directional noise oracle? Comparing fixed β2\beta_2 with β2=1−1/T\beta_2=1-1/T on the rare-shock construction would also test the proposed mechanism directly.

  • Q4. What is the main technical novelty of Theorem 1 relative to Cutkosky and Mehta [1], Hübler et al. [2,4], and Choudhury et al. [3]? For Theorem 3, please clarify the distinction from Heilman and Mohanty [5], who establish nonvanishing online regret for Adam and a projected scalar Muon variant. In particular, how does their regret-based construction differ from the present stochastic-stationarity lower bound?

Required Corrections

  • Incomplete NS5 specification (p. 3, Lines 129–141; p. 6, Lines 287–290; p. 16, Lines 859–863). Specify the exact five-step Newton–Schulz polynomial, input normalization, and numerical value of εNS\varepsilon_{\mathrm{NS}} used in the experiments. Clarify whether the implemented update satisfies Assumption 4 for any justified K<2K<2 and τ\tau. The matrix-dependent update scaling is already reported in Appendix A.3.1.

References

  • [1] Cutkosky, A., and Mehta, H. (2021). High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails. NeurIPS 2021.
  • [2] Hübler, F., Fatkhullin, I., and He, N. (2025). From Gradient Clipping to Normalization for Heavy Tailed SGD. AISTATS 2025
  • [3] Choudhury, S., Cheng, X., Takáč, M., Na, S., and Kolar, M. (2026). Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition. arXiv:2605.06884.
  • [4] Hübler, F., Pethick, T., and Sra, S. (2026). Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success. arXiv:2606.14560.
  • [5] Heilman, S., and Mohanty, S. (2026). On the Convergence of Adam, Revisited. arXiv:2607.03519.
6 comments

We thank the reviewer for the very detailed review, including the careful reading of the proofs in Appendix C, and for recognizing the high-probability convergence without clipping (the block-supermartingale argument) and the Adam lower bound covering long-memory momentum.

W1 / Q1: scope of the separation, the stronger lower bound, and the 1×21\times 2 instances

The stronger piecewise lower bound. The reviewer's reading is correct. The case analysis of Lemma C.9 together with Section C.4 indeed gives a piecewise lower bound uniform over all γ>0\gamma > 0: for every sufficiently small fixed ϑ>0\vartheta > 0 and sufficiently small δ\delta, with probability larger than δ\delta,

  • if δ≤T−2(p+ϑ)\delta \le T^{-2(p+\vartheta)}, the average gradient norm is at least cc;
  • otherwise it is at least cmin⁡{1/log⁡(eT),T−(p−1)/(2p)δ−1/(2p)}c\min\lbrace 1/\log(eT), T^{-(p-1)/(2p)}\delta^{-1/(2p)}\rbrace.

The cases come from:

  • for δ≤T−2(p+ϑ)\delta \le T^{-2(p+\vartheta)}, Lemma C.1 (the tail construction) gives a constant lower bound;
  • otherwise, intermediate memory gives c/log⁡(eT)c/\log(eT) through Lemma C.2 (the bias floor);
  • long memory gives cmin⁡{1,T−(p−1)/(2p)δ−1/(2p)}c\min\lbrace 1, T^{-(p-1)/(2p)}\delta^{-1/(2p)}\rbrace through Lemma C.8;
  • all remaining cases (including large γ\gamma in Section C.4) give constant lower bounds.

Role of the common-exponent formulation. We used the form cmin⁡{1,T−aδ−q}c\min\lbrace 1, T^{-a}\delta^{-q}\rbrace to write all cases with the same time exponent a=(p−1)/(3p−2)a = (p-1)/(3p-2) as Muon's upper bound, which reduces the comparison to the single ratio δ−q/(1+log⁡(1/δ))\delta^{-q}/(1+\log(1/\delta)). The price is that merging the c/log⁡(eT)c/\log(eT) branch into this form requires log⁡(eT)≤LζTζ\log(eT) \le L_\zeta T^\zeta with ζ=a−2(p+ϑ)q>0\zeta = a - 2(p+\vartheta)q > 0, which forces q<a/(2p)q < a/(2p). The piecewise form is stronger: at p=2p = 2 the confidence exponent is 1/41/4 rather than 1/321/32, and for p<2p < 2 we have (p−1)/(2p)<a(p-1)/(2p) < a, so even for fixed δ\delta Adam's lower bound decays more slowly in TT than Muon's upper bound. We will state the piecewise bound as the main form of Theorem 3 in the revision and keep the unified form for the direct comparison.

β2=1−1/T\beta_2 = 1-1/T. With ϵ=0\epsilon = 0, yes: the new Theorem 4 (Section 3.3, proof in Appendix D) covers β2=1−1/T\beta_2 = 1-1/T, and in fact any β2\beta_2 that depends on TT and δ\delta (together with β1\beta_1, γ\gamma and v0v_0), with constants cc and κ\kappa that depend only on pp and are uniform in TT; its conclusion is that no tuning attains Muon's guarantee CT−apolylog(1/δ)C T^{-a}\mathrm{polylog}(1/\delta) at high confidence. For ϵ>0\epsilon > 0, the constant of Theorem 3 depends on β2\beta_2, and we do not claim uniformity as β2→1\beta_2 \to 1.

(continued in the next comment)

(continued)

Polar normalization reduces to Euclidean normalization on the 1×21\times 2 instances. Yes, and this is exactly why we say that the confidence separation comes from normalization in time: the proof of Theorem 1 uses only two properties of the polar map, bounded updates and the dual descent certificate, so the same argument applies to momentum normalized SGD. The gain from matrix geometry appears elsewhere. The revision introduces the spectral smoothness constant LopL_{\mathrm{op}} (∥∇f(X)−∇f(Y)∥∗≤Lop∥X−Y∥op\lVert \nabla f(X)-\nabla f(Y)\rVert_{\ast} \le L_{\mathrm{op}}\lVert X-Y\rVert_{\mathrm{op}}, Lop≤rLL_{\mathrm{op}} \le rL) and replaces LrLr by LopL_{\mathrm{op}} in Theorem 1 (Section 3.2, proof in Appendix B.2.6). In nuclear-norm stationarity at the same β\beta and BB satisfying Muon's noise condition, with η\eta tuned for each method, every term of Muon's guarantee except the common noise term is smaller than for Frobenius normalization by the factor rL/Lop\sqrt{rL/L_{\mathrm{op}}}, between 11 and r\sqrt{r} for the smallest LL. On the 1×21\times 2 instances r=1r = 1 and this gain disappears, leaving only the confidence separation. See also our responses to Reviewers 4mz1 and ZbGo.

W2 / Q2 and required correction: NS5

Implementation details. The NS5 used in the experiments (Appendix A.3):

  • runs in bf16, and first transposes the matrix if it has more rows than columns;
  • normalizes X←N/(∥N∥F+εNS)X \leftarrow N/(\lVert N\rVert_F + \varepsilon_{\mathrm{NS}}) with εNS=10−7\varepsilon_{\mathrm{NS}} = 10^{-7};
  • then performs five steps X←aX+(bXX⊤+c(XX⊤)2)XX \leftarrow aX + (b XX^\top + c (XX^\top)^2) X with (a,b,c)=(3.4445,−4.775,2.0315)(a,b,c) = (3.4445, -4.775, 2.0315).

We will add this information at lines 129 to 141, 287 to 290, and 859 to 863.

Values of KK and τ\tau. NS5 applies the same scalar map to every singular value: it maps x=σi/(∥N∥F+εNS)∈(0,1]x = \sigma_i/(\lVert N\rVert_F + \varepsilon_{\mathrm{NS}}) \in (0,1] to φ∘5(x)\varphi^{\circ 5}(x), the fivefold iterate of φ(x)=ax+bx3+cx5\varphi(x) = ax + bx^3 + cx^5. In exact arithmetic, φ∘5(x)∈[0.682,1.203]\varphi^{\circ 5}(x) \in [0.682, 1.203] for x∈[3×10−3,1]x \in [3\times 10^{-3}, 1], and the output is smaller for smaller xx. This gives a sufficient spectral condition:

  • if every nonzero singular value of NtN_t satisfies σi≥3×10−3(∥Nt∥F+εNS)\sigma_i \ge 3\times 10^{-3}(\lVert N_t\rVert_F + \varepsilon_{\mathrm{NS}}), then ∥Pt∥op≤1.203\lVert P_t\rVert_{\mathrm{op}} \le 1.203 and ⟨Nt,Pt⟩≥0.682∥Nt∥∗\langle N_t, P_t\rangle \ge 0.682\lVert N_t\rVert_{\ast}, so Assumption 4 holds with K=2−0.682≈1.32K = 2 - 0.682 \approx 1.32 and τ=0\tau = 0: the factor 1/(2−K)1/(2-K) in Theorem 2 is about 1.471.47, and there is no additional error floor;
  • more generally, if the singular values below this threshold carry at most a fraction ρ<1\rho < 1 of the nuclear norm, Assumption 4 holds with K=2−0.682(1−ρ)K = 2 - 0.682(1-\rho).

These constants are for exact arithmetic; bf16 rounding perturbs them slightly. The condition can also fail, for example for matrices whose nuclear norm is concentrated on very small singular values, so for general inputs Theorem 2 remains conditional. We did not measure these quantities in the Qwen training; in the revision we will report the values of ∥Pt∥op\lVert P_t\rVert_{\mathrm{op}} and ⟨Nt,Pt⟩/∥Nt∥∗\langle N_t, P_t\rangle/\lVert N_t\rVert_{\ast} during training. The pathwise form of Assumption 4 is adapted from Qian et al. (2026); the scalar analysis above connects it directly to how the NS iteration acts on singular values.

(continued in the next comment)

(continued)

Layerwise scaling in the Qwen experiment. In the Qwen training, the update of each m×nm\times n matrix is multiplied by 0.2max⁡(m,n)0.2\sqrt{\max(m,n)}, with decoupled weight decay and gradient clipping; non-matrix parameters use AdamW. The layerwise scaling amounts to a deterministic step-size constant per matrix, but multiple matrix blocks, weight decay and clipping are outside the setting of Theorem 2. The Qwen experiment is therefore a comparison in real training, not an instance of Theorem 2. We will state this in the paper.

W3 / Q3: experiments

The reviewer's summary of the roles of the experiments is accurate:

  • the radial Iris experiment uses β=0\beta = 0, so positive scalar shocks cancel exactly; the six-learning-rate Adam sweep tests scale robustness, not the momentum mechanism;
  • the directional-noise experiment does not include Adam;
  • the Qwen comparison uses one run per optimizer with gradient clipping and does not report upper-tail stationarity;
  • the GPD fits characterize the tails only within the observed range and do not establish infinite variance; we will revise the corresponding statements.

We will add the two experiments suggested by the reviewer:

  1. under the directional-noise oracle, a comparison of the upper-tail stationarity (quantiles for each δ\delta) of Adam and nonzero-momentum Muon;
  2. on the rare-shock construction, a comparison of Adam with fixed β2\beta_2 and with β2=1−1/T\beta_2 = 1-1/T.

Q4: Differences from prior work

Theorem 1.

  • Cutkosky and Mehta (2021): high-probability bounds for normalized SGD with clipping and momentum; our bound needs no clipping.
  • Hübler et al. (2025): high-probability bounds for normalized SGD with increasing batch sizes, pointing out momentum as the difficulty; we handle momentum with a fixed batch size.
  • Hübler et al. (2026) and Choudhury et al. (2026): expectation bounds for Muon under heavy-tailed noise. We use the same parameter schedule and strengthen the conclusion to a high-probability bound with log⁡(1/δ)\log(1/\delta) dependence.
  • Technical novelty: we control the error on blocks of the momentum length through conditional pp-th moments, and combine the blocks into a single confidence event through a log-shock supermartingale, which avoids per-step high-probability control. The noise may also grow with the gradient (σ1>0\sigma_1 > 0).

Theorem 3 versus Heilman and Mohanty (2026). The two works answer different questions:

  • they study regret in an online-learning framework, and show that Adam and a projected scalar Muon variant have non-vanishing regret;
  • we study stochastic nonconvex optimization: a smooth objective and a stochastic oracle with bounded conditional pp-th moment are fixed before sampling, and the lower bound states that the average gradient norm exceeds a threshold with probability larger than δ\delta, uniformly over β1\beta_1 and constant learning rates;
  • in our setting, the Muon side is a positive high-probability guarantee rather than a failure example.

We thank the reviewer again.

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

The paper states that one of the reasons why Muon has an empirical advantage over Adam is due to its behavior at high confidence when subjected to heavy-tailed gradient noise. By setting each singular value to one in its polar map, Muon limits the size of the update in terms of operator norm while at the same time retaining the descent certificate. The authors assert that this enables Muon to achieve the scale regularization which Adam obtains through second-moment normalization, without using the random, history-dependent denominator that Adam has. Since converting the preconditioned convergence guarantees of Adam back into unpreconditioned stationarity involves a polynomial loss of confidence, Muon does not have to incur that cost.

The key contributions are the Muon upper bound (Theorems 1–2) and the Adam lower bound (Theorem 3); the validation studies comprise the Iris softmax regression, Iris with directional noise, training of the Qwen3-0.6B model from scratch, the gradient-tail diagnostics, and formal verification using Lean.

Critical strengths

Strength 1: A clean high-probability upper bound for momentum Muon under infinite-variance noise. Theorem 1 holds for the exact canonical recursion with fixed batch size, under conditional pp-moment noise for any p∈(1,2]p \in (1,2]. The noise may also grow with the gradient (σ1>0\sigma_1 > 0), which goes beyond the pp-BCM model used in prior normalized-SGD work. The confidence dependence is only log⁡(1/δ)\log(1/\delta).

Strength 2: An Adam lower bound that is uniform over all first-moment parameters and all learning rates. Theorem 3 does not show failure at one bad hyperparameter setting. It holds for every β1∈[0,1)\beta_1 \in [0,1) and every γ>0\gamma > 0, including any horizon-dependent rule β1(T)\beta_1(T).

Critical weaknesses

Weakness 1: The claim ``separation from Adam'' rests on a comparison whose setup favors Muon. The lower bound holds for every first-moment parameter β1\beta_1 and every learning rate γ\gamma, but it fixes Adam's second-moment parameter β2∈(0,1)\beta_2 \in (0,1) independently of the horizon TT. Muon, by contrast, gets a momentum parameter β=1−T−p/(3p−2)\beta = 1 - T^{-p/(3p-2)} tuned to TT. That asymmetry matters because β2\beta_2 controls exactly the mechanism the lower bound exploits: how quickly the second moment forgets a rare impulse, which takes k(M)=O(log⁡M)k(M) = O(\log M) steps, while the first moment keeps the impulse's sign for about 1/(1−β1)1/(1-\beta_1) steps.

Two further points shrink the articles claim. First, the hard instance is chosen after the tuning tuple (T,δ,β1,γ)(T, \delta, \beta_1, \gamma) is fixed, so this is a worst-case-over-instances statement, not a single problem on which tuned Adam provably loses. Second, the polynomial confidence exponent satisfies q<(p−1)/(2p(3p−2))q < (p-1)/(2p(3p-2)); for example q=1/32q = 1/32 at p=2p = 2. At any practical δ\delta, δ−1/32\delta^{-1/32} is barely distinguishable from a logarithmic factor. This is the most consequential issue because the title, abstract and conclusion all frame the contribution as an explanation of why Muon beats Adam.

Weakness 2: The experiments do not test the theory, and some are uninformative by construction. This matters because the paper presents its experiments as support for the proposed mechanism, yet none isolate it. A convincing validation would vary δ\delta and the tail index under genuinely noisy momentum Muon, compare against Adam with horizon-tuned β2\beta_2, and include normalized SGD and sign-based baselines. Without that, the empirical section neither confirms the separation nor rules out simpler explanations.

Questions for authors

The AI-use statement says the proofs were formally verified in Lean. Which results are covered: Theorems 1--3 in full, or only selected lemmas? Is the formalization included in the supplementary material?

Can you report confidence profiles (quantiles across δ\delta) under genuinely noisy momentum Muon, with β>0\beta > 0 and non-radial noise, against Adam with horizon-tuned β2\beta_2 and without gradient clipping?

What does Theorem 1 add beyond Choudhury et al. (2026) and H"ubler et al. (2026), whose parameter schedule you adopt? Do those works already give high-probability bounds with log⁡(1/δ)\log(1/\delta) dependence for momentum Muon under pp-moment noise, and if so, under which assumptions (for instance σ1=0\sigma_1 = 0, batch size growing with TT, or a different stationarity measure)?

4 comments

We thank the reviewer for the detailed comments, and for recognizing the high-probability upper bound of Theorem 1 under infinite-variance noise and the lower bound of Theorem 3 that holds uniformly over all first-moment parameters and learning rates.

Weakness 1: the comparison setup, worst-case instances, and the exponent qq

β2\beta_2 is fixed while Muon's β\beta is tuned to TT. We agree that this limits the scope of Theorem 3: it lets Adam's β1\beta_1 and constant learning rate γ\gamma depend on TT (and even on δ\delta), and fixes only β2\beta_2, ϵ\epsilon and the initial moments. To remove this asymmetry we added Theorem 4 (see the general response): with ϵ=0\epsilon = 0, Adam's β1\beta_1, β2\beta_2, γ\gamma and v0v_0 may all be tuned to the horizon (and even to δ\delta), just like Muon's parameters, and still no tuning attains Muon's guarantee CT−apolylog(1/δ)C T^{-a}\mathrm{polylog}(1/\delta) at high confidence; at p=2p = 2, Adam's exponent is at most 1/51/5, versus 1/41/4 for Muon.

The instance is chosen after the tuning. Yes, Theorem 3 is a worst-case (minimax) lower bound: for each (T,δ,β1,γ)(T, \delta, \beta_1, \gamma) there is an instance in a fixed problem class on which Adam fails. This is the standard order of quantifiers for lower bounds. The key point is that the class is common, with the same smoothness constant, initial gap and noise-moment bound, while Muon's upper bound holds on every instance of the class with constants independent of the instance. We thus compare the worst-case guarantees of the two methods on the same class. We do not claim that there is a single fixed problem on which Adam fails for every tuning.

The exponent qq is small. This relates to Q1 of Reviewer QkQ4. The restriction q<(p−1)/(2p(3p−2))q < (p-1)/(2p(3p-2)) comes from our unified formulation: to give Adam's lower bound and Muon's upper bound the same time exponent, we wrote all cases in one form. It is not a limitation of the proof. The case analysis of Lemma C.9 and Appendix C.4 actually gives a stronger piecewise lower bound: for every sufficiently small fixed ϑ>0\vartheta > 0, with probability larger than δ\delta,

  • if δ≤T−2(p+ϑ)\delta \le T^{-2(p+\vartheta)}, the average gradient norm is at least a constant cc;
  • otherwise it is at least cmin⁡{1/log⁡(eT),T−(p−1)/(2p)δ−1/(2p)}c\min\lbrace 1/\log(eT), T^{-(p-1)/(2p)}\delta^{-1/(2p)}\rbrace.

At p=2p = 2 the confidence exponent is 1/41/4 rather than 1/321/32: for δ≥(log⁡(eT))4/T\delta \ge (\log(eT))^4/T, the ratio of Adam's lower bound to Muon's upper bound is of order δ−1/4/(1+log⁡(1/δ))\delta^{-1/4}/(1+\log(1/\delta)). For p<2p < 2, (p−1)/(2p)(p-1)/(2p) is smaller than Muon's time exponent (p−1)/(3p−2)(p-1)/(3p-2), so even for fixed δ\delta Adam's lower bound decays more slowly in TT than Muon's upper bound. We will state this piecewise bound as the main form of Theorem 3 and keep the unified form for the direct comparison.

Positioning of the paper. The paper isolates one specific mechanism behind Muon's advantage: high-confidence behavior under heavy-tailed noise; the advantage from matrix geometry is a complementary aspect (see our response to Reviewer 4mz1). We will state this positioning more precisely in the title, abstract and conclusion, so that the paper is not read as a complete explanation of why Muon outperforms Adam.

(continued in the next comment)

(continued)

Weakness 2 and Question 2: experiments

The existing experiments test different parts of the theory, but none of them isolates the confidence separation itself. Their roles:

  • the radial-noise Iris experiment (β=0\beta = 0) tests robustness to the noise scale;
  • the directional-noise experiment, with Muon at β>0\beta > 0 and normalized SGD with the same momentum numerator, tests the tradeoff of momentum between the median and the upper tail, but does not include Adam;
  • the Qwen experiment uses gradient clipping and is only a comparison in real training.

We will add the experiment suggested by the reviewer: momentum Muon with β>0\beta > 0 under non-radial (directional) heavy-tailed noise, varying δ\delta and the tail index, reporting quantiles of the average gradient norm for each δ\delta. Baselines will include Adam with fixed β2\beta_2 and with horizon-tuned β2\beta_2 (β2=1−1/T\beta_2 = 1-1/T), momentum normalized SGD, and sign-based methods, all without gradient clipping.

Question 1: Lean formal verification

Our submission does not claim any Lean formal verification. The AI-use statement on page 10 of the submission says that AI assisted with the mathematical arguments and with writing and checking the proofs; it does not mention Lean, and neither the submission nor the supplementary material contains a Lean formalization. The complete proofs of Theorems 1 to 3 are in Appendices B and C.

Question 3: What does Theorem 1 add beyond Choudhury et al. (2026) and Hübler et al. (2026)?

Both works give guarantees in expectation:

  • Choudhury et al. (2026) consider Muon with Nesterov momentum and inexact polar factors, and bound min⁡kE∥∇f(Xk)∥F\min_k \mathbb{E}\lVert \nabla f(X_k)\rVert_F. Their noise model also allows σ1>0\sigma_1 > 0, with a fixed batch size (above a threshold when σ1>0\sigma_1 > 0). We adopt their parameter schedule.
  • Hübler et al. (2026) give an expected sample complexity for Muon in nuclear-norm stationarity, and list high-probability guarantees as future work in their conclusion.

To our knowledge, neither gives a high-probability bound with log⁡(1/δ)\log(1/\delta) dependence. Under the same schedule, with a fixed batch size and no clipping, Theorem 1 proves a high-probability bound on the average nuclear norm of the gradient along the whole trajectory, with confidence dependence log⁡(1/δ)\log(1/\delta). Because the tail decays like log⁡(1/δ)\log(1/\delta), integrating this bound also gives an expectation bound of the same order; conversely, an expectation bound yields only 1/δ1/\delta dependence through Markov's inequality.

Technically, the difficulty is the momentum error under heavy-tailed noise: controlling it step by step with high probability costs a polynomial in 1/δ1/\delta. Instead, we control the error on blocks of the momentum length through conditional expectations, and combine the blocks through a log-shock supermartingale, so that the whole proof uses a single confidence event.

We thank the reviewer again. If our responses address the main concerns, we would be grateful if the reviewer would consider updating the score.

Dear Reviewer ojwh,

Thank you for your detailed review. We would like to follow up on our response of November 16 and the revised PDF (changes marked in blue). In brief:

  • Asymmetric comparison (W1): You pointed out that Adam's β₂ is fixed while Muon's momentum is tuned to T. To address this, the revision adds Theorem 4 (Section 3.3, Appendix D; see also our general response). Theorem 4 lets Adam (with ε = 0) tune β₁, β₂, the step size, and the initial second moment to T (and even to δ), and still no tuning covered by the theorem, including β₂ = 1 − 1/T, attains Muon's guarantee at high confidence. At p = 2, Adam's rate exponent is at most 1/5, versus 1/4 for Muon.

  • Small confidence exponent q (W1): This restriction comes from our unified formulation, which writes all cases with the same time exponent; it is not a limitation of the proof. Lemma C.9 and Appendix C.4 in fact yield a stronger piecewise lower bound, with confidence exponent 1/4 at p = 2 (rather than 1/32). We will state it as the main form of Theorem 3.

  • Choudhury et al. and Hübler et al. (2026): To our knowledge, both give guarantees in expectation. Under the same parameter schedule, with a fixed batch size and no clipping, Theorem 1 gives a high-probability bound with only log(1/δ) dependence.

  • Lean: To clarify, our submission does not claim any Lean formal verification, and the supplementary material contains none; the complete proofs are in Appendices B and C.

  • Experiments (W2): Following your suggestion, we will add experiments with momentum Muon (β > 0) under directional heavy-tailed noise, varying δ and the tail index. The baselines will include Adam with fixed β₂ and with β₂ = 1 − 1/T, momentum normalized SGD, and sign-based methods, all without gradient clipping.

The author–reviewer discussion closes on November 18 (AoE). We would greatly appreciate it if you could let us know before then whether our responses address your concerns. If any concerns remain, we would be glad to clarify further as soon as possible; if they have been resolved, we would be grateful if you would consider updating your score accordingly. Thank you again for your time!

Best regards, The Authors

Thank you to the authors for their rebuttal, which clarifies the scope of the results. I am satisfied with the clarifications, which address my concerns and strengthen the manuscript. I appreciate the authors' efforts and will raise my rating from 2 to 3.

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

This paper investigates the high-probability convergence behavior of Muon under heavy-tailed stochastic gradient noise. It establishes a logarithmic confidence-dependent stationarity bound for momentum Muon and a uniform polynomial confidence-dependent lower bound for Adam, providing a worst-case theoretical separation between their normalization mechanisms.

Critical strengths
  1. The paper develops a high-probability analysis for momentum Muon using logarithmic concentration, avoiding separate high-probability control of stochastic errors at individual iterations.
  2. The uniform lower bound for Adam covers arbitrary first-moment parameters and positive constant learning rates, offering theoretical insights into the different behaviors of normalization mechanisms under heavy-tailed noise.
Critical weaknesses
  1. The theoretical separation assumes a fixed second-moment parameter and does not cover commonly used Adam variants with bias correction, learning-rate scheduling, or decoupled weight decay (e.g., AdamW). Therefore, the results do not establish a general theoretical advantage of Muon over Adam-type optimizers.
  2. Although the analysis exploits properties of polar normalization, it remains unclear whether the logarithmic confidence dependence relies on its specific matrix geometry or follows from more general properties of normalized gradient methods.
  3. The experiments do not directly verify the predicted polynomial-versus-logarithmic confidence separation. In particular, the controlled radial-noise experiment largely exploits the scale invariance of polar normalization, while the language-model results provide limited evidence for the proposed theoretical mechanism.
Questions for authors
  1. Is the logarithmic high-probability guarantee specific to the polar mapping, or can the analysis be extended to other normalization operators, such as normalized SGD with momentum?
  2. Does the Adam lower bound remain valid when the second-moment parameter is allowed to depend on the training horizon, or when standard bias correction and learning-rate schedules are introduced?
  3. Could the authors provide experiments directly evaluating the confidence-dependent stationarity bounds, particularly on the hard instances constructed for the Adam lower bound?
4 comments

We thank the reviewer for the careful reading, and for recognizing the analysis via logarithmic concentration that avoids per-step high-probability control, as well as the Adam lower bound that holds uniformly over all first-moment parameters and constant learning rates.

W1 / Q2: horizon-dependent β2\beta_2, bias correction, learning-rate schedules, and AdamW

Theorem 3 targets the most common usage in practice: β2\beta_2, ϵ\epsilon and the initial moments are fixed (e.g., β2=0.95\beta_2 = 0.95 or 0.9990.999), and the lower bound holds uniformly over all first-moment parameters β1\beta_1 and constant learning rates γ\gamma, including horizon-dependent β1(T)\beta_1(T), and even β1\beta_1 and γ\gamma chosen with knowledge of δ\delta. So tuning β1\beta_1 and the learning rate alone cannot remove the polynomial dependence on δ\delta. The new Theorem 4 extends the result to the case where β2\beta_2 is also tuned to the horizon (ϵ=0\epsilon = 0). Item by item:

  • Horizon-dependent β2\beta_2. We added Theorem 4; please see the general response. For Adam with ϵ=0\epsilon = 0, β1\beta_1, β2\beta_2, γ\gamma and v0v_0 may all depend on TT and δ\delta, and still no tuning attains Muon's guarantee CT−apolylog(1/δ)C T^{-a}\mathrm{polylog}(1/\delta) at high confidence; at p=2p = 2, Adam's exponent is at most 1/51/5, versus 1/41/4 for Muon.
  • Bias correction. Bias correction divides the two moments by 1−β1t1-\beta_1^t and 1−β2t1-\beta_2^t. With fixed β2\beta_2, the second-moment correction is close to one after O(1/(1−β2))O(1/(1-\beta_2)) steps; but when β1→1\beta_1 \to 1 with TT, the first-moment correction stays large for a long time, and our construction does not transfer directly.
  • Learning-rate schedules and AdamW. Theorem 3 covers every constant learning rate, but not schedules such as warmup or decay, nor AdamW with positive weight decay.

We will state this scope clearly in the paper: Theorem 3 covers fixed β2\beta_2 and ϵ>0\epsilon > 0, and the new Theorem 4 covers ϵ=0\epsilon = 0 with β2\beta_2 and the other parameters tuned to the horizon.

W2 / Q1: Is the logarithmic confidence dependence specific to the polar map?

The logarithmic confidence dependence comes from normalizing the current momentum deterministically; it does not require the polar map itself. The proof of Theorem 1 uses only two properties of the polar map:

  1. bounded updates: ∥polar(N)∥op≤1\lVert \mathrm{polar}(N)\rVert_{\mathrm{op}} \le 1, hence ∥polar(N)∥F2≤r\lVert \mathrm{polar}(N)\rVert_F^2 \le r;
  2. the dual descent certificate: ⟨N,polar(N)⟩=∥N∥∗\langle N, \mathrm{polar}(N)\rangle = \lVert N\rVert_{\ast}, hence ⟨g,polar(N)⟩≥∥g∥∗−2∥N−g∥∗\langle g, \mathrm{polar}(N)\rangle \ge \lVert g\rVert_{\ast} - 2\lVert N-g\rVert_{\ast}.

All other steps (conditional pp-th moment estimates on blocks of the momentum length, geometric contraction, and the log-shock supermartingale) do not depend on matrix structure. Hence any normalization operator with these two properties yields the same result in the corresponding norm. In particular, momentum normalized SGD (Pt=Nt/∥Nt∥FP_t = N_t/\lVert N_t\rVert_F), with the nuclear norm replaced by the Frobenius norm and rr by 11, attains the same rate O(T−(p−1)/(3p−2)(1+log⁡(1/δ)))O(T^{-(p-1)/(3p-2)}(1+\log(1/\delta))). On the 1×21\times 2 hard instances, Muon's update is exactly the normalized SGD update, so the comparison in Section 3.3 holds for it as well.

(continued in the next comment)

(continued)

The polar map matters through geometry: the update is bounded in the spectral norm, and stationarity is measured in the nuclear norm. The revision introduces the spectral smoothness constant LopL_{\mathrm{op}} (∥∇f(X)−∇f(Y)∥∗≤Lop∥X−Y∥op\lVert \nabla f(X)-\nabla f(Y)\rVert_{\ast} \le L_{\mathrm{op}}\lVert X-Y\rVert_{\mathrm{op}}, always Lop≤rLL_{\mathrm{op}} \le rL), with which the curvature term Lrη/(1−β)Lr\eta/(1-\beta) of Theorem 1 becomes Lopη/(1−β)L_{\mathrm{op}}\eta/(1-\beta) (Section 3.2, proof in Appendix B.2.6). Comparing the two guarantees in nuclear-norm stationarity at the same β\beta and BB satisfying Muon's noise condition, with η\eta tuned for each method, every term of Muon's bound except the common noise term is smaller than for momentum normalized SGD by the factor rL/Lop\sqrt{rL/L_{\mathrm{op}}}, which lies between 11 and r\sqrt{r} for the smallest LL; for example, it is (r+1)/2\sqrt{(r+1)/2} for f(X)=12tr(XQX⊤)f(X)=\frac{1}{2}\mathrm{tr}(XQX^\top) with Q=qq⊤+I/rQ=qq^\top+I/r and ∥q∥2=1\lVert q\rVert_2=1, where the curvature is concentrated along qq. This is the gain in the guarantee that comes from matrix geometry; since it compares upper bounds, how much of it is realized depends on how spread the gradient spectra are (see our response to Reviewer 4mz1). Both this extension and the statement that Theorem 1 holds for momentum normalized SGD are in Section 3.2 of the revision.

W3 / Q3: Do the experiments directly verify the confidence separation?

The existing experiments test different parts of the theory: robustness of normalization to the noise scale, the tradeoff of momentum between the median and the upper tail, and behavior in real training. A simulation that directly tests the polynomial-versus-logarithmic separation will be added in the revision (see the end of this section). The role of each experiment:

  • Radial-noise Iris experiment. As the reviewer notes, this experiment exploits the scale invariance of polar normalization: with β=0\beta = 0, positive scalar shocks cancel exactly. Its purpose is to isolate normalization in a controlled setting. The theory attributes Muon's confidence advantage to normalizing the current direction, whereas Adam's update is affected by the noise magnitude. Appendix A reports confidence profiles from 5,000 trajectories per tail index for δ\delta from 0.20.2 to 0.010.01, together with Adam at six learning rates. This experiment tests scale robustness, not the momentum mechanism.
  • Directional-noise experiment. This experiment tests the momentum mechanism. Under additive directional noise, we compare Muon with different β\beta against normalized SGD with the same momentum numerator. The median and the upper tail favor different momentum lengths, consistent with the tradeoff between noise averaging and gradient tracking in the upper bound.
  • Language-model experiment. It only shows Muon's behavior in real training and the heavy tails of native gradient noise; it is not direct evidence for the mechanism.

Direct verification on the hard instances has two difficulties:

  1. The event that triggers the lower bound has probability of order δ\delta, so reliably estimating the 1−δ1-\delta quantile requires far more than 1/δ1/\delta trajectories per configuration, and the instance changes with (T,δ,β1,γ)(T, \delta, \beta_1, \gamma).
  2. The theorems compare orders as δ→0\delta \to 0, while finite simulations cover only a limited range of δ\delta and cannot confirm asymptotic exponents.

Nevertheless, the mechanism behind the lower bound can be simulated directly. We will add this simulation in the revision: on the rare-shock instance, we compare Adam with fixed β2\beta_2 (including horizon-dependent β1\beta_1) against momentum Muon and normalized SGD, and report quantiles of the average gradient norm for several values of δ\delta.

We thank the reviewer again. We hope these responses clarify the scope of the results; if the main concerns are resolved, we would be grateful if the reviewer would consider updating the score.

Dear Reviewer ZbGo,

Thank you for your careful review. We would like to follow up on our response of November 16 and the revised PDF (changes marked in blue). In brief:

  • Horizon-dependent β₂ and Adam variants (W1/Q2): The revision adds Theorem 4 (Section 3.3, Appendix D; see also our general response). For Adam with ε = 0, even when β₁, β₂, the step size, and the initial second moment are all tuned to T (and even to δ), no tuning covered by the theorem, including β₂ = 1 − 1/T, attains Muon's guarantee at high confidence. Bias correction, learning-rate schedules, and AdamW are not directly covered by the current results, and we will state this scope clearly in the paper.

  • Whether the log(1/δ) dependence is specific to the polar map (W2/Q1): It is not. It comes from deterministically normalizing the current momentum, and momentum normalized SGD attains the same rate. The role of the polar map lies in matrix geometry, reflected in the improvement given by the newly introduced spectral smoothness constant L_op (Section 3.2).

  • Experiments (W3/Q3): We explained which part of the theory each existing experiment tests. We will also add a direct simulation on the rare-shock hard instance, comparing Adam with fixed β₂, momentum Muon, and normalized SGD, and reporting quantiles of the average gradient norm for several values of δ.

The author–reviewer discussion closes on November 18 (AoE). We would greatly appreciate it if you could let us know before then whether our responses address your concerns. If any concerns remain, we would be glad to clarify further as soon as possible; if they have been resolved, we would be grateful if you would consider updating your score accordingly. Thank you again for your time!

Best regards, The Authors

Thank you for the detailed response. The distinction between logarithmic confidence dependence and matrix geometry largely resolves W2. Theorem 4 partially addresses W1, but still requires ϵ=0\epsilon=0 and does not directly cover bias correction, learning-rate schedules, or AdamW. For W3, the additional experiments remain promised rather than provided, leaving the proposed mechanism without direct empirical validation. I appreciate the progress, but the main concerns are not fully resolved, so I maintain my original rating.

Reviewer_4mz1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the high-probability convergence of Muon under heavy-tailed gradient noise. The authors establish stationarity guarantees with logarithmic confidence dependence for exact-polar Muon. They also provide an Adam lower bound with polynomial confidence dependence.

Critical strengths
  1. Studying Muon under heavy-tailed noise is a meaningful direction.
  2. The high-probability convergence guarantees, particularly the logarithmic confidence dependence, are theoretically interesting.
  3. The Adam lower bound covers all first-moment parameters and positive constant learning rates, strengthening the theoretical comparison.
Critical weaknesses
  1. Limited connection between the theoretical advantage and Muon's matrix orthogonalization. My main concern is that the claimed advantage is not clearly connected to Muon's matrix orthogonalization. The Adam hard instances use 1 × 2 matrices, where polar normalization reduces to ordinary vector normalization. Although the Muon upper bound uses nuclear–operator norm duality, the confidence separation does not establish an advantage specific to matrix orthogonalization.

  2. The limitations of Adam have been studied extensively. More closely related, Chezhegov et al. (2025) established poor high-probability convergence for Adam under heavy-tailed noise. The authors should clarify the novelty over their results regarding the Adam lower bound.

  3. The Adam lower bound assumes a fixed second-moment parameter, whereas Muon's momentum parameter can depend on the optimization horizon. It is unclear whether the separation persists when Adam is also allowed to use a horizon-dependent.

  4. Presentation could be improved. All experimental figures are placed in the appendix. I suggest moving representative results and/or training curves to the main text. The conclusion mainly repeats the theoretical results and could better discuss the insights and limitations.

[1] Chezhegov et al., Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed. Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:10269-10333, 2025.

Questions for authors

What is the role of matrix orthogonalization? Since polar normalization reduces to vector normalization on the 1 × 2 hard instances, could the same confidence separation be established for normalized SGD with momentum? What advantage is specific to Muon?

4 comments

We thank the reviewer for the comments, and for recognizing the research direction, the high-probability guarantee with logarithmic confidence dependence, and that the Adam lower bound holds uniformly over all first-moment parameters and positive constant learning rates.

W1 and Question: the role of matrix orthogonalization, and what is specific to Muon

Our results have two layers: the confidence dependence comes from normalization in time, and matrix orthogonalization improves the smoothness constant of the guarantee on top of it.

Layer 1: the confidence separation. The proof of Theorem 1 uses only two properties of the polar map: the update is bounded in the spectral norm (∥polar(N)∥op≤1\lVert \mathrm{polar}(N)\rVert_{\mathrm{op}} \le 1), and the dual descent certificate holds (⟨N,polar(N)⟩=∥N∥∗\langle N, \mathrm{polar}(N)\rangle = \lVert N\rVert_{\ast}). So the answer to the reviewer's question is yes: momentum normalized SGD also has log⁡(1/δ)\log(1/\delta) dependence, and the confidence separation of Section 3.3 holds for it as well; on the 1×21\times 2 instances the two updates coincide. This shows that the separation comes from normalizing the current momentum deterministically, as opposed to Adam's random, history-dependent denominator.

Layer 2: a geometric gain in the guarantee, visible in the smoothness constant. Muon's update is bounded in the spectral norm, and stationarity is measured in its dual, the nuclear norm. Theorem 1 as submitted uses the Frobenius smoothness constant LL, so its curvature term is Lrη/(1−β)Lr\eta/(1-\beta), where the factor rr comes from comparing the spectral and nuclear norms with the Frobenius norm. The revision introduces the spectral smoothness constant LopL_{\mathrm{op}} (defined after Assumption 2):

∥∇f(X)−∇f(Y)∥∗≤Lop∥X−Y∥op,Lop≤rL.\lVert \nabla f(X)-\nabla f(Y)\rVert_{\ast} \le L_{\mathrm{op}}\lVert X-Y\rVert_{\mathrm{op}}, \qquad L_{\mathrm{op}} \le rL.

Smoothness enters the proof of Theorem 1 in only four places: the descent inequality, the gradient radius, the one-step gradient drift, and the blockwise gradient drift. With LopL_{\mathrm{op}}, the form of Theorem 1 is unchanged: LrLr becomes LopL_{\mathrm{op}}, and 2LrΔ1\sqrt{2Lr\Delta_1} becomes 2LopΔ1\sqrt{2L_{\mathrm{op}}\Delta_1}. Theorems 1 and 2 and Corollaries 1 and 2 in the revision are now stated with LopL_{\mathrm{op}} (Section 3.2; proofs in Appendices B.2.6 and B.2.7). This gives a direct comparison:

  • By the same argument, momentum normalized SGD gets Frobenius stationarity with constant LL; converting to the nuclear norm costs a factor r\sqrt{r}.
  • Comparing the two guarantees in nuclear-norm stationarity at the same β\beta and BB satisfying Muon's noise condition (with η\eta tuned for each method and the smallest smoothness constants), every term of Muon's bound except the noise term is smaller by the factor rL/Lop∈[1,r]\sqrt{rL/L_{\mathrm{op}}} \in [1,\sqrt{r}]; the noise terms coincide. These are exactly the terms that grow with log⁡(1/δ)\log(1/\delta), so the gain is largest at high confidence. When σ1>0\sigma_1 > 0, Muon's noise condition is stricter by the factor r\sqrt{r}, and in the Frobenius norm the order of the bounds reverses: Muon's gain is in nuclear-norm stationarity, the stronger measure and the one dual to its spectral-norm step.
  • Intuitively, the factor is large when the curvature is concentrated in a few directions. For example, f(X)=12tr(XQX⊤)f(X)=\frac{1}{2}\mathrm{tr}(XQX^\top) with Q=qq⊤+I/rQ=qq^\top+I/r and ∥q∥2=1\lVert q\rVert_2=1 has L=1+1/rL=1+1/r and Lop=2L_{\mathrm{op}}=2, so the factor is (r+1)/2\sqrt{(r+1)/2}; more generally, whenever the Hessian has the Kronecker form I⊗QI \otimes Q (as in linear least squares, with QQ the second-moment matrix of the inputs), Lop/L≤∥Q∥∗/∥Q∥opL_{\mathrm{op}}/L \le \lVert Q\rVert_{\ast}/\lVert Q\rVert_{\mathrm{op}}, which is small when a few eigenvalues dominate QQ. Since the factor compares upper bounds, how much of it shows in practice depends on how spread the gradient spectra are: the conversion ∥⋅∥∗≤r∥⋅∥F\lVert \cdot\rVert_{\ast} \le \sqrt{r}\lVert \cdot\rVert_F is tight only for flat spectra, and for a rank-one momentum the polar and Frobenius directions coincide. This is in line with Shen et al. (2025, arXiv:2505.23737), who use the same spectral smoothness constant and relate Muon's advantage to the low-rank and approximately blockwise diagonal structure of the Hessian.

On the 1×21\times 2 instances r=1r = 1, so the geometric gain disappears and only the confidence separation remains. On general matrices Muon has both: a proven confidence separation from Adam, and a gain in the guarantee over Frobenius normalization by the factor rL/Lop\sqrt{rL/L_{\mathrm{op}}}. All of this is in Sections 2.2 and 3.2 of the revision, with proofs in Appendix B.2.

(continued in the next comment)

(continued)

W2: Difference from Chezhegov et al. (2025)

We thank the reviewer for pointing out this work and will discuss it in the related work. The differences are:

  1. Range of β2\beta_2 and uniformity. Their negative result concerns only the single value β2=1−1/K\beta_2 = 1-1/K (KK the number of iterations), for Adam-Norm and AdaGrad-Norm; their examples are one-dimensional and therefore also apply to coordinatewise versions. Our Theorem 3 holds for every fixed β2\beta_2 and ϵ>0\epsilon > 0, uniformly over all β1\beta_1 and constant learning rates. The new Theorem 4 covers ϵ=0\epsilon = 0 with β1\beta_1, β2\beta_2, γ\gamma and v0v_0 all tuned to the horizon and the confidence level.
  2. Noise. Their negative result is under bounded variance (with a single noise spike at the first step); for infinite variance they only state a conjecture. Our lower bounds hold under pp-th moment noise, p∈(1,2]p \in (1,2], allowing infinite variance.
  3. Criterion and comparison. They use the last-iterate function value on a one-dimensional convex Huber function; we use nonconvex stationarity, the average gradient norm. This is the criterion of Muon's upper bound, so Adam's lower bound and Muon's upper bound can be compared directly on the same instances.
  4. Emphasis. They show that gradient clipping repairs Adam's confidence dependence; we show that clipping is not needed: normalizing the current momentum (as Muon does) gives log⁡(1/δ)\log(1/\delta) dependence by itself.

W3: β2\beta_2 is fixed while Muon's momentum is tuned to the horizon

We thank the reviewer for pointing out this asymmetry. The revision adds Theorem 4; please see the general response. In short: for Adam with ϵ=0\epsilon = 0, even with β1\beta_1, β2\beta_2, γ\gamma and v0v_0 all tuned to the horizon (and even to δ\delta), no tuning attains Muon's guarantee CT−apolylog(1/δ)C T^{-a}\mathrm{polylog}(1/\delta) at high confidence; at p=2p = 2, Adam's exponent is at most 1/51/5, versus 1/41/4 for Muon.

W4: Presentation and placement of the experiments

We agree. Within the 10-page limit, we will move a representative experimental figure (the confidence profiles of the Iris experiment) to the main text and shorten the proof sketch in Section 4 accordingly. The conclusion will discuss implications and limitations instead of restating the theorems:

  • Theorem 3 concerns fixed β2\beta_2 and ϵ>0\epsilon > 0, and Theorem 4 concerns ϵ=0\epsilon = 0;
  • both are worst-case lower bounds over instances;
  • the constants and the threshold on TT are not optimized.

We thank the reviewer again. If our responses address the main concerns, we would be grateful if the reviewer would consider updating the score.

Dear Reviewer 4mz1,

Thank you for your review. We would like to follow up on our response of November 16 and the revised PDF (changes marked in blue). In brief:

  • Role of matrix orthogonalization (W1 and your question): Yes, the same confidence separation can be established for momentum normalized SGD. It comes from deterministically normalizing the current momentum, so momentum normalized SGD also enjoys log(1/δ) dependence, and the separation in Section 3.3 holds for it as well. What is specific to Muon appears through the newly introduced spectral smoothness constant L_op: in nuclear-norm stationarity, every term of Muon's guarantee except the noise term is smaller than the corresponding term for momentum normalized SGD by a factor of √r·L/L_op (Sections 2.2 and 3.2, Appendix B.2).

  • Difference from Chezhegov et al. (2025) (W2): Their negative result concerns only β₂ = 1 − 1/K under bounded variance, and measures the last-iterate function value on a one-dimensional convex Huber function. Our lower bound holds for every fixed β₂ (with ε > 0), uniformly over all β₁ and constant step sizes; it allows infinite variance and measures nonconvex stationarity, so it can be compared directly with Muon's upper bound.

  • Horizon-dependent β₂ (W3): The revision adds Theorem 4 (Section 3.3, Appendix D; see also our general response). For Adam with ε = 0, even when β₁, β₂, the step size, and the initial second moment are all tuned to T (and even to δ), no tuning covered by the theorem, including β₂ = 1 − 1/T, attains Muon's guarantee at high confidence. At p = 2, Adam's rate exponent is at most 1/5, versus 1/4 for Muon.

  • Presentation (W4): We will move the confidence profiles of the Iris experiment to the main text and revise the conclusion to discuss implications and limitations.

The author–reviewer discussion closes on November 18 (AoE). We would greatly appreciate it if you could let us know before then whether our responses address your concerns. If any concerns remain, we would be glad to clarify further as soon as possible; if they have been resolved, we would be grateful if you would consider updating your score accordingly. Thank you again for your time!

Best regards, The Authors

Thank you for the detailed response and revisions, which address some of my concerns, while I am not fully convinced by the scope of the theoretical separation and the limited experimental validation. I thus would like to maintain my rating.

Reviewer_gNpUOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper derives and presents 3 theoretical results about high probability convergence of Muon and Adam under heavy tailed noise as measured by the gradient norms averaged over training trajectory

  • Upper bounds for exact muon that uses polar decomposition to orthogonalize the momentum buffer, and its approximate newton shultz counterpart.
  • Lower bound for Adam under the first momentum β1\beta_1 tuning.

The contextualization with respect to the related work and support by the experiments are done in a very limited way presented on the last page of the main paper.

Critical strengths

The lower bound for Adam is a good ingredient that makes the muon upper bounds more informative.

Critical weaknesses

The paper presentation is extremely poor. From the very first page, including even the abstract, the paper presents technical details related to their theoretical analysis. This presentation style continues for the first 8 pages: assumptions, definitions, theorem and corollary statements, proof sketch. No plots or discussion of motivation or contextualization of the results beyond the technical details around the three theorems. Only the last page contains related work and experiments, but both in a too limited form. I do not see how the paper at least attempts to explain why its results are needed, or relevant, or interesting, and not simply feels a vacant neighborhood the known results about convergence of muon and Adam under heavy tailed noise.

The overall feeling is well illustrated by the first page of the paper if one tries to genuinely understand what the authors wanted to communicate with it. Here is the full quotation

Muon has shown strong empirical performance in modern machine learning (Jordan et al., 2024; Liu et al., 2025). A theoretical comparison with Adam requires specifying both the optimization criterion and the noise model. Here we study high-probability stationarity: expectations can conceal rare, large errors, whereas a 1−δ1-\delta guarantee exposes performance at a small failure probability δ\delta.

 

This perspective is relevant under heavy-tailed noise. Heavy-tailed stochastic gradients or gradient noise have been observed in neural networks, attention models, reinforcement learning, and generative and discriminative tasks (Simsekli et al., 2019; Zhang et al., 2020; Garg et al., 2021; Battash et al., 2024); language tasks also exhibit heavy-tailed class imbalance (Kunstner et al., 2024), and multiplicative noise can produce heavy-tailed trajectories even from light-tailed data (Hodgkinson & Mahoney, 2021; Gurbuzbalaban et al., 2021).

 

For a rank-ss compact SVD M=UsΣsVs⊤M=U_s\Sigma_s V_s^\top, Muon’s exact normalization is

with polar⁡(0)=0\operatorname{polar}(0)=0. This replaces every nonzero singular value by one and gives

⟨M,polar⁡(M)⟩=∥M∥∗,∥polar⁡(M)∥op≤1.\langle M,\operatorname{polar}(M)\rangle=\lVert M\rVert_{\ast},\qquad \lVert\operatorname{polar}(M)\rVert_{\mathrm{op}}\leq 1.

The update is bounded while retaining a nuclear-norm descent certificate. For pre-polar momentum, conditional pp-moment estimates over momentum-length blocks, geometric contraction, and a log-shock supermartingale give logarithmic confidence dependence. This argument directly controls the unweighted gradient sum without removing a random historical denominator. For smooth lower-bounded objectives under conditional pp-moment noise, p∈(1,2]p\in(1,2], choosing the momentum and […]

Questions for authors
  • What was the motivation behind the derivation of the presented results?
  • How would you describe what the presented results add to the understanding of the behavior of Adam and muon already available in the literature?
3 comments

We thank the reviewer for the comments, and for recognizing that the Adam lower bound makes the Muon upper bound more informative. The main criticism concerns the presentation: the motivation and positioning are unclear, technical details appear too early, and related work and experiments are compressed into the last page. We agree. Below we first answer the two questions and then describe how we will revise the presentation.

Q1: What is the motivation for deriving these results?

Muon often outperforms Adam/AdamW in practice, but the reason is not well understood. Our starting point is two observations.

  • A training run is a single trajectory. What one experiences is the behavior of this one trajectory, not an average over many runs. Bounds in expectation can hide errors that are rare but large. A bound that holds with probability 1−δ1-\delta states directly what is guaranteed when the failure probability δ\delta is small.
  • Stochastic gradients are often heavy-tailed. Heavy-tailed gradient noise has been observed repeatedly in deep learning (Simsekli et al., 2019; Zhang et al., 2020), possibly with infinite variance. Under heavy tails, the dependence on δ\delta is exactly where methods differ: some pay only log⁡(1/δ)\log(1/\delta), others pay a polynomial in 1/δ1/\delta.

Adam's second-moment normalization is designed to control the scale of the update, which is the property needed under heavy-tailed noise. Muon controls the scale differently: it sets all singular values of the momentum matrix to one. Our question is therefore: under heavy-tailed noise, do these two ways of controlling the scale behave fundamentally differently at high confidence, and if so, where does the difference come from?

Q2: What do these results add to the literature?

We would like to explain that the paper answers questions that existing results leave open.

  1. High-probability guarantee for momentum Muon.
    • Existing analyses of Muon under heavy-tailed noise (Hübler et al., 2026; Choudhury et al., 2026) give guarantees in expectation.
    • High-probability results with log⁡(1/δ)\log(1/\delta) dependence were previously available for normalized-SGD-type methods, and they either rely on gradient clipping (Cutkosky & Mehta, 2021) or do not include momentum (Hübler et al., 2025).
    • Theorem 1 treats standard momentum Muon as used in practice, with a fixed batch size, no clipping, and only a conditional pp-th moment assumption (p∈(1,2]p \in (1,2], allowing infinite variance and noise that grows with the gradient). Under these conditions we prove a high-probability stationarity bound with only log⁡(1/δ)\log(1/\delta) dependence.

(continued in the next comment)

(continued)

  1. Lower bound for Adam. Theorem 3 shows that, under the same noise class, as long as β2\beta_2, ϵ\epsilon and the initial moments are fixed, for every choice of β1\beta_1 and constant learning rate there is a hard instance on which Adam's stationarity depends polynomially on 1/δ1/\delta. Thus log⁡(1/δ)\log(1/\delta) dependence is not automatic for adaptive methods. The new Theorem 4 further shows that without offset (ϵ=0\epsilon = 0), even if β1\beta_1, β2\beta_2, the learning rate and the initialization are all tuned to the horizon and the confidence level, no tuning attains Muon's guarantee at high confidence.
  2. What the two results say together. Together, the upper and lower bounds separate the two methods in their confidence dependence. In the setting of Theorem 3 the difference lies in the dependence on δ\delta, which bounds in expectation cannot capture. The analysis also identifies the source of the difference:
    • Adam's denominator is random and history-dependent; converting its guarantee into unpreconditioned stationarity costs confidence.
    • The lower-bound construction exploits exactly this: after a rare large shock, the second moment forgets it within O(log⁡M)O(\log M) steps, while the first moment keeps the sign of the shock for about 1/(1−β1)1/(1-\beta_1) steps.
    • Muon's polar map needs no separate random denominator. Every update is bounded (∥polar(M)∥op≤1\lVert \mathrm{polar}(M)\rVert_{\mathrm{op}} \le 1) and keeps the nuclear-norm descent certificate (⟨M,polar(M)⟩=∥M∥∗\langle M, \mathrm{polar}(M)\rangle = \lVert M\rVert_{\ast}), which directly controls unpreconditioned stationarity, so Muon does not pay this confidence cost.

The paper isolates one specific mechanism behind Muon's advantage: high-confidence behavior under heavy-tailed noise. The advantage from matrix geometry is a complementary aspect; our response to Reviewer 4mz1 explains how it enters the bound. For a horizon-dependent β2\beta_2, please see the general response; for a detailed comparison with Choudhury et al. and Hübler et al., please see our responses to Reviewers ojwh and QkQ4.

Presentation

We will revise the presentation as follows:

  1. The abstract and introduction will first explain the motivation and the question in words (the content of Q1 above), and then state the results; the polar notation and the proof outline will move from the first page to later sections.
  2. Related work will move earlier, with a table comparing existing results by noise assumption, algorithm, and type of guarantee (expectation or high probability).
  3. Representative experimental results will move to the main text, and the conclusion will discuss implications and limitations instead of restating the theorems.

We thank the reviewer again and are happy to clarify anything further.

Dear Reviewer gNpU,

Thank you for your review. We would like to follow up on our response of November 16. In brief:

  • Motivation (Q1): A training run is a single trajectory, and bounds in expectation can hide errors that are rare but large. Under heavy-tailed noise, methods differ precisely in how they depend on the failure probability δ: log(1/δ) versus a polynomial in 1/δ. Our question is whether Adam's second-moment normalization and Muon's singular-value normalization differ fundamentally at high confidence, and if so, where the difference comes from.

  • Contribution relative to prior work (Q2): To our knowledge, existing analyses of Muon under heavy-tailed noise give guarantees only in expectation. For momentum Muon as used in practice (fixed batch size, no gradient clipping, infinite variance allowed), we prove a high-probability guarantee with only log(1/δ) dependence. Together with the Adam lower bound (and the new Theorem 4 in the revision), the analysis identifies the source of the difference: Adam's random, history-dependent denominator.

  • Presentation: The abstract and introduction will first explain the motivation and the question, with technical details moved later; the related work will move earlier, with a comparison table; representative experiments will move to the main text; and the conclusion will discuss implications and limitations.

The author–reviewer discussion closes on November 18 (AoE). We would greatly appreciate it if you could let us know before then whether our responses address your concerns. If any concerns remain, we would be glad to clarify further as soon as possible; if they have been resolved, we would be grateful if you would consider updating your score accordingly. Thank you again for your time!

Best regards, The Authors

Comments on the paper

1 comment

General response: Adam with a horizon-dependent β2\beta_2

Several reviewers (4mz1, ZbGo, ojwh, QkQ4) point out that Theorem 3 fixes Adam's second-moment parameter β2\beta_2 (and the offset ϵ>0\epsilon > 0), whereas Muon's momentum parameter is tuned to the horizon TT, and ask whether the separation persists when β2\beta_2 may also depend on TT. We agree that this asymmetry needs an answer. The revision adds Theorem 4 (Section 3.3, proof in Appendix D); changes in the revised PDF are marked in blue.

Theorem 4 (offset-free Adam under horizon-dependent tuning). Let p∈(1,2]p \in (1,2], batch size B=1B = 1, and run Adam with ϵ=0\epsilon = 0. There exist c>0c > 0 and κ≥1\kappa \ge 1, depending only on pp, such that for every sufficiently large TT, every δ∈(0,T−κ]\delta \in (0, T^{-\kappa}], and every choice of β1∈[0,1)\beta_1 \in [0,1), β2∈(0,1)\beta_2 \in (0,1), γ>0\gamma > 0, ν∈(0,1]\nu \in (0,1] as arbitrary functions of (T,δ)(T,\delta) with

1−β1≥2(1−β2)orβ2≤β13orβ2≤1/2,1-\beta_1 \ge 2(1-\beta_2) \quad \text{or} \quad \beta_2 \le \beta_1^3 \quad \text{or} \quad \beta_2 \le 1/2,

there is a preselected instance in the same class as in Theorem 3 (1×21\times 2 row matrices, L=1L = 1, f⋆=0f_\star = 0, Δ1=1\Delta_1 = 1, (σ0,σ1)=(1,0)(\sigma_0,\sigma_1) = (1,0)) on which

P{1T∑t=1T∥∇f(Xt)∥F≥c⋅T−aTa/(3p−1)log⁡T}>δ,a=p−13p−2.\mathbb{P}\left\lbrace \frac{1}{T}\sum_{t=1}^{T}\lVert \nabla f(X_t)\rVert_F \ge c \cdot \frac{T^{-a} T^{a/(3p-1)}}{\log T} \right\rbrace > \delta, \qquad a = \frac{p-1}{3p-2}.

Comparison with Muon. On the same instances, Muon's guarantee (Corollary 1) at δ=T−κ\delta = T^{-\kappa} is at most CM(1+κlog⁡T)T−aC_{\mathrm{M}}(1+\kappa\log T) T^{-a}. Hence:

  • with ϵ=0\epsilon = 0, no tuning covered by Theorem 4, even one that depends on TT and δ\delta, attains a guarantee of Muon's form CT−apolylog(1/δ)C T^{-a}\mathrm{polylog}(1/\delta);
  • at high confidence, Adam is slower than Muon by the power Ta/(3p−1)T^{a/(3p-1)}; at p=2p = 2, Adam's exponent is at most 1/51/5, versus 1/41/4 for Muon.

Coverage. The condition covers β1=0\beta_1 = 0 (any β2\beta_2); any fixed β1\beta_1 with β2→1\beta_2 \to 1 (e.g., β2=1−1/T\beta_2 = 1-1/T, or Muon's own 1−T−p/(3p−2)1-T^{-p/(3p-2)}); and the default (β1,β2)=(0.9,0.999)(\beta_1,\beta_2) = (0.9, 0.999). It excludes only the band β13<β2<(1+β1)/2\beta_1^3 < \beta_2 < (1+\beta_1)/2, β2>1/2\beta_2 > 1/2, which contains the curve β12=β2\beta_1^2 = \beta_2 (with Hi=1/(1−βi)H_i = 1/(1-\beta_i), roughly H2/2<H1<3H2H_2/2 < H_1 < 3H_2). We need ν>0\nu > 0 because with ϵ=0\epsilon = 0 the denominator must be positive.

Mechanism. Letting β2→1\beta_2 \to 1 with TT does remove the mechanism of Theorem 3 (the second moment quickly forgets a shock), but it creates new costs that cannot all be avoided:

  1. Intermediate memory. When the true gradient is below σ0(1−β2)(p−1)/p\sigma_0(1-\beta_2)^{(p-1)/p}, skewed noise makes Adam with ϵ=0\epsilon = 0 move against the gradient in a sign-like way. As long as one period fits into the horizon, a periodic "washboard" objective amplifies this into an average gradient of order (1−β2)(3p−4)/(4p)(1-\beta_2)^{(3p-4)/(4p)}, up to logarithms.
  2. Very long memory. When 1−β21-\beta_2 or 1−β11-\beta_1 is below T−2p/(3p−1)T^{-2p/(3p-1)}, one large shock stalls the iterates for most of the horizon; for δ\delta polynomially small in TT, this cost cannot be neglected.
  3. Remaining cases. For β2≤β13\beta_2 \le \beta_1^3, the rare-shock-and-uphill-bank mechanism of Theorem 3 persists at ϵ=0\epsilon = 0; with very short second-moment memory, skewed noise creates an error floor that does not vanish; very small steps cannot travel.

Every admissible tuning falls into at least one of these cases. The threshold on TT and the constants are not optimized; the result is asymptotic.

Division of labor. Theorem 3 covers fixed β2\beta_2 and fixed ϵ>0\epsilon > 0 (the setting used in practice), uniformly over β1\beta_1 and γ\gamma. Theorem 4 covers ϵ=0\epsilon = 0 with all remaining parameters tuned arbitrarily to the horizon and the confidence level.

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

Related papers

Discussion (0)

Sign in to comment.