Search papers, labs, and topics across Lattice.
This paper establishes a finite-time training guarantee for Muon, addressing the open question of whether its five tuned Newton-Schulz steps suffice to reach a prescribed neural-network training loss, unlike prior analyses that assumed exact orthogonalization or only guaranteed stationarity. For sufficiently wide two-layer ReLU networks, it proves that Muon can reach any target empirical squared loss $\varepsilon>0$ with high probability, with a hitting-time bound of $O((1-\mu)^{-1}\varepsilon^{-1/2})$ for a target-dependent learning rate. The analysis reveals that the tuned Newton-Schulz map maintains alignment with the momentum buffer and bounds the update's spectral norm, ensuring descent without exact orthogonalization.
Muon's finite-step orthogonalization provably guarantees reaching any target training loss for wide networks, resolving a key theoretical gap.
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.
