論文の概要: On Arbitrary Compression for Decentralized Consensus and Stochastic
Optimization over Directed Networks
- arxiv url: http://arxiv.org/abs/2204.08160v1
- Date: Mon, 18 Apr 2022 04:41:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-19 17:01:06.784257
- Title: On Arbitrary Compression for Decentralized Consensus and Stochastic
Optimization over Directed Networks
- Title（参考訳）: 分散型コンセンサスに対する任意圧縮と指向ネットワーク上の確率最適化について
- Authors: Mohammad Taha Toghani, C\'esar A. Uribe
- Abstract要約: 所望の圧縮比に応じてメッセージを圧縮する反復型アルゴリズムを提案する。
既存の文献とは対照的に、任意の圧縮比が可能である。
滑らかな関数に対する分散最適化問題に対して明確な収束率を示す。
- 参考スコア（独自算出の注目度）: 0.6526824510982799
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the decentralized consensus and stochastic optimization problems
with compressed communications over static directed graphs. We propose an
iterative gradient-based algorithm that compresses messages according to a
desired compression ratio. The proposed method provably reduces the
communication overhead on the network at every communication round. Contrary to
existing literature, we allow for arbitrary compression ratios in the
communicated messages. We show a linear convergence rate for the proposed
method on the consensus problem. Moreover, we provide explicit convergence
rates for decentralized stochastic optimization problems on smooth functions
that are either (i) strongly convex, (ii) convex, or (iii) non-convex. Finally,
we provide numerical experiments to illustrate convergence under arbitrary
compression ratios and the communication efficiency of our algorithm.
- Abstract（参考訳）: 静的有向グラフ上の圧縮通信における分散コンセンサスと確率的最適化問題について検討する。
所望の圧縮比に応じてメッセージを圧縮する反復勾配に基づくアルゴリズムを提案する。
提案手法は,各通信ラウンドにおけるネットワーク上の通信オーバーヘッドを確実に低減する。
既存の文献とは対照的に、通信されたメッセージの任意の圧縮比率を許容する。
本稿では,コンセンサス問題に対する提案手法の線形収束率を示す。
さらに、滑らかな関数上の分散確率最適化問題に対して明示的な収束率を提供する。
(i)強凸,強凸
(ii)凸,又は
(iii)非凸。
最後に,任意の圧縮比下での収束と,アルゴリズムの通信効率を示す数値実験を行った。
関連論文リスト
- Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。
平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
論文 参考訳（メタデータ） (2024-05-17T21:17:27Z) - Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity [92.1840862558718]
ダウンリンク圧縮のための新しい手法であるMARINA-Pを導入する。
置換圧縮機を用いたMARINA-Pは、作業者数に応じてサーバ間通信の複雑さを向上できることを示す。
本稿では,MARINA-Pとアップリンク圧縮とモーメントステップを組み合わせた手法であるM3を導入する。
論文 参考訳（メタデータ） (2024-02-09T13:58:33Z) - Lower Bounds and Accelerated Algorithms in Distributed Stochastic
Optimization with Communication Compression [31.107056382542417]
通信圧縮は通信オーバーヘッドを軽減するための重要な戦略である。
軽度条件下での圧縮のほぼ最適アルゴリズムであるNEOLITHICを提案する。
論文 参考訳（メタデータ） (2023-05-12T17:02:43Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Decentralized Composite Optimization with Compression [36.75785129001134]
非滑らかなコンポーネントを用いた分散合成最適化問題について検討する。
圧縮を伴う収束アンダーライン分散アルゴリズム Prox-LEAD を提案する。
我々の定理は、Prox-LEADが任意の圧縮精度で動作することを示している。
論文 参考訳（メタデータ） (2021-08-10T04:54:52Z) - Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks [17.49477125920901]
汎用マルチエージェントネットワーク上での2つの通信効率の良い分散最適化アルゴリズムを提案する。
最初のアルゴリズムは、Push-Pull法と通信圧縮を組み合わせた勾配追跡手法である。
第2のアルゴリズムはCPP(B-CPP)の放送的バージョンであり、目的関数上の同じ条件下での線形収束率も達成する。
論文 参考訳（メタデータ） (2021-06-14T08:53:30Z) - A Linearly Convergent Algorithm for Decentralized Optimization: Sending
Less Bits for Free! [72.31332210635524]
分散最適化手法は、中央コーディネータを使わずに、機械学習モデルのデバイス上でのトレーニングを可能にする。
ランダム化圧縮演算子を適用し,通信ボトルネックに対処する新しいランダム化一階法を提案する。
本手法は,ベースラインに比べて通信数の増加を伴わずに問題を解くことができることを示す。
論文 参考訳（メタデータ） (2020-11-03T13:35:53Z) - Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。
原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。
underline Decentralized with compression, LEAD。
論文 参考訳（メタデータ） (2020-07-01T04:35:00Z) - Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。
モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。
本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-23T18:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。