論文の概要: Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2610.16923v1
• Date: Mon, 12 Oct 2026 15:07:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-18 04:06:56.752154
• Title: Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization
• Title（参考訳）: 非定常確率最適化のためのシャンプーの最小最適性
• Abstract要約: 非定常最適化における時間相追跡のための行列シャンプーの理論解析法を開発した。 本研究では, ドリフト, 運動量誘起ドリフト, 雑音, 安定性, 適応前条件を乱す平均追従誤差に対して, 有限水平高確率境界を導出する。 これらの境界は明示的なドリフト-ノイズと安定性-幾何学的トレードオフを明らかにしている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a comprehensive theoretical analysis of Matrix Shampoo for tracking time-varying optima in nonstationary stochastic optimization. We derive finite-horizon high-probability bounds for average tracking error that disentangle initialization, optimizer drift, momentum-induced drift penalty, stochastic noise, and adaptive preconditioning, with explicit dependence on momentum parameter \(β_1\) and stabilization parameter \(\varepsilon\). These bounds reveal an explicit drift--noise and stability--geometry tradeoffs: noise-dominated regimes favor larger $β_1$, which provides stronger first-moment averaging and greater suppression of gradient noise, whereas drift-dominated regimes favor smaller $β_1$, allowing faster adaptation to moving optimizer. Larger $\varepsilon$ reduces the preconditioner-perturbation term while weakening Shampoo's ability to exploit matrix geometry, thereby reducing adaptivity. We establish a matching minimax lower bound under squared path-variation constraint, proving the information-theoretic optimality of Shampoo over the class of causal optimization procedures. Under a constant stepsize, we establish high-probability bounds for the average projected stationarity gap along general nonstationary nonconvex objectives. We validate our theoretical findings on both synthetic and multiple real-world problems.
• Abstract（参考訳）: 非定常確率最適化における時間変化最適性を追跡するためのマトリックスシャンプーの包括的理論的解析法を開発した。 我々は、運動量パラメータ \(β_1\) と安定化パラメータ \(\varepsilon\) に明示的に依存して、初期化、オプティマイザドリフト、運動量誘発ドリフトペナルティ、確率雑音、適応事前条件を乱す平均追跡誤差に対する有限水平高確率境界を導出した。 これらの境界は明示的なドリフトノイズと安定性のトレードオフを示しており、ノイズ支配型レジームはより大きい$β_1$を好んでおり、これはより強い第1モーメント平均化と勾配雑音の抑制を提供する一方、ドリフト支配型レジームはより小さい$β_1$を好んでおり、移動オプティマイザへの適応がより高速である。 より大きな$\varepsilon$はプレコンディショナー摂動項を減らし、シャンプーの行列幾何学を活用できる能力を弱め、適応性を低下させる。 正方形経路偏差制約の下で,最小値の最小値の下限を定め,因果最適化手順のクラスに対するシャンプーの情報理論的最適性を証明する。 定常的なステップサイズの下では、一般の非定常な非凸な目的に沿った平均投影された定常性ギャップに対して高い確率境界を確立する。 我々は, 実世界の複合問題と実世界の複数問題に関する理論的知見を検証した。

関連論文リスト

• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max最適化は、現代の機械学習に応用されているため、注目を集めている。 我々は、勾配降下(SGDA)の包括的理論を提供する。 我々は,Stoc-GDAMとStoc-TRmaxという新たなクリッピングフリーアルゴリズムを開発し,グラディエントクリッピングを使わずに,目標精度への最適依存を実現する。
  論文  参考訳（メタデータ） (2026-09-05T12:49:28Z)
• The Road Taken: The Role of Optimizers at the Edge of Stability [53.81268610971847]
  安定性のエッジ(Edge of stability)とは、古典的な降下が不安定であると予測されるしきい値より上のヘッセンの固有値が安定である深層学習における現象を指す。 それまでの研究は、最大ヘッセン固有値と学習率に関して安定性の端を定式化していた。 我々は、勾配降下を含む多くの一階法が、これらの理論によって予測される安定性を21.1ドルという大きな因子で著しく破っていることを観察した。
  論文  参考訳（メタデータ） (2026-08-19T01:03:34Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  乱摂動の分布は, 摂動段差がゼロになる傾向にあるため, 推定子の分散を最小限に抑える。 以上の結果から, 一定の長さを維持するのではなく, 真の勾配に方向を合わせることが可能であることが示唆された。
  論文  参考訳（メタデータ） (2025-10-22T19:06:39Z)
• Towards Weaker Variance Assumptions for Stochastic Optimization [19.339358874690568]
  次数次法の2乗ノルムを最適化変数の2乗ノルムの2乗ノルムと同程度の速さで成長させることができるような勾配アルゴリズムを解析するための古典的な仮定を再検討する。 関数的制約や正規化された凸凹 min-max 問題を用いて凸問題を解析する。 実現可能な集合の有界性を必要としない最適度測度に対するレートを得る。
  論文  参考訳（メタデータ） (2025-04-14T07:26:34Z)
• Langevin dynamics based algorithm e-TH$\varepsilon$O POULA for stochastic optimization problems with discontinuous stochastic gradient [6.563379950720334]
  我々は,不連続勾配による最適化問題を解くために,e-TH$varepsilon$O POULAと呼ばれる新しいランゲヴィン力学に基づくアルゴリズムを導入する。 金融と保険の3つの重要な応用として、多周期ポートフォリオ最適化、多周期ポートフォリオ最適化におけるトランスファーラーニング、保険請求予測がある。
  論文  参考訳（メタデータ） (2022-10-24T13:10:06Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。 非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
  論文  参考訳（メタデータ） (2020-01-15T16:11:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。