論文の概要: Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression

• arxiv url: http://arxiv.org/abs/2206.03665v1
• Date: Wed, 8 Jun 2022 03:36:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-09 14:34:35.026645
• Title: Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression
• Title（参考訳）: 通信圧縮を用いた分散学習における下限と近似最適アルゴリズム
• Authors: Xinmeng Huang, Yiming Chen, Wotao Yin, Kun Yuan
• Abstract要約: 通信圧縮は、通信を減らす最も効果的な方法の1つである。 分散最適化と学習の最近の進歩は、通信圧縮が通信を減らす最も効果的な方法の1つであることを示している。
• 参考スコア（独自算出の注目度）: 33.217552987061474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent advances in distributed optimization and learning have shown that communication compression is one of the most effective means of reducing communication. While there have been many results on convergence rates under communication compression, a theoretical lower bound is still missing. Analyses of algorithms with communication compression have attributed convergence to two abstract properties: the unbiased property or the contractive property. They can be applied with either unidirectional compression (only messages from workers to server are compressed) or bidirectional compression. In this paper, we consider distributed stochastic algorithms for minimizing smooth and non-convex objective functions under communication compression. We establish a convergence lower bound for algorithms whether using unbiased or contractive compressors in unidirection or bidirection. To close the gap between the lower bound and the existing upper bounds, we further propose an algorithm, NEOLITHIC, which almost reaches our lower bound (up to logarithm factors) under mild conditions. Our results also show that using contractive bidirectional compression can yield iterative methods that converge as fast as those using unbiased unidirectional compression. The experimental results validate our findings.
• Abstract（参考訳）: 分散最適化と学習の最近の進歩は、通信圧縮が通信を減らす最も効果的な方法の1つであることを示している。 通信圧縮下での収束率には多くの結果があるが、理論上の下限はいまだに欠けている。 通信圧縮を伴うアルゴリズムの解析は、2つの抽象的性質(偏りのない性質と収縮的性質)に収束している。 それらは一方向圧縮(ワーカからサーバへのメッセージのみ圧縮)または双方向圧縮で適用できる。 本稿では,コミュニケーション圧縮下での滑らかで非凸な対象関数を最小化するための分散確率アルゴリズムについて検討する。 一方向または二方向の非バイアス圧縮機を用いても、アルゴリズムの収束低境界を確立する。 下界と既存の上界の間のギャップを埋めるため、より穏やかな条件下で下界(対数係数まで)にほぼ到達する新石器式アルゴリズムを提案する。 また, 両方向圧縮を用いた場合, 非バイアスの一方向圧縮と同程度の速度で収束する反復的手法が得られた。 実験結果は我々の発見を裏付ける。

関連論文リスト

• 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)
• Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression [31.107056382542417]
  通信圧縮は通信オーバーヘッドを軽減するための重要な戦略である。 軽度条件下での圧縮のほぼ最適アルゴリズムであるNEOLITHICを提案する。
  論文  参考訳（メタデータ） (2023-05-12T17:02:43Z)
• 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)
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free! [72.31332210635524]
  分散最適化手法は、中央コーディネータを使わずに、機械学習モデルのデバイス上でのトレーニングを可能にする。 ランダム化圧縮演算子を適用し,通信ボトルネックに対処する新しいランダム化一階法を提案する。 本手法は,ベースラインに比べて通信数の増加を伴わずに問題を解くことができることを示す。
  論文  参考訳（メタデータ） (2020-11-03T13:35:53Z)
• Optimal Gradient Compression for Distributed and Federated Learning [9.711326718689492]
  分散学習における計算ノード間の通信は、通常避けられない負担である。 通信効率の訓練アルゴリズムの最近の進歩は、圧縮技術を用いてボトルネックを減らしている。 本稿では,圧縮ベクトルの符号化に必要なビット数と圧縮誤差との基本的なトレードオフについて検討する。
  論文  参考訳（メタデータ） (2020-10-07T07:58:59Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。