Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization

Amartya Roy; Souvik Chakraborty

cs.LGOct 2, 2026

Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization

Authors: Amartya Roy, Souvik Chakraborty

Organizations: The School of Interdisciplinary Research Indian Institute of Technology Delhi, India · Robert Bosch GmbH, India · Department of Applied Mechanics Indian Institute of Technology Delhi, India · Yardi School of Artificial Intelligence (ScAI) Indian Institute of Technology Delhi, India

Abstract

Existing convergence analyses of Muon either assume exact orthogonalization or analyze classical Newton--Schulz polynomials, and guarantee only stationarity, so it is unresolved what Muon's five tuned Newton--Schulz steps preserve and whether that suffices to reach a prescribed neural-network training loss. We establish a finite-time training guarantee that accounts for both momentum accumulation before orthogonalization and the tuned finite-step update. For full-batch training of a sufficiently wide two-layer ReLU network with fixed random output weights and a positive-definite limiting neural tangent kernel, we prove that Muon reaches any target empirical squared loss $\varepsilon>0$ with high probability over initialization. For every momentum parameter $μ\in[0,1)$ , a target-dependent constant learning rate proportional to $(1-μ)\sqrt{\varepsilon}$ yields a hitting-time bound of $O((1-μ)^{-1}\varepsilon^{-1/2})$ , with other problem parameters fixed. The sufficient width is independent of both target accuracy and momentum. The analysis shows that the tuned Newton--Schulz map preserves alignment with the momentum buffer while bounding the update's spectral norm. Control of gradient variation near initialization transfers this alignment to the current gradient, ensuring descent until the target is reached without requiring exact orthogonalization. Numerical experiments support these mechanisms at widths below the sufficient theoretical threshold: gradient-update alignment remains above the analytical reference, and all 30 runs across six widths and five student initializations on a fixed teacher-student dataset reach the target loss while maintaining kernel positivity.

Figures & tables

Figure 1: Training loss across accuracy targets and momentum values. (a) Loss curves for five target values of

\varepsilon

\mu=0.95

; dots mark the first iteration reaching each target. (b) Hitting time versus

\varepsilon

, with an

\varepsilon^{-1/2}

reference line. (c) Loss curves for five momentum values at target

10^{-2}

, using

\eta=(1-\mu)\eta_{0}

with

\eta_{0}=1.54\times 10^{-4}

. (d) The curves in (c) plotted against

(1-\mu)t

. Panels (a,b) use a separate data draw (

\lambda_{0}\approx 0.34

R_{0}\approx 26

); panels (c,d) use the saved draw (

\lambda_{0}=0.335

R_{0}=30.2

Figure 2: Gradient alignment and momentum discrepancy. Both panels plot iteration

t

(logarithmic axis) for five momentum values

\mu

, each run until it first reaches the target

10^{-2}

. (a) Alignment

A_{t}=\langle G_{t},O_{t}\rangle/\|G_{t}\|_{F}

between the gradient and the update; the dashed line is the reference

\kappa/2=1/3

. (b) Buffer discrepancy

D_{t}=\|B_{t}/s_{t}-G_{t}\|_{F}/\|G_{t}\|_{F}

, which is identically zero at

\mu=0

Figure 3: Training success and kernel stability across widths. (a) Target attainment within

1{,}414{,}000

updates; (b) minimum

K_{t}

, with reference

1/2

; (c) maximum

S_{t}

. Points and bars show mean

\pm 1

sample standard deviation over five seeds per width, measured through target attainment.

Figure 4: Finite maps on shared training buffers. Left to right: buffer alignment

a

, spectral norm

s

, and normalized alignment per spectral norm

q

. Points are

59

saved buffers from student seed

10

; black ticks mark medians. Dashed references are

2/3

5/4

, and the polar optimum

1

, respectively. Classical NS5 uses the cubic recurrence.

Figure 5: Movement within the analytical radius. Maximum

\|W_{t}-W_{0}\|_{F}/R_{\mathbb{B}}

up to target attainment, with

R_{\mathbb{B}}

from ( 17 ). Points show five seeds per width; the line and bars show their mean and

\pm 1

sample standard deviation. The dashed line is the ball boundary.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Reference	Guarantee	Width
Du et al. [10]	$L(W_{T})\to 0$ , linear	$\Omega(n^{6}/(\lambda_{0}^{4}\delta^{3}))$
Arora et al. [2]	$L(W_{T})\leq\varepsilon$	$\Omega(n^{7}/(\lambda_{0}^{4}\nu^{2}\delta^{4}\varepsilon^{2}))$
Ji & Telgarsky [11]	test error $\leq\varepsilon$	$\operatorname{polylog}(1/\varepsilon)$
Du et al. [9]	$L(W_{T})\to 0$ , linear	– ( $\operatorname{poly}(n)$ )
Zou & Gu [20]	$L(W_{T})\to 0$ , faster	$<$ Allen-Zhu et al.
Li & Liang [14]	pop. risk $\to 0$	margin-dependent

Appendix

Table 1: Non-asymptotic guarantees for wide-network training and Muon. The first eight rows follow the raw gradient: GD for the first five and SGD for the next three. Networks have depth

2

except in Du et al. [9] , Zou & Gu [20] , Allen-Zhu et al. [1] , Cao & Gu [5] , which allow depth

>2

. The last three rows use momentum followed by, respectively, the exact polar factor, classical Newton–Schulz (NS), and five tuned NS steps. The two prior Muon results concern general

L

-smooth objectives. Population-risk and stationarity guarantees are not directly comparable to training-loss guarantees. A dash denotes an unstated explicit bound. For Arora et al. [2] ,

\nu=O(\varepsilon\delta/\sqrt{n})

is the initialization scale. For our row,

\alpha

and

\|y\|_{2}^{2}/n

are treated as constants and

T=\mathcal{O}\bigl(n^{3/2}/((1-\mu)\lambda_{0}\sqrt{\delta\varepsilon})\bigr)

Setting	Value or status
Default data and student	$n=20$ , $d=100$ , $m=1000$ , $\alpha=1$
Budget parameter	$\delta=0.05$
Accuracy panels	$\varepsilon\in\{10^{-1},10^{-2},10^{-3},10^{-4},10^{-5}\}$ ; $\mu=0.95$ ; separate draw with $R_{0}\approx 26$
Displayed momentum values	$\mu\in\{0,0.5,0.9,0.95,0.99\}$
Fixed-step comparison	Target $10^{-2}$ ; shared step $\eta=\eta_{0}=1.54\times 10^{-4}$ ; horizon $50{,}000$
Teacher specification	Width $1000$ , output weights $\pm 1$ , seed $1$ , labels scaled by $m^{-1/2}$

Appendix

Table 2: Experimental settings for the diagnostics in this appendix and in Section 5 . Learning rates use the measured constants of the frozen draw,

\lambda_{0}=0.335

and

R_{0}=30.2

. Horizons are the iteration caps actually used, not the theoretical budget.

Muon Optimizer

Muon optimizer uses momentum and matrix orthogonalization to shape neural-network updates, especially in large language-model training.

See all 143 papers

May 13, 2026

Spectral Flattening Is All Muon Needs: How Orthogonalization Controls Learning Rate and Convergence

Muon orthogonalizes the momentum buffer before each update, replacing its singular values with ones via Newton-Schulz iterations. This simple change lets Muon tolerate far larger learning rates and converge faster than other optimizers, but why? We show that the mechanism is spectral flattening, and develop two results around it. First, we prove that Muon's maximal stable step size scales with the average singular value of the gradient rather than the largest, which bottlenecks standard gradient descent. Second, we recast Muon as a preconditioned gradient method and show, under a Kronecker-factored curvature model, that it improves the effective convergence factor, with the improvement controlled by the spectrum of the gradient covariance. Extensive experiments validate both results: Muon remains stable at learning rates that cause SGD to diverge within the first few iterations, and reaches accuracy milestones several epochs earlier even at identical step sizes. Taken together, our results offer a principled, geometric explanation for Muon's empirical success.

Tien-Phat Nguyen, Truong Nguyen, Minh-Phuc Truong +3

Hanoi University of Science and Technology Hanoi, Vietnam · Indiana University 107 S. Indiana Ave, Bloomington, IN 47405, USA · Monash University Clayton, VIC 3800, Australia

Momentum Methods Gradient Descent Muon Optimizer Spectral Methods Stochastic Gradient Descent

Ask PDF

Sep 30, 2026

Convergence of Practical Muon with Finite Newton-Schulz Iterations and Nesterov Momentum

Practical Muon maintains momentum and performs a small, fixed number of Newton--Schulz iterations separately for each parameter matrix, often with a Nesterov correction. We analyze these layer-wise finite-step updates jointly on a coupled nonconvex objective, rather than replacing them by exact polar factors or one global orthogonalization. Under gradient-dependent

(\mathcal L_0,\mathcal L_1,q)

-smoothness and conditionally unbiased stochastic gradients with bounded layer-wise variance, we establish an

\mathcal O(T^{-1/4})

bound on the expected average Frobenius gradient norm. The analysis retains the Nesterov recursion and requires neither bounded stochastic gradients, symmetric noise, nor a uniform positive lower bound on the nonzero output singular values. Its constants contain no explicit matrix-dimension or rank factors when the number of blocks and problem constants are fixed. The proof follows a descent inequality and a decomposition of the momentum tracking error into initialization, noise, and drift. For the original five-step quintic, we verify the required scalar-map bounds analytically; the result also allows step-dependent coefficients satisfying the same bounds. A complementary nuclear-norm result quantifies rank dependence under a stronger spectral condition. The vanishing rate uses coupled learning-rate and momentum schedules, including the standard single-coefficient Nesterov rule.

Hanyng Peng, Hui Wang, Yue Yu

Pengcheng Laboratory, Shenzhen, China

Newton-Schulz Iteration Gradient Descent Nonconvex Stochastic Optimization Muon Optimizer Stochastic Optimization Convergence

Ask PDF

Sep 24, 2026

Convergence guarantees for Muon: New parameter regimes and generalizations

In this paper, we establish the first asymptotic convergence guarantees for the Muon algorithm through a more accurate proxy for the Newton-Schultz iteration than the typical matrix sign function. We prove that, for appropriate choices of hyperparameters, the iterates satisfy

\lim_{k\to\infty}\|\nabla f(x_k)\|=0

, and, under a global Polyak-Łojasiewicz condition, that the sequence of function values converges linearly. The key insight is that the regularization, implicit in Muon's Newton-Schulz implementation, induces a bounded preconditioner, exposing Muon as a preconditioned Polyak heavy-ball method and enabling a classical Lyapunov analysis. This observation naturally motivates applying the same preconditioning structure to the Nesterov gradient evaluation. We formalize this idea by introducing Muesterov, a Nesterov-based variant of Muon, and prove that it enjoys the same convergence guarantees, extending the theoretical framework beyond the heavy-ball setting. Numerical experiments on a scalar cross-entropy problem corroborate the theory and illuminate the joint role of the learning rate and the Newton-Schulz regularizer in controlling convergence. Preliminary numerical simulations training the nanoGPT dataset provide intuition regarding the relevance of the observations in this paper to practical applications.

Arthur C. B. de Oliveira, Dhruv D. Jatkar, Guilherme S. Vicinansa +1

Department of Electrical and Computer Engineering Northeastern University Boston, MA 02115 · Department of Telecommunications and Control Escola Politecnica, University of São Paulo São Paulo, SP 05508-010

Muon Optimizer Optimization Convergence Analysis Accelerated Gradient Methods

Ask PDF

Abstract

Muon Optimizer

Explore similar work

Spectral Flattening Is All Muon Needs: How Orthogonalization Controls Learning Rate and Convergence

Convergence of Practical Muon with Finite Newton-Schulz Iterations and Nesterov Momentum

Convergence guarantees for Muon: New parameter regimes and generalizations