跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.18124 · v1

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

首次提交 2026-11-13 20:52
版本更新 2026-11-13 20:52
雷达观测 2026-11-16 11:41
arXiv ↗PDF ↗

摘要

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.

作者备注:25 pages, 14 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-13 20:52 · 最新观测版本

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

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.

查看此版本解读 →查看此版本原文 ↗