論文の概要: Sequential Gradient Coding For Straggler Mitigation
- arxiv url: http://arxiv.org/abs/2211.13802v1
- Date: Thu, 24 Nov 2022 21:12:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-28 18:33:27.710496
- Title: Sequential Gradient Coding For Straggler Mitigation
- Title（参考訳）: ストラグラー緩和のための逐次勾配符号化
- Authors: M. Nikhil Krishnan, MohammadReza Ebrahimi, Ashish Khisti
- Abstract要約: 分散コンピューティングでは、遅いノード(ストラグラー)がボトルネックとなる。
グラディエント符号化(GC)は、誤り訂正符号の原理を用いて、ストラグラーの存在下で勾配計算を分散する効率的な手法である。
本稿では,GCと比較して性能向上を示す2つのスキームを提案する。
- 参考スコア（独自算出の注目度）: 28.090458692750023
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In distributed computing, slower nodes (stragglers) usually become a
bottleneck. Gradient Coding (GC), introduced by Tandon et al., is an efficient
technique that uses principles of error-correcting codes to distribute gradient
computation in the presence of stragglers. In this paper, we consider the
distributed computation of a sequence of gradients $\{g(1),g(2),\ldots,g(J)\}$,
where processing of each gradient $g(t)$ starts in round-$t$ and finishes by
round-$(t+T)$. Here $T\geq 0$ denotes a delay parameter. For the GC scheme,
coding is only across computing nodes and this results in a solution where
$T=0$. On the other hand, having $T>0$ allows for designing schemes which
exploit the temporal dimension as well. In this work, we propose two schemes
that demonstrate improved performance compared to GC. Our first scheme combines
GC with selective repetition of previously unfinished tasks and achieves
improved straggler mitigation. In our second scheme, which constitutes our main
contribution, we apply GC to a subset of the tasks and repetition for the
remainder of the tasks. We then multiplex these two classes of tasks across
workers and rounds in an adaptive manner, based on past straggler patterns.
Using theoretical analysis, we demonstrate that our second scheme achieves
significant reduction in the computational load. In our experiments, we study a
practical setting of concurrently training multiple neural networks over an AWS
Lambda cluster involving 256 worker nodes, where our framework naturally
applies. We demonstrate that the latter scheme can yield a 16\% improvement in
runtime over the baseline GC scheme, in the presence of naturally occurring,
non-simulated stragglers.
- Abstract（参考訳）: 分散コンピューティングでは、遅いノード(ストラグラー)は通常ボトルネックとなる。
Tandonらによって導入されたGC(Gradient Coding)は、誤り訂正符号の原理を用いて、ストラグラーの存在下で勾配計算を分散する効率的な手法である。
本稿では,各勾配の処理をラウンド$t$で開始し,ラウンド$(t+t)$で終了するような勾配列$\{g(1),g(2),\ldots,g(j)\}$の分散計算を考える。
ここで$T\geq 0$は遅延パラメータを表す。
GCスキームでは、コーディングは計算ノード間でのみ行われ、結果として$T=0$というソリューションが得られる。
一方、$t>0$を持つことで、時間次元を利用するスキームを設計することができる。
本稿では,GCと比較して性能向上を示す2つの手法を提案する。
最初のスキームでは、GCと未完成タスクの選択的な繰り返しを組み合わせることで、トラグラー緩和の改善を実現しています。
私たちの主な貢献を構成する第2のスキームでは、タスクのサブセットにgcを適用し、残りのタスクを反復します。
次に、過去のストラグラーパターンに基づいて、労働者とラウンドにまたがる2つのタスクのクラスを適応的に多重化する。
理論解析を用いて,第2のスキームが計算負荷を大幅に削減できることを実証する。
実験では、256のワーカノードを含むAWS Lambdaクラスタ上で、並列に複数のニューラルネットワークをトレーニングする実践的な設定について検討した。
提案手法は, 自然に発生する非シミュレートストラグラーの存在下で, ベースラインGC方式よりも16倍のランタイム改善を実現することができることを示す。
関連論文リスト
- Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。
既存のGCメソッドは複雑な最適化プロセスに悩まされており、過剰な計算資源を必要とする。
我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。
CGCはより効率的な凝縮プロセスで最先端の性能を達成する。
論文 参考訳（メタデータ） (2024-05-22T14:57:09Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳（メタデータ） (2023-10-05T02:58:29Z) - Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。
IG/RRスキームの簡易制御による修正を定義する。
我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
論文 参考訳（メタデータ） (2022-12-04T15:26:36Z) - 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) - A Communication-Efficient Distributed Gradient Clipping Algorithm for
Training Deep Neural Networks [11.461878019780597]
グラディエントDescentは、ディープニューラルネットワークにおいてゆっくりと収束する。
勾配クリッピング方式が並列スピードアップを楽しむために複数のマシンを活用できるかどうかは謎のままである。
論文 参考訳（メタデータ） (2022-05-10T16:55:33Z) - Gradient Coding with Dynamic Clustering for Straggler-Tolerant
Distributed Learning [55.052517095437]
勾配降下(GD)は、複数の労働者にデータセットを分散することで学習タスクの並列化に広く用いられている。
分散同期gdにおけるイテレーション完了時間ごとの重要なパフォーマンスボトルネックは$straggling$ workersである。
コード化された分散技術は、最近ストラグラーを緩和し、労働者に冗長な計算を割り当てることでgdイテレーションを高速化するために導入された。
本稿では,従来のトラグリング動作に依存する可能性のあるコードの中から,冗長なデータを労働者に割り当てて選択する動的GC方式を提案する。
論文 参考訳（メタデータ） (2021-03-01T18:51:29Z) - Gradient Coding with Dynamic Clustering for Straggler Mitigation [57.9123881133818]
GC-DCは、前回のイテレーションにおけるストラグラーの振る舞いに基づいて、各クラスタ内のストラグラーワーカ数を規制する。
本稿では,GC-DCが従来のGC方式に比べて通信負荷を増大させることなく,各イテレーションの平均完了時間(各イテレーション)を大幅に改善できることを数値的に示す。
論文 参考訳（メタデータ） (2020-11-03T18:52:15Z) - Gradient Centralization: A New Optimization Technique for Deep Neural
Networks [74.935141515523]
勾配集中(GC)は、勾配ベクトルをゼロ平均とする集中化によって、勾配を直接操作する。
GCは、制約された損失関数を持つ射影勾配降下法とみなすことができる。
GCは実装が非常に簡単で、1行のコードだけで既存のグラデーションベースのDNNに簡単に組み込める。
論文 参考訳（メタデータ） (2020-04-03T10:25:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。