論文の概要: Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
- arxiv url: http://arxiv.org/abs/2501.16168v1
- Date: Mon, 27 Jan 2025 16:07:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-28 13:58:12.097949
- Title: Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
- Title(参考訳): Ringmaster ASGD: 最適な時間複雑性を備えた最初の非同期SGD
- Authors: Artavazd Maranjyan, Alexander Tyurin, Peter Richtárik,
- Abstract要約: Ringmaster ASGDは任意に不均一な計算時間の下で最適な時間複雑性を達成する。
これにより、このようなシナリオにおける時間複雑性の理論的な下限を満たす最初の非同期SGD法となる。
- 参考スコア(独自算出の注目度): 92.1840862558718
- License:
- Abstract: Asynchronous Stochastic Gradient Descent (Asynchronous SGD) is a cornerstone method for parallelizing learning in distributed machine learning. However, its performance suffers under arbitrarily heterogeneous computation times across workers, leading to suboptimal time complexity and inefficiency as the number of workers scales. While several Asynchronous SGD variants have been proposed, recent findings by Tyurin & Richt\'arik (NeurIPS 2023) reveal that none achieve optimal time complexity, leaving a significant gap in the literature. In this paper, we propose Ringmaster ASGD, a novel Asynchronous SGD method designed to address these limitations and tame the inherent challenges of Asynchronous SGD. We establish, through rigorous theoretical analysis, that Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous and dynamically fluctuating worker computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
- Abstract(参考訳): Asynchronous Stochastic Gradient Descent (Asynchronous SGD) は分散機械学習における学習の並列化のための基礎的手法である。
しかし、その性能は労働者間で任意に不均一な計算時間に悩まされ、労働者の数がスケールするにつれて、最適時間以下の複雑さと非効率性が生じる。
いくつかの非同期SGD変種が提案されているが、Tyurin & Richt\'arik (NeurIPS 2023) による最近の研究によると、最適な時間複雑性は得られず、文献に大きなギャップが残されている。
本稿では,これらの制約に対処し,非同期SGDの本質的課題をテーム化する新しい非同期SGD手法であるRingmaster ASGDを提案する。
厳密な理論的解析により、Ringmaster ASGDは任意に不均一で動的に変動するワーカ計算時間の下で最適な時間複雑性を実現する。
これにより、このようなシナリオにおける時間複雑性の理論的な下限を満たす最初の非同期SGD法となる。
関連論文リスト
- MindFlayer: Efficient Asynchronous Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
並列作業者の助けを借りてスムーズな非関数の期待を最小化する問題について検討する。
本稿では,ノイズの重み付けを行う新しい非同期SGD手法であるMindlayer SGDを提案する。
我々の理論は、ノイズが重く尾行されている場合に、Mindlayer SGDの優位性を実証するものである。
論文 参考訳(メタデータ) (2024-10-05T21:11:32Z) - Dual-Delayed Asynchronous SGD for Arbitrarily Heterogeneous Data [22.917944307972434]
我々は、中央サーバのオーケストレーションの下で、複数のワーカにまたがるデータによる分散学習問題を考察する。
データ繰り返しの悪影響を考慮に入れたテキスト遅延非同期SGD(DuDe-ASGD)アルゴリズムを提案する。
DuDe-ASGDは非同期トレーニング中にすべてのワーカーからの静的な勾配をフルに利用し、モデルパラメータとサーバで使用されるデータサンプルに2つの時間ラグをもたらす。
論文 参考訳(メタデータ) (2024-05-27T09:00:30Z) - 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) - AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
不均一な環境で分散SGDのための非同期型アルゴリズムを解析する。
また,本分析の副産物として,ランダムなきついSGDのような勾配型アルゴリズムの保証を示す。
論文 参考訳(メタデータ) (2023-10-31T13:44:53Z) - Towards Understanding the Generalizability of Delayed Stochastic
Gradient Descent [63.43247232708004]
非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。
既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。
我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
論文 参考訳(メタデータ) (2023-08-18T10:00:27Z) - Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays [8.46491234455848]
ステップの数だけでなく、ステップの遅延にもよらず、同じ非同期勾配の保証がずっと良いことを証明しています。
そこで本研究では,「仮想ステップ」と「遅延反復」に基づいて,両凸非適応勾配に対する最先端保証を導出する手法を提案する。
論文 参考訳(メタデータ) (2022-06-15T16:28:37Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳(メタデータ) (2021-07-06T21:59:49Z) - Slow and Stale Gradients Can Win the Race [39.750046808758526]
同期的に実行される分散Gradient Descent(SGD)は、最も遅いワーカー(ストラグラー)を待つとき、実行時の遅延に悩まされる。
非同期手法はストラグラーを緩和するが、収束誤差に悪影響を及ぼす勾配の安定化を引き起こす。
本稿では,訓練されたモデルにおけるエラーと実際のトレーニング実行時のトレードオフを解析し,非同期手法によって提供される高速化の理論的特徴について述べる。
論文 参考訳(メタデータ) (2020-03-23T23:27:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。