Convergence Bound and Critical Batch Size of Muon Optimizer
Naoki Sato [email protected], Hiroki Naganuma [email protected], Hideaki Iiduka [email protected] · 2025
Read Convergence Bound and Critical Batch Size of Muon Optimizer by Naoki Sato [email protected], Hiroki Naganuma [email protected], Hideaki Iiduka [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01598.txt.
Introduction
Naoki Sato and co-authors prove how a new training optimizer settles and scales in a 2025 paper. The optimizer, called Muon, uses the matrix shape of network weights and has beaten standard tools in practice. Theory had lagged behind those gains, leaving users to guess at settings.
Proofs cover four setups, with and without momentum tricks and weight decay. Decay alone keeps weights and slopes bounded, with no need for the usual blanket assumption. The team also derives how the ideal batch size scales with momentum and decay settings. Tests on image and language tasks match those scaling calls, guiding real training runs.
Catalog record
| CREATOR | Naoki Sato [email protected], Hiroki Naganuma [email protected], Hideaki Iiduka [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01598
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence Bound and Critical Batch Size of Muon Optimizer Naoki Sato [email protected], Hiroki Naganuma [email protected], Hideaki Iiduka [email protected] 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. Our analysis covers the standard configuration using both, thereby elucidating its real-world performance. We then demonstrate that the addition of weight decay yields strictly tighter theoretical bounds and clarify the interplay between the weight decay coefficient and the learning rate. Finally, we derive the critical batch size for Muon that minimizes the computational cost of training. Our analysis identifies the hyperparameters governing this value, and our experiments validate the corresponding theoretical findings. † † firstpage: 1 1 Introduction Optimization algorithms are fundamental to the training of deep neural networks (DNNs). Since the introduction of stochastic gradient descent (SGD) Robbins1951Ast , numerous optimizers have been proposed to accelerate convergence. Among these, adaptive gradient algorithms such as Adam Kingma2015Ame and its subsequent variant AdamW Loshchilov2019Dec have emerged as the de facto standard in modern deep learning, valued for their rapid convergence and robust performance across a wide range of tasks. A common characteristic of these widely used first-order optimizers is that they treat the weight parameters of neural networks, which are inherently matrices or higher-order tensors, as high-dimensional vectors. However, this vector-based perspective, while effective, disregards the underlying geometric and algebraic structure within the parameter matrices. The recently proposed Muon optimizer jordan2024muon introduces a distinct paradigm that departs from the conventional vector-based viewpoint. The core idea of Muon is to preserve and leverage the intrinsic matrix structure of the network parameters. Instead of using the gradient vector, Muon computes its search direction by orthogonalizing the gradient momentum matrix. Specifically, for a given momentum matrix C_{t}\in\mathbb{R}^{m\times n} , the search direction O_{t}\in\mathbb{R}^{m\times n} is the orthogonal matrix that is closest in Frobenius norm, found by solving \displaystyle O_{t}:=\underset{O\in\left\{O\in\mathbb{R}^{m\times n}:O^{\top}O=I_{n}\right\}}{\operatorname{argmin}}\|O-C_{t}\|_{\rm{F}}, (1) where I_{n} denotes a n\times n identity matrix. As established by classic matrix theory, if the singular value decomposition (SVD) of C_{t} is U_{t}S_{t}V_{t}^{\top} , the optimal search direction is simply O_{t}=U_{t}V_{t}^{\top} , where U_{t}\in\mathbb{R}^{m\times r},S_{t}\in\mathbb{R}^{r\times r},V_{t}\in\mathbb{R}^{n\times r} , and r>0 is the rank of C_{t} . This process of gradient orthogonalization is aimed at finding a search direction that is independent of the gradient’s magnitude, potentially leading to more stable and effective training dynamics. While SVD provides an exact analytical solution, its high computational cost renders it impractical for the large matrices found in modern DNNs. As detailed by Bernstein Bernstein2025Der , the key computational innovation of Muon is the use of the Newton–Schulz iteration Bernstein2024Old ; Higham2008Fun ; Bjorck1971AnI ; Kovarik1970Som , a classic and remarkably efficient numerical method, to approximate this orthogonalization. This iterative algorithm enables Muon to compute the search direction without performing an explicit SVD, making it a computationally feasible optimizer for large-scale applications. This elegant fusion of a novel optimization perspective with a powerful numerical technique positions Muon as a promising, theoretically grounded alternative to existing optimizers. Several studies have reported the strong empirical performance of Muon. jordan2024muon showed that Muon outperforms Shampoo Gupta2018Sha and SOAP Vyas2025SOA , both on a per-step and wall-clock basis. Liu2025COS showed that by dividing the parameters and updating them with SOAP and Muon, optimization performance equivalent to or better than SOAP can be achieved while substantially reducing memory usage. Liu2025Muo demonstrated that Muon is effective for training large-scale LLMs and suggested it has the potential to replace AdamW as the standard optimizer. Ess2025Pra showed that Muon expands AdamW’s Pareto frontier on the compute–time plane, enlarging the practitioner’s flexibility in resource allocation. However, the theoretical understanding of Muon’s convergence behavior remains underdeveloped, and a formal justification for its strong performance over AdamW is still lacking. This work aims to bridge this gap by providing a rigorous convergence analysis of Muon. Furthermore, since the batch size is a critical hyperparameter for managing computational costs in large-scale training, we also consider Muon’s critical batch size. This is defined as the batch size that minimizes the computational cost of training. In other words, the critical batch size is the point at which further increases in batch size yield diminishing returns in hardware throughput (i.e., the number of samples processed per unit time). By understanding and utilizing the critical batch size, one can maximize GPU utilization, thereby shortening training times and reducing overall computing costs. Therefore, to theoretically understand Muon and maximize its performance, analyzing its critical batch size is essential. Following previous studies, we aim to clarify the critical batch size of Muon. Table 1: Upper bound of \frac{1}{T}\sum_{t\in[T]}\mathbb{E}\left[\|\nabla f(W_{t})\|_{\rm{F}}\right] . See Section 2 for notation. w/o weight decay w/ weight decay w/o Nesterov \mathcal{O}\left(\frac{1}{T}+\frac{1-\beta}{b}+n\right) (Theorem 3.1 (i)) \mathcal{O}\left(\frac{1}{T}+\frac{1-\beta+\frac{\lambda}{2}}{b}+n\right) (Theorem 3.2 (i)) w/ Nesterov \mathcal{O}\left(\frac{1}{T}+\frac{(2\beta+1)(1-\beta)}{2}\cdot\frac{1}{b}+n\right) (Theorem 3.1 (ii)) \mathcal{O}\left(\frac{1}{T}+\frac{(2\beta+1)(1-\beta)+\lambda}{2}\cdot\frac{1}{b}+n\right) (Theorem 3.2 (ii)) Our main contributions are as follows: • We present a convergence analysis for four variants of Muon-with and without Nesterov momentum and with and without weight decay (Theorems 3.1 and 3.2 ). For each variant, we establish an upper bound on the average expected gradient norm, summarized in Table 1 . The variant combining both Nesterov momentum and weight decay is of particular interest as it mirrors common practical settings. Our analysis thus offers direct insights into Muon’s real-world behavior. • We prove that incorporating weight decay yields tighter theoretical bounds on both the parameter and gradient norms (Propositions 3.1 and 3.2 ) and present experimental results to support this finding. We also show that for Muon to converge, the learning rate \eta and weight decay coefficient \lambda must satisfy \eta\leq\frac{1}{\lambda} , a condition supported by our experimental results. • We derive the critical batch size for the four Muon variants (Proposition 4.3 ). For example, we show that the critical batch size of Muon with Nesterov momentum and weight decay is given by \displaystyle b_{\text{Muon}}^{\star}=\frac{\left\{(2\beta+1)(1-\beta)+\lambda\right\}\sigma^{2}}{\epsilon}, where \beta\in(0,1] is momentum, \lambda>0 is the weight decay coefficient, \sigma^{2}>0 is the variance of the stochastic gradient, and \epsilon>0 is the threshold or stopping condition. While not fully predictive due to its reliance on several unknown parameters, our theoretical analysis produces a formula for the critical batch size that successfully identifies the hyperparameters governing this value, as validated by our empirical results. 2 Preliminaries 2.1 Notations and Definition Let \mathbb{N} be the set of nonnegative integers. For p\in\mathbb{N}\setminus\{0\} , define [p]:=\{1,2,\ldots,p\} . Let \mathbb{R}^{d} be a d -dimensional Euclidean space. We use lowercase letters for scalars (e.g., a\in\mathbb{R}) , bold lowercase letters for vectors (e.g., \bm{a}\in\mathbb{R}^{d} ), and uppercase letters for matrices (e.g., A\in\mathbb{R}^{m\times n} ). \bm{a}^{\top}\in\mathbb{R}^{1\times d} and A^{\top}\in\mathbb{R}^{n\times m} denote the transposes of \bm{a}\in\mathbb{R}^{d} and A\in\mathbb{R}^{m\times n} , respectively. For a square matrix A=(a_{ij})\in\mathbb{R}^{n\times n} , the trace is defined as \operatorname{tr}(A):=\sum_{i=1}^{n}a_{ii} . For all vectors \bm{x},\bm{y}\in\mathbb{R}^{d} , the Euclidean inner product is defined as \langle\bm{x},\bm{y}\rangle_{2}:=\bm{x}^{\top}\bm{y} and the Euclidean norm is defined as \|\bm{x}\|_{2}:=\sqrt{\langle\bm{x},\bm{x}\rangle}_{2} . For all matrices A,B\in\mathbb{R}^{m\times n} , the Frobenius inner product is defined as