Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

By Anastasia Koloskova, Sebastian U. Stich, Martin Jaggi. 2019

612 citations recorded by the source corpus.

We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over $n$ machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communication bottleneck, the nodes compress (e.g. quantize or sparsify) their model updates. We cover both unbiased and biased compression operators with quality denoted by $\omega \leq 1$ ($\omega=1$ meaning no compression). We (i) propose a novel gossip-based stochastic gradient descent algorithm, CHOCO-SGD, that converges at rate $\mathcal{O}\left(1/(nT) + 1/(T \delta^2 \omega)^2\right)$ for strongly convex objectives, where $T$ denotes the number of iterations and $\delta$ the eigengap of the connectivity matrix. Despite compression quality and network connectivity affecting the higher order terms, the first term in the rate, $\mathcal{O}(1/(nT))$, is the same as for the centralized baseline with exact communication. We (ii) present a novel gossip algorithm, CHOCO-GOSSIP, for the average consensus problem that converges in time $\mathcal{O}(1/(\delta^2\omega) \log (1/\epsilon))$ for accuracy $\epsilon > 0$. This is (up to our knowledge) the first gossip algorithm that supports arbitrary compressed messages for $\omega > 0$ and still exhibits linear convergence. We (iii) show in experiments that both of our algorithms do outperform the respective state-of-the-art baselines and CHOCO-SGD can reduce communication by at least two orders of magnitudes.

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

In Computer Networks and Communications

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Translating and generalizing some of the existing compressed communication schemes from the centralized orchestratorfacilitated setting to the fully decentralized setting, without negatively impacting the convergence is an active research direction [243, 335, 380, 242].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…al., 2012; Rakhlin et al., 2012)—the diversity in the data distribution on each worker sometimes can be hidden in this generous upper bound and the analyses cannot distinguish between iid. and non-iid. data cases, such as e.g. in (Koloskova et al., 2019; Nadi-radze et al., 2019; Li et al., 2020b).”
Decentralized gradient methods: does topology matter? (2020, neutral): “These results do not explain why insensitivity is often observed in practice (as shown in (Lian et al., 2017, 2018; Luo et al., 2019; Koloskova et al., 2019)) 1) since the beginning of the training phase, 2) with constant learning rates, and 3) for non-diﬀerentiable machine learning models (e.g.,…”
Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “Assumption 3 has been used before, either in this general form or in special cases, in the analysis of gradient methods with compressed gradients [17,19] and compressed iterates [18].”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “This promising result pushes the research of distributed optimization from a sheer centralized mechanism to a more decentralized pattern [15, 41, 11, 45, 24].”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Finally, we note that various approaches to gradient compression have been proposed to reduce the communication overhead for ALLREDUCE and decentralized learning methods (Alistarh et al., 2007; Wen et al., 2007; Bernstein et al., 2019; Karimireddy et al., 2019; Koloskova et al., 2019; Vogels et al.,”
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].”
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.”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…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 al., 2018a,b).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “For the specific averaging used in CHOCO-SGD, linear convergence has been shown in (Koloskova et al., 2019) and we will use their estimate of the convergence rate of the averaging scheme.”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, methodology): “Skipping the detailed derivation, we can obtain the closed forms: • D-PSGD [Lian et al., 2017] (without compression): • DCD-PSGD [Tang et al., 2018] (with compression): • CHCHO-SGD [Koloskova et al., 2019] (with compression): • Updating rule of DeepSqueeze (with error-compensated compression): We ca”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “Another recent work in [33] studies the decentralized case with sparsification for strongly convex functions.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, methodology): “Given an arbitrary network topology, there are two orthogonal methods that reduce the communication time: one is to reduce the communication amount, as proposed in [16]; another is to reduce the frequency of communications, as proposed in this paper.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “…consider unbiased quantization and show convergence to the neighborhood of a stationary point on non-convex functions under very rigid assumptions on the quantization, i.e. allowing only O (1) compression, Koloskova et al. (2019) relax those constraints but only consider strongly convex functions.”
vqSGD: Vector Quantized Stochastic Gradient Descent (2022, background): “In the recent years various quantization and sparsiﬁca-tion techniques [2, 5, 7, 21, 26, 29, 33, 35, 37] have been developed to alleviate the problem of communication bottleneck.”
Efficient sparse collective communication and its application to accelerate distributed deep learning (2020, neutral): “Orthogonal to our work, various works propose efficient distributed optimization algorithms [4, 36, 41, 72].”
Distributed Gradient Methods for Convex Machine Learning Problems in Networks: Distributed Optimization (2020, background): “Studies of the effects of quantization in distributed methods have been somewhat limited in the past decade [34]–[36] and very recently in [37].”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, background): “References [32, 33, 13] consider SGD-type algorithms in the non-convex setting, while references [48, 31] analyze the use of quantization in the gossip setting.”