math.OCNov 13, 2026

Muon Attains O(ε−3)\mathcal{O}(\varepsilon^{-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

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 O(ε−3)\mathcal{O}(\varepsilon^{-3}) iteration complexity for finding an ε\varepsilon-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 ε\varepsilon, and improves on Muon's O(ε−4)\mathcal{O}(\varepsilon^{-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)β\in[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

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Last-Iterate Stationarity of Muon with Finitely Many Newton-Schulz Iterations

    Oct 25, 2026Ping Li, Vincent Y. F. TanMuon OptimizerLast-Iterate Convergence

  2. Spectral Flattening Is All Muon Needs: How Orthogonalization Controls Learning Rate and Convergence

    May 13, 2026Tien-Phat Nguyen, Truong Nguyen, Minh-Phuc Truong +3Momentum MethodsGradient Descent

  3. Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization

    Aug 26, 2026Mingyi Li, Taira TsuchiyaMuon OptimizerNewton-Schulz Iteration