論文の概要: Unbiased Compression Saves Communication in Distributed Optimization:
When and How Much?
- arxiv url: http://arxiv.org/abs/2305.16297v3
- Date: Wed, 10 Jan 2024 18:55:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-13 04:06:18.628119
- Title: Unbiased Compression Saves Communication in Distributed Optimization:
When and How Much?
- Title(参考訳): Unbiased Compressionは分散最適化におけるコミュニケーションを省く: いつ、どのくらいか?
- Authors: Yutong He, Xinmeng Huang, Kun Yuan
- Abstract要約: 通信圧縮は、圧縮された勾配とモデルパラメータを伝達することで通信オーバーヘッドを軽減することができる。
通信圧縮によって通信コストが削減されるかどうかは不明である。
独立な非バイアス圧縮を用いることで、すべての局所的滑らか度定数が制約された場合、最大$Theta(sqrtminn, kappa)$で通信コストを削減できることを示す。
- 参考スコア(独自算出の注目度): 22.701976655513043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Communication compression is a common technique in distributed optimization
that can alleviate communication overhead by transmitting compressed gradients
and model parameters. However, compression can introduce information
distortion, which slows down convergence and incurs more communication rounds
to achieve desired solutions. Given the trade-off between lower per-round
communication costs and additional rounds of communication, it is unclear
whether communication compression reduces the total communication cost.
This paper explores the conditions under which unbiased compression, a widely
used form of compression, can reduce the total communication cost, as well as
the extent to which it can do so. To this end, we present the first theoretical
formulation for characterizing the total communication cost in distributed
optimization with communication compression. We demonstrate that unbiased
compression alone does not necessarily save the total communication cost, but
this outcome can be achieved if the compressors used by all workers are further
assumed independent. We establish lower bounds on the communication rounds
required by algorithms using independent unbiased compressors to minimize
smooth convex functions and show that these lower bounds are tight by refining
the analysis for ADIANA. Our results reveal that using independent unbiased
compression can reduce the total communication cost by a factor of up to
$\Theta(\sqrt{\min\{n, \kappa\}})$ when all local smoothness constants are
constrained by a common upper bound, where $n$ is the number of workers and
$\kappa$ is the condition number of the functions being minimized. These
theoretical findings are supported by experimental results.
- Abstract(参考訳): 通信圧縮は、圧縮勾配とモデルパラメータを伝達することで通信オーバーヘッドを軽減する分散最適化において一般的な手法である。
しかし、圧縮は情報歪みを導入し、収束を遅くし、より多くの通信ラウンドを発生させ、望ましいソリューションを実現する。
ラウンド単位の通信コストの低減と追加の通信ラウンドのトレードオフを考えると,通信圧縮によって通信コストが削減されるかどうかは不明である。
本稿では,広範に使用される圧縮形式である非バイアス圧縮が,通信コストを低減し,その程度を低減できる条件について検討する。
そこで本研究では,通信圧縮を伴う分散最適化における通信コストを特徴付ける最初の理論的定式化を行う。
非バイアス圧縮だけでは通信コストを節約できるわけではないが、全作業員が使用する圧縮機を独立と仮定すれば、この結果が得られる。
独立な非バイアス圧縮機を用いたアルゴリズムが要求する通信ラウンドの下位境界を確立し、滑らかな凸関数を最小化し、これらの下位境界がADIANAの分析を精査することによってきついことを示す。
独立な非バイアス圧縮を用いることで、すべての局所滑らか度定数が共通の上限によって制約されている場合、最大$\Theta(\sqrt{\min\{n, \kappa\}})$で通信コストを削減でき、$n$は労働者数、$\kappa$は最小化される関数の条件数である。
これらの理論的知見は実験結果によって裏付けられている。
関連論文リスト
- 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) - Stochastic Controlled Averaging for Federated Learning with Communication Compression [36.09135695005069]
我々は,非バイアス圧縮とバイアス圧縮をサポートするために,SCALLIONとSCAFCOMという2つの圧縮FLアルゴリズムを提案する。
両手法は通信や計算の複雑さの観点から既存のFL法よりも優れている。
論文 参考訳(メタデータ) (2023-08-16T06:35:36Z) - Lower Bounds and Accelerated Algorithms in Distributed Stochastic
Optimization with Communication Compression [31.107056382542417]
通信圧縮は通信オーバーヘッドを軽減するための重要な戦略である。
軽度条件下での圧縮のほぼ最適アルゴリズムであるNEOLITHICを提案する。
論文 参考訳(メタデータ) (2023-05-12T17:02:43Z) - Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with
Communication Compression [33.217552987061474]
通信圧縮は、通信を減らす最も効果的な方法の1つである。
分散最適化と学習の最近の進歩は、通信圧縮が通信を減らす最も効果的な方法の1つであることを示している。
論文 参考訳(メタデータ) (2022-06-08T03:36:34Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳(メタデータ) (2021-10-07T09:38:15Z) - Towards Compact CNNs via Collaborative Compression [166.86915086497433]
チャネルプルーニングとテンソル分解を結合してCNNモデルを圧縮する協調圧縮方式を提案する。
52.9%のFLOPを削減し、ResNet-50で48.4%のパラメータを削除しました。
論文 参考訳(メタデータ) (2021-05-24T12:07:38Z) - A Linearly Convergent Algorithm for Decentralized Optimization: Sending
Less Bits for Free! [72.31332210635524]
分散最適化手法は、中央コーディネータを使わずに、機械学習モデルのデバイス上でのトレーニングを可能にする。
ランダム化圧縮演算子を適用し,通信ボトルネックに対処する新しいランダム化一階法を提案する。
本手法は,ベースラインに比べて通信数の増加を伴わずに問題を解くことができることを示す。
論文 参考訳(メタデータ) (2020-11-03T13:35:53Z) - On Biased Compression for Distributed Learning [55.89300593805943]
バイアス圧縮機が単一ノードと分散設定の両方において線形収束率をもたらすことを初めて示す。
理論的保証と実用性能を期待できる新しいバイアス圧縮機を提案する。
論文 参考訳(メタデータ) (2020-02-27T19:52:24Z) - Uncertainty Principle for Communication Compression in Distributed and
Federated Learning and the Search for an Optimal Compressor [5.09755285351264]
我々は,ベクトルのカシン表現にインスパイアされた非バイアス圧縮法を考察し,これをエムカシン圧縮(KC)と呼ぶ。
KC は、各ベクトルエントリごとに数ビットしか通信する必要のない状態であっても、明示的な公式を導出するエム次元独立分散境界を享受する。
論文 参考訳(メタデータ) (2020-02-20T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。