論文の概要: On the Benefits of Multiple Gossip Steps in Communication-Constrained
Decentralized Optimization
- arxiv url: http://arxiv.org/abs/2011.10643v1
- Date: Fri, 20 Nov 2020 21:17:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-23 05:40:29.366976
- Title: On the Benefits of Multiple Gossip Steps in Communication-Constrained
Decentralized Optimization
- Title（参考訳）: 通信制約付き分散最適化における複数のゴシップステップの利点について
- Authors: Abolfazl Hashemi, Anish Acharya, Rudrajit Das, Haris Vikalo, Sujay
Sanghavi, Inderjit Dhillon
- Abstract要約: ステップサイズが一定である$O(logfrac1epsilon)$の反復を$O(logfrac1epsilon)$とすることで、スムーズな非圧縮勾配目的に対する最適値の$epsilon$に収束できることを示す。
我々の知る限り、これは圧縮された通信圧縮パラメータの下での非最適化の収束結果を導出した最初の研究である。
- 参考スコア（独自算出の注目度）: 29.42301299741866
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In decentralized optimization, it is common algorithmic practice to have
nodes interleave (local) gradient descent iterations with gossip (i.e.
averaging over the network) steps. Motivated by the training of large-scale
machine learning models, it is also increasingly common to require that
messages be {\em lossy compressed} versions of the local parameters. In this
paper, we show that, in such compressed decentralized optimization settings,
there are benefits to having {\em multiple} gossip steps between subsequent
gradient iterations, even when the cost of doing so is appropriately accounted
for e.g. by means of reducing the precision of compressed information. In
particular, we show that having $O(\log\frac{1}{\epsilon})$ gradient iterations
{with constant step size} - and $O(\log\frac{1}{\epsilon})$ gossip steps
between every pair of these iterations - enables convergence to within
$\epsilon$ of the optimal value for smooth non-convex objectives satisfying
Polyak-\L{}ojasiewicz condition. This result also holds for smooth strongly
convex objectives. To our knowledge, this is the first work that derives
convergence results for nonconvex optimization under arbitrary communication
compression.
- Abstract（参考訳）: 分散最適化では、ノードを(局所的な)勾配降下反復をゴシップ(ネットワーク上の平均化)ステップでインターリーブするアルゴリズムが一般的である。
大規模機械学習モデルのトレーニングによって動機付けられたメッセージは、ローカルパラメータの可逆圧縮バージョンを要求されることがますます一般的になっている。
本稿では,圧縮された分散最適化設定において,圧縮情報の精度を低下させるなど,そのコストが適切に考慮されている場合でも,後続の勾配イテレーションの間に"em multiple"のゴシップステップを持つことにメリットがあることを示す。
特に、これらの各イテレーション間の$o(\log\frac{1}{\epsilon})$gradient iterations {with constant step size} - and $o(\log\frac{1}{\epsilon})$ gossip stepを、polyak-\l{}ojasiewicz条件を満たす滑らかな非凸目的に対して最適な値である$\epsilon$に収束できることを示す。
この結果は滑らかな強凸目的にも当てはまる。
我々の知る限り、これは任意の通信圧縮の下で非凸最適化の収束結果を導出する最初の研究である。
関連論文リスト
- Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。
両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。
$(textFG)2textU$は本質的に並列コンピューティングをサポートするように設計されており、大規模分散コンピューティングシステムを効果的に活用することができる。
論文 参考訳（メタデータ） (2024-06-20T08:21:52Z) - Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach [32.36073823372713]
機械学習モデルでは、アルゴリズムはその勾配のためにデータセンターとサンプルデータに通信する必要がある。
これにより、通信効率が良く、勾配計算の数を最小限に抑える分散最適化アルゴリズムの必要性が生じる。
通信効率が高く,$varepsilon$-approximate のソリューションを実現する。
論文 参考訳（メタデータ） (2024-04-03T06:55:59Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - 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 Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - 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) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳（メタデータ） (2021-11-01T15:43:36Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳（メタデータ） (2020-10-22T22:54:54Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳（メタデータ） (2020-05-15T21:14:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。