論文の概要: Lower Bounds and Accelerated Algorithms in Distributed Stochastic
Optimization with Communication Compression
- arxiv url: http://arxiv.org/abs/2305.07612v1
- Date: Fri, 12 May 2023 17:02:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-15 11:59:30.338495
- Title: Lower Bounds and Accelerated Algorithms in Distributed Stochastic
Optimization with Communication Compression
- Title（参考訳）: 通信圧縮を用いた分散確率最適化における下限と高速化アルゴリズム
- Authors: Yutong He, Xinmeng Huang, Yiming Chen, Wotao Yin, Kun Yuan
- Abstract要約: 通信圧縮は通信オーバーヘッドを軽減するための重要な戦略である。
軽度条件下での圧縮のほぼ最適アルゴリズムであるNEOLITHICを提案する。
- 参考スコア（独自算出の注目度）: 31.107056382542417
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Communication compression is an essential strategy for alleviating
communication overhead by reducing the volume of information exchanged between
computing nodes in large-scale distributed stochastic optimization. Although
numerous algorithms with convergence guarantees have been obtained, the optimal
performance limit under communication compression remains unclear.
In this paper, we investigate the performance limit of distributed stochastic
optimization algorithms employing communication compression. We focus on two
main types of compressors, unbiased and contractive, and address the
best-possible convergence rates one can obtain with these compressors. We
establish the lower bounds for the convergence rates of distributed stochastic
optimization in six different settings, combining strongly-convex,
generally-convex, or non-convex functions with unbiased or contractive
compressor types. To bridge the gap between lower bounds and existing
algorithms' rates, we propose NEOLITHIC, a nearly optimal algorithm with
compression that achieves the established lower bounds up to logarithmic
factors under mild conditions. Extensive experimental results support our
theoretical findings. This work provides insights into the theoretical
limitations of existing compressors and motivates further research into
fundamentally new compressor properties.
- Abstract（参考訳）: 通信圧縮は,大規模分散確率最適化において,計算ノード間で交換される情報の量を削減し,通信オーバーヘッドを軽減するための重要な戦略である。
収束保証付きアルゴリズムが多数得られたが、通信圧縮時の最適性能限界は未定である。
本稿では,通信圧縮を用いた分散確率最適化アルゴリズムの性能限界について検討する。
圧縮機は非バイアスと収縮の2種類の圧縮機に焦点を合わせ, 圧縮機で得られる最良の収束率に対処する。
分散確率最適化の収束率の下位境界を6つの異なる設定で定め, 強凸, 一般凸, 非凸関数を非バイアス圧縮器型と組み合わせた。
低境界と既存のアルゴリズムの速度のギャップを埋めるため、軽度条件下で確立された下界から対数的要因までを圧縮するほぼ最適なアルゴリズムNEOLITHICを提案する。
広範な実験結果が我々の理論的知見を支持している。
この研究は、既存の圧縮機の理論的限界に対する洞察を与え、基本的な新しい圧縮機特性に関するさらなる研究を動機付ける。
関連論文リスト
- Differential error feedback for communication-efficient decentralized learning [48.924131251745266]
本稿では,差分量子化と誤りフィードバックをブレンドする分散通信効率学習手法を提案する。
その結果,平均二乗誤差と平均ビットレートの両面において通信効率が安定であることが示唆された。
その結果、小さなステップサイズで有限ビットの場合には、圧縮がない場合に達成可能な性能が得られることが判明した。
論文 参考訳（メタデータ） (2024-06-26T15:11:26Z) - 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) - Learning Accurate Performance Predictors for Ultrafast Automated Model
Compression [86.22294249097203]
フレキシブルネットワーク展開のための超高速自動モデル圧縮フレームワークSeerNetを提案する。
本手法は,探索コストを大幅に削減した競合精度・複雑度トレードオフを実現する。
論文 参考訳（メタデータ） (2023-04-13T10:52:49Z) - Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with
Communication Compression [33.217552987061474]
通信圧縮は、通信を減らす最も効果的な方法の1つである。
分散最適化と学習の最近の進歩は、通信圧縮が通信を減らす最も効果的な方法の1つであることを示している。
論文 参考訳（メタデータ） (2022-06-08T03:36:34Z) - EF-BV: A Unified Theory of Error Feedback and Variance Reduction
Mechanisms for Biased and Unbiased Compression in Distributed Optimization [7.691755449724637]
分散最適化と学習では、異なるコンピュータユニット間の通信がボトルネックとなることが多い。
圧縮演算子には2つのクラスがあり、それを利用するアルゴリズムは別々である。
本稿では,特にDIANAとEF21を復元する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-09T10:44:23Z) - On Arbitrary Compression for Decentralized Consensus and Stochastic
Optimization over Directed Networks [0.6526824510982799]
所望の圧縮比に応じてメッセージを圧縮する反復型アルゴリズムを提案する。
既存の文献とは対照的に、任意の圧縮比が可能である。
滑らかな関数に対する分散最適化問題に対して明確な収束率を示す。
論文 参考訳（メタデータ） (2022-04-18T04:41:56Z) - Decentralized Composite Optimization with Compression [36.75785129001134]
非滑らかなコンポーネントを用いた分散合成最適化問題について検討する。
圧縮を伴う収束アンダーライン分散アルゴリズム Prox-LEAD を提案する。
我々の定理は、Prox-LEADが任意の圧縮精度で動作することを示している。
論文 参考訳（メタデータ） (2021-08-10T04:54:52Z) - Compressing Neural Networks: Towards Determining the Optimal Layer-wise
Decomposition [62.41259783906452]
本稿では,ディープニューラルネットワークのための新しいグローバル圧縮フレームワークを提案する。
各層を自動的に解析し、最適な層間圧縮比を特定する。
我々の結果は、現代のニューラルネットワークのグローバルなパフォーマンス-サイズトレードオフに関する将来の研究のための新たな道を開く。
論文 参考訳（メタデータ） (2021-07-23T20:01:30Z) - Innovation Compression for Communication-efficient Distributed
Optimization with Linear Convergence [23.849813231750932]
本稿では,強い凸最適化問題を解決するために,通信効率のよい線形収束分散(COLD)アルゴリズムを提案する。
イノベーションベクターを圧縮することで、COLDは$delta$-contractedコンプレッサーのクラスに対して線形収束を達成できます。
数値実験は、異なる圧縮機の下で両方のアルゴリズムの利点を実証する。
論文 参考訳（メタデータ） (2021-05-14T08:15:18Z) - PowerGossip: Practical Low-Rank Communication Compression in
Decentralized Deep Learning [62.440827696638664]
本稿では,近隣労働者間のモデル差を直接圧縮する簡単なアルゴリズムを提案する。
中央集権的なディープラーニングのためにPowerSGDにインスパイアされたこのアルゴリズムは、パワーステップを使用して、1ビットあたりの転送情報を最大化する。
論文 参考訳（メタデータ） (2020-08-04T09:14:52Z) - Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。
原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。
underline Decentralized with compression, LEAD。
論文 参考訳（メタデータ） (2020-07-01T04:35:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。