Analysis of Muon's Convergence and Critical Batch Size

Naoki Sato, Hiroki Naganuma, Hideaki IidukaarXiv 2025 · DOI · arXiv

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.

Muon stability analysis showing the gradient norm explosion and loss increase when the learning rate exceeds $1/\lambda$.

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.

Training loss and gradient norm comparison on ResNet-18, demonstrating Muon's faster convergence compared to AdamW and Momentum SGD.

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

Abstract

Muon, a recently proposed optimizer that leverages the inherent matrix structure of neural network parameters, has demonstrated strong empirical performance, indicating its potential as a successor to standard optimizers such as AdamW. This paper presents theoretical analysis to support its practical success. We provide convergence proofs for Muon across four practical settings, systematically examining its behavior with and without the inclusion of Nesterov momentum and weight decay. We then demonstrate that the addition of weight decay ensures almost-sure boundedness of the parameter and gradient norms -- without relying on the commonly imposed bounded-gradient assumption -- and clarify the interplay between the weight decay coefficient and the learning rate. Finally, we derive a lower bound on the critical batch size for Muon -- the batch size that minimizes the stochastic first-order oracle (SFO) complexity of training. Because the resulting formula involves problem-dependent quantities that are not directly observable (gradient variance, target precision, effective rank), it does not predict the critical batch size in absolute terms; rather, it reveals how the hyperparameters $β$ (momentum) and $λ$ (weight decay) govern the qualitative scaling of this value. Our experiments validate these hyperparameter-dependent predictions across workloads including image classification and language modeling.
BibTeX
@misc{sato2025analysis,
  author = {Naoki Sato and Hiroki Naganuma and Hideaki Iiduka},
  title = {{Analysis of Muon's Convergence and Critical Batch Size}},
  year = {2025},
  eprint = {2507.01598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.01598},
}
Figure