論文の概要: Communication-efficient SGD: From Local SGD to One-Shot Averaging
- arxiv url: http://arxiv.org/abs/2106.04759v1
- Date: Wed, 9 Jun 2021 01:10:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:51:56.766718
- Title: Communication-efficient SGD: From Local SGD to One-Shot Averaging
- Title(参考訳): 通信効率のよいSGD:ローカルSGDからワンショット平均化
- Authors: Artin Spiridonoff, Alex Olshevsky and Ioannis Ch. Paschalidis
- Abstract要約: 複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。
そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
- 参考スコア(独自算出の注目度): 16.00658606157781
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider speeding up stochastic gradient descent (SGD) by parallelizing it
across multiple workers. We assume the same data set is shared among $N$
workers, who can take SGD steps and coordinate with a central server. While it
is possible to obtain a linear reduction in the variance by averaging all the
stochastic gradients at every step, this requires a lot of communication
between the workers and the server, which can dramatically reduce the gains
from parallelism. The Local SGD method, proposed and analyzed in the earlier
literature, suggests machines should make many local steps between such
communications. While the initial analysis of Local SGD showed it needs $\Omega
( \sqrt{T} )$ communications for $T$ local gradient steps in order for the
error to scale proportionately to $1/(NT)$, this has been successively improved
in a string of papers, with the state-of-the-art requiring $\Omega \left( N
\left( \mbox{ polynomial in log } (T) \right) \right)$ communications. In this
paper, we suggest a Local SGD scheme that communicates less overall by
communicating less frequently as the number of iterations grows. Our analysis
shows that this can achieve an error that scales as $1/(NT)$ with a number of
communications that is completely independent of $T$. In particular, we show
that $\Omega(N)$ communications are sufficient. Empirical evidence suggests
this bound is close to tight as we further show that $\sqrt{N}$ or $N^{3/4}$
communications fail to achieve linear speed-up in simulations. Moreover, we
show that under mild assumptions, the main of which is twice differentiability
on any neighborhood of the optimal solution, one-shot averaging which only uses
a single round of communication can also achieve the optimal convergence rate
asymptotically.
- Abstract(参考訳): 複数の作業員を並列化することで,確率勾配降下 (sgd) の高速化を検討する。
同じデータセットが、sgdステップと中央サーバとの調整が可能な、n$ workers間で共有されていると仮定します。
全てのステップで確率勾配を平均化することで分散の線形化が可能であるが、これは労働者とサーバの間で多くの通信を必要とするため、並列化による利得を劇的に減少させることができる。
従来の文献で提案され分析されたローカルSGD法は、機械がそのような通信の間に多くのローカルステップを踏むべきであることを示唆している。
ローカルSGDの初期分析では、エラーが1/(NT)$に比例してスケールするために、$T$ローカル勾配ステップに対して$\Omega ( \sqrt{T} )$通信が必要であることが示されたが、これは一連の論文で連続的に改善され、現状では$\Omega \left( N \left( \mbox{ polynomial in log } (T) \right)$通信が必要である。
本稿では,反復数の増加に伴って通信頻度を小さくすることで,全体通信の少ないローカルSGD方式を提案する。
我々の分析によると、これは1/(NT)$のスケールのエラーを達成でき、多くの通信が$T$から完全に独立している。
特に、$\Omega(N)$通信が十分であることを示す。
実証的な証拠によると、この境界は、シミュレーションで$\sqrt{n}$ または $n^{3/4}$ の通信が線形速度アップを達成できないことを示すため、ほぼタイトである。
さらに, 最適解の任意の近傍における2倍の微分可能性を持つ軽微な仮定の下では, 1ラウンドの通信のみを用いるワンショット平均化は, 漸近的に最適収束率を達成できることを示す。
関連論文リスト
- The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity [2.845817138242963]
DGT(Decentralized Gradient Tracking)とDGD(Decentralized Gradient Descent)の2つの基本的な分散最適化手法を再検討する。
K > 1$ ローカル更新のステップを組み込むことで通信の複雑さを低減できることを示す。
論文 参考訳(メタデータ) (2024-03-23T00:01:34Z) - A Quadratic Synchronization Rule for Distributed Deep Learning [66.68264684667562]
本研究は、擬似同期規則(QSR)と呼ばれる$H$を決定するための理論基底法を提案する。
ResNet と ViT の実験により、QSR を用いた局所勾配法は、他の同期戦略よりもテスト精度を一貫して向上することが示された。
論文 参考訳(メタデータ) (2023-10-22T21:38:57Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳(メタデータ) (2023-05-10T20:29:29Z) - 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) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳(メタデータ) (2021-04-06T15:34:14Z) - Sparse Normal Means Estimation with Sublinear Communication [13.257075075199781]
通信制約のある分散環境における正規平均推定の問題点を考察する。
信号対雑音比(SNR)がわずかに高くなると、$mu$のサポートはより少ない通信で正確に回復できることを示す。
論文 参考訳(メタデータ) (2021-02-05T08:52:25Z) - Local SGD With a Communication Overhead Depending Only on the Number of
Workers [17.886554223172517]
複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。
同じデータセットが$n$のワーカー間で共有されていると仮定します。
従来の文献で提案され分析されたローカルSGD法は、機械がそのような通信の間に多くのローカルステップを踏むべきであることを示唆している。
論文 参考訳(メタデータ) (2020-06-03T23:33:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。