Sparsified SGD with Memory

By Sebastian U. Stich, Jean-Baptiste Cordonnier, Martin Jaggi. 2018

894 citations recorded by the source corpus.

Huge scale machine learning problems are nowadays tackled by distributed optimization algorithms, i.e. algorithms that leverage the compute power of many devices for training. The communication overhead is a key bottleneck that hinders perfect scalability. Various recent works proposed to use quantization or sparsification techniques to reduce the amount of data that needs to be communicated, for instance by only sending the most significant entries of the stochastic gradient (top-k sparsification). Whilst such schemes showed very promising performance in practice, they have eluded theoretical analysis so far. In this work we analyze Stochastic Gradient Descent (SGD) with k-sparsification or compression (for instance top-k or random-k) and show that this scheme converges at the same rate as vanilla SGD when equipped with error compensation (keeping track of accumulated errors in memory). That is, communication can be reduced by a factor of the dimension of the problem (sometimes even more) whilst still converging at the same rate. We present numerical experiments to illustrate the theoretical findings and the good scalability for distributed applications.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Efficiency & Compression, Optimization & Training

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 Computer Networks and Communications

In Efficiency & Compression

In Optimization & Training

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “In this work we do not consider gradient compression techniques (Alistarh et al., 2017; Stich et al., 2018; Tang et al., 2018a; 2019; Stich & Karimireddy, 2019)—but such orthogonal techniques could be added on top of our scheme—and instead only focus on local updates steps which are often efficient ”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, positive): “…communication overhead of distributed SGD, such as quantization (Seide et al., 2014; Strom, 2015; Wen et al., 2017; Alistarh et al., 2016; Bernstein et al., 2018; Karimireddy et al., 2019; Zheng et al., 2019) and sparsification (Aji and Heafield, 2017; Stich et al., 2018; Jiang and Agrawal, 2018).”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “Gradient vector sparsification is another approach analyzed in [4, 40, 39, 5, 30, 34, 9, 3, 36, 21, 32].”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “That includes 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),…”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “Gradient compression techniques have been proposed for the standard distributed training case (Alistarh et al., 2017; Wen et al., 2017; Lin et al., 2018; Wangni et al., 2018; Stich et al., 2018), to reduce the amount of data that has to be sent over each communication link in the network.”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “The error-compensation strategy is proved to be able to potentially improve the training efficiency for strongly convex loss function [Stich et al., 2018].”
On the Convergence of FedAvg on Non-IID Data (2019, neutral): “Assumptions 3 and 4 have been made by the works (Zhang et al., 2013; Stich, 2018; Stich et al., 2018; Yu et al., 2019).”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “The analysis for the centralized Topk (among other sparsifiers) was considered in [18], and [5] analyzed a distributed version with the assumption of closeness of the aggregated Topk gradients to the centralized Topk case, see Assumption 1 in [5].”
Natural Compression for Distributed Deep Learning (2019, methodology): “, with the optimized sparsifiers [28, 47], or with [4, 44]), boosting the performance of the system even further.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “However, previous work assume that the error compensation is done only for each worker, g, but not for the aggregated gradient g (Stich et al., 2018).”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “, 2014) and analyzed in (Stich et al., 2018) for the convex case, error feedback involves computing the difference between a worker’s gradient and the compressed gradient (i.”
Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data (2019, background): “Definition 1 (k-Contraction) [33]: For a parameter 0 < k ≤ d , a k-contraction is an operator comp : Rd → Rd that satisfies the contraction property”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “Much sparser vectors can be obtained by random sparsiﬁcation techniques that randomly mask the input vectors and only preserve a constant number of coordinates (Wangni et al., 2018; Konecny & Richt´arik, 2018; Stich et al., 2018).”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, background): “We generalize the notion of a compressor from (Stich et al., 2018).”
Wireless Network Intelligence at the Edge (2018, background): “, sparsification [192], opportunistic uploading based on gradient magnitudes [193], and adaptively adjusting the communication intervals [31], [194].”