betaFeedback

WorksMathematics

Muon Attains O(ε−3)\mathcal{O}(\varepsilon^{-3}) Iteration Complexity under Shuffling

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.

Paper details

vlnc:W_sfhmzfhw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…