論文の概要: Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

• arxiv url: http://arxiv.org/abs/2609.17483v1
• Date: Tue, 15 Sep 2026 17:24:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 14:56:08.636598
• Title: Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult
• Title（参考訳）: 均一性と不均一な非同期最適化のギャップを埋めるのは意外と難しい
• Abstract要約: ランダム化アルゴリズムの1階と2階の類似性仮定において、改善は証明不可能であることを示す。 我々は、労働者の計算時間に依存した新しい時間複雑性を、同質な設定で最もよく知られた結果に導出する。
• 参考スコア（独自算出の注目度）: 67.12978375116599
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.
• Abstract（参考訳）: 現代の大規模機械学習タスクでは、複数のワーカー、デバイス、CPU、GPUが並列かつ非同期に確率勾配を計算し、モデルの重みをトレーニングする必要があることが多い。 理論的な結果は典型的には2つの設定を区別する。 一 すべての労働者が同一のデータ配信にアクセスできる同質の設定 (ii)各作業者が異なるデータ分散を運用する異種設定。 これらの設定における最適な時間複雑性は、不均一な場合においてはるかに悲観的な保証とともに、大きなギャップを示す。 本研究では、これらの悲観的最適時間複雑性が異なる仮定の下で克服できるかどうかを考察する。 意外なことに、任意のランダム化アルゴリズムに対して広く使われている1階と2階の類似性仮定の下では、改善は証明不可能であることを示す。 次に、補間体制に目を向け、補間仮定が弱いだけでは不十分であることを示す。 最後に、既約仮定、強い補間、局所ポリャク・ロジャシエヴィチ条件の最小の組み合わせを導入し、同じデータ分布を必要とせず、最もよく知られた結果における労働者計算時間への依存と一致する新しい時間複雑性を導出する。

関連論文リスト

• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  本稿では,並列計算の理論的下界を実現する最初の非同期アルゴリズムであるリングリーダーASGDを紹介する。 我々の分析により、リングリーダーASGDは任意の勾配と時間変化速度の下で最適であることが明らかとなった。
  論文  参考訳（メタデータ） (2025-09-26T19:19:15Z)
• Instance-Optimal Uniformity Testing and Tracking [20.711670932098176]
  本稿では,一様性追跡の問題を導入し,一様性から偏差を検出するアルゴリズムを提案する。 我々の主な貢献は$operatornamepolylog(operatornameopt)$-competitive uniformity tracking algorithmである。
  論文  参考訳（メタデータ） (2025-08-04T17:23:00Z)
• Rademacher learning rates for iterated random functions [0.0]
  トレーニングデータセットが、必ずしも既約あるいは非周期的でない反復ランダム関数によって生成される場合を考える。 支配関数が第一引数に関して収縮的であるという仮定の下で、まず、対応するサンプル誤差に対する一様収束結果を確立する。 次に、近似経験的リスク最小化アルゴリズムの学習可能性を示し、その学習速度を導出する。
  論文  参考訳（メタデータ） (2025-06-16T19:36:13Z)
• 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)
• Generalization error of min-norm interpolators in transfer learning [2.7309692684728617]
  最小ノルム補間器は、現代の機械学習アルゴリズムの暗黙の正規化限界として自然に現れる。 多くのアプリケーションでは、トレーニング中に限られた量のテストデータが利用できるが、この設定におけるmin-normの特性は十分に理解されていない。 我々はこれらの特徴を達成するために、新しい異方性局所法を確立した。
  論文  参考訳（メタデータ） (2024-06-20T02:23:28Z)
• 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)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Stochastic linear optimization never overfits with quadratically-bounded losses on general data [20.41989568533313]
  この研究は、一般データ上での線形最適化手法の多様なコレクションは、明示的な制約や正規化が欠如しているにもかかわらず、過度に適合しないことを示している。 この分析は、多くの設定を扱える基本的だが柔軟な証明方式によって実現されている。
  論文  参考訳（メタデータ） (2022-02-14T18:12:38Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。 この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
  論文  参考訳（メタデータ） (2021-01-16T17:11:02Z)

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

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