論文の概要: STL-SGD: Speeding Up Local SGD with Stagewise Communication Period
- arxiv url: http://arxiv.org/abs/2006.06377v2
- Date: Tue, 15 Dec 2020 15:19:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 13:05:29.905101
- Title: STL-SGD: Speeding Up Local SGD with Stagewise Communication Period
- Title（参考訳）: STL-SGD: 段階通信によるローカルSGDの高速化
- Authors: Shuheng Shen, Yifei Cheng, Jingchang Liu and Linli Xu
- Abstract要約: 局所勾配降下 (Local SGD) は通信の複雑さが低いために注目されている。
STL-SGDはミニバッチSGDと同じ収束率と線形スピードアップを保持することができる。
凸問題とノンフラクチャー問題の両方の実験は、STL-SGDの優れた性能を示している。
- 参考スコア（独自算出の注目度）: 19.691927007250417
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Distributed parallel stochastic gradient descent algorithms are workhorses
for large scale machine learning tasks. Among them, local stochastic gradient
descent (Local SGD) has attracted significant attention due to its low
communication complexity. Previous studies prove that the communication
complexity of Local SGD with a fixed or an adaptive communication period is in
the order of $O (N^{\frac{3}{2}} T^{\frac{1}{2}})$ and $O (N^{\frac{3}{4}}
T^{\frac{3}{4}})$ when the data distributions on clients are identical (IID) or
otherwise (Non-IID), where $N$ is the number of clients and $T$ is the number
of iterations. In this paper, to accelerate the convergence by reducing the
communication complexity, we propose \textit{ST}agewise \textit{L}ocal
\textit{SGD} (STL-SGD), which increases the communication period gradually
along with decreasing learning rate. We prove that STL-SGD can keep the same
convergence rate and linear speedup as mini-batch SGD. In addition, as the
benefit of increasing the communication period, when the objective is strongly
convex or satisfies the Polyak-\L ojasiewicz condition, the communication
complexity of STL-SGD is $O (N \log{T})$ and $O (N^{\frac{1}{2}}
T^{\frac{1}{2}})$ for the IID case and the Non-IID case respectively, achieving
significant improvements over Local SGD. Experiments on both convex and
non-convex problems demonstrate the superior performance of STL-SGD.
- Abstract（参考訳）: 分散並列確率勾配勾配アルゴリズムは大規模機械学習タスクのためのワークホースである。
中でも局所確率勾配降下(局所SGD)は,通信の複雑さが低かったために注目されている。
これまでの研究では、固定または適応的な通信期間を持つローカルSGDの通信複雑性が$O(N^{\frac{3}{2}} T^{\frac{1}{2}})$と$O(N^{\frac{3}{4}} T^{\frac{3}{4}})$の順にあることが証明されていた。
本稿では,コミュニケーションの複雑さを減らして収束を加速させるため,学習率の低下とともに通信期間を徐々に増加させる「textit{ST}agewise \textit{L}ocal \textit{SGD}」(STL-SGD)を提案する。
STL-SGD はミニバッチ SGD と同じ収束率と線形高速化を維持できることを示す。
加えて、通信期間を増加させる利点として、目的がポリak-\l ojasiewicz条件の強い凸または満足する場合、stl-sgdの通信複雑性は、それぞれiidケースと非iidケースに対して$o (n \log{t})$および$o (n^{\frac{1}{2}} t^{\frac{1}{2}})$であり、ローカルsgdよりも大幅に改善される。
凸問題と非凸問題の両方の実験は、STL-SGDの優れた性能を示す。
関連論文リスト
- A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity
in Federated Min-Max Learning [9.001405567602745]
本稿では,SAGDAがクライアント数とローカル更新ステップの両方で線形高速化を実現することを示す。
また,フェデレートされたmin-max学習のための標準FSGDA法の通信複雑性に関する現在の理解も進める。
論文 参考訳（メタデータ） (2022-10-02T20:04:50Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD
for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
ローカル手法は通信時間を短縮する有望なアプローチの1つである。
局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-02-12T15:12:17Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Communication-efficient SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。
そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
論文 参考訳（メタデータ） (2021-06-09T01:10:34Z) - Avoiding Communication in Logistic Regression [1.7780157772002312]
勾配降下(SGD)は、様々な機械学習問題を解くために最も広く使われている最適化手法の1つである。
並列的な設定では、SGDはイテレーション毎にプロセス間通信を必要とする。
本稿では,SGDを用いたロジスティック回帰問題を解くための新しいコミュニケーション回避手法を提案する。
論文 参考訳（メタデータ） (2020-11-16T21:14:39Z) - O(1) Communication for Distributed SGD through Two-Level Gradient
Averaging [0.0]
我々は,2段階勾配平均化(A2SGD)と呼ばれる戦略を導入し,すべての勾配を労働者1人当たりの局所的な平均値に統一する。
我々の理論的解析は、A2SGDがデフォルト分散SGDアルゴリズムと同様に収束していることを示している。
論文 参考訳（メタデータ） (2020-06-12T18:20:52Z) - A Unified Theory of Decentralized SGD with Changing Topology and Local
Updates [70.9701218475002]
分散通信方式の統一収束解析を導入する。
いくつかの応用に対して普遍収束率を導出する。
私たちの証明は弱い仮定に依存している。
論文 参考訳（メタデータ） (2020-03-23T17:49:15Z) - Variance Reduced Local SGD with Lower Communication Complexity [52.44473777232414]
本稿では,通信の複雑さをさらに軽減するために,分散化ローカルSGDを提案する。
VRL-SGDは、労働者が同一でないデータセットにアクセスしても、通信の複雑さが低い$O(Tfrac12 Nfrac32)$で、エンフラーイテレーションのスピードアップを達成する。
論文 参考訳（メタデータ） (2019-12-30T08:15:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。