Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

By Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian U. Stich, Peter Richtárik. 2019

143 citations recorded by the source corpus.

We consider distributed optimization where the objective function is spread among different devices, each sending incremental model updates to a central server. To alleviate the communication bottleneck, recent work proposed various schemes to compress (e.g.\ quantize or sparsify) the gradients, thereby introducing additional variance $\omega \geq 1$ that might slow down convergence. For strongly convex functions with condition number $\kappa$ distributed among $n$ machines, we (i) give a scheme that converges in $\mathcal{O}((\kappa + \kappa \frac{\omega}{n} + \omega)$ $\log (1/\epsilon))$ steps to a neighborhood of the optimal solution. For objective functions with a finite-sum structure, each worker having less than $m$ components, we (ii) present novel variance reduced schemes that converge in $\mathcal{O}((\kappa + \kappa \frac{\omega}{n} + \omega + m)\log(1/\epsilon))$ steps to arbitrary accuracy $\epsilon > 0$. These are the first methods that achieve linear convergence for arbitrary quantized updates. We also (iii) give analysis for the weakly convex and non-convex cases and (iv) verify in experiments that our novel variance reduced schemes are more efficient than the baselines.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Federated & Distributed Learning

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 Federated & Distributed Learning

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “, natural compression and natural dithering, standard dithering, sparsification, and quantization [16,17,18,28].”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “The more direct approach is to reduce the size of the messages through gradient compression or sparsiﬁcation [32, 23, 51, 40, 42, 8].”
Gradient Descent with Compressed Iterates (2019, methodology): “As a result, there are many algorithms designed with the goal of reducing communication in stochastic gradient methods: including SignSGD (1-bit quantization) [4], TernGrad (ternary quantization) [35], QSGD [1], DIANA (with arbitrary quantization) [11], ChocoSGD [15], and others, see e.”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “…( t ) i and receive q ( t ) j communication 6: ˆ x j end for i ) 9: x In contrast to the quantization operators used in e.g. (Alistarh et al., 2017; Horváth et al., 2019), compression operators deﬁned as in (2) are not required to be unbiased and therefore supports a larger class of compression…”
Natural Compression for Distributed Deep Learning (2019, methodology): “[19] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik.”
Better Theory for SGD in the Nonconvex World (2020, background): “We say that a stochastic operator Assumption 4 is mild and is satisﬁed by many compression operators in the literature, including random dithering (Alis-tarh et al., 2017), random sparsiﬁcation, block quantization (Horv´ath et al., 2019), and others.”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, methodology): “When the functions of fi are of a finite-sum structure as in (4), one can apply variance reduction to reduce the variance of the stochastic gradients g i together with quantization, resulting in the VR-DIANA method (Horváth et al., 2019).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “Moreover, in the case where each f i is itself a ﬁnite average of local functions, variance reduced versions of DIANA , called VR-DIANA [18], were recently developed and proved to converge sublinearly with a ﬁxed step size for convex functions.”
Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (2020, methodology): “The variance-reduced CGD method DIANA (Mishchenko et al., 2019a; Horv´ath et al., 2019b) enjoys even better behavior: the number of communication rounds for this method is unaﬀected up to a certain level of compression when the variance induced by compression reaches a certain threshold.”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, methodology): “Finally, compression operators can be classified in two main categories: quantization [as in Alistarh et al., 2017; Seide et al., 2014; Zhou et al., 2018; Wen et al., 2017; Reisizadeh et al., 2019; Horváth et al., 2019] and sparsification [as in Aji and Heafield, 2017; Alistarh et al.”
vqSGD: Vector Quantized Stochastic Gradient Descent (2022, methodology): “Many works focused on providing techniques to reduce the error incurred due to quantization Horváth et al. [2019], Karimireddy et al. [2019] using locally accumulated errors. In this work, we focus primarily on gradient quantization techniques, and note that the variance reduction techniques of Horv”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, background): “…k , such that, for every k ∈ N , Assumption 1 is satisﬁed by several stochastic gradient estimators used in machine learning, including stochastic gradients used for coordinate descent [31], variance reduction [22,32–34] and stochastic gradients used in Federated learning [35], see Table 1 in [19].”
Communication Efficient Distributed Learning with Censored, Quantized, and Generalized Group ADMM (2020, background): “…updates are quantized under centralized (Bernstein et al., 2018; Suresh et al., 2017; Sun et al., 2019; Vogels et al., 2019; Alistarh et al., 2017; Horv´ath et al., 2019) and decentralized network topologies (Sriranga et al., 2019; Zhu et al., 2016; Koloskova et al., 2019; Gao and Huang, 2020;…”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “For examples of such compression schemes we refer the reader to [5,21].”
Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor (2020, unknown): “…2018), top-k sparsiﬁcation (Alistarh et al., 2018), standard random dithering (Goodall, 1951; Roberts, 1962; Alistarh et al., 2017), natural dithering (Horv´ath et al., 2019a), ternary quantization (Wen et al., 2017), and scaled sign quantization (Karimireddy et al., 2019b; Bernstein et al.,…”