論文の概要: Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning
- arxiv url: http://arxiv.org/abs/2206.02450v1
- Date: Mon, 6 Jun 2022 09:25:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-07 18:29:00.246908
- Title: Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning
- Title(参考訳): 分散学習における部分ストラグラー緩和のための最適化に基づくブロック座標勾配符号化
- Authors: Qi Wang, Ying Cui, Chenglin Li, Junni Zou, Hongkai Xiong
- Abstract要約: 本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。
L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
- 参考スコア(独自算出の注目度): 58.91954425047425
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient coding schemes effectively mitigate full stragglers in distributed
learning by introducing identical redundancy in coded local partial derivatives
corresponding to all model parameters. However, they are no longer effective
for partial stragglers as they cannot utilize incomplete computation results
from partial stragglers. This paper aims to design a new gradient coding scheme
for mitigating partial stragglers in distributed learning. Specifically, we
consider a distributed system consisting of one master and N workers,
characterized by a general partial straggler model and focuses on solving a
general large-scale machine learning problem with L model parameters using
gradient coding. First, we propose a coordinate gradient coding scheme with L
coding parameters representing L possibly different diversities for the L
coordinates, which generates most gradient coding schemes. Then, we consider
the minimization of the expected overall runtime and the maximization of the
completion probability with respect to the L coding parameters for coordinates,
which are challenging discrete optimization problems. To reduce computational
complexity, we first transform each to an equivalent but much simpler discrete
problem with N\llL variables representing the partition of the L coordinates
into N blocks, each with identical redundancy. This indicates an equivalent but
more easily implemented block coordinate gradient coding scheme with N coding
parameters for blocks. Then, we adopt continuous relaxation to further reduce
computational complexity. For the resulting minimization of expected overall
runtime, we develop an iterative algorithm of computational complexity O(N^2)
to obtain an optimal solution and derive two closed-form approximate solutions
both with computational complexity O(N). For the resultant maximization of the
completion probability, we develop an iterative algorithm of...
- Abstract(参考訳): すべてのモデルパラメータに対応する符号化された局所偏微分に同一の冗長性を導入することにより、分散学習におけるフルストラグラーを効果的に緩和する。
しかし、部分トラグラーによる不完全な計算結果を利用できないため、部分トラグラーにはもはや有効ではない。
本稿では,分散学習における部分ストラグラーの軽減を目的とした新しい勾配符号化手法を提案する。
具体的には,1人のマスタとn人のワーカーからなる分散システムを,一般的な部分的ストラグラーモデルで特徴付けし,勾配符号化を用いたlモデルパラメータを用いた一般大規模機械学習問題を解くことに焦点を当てた。
まず、L座標の多様性を示すL符号パラメータを用いた座標勾配符号化方式を提案し、ほとんどの勾配符号化方式を生成する。
そこで, 離散最適化問題である座標のL符号パラメータに関して, 期待される全実行時間の最小化と完了確率の最大化を考察する。
計算の複雑さを減らすために、まず l 座標の分割を表す n\lll 変数を n 個のブロックにそれぞれ同一の冗長性を持つ、等価だがはるかに単純な離散問題に変換する。
これは、ブロックに対してn個の符号パラメータを持つ等価だが実装が容易なブロック座標勾配符号化スキームを示している。
次に,計算の複雑さをさらに減らすために,連続緩和を採用する。
その結果,計算複雑性 O(N^2) の反復アルゴリズムを開発し,計算複雑性 O(N) の2つの閉形式近似解を導出する。
完了確率の最大化のために、我々は...の反復アルゴリズムを開発する。
関連論文リスト
- Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
混合整数非NLPプログラム(MINLP)はエネルギーシステムや輸送など様々な領域で発生するが、解決は困難である。
機械学習の最近の進歩は、最適化のための学習として知られる領域において、顕著な成功をもたらしている。
勾配を保ちながら整数出力を生成する2つの異なる補正層を提案する。
論文 参考訳(メタデータ) (2024-10-14T20:14:39Z) - 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) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳(メタデータ) (2022-09-01T11:05:26Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Optimization-Based GenQSGD for Federated Edge Learning [12.371264770814097]
我々は、連合学習(FL)のための一般化された並列最小バッチ収束降下(SGD)アルゴリズムを提案する。
我々は,時間収束誤差の下でのエネルギーコストを最小限に抑えるために,アルゴリズムパラメータを最適化する。
その結果,既存のFLアルゴリズムよりも有意な利得が得られた。
論文 参考訳(メタデータ) (2021-10-25T14:25:11Z) - Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity [14.93584434176082]
擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。
我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
論文 参考訳(メタデータ) (2021-08-19T15:50:41Z) - Block majorization-minimization with diminishing radius for constrained
nonconvex optimization [9.907540661545328]
BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。
凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
論文 参考訳(メタデータ) (2020-12-07T07:53:09Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。