acceptodds
Under review as a conference paper at ICLR 2027

Preconditioning Benefits of Spectral Orthogonalization in Muon

Abstract

The Muon optimizer has achieved strong empirical performance in large language model training, yet the role of spectral orthogonalization in its effectiveness remains poorly understood. We study its preconditioning effect through two case studies: matrix factorization and in-context linear regression in an infinite-prompt Gaussian softmax-attention model. For both problems, we prove that exact-polar \muon attains logarithmic iteration complexity independent of the relevant condition number, for every fixed momentum parameter under suitable initialization and stepsize conditions. We also establish condition-number-dependent lower bounds for gradient descent and standard full-batch Adam on separate hard instances. On a common locally initialized matrix-factorization instance, we further separate Muon's logarithmic dependence on the condition number from stabilized Adam's square-root dependence, assuming bounded scalar learning rates. Our analysis reduces the convergence argument to scalar dynamics in the spectral domain, revealing how orthogonalization balances progress across modes. These results identify spectral orthogonalization as the source of the preconditioning effect, which arises even without momentum.

Primary area:
optimization
Keywords:
Muon, preconditioning effect, matrix factorization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_oQLBOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the preconditioning effect of exact-polar Muon in symmetric matrix factorization and an infinite-prompt Gaussian softmax-attention model. It establishes logarithmic iteration complexity, independent of the condition number, for each fixed momentum parameter. The paper proves lower bounds for a coordinatewise gradient-history class that includes full-batch Adam, along with a matched local separation between Muon and stabilized Adam. Synthetic experiments support the theoretical claims.

Critical strengths
  1. The paper delivers a theoretical characterization of spectral orthogonalization and undercomplete matrix factorization. The analysis shows that normalizing spectral updates can eliminate dependence on the condition number, clarifying the mechanism in Muon’s preconditioning.
Critical weaknesses
  1. The guarantee on the general matrix factorization is limited. Table 1 suppresses 1/(1−ρ)1/(1-\rho), which the sufficient positive-momentum conditions (in Appendix B.3) force to be extremely large as μ\mu gets closer to 1; the value is lower bounded by Ω((1−μ)−4)\Omega((1-\mu)^{-4}). These restrictions limit what the logarithmic iteration bound explains about training with practical schedules.

  2. The comparison with Adam remains restricted. Though the paper provides a matched comparison in a particular regime (Table 1), the main lower bounds use different initializations from the Muon upper bounds.

Questions for authors
  1. Could Table 1 explicitly include the dependence on ρ\rho and its admissible range depending on μ\mu?

  2. Equation 31 gives an initialization scale for the undercomplete guarantee, which depends on the accuracy level ε\varepsilon. How much of this dependence is necessary for the dynamics? Could the authors either explain this sensitivity or provide experimental results?

  3. How robust are the Adam lower bounds to small perturbations in the initializations? Do these lower bounds hold with non-negligible probability under a random initialization scheme? Can a comparable bound be derived under the initializations assumed in the Muon upper bounds?

2 comments
AuthorsOpenReview ↗

Response to Reviewer oQLB

Thank you for these questions. We have made the schedule dependence explicit, examined initialization sensitivity, and clarified what the Adam lower bounds establish.

1. Dependence on ρ\rho and μ\mu. We agree that hiding 1/(1−ρ)1/(1-\rho) obscured an important limitation. Table 1 now reports (1+log⁡(1/ε))/(1−ρ)(1+\log(1/\varepsilon))/(1-\rho) and the admissible decay ranges. For example, at μ=0.9\mu=0.9 the general matrix-factorization proof requires 1/(1−ρμ)≃3.42×1091/(1-\rho_\mu)\simeq3.42\times10^9, while the experiments use ρ=0.98\rho=0.98 (giving 5050). Thus the general theorem does not explain that practical schedule. The ICL theorem and the matched local comparison admit faster decay; we distinguish these results in the Discussion.

2. Accuracy-dependent initialization in undercomplete factorization. The requirement that the starting scale shrink with ε\varepsilon is sufficient, not known to be necessary. Our proof controls the accumulated alignment error until the decaying steps become smaller than the desired tolerance; finer accuracy requires a longer tracking horizon and hence a smaller certified initial scale (Appendix B.1). We cannot yet prove convergence to arbitrary accuracy from one fixed undercomplete start. However, in 160 sensitivity runs using a common schedule across four starting scales, two widths, and two condition numbers, every run reached and sustained 10−710^{-7} error within 2,000 updates (Appendix L.3). This suggests the sufficient condition may be conservative.

3. Are the Adam lower bounds caused by poor initialization? No: the constructions deliberately start near a true solution. With unrestricted initialization, an algorithm might stall at a saddle point or in an invariant low-dimensional subspace; that would say little about its local convergence rate. Our lower bounds avoid this issue:

  • Matrix factorization (Theorem 2; Appendix G): The hard initialization is full-rank and can be made arbitrarily close to the solution set: its distance is at most Cτκ−1/4C\tau\kappa^{-1/4} for arbitrarily small τ>0\tau>0. Yet coordinatewise gradient-history methods, including the specified full-batch Adam, still have an Ω(κ)\Omega(\sqrt\kappa) conditioning barrier when seeking sufficiently high accuracy.
  • Softmax ICL (Theorem 4; Appendix I): The hard initialization can satisfy ∥Q0−Q⋆∥F=r0\|Q_0-Q^\star\|_F=r_0 for any r0>0r_0>0, while the lower bound remains Ω(κlog⁡(1/ε))\Omega(\sqrt\kappa\log(1/\varepsilon)) for the stated relative-objective target.

We agree that these broader lower bounds use different starts and error criteria from the Muon upper bounds; they are not direct matched comparisons. That is why we also added Proposition 6: for any prescribed neighborhood of an optimum, it constructs a common factorization instance and initialization on which Muon needs Oμ(log⁡κ+log⁡(1/ε))O_\mu(\log\kappa+\log(1/\varepsilon)) iterations but stabilized Adam requires Ω(κlog⁡(1/ε))\Omega(\sqrt\kappa\log(1/\varepsilon)). The Adam result assumes a positive stabilizer and bounded scalar rates, which we state explicitly.

Robustness to perturbations. Theorem 2 uses exact zero-gradient histories, so its support-based proof does not extend directly to dense perturbations or isotropic random starts. For the matched Adam result, Appendix J.4 shows that the finite-horizon lower bound persists in some Frobenius ball around the constructed initialization, uniformly over bounded scalar-rate schedules. We do not quantify that ball's probability under standard random initialization or claim a matched Muon guarantee throughout it.

Thank you for your clarification. The authors' response addressed my questions, hence I raise my score to 3 (weak accept).

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

Muon orthogonalizes a matrix-valued momentum buffer by replacing every nonzero singular value of B with one. This paper argues that such orthogonalization provides a condition-number-independent convergence advantage in matrix factorization and infinite-prompt in-context learning with softmax attention. It establishes condition-number-independent upper bounds for exact-polar Muon and condition-number-dependent lower bounds for coordinatewise adaptive methods on separate hard instances, together with a restricted matched comparison against stabilized Adam. Numerical evaluations support weak condition-number dependence for exact-polar Muon at zero and positive momentum. Additional experiments show that five-step Newton–Schulz approximately preserves this behavior in the positive-momentum ICL setting.

Critical strengths
  1. The paper provides a clear preconditioning mechanism explaining how orthogonalization equalizes progress across spectral modes. It presents substantial theoretical analysis covering zero and positive momentum across two structured objectives.
  2. The paper identifies concrete settings in which exact-polar Muon removes the condition-number dependence observed for ordinary gradient methods. It provides Muon upper bounds, coordinatewise lower bounds, and a restricted matched separation from stabilized Adam.
  3. The numerical comparisons support the theoretical behavior on the studied synthetic problems. The appendices provide detailed reproducibility information, including tuning procedures, evaluation seeds, censoring rules, and numerical diagnostics.
Critical weaknesses
  1. The analyzed objectives and initializations ensure, or rapidly induce, alignment between the spectral directions normalized by Muon and the directions encoding ill-conditioning. This limits the generality of the proposed causal mechanism, as the paper does not theoretically or empirically demonstrate that such alignment persists in noncommuting neural-network optimization.
  2. Different learning-rate schedules introduce an intervention beyond spectral orthogonalization. Muon, SignGD, and GD use different schedule families, so we may not be able to attribute the numerical differences exclusively to orthogonalization.
  3. In undercomplete matrix factorization, the condition-number-independent iteration bound shifts substantial dependence into initialization. The admissible initialization scale depends strongly on the condition number and requested accuracy. Consequently, a different or practically fixed initialization may not satisfy the theorem’s assumptions, and condition-number-independent convergence is then not established.
Questions for authors
  1. Can the authors theoretically or empirically examine whether the gradient singular directions remain aligned with the directions of ill-conditioning in noncommuting neural-network optimization?
  2. Can the authors better justify the optimizer-specific schedule choices and provide controlled comparisons using matched schedule families and equal tuning budgets? How sensitive are the conclusions to these choices?
  3. How sensitive is the undercomplete condition-number-independent result to initialization? Can it be extended to a fixed initialization independent of the requested accuracy, with explicit condition-number dependence?
2 comments
AuthorsOpenReview ↗

Response to Reviewer XDkb

Thank you for raising these questions. We added experiments to probe alignment and control for learning-rate choices, and clarified the scope of the initialization guarantees.

1. Does alignment persist outside the structured model? We agree that this remains open. In a new finite-prompt softmax experiment with a dense, noncommuting initialization (Appendix L.7), we test whether the momentum-buffer Gram matrix aligns with the input covariance and whether a leading gradient singular mode aligns with the full training-loss Hessian. Neither diagnostic shows persistent alignment: at prompt length 128 and κ(S)=16\kappa(S)=16, the normalized commutator stays around 0.09–0.12 across measured checkpoints, while the Hessian-mode residual rises from 0.602 to 0.751. Held-out loss nevertheless decreases. These results limit how far we can extrapolate our aligned theory; they do not rule out alignment of larger subspaces or establish a mechanism for general neural-network training.

2. Could learning-rate schedules explain the difference? Learning rates matter, but a scalar step size changes the magnitude of an update, not the shape of its preconditioner. At a fixed momentum buffer BtB_t, Muon replaces all nonzero singular values by one, whereas norm-normalized GD preserves their ratios and Adam uses coordinatewise scaling. No choice of a single scalar step size can generally turn these directions into one another. Of course, schedules can change future iterates, so controlled comparisons are still important.

We added a matched-search experiment (Table 2; Appendix L.1): all five methods tune over the same 51 schedules and evaluation starts. Norm-GD is a particularly useful control because its step has the same spectral norm as Muon's on an identical schedule, without flattening singular values. At κ=15625\kappa=15625, tuned Norm-GD takes a median 4,863.5 updates to remain below the target, versus 597 for Muon; at κ=25\kappa=25, Norm-GD is slightly faster. Thus spectral orthogonalization matters on this family, but we do not claim a universal ranking.

Importantly, our Adam lower bounds in Theorems 2 and 4 are independent of the learning-rate schedule. They cover the specified full-batch Adam recursion with arbitrary shared scalar step sizes, including adaptive choices, on their respective hard instances. They do not arise from the optimizer-specific schedules in the original figures. The separate matched-instance comparison in Proposition 6 does require bounded scalar Adam step sizes; we now distinguish these claims explicitly.

3. Does the undercomplete result extend to a fixed initialization? Not under our current proof. Theorem 1(b) requires a starting scale that depends on the desired accuracy and, through its sufficient conditions, on κ\kappa (Appendix B.1). We have clarified that this does not establish convergence to arbitrary accuracy from one fixed undercomplete initialization; Theorem 1(a) does provide a fixed-start guarantee in the wide regime.

We also tested initialization sensitivity with a fixed schedule at μ=0.9\mu=0.9, varying the starting scale, width, and condition number across 160 runs (Appendix L.3). Every run reached and sustained operator error 10−710^{-7} within 2,000 updates. This suggests that the sufficient condition may be conservative in these examples, but it does not prove the desired fixed-start theorem.

C1. The new noncommuting experiment weakens the proposed mechanism's extension beyond structured models, but should not be considered as a major weakness of this study. C2. The schedule-independent Adam lower bounds separate the theoretical result from experimental schedule choices. C3. This study does not provide arbitrary-accuracy convergence from a fixed initialization, while the experiment suggests the sufficient conditions may be conservative.

I believe the main paper should explicitly distinguish the aligned theory on structured models, the wide fixed-start guarantee, and the under-complete result on initialization dependency. I would not change my score.

Reviewer_xSdzOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper analyzes exact-polar Muon with ordinary momentum on symmetric matrix factorization and a structured infinite-prompt Gaussian softmax-attention objective. By reducing the dynamics to spectral scalar recursions, it proves condition-number-independent iteration bounds under suitable initialization and schedules. It also develops coordinatewise-method lower bounds and a narrower matched-instance separation from stabilized Adam.

Critical strengths

Reducing the dynamics to spectral scalar recursions provides a good framework for understanding how orthogonalization balances progress across modes. The condition number independent iteration bounds with momentum are novel.

Critical weaknesses

My main concerns are limited novelty and limited evaluation. While the discrete-time, exact-polar guarantees with arbitrary momentum, and formal lower bounds against Adam is novel, the conceptual novelty beyond very similar ideas in the direction of Muon working as an effective preconditioner is limited. Similar works include Lau et al (PolarGrad), Rhee et al (Muon learned balanced solutions in matrix factorization), Tong et al (Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent), etc, as well as the original Muon expositions by Bernstein and Newhouse. I see that these are cited in the paper itself, I believe the conceptual novelty beyond them is limited, especially with limited empirical evaluation.

On the empirical side, the evaluation settings are limited. There should also be more extensive comparisons with prior works such as Parviz et al (Reassessing Muon for matrix factorization), which found that AdamW outperforms Muon at extreme condition numbers.

Questions for authors

Please refer to weaknesses above. In particular regarding more extensive empirical evaluations. The current evaluations are limited to structured synthetic objectives. Furthermore, the Adam baseline should be tuned.

3 comments
AuthorsOpenReview ↗

Response to Reviewer xSdz

Thank you for the thoughtful review. We have clarified the theoretical novelty and added better-tuned comparisons, while making the limitations more explicit.

1. Theoretical novelty: a convergence-rate separation between Muon and Adam. We agree that Muon's preconditioning interpretation is established (Bernstein and Newhouse; Lau et al.; Tong et al.), and Rhee et al. have explained spectral balancing and geometric annealing without momentum. But knowing that Muon acts as a preconditioner does not establish that it converges faster than Adam: existing generic rate analyses do not distinguish the two.

To our knowledge, Proposition 6 provides the first such rigorous rate separation in a matrix-factorization model. On the same instance, initialization, and relative-objective target, exact-polar Muon needs Oμ(log⁡κ+log⁡(1/ε))O_\mu(\log\kappa+\log(1/\varepsilon)) iterations for any fixed 0≤μ<10\leq\mu<1, while stabilized full-batch Adam needs Ω(κlog⁡(1/ε))\Omega(\sqrt{\kappa}\log(1/\varepsilon)), even with adaptively chosen bounded scalar learning rates. This is a local separation requiring a positive Adam stabilizer, not a universal claim about Adam.

More broadly, Theorems 1 and 3 establish condition-number-independent Oμ(1+log⁡(1/ε))O_\mu(1+\log(1/\varepsilon)) reconstruction rates for momentum Muon in matrix factorization and structured softmax ICL. Theorems 2 and 4 give lower bounds for coordinatewise methods including Adam, but use different initializations or error criteria; Proposition 6 is the matched comparison. The new proof controls the overshoot caused by momentum when a spectral gradient changes sign (Appendix B.3). We now state the initialization and learning-rate restrictions clearly.

2. Better-tuned Adam comparisons. We now evaluate actual Adam, not just a local approximation (Table 2; Appendix L.1). In d=64d=64 factorization, we tune over 51 schedules on separate starts and evaluate on ten paired starts, with an expanded β2\beta_2 search for Adam. Results are mixed: at κ=625\kappa=625, Adam reaches the target sooner, but only 1/10 runs stays below it versus 10/10 for Muon. At κ=15625\kappa=15625, tuned Adam (β2=0.99\beta_2=0.99) achieves 10/10 sustained successes, but its median time is 3,842.5 updates versus 597 for Muon. We do not claim uniform superiority and distinguish these zero-weight-decay Adam runs from Parviz et al.'s AdamW experiments.

3. Broader evaluation. Appendix L.7 adds finite-prompt softmax-attention training with minibatches, noncommuting initialization, and held-out evaluation. We compare exact-polar Muon, Newton–Schulz Muon, AdamW, and momentum GD. Momentum GD achieves the lowest median held-out loss in three of four settings, and Newton–Schulz Muon in one. This remains a synthetic model, and we make no theoretical claim about end-to-end language-model training.

Area_Chair_VeWAOpenReview ↗

Please respond to the rebuttal before the deadline

Dear Reviewer xSdz,

The authors have responded to your concerns.

Please respond before tomorrow's deadline (AoE), say whether your concerns are resolved, and update your score accordingly.

Reviews without a response will carry less weight in my decision.

Best, AC

Reviewer_xSdzOpenReview ↗

Thank you for your responses

Dear Authors, Thank you very much for clarifying some of my novelty concerns. I think the theoretical contributions are interesting. However, my concern regarding limited evaluation remains open. The comparisons happen in a synthetic setting, with small finite-prompt attention experiments for a small number of updates. The models evaluated, as well as the dataset and training regimes used, are far from the modern LLM training pipelines. As a result, I tend to maintain my current score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the three reviewers and the Area Chair for their careful reading and constructive feedback. In response, we have substantially revised the manuscript, including its theoretical exposition, comparison with prior work, and empirical evaluation. Beyond clarifying our claims, we have added new controlled optimizer comparisons, initialization-sensitivity studies, and experiments that directly test the assumptions behind our theory. We summarize these major changes below; our individual responses address each concern in more detail.

1. Reframing and sharpening the theoretical contribution. Muon's spectral-preconditioning interpretation is well established; our contribution is to show when it produces a provable convergence-rate separation. Theorems 1 and 3 give condition-number-independent reconstruction rates for exact-polar momentum Muon in matrix factorization and structured softmax ICL. Theorems 2 and 4 establish condition-number-dependent lower bounds for coordinatewise methods, including the specified full-batch Adam with arbitrary shared scalar learning-rate schedules. These broader bounds use different starts and error criteria. Crucially, Proposition 6 gives a matched comparison on the same factorization instance, initialization, and accuracy target: Oμ(log⁡κ+log⁡(1/ε))O_\mu(\log\kappa+\log(1/\varepsilon)) iterations for Muon versus Ω(κlog⁡(1/ε))\Omega(\sqrt\kappa\log(1/\varepsilon)) for stabilized Adam under its local assumptions. Our lower-bound hard starts can be arbitrarily close to an optimum; their slowness is not merely a saddle-point artifact.

2. Revising the theoretical presentation and assumptions. Table 1 now shows the full dependence on the decay factor ρ\rho and its admissible range. We acknowledge that the general positive-momentum factorization theorem requires much slower decay than our experimental schedules. We distinguish fixed-start guarantees in wide factorization from accuracy-dependent initialization in the undercomplete case, and explicitly state the positive-stabilizer and bounded-rate assumptions of the matched Adam comparison.

3. Adding controlled optimizer comparisons. We added actual Adam and spectral-norm-normalized GD baselines. In the new d=64d=64 factorization study (Table 2; Appendix L.1), all five methods search the same 51 schedules on separate tuning starts and are evaluated on ten paired starts. We also test Adam's β2\beta_2 and different target spectra, reporting both first-hit and sustained accuracy. The results are mixed: Adam can improve substantially with tuning. We do not claim uniform superiority for Muon or present these zero-weight-decay runs as an AdamW replication.

4. Adding robustness tests beyond aligned models. We added 160 undercomplete-factorization runs varying initialization (Appendix L.3), plus finite-prompt softmax training with noncommuting starts, minibatches, and held-out evaluation (Appendix L.7). The latter compares exact-polar and Newton–Schulz Muon, AdamW, and momentum GD, and measures alignment with the covariance and full loss Hessian. We report the mixed findings openly: they do not establish persistent alignment or an advantage in end-to-end language-model training.

We believe these substantive changes significantly strengthen the manuscript, both by making its theoretical contributions easier to assess and by providing better-controlled experimental evidence and diagnostics. At the same time, we have been careful to state where the current analysis does not yet apply. We appreciate the reviewers' and Area Chair's consideration of the revised paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.