論文の概要: MG-Skip: Random Multi-Gossip Skipping Method for Nonsmooth Distributed Optimization

• arxiv url: http://arxiv.org/abs/2312.11861v1
• Date: Tue, 19 Dec 2023 05:13:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 17:02:45.704329
• Title: MG-Skip: Random Multi-Gossip Skipping Method for Nonsmooth Distributed Optimization
• Title（参考訳）: MG-Skip:非平滑分散最適化のためのランダムマルチゴシップスキー法
• Authors: Luyao Guo, Luqing Wang, Xinli Shi, Jinde Cao
• Abstract要約: 本稿では損失関数の条件として$kappa$を用いたMG+Skipの最初のイテレーションを示す。 MG-Skipはアップデートの余分な条件なしに複数ラウンドのゴシップ通信を可能にする。 我々の知る限り、MG+Skipは損失関数が滑らかな(強い凸)局所的な複雑さを持ち、$kappa$がネットワークの接続性を反映している場合の知識を達成する。
• 参考スコア（独自算出の注目度）: 40.177044531605446
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributed optimization methods with probabilistic local updates have recently gained attention for their provable ability to communication acceleration. Nevertheless, this capability is effective only when the loss function is smooth and the network is sufficiently well-connected. In this paper, we propose the first linear convergent method MG-Skip with probabilistic local updates for nonsmooth distributed optimization. Without any extra condition for the network connectivity, MG-Skip allows for the multiple-round gossip communication to be skipped in most iterations, 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 and $\rho$ reflects the connectivity of the network topology. To the best of our knowledge, MG-Skip achieves the best communication complexity when the loss function has the smooth (strongly convex)+nonsmooth (convex) composite form.
• 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)

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

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