acceptodds
Under review as a conference paper at ICLR 2027

Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition

Abstract

Most first-order optimizers treat matrix-valued parameters as vectors, ignoring the intrinsic geometry of hidden-layer weights in neural networks. Muon addresses this mismatch by updating along the polar factor of a momentum matrix, but its theoretical understanding has lagged behind practice. In particular, practical implementations incorporate Nesterov momentum, compute the polar factor only approximately, and operate with stochastic gradients that may be heavy-tailed. We close this gap by developing a convergence theory for Muon with Nesterov momentum and inexact polar decomposition in non-convex matrix optimization under heavy-tailed noise. Our analysis builds on a unified framework for inexact polar decomposition that captures practical iterative approximations such as Newton-Schulz and quantifies how their errors propagate through the optimization dynamics. Under this framework, we establish an optimal iteration and sample complexity of for finding an -stationary point, where  denotes the heavy-tail index. For the inexact-polar setting with , we also provide guarantees that do not require prior knowledge of . We analyze a randomized low-rank polar decomposition that is substantially more efficient than full-space methods while remaining compatible with our theory. Numerical experiments further demonstrate the effectiveness of the proposed inexact and randomized variants.

Primary area:
optimization
Keywords:
optimization, stochastic, muon, machine learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_1PjVOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper analyzes convergence of the MUON optimizer. In particular it proves sample complexity / iteration rates required to achieve epsilon-stationarity (gradient is less then epsilon). This paper differentiates itself from other works by trying to extend previous analysis to more realistic settings, i.e. with muon with nesterov momentum and with inexact polar decomposition. They tackle the ladder by making an assumption on the error between the approximate polar decomposition and the true value and demonstrate that practically used approximation methods (polynomial iterations) can be covered by the assumption. They also do not strictly assume bounded variance but allow for heavy tailed noise. They also present a randomized projection version of the Muon optimizer that projects the matrix to a low dimensional subspace before performing the polynomial iterations in order to save compute. Their theorems cover this setting as well. Lastly some simulations are performed to demonstrate the effectiveness of both MUON and the randomized variation, in particular by comparing against other popular optimizers like Adam and SGD with various forms of momentum.

Critical strengths

This paper extends convergence guarantees to a more realistic setting that closely aligns with the MUON that is applied in practice. No existing work covers both nesterov momentum and approximate polar decomposition. This is a clear contribution. The main paper is also fairly easy to understand.

Critical weaknesses

The only real weakness I have to point out is with respect to the randomized projection version of the algorithm. The benefit of the projected version is scalability in terms of complexity in the size of the matrices. The experiments demonstrate that the cost in terms of accuracy is fairly small and that the savings in terms of GFLOPs (only for the update steps) is valuable. However, the latency is actually greater for this randomized version. There is no evidence of any practical use of the algorithm if its accuracy is worse and it is slower in practice (fixing some compute budget / memory). Perhaps if dramatically scaling weight matrices at some point the savings will kick in, but it does not seem so practical.

Questions for authors

Do you believe there is practicality of the randomized projection variation to muon in terms of cost efficiency / scaling up?

How similiar is the analysis to existing work? Given that the aspects emphasized here (heavy tailed noise, nesterov momentum and approximate polar decomposition) all exist in other works on their own and not together, it is not clear to me (someone unfamiliar with the existing work on muon convergence) how substantial the technical contribution is here.

some minor feedback:

Under main contributions there is the following quote: ‘To our knowledge, this is the first work that achieves optimal sample complexity for Muon with Nesterov momentum, even under bounded-variance assumption.’. The table shown says other work (yu et al [51]) has the same convergence rate and also considers nesterov momentum. Does this contradict the quote or is there something else I am missing?

σ\sigma is used in assuption 3.2 as existing values for the inequality but it is also used throughout for singular values. While it did not bother me I could see it perhaps being confusing particularly in the proofs section.

3 comments

Do you believe there is practicality of the randomized projection variation to muon in terms of cost efficiency / scaling up? The only real weakness I have to point out is with respect to the randomized projection version of the algorithm. The benefit of the projected version is scalability in terms of complexity in the size of the matrices. The experiments demonstrate that the cost in terms of accuracy is fairly small and that the savings in terms of GFLOPs (only for the update steps) is valuable. However, the latency is actually greater for this randomized version. There is no evidence of any practical use of the algorithm if its accuracy is worse and it is slower in practice (fixing some compute budget / memory). Perhaps if dramatically scaling weight matrices at some point the savings will kick in, but it does not seem so practical.

Thank you for the excellent suggestions. Your conjecture about scaling is what we find. We have a new timing experiment to support this, which we will add to the paper.

Training time. We timed one orthogonalization of a Gaussian random matrix for the two common matrix shapes of a transformer of width d: d x d (attention) and 4d x d (MLP). Note that d = 768 in our nanoGPT, and d = 4096 and 8192 are the widths of 7B and 70B models (e.g. Llama-2). Times are in ms on one H100 GPU, speed-up over Newton-Schulz in brackets:

width dlayer shapeNewton-Schulz, 7 stepsrandomized, rank 10% of drandomized, rank 26% of drandomized, rank 256
768 (our nanoGPT)attention, d x d0.550.98 (0.56x)1.09 (0.51x)1.41 (0.39x)
768 (our nanoGPT)MLP, 4d x d0.640.85 (0.76x)1.35 (0.48x)1.71 (0.38x)
2048attention, d x d0.711.23 (0.58x)2.65 (0.27x)1.50 (0.47x)
2048MLP, 4d x d1.812.02 (0.90x)4.79 (0.38x)2.39 (0.76x)
4096 (7B scale)attention, d x d5.292.70 (1.96x)7.82 (0.68x)1.92 (2.75x)
4096 (7B scale)MLP, 4d x d15.55.25 (2.95x)15.5 (1.00x)3.51 (4.41x)
8192 (70B scale)attention, d x d40.010.1 (3.97x)25.7 (1.56x)2.98 (13.4x)
8192 (70B scale)MLP, 4d x d12023.2 (5.15x)57.3 (2.09x)6.24 (19.2x)

At d = 768 and 2048, the randomized step is slower at each rank. This is the scenario of our benchmarks (the CIFAR-10 matrices are even smaller), which is why it does not improve training time. At the 26% rank ratio of our experiments, it becomes faster only at d = 8192, which is the scale of a 70B model. With a smaller rank (10% of d, or 256), it is already faster at d = 4096.

Setup. We also ran an experiment on the following matrix regression problem, to measure the end-to-end running time:

min⁡X∈Rn×nf(X)=12∥AXB−C∥F2,A∈Rp×n, B∈Rn×p, C=AX⋆B+cE.\min_{X \in \mathbb{R}^{n\times n}} f(X) = \tfrac12 \lVert AXB - C\rVert_F^2, \qquad A \in \mathbb{R}^{p\times n},\ B \in \mathbb{R}^{n\times p},\ C = AX^\star B + cE.

AA and BB are given data matrices. The ground truth X⋆X^\star and the noise EE have i.i.d. standard Gaussian entries.

The timings above are for a single orthogonalization. To check that the saving carries over to a complete optimization run, we ran Muon and Rand-Muon with Nesterov momentum for 20,000 iterations on the problem above with p=100p = 100, c=10−3c = 10^{-3} and the exact gradient ∇f(X)=A⊤(AXB−C)B⊤\nabla f(X) = A^\top (AXB - C) B^\top. As the table below shows, Rand-Muon is 10-13x faster at n = 8192. Both methods reach the same final gradient norm (about 6×10−86 \times 10^{-8} of the initial gradient), and they need about the same number of iterations to reach a given gradient norm. The table reports, for each run, the total wall-clock time, the final gradient norm and the number of iterations needed to reach a gradient norm of 10−210^{-2}, 10−310^{-3} and 10−510^{-5} (gradient norms are relative to the initial one):

nmethodtotal time (s)final gradient norm (10-8)iterations to reach 10-2iterations to reach 10-3iterations to reach 10-5
2048Muon186.31650270019850
2048Rand-Muon, rank 128256.41700240019850
2048Rand-Muon, rank 64256.01700240019850
4096Muon1215.41750270019850
4096Rand-Muon, rank 128355.61750250019850
4096Rand-Muon, rank 64266.21800250019850
8192Muon8606.01700270019850
8192Rand-Muon, rank 128825.91750245019850
8192Rand-Muon, rank 64676.11750245019850

Perplexity. The worse perplexity on nanoGPT (29.46 against 27.25) is the cost of rank 26% at d = 768. For this small-scale pretraining task, full Muon is the right choice when higher accuracy is the priority. Nevertheless, at larger scale, the proposed Rand-Muon can be much more efficient.

How similiar is the analysis to existing work? Given that the aspects emphasized here (heavy tailed noise, nesterov momentum and approximate polar decomposition) all exist in other works on their own and not together, it is not clear to me (someone unfamiliar with the existing work on muon convergence) how substantial the technical contribution is here.

Thanks for the question. We detail the challenges for our analysis below

  • Here, we want to highlight that one of the main contributions of our work is the Assumption 2.1 to capture inexact polar decomposition. This assumption is novel and does not exist in the literature. Therefore, the analysis of Muon under this proposed assumption requires new proof techniques even if there are works on Nesterov momentum and heavy tailed noise.

  • Moreover, the analysis of stochastic algorithms under bounded variance is much simpler given the existing huge literature. However, the analysis becomes much more complicated when the gradient noise is heavy-tailed with σ1>0\sigma_1 > 0 (Assumption 3.2) and there is also stochasticity coming from randomized inexact polar decomposition.

  • Finally, we proved that the algorithms used in practice for Newton Schulz satisfy our proposed assumption 2.1. We hope this clarifies the difficulties of our analysis compared to the existing literature.

Under main contributions there is the following quote: ‘To our knowledge, this is the first work that achieves optimal sample complexity for Muon with Nesterov momentum, even under bounded-variance assumption.’. The table shown says other work (yu et al [51]) has the same convergence rate and also considers nesterov momentum. Does this contradict the quote or is there something else I am missing?

No, the statement is correct and doesn’t contradict the table. Yu et al [51] does not consider the inexact polar decomposition whereas we do in Theorem 3.5. Their analysis assumes T(Mk)\mathcal{T}(M_k) is an orthogonal matrix which is not the case in practice when we use Newton Schulz to approximate the polar decomposition.

σ\sigma is used in assuption 3.2 as existing values for the inequality but it is also used throughout for singular values. While it did not bother me I could see it perhaps being confusing particularly in the proofs section.

Thanks for the pointer. We will definitely fix it in the updated version of the manuscript.

Thank you for the response, it is nice to see the crossover point at which savings kick in from the added experiment. I will maintain my positive score.

Reviewer_T6ouOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the nonconvex convergence of Muon under Nesterov momentum, inexact pole decomposition, and heavy-tailed stochastic gradient noise conditions. First, the authors establish a unified analytical framework for inexact polar decomposition through orientation alignment and operator norm constraints. Then, under the generalized heavy-tailed noise assumption, they prove the corresponding convergence guarantee, with iterative complexity consistent with the optimal order in existing nonconvex stochastic optimization theory. Furthermore, the paper proposes and analyzes a stochastic low-rank polar decomposition method, and evaluates its performance and computational cost through nanoGPT pre-training and CIFAR-10 classification experiments.

Critical strengths

This paper incorporates Nesterov momentum, inexact polar decomposition, and generalized heavy-tailed noise into a unified analytical framework, and clearly characterizes the impact of approximation errors on convergence guarantees. In particular, the handling of gradient-dependent noise and stochastic low-rank polar decomposition presents certain technical challenges, and the theoretical derivation is relatively complete.

Critical weaknesses
  1. Limited theoretical novelty, lacking substantial insights to deepen the understanding of Muon.

The main convergence conclusions of this paper are consistent with the complexity order of existing heavy-tailed stochastic nonconvex optimization theories. As shown in Table 1, previous studies have obtained results of the same order under Nesterov momentum and exact polar decomposition, inexact polar decomposition, and other momentum or noise conditions. This paper mainly combines these studied technical conditions without further revealing the optimization mechanism unique to Muon.

Of particular note is that Nesterov momentum is one of the core motivations of the paper, but the theory does not prove that it has a faster convergence speed than Polyak momentum, nor does it explain under what conditions Nesterov should be preferred. Existing Nesterov-like optimization methods (to my knowledge, such as Adan [1]) can achieve a complexity of (O(\varepsilon^{-3.5})) under stronger Hessian Lipschitz conditions. Although this result is not directly comparable to the assumptions of this paper, it further highlights the need for the authors to explain what new insights beyond existing complexity results the current theory provides.

  1. There remains a significant gap between Assumption 2.1 and practical Newton-Schulz implementations, limiting the practical significance of its theoretical guarantees.

Assumption 2.1 characterizes inexact polar decompositions through expected direction alignment and upper bounds on operator norms, but the extent to which these conditions constrain practical Muon implementations is unclear.

Specifically, Proposition 2.2 analyzes classical cubic and quintic Newton-Schulz polynomials, rather than the empirical quintic polynomials commonly used in practical Muon implementations. Furthermore, the unified alignment guarantee for stochastic low-rank polar decompositions satisfies (1-\bar{\gamma}=d_0^{-3/2}). This lower bound rapidly approaches zero as the matrix dimension increases, potentially leading to overly loose convergence constants in Theorem 3.5 and introducing stricter batch size requirements under gradient-dependent noise conditions.

On the other hand, existing research (e.g., [2]) has shown that, under the corresponding assumptions, a finite number of Newton–Schulz iterations can maintain the same asymptotic convergence order as the ideal Muon. Therefore, this paper needs to further explain what new conclusions its abstract analytical framework provides that can be used to guide practical Newton-Schulz iterative design, rather than simply re-establishing conditions sufficient to guarantee convergence.

  1. The experiments failed to adequately validate the core theoretical conclusions and lacked practical efficiency advantages.

Heavy-tailed noise is the main motivation for the paper, but the experiments do not examine convergence behavior under different heavy-tailed indices, nor do they validate theoretical predictions. Furthermore, Nesterov momentum do not show a stability advantage over Polyak momentum. While the stochastic low-rank method significantly reduced optimizer FLOPs, it do not improve end-to-end training time. For example, training time increased slightly on nanoGPT, validating a perplexity increase from 27.25 to 29.46. Similarly, there is a lack of practical speedup on CIFAR-10. Therefore, the existing experiments are insufficient to validate the core theory and do not adequately support the claimed computational efficiency advantages.

[1]Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models

[2]Convergence of Muon with Newton-Schulz

Questions for authors
  1. Regarding theoretical novelty: Compared to existing Nesterov-Muon and heavy-tailed stochastic optimization theories, what new optimization insights does Theorem 3.5 offer?

  2. Regarding Assumption 2.1: For the empirical fifth-order Newton-Schulz polynomial commonly used in practical Muon optimization, can Assumption 2.1 be verified and practically meaningful dimensionality-related constants obtained? Under typical large model matrix dimensions, how stringent is the batch size constraint of Theorem 3.5?

  3. Regarding experimental verification: Can convergence experiments under different heavy-tailed noise conditions be provided to verify theoretical predictions? Furthermore, in which practical training scenarios can stochastic low-rank decomposition lead to improvements in end-to-end training time, rather than just a reduction in optimizer FLOPs?

9 comments

We thank the reviewer T6ou for investing time in the review process. We address the concerns of the reviewer below.

[Weaknesses]

Limited theoretical novelty, lacking substantial insights to deepen the understanding of Muon. Regarding theoretical novelty: Compared to existing Nesterov-Muon and heavy-tailed stochastic optimization theories, what new optimization insights does Theorem 3.5 offer?

  • To the best of our knowledge Muon with Nesterov momentum has never been studied for inexact polar decomposition in the literature. This is the first work that does it. To tackle this assumption, our analysis goes through two rescaled momentum matrices (scaled by 1−β1 - \beta in line 289 - 290) and a recursion Lemma 3.3.

  • In Theorem 3.5 we provide the convergence guarantee of Muon. In this result, γ\gamma captures the error due to inexact polar decomposition (including Newton Schulz algorithm). However, the interesting insight from this theorem is that despite the amount of error in the oracle, we can always find a large batch size to guarantee convergence.

  • In Corollary 3.6, we guarantee convergence of Muon without the knowledge of α\alpha which characterizes the noise distribution. To the best of our knowledge, this is the first result for Muon which guarantees convergence without the knowledge of α\alpha.

  • Most of the previous work makes assumptions on the distance between momentum and inexact polar of momentum parameter. However, this is the first work that assumes a constraint on the inner product of the momentum and inexact polar of momentum. It captures the previous assumption as a special case (check table 1). Moreover, we show our assumption captures Newton Schulz and randomized Newton Schulz as a special case.

There remains a significant gap between Assumption 2.1 and practical Newton-Schulz implementations, limiting the practical significance of its theoretical guarantees. Regarding Assumption 2.1: For the empirical fifth-order Newton-Schulz polynomial commonly used in practical Muon optimization, can Assumption 2.1 be verified and practically meaningful dimensionality-related constants obtained? Under typical large model matrix dimensions, how stringent is the batch size constraint of Theorem 3.5?

Thanks for the insightful question. In practice a quintic polynomial φ(x)=ax+bx3+cx5\varphi(x)=ax+bx^3+cx^5 with coefficients (a,b,c)=(3.4445,−4.7750,2.0315)(a,b,c)=(3.4445,-4.7750,2.0315) is used for Newton Schulz. We can show that even this polynomial satisfies our Assumption 2.1. We provide a detailed proof of this result in the revised manuscript as Proposition G.1. We will add it to the main text of the paper in the updated version. We hope this addresses the reviewer’s concern about gap between practical Newton Schulz implementation and our proposed assumption.

The experiments failed to adequately validate the core theoretical conclusions and lacked practical efficiency advantages. Regarding experimental verification: Can convergence experiments under different heavy-tailed noise conditions be provided to verify theoretical predictions? Furthermore, in which practical training scenarios can stochastic low-rank decomposition lead to improvements in end-to-end training time, rather than just a reduction in optimizer FLOPs?

Thank you for the excellent suggestions. We have two new experiments to support our claims, which we will add to the paper.

Setup. We ran experiments on the following matrix regression problem, to measure the end-to-end running time and the convergence under heavy-tailed noise:

min⁡X∈Rn×nf(X)=12∥AXB−C∥F2,A∈Rp×n, B∈Rn×p, C=AX⋆B+cE.\min_{X \in \mathbb{R}^{n\times n}} f(X) = \tfrac12 \lVert AXB - C\rVert_F^2, \qquad A \in \mathbb{R}^{p\times n},\ B \in \mathbb{R}^{n\times p},\ C = AX^\star B + cE.

AA and BB are given data matrices. The ground truth X⋆X^\star and the noise EE have i.i.d. standard Gaussian entries.

Heavy-tailed noise. We use the problem above with p=n=256p = n = 256 and c=0c = 0. The stochastic gradient is Gk=∇f(Xk)+NkG_k = \nabla f(X_k) + N_k, where the entries of NkN_k are i.i.d. Student-t with tail index (degrees of freedom) 1.2, 1.5 or 2.5, or Gaussian. Each method is tuned separately for each tail index (the Nesterov and Polyak variants share the step size), and Rand-Muon uses rank 64. The table below shows the gradient norm averaged over the last 1,000 of the 10,000 iterations, relative to the initial gradient (mean ± standard deviation over 16 seeds; lower is better). All Muon variants are stable at every tail index without clipping, including the two infinite-variance cases (tail indices 1.2 and 1.5). This confirms convergence without bounded variance in our theory. We also can see that under heavy-tailed noise, Nesterov momentum can be better since it reaches a lower gradient norm than Polyak momentum for both Muon and Rand-Muon (by 1-4%) in the two infinite-variance cases. Under Gaussian noise, Rand-Muon matches Muon (its final gradient norm is 3-5% lower).

methodtail index 1.2tail index 1.5tail index 2.5Gaussian
Muon (Nesterov)0.0845 ± 0.00050.0364 ± 0.00010.01652 ± 0.000030.01197 ± 0.00001
Muon (Polyak)0.0877 ± 0.00060.0372 ± 0.00020.01759 ± 0.000030.01160 ± 0.00001
Rand-Muon (Nesterov, Gaussian sketch)0.1283 ± 0.00080.0486 ± 0.00020.01833 ± 0.000020.01132 ± 0.00001
Rand-Muon (Polyak, Gaussian sketch)0.1296 ± 0.00090.0498 ± 0.00020.01753 ± 0.000020.01113 ± 0.00001
Rand-Muon (Nesterov, Kaczmarz sketch)0.1134 ± 0.00090.0475 ± 0.00020.01717 ± 0.000030.01158 ± 0.00001

Orthogonalization time. We timed one orthogonalization of a Gaussian random matrix for the two common matrix shapes of a transformer of width d: d x d (attention) and 4d x d (MLP). Note that d = 768 in our nanoGPT, and d = 4096 and 8192 are the widths of 7B and 70B models (e.g. Llama-2). Times are in ms on one H100 GPU, speed-up over Newton-Schulz in brackets:

width dlayer shapeNewton-Schulz, 7 stepsrandomized, rank 10% of drandomized, rank 26% of drandomized, rank 256
768 (our nanoGPT)attention, d x d0.550.98 (0.56x)1.09 (0.51x)1.41 (0.39x)
768 (our nanoGPT)MLP, 4d x d0.640.85 (0.76x)1.35 (0.48x)1.71 (0.38x)
2048attention, d x d0.711.23 (0.58x)2.65 (0.27x)1.50 (0.47x)
2048MLP, 4d x d1.812.02 (0.90x)4.79 (0.38x)2.39 (0.76x)
4096 (7B scale)attention, d x d5.292.70 (1.96x)7.82 (0.68x)1.92 (2.75x)
4096 (7B scale)MLP, 4d x d15.55.25 (2.95x)15.5 (1.00x)3.51 (4.41x)
8192 (70B scale)attention, d x d40.010.1 (3.97x)25.7 (1.56x)2.98 (13.4x)
8192 (70B scale)MLP, 4d x d12023.2 (5.15x)57.3 (2.09x)6.24 (19.2x)

At d = 768 and 2048, the randomized step is slower at each rank. This is the scenario of our benchmarks (the CIFAR-10 matrices are even smaller), which is why it does not improve training time. At the 26% rank ratio of our experiments, it becomes faster only at d = 8192, which is the scale of a 70B model. With a smaller rank (10% of d, or 256), it is already faster at d = 4096.

The timings above are for a single orthogonalization. To check that the saving carries over to a complete optimization run, we ran Muon and Rand-Muon with Nesterov momentum for 20,000 iterations on the problem above with p=100p = 100, c=10−3c = 10^{-3} and the exact gradient ∇f(X)=A⊤(AXB−C)B⊤\nabla f(X) = A^\top (AXB - C) B^\top. As the table below shows, Rand-Muon is 10-13x faster at n = 8192. Both methods reach the same final gradient norm (about 6×10−86 \times 10^{-8} of the initial gradient), and they need about the same number of iterations to reach a given gradient norm. The table reports, for each run, the total wall-clock time, the final gradient norm and the number of iterations needed to reach a gradient norm of 10−210^{-2}, 10−310^{-3} and 10−510^{-5} (gradient norms are relative to the initial one):

nmethodtotal time (s)final gradient norm (10-8)iterations to reach 10-2iterations to reach 10-3iterations to reach 10-5
2048Muon186.31650270019850
2048Rand-Muon, rank 128256.41700240019850
2048Rand-Muon, rank 64256.01700240019850
4096Muon1215.41750270019850
4096Rand-Muon, rank 128355.61750250019850
4096Rand-Muon, rank 64266.21800250019850
8192Muon8606.01700270019850
8192Rand-Muon, rank 128825.91750245019850
8192Rand-Muon, rank 64676.11750245019850

So the randomized step reduces the time of the optimizer step when the weight matrices have width 4096 or more and the rank is small relative to the width.

Perplexity. The worse perplexity on nanoGPT (29.46 against 27.25) is the cost of rank 26% at d = 768. For this small-scale pretraining task, full Muon is the right choice when higher accuracy is the priority. Nevertheless, at larger scale, the proposed Rand-Muon can be much more efficient.

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

The paper studies Muon with Nesterov momentum under more general assumptions on gradient noise and approximate matrix orthogonalization. The authors provide convergence guarantees and propose a randomized low-rank method to reduce the computational cost of Muon.

The authors test their method on nanoGPT and CIFAR-10. The experiments show a substantial reduction in optimizer FLOPs, but no improvement in training time. The randomized method achieves similar accuracy on CIFAR-10 but worse perplexity than full Muon on nanoGPT.

Critical strengths

The paper provides a convergence analysis of Muon with Nesterov momentum, inexact polar decomposition, and heavy-tailed noise in a unified framework. The theoretical analysis is technically nontrivial and extends existing convergence results to a more practical setting.

Critical weaknesses

Several parts of theory have already been studied in previous works. The main contribution is combining these results into a single framework. The theoretical guarantee for the randomized method is very weak: guarantee in Lemma B.1 does not improve when increasing the sketch rank or the number of Newton–Schulz iterations and does not explain how additional computation improves the quality of the approximation. Also, the bound in Proposition 2.3 does not provide a useful guarantee in NanoGPT experiments.

The proposed randomized method does not improve training time and is slower than Muon, gives lower perplexity. On CIFAR-10 it takes longer to train. Heavy-tailed noise is not checked but it is one of the main motivations of the paper. I do not think experiments are convincing to demonstrate the practical benefits.

Questions for authors

I do not have specific questions for the authors. My main concerns are novelty of the theory and weak experiments, not clarity.

4 comments

We thank reviewer BCBR for investing time in the review process. We address the concerns of the reviewer below.

Several parts of theory have already been studied in previous works. The main contribution is combining these results into a single framework.

We agree that Muon has been analyzed in the literature on several occasions under different settings. However, it is unfair to undermine our contribution by calling it a combination of previous results. We detail the technical difficulties of our work below

  • Our paper is the first to propose an assumption like Assumption 2.1 which puts a constraint on the alignment of momentum MkM_k and the inexact polar oracle T(Mk)\mathcal{T}(M_k). The previous works on inexact polar decomposition most often put constraints on the distance of the actual momentum from their polar oracle. This new form of assumption comes with new difficulties and requires novel treatments. Therefore, calling the analysis just a combination of previous work is unfair.

  • Moreover, the analysis of stochastic algorithms under bounded variance is much simpler given the existing huge literature. However, the analysis becomes much more complicated when the gradient noise is heavy-tailed with σ1>0\sigma_1 > 0 (Assumption 3.2) and there is also stochasticity coming from randomized inexact polar decomposition.

  • The only other work that considers Muon with inexact momentum and heavy tailed noise is He et al. 2025. However, their analysis does not achieve the optimal convergence rate as we do in our work (check Table 1).

  • Our analysis also guarantees convergence of Muon for heavy tailed noise without the knowledge of noise parameter α\alpha (Corollary 3.6). To the best of our knowledge this is the first result of its kind for Muon.

The theoretical guarantee for the randomized method is very weak: guarantee in Lemma B.1 does not improve when increasing the sketch rank or the number of Newton–Schulz iterations and does not explain how additional computation improves the quality of the approximation.

Thanks for the excellent question. Here we provide the proof that our guarantee improves when we increase the number of iterations of Newton-Schulz method. In Lemma B.1, we proved Newton Schulz with qq iterations satisfy Assumption 2.1 γq=1−∑i=rσipq(σi/δ)∑i=1rσi\gamma_q = 1 - \frac{ \sum_{i = r} \sigma_i p_q (\sigma_i/ \delta)}{ \sum_{i = 1}^r \sigma_i}. Here we show that, γq≤γq−1\gamma_q \leq \gamma_{q-1} which implies our guarantee of Muon improves when we use more Newton Schulz iteration.

γq=1−∑i=rσipq(σi/δ)∑i=1rσi=1−∑i=rσiφ(pq−1(σi/δ))∑i=1rσi≤1−∑i=rσipq−1(σi/δ)∑i=1rσi=γq−1.\gamma_q = 1 - \frac{ \sum_{i = r} \sigma_i p_q (\sigma_i/ \delta)}{ \sum_{i = 1}^r \sigma_i} = 1 - \frac{ \sum_{i = r} \sigma_i \varphi (p_{q -1}(\sigma_i/ \delta))}{ \sum_{i = 1}^r \sigma_i} \leq 1 - \frac{ \sum_{i = r} \sigma_i p_{q -1}(\sigma_i/ \delta)}{ \sum_{i = 1}^r \sigma_i} = \gamma_{q-1}. Here, the inequality follows from Lemma A.6 φ(x)≥x\varphi(x) \geq x. I hope this clarifies the reviewer’s question and we will include this in the updated version of the manuscript.

Also, the bound in Proposition 2.3 does not provide a useful guarantee in NanoGPT experiments.

We do not see this as a weakness of our work. The primary goal of Proposition 2.3 is to highlight that our assumption 2.1 captures the randomized version of Newton Schulz as a special case. Therefore, our theoretical guarantees of Theorem 3.5 and Corollary 3.6 also explains the convergence of Muon with randomized Newton Schulz. We hope this clarifies the purpose of Proposition 2.3 to the reviewer.

The proposed randomized method does not improve training time and is slower than Muon, gives lower perplexity. On CIFAR-10 it takes longer to train. Heavy-tailed noise is not checked but it is one of the main motivations of the paper. I do not think experiments are convincing to demonstrate the practical benefits.

Thank you for the excellent suggestions. We have two new experiments to support our claims, which we will add to the paper.

Training time. We timed one orthogonalization of a Gaussian random matrix for the two common matrix shapes of a transformer of width d: d x d (attention) and 4d x d (MLP). Note that d = 768 in our nanoGPT, and d = 4096 and 8192 are the widths of 7B and 70B models (e.g. Llama-2). Times are in ms on one H100 GPU, speed-up over Newton-Schulz in brackets:

width dlayer shapeNewton-Schulz, 7 stepsrandomized, rank 10% of drandomized, rank 26% of drandomized, rank 256
768 (our nanoGPT)attention, d x d0.550.98 (0.56x)1.09 (0.51x)1.41 (0.39x)
768 (our nanoGPT)MLP, 4d x d0.640.85 (0.76x)1.35 (0.48x)1.71 (0.38x)
2048attention, d x d0.711.23 (0.58x)2.65 (0.27x)1.50 (0.47x)
2048MLP, 4d x d1.812.02 (0.90x)4.79 (0.38x)2.39 (0.76x)
4096 (7B scale)attention, d x d5.292.70 (1.96x)7.82 (0.68x)1.92 (2.75x)
4096 (7B scale)MLP, 4d x d15.55.25 (2.95x)15.5 (1.00x)3.51 (4.41x)
8192 (70B scale)attention, d x d40.010.1 (3.97x)25.7 (1.56x)2.98 (13.4x)
8192 (70B scale)MLP, 4d x d12023.2 (5.15x)57.3 (2.09x)6.24 (19.2x)

At d = 768 and 2048, the randomized step is slower at each rank. This is the scenario of our benchmarks (the CIFAR-10 matrices are even smaller), which is why it does not improve training time. At the 26% rank ratio of our experiments, it becomes faster only at d = 8192, which is the scale of a 70B model. With a smaller rank (10% of d, or 256), it is already faster at d = 4096.

Setup. We also ran experiments on the following matrix regression problem, to measure the end-to-end running time and the convergence under heavy-tailed noise:

min⁡X∈Rn×nf(X)=12∥AXB−C∥F2,A∈Rp×n, B∈Rn×p, C=AX⋆B+cE.\min_{X \in \mathbb{R}^{n\times n}} f(X) = \tfrac12 \lVert AXB - C\rVert_F^2, \qquad A \in \mathbb{R}^{p\times n},\ B \in \mathbb{R}^{n\times p},\ C = AX^\star B + cE.

AA and BB are given data matrices. The ground truth X⋆X^\star and the noise EE have i.i.d. standard Gaussian entries.

The timings above are for a single orthogonalization. To check that the saving carries over to a complete optimization run, we ran Muon and Rand-Muon with Nesterov momentum for 20,000 iterations on the problem above with p=100p = 100, c=10−3c = 10^{-3} and the exact gradient ∇f(X)=A⊤(AXB−C)B⊤\nabla f(X) = A^\top (AXB - C) B^\top. As the table below shows, Rand-Muon is 10-13x faster at n = 8192. Both methods reach the same final gradient norm (about 6×10−86 \times 10^{-8} of the initial gradient), and they need about the same number of iterations to reach a given gradient norm. The table reports, for each run, the total wall-clock time, the final gradient norm and the number of iterations needed to reach a gradient norm of 10−210^{-2}, 10−310^{-3} and 10−510^{-5} (gradient norms are relative to the initial one):

nmethodtotal time (s)final gradient norm (10-8)iterations to reach 10-2iterations to reach 10-3iterations to reach 10-5
2048Muon186.31650270019850
2048Rand-Muon, rank 128256.41700240019850
2048Rand-Muon, rank 64256.01700240019850
4096Muon1215.41750270019850
4096Rand-Muon, rank 128355.61750250019850
4096Rand-Muon, rank 64266.21800250019850
8192Muon8606.01700270019850
8192Rand-Muon, rank 128825.91750245019850
8192Rand-Muon, rank 64676.11750245019850

Perplexity. The worse perplexity on nanoGPT (29.46 against 27.25) is the cost of rank 26% at d = 768. For this small-scale pretraining task, full Muon is the right choice when higher accuracy is the priority. Nevertheless, at larger scale, the proposed Rand-Muon can be much more efficient.

Heavy-tailed noise. We use the problem above with p=n=256p = n = 256 and c=0c = 0. The stochastic gradient is Gk=∇f(Xk)+NkG_k = \nabla f(X_k) + N_k, where the entries of NkN_k are i.i.d. Student-t with tail index (degrees of freedom) 1.2, 1.5 or 2.5, or Gaussian. Each method is tuned separately for each tail index (the Nesterov and Polyak variants share the step size), and Rand-Muon uses rank 64. The table below shows the gradient norm averaged over the last 1,000 of the 10,000 iterations, relative to the initial gradient (mean ± standard deviation over 16 seeds; lower is better). All Muon variants are stable at every tail index without clipping, including the two infinite-variance cases (tail indices 1.2 and 1.5). This confirms convergence without bounded variance in our theory. We also can see that under heavy-tailed noise, Nesterov momentum can be better since it reaches a lower gradient norm than Polyak momentum for both Muon and Rand-Muon (by 1-4%) in the two infinite-variance cases. Under Gaussian noise, Rand-Muon matches Muon (its final gradient norm is 3-5% lower).

methodtail index 1.2tail index 1.5tail index 2.5Gaussian
Muon (Nesterov)0.0845 ± 0.00050.0364 ± 0.00010.01652 ± 0.000030.01197 ± 0.00001
Muon (Polyak)0.0877 ± 0.00060.0372 ± 0.00020.01759 ± 0.000030.01160 ± 0.00001
Rand-Muon (Nesterov, Gaussian sketch)0.1283 ± 0.00080.0486 ± 0.00020.01833 ± 0.000020.01132 ± 0.00001
Rand-Muon (Polyak, Gaussian sketch)0.1296 ± 0.00090.0498 ± 0.00020.01753 ± 0.000020.01113 ± 0.00001
Rand-Muon (Nesterov, Kaczmarz sketch)0.1134 ± 0.00090.0475 ± 0.00020.01717 ± 0.000030.01158 ± 0.00001

We again thank the reviewer for thoughtful reviews. We will include all these clarifications and experiments in the updated version of the manuscript. If the reviewer thinks we have addressed all the concerns, please consider raising your score to support acceptance.

AuthorsOpenReview ↗

Kind reminder and new results

Dear Reviewer BCBR,

As the discussion period is coming to an end, we would like to kindly follow up. We hope our response has resolved your concerns. If so, we would greatly appreciate it if you would consider raising your score to support the paper's acceptance. Please let us know if anything remains unclear.

Moreover, we would like to let you know about the new experiments we added at the request of Reviewer T6ou. First, we extended our heavy-tailed experiment to noise that grows with the gradient (σ1>0\sigma_1 > 0). All Muon variants converge without clipping, and Nesterov momentum reaches a lower gradient norm than Polyak momentum. Second, we evaluated the batch-size condition of Theorem 3.5 at the widths of three well-known LLMs. For σ1=0.05\sigma_1 = 0.05 and finite variance, the batch size required by Rand-Muon is within the range of batch sizes used in practice at these widths.

Comments on the paper

1 comment

We express our sincere gratitude to all reviewers for their thorough evaluations and constructive feedback. Throughout the rebuttal phase, we addressed each point of concern, conducting additional empirical evaluations and deriving new theoretical results. Below, we present a summary of new things we did during rebuttal.

  • [Refinement of Theoretical Guarantees via Newton–Schulz Iterations] In response to Reviewer BCBR, we established that the theoretical guarantees provided in Lemma B.1 strictly strengthen as the number of Newton-Schulz iterations increases.
  • [Validity of Proposed Assumption for Practical Newton–Schulz Implementations] Addressing Reviewer T6ou's observation regarding the practical use of a quintic polynomial with tuned coefficients, we provided formal proof in Appendiix G demonstrating that this practical variant satisfies Assumption 3.2.
  • [Theoretical Justification for Nesterov vs. Polyak Momentum] In response to Reviewer T6ou's inquiry concerning the choice of momentum scheme, we provided a theoretical analysis in the Appendix G demonstrating the advantages of Nesterov momentum for Muon.
  • [Randomized Muon Speeds Up the Optimizer Step for Larger LLMs] All reviewers raised the question of training time. With a small rank, the randomized orthogonalization is 2-19x faster than Newton-Schulz at the scale of 7B and 70B models, and the speed-up grows with the model width. It is slower only at the small scales of our nanoGPT and CIFAR-10 experiments, where the GPU is not fully utilized.
  • [Randomized Muon Is Faster End-to-End on Large Problems] In response to all reviewers, we also measured the end-to-end time on an 8192 x 8192 matrix regression problem, where Rand-Muon is 10-13x faster than Muon and reaches the same final gradient norm.
  • [Convergence under Heavy-Tailed Noise] As suggested by Reviewers BCBR and T6ou, we added matrix regression experiments with Student-t noise. All Muon variants converge without clipping, even with infinite variance, where Nesterov momentum reaches a lower gradient norm than Polyak momentum.
  • [Convergence When Noise Grows with the Gradient] As further suggested by Reviewer T6ou, we tested noise that grows with the gradient (1>0). Rand-Muon still converges, and a larger batch consistently lowers the gradient norm.
  • [Batch-Size Condition Is Attainable for Larger LLMs] As suggested by Reviewer T6ou, we estimated the batch size that Theorem 3.5 requires for Rand-Muon at the widths of three well-known LLMs. Assuming 1=0.05 and finite variance, it is within the range used in practice.

We trust that our revisions and detailed responses successfully address all of the reviewers' comments and concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.