Why spectral orthogonalization helps nonnegative matrix factorization: characterizing the problem properties behind Muon's advantage

The Muon optimizer, which reshapes matrix-parameter updates by approximately orthogonalizing the momentum matrix (a Newton–Schulz approximation of its polar factor), is a leading method for training large language models, yet a controlled 2026 study finds its benefits are strongly problem-dependent: under equal hyperparameter tuning, Muon matches or loses to AdamW on unconstrained low-rank matrix factorization, and its reported gains mostly disappear on matrix completion as well, though it retains an edge on some highly ill-conditioned completion instances; on nonnegative matrix factorization (NMF) with adversarial uniform and decayed target spectra, tuned Muon is the only method to fit the target across ranks — AdamW trails by several orders of magnitude and gradient descent and sign gradient descent fail — while on a smooth Gaussian-kernel NMF target the advantage disappears and AdamW reaches the same global floor. The study offers only a hypothesis for this unexplained advantage — orthogonalized updates may discourage redundant factors and promote more diverse representations — and its experiments are limited to deterministic full-batch optimization, while its tensor-train depth sweeps change the optimization problem itself and cover only overparameterized ranks. The open problem is to identify which problem properties (the entrywise nonnegativity constraint and its projection, the target's spectral distribution, ill-conditioning, landscape geometry, overparameterization) make spectral orthogonalization advantageous; to give a theoretical or experimentally isolated account of the NMF advantage that is consistent with the observed pattern on unconstrained factorization and completion; and to determine how the advantage behaves under stochastic gradients, at matched rank, and with increasing factorization depth in a fixed loss landscape. As of August 2026, no published work beyond the source study itself explains the mechanism of Muon's NMF advantage or resolves this discrepancy.

Background

The Muon optimizer, introduced by Keller Jordan in 2024 as an open-source method for the hidden layers of neural networks, applies momentum to a matrix-shaped gradient and then replaces the momentum matrix by an approximately orthogonalized version of itself: if the momentum has singular value decomposition $U\Sigma V^\top$, the update direction is (up to scale) the orthogonal factor $UV^\top$ of its polar decomposition, computed by a small fixed number of Newton–Schulz polynomial iterations rather than an explicit singular value decomposition. Bernstein and Newhouse (2024) interpreted such updates as steepest descent under the spectral norm (the matrix norm induced by Euclidean vector norms, $\|M\|_{\mathrm{op}}=\sigma_1(M)$, the largest singular value), and Muon has since been reported to outperform AdamW — the per-coordinate adaptive method that is the default optimizer for large language models — in LLM pretraining, motivating a rapidly growing theoretical literature.

A natural laboratory for isolating what spectral orthogonalization actually buys is low-rank matrix factorization: recovering a rank-$r$ target $M^\star\in\mathbb{R}^{d_1\times d_2}$ through the factored parameterization $\hat M = UV^\top$ by minimizing $\frac12\|UV^\top - M^\star\|_F^2$, where $\|\cdot\|_F$ is the Frobenius (entrywise Euclidean) norm. The problem is nonconvex in the factors but has an explicitly known spectral structure — its curvature is governed by the singular values of $M^\star$, and the ratio of the largest to smallest nonzero singular value, the condition number, controls the difficulty of first-order optimization. Standard variants include matrix completion, in which only a subset of entries of $M^\star$ is observed and the loss is taken over those entries only, and nonnegative matrix factorization (NMF), in which both factors are constrained entrywise to the nonnegative orthant and each optimizer step is followed by the Euclidean projection $\max(X,0)$ applied entrywise; NMF is the classical model for parts-based representations of nonnegative data. Overparameterization refers to choosing the search rank $k$ larger than the target's true rank $r$.

Three recent theory papers analyze Muon-style updates on the unconstrained problem. Ma, Huang, Chi and Chen (2026) prove that a simplified Muon converges linearly on unconstrained matrix factorization with iteration complexity independent of the condition number, provably outperforming gradient descent and Adam. Rhee, Simon and Karkada (2026) show that Muon learns all top modes of $M^\star$ at equal rates — avoiding the saddle-to-saddle dynamics of gradient descent from small initialization, in which one singular mode is learned at a time with long stalls near saddle points — remains stable at learning rates above the threshold set by local loss sharpness, and converges to balanced solutions with equalized factor scales. Kang, Yun, Shin, Cho and Yun (2026) prove equal-rate singular-value growth and global convergence for spectral gradient flow in a LoRA-style factorization (LoRA, low-rank adaptation, parameterizes weight updates as a product of two low-rank factors). Qi, Chen, Ye, He and Xiao (2026) empirically find, consistent with these works' idealized settings being delicate, that the Muon update does not consistently outperform Adam across controlled spectral transformations.

Parviz, Mishne and Cloninger (2026) — the source of this problem — benchmark Muon against equally tuned AdamW, gradient descent, and sign gradient descent (which replaces each entry of the gradient by its sign) on five matrix-recovery problems under a disciplined protocol: dense learning-rate grids, three random seeds, an identical patience-based learning-rate decay schedule, and normalized mean-squared error as the metric. Their central empirical finding is a problem-dependent picture. On symmetric and general low-rank factorization, Muon's reported gains disappear under equal tuning, with AdamW and gradient descent matching or exceeding it; on matrix completion, Muon and AdamW are comparable overall, with Muon retaining an advantage on some highly ill-conditioned completion instances. On severely ill-conditioned tensor-train factorizations (chains of factor cores contracted into a matrix), Muon helps. And on NMF across uniform and decayed target spectra and ranks 10–100, tuned Muon is the only method to fit the target across ranks — AdamW trails by several orders of magnitude and gradient descent and sign gradient descent fail — whereas on a smooth Gaussian-kernel NMF target factorized at a principled bottleneck rank, tuned AdamW converges to the same global floor and the advantage disappears. The paper offers only a hypothesis for this NMF advantage — orthogonalized updates may discourage redundant factors and promote more diverse representations — and explicitly notes two limitations of its depth experiments: increasing tensor-train depth changes the optimization problem itself, so the observed trends confound optimizer comparison with task difficulty, and the results cover only the overparameterized regime. All of its experiments are deterministic and full-batch; mini-batch (stochastic) gradients, ubiquitous in deep learning, are never considered.

Problem Statement

Identify and rigorously establish the mechanism by which Muon's spectral orthogonalization produces an optimization advantage on nonnegative matrix factorization (NMF) with adversarial uniform and decayed target spectra, while providing no comparable advantage overall on unconstrained low-rank matrix factorization or matrix completion and the advantage itself disappears on a smooth Gaussian-kernel NMF target, under equal hyperparameter tuning, in the controlled framework of Parviz, Mishne and Cloninger (2026). Concretely, an answer should address the following linked aspects of one overarching objective — a predictive characterization of when and why spectrum-aware orthogonalized updates help in controlled low-rank recovery problems, with the NMF advantage as its central unexplained instance. Aspects 1 and 2 together constitute the required resolution; aspect 3's three axes are optional extensions of the characterization:

1. Characterize the responsible problem properties. Determine which property or combination of properties — the entrywise nonnegativity constraint and its projection step, the spectral distribution of the target matrix, ill-conditioning, the geometry of the NMF loss landscape, or overparameterization — is causally responsible for the advantage, and establish or refute the source paper's hypothesis that orthogonalized updates discourage redundant factors and promote more diverse factor representations in NMF. Because the source paper states this hypothesis only informally, the verdict must fix and state explicitly which formalization of factor redundancy and factor diversity it assesses.

2. Explain the discrepancy. Provide a theoretical account or a controlled experimental isolation that predicts when spectral orthogonalization beats equally tuned adaptive methods and when it does not, consistent with the observed pattern across NMF, unconstrained factorization, and matrix completion.

3. Extend the characterization across the framework's untested axes. Determine whether and how the advantage behaves under mini-batch stochastic gradients (the source experiments are entirely deterministic and full-batch), as factorization depth increases within a fixed loss landscape (a depth-varying parameterization that leaves the end-to-end objective unchanged, in contrast to the source paper's depth sweeps, which change the problem), and outside the overparameterized rank regime (at search ranks matched to or below the target's rank; the source's matched- and under-parameterized rank sweeps cover its unconstrained factorization, completion, and tensor-train problems, but the NMF advantage has not been tested at those ranks).

Aspect 1 is a component of the resolution rather than a separate deliverable: it fixes which problem properties or combination of properties are causally responsible (including an establish-or-refute verdict on the source paper's hypothesis that orthogonalized updates discourage redundant factors), and aspect 2 is resolved when those properties yield a predictive account of when spectral orthogonalization beats equally tuned adaptive methods and when it does not, consistent with the observed pattern across NMF, unconstrained factorization, and matrix completion. The three axes of aspect 3 — mini-batch stochastic gradients, depth within a fixed loss landscape, and matched or under-parameterized rank — are extensions that an answer need not cover to resolve the task, provided it states which parts of the characterization remain open.

Nonnegative factorization instances in which the reported advantage disappears are already documented in the source paper itself (its Gaussian-kernel NMF experiment); what remains open is not a further demonstration of such a disappearance but the identification of the mechanism and of the problem properties that predict the boundary of the phenomenon.

References

1. Ali Parviz, Gal Mishne, Alex Cloninger. Reassessing Muon for Matrix Factorization. arXiv:2607.13246, DOI:10.48550/arxiv.2607.13246 (2026). https://arxiv.org/abs/2607.13246
2. Keller Jordan. Muon: An optimizer for hidden layers in neural networks. Open-source release and blog post (2024). https://kellerjordan.github.io/posts/muon/ (code repository: https://github.com/KellerJordan/Muon)
3. Jeremy Bernstein, Laker Newhouse. Old Optimizer, New Norm: An Anthology. arXiv:2409.20325 (2024). https://arxiv.org/abs/2409.20325
4. Jianhao Ma, Yu Huang, Yuejie Chi, Yuxin Chen. Preconditioning Benefits of Spectral Orthogonalization in Muon. arXiv:2601.13474 (2026). https://arxiv.org/abs/2601.13474
5. Mark Rhee, Jamie Simon, Dhruva Karkada. Muon learns balanced solutions in matrix factorization without slow saddle-to-saddle dynamics. arXiv:2606.30509 (2026). https://arxiv.org/abs/2606.30509
6. Changmin Kang, Jihun Yun, Baekrok Shin, Yeseul Cho, Chulhee Yun. Uniform Spectral Growth and Convergence of Muon in LoRA-Style Matrix Factorization. arXiv:2602.06385 (2026). https://arxiv.org/abs/2602.06385
7. Xianbiao Qi, Marco Chen, Jiaquan Ye, Yelin He, Rong Xiao. Delving into Muon and Beyond: Deep Analysis and Extensions. arXiv:2602.04669 (2026). https://arxiv.org/abs/2602.04669
8. Konstantinos Oikonomidis, Jan Quan, Kimon Antonakopoulos, Antonio Silveti-Falls, Volkan Cevher, Panagiotis Patrinos. Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives. arXiv:2605.11850 (2026). https://arxiv.org/abs/2605.11850
9. Thang Do, Steffen Dereich, Arnulf Jentzen. On MUON optimization: From non-convergence to an error analysis with Polar Express and the Newton-Schulz polynomial from implementations. arXiv:2608.04607 (2026). https://arxiv.org/abs/2608.04607
10. Elliot Paquette, Noah Marshall, Lucas Benigni, Guangyuan Wang, Atish Agarwala, Courtney Paquette. Phases of Muon: When Muon Eclipses SignSGD. arXiv:2605.09552 (2026). https://arxiv.org/abs/2605.09552
11. Zakhar Shumaylov, Nathaël Da Costa, Peter Zaika, Bálint Mucsányi, Alex Massucco, Yoav Gelberg, Carola-Bibiane Schönlieb, Yarin Gal, Philipp Hennig. Muon is Not That Special: Random or Inverted Spectra Work Just as Well. arXiv:2605.11181 (2026). https://arxiv.org/abs/2605.11181
12. Florian Hübler, Thomas Pethick, Suvrit Sra. Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success. arXiv:2606.14560 (2026). https://arxiv.org/abs/2606.14560
13. Yufeng Wang. The Active Ingredient in Muon's Grokking. arXiv:2607.20512 (2026). https://arxiv.org/abs/2607.20512