論文の概要: First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data

• arxiv url: http://arxiv.org/abs/2601.02523v1
• Date: Mon, 05 Jan 2026 19:51:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-07 17:02:12.714795
• Title: First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data
• Title（参考訳）: 均一データと不均一データに対する確率的最適非同期SGD
• Authors: Artavazd Maranjyan,
• Abstract要約: 論文は非同期順序最適化のための厳格なフレームワークを開発する。 適切な設計により、非同期SGDは、これまで同期メソッドでのみ知られていた保証に適合する最適な時間複雑性を実現することができることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Artificial intelligence has advanced rapidly through large neural networks trained on massive datasets using thousands of GPUs or TPUs. Such training can occupy entire data centers for weeks and requires enormous computational and energy resources. Yet the optimization algorithms behind these runs have not kept pace. Most large scale training still relies on synchronous methods, where workers must wait for the slowest device, wasting compute and amplifying the effects of hardware and network variability. Removing synchronization seems like a simple fix, but asynchrony introduces staleness, meaning updates computed on outdated models. This makes analysis difficult, especially when delays arise from system level randomness rather than algorithmic choices. As a result, the time complexity of asynchronous methods remains poorly understood. This dissertation develops a rigorous framework for asynchronous first order stochastic optimization, focusing on the core challenge of heterogeneous worker speeds. Within this framework, we show that with proper design, asynchronous SGD can achieve optimal time complexity, matching guarantees previously known only for synchronous methods. Our first contribution, Ringmaster ASGD, attains optimal time complexity in the homogeneous data setting by selectively discarding stale updates. The second, Ringleader ASGD, extends optimality to heterogeneous data, common in federated learning, using a structured gradient table mechanism. Finally, ATA improves resource efficiency by learning worker compute time distributions and allocating tasks adaptively, achieving near optimal wall clock time with less computation. Together, these results establish asynchronous optimization as a theoretically sound and practically efficient foundation for distributed learning, showing that coordination without synchronization can be both feasible and optimal.
• Abstract（参考訳）: 人工知能は、数千のGPUまたはTPUを使用して巨大なデータセットでトレーニングされた巨大なニューラルネットワークを介して急速に進歩した。 このようなトレーニングは、数週間にわたってデータセンター全体を占有し、膨大な計算とエネルギー資源を必要とする。 しかし、これらの実行の背後にある最適化アルゴリズムはペースを保っていない。 ほとんどの大規模トレーニングは同期方式に依存しており、労働者は最も遅いデバイスを待ち、計算を浪費し、ハードウェアとネットワークのばらつきの影響を増幅しなければならない。 同期の削除は単純な修正のように思えるが、asynchronyは陳腐化を導入している。 これにより、特にアルゴリズムの選択よりもシステムレベルのランダム性による遅延が発生すると、分析が困難になる。 その結果、非同期メソッドの時間的複雑さはいまだに理解されていない。 この論文は非同期一階確率最適化のための厳密なフレームワークを開発し、不均一な作業速度のコア課題に焦点を当てている。 このフレームワーク内では、非同期SGDは適切な設計により、これまで同期メソッドでのみ知られていた保証に適合する最適な時間複雑性を実現することができることを示す。 最初のコントリビューションであるRingmaster ASGDは、古い更新を選択的に破棄することで、均一なデータ設定において最適な時間複雑性を実現する。 第2のRing Leader ASGDは、構造化勾配テーブル機構を使用して、フェデレート学習で一般的な異種データに最適性を拡張する。 最後に、ATAは、作業者の時間分布を学習し、タスクを適応的に割り当てることにより、より少ない計算で最適なウォールクロック時間を達成することにより、リソース効率を向上させる。 これらの結果から,分散学習の理論的に健全かつ実用的な基礎として非同期最適化が確立され,同期のない協調が実現可能かつ最適であることが示唆された。

関連論文リスト

• 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)
• 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)
• Asynchronous Distributed Optimization with Delay-free Parameters [9.062164411594175]
  本稿では,2つの分散アルゴリズム, Prox-DGD と DGD-ATC の非同期バージョンを開発し,無方向性ネットワーク上でのコンセンサス最適化問題を解く。 代替アルゴリズムとは対照的に,我々のアルゴリズムは,遅延に依存しないステップサイズを用いて,同期アルゴリズムの固定点集合に収束することができる。
  論文  参考訳（メタデータ） (2023-12-11T16:33:38Z)
• Robust Fully-Asynchronous Methods for Distributed Training over General Architecture [11.480605289411807]
  分散機械学習問題における完全な同期は、レイテンシ、パッケージの損失、ストラグラーの存在のため、非効率であり、不可能である。 本稿では,R-FAST (Fully-Asynchronous Gradient Tracking Method) を提案する。
  論文  参考訳（メタデータ） (2023-07-21T14:36:40Z)

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

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