Abstract
Muon is a matrix-aware optimizer that utilizes gradient orthogonalization via Newton-Schulz iteration, treating neural network parameters as matrices rather than flattened vectors. While Muon has demonstrated significant empirical gains over AdamW, a rigorous theoretical foundation was previously lacking. This paper provides the first convergence proofs for Muon and its variants, including Nesterov momentum and weight decay. We identify a critical stability condition where the learning rate must not exceed the inverse of the weight decay coefficient ($\eta \leq 1/\lambda$). Furthermore, we derive the "critical batch size"—the optimal point for balancing training speed and computational cost. Our results, validated on ResNet-18 and Llama 3.1, show that Muon offers superior scaling properties, particularly for large-scale distributed training.
Introduction
Standard deep learning optimizers like SGD and AdamW treat weight matrices as high-dimensional vectors, ignoring the inherent geometric structures of neural network layers. The Muon optimizer, recently introduced by Jordan et al. (2024), addresses this by employing gradient orthogonalization. Instead of following the raw gradient, Muon updates weights in the direction of the closest orthogonal matrix. Despite its empirical success, the theoretical mechanisms driving its convergence and scaling efficiency remained unmapped. This work fills this gap by providing a comprehensive analysis of Muon’s convergence properties and deriving its optimal hyperparameter configurations.
Theoretical Framework
We analyze four primary variants of the Muon optimizer: Vanilla Muon, Muon with Nesterov Momentum, Muon with Weight Decay, and the combined Muon + Nesterov + Weight Decay setup. To ensure practical relevance, our proofs account for the Newton–Schulz iteration, which Muon uses to approximate orthogonalization without the prohibitive cost of Singular Value Decomposition (SVD).
By applying the Stochastic First-Order Oracle (SFO) complexity framework, we determine the "critical batch size" ($b^*$). This metric identifies the threshold beyond which increasing the batch size yields diminishing returns in training speed relative to hardware expenditure.
Stability and Search Directions
A key theoretical finding is the necessity of weight decay for Muon's stability. Unlike SGD, where weight decay is primarily a regularizer, in Muon it serves as a fundamental constraint. We prove that the learning rate $\eta$ must satisfy $\eta \leq 1/\lambda$. Exceeding this threshold leads to an explosion in the gradient norm and training instability.
Additionally, because Muon utilizes orthogonal matrices for updates, its search directions are inherently bounded. This property allows for convergence proofs that do not rely on the often-unrealistic "bounded gradient" assumption common in optimization theory.
Empirical Performance and Scaling
Our experiments across computer vision (ResNet-18 on CIFAR-10) and language modeling (Llama 3.1 on C4) confirm our theoretical predictions. Muon variants consistently achieve lower final loss than AdamW within identical token budgets.
We derived a concrete formula for the critical batch size ($b^*$). For the Nesterov + Weight Decay variant, it is approximately: $$b^* \approx \frac{\{(2\beta + 1)(1 - \beta) + \lambda\} \sigma^2}{\epsilon}$$ where $\sigma^2$ represents gradient variance and $\epsilon$ is the target precision. We observed a unique interplay between momentum and batch size: increasing momentum ($\beta \to 1$) decreases the critical batch size, while Nesterov momentum and weight decay increase it. This suggests that Muon is particularly well-suited for massive-scale distributed training, as the performance gap between Muon and AdamW widens at larger batch sizes.
Conclusion and Future Work
This paper establishes the theoretical groundwork for Muon, identifying its stability requirements and optimal scaling laws. While Muon is algorithmically more efficient than AdamW, it introduces system-level overhead in sharded environments due to additional gradient communication steps. Future work should focus on optimizing these communication patterns and verifying these theoretical bounds on frontier models exceeding 70 billion parameters.
Summary updated