The Convergence of Sparsified Gradient Methods

By Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, Cédric Renggli. 2018

553 citations recorded by the source corpus.

Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods - where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally - are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to three orders of magnitude, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Statistical Learning Theory

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 Statistical Learning Theory

Citations in the corpus

rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, background): “Assumption (ii) is a standard assumption in [26], [27], [38]–[41].”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “Further two biased compression schemes: (iii) topa, which selects the a fraction of weights with the largest magnitude and sets the other ones to zero (Alistarh et al., 2018; Stich et al., 2018), and (iv) sign compression, which compresses each weight to its sign scaled by the norm of the full vecto”
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): “In order to alleviate this cost, recently it has been suggested that each worker can send a compressed version of the local gradient (Alistarh et al., 2018; Stich et al., 2018; Zhang et al., 2017a), with methods such as quantization or sparsification.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “Here we propose the ﬁrst method that supports arbitrary low accuracy and even biased compression operators, such as in (Alistarh et al., 2018; Lin et al., 2018; Stich et al., 2018).”
Sparsified SGD with Memory (2018, background): “[4] study biased top-k sparsification.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “However, as these schemes are biased, they resisted careful analysis until very recently (Alistarh et al., 2018; Stich et al., 2018).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “[2] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli.”
vqSGD: Vector Quantized Stochastic Gradient Descent (2022, methodology): “[2016]), communication becomes a bottleneck to the efficiency and speed of learning using SGD Chilimbi et al. [2014]. In the recent years various quantization and sparsification techniques Acharya et al.”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, result): “We also want to note some related work [19–21] and the references therein, in which distributed stochastic gradient with quantization under master/worker models is considered.”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, methodology): “The current methodology towards reducing the size of messages is to communicate compressed local gradients or models to the central server by utilizing a quantization operator [3, 6, 48, 58, 59, 63, 65], sparsification schema [4,39,56,65], or composition of both [5].”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “to (Alistarh et al., 2018; Stich et al., 2018; Cordonnier, 2018; Karimireddy et al., 2019) for the discussion of key examples, including sparsification and quantization (that we have not discussed here).”
A Federated Learning Framework for Healthcare IoT devices (2020, background): “To further reduce the network traffic, we extend the idea of sparsification of gradients (Stich et al., 2018; Alistarh et al., 2018).”
SparCML: High-Performance Sparse Communication for Machine Learning (2018, background): “The argument (provided in the appendix) is based on the convergence proof of TopK SGD [5]; the main source of novelty is the addition of stochastic quantization.”