- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper asks whether the row normalization in NorMuon can make Muon provably faster. To answer it, the authors analyze the worst-case iteration complexity in the operator-norm geometry, under which Muon’s update is the steepest descent direction. They show that NorMuon's row normalization instead increases the complexity by a factor of the number of rows. This cost remains even with exact orthogonalization and for any fixed momentum parameters and step-size rule. The experiments cover synthetic problems built on the worst-case construction and LLM pretraining up to 6.4B parameters. NorMuon is slower than Muon on the synthetic problems but outperforms it in LLM pretraining, which the authors present as sharpening the puzzle of why row normalization helps in practice.
Critical strengths
- The theoretical results are clean and complete in the deterministic setting.
- The worst-case construction gives a simple and intuitive picture of where the cost comes from, which the synthetic experiments also confirms.
Critical weaknesses
-
The main theoretical result is largely expected from the setup. In the operator-norm geometry, Muon’s update is the steepest descent direction by definition, so any fixed rescaling of its rows can only move the update away from it in the worst case.
-
The puzzle that the paper raises is also largely a consequence of the chosen lens, i.e., the worst case over all smooth functions. Aurora [1] already gives a concrete explanation of why row normalization helps in practice. In tall matrices, neurons that receive small updates under Muon keep receiving small updates and eventually become inactive. Such a feedback between past updates and future gradients comes from the structure of neural networks, which the worst case construction does not need to have. The function that the paper constructs for its lower bound has a gradient that stays constant along the iterates, so how much a row is updated never changes the gradient it receives. Moreover, a network with many inactive neurons can still have a small gradient, so reaching a small gradient faster does not mean reaching a better solution. Therefore, being slower in the worst case and better in practice is not a contradiction, and the claim that the findings sharpen the puzzle seems overstated.
-
The experiments are largely disconnected from the analysis. The synthetic problems are built directly from the worst-case construction, so NorMuon being slower there is expected by design. The LLM part mostly reruns several existing normalization variants against Muon, and reaches the same conclusions as prior work that normalization helps and that the gain comes mainly from the MLP matrices. None of these experiments relates back to the analysis. For example, the paper never checks whether the updates in real training are concentrated on a few rows as in the worst-case construction. As a result, the experiments neither support nor challenge the theory, and only restate the gap between the worst case and practice.
[1] Dewulf, Alec, et al. "Aurora: A Leverage-Aware Spectral Optimizer." arXiv preprint arXiv:2606.27715 (2026).
Questions for authors
-
The worst-case construction seems to apply to any method that equalizes the rows of the update, whether before or after the orthogonalization. Does the lower bound then also cover Muon+, MuonEq-R and Aurora? If so, stating this would make clear that the result is about row balancing in general, not NorMuon specifically, which would broaden the impact of this work.
-
The conclusion is tied to the operator-norm geometry, under which Muon’s update is the steepest descent direction. Under a geometry defined by the largest row norm, row normalization is instead the steepest descent direction. How would the results change in such a geometry, and which geometry do the authors think better matches the matrices where NorMuon helps?
-
The theory analyzes normalization over rows, while the experiments normalize the MLP matrices along their larger dimension. Could the authors clarify how the theory applies to the setting used in the experiments?
5 comments
Kind Follow-Up on Our Response
Dear Reviewer utW4,
Thank you for your detailed review. We appreciate your time and effort.
As the discussion deadline approaches, we wanted to follow up to check whether our response has addressed your concerns and questions. If you have any further questions, we would be happy to discuss them.
Thank you again, and we look forward to your response.
Sincerely,
Authors of Paper 22475
Dear Reviewer utW4,
Thank you again for your detailed review. As the discussion period ends in 48 hours, we would be grateful if you could let us know whether our responses have addressed your questions and concerns. We would be happy to discuss any further questions you may have.
Sincerely,
Authors of Paper 22475
Thank you for your time and comments. We clarify each point below.
W1: The main theoretical result is largely expected from the setup. In the operator-norm geometry, Muon's update is the steepest descent direction by definition, so any fixed rescaling of its rows can only move the update away from it in the worst case.
Muon is steepest, and we hope to clarify that rescaling steepest descent may not worsen the complexity. E.g., AdaGrad's regret is never worse than that of online gradient descent in ℓ2 (Corollary 1 of [1]). NorMuon's rescaling is similar to AdaGrad. Moreover, steepest descent concerns the one step decrease, not the complexity, which we characterize as a Θ(m) extra cost.
W2(a): ... receives.
We agree that Aurora empirically explains why NorMuon works in LLM, but it gives limited theory on optimization gains. We view Aurora and our paper as complement to each other. Since NorMuon is worse in the worst case, its gain should come from the structure of LLM, which Aurora may help reveal. We agree that the hard instance does not characterize the feedback between past updates and future gradients, and will list this as future work.
W2(b): Moreover ...
We agree that small gradient does not imply a better solution. This is a limitation of worst-case nonconvex analysis.
We do not claim a contradiction between the worst case and LLM. By "sharpen the puzzle," we mean that our analysis and ablations rule out polar and β2 as explanations. We have revised the wording.
W3
We hope to make a point that our synthetic experiments, new experiments (Tables R1–R2, Reviewer bVe2), and ablations are closely connected to theory.
For synthetic experiments, we clarify that it is designed with imbalanced rows but different from Theorem 3.1. It is to show that NorMuon remains slower even after tuning. We have added a new experiment to include cosine scheduling.
For LLM, as suggested, we measured the norm imbalance along the normalization dimension, i.e., the rows for square matrices and the larger dimension otherwise (Tables R1–R2). The CV (std/mean) of these norms in the momentum is below 1, compared with >13 in the lower bound. The norms are imbalanced, but far less than in the worst case. Appendix C.3 shows that NorMuon attains a larger alignment than Muon on MLP matrices via a larger momentum. On the same momentum, NorMuon's alignment is smaller than Muon's (Table R2), yet the ratio (0.8–1) far exceeds ~0.08 of the hard instance.
Q1
The lower bound covers Muon+, MuonEq-R, and Aurora. We have added the proof to Appendix B.2, where we establish a unified condition.
Q2(a): How would the results change in such a geometry?
Let ∥X∥R=maxi∥Xi,:∥2, with dual ∥G∥R∗=∑i∥Gi,:∥2. Steepest descent is Xt+1=Xt−ηtR(∇F(Xt)), [R(G)]i,:=Gi,:/∥Gi,:∥2. If ∥∇F(Y)−∇F(X)∥R∗≤LR∥Y−X∥R, then, similar to Eq. (3.1), ηt=∥∇F(Xt)∥R∗/LR gives F(Xt+1)≤F(Xt)−∥∇F(Xt)∥R∗2/(2LR), and thus mint<T∥∇F(Xt)∥R∗≤ϵ within T=O(ΔLRϵ−2) iterations, free of dimension. The steepest descent is not NorMuon, which normalizes polar.
Q2(b): Which geometry do the authors think better matches the matrices where NorMuon helps?
We currently view the operator norm as the best choice and leave this to future work. Given the layerwise structure and normalization layers of LLMs, the operator (ℓ2→ℓ2) norm is regarded as a good model [2,3], underlying Muon's success. No ℓp1→ℓp2 induced norm makes NorMuon steepest descent. We have not found a natural norm modeling NorMuon better. Still, the operator norm may not fully characterize LLMs; e.g., [2] treats the first and the last layers by different norms, and they are often trained with AdamW in practice. A better norm model for LLMs may eventually explain NorMuon's gain.
Q3
Theorems 3.1-3.3 hold by transposition. Normalizing along the larger dimension can be viewed as normalizing the rows of the possibly transposed max(m,n)×min(m,n) matrix. Since polar, the operator and nuclear norms, and Assumptions 2.1–2.3 are transposition invariant, Theorems 3.1–3.3 hold with m replaced by max(m,n). We have added a remark.
Thank you again, and we look forward to further discussion.
References
[1] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. JMLR, 12(7), 2011.
[2] T. Pethick, W. Xie, K. Antonakopoulos, Z. Zhu, A. Silveti-Falls, and V. Cevher. Training deep learning models with norm-constrained LMOs. In ICML, pp. 49069–49104. PMLR, 2025.
[3] K. Jordan, Y. Jin, V. Boza, J. You, F. Cesista, L. Newhouse, and J. Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024.