論文の概要: 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は、不均衡な有向グラフ上で証明可能な加速を達成するための最初の分散化手法である。 数値実験は両手法の有効性を実証する。

関連論文リスト

• Fully First-Order Methods for Decentralized Bilevel Optimization [17.20330936572045]
  本稿では,エージェントが隣人とのみ通信する分散二段階最適化(DSBO)に焦点を当てる。 本稿では,既存の作品に広く採用されている2次オラクルよりもはるかに安価な1次オラクルのみを必要とする新しいアルゴリズムである,分散グラディエントDescent and Ascent with Gradient Tracking (DSGDA-GT)を提案する。
  論文  参考訳（メタデータ） (2024-10-25T06:11:43Z)
• Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps [4.471962177124311]
  分散機械学習では、異なるデータを持つ複数のエージェントにまたがる線形変数が大きな課題となる。 本稿では,原変数上のラグランジアン収束を実現するフレームワークは,エージェント間通信を必要としないことを示す。
  論文  参考訳（メタデータ） (2024-07-02T22:14:54Z)
• Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
  パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。 平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
  論文  参考訳（メタデータ） (2024-05-17T21:17:27Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。 解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
  論文  参考訳（メタデータ） (2024-03-11T09:10:37Z)
• CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
  本稿では,通信制限条件下で分散最適化問題を解くことを検討する。 CEDASと呼ばれる圧縮精密拡散法について述べる。 特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
  論文  参考訳（メタデータ） (2023-01-14T09:49:15Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。