TY - GEN

T1 - Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

AU - Li, Zhize

AU - Kovalev, Dmitry

AU - Qian, Xun

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2021-09-16
Acknowledgements: KAUST Baseline Research Fund.

PY - 2020

Y1 - 2020

N2 - 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 ((1 + omega) root L/mu log 1/epsilon) for mu-strongly convex problems and O ((1 + omega )root L/epsilon )for convex problems, respectively, where w is the compression parameter. Our results improve upon the ex- isting non-accelerated rates O ((1 + omega) L/mu log 1/epsilon) and O ((1 + omega ) L/epsilon), 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 (O) over tilde (omega + root L/mu + root(omega/n +root omega/n)omega L/mu) , where n is the number of devices/workers and hides the logarithmic factor log This improves upon the previous best result (O) over tilde (omega + L/mu+omega L/n mu) 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.

AB - 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 ((1 + omega) root L/mu log 1/epsilon) for mu-strongly convex problems and O ((1 + omega )root L/epsilon )for convex problems, respectively, where w is the compression parameter. Our results improve upon the ex- isting non-accelerated rates O ((1 + omega) L/mu log 1/epsilon) and O ((1 + omega ) L/epsilon), 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 (O) over tilde (omega + root L/mu + root(omega/n +root omega/n)omega L/mu) , where n is the number of devices/workers and hides the logarithmic factor log This improves upon the previous best result (O) over tilde (omega + L/mu+omega L/n mu) 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.

UR - http://hdl.handle.net/10754/662100

UR - https://arxiv.org/pdf/2002.11364

M3 - Conference contribution

BT - International Conference on Machine Learning (ICML)

PB - arXiv

ER -