論文の概要: Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

• arxiv url: http://arxiv.org/abs/2605.08871v1
• Date: Sat, 09 May 2026 10:46:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:49.944194
• Title: Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
• Title（参考訳）: Rennala MVR:Momentum-based Variance Reductionによる並列確率最適化のための時間複雑性の改善
• Abstract要約: 平均次元の滑らかさ仮定の下では、分散の低減は異種系の時間複雑性を改善することが示される。 本稿では、モーメントに基づく分散還元に基づくRennala SGDの分散還元拡張であるRennala MVRを提案する。
• 参考スコア（独自算出の注目度）: 45.88028371034407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large-scale machine learning models are trained on clusters of machines that exhibit heterogeneous performance due to hardware variability, network delays, and system-level instabilities. In such environments, time complexity rather than iteration complexity becomes the relevant performance metric for optimization algorithms. Recent work by Tyurin and Richtárik (2023) established the first time complexity analysis for parallel first-order stochastic optimization, proposing Rennala SGD as a time-optimal method for smooth nonconvex optimization. However, Rennala SGD is fundamentally a modification of SGD, and variance reduction techniques are known to improve the iteration complexity of SGD. In this work, we investigate whether variance reduction can also improve time complexity in heterogeneous systems. We show that, under a mean-squared smoothness assumption, variance reduction can improve time complexity in relevant parameter regimes. To this end, we propose Rennala MVR, a variance-reduced extension of Rennala SGD based on momentum-based variance reduction, and analyze its oracle and time complexity. We establish lower bounds for time complexity under these assumptions. On a stochastic quadratic benchmark, experiments with the exact method support the theory, while neural-network experiments with a practical inexact variant show similar empirical gains over Rennala SGD.
• Abstract（参考訳）: 大規模機械学習モデルは、ハードウェアの可変性、ネットワーク遅延、システムレベルの不安定性による不均一なパフォーマンスを示すマシンのクラスタでトレーニングされる。 このような環境では、イテレーションの複雑さよりも時間の複雑さが最適化アルゴリズムの関連するパフォーマンス指標となる。 Tyurin と Richtárik (2023) による最近の研究は、並列一階確率最適化のための最初の複雑性解析を確立し、円滑な非凸最適化のための時間最適化手法として Rennala SGD を提案した。 しかし、Rennala SGDは基本的にSGDの修正であり、分散還元技術はSGDの反復複雑性を改善することが知られている。 本研究では,不均質系における分散低減が時間複雑性を改善できるかどうかを考察する。 平均2乗の滑らか性仮定の下では、分散の減少は関連するパラメータの時間的複雑さを改善することが示される。 この目的のために,運動量に基づく分散還元に基づくRennala SGDの分散還元拡張であるRennala MVRを提案し,そのオラクルと時間複雑性を解析する。 これらの仮定の下で、時間複雑性の低い境界を確立する。 確率的2次ベンチマークでは、正確な方法による実験が理論を支持する一方で、実用的不正確な変種によるニューラルネット実験は、ルナルナSGDに対して同様の経験的な効果を示す。

関連論文リスト

• Trajectory-Optimized Time Reparameterization for Learning-Compatible Reduced-Order Modeling of Stiff Dynamical Systems [0.2877671212386687]
  時間再パラメータ化(TR)は、ニューラルODEの低次モデリングのための剛性緩和機構である。 本研究では, TR をニューラルODE の低次モデリングのための剛性緩和機構として検討し, トラジェクトリ最適化TR (TOTR) の定式化を導入する。 ToTRは、パラメータ化された剛性線形系、ファンデルポル発振器、HIRES化学動力学モデルという3つの硬質問題で評価される。
  論文  参考訳（メタデータ） (2026-03-17T14:33:59Z)
• Momentum LMS Theory beyond Stationarity: Stability, Tracking, and Regret [6.655960359749289]
  大規模データ処理のシナリオでは、データが複雑なシステムによって生成されるシーケンシャルストリームに到達することが多い。 この非定常性は古典的な仮定に反する理論解析に挑戦する。 本稿では,適応型識別ツールとしてMomentum Least Mean Squares (MLMS)アルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2026-02-12T14:24:42Z)
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  本稿では,並列計算の理論的下界を実現する最初の非同期アルゴリズムであるリングリーダーASGDを紹介する。 我々の分析により、リングリーダーASGDは任意の勾配と時間変化速度の下で最適であることが明らかとなった。
  論文  参考訳（メタデータ） (2025-09-26T19:19:15Z)
• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity [92.1840862558718]
  Ringmaster ASGDは任意に不均一な計算時間の下で最適な時間複雑性を達成する。 これにより、このようなシナリオにおける時間複雑性の理論的な下限を満たす最初の非同期SGD法となる。
  論文  参考訳（メタデータ） (2025-01-27T16:07:26Z)
• MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
  最適勾配を計算できる複数の並列作業者の設定において、滑らかな非関数の期待を最小化する問題について検討する。 この文脈における課題は、任意に不均一で分散された計算時間の存在である。 本稿では,このギャップに対処する新しい並列SGD法であるMindFlayer SGDを紹介する。
  論文  参考訳（メタデータ） (2024-10-05T21:11:32Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Scalable Spatiotemporally Varying Coefficient Modelling with Bayesian Kernelized Tensor Regression [17.158289775348063]
  カーネル化されたテンソル回帰(BKTR)は、低ランクの時間構造を持つモデリングプロセスに対する新しいスケーラブルなアプローチと考えられる。 そこで本研究では,BKTRのモデル推定と推定において,BKTRの優れた性能と効率性を確認した。
  論文  参考訳（メタデータ） (2021-08-31T19:22:23Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。 本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
  論文  参考訳（メタデータ） (2020-06-16T19:57:48Z)

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

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