論文の概要: 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}$はデータ分割が複製される最小数である。
言い換えれば、通信コストは、配置の構造に関係なく、最小限の複製でデータパーティションによって決定されます。
提案された達成可能なスキームは、集合勾配行列の多項式関数の計算も対象とすることができる。
また、データ配置の繰り返しが通信コストに課される制限を満たすために必要なものよりも小さい場合や、システム設計の推定値よりもストラグラーの数が多いと思われる場合に、近似計算からいくつかのアイデアを借り、近似勾配符号化スキームを提案します。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳（メタデータ） (2024-07-26T03:14:13Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach [32.36073823372713]
機械学習モデルでは、アルゴリズムはその勾配のためにデータセンターとサンプルデータに通信する必要がある。
これにより、通信効率が良く、勾配計算の数を最小限に抑える分散最適化アルゴリズムの必要性が生じる。
通信効率が高く,$varepsilon$-approximate のソリューションを実現する。
論文 参考訳（メタデータ） (2024-04-03T06:55:59Z) - CORE: Common Random Reconstruction for Distributed Optimization with
Provable Low Communication Complexity [110.50364486645852]
コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。
本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
論文 参考訳（メタデータ） (2023-09-23T08:45:27Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。