論文の概要: Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

• arxiv url: http://arxiv.org/abs/2002.11364v2
• Date: Thu, 25 Jun 2020 21:36:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 16:01:27.871095
• Title: Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Title（参考訳）: 分散・フェデレーション最適化における圧縮勾配降下の加速
• Authors: Zhize Li and Dmitry Kovalev and Xun Qian and Peter Richt\'arik
• Abstract要約: 本稿では,最初の加速圧縮勾配降下法(ACGD)を提案する。 ACGD は$OBig( (1+omega)sqrtfracLmulog frac1epsilonBig)$ for $mu$-strongly convex problem。 また、ACGD(ADIANA)の分散変種を提案し、収束率を$widetildeOBig(+sqrtfracLmu+sqrtbig)$とする。
• 参考スコア（独自算出の注目度）: 31.066505042748826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Due to the high communication cost in distributed and federated learning problems, methods relying on compression of communicated messages are becoming increasingly popular. While in other contexts the best performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of iterations, there are no methods which combine the benefits of both gradient compression and acceleration. In this paper, we remedy this situation and propose the first accelerated compressed gradient descent (ACGD) methods. In the single machine regime, we prove that ACGD enjoys the rate $O\Big((1+\omega)\sqrt{\frac{L}{\mu}}\log \frac{1}{\epsilon}\Big)$ for $\mu$-strongly convex problems and $O\Big((1+\omega)\sqrt{\frac{L}{\epsilon}}\Big)$ for convex problems, respectively, where $\omega$ is the compression parameter. Our results improve upon the existing non-accelerated rates $O\Big((1+\omega)\frac{L}{\mu}\log \frac{1}{\epsilon}\Big)$ and $O\Big((1+\omega)\frac{L}{\epsilon}\Big)$, respectively, and recover the optimal rates of accelerated gradient descent as a special case when no compression ($\omega=0$) is applied. We further propose a distributed variant of ACGD (called ADIANA) and prove the convergence rate $\widetilde{O}\Big(\omega+\sqrt{\frac{L}{\mu}}+\sqrt{\big(\frac{\omega}{n}+\sqrt{\frac{\omega}{n}}\big)\frac{\omega L}{\mu}}\Big)$, where $n$ is the number of devices/workers and $\widetilde{O}$ hides the logarithmic factor $\log \frac{1}{\epsilon}$. This improves upon the previous best result $\widetilde{O}\Big(\omega + \frac{L}{\mu}+\frac{\omega L}{n\mu} \Big)$ achieved by the DIANA method of Mishchenko et al. (2019). Finally, we conduct several experiments on real-world datasets which corroborate our theoretical results and confirm the practical superiority of our accelerated methods.
• Abstract（参考訳）: 分散学習問題や連合学習問題における通信コストが高いため,通信メッセージの圧縮に依存する手法が普及している。 他の文脈では、最も優れた勾配型手法は繰り返し回数を減らすために加速度/モーメントの何らかの形式に依存するが、勾配圧縮と加速度の両方の利点を組み合わせた方法はない。 本稿では、この状況を緩和し、最初の加速圧縮勾配降下法(ACGD)を提案する。 単一マシンのシステムでは、agcd は $o\big((1+\omega)\sqrt{\frac{l}{\mu}}\log \frac{1}{\epsilon}\big)$ と $o\big((1+\omega)\sqrt{\frac{l}{\epsilon}}\big)$ のそれぞれ対流問題に対して$o\big((1+\omega)\sqrt{\frac{l}{\epsilon}}\big)$ を満足していることが証明される。 その結果,既存の非加速速度である$o\big((1+\omega)\frac{l}{\mu}\log \frac{1}{\epsilon}\big)$と$o\big((1+\omega)\frac{l}{\epsilon}\big)$をそれぞれ改善し,圧縮(\omega=0$)が適用されない場合の特別な場合として,加速勾配降下の最適速度を回復した。 さらに、ACGD の分散変種 (ADIANA) を提案し、収束率 $\widetilde{O}\Big(\omega+\sqrt {\frac{L}{\mu}}+\sqrt{\big(\frac {\omega}{n}+\sqrt{\frac{\omega}{n}}\big)\frac {\omega L}{\mu}}\big)$, $n$ はデバイス/ワーカーの数であり、$\widetilde{O}$ は対数係数 $\log \frac{1}{\epsilon}$ を隠蔽する。 これにより、Mishchenko et al. (2019) の DIANA 法で達成された $\widetilde{O}\Big(\omega + \frac{L}{\mu}+\frac{\omega L}{n\mu} \Big)$ が改善される。 最後に, 実世界のデータセットについて実験を行い, 理論結果と照合し, 高速化手法の実用的優位性を確認した。

関連論文リスト

• On the Complexity of Finite-Sum Smooth Optimization under the Polyak-{\L}ojasiewicz Condition [14.781921087738967]
  本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
  論文  参考訳（メタデータ） (2024-02-04T17:14:53Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression [17.259824817932294]
  本稿では,分散最適化のためのエンハン圧縮・高速化勾配法を提案し,これをCANITAと呼ぶ。 我々の結果は、$n$のデバイス数が大きければ、CANITAはより高速な収束率$OBig(sqrtfracLepsilonBig)$、すなわち通信ラウンドの数は$OBig(sqrtfracLepsilonBig)$を達成できることを示している。
  論文  参考訳（メタデータ） (2021-07-20T13:01:56Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method [17.259824817932294]
  有限和最適化のための新しい加速分散還元法ANITAを提案する。 一般凸設定では、ANITA は収束結果 $Obig(nminbig1+logfrac1epsilonsqrtn) を達成する。 強い凸設定では、ANITA が最適収束結果 $OBig(big(n+sqrtfracnLmubig)logfracnLmubig)$ matching the lower bound $ を達成することも示している。
  論文  参考訳（メタデータ） (2021-03-21T08:14:40Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
  改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。 高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
  論文  参考訳（メタデータ） (2020-02-24T08:07:08Z)

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

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