論文の概要: Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity

• arxiv url: http://arxiv.org/abs/2509.22860v2
• Date: Tue, 30 Sep 2025 15:11:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-01 14:44:59.847223
• Title: Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity
• Title（参考訳）: リングリーダーASGD:データヘテロジニティの下での最適時間複雑度を持つ最初の非同期SGD
• Authors: Artavazd Maranjyan, Peter Richtárik,
• Abstract要約: 本稿では,並列計算の理論的下界を実現する最初の非同期アルゴリズムであるリングリーダーASGDを紹介する。 我々の分析により、リングリーダーASGDは任意の勾配と時間変化速度の下で最適であることが明らかとなった。
• 参考スコア（独自算出の注目度）: 51.56484100374058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Asynchronous stochastic gradient methods are central to scalable distributed optimization, particularly when devices differ in computational capabilities. Such settings arise naturally in federated learning, where training takes place on smartphones and other heterogeneous edge devices. In addition to varying computation speeds, these devices often hold data from different distributions. However, existing asynchronous SGD methods struggle in such heterogeneous settings and face two key limitations. First, many rely on unrealistic assumptions of similarity across workers' data distributions. Second, methods that relax this assumption still fail to achieve theoretically optimal performance under heterogeneous computation times. We introduce Ringleader ASGD, the first asynchronous SGD algorithm that attains the theoretical lower bounds for parallel first-order stochastic methods in the smooth nonconvex regime, thereby achieving optimal time complexity under data heterogeneity and without restrictive similarity assumptions. Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary and even time-varying worker computation speeds, closing a fundamental gap in the theory of asynchronous optimization.
• Abstract（参考訳）: 非同期確率勾配法は、特にデバイスが計算能力が異なる場合に、拡張性のある分散最適化の中心となる。 このような設定は、スマートフォンやその他の異種エッジデバイスでトレーニングが行われる連邦学習において自然に発生する。 計算速度の変化に加えて、これらのデバイスは、しばしば異なる分布からのデータを保持する。 しかし、既存の非同期SGDメソッドは、このような不均一な設定で苦労し、2つの重要な制限に直面している。 第一に、多くの人は労働者のデータ分布における類似性の非現実的な仮定に依存している。 第二に、この仮定を緩和する手法は、不均一な計算時間下で理論的に最適な性能を達成できない。 並列一階確率法の理論的下界をスムーズな非凸方式で達成し,データ不均一性と制約的類似性仮定を伴わない最適時間複雑性を実現する,最初の非同期SGDアルゴリズムであるリングリーダーASGDを導入する。 我々の分析により、Ring Leader ASGDは任意の時間変化のワーカ計算速度の下では最適であり、非同期最適化理論の根本的なギャップを埋めることになる。

関連論文リスト

• 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)
• Robust Fully-Asynchronous Methods for Distributed Training over General Architecture [11.480605289411807]
  分散機械学習問題における完全な同期は、レイテンシ、パッケージの損失、ストラグラーの存在のため、非効率であり、不可能である。 本稿では,R-FAST (Fully-Asynchronous Gradient Tracking Method) を提案する。
  論文  参考訳（メタデータ） (2023-07-21T14:36:40Z)

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

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