論文の概要: CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression

• arxiv url: http://arxiv.org/abs/2107.09461v1
• Date: Tue, 20 Jul 2021 13:01:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-21 14:44:10.959890
• Title: CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Title（参考訳）: CANITA:通信圧縮による分散凸最適化の高速化
• Authors: Zhize Li, Peter Richt\'arik
• Abstract要約: 本稿では,分散最適化のためのエンハン圧縮・高速化勾配法を提案し,これをCANITAと呼ぶ。 我々の結果は、$n$のデバイス数が大きければ、CANITAはより高速な収束率$OBig(sqrtfracLepsilonBig)$、すなわち通信ラウンドの数は$OBig(sqrtfracLepsilonBig)$を達成できることを示している。
• 参考スコア（独自算出の注目度）: 17.259824817932294
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Due to the high communication cost in distributed and federated learning, methods relying on compressed communication are becoming increasingly popular. Besides, the best theoretically and practically performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of communications (faster convergence), e.g., Nesterov's accelerated gradient descent (Nesterov, 2004) and Adam (Kingma and Ba, 2014). In order to combine the benefits of communication compression and convergence acceleration, we propose a \emph{compressed and accelerated} gradient method for distributed optimization, which we call CANITA. Our CANITA achieves the \emph{first accelerated rate} $O\bigg(\sqrt{\Big(1+\sqrt{\frac{\omega^3}{n}}\Big)\frac{L}{\epsilon}} + \omega\big(\frac{1}{\epsilon}\big)^{\frac{1}{3}}\bigg)$, which improves upon the state-of-the-art non-accelerated rate $O\left((1+\frac{\omega}{n})\frac{L}{\epsilon} + \frac{\omega^2+n}{\omega+n}\frac{1}{\epsilon}\right)$ of DIANA (Khaled et al., 2020b) for distributed general convex problems, where $\epsilon$ is the target error, $L$ is the smooth parameter of the objective, $n$ is the number of machines/devices, and $\omega$ is the compression parameter (larger $\omega$ means more compression can be applied, and no compression implies $\omega=0$). Our results show that as long as the number of devices $n$ is large (often true in distributed/federated learning), or the compression $\omega$ is not very high, CANITA achieves the faster convergence rate $O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$, i.e., the number of communication rounds is $O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$ (vs. $O\big(\frac{L}{\epsilon}\big)$ achieved by previous works). As a result, CANITA enjoys the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds).
• Abstract（参考訳）: 分散学習とフェデレーション学習の通信コストが高いことから, 圧縮通信に依存する手法が普及しつつある。 さらに、最も理論的かつ実用的な勾配型法は、通信数(より高速な収束)を減らすために、例えばネステロフの加速勾配降下(Nesterov, 2004)とアダム(Kingma and Ba, 2014)の何らかの形式に依存している。 通信圧縮と収束加速度の利点を組み合わせるために,分散最適化のための<emph{compressed andaccelerated}勾配法を提案し,これをcanitaと呼ぶ。 Our CANITA achieves the \emph{first accelerated rate} $O\bigg(\sqrt{\Big(1+\sqrt{\frac{\omega^3}{n}}\Big)\frac{L}{\epsilon}} + \omega\big(\frac{1}{\epsilon}\big)^{\frac{1}{3}}\bigg)$, which improves upon the state-of-the-art non-accelerated rate $O\left((1+\frac{\omega}{n})\frac{L}{\epsilon} + \frac{\omega^2+n}{\omega+n}\frac{1}{\epsilon}\right)$ of DIANA (Khaled et al., 2020b) for distributed general convex problems, where $\epsilon$ is the target error, $L$ is the smooth parameter of the objective, $n$ is the number of machines/devices, and $\omega$ is the compression parameter (larger $\omega$ means more compression can be applied, and no compression implies $\omega=0$). 我々の結果は、$n$のデバイス数が大きければ(分散/フェデレート学習においてしばしば真である)、あるいは$\omega$が大きすぎる場合、CANITAは、$O\Big(\sqrt {\frac{L}{\epsilon}}\Big)$、すなわち、通信ラウンドの数は$O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$(vs.$O\big(\frac{L}{\epsilon}\big)$)$(vs.$O\big(\frac{L}{\epsilon}\big)$であることを示す。 その結果、CANITAは圧縮(各ラウンドでの圧縮通信)と加速度(通信ラウンドが大幅に少ない)の両方の利点を享受できる。

関連論文リスト

• Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
  非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。 本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。 これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
  論文  参考訳（メタデータ） (2024-08-10T09:03:06Z)
• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• 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)
• 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)
• Faster Rates for Compressed Federated Learning with Client-Variance Reduction [23.169998435268504]
  我々はCOFIGとFRECONが$O(frac(1+omega)sqrtNSepsilon2)$通信ラウンドに収束していることを示す。 凸設定では、COFIGは$O(frac(1+omega)sqrtNSepsilon2)$通信ラウンドに収束する。
  論文  参考訳（メタデータ） (2021-12-24T16:28:18Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization [31.066505042748826]
  本稿では,最初の加速圧縮勾配降下法(ACGD)を提案する。 ACGD は$OBig( (1+omega)sqrtfracLmulog frac1epsilonBig)$ for $mu$-strongly convex problem。 また、ACGD(ADIANA)の分散変種を提案し、収束率を$widetildeOBig(+sqrtfracLmu+sqrtbig)$とする。
  論文  参考訳（メタデータ） (2020-02-26T09:03:23Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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