Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations

By Debraj Basu, Deepesh Data, Can Bülent Karakus, Suhas N. Diggavi. 2019

455 citations recorded by the source corpus.

Communication bottleneck has been identified as a significant issue in distributed optimization of large-scale learning models. Recently, several approaches to mitigate this problem have been proposed, including different forms of gradient compression or computing local models and mixing them iteratively. In this paper, we propose Qsparse-local-SGD algorithm, which combines aggressive sparsification with quantization and local computation along with error compensation, by keeping track of the difference between the true and compressed gradients. We propose both synchronous and asynchronous implementations of Qsparse-local-SGD. We analyze convergence for Qsparse-local-SGD in the distributed setting for smooth non-convex and convex objective functions. We demonstrate that Qsparse-local-SGD converges at the same rate as vanilla distributed SGD for many important classes of sparsifiers and quantizers. We use Qsparse-local-SGD to train ResNet-50 on ImageNet and show that it results in significant savings over the state-of-the-art, in the number of bits transmitted to reach target accuracy.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

On the Outsized Importance of Learning Rates in Local Update Methods (2020, background): “…(McMahan et al., 2018; Augenstein et al., 2020), fairness (Mohri et al., 2019; Li et al., 2020b), robustness (Ghosh et al., 2019; Bagdasaryan et al., 2018; Sun et al., 2019), and communication-efficiency (Konečný et al., 2016; Sattler et al., 2019; Basu et al., 2019; Reisizadeh et al., 2020).”
Adaptive Federated Optimization (2020, background): “, 2010), which has been analyzed by many works (Stich, 2019; Yu et al., 2019; Wang and Joshi, 2018; Stich and Karimireddy, 2019; Basu et al., 2019).”
Personalized Federated Learning: A Meta-Learning Approach (2020, background): “In particular, there have been several works on various aspects of FL, including preserving the privacy of users [6, 7, 8, 9] and lowering communication cost [10, 11, 12, 13].”
Distributed Fixed Point Methods with Compressed Iterates (2019, background): “Usually, the exchanged information is usually some compressed gradient [1,7,27] or compressed model update [4,25] in a distributed master-worker setting.”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “…the design of more eﬃcient communication strategies (Konečn`y et al., 2016b,a; Suresh et al., 2017; Stich et al., 2018; Karimireddy et al., 2019; Basu et al., 2019), the study of lower bounds for parallel stochastic optimization with a dependency graph (Woodworth et al., 2018b), devising…”
Gradient Descent with Compressed Iterates (2019, background): “Another line of work focused on local stochastic gradient methods that communicate only intermittently and average models, such as Local SGD [20, 28, 31, 32] and Federated Averaging [22], and combinations of such methods and update quantization (where the sum of gradients over an epoch is quantized)”
First Analysis of Local GD on Heterogeneous Data (2019, background): “[1, 14, 15, 19].”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “…gradient methods have been considered, for example with momentum (Yu et al., 2019a; Wang et al., 2019), with quantization (Reisizadeh et al., 2019; Basu et al., 2019), with adaptive stepsizes (Xie et al., 2019) and with various variance-reduction methods (Liang et al., 2019; Sharma et al., 2019;…”
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.”
Better Communication Complexity for Local SGD (2019, background): “While local SGD has been popular among practitioners for a long time [5, 12], its theoretical understanding has remained elusive until very recently [1, 9, 14, 15, 16, 17] (see Table 1).”
FedBoost: Communication-Efficient Algorithms for Federated Learning (2020, unknown): “, 2018) and in other distributed settings (Stich et al., 2018; Karimireddy et al., 2019; Basu et al., 2019).”