Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

By Zhize Li, Dmitry Kovalev, Xun Qian, Peter Richtárik. 2020

158 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

FedML: A Research Library and Benchmark for Federated Machine Learning (2020, methodology): “ICML 2020 Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization[152] a5a logistic regression mushrooms logistic regression a9a logistic regression w6a LIBSVM logistic regression ICLR 2020 Federated Learning with Matched Averaging [5] CIFAR-10 VGG-9 16 Shakespheare sa”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[47] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik.”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “Compared to parameter server based baselines using distributed gradient descent (GD), quantized GD (QGD), and Accelerated DIANA [25], Q-GADMM achieves faster convergence and signiﬁcantly less communication cost.”
Federated Learning Based on Dynamic Regularization (2021, methodology): “These variants include using a decreasing learning rate (Li et al., 2020b); modifying device empirical loss dynamically (Li et al., 2020a); or modifying server side updates (Hsu et al., 2019; Reddi et al., 2020).”
Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach (2020, background): “In particular, there have been several works on various aspects of FL, including preserving the privacy of users [6–9] and lowering communication cost [10– 13].”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, methodology): “A gradient acceleration approach with compression is proposed in [25].”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, methodology): “2 compares Q-GADMM with GADMM and two PSbased schemes (QGD and ADIANA [175]) in terms of the”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, methodology): “More precisely, we combine two main tools: 1) an unbiased compression operator C : R d → R d that reduces the number of bits exchanged, and 2) a memory process that reduces the size of the signal to compress, and consequently the error [25, 20].”
Distributed learning with compressed gradient differences (2019, unknown): “…multiple extensions including the generalization to the general unbiased compression and variance reduced variants [7], accelerated versions [14], decentralized versions [13], combinations with biased compression and methods with delayed updates [6], extensions to the second-order…”
Personalized Federated Learning using Hypernetworks (2021, background): “Duchi et al. (2014); McMahan et al. (2017b); Agarwal et al. (2018); Zhu et al. (2019) proposed new meth-ods for preserving privacy, and Reisizadeh et al. (2020); Dai et al. (2019); Basu et al. (2020); Li et al. (2020b); Stich (2018) focused on reducing communication cost.”