Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization
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 with high probability over initialization. For every momentum parameter μ∈[0,1), a target-dependent constant learning rate proportional to (1−μ)√ε yields a hitting-time bound of 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.
Related
- Learning in Inverse Games: Tractable Training with Probabilistic Guarantees
- Statistically Valid Post-Training Hyperparameter Selection: From Tuning to Guarantees
- Grad-div stabilized finite element Picard-Newton iterative methods for the Navier-Stokes equations
- Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
- Operator Calculus for Population-Based Optimization: Modular Convergence and Finite-Population Guarantees
BibTeX
@misc{roy2026trainingloss,
title = {{Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization}},
author = {Amartya Roy and Souvik Chakraborty},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03306},
eprint = {2610.03306},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03306},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization
AU - Amartya Roy
AU - Souvik Chakraborty
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03306
UR - https://arxiv.org/abs/2610.03306
AB - 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 with high probability over initialization. For every momentum parameter μ∈[0,1), a target-dependent constant learning rate proportional to (1−μ)√ε yields a hitting-time bound of 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.
ER -