論文の概要: Communication-efficient Decentralized Local SGD over Undirected Networks
- arxiv url: http://arxiv.org/abs/2011.03255v1
- Date: Fri, 6 Nov 2020 09:34:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 05:34:50.007644
- Title: Communication-efficient Decentralized Local SGD over Undirected Networks
- Title(参考訳): 非指向ネットワーク上の通信効率の良い分散ローカルSGD
- Authors: Tiancheng Qin, S. Rasoul Etesami, C\'esar A. Uribe
- Abstract要約: 我々は、$n$エージェントのネットワークがグローバル関数$F$を最小化しようとする分散学習問題を考察する。
通信ラウンド数と各エージェントの計算労力のトレードオフを分析する。
その結果,R=Omega(n)$通信ラウンドのみを用いることで,O(1/nT)$というスケールの誤差を実現できることがわかった。
- 参考スコア(独自算出の注目度): 2.3572498744567123
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the distributed learning problem where a network of $n$ agents
seeks to minimize a global function $F$. Agents have access to $F$ through
noisy gradients, and they can locally communicate with their neighbors a
network. We study the Decentralized Local SDG method, where agents perform a
number of local gradient steps and occasionally exchange information with their
neighbors. Previous algorithmic analysis efforts have focused on the specific
network topology (star topology) where a leader node aggregates all agents'
information. We generalize that setting to an arbitrary network by analyzing
the trade-off between the number of communication rounds and the computational
effort of each agent. We bound the expected optimality gap in terms of the
number of iterates $T$, the number of workers $n$, and the spectral gap of the
underlying network. Our main results show that by using only $R=\Omega(n)$
communication rounds, one can achieve an error that scales as $O({1}/{nT})$,
where the number of communication rounds is independent of $T$ and only depends
on the number of agents. Finally, we provide numerical evidence of our
theoretical results through experiments on real and synthetic data.
- Abstract(参考訳): 我々は、$n$エージェントのネットワークがグローバル関数$F$を最小化しようとする分散学習問題を考察する。
エージェントはノイズの勾配を通じて$f$にアクセスでき、近隣のネットワークとローカルに通信することができる。
本稿では、エージェントが複数の局所勾配ステップを実行し、時には隣人と情報交換を行う分散ローカルSDG法について検討する。
従来のアルゴリズム分析の取り組みは、リーダーノードが全てのエージェントの情報を集める特定のネットワークトポロジー(スタートポロジー)に焦点を当ててきた。
通信ラウンド数と各エージェントの計算労力のトレードオフを分析することにより、任意のネットワークに設定を一般化する。
我々は、反復数$T$、労働者数$n$、基礎となるネットワークのスペクトルギャップという観点から、期待される最適性ギャップを定めている。
我々の主な結果は、$R=\Omega(n)$通信ラウンドのみを使用することで、$O({1}/{nT})$にスケールするエラーを実現できることを示している。
最後に,実データおよび合成データを用いた実験により,理論結果の数値的証明を行う。
関連論文リスト
- Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳(メタデータ) (2023-05-10T20:29:29Z) - Convergence Rates for Localized Actor-Critic in Networked Markov
Potential Games [12.704529528199062]
本稿では,ネットワーク内のノードにエージェントが関連付けられているネットワークマルコフポテンシャルゲームについて紹介する。
それぞれのエージェントは独自の潜在機能を持ち、各エージェントの報酬は、近隣のエージェントの状態と行動にのみ依存する。
これはエージェントの数に依存しないマルチエージェント競争ゲームに対する最初の有限サンプル境界である。
論文 参考訳(メタデータ) (2023-03-08T20:09:58Z) - Communication-Efficient Topologies for Decentralized Learning with
$O(1)$ Consensus Rate [35.698182247676414]
分散最適化は分散学習における新たなパラダイムであり、エージェントは中央サーバを使わずにピアツーピア通信によってネットワーク全体のソリューションを実現する。
エージェントの情報が混在する速度によって,ネットワーク全体のソリューションに到達するためのイテレーションの総数が影響を受けることを示す。
本稿では,(ほぼ)一定の等級とネットワークサイズに依存しないコンセンサス率を有する新しいトポロジであるEquiTopoを提案する。
論文 参考訳(メタデータ) (2022-10-14T15:02:01Z) - 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) - On the Performance of Gradient Tracking with Local Updates [10.14746251086461]
LU-GTは通信品質は同じであるが、任意のネットワークトポロジが可能であることを示す。
数値的な例では、局所的な更新は特定のレシエーションにおける通信コストを低下させる可能性がある。
論文 参考訳(メタデータ) (2022-10-10T15:13:23Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳(メタデータ) (2022-07-07T06:16:19Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳(メタデータ) (2022-01-21T01:26:08Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - Learning Connectivity for Data Distribution in Robot Teams [96.39864514115136]
グラフニューラルネットワーク(GNN)を用いたアドホックネットワークにおけるデータ分散のためのタスク非依存,分散化,低レイテンシ手法を提案する。
当社のアプローチは、グローバル状態情報に基づいたマルチエージェントアルゴリズムを各ロボットで利用可能にすることで機能させます。
我々は,情報の平均年齢を報酬関数として強化学習を通じて分散gnn通信政策を訓練し,タスク固有の報酬関数と比較してトレーニング安定性が向上することを示す。
論文 参考訳(メタデータ) (2021-03-08T21:48:55Z) - Multi-Level Local SGD for Heterogeneous Hierarchical Networks [11.699472346137739]
異種ネットワークにおける学習・非目的フレームワークのための分散勾配法であるマルチレベルローカルSGDを提案する。
まず,マルチレベル局所SGDアルゴリズムを記述する統一数学的手法を提案する。
次に,アルゴリズムの理論的解析を行う。
論文 参考訳(メタデータ) (2020-07-27T19:14:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。