論文の概要: Muon Attains $\mathcal{O}(\varepsilon^{-3})$ Iteration Complexity under Shuffling
- arxiv url: http://arxiv.org/abs/2611.18124v1
- Date: Fri, 13 Nov 2026 12:52:59 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-11-16 19:30:57.165291
- Title: Muon Attains $\mathcal{O}(\varepsilon^{-3})$ Iteration Complexity under Shuffling
- Title(参考訳): Muon はシャッフルの下で $\mathcal{O}(\varepsilon^{-3})$イテレーション複素数を得る
- Abstract要約: Muon は行列パラメータの1階数である。
Muonは大規模言語モデルの高速化と安定化が報告されている。
シャッフル中のミューオンを交換せずに解析する。
- 参考スコア(独自算出の注目度): 14.669194533990725
- License:
- 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 $\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 $\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 $β\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.
- Abstract(参考訳): Muon は行列値パラメータの確率的一階最適化器である。
運動量バッファ内の確率勾配の指数的な移動平均を係数$β$で維持し、バッファを直交して更新方向を得る。
Muonは、大規模な言語モデルのトレーニングを加速し、安定化することが報告されている。
実際には、これはシャッフルリング(置換のないサンプリング)でよく使用され、各エポックは置換順序で有限サム対象の成分を訪問する。
しかし、この設定でのイテレーションの複雑さは未解決のままである。
我々は、モーメントバッファを極写像で直交させ、シャッフル中のムオンを解析する。
滑らかな非凸有限サム問題に対して、$\mathcal{O}(\varepsilon^{-3})$の反復複雑性を確立して、$\varepsilon$-定常点を求める。
この保証は、全ての順列を保ち、ランダムな再シャッフル、シャッフル1回、インクリメンタル勾配法をカバーしている。
この複雑性はシャッフィングの下での確率勾配降下の値と一致し、ムオンの$\mathcal{O}(\varepsilon^{-4})$複雑性を置換したサンプリングで改善する。
私たちの保証には、コンポーネントの数が増えるにつれてアプローチする問題依存の$β$が必要です。
対照的に、固定$β$は各成分の定常性への収束を保証するものではない。
このことは、任意の固定された$β\in[0,1)$に対して、成分の数が十分に大きいとき、ムオンは定常性から遠ざかっているような滑らかな凸問題の族を構成することによって示される。
この失敗は置換のシーケンスごとに発生し、小さなステップサイズでも持続する。
これらの結果から,段階的縮小後のトレーニング損失が減少しなくなった場合,β$が増加し,β$が増加すると段階的減少が減少することが示唆された。
関連論文リスト
- Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization [0.0]
我々は,1つのエルゴード連鎖に対する非制約モンテカルロ最適化を新たに提案する。
特に、一般化されたCarlo-Wolfevious gradient $MC-ALFCFCを用いてプロジェクションフリー設定に対処する。
本手法は,期待されるサンプルの複雑さを$widetildeO(_mathrmmix2G_+_mathrmmix5G_2)varepsilon-3+_mathrmmix5varepsilon-2で実現することを示す。
論文 参考訳(メタデータ) (2026-07-28T14:37:47Z) - SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳(メタデータ) (2026-06-14T14:11:07Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳(メタデータ) (2024-05-10T09:58:47Z) - Untangling Lariats: Subgradient Following of Variationally Penalized Objectives [10.043139484808949]
本稿では,不規則なペナルティを伴う凸問題の最適解を段階的に追従する装置について述べる。
我々は,このアプローチの特殊な場合として,溶存ラッソや等調回帰といった既知のアルゴリズムを導出する。
そこで我々は,任意の畳み込みフィルタによって特徴づけられる変分罰則の段階的追従のための格子ベースの新しい手順を導出した。
論文 参考訳(メタデータ) (2024-05-07T23:08:24Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。