Moniqua: Modulo Quantized Communication in Decentralized SGD
Authors: Yucheng Lu
Christopher De Sa
Venue:  (2020)
Keywords: decentralized training
quantization
communicaiton
stochastic gradient descent

Abstract: Decentralized stochastic gradient descent (SGD), where parallel workers are connected to form a graph and communicate adjacently, has shown promising results both theoretically and empirically. In this paper we propose Moniqua, a technique that allows decentralized SGD to use quantized communication. We prove in theory that Moniqua communicates a provably bounded number of bits per iteration, while converging at the same asymptotic rate as the original algorithm does with full-precision communication. Moniqua improves upon prior works in that it (1) requires no additional memory, (2) applies to non-convex objectives, and (3) supports biased/linear quantizers. We demonstrate empirically that Moniqua converges faster with respect to wall clock time than other quantized decentralized algorithms.  We also show that Moniqua is robust to very low bit-budgets, allowing  less than 4-bits-per-parameter communication without affecting convergence when training VGG16 on CIFAR10.

Under review as a conference paper at ICLR 2020
MONIQUA: MODULO QUANTIZED COMMUNICATION IN DECENTRALIZED SGD
Anonymous authors Paper under double-blind review
ABSTRACT
Decentralized stochastic gradient descent (SGD), where parallel workers are con- nected form graph and communicate adjacently, has shown promising results both theoretically and empirically. In this paper we propose Moniqua, a technique that allows decentralized SGD to use quantized communication. We prove in theory that Moniqua communicates a provably bounded number of bits per itera- tion, while converging at the same asymptotic rate as the original algorithm does with full-precision communication. Moniqua improves upon prior works in that it (1) requires no additional memory, (2) applies to non-couvex objectives, and (3) supports biased or linear quantizers. We demonstrate empirically that Moniqua converges faster with respect to wall clock time than other quantized decentralized algorithms. We also show that Moniqua is robust to very low bit- bit-budgets, allowing less than 4-bits-per-parameel communication without affecting convergence when training VGG16 CIFARIO.
INTRODUCTION
Stochastic gradient descent (SGD), as a widely adopted optimization algorithm for machine learning, has shown promising performance when running at large scale (Zhang) [004 [Bottou| 2010 Dean ct al. 2012 Goyal et al. 2017). However, the communication bottleneck among workers when running distributed SGD presents non-trivial challenge (Alistarh 2018). Mtate-of-the-aa frameworks such as TensorFlow (Abadi et al. 2016), CNTK (Seide and Agarwal 2016) and MXNet (Chen et al. 2015) are built in centralized fashion, where workers exchange gradients either via centralized parameter server (Li et al. 2014a b) or the MPI AllReduce operation (Gropp et al.) 1999). Such a design, however, puts heavy pressure on the central server and strict requirements on the underlying network. In other words, when the underlying network is poorly constructed, i.c. high latency or low bandwidth, can easily cause degradation of training performance due to communication congestion in the central server or stragglers (slow workers) in the system.
There are two general approaches to deal with these problems: (1) decentralized training (Lian et al. 2017a by Tang et al. 2018a Hendrikx et al. (018)) and (2) quantized communication (Zhang al. 2017 Alistarh al. 2017 Wen et al.) 2017). In decentralized training, all the workers are connected form graph and each worker communicates only with adjacent workers by averaging model parameters. This balances load and is robust to scenarios where workers can only partially connected or the communication latency is high. On the other hand, quantized communication reduces the amount of data exchanged among workers, which leads to faster convergence with respect to wall clock time (Alistarh et al. 2017 Seide et al. 2014 Doan al., 2018 Zhang al. 2017 Wang et al. 2018). This is especially useful when the communication bandwidth is restricted.
At this point, natural question is: Can we apply quantized communication to decentralized training, and thus from both of them? Unfortunately, directly combining them together negatively affects the convergence rate (Tang et al.) 2018b). This happens because existing quantization techniques are mostly designed for centralized SGD, where workers communicate via exchanging gradients (Alistarh et al. 2017 Seide et al. 2014 Wangni al., 2018). Gradients are robust to quantization since they get smaller in magnitude near local optimum and in some sense carry less information, causing quantization error to approach zero (De Sa al. 2018). In contrast, decentralized workers are communicating model parameters, which do not necessarily approach zero, and so quantization error does not diminish unless precision is explicitly increased (Tang et al. 2018c). Previous work
A worker could refer to any computing unit that capable computing, communicating and has local memory such as CPU, GPU, or even a single thread, etc. "These approaches include low-precision, sparsification, and compression techniques more generally.

---

Under review as a conference paper at ICLR 2020
solved this problem by adding enror tracker to compensate quantization errors (Tang al. 2019
or adding replicas of neighboring models and focusing on quantizing model difference which does approach zero (Koloskova et al. 2019 Tang al.) 2018b). However, these methods suffer from trade-offs and limitations in that: (1) the extra replicas or error tracking incurs substantial memory overhead that is proportional model size (more details in Section 2): and (2) these methods
statistically restricted, in the sense that they are either limited to convex problems (Koloskova et al. 2019) or require unbiased or non-linear quantizers (Koloskova& et al. 2019 Tang al. 2018b; 2019).
To address these problems, in this paper we propose Moniqua, an extra-memory-free (details in Section 2 method for decentralized training to use quantized communication. Moniqua supports both biased and linear quantizers, as well as non-convex objectives.
Intuition behind Moniqua. In a communication step of decentralized training, a worker wi updates its model parameter mi by averaging with a neighboring worker w2 'y's model parameter m2: mi <- (mi + m2). Note that 1 2 [m² + m2) = my +
obtain 1/12- m (same logic for w2). Since 2 [m2 m1), so averaging is equivalent to letting w and m2 will approach the same local optimuum as the algorithm converges, we can expect the higher-order bits of mi and m2 to get close. Then we can save communication by having Wig not communicate those higher-order bits to w1- More explicitly, if we know that ||m= mm2lsso S 9 for some known parameter 9 (later we will show it can be derived in theory). then instead of sending the entire model m2 which might cause overhead, w2 can just send its j-th coordinate (mz), as (m2)j mod 0 (Vj E [d). Note that given [[m= m2ll S B:
(mz) mod 0- - (m1) mod 0 = ((mm)) (m²))) mod 0 = =mm2) (m2)
so w1 can obtain the j-th coordinate of m2 - m, by locally computing (mz) mod - (m1); mod with (mz); mod 0 received from W2. Since (m2); mod 0 is generally smaller number than (m2)j. u2 can send fewer bits with the same level of absolute error.
In this paper, we make the following contributions.
We show by example that directly quantizing communication in decentralized training, even with an unbiased quantizer, can fail to converge asymptotically, (Section 3
We propose Moniqua, general algorithm that uses modular arithmetic for communication quantization in decentralized training. We prove applying Moniqua achieves the same asymptotic convergence rate as the bascline full-precision algorithm (D-PSGD) while requiring at most (log log n) number of bits per parameter communicated, where n is the number of parallel workers. (Section 4
We apply Moniqua to decentralized algorithms with variance reduction and asynchronous communication (D2 and AD-PSGD) and prove Moniqua enjoys the same asymptotic rate as with full-precision communication when applied to these cases. (Section 5)
We empirically evaluate Moniqua and show it outperforms all the related algorithms given an identical quantizer. We also show Moniqua is scalable and robust to very low bit- budgets, and we introduce techniques found empirically useful to run Moniqua even more efficiently. (Section
2 RELATED WORK
Decentralized Stochastic Gradient Descent (SGD) Decentralized algorithms (Mokhtari and Ribeiro 2015; Sirb and Ye 2016 Lan et al. 2017 Wu et al. 2018a) have been widely studied with consideration of communication efficiency. privacy and scalability. In the domain of large- scale machine learning, D-PSGD was the first Decentralized SGD algorithm that enjoys the same asymptotic convergence rate ((IVKnn) (where K is the number of total iterations and n is the number of workers) as centralized algorithms (Lian et al. 2017a). After D-PSGD came D2, which improves D-PSGD and is applicable to the case where workers are not sampling from identical data sources (Tagg et al. 201 Another extension was AD-PSGD, which lets workers communicate asynchronously and has a convergence rate of O O(/VK)) (Lian et al. 2017b). In this paper we prove that Moniqua is applicable to all of these three algorithms. Other relevant work includes: [e ct al. 2018), which investigates decentralized learning on linear models; models:[Nazan Nazari all (2019). which introduces decentralized algorithms with online learning; Zhang and You You (2019). which analyzes the case when workers cannot mutually communicate; and Assran et al. (2018), which investigates Decentralized SGD specifically for deep learning.
2

---

Under review as a conference paper at ICLR 2020
Quantized Communication in Centralized SGD Prior research quantized communication is often focused on centralized algorithms, such as randomized quantization (Doan et al. 22018) Suresh
ct al.
2017: Zhang et al. 2017) and randomized sparsification (Wangni et a.. 2018]] Stich et al. 2018
Wang et al.
2018 Alistarh et al. 2018). Many examples of prior work focus on studying quantization
in the communication of deep learning tasks specifically (Han et al., 2015 Wen et al. 2017 Grubic iet al. 2018). [Alistarh et al. (2017) proposes QSGD, which uses an encoding-efficien scheme, and discusses its communication complexity. Another method, IbitSGD, quantizes exchanged gradients with one bit and shows great empirical success on speech recognition (Seide et al. 2014). Other work discusses the convergence rate under sparsified or quantized communication (Jiang and Agrawal
2018 [tich et al.) 2018). Acharya et al. (2019) theoretically analyzes sublinear communication for distributed training.
Quantized communication for decentralized algorithms is rising topic in the optimization community. Previous work has proposed decentralized algorithms with quantized communication for strongly convex objectives (Reisizadeh et al., 20188)
Quantized Communication in Decentralized SGD
Koloskova et al., 2019). Following that, Tang et al. (2018b) proposes DCD/ECD-PSGD. which quantizes communication via estimating model difference. Furthermore, Tang et al. (209)) proposes DeepSqueeze, which applies an proo-compensatton method (Wu et al. 2018b) to decentralized setting. From systems perspective, Koloskova et al. (2019) and Tang et al. (2018b) require O I)
and Tang et al. (2019) requires ((d) extra memory compared to D-PSGD to implement quantized communication, where d denotes the dimension of the model and I denotes the number of connections in the network. In comparison, Moniqua is Aitra-memory-free
SETTING AND NOTATION
In this section, introduce our notation and the general assumptions will make about the quantizers for our results to hold. Then we describe D-PSGD (Lian et al. (0177a), the basic algorithm for Decentralized SGD, and we show how naive quantization can fail in decentralized training.
Quantizers. Throughout this paper, we assume that we use quantizer 2s that has bounded error
[2(x)) =1100 S 8, Vx E [-1,
(I)
where 8 is some constant. In general, smaller å denotes more fine-grained quantization requiring more bits. For example, a biased linear quantizer can achieve (I) by rounding x to the nearest number in the set {28n n E 2 this will require about 8-1 quantization points to cover the interval |-1, 1). so such linear quantizer can satisfy (1) using only [log, (13 + 1) bits (Li et al. 2017 Gupta et al. 2015). Note that (T) can be satisfied (for appropriate values of 8) by both linear (Gupta et al.) 2015] De Sa et al. 2017) and non-linear (Stich 2018 Alistarh et al. (017)) quantizers, and thus it is more general than assumptions used in previous works where only non-linear quantizers are considered
(Koloskova et al. 2019 Tang et al.
2018c 2019).
Decentralized parallel SGD (D-PSGD). D-PSGD LLin et al. 2017a) is the first and most basic Decentralized SGD algorithm. In D-PSGD, n workers are connected to form a graph. Each worker stores copy of model æ e Rd and a local dataset D; and collaborates to optimize
1 n
min f(x) ZERd
f((x))
where & is data sample from D, In each iteration of D-PSGD, worker computes a local gradient sample using D.. Then averages its model parameters with its neighbors according to symmetric and doubly stochastic matrix W, where W.j denotes the ratio worker j averages from worker i. Formally: Let ø and ğk.; denote local model and sampled gradient on worker at k-th iteration, respectively. Let denote the step size. The update rule of D-PSGD can be expressed as:
Ik+1,1 = Σ DR. Wf agkkt = Ik,s
T ( ,, DK.)
-ggk.
(3)
gradient stop
communicate reduce difference
the update of single local model contains two parts: communication to reduce model difference and a gradient step. Lian et al. (2017a) shows that all local models in D-PSGD are able to reach the same stationary point.
From 3
3

---

Under review as a conference paper at ICLR 2020
Failure with direct quantization. Here, we illustrate why directly quantizing communication in decentralized training naively quantizing the exchanged data can fail to converge asymptotically a simple problem. This naive approach with quantizer 2s be represented by
Tk+1. = WH + Σ jzHt
25 (s(In)) -ggk,
(4)
Based on Equation 4 we obtain the following theorem.
Theorem For some constant 6, suppose that we use an unbiased linear quantizer with repre- 2 to learn on the quadratic objective function f(x)) = (x ((/2)/))6)_)) 6 x
sentable points {ōn 6/22/2 with the direct quantization approach 14). Let & denote the smallest value of non-zero entry in W. Regardless of what step size adopt, it will always hold for all iterations k and local
model indices that IE || (xrx,)))) B01+0r5. That is, the local iterates will fail to asymptotically
62-6²
converge to a region of small gradient magnitude in expectation.
MONIQUA
Theorem shows that when directly quantizing communication in decentralized SGD, even with an unbiased quantizer, any local model can fail to converge on a simple quadratic objective. In this seciton, propose technique, Moniqua, that solves this problem. Moniqua works under the following common assumptions for analyzing decentralized optimization algorithms (Lian et al. 2017a Tang al. 2018b Koloskova al. 2019).
(A1) Lipschitzian gradient. All the functions fi have L-Lipschitzian gradients.
V vf((v)ll - L||= yll, Vx, E gd
(A2) Spectral gap. The communication matrix W is symmetric doubly stochastic matrix and max([A2(W))) [W))] = < 1, where (W)) denotes the ith eigenvalue of W.
(A3) Bounded variance. There exist non-negative and such that
EqWND [(( -V(00] s
BM((I.)))) [V - vf(()) s²
where V fa(;; &.) denotes gradient sample on worker computed via data sample &,. (A4) Initialization. All the local models are initialized by the same weight: Zo,; No. for all and without loss of generality zo 0.
(A5) Bounded gradient magnitude. The norm of sampled gradient bounded by 1l S Go for all and i with some constant G.e.
In Section [ we described how a modulo operation can be used to avoid sending redundant bits if a bound 0 on model difference is known. Here outline how we can obtain such bound. We do so by leveraging the following insight: decentralized training, all the workers initialize local models same point and average with each other periodically. The only difference among their models is caused by the sampled gradients (updated with the step size), and this difference reduced each time they communicate. Since have upper bound on the magnitude of the gradients (A5) well as a bound characterizing how quickly the communication process converges (A2), we can combine these to get an priori bound 6 on how much the models can differ. We can then pass this bound
as parameter to the algorithm, which can proceed to modulo-quantize the communication via the process described in Section We formalize this approach as Moniqua (Algorithm)
Algorithm 1 Pseudo-code of Moniqua worker
Input:
initial point Zo.; Tg. step size a, the priori bound 0, communication matrix W, number of iterations K, quantizer Q5 neighbor list.N
for & 0, 2. K do
2: Compute a local stochastic gradient G.. with data sample Ev.; and current weight ææ,i
3: Compute modulo-ed model: (k,i <- 0 Q8 ( mod 1) (element-wise division and mod)
4: Average with neighboring workers: I&+ f- Ihii + >jEN, (gk.j - W
5: Update the local weight with local gradient: F2+1,6 f- Tet orkkt
6: end for
Output: Averaged model Xx 1E DKK
4

---

Under review as a conference paper at ICLR 2020
In line 3 we rescale each coordinate that the number to be quantized falls in the region of [-1, 1], which is required for ( to apply. Note that with quantization, the priori bound could increase since local models may move further apart due quantization enror. However, with appropriately chosen 5, we can still obtain a bound and apply modulo-quantized communication that allows Moniqua to converge. We present these parameter choices in Theorem 2 along with the resulting convergence rate for Moniqua.
Theorem If we run Algorithm 7 in setting where
0 = 2 log aG
1-p
1
1-p
and converges at the asymptotic rate
4log(16n))
a
2//3 + K/n +
then the output of Algorithm
K-1
53
pºn o²K +n o
Σ
E
K
Vnk
K
where p. f(0)- - f and L are omitted as constants. Consistent with D-PSGD. Note that D-PSGD converges the asymptotic rate of Ola/Vnt <$ K )), and thus Moniqua has the same asymptotic rate D-PSGD (Lian al. 2017ap. In other words, the asymptotic convergence rate is not negatively impacted by the quantization.
Robust to large In Assumptions (A3) and (A5) we use 12-norm and -nom to bound sample variance and gradient magnitude, respectively. Note that, when d gets larger, the variance o² will also grow proportionally. So, the last term will tend to remain n K asymptotically with large d.
How many bits does Moniqua need? The specific number of bits required by Moniqua depends on the underlying quantizer (Qs). If we use nearest rounding (Gupta et al. 2013) as 2s in Theorem suffices to use each step a number of bits B for each parameter sent, where
B log2 (3 + 1)] logg ( (1
(162))) +1)]
Note that this bound is independent of model dimension d. When the system scales up, the number of required bits grows rate of O (log log
5 SCALABLE MONIQUA
Previous work has extended D-PSGD to D (Tng al., 2018a) (to make Decentralized SGD applicable to workers sampling from different data sources) and AD-PSGD (Lian et al. (01 (an asynchronous version of D-PSGD). this section, we theoretically prove Moniqua is applicable to both of these algorithms.
Moniqua with Decentralized Data Decentralized data refers to the case where all the local datasets D; are not identically distributed (Tang et al., 2018a). More explicitly, the outer variance [((z) V f (z)]² is no longer bounded by s² as assumed in D-PSGD (Assump- This update rule presented can be explicitly expressed in two steps
E 1.... m]
tion (A3)
X =2Xx -x-1- - aGxx
- + atx-1
X X W + (Q: Xx+z)
where Xt. Gp and Qk matrix in the shape of pdx", where their i-th column TR,i S and Ik.s respectively. And X-1 and G_ are gdxn by convention. Based on this, we obtain the following convergence theorem.
Theorem we run D2 with Monqiua a setting where
0 = (6 + 8)
8
6n and
a
o K/K/n 2L
where Di and D2 are two constants that only depend the eigenvalues of W (definition can be found in supplementary material), the output has the following asymptotic convergence rate:
K-1
Σ R=O
a Vnk
o2n
Gd dn
+ o2K
K
o2 +n
Detailed pseudo-code in the supplementary material.
5

---

Under review as a conference paper at ICLR 2020
Note that D Tang al. 2018a) with full full-precision communication has the asymptotic convergence rate of O (1/K + o/vnk + t/ Moniqua on D2 has the same asymptotic rate.
Moniqua with Asychronous Communication. Both D-PSGD and D are synchronous algorithms they require global synchronization the end of each iteration, which become bottleneck when such synchronization is not cheap. Another algorithm, AD-PSGD, avoids this overhead by letting workers communicate asynchronously (Lian al., 2017b). In the analysis of AD-PSGD, an eration represents a single gradient update on one randomly-chose worker, rather than a synchronous bulk update of all the workers. This single woorker-update analysis models the asynchronous nature of the algorithm. We apply Moniqua to AD-PSGD and obtain the following update rulc
xx+1 W + (Qx (W -GG
where Wi describes the communication behaviour between the ktth and (k + 1 1)th gradient update, and Ty denotes the delay (measured as a number of iterations) between when the gradient is computed and updated to the model. Note that unlike D D-PSGD, here Wa can be different at each update step and usually each individually has P = 1, so we can't 't expect to get a bound terms of bound on the Instead, we require the following condition, which is inspired by the literature on Markov chain Monte Carlo methods: for some constant fmix.
spectral gap, as we did in Theorems 2 and B
Vμ R", AK E N, if p4 2 and 1 μ L, it must hold that [[TT fiii Wa+1 1
We call this constant mix because it is effectively the mixing time of the time-inhomogeneous Markov chain with transition probability matrix Wa at time & (Levin and Peres] (017). Note that this condition more general than those used in previous work on AD-PSGD because it does not require that the Wa are sampled independently or in an unbiased manner. Using this, we obtain the following convergence theorem.
Theorem 4 If we run AD-PSGD with Moniqua in setting where
and
a 2L + (K + +62)
32imix
the oulput has the following asymptolic convergence rate:
K-1
Σ k=
1 x K
2
+ (o2 + C
mix n?
n2 mixx Good
K
VK
(02 65
+1
2 + 6 K K1
Note that AD-PGG (Lian al. 2017b) with full-precision communication has the asymptotic
convergence rate of O (1/K vo² 6x2 //K n²/ 12/K). Moniqua converges at the same rate.
EXPERIMENTS
In this section, evaluate Moniqua empirically. First, compare Moniqua and other quantized decentralized training algorithms' convergence under different network configurations. Second, we evaluate Moniqua's scalability D2 and AD-PSGD. Third, we introduce two additional techniques to run Moniqua more efficiently and empirically investigate the limits of Moniqua.
Configuration. All the models and training scripts in this section are implemented in PyTorch and run on Google Cloud Platform. We launch an instance as one worker, each configured with a 2-core CPU with 4 GB memory and an NVIDIA Tesla P100 GPU. We use MPICH as the communication backend. All the instances are rumning Ubuntu 16.04, and latency and bandwidth on the underlying network are configured using the t c command in Linux. all the experiments, we use the following
hyperparameters by default: batch size 128, weight decay = 1e -4, 4, and momentum = 0.9, which are default values adopted in previous works (Lian et al. [0176] Grubic al. 2018).. We tune the step size from set (0.5. 0.1. 0.05..0.... 0.01) for each algorithm. Throughout our experiments, we adopt the commonly used Gupta et al. 2015 Li et al. 2017) stochastic rounding with quantization step
Details in the supplementary material.
"Since several baselines are not applicable to biased quantizers, for fair comparison we consistently use stochastic rounding (unbiased). More experiments using different quantizers including biased and non-linear quantizers Moniqua can be found in supplementary material.

---

Under review as a conference paper at ICLR 2020
2.0
Trakiin LONK
Tolnine
1.20
6.0
Reach
156
03
Tieee))
Wieed
1630
1300
Flaee0)
(a) Training Loss vs Epoch (b) Bandwidth1100Mtp (c) 200bs,,,
(d) Bandwidth= 100Mbss
Latency=0.15mm
Latency=0.15mm
Latency=10ms
Figure I: Performance of different algorithms under different network configurations
Trassin
Spach
200
156
33
Spech
103
253
33
136"
26
Epech
153
(a) 3-Bit Training Loss
(b) 2-Bit Training Loss
(c) 3-Bit Test Accuracy
(d) 2-Bit Test Accuracy
Figure 2: Performance of Moniqua and other quantization algorithms under extreme bit-budget.
Wall-clock Time Evaluation. We start by evaluating the performance of Moniqua and other baseline algorithms under different network configurations. We launch 8 workers connected in a ring topology and train ResNetl 10 (He et al. (016) model on CIFAR10 10 (Krizhevsky et al. 2014). We compare Moniqua with the following baselines Centralized (implemented as a standard AllReduce (Tang
operation), D-PSGD (Lian et al. (017a) with full precision communication, DCD/ECD-
ctt al. 2018b), ChocoSGD (Koloskova et al. 2019) and DeepSqueeze (Tang et al. 2019). We set
ő 0.01 for stochastic rounding across all algorithms that use quantization. To prevent overflow, use 16-bit integers toreitoorccc. torch. intl6 6 as the floored output on the sender side. For Moniqua, we set 0 = 3.0.
We plot our results in Figure As can be seen in Figure I(a] with respect to epochs, All the algorithms have similar convergence curve while DCD/ECI-PSGDD have slightly slower convergence curves. We can see from Figures [ and [(c] that when the network bandwidth decreases, the curves begin to separate. AllReduce and full- aill-precison D-PSGD suffer the most, since they require a large volume of nigh-ppreiiioo exchanged data, And from Figure [(b) to Figure [(d) when the
network latency increases, we observe similar behavior. On the other hand, from Figure [(b) to
Figure [(c) and Figure [(d] curves of all the quantized baselines (DCD/ECD
ChocoSGD
and DeepSqueeze) are getting closer to Moniqua. This is because, as shown in Figure [(b] the extra updating of the replicas in DCD/ECD-PSGD and ChocoSGD as well as the error tracking in DeepSqueeze counteract the benefits from accelerated communication. However, when network bandwidth decreases or latency increases, communication becomes the bottleneck and allow these algorithms obtain acceleration compared to centralized SGD and D-PSGD. Delay between Moniqua and quantized baselines does not vary with the network since that only depends on the their extra local computation (error tracking and replica update). We observe that compared to Moniqua, DCD/ECD- PSGD is approximately 13 seconds slower while ChocoSGD and DeepSqueeze being 10 and 8 seconds slower repectively. From Figure we can see that Moniqua outperforms all these other algorithms.
Aggressive Quantization. Now we investigate how Moniqua and baselines behave under aggressive quantization. We enforce two strict bit-budget: 2bit and 3bit (per parameter). We plot the results in Figure 2 We can see that DCD-PSGD fails to converge in both cases and ECD-PSGD fails to converge with 2bit. This is consistent with results in previous work (Tang et al. 2018c 2019). On the other hand, Moniqua converges faster than any other baselines. We observe at the end of 150 epoch,
6 'ttee algorithms are not applicable to non-convex DNN problems, so we are not comparing them here. "Since we measuring the system performance, the specifie number of bits is not the focus here. In later section we will discuss statistical performance with small number of bits.
7

---

Under review as a conference paper at ICLR 2020
Traiiin Coua
Meniquats -03
Neniquaté-o 081
Neriquats 11)
Noriquati 25)
Meriquals
Noriquati
2333
25
53
15
100
125
40
Epach
201
(a) Training Loss (Decentralized Data)
(b) Training Loss (Asynchronous Communi- cation)
(a) Training Loss (VGG16)
(b) Training Loss
(ResNetl
Figure 4: Performance of Moniqua on VGG16 and Figure 3: Performance of applying Moniqua on ResNetl 10 under different 0
D and AD-PSGD
with 3-bit communication Moniqua achieves 85% training accuracy while other baselines are below 70% (full precision achieves 97%). Compared to the theoretical results in Section we show that
Moniqua is much more robust to low-bits budget in practice.
Scalability of Moniqua. We evaluate how Moniqua can be applied to D (Tagg et al. 2018a) and AD-PSGD (Lian et al. 2017b). First, we demonstrate how applying Moniqua D can handle decentralized data. We launch 10 workers, collaborating to train a VGG16 (Simonyan and Zisserman 2014) model on CIFARIO. 10. Similar to the setting of D Tang al. 2018a), we let each worker have exclusive access to 1 labels (of the 10 labels total in CIFARTO), In this way. the data variance among workers is maximized. We plot the results Figure ((a) We observe that applying Moniqua on D2 does not affect the convergence rate while D-PSGD can no longer converge because of the outer variance. Here we omit the wall clock time comparison since the communication volume the same in comparison of Moniqua and Centralized algorithm in Figure [
Next, we evaluate Moniqua on AD-PSGD. We launch 6 workers organized in a ring topology, collaborating to train ResNetl 10 model on CIFARIO. We set the network bandwidth to be 20Mbps and latency to be 0.15ms. We plot the results in Figure 3(b] We can see that both AD-PSGD and asynchronous Moniqua outperform D-PSGD. Besides, Moniqua outperforms AD-PSGD in that communication is reduced, which is aligned with the intuition and theory.
Efficient Moniqua. There are two techniques have observed to improve the performance of Moniqua when using stochastic rounding: (x(x) = 5 - + uJ (where u is uniformly sampled from [0, 1)). Vz E Rd. The first is to use shared randomness, in which the same random seed is used for stochastic rounding on all the workers. That is, if two workers are exchanging tensors r and y respectively, then the floored tensors 1 + u and / uI they send use the same randomly sampled value u. This provably reduces the error due to quantization (more details are the supplementary material). The second technique is use standard entropy compressor like bzip to further compress the communicated tensors. This can help further reduce the number of bits because the modulo operation in Moniqua can introduce some redundancy in the higher-order bits, which traditional compression algorithm can easily remove.
To evaluate these methods, train both ResNetl 10 and VGG16 CIFAR10 using 8 ring- connected workers. We plot the training loss under different 9 in Figure (with 8 = 0.01 for stochastic rounding). Note that for VGG16, the other hand, for ResNetl 10, begins to diverge when 0 decreases to 0.5. This is because VGG16 has more fully connected layers than ResNetl 10, and these layers are less sensitive to quantization, as claimed in (Grubic et al., 2018). We observed that the fewest number of bits per number needed to communicate by Moniqua for VGG16 and ResNetl to guarantee convergence (aceuracy loss < 0.3%, criterion adopted by (Grubic et al. 2018) ) are 3.64 and 5.67, respectively (details in the supplementary material).
tolerate small 0.08 while still preserving the convergence rate. On
7 CONCLUSIONS
In this paper we propose Moniqua, a simple unified method of quantizing the communication in decentralized training algorithms. Theoretically, Moniqua supports biased quantizer and non-convex problems, while enjoying the same asymptotic convergence rate as full-precision wil-pprcioocccommmeeee communication algorithms without incurring storage computation overhead. Empirically, we observe Moniqua
8

---

Under review as a conference paper at ICLR 2020
converges faster than other related algorithms with respect to wall clock time. Additionally, Moniqua is robust to very low bits-budget.
REFERENCES
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the twenty-first international conference on Machine learning, page 116. ACM, 2004.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pages 177-186. Springer, 2010.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang. Quoe V Le, et al. Large scale distributed deep networks. In Advances in neural information processing systems, pages 1223-1231, 2012.
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 1 hour. arXiv preprint
2017.
Dan Alistarh. A brief tutorial on distributed and concurrent machine learning. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 487-488. ACM, 2018
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, al. Tensorflow: system for large-scale machine learning. In OSDI, volume 16, pages 265-283, 2016.
Frank Seide and Amit Agarwal. Cntk: Microsoft's open-source deep-learning toolkit. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2135-2135. ACM, 2016.
Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang. Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv preprint 1XXi::55/2.0122: 2015.
Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In OSDI, volume 14, pages 583-598, 2014a.
Mu Li, David Andersen, Alexander J Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. In Advances in Neural Information Processing Systems, pages 19-27, 2014b.
William Gropp, Rajeev Thakur, and Ewing Lusk. Using MPI-2: Advanced features of the message passing interface. MIT press, 1999.
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 Advances Neural Information Processing Systems, pages 5330-5340, 2017 7a.
Xiangru Lian, Wei Zhang, Ce Zhang, and Liu. Asynchronous decentralized parallel stochastic gradient descent. arXiv preprint arXiv: 1710.0695, 2017b.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. arXiv preprint arXiv:I803 180300068, 2018a.
Hadrien Hendrikx, Laurent Massoulié, and Francis Bach. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. arXiv preprint arXiv: 1 0200660, 2018.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference Machine Learning, pages 4035-4043, 2017.

---

Under review as a conference paper at ICLR 2020
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In Advances Neural Information Processing Systems, pages 1709-17200 2017.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems, pages 1509-1519, 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Thinh T' Doan, Siva Theja Maguluri, and Justin Romberg. On the convergence of distributed subgra- dient methods under quantization. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 567-574. IEEE, 2018.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: conmuuicationnefficiin learning via atomic sparsification. In Advances in Neural Information Processing Systems, pages 9850-9861, 2018.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. In Advances in Neural Information Processing Systems, pages 7663-7673, 2018b.
Jianqiao Wangni, Jialei Wang, Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems, pages 1306-1316, 2018.
Christopher De Sa, Megan Leszczynski, Jian Zhang, Alana Marzoev, Christopher R Aberger, Kunle Olukotun, and Christopher Ré. High-accuracy low-precision training. arXiv preprint arXiv:1803.03383, 2018.
Hanlin Tang, Chen Yu, Cedric Renggli, Simon Kassing, Ankit Singla, Dan Alistarh, Ji Liu, and Ce Zhang. Distributed learning over unreliable networks. arXiv preprint arXiv:1810.07766 2018c.
Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu. Deepsqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. arXiv preprint wr.Xiv:1907.072. 2019.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. arXiv preprint arXiv:1902.003:4 0009000000000 2019.
Aryan Mokhtari and Alejandro Ribeiro. Decentralized double stochastic averaging gradient. In Signals, Systems and Computers, 2015 49th Asilomar Conference on, pages 406-410. IEEE, 2015.
Benjamin Sirb and Xiaojing Ye. Consensus optimization with delayed and stochastic gradients on decentralized networks. In Big Data (Big Data), 2016 IEEE International Conference on, pages 76-85. IEEE, 2016.
Guanghui Lan, Soomin Lee, and Yi Zhou. Communication-effccieen algorithms for decentralized and stochastic optimization. arXiv preprint arXiv: 2017.
Tianyu Wu, Kun Yuan, Qing Ling, Wotao Yin, and Ali H Sayed. Decentralized consensus optimization with asynchrony and delays. IEEE Transactions Signal and Information Processing Networks, 4(2):293-307, 2018a.
Lie He, An Bian, and Martin Jaggi. Cola: Decentralized linear learning. In Advances in Neural Information Processing Systems, pages 4541-4551, 2018
Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Dadam: A consensus-baue based distributed adaptive gradient method for online optimization. arXiv preprint arXiv: 09109, 2019.
10

---

Under review as a conference paper at ICLR 2020
Jiaqi Zhang and Keyou You. Asynchronous decentralized optimization in directed networks. arXiv preprint MXXiv11901.0221:. 2019.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. arXiv preprint 1tXiv:/811..0111 2018.
Ananda Theertha Suresh, Felix X Yu, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Volume 70, pages
Machine Learning- Searning-Volume
JMLR. org, 2017.
Sebastian U Stich, Jean- -anntttttstt Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pages 1452-446,, 2018
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric
Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pages 5973-5983, 2018.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding, arXiv preprint 1r 2015.
D Grubic, L Tam. Dan Alistarh, and Ce Zhang. Synchronous multi-gpu deep learning with low- precision communication: An experimental study. Proceedings of the EDBT 2018, 2018.
Peng Jiang and Gagan Agrawal. linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems, pages 2525-2538 2018
Jayadev Acharya, Christopher De Sa, Dylan Foster, and Karthik Sridharan. Distributed learning with sublinear communication. arXiv preprint 19X2:: 1129,, 2019.
Amirhossein Reisizadeh, Aryan Mokhtari, S. Hamed Hassani, and Ramtin Pedarsani. Quantized decentralized consensus optimization. CoRR, abs/1806. 11536, 2018. URL http:://axix: org//bb////// /80.. 11536
Jaaxiang Wu, Weidong Huang. Junzhou Huang, and Tong Zhang. Error compensated quantized sgd and its applications to large-scale distributed optimization. arXiv preprint arXiv:1806.0803: 180.00054, 2018b.
Hao Li. Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. In Advances in Neural Information Processing Systems, pages 5811-5821, 2017.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International Conference on Machine Learning, pages 1737-1746, 2015.
Christopher De Sa, Matthew Feldman, Christopher Ré, and Kunle Olukotun. Understanding and optimizing asynchronous low-precision stochastic gradient descent. In ACM SIGARCH Computer Architecture News, volume 45, pages 561-574. ACM, 2017.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint a 2018.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. online: http://www. cs. toronto. edu/kriz/cifar huml, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.

---

Under review as a conference paper at ICLR 2020
Supplementary Material
A OVERVIEW
This supplementary material contains proofs of all the theoretical results and extra experimental results of Moniqua. It is organized as follows: In Section[B, [B we provably explain why using shared randomness communication with stochastic rounding can improve performance (theoretical expla- nation for technique 1 in Experiment Efficcintt Moniqua). Then we demonstrate more experimental results in Section C Section D we illustrate why naively quantizing communication in D-PSGI) In Section B we introduce some useful tools of modeling communication as Markov Chain for the rest of the proof (part of the intuition is illustrated in the paper). We recommend to go through this before getting into Section F to H Finally we will provide proof to Theorem and from Section to
fails to converge asymptotically, as proof to Theorem [
Fo H with corollaries contained in the corresponding sections. Detailed algorithm statements for applying Moniqua on D and AD-PSGD can be found in Section Algorithm and Section H Algorithm respectively.
B SHARED RANDOMNESS (EXPERIMENT OF Efficient Moniqua)
In this section, we provide a theoretical explanation why using shared randomness in the stochastic rounding is able to improve the performance. Without the loss of generality, in the following analysis, we let the quantization step associated with stochastic rounding quantizer Q be = 1. For any quantized using 2, let 2 2 [=], the variance of quantization error can be expressed
E [()) - =1| (1 2-) + 2,(1 2,)² =, 22)
(5)
Note that in Moniqua, the term asssociate with quantization error is
E [1 -kks) (gh.s =x,1)l1
We now show for Va,, Rd
E (1(((z) - 2) (Q(y) - r)1l = 11 - x) - (g - x)1
With out the loss of generality, let [x]] S y [y| Let By
| and ys y [y]. then
c + ul = [ and
ly + u = |y], with probability
[v]
[
[x]] and
ly u [y] with probability
x [x]]
[ + ul = [o]] and
[y + m yl with probability
([x] - x) - -([y] -2)
Then we have
[1(((()) - (Q(v) - 1)
-E (8 [ +u - =) (6 y
[6L + -v
-(Tv] - ()(([=] - x) ([v]-)))² + +(x (===<=())(([]] -x) x) - ([y] v))²
[=])([[x]
+[[==] -x) - -[v] ()((( - x) ([yl y))²
=(1 11--/ -M/)(=; - -y) (xy)(E5- - -yr) + (vs zy)(ys - 2z 1)²
=(1 // + = x,)²² + (Ur 2 Iz - 1)²
-(1 8// + +,)(())) xz)
E 112 .²) (y - 2:)1
The last equality holds due to equation 5 Next, let
= y x
r ((A)
And let Th denote h-th entry of r, let A denote /-th entry of A. We obtain
Fh -((() A
12

---

Under review as a conference paper at ICLR 2020
A A
+1
Pt S _
1
A1
otherwise
+
1,
Pt S
9:
otherwise
where
A
A
9
19 [0.1]
6
8
Based on that, we have
[ ( + 1)3g (-1) 4))
=6 - 9)
< min (q, 1 /}
Since min(g, 1 - 9} S Za we have
Ah
E [ - 82
S 5dAnN
Summing over the index h yields,
E | 2 < 8E |||| 3 vd&E |
Pushing back and r, we have
E Q x) - (y =)1l - doE 11y 211 vddE | y/1
Putting it back we have
E (1()))) x) (2(x) -) VdoTE |
yll
Now we can see that the error term is bounded by the distance of two quantized tensor, which, in decentralized training, refers to the distance between models on adjacent workers. In such way, the error bound can be reduced since the workers are getting close to each other.
C MORE EXPERIMENTAL RESULTS
C.1 COMPUTE NUMBER OF BITS
In Experiment of Efficient Moniqua, calculate the number of bits in the following way: First, we calculate the total number of bits each worker send out, sum them up and divided by number of epochs, and we get the average bandwidth consumption BW of the whole system in each epoch. Then we compute the number of bits required for each number in the following way (note that every worker has 2 neighbors in ring topology):
BW
#bits #neighbors #workers #params of model
In our experiments, #neighbors=2, #workers=8. For VGGI6, #params of model= 15.245,130 while for 10, #params of 146.4 We formalize the results in Table C.I
C.2 VARIOUS QUANTIZERS
In this section, we will verify Moniqua is applicable to other quantizers aside from linear quantizer as shown in the paper. We test it on two more quantizers:
1. Nearest Rounding (Biased)
I + 0.5 (xx) = [
where 5 is the quantization step as defined in the linear quantizer. In this experiment, we set 8 0.01, the same value as we used in the paper with stochastic rounding.
Note that only put results that's "close the limit of Moniqua' here
13

---

Under review as a conference paper at ICLR 2020
Table 1: Wall Clock Time consumption (Seconds)/Epoch in average under different network in Experiment of Evaluation of Moniqua.
100mbps/0.1500 15mm
20mbps/0.15mm
100mbps/10ms
Extra Memory
Centralized
38.92
206.14
343.28
N/A
D-PSGD
36.25
189.48
310.98
N/A
DCD-PSGD
32.99
105.40
202.42
20.4 MB
ECD-PSGD 31.96
105.26
202.04
20.4 MB
ChocoSGD
32.03
105.18
201.18
20.4 MB
DeepSqueeze
30.01
103.67
193.92
13.6 MB
Moniqua
22.42
95.08
184.86
0 B
Table 2: Bandwidth consumption under different 0 and ó when applying linear quantizer in Moniqua
MODEL
MOD PARAM 0
QUANT STEP
BYTES/EPOCH
AvG Brts
NONE
NONE
45594MB
32
VGG16
1.0
0.01
5206MB
3.65
0.08
0.01
5192MB
3.64
NONE
NONE
3430MB
RESNET 10
2.0
0.01
609MB
5.67
1.3
0.01
608MB
5.67
2. Randomized Gossip (Non-linear)
((x) = -fx x with probability
0,
with probability
1 -
In this experiment, we set p 0.7.
We train ResNetl on CIFARIO, and plot the results in Figure 5(c) We can see that the training curves of using three quantizers are all aligned with D-PSGD with full-pne precision communication. Note that in the paper we show that previous work cannot perserve the aligned curve even with stochastic rounding (unbiased), thus we are not comparing them here.
C.3 MORE RESULTS ON DIFFERENT HYPERPARAMETERS
In this experiment, we plot result of training ResNetl 10 and VGG16 CIFAR10 under different 8 and in the experiment of aggressive quantization. And we plot the results in Figure ((a) and Figure 5(b)
D-PSGD
D-PSGD
D-PSGD
Training Loss
Moniqua(5 0.05, 8-2.0)
Moniqua(8-008 0-000
Moniqua(a-
Training Loss
2.5
2.0
Moniqualo
Moniquatd - -000,, 2.20)
Moniqueld-Oo -00000000000000..0000
Training Loos
Randomized Gossip
Stochastic dounding
Rounding
Moniqua(6= 0.01, 8 0.004)
Moniquatd = 0.01, 0.4)
L.0
1.0
0.5
0.5
100
0.0
0.0
Epoch
Epach
Epoch
(a) Performance of Moniqua on (b) Performance of Moniqua on (c) Performance of algorithms un-
VGG16 under different 0 and 8 ResNetl under different 0 and der different quantizer
8
14

---

Under review as a conference paper at ICLR 2020
C.4 PERFORMANCE ON THE TESTSET UNDER AGGRESSIVE QUANTIZATION
We report the results in experiment of Aggressive Quantization" and report the test error and test accuracy in the Figure 3 and Figure 6
D-PSGD
D-PAGD RCD PSGROW
D-PSGD
Training Accuracy
1000
ECD PECDERARI
Decefroworel of (an)
ChoceSRDUAaR)
Test Accuracy
60
80
ChocaSeg1
(
Twast Lass
0,015
ChocassoLAai
RCD PSERUTMM
80.000
40
20
0.005
50
100
150
50
100
150
50
100
150
Epoch
Epoch
Epoch
(d) Training Accuracy under differ- (e) Test Accuracy under different (1) Test Loss under different algo- ent algorithms with 3-bit communi- algorithms with 3-bit communica- rithms with 3-bit communication cation
tion
Figure 5: More statistics from Experiment of Aggressive Quantization under 3-bit communication
Training Accuracy
100
DCD 29 2011
-0
DCB PSD-P50922
0.020
BCD KCD-PSDDDARI
ICD (36024011111
80
Test Accuracy
60
Mariquarda)) da1)
Teat Lawe
10.015
MaxiquatZkii
30
10.010
20-
0.005
50
Epoch
Epoch
Epoch
(a) Training Accuracy under differ- (b) Test Accuracy under different (c) Test Loss under different algo- ent algorithms with 2-bit communi- algorithms with 2-bit communica- rithms with 2-bit communication cation
tion
Figure 6: More statistics from Experiment of Aggressive Quantization under 2-bit communication
C.5 DECREASING STEP SIZE AND CONSENSUS ERROR
In this subsection, we provide more experimental results with decreasing step size. We also provide and discuss results on consensus error in this experiment. We run the experiments in the following setting:
Models, Datasets and Hyperparameters. We launch 8 workers connected using a ring network. We train ResNetl 10 and ResNet18 on CIFAR10. The hyperparameters of Moniqua are: ResNetl 10 (Initial step size = 0.05, 0 3.0, batch size = 128, weight decay- 3e 4, and momentum 0.9) and ResNet18 (Initial step size 0.1, 0 2.5, batch size = 128, weight decay = le - 4, and momentum 0.9). Step size is decreased (times a 0.1 factor) every 30 epochs. To be consistent with the original paper, we use the stochastic rounding to quantize each number.
Results of Decreasing Step Size We plot the results of test accuracy in Figure We can see from Figure ( that Moniqua requires at least 6 bits to achieve the comparable (accuracy drop < 0.3%) test accuracy as the baseline (D-PSGD with 32 bits). Once the numeber bits decrease to 5, there is accuracy gap between Moniqua and D-PSGD. On the other hand, other baselines including DeepSqueeze, ChocoSGD and DCD/ECD-PSGD are not able to achieve comparable test accuracy with 6 bits. Similarily, we can see from Figure 7(b) that when training ResNet18 8 with 4 bits, Moniqua is able to achieve comparable test accuracy after 120 epochs, while other baselines suffer a certain accuracy gap.
We also plot the test accuracy of different algorithms under different bit-level communication in Figure 8 (ResNetl 10). We can see that compared the baselines, Moniqua is generally robust to low
15

---

Under review as a conference paper at ICLR 2020
90
90
Test Accuracy
80
Test Accuracy
80
D-PSGD(32bit)
70
D-PSGD(32bRt)
70
Moniqua(Bbit)
Moniqua(Bbit)
Moniqua((bit)
60
Moniqua(Ebiti
6.0
Moniqua(Sbit)
Moniqua(
ChocoSGD(Ebit)
50
ChocoSGD(4bit)
50
SeepSqueeze
Deapqquaza(4brt)
ECD-PSGD(SbiR)
ECD-PSGD(4bit)
DCD-PSGD(ebit)
40
DCD-PSGD(abit)
40
25
75
100
125
150
25
75
100
125
150
Epoch
Epoch
(a) ResNetL on CIFARIO
(b) ResNet18 on CIFARIO
Figure 7: Test Accuracy and Consensus Error of Moniqua under decreasing step size.
Test Accuracy
80
60
D-PSGD
DCD-P5GD
ECD-PSGD
ChocoSGD
40
DeepSqueeze
Moniqua
2
3
4
5
7
8
Number of Bits/Parameter
Figure 8: Test Accuracy of different algorithms on training ResNetl 10 on CIFARIO.
bits-budget. (Some of the dots missing for some algorithms, that means they do not converge under the corresponding bidg-budget.)
Results of Consensus Error. To better measure the behaviour of workers reaching consensus, define the consensus error at iteration k: Cj as follows (Notations are the same as in the original paper):
C₁ = nk t=0
Ft.j
(6)
Note that Cş is essentially the running average of distance among workers and the averaged model. Trivially, decreasing C₁ indicates the workers reaching consensus. We measure the consensus error in three aspects. We first provide the results of the original paper in Figure (a) where constant step size is adopted. We can that even with extremely small number of bits as used in "Aggressive Quantization", all the workers are able to reach consensus. We further plot consensus error under the setting where decreasing step size is adopted as defined in this section. We in Figure 9() and Figure ((c) that all the workers are able to reach consensus.
16

---

Under review as a conference paper at ICLR 2020
Montowe Beigg Mariqua 2010
50
D-P560122811 Neskquat66i) Mesk
P5500 Moxiquatten)
Consenaus Ereor
Consentt Consemsii Erros
-0
Meniquedtinn
750
20
20
500
70
0
50
300
150
200
0
25
50
75
100
125
150
25
50
75
300
125
150
Epoch
Epoch
Epoch
(a) Consensus Error on ResNetl 10 (b) Consensus Error on ResNetl 10 (c) Consensus Error on ResNet18 with decreasing step size
with constant step size
with decreasing step size
Figure 9: Consensus Error of Moniqua with different number of bits.
D WHY NAIVE QUANTIZATION FAILS IN D-PSGD (PROOF TO THEOREM
The update rule of naive quantization D-PSGD is
Fe+1. The Wi:
((r,)) ozğk. Tk,i +
(Q(*k)) - FR,: O..
j=1
where or allowed vary with any policy. Let
Xx
[K,11
(Zkkl E Rdxx
Q4
Σ W5 (Q(Iks) -
Σ 87n
Win (Q(xk.) Ikr)
E Rdxn
j+1
G I.. n Rdxa
by rewritting the update rule, obtain
X++1 = Xx + S2 GgGr
Let Y2 X2 I,, and considering the fact that ff(x) x -8/22 xx, we can rewrite the update rule as
Y441;; Yge; S44 ogybe an (āx - Gkz) -Gk) c
where (āx (Gx) denotes variance in the gradient sampling.
Suppose that by using the update rule of naive quantization, worker converges to x". Then there must exist a K such that vk 2 K,
628²
E B| < ||Yeesl|
8(1 + Ø2)
Next we show that this assumption lets us derive a contradiction. Firstly, considering the property of linear quantizer,
8²
< E Q((x.)) - 201 < 2E ((
x2,Ill 2E I x²1
4
As result
8²
8²
8² 8(1 + 02)
E B
2b,1|
8
8(1 + 62)
Since Q is unbiased, that means [[Q(x) - x] = 0, then we have
E |
17

---

Under review as a conference paper at ICLR 2020
=E
Σ Wse (Q(I).)) - 2k.i)
W (1(())))))))))))))))))((((())( - rx.i)
Σ ((( -RR,) Wmi, (Q(Ik,n) xk.e) Wme)
JEN
minti
E [I(((()k)) -I,NIl
Σ
E ((Q( Ikis) W (Q( Ikii) Wii)
jEM:
melnpii
(II(( - 22
JEM
0²62
8(1 + x2)
where step (x) holds due to unbiased quantizer. Putting it back to the update rule, we obtain
1 =IE Yx + S2 - au.Y + ax GGx - -G&) es
( E [I(1 - ax) BBl [[000
E an GGx
G$ ez 2
E 1[xeell*
6²8²
8(1 + 62)
where cross terms in the (+) step are all 0 due to the unbiased quantizer and unbiased sampling of the
gradient. Her we obtain the contradictory that 62 said, for Vk,
8(+67)) I | - x=1
62 28
That being
8 311+09 0
Φ282
E
- - (V
8(1+
Thus we complete the proof.
E A MARKOV CHAIN ANALYSIS ON THE COMMUNICATION
To better understand how the parallel workers reach consensus over communication matrix, in this section we use theory from the analysis Markov Chains to obtain some useful lemmas for proof of Moniqua D-PSGD and AD-PSGD.
Since the communication matrix W doubly stochastic (each row and column sum to 1), has the same structure the transition matrix of Markov Chain with 1a as its the stationary distribution (W a (. Now let tmix and d(t) denote the mixing time and maximal distance between initial state and stationary distribution as defined in Markov Chain theory 7
E.1 D-PSGD
In D-PSGD, the communication matrix is fixed during the training. That makes it perfectly aligned with the structure of a Markov Chain. As a result, we obtain the following lemma: Lemma
W (1- n 1 |[
(1_1n
2
Proof For Yx E Red, let u E &Rd be such a vector that every entry of u is the positive entry of and otherwise. Let u E Rd be such vector that every entry of is the absolute value of negative entry of x and otherwise, The setting above means I = u v. For example,
12, T
Here using notation from Chapter 4.5 of Markov Chains ond Mixing Times (Levin 2009), available https::ps..... / pages. uoregon. edu/dlevi h
wi..n-iiingg........ ng.pdff
18

---

Under review as a conference paper at ICLR 2020
[2. 0
00. 1]
And we have
W
a
1 1
W
W
+
Wr
1
m
1 "
W
u
1n
W
11
1
1
22 u I, v)d(t)
22d(t) ||0||
Considering the definition of LI LI-norm, we have
Wh (I 1n
W ( 1n >|;
(1-1
20
=max max
S 2d(t)
n
|
According to well-known results on the theory of Markov Chains non-negative integer so we have
d(ltmix S 2-
holds for any
W' (1 (
1n n
11 s 2d(t)= S 2d
----6mis Imix
t Lmix
S
bmix
S 22
Fmix
Lmxx
That completes the proof.
Additionally, based on standard results in the theory of reversible Markov Chains, we also have
1
log(4n)
mmix S log
I
1 1-p
1
E.2 AD-PSGD
Note that unlike D-PSGD, here WA can be different at each update step and usually each individually have spectral radius 1. so we can't expect to get bound in terms of bound on the spectral gap as we did Theorems 2 and 3 Instead, we require the following condition, which inspired by the literature on Markov chain Monte Carlo methods: for some constant lmix (here mix is the same as mix in the paper) and for any and any non non-negative negative vector μ E Rd such that L μ = 1, it must hold that
finix [[
1
1 2
k-t
11
n2
We call this constant mmix because it is effectively the mixing time of the tine-inhomogeneous Markov chain with transition probability matrix Wy at time Note that this condition is more general than those used in previous work on AD-PSGD because it does not require that the Wi sampled independently or in an unbiased manner. Based on the above analysis, we can prove the following lemma, which is analogous the lemma used in the synchronous case.
Lemma For any k 2 0 and for any 2 2 0, there exists bmix such that
II W (1 (1- q
2
n
10 "ggai,, see Markov Chains and Mixing Times for more details. Detailed analysis and proofs of this result be found in chapter 12.2 of Markov Chains and Mixing Times.
19

---

Under review as a conference paper at ICLR 2020
Proof Note that for any R and let u and u be vectors having same definition in Lemma with respect to 2, then we have for any k
!
II w
(1
[
1
x
mix
W Witk
1
(u
v)
n
In 1
mmis
Woth (1
1 1
W With
n1
11
9=1
1 T u
W q+
u
1x
1
Cwit
W g+ k
v
1
1
7
1
(1, [ 11
||=||]
Considering the definition of the induced & operator norm, we have
Witk (I 1n
Emix
1 1n11 1 (1-
I
II W g+
max
As a result, from the submultiplicativity of the matrix induced norm, we obtain
II Wa (1 1
Emix
[ Intn
Emix W tq
1,1 n
f. W +..
(T 1n
Wa - 1t4
b-o+1 fmix
II W W...tq (1-
11
<2
where t, = (b-ar a 1) mod tmix- Note that
II
4 Wg
r (r-
(r
1 1T
2
$
+ (n 1)
=
n
Putting it back we obtain
II W +g 1
1 T
2- 2
bmutt1 Fmix
That completes the proof.
Note that in the analysis of Moniqua on AD-PSGD (Section we will use this lemma as an assumption.
F MONIQUA ON D-PSGD (PROOF TO THEOREM 2
Consistent with linear and non-linear quantizer Here we briefly explain why using 0 2s ( mod 1) instead of Qs (a mod 0) for theoretical analysis and how covers both linear and non-linear quantizers. Note that typically, linear quantizer has:
(xx) olloo I 8, Va Rd
20

---

Under review as a conference paper at ICLR 2020
while a non-linear quantizer has
[[(((z) 10x - 8
Vo 1R
so that for linear quantizer, with given A:
0 2 h mod ) - =|
0 Qs @ mod 1) - -(Ø mod 1) 1)11_
I 06 06
And for non-linear quantizer, with a given x <
Qs @ mod 1) x e
@s @ mod 1) - ( mod 1)
0-
I 08 A6
As a result, we can use the same bound 06 for quantizers with both of the properties, which we will show in the rest of the proof.
F.1 PROOF TO THEOREM
Proof For convenience, we define the following notation
Xx = [2,,1, ... Ik.n]
Q: [q,,1, [k.n
Gx 1 [k.nl
Gk [9k.1, .9k,ml
X = X In VX E Bdxn
S4 = (Qk X&) I)
where 9k, denotes gradient computed via the whole dataset D: and x From local view, the update rule of Algorithm 7 on worker iteration can be written as
Tk+1s <- Ikk Σ JeN; (gks (k.k) W 00
which is equivalent
Ek+1. Tki + Σ (Th. Ik.)) W3 -ogg.
Σ
((au.) - Tkj) - -(gh.; -Ik,i) Wi
(8)
j=1
From global view, the update rule can be written
X = X2 + QW - 1) - - = X at (Qu - Xx)(W -1)
(9)
From Lemmn 5 we have
K
4(f(0) - f))
2aL 0² +
sa² (0² +
E
[V(x))]|
K
ak
n
(1-p)2
81,2
K-1
nK (1 p)2
Note that
K
K-1
E
E
Σ ((ak.) mk.) (gk.i xk.e)) WGs
Levnma
808 GZ
K=O 1=1
The last step holds because 80 ffaGGoo Pushing it back we obtain
K-1
4(1(0)- - Pr)
2aL 2
8.2 (o² + 3x2)
Sa2 dT?
Σ
+
+
K
aK
n
(1- p)²
(1 p)²
0=
21

---

Under review as a conference paper at ICLR 2020
By setting
we have
<x +a V +25"
) 8(f(0) - L
K + 40(f(0) f +
L/2) 4c(( f*)
E [
K
vnK
K$
8L200n
24L24
GL dn
(1 ()
+ AnT.)
(1 0)2
(1 ( K-KK++0 4m
Q²n + Go dn
K Vnk
K
o²k +
02 +
That completes the proof of Theorem
F.2 LEMMA FOR MONIQUA ON D-PSGD
Lemma If [/1,,,1 - Ft.i oo S 0. Vi,j holds at iteration I, then
Σ
((gra Iz.)) (gt.s zz,,)) W
200
Proof
(gas Izi)) -(gr 21,,)) Wjj
Wyi I1(ar. - x1.) - (gr,s x1,i)ll
Wi
000
The
mod 1) -0
Tr.i
mod 1) - (vt.) - xe,i) 00
0
Σ
Wj
0
Fi. 0
mod 1)
00
Ft.j
mod! 1) -0 0 Ft.j - It,s mod 1)
Σ
00
Tuj
mod 1) -0
0
Fte
mod 1) - (0Q
mod 1) 0 (22 mod 1 1))
0
(
W5
000
Teai 0
mod 1)
0
Fris mod 1) 1|
W'i
100
Teai 0
Piis mod -)
(%r mod l|
1=1
<280
Lemma 4 In any iteration k 2 0, and any two worker i and j, we have:
2 21oo(16m)
(a(ee-ee)lla. S 5
aG
1
Proof We use mathematical induction to prove this:
1. When k = 0, |Xooee - -2))l 0 < Vi,j
II. Suppose for || - - S 0 2 0, Ji we have
[ e,)llx (x + 21)) (et ( eg)
0
Σ
(-aCr + 22x) W ei)
1=
22

---

Under review as a conference paper at ICLR 2020
aG; (2)) w ((e: - =eill0
aGi +00
(e= e2))l
1,00
t=0
=112ell2.00)
I|w* -ee-l
a
1,30
induction hypothesis
(aGx + 268)
( -c)-l
1=
S oaGo + +250
Σ
[| -c))1
For any 2 on one hand
(e-ee-e))lll valll" - ei)ll2 S vT W (
In
+ vi
W'e,
1n
< 22/mpt
n
ofW. W. On the other hand. where the last step holds due the diagonalizability of
[[= e))l, s W W 1
So
|| -1)ll S min 23
Let To
[o log(p)
so that npno S 1, then we have
To
Σ
Σ
W - -e)lli+ + Σ
(e -
1=0
t=0
T=
To
<
2
+
/
log(vn)
2
Σ
2 ) p'
log(p)
1=0
2 2
2
+ +
1 1-p
P
log(16n)
1 1-
As a result, we have
log( 16n)
(ei-leeree)ll 5 s(aGo + 250)
p
Since 8 = TTo][Ton] we have
1-p
| - e;)l S <(aGoc + 280) log(16n)
2 2log(16n)
aG = 0
1
1 1-p
Combining I and II, we complete the proof.
Lemma 5 The output of Algorithm 7 has the following bound:
A(f(0)-7)
2
8a 322 122200230 +3x2)
K E
2
ak
n
(1 (1-p)² p)2
81,2
K-1
Σ
E 2
nK (1 p)2
23

---

Under review as a conference paper at ICLR 2020
Proof From Lemma
8 we have
K
K-1
1
aL
Σ
E
Gall
+ K
S (x
K
k=U
k=
< 2( - 1*)
at 0²² +
I,2
K 1
E | - -k,i 1
+
ak
nk
k=0 i=1
Lemma ((() - M)
al 0²
2a²² T.2
3 Σ B E
0² +x²
35²
ak
n
M1 p)²
K
2L2
K-1
E || p
M1nK(1 - p)²
where
6a
M = 1
p)²
Rearrange the terms, we get
1 - aT.
K-1
B
2 + 1
6a2
1 K-1
Σ E [(
K
M1(1 - -p)2
K
k=
2(f(0) f*)
+ aL 0² +
2a L2 (62+3x3)
2L2
K-1
E || 2
aK
M1 M1 (1-11) -))²
Mink (1 p)²
k=1
Let
6a2
M2 1
(1 - p)²
we gel
1 aL
K-1
M2 K-1
E ||
1 +
Σ k=
E [(xn) 2
K
K
k=
(() - f*)
aL
2a L (0² + 35²)
212
K-1
0²
Σ
E $1 /
+
aK
n
Mi (1 - p)2
MinK(1 - p]
k=1
Let M1, M2 2 1 and rearrange the terms, we have
2
1 K-1
4(f(0) - -)")
2 0² +
Sa² (0² + 3x2))
E
K
aK
n
(1-p)²
k=0
8L2
K-1
E 11
nk (1 p)2
k=1
and that completes the proof
Lemma 6 Let M1 = 11
6o
> 0, we have
(1-p)z
L K 1
2a²
3 K-1
Σ ((((((X))1** k=U
E X - In.il
0²+33²2 +
K
Mi p)3
K
0=
21.2
K-1
E S
MnnK(1 11-pp p)2
k=
Proof
K-1 n
Σ ΣΣ X - -
0= 1=1
24

---

Under review as a conference paper at ICLR 2020
k-
1n
))
E
X
ei)
[ W- - atx-1 + 24-1)
(In -e)
Es |
E
k=
20.1
K-1
E
Σ
aG (-aGz
+ +.2))
("n wh-rlte 64
In
n7
1n
22a
2
E
G
W
Wk-t-lcs
o2
π
1n
2
E
Σ
Wh-
E7
K-1
1,17 T
K-1
1,,
-2a2
E
Σ
G
W
E
2
W
7
n
K-1
2
K-1
k-1
2
Lemma 10
2
+2
E
||2
k=1
Lemma S
2a
K-1
Gh
+
2
K-1
Σ
E1 2
E
p1-
(1- p)
(1
k=1
k=1
Lemma
0
2a
no² K + 3L
K-1
Σ
Σ
B
X - =2.el?
3nc K + 3n
K-1 Σ
E
VJ
(1-p)² p]²
k=
A= 0
K-1
E 1
(1 p]
k=1
Rearrange the terms, we have
2a2 (1-p)²
K n
ΣΣ
E
X Xx
TkAll 1l
k=0
<-
2a²
no n K + 3:3
2 K + -3
K-1
E V \
+ (1 - p)
K-1
E |1 1F
(1 2)
Let Mj = 1
1,2
> 0, we have
(I-p)z
2
K 1
2a
K
R
X
Ik
02+35² +
E
nkK
Mi
p)
K
1=1
k=0
2L
K-1
E 1
MinK p)2
k=1
Lemma 7
K-1
K-1 n
K-1 K + 3n
Σ
Gk F
S no
K 3L
X I2,
+ 3ns 2
Σ Vf((x))]'
Proof From the property of Frobenius norm, we have
G =
25

---

Under review as a conference paper at ICLR 2020
Next, derive the upper bound of E ll
E |l
E lo 9h Ih.
loke - 9k,,ll + |1 + 21 (ōk, - (k,i-9k,1)
=E lork, gk.ill + E 11 11
So² + 3TE I VX((Xx) x)
3TE (Xi(XA) V/(Xa)| 3
So² + 3L X =2,il| 2|
+ 35 + 3E [
Summing from k = 0 to K 1, we obtain
E
K
k= 1=1
K-1
K-1
K-1
K-1
3I.2
E X
TK,I
+3 Σ
++3
Σ
Σ
V
E
k=0 1=1
k=0 i=1
R=0 1=1
k=0 i=1
K-1 n
=no K 3L
E |
-21,11
2
+
+3ns
33n22K+H KK3n 3n Σ
E vi
1=1
That completes the proof
Lemma
aL K-1
K-1
GR
+
(X)))
K
K
k=0
k=0
2(f(0) - f*)
aL 8²
L
K K-1
E
X
- IK.El
aK
k
k=0
i=1
Proof Let Ln denote n-dimensional vector with all the entries be I. And we have
- (X&W aGxx + fxx) n
Xx - (Qu Xx)(W - 1) - n
Xx - aG
And by Taylor Expansion, we have
(X&W - aGix + Ax
Ef(X++1) = Ef
= Ef [x - ati))
< <B(Xxs
(.
C.)
a²L
T. 2
2
And for the last term, have
2
Σ 1= Tk.
E
G
E
n1
Σ 1= Ih.
Σn Ih.s
Σm Ik.s
E
Σn
Ih.t
En= Th.s
Σn 9k.
+ E
26

---

Under review as a conference paper at ICLR 2020
Σ
Li=l
Ik.
Ei=1 Ik.
Ei=1 gk.
+E
+
n
2
Lisl
I
Zim
I
Lim Ik.
+ E
n
Assumption
(43)
E
gk.i 11
+
ii=1 9k.i
n1
71
Assumption
0
E
-i=1
R
9k.i
Putting back, we obtain
Ef(X++1) & Bf(x)) - -BB(V GR)
+
0
+
T
18
Ei=
Ik.s
2n
2
=B((x() a - a azL
a²L
E Gk
a
E
||
2
2n
= - =x
2
where the last step comes from 2(a, b) ||a||2
+ |18| = ||a
b112 And
Σ =1 Fk.s
B B)
Gk
E
V
71
n
Assumption [A1)
Σ
E
i=
L
R
Xx - Tk,1
n
putting it back, have
a²
Go -
||
aLL
0²
aL "
Σ E
X
2n
2n
summing over from k: = to on both sides, we have
1-
K-1
K
Gk
+
Σ
K
K
k=
R=0
2(f(0) f*)
aL
L
K
0
+
E
Xx
- I2.ll
aK
nk
k=
i=1
That completes the proof.
Lemma
Given two non-negative sequences {az 100 and {be that satisfying
bb
==l
with p 1.we have
S
P ==1
1=1
D3
[1 1
27

---

Under review as a conference paper at ICLR 2020
Proof
1
S
<
1
P
1=1
[=1
s=1
t=
1=
k
D&
Qt
b,
Σ
21
b.b-
k
21-8-1
21-3-163 6²
2
1=1
s=
t=1
$
(1
p)2
s=1
==1
Lemma 10 For any X₁ E Rdxn, we have
Antn - Wk Wh-1-1)
Σ
X
5
Σ
||xill
t=
1=0
Proof
LnIn
1n Wk--
Σ X
W
Σ
X
n
1, 1,
X
1 T
|| F
That completes the proof.
G
MONIQUA ON D2 (PROOF TO THEOREM
G.1 ALGORITHM
Algorithm 2 Moniqua with Variance Reduction on worker
Input: initial point T = step size the discrepency bound 0, communication matrix W. number of iterations K, neighbor list of worker N₁
1: for k = 0, 2, ... K 1 do
2: Randomly sample data Ça.s from local memory
3: Compute a local stochastic gradient based on &k and current weight Zb,i Tk.
4: if k then
5:
Update local weight: 2k+ 2k,5 agk,i
6:
else
7:
Update local weight: 3. <- 25 - Ik ogfes, + Or 1,1
8:
end if
Compute modulo-ed model: Te.s + 0 25 (# mod 1) (element-wise division and
9:
mod)
10:
Average with neighboring workers: T4+1, f- TK- s + ESEN, Ws,
11: end for
Output: X k 1 Σ FK.
28

---

Under review as a conference paper at ICLR 2020
G.2 ASSUMPTIONS
D makes the following assumptions (1-4), and we add the additional assumption (5):
1. Lipschitzian Gradient: All the function ft have L-Lipschitzian gradients.
2. Communication Matrix: Communication matrix W a symmetric doubly stochastic matrix. Let the eigenvalues of W Rn be A1 2 ... 2 Az- We assume X2 1,
3. Bounded Variance:
[i((=)) - V/(w) S s
E ED
where (a((;;;))) denotes gradient sample on worker computed via data sample &x-
4. Initialization: All the models are initialized by the same parameters: To,s = 20, Vi and with the loss of generality 20 O.
5. Gradient magnitude: The norm of sampled gradient is bounded by 1 Go for some constant Goe.
G.3 PROOF TO THEOREM 3
Proof From a local view, define r- = 9-1 O, the update rule of Moniqua on D2 on worker in iteration k can be written
Fk+ 1
20
2,- 1 a.jki + aoik-16
Σ UK+ CKt
Wii + Σ
E(((s (( IR+ (0e, - okt Wji
Tk+1.
From a global view, the update rule can be written as
X 2Xxx XR-1 - aGG atk-1
Xk-1 Xx+$ W + (Qx XW
Define
Ω4 = (Qx - Xx+ )) -
Since W is symmetric, it can be diagonalized as W = PAPT, where the i-th column of P and A are W's 's' i-th eigenvector and eigenvalue, re respectively. And we obtain
x = PX, - -GAPAPT + PGG +0
and
X4-1PA P - aGPPA P
Denote Y₁ = X,P, H(X {x) = G.P. and denote yk, has and Tk. as the i-th column of Ys, H and QyP, respectively. Then we have
1k+ Ae yk- abw. ol1g-11) + Tk.
From Lemma 15 Constants C1. C2. C3 andn C4 are defined in the Lemma Constants D and Dz are defined in Lemma
75) we get
(1
30
E [
+ (1-OL-3
-G
E K
1
K-1
K Σ
E
C4
C4
k=
k=0
2(((0) 1r) aK
al. 0²
32 + s8)
C2
C2 nC₁
+6
a
20
+3 a 202214
C.K
C₁
29

---

Under review as a conference paper at ICLR 2020
CzL2
13Dmn+4)
a
C2
3D2n
Let
KVK/n+2L' we have
Σ
K
2(f(0) - f*)
al 0= + 30qa2 +
+ 2a L2 +3 afo
C2
ak
CiK
C4
nC4
3Dm +4
CgLL
G2 G2 da?
+
3D2m
C4
(((()) F'LL
20(f(0) - f + L/2)
(0) +
60²L20²2
K
VnK
Ca(o212 + +nl2K)
Ca(oaK + 4n
32
33Dm +4
2
C3G2
C2(o-K2 + 16n=
3Dnn
Ca(o2K + 4mL2)
Vnk + (0² + +
o"n
g2K2 + + G dd dn
K
0²K2 nk
g²K +
o²K +n
dºn
G Gn
K
Vkk
o2 +n
o
That completes the proof.
G.4 LEMMA FOR 2
Lemma 11 Define
2 Am
A
+ 212
D1 = max
|0n| +
1 |121
1 2
A2
2
D2 = max
1 - |val
vI A2
Un An
X2 An
Let 8 bnDD and we have for V
T (e ej) =0=(6D,m) +8
Proof We use mathematical induction to prove this:
I. When ks =0, O, - [xo+f(i-ee))
= -ll-aoolei -eiil (e) sa To 1,00
||e; - -eyll s 20G S 1.Din+8)ack
II. Suppose for 1 2 O, Vt < k. we have
|x++y (c. -
s (6Dnn &))GGoo then for Vi.j
Xx+1(ee =E))llc
In Xx+1
Ln
Xx+1
Ej
n
n
2
0
0
0
0
0
PPT -X
0
0
0
PT
6;
30

---

Under review as a conference paper at ICLR 2020
00
0 0
+
Xk+1
PPT
ej
-X
PT Cj
0O
0
0 0 0
0
0
X
P
0
0
|| 4111 +
Xk+1 P
0
0
PP eylb
1,0c
1,00
TO
0 0 1
0
<2Vn
X
P
0
0
0
1,00
From the update rule, we have
yk+1,i >e(2yk, yk-1, ahg, + ahx-1,1) Tk,i >x 1k- Ar3R, Tkaa
whereBk, -aha,i + ahx for all ys with
A < O, from Lemma 13 we have
k+1
k+1
k
u. st1
1K+ V1,
u
+
14 (A, + ra.i)
Ui
where u, X4 + Vx= X and
1 2;
X obtain
k+1 k+1
k- x+1
1, S 1111,,llo0
u,
2i
+ A
1a,x 1o0
11
ui 11a
144
U1
u
| 00
M1
Since
u n+1
11 n+1
ML
U/
5 |0: m
I |uy m
Ui Vi
U;
We obtain
l1vet1alloo < 11 |0: + 1Ail Σ
B 1-
r lu-lk-s
1=1
For Bag we have
11 = alhh + ahl- $ 20([I :o + (10k-1
Peelli + || <2a <2
For Tall we have
|Ik. = 110 Pesll < |1 |Peell S 25n58
when A < O, we have
b 1ie+l.illos 5 a11 l0: + +|Ai Σ
k 1Ba.illo 10: |001* k-s + >
|| lui
31

---

Under review as a conference paper at ICLR 2020
$ 111i..i |0al + |nl Σ
|2x h- + Σ
||
20 |121 k=
==1
==1
26
oc
SaviGGoloall 1e 22r |nl
Σ
|unl
Un
8-
+ n
On k-8
20/TG22011 Anl
2/1508
1 |1x
1 |1/2
where Un An V Am.
On the other hand, when 0 S X < 1, from Lemmal 13
we have
1k+1, sin 0, i sin [(t + 1)0,} + x Σ Bo,d2 2 sin(( + s}0,]
, sin((k: + s00c
By taking norm, ger
114+1, sin 0,1
1111, X / 1))a1l + X Σ
|| 12, 2-" ||sin(( + =s)0,]
8=1
|sailloo 11g
sin((k 1-))0
1 + 22/ Ilu 25z + az Σ
8=1
2 20v/nGood + 2Vn00
I aav V22t
--
Since ssn 0:] 2 VI X2, putting it back, we get
/
X2
20 nav/nZzop + 2/n50
|M++1,ll S aann
+
1
1- 22
So there exists D,
2 Ax
A2
+ 2X2
D1 = max
|Un]
+
1
|ua|
A2
A2
2
D2 max
|val
v1 X22
such that
|1 S DDavvTG + D2yn50
Putting back we have Vi,j
-x s DianGo + D2n50
As a result
Xxtz(ei-
12Xx - Xx-1 at, +
<2 Xalee l)) + +1 -e))l ta Gx 1,00
|le eill +a |
|c cyll
32

---

Under review as a conference paper at ICLR 2020
3( Do + D2no0) + 4aGx (6 8)aG
The last step because ö
6nD2
Combining I and II complete the proof.
Lemma 12
K
(1 - 12
Xx
1=1 k=1
53Cia + 30ia no + 3C n f()]| 6C2a2no "C 3C2a'
K-1
+3Cza'nI'
G
+ C3
Σ
B 1
Proof
2
1n
X
Ib.i
X
Es
i=1
1ntn
T
Xx
1
|XpPPT Xx
0
0 1
0
0
Lemma
X&P
0
ell
From the update rule, we obtain,
yk+1,i = A:(2yn, 1, - ahg,s + ch1- 1,1) + Thi A:(2ii - 1,-1,a) A9 + Tk.
whereßk, -OhRRi 1,5 for all yı with
> < O, from Lemma
13
we have
k+l of
k+1
h -+1
"
"
Vk+1,1 V1,
(A:Ba, rk.e)
Us 1 Di
U1
where ui >o + /
Ni and
X2
Ai oblain
u, - k+1
I Σ
1:
s+1
3 1,,++1,111
+ 3A?
1|3
u,
14
k
u
k-
1/
k
2
+3 3 Σ
|
24
Since
n+1
n+11
W4
Us
1 |2 m
< | 1
24
02
U4
We obtain
k Σ
2
1, 2 53 ||1,: 1 + 3X
Σ
113
|0:|
+3
|
k-o
33

---

Under review as a conference paper at ICLR 2020
Summing over from k 0
K
1, we obtain
K-1
Σ
18K+1,1
11
1
k=
K-1
K-1
K-1
2
$3 111,=11
10: 12
+ 3A3
Σ
1 10y
8-8
+3 Σ
Σ
1 10g
3 1l
312
K-1
3
K-1
+
Σ
|13,,,11 +
||w,,ell ?
1 10:
(1-1o:)2
(1 - lo:1)2
(1-1e/1)
k=1
3
$1 2
32
K-1
3
K-1
11
+
|| 11
Unl [2
(1 |un
(1
[2n))
k=1
where An
/12 - Xx.
On the other hand, when 0 S Xr < 1, from Lemmal 13
we have
& 9k+1, sin 02 A1 sin((t + 1)6.] + A Σ
Baod
sin(( + =s]0,]
8=1
, sin[(k: + 1 - s}
And we have
1, Ill "sin" 0, s 3 11 2/ ssinn + 1)0,]+33 332
Σ
3 3
sinl(k + - s)0:}
==1
+
Σ rard
sin((k +1 1 s)0s]
* Σ
2
h
2
$ 3 |1. A/4 + 3X,
Bo,id
+3
Summing from k = 0 to K - 1, we have
K
K
11
"sinn =
Σ
:ll ssnn
k=
K-1
K
2
K-1
2
<3 111,,al1
2
Σ k==0
X + 3X?
I1 A
+3
Σ
Σ
k=
k=
3 111
3X3
K-1
11
3
K-1
||r
1 di (1- vA,2²
(1 - v2,)²
Since sin² 2 0; = 1 - ds. we have
K
3 $1lun,il1 2
+
323
Σ
K-1
11 + (1- V1,(( Xx))
3
K-1
(1 )x
(1- 11) X1)
k=
3 |11 2
+
3x3
K-1
Σ
11 +
3
Σ ll
X2)²
(1 - 22 - x2)
(1- 222))2 - -x2)
34

---

Under review as a conference paper at ICLR 2020
So there exists C1 C2 C3s
3
3
C1 max
|1 12' (1- X₂) (1-
3
313
C22 max
(1 |unl)3
(1 - (22 - X²)
3
3
C3 max
12l)22 (1 - (12)2(1 - x12)
K-1
K- 1
el - C1
11 + +02
Σ
|| + C3
Σ
|rreel
R=1
k=1
By taking expectation we have
K-1
K
Σ 11 S 11r,ll
+ C2
Σ
E
3 2 + C3
Σ
E |rs
We next analyze Sk,
E |13 2
E |//,,
h6 h.11
=
E
G Pe, Pep
1=2
G Pe; - PP; 1
<a² 2
Σ
1E
1=1
G.P G2 G p 2
Lemmo
14
Gx
G
2
F
=0
Gre; Gh-
<3a² 2
1
E Cre: Gres 1|
+ +3a² 2
Σ
7
E G 10;
Gh-
+3a² 2
E
[kRe GR-
1=1
26a2no" 3a
E GIAG - 12
i=l
n E |a 1,
2602n02 + 30 1.2
2oa²no² +3021 2
E Vgg PT c - -Yr-1PTeil
<6a² noa + 30 2 L'E
|Y:PT - -YK-IPT1 ||=
Lemmal 14
2a 30 1 [|2 YE- P
35

---

Under review as a conference paper at ICLR 2020
n B likki yk 1,e1,
<ba2no²
3,2
And Putting back, have
K
E
K-1
K-1
SCEBI
C2
E B11 2 + C3
Σ Σ E ||
Am
K-1
n
K-1 n
SCBBIY 1/ + C2
Σ
6a2no² + L
IE Il - 11-1..1?
+C3
| 2
k=
Lemma S 1 + 60za2no K + 3C L
K- 1
K-1
E lyyk, 32-1, +Cs
EE || ||
k=1
k=
Since
||bk,1 yk- 11 = E P|x
X 11 =E x
1 11
=E X vn
1
1, - X
//1 1
1
= nB X - X = nax 2 Gx
vn
<na²E
Gk Gx ||2
na
|
S na 0² na G 2
=a²o² + n G
?
Putting back, and we obtain
K E ell 2
K-1
(CBB/ + 6C2a2 no K + 302aa0011 3a nL?
Σ E
Gall
K-1
K-1
+3Cza²1 2
- - CCB
E 2
K
SCE|IYI + 602a2 no K + 3C 02 L2 + 3C
Σ
E
GR
+6Cza² 2,2 ΣΣ Σ
E (110..11++11um
C3
Σ
E E
K-1
SCE|||Y]| + 6C2a2 no + o2 + 3C2a 'C
Σ
E
G 2
K-1 1 +12Cza²LL
K-
E Iu 212 + C
E
11
k=1
Rearrange the terms, we get
K ΣΣ
1-120za213
k=
36

---

Under review as a conference paper at ICLR 2020
K-1
R-1
<CB F + + 3C2a
B|
E
2
+ +C3
E 112
k=1
<0 [1 + 602a0 3C2a L "33a'''''
3L2
E
G
C3
E
||
|2 /
k=1
Considering
E
1 1|
Go
F
a
E
Go.5
Go.t + Go, V/(0)+ v
i=1
2 3a 2
Σ
E
Go.t - Go.s ||
+ 3a 2
Σ
E - + 3a 2 E [V)()))
i=1
S 3 no²
+ 3a²nn5 + 33 Vf(0)]
We finally gel
12
12C2a L
E
el
k=
K
-(1 - 1-22aa L2)
[x - Zn,il 11
2m1 k=1
<3Cia"no" + 33ia0 noso + 3C |V00]
602a"noon 60 K + 3Caa 2022
+3Cza'nI²
E G 2 +Cs
Σ
B1
That completes the proof.
Lemma 13 Given E (-3, 0) U (0, 1). for any two sequence {ar (ba and 1e that satisfying
bu 0,
0,+1 = p (2ar 0t-1) + bt b--1 + a. 14 21
have
(u++1 (uttl_zth 2 )
(
- - -
a++1 01
(b. .b- +
44 42 0
U
where
u p+ Vp² P. p V
Moreover, if0 < < 1, we have
0t-1 = a1p² sin + 1)0)
sin s + 1)8)
(b. ---1 cs)p 00=
+
sin
sin
s=1
where
0 arccos (vp)
Proof when t 1, we have
a++1 = 2po pa4-1 + by
bi + Ce
since,
p Vp 2V== p -P-
37

---

Under review as a conference paper at ICLR 2020
obtain
a++1 Wa4 = (at ua uu44111 1)0 + b. - -b-1 + ct
Recursively we have
a1+1 ud = (at - ud=-1 ) + b, - + Ct
= (at-1 u + (1,-1 - 1/22 + cc-1) by bu +
= (a1 uao)v' + Σ (b. - b + col
==1
=av² +
(bs 1 + cg)ut=
a=1
Dividing both sides by 1 we have
ac+l
at
+
u
(1+1)
a1v' + Σ (b. - 11-11 + co)ot=
"
4
t-1
w-1 + zt
4-1
a1vl=1
+
bbs b + co)
s=1
+ u (I+1)
arvl
(b. b + cg)
==1
k-1
a11" + Σ> (b. b colotiss
Multiplying both sides by +1
a++1 = aju'
w
0g
(b, bb- + cx)o'=
h (b. 1 + c,) (
= aj
1
U
+ u
2
k=1
k= a=1
U
anp
(b. b + cx)v
t-s-1
anl'
(b. 6,- + tca
1
u vt+1
-- 1+1+
=01
(b. b-- + C.)
u
Note that when 0 < p < 1, both u and are complex numbers, we have
= Vpe" 2 Vpe 10
where 9 arccos vp. And under this context, we have
sin + 1)0)
sin s + 1)0]
+ Σ (b. 6,- + ca)p =
at-1 = appt
sin
sin
That completes the proof. Lemma 14 For any matrix X E R Nxn, we have
|x:112 = =|
i=2
1=1
Σ
XPT e;
= XP
1|2 = ||x
1=1
38

---

Under review as a conference paper at ICLR 2020
Proof
" |x & Σ |x,,ul1 =| = - = 1
And similarly,
XP =||'=||XXT|[1 -
Tr(xxx)) = ||x.
That completes the proof.
Lemma 15 If we run Algorithm 2 for K iterations the following inequality holds:
a2
BIV
B
+ (1- -3 C2
-3
a
1 K
E
C1
C1
K
K-1
Σ B||vf(X>>)1
K
k=0
2() 1 1") +
al 0² + 30 + +
222002 L22 +3
C2
C2 nC,
L
aK
C₁K
Ogl2²
(3Dmn+4)
2
Q2
C4
3D2m
where
3
3
C = max
2
(1 - -2
31
323
C2 max
(1
(2z))2'
(1 v22)2(1 A1)
3
C3 max
|n 12 (1- vA2)2 22)
C 1 2 L?
l4e = Σ
(aans Ix+ - (gk.s x2+ Wgi
1=l
Proof Since
X (2Xx Xx-1 aG + a
1n n
+ (Qx XW+ -1) Ln n
2X - Xx-1 - atx + aG
and we have
X Xx = Xx X
aG₁ ao
=
= X1 X,- a
G. G
-aGk
As a result, we can reuse Lemma
8 from D-PSGD, thus we have
aL
K-1
G
2
+
K-1
Σ
(x)))
K
K
0m0
k=
2(f(0) - f*)
aL
K
- -
E
X
aK
nk
k=U iml
39

---

Under review as a conference paper at ICLR 2020
From Lemmal 12 we obatin
- aL
K-1
K-1
Σ
E
G
Σ
E
K
K
h=
2(S(0) (M)
ab
1010212
+ S + 1
C2
C2 d'021, nC₁
0² +
+ + 2² +3
aK
n
C₁K'
C4
C2
K-1
C2L²
K-1
+3
E Gx
+
Σ
E 112 lF
CtriK
Rearrange the terms, we get
3C
E B|V + (1-a1--38
Σ
K-
G 2
C4
C4
K
K-1
E {(xv|(
K k=0
2(J(0) 1*)
al 0² + 301a213 + +5))
C2
C2 1
+6 +6 22 1?
+3
aK
n
C₁K
C1
nC₁
CzL K-1
CanK E. 1112211 1/
Lemma 162 (f(0) - -ft)
aL 0²
30 3Cia2L2 +6)
C2
C2
+6 + a
20
+3
a L
aK
n
CKK
C4
nC4
CsL?
(3Din +4
a'G2d
+
3D2n
That completes the proof.
Lemma 16
K-1
(3Dnn+4) +
E
11 <
2
3Dnn
A==
Proof Similar to the case in D-PSGD, we have
K
K-1
(gN.s - IR+z.) - -(gk.) =xoz Wjs
A=
A=
Lemina
8
K
+ (3D /3Dnn+49 4)
1) a G2222dnK
8
3Dnn
k=0
1=1
That completes the proof.
40

---

Under review as a conference paper at ICLR 2020
H
MONIQUA ON AD-PSGD (PROOF TO THEOREM 4)
H.1 ALGORITHM
Algorithm 3 Moniqua with Asynchronous Communication
Input: initial point To.; zg. step size a, the discrepency bound 0, number of iterations K, quantization function Q. initial random seed
for k == 1,,2, 2, K 1 do
2: worker 23 is updating the gradient while during this iteration the global communication
behaviour written the form of W
3:
Compute local stochastic gradient with model delayed by T&l 9k-re.
4:
Compute modulo-ed model: Ge.i < 0 Qs ( (fiik mod 1) (element-wise division and mod)
5: Randomly select one of the neighbors Jis and average local weights with remote weights
while subtracting the biased term: Tk+ 2.4 This 29h. T9,,
6: Update the local weight with local gradient: Ib+ f- Ihiie 00jk-Tu.1
7: end for
Output: XK E. IK₁S
H.2 DEFINITION AND NOTATION
In the original analysis of AD-PSGD, to better capture the nature of workers computing at different speed, the objective function is expressed as
fxx) = Σ p=f((z)
where Pt a parameter denoting the speed of i-th worker gradient updates. In the rest of the proof, we denote p = (ax
For simplicity, we also define the following terms
VF(X2) = n (119k11 PnBk.nl dx
V((x)) (1. Pn. E ddd
GR .... "..
G₁ Ihiis:"
A 1 1
W
q
H.3 ASSUMPTION
We makes the following assumptions:
1. Lipschitzian Gradient: All the function fa have L--Lipschitzian gradients.
2. Communication Matrix [2 The communication matrix W₂ is doubly stochastic for any there exists fmix such that
k 2 0 and for any
II W (1- quaa
(1-
Inn n
2 2
A-a+1
Fanix
3. Bounded Variance:
E D. Vī((z=)) - - 50,
Pleass refer Section for more details
41

---

Under review as a conference paper at ICLR 2020
(1,(1, m) Vf((() Vf(x)) <
where [a;; ()) denotes gradient sample on worker computed via data sample &
4. Bounded Staleness: There exists 7 such that 7 S T, Vk
5. Gradient magnitude: The norm of sampled gradient bounded by 10 S Goo for some constant G..
H.4 PROOF TO THEOREM 4
Proof We start from
K-1
+(1- 11-2aL)
20L
1 K-1
Σ E
VF (xx- xx
K
n
K
km0
kmm
Lemma
20 f(0) - f*)
(o + 6< )L
+ 22L2
1
K K-1
DrlE
X
( Ln
)(²
aK
k=0 1=
21. K-1
(X
X X 1n
E
K
n1
k=
Lemma 2112 (12m(((0)= - 1*)
(02 + 65 )aL
2T + 1.22)12
4ax 2T2 1,2
K
+
EB
Psfk T
aK
n
n K
k=0
2T. 12aL
24L 7
n K
Ln
P.R.
Xk-Ta
n
n²
71
Lemmo 20 (2) - f*)
66² )
2a 2
+ 2
2
K-1
Σ
E
Pagk 7k
aK
n²
n²K
k=
i=1
2
128 mix 1,2
2p
(o² (o2+652)p=
E
Pifk Taii
+
G
A1
K
where A₁ = = 192pa 2f,ii L² as defined in Lemma 19
Rearrange the terms, we get
(0( - f*) aK
+ (o (o2+653)aL 20² + +62
E [|]][(X*)|
"
n²
128pa P 2t L
128a 2 I2
(o² + +s2)+
G
A
A
By setting a
Vo² + 652
pf 102 (02 + Gr
22 22 G
- +
K K=U
VK
(02 + (.2)KK K + 4T22
(02 65 K - 412
1
-0² + 65
(02 + 65 2)22 mixx n
n222 p G2dd
K
VK
(02 + 652) )) K +1
+ 65
H.S LEMMA FOR MONIQUA ON AD-PSGD
Lemma 17
E
Gk-T2
ln
<
g²
+
Σ
E.E
gk-
V4: 2 0. 11
11
n
n²
n²
1=1
42

---

Under review as a conference paper at ICLR 2020
Proof
E
Gk
To
1n
<
P.E
Tk. T
1=1
Σ
Prl
9k
TR T
+ 2
Pel
9h
n
im
n1
prl
19 - 11
n2
n
Lemma 18
1,
12
E 9 19
12L Σ
p.E
XR-Te
+ 65 2E
2 P.gk Tk.
444 2 0.
n
==1
Proof
E.E.
g1 Taiil 11
Σ
P;E
9k Tk.t
Pigk Thek
+
Pigk Tke
i=1
1=1
1=1
2
1
n
7
$ 2
PEE
9k-Tk
Pifk Thet
P
Pifk PiTk-rki Tk
2
P
9k T
Pifk Th.
2E
Σ
PaOk Th.
And
E.E
9k - - Σ
Pigk-TeC -
1=1
a
[h Mk- Vfi(X=-Ta)) )11 +3
+3 +, P.E
f1 X k - (X KTTH)
1=1
+3
D
Pilk Tei Σ
V (X
1=1
j=1
7
X KT- 2 +33 n
12 ΣrソT X (x)))
<31
E Teit
P
V k- x-
1=1
+3E
Pifk Th.t
Σ
P3 f. X )
1=l
a
1n -e:)
Ei )
E&E
XR-Th
+3 Σ
P.E V ([(X==1))1
n1
+3
P3 TE
gh
Vlr(X x-(-+1))1
7
1n
)
||
<61
Σ P.E XR-T2
4/
+352
n
That completes the proof.
43

---

Under review as a conference paper at ICLR 2020
Lemma 19 Let A1 192pa t I??
K K-1
1n - Eú XR-Tu -h
Σ
Σ
k=0 i=1
32a 222 mix
R-- 1
(a² 6o²+ + 2p
E
Pigk Tk.t
+ &ook
A1
k=
1=1
Proof
In
)
|
p,lE
Xx
(XL-1 W/
+ +52= aGk-1-70-1
{th -e;) l|a
In
1=1
2
Xo
P+LE
(aaG +8l,
A
1=1
1-1
2
P,B
a A &i
+ +
P,E
Q4
1=0
1=1
Now for the first term, we have
k-1
1-
P.B
Σ
aG
Aftle
<2pa 2
k-1
1+1
2=
2
<2pa 2F
G
| |
1=0
<2pa
G
|
k-r= Imix
<8pa2E
G
2
Now replace k with ks
Tke that is
In
Σ 1=1
R
Xx Th
Ci
-1- -1
k-
$8pa2E
G -
2
Fmix
Ty
+
E
2 2AABT
141
1=0
1=0
Summing from h: = 0 to K 1 on both sides, we obtain
K
n
1n
P.E.
XR-TV
e:
n2
k=0
K
R- 1 Σ
2
k- ---
< <8pa
G
G
--
Amix
F
k=0
K-1
1 T2 -1
+ 2 Σ
2 k-
Ci
44

---

Under review as a conference paper at ICLR 2020
2
11
k- 12-1-11
< 8pa 2
G
miia
F
k=0
K-1
R T--h- -1
2
+ 2
| 1.2
A4+1
Ak-Te-1
|1, lleilla
1=1
k=0
t=0
K-1
R--H Th -1
k
2
<
8p0
2
G 71
2
F
k=0
t=0
K
k- k-re-t-1 Imis
2
+ 8
E
|Selll 1,2
2
1=1
k=0
K
R-Th-1
K-1
Taman
8pa
2
G
2
mmix
+ 32t mix
Σ
E || 1.2
F
km0
1=0
2m
kmm
<8po2
2
E
G. T 1|
2
miix
+ 1288202
mix K
k=0
1=0
K-
Lemmn
2
32pa
2
mix
Σ
E
Ck-Te
di K
Note that for the first term, we have
Gk-Tz F
E
11
Σ E 11
2h re 2 +
E I1gn - Te. 1
K-1 n
<0²K
E&E g[c
1= i=1
K-1 n
(1m ei
|2
7 Σ
<(0² + 65 K
121
Σ
E
Xx-Ti
E
Pig
Putting these two terms back, we obtain
K-1 1
1n - es
E
Xb-T2
12
k= 1=1
K-1
1n - ei 11"
12
K-1
2
<32pa mix
66=+622 + 121.2
PelE
X XR-FA t
+ 2
Σ
E
Σ
Prfk Th.i
k=0 1=1
k=
+12862 d
Rearrange the terms, we obtain
K
In
2
- 192pa 2
2 2
P.E
Xx Xn-TA
Ei
k=0 1=1
K-1
<32pa 2nix
(0" (0²+ + 2
Σ
E
Σ
Pigk - T
+ 222
mix K
k=0
1=1
45

---

Under review as a conference paper at ICLR 2020
Laman 21
K-
n
2
2 mix (o² 32++622pkk + 2p
Σ
Σ
GKd dK
P.gk tmd
k=
Let A1 = 192pa 2 mix_L
L2, we obtain
K
1n ei)
||
p,LE
XR XR-Te
Ei
k=0 i=1
32a 32a
K-1
(o²+6s
+ 2p
E
Pilk - Tkit
+ +Ca
A1
km
i=1
Lemma 20
1 K-1
[x))l+ + (1-
2al
1
K-1
Σ E
VF Xx x1) 11
K
n
K
2n(f(0) - ff)
2L k-1
(Xx
Xx=
+
E
aK
K
k=0
2L 12
K-1
1n
Ei ||
(02 + +52))al
+
P.B
Xk -k-Th
n
K
k=0
i=1
Proof We start from (()+1) Since
= 1,
+ Xe)(Wa)(Wa - 1) 1n
aGk=rz = Xx -aG
n
n
Then from Taylor Expansion, we have
Ef(X k+1)
EEf Xx aZx
a²L E
Gk-Tz ?
<ES(X;) aB(V Gx-
a²L E
-E)(X²) aB Gk a Gk-my - Gk-Tr)
+
G Th
2
=Ef(Xx) B(V((x,) VF(X +
gk Tk-Te
2
11
<ES(Xi)
VF(X
a²L a
a²L L
n
9k T
9k -r.i
9 T
+ 2
E.E
PE
n
2
n
Lo
a L
<Ef(XR) B(VF(X)). VF(X +
p:1E gk s
2n
2n
=ES(Xx) + E v/(X,)
VP(XA-N)) )11
E BBV
a E
V
2n
2n
2n
Lo
L
+
2n
2n
Rearrange these terms, we can get
a E v((x)))
+
VF
2n
2n
< Ef(x,) - Ef(xx+1)
a
VF((X-1)) |
2n
46

---

Under review as a conference paper at ICLR 2020
Lo²
a²
_ pr B
Ok gk
2n
2n
Summing over 10 K
1 on both sides, we can get
K-1
K-
1
E
E
VF(xxTe))
K
K
K=
2n(
K-1
abo² aL
K n
+
V
VF(X
nk Σ
g 12
aK
K
n
k=0
For
k
E x VF(X rl )1(
have
K
E Bl vF(X
K-1
( -1) +2
Σ
-
E
-
K=
12
E
Σ
E
Pi (Vi((X - -9k-Tu
K=
K-1
|V
Σ
E
P
VJI(Xxn1 9K-
k=0
k=
1=1
K-1
(Xp X
)
K-
1n - et) )
|1
<21²
E
+ 2L
Σ
P.E
Xk-Tz
k=
km0 2=1
Putting it back, we have
K-1
K-1
1
V F (x ||
+
K K=
K
k=
2n(
f*)
2L
K-1
(Xx Xx- 1n
E
aK
K
k=U
2L K-1
1n
}> ||
aLo?
aL
K-1 n
P&LE
X Xk-Th
ei
+
Σ
p, gh 9
n1
n
nk
Lemma
(n((((
)r)
2T.
K-1
(Xx
Xx-Ta)le
1
aK
K
n
k=
2L K-1
1n
2 aLo²
E
X Xx-Tk 7
et
K
n
k=0 1=1
aT.
1n Es )|²
1 Σ
P,E
Xx-Th
+ 65² + 2
Pigk - T
k
1=1
20( f²)
21 K-1
(Xx
Xx-re 1n 1
E
ak
K
n
k=U
12al,3
K-1 n
( 1n
+ 222 +
Σ
Σ
p
Xx-Ta
K
n
k= i=1
47

---

Under review as a conference paper at ICLR 2020
(o²
+
JaT
20l.
E
Σ
PiKk Th.
n
nk
k==
i=1
Note that
2
E
Σ
=B
=
VF X )l
Moving it to the left side, we finally get
K-
E E
+
(1- 2aL
1
K
E
V F (Xx (x 111
K
n
K
k=0
k=0
2n(J(0) -n)
2L K-1
(Xx
Xx- ) n
+
E
aK
K
n
k=0
12aL
K-1 K
( 1n - ei )1²
+ (0² + aa
+ 2L
P:B
Xk-Th
n
k=0
1=1
That completes the proof.
Lemma 21 For all k 2 O, we have
2T2 K-1
1 2
Σ E
(X
Xk-TA)
Xx
K
k=0
2a 2
2
K
Ln
ei -
Σ
p:lE
Xx-
n²K
71
4a
2
K-1
Σ
E
Σ
Pigk Tk.d
2
K
k=0
Proof From Lemma 20
we know the fact
1n
Xx)(Wa 11 1n
X Xx
+ (Qx
aGk-m = Xx at
As result
K-
1n
E
Xx
X
K
1n
E
Σ
aG
K=U
A=1
K-1
Tk
1
Tk
E
G k-
8
0=
1=1
K-1
02
<a²
Tk
Σ
P. 11a6- 1.1
112
1
k=0
1=1
2 27
2T
K-1
E.E. 1 1
2
2
k=0
1=1
1=1
2T2gK K
a 2T
K-
1 ej || + 65 + 2
127.2
P.E.
X
Pt 1,8
2
n
k=
t=1
i=1
1=1
2TTKPK
a 2T
K-1
1n
e, )
121 2
P.E.
Xx-
+ 65 + 2E
Σ
P.gk T2.8
n
1=1
1=1
48

---

Under review as a conference paper at ICLR 2020
a (o² + 6
a
K
In
P.E
X
n?
n²
12
n2
k=0
i=1
2a
2a
K
n
+
n²
E
Pigk
k=0
i=1
And we get
2T2 K
1
(Xx
Xk- m
K
71
km0
2a 2a?
+ 652 )
FAL*a2T"
K
Ln
es |
D:l
Xx
112
neK
k=0 1=1
2 L K
n²K
Pigk -k
That completes the proof.
Lemma 22 Given non-negative sequences {ae (brle and {Ta] and a positive number T that satisfying
1-7
Σ
p
b.
with S < 1.we have
(2 p)T
S
4 S
Σ b
1 P
1=1
(2 T2
D2 Σ
Σ 12
4 5
(1- pp-
Proof
4: 1-T
k
k
1.00)
max((
b 1.00
S₁
a:
pl
I=1
k
k-7g-9
k
k
TT
x
k
T T
Σ
Σ
p
Σ
b S
Σ
m
b
+
Tk
b
Σ b
sm1
1=0
1=0
m
D₁
6
b,br
t=1
t=
r=1
12
+2
f-
18?
k
p
5
pm
T
Us
(2 - 2) k
cs6 <
S
82
(1 - p) am1
Lemma 23 for Vi,j and wk 2 0, we have
[Xa(es - -2i)lss 0 161mix
49

---

Under review as a conference paper at ICLR 2020
Proof Similar to Section F
and Section
G we mathmatical induction to prove this.
1. First, for l = O, we have
[e - -x)llle;)ll>_ S 1Gx s0
II. Suppose for k 2 O, we have
- 0. Vt S k. then have
Xx++ - -ei)lo0
In -
1n - es, |
Xk+1
E/
Xx+1
11
100
n
inin Xx+1
1ntn
|e:ll1 +
Xx+1
I
|ee/ll
n
1,00
n
1,20
1n1 I Xx+1
-2
1,00
1n
2
X WR k
-aGk k- +5(
Ei
1,000
1n 1
-2
Σ
aGrim + S()
II 1=t++1
Wg
1=0
1,20
1 1, 1
2
-ati- + Sl))
II 1=1++1
Wg
n
1,00
1
-aGi-n + S2
II
Wg
1,00
1=0
1=t+1
<4(0Goo + 260)
Σ
2 ((k- [X)mm)/)mixx]
t=0
fmix -1
<4(0Goo + 2250)
2
t=0
r=0
<8(0Gxo + fmix
Put in 8 32fmme' we obtain
(Xx+1(e;-c))l) S 8(aGoc + fmix Ol + Slanixa 16t
Combining I and II and complete the proof.
50


Reviews:
[{"review_id": "Hyl8Hk66KS", "reviewer": "AnonReviewer3", "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 considers training of DL models in a decentralized setting. Previous work (Tang et al 2018b, Koloskova et al 2019, Tang et al 2019) introduced communication compression in order to reduce communication cost in decentralized SGD. This paper shows that the naive way to apply quantization to compress communication can fail (but, none of the previous works used this naive way). The paper proposes a novel decentralized SGD algorithm called MONIQUA which communicates only with compressed vectors. The paper theoretically proves that MONIQUA asymptotically converges with the same speed as D-PSGD (Decentralized SGD with full communications) for non-convex functions. \nThe main benefit of the proposed algorithm is that in contrast to the baselines, MONIQUA doesn’t require any additional memory and computation overhead connected to that. \nThe paper also allow to combine MONIQUA with asynchronous communications (AD-PSGD) and decentralized data (D^2), which is novel, previous baseline didn’t allow asynchronous communications. Paper experimentally validates MONIQUA and show that it converges faster than the baselines on early optimization stage, but omit comparison of final results.\n\nMy score is weak reject. The method is interesting and elegant, doesn’t require additional memory, theoretically convergent with a good speed and allows asynchronous communication. However, it looks a bit incremental. In contrast to the baselines, MONIQUA does not support arbitrary communication compression. Experimental comparison is shown only for the beginning of the optimization where the algorithm doesn’t achieve state of the art accuracy. \n\nMajor concerns: \n\n1. Superior experimental results are shown only for (i) the constant stepsize schedule and (ii) only in the beginning of the optimization. The algorithm is unable to achieve s.o.t.a. test accuracy and has severe accuracy drop of 10-20%. It is unclear if MONIQUA is able to close the accuracy gap. \nTo get good test accuracy the exponentially decaying learning rate schedules are usually used when training ResNet on Cifar10. However, that is unclear if this learning rate schedule could be supported by the algorithm. I see that theoretically the same result would be not possible. Once the learning rate dropped, ||x_i - x_j|| has to be smaller than the new theta, which is not true. \n\n2. In contrast to the baselines, MONIQUA doesn’t support arbitrary quantization. The quantization level is fixed. For example, for the ring 8 case (which was used in experiments), the number of bits required to converge is at least 5 (I calculated it using expression for B on page 5). This also questions if MONIQUA will be able to converge to good accuracy in extreme bit-budget. \n\n\nOther concerns that should be addressed: \n\n3. The spectral gap is usually not a constant: for example for the ring topology it decreases as 1/n^2. That should be clarified in the convergence rate and the number of bits required to communicate. \n\n4. In the experiments, to ensure fair comparison, the tuning details of the averaging rate for DeepSqueeze and Choco baselines, and theta parameter for MONIQUA were not given.\n\n5. Reproducibility of the experiments: Many experimental details are omitted: \n   - What are the values of hyperparameters used in the plots?\n   - How did you model asynchrony in experiments?\n   - How did you choose the parameter \\theta in experiments?\n\n6. In (1), why x is \\in [-1, 1]^d? What if this assumption doesn’t hold in (4)? The Theorem 1 is not clear then.\n\n7. Why taking mod \\theta is required? Cannot you assume that ||Q(x) - x|| <= theta delta? The whole analysis will stay true.\n\n8. In Asynchronous communication section, why \\tau_k are the same for all the workers? Cannot different workers have different delays? \n\n9. Why in experiments D-PSGD doesn’t converge when the data are decentralized? This is not consistent with the theory, D-PSGD should converge just slower. \n\nQuestions: \n10. Is there a way to compute theta it in practice beforehand? \n\nMinor comments: \n- x mod y is not defined when x is a float number.\n- Intuition behind Moniqua: do you assume that worker 1 has only one neighbour (worker 2)? does m_1 is one dimensional or high dimensional? \n- Algorithm 1, the notation \\bar X_k might be confusing as in the proof big letters correspond to matrixes. Consider to change on \\bar x_k.\n- why some equations are numbered and some are not? \n- In Asynchronous communication section: what are the assumptions on W_k? \n- it would be helpful for the clarity to remind what is the stochastic rounding quantization in configuration of experiments section. \n- which are the other algorithms you talk about in footnote 6? \n- In wall-clock time evaluation section: how floored outputs could be represented as 16-bit integers? aren’t the vectors which you quantize always smaller than one? \n- wall-clock time evaluation section: the statement that “algorithms diverge” might be confusing.\n- Aggressive quantization add  ”.”\n- why the number of epochs differ in different experiments? Fig. 3(a) and Fig. 4(a) ?\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 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": "Bke4EFvwcr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 work is about the use of quantized communication in decentralized stochastic gradient descent. The general advantage of using quantized communication is that is has the potential to reduce the amount of data exchanged, thereby leading to faster convergence -- and the main focus of this work is to include ideas that stem from quantized communication into decentralized training approaches. Competing methods of this kind suffer from potentially severe problems like memory overhead, limited applicability to convex problems, or the need for nonlinear quatizers.\n\nThe proposed Moniqua algorithm is an attempt to overcome these shortcomings. A central technical contribution is the analysis of direct quantization strategies in decentralized SGD in Theorem 1, which basically states that local models can fail to converge even for simple objective functions. The motivation for the Moniqua algorithm -- which is designed to solve this problem of local models -- is rather intuitive, and the algorithm can be implemented quite easily in practice. Some theoretic insight is provided, such as the asymptotic convergence rate (which is the same as in D-PSGD) and the loglog(n)-bound on the number of bits per parameter communicated as a function of the number of parallel workers.\n\nMoniqua is empirically evaluated on a large number of different network configurations, and it seems that it indeed converges faster than other related algorithms, while being highly robust to aggressive quantization and strict bit-budgets. In summary, this work addresses a highly relevant problem and it nicely combines formal asymptotic analysis with experimental validation. I think, this work has indeed a great potential to advance this field of research. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJlhW4Q6FS", "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 an important problem in the decentralized optimization, i.e., communication compression. Unlike gradient compression, the model compression in decentralized optimization is more challenging because the model parameters will not vanish like gradient. To solve this problem, the authors proposed Moniqua, where only lower-order bits of model are communicated since their higher-order bits are getting close. A hyperparameter $\\theta$ is used as a “criterion” to separate the higher-order bits and lower-order bits of the model parameter via a modular arithmetic. The authors also apply Moniqua on D^2 and AD-PSGD.\n\nThere are several major concerns:\n1.\tIt is not clear how the performance is measured in this paper. If the authors simply take the average of training loss over all nodes, this is not a good evaluation unless consensus is achieved. Unless clarifying this, it is hard to judge the performance. \n2.\tIt is better to provide evaluation on the consensus error which meansures the model consistency.\n3.\tThe modular hyperparameter $\\theta$ is not easy to choose and seems cannot help achieve consensus. On the one hand, the theory suggests its value to be proportional to the gradient magnitude bound, which could be very large in practice. But if $\\theta$ is large, we cannot achieve even approximate consensus because of the quantization error. On the other hand, a small $\\theta$ cannot ensure sufficient model average since higher-order bits are ignored by the modular arithmetic but actually they should be communicated. Either way, it doesn’t seem to be good for achieving consensus. \n\nOverall, the idea of Moniqua is interesting and the authors provide useful extensions based on it. But the evaluation is not convincing and whether the proposed Moniqua can achieve consensus is unclear.\n\n\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": "B1eLpFlt2r", "reviewer": "AnonReviewer4", "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 papers proposed an interesting idea for distributed decentralized training with quantized communication. The authors show that naively compressing the exchanged model can fail to converge, and introduce to compress the model difference with modulo operation. The idea is further applied to decentralized data and asynchronous optimization settings. Convergence analyses are provided for non-convex problems. \n\nThough I found this paper interesting and novel, I have several concerns:\n\n1. There is no convincing explanation why modulo operation makes the algorithm better. In particular, the equation $((m_2)_j - (m_1)_j) \\text{mod} \\theta = (m_2)_j - (m_1)_j$ does not hold. For example, let $(m_2)_j = 5$, $(m_1)_j = 3$ and $\\theta=2$, then $((m_2)_j - (m_1)_j) \\text{mod} \\theta = (5 - 3) \\text{mod} 2 = 0$ and $(m_2)_j - (m_1)_j = 5- 3 = 2$.\n\n2. The proposed algorithm requires knowledge of $\\theta$, which depends on the upper bound of gradient. If $\\theta$ is underestimated, the algorithm will suffer from large errors. For instance, suppose that true $\\theta$ is $5$ while we use $4.5$, then an identity quantizer cannot even recover the original value, e.g., $(5/4.5) \\text{mod} 1*4.5 = 0.5 << 5$. On the other hand, if $\\theta$ is overestimated, the convergence is dramatically slowed down. I checked authors' response to Reviewer 3 regarding this issue. However, they are not efficient and can still provide wrong estimates.\n\n3. The upper bound of staleness is missing in the main text and convergence bound. I found that bounded delay is assumed in the supplementary. However, the constant for bounded delay is missing in Theorem 4.\n\n4. The experiments are not convincing. In particular, Figure 2 shows that all the quantization methods perform very bad with low bits format. The centralized method DoubleSqueeze uses error feedback and supports arbitrary compression. Based on my experience, even with the 1-bit quantizer introduced in (Karimireddy et al., 2019), DoubleSqueeze converges as fast as full precision SGD. Also, it seems that final test accuracy of D-PSGD on ResNet110 is just 80+, which is much lower than its official 93.6% test accuracy. This indicates that experiments are not appropriately done.\n\n5. CIFAR-10 is a very small scale dataset. For distributed training, it is more convincing to conduct experiments on larger datasets such as ImageNet.\n\nThey are a lot of typos. The authors need to double check.\n\nKarimireddy et al., Error Feedback Fixes SignSGD and other Gradient Compression Schemes. ICML 2019.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This papers proposed an interesting idea for distributed decentralized training with quantized communication. The method is interesting and elegant. However, it is incremental, does not support arbitrary communication compression, and does not have a convincing explanation why modulo operation makes the algorithm better. The experiments are not convincing. Comparison is shown only for the beginning of the optimization where the algorithm does not achieve state of the art accuracy. Moreover, the modular hyperparameter is not easy to choose and seems cannot help achieve consensus.
Decision: Reject