Muon Attains O(ε−3) Iteration Complexity under Shuffling
Authors: Kun Huang, Shi Pu, Karl Henrik Johansson
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
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 O(ε−3) 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 O(ε−4) 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 β∈[0,1), 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
O(ε−4) [ 8 ]
O(ε−3) [ 33 , 35 ]
SGDM
O(ε−4) [ 30 ]
O(ε−3) [ 43 ]
Adam
O(ε−4) [ 14 ]
neighborhood † [ 55 ]
Muon
O(ε−4) [ 25 , 48 , 52 ]
O(ε−3) (this work) ‡
Table 1: Iteration complexity for finding an ε -stationary point in smooth nonconvex problems. Stationarity is measured in the nuclear norm for Muon and in the Euclidean norm for the other methods.
Figure 1: Iteration indices and state transitions in Algorithm 1 , illustrated for N=3 with two example permutations. The upper boxes label updates. The lower boxes show the parameter and momentum states before each update.
random partition
sorted partition
β=0.9
β=0.99
β=0.9
β=0.99
f
∥∇f∥∗
f
∥∇f∥∗
f
∥∇f∥∗
f
∥∇f∥∗
RR
0.1040
0.087
0.0601
0.061
0.1447
0.149
0.0671
0.087
SO
0.1042
0.092
0.0601
0.070
0.1468
0.156
0.0668
0.079
IG
0.1050
0.083
0.0600
0.059
2.2654
1.154
0.3523
0.856
with replacement
0.1049
0.099
0.0638
0.079
0.1475
0.176
0.0711
0.092
Table 2: Final training loss f(WT) and gradient norm ∥∇f(WT)∥∗ for an MLP on MNIST. Values are medians over three random seeds; IG is deterministic and was run once. The lowest value in each column is shown in bold.
Figure 2: Training loss f(Wt) under four sampling schemes with β=0.95 . Curves show the median over three seeds, and shaded bands show the range across seeds. Left: ResNet-18 on CIFAR-10 with B=125 ( N=400 ). Right: GPT-2 small on FineWeb-Edu with B=32 ( N=9155 ).
Figure 3: The counterexample in ( 20 ) under RR. Left: final objective gap f(WT)−f∗ , shown as the median over five seeds. Right: objective gap f(Wt)−f∗ over the course of training for N=9,33,129,513 and four momentum coefficients, shown as the median over ten seeds.
Figure 4: Final training loss f(WT) for the MLP on MNIST under RR, with η=3×10−4 and T=2×104 . Values are medians over three seeds. Left: heatmap over N=S/B and β , with empirical level curves. Right: the same values plotted against β for each N .
Figure 5: Training loss f(Wt) for the MLP on MNIST under IG with the sorted partition ( B=100 ), plotted against the cumulative stepsize. Left: separate runs for each (β,η) . Right: the run with β=0.9 and η=3×10−4 , continued from the plateau (black dot) using each (β,η) pair.
Figure 6: Final training loss f(WT) under RR across values of (β,η) . Left: MNIST with B=100 and a random partition, T=2×104 ; values are medians over three seeds. Right: GPT-2 small trained for one epoch ( T=9155 ); results are from one seed.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: One epoch whose gradient-evaluation points lie in [−1,1] , for K=2 ( N=9 ), with a=3 (top), a=1 (middle), and a=7 (bottom) inputs −1 before the large input N . The top row has a≥K , the middle row a<K , and the bottom row 4K−a<K ; the top and middle rows have 4K−a≥K . The braces mark the runs of inputs −1 , and the small numbers index the updates of the epoch. Shaded updates may have nonnegative momentum: at most K−1 before the large input and at most K from it on.
Figure 8: Final gap f(WT)−f∗ on the counterexample under SO (left) and IG (right).
Muon has demonstrated strong empirical performance in large-scale language-model training, motivating a deeper theoretical understanding of its practical implementation. Unlike the idealized polar-factor update, practical Muon employs a fixed number of quintic Newton-Schulz iterations. Existing analyses primarily establish average- or best-iterate stationarity guarantees, while last-iterate convergence remains less understood. In this work, we investigate last-iterate gradient convergence of practical finite-step Muon on smooth, lower-bounded nonconvex objectives. In the deterministic setting, we show that Muon without input stabilization can exhibit cyclic behavior even on a smooth convex quadratic. In contrast, with positive stabilization, we establish last-iterate gradient convergence and square-summability of gradients for any fixed momentum coefficient below one and a sufficiently small constant learning rate. In the stochastic setting, we first demonstrate that persistent bounded, unbiased noise can prevent convergence under fixed learning rates and momentum, even with positive stabilization. We then establish almost-sure and mean-square last-iterate gradient convergence under bounded-variance stochastic gradients by combining diminishing learning rates with increasing momentum. Finally, we construct a smooth counterexample demonstrating that neither convergence theorem implies a pointwise polynomial convergence rate. Nevertheless, we establish density-one convergence rates, guaranteeing polynomial gradient decay for all but an asymptotically vanishing fraction of iterations.
Ping Li, Vincent Y. F. Tan
V. Y. F. Tan is also with the Department of Electrical and Computer Engineering, NUS.
Muon orthogonalizes the momentum buffer before each update, replacing its singular values with ones via Newton-Schulz iterations. This simple change lets Muon tolerate far larger learning rates and converge faster than other optimizers, but why? We show that the mechanism is spectral flattening, and develop two results around it. First, we prove that Muon's maximal stable step size scales with the average singular value of the gradient rather than the largest, which bottlenecks standard gradient descent. Second, we recast Muon as a preconditioned gradient method and show, under a Kronecker-factored curvature model, that it improves the effective convergence factor, with the improvement controlled by the spectrum of the gradient covariance. Extensive experiments validate both results: Muon remains stable at learning rates that cause SGD to diverge within the first few iterations, and reaches accuracy milestones several epochs earlier even at identical step sizes. Taken together, our results offer a principled, geometric explanation for Muon's empirical success.
Hanoi University of Science and Technology Hanoi, Vietnam · Indiana University 107 S. Indiana Ave, Bloomington, IN 47405, USA · Monash University Clayton, VIC 3800, Australia
Muon has emerged as a strong optimizer for the matrix-valued parameters in large language model pretraining, approximately orthogonalizing its momentum with a few Newton-Schulz iterations. Existing theory either replaces this iteration with the exact polar factor it approximates, or treats its finite depth as an approximation error, and thus the iteration Muon actually runs can only hurt the guarantees. We show that finite Newton-Schulz can instead be beneficial for nonsmooth nonconvex optimization. To this end, we analyze Muon through the online-to-nonconvex conversion, which views the update rule as an online learner and converts its regret bound into a stationarity guarantee. The finite Newton-Schulz iteration smooths the discontinuous polar map into a Lipschitz map of the singular values, and Muon with finite Newton-Schulz can be regarded as an online learner with a smoothed spectral potential. This smoothing is exactly what the conversion needs: we prove that a Newton-Schulz depth growing only logarithmically in the target accuracy suffices for convergence to stationary points in nonsmooth nonconvex optimization, whereas Muon with the exact-polar update may fail to converge. The resulting sample complexity bounds match the best-known guarantees for nonsmooth nonconvex optimization and are optimal for smooth nonconvex optimization up to problem-dependent factors. The argument extends beyond Newton-Schulz to general spectral maps with the same smoothing property.
Mingyi Li, Taira Tsuchiya
The University of Tokyo · The University of Tokyo and RIKEN