論文の概要: Revisiting Decentralized ProxSkip: Achieving Linear Speedup

• arxiv url: http://arxiv.org/abs/2310.07983v2
• Date: Fri, 19 Apr 2024 05:21:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-22 20:16:45.845810
• Title: Revisiting Decentralized ProxSkip: Achieving Linear Speedup
• Title（参考訳）: 分散型 ProxSkip の再検討 - 線形スピードアップの実現
• Authors: Luyao Guo, Sulaiman A. Alghunaim, Kun Yuan, Laurent Condat, Jinde Cao,
• Abstract要約: ProxSkipilonの既存の解析は限定凸設定であり、ProxSkipilonの強い線形速度を達成できない。 本稿では, ProxSkipilon が線形スピードアップを実現し,通信の確率に比例した通信オーバーヘッドを低減することができることを示す。
• 参考スコア（独自算出の注目度）: 50.28561300894826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ProxSkip algorithm for decentralized and federated learning is gaining increasing attention due to its proven benefits in accelerating communication complexity while maintaining robustness against data heterogeneity. However, existing analyses of ProxSkip are limited to the strongly convex setting and do not achieve linear speedup, where convergence performance increases linearly with respect to the number of nodes. So far, questions remain open about how ProxSkip behaves in the non-convex setting and whether linear speedup is achievable. In this paper, we revisit decentralized ProxSkip and address both questions. We demonstrate that the leading communication complexity of ProxSkip is $\mathcal{O}\left(\frac{p\sigma^2}{n\epsilon^2}\right)$ for non-convex and convex settings, and $\mathcal{O}\left(\frac{p\sigma^2}{n\epsilon}\right)$ for the strongly convex setting, where $n$ represents the number of nodes, $p$ denotes the probability of communication, $\sigma^2$ signifies the level of stochastic noise, and $\epsilon$ denotes the desired accuracy level. This result illustrates that ProxSkip achieves linear speedup and can asymptotically reduce communication overhead proportional to the probability of communication. Additionally, for the strongly convex setting, we further prove that ProxSkip can achieve linear speedup with network-independent stepsizes.
• Abstract（参考訳）: 分散学習とフェデレーション学習のためのProxSkipアルゴリズムは、データ不均一性に対する堅牢性を維持しつつ、通信の複雑さを加速させることの証明された利点により、注目を集めている。 しかし、既存の ProxSkip の解析は強い凸設定に限られており、ノード数に対して収束性能が線形に増加するような線形高速化は達成できない。 今のところ、ProxSkipが非凸設定でどのように振る舞うのか、線形スピードアップが達成可能かどうか、疑問が残る。 本稿では、分散化されたProxSkipを再検討し、両方の疑問に対処する。 ProxSkipの主な通信複雑性は$\mathcal{O}\left(\frac{p\sigma^2}{n\epsilon^2}\right)$と$\mathcal{O}\left(\frac{p\sigma^2}{n\epsilon}\right)$である。 この結果は, ProxSkipが線形スピードアップを実現し, 通信の確率に比例した通信オーバーヘッドを漸近的に低減できることを示す。 さらに, 強い凸条件下では, ProxSkip がネットワーク非依存のステップサイズで線形高速化できることを示す。

関連論文リスト

• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization [36.777745196161035]
  本稿では,分散合成(平滑+非平滑)最適化のための通信効率の良いMG-Skipを提案する。 MG-Skipは通信の複雑さを最適に達成し,非滑らかなセットアップにおけるローカル更新の利点を確認する。
  論文  参考訳（メタデータ） (2023-12-19T05:13:16Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
  我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。 我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。 我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
  論文  参考訳（メタデータ） (2023-07-14T01:32:16Z)
• 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)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。 MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
  論文  参考訳（メタデータ） (2022-02-02T20:10:40Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  本稿では,有向ピアツーピアネットワーク上での分散強化学習(DisRL)のポリシー評価問題に対する非同期手法を提案する。 ネットワークの他のノードを待つことなく、各ノードは隣人からの(おそらく遅れた)情報を使用して、いつでもローカルに値関数を更新できる。
  論文  参考訳（メタデータ） (2020-03-01T08:12:08Z)

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

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