Paper deep dive
Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization
Amartya Roy, Souvik Chakraborty
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\mu\in[0,1)$, a target-dependent constant learning rate proportional to $(1-\mu)\sqrt{\varepsilon}$ yields a hitting-time bound of $O((1-\mu)^{-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.
Tags
Links
- Source: https://arxiv.org/abs/2610.03306v1
- Canonical: https://arxiv.org/abs/2610.03306v1
Trouble viewing inline? Open PDF directly →
Full Text
84,321 characters extracted from source content.
Expand or collapse full text
Training-Loss Guarantees for Muon with Finite-Step Newton–Schulz Orthogonalization Amartya Roy Affiliation: The School of Interdisciplinary Research Affiliation: Indian Institute of Technology Delhi, India Affiliation: Robert Bosch GmbH, India Email: srz248670@iitd.ac.in Souvik Chakraborty Affiliation: Department of Applied Mechanics Affiliation: Indian Institute of Technology Delhi, India Affiliation: Yardi School of Artificial Intelligence (ScAI) Affiliation: Indian Institute of Technology Delhi, India Email: souvik@am.iitd.ac.in 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 ε>0 >0 with high probability over initialization. For every momentum parameter μ∈[0,1)μ∈[0,1), a target-dependent constant learning rate proportional to (1−μ)ε(1-μ) yields a hitting-time bound of O((1−μ)−1ε−1/2)O((1-μ)^-1 ^-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. Keywords Muon · Newton–Schulz orthogonalization · Momentum · Neural tangent kernel · Training-loss guarantees · Optimization for deep learning. 1 Introduction How much can an optimizer alter the gradient and still provably fit the training data? Muon (MomentUm Orthogonalized by Newton–Schulz) makes this question concrete: it accumulates gradients in a momentum buffer and then reshapes the buffer’s singular values through five tuned Newton–Schulz iterations before updating the weights [12]. This approximately orthogonalized update has proved effective in large-scale language-model training [15, 18], yet the transformation complicates the connection between the direction applied to the weights and the gradient of the current loss. Momentum carries information from earlier iterates, while finite orthogonalization changes how that information enters the update. Understanding why sufficient descent survives these operations is central to establishing a training-loss guarantee. We study this question for overparameterized two-layer ReLU networks and show that Muon can reach a prescribed loss while retaining both momentum and the tuned five-step Newton–Schulz transformation. Existing analyses explain several aspects of Muon’s update, but leave a gap between its practical construction and a neural-network training-loss guarantee. The exact polar factor admits a geometric interpretation as a steepest-descent direction under a spectral-norm constraint [3, 4]. Analyses incorporating momentum establish stationarity guarantees for smooth objectives, but replace the finite Newton–Schulz map with exact orthogonalization [7, 17, 16, 6, 8]; de Oliveira et al. [8] additionally obtain linear convergence of the objective under a Polyak–Łojasiewicz condition, which is an assumption on the objective rather than a training-loss guarantee for a neural network. Kim & Oh [13] analyze finitely many Newton–Schulz iterations, but their guarantees concern classical polynomial iterations rather than the tuned coefficients used by Muon. Separately, overparameterized-network theory establishes conditions under which gradient descent reaches arbitrarily small training loss [10, 9, 2]. These results do not transfer directly to Muon: a positive-definite tangent kernel controls the gradient through the training residual, but the actual loss decrease depends on the gradient’s alignment with the transformed momentum buffer. The missing link is therefore a quantitative descent guarantee that accommodates both accumulated gradients and tuned, approximate orthogonalization. Table 1 (in the appendix) summarizes the closest results. For gradient descent on this model, Du et al. [10] reach arbitrarily small training loss at a linear rate with width Ω(n6/(λ04δ3)) (n^6/( _0^4δ^3)), and Arora et al. [2] reach loss ε with width Ω(n7/(λ04ν2δ4ε2)) (n^7/( _0^4ν^2δ^4 ^2)) at initialization scale ν=O(εδ/n)ν=O( δ/ n). The two closest Muon analyses [7, 13] guarantee only stationarity. Our result is a training-loss guarantee for Muon, with width Ω(n5/(λ04δ3)) (n^5/( _0^4δ^3)). We establish this link by identifying two properties of the finite Newton–Schulz map that suffice for a training-loss guarantee: alignment with its input and a bounded output spectral norm. For Muon’s tuned five-step map, we prove both properties uniformly over nonzero momentum buffers, without requiring proximity to the exact polar factor. The remaining challenge is to transfer alignment from the buffer to the current gradient. We show that, within a controlled neighborhood of initialization, gradient variation is sufficiently small for this transfer to hold for every momentum parameter μ∈[0,1)μ∈[0,1), with a learning rate scaled by 1−μ1-μ. A uniform neural tangent kernel argument controls the ReLU linearization error and ensures that the iterates remain in this neighborhood until the target loss is reached. Together, these estimates yield an explicit finite-time guarantee for full-batch training of a two-layer ReLU network with fixed random output weights, summarized below. Theorem (Informal statement). Consider full-batch Muon with momentum μ∈[0,1)μ∈[0,1) and five tuned Newton–Schulz iterations, training the first layer of a width-m two-layer ReLU network with fixed random output weights. Let the n training inputs have unit norm, and suppose their limiting neural tangent kernel has smallest eigenvalue λ0>0 _0>0. Treat the output-weight scale and the average squared label magnitude as constants. For any target loss ε>0 >0 and failure probability δ∈(0,1)δ∈(0,1), take m=Ω(n5λ04δ3),η=Θ((1−μ)λ0εn).m= \! ( n^5 _0^4δ^3 ), η= \! ( (1-μ) _0 n ). Then, with probability at least 1−δ1-δ over initialization, an iterate with empirical squared loss at most ε is reached within T=(n3/2(1−μ)λ0δε)T=O\! ( n^3/2(1-μ) _0 δ ) steps. The precise assumptions and constants are given in Theorem 3.1. The sufficient width is independent of both the target accuracy ε and momentum μ: a smaller target or larger momentum changes the prescribed learning rate and iteration budget without requiring a wider network. The result is a hitting-time guarantee with a target-dependent constant learning rate; it does not imply acceleration over gradient descent or a benefit from increasing momentum. By contrast, Wang et al. [19] prove that heavy-ball momentum accelerates gradient descent for training a wide ReLU network with one hidden layer; our bound scales with (1−μ)−1(1-μ)^-1 and shows no such gain. Our experiments directly examine the alignment and stability mechanisms underlying the proof. Across the tested momentum values, gradient-update alignment remains above the analytical reference. All 30 runs across six widths and five student initializations on a fixed dataset and teacher reach the target loss while maintaining kernel positivity, and kernel variation decreases with width. Comparisons on shared momentum buffers further quantify the alignment and norm properties of tuned Newton–Schulz updates relative to classical iterations and the exact polar factor. These findings support the relevance of the proof’s mechanisms at widths many orders of magnitude below the sufficient theoretical threshold (Section 5), without establishing the necessity or tightness of the bounds. 2 Problem Setup and the Muon Update For vectors, ∥⋅∥2\|·\|_2 denotes the Euclidean norm; for matrices, ∥⋅∥2\|·\|_2, ∥⋅∥F\|·\|_F, and ∥⋅∥∗\|·\|_* denote the spectral, Frobenius, and nuclear norms, respectively. We use the Frobenius inner product ⟨A,B⟩=tr(A⊤B) A,B =tr(A B) and column-wise vectorization. 2.1 Network and Training Objective Let (xi,yi)i=1n⊂ℝd×ℝ\(x_i,y_i)\_i=1^n ^d×R be fixed training data with ‖xi‖2=1\|x_i\|_2=1. We consider the width-m two-layer ReLU network f(x,W)=1m∑r=1marσ(wr⊤x),W=(w1,…,wm)∈ℝd×m,σ(z)=max0,z.f(x;W)= 1 m _r=1^ma_rσ(w_r x), W=(w_1,…,w_m) ^d× m, σ(z)= \0,z\. (1) Only the first-layer weights W are trained. For a fixed α>0α>0, the output weights are sampled independently as ar∼Unif±αa_r \±α\ and held fixed. The first-layer weights are initialized independently as wr(0)∼(0,Id)w_r(0) (0,I_d), independently of the output weights. All probability statements concern this random initialization, conditional on the training data. Write y=(y1,…,yn)⊤y=(y_1,…,y_n) , let u(W)=(f(x1,W),…,f(xn,W))⊤u(W)=(f(x_1;W),…,f(x_n;W)) , and define the residual e(W)=y−u(W)e(W)=y-u(W). The training objective is the unnormalized empirical squared loss L(W)=12‖u(W)−y‖22=12‖e(W)‖22.L(W)= 12\|u(W)-y\|_2^2= 12\|e(W)\|_2^2. (2) We adopt the derivative convention σ′(z)=z≥0σ (z)= 1\z≥ 0\, including at z=0z=0. The resulting selected gradient G(W)∈ℝd×mG(W) ^d× m has columns [G(W)]⋅,r=−arm∑i=1ne(W)i 1wr⊤xi≥0xi.[G(W)]_·,r=- a_r m _i=1^ne(W)_i\, 1\w_r x_i≥ 0\\,x_i. (3) Our objective is to bound the number of full-batch Muon updates required to reach L(W)≤εL(W)≤ for a prescribed ε>0 >0. 2.2 Momentum and the Newton–Schulz Update Muon constructs each update by applying a finite Newton–Schulz map to a momentum buffer. For a nonzero matrix B∈ℝd×mB ^d× m, initialize X0=B/‖B‖FX_0=B/\|B\|_F and perform Xk+1=pk(XkXk⊤)Xk,k=0,…,K−1,X_k+1=p_k(X_kX_k )X_k, k=0,…,K-1, (4) where pkp_k is a polynomial. Define NSK(B)=XKNS_K(B)=X_K and NSK(0)=0NS_K(0)=0. Muon uses K=5K=5 with the same tuned polynomial at every step [12]: pk(s)=3.4445−4.7750s+2.0315s2,k=0,…,4.p_k(s)=3.4445-4.7750s+2.0315s^2, k=0,…,4. (5) This map transforms the singular values of the normalized buffer while retaining its singular-vector directions. It does not, in general, return the exact polar factor. We formulate the analysis for general polynomial schedules and specialize the resulting bounds to Muon’s tuned map. Algorithm 1 specifies the full-batch trajectory. Momentum is accumulated before the Newton–Schulz transformation; orthogonalizing individual gradients and then averaging them would define a different update. Algorithm 1 Full-batch Muon 1: Initial weights W0W_0, learning rate η>0η>0, momentum μ∈[0,1)μ∈[0,1), target loss ε>0 >0, iteration budget T 2: B0←0B_0← 0 3: for t=1,…,Tt=1,…,T do 4: if L(Wt−1)≤εL(W_t-1)≤ then 5: return Wt−1W_t-1 6: end if 7: Gt←G(Wt−1)G_t← G(W_t-1) 8: Bt←μBt−1+GtB_t←μ B_t-1+G_t 9: Ot←NS5(Bt)O_t _5(B_t) 10: Wt←Wt−1−ηOtW_t← W_t-1-η O_t 11: end for 12: return WTW_T We write ut=u(Wt)u_t=u(W_t) and et=e(Wt)e_t=e(W_t). Reaching the target loss is equivalent to ‖et‖2≤2ε\|e_t\|_2≤ 2 . The analysis concerns the exact-arithmetic Newton–Schulz map; finite-precision effects and denominator regularization used in numerical implementations are outside its scope. 2.3 Kernel and Update Conditions The network Jacobian J(W)∈ℝn×dmJ(W) ^n× dm, defined using the derivative convention above, has blocks [J(W)]i,(r−1)d+1:rd=armwr⊤xi≥0xi⊤.[J(W)]_i,(r-1)d+1:rd= a_r m 1\w_r x_i≥ 0\\,x_i . (6) Consequently, vec(G(W))=−J(W)⊤e(W)vec(G(W))=-J(W) e(W). Define the empirical neural tangent kernel as H(W)=J(W)J(W)⊤H(W)=J(W)J(W) . Under the specified initialization, its expectation is [H(W0)]=α2H∞E[H(W_0)]=α^2H^∞, where Hij∞=xi⊤xjπ−arccos(xi⊤xj)2π.H^∞_ij=x_i x_j\, π- (x_i x_j)2π. (7) We assume that this normalized limiting kernel is positive definite: λ0:=λmin(H∞)>0. _0:= _ (H^∞)>0. (8) Since Hii∞=1/2H^∞_i=1/2, necessarily λ0≤1/2 _0≤ 1/2. Kernel positivity relates the gradient magnitude to the residual through ‖G(W)‖F2=e(W)⊤H(W)e(W)\|G(W)\|_F^2=e(W) H(W)e(W). For Muon, turning this relation into loss decrease also requires control of the transformed momentum update. To describe that transformation, define ϕk(x)=xpk(x2) _k(x)=x\,p_k(x^2). The Newton–Schulz recurrence acts on the normalized singular values through Φ=ϕK−1∘⋯∘ϕ0. = _K-1 ·s _0. (9) In particular, if B=UΣV⊤B=U V is a compact singular value decomposition of a nonzero buffer, then NSK(B)=UΦ(Σ‖B‖F)V⊤,NS_K(B)=U\, \! ( \|B\|_F )V , where Φ acts entrywise on the diagonal. Assumption 1 (Newton–Schulz schedule). There exist constants κ>0κ>0 and M>0M>0 such that κx≤Φ(x)≤Mfor all x∈[0,1].κ x≤ (x)≤ M all x∈[0,1]. (10) Taking x=1x=1 in (10) gives κ≤Φ(1)≤Mκ≤ (1)≤ M; we use κ≤Mκ≤ M throughout. The constant κ controls alignment with the input buffer, while M bounds the update’s spectral norm. Indeed, for every nonzero B, ⟨B,NSK(B)⟩≥κ‖B‖F,‖NSK(B)‖2≤M. B,NS_K(B) ≥κ\|B\|_F, \|NS_K(B)\|_2≤ M. These conditions do not require the transformed singular values to be close to one. Proposition 1 establishes their validity for Muon’s tuned five-step map. The next section uses these bounds together with kernel stability to transfer alignment from the momentum buffer to the current gradient and establish the training guarantee. 3 Finite-Time Training Guarantee We establish a training-loss guarantee for any Newton–Schulz schedule satisfying Assumption 1, including Muon’s tuned five-step map. Starting from B0=0B_0=0, consider Gt=G(Wt−1),Bt=μBt−1+Gt,Ot=NSK(Bt),Wt=Wt−1−ηOt.G_t=G(W_t-1), B_t=μ B_t-1+G_t, O_t=NS_K(B_t), W_t=W_t-1-η O_t. (11) For δ∈(0,1)δ∈(0,1), define the initial-residual bound R0:=3(‖y‖22+nα2/2)δ.R_0:= 3(\|y\|_2^2+nα^2/2)δ. (12) Theorem 3.1 (Finite-time training guarantee). Consider the model and initialization of Section 2, and suppose Assumption 1 holds with constants κ and M. Fix ε>0 >0, δ∈(0,1)δ∈(0,1), and μ∈[0,1)μ∈[0,1). If m≥5⋅1012(Mκ)8n4λ04δ3(n+‖y‖22α2),m≥ 5· 10^12 ( Mκ )^8 n^4 _0^4δ^3 (n+ \|y\|_2^2α^2 ), (13) run (11) with η η =(1−μ)κλ0ε8M2nα, =(1-μ) κ _0 8M^2nα, (14) T T =⌈128M2nR0(1−μ)κ2λ0ε⌉. = 128M^2nR_0(1-μ)κ^2 _0 . (15) Then, with probability at least 1−δ1-δ over initialization, min0≤t≤TL(Wt)≤ε. _0≤ t≤ TL(W_t)≤ . (16) Thus, stopping at the first iterate with loss at most ε requires no more than T updates. For Muon’s tuned coefficients, Proposition 1 permits κ=2/3κ=2/3 and M=5/4M=5/4. The sufficient width is independent of both ε and μ, whereas the learning rate and iteration budget depend explicitly on them. The result is a target-dependent hitting-time guarantee; it does not assert convergence to zero under one fixed learning rate. The proof is given in Section 4. Scope: what is specific to Muon. The theorem uses the Newton–Schulz map only through κ and M. It therefore also covers K=0K=0, where NS0(B)=B/‖B‖FNS_0(B)=B/\|B\|_F and Φ(x)=x (x)=x: Frobenius-normalized momentum gradient descent satisfies Assumption 1 with κ=M=1κ=M=1. What is specific to Muon is that its tuned five-step map satisfies the assumption, with κ=2/3κ=2/3 and M=5/4M=5/4, without its transformed singular values being close to one, that is, without approximating the polar factor. Why ε−1/2 ^-1/2. Since ⟨Bt,Ot⟩≤‖Bt‖F‖Ot‖F B_t,O_t ≤\|B_t\|_F\|O_t\|_F, the alignment bound gives ‖Ot‖F≥κ\|O_t\|_F≥κ whenever Bt≠0B_t≠ 0: the update does not shrink with the gradient. With a fixed η, the descent inequality (20) then certifies progress only down to a residual of order η, because of its term nM2α2η2nM^2α^2η^2. Reaching loss ε therefore requires η∝εη , and the iteration count scales as 1/η1/η. Gradient descent differs because its steps shrink with the gradient, which gives a linear rate with a constant step size [10]. 3.1 Stability Near Initialization The analysis controls the trajectory within :=W:‖W−W0‖F≤18MnR0καλ0.B:= \W:\|W-W_0\|_F≤ 18M n\,R_0κα _0 \. (17) Under (13), Lemma B.1 establishes an event ℰE of probability at least 1−δ1-δ controlling the initial residual, kernel concentration, and the number of neuron–input pairs near an activation boundary. On this event, Lemma B.2 gives, uniformly for W,V∈W,V , λmin(H(W))≥α2λ02,‖u(V)−u(W)−J(W)vec(V−W)‖2≤καλ018M‖V−W‖2. _ (H(W))≥ α^2 _02, \|u(V)-u(W)-J(W)vec(V-W)\|_2≤ κα _018M\|V-W\|_2. The full statements and proofs appear in Appendices B.1 and B.2. Kernel positivity relates the gradient magnitude to the residual, while the spectral-norm remainder bound controls the prediction error produced by an update. The trajectory containment argument uses the update norm and total iteration budget, without first assuming loss decrease. 3.2 From Momentum Alignment to Descent By (3), every gradient and momentum buffer has its column space in spanx1,…,xnspan\x_1,…,x_n\. The Newton–Schulz conditions therefore yield ⟨Bt,Ot⟩≥κ‖Bt‖F,‖Ot‖2≤M,‖Ot‖F≤Mn. B_t,O_t ≥κ\|B_t\|_F, \|O_t\|_2≤ M, \|O_t\|_F≤ M n. (18) The Frobenius bound follows from the rank bound rank(Bt)≤nrank(B_t)≤ n; the complete statement is Lemma B.3 in Appendix B.3. These bounds control alignment with the buffer. The central step transfers that alignment to the current gradient. Lemma 3.2 (Gradient-update alignment). Assume ℰE, let W0,…,Wt−1∈W_0,…,W_t-1 , and suppose ‖et−1‖2>2ε\|e_t-1\|_2> 2 . If η≤(1−μ)κλ0ε8M2nα,η≤(1-μ) κ _0 8M^2nα, then ⟨Gt,Ot⟩≥κ2‖Gt‖F. G_t,O_t ≥ κ2\|G_t\|_F. (19) The proof controls the discrepancy between the normalized momentum buffer and the current gradient using the stability estimates within B; see Appendix B.5. The learning-rate factor 1−μ1-μ compensates for the accumulation of older gradients. Lemma 3.3 (One-step residual decrease). Assume ℰE, let Wt−1,Wt∈W_t-1,W_t , and suppose (19) holds. Then ‖et‖22≤‖et−1‖22−καηλ04‖et−1‖2+nM2α2η2.\|e_t\|_2^2≤\|e_t-1\|_2^2- καη _04\|e_t-1\|_2+nM^2α^2η^2. (20) If, additionally, η≤κλ0‖et−1‖28M2nα,η≤ κ _0\|e_t-1\|_28M^2nα, (21) then ‖et‖2≤‖et−1‖2−καηλ016.\|e_t\|_2≤\|e_t-1\|_2- καη _016. (22) The proof appears in Appendix B.4. The prescribed learning rate satisfies (21) whenever L(Wt−1)>εL(W_t-1)> . Thus, containment in B and gradient-update alignment yield a fixed decrease in residual norm until the target is reached; summing this decrease gives the budget in (15). The exact polar factor maximizes buffer alignment per unit spectral norm (Proposition 3 in the appendix). Our guarantee requires only the bounds in (18), which the tuned finite-step map satisfies without needing to approximate the polar factor closely. 4 Proof of the Finite-Time Guarantee The proof first establishes trajectory containment using only the update norm and iteration budget. This makes the uniform kernel bounds available without assuming loss decrease. Gradient-update alignment then yields a fixed residual decrease until the target is reached. Proof of Theorem 3.1. By Lemma B.1, the event ℰE has probability at least 1−δ1-δ. Fix an initialization in ℰE, so that ‖e0‖2≤R0\|e_0\|_2≤ R_0. If R0≤2εR_0≤ 2 , the initial iterate already satisfies the conclusion. Hence assume R0>2εR_0> 2 . Trajectory containment. Every momentum buffer has its column space in spanx1,…,xnspan\x_1,…,x_n\. Thus, Lemma B.3 gives ‖Wt−Wt−1‖F=η‖Ot‖F≤ηMn.\|W_t-W_t-1\|_F=η\|O_t\|_F≤η M n. (23) Using ⌈z⌉≤z+1 z ≤ z+1 and the prescribed learning rate and budget, Tη≤16R0καλ0+η≤17R0καλ0.Tη≤ 16R_0κα _0+η≤ 17R_0κα _0. (24) For the last inequality, observe that ηκαλ0=(1−μ)κ2λ0ε8M2n≤ε16<R0,ηκα _0= (1-μ)κ^2 _0 8M^2n≤ 16<R_0, where κ≤Mκ≤ M, λ0≤1/2 _0≤ 1/2, and n≥1n≥ 1. Consequently, for every 0≤t≤T0≤ t≤ T, ‖Wt−W0‖F≤tηMn≤17MnR0καλ0<18MnR0καλ0.\|W_t-W_0\|_F≤ tη M n≤ 17M n\,R_0κα _0< 18M n\,R_0κα _0. (25) Thus W0,…,WT∈W_0,…,W_T , and Lemma B.2 applies throughout the budget. Descent until the target is reached. Suppose, for contradiction, that ‖et‖2>2εfor every 0≤t≤T.\|e_t\|_2> 2 every 0≤ t≤ T. (26) For each 1≤t≤T1≤ t≤ T, trajectory containment and the prescribed learning rate allow us to apply Lemma 3.2, yielding ⟨Gt,Ot⟩≥(κ/2)‖Gt‖F G_t,O_t ≥(κ/2)\|G_t\|_F. Moreover, η≤κλ0ε8M2nα<κλ0‖et−1‖28M2nα.η≤ κ _0 8M^2nα< κ _0\|e_t-1\|_28M^2nα. Hence Lemma 3.3 gives ‖et‖2≤‖et−1‖2−καηλ016.\|e_t\|_2≤\|e_t-1\|_2- καη _016. (27) Summing over the budget and substituting (14) yields ‖eT‖2 \|e_T\|_2 ≤R0−Tκαηλ016 ≤ R_0-T καη _016 =R0−T(1−μ)κ2λ0ε128M2n≤0, =R_0-T (1-μ)κ^2 _0 128M^2n≤ 0, (28) where the last inequality follows from (15). This contradicts (26). Therefore some t≤Tt≤ T satisfies L(Wt)≤εL(W_t)≤ . Since the argument holds on ℰE, the conclusion has probability at least 1−δ1-δ. ∎ 5 Numerical Evaluation of the Theory We examine the accuracy and momentum dependence of the training dynamics, gradient-update alignment, and kernel stability across widths. The experiments use widths far below the sufficient condition in Theorem 3.1: for our dataset, (13) requires m≳2×1027m 2× 10^27 and (15) gives T≈1.6×108T≈ 1.6× 10^8 at μ=0.95μ=0.95 and ε=10−2 =10^-2, whereas the width sweep uses widths 6464–20002000 and its hitting times at the same μ and ε are below 7.3×1057.3× 10^5. The theoretical budget and stability bounds thus serve as references rather than certified guarantees for these runs. Detailed protocols are provided in Appendix E. Setup. We train a two-layer ReLU student on unit-normalized Gaussian inputs with labels generated by an independent, fixed ReLU teacher. Only the student’s first layer is trained, using full-batch Muon with five tuned Newton–Schulz steps evaluated in double precision. Unless otherwise stated, n=20n=20, d=100d=100, m=1000m=1000, α=1α=1, and δ=0.05δ=0.05. We compute λ0 _0 from the limiting kernel and R0R_0 from (12), then prescribe η and the reference budget T using (14) and (15). The accuracy panels use λ0≈0.34 _0≈ 0.34 and R0≈26R_0≈ 26; the saved runs used in the remaining diagnostics have λ0=0.335 _0=0.335 and R0=30.2R_0=30.2. We record the first target crossing, thit=mint:L(Wt)≤εt_hit= \t:L(W_t)≤ \. Accuracy and momentum scaling. Figure 1: Training loss across accuracy targets and momentum values. (a) Loss curves for five target values of ε at μ=0.95μ=0.95; dots mark the first iteration reaching each target. (b) Hitting time versus ε , with an ε−1/2 ^-1/2 reference line. (c) Loss curves for five momentum values at target 10−210^-2, using η=(1−μ)η0η=(1-μ) _0 with η0=1.54×10−4 _0=1.54× 10^-4. (d) The curves in (c) plotted against (1−μ)t(1-μ)t. Panels (a,b) use a separate data draw (λ0≈0.34 _0≈ 0.34, R0≈26R_0≈ 26); panels (c,d) use the saved draw (λ0=0.335 _0=0.335, R0=30.2R_0=30.2). The accuracy sweep fixes μ=0.95μ=0.95 and uses η∝εη . The panels show target attainment before the reference budget and a trend consistent with its ε−1/2 ^-1/2 dependence (Figure 1a,b). This compares separate runs with different learning rates. With η=(1−μ)η0η=(1-μ) _0, larger momentum requires more iterations, and plotting against (1−μ)t(1-μ)t approximately collapses the trajectories (Figure 1c,d). This reflects the joint change in momentum and learning rate. A separate fixed-step comparison uses η=η0η= _0 for 50,00050,000 iterations: all three seeds at each displayed momentum reach 10−210^-2 in 14,68014,680–25,44425,444 updates. Thus the factor 1−μ1-μ remains a sufficient choice; these runs do not establish necessity. Gradient-update alignment. We directly examine the mechanism of Lemma 3.2 by measuring gradient-update alignment and the discrepancy between the current gradient and normalized momentum: At=⟨Gt,Ot⟩‖Gt‖F,Dt=‖Bt/st−Gt‖F‖Gt‖F,st=1−μt1−μ.A_t= G_t,O_t \|G_t\|_F, D_t= \|B_t/s_t-G_t\|_F\|G_t\|_F, s_t= 1-μ^t1-μ. (29) Here Bt/stB_t/s_t is the weighted average of stored gradients. The theorem gives the reference At≥κ/2=1/3A_t≥κ/2=1/3 under its assumptions, while DtD_t measures the buffer discrepancy involved in transferring alignment to the current gradient. We record both quantities before target attainment for several momentum values. Figure 2: Gradient alignment and momentum discrepancy. Both panels plot iteration t (logarithmic axis) for five momentum values μ, each run until it first reaches the target 10−210^-2. (a) Alignment At=⟨Gt,Ot⟩/‖Gt‖FA_t= G_t,O_t /\|G_t\|_F between the gradient and the update; the dashed line is the reference κ/2=1/3κ/2=1/3. (b) Buffer discrepancy Dt=‖Bt/st−Gt‖F/‖Gt‖FD_t=\|B_t/s_t-G_t\|_F/\|G_t\|_F, which is identically zero at μ=0μ=0. Alignment remains about 2.72.7 for most of training and declines near the target; its smallest recorded value is 0.6950.695 (at μ=0.99μ=0.99), above 1/31/3. The discrepancy is zero at μ=0μ=0 and has run-wise maxima in [0.066,0.073][0.066,0.073] at μ=0.5μ=0.5 and [0.105,0.124][0.105,0.124] for μ≥0.9μ≥ 0.9. The alignment decrease also occurs at μ=0μ=0, so it cannot be attributed solely to momentum discrepancy. Width and kernel stability. We vary student width while keeping the dataset, teacher, target, momentum, and prescribed learning rate fixed. Across repeated student initializations, we record target attainment and monitor Kt=λmin(H(Wt))α2λ0,St=‖H(Wt)−H(W0)‖2‖H(W0)‖2.K_t= _ (H(W_t))α^2 _0, S_t= \|H(W_t)-H(W_0)\|_2\|H(W_0)\|_2. (30) The reference Kt=1/2K_t=1/2 corresponds to the kernel lower bound used in the proof; StS_t measures relative kernel variation. Figure 3 summarizes these quantities over each run. We also measure displacement relative to the analytical radius in (17) (Figure 5). Figure 3: Training success and kernel stability across widths. (a) Target attainment within 1,414,0001,414,000 updates; (b) minimum KtK_t, with reference 1/21/2; (c) maximum StS_t. Points and bars show mean ±1± 1 sample standard deviation over five seeds per width, measured through target attainment. Every one of these 3030 runs reaches 10−210^-2. The run-wise minimum of KtK_t has mean 0.871±0.0300.871± 0.030 at width 6464 and 0.990±0.0120.990± 0.012 at width 20002000, and the smallest value on any run is 0.8260.826, above the reference 1/21/2. The run-wise maximum of StS_t falls from 0.143±0.0470.143± 0.047 at width 6464 to 0.031±0.0070.031± 0.007 at width 20002000. No run fails to reach the target. These measurements examine behavior below the sufficient width threshold; they do not establish that threshold’s necessity or tightness. Finite maps and parameter movement. Figure 4 compares the tuned five-step map, five classical cubic Newton–Schulz steps, and the exact polar factor on 5959 shared training buffers. For a buffer B with update O, we record the alignment a=⟨B,O⟩/‖B‖Fa= B,O /\|B\|_F, the spectral norm s=‖O‖2s=\|O\|_2, and the ratio q=⟨B,O⟩/(‖B‖∗‖O‖2)q= B,O /(\|B\|_*\|O\|_2), whose maximum 11 is attained by the polar factor. The tuned map satisfies a≥2/3a≥ 2/3 and s≤5/4s≤ 5/4 on every buffer, as Assumption 1 requires. The median q is 0.7640.764 for the tuned map and 0.8600.860 for the classical map. These are diagnostics of the maps; they do not compare training speed or distance to the polar factor. 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 5959 saved buffers from student seed 1010; black ticks mark medians. Dashed references are 2/32/3, 5/45/4, and the polar optimum 11, respectively. Classical NS5 uses the cubic recurrence. Figure 5: Movement within the analytical radius. Maximum ‖Wt−W0‖F/R\|W_t-W_0\|_F/R_B up to target attainment, with R_B from (17). Points show five seeds per width; the line and bars show their mean and ±1± 1 sample standard deviation. The dashed line is the ball boundary. In every width-sweep run, the target is reached with displacement at most 1.67×10−3R1.67× 10^-3R_B, where R=7.88×103R_B=7.88× 10^3. The iterates thus remain well inside B and the kernel remains positive, consistent with the containment step of the proof. These measurements do not verify the uniform Jacobian and remainder bounds at these widths. 6 Conclusion We proved a finite-time training-loss guarantee for full-batch Muon with momentum followed by five tuned Newton–Schulz iterations. For sufficiently wide two-layer ReLU networks with fixed random output weights, a learning rate proportional to (1−μ)ε(1-μ) attains any prescribed loss ε within ((1−μ)−1ε−1/2)O ((1-μ)^-1 ^-1/2 ) iterations, with probability at least 1−δ1-δ over initialization. The proof uses only two properties of the finite-step map, alignment with the momentum buffer and a bounded spectral norm. The tuned map has both without approximating the polar factor, so exact orthogonalization is unnecessary. The experiments are consistent with these mechanisms at widths far below the sufficient threshold (m≳2×1027m 2× 10^27 for our dataset): gradient-update alignment stays above 1/31/3, the kernel ratio KtK_t above 1/21/2, displacement below 1.7×10−3R1.7× 10^-3R_B, and all 3030 width-sweep runs reach the target. They do not test necessity or tightness. On shared buffers, classical Newton–Schulz has a higher median alignment per spectral norm than the tuned map, which does not by itself imply faster training. Future work. Four directions remain: (i) sharper width and momentum requirements, and whether momentum can accelerate Muon as it does gradient descent in Wang et al. [19]; (i) analysis beyond the near-initialization regime, in which the features move; (i) minibatch gradients and finite-precision arithmetic; and (iv) deeper networks and joint training of both layers. Reproducibility Statement The network, initialization, selected ReLU derivative, and full-batch loss are specified in Section 2. Algorithm 1 is the Muon update analyzed in the paper, and equations (4)–(5) fix all five Newton–Schulz steps; Assumption 1 states the only properties of the Newton–Schulz steps that the proof uses, and Appendix B.6 verifies them for the coefficients of Jordan et al. [12]. Equations (12)–(15) specify the width, momentum range, learning rate, and update budget. No empirical result is used in the proof. References [1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, p. 242–252. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/allen-zhu19a.html. [2] Sanjeev Arora, Simon Shaolei Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. ArXiv, abs/1901.08584, 2019. URL https://api.semanticscholar.org/CorpusID:59222746. [3] Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology. ArXiv, abs/2409.20325, 2024a. URL https://api.semanticscholar.org/CorpusID:272987272. [4] Jeremy Bernstein and Laker Newhouse. Modular duality in deep learning. ArXiv, abs/2410.21265, 2024b. URL https://api.semanticscholar.org/CorpusID:273655185. [5] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019. [6] Da Chang, Yongxiang Liu, Huihui Zhou, and Ganzhao Yuan. On the convergence of Muon and beyond. arXiv preprint arXiv:2509.15816, 2025. [7] Lizhang Chen, Jonathan Li, and Qiang Liu. Muon optimizes under spectral norm constraints. Trans. Mach. Learn. Res., 2026, 2025. URL https://api.semanticscholar.org/CorpusID:279447438. [8] Arthur C. B. de Oliveira, Dhruv D. Jatkar, Guilherme S. Vicinansa, and Eduardo D. Sontag. Convergence guarantees for Muon: New parameter regimes and generalizations. arXiv preprint arXiv:2609.30546, 2026. [9] Simon Shaolei Du, J. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. ArXiv, abs/1811.03804, 2018a. URL https://api.semanticscholar.org/CorpusID:53250419. [10] Simon Shaolei Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. ArXiv, abs/1810.02054, 2018b. URL https://api.semanticscholar.org/CorpusID:52920808. [11] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. arXiv preprint arXiv:1909.12292, 2019. [12] Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https://kellerjordan.github.io/posts/muon/. [13] Gyu Yeol Kim and Min-hwan Oh. Convergence of muon with Newton–Schulz. In International Conference on Learning Representations (ICLR), 2026. arXiv:2601.19156. [14] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. ArXiv, abs/1808.01204, 2018. URL https://api.semanticscholar.org/CorpusID:51920936. [15] Jingyuan Liu, Jianling Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, Yanru Chen, Huabin Zheng, Yi-Bo Liu, Shaowei Liu, Bohong Yin, Weiran He, Han Zhu, Yuzhi Wang, Jianzhou Wang, Meng Dong, Zheng Zhang, Yongsheng Kang, Hao Zhang, Xinran Xu, Yutao Zhang, Yuxin Wu, Xinyu Zhou, and Zhilin Yang. Muon is scalable for llm training. ArXiv, abs/2502.16982, 2025. URL https://api.semanticscholar.org/CorpusID:276575212. [16] Naoki Sato, Hiroki Naganuma, and Hideaki Iiduka. Convergence bound and critical batch size of Muon optimizer. arXiv preprint arXiv:2507.01598, 2025. [17] Wei Shen, Ruichuan Huang, Minhui Huang, Cong Shen, and Jiawei Zhang. On the convergence analysis of muon. arXiv preprint arXiv:2505.23737, 2025. [18] Kimi Team, Yifan Bai, Yiping Bao, Y Charles, Cheng Chen, Guanduo Chen, Haiting Chen, Huarong Chen, Jiahao Chen, Ningxin Chen, et al. Kimi k2: Open agentic intelligence. arXiv preprint arXiv:2507.20534, 2025. [19] Jun-Kun Wang, Chi-Heng Lin, and Jacob D. Abernethy. A modular analysis of provable acceleration via polyak’s momentum: Training a wide relu network and a deep linear network. In International Conference on Machine Learning, 2020. URL https://api.semanticscholar.org/CorpusID:235359199. [20] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. Advances in neural information processing systems, 32, 2019. Appendix A Comparison with Prior Guarantees 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 22 except in Du et al. [9], Zou & Gu [20], Allen-Zhu et al. [1], Cao & Gu [5], which allow depth >2>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], ν=O(εδ/n)ν=O( δ/ n) is the initialization scale. For our row, α and ‖y‖22/n\|y\|_2^2/n are treated as constants and T=(n3/2/((1−μ)λ0δε))T=O (n^3/2/((1-μ) _0 δ ) ). Reference Guarantee Width Du et al. [10] L(WT)→0L(W_T)→ 0, linear Ω(n6/(λ04δ3)) (n^6/( _0^4δ^3)) Arora et al. [2] L(WT)≤εL(W_T)≤ Ω(n7/(λ04ν2δ4ε2)) (n^7/( _0^4ν^2δ^4 ^2)) Ji & Telgarsky [11] test error ≤ε≤ polylog(1/ε)polylog(1/ ) Du et al. [9] L(WT)→0L(W_T)→ 0, linear – (poly(n)poly(n)) Zou & Gu [20] L(WT)→0L(W_T)→ 0, faster << Allen-Zhu et al. Li & Liang [14] pop. risk →0→ 0 margin-dependent Allen-Zhu et al. [1] L(WT)→0L(W_T)→ 0, poly time Ω(n24) (n^24) Cao & Gu [5] pop. risk ≤~(n−1/2)≤ O(n^-1/2) sufficiently wide Chen et al. [7] KKT score (1/T)O(1/ T) – Kim & Oh [13] stationarity – Sato et al. [16] stationarity – Chang et al. [6] stationarity – de Oliveira et al. [8] stationarity; linear under PL – This work min0≤t≤TL(Wt)≤ε _0≤ t≤ TL(W_t)≤ Ω(n5/(λ04δ3)) (n^5/( _0^4δ^3) ) Appendix B Supporting Lemmas and Proofs B.1 Initialization Lemma B.1 (Initialization event). Let ℰ1 _1 :=∥e0∥2≤R0, :=\\|e_0\|_2≤ R_0\, ℰ2 _2 :=∥H(W0)−α2H∞∥2≤α2λ04, := \\|H(W_0)-α^2H^∞\|_2≤ α^2 _04 \, ℰ3 _3 :=1m∑i=1n∑r=1m|wr(0)⊤xi|≤δκ2λ01620M2n≤κ2λ0648M2. := \ 1m _i=1^n _r=1^m 1 \|w_r(0) x_i|≤ δκ^2 _01620M^2n \≤ κ^2 _0648M^2 \. (31) Under the width condition (13), each complement has probability at most δ/3δ/3. Hence ℰ:=ℰ1∩ℰ2∩ℰ3E:=E_1 _2 _3 satisfies ℙ(ℰ)≥1−δP(E)≥ 1-δ. Proof of Lemma B.1. We show that each of the three events fails with probability at most δ/3δ/3; a union bound then gives ℙ(ℰ)≥1−δP(E)≥ 1-δ. Part 1. For Z∼(0,1)Z (0,1), σ(Z)2=[Z2Z≥0]=1/2Eσ(Z)^2=E[Z^2 1\Z≥ 0\]=1/2. Since the ara_r are independent of W0W_0 with ar=0Ea_r=0 and ar2=α2a_r^2=α^2, and wr(0)⊤xi∼(0,1)w_r(0) x_i (0,1), u(W0)i=0,u(W0)i2=1m∑r=1mα2σ(wr(0)⊤xi)2=α22.Eu(W_0)_i=0, (W_0)_i^2= 1m _r=1^mα^2\,Eσ(w_r(0) x_i)^2= α^22. (32) Then ℙ(ℰ1c) (E_1^c) =ℙ(‖e0‖22>R02) =P(\|e_0\|_2^2>R_0^2) ≤‖e0‖22R02 ≤ E\|e_0\|_2^2R_0^2 [Markov’s inequality] =‖y‖22+nα2/2R02 = \|y\|_2^2+nα^2/2R_0^2 [cross term vanishes by (32)] =δ3 = δ3 [definition (12) of R0]. [definition ( eq:muon_constants) of $R_0$]. (33) Part 2. For fixed i,ji,j, H(W0)ijα2=1m∑r=1mZrij,Zrij:=xi⊤xj 1wr(0)⊤xi≥0,wr(0)⊤xj≥0. H(W_0)_ijα^2= 1m _r=1^mZ_r^ij, Z_r^ij:=x_i x_j\, 1\w_r(0) x_i≥ 0,\ w_r(0) x_j≥ 0\. (34) The ZrijZ_r^ij are independent over r, have mean Hij∞H^∞_ij by (7), and take values in an interval of length |xi⊤xj|≤1|x_i x_j|≤ 1. Since logz≤z z≤ z, κ≤Mκ≤ M, λ0≤12 _0≤ 12 and δ<1δ<1, the width condition (13) gives m≥48n4/(λ02δ)≥(8n2/λ02)log(6n2/δ)m≥ 48n^4/( _0^2δ)≥(8n^2/ _0^2) (6n^2/δ). Hence ℙ(maxi,j|H(W0)ijα2−Hij∞|>λ04n) ( _i,j | H(W_0)_ijα^2-H^∞_ij |> _04n ) ≤n2⋅2exp(−mλ028n2) ≤ n^2· 2 (- m _0^28n^2 ) [union bound, Hoeffding’s inequality] ≤δ3 ≤ δ3 [m≥(8n2/λ02)log(6n2/δ)]. [$m≥(8n^2/ _0^2) (6n^2/δ)$]. (35) Outside this event, D:=H(W0)/α2−H∞D:=H(W_0)/α^2-H^∞ satisfies ‖D‖2 \|D\|_2 ≤‖D‖F ≤\|D\|_F [operator norm ≤ Frobenius norm] ≤nmaxi,j|Dij| ≤ n _i,j|D_ij| [D has n2n^2 entries] ≤λ04, ≤ _04, (36) which is ℰ2E_2 after multiplying by α2α^2. Hence ℙ(ℰ2c)≤δ/3P(E_2^c)≤δ/3. Part 3. The density of (0,1)N(0,1) is at most 1/2π1/ 2π, so ℙ(|wr(0)⊤xi|≤δκ2λ01620M2n)≤2/πδκ2λ01620M2nP (|w_r(0) x_i|≤ δκ^2 _01620M^2n )≤ 2/π\, δκ^2 _01620M^2n. Let N be the double sum in ℰ3E_3. Then ℙ(ℰ3c) (E_3^c) =ℙ(Nm>κ2λ0648M2) =P ( Nm> κ^2 _0648M^2 ) ≤648M2κ2λ0Nm ≤ 648M^2κ^2 _0\,E Nm [Markov’s inequality] ≤648M2κ2λ0⋅n2πδκ2λ01620M2n ≤ 648M^2κ^2 _0· n 2π\, δκ^2 _01620M^2n [linearity of expectation] ≤δ3 ≤ δ3 [2/π≤56]. [$ 2/π≤ 56$]. (37) The union bound over Parts 1–3 completes the proof. ∎ B.2 Uniform control in the stability ball Throughout this subsection, the gate of hidden unit r on input xix_i at weights Z=(z1,…,zm)Z=(z_1,…,z_m) is the indicator zr⊤xi≥0 1\z_r x_i≥ 0\, and the gate flips between Z and Z′Z if zr⊤xi≥0≠zr′⊤xi≥0 1\z_r x_i≥ 0\≠ 1\z_r x_i≥ 0\. These indicators are exactly the ones appearing in (3) and (6). Lemma B.2 (Uniform NTK and ReLU remainder). On ℰE, for every W,V∈W,V and every matrix O, λmin(H(W)) _ (H(W)) ≥α2λ02, ≥ α^2 _02, (38) ‖J(W)−J(W0)‖F \|J(W)-J(W_0)\|_F ≤καλ018M, ≤ κα _018M, (39) ‖(J(W)−J(V))vec(O)‖2 \|(J(W)-J(V))vec(O)\|_2 ≤καλ018M‖O‖2, ≤ κα _018M\,\|O\|_2, (40) ‖u(V)−u(W)−J(W)vec(V−W)‖2 \|u(V)-u(W)-J(W)vec(V-W)\|_2 ≤καλ018M‖V−W‖2. ≤ κα _018M\,\|V-W\|_2. (41) The ball is measured in Frobenius norm and the last two bounds in operator norm, because one step moves the weights by η‖Ot‖2≤ηMη\|O_t\|_2≤η M. Proof of Lemma B.2. Fix an initialization in ℰE and arbitrary W=(w1,…,wm)W=(w_1,…,w_m) and V=(v1,…,vm)V=(v_1,…,v_m) in B. Part 1 counts the gates that can flip; Part 2 turns that count into the Jacobian bound (39) and the kernel bound (38); Parts 3 and 4 turn it into the remainder bound (41) and the bound (40). Part 1. For Z∈W,VZ∈\W,V\ and each i, define i:=r:|wr(0)⊤xi|≤δκ2λ01620M2n,ℐ(Z):=r:‖zr−wr(0)‖2>δκ2λ01620M2n.S_i:= \r:|w_r(0) x_i|≤ δκ^2 _01620M^2n \, (Z):= \r:\|z_r-w_r(0)\|_2> δκ^2 _01620M^2n \. (42) If r∉i∪ℐ(Z)r _i (Z), then, using ‖xi‖2=1\|x_i\|_2=1, |(zr−wr(0))⊤xi|≤‖zr−wr(0)‖2≤δκ2λ01620M2n<|wr(0)⊤xi|,|(z_r-w_r(0)) x_i|≤\|z_r-w_r(0)\|_2≤ δκ^2 _01620M^2n<|w_r(0) x_i|, (43) so zr⊤xiz_r x_i and wr(0)⊤xiw_r(0) x_i have the same nonzero sign and the gate of unit r on xix_i does not flip between W0W_0 and Z. Hence the set i(W,V):=r:the gate of r on xi flips between W0 and W, or between W0 and VA_i(W,V):=\r:the gate of $r$ on $x_i$ flips between $W_0$ and $W$, or between $W_0$ and $V$\ (44) satisfies i(W,V)⊆i∪ℐ(W)∪ℐ(V)A_i(W,V) _i (W) (V). Each r∈ℐ(Z)r (Z) contributes more than (δκ2λ0/(1620M2n))2(δκ^2 _0/(1620M^2n))^2 to ‖Z−W0‖F2\|Z-W_0\|_F^2, and Z∈Z , so |ℐ(Z)|≤(18MnR0καλ0)2(1620M2nδκ2λ0)2≤8.51⋅108M6n3R02κ6α2λ03δ2.|I(Z)|≤ ( 18M n\,R_0κα _0 )^2 ( 1620M^2nδκ^2 _0 )^2≤ 8.51· 10^8\,M^6n^3R_0^2κ^6α^2 _0^3δ^2. (45) Therefore 1m∑i=1n|i(W,V)| 1m _i=1^n|A_i(W,V)| ≤1m∑i=1n|i|+nm(|ℐ(W)|+|ℐ(V)|) ≤ 1m _i=1^n|S_i|+ nm (|I(W)|+|I(V)| ) [inclusion above] ≤κ2λ0648M2+1.71⋅109M6n4R02mκ6α2λ03δ2 ≤ κ^2 _0648M^2+ 1.71· 10^9\,M^6n^4R_0^2m\,κ^6α^2 _0^3δ^2 [on ℰ3E_3; by (45)] ≤κ2λ0324M2 ≤ κ^2 _0324M^2 [width (13), R02≤3α2δ(n+‖y‖22α2)]. [width ( eq:muon_width), $R_0^2≤ 3α^2δ (n+ \|y\|_2^2α^2 )$]. (46) The last inequality uses (13) together with 648⋅3⋅1.71⋅109<3.4⋅1012≤5⋅1012648· 3· 1.71· 10^9<3.4· 10^12≤ 5· 10^12. Part 2. Take V=W0V=W_0. A block of J(W)−J(W0)J(W)-J(W_0) is nonzero only when the gate flips, and then has squared norm α2/mα^2/m. Hence ‖J(W)−J(W0)‖F2≤α2m∑i=1n|i(W,W0)|≤κ2α2λ0324M2\|J(W)-J(W_0)\|_F^2≤ α^2m _i=1^n|A_i(W,W_0)|≤ κ^2α^2 _0324M^2 (47) by (46), which is (39). For every q∈ℝnq ^n, ‖J(W)⊤q‖2 \|J(W) q\|_2 ≥‖J(W0)⊤q‖2−‖J(W)−J(W0)‖2‖q‖2 ≥\|J(W_0) q\|_2-\|J(W)-J(W_0)\|_2\|q\|_2 [reverse triangle inequality] ≥q⊤H(W0)q−καλ018M‖q‖2 ≥ q H(W_0)q- κα _018M\|q\|_2 [by (47)] ≥(32−118)αλ0‖q‖2 ≥ ( 32- 118 )α _0\,\|q\|_2 [on ℰ2; κ≤M]. [on $ E_2$; $κ≤ M$]. (48) Here ℰ2E_2 gives λmin(H(W0))≥34α2λ0 _ (H(W_0))≥ 34α^2 _0. Since (3/2−1/18)2>1/2( 3/2-1/18)^2>1/2, squaring (48) gives (38). Part 3. Set ξ:=u(V)−u(W)−J(W)vec(V−W),ξi=1m∑r=1marρ(wr⊤xi,(vr−wr)⊤xi),ξ:=u(V)-u(W)-J(W)vec(V-W), _i= 1 m _r=1^ma_r\,ρ (w_r x_i,(v_r-w_r) x_i ), (49) where ρ(z,h):=σ(z+h)−σ(z)−z≥0hρ(z,h):=σ(z+h)-σ(z)- 1\z≥ 0\h. The scalar remainder satisfies |ρ(z,h)|≤|h||ρ(z,h)|≤|h|, and ρ(z,h)=0ρ(z,h)=0 unless the gates at z and z+hz+h differ. If neither W nor V flips a gate relative to W0W_0, the gates at W and V agree, so only r∈i(W,V)r _i(W,V) contributes. Therefore |ξi| | _i| ≤αm∑r∈i(W,V)|(vr−wr)⊤xi| ≤ α m _r _i(W,V)|(v_r-w_r) x_i| [|ar|=α|a_r|=α, |ρ(z,h)|≤|h||ρ(z,h)|≤|h|] ≤α|i(W,V)|m‖(V−W)⊤xi‖2 ≤α |A_i(W,V)|m\,\|(V-W) x_i\|_2 [Cauchy–Schwarz over r] ≤α|i(W,V)|m‖V−W‖2 ≤α |A_i(W,V)|m\,\|V-W\|_2 [‖xi‖2=1]. [$\|x_i\|_2=1$]. (50) Squaring and summing over i, ‖ξ‖22 \|ξ\|_2^2 ≤α2∥V−W∥22⋅1m∑i=1n|i(W,V)| ≤α^2\|V-W\|_2^2· 1m _i=1^n|A_i(W,V)| ≤κ2α2λ0324M2‖V−W‖22 ≤ κ^2α^2 _0324M^2\,\|V-W\|_2^2 [by (46)], [by ( eq:appendix_bad_gate_average)], (51) which is (41). Part 4. Write oro_r for the r-th column of O. The i-th entry of (J(W)−J(V))vec(O)(J(W)-J(V))vec(O) is 1m∑rar(wr⊤xi≥0−vr⊤xi≥0)or⊤xi 1 m _ra_r ( 1\w_r x_i≥ 0\- 1\v_r x_i≥ 0\ )o_r x_i, and as in Part 3 only r∈i(W,V)r _i(W,V) contribute. Hence ‖(J(W)−J(V))vec(O)‖22 \|(J(W)-J(V))vec(O)\|_2^2 ≤∑i=1nα2|i(W,V)|m‖O⊤xi‖22 ≤ _i=1^nα^2 |A_i(W,V)|m\,\|O x_i\|_2^2 [|ar|=α|a_r|=α, Cauchy–Schwarz over r] ≤κ2α2λ0324M2‖O‖22 ≤ κ^2α^2 _0324M^2\,\|O\|_2^2 [‖xi‖2=1, (46)], [$\|x_i\|_2=1$, ( eq:appendix_bad_gate_average)], (52) which is (40). ∎ B.3 Newton–Schulz steps Lemma B.3 (Newton–Schulz matrix bounds). Under Assumption 1, every matrix B whose column space lies in spanx1,…,xnspan\x_1,…,x_n\ satisfies ⟨B,NSK(B)⟩≥κ‖B‖F,‖NSK(B)‖2≤M,‖NSK(B)‖F≤Mn. B,NS_K(B) ≥κ\|B\|_F, \|NS_K(B)\|_2≤ M, \|NS_K(B)\|_F≤ M n. Proof of Lemma B.3. By Assumption 1, κx≤Φ(x)≤M,x∈[0,1].κ x≤ (x)≤ M, x∈[0,1]. (53) The case B=0B=0 holds by the convention NSK(0)=0NS_K(0)=0. Otherwise let B=UΣV⊤B=U V be a compact SVD with positive singular values s1,…,sks_1,…,s_k. Each step of (4) keeps U,VU,V and applies ϕk _k to the diagonal, so NSK(B)=Udiag(Φ(s1‖B‖F),…,Φ(sk‖B‖F))V⊤,sj‖B‖F∈(0,1].NS_K(B)=Udiag ( ( s_1\|B\|_F ),…, ( s_k\|B\|_F ) )V , s_j\|B\|_F∈(0,1]. (54) By (53) the diagonal entries lie in [0,M][0,M], so ‖NSK(B)‖2≤M\|NS_K(B)\|_2≤ M. The column space of B lies in spanx1,…,xnspan\x_1,…,x_n\, so k≤nk≤ n and ‖NSK(B)‖F≤Mk≤Mn\|NS_K(B)\|_F≤ M k≤ M n. Finally, ⟨B,NSK(B)⟩ B,NS_K(B) =∑j=1ksjΦ(sj‖B‖F) = _j=1^ks_j\, ( s_j\|B\|_F ) [shared singular vectors in (54)] ≥κ‖B‖F∑j=1ksj2 ≥ κ\|B\|_F _j=1^ks_j^2 [lower bound in (53)] =κ‖B‖F =κ\|B\|_F [∑jsj2=‖B‖F2]. [$ _js_j^2=\|B\|_F^2$]. (55) ∎ B.4 One-step descent Proof of Lemma 3.3. Every buffer column lies in spanx1,…,xnspan\x_1,…,x_n\, so Lemma B.3 applies to BtB_t, and Wt−Wt−1=−ηOtW_t-W_t-1=-η O_t. Part 1 bounds how far the predictions move; Part 2 expands the new residual and proves (20); Part 3 converts it into (22). Part 1. For each i, |u(Wt)i−u(Wt−1)i| |u(W_t)_i-u(W_t-1)_i| ≤αηm∑r=1m|(Ot)⋅,r⊤xi| ≤ αη m _r=1^m|(O_t)_·,r x_i| [σ is 11-Lipschitz, |ar|=α|a_r|=α] ≤αη‖Ot⊤xi‖2 ≤αη\,\|O_t x_i\|_2 [Cauchy–Schwarz over r] ≤Mαη ≤ Mαη [‖xi‖2=1, Lemma B.3], [$\|x_i\|_2=1$, Lemma~ lem:ns5], (56) so ‖u(Wt)−u(Wt−1)‖2≤nMαη\|u(W_t)-u(W_t-1)\|_2≤ n\,Mαη. This bound holds at every step, whether or not the iterates lie in B. Part 2. By hypothesis (19) and the kernel bound (38), ⟨Gt,Ot⟩≥κ2‖Gt‖F=κ2(et−1⊤H(Wt−1)et−1)1/2≥καλ022‖et−1‖2. G_t,O_t ≥ κ2\|G_t\|_F= κ2 (e_t-1 H(W_t-1)e_t-1 )^1/2≥ κα _02 2\,\|e_t-1\|_2. (57) Let ξ:=u(Wt)−u(Wt−1)+ηJ(Wt−1)vec(Ot)ξ:=u(W_t)-u(W_t-1)+η J(W_t-1)vec(O_t) be the linearization remainder of the step. Both iterates lie in B, so (41) and Lemma B.3 give ‖ξ‖2≤καλ018M⋅Mη=καηλ018\|ξ\|_2≤ κα _018M· Mη= καη _018. Moreover, −ηet−1⊤J(Wt−1)vec(Ot)=−η(J(Wt−1)⊤et−1)⊤vec(Ot)=η⟨Gt,Ot⟩.-η\,e_t-1 J(W_t-1)vec(O_t)=-η\,(J(W_t-1) e_t-1) vec(O_t)=η G_t,O_t . (58) Since et=et−1−(u(Wt)−u(Wt−1))e_t=e_t-1-(u(W_t)-u(W_t-1)), ‖et‖22 \|e_t\|_2^2 =‖et−1‖22−2η⟨Gt,Ot⟩−2et−1⊤ξ+‖u(Wt)−u(Wt−1)‖22 =\|e_t-1\|_2^2-2η G_t,O_t -2e_t-1 ξ+\|u(W_t)-u(W_t-1)\|_2^2 [expand, (58)] ≤‖et−1‖22−(12−218)καηλ0‖et−1‖2+nM2α2η2 ≤\|e_t-1\|_2^2- ( 1 2- 218 )καη _0\,\|e_t-1\|_2+nM^2α^2η^2 [(57), Part 1, Cauchy–Schwarz] ≤‖et−1‖22−καηλ04‖et−1‖2+nM2α2η2 ≤\|e_t-1\|_2^2- καη _04\|e_t-1\|_2+nM^2α^2η^2 [12−218>14]. [$ 1 2- 218> 14$]. (59) This is (20). Part 3. Assume (21); since η>0η>0 it forces ‖et−1‖2>0\|e_t-1\|_2>0. Multiplying (21) by nM2α2ηnM^2α^2η gives nM2α2η2≤καηλ08‖et−1‖2nM^2α^2η^2≤ καη _08\|e_t-1\|_2, so ‖et‖22 \|e_t\|_2^2 ≤‖et−1‖22−καηλ08‖et−1‖2 ≤\|e_t-1\|_2^2- καη _08\|e_t-1\|_2 [by (59)] =‖et−1‖22(1−καηλ08‖et−1‖2). =\|e_t-1\|_2^2 (1- καη _08\|e_t-1\|_2 ). (60) The left side is nonnegative, so the bracket lies in [0,1][0,1], and ‖et‖2 \|e_t\|_2 ≤‖et−1‖2(1−καηλ016‖et−1‖2) ≤\|e_t-1\|_2 (1- καη _016\|e_t-1\|_2 ) [1−z≤1−z/2 1-z≤ 1-z/2 on [0,1][0,1]] =‖et−1‖2−καηλ016, =\|e_t-1\|_2- καη _016, (61) which is (22). ∎ B.5 Momentum Proof of Lemma 3.2. Write Jk:=J(Wk)J_k:=J(W_k). Unrolling Bt=μBt−1+GtB_t=μ B_t-1+G_t down to B0=0B_0=0 splits the buffer into the current gradient and the change of the older ones, Bt=SGt+D,S:=∑j=0t−1μj≥1,D:=∑j=1t−1μj(Gt−j−Gt).B_t=S\,G_t+D, S:= _j=0^t-1μ^j≥ 1, D:= _j=1^t-1μ^j (G_t-j-G_t ). (62) Part 1 reduces the claim to a bound on D, Part 2 bounds one term of D, and Part 3 adds the terms up. Part 1. The column space of BtB_t lies in spanx1,…,xnspan\x_1,…,x_n\, so S⟨Gt,Ot⟩ S G_t,O_t =⟨Bt,Ot⟩−⟨D,Ot⟩ = B_t,O_t - D,O_t [by (62)] ≥κ‖Bt‖F−|⟨D,Ot⟩| ≥κ\|B_t\|_F-| D,O_t | [Lemma B.3] ≥κS‖Gt‖F−κ‖D‖F−|⟨D,Ot⟩| ≥κ S\|G_t\|_F-κ\|D\|_F-| D,O_t | [triangle inequality]. [triangle inequality]. (63) It therefore suffices to show κ‖D‖F+|⟨D,Ot⟩|≤κ2S‖Gt‖F.κ\|D\|_F+| D,O_t |≤ κ2\,S\|G_t\|_F. (64) Part 2. Fix 1≤j≤t−11≤ j≤ t-1 and put s=t−js=t-j. By the gradient identity, vec(Gs−Gt)=−Js−1⊤(es−1−et−1)−(Js−1−Jt−1)⊤et−1vec(G_s-G_t)=-J_s-1 (e_s-1-e_t-1)-(J_s-1-J_t-1) e_t-1. Two facts control the first term. By Part 1 of the proof of Lemma 3.3, the residual moves by at most nMαη n\,Mαη per step, so ‖es−1−et−1‖2≤jnMαη\|e_s-1-e_t-1\|_2≤ j n\,Mαη. And for every W and every matrix O, each entry of J(W)vec(O)J(W)vec(O) is at most α‖O⊤xi‖2≤α‖O‖2α\|O x_i\|_2≤α\|O\|_2 in magnitude, by Cauchy–Schwarz over the hidden units, so ‖J(W)vec(O)‖2≤αn‖O‖2\|J(W)vec(O)\|_2≤α n\,\|O\|_2 and ‖J(W)‖2≤αn\|J(W)\|_2≤α n. Since Ws−1,Wt−1∈W_s-1,W_t-1 , ‖Gs−Gt‖F \|G_s-G_t\|_F ≤‖Js−1‖2‖es−1−et−1‖2+‖Js−1−Jt−1‖2‖et−1‖2 ≤\|J_s-1\|_2\|e_s-1-e_t-1\|_2+\|J_s-1-J_t-1\|_2\|e_t-1\|_2 [triangle inequality] ≤jnMα2η+2καλ018M‖et−1‖2 ≤ jnMα^2η+ 2κα _018M\|e_t-1\|_2 [facts above, (39) twice], [facts above, ( eq:muon_jacobian_close) twice], (65) |⟨Gs−Gt,Ot⟩| | G_s-G_t,O_t | ≤‖es−1−et−1‖2‖Js−1vec(Ot)‖2 ≤\|e_s-1-e_t-1\|_2\|J_s-1vec(O_t)\|_2 +‖et−1‖2‖(Js−1−Jt−1)vec(Ot)‖2 +\|e_t-1\|_2\|(J_s-1-J_t-1)vec(O_t)\|_2 [Cauchy–Schwarz] ≤jnM2α2η+καλ018‖et−1‖2 ≤ jnM^2α^2η+ κα _018\|e_t-1\|_2 [facts above, (40), ‖Ot‖2≤M]. [facts above, ( eq:muon_jacobian_action), $\|O_t\|_2≤ M$]. (66) Since κ≤Mκ≤ M, the two bounds combine to κ‖Gs−Gt‖F+|⟨Gs−Gt,Ot⟩|≤2jnM2α2η+3καλ018‖et−1‖2.κ\|G_s-G_t\|_F+| G_s-G_t,O_t |≤ 2jnM^2α^2η+ 3κα _018\|e_t-1\|_2. (67) Part 3. Exchanging the order of summation and using ∑k=0t−1−iμk≤S _k=0^t-1-iμ^k≤ S, ∑j=1t−1jμj=∑i=1t−1∑j=it−1μj=∑i=1t−1μi∑k=0t−1−iμk≤S∑i=1t−1μi≤Sμ1−μ, _j=1^t-1jμ^j= _i=1^t-1 _j=i^t-1μ^j= _i=1^t-1μ^i _k=0^t-1-iμ^k≤ S _i=1^t-1μ^i≤ Sμ1-μ, (68) and also ∑j=1t−1μj≤S _j=1^t-1μ^j≤ S. Summing (67) with weights μjμ^j, κ‖D‖F+|⟨D,Ot⟩| κ\|D\|_F+| D,O_t | ≤S(2μ1−μnM2α2η+3καλ018‖et−1‖2) ≤ S ( 2μ1-μ\,nM^2α^2η+ 3κα _018\|e_t-1\|_2 ) [triangle inequality, weight sums] ≤S(κ4αλ0ε+3καλ018‖et−1‖2) ≤ S ( κ4\,α _0 + 3κα _018\|e_t-1\|_2 ) [bound on η, μ≤1μ≤ 1] ≤κ2S‖Gt‖F ≤ κ2\,S\|G_t\|_F [see below]. [see below]. (69) The last line uses the kernel bound (38) at Wt−1W_t-1 and ‖et−1‖2>2ε\|e_t-1\|_2> 2 , which give ‖Gt‖F≥αλ0/2‖et−1‖2>αλ0ε\|G_t\|_F≥α _0/2\,\|e_t-1\|_2>α _0 , together with 318≤142 318≤ 14 2; each of the two terms is then at most κ4‖Gt‖F κ4\|G_t\|_F. This is (64), and with (63) it gives ⟨Gt,Ot⟩≥κ‖Gt‖F−κ2‖Gt‖F G_t,O_t ≥κ\|G_t\|_F- κ2\|G_t\|_F. For t=1t=1 the sums are empty, D=0D=0, and the claim is Lemma B.3 directly. ∎ B.6 Constants of Muon’s coefficients and of the classical polynomials The classical schedules used below are defined by the Taylor truncations p(d)(λ)=∑s=0d(2s)!4s(s!)2(1−λ)s,ϕ(d)(x)=xp(d)(x2).p^(d)(λ)= _s=0^d (2s)!4^s(s!)^2(1-λ)^s, φ^(d)(x)=xp^(d)(x^2). (70) Here d=1d=1 gives the cubic scalar iteration and d=2d=2 the quintic. The tuned map instead uses the coefficients specified in the main text. Proposition 1. For p(λ)=a+bλ+cλ2p(λ)=a+bλ+cλ^2 with (a,b,c)=(3.4445,−4.7750,2.0315)(a,b,c)=(3.4445,-4.7750,2.0315), ϕ(x)=xp(x2)φ(x)=x\,p(x^2) and Φ=ϕ∘5 =φ 5, Φ(x)≤54andΦ(x)≥23xfor x∈[0,1],Φ(x)≥0.68for x∈[1400,1]. (x)≤ 54 (x)≥ 23x x∈[0,1], (x)≥ 0.68 x∈ [ 1400,1 ]. (71) Proof. The proof uses four facts about the single quintic ϕφ, each an evaluation of a polynomial. Let xa≈0.55453x_a≈ 0.55453 and xb≈1.05014x_b≈ 1.05014 be the positive roots of ϕ′(x)=a+3bx2+5cx4φ (x)=a+3bx^2+5cx^4. (F1) p(z)≥a−b2/(4c)=0.6386…>0p(z)≥ a-b^2/(4c)=0.6386…>0 for all z, and p decreases on [0,−b/(2c)]=[0,1.1752…][0,-b/(2c)]=[0,1.1752…]. (F2) ϕφ increases on [0,xa][0,x_a], decreases on [xa,xb][x_a,x_b] and increases on [xb,54][x_b, 54], with ϕ(xa)=1.2023…φ(x_a)=1.2023…, ϕ(xb)=0.6818…φ(x_b)=0.6818… and ϕ(54)=1.1790…φ( 54)=1.1790…. (F3) p(xa2)=2.1682…p(x_a^2)=2.1682…. (F4) The first five iterates of 1400 1400 under ϕφ are 0.0086…0.0086…, 0.0296…0.0296…, 0.1020…0.1020…, 0.3464…0.3464… and 1.0048…1.0048…. By (F1) and (F2), ϕφ maps [0,54][0, 54] into [0,1.2024][0,1.2024] and maps [xa,54][x_a, 54] into [0.6818,1.2024][0.6818,1.2024]. Fix x∈(0,1]x∈(0,1] and let xk=ϕ∘k(x)x_k=φ k(x), so every xkx_k lies in [0,1.2024][0,1.2024] and in particular Φ(x)=x5≤54 (x)=x_5≤ 54. Part 1. Suppose xk≥xax_k≥ x_a for some k≤4k≤ 4. Then xk∈[xa,54]x_k∈[x_a, 54], every later iterate stays in [0.6818,1.2024]⊆[xa,54][0.6818,1.2024] [x_a, 54], and so Φ(x)≥0.6818 (x)≥ 0.6818. In particular Φ(x)≥0.68 (x)≥ 0.68 and Φ(x)≥23x (x)≥ 23x, since x≤1x≤ 1. Part 2. Suppose xk<xax_k<x_a for every k≤4k≤ 4. Since p decreases on [0,xa2][0,x_a^2], Φ(x)x (x)x =∏k=04p(xk2) = _k=0^4p(x_k^2) [ϕ(x)=xp(x2)φ(x)=x\,p(x^2)] ≥p(xa2)5 ≥ p(x_a^2)^5 [(F1), xk2<xa2x_k^2<x_a^2] ≥1 ≥ 1 [(F3)], [(F3)], (72) so Φ(x)≥23x (x)≥ 23x. If moreover x≥1400x≥ 1400, then, since ϕφ increases on [0,xa][0,x_a], induction on k gives xk≥ϕ∘k(1400)x_k≥φ k( 1400) for k≤4k≤ 4, and so Φ(x)=ϕ(x4)≥ϕ(ϕ∘4(1400))=1.0048…≥0.68 (x)=φ(x_4)≥φ (φ 4( 1400) )=1.0048…≥ 0.68 by (F4). Parts 1 and 2 cover all x∈(0,1]x∈(0,1] and prove (71); x=0x=0 is trivial. ∎ The first two claims give Assumption 1 for Muon’s coefficients with κ=23κ= 23 and M=54M= 54, the values used in Theorem 3.1. The third claim also yields a nuclear-norm alignment bound: if every nonzero singular value of B is at least ‖B‖F/400\|B\|_F/400, then by (54) ⟨B,NS5(B)⟩=∑jsjΦ(sj/‖B‖F)≥0.68‖B‖∗ B,NS_5(B) = _js_j (s_j/\|B\|_F)≥ 0.68\,\|B\|_*. Proposition 2 (Classical Newton–Schulz polynomials). Let Φ be the composition of K classical polynomials (70) of degrees d0,…,dK−1≥1d_0,…,d_K-1≥ 1. For x∈[0,1]x∈[0,1], x≤Φ(x)≤1and1−Φ(x)2≤(1−x2)∏k(dk+1).x≤ (x)≤ 1 1- (x)^2≤(1-x^2) _k(d_k+1). (73) Hence Assumption 1 holds with κ=M=1κ=M=1 for every degree and every number of steps. For five steps of the same degree, Φ(x)≥0.68 (x)≥ 0.68 on [17,1][ 17,1] when d=1d=1 and on [119,1][ 119,1] when d=2d=2. Proof. Part 1. For λ∈(0,1]λ∈(0,1], the Taylor series λ−1/2=∑s≥0(2s)!4s(s!)2(1−λ)sλ^-1/2= _s≥ 0 (2s)!4^s(s!)^2(1-λ)^s converges and has nonnegative terms, and p(d)p^(d) is its truncation after the term s=ds=d. Hence 1≤p(d)(λ)≤λ−1/21≤ p^(d)(λ)≤λ^-1/2, and with λ=x2λ=x^2, x≤xp(d)(x2)=ϕ(x)≤1,x∈(0,1].x≤ x\,p^(d)(x^2)=φ(x)≤ 1, x∈(0,1]. (74) So each step maps [0,1][0,1] into itself without decreasing its argument, and composing K steps gives x≤Φ(x)≤1x≤ (x)≤ 1. Part 2. For a classical polynomial of degree d and u∈[0,1]u∈[0,1], 1−(1−u)p(d)(1−u)2≤ud+11-(1-u)\,p^(d)(1-u)^2≤ u^d+1 [13, Lemma 3]. With u=1−x2u=1-x^2 this reads 1−ϕ(x)2≤(1−x2)d+11-φ(x)^2≤(1-x^2)^d+1. By Part 1 every iterate stays in [0,1][0,1], so applying this bound at each of the K steps gives the second claim of (73). The bound Φ(x)≥(1−(1−x2)∏k(dk+1))1/2 (x)≥ (1-(1-x^2) _k(d_k+1) )^1/2 increases in x. For K=5K=5 and d=1d=1 the exponent is 3232 and (48/49)32<0.52(48/49)^32<0.52, so Φ≥0.69 ≥ 0.69 on [17,1][ 17,1]. For d=2d=2 the exponent is 243243 and (360/361)243<0.51(360/361)^243<0.51, so Φ≥0.70 ≥ 0.70 on [119,1][ 119,1]. ∎ Appendix C Derivation of the infinite-width kernel Let w∼(0,Id)w (0,I_d). The pair (w⊤xi,w⊤xj)(w x_i,w x_j) is a centered bivariate Gaussian with unit variances and correlation xi⊤xjx_i x_j. The two half-space conditions intersect in an angular wedge of length π−arccos(xi⊤xj)π- (x_i x_j), so ℙ(w⊤xi≥0,w⊤xj≥0)=π−arccos(xi⊤xj)2π.P(w x_i≥ 0,\ w x_j≥ 0)= π- (x_i x_j)2π. (75) Multiplying by xi⊤xjx_i x_j gives (7). Appendix D Polar-Factor Optimality and Finite-Step Alignment The exact polar factor maximizes alignment with a given buffer per unit spectral norm. This property concerns the buffer; transfer to the current gradient additionally requires Lemma 3.2. Proposition 3 (Optimal buffer alignment per unit spectral norm). Let B≠0B≠ 0 have compact singular value decomposition B=UΣV⊤B=U V . For every nonzero matrix O of the same dimensions, ⟨B,O⟩‖O‖2≤‖B‖∗, B,O \|O\|_2≤\|B\|_*, (76) with equality for O=UV⊤O=UV . Proof. The trace inequality gives ⟨B,O⟩≤∑jsj(B)sj(O)≤‖O‖2∑jsj(B)=‖O‖2‖B‖∗ B,O ≤ _js_j(B)s_j(O)≤\|O\|_2 _js_j(B)=\|O\|_2\|B\|_*. For O=UV⊤O=UV , ‖O‖2=1\|O\|_2=1 and ⟨B,O⟩=tr(Σ)=‖B‖∗ B,O =tr( )=\|B\|_*. ∎ Under Assumption 1, the finite map satisfies ⟨B,NSK(B)⟩‖NSK(B)‖2≥κM‖B‖F. B,NS_K(B) \|NS_K(B)\|_2≥ κM\|B\|_F. This bound suffices for the training analysis without establishing a uniform, rank-independent fraction of the polar optimum. If every nonzero singular value of B is at least ‖B‖F/400\|B\|_F/400, then Proposition 1 additionally gives ⟨B,NS5(B)⟩≥0.68‖B‖∗ B,NS_5(B) ≥ 0.68\|B\|_*. Together with M≤5/4M≤ 5/4, this implies an alignment-per-norm ratio of at least 0.544‖B‖∗0.544\|B\|_*. This stronger comparison requires the stated spectral condition and is not assumed in the training theorem. Appendix E Experimental Details and Additional Diagnostics This section collects the protocols and supporting diagnostics accompanying Section 5. The finite-map comparison is interpreted using Proposition 3. E.1 Data, Initialization, and Numerical Settings Inputs are sampled from a standard Gaussian distribution in ℝdR^d and normalized individually to unit norm. For the saved experiments, we use one dataset with seed 0 and an independent two-layer ReLU teacher with seed 1, width 1000, and output weights sampled from ±1\± 1\. The teacher output uses the 1/10001/ 1000 normalization in (1). The teacher and labels remain fixed across student initializations and widths. Unless otherwise specified, n=20n=20, d=100d=100, m=1000m=1000, α=1α=1, and δ=0.05δ=0.05. Student initialization and the unnormalized squared-loss convention follow Section 2. The alignment and fixed-step momentum experiments use student seeds 10, 11, and 12; the width sweep uses seeds 10–14 at each width. For the saved dataset, we compute λ0=0.335 _0=0.335 from (7) and R0=30.2R_0=30.2 from (12). With κ=2/3κ=2/3, M=5/4M=5/4, and target ε=10−2 =10^-2, the prescribed learning rate is η=(1−μ)η0η=(1-μ) _0, where η0≈1.54×10−4 _0≈ 1.54× 10^-4. The fixed-step comparison instead uses η=η0η= _0 for every momentum value. The reference budget T is computed from (15); practical iteration caps are listed separately in Table 2 and are distinguished from T in Appendix E.2. Figure 1(c,d) uses the saved seed-10 trajectories from the alignment experiment. Figure 1(a,b) shows a separate accuracy sweep on a different draw of the data, with λ0≈0.34 _0≈ 0.34, R0≈26R_0≈ 26, and μ=0.95μ=0.95. The experiments use Python 3.14.6 and NumPy 2.5.3. Newton–Schulz calculations use float64 arithmetic and Frobenius normalization without a denominator regularizer. Double precision reduces roundoff but does not make the computation identical to the exact-arithmetic map analyzed in the theorem. The SVD routine, numerical-rank threshold, logging schedule, and run horizons are specified in Table 2. Table 2: Experimental settings for the diagnostics in this appendix and in Section 5. Learning rates use the measured constants of the frozen draw, λ0=0.335 _0=0.335 and R0=30.2R_0=30.2. Horizons are the iteration caps actually used, not the theoretical budget. Setting Value or status Default data and student n=20n=20, d=100d=100, m=1000m=1000, α=1α=1 Budget parameter δ=0.05δ=0.05 Accuracy panels ε∈10−1,10−2,10−3,10−4,10−5 ∈\10^-1,10^-2,10^-3,10^-4,10^-5\; μ=0.95μ=0.95; separate draw with R0≈26R_0≈ 26 Displayed momentum values μ∈0,0.5,0.9,0.95,0.99μ∈\0,0.5,0.9,0.95,0.99\ Fixed-step comparison Target 10−210^-2; shared step η=η0=1.54×10−4η= _0=1.54× 10^-4; horizon 50,00050,000 Teacher specification Width 10001000, output weights ±1± 1, seed 11, labels scaled by m−1/2m^-1/2 Repetitions One dataset (seed 00) and one teacher. Alignment and fixed-step: student seeds 10,11,1210,11,12. Width: seeds 1010–1414 Alignment study Target 10−210^-2; μ∈0,0.5,0.9,0.95,0.99μ∈\0,0.5,0.9,0.95,0.99\; η=(1−μ)η0η=(1-μ) _0; horizons 70,70070,700 to 7,070,0007,070,000 Width study m∈64,128,256,512,1000,2000m∈\64,128,256,512,1000,2000\; target 10−210^-2; μ=0.95μ=0.95; horizon 1,414,0001,414,000 Logging At,Dt,CtA_t,D_t,C_t every step. Kernel and displacement every step in the width sweep. Buffers: 1212 geometric steps plus the last, seed 1010 only (5959 buffers) SVD computation numpy.linalg.svd; keep s>max(d,m)εfloat64smaxs> (d,m)\, _float64\,s_ . Discarded nuclear fraction ≤8×10−15≤ 8× 10^-15 Implementation Python 3.14.63.14.6, NumPy 2.5.32.5.3, float64. No denominator regularizer Variability summaries Each seed has equal weight. Bands and error bars are mean ±1± 1 standard deviation across seeds. Extrema are over every logged iteration E.2 Stopping, Logging, and Alignment Conventions For each run, we define thit=mint:L(Wt)≤εt_hit= \t:L(W_t)≤ \, with thit=0t_hit=0 if the initial iterate already satisfies the target. Training terminates at target attainment or the practical horizon H listed in Table 2. A run that does not reach the target within H is recorded as unsuccessful within that horizon; it is not assigned a hitting time of H. The practical cap is distinct from the theorem’s reference budget. For the saved dataset with μ=0.95μ=0.95 and ε=10−2 =10^-2, T≈1.62×108T≈ 1.62× 10^8, whereas the practical horizon is H=1,414,000H=1,414,000. The parameter δ specifies the theoretical reference calculation, not an empirical confidence interval or a guaranteed failure probability at the tested widths. The alignment quantities AtA_t and DtD_t in (29) are recorded at every update, including the update that first reaches the target. The quantity AtA_t is not a cosine similarity because it is normalized only by the gradient norm. The normalization Bt/stB_t/s_t, with st=(1−μt)/(1−μ)s_t=(1-μ^t)/(1-μ), removes the accumulation factor from the momentum buffer. Consequently, Dt=0D_t=0 whenever all stored gradients coincide; in particular, Dt=0D_t=0 for μ=0μ=0. Normalized diagnostics are defined only when their denominators are nonzero. A zero denominator is treated as an undefined measurement rather than assigned a numerical value. Figure 2 uses student seeds 10, 11, and 12. At each iteration, the plotted mean includes only seeds that have not already terminated; each contributing seed receives equal weight. Shaded bands show one sample standard deviation above and below the mean when at least two seeds remain. Thus, the number of contributing seeds decreases after the first target crossing, and changes near the endpoints can reflect both within-run dynamics and changes in the set of contributing runs. The reported minimum alignment and ranges of run-wise maximum discrepancy are computed from individual runs, rather than from these averaged curves. We also record buffer-update alignment at every update: Ct:=⟨Bt,Ot⟩‖Bt‖F.C_t:= B_t,O_t \|B_t\|_F. (77) The reference Ct≥κ=2/3C_t≥κ=2/3 follows from the tuned Newton–Schulz map in exact arithmetic, independently of network width. In contrast, the current-gradient bound At≥κ/2A_t≥κ/2 additionally requires the trajectory assumptions of Lemma 3.2. For the matrix-map comparison, buffers are saved from student seed 10 at geometrically spaced updates and at the final update, yielding 59 buffers across the tested momentum values. These measurements characterize the saved buffers; they do not constitute independent training runs. The fixed-step comparison uses η=η0≈1.54×10−4η= _0≈ 1.54× 10^-4, target 10−210^-2, and horizon 50,00050,000 for μ∈0,0.5,0.9,0.95,0.99μ∈\0,0.5,0.9,0.95,0.99\. All three student seeds at each momentum reach the target, with hitting times ranging from 14,680 to 25,444 updates. These runs show that the prescribed (1−μ)(1-μ) learning-rate scaling can be conservative for the tested problem; they do not establish a generally valid momentum-independent step size. E.3 Finite Newton–Schulz Maps and the Exact Polar Factor We compare three transformations on identical nonzero momentum buffers saved from tuned Muon trajectories: the tuned five-step Newton–Schulz map, five classical cubic Newton–Schulz iterations, and the exact polar factor evaluated numerically by SVD. Both iterative maps start from X0=B/‖B‖FX_0=B/\|B\|_F. The classical recurrence is Xk+1=32Xk−12XkXk⊤Xk,k=0,…,4,X_k+1= 32X_k- 12X_kX_k X_k, k=0,…,4, (78) corresponding to d=1d=1 in (70). Although Proposition 2 also covers higher-degree classical polynomials, the empirical comparison here uses only the cubic map. Evaluating each transformation on the same buffers isolates its effect from differences in training trajectories. We compute the SVD using numpy.linalg.svd and retain singular values satisfying sj>max(d,m)ϵfloat64smaxs_j> (d,m) _float64s_ , where ϵfloat64 _float64 is machine precision. The numerical polar update is UrVr⊤U_rV_r , formed from the retained singular-vector pairs. Across the 59 saved buffers, the discarded singular values account for at most 8×10−158× 10^-15 of the nuclear norm. Thus, truncation has negligible effect on the alignment comparison at the reported precision. For each buffer B and transformed update O, we evaluate a(B,O):=⟨B,O⟩‖B‖F,s(O):=‖O‖2,q(B,O):=⟨B,O⟩‖B‖∗‖O‖2.a(B,O):= B,O \|B\|_F, s(O):=\|O\|_2, q(B,O):= B,O \|B\|_*\|O\|_2. (79) The quantities a and s examine the alignment and norm bounds used in the training proof. The ratio q measures alignment per unit spectral norm relative to the optimum in Proposition 3; the exact polar factor attains q=1q=1. These quantities do not measure distance to the polar factor. Figure 4 displays the measurements on the 59 buffers from student seed 10. Tuned NS5 has a∈[0.697,2.690]a∈[0.697,2.690], with median 2.6872.687, and s∈[0.696,1.202]s∈[0.696,1.202]. Thus, all sampled buffers satisfy the analytical references a≥2/3a≥ 2/3 and s≤5/4s≤ 5/4. Its normalized ratio lies in q∈[0.748,0.999]q∈[0.748,0.999], with median 0.7640.764 and standard deviation 0.0750.075 across buffers. Classical cubic NS5 has s=1s=1 to the reported precision and q∈[0.860,0.998]q∈[0.860,0.998], with median 0.8600.860 and standard deviation 0.0430.043. The numerical polar update has s=1s=1 and q=1q=1 to the reported precision. The classical cubic map therefore achieves a higher median alignment-per-norm ratio on these sampled buffers, while the tuned map retains the properties sufficient for the training guarantee. The medians and standard deviations summarize correlated buffers from the saved trajectories, not variability across independent datasets. This comparison establishes neither a ranking of training performance nor which map more closely approximates the polar factor. E.4 Width, Displacement, and Kernel Diagnostics We vary the student width over m∈64,128,256,512,1000,2000m∈\64,128,256,512,1000,2000\ while holding the dataset, teacher, target loss, momentum, and prescribed learning rate fixed. Each width uses student seeds 10–14, giving 30 runs in total. We set ε=10−2 =10^-2, μ=0.95μ=0.95, and the practical horizon to 1,414,0001,414,000 updates. For this dataset, λ0=0.335 _0=0.335 and R0=30.2R_0=30.2. Kernel and displacement diagnostics are recorded at every iteration through target attainment or horizon exhaustion. Alongside KtK_t and StS_t in (30), we measure Pt:=‖Wt−W0‖F,R:=18MnR0καλ0,P^t:=PtR.P_t:=\|W_t-W_0\|_F, R_B:= 18M n\,R_0κα _0, P_t:= P_tR_B. (80) The radius is R≈7.88×103R_B≈ 7.88× 10^3 and is shared across the width sweep. For each run, we compute the minimum KtK_t, maximum StS_t, and maximum P^t P_t over the recorded trajectory. Summary points and error bars report the mean and one sample standard deviation of these run-wise extrema across the five student initializations, with equal weight assigned to each run. All 30 runs reach the target loss within the practical horizon. The minimum normalized kernel eigenvalue has mean 0.871±0.0300.871± 0.030 at width 64 and 0.990±0.0120.990± 0.012 at width 2000. The smallest value recorded across all runs is 0.8260.826, above the analytical reference 1/21/2. The maximum relative kernel change decreases from 0.143±0.0470.143± 0.047 at width 64 to 0.031±0.0070.031± 0.007 at width 2000 (Figure 3). The largest normalized displacement across all runs is 1.67×10−31.67× 10^-3, attained at width 2000 (Figure 5). Thus, every observed trajectory remains far inside the analytical neighborhood while maintaining kernel positivity. The small relative displacement and reduced kernel variation at larger widths are consistent with the stability mechanism used in the proof. These observations concern repeated student initializations on one fixed dataset and teacher. They do not establish the necessity or tightness of the sufficient width condition. In particular, containment within the analytical radius at these widths does not itself certify the uniform kernel bounds, and the measured kernel diagnostics do not verify every Jacobian-action and linearization estimate used in the analysis.