論文の概要: 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は損失関数が滑らかな(強い凸)+非滑らかな(凸)合成形式を持つとき、最高の通信複雑性を達成する。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [58.372148767703955]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳(メタデータ) (2024-02-14T13:44:16Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳(メタデータ) (2022-10-25T11:37:11Z) - 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) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳(メタデータ) (2022-05-30T14:28:02Z) - 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) - Learning with Smooth Hinge Losses [15.288802707471792]
我々は、$psi_G(alpha;sigma)$と$psi_M(alpha;sigma)$の2つの滑らかなヒンジ損失を紹介します。
テキスト分類タスクの実験では,提案したSSVMが実世界のアプリケーションに有効であることが示されている。
論文 参考訳(メタデータ) (2021-02-27T14:50:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。