Decentralized Deep Learning with Arbitrary Communication Compression
Authors: Anastasia Koloskova*
Tao Lin*
Sebastian U Stich
Martin Jaggi
Venue:  (2020)

Abstract: Decentralized training of deep learning models is a key element for enabling data privacy and on-device learning over networks, as well as for efficient scaling to large compute clusters. As current approaches are limited by network bandwidth, we propose the use of communication compression in the decentralized training context. We show that Choco-SGD achieves linear speedup in the number of workers for arbitrary high compression ratios on general non-convex functions, and non-IID training data.  We demonstrate the practical performance of the algorithm in two key scenarios: the training of deep learning models (i) over decentralized user devices, connected by a peer-to-peer network and (ii) in a datacenter. 

Published as a conference paper at ICLR 2020
DECENTRALIZED DEEP LEARNING WITH ARBITRARY COMMUNICATION COMPRESSION
Anastasia Koloskova"
Tao Lin' tao. tac. poo.lin@epf..co ch
anastasia a koloskovaleptl.cc.
Sebastian U. Stich
Martin Jaggi
sebastian. sti.heeff..ccheeee..hhhh
martin. Jartinnjjggi@epfl..c ch.
EPFL
Lausanne, Switzerland
ABSTRACT
Decentralized training of deep learning models a key element for enabling data privacy and on-device learning over networks, as well for efficient scaling to large compute clusters. As current approaches are limited by network bandwidth, we propose the use of communication compression in the decentralized training context. We show that CHOCO-SGD achieves linear speedup in the number workers for arbitrary high compression ratios general non-convex functions, and non-IID training data. We demonstrate the practical performance the algorithm in two key scenarios: the training of deep learning models (i) over decentralized user devices, connected by a peer-to-peer network and (ii) datacenter.
INTRODUCTION
Distributed machine learning-in -i.. the training of machine learning models using distributed opti- mization algorithms-has recently enabled many successful applications in research and industry. Such methods offer of the key success factors: 1) computational scalability by leveraging the simultancous computational power of many devices, and 2) data-locality, the ability to perform joint training while keeping each part of the training data local each participating device. Recent theoretical results indicate that decentralized schemes can be as efficient as the centralized approaches. least when considering convergence training loss vs. iterations (Scaman et al.) 2017 2018 Lian
et al. 2017 Tang et al. 2018 Koloskova et al.) 2019 Assran et al. 2019).
Gradient compression techniques have been proposed for the standard distributed training case (Alis tarh et al.] 2017 Wen et al. 2017 [in et al., 2018 Wangni et al.] 20188 Stich et al. 2018 to reduce the amount data that has to be sent over each communication link the network. For decentralized training of deep neural networks, Tang et al. (2018) introduce two algorithms (DCD, ECD) which allow for communication compression. However, both these algorithms are restrictive with respect to the used compression operators, only allowing for unbiased compressors and- and-more significantly- so far not supporting arbitrarily high compression ratios. We here study CHOCO-SGD SGD-recently introduced for convex problems only (Koloskova al. 2019- overcomes these constraints.
For the evaluation of our algorithm we in particular focus on the generalization performance (on the test-set) standard machine learning benchmarks, hereby departing from previous work such as e.g. (Tang et al.) 2018) Wang et al.) 2019 Tang et af. 2019 Reisizadeh et al.) 2019) that mostly con- sidered training performance
the train-set). We study two different scenarios: firstly, (i) training on a challenging peer-to-peer setting, where the training data is distributed over the training devices (and not allowed to move), similar to the federated learning setting (McMahan al. (017). 7). We are again able to show speed-ups for CHOCo-SCe with much less communication overhead. Secondly, (ii) training datacenter setting, where decen- tralized communication patterns allow better scalability than centralized approaches. For this setting
over the decentralized baseline (Lian et al., (017)
Equual contribution.

---

Published as a conference paper at ICLR 2020
show that communication efficient CHOCo-SGD improve time-to- to-acuurycy on large tasks, such as e.g. ImageNet training. However, when investigating the scaling of decentralized algorithms to larger number of nodes observe that (all) decentralized schemes encounter difficulties and often do not reach the same (test and train) performance as centralized schemes. As these findings point out some deficiencies of current decentralized training schemes (and are particular think that reporting these results is helpful contribution to the community to spur further research on decentralized training schemes that scale to large number of peers.
scheme)
Contributions. Our contributions can be summarized as: On the theory side, we are the first to show that CHOCO-SGD converges at rate O1//nT + 8/p78ar)) on non-convex smooth functions, where denotes the number of nodes, T the number iterations, the spectral gap of the mixing matrix and the compression ratio. The main term, O ('VvT), matches with the centralized baselines with exact communication and shows a linear speedup in the number of workers n. Both and only affect the asymptotically smaller second term.
On the practical side, we present a version of CHOCO-SGD with momentum and analyze its practical performance on two relevant scenarios:
for on-device training over a realistic peer-to-pect peerr social network, where lowering the bandwidth requirements of joint training is especially impactful in datacenter setting for computational scalability of training deep learning models for resource efficiency and improved time-to-accuracy
Lastly, we systematically investigate performance of the decentralized schemes when scaling to larger number of nodes and we point out some (shared) difficulties encountered by current decentralized learning approaches.
2
RELATED WORK
For the training in communication restricted settings a variety of methods have been proposed. For instance, decentralized schemes (Lian al. 2017
Nedić al. [0188) Koloskova al. 2019).
gradient compression (Seide et al. 201,)014 Strom
2015
Alistarh et al. Wen et al. 2017: Lin
al.
2018
Wangni al. 2018 Bernstein et al.
2018
Lin al. 2018 Alistarr et al.] 2018 Stich
et al.
2018
Karimireddy et al. 2019). asynchronous methods (Recht et al. [201 Assran et al. 2019)
or performing multiple local SGD steps before averaging (Zhang et 2 McMahan et al. 2017
Lin et al. 2020). This especially covers learning over decentralized data, as extensively studied in the federated learning literature for the centralized algorithms (McMahan et al. 2016)). In this paper we advocate for combining decentralized SGD schemes with gradient compression.
Decentralized SGD. We particular focus on approaches based on gossip averaging (Kempe et al. 2003 Xiao & Boyd 2004 Boyd et al., 2006) whose convergence rate typically depends on the spectral gap 2 O of the mixing matrix (Xiao & Boyd 2004). Lian et al. (2017) combine SGD with gossip averaging and show that the leading term in the convergence rate O 1/vrr) is consistent with the convergence of the centralized mini-batch SGD (Dekel et al. 2012) and the spectral gap only
affects the asymptotically smaller terms. Similar results have been observed very recently for related
schemes (Scaman et al. 2017 2018 Koloskova et al., 2019 Yu et al. 2019).
Quantization. Communication compression with quantization has been popularized in the deep learning community by the reported successes in (Seide et al. [0144] Strom 2015).. Theoretical guarantees were first established for schemes with unbiased compression (Alistarh et al. 2017 Wen et al. 2017 Wangni et al.) 2018) but soon extended to biased compression (Bernstein et al. 2018) as well. Schemes with error correction work often best in practice and give the best theoretical
gurantees (Lin et al. 2018 Alistarh et al.) 2018 [ttchh et al. 2018 Karimireddy et al.) 2019). Recently, also proximal updates and variance reduction have been studied combination with quantized updates (Mishchenko et al. 2019 Horväth et al. 2019).
Decentralized Optimization with Quantization. It has been observed that gossip averaging can diverge (or not converge to the correct solution) in the presence of quantization noise (Xiao et al. 2005| Carli et al.) 2007 Nedić et al., 2008 Dimakis et al., 2010 Carli et al. 2010bb Yuan et al. 2012). Reisizadeh et al. (2018) propose algorithm that still converge, though at slower rate than the exact scheme. Another line of work proposed adaptive schemes (with increasing compression
accuracy) that converge the expense of higher communication cost (Carli et al. 20TOa Doan et al.
2

---

Published as a conference paper at ICLR 2020
2018
Berahas et al. 2019). For deep learning applications, Tang al. (2018) proposed the DCD and ECD algorithms that converge at the same rate as the centralized baseline though only for constans compression ratio. The CHOCO-SGD algorithm that consider in this work can deal with arbitrary high compression, and has been introduced in (Koloskova et al. 2019) but only been analyzed for convex functions. For non-convex functions show measures the compression quality. Simultaneous work of Tang et al. (2019) introduced DeepSqueeze, an alternative method which also converges with arbitrary compression ratio. In our experiments, under the same amount of tuning, CHOCo-SGD achieves higher test accuracy.
of O (1/aTT + 1/62287)8) where 8 0
3 CHOCO-SGD
In this section we formally introduce the decentralized optimization problem, compression operators, and the gossip-based stochastic optimization algorithm CHOCo-SGD from (Koloskova et al., (019)..
Distributed Setup. We consider optimization problems distributed across n nodes of the form
f(x) = 1 1 f(()
f := min xER
f.(x) = DE,DD (x)
Vi E [n] (I)
where D1.... Dr are local distributions for sampling data which can be different on every node, Fj: Id x Ω + are possibly non-convex (and non-identical) loss functions. This setting covers the important case of empirical risk minimization in distributed machine learning and deep learning applications.
Communication. Every device is only allowed to communicate with its local neighbours defined by the network topology, given as a weighted graph G ([m], E), with edges E representing the communication links along which messages (e.g. model updates) can be exchanged. We assign positive weight wiy to every edge (Wij- = 0 for disconnected nodes [i,j} & F).
Assumption 1 (Mixing matrix). We assume that W E [0, 1]m1,, (W);j wii is a symmetric (W- W doubly stochastic (W1
= 1 matrix with eigenvalues 1 = [Ar(W)) [22(W)] 2... ... 2 (W)) and spectral gap == 1 - [22(W]] E (0.
In our experiments we set the weights based on the local node degrees: Wiy max maxxdde((t), deg(s)}-1 for {i.5} E E. This will not only guarantee p > 0 but these weights can easily be computed in local fashion on each node (Xiao Boyd 2004).
Compression. We aim to only transmit compressed (e.g. quantized or sparsified) messages. We formalized this through the notion of compression operators that was e.g. also used in (Tang et al.. 2018 Stich et al. 2018).
Definition 3.1 (Compression operator). Q: Rd + Rdd is a compression operator if satisfies
EQQ [[Q(x) x|| 2 s (1 8) |x|
Vx E TRd
for a parameter 8 > 0. Here Eq denotes the expectation over the internal randomness of operator Q.
In contrast to the quantization operators used in e.g. (Alistarh et al. 2017 Horváth et al. 2019). compression operators defined as (2) are not required be unbiased and therefore supports larger class of compression operators. Some examples can be found in (Koloskova et al., 2019) and we further discuss specific compression schemes in Section
Algorithm. CHOCO-SCO SGD is summarized in Algorithm I Every worker i stores its own private variable x; Rd that is updated by stochastic gradient step in part ( and modified gossip averaging step on line 2. This step is key element of the algorithm as it preserves the averages of the iterates even in presence of quantization noise (the compression errors are not discarded, but aggregated in the local variables x,, see also (Koloskova et al. 2019)). The nodes communicate with their neighbors in part ! and update the variables X, E Rd for all their neighbors {i,j} E E only using compressed updates. These x; are available to all the neighbours of the node and represent the puullcly available" copies of the private X,, in general x; + X,, due to the communication restrictions.
From an implementation aspect, it is worth highlighting that the communication part I and the gradient computation part ② can both be executed in parallel because they are independent. Moreover,
3

---

Published as a conference paper at ICLR 2020
Algorithm CHoCo-SGD Koolsskoa et al. 2019)
input: Initial value x +) Rd. x -) x b on each node [n]. consensus stepsize y SGD stepsize "
communication graph G = ([r)) E3) and mixing matrix W, initialize x! = 0 ví E [M]
1: for in O... T do iin parailel for all workers i e [x]]
2: x (1-b) + SooJEE wey (x) x(")
modified gossip averaging
( Q(x,)) )
3: q.
4 compression
4: for neighbors j: {i,s} E E (including {i} E E) do
①
5: Send q00h and receive q;
(t)
communication
x/+")== (4) +x,
=
local update
end for
Sample !! compute gradient gi g00 (F
9:
() = 75;
(4)
stochastic gradient update
10: end for
each node only needs to store 3 vectors at most, independent of the number of neighbors (this might not be obvious from the notation used here for additinal clarity, for further details c.f. (Koloskoval et al. 2019)). We further propose a momentum-version of CHOCO-SGD in Algorithm 2 (see also Section D for further details).
CONVERGENCE OF CHOCO-SGD ON SMOOTH NON-CONVEX PROBLEMS
As the first main contribution, we here extend the analysis of CHOCo-SGD to non-convex problems. For this we make the following technical assumptions:
Assumption 2. Each function fc: Rdd R for E [m] L-smooth, that
[V(ly) {x(()) - Ily x||
Vx,y E Rd i [n].
and the variance of the stochastic gradients bounded on each worker:
Rgg, [[V (x)) S o? EEg [IV &II S G?,
Vx E TR.d, E [n],
(3)
where Eg, I denotes the expectation over &, D. We also denote T² 1 of for convenience. Theorem 4.1. Under Assumptions
there exists constant stepsize and the consensus stepsize
from Koloskova et al. 2019)
16ptp' 43" 203² -8p with 3 = 1| 2 E [0, 2), such that
0²6
the averaged iterates x (1) = - x of Algorithm satisfy:
Σ |
-
L
(((T+))
LF
1/2
+
GLFo 2/3
LF
T+1
+1)+1)
T+1
p²6
where == 82
denotes the convergence rate of the underlying consensus averaging scheme of (Koloskova et al. 2019). Fo f(x()))
This result shows that CHOCO-SGD SGD converges as (1///T + +/(67)))))) The first term shows a linear speed-up compared SGD single node, while compression and graph topology affect only the higher order second term. By differently choosing the stepsize r := vn//T+I we can recover asymptotic convergence rate of O(1/nor + n/(o'8"))). For the proofs and convergence of the individual iterates x; we refer to Appendix
5 COMPARISON TO BASELINES FOR VARIOUS COMPRESSION SCHEMES
In this section we experimentally compare CHOCO-SOR SGD to the relevant baselines for a selection of commonly used compression operators. For the experiments further leverage momentum in all implemented algorithms. The newly developed momentum version CHOCo-SGD is given as Algorithm 2
4

---

Published as a conference paper at ICLR 2020
Algorithm 2 CHoco-SGD with Momentum
input: Same as for Algorithm additionally: weight decay factor X, momentum factor B, local momentum memory (0) = 0' E [r]]
Lines 1-8 in Algorithm|| T are left unmodified
Line 9 in Algorithm
T is replaced with the following two lines
9: V [++1)
gg + >xx")) + (v
< local momentum with weight decay
10: X;
x! nyv !v!!+) (e+1)
stochastic gradient update
Setup. In order match the setting in (Tang al. 2018) for first set of experiments, use a ring topology with n = nodes and train the ResNet C architecture (He et al. (016) on the Cifar10 dataset (50K/10K training/test samples) (Krizhevsky 2012). We randomly split the training data between workers and shuffle it after every epoch, following standard procedure as e.g. in (Goyal et al., 2017). We implement DCD and ECD with momentum (Tang et al. (018). DeepSqueeze with momentum (Tang et al. 2019), CHOCO-SGD with momentum (Algorithm 2 and standard (all-reduce) mini-batch SGD with momentum and without compression (Dekel et al. 2012). Our implementations are open-source and available at ttttpps: / // thub. com/ e fm] Choco5GD The momentum factor is set 0.9 without dampening. For all algorithms we fine- tune the initial learning rate and gradually warm it up from relative small value (0.1) (Goyal al. 2017) for the first 5 epochs. The learning rate is decayed by 10 twice, at 150 and 225 epochs, and stop training at 300 epochs. For CHOCo-SGD and DeepSqueeze the consensus learning rate y is also tuned. The detailed ryper-parameter tuning procedure refers to Appendix [F] Every compression scheme is applied to every layer of ResNet20 separately. We evaluate the top-1 test accuracy on every node separately over the whole dataset and report the average performance over all nodes.
Compression Schemes. We implement two unbiased compression schemes: (i) gsgd, quantization that randomly rounds the weights b-bit representations (Alistarh al., 2017). and (ii) random, sparsification, which preserves a randomly chosen fraction of the weights and sets the other ones to zero (Wangni et al., 2018). Further two biased compression schemes: (iii) top,, which selects the 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 vector (Bernstein et al. 2018 Karimireddy et al. 2019). We refer to Appendix for exact definitions of the schemes.
DCD and ECD have been analyzed only for unbiased quantization schemes, thus the combination with the two biased schemes is not supported by theory. In converse, CHOCo-SGD and DeepSquecze has been studied only for biased schemes according Definition However, both unbiased compression schemes can be scaled down in order to meet the specification (cf. discussions in (Stich et al. 2018 Koloskova et al. 2019) and adopt this for the experiments.
The results summarized in Tab. [ For unbiased compression schemes, ECD and DCD only achieve good performance when the compression ratio is small, and sometimes even diverge when the compression ratio high. This is consisten with the theoretical and experimental results in (Tang et al. 2018). We further observe that the performance of DCD with the biased top, sparsification is much better than with the unbiased random, counterpart, though this operator not yet supported by theory.
Results.
CHoco- -GD can generalize reasonably well in scenarios (at most 1.65% accuracy drop) for fixed training budget. The sigu compression achieves state-of-the-arr accuracy and requires approximately 32x less bits per weight than the full precision baseline.
Tang et al. 2018) only consider absolute bounds on the quantization error. Such bounds might be restrictive (i.e. allowing only for low compression) when the input vectors are unbounded. This might be the reason for the instabilities observed here and also in (Tang al. 2018 Fig. 4), (Koloskova al. 2019 Figs. 5-6).
5

---

Published as a conference paper at ICLR 2020
Table 1: Top-1 test accuracy for decentralized DCD, ECD, DeepSqueeze and CHOCO-SGI) with different compression schemes. Reported top-1 test accuracies are averaged over three runs with fine-tuned hyper- parameters (learning rate, weight decay, consensus stepsize). The fine-tuned all-reduce baseline reaches accuracy 92.64, with 1.04 MB gradient transmission per iteration. (* indicates that 2 out of 3 runs diverged).
Algorithm
Error-
Quantization (QSGD)
Sparsilication (random- %)
feedback
16 bits
bits
4 bits
2 bits
50%
10%
1%
transmirted dataliteration
0.52 MB
0.13 MB
MB diverges
1.04
0.21 MB
MB
DCD-PSGD
92.51 0.05
92.36 = 0.28
23.56 2.97
92.05 +: 0.25
diverges
divergos
ECD-PSGD
92.02
0.14
59.11
= 1.57
divergas
diverges
diverges
diverges
diverges
DeepSqueeze
92.27 0.21
91.83
a 0.35
91.47 4 0.21
90.96 1 0.19
91.46 1: 0.09
90.96 0.16
88.55 4 0..1
CHOCO-SGD
92.34
92.30 0.08
91.92 0.27
91 0.11
92.54 0.26
91.87
91.32 + 0.17
Algoritha
Error- feedback
Sparsification (top- %)
Sign+Norm
50%
10%
1%
transmisted data/itcration
1,04 MB
0.21 MB
0,031 MB
0.032 MB
DCD-PSGD
91.97 0.14
92.40
ECD-PSGD
17.03
16.78 *
18.03 *
diverges
DeepSqueeze
91.55 = 0,28
91.31
= 0.25
90.47 +1477:0..1 0.17
91.38 0.19
CHOCO-SGD
92/29 0.05
91.78:+00.1
6 USE CASE I: ON-DEVICE PEER-TO-PEER LEARNING
We now shift our focus to challenging real-world scenarios which are intrinsically decentralized, i.e. each part of the training data remains local to each device, and thus centralized methods either fail or inefficient to implement. Typical scenarios comprise e.g. sensor networks, mobile devices or hospitals which jointly train a machine learning model. Common to these applications is that i) each device has only access to locally stored acquired data, ii) communication bandwidth is limited (either physically, or artificially for e.g. metered connections), iii) the global network topology is typically unknown Additionally, this fully decentralized setting is also strongly motivated by privacy aspects, enabling to keep the training data private on each device all times.
single device, and iv) the number of connected devices is typically large.
Modeling. To simulate this scenario. we permanently split the training data between the nodes, i.e. the data is never shuffled between workers during training, and every node has distinct part of the dataset. To the best of our knowledge, no prior works studied this scenario for decentralized deep learning. For the centralized approach, gathering methods such as all-reduce are not efficiently implementable in this setting, hence we compare to the centralized baseline where all nodes route their updates to a central coordinator for aggregation. For the comparison we consider CHOCC--SGD with sign compression (this combination achieved the compromise between accuracy and compression level in Tab. [T] decentralized SGD without compression (Lian et al. 2017), and centralized SGD without compression.
Scaling to Large Number of Nodes. To study the scaling properties of CHOCO- SGD, train 4, 16, 36 and 64 number of nodes. We compare decentralized al- gorithms on two different topologies: ring as the worst possible topology. and on
the torus with much larger spectral gap. Their parameters are listed in the table 2 We train ResNet (He et al. (016) (78K parameters). on Cifarl0 dataset (50K/10K training/test sam- ples) (Krizhevsky) 2012). For the simplicity, we keep the learning rate constant and separately tune it for all methods. We tune consensus learning rate for CHOCO-SGD.
Table 2: Summary of communication topologics.
Topology
spectral gap
max, mode degree
==
n 36
ring
0.67
0.05
0.01
0,003
0.67
0.4
0.2
0.12
Folly-connected
The results are summarized in Fig. [ (and Fig. 6 Tabs. 7 in Appendix G). First we compare the testing accuracy reached after 300 epochs (Fig. [ Left). CentralizedSGD has a good performance for all the considered number of nodes. CHocO-SGD slows down due to the influence of graph topology (Decent aal izd curve), which is consistent with the spectral gaps order (see Tab. 2 and also influenced by the communication compression (CHOCO curve), which slows down training uniformly for both topologies. We observed that the train performance is similar to the test on Fig. therefore the performance degradation is explained by the slower convergence (Theorem 4. and is not

---

Published as a conference paper at ICLR 2020
DHOCO (Ttral
Decentre bad Meraa
Centellced
Tectopp souumcy
05.0
74
62.5
00.0
77.5
16 modes
=ofrooess
Fix budget of 300 epochs
Fixed budget of communication size (1000 MB)
Figure 1: Scaling of CHOCO-SCH SGD with sign compression to large number of devices on Ci cifarl 0 dataset. Left: best testing accuracy of the algorithms reached after 300 epochs. Right: best testing accuracy reached after communicating 1000 MB.
generalization issue. Increasing the number of epochs improves the performance of the decentralized schemes. However, even using 10 times more epochs. we were not able to perfectly close the gap between centralized and decentralized algorithms for both train and test performance.
In the real decentralized scenario, the interest is not to minimize the epochs number, but the amount of communication to reduce the cost of the user's mobile data. We therefore fix the number of transmitted bits to 1000 MB and compare the best testing accuracy reached (Fig. [ Right). CHOCo- SGD performs the best while having slight degradation due to increasing number of nodes. is beneficial to use torus topology when the number of nodes is large because it has good mixing properties, for small networks there is not much difference between these two topologies the of large spectral gap is canceled by the increased communication due larger node degree for torus topology. Both Decentralized and Centralized SGD requires significantly larger number of bits to reach reasonable accuracy.
the benefit
Experiments on a Real Social Network Graph. We simulate training models on user devices (e.g. mobile phones), connected by real social network. We chosen Davis Southern women social network (Davis et al. 194T) with 32 nodes. We train Re (0.27 million parameters) model on the Ci farlō dataset (50K/10K training/test samples) (Krizhevsky 2012) for image classification and a three-layer LSTM architecture (Hochreiter & Schmidhuber (997) (28.95 million parameters) for a language modeling task on WikiText-2 (600 training and 60 validation articles with a total of 2'088' 628 and 217'646 tokens respectively) (Merity et al. 2016). The depicted curves of the training loss are the averaged local loss over all workers (local model with fixed local data); the test performance uses the mean of the evaluations for local models on whole test dataset. For more detailed experimental setup we refer Appendix
F
The results are summarized in Figs. 3 in Tab. 3 For the image classification task, when compar- ing the training accuracy reached after the same number of epochs, we observe that the decentralized algorithm performs best, follows by the centralized and lastly the quantized decentralized. However, the test accuracy is highest for the centralized scheme. When comparing the test accuracy reached for the same transmitted data") CHOCo-SGD significantly outperforms the exact decentralized scheme, with the centralized performing worst. We note slight accuracy drop, i.e. after the same number of epochs (but much less transmitted data), CHOCO-SGD does not reach the same level of test accuracy than the baselines.
For the language modeling task, both decentralized schemes suffer drop in the training loss when the evaluation reaching the epoch budget; while our CHoCo-SGD outperforms the centralized SGD in test perplexity. When considering perplexity for fixed data volume (middle and right subfigure of Fig. B. CHOCO-SGD performs best, followed by the exact decentralized and centralized algorithms.
On Figure 4 we additionally depict the test accuracy of the averaged model (()) = 1 Σn x (left)
(+)
and averaged distance of the local models from the averaged model (right), for CHOCO-SGI on image classification task. Towards the end of the optimization the local models reach consensus (Figure right), and their individual test performances are the same as performance of averaged model. Interestingly, before decreasing the stepsize at the epoch 225, the local models are in general
2 The figure reports the transmitted data on the husiest node, i.e on the max-degree node (degree 14) node for decentralized schemes, and degree 32 for the centralized one.
7

---

Published as a conference paper at ICLR 2020
Depernulradd 920
Decerzalaedd 9G0
0.50
Training
0.50
0.25
0.25
Test
Cecedraaion 5013 ge-itomm)
163
(MB)
(MB)
Figure 2: Image classification: ResNet-20 on CIFAR-I0 on social network topology.
Comnebee 550
Centre 500 CHOcc Baais
CHCOR Big
Text perplexitt
Corpuleed
0
50
100
150
200
250
300
Epoch
Dota transmitted in (MB)
Data transm ttdd (MB)
Figure 3: Language modeling: LSTM WikiText-2 on social network topology.
Table 3: Summary of performance when training with the same epoch budget (as centralized SGD).
Algorithm
ResNet-20 20 (Fig []
LSTM (Fig
connections/oode
data/gradient
lop-1 acc.
data/gradient
test perplexity
Centralized SGD
32
1.04 MB
93.00
110.43 MB
89.39
Decentralized
91.38
CHOCO-SGD (Sign Norm)
14
0.032 MR
91.80
3.45 MB
86.58
Test top-1 accuracy
distance
4
70
Local Averoged
whole data
dizanoe
60
0
50
100
150
200
250
300
50
100
150
200
250
300
Epoch
Epoch
Parameter deviations for Resnet20 trained on Cifar10 (using CHOCO-SGD) on social network topology (32 workers). (Leftt) performance of the averaged model compared to the average of performances of local models. (Right) parameters divergence: averaged La consensus distance between local models x; and the averaged model
Figure 4:
E Xx, i.e., Σ [x, x
diverging from the averaged model, while decreasing only when the stepsize decreases. The same behavior was also reported in Assran et (2019).
USE CASE II: EFFICIENT LARGE-SCALE TRAINING IN DATACENTER
Decentralized optimization methods offer way address scaling issues for well connected devices, such as e.g. in datacenter with fast InfiniBand (100Gbps) or Ethernet (10Gbps) connections. Lian al. (2017) describe scenarios when decentralized schemes can outperform centralized ones, and recently, Assran et al.] (2019) presented impressive speedups for training on 256 GPUs, for the setting when all nodes can access all training data. The main differences of their algorithm to CHOCO-SGr SGD are the asynchronous gossip updates, time-varying communication topology and most importantly exact communication, making their setup not directly comparable to ours. We note that these properties of asynchronous communication and changing topology for faster mixing are orthogonal to our contribution, and offer promise to be combined.
Setup. We train ImageNet-1k (1.28M/50K training/validation) Deng al. 2009) with Resnet-50 (He et al. 2016). We perform our experiments on machines (nl -tanddardd from Google Cloud with Intel Ivy Bridge CPU platform), where each of machines has 4 Tesla P100
8

---

Published as a conference paper at ICLR 2020
Test top-1 accuracy
Certralled 5GD (SgT-RaTE
Training loss
Cer corislad 55B ga-Hoam
60
01000
01000 1s (ignehamm
Training
40
507 Centratoo Sigh+
20
CHICO Signe
0
10000 20000
30000
40000
50000
30000 40000 50000
Epoch
Time (s)
Time (s)
Figure 5: Large-scale training: Resnet-50 ImageNet-1k in the datacenter setting. The topology has nodes (each accesses GPUs). We use sign as the compression scheme, for Ciocco- SGD and Centralized SGD. For centralized SGD baseline without compression, we use all-reduce to aggregate the gradients; we use all- all-gather for centralized SGD with sign gradients quantization. The benefits of CHOCO-SGD can be further pronounced when scaling more nodes.
GPUs and each machine interconnected via 10Gbps Ethernet. Within one machine communication is fast and we rely on the local data parallelism to aggregate the gradients for the later gradients communication (over the machines). Between different machines we consider centralized (fully connected topology) and decentralized (ring topology) communication, with and without compressed communication (sign compression). Several methods categorized by communication schemes are evaluated: (i) centralized SGD (full-precision communication). (ii) error-feedback centralized SGD with compressed communications Karimireddy et al. (2019) through sign compression, (iii) de- centralized SGD (Lian et al. 2017) with parallelized forward pass and gradients communication (full-precision communication) ) and (iv) CHOCO-SGD with sign compressed communications. The mini-batch size each GPU is 128, and we follow the general SGD training scheme in (Goyal et al., 2017) and directly use all their hyperparameters for all evaluated methods. Due to the limitation of the computational resource, we did not heavily tune the consensus stepsize for CHOCO-SGI
Results. We depict the training loss and top-1 test accuracy in terms of epochs and time Fig. 5 CHOCo-SGD benefits from its decentralized and parallel structure and takes less time than all-reduce to perform the same number of epochs, while having only a slight 1.5% accuracy loss 4 In terms of time per epoch, speedup does not match that of (Assran et al., 2019), as the used hardware and the communication patterr are very different. Their scheme is orthogonal to our approach and could be integrated for better training efficiency. Nevertheless, still demonstrate time-wise 20% gain over the common all-reduce baseline, on our used commodity hardware cluster.
CONCLUSION
We propose the use of CHOCO- -GD (and its momentum version) for enabling decentralized deep learning training in bandwidtt-constrained environments. We provide theoretical convergence guarantees for the non-convex setting and show that the algorithm enjoys linear speedup in the number of nodes. We empirically study the performance of the algorithm in a variety of settings on the image classification (ImageNet- 1k, Cifar10) and on the language modeling task (WikiText-2). Whilst previous work successfully demonstrated that decentralized methods can be competitive alternative to centralized training schemes when no communication constraints are present (Lian et al.) 2017, Assran et al., 2019), our main contribution is to enable training in strongly communication- restricted environments, and while respecting the challenging constraint of locality of the training data. We theoretically and practically demonstrate the performance of decentralized schemes for arbitrary high communication compression, and under data-locality, and thus significantly expand the reach of potential applications of fully decentralized deep learning.
3 We estimate the consensus stepsize by running CHOCO-SCO CRDCOO-SGD&O with different values for the first epochs.
A Centralized SGD with full precision gradients achieved test accuracy of 76.37%. v.s. 76.03% for centralized SGD (with sign compression), v.s. 74.92% for plain decentralized SGD, and 75.15% for CHoCo-SGD (with sign compression).
We consider undirected communication, contrary to the directed 1-peer communication (every node sends and receives one message at every iteration) in Assran et al. (209))

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
We acknowledge funding from SNSF grant Award.
as well as a Google Focused Research
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effici SGD via gradient quantization encoding] NIPS Advances in Neural Information Processing Systems 30, pp. 1709-1720. Curran Associates, Inc., 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence sparsified gradient methods) NeurlPS Advances in Neural Information Processing Systems 37. pp. 5977-5987. Curran Associates, Inc., 2018.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. (ttochsttic gradient push for distributed deep learning In JCMI- Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 343-353. PMLR, 09-15 Jun 2019.
Albert S. Berahas, Charikleia lakovidou, and Ermin Wei. Nested distributed gradient methods with adaptive quantized communication. arXiv preprint, pp. arXiv: 190..081439099 19,,, 2019.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli,, and Animashree Anandkumar. SignSGD: Com- pressed optimisation for non-convex problems In Proceedings of 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 560-569, Stockholmsmäss
san, Stockholm Sweden, 10- 15 Jul 2018, PMLR.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms Trans. Netw. 14(S1):2508 2530,, June 2006.
IEEE/ACM
R. Carli, F. Fagnani, P. Frasca, T. Taylor, and S. Zampieri. Average consensus networks with transmission noise or quantization. In 2007 European Control Conference (ECC), pp. 1852-1857, July 2007.
R. Carli, F. Bullo, and S. Zampieri. Quantized average consensus via dynamic coding/deecodin schemes. International Journal Robust and Nonlinear Control, 20: 10:1561, 2010a.
R. Carli, P. Frasca, F. Fagnani, and S. Zampieri. Gossip consensus algorithms via quantized communication. Automatica, 46:70-80, 2010b.
A. Davis, B. Gardner, and M. R. Gardner. Deep South. University of Chicago Press, Chicago, IL., May 1941.
Ofer Dekel, Ran Bichh-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches Mach. Learn. Res., 13(1):165-202 January 2012.
J. Deng, W. Dong, R. Socher, I..J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione. Gossip algorithms for distributed signal processing. Proceedings of the IEEE, 98(11):1847-184, Nov 2010.
Thinh T. Doan, Siva Theja Maguluri, and Justin Romberg. Accelerating the Convergence Rates Distributed Subgradient Methods with Adaptive Quantization. arXiv e-prints, art. arXiv: 1810. 810.13245, 13245, Oct 2018.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch. Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in hour. arXiv preprint (o0:::706002333 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 778-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9:1735-80, 12 1997.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik, and Schastian Urban Stich, SSochasticc distributed learning with gradient quantization and variance reduction arXiv preprint, pp. arXiv:1904.05113: 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes) In ICML Proceedings of the 36th International Conference Machine Learning, volume 97, pp. 3261. PMLR, 09-11 Jun 2019.
10

---

Published as a conference paper at ICLR 2020
David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS '03, pp. 482-, Washington, DC, USA, 2003, IEEE Computer Society,
Anastasia Koloskova, Sehastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication In ICMI.- Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 3478-3487. PMLR. 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. [Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent In NIPS Advances Neural Information Processing Systems 30, pp. 5330-5340. Curran Associates, Inc., 2017.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't I use large mini-batches, use local SGD ICLR- International Conference on Learning Representations, 2020.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the
communication bandwidth for distributed training In ICLR 2078 International Conference on Learning Representations, 2018.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. In AISTATS 2017 Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273 1282, 2017.
H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networkss using model averaging
CoRR, abs/1602.00629, 2016.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint 1600::1609.07843, 2016.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. arXiv preprint, pp. arXiv: 708.02288, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv e-prints, pp. 1901:19900009699 2019.
A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communication tradeoff's in decentralized optimization. Proceedings of the IEEE, 106(5);953-97,, May 2018
Angelia Nedić, Alex Olshevsky, Asuman Ozdaglar, and John N. Tsitsiklis. Distributed subgradient methods and quantization effects. In Proceedings of the 47th IEEE Conference Decision and Control, CDC 2008, pp. 4177-4184, 2008
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach parallelizing Stochastic gradient descent NIPS Advances in Neural Information Processing Systems 24, pp. 693-701. Curran Associates, Inc., 2011.
Amirhossein Reisizadeh, Aryan Mokhtari. Hamed Hassani, and Ramtin Pedarsani. An exact quantized decen- tralized gradient descent algorithm. arXiv e-prints, pp. arXiv:1806. 1536, 2018.
Amirhossein Reisizadeh, Hossein Taheri, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. Robust and Communication-effiteen collaborative learning arXiv e-prints, pp. arXiv: 1907. 1055,, 2019.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks In Proceedingy of the 34th International Conference on Machine Learning, volume 70 Proceedings of Machine Learning Research, pp. 3027-3036, International Convention Centre, Sydney, Australia, 06 11 Aug 2017. PMLR.
Kevin Scaman, Francis Bach, Sehastien Bubeck, Laurent Massoulié, and Yin Tat Lee. Optimal algorithms for non-smooth distributed optimization in networks In NeurlPS Advances in Neural Information Processing Systems 31, pp. 2745 2754. Curran Associates, Inc., 2018
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bii stochastic gradient descent and its application to data- aarallp distributed training of speech DNNs. In INTERSPEECH, pp. 1058 1062. ISCA, 2014.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedbckk framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint, pp. 1eX.iv:1999005300 05350, 2019.
11

---

Published as a conference paper at ICLR 2020
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory In NeurlPS- Advances Neural Information Processing Systems 31, pp. 4452 4463. 2018.
Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In INTERSPEECH, pp. 1188-1492, ISCA, 2015.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training NeurlPS Advances Neural Information Processing Systems 31, pp. (663-7673. Curran Associates, Inc., 2018.
Hanlin Tang, Xiangru Lian, Shuang Qiu, Yuan, Ce Zhang, Tong Zhang, and Liu. Deepsqueeze: Decentral ization meets error-compensated compression arXiv preprint, pp.
2019.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang. Gauri Joshi, and Soummya Kar. exact quantized decentralized gradient descent algorithm arXiv e-prints, pp. arXiv:1905.09433 2019.
Jiangiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication--ffiieen distributed optimization In NeurlPS Advances in Neural Information Processing Systems 31, pp. 1306 1316. Curran Associates, Inc., 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning In NIPS Advunces in Neural Information Processing Systems 30, pp. 1509-1511 Curran Associates, Inc., 2017.
L. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion based on average consensus. In IPSN 2005. Fourth International Symposiun Information Processing in Sensor Networks, 2005., pp. 63-70. April 2005.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging Systems & Control Letters, 53(1): 65-78 78-7,.22 2004.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization In /CML- Proceedings the 36th International Conference on Machine Learning, volume 97, pp. 7184-7193, PMLR, 09-15 Jun 2019.
Deming Yuan, Shengyuan Xu, Huanyu Zhao, Lina Rong. Distributed dual averaging method for multi agent opptimization with quantized communication Systems & Control Letters, 61(11):1053 1061, 2012.
Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, and Christopher Ré, Parallel SGD: When does averaging help? arxiy preprint, 2016.
12

---

Published as a conference paper at ICLR 2020
A CONVERGENCE OF CHOCO-SGD
In this section we present the proof of Theorem For this, we will first derive a slightly more general statement: in Theorem A.3 we analyze CHOCo-SGD for arbitrary stepsizes y, and then derive Theorem 4. as special case.
The structure of the proof follows Koloskova et al. (2019). That is, first show that Algorithm is a special case of a more general class of algorithms (given in Algorithm 3 Observe that Algorithm | consists of two main components: @ the stochastic gradient update, performed locally on each node, and ( the (quantized) averaging among the nodes. We can show convergence of all algorithms of this type-iic. stochastic gradient updates @ followed by an arbitrary averaging step O-as as long as the averaging scheme exhibits linear convergence. For the specific averaging used in CHOCO-S SGD, linear convergence has been shown in (Koloskova al., 2019) and we will use their estimate of the convergence rate of the averaging scheme.
A.1 A GENERAL FRAMEWORK FOR DECENTRALIZED SGD WITH ARBITRARY AVERAGING
For convenience, we use the following matrix notation in this subsection.
(0) x xi .....
X
Rdxn
OF(X (()) = (x ccl (F )
Rd
Decentralized SGD with arbitrary averaging is given in Algorithm 3
Algorithm 3 DECENTRALIZED SGD WITH ARBITRARY AVERAGING SCHEME
input: (0) [x("), ...., { stepsize 1) averaging function h Rdxx x gdxn + Rdxa x Rdxx initialize (
I: for t in ....T 1 do (in parallel for all workers i [n]] x (()) - nOF,(X()), (())
stochastic gradient updates
{ 3: (X(+1), ((+1)) h ((x(++)),
blackbox averaging/gossip
4: end for
Assumption 3. For an averaging scheme h: Rdxa Rddx - Rdxn x RRdx let (X+, (Y)
=
for x, Y Rdxa, Assume that h preserves the average of iterates:
x+ 11
11
-
VX,Y E Rdxn
(4)
n
n
and that it converges with linear rate for parameter 0 < <c51
E. ( y+) s (1 - (X)(
VX. Y E dxn
(5)
and Laypumov function V (X, = 1X +IX YI with x= 1 XII where E, denotes the expectation over internal randomness of averaging scheme h.
Example: Exact Averaging. Setting X = XW and Y = X gives an exact consensus averaging algorithm with mixing matrix W (Xiao Boyd 2004). It converges the rate e p. where is an eigengap of mixing matrix W. detined in Assumption I Substituting it into the Algorithm we recover D-PSGD algorithm, analyzed in Lian et al. (2017).
Example: CHOCO-SGD. To recover CHOCO-SGD, we need to choose CHOCO- GOSSIP (Koloskova et al., 2019) as consensus averaging scheme, which defined as X+ = X + ?Y - 7) and y+ = Y + Q(x+ - Y) (in the main text we write X in- stead of Y). This scheme converges with 28 The results from the main part be recovered by
13

---

Published as a conference paper at ICLR 2020
substituting this c 0²6 in the more general results below. is important to note that for Algorithm 82
given in the main text, the order of the communication part ① and the gradient computation part @ exchanged. We did this to better illustrate that both these parts are independent and that they can be executed in parallel. The effect of this change can be captured by changing the initial values but does not affect the convergence rate.
A.2 PROOFS
Remark A.1 (Mini-batch variance). for functions Sú. Fi defined in ① Assumption 2 holds, i.e. Eg [x. ff(x)) S of. E [n], then
Vi((x() VV-(- (50)))))(0))
E
(0)
(6)
2=1
where 02
En of
Proof. This follows from
σ²
E
Y
Σ
BIII| + +Σ i
B(Y, Yj)
E
2
<
Σ
0
2
n
n 1=1
for Y, = -VF())) independent of Ej since i + j.
(0) )
Expectation of scalar product is equal to zero because & is
Lemma A.2. Under Assumptions
73 the iterates of the Algorithm
with constant stepsize satisfy
Σ
x(1)
x(0) |
12n
S "
c²
Proof of Lemma A.2
We start by following the proof of Lemma 21 from Koloskova et al. (019))
Define rz = E
(())
x + Bl| x - y
x
c)BB X (++ - x((+ 11
y(u + (1 +11 c)DB
x ((+
Tt+1
111
-1- [] T - x(1 + nOF(X()) (01)
+ +1 -(1-c)B
- x n g(1))
F
(1 (1-c)(1 + a1 (|XX) x + ||(00
x100/1 F)
Baiik +1-
Ooo goo) (())
( 1)
2
+ 1000)
n
(1 - () (1 1 | -x0o1/ + -||000 x1o11²
2n(1 + a)p
a=? 2 (1 ;) E 1 x(0 + 1||r00) - -1|100--x001 -x(o0(]))
+ 6n
c 1²2
Define A 3nG got recursion
T(t1 - [ c) r:
PA 2
2
Verifying that r2 < 2 ş satisfy recursion completes the proof as E x - x10_ xx00 St
14

---

Published as a conference paper at ICLR 2020
Indeed, To = 0 1y of as x = =x and ( =0
r++1 _ (1-2) 2
re + sp n/= - (1 (1- (1-2) 4A c
2A t1p
2 = rp
4A c²
c
Theorem A.3. Under Assumptions
3
with constant stepsize 1j <
1, the averaged iterates
(+)) 1 Ei= x of Algorithm satisfy:
Σ
1
TT(T -(x)))))))))))
(r)
2 +
33G L² 6
+ ")
T+1
n
where e denotes convergence rate of undertying averaging scheme.
Proof of Theorem A.3 By L-smoothness
B111 ((x(1=1)) = Be+1 f (x(()
Σ
(x (1) $00)
V Vx (1) (5 ) +B4+1 ""
n
S {((10)) BB+1
V)(((()).
1 Σ
F (x e(0)
n
1=1
i=1
::
TT2
To estimate the second term, we add and subtract {x((x(())
- n Ti = - V f( + Vf(x(')) (x((1))
Σ Vi(((())
V)((()) [)((x()) |
For the last term, we add and subtract ()( and the sum of (x(
T2 E,+1
(x
-
(x (1) + V
[(x(0) - vA(x -(x(0)))AA
Combining this together and using L-smoothness to estimate | - V)i(( 11)
E+11 f(x((-1)) f(( 17 ( (2-11) Lm) | (GOL² + 2
1
x
(8)
L
2n
Using Lemma A.2 to bound the third term and using that 7 S th in the second and in the third terms
E+s1 ((x(++1)) < f(x())
7 v {)(x
+ 173 G2
+
Lo²
c
2n
Rearranging terms and averaging over t
1 T
11 3
2LJ
n + Σ (Ef(x(() - -Bf(x((+1))
n
T
n
(T +1) ()(x(0)) -+m) + 2
4
n 1u 36G212
15

---

Published as a conference paper at ICLR 2020
Corollary A.4. Under Assumptions
with constant stepsize
/ T-I for 2 16n the
averaged iterates x(1)
2
of Algorithm 3 satisfy:
7
4 ( - (4) 20
Σ T+1 1=
1
36G (1'
+
(n(T+]
where denotes convergence rale of underlying averaging scheme.
The first term shows a linear speed up compared to SGD on one node, whereas the underlying averaging scheme affects only the second-order term. Substituting the convergence rate for exact averaging with W gives the rate O(//mT + n/(T)²)).
CHOCO-SGD with the underlying CHOCo- CHOCo-GOSSIP GOSSIP averaging scheme converges at the rate O(1/ATT + x/)Tp>83)). The dependence p (eigengap of the mixing matrix W) is worse than the exact case. This might either just be an artifact of our proof technique or a consequence of supporting arbitrary high compression.
A.3 CONVERGENCE FOR ARBITRARY T
The previous result holds only for T larger than 16nL2. This not necessary and can be relaxed by carefully tuning the stepsize.
Lemma A.S. For any parameters ro 2 0, 0, 2 0, 2 O there exists constant stepsize nj S such that
To T
+ by + erj² 52
bro
2/3
To
dro
(T + 1)
T T
T+1
T+1
Proof. Choosing n = min
Fo b[T41J
c(T++]
7
< d
we have three cases
17 = 1/ and is smaller than both
ro
and
To c(T+1))
then
6(T+1)
1/2
TT v
dro
+
b
+
bro
+ T+1
dro
+
2/33
To
T ++1 1
d
d²
T T+1
T
1/2
17
(,7+TJ)
< [(T+IT)
then
V 2 2
T+11)
rob
1/$
te
b(T + 1)
To
2
T +1
rob
1/2
+ e
To (T 1)
The last case, 17
Pu b(T+1}
((I+1)
3
V < 2e
To
+
< 2ea
ro
+
bro
(T [ 1)
E(T + 1)
(T 1)
T+
Corollary A.6 (Generalized Theorem as Lemma A.5 the averuged iterates
Under Assumptions 7 with constant stepsize tuned
(())
Eiixx x of Algorithm satisfy:
2
2L
GLFo
16LF
T+I
V
S
+1)
+ 17
c(T++1 +1)
+
T+I
1=
where denotes convergence rale of underlying averaging scheme, Fo -(x(()) s
16

---

Published as a conference paper at ICLR 2020
Proof. The result follows from Theorem A.3 and Lemma A.5 with ro = 4 (1(x10)-
20 3GG²L and 4L.
n
The corollary gives guarantees for the averaged vector of parameters however in decentralized setting very expensive and sometimes impossible to average the parameters distributed across several machines, especially when the number of machines and the model size is large. We can get similar guarantees on the individual iterates x; as c.g. (Assran et al. 2019). We summarize these briefly below.
Corollary A.7 (Convergence of local weights). Under the same setting as in Corollary A.6
1
T
2 <B1
2L
GLFo
32LFo
vf(x
37
T+
n(T +
T
Proof of Corollary
A.7
2
V)( +2 +2|[V[(((() ([²
2 V
T+1
t= n
T+1
T
2L
x
19 +
xx0
1=U
where we used T-smoothness of f. Using Theorem get the statement of the corollary.
A.3 and tuning the stepsize as Lemma A.5 we
B USEFUL INEQUALITIES
Lemma B.1. For arbitrary set of n vectors
(a: Ii
E Rdd
Σ a
S n
a 1
(7)
Lemma B.2. For given two vectors b E Rd
(a. b) S |||| + |lb|]
Vy >
(8)
Lemma B.3, For given two vectors a, b e Rd
a + bl1 < (1+ +1+aa This inequality also holds for the sum of two matrices A, B Buxd d in Frobenius norm.
Va > 0.
(9)
C COMPRESSION SCHEMES
We implement the compression schemes detailed below.
g
Alistarh al. 2017). The unbiased gsgd, Rd TRd compression operator (for b > given as
gsgd, (x) ||x|| sig(x) 2- (6-1)) 2(b [x|
|
where u ~u.a.r [0, 1]d is a random dithering vector and sig(x) assigns the element-wise if (x); 2 0 and (sig(x)); -1 1 if (x); < 0. As the value in the right
sign: (sig(x)); bracket will be rounded to an integer in {0, {O...., 2 1) 1}. each coordinate can be encoded with at most (b 16-11 1) + 1 bits (1 for the sign). For more efficent encoding schemes cf. Alistarh et al. (2017).
17

---

Published as a conference paper at ICLR 2020
A biased version is given
gsgd, (x) = ||*|| sig(()) 2-(1-1) 2(6-1)
x
+ u
x
va for min 22
20-11) } and is a compression operator
Koloskova et al.
2019).
random, (Wangni et al. random from the set IRd operator is defined
2018 Let u E {0, 1] d be a masking vector, sampled uniformly at {0. 11a [u]] [ad]]. Then the unbiased random, R
d [ad]
random,
The biased version is given random, (x) = u.
and a compression operator (Stich al. 2018).
Only 32 32|ad] ad] bits are required to send random, (x) to another node-all the values of non-zero entries (we assume that entries are represented float32 numbers), Receiver can recover positions of these entries
knows the random seed of uniform sampling operator used to select these entries. This random seed could be communicated once preprocessing stage (before starting the algorithm).
top, (Alistarh et al., 2018 Stich et al., 2018). The biased top,: Rd Rd operator is defined as
(x) x ④ u(x),
where u(x) E 1) 1)d, ||u|| = [ad] is a masking vector with (u); = 1 for indices
E π (fl..... [od] }) where the permutation ı such that ((x) 2 (xx) 2
(xa) The top, operator is a 8 = compression operator (Stich et al. 2018).
In the case of topa compression 2 32 | bits are required because along with the values
we need to send positions of these values.
sign (Bernstein et al. 2018: Karimireddy et al. 2019). The biased (scaled) sign: Rd B compression operator defined as
sign(x) |x||| sgn(x).
The sign operator is 8 |
compression operator Karimireddy et al. 2019
d|
In total for the sign compression need send only + bits-one bit for every entry in x and 32 bits for ||x||]-
D CHOCO-SGD WITH MOMENTUM
Algorithm 2 demmnstratess how to combine CHOCO-SGD with weight decay and momentum. Nes- terov momentum be analogously adapted for our decentralized setting.
E ERROR FEEDBACK INTERPRETATION OF CHOCO-SGD
To better understand how does CHOCO- SGD work, we can interpret as an error feedback algorithm Stich al. 2018 Karimireddy et al. 2019 Stich & Karimireddy 2019). We can equivalently rewrite CHOCo-SGD (Algorithm) I as Algorithm The common feature of error feedback algorithms is that quantization errors are saved into the internal memory, which is added the compressed value at the next iteration. In CHOCO-SGI the value we want to transmit is the difference x!" x (c-1) which represents the evolution local variable x; step Before compressing this value on line the internal memory is added on line 3 to correct for the errors. Then, on line 5 internal memory is
updated. Note that m!! (t-1) x (1) in the old notation.
18

---

Published as a conference paper at ICLR 2020
Algorithm 4 CHOCO-SGD (Koloskova et al. 2019) as Error Feedback
input: Initial values x;
(0) _d on each node E [n]. consensus stepsize 7, SGD stepsize 1).
communication graph G = ([n] E) and mixing matrix W, initialize x!") x (-1) == 0, vi E
[n]]
for in ....T 1 do {in parallel for all workers [n]]
= x;
(t- 1)
+ E LyALEEE wis (x,)) x(")
modified gossip averaging
v
(t) = xi x;
(t)
(1-1) +m?"
4: q. (1) Q(v
(1)
compression
(1+1)
vi (1)
(8)
5: m
- -q,
< memory update
6: for neighbors j: {i.j} E E (including {i} E E) do
Send ( and receive q
4 communication
x((+1) = 9 + (()) X
local update
end for
10: Sample (1) compute gradient gi 10 VFF( ((
(1+4) = x, (1) (t)
11:
X;
77,
stochastic gradient update
12: end for
F DETAILED EXPERIMENTAL SETUP AND TUNED HYPERPARAMETERS
We precise the procedure of model training as well as the hyper-parameter tuning in this section.
Social Network Setup. For the comparison consider CHOCC-SSG with sign compression (this combination achieved the compromise between accuracy and compression level in Table D)). decentralized SGD without compression, and centralized SGD without compression. We train two models, firstly ResNet 20 (He et al.] (2066) (0.27 million parameters) for image classification on the ci Cifar10 0 dataset (50K/10K training/test samples) (Krizhevsky) (012)) and secondly, a three-layer LSTM architecture (Hochreiter & Schmidhuber (997) (28.95 million parameters) for language modeling task on WikiText-2 (600 training and 60 validation articles with a total of 2'088' 628 and 217'646 tokens respectively) (Merity et al. 2016). For the language modeling task, borrowed and adapted the general experimental setup of Merity et al. (2017). where we use a three-layer LSTM with hidden dimension of size 650. The loss is averaged over all examples and timesteps. The BPTT length is set to 30. We fine-tune the value of gradient clipping (0.4), and the dropout (0.4) is only applied the output of LSTM.
We train both of ResNet20 0 and LSTM for 300 epochs, unless mentioned specifically. The per node mini-batch size is 32 for both datasets. The momentum (with factor 0.9) is only applied on the ResNet20 training.
Social Network and a Datacenter details. For all algorithms, we gradually warmup (Goyal et al.) 2017) the learning rate from relative small value (0.1) to the fine-tuned initial learning rate for the first 5 training epochs. During the training procedure, the tuned initial learning rate decayed by the factor of 10 when accessing 50% and 75% of the total training epochs. The learning rate is tuned by finding the optimal initial learning rate (after the scaling).
The optimal r is searched in pre-defined grid and we ensure that the best performance was contained in the middle of the grids. For example, if the best performance was ever at one of the extremes of the grid, we would try new grid points. Same searching logic applies to the consensus stepsize.
Table 4 demonstrates the fine-tuned hpyerparameters CHOCO-SGD for training ResNet-20 on C0far10, while Table reports mee-tuned hpyerparameters of our baselines. Table 5 demonstrates the fine-tuned hpyerparameters of CHOCO-SGD for training ResNett20/LSSTY on a social network topology.
We estimate the runtime information (depicted in Figure 5 of different methods from three trials of the evaluation Google Cloud (Kubernetes Engine). More precisely, create the cluster
19

---

Published as a conference paper at ICLR 2020
Google Cloud for three times and each time estimate the time per mini mani-bbtch of different methods (through the first two training epochs).
Table 4:
Tuned papam--araeeeerss of CHOCO-SOO --D for training ResNet 20 on Ci fifrl1, corresponding to the ring topology with 8 nodes in [able We randomly split the training data between nodes and shuffie it after every epoch. The per node mini-batch size 128 and the degrce of each node is 3.
Compression schemes
Learning rate
Consensus stepsize
QSGD (16-bit)
1.60
0.2
QSGD (8-bit)
0.96
0.2
QSGD (4-b
1.60
0.075
QSGD (2-bit)
0.96
0.025
Sparsification (random-50%)
2.40
0,45
Sparsification (random-10%)
1.20
0.075
Sparsification (random-1%)
0.48
0,00625
Sparsification (top-50%)
1.60
0.45
Sparsification
1.60
0.15
Sparsification (top-1%)
1.20
0.0375
Sign+Norm
1.60
0.45
Table 5: Tuned hyper-parameee of CHOCO-SC ARDDO corresponding the social network topology with 32 nodes in Table We randomly split training data between the nodes and keep this partition fixed during entire training (no shuffling). The per node mini-batch size 32 and the maximum degree of the node 14.
Configuration
Learning rate
Consensus stepsize
ResNet-20, Cifar10, Sign+Norm LSTM, WikiText-2, Sign+Norm
1.0
0.5
25
0.6
Table Tuned hyper-parameters DCD, ECD, and DeepSqueeze training ResNet-20 on Cifarll corresponding to the ring topology with 8 nodes in Table We randomly split the training data between nodes and shuffle it after every epoch. The per node mini-batch size is 128 and the degree of each node is 3. We only report the hpyerparameters corresponding results that reach reasonable performance in experiments.
Compression schemes
I Learning rate
Consensus stepsize
DCD, QSGD (16-bit)
2.40
DCD, QSGD (8-bit)
1.20
DCD, Sparsification (random-50%)
0.80
DCD, Sparsification (top-50%)
1.20
DCD, Sparsification (top~10%)
1.60
DCD, Sparsification (top-1%)
2.40
ECD, QSGD (16-bit)
0.96
BCD, QSGD (8-bit)
1.20
DeepSquceze, QSGD (4-bit)
0.60
0.01
DeepSqueeze, QSGD (2-bit)
0.80
0.005
DeepSqueeze, Sparsification (top-50%)
0.80
0.05
DeepSqueeze, Sparsification (top-10%)
0.60
0.01
DeepSqueeze, Sparsification (top-1%)
0.40
0,005
DeepSqueeze, Sparsification (random-19%
0.80
0.0005
DeepSqueeze, Sign+Norm
0.48
0.01
20

---

Published as a conference paper at ICLR 2020
G ADDITIONAL PLOTS
To complement our results for scaling to a large number of nodes, we here additionally depict the learning curves (e.g. accuracy) for the training 64 nodes. We also mark the levels used for Fig. I
Texc
107
161
237
2.'
30'
traamitodd
Figure 6: Scaling of CHOCO-SGD with sign compression to large number of devices Cifar
dataset. Convergence curves for 64 nodes. Vertical lines corresponds epoch/bits budget used in Fig.
Table 7: The exact epoch for the same hits budget in Fig.
16
36
64
Centralized
5
6
6
Decentralized (Ring)
17
32
Decentralized (Torus)
10
18
29
CHOCO (Ring)
105
408
904
1588
CHOCO (Torus)
55
206
454
796
Table The exact transmitted bits (in MB) for the same epoch budget in Fig.
n 4
n
16
36
71
64
Centralized
139683
140041
144299
142899
Decentralized (Ring)
69841
17505
8016
4554
Decentralized (Torus)
139683
35010
16033
9109
CHOCO (Ring)
2208
564
253
144
CHOCO (Torus)
4417
1129
506
288
We additionally visualize the learning curves for the social network topology in Fig. 7 and Fig. g
Training accuracy
Training tap accuracy
Tost top- top-1 accuracy
100
80
90
60
Centrllne wew.aaa
Centrolzed 500
Centrullaed PCD une
40
100
200
300
50
40
1000
200
300
Epoch
Data transmitted in (MB)
Epoch
Training top-1 accuracy.
(b) Training top-1 accuracy.
(c) Test top-1 accuracy.
Figure 7: Training ResNet- CIFAR-10 10 with decentralized algorithm real world social network topology. topology has 32 nodes and we assume each node can only access a disjoint subset of the whole dataset. The local mini-hatch size is 32.
We additionally provide the learning curves of training top-1, top-5 accuracy and test top-5 accuracy for the datacenter experiment in Fig.
21

---

Published as a conference paper at ICLR 2020
Centralired SGD
ea
Centralzed SC0
Test perplexity
Decentallzed
Test loss
CN0C0 (Sin-Normi
e7
(Sign Nomn)
e5
e4
50
100
150
200
250
300
10*
10
10
10?
10a
Epoch
Data transmitted (MB)
(a) Test loss.
(b) Test perplexity.
Figure Training LSTM on WixiText2 with decentralized algorithm on a real world social network topology. The topology has 32 nodes and we assume each node can only access a disjoint subset of the whole dataset. The local mini-batch size is 32.
Training accurccy
Training top-5 accuracy
Test top-1 accuracy
40
Contiairee siiee 100
Contudernt son
Centra lene 901 Deneent uaivel soo sigonieemi
20
Dicc exsiers 5no
Bocente seno
Gr0C0 (iigeehmmm
ta lignetom
Epoch
Epoch
(a) Training top-1 accuracy.
(b) Training top-5 accuracy.
(c) Test top- accuracy.
Figure 9: Large-scale training: ResNet-S5 on ImageNet datacenter.
22


Reviews:
[{"review_id": "rkeaNDmTKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the convergence of CHOCO-SGD for nonconvex objectives and shows its linear speedup while the original paper of CHOCO-SGD only provides analysis for convex objectives. The momemtum version of CHOCO-SGD is also provided although no theoretical analysis is presented.\n\nExtensive empirical results are presented in this paper and the two use cases highlight some potential usage of the algorithm. However, there some concerns which could be addressed.\n\nFirst, the authors only provide analysis on CHOCO-SGD but the comparison with baselines are based on their momemtum versions. Moreover, some highly relevant baseline like DeepSqueeze are not cited and compared. Thus, the advantage of vanilla CHOCO-SGD over other alternatives is not convincing. \n\nSecond, the cores of decentralized optimization include minimization of objective and consensus of the solution. However, no evaluation of the consensus is presented and this leads to the following point.\n\nThird, it seems the authors report the average performance over all nodes using their individual model. If this is the case, the reported perfromance and comparison are not convincing. Without consensus, different nodes can have individual minimizer. In this case, the obtained average loss can be even smaller than the optimal loss. Under current measurement, if we run SGD on each worker individually without any communication, we will still get pretty good performance but this does not achieve the goal of decentralized optimization. Further clarification on this is needed.\n\nOverall, I think the technical contribution of this paper is unclear and the evaluation is not convincing. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkx924tpKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present an algorithm CHOCO-SGD to make use of communication compression in a decentralized setting. This is an interesting problem and the results are promising. Firstly they prove the convergence rate of the algorithm on non-convex smooth functions, which shows a nearly linear speedup. \n\nSecond, on the practical part, there have 3 main results:\n\t1. They compare CHOCO-SGD under various compression schemes with the baseline. The results show the algorithm generally outperforms the baseline.\n\t2. They implement it over a realistic peer-to-peer social network and show a great communication performance under such a network with limited bandwidth.\n\t3. In a datacenter setting, they compare the algorithm with all-reduce, which is a centralized communication method. The results show a strong training reduction for CHOCO-SGD.\n\nAlso, the paper is mostly nicely written.\n\nHowever, there have several issues:\n\n\t1. In the introduction, they introduce their experiments with the order from \"datacenter experiment\" to \"peer-to-peer experiment\", which is different from the actual presenting order.\n\t2. In the description of Algorithm 1, the representation of initial values should be x{(-1/2)}_{i} instead of x{(0)}_{i} since line 2 using the term x^{t-1/2}_{i} with the range of t from 0 to T-1.\n\t3. About \"datacenter setting\" experiment, it seems not an apple to apple comparison between CHOCO-SGD and all-reduce method since CHOCO-SGD stands for the decentralized algorithm with compression and all-reduce stands for a centralized algorithm without compression. It's better to compare with at least one centralized algorithm with a compression scheme (like QSGD[1], signSGD[2], DGC[3]).\n\t4. Although they compare with the baseline (DCD and ECD) on Cifar-10 dataset,  it's worth to compare with them on the ImageNet since the result may be different under large-scale training.\n\nOverall, this could be a great paper if fixing the issues above.\n\n\n[1] D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-efﬁcient SGD via gradient quantization and encoding. In Proc. Advances in Neural Information Processing Systems (NIPS), 2017.\n\n[2] Bernstein J, Zhao J, Azizzadenesheli K, Anandkumar A. signSGD with majority vote is communication efficient and fault tolerant. arXiv. 2018 Oct 11.\n\n[3] Lin Y, Han S, Mao H, Wang Y, Dally WJ. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887. 2017 Dec 5.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgEjGYpKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies non-convex decentralized optimization with arbitrary communication compression. It is well motivated and well written. The authors consider CHOCO-SGD for non-convex decentralized optimization and establish the convergence result based on the compression ratio. This result does not rely on specific quantized method and main term in the upper bound matches with the centralized baseline. The authors also show CHOCO-SGD with momentum is effectiveness in practical. The experimental results on several benchmark datasets validate the algorithm achieves better performance than baselines\n\nBoth of the theoretical and empirical results are convincing. I believe this paper is ready for publication.\n\nMinor comments:\n\n1. It is prefer to present Algorithm 2 and 3 in the main text, since they are mentioned by the statement of Theorem 4.1 and used in experiments respectively.\n\n2. Can you provide some theoretical guarantee of CHOCO-SGD with momentum?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an algorithm CHOCO-SGD to make use of communication compression in a decentralized setting. This is an interesting problem, and the paper is well-motivated and well-written. On the theoretical side, the authors prove the convergence rate of the algorithm on non-convex smooth functions, which shows a nearly linear speedup. The experimental results on several benchmark datasets validate the algorithm achieves better performance than baselines. These can be made more convincing by comparing with more baselines (including DeepSqueeze and other centralized algorithms with a compression scheme), and on larger datasets. The authors should also clarify results on consensus.
Decision: Accept (Poster)