論文の概要: A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization

• arxiv url: http://arxiv.org/abs/2312.11861v2
• Date: Sun, 27 Oct 2024 07:37:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 16:00:54.611550
• Title: A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization
• Title（参考訳）: 分散合成最適化のための確率的多重ゴシップ通信を用いた近似勾配法
• Authors: Luyao Guo, Luqing Wang, Xinli Shi, Jinde Cao,
• Abstract要約: 本稿では,分散合成(平滑+非平滑)最適化のための通信効率の良いMG-Skipを提案する。 MG-Skipは通信の複雑さを最適に達成し,非滑らかなセットアップにおけるローカル更新の利点を確認する。
• 参考スコア（独自算出の注目度）: 36.777745196161035
• License:
• Abstract: Decentralized optimization methods with local updates have recently gained attention for their provable ability to communication acceleration. In these methods, nodes perform several iterations of local computations between the communication rounds. Nevertheless, this capability is effective only when the loss function is smooth and the network is sufficiently well-connected. In this paper, we propose a communication-efficient method MG-Skip with probabilistic local updates and multi-gossip communications for decentralized composite (smooth + nonsmooth) optimization, whose stepsize is independent of the number of local updates and the network topology. Without any additional condition for network connectivity, MG-Skip allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting, while its iteration complexity is $\mathcal{O}\left(\kappa \log \frac{1}{\epsilon}\right)$ and communication complexity is only $\mathcal{O}\left(\sqrt{\frac{\kappa}{(1-\rho)}} \log \frac{1}{\epsilon}\right)$, where $\kappa$ is the condition number of the loss function, $\rho$ reflects the connectivity of the network topology, and $\epsilon$ is the target accuracy. The theoretical results demonstrate that MG-Skip achieves the optimal communication complexity and confirm the benefits of local updates in the nonsmooth setup.
• Abstract（参考訳）: 局所的な更新を伴う分散最適化手法は,近年,通信高速化の実現可能性に注目が集まっている。 これらの方法では、ノードは通信ラウンド間の局所的な計算を繰り返し実行します。 それでも、この機能は損失関数が滑らかでネットワークが十分に接続された場合にのみ有効である。 本稿では,分散化合成(平滑+非平滑)最適化のための確率的局所更新とマルチゴシップ通信を備えた通信効率のよいMG-Skipを提案する。 MG-Skipは、ネットワーク接続のための追加条件なしで、マルチゴシップ通信を、強い凸設定でほとんどのイテレーションでスキップすることができるが、そのイテレーションの複雑さは$\mathcal{O}\left(\kappa \log \frac{1}{\epsilon}\right)$と通信の複雑さは、$\mathcal{O}\left(\sqrt{\frac{\kappa}{(1-\rho)}} \log \frac{1}{\epsilon}\right)$、$\kappa$は損失関数の条件番号であり、$\rho$はネットワークトポロジの接続を反映している。 理論的な結果は,MG-Skipが通信複雑性を最適に達成し,非滑らかなセットアップにおける局所的な更新の利点を確認することを証明している。

関連論文リスト

• 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)
• DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
  DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。 我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-07-26T08:47:54Z)
• Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization [37.85806148420504]
  分散最適化環境では、$n$最適化ノードのネットワーク内の各エージェント$i$は、プライベート関数$f_i$を持つ。 最適化対応の選択ルールを導入し、高い2倍のコスト改善で隣人を選択する。 提案したセットワイズGSルールは,ネットワークの最大次数による高速化を実現する。
  論文  参考訳（メタデータ） (2022-07-15T15:37:03Z)
• 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 SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
  複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。 そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:10:34Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization [29.42301299741866]
  ステップサイズが一定である$O(logfrac1epsilon)$の反復を$O(logfrac1epsilon)$とすることで、スムーズな非圧縮勾配目的に対する最適値の$epsilon$に収束できることを示す。 我々の知る限り、これは圧縮された通信圧縮パラメータの下での非最適化の収束結果を導出した最初の研究である。
  論文  参考訳（メタデータ） (2020-11-20T21:17:32Z)

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

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