論文の概要: Optimal Communication-Computation Trade-Off in Heterogeneous Gradient
Coding
- arxiv url: http://arxiv.org/abs/2103.01589v1
- Date: Tue, 2 Mar 2021 09:25:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-03 15:40:50.911341
- Title: Optimal Communication-Computation Trade-Off in Heterogeneous Gradient
Coding
- Title(参考訳): 不均一勾配符号化における最適通信計算トレードオフ
- Authors: Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali
- Abstract要約: グラデーションのサイズによって正規化された最適な通信コストは$(r-s-2a)-1$に等しく、mathbbN$の$rはデータパーティションが複製される最小数である。
また、近似計算からいくつかのアイデアを借用し、通信コストに課される制約を満たすためにデータ配置の繰り返しが必要とされるものよりも小さい場合の近似勾配符号化スキームを提案する。
- 参考スコア(独自算出の注目度): 23.783023315297875
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient coding allows a master node to derive the aggregate of the partial
gradients, calculated by some worker nodes over the local data sets, with
minimum communication cost, and in the presence of stragglers. In this paper,
for gradient coding with linear encoding, we characterize the optimum
communication cost for heterogeneous distributed systems with \emph{arbitrary}
data placement, with $s \in \mathbb{N}$ stragglers and $a \in \mathbb{N}$
adversarial nodes. In particular, we show that the optimum communication cost,
normalized by the size of the gradient vectors, is equal to $(r-s-2a)^{-1}$,
where $r \in \mathbb{N}$ is the minimum number that a data partition is
replicated. In other words, the communication cost is determined by the data
partition with the minimum replication, irrespective of the structure of the
placement. The proposed achievable scheme also allows us to target the
computation of a polynomial function of the aggregated gradient matrix. It also
allows us to borrow some ideas from approximation computing and propose an
approximate gradient coding scheme for the cases when the repetition in data
placement is smaller than what is needed to meet the restriction imposed on
communication cost or when the number of stragglers appears to be more than the
presumed value in the system design.
- Abstract(参考訳): グラディエントコーディングにより、マスターノードは部分勾配の集約を導出することができ、いくつかのワーカノードがローカルデータセット上で計算し、最小の通信コストとストラグラーの存在下で計算する。
本稿では,線形符号化を用いた勾配符号化において,emph{arbitrary}データ配置を持つ異種分散システムの最適な通信コストを,s \in \mathbb{n}$ stragglers と $a \in \mathbb{n}$ adversarial node で特徴付ける。
特に、勾配ベクトルの大きさで正規化された最適な通信コストは$(r-s-2a)^{-1}$に等しいことが示され、ここでは$r \in \mathbb{n}$はデータ分割が複製される最小数である。
言い換えれば、通信コストは、配置の構造に関係なく、最小限の複製でデータパーティションによって決定されます。
提案された達成可能なスキームは、集合勾配行列の多項式関数の計算も対象とすることができる。
また、データ配置の繰り返しが通信コストに課される制限を満たすために必要なものよりも小さい場合や、システム設計の推定値よりもストラグラーの数が多いと思われる場合に、近似計算からいくつかのアイデアを借り、近似勾配符号化スキームを提案します。
関連論文リスト
- CORE: Common Random Reconstruction for Distributed Optimization with
Provable Low Communication Complexity [110.50364486645852]
コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。
本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
論文 参考訳(メタデータ) (2023-09-23T08:45:27Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳(メタデータ) (2023-02-14T22:12:16Z) - 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) - DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。
我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文 参考訳(メタデータ) (2022-07-26T08:47:54Z) - Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning [58.91954425047425]
本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。
L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
論文 参考訳(メタデータ) (2022-06-06T09:25:40Z) - Combinatorial optimization for low bit-width neural networks [23.466606660363016]
低ビット幅のニューラルネットワークは、計算資源を減らすためにエッジデバイスに展開するために広く研究されている。
既存のアプローチでは、2段階の列車・圧縮設定における勾配に基づく最適化に焦点が当てられている。
グリーディ座標降下法とこの新しい手法を組み合わせることで、二項分類タスクにおける競合精度が得られることを示す。
論文 参考訳(メタデータ) (2022-06-04T15:02:36Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - Distributed Learning and Democratic Embeddings: Polynomial-Time Source
Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient
Descent under Communication Constraints [46.17631511884969]
我々は、n次元ユークリッド空間においてベクトルを圧縮する問題を考える。
数値化器の被覆効率が次元独立であるか、あるいは非常に弱い対数依存であるという意味では、民主主義的および民主的に近いソースコーディングスキームが(ほぼ)最適であることを示す。
分散最適化アルゴリズムDGD-DEFを提案する。このアルゴリズムは,提案した符号化戦略を用いて,(ほぼ)定数要素内における最小収束率を実現する。
論文 参考訳(メタデータ) (2021-03-13T00:04:11Z) - The Min-Max Complexity of Distributed Stochastic Convex Optimization
with Intermittent Communication [61.60069865891783]
間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
論文 参考訳(メタデータ) (2021-02-02T16:18:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。