Muon Attains Iteration Complexity under Shuffling
Organizations: KTH Royal Institute of Technology, Department of Decision and Control Systems (DCS), Digital Futures, Stockholm, Sweden · The Chinese University of Hong Kong, Shenzhen, School of Data Science (SDS), Shenzhen, Guangdong, China
Abstract
Muon is a stochastic first-order optimizer for matrix-valued parameters. It maintains an exponential moving average of stochastic gradients in a momentum buffer with coefficient , and orthogonalizes the buffer to obtain the update direction. Muon has been reported to accelerate and stabilize the training of large language models. In practice, it is often used with shuffling (sampling without replacement), where each epoch visits the components of a finite-sum objective in a permuted order. However, its iteration complexity in this setting remains open. We analyze Muon under shuffling, with the momentum buffer orthogonalized by the polar map. For smooth nonconvex finite-sum problems, we establish an iteration complexity for finding an -stationary point. This guarantee holds for every sequence of permutations, covering random reshuffling, shuffle once, and the incremental gradient method. This complexity matches that of stochastic gradient descent under shuffling in its dependence on , and improves on Muon's complexity under sampling with replacement. Our guarantee requires a problem-dependent that approaches one as the number of components grows. In contrast, no fixed guarantees convergence to stationarity for every number of components. We show this by constructing a family of smooth convex problems on which, for any fixed , Muon remains bounded away from stationarity once the number of components is sufficiently large. This failure occurs for every sequence of permutations and persists even with small stepsizes. These results suggest two practical tuning rules: if the training loss stops decreasing even after reducing the stepsize, increase ; when increasing , reduce the stepsize accordingly.
Figures & tables
| Sampling with replacement | Shuffling | |
|---|---|---|
| SGD | [ 8 ] | [ 33 , 35 ] |
| SGDM | [ 30 ] | [ 43 ] |
| Adam | [ 14 ] | neighborhood † [ 55 ] |
| Muon | [ 25 , 48 , 52 ] | (this work) ‡ |
| random partition | sorted partition | |||||||
| RR | ||||||||
| SO | ||||||||
| IG | ||||||||
| with replacement | ||||||||
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Muon Optimizer
Muon optimizer uses momentum and matrix orthogonalization to shape neural-network updates, especially in large language-model training.
See all 159 papers