論文の概要: Communication-Efficient Topologies for Decentralized Learning with
$O(1)$ Consensus Rate
- arxiv url: http://arxiv.org/abs/2210.07881v1
- Date: Fri, 14 Oct 2022 15:02:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-17 18:12:24.899818
- Title: Communication-Efficient Topologies for Decentralized Learning with
$O(1)$ Consensus Rate
- Title(参考訳): O(1)$コンセンサスレートによる分散学習のためのコミュニケーション効率の良いトポロジ
- Authors: Zhuoqing Song, Weijian Li, Kexin Jin, Lei Shi, Ming Yan, Wotao Yin,
Kun Yuan
- Abstract要約: 分散最適化は分散学習における新たなパラダイムであり、エージェントは中央サーバを使わずにピアツーピア通信によってネットワーク全体のソリューションを実現する。
エージェントの情報が混在する速度によって,ネットワーク全体のソリューションに到達するためのイテレーションの総数が影響を受けることを示す。
本稿では,(ほぼ)一定の等級とネットワークサイズに依存しないコンセンサス率を有する新しいトポロジであるEquiTopoを提案する。
- 参考スコア(独自算出の注目度): 35.698182247676414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decentralized optimization is an emerging paradigm in distributed learning in
which agents achieve network-wide solutions by peer-to-peer communication
without the central server. Since communication tends to be slower than
computation, when each agent communicates with only a few neighboring agents
per iteration, they can complete iterations faster than with more agents or a
central server. However, the total number of iterations to reach a network-wide
solution is affected by the speed at which the agents' information is ``mixed''
by communication. We found that popular communication topologies either have
large maximum degrees (such as stars and complete graphs) or are ineffective at
mixing information (such as rings and grids). To address this problem, we
propose a new family of topologies, EquiTopo, which has an (almost) constant
degree and a network-size-independent consensus rate that is used to measure
the mixing efficiency.
In the proposed family, EquiStatic has a degree of $\Theta(\ln(n))$, where
$n$ is the network size, and a series of time-dependent one-peer topologies,
EquiDyn, has a constant degree of 1. We generate EquiDyn through a certain
random sampling procedure. Both of them achieve an $n$-independent consensus
rate. We apply them to decentralized SGD and decentralized gradient tracking
and obtain faster communication and better convergence, theoretically and
empirically. Our code is implemented through BlueFog and available at
\url{https://github.com/kexinjinnn/EquiTopo}
- Abstract(参考訳): 分散最適化は分散学習における新たなパラダイムであり、エージェントは中央サーバなしでピアツーピア通信によってネットワーク全体のソリューションを実現する。
通信は計算よりも遅い傾向があるため、各エージェントが各イテレーション毎に数個のエージェントと通信する場合、より多くのエージェントや中央サーバよりも速いイテレーションを完了することができる。
しかし、ネットワーク全体のソリューションに到達するためのイテレーションの総数は、エージェントの情報が通信によって‘mixed’される速度に影響される。
一般的な通信トポロジは、恒星や完全グラフのような大きな最大度を持つか、情報(リングやグリッドなど)を混ぜるには効果がないことがわかった。
そこで本研究では,混合効率を測定するためのネットワークサイズ非依存コンセンサス率と(ほぼ)一定次数を持つ新しい位相群であるequitopoを提案する。
提案されたファミリーでは、EquiStatic は$\Theta(\ln(n))$ の次数を持ち、$n$ はネットワークサイズであり、時間依存の一ピア位相の列 EquiDyn は定数次数 1 を持つ。
特定のランダムサンプリング手順によってEquiDynを生成する。
どちらもn$独立のコンセンサス率を達成している。
我々は、分散SGDと分散勾配追跡に適用し、より高速な通信とより優れた収束を得る。
私たちのコードはBlueFogを通じて実装され、 \url{https://github.com/kexinjinnn/EquiTopo}で利用可能です。
関連論文リスト
- FedScalar: A Communication efficient Federated Learning [0.0]
フェデレーテッド・ラーニング(FL)は分散機械学習でかなりの人気を集めている。
emphFedScalarは、エージェントが単一のスカラーを使用して更新を通信することを可能にする。
論文 参考訳(メタデータ) (2024-10-03T07:06:49Z) - Asynchronous Local Computations in Distributed Bayesian Learning [8.516532665507835]
本稿では,高速な計算と通信オーバヘッドを同時に低減するために,ゴシップに基づく通信を提案する。
我々は、特に低データ範囲において、より高速な初期収束と性能精度の向上を観察する。
UCI MLレポジトリのガンマ望遠鏡とmHealthデータセットで,それぞれ平均78%,90%以上の分類精度を達成した。
論文 参考訳(メタデータ) (2023-11-06T20:11:41Z) - Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-08-31T12:22:40Z) - 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) - Exponential Graph is Provably Efficient for Decentralized Deep Training [30.817705471352614]
いわゆる指数グラフでは、すべてのノードが$O(log(n)$ 隣り合っていて、$n$ はノードの総数である。
この研究は、そのようなグラフが高速通信と効果的な平均化の両方に同時に結びつくことを証明している。
また、各ノードが反復ごとに1つの隣接ノードと通信する$log(n)$ 1-peer指数グラフの列は、共に正確な平均化を達成することができる。
論文 参考訳(メタデータ) (2021-10-26T02:33:39Z) - 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) - Communication-efficient Decentralized Local SGD over Undirected Networks [2.3572498744567123]
我々は、$n$エージェントのネットワークがグローバル関数$F$を最小化しようとする分散学習問題を考察する。
通信ラウンド数と各エージェントの計算労力のトレードオフを分析する。
その結果,R=Omega(n)$通信ラウンドのみを用いることで,O(1/nT)$というスケールの誤差を実現できることがわかった。
論文 参考訳(メタデータ) (2020-11-06T09:34:00Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳(メタデータ) (2020-10-02T10:41:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。