Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks

By Xin Zhang, Jia Liu, Elizabeth Serena Bentley. 2018

28 citations recorded by the source corpus.

Network consensus optimization has received increasing attention in recent years and has found important applications in many scientific and engineering fields. To solve network consensus optimization problems, one of the most well-known approaches is the distributed gradient descent method (DGD). However, in networks with slow communication rates, DGD’s performance is unsatisfactory for solving high-dimensional network consensus problems due to the communication bottleneck. This motivates us to design a communication-efficient DGD-type algorithm based on compressed information exchanges. Our contributions in this paper are three-fold: i) We develop a communication-efficient algorithm called amplified-differential compression DGD (ADC-DGD) and show that it converges under any unbiased compression operator; ii) We rigorously prove the convergence performances of ADC-DGD and show that they match with those of DGD without compression; iii) We reveal an interesting phase transition phenomenon in the convergence speed of ADC-DGD. Collectively, our findings advance the state-of-the-art of network consensus optimization theory.

Subfields: Computational Mechanics, Computer Networks and Communications, Optimization & Training, ML Systems & Hardware

How researchers see this paper

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

In Computational Mechanics

1. Hamed Hassani
2. Ramtin Pedarsani
3. Amirhossein Reisizadeh
4. Hossein Taheri
5. Ali Jadbabaie
6. Aryan Mokhtari
7. Alejandro Ribeiro

In Computer Networks and Communications

1. Amirhossein Reisizadeh
2. Hamed Hassani
3. Ramtin Pedarsani
4. Aryan Mokhtari
5. Hossein Taheri
6. Ali Jadbabaie
7. Wei Ren
8. Francesco Bullo

In Optimization & Training

1. Hamed Hassani
2. Ramtin Pedarsani
3. Amirhossein Reisizadeh
4. Aryan Mokhtari
5. Hossein Taheri
6. Ali Jadbabaie

In ML Systems & Hardware

1. Amirhossein Reisizadeh
2. Ali Jadbabaie
3. Ramtin Pedarsani
4. Aryan Mokhtari

Citations in the corpus

• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “…and compression in distributed learning has recently gained considerable attention for both master-worker [Alistarh et al., 2017, Bernstein et al., 2018, Seide et al., 2014, Smith et al., 2016] and masterless topologies [Koloskova et al., 2019, Reisizadeh et al., 2019a, Zhang et al., 2018].”
• Robust and Communication-Efficient Collaborative Learning (2019, methodology): “The first exact decentralized optimization method with quantized messages was given in (Reisizadeh et al., 2018; Zhang et al., 2018), and more recently, new techniques have been developed in this context for convex problems (Doan et al., 2018; Koloskova et al., 2019; Berahas et al., 2019; Lee et…”