論文の概要: Efficient Distributed Machine Learning via Combinatorial Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2202.08302v1
• Date: Wed, 16 Feb 2022 19:18:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-18 14:52:09.547319
• Title: Efficient Distributed Machine Learning via Combinatorial Multi-Armed Bandits
• Title（参考訳）: 組合せ型マルチアーマッドバンドによる分散機械学習の効率化
• Authors: Maximilian Egger, Rawad Bitar, Antonia Wachter-Zeh and Deniz G\"und\"uz
• Abstract要約: 我々は、主ノードが$n$ワーカー間で勾配計算を分散する分散勾配降下問題を考え、そこから少なくとも$b leq n$を並列に利用することができる。 すべてのワーカーにタスクを割り当て、$k$の高速なものだけを待つことで、メインノードはアルゴリズムが進化するにつれて徐々に$k$を増大させることで、アルゴリズムのエラーをランタイムとトレードオフすることができる。 この戦略はアダプティブkシンクと呼ばれ、遅い作業者の計算作業を無視するため、追加のコストを発生させることができる。 タスクを$k$にのみ割り当てるコスト効率の高いスキームを提案する。
• 参考スコア（独自算出の注目度）: 23.289979018463406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the distributed stochastic gradient descent problem, where a main node distributes gradient calculations among $n$ workers from which at most $b \leq n$ can be utilized in parallel. By assigning tasks to all the workers and waiting only for the $k$ fastest ones, the main node can trade-off the error of the algorithm with its runtime by gradually increasing $k$ as the algorithm evolves. However, this strategy, referred to as adaptive k sync, can incur additional costs since it ignores the computational efforts of slow workers. We propose a cost-efficient scheme that assigns tasks only to $k$ workers and gradually increases $k$. As the response times of the available workers are unknown to the main node a priori, we utilize a combinatorial multi-armed bandit model to learn which workers are the fastest while assigning gradient calculations, and to minimize the effect of slow workers. Assuming that the mean response times of the workers are independent and exponentially distributed with different means, we give empirical and theoretical guarantees on the regret of our strategy, i.e., the extra time spent to learn the mean response times of the workers. Compared to adaptive k sync, our scheme achieves significantly lower errors with the same computational efforts while being inferior in terms of speed.
• Abstract（参考訳）: 分散確率勾配降下問題において、主ノードは、少なくとも$b \leq n$を並列に使用できる$n$ワーカー間で勾配計算を分散する。 すべてのワーカーにタスクを割り当て、$k$の高速なものだけを待つことで、メインノードはアルゴリズムが進化するにつれて徐々に$k$の増加によって、アルゴリズムのエラーをランタイムとトレードオフすることができる。 しかし、この戦略は適応的kシンクと呼ばれ、遅い作業者の計算作業を無視するため、追加コストを発生させることができる。 我々は、タスクを$k$ワーカーに割り当て、徐々に$k$を増加させるコスト効率の高いスキームを提案する。 使用可能な作業者の応答時間は,主ノードaプライオリに対して未知であるため,階層計算を割り当てながら最も速い作業者について学習し,遅い作業者の影響を最小限に抑えるために,組合せ型マルチアームバンディットモデルを用いる。 労働者の平均応答時間が異なる手段で独立して指数関数的に分配されていると仮定すると、我々の戦略の後悔、すなわち労働者の平均応答時間を学ぶのに費やした余分な時間を経験的および理論的保証を与える。 適応的k同期と比較して,本手法は,速度の点で劣る一方,同じ計算量で誤差を著しく低減する。

関連論文リスト

• DropCompute: simple and more robust distributed synchronous training via compute variance reduction [30.46681332866494]
  本稿では,計算時間の変動により労働者が混在する典型的なシナリオについて考察する。 作業者間のばらつきを低減し,同期学習の堅牢性を向上する,シンプルで効果的な分散化手法を提案する。
  論文  参考訳（メタデータ） (2023-06-18T16:55:31Z)
• Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load [11.069252535469644]
  勾配降下(SGD)のような最適化手順は、ストラグラーと呼ばれる非応答性や遅い労働者の影響を軽減するために利用することができる。 これは、ワーカのサブセットがアルゴリズムの各イテレーションで計算を完了するのを待つだけで実現できる。 我々は,アルゴリズムの実行時間を通じて,作業者数と計算負荷の両方を適応させる新しいスキームを構築した。
  論文  参考訳（メタデータ） (2023-04-17T20:12:18Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Coded Computation across Shared Heterogeneous Workers with Communication Delay [42.50248255900814]
  複数の行列乗算タスクを符号化し、並列計算のためにワーカーに割り当てるマルチワーカー分散コンピューティングのシナリオを考察する。 本稿では、各作業者が符号化されたタスクを処理可能な、専用および分数的な作業者割当ポリシーの下で、作業者割当、リソース割当負荷割当アルゴリズムを提案する。 提案アルゴリズムは,ベンチマークよりもタスク遅延の完了率を低減できることを示すとともに,専用および少数のワーカ割り当てポリシがアプリケーションのスコープが異なることを観察する。
  論文  参考訳（メタデータ） (2021-09-23T09:40:54Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning [55.052517095437]
  勾配降下(GD)は、複数の労働者にデータセットを分散することで学習タスクの並列化に広く用いられている。 分散同期gdにおけるイテレーション完了時間ごとの重要なパフォーマンスボトルネックは$straggling$ workersである。 コード化された分散技術は、最近ストラグラーを緩和し、労働者に冗長な計算を割り当てることでgdイテレーションを高速化するために導入された。 本稿では,従来のトラグリング動作に依存する可能性のあるコードの中から,冗長なデータを労働者に割り当てて選択する動的GC方式を提案する。
  論文  参考訳（メタデータ） (2021-03-01T18:51:29Z)
• Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers [9.919012793724628]
  作業者毎のバックアップ作業者数を決定するための完全分散アルゴリズムを提案する。 我々のアルゴリズムは収束の線形スピードアップを達成する(すなわち、労働者数に対して収束性能が線形に増加する)。
  論文  参考訳（メタデータ） (2021-02-11T21:39:53Z)
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off [56.08535873173518]
  ストラグワーカーは冗長な計算を割り当て、データと計算をまたいでコーディングすることで許容できる。 既存のほとんどのスキームでは、各非ストラグリングワーカーは、全ての計算を完了した後、1イテレーションごとに1つのメッセージをパラメータサーバ(PS)に送信する。 このような制限を課すことで、ストレグリング動作の不正確な予測による過剰計算と、ストレグラー/非ストレグラーとしての作業員の処理による未使用の2つの主な欠点が生じる。
  論文  参考訳（メタデータ） (2020-04-10T08:39:36Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。 我々は、新しい空間演算子:ランダムトップk演算子を導入する。 我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
  論文  参考訳（メタデータ） (2020-01-27T08:23:58Z)

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

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