論文の概要: Provably Accelerated Decentralized Gradient Method Over Unbalanced
Directed Graphs
- arxiv url: http://arxiv.org/abs/2107.12065v1
- Date: Mon, 26 Jul 2021 09:42:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-27 15:41:50.876431
- Title: Provably Accelerated Decentralized Gradient Method Over Unbalanced
Directed Graphs
- Title(参考訳): 非平衡有向グラフ上での分散勾配法の実現可能性
- Authors: Zhuoqing Song, Lei Shi, Shi Pu, Ming Yan
- Abstract要約: APD と APD-SC は $Oleft(frac1k2right)$ と $Oleft(left (1 - CsqrtfracmuLright)kright)$ で収束することを示す。
我々の知る限り、APDとAPD-SCは、不均衡な有向グラフ上で証明可能な加速を達成するための最初の分散化手法である。
- 参考スコア(独自算出の注目度): 9.503564093758197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we consider the decentralized optimization problem in which a
network of $n$ agents, each possessing a smooth and convex objective function,
wish to collaboratively minimize the average of all the objective functions
through peer-to-peer communication in a directed graph. To solve the problem,
we propose two accelerated Push-DIGing methods termed APD and APD-SC for
minimizing non-strongly convex objective functions and strongly convex ones,
respectively. We show that APD and APD-SC respectively converge at the rates
$O\left(\frac{1}{k^2}\right)$ and $O\left(\left(1 -
C\sqrt{\frac{\mu}{L}}\right)^k\right)$ up to constant factors depending only on
the mixing matrix. To the best of our knowledge, APD and APD-SC are the first
decentralized methods to achieve provable acceleration over unbalanced directed
graphs. Numerical experiments demonstrate the effectiveness of both methods.
- Abstract(参考訳): 本研究では,n$エージェントのネットワークが,それぞれが滑らかで凸な目的関数を持ち,有向グラフにおけるピアツーピア通信を通じて,すべての目的関数の平均を協調的に最小化しようとする分散最適化問題を考える。
そこで本研究では,非強凸目的関数と強凸関数をそれぞれ最小化するために,adp と apd-sc と呼ばれる2つの高速化プッシュダイジング法を提案する。
APD と APD-SC はそれぞれ$O\left(\frac{1}{k^2}\right)$ と $O\left(\left(1C\sqrt {\frac{\mu}{L}}\right)^k\right)$ で収束することを示した。
我々の知る限り、APDとAPD-SCは、不均衡な有向グラフ上で証明可能な加速を達成するための最初の分散化手法である。
数値実験は両手法の有効性を実証する。
関連論文リスト
- Adaptive Federated Learning Over the Air [108.62635460744109]
オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。
解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
論文 参考訳(メタデータ) (2024-03-11T09:10:37Z) - Clip21: Error Feedback for Gradient Clipping [8.979288425347702]
我々はClip21を設計し、分散メソッドに対する最初の有効で実用的なフィードバックメカニズムを設計する。
提案手法は, 競合手法よりも高速に収束する。
論文 参考訳(メタデータ) (2023-05-30T10:41:42Z) - CEDAS: A Compressed Decentralized Stochastic Gradient Method with
Improved Convergence [10.770843226843418]
本稿では,通信制限条件下でのマルチエージェントネットワークの分散最適化問題について考察する。
提案手法は,CEDAS (Convexizes) を圧縮し,滑らかな凸関連ステップの適応的なステップを実現する。
論文 参考訳(メタデータ) (2023-01-14T09:49:15Z) - Linear Convergence of Natural Policy Gradient Methods with Log-Linear
Policies [115.86431674214282]
我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。
両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
論文 参考訳(メタデータ) (2022-10-04T06:17:52Z) - DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over
Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。
Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。
提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文 参考訳(メタデータ) (2022-08-29T18:01:42Z) - MDPGT: Momentum-based Decentralized Policy Gradient Tracking [29.22173174168708]
マルチエージェント強化学習のための運動量に基づく分散型ポリシー勾配追跡(MDPGT)を提案する。
MDPGTは、グローバル平均の$N$ローカルパフォーマンス関数の$epsilon-stationaryポイントに収束するために$mathcalO(N-1epsilon-3)$の最良のサンプル複雑性を実現する。
これは、分散モデルレス強化学習における最先端のサンプル複雑さよりも優れています。
論文 参考訳(メタデータ) (2021-12-06T06:55:51Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳(メタデータ) (2021-05-11T08:09:31Z) - Push-SAGA: A decentralized stochastic algorithm with variance reduction
over directed graphs [18.53372294049107]
Push-SAGAはノードの有向ネットワークに対する有限一階法のための分散一階法である。
我々はPush-SAGAが滑らかで凸な問題に対して線形収束を実現することを示す。
論文 参考訳(メタデータ) (2020-08-13T18:52:17Z) - Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。
原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。
underline Decentralized with compression, LEAD。
論文 参考訳(メタデータ) (2020-07-01T04:35:00Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。