論文の概要: When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds
- arxiv url: http://arxiv.org/abs/2605.06615v1
- Date: Thu, 07 May 2026 17:32:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-08 22:27:12.046085
- Title: When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds
- Title（参考訳）: SignSGDがSGDを上回る時期と理由:$\ell_1$-norm下界に基づく理論的研究
- Authors: Hongyi Tao, Dingzhi Yu, Lijun Zhang,
- Abstract要約: SignSGDやMuonのような符号ベースの最適化アルゴリズムは、大規模な基礎モデルのトレーニングにおける顕著なパフォーマンスに対して大きな注目を集めている。
そこで,SignSGD は Emphsparse ノイズ下での $d$ の係数で,問題次元が $d$ であるような複雑性を効果的に低減することを示す。
- 参考スコア（独自算出の注目度）: 15.724495678714007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sign-based optimization algorithms, such as SignSGD and Muon, have garnered significant attention for their remarkable performance in training large foundation models. Despite this empirical success, we still lack a theoretical understanding of when and why these sign-based methods outperform vanilla SGD. The core obstacle is that under standard smoothness and finite variance conditions, SGD is known to be minimax optimal for finding stationary points measured by $\ell_2$-norms, thereby fundamentally precluding any complexity gains for sign-based methods in standard settings. To overcome this barrier, we analyze sign-based optimizers leveraging $\ell_1$-norm stationarity, $\ell_\infty$-smoothness, and a separable noise model, which can better capture the coordinate-wise nature of signed updates. Under this distinct problem geometry, we derive matched upper and lower bounds for SignSGD and explicitly characterize the problem class in which SignSGD provably dominates SGD. Specifically, we compare the \emph{upper bound of SignSGD} with the \emph{lower bound of SGD}, illustrating that SignSGD effectively reduces the complexity by a factor of $d$ under \emph{sparse noise}, where $d$ is the problem dimension. Furthermore, we elevate this framework to the matrix domain, providing an equivalent optimal lower bound for the Muon optimizer, proving that extending the sign operator to matrices preserves this optimal scaling with dimensionality. Finally, we bridge our theoretical bounds to practice, demonstrating that the theoretical superiority of SignSGD accurately predicts its faster convergence during the pretraining of a 124M parameter GPT-2 model.
- Abstract（参考訳）: SignSGDやMuonのような符号ベースの最適化アルゴリズムは、大規模な基礎モデルのトレーニングにおける顕著なパフォーマンスに対して大きな注目を集めている。
このような経験的成功にもかかわらず、我々はこの手話に基づく手法がバニラSGDを上回った時期と理由について理論的には理解していない。
中心となる障害は、標準の滑らかさと有限分散条件の下では、SGDは$\ell_2$-normsで測定された定常点を求めるのに最小限の最適であることが知られ、したがって標準設定における符号ベースの方法の複雑性ゲインを根本から排除することが知られていることである。
この障壁を克服するために、我々は、$\ell_1$-norm固定性、$\ell_\infty$-smoothness、および署名された更新の座標的な性質をよりよく捉えることのできる分離可能なノイズモデルを利用して、符号ベースのオプティマイザを分析する。
この異なる問題幾何学の下では、SignSGDの上下境界を一致させ、SignSGDがSGDを確実に支配する問題クラスを明示的に特徴付ける。
具体的には、SignSGD の \emph{upper bound と SGD {\displaystyle SGD} の \emph{lower bound を比較し、SignSGD が問題次元であるような \emph{sparse noise} の下での$d$ の係数で効果的に複雑性を減少させることを示した。
さらに、このフレームワークを行列領域に高め、Muonオプティマイザに等価な最適下界を与え、符号演算子を行列に拡張することは、この最適スケーリングを次元性で保っていることを証明した。
最後に,124M パラメータ GPT-2 モデルの事前学習において,SignSGD の理論的優位性が精度良く収束を予測できることを示す。
関連論文リスト
- StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models [16.690425653502256]
SignSGDのような符号ベースの最適化アルゴリズムは、分散学習と大規模基盤モデルの訓練において、顕著な性能で大きな注目を集めている。
実験的な優位性にもかかわらず、SignSGDは非テキスト・平滑な目的において分岐することが知られている。
我々はbfStoSignSGDを提案する。bfStoSignSGDは、不偏更新ステップを維持しつつ、手話演算子に構造性を注入するアルゴリズムである。
論文 参考訳（メタデータ） (2026-04-16T17:55:36Z) - Provable Benefit of Sign Descent: A Minimal Model Under Heavy-Tailed Class Imbalance [12.08350675783261]
我々は,データ分布の特性,すなわち重み付きクラス不均衡から直接,$ell_infty$-norm 降下の利点について検討する。
我々は、座標アルゴリズムの高速収束を証明可能な、最小でも代表的な次世代予測設定を提案する。
論文 参考訳（メタデータ） (2025-11-30T07:21:02Z) - Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。
このような悪条件下でSGDが確実に成功できるかどうかを精査する。
論文 参考訳（メタデータ） (2025-08-06T20:09:41Z) - Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order [39.25335214877435]
ダウンストリームタスクに事前訓練されたモデルを適用するには、微調整大型言語モデル(LLM)が不可欠である。
従来の一階述語アルゴリズムは、モデルサイズであまりスケールしない、禁止的なメモリと計算コストを発生させる。
メモリと計算効率の代替としてゼロオーダー(ZO)最適化法を提案する。
論文 参考訳（メタデータ） (2025-06-04T20:27:17Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
適応勾配法は、最も成功したニューラルネットワークトレーニングアルゴリズムの一つである。
これらの手法は凸SGD-ノルマリティよりも次元依存性が優れていることが知られている。
本稿では,構造物の滑らかさと勾配雑音の分散に関する新しい仮定を紹介する。
論文 参考訳（メタデータ） (2024-06-07T02:55:57Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - Label Noise SGD Provably Prefers Flat Global Minimizers [48.883469271546076]
過度パラメータ化モデルでは、勾配降下(SGD)のノイズは最適化軌道を暗黙的に規則化し、どの局所最小SGDが収束するかを決定する。
ラベルノイズを持つSGDが正規化損失$L(theta) +lambda R(theta)$の定常点に収束することを示す。
解析の結果,線形スケーリング法則を超越した大規模学習率の正規化効果が明らかとなった。
論文 参考訳（メタデータ） (2021-06-11T17:59:07Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Direction Matters: On the Implicit Bias of Stochastic Gradient Descent
with Moderate Learning Rate [105.62979485062756]
本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。
SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
論文 参考訳（メタデータ） (2020-11-04T21:07:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。