Title: MONIQUA: MODULO QUANTIZED COMMUNICATION IN DECENTRALIZED

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 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-budgets, allowing less than 4-bits-per-parameter communication without affecting convergence when training VGG16 on CIFAR10.

1. INTRODUCTION:

Stochastic gradient descent (SGD), as a widely adopted optimization algorithm for machine learning, has shown promising performance when running at large scale (Zhang, 2004; Bottou, 2010; Dean et al., 2012; Goyal et al., 2017) . However, the communication bottleneck among workers1 when running distributed SGD presents a non-trivial challenge (Alistarh, 2018) . State-of-the-art frameworks such as TensorFlow (Abadi et al., 2016) , CNTK (Seide and Agarwal, 2016) and MXNet (Chen et al., 2015) are built in a centralized fashion, where workers exchange gradients either via a 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.e. high latency or low bandwidth, it 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; b; Tang et al., 2018a; Hendrikx et al., 2018) and (2) quantized communication2 (Zhang et al., 2017; Alistarh et al., 2017; Wen et al., 2017) . In decentralized training, all the workers are connected to form a 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 be 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 et al., 2018; Zhang et al., 2017; Wang et al., 2018) . This is especially useful when the communication bandwidth is restricted.

At this point, a natural question is: Can we apply quantized communication to decentralized training, and thus benefit 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 et 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 et 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 solved this problem by adding an error tracker to compensate quantization errors (Tang et al., 2019) or adding replicas of neighboring models and focusing on quantizing model difference which does approach zero (Koloskova et al., 2019; Tang et 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 to model size (more details in Section 2); and (2) these methods are 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 et 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 w 1 updates its model parameter m 1 by averaging with a neighboring worker w 2 's model parameter m 2 :

m 1 ← 1 2 (m 1 + m 2 ). Note that 1 2 (m 1 + m 2 ) = m 1 + 1 2 (m 2 -m 1 )

, so averaging is equivalent to letting w 1 obtain m 2 -m 1 (same logic for w 2 ). Since m 1 and m 2 will approach the same local optimum as the algorithm converges, we can expect the higher-order bits of m 1 and m 2 to get close. Then we can save communication by having w 2 not communicate those higher-order bits to w 1 . More explicitly, if we know that m 1 -m 2 ∞ ≤ θ for some known parameter θ (later we will show it can be derived in theory), then instead of sending the entire model m 2 which might cause overhead, w 2 can just send its j-th coordinate (m 2 ) j as (m 2 ) j mod θ (∀j ∈ [d] ). Note that given m 1 -m 2 ∞ ≤ θ:

(m 2 ) j mod θ -(m 1 ) j mod θ = ((m 2 ) j -(m 2 ) j ) mod θ = (m 2 ) j -(m 2 ) j so w 1 can obtain the j-th coordinate of m 2 -m 1 by locally computing (m 2 ) j mod θ -(m 1 ) j mod θ with (m 2 ) j mod θ received from w 2 . Since (m 2 ) j mod θ is generally a smaller number than (m 2 ) j , w 2 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, a general algorithm that uses modular arithmetic for communication quantization in decentralized training. We prove applying Moniqua achieves the same asymptotic convergence rate as the baseline full-precision algorithm (D-PSGD) while requiring at most O(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 (D 2 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 bitbudgets, and we introduce techniques we found empirically useful to run Moniqua even more efficiently. (Section 6)

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 largescale machine learning, D-PSGD was the first Decentralized SGD algorithm that enjoys the same asymptotic convergence rate O(1/ √ Kn) (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 D 2 , which improves D-PSGD and is applicable to the case where workers are not sampling from identical data sources (Tang et al., 2018a) . Another extension was AD-PSGD, which lets workers communicate asynchronously and has a convergence rate of O(1/ √ K) (Lian et al., 2017b) . In this paper we prove that Moniqua is applicable to all of these three algorithms. Other relevant work includes: He et al. (2018) , which investigates decentralized learning on linear models; Nazari et al. (2019) , which introduces decentralized algorithms with online learning; Zhang and You (2019) , which analyzes the case when workers cannot mutually communicate; and Assran et al. (2018) , which investigates Decentralized SGD specifically for deep learning.

Quantized Communication in Centralized SGD Prior research on quantized communication is often focused on centralized algorithms, such as randomized quantization (Doan et al., 2018; Suresh et al., 2017; Zhang et al., 2017) and randomized sparsification (Wangni et al., 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 et al., 2018) . Alistarh et al. (2017) proposes QSGD, which uses an encoding-efficient scheme, and discusses its communication complexity. Another method, 1bitSGD, 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; Stich et al., 2018) . Acharya et al. (2019) theoretically analyzes sublinear communication for distributed training. Quantized Communication in Decentralized SGD Quantized communication for decentralized algorithms is a rising topic in the optimization community. Previous work has proposed decentralized algorithms with quantized communication for strongly convex objectives (Reisizadeh et al., 2018; 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. (2019) proposes DeepSqueeze, which applies an error-compensation method (Wu et al., 2018b) to decentralized setting. From a systems perspective, Koloskova et al. (2019) and Tang et al. (2018b) 

3. SETTING AND NOTATION:

In this section, we introduce our notation and the general assumptions we will make about the quantizers for our results to hold. Then we describe D-PSGD (Lian et al., 2017a) , 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 a quantizer Q δ that has bounded error

Q δ (x) -x ∞ ≤ δ, ∀x ∈ [-1, 1] d (1)

where δ is some constant. In general, a smaller δ denotes more fine-grained quantization requiring more bits. For example, a biased linear quantizer can achieve (1) by rounding x to the nearest number in the set {2δn | n ∈ Z}; this will require about δ -1 quantization points to cover the interval [-1, 1], so such a linear quantizer can satisfy (1) using only log 2 1 δ + 1 bits (Li et al., 2017; Gupta et al., 2015) . Note that (1) can be satisfied (for appropriate values of δ) by both linear (Gupta et al., 2015; De Sa et al., 2017) and non-linear (Stich, 2018; Alistarh et al., 2017) 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 (Lian 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 i stores a copy of model x ∈ R d and a local dataset D i and collaborates to optimize

EQUATION

where ξ is data sample from D i . In each iteration of D-PSGD, worker i computes a local gradient sample using D i . Then it averages its model parameters with its neighbors according to a symmetric and doubly stochastic matrix W , where W ij denotes the ratio worker j averages from worker i. Formally: Let x k,i and g k,i denote local model and sampled gradient on worker i at k-th iteration, respectively. Let α denote the step size. The update rule of D-PSGD can be expressed as:

x k+1,i = n j=1 x k,j W ji -α g k,i = x k,i - n j=1 (x k,i -x k,j )W ji communicate to reduce difference -α g k,i

gradient step

(3)

From (3) we can see the update of a 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.

Failure with direct quantization. Here, we illustrate why directly quantizing communication in decentralized training -naively quantizing the exchanged data-can fail to converge asymptotically even on a simple problem. This naive approach with quantizer Q δ can be represented by

EQUATION

Based on Equation 4, we obtain the following theorem.

Theorem 1 For some constant δ, suppose that we use an unbiased linear quantizer Q with representable points {δn | n ∈ Z} to learn on the quadratic objective function f (x) = (x -δ/2) (xδ/2)/2 with the direct quantization approach (4). Let φ denote the smallest value of a non-zero entry in W . Regardless of what step size we adopt, it will always hold for all iterations k and local model indices

i that E ∇f (x k,i ) 2 ≥ φ 2 δ 2 8(1+φ 2 )

. That is, the local iterates will fail to asymptotically converge to a region of small gradient magnitude in expectation.

4. MONIQUA:

Theorem 1 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, we propose a technique, Moniqua, that solves this problem. Moniqua works under the following common assumptions for analyzing decentralized optimization algorithms (Lian et al., 2017a; Tang et al., 2018b; Koloskova et al., 2019) .

(A1) Lipschitzian gradient. All the functions f i have L-Lipschitzian gradients. 

∇f i (x) -∇f i (y) ≤ L x -y , ∀x, y ∈ R d (A2)

E ξi∼Di ∇ f i (x; ξ i ) -∇f i (x) 2 ≤ σ 2 , E i∼{1,••• ,n} ∇f i (x) -∇f (x) 2 ≤ ς 2

where ∇ f i (x; ξ i ) denotes gradient sample on worker i computed via data sample ξ i . (A4) Initialization. All the local models are initialized by the same weight: x 0,i = x 0 , for all i and without loss of generality x 0 = 0. (A5) Bounded gradient magnitude. The norm of a sampled gradient is bounded by g k,i ∞ ≤ G ∞ , for all i and k with some constant G ∞ .

In Section 1, we described how a modulo operation can be used to avoid sending redundant bits if a bound θ on model difference is known. Here we outline how we can obtain such a bound. We do so by leveraging the following insight: in decentralized training, all the workers initialize local models at 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 is reduced each time they communicate. Since we have an upper bound on the magnitude of the gradients (A5) as well as a bound characterizing how quickly the communication process converges (A2), we can combine these to get an a priori bound θ on how much the models can differ. We can then pass this bound θ as a parameter to the algorithm, which can proceed to modulo-quantize the communication via the process described in Section 1. We formalize this approach as Moniqua (Algorithm 1).

Algorithm 1 Pseudo-code of Moniqua on worker i Input: initial point x 0,i = x 0 , step size α, the priori bound θ, communication matrix W , number of iterations K, quantizer Q δ , neighbor list

N i 1: for k = 0, 1, 2, • • • , K -1 do 2:

Compute a local stochastic gradient g k,i with data sample ξ k,i and current weight x k,i

3::

Compute modulo-ed model:

q k,i ← θ • Q δ x k,i

θ mod 1 (element-wise division and mod) 4:

Average with neighboring workers:

x k+ 1 2 ,i ← x k,i + j∈Ni (q k,j -q k,i )W ji 5:

Update the local weight with local gradient:

x k+1,i ← x k+ 1 2 ,i -α g k,i 6: end for Output: Averaged model X K = 1 n n i=1 x K,i

In line 3 we rescale each coordinate so that the number to be quantized falls in the region of [-1, 1], which is required for (1) to apply. Note that with quantization, the priori bound θ could increase since local models may move further apart due to quantization error. However, with appropriately chosen δ, 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 2 If we run Algorithm 1 in a setting where

θ = 2 log(16n)αG ∞ 1 -ρ , δ = 1 -ρ 4 log(16n)

, and α = 1

ς 2/3 K 1/3 + σ K/n + 2L ,

then the output of Algorithm 1 converges at the asymptotic rate

1 K K-1 k=0 E ∇f (X k ) 2 1 K + σ √ nK + ς 2 3 K 2 3 + σ 2 n σ 2 K + n + G 2 ∞ dn σ 2 K + n .

where ρ, f (0) -f * and L are omitted as constants.

Consistent with D-PSGD. Note that D-PSGD converges at the asymptotic rate of O(σ/ √ nK + ς 23 /K 2 3 + n/K), and thus Moniqua has the same asymptotic rate as D-PSGD (Lian et al., 2017a) . In other words, the asymptotic convergence rate is not negatively impacted by the quantization.

Robust to large d. In Assumptions (A3) and (A5), we use l 2 -norm and l ∞ -norm to bound sample variance and gradient magnitude, respectively. Note that, when d gets larger, the variance σ 2 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 (Q δ ). If we use nearest rounding (Gupta et al., 2015) as Q δ in Theorem 2, it suffices to use at each step a number of bits B for each parameter sent, where

B = log 2 1 δ + 1 = log 2 4 log 2 (16n) 1-ρ + 1

Note that this bound is independent of model dimension d. When the system scales up, the number of required bits grows at a rate of O (log log n).

5. SCALABLE MONIQUA:

Previous work has extended D-PSGD to D 2 (Tang et al., 2018a) (to make Decentralized SGD applicable to workers sampling from different data sources) and AD-PSGD (Lian et al., 2017b) (an asynchronous version of D-PSGD). In 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 i are not identically distributed (Tang et al., 2018a) . More explicitly, the outer variance

E i∼{1,••• ,n} ∇f i (x) -∇f (x)

2 is no longer bounded by ς 2 as assumed in D-PSGD (Assumption (A3)). This update rule presented can be explicitly expressed in two steps 3 :

X k+ 1 2 = 2X k -X k-1 -α G k + α G k-1 X k+1 = X k+ 1 2 W + (Q k -X k+ 1 2 )(W -I)

where X k , G k and Q k are matrix in the shape of R d×n , where their i-th column are x k,i , g k,i and q k,i respectively. And X -1 and G -1 are 0 d×n by convention. Based on this, we obtain the following convergence theorem. Theorem 3 If we run D 2 with Monqiua in a setting where

θ = (6D 1 n + 8)αG ∞ , δ = 1 6nD 2

, and α = 1

σ K/n + 2L ,

where D 1 and D 2 are two constants that only depend on the eigenvalues of W (definition can be found in supplementary material), the output has the following asymptotic convergence rate:

1 K K-1 k=0 E ∇f (X k ) 2 1 K + σ √ nK + σ 2 n σ 2 K + n + G 2 ∞ dn σ 2 K + n .

Note that D 2 (Tang et al., 2018a) with full-precision communication has the asymptotic convergence rate of O 1/K + σ/ √ nK + n/K , Moniqua on D 2 has the same asymptotic rate.

Moniqua with Asychronous Communication. Both D-PSGD and D 2 are synchronous algorithms as they require global synchronization at the end of each iteration, which can become a bottleneck when such synchronization is not cheap. Another algorithm, AD-PSGD, avoids this overhead by letting workers communicate asynchronously (Lian et al., 2017b) . In the analysis of AD-PSGD, an iteration represents a single gradient update on one randomly-chosen worker, rather than a synchronous bulk update of all the workers. This single-worker-update analysis models the asynchronous nature of the algorithm. We apply Moniqua to AD-PSGD and obtain the following update rule4 :

X k+1 = X k W k + (Q k -X k )(W k -I) -α G k-τ k

where W k describes the communication behaviour between the kth and (k + 1)th gradient update, and τ k denotes the delay (measured as a number of iterations) between when the gradient is computed and updated to the model. Note that unlike D-PSGD, here W k can be different at each update step and usually each individually has ρ = 1, so we can't expect to get a bound in terms of a bound on the spectral gap, as we did in Theorems 2 and 3. Instead, we require the following condition, which is inspired by the literature on Markov chain Monte Carlo methods: for some constant t mix ,

∀µ ∈ R n , ∀k ∈ N, if µ i ≥ 0 and 1 µ = 1, it must hold that tmix i=1 W k+i µ -1 n 1 ≤ 1 2 .

We call this constant t mix because it is effectively the mixing time of the time-inhomogeneous Markov chain with transition probability matrix W k at time k (Levin and Peres, 2017). Note that this condition is more general than those used in previous work on AD-PSGD because it does not require that the W k 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 a setting where

θ = 16t mix αG ∞ , δ = 1 32t mix

, and α = n

2L + K(σ 2 + 6ς 2 ) ,

the output has the following asymptotic convergence rate:

1 K K-1 k=0 E ∇f (X k ) 2 1 K + √ σ 2 + 6ς 2 √ K + (σ 2 + 6ς 2 )t 2 mix n 2 (σ 2 + 6ς 2 )K + 1 + n 2 t 2 mix G 2 ∞ d (σ 2 + 6ς 2 )K + 1

Note that AD-PSGD (Lian et al., 2017b) 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 running Ubuntu 16.04, and latency and bandwidth on the underlying network are configured using the tc command in Linux. In all the experiments, we use the following hyperparameters by default: batch size = 128, weight decay = 1e -4, and momentum = 0.9, which are default values adopted in previous works (Lian et al., 2017b; Grubic et al., 2018) . We tune the step size from set {0.5, 0.1, 0.05, 0.01} for each algorithm. Throughout our experiments, we adopt the commonly used (Gupta et al., 2015; Li et al., 2017 ) stochastic rounding5 with quantization step δ. 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 a ResNet110 (He et al., 2016) model on CIFAR10 (Krizhevsky et al., 2014) . We compare Moniqua with the following baselines:6 Centralized (implemented as a standard AllReduce operation), D-PSGD (Lian et al., 2017a) with full-precision communication, DCD/ECD-PSGD (Tang et 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, we use 16-bit integers7 torch.int16 as the floored output on the sender side. For Moniqua, we set θ = 3.0.

We plot our results in Figure 1 . As can be seen in Figure 1 (a), with respect to epochs, All the algorithms have similar convergence curve while DCD/ECD-PSGD have slightly slower convergence curves. We can see from Figures 1(b ) and 1(c) that when the network bandwidth decreases, the curves begin to separate. AllReduce and full-precision D-PSGD suffer the most, since they require a large volume of high-precision exchanged data. And from 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, Scalability of Moniqua. We evaluate how Moniqua can be applied to D 2 (Tang et al., 2018a) and AD-PSGD (Lian et al., 2017b) . First, we demonstrate how applying Moniqua to D 2 can handle decentralized data. We launch 10 workers, collaborating to train a VGG16 (Simonyan and Zisserman, 2014) model on CIFAR10. Similar to the setting of D 2 (Tang et al., 2018a) , we let each worker have exclusive access to 1 labels (of the 10 labels total in CIFAR10). In this way, the data variance among workers is maximized. We plot the results in Figure 3 (a). We observe that applying Moniqua on D 2 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 is the same in comparison of Moniqua and Centralized algorithm in Figure 1 .

Next, we evaluate Moniqua on AD-PSGD. We launch 6 workers organized in a ring topology, collaborating to train a ResNet110 model on CIFAR10. 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 we have observed to improve the performance of Moniqua when using stochastic rounding:

Q δ (x) = δ x δ + u (where u is uniformly sampled from [0, 1]), ∀x ∈ R d .

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 x and y respectively, then the floored tensors x δ + u and y δ + u they send use the same randomly sampled value u. This provably reduces the error due to quantization (more details are in the supplementary material). The second technique is to use a 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 a traditional compression algorithm can easily remove.

To evaluate these methods, we train both ResNet110 and VGG16 on CIFAR10 using 8 ring-connected workers. We plot the training loss under different θ in Figure 4 (with δ = 0.01 for stochastic rounding). Note that for VGG16, it can tolerate small θ = 0.08 while still preserving the convergence rate. On the other hand, for ResNet110, it begins to diverge when θ decreases to 0.5. This is because VGG16 has more fully connected layers than ResNet110, 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 ResNet110 to guarantee convergence (accuracy loss < 0.3%, criterion adopted by (Grubic et al., 2018) ) are 3.64 and 5.67, respectively (details in the supplementary material).

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-communication algorithms without incurring storage or computation overhead. Empirically, we observe Moniqua converges faster than other related algorithms with respect to wall clock time. Additionally, Moniqua is robust to very low bits-budget.

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, we provably explain why using shared randomness in communication with stochastic rounding can improve performance (theoretical explanation for technique 1 in Experiment Efficient Moniqua). Then we demonstrate more experimental results in Section C. In Section D, we illustrate why naively quantizing communication in D-PSGD fails to converge asymptotically, as a proof to Theorem 1. In Section E, we introduce some useful tools of modeling communication as a 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 2, 3 and 4 from Section F to H, with corollaries contained in the corresponding sections. Detailed algorithm statements for applying Moniqua on D 2 and AD-PSGD can be found in Section G Algorithm 2 and Section H Algorithm 3, 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 z quantized using Q, let z f = z -z , the variance of quantization error can be expressed as

EQUATION

Note that in Moniqua, the term asssociate with quantization error is

E (q k,j -x k,j ) -(q k,i -x k,i ) 2 We now show for ∀x, y ∈ R d E (Q(x) -x) -(Q(y) -y) 2 = E Q(y -x) -(y -x) 2

With out the loss of generality, let x -x ≤ y -y . Let x f = x -x and y f = y -y , then

x + u = x and y + u = y , with probability y -y x + u = x and y + u = y , with probability x -x x + u = x and y + u = y , with probability ( x -x) -( y -y)

Then we have

E (Q(x) -x) -(Q(y) -y) 2 =E δ x δ + u -x -δ y δ + u -y 2 =( y -y)(( x -x) -( y -y)) 2 + (x -x )(( x -x) -( y -y)) 2 +(( x -x) -( y -y))(( x -x) -( y -y)) 2 =(1 -y f )(x f -y f ) 2 + (x f )(x f -y f ) + (y f -x f )(y f -x f -1) 2 =(1 -y f + x f )(y f -x f ) 2 + (y f -x f )(y f -x f -1) 2 =(1 -y f + x f )(y f -x f ) =E Q(y -x) -(y -x) 2

The last equality holds due to equation 5. Next, let

∆ = y -x r = Q(∆) -∆

And let r h denote h-th entry of r, let ∆ h denote h-th entry of ∆. We obtain

r h =Q(∆ h ) -∆ h =δ -∆ h δ + ∆ h δ + 1, p t ≤ ∆ h δ -∆ h δ -∆ h δ + ∆ h δ , otherwise =δ -q + 1, p t ≤ q -q, otherwise where q = ∆ h δ - ∆ h δ , q ∈ [0, 1]

Based on that, we have

E r 2 h ≤δ 2 ((-q + 1) 2 q + (-q) 2 (1 -q)) =δ 2 q(1 -q) ≤δ 2 min{q, 1 -q} Since min{q, 1 -q} ≤ x h δ , we have E r 2 h ≤ δ 2 ∆ h δ ≤ δ |∆ h | Summing over the index h yields, E r 2 2 ≤ δE ∆ 1 ≤ √ dδE ∆ 2

Pushing back x and r, we have

E Q(y -x) -(y -x) 2 ≤ √ dδE y -x = √ dδE x -y

Putting it back we have

E (Q(x) -x) -(Q(y) -y) 2 ≤ √ dδE x -y

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 two models on adjacent workers. In such a 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, we 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 a ring topology):

#bits = BW #neighbors • #workers • #params of model

In our experiments, #neighbors=2, #workers=8. For VGG16, #params of model= 15,245,130 while for ResNet110, #params of model=1,146,842. We formalize the results in Table C .18 .

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)

Q(x) = δ x δ + 0.5

where δ is the quantization step as defined in the linear quantizer. In this experiment, we set δ = 0.01, the same value as we used in the paper with stochastic rounding. 

Q(x) =

x, with probability p 0, with probability 1 -p

In this experiment, we set p = 0.7.

We train ResNet110 on CIFAR10, 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-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 more result of training ResNet110 and VGG16 on CIFAR10 under different δ and θ in the experiment of aggressive quantization. And we plot the results in Figure 5 We report the results in experiment of "Aggressive Quantization" and report the test error and test accuracy in the Figure 5 and Figure 6 . 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 ResNet110 and ResNet18 on CIFAR10. The hyperparameters of Moniqua are: ResNet110 (Initial step size = 0.05, θ = 3.0, batch size = 128, weight decay = 3e -4, and momentum = 0.9) and ResNet18 (Initial step size = 0.1, θ = 2.5, batch size = 128, weight decay = 1e -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 7 . We can see from Figure 7 (a) 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 a 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 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 (ResNet110). We can see that compared to the baselines, Moniqua is generally robust to low bits-budget. (Some of the dots are missing for some algorithms, that means they do not converge under the corresponding bits-budget.)

Results of Consensus Error. To better measure the behaviour of workers reaching consensus, we define the consensus error at iteration k: C k as follows (Notations are the same as in the original paper):

EQUATION

Note that C k is essentially the running average of distance among workers and the averaged model. Trivially, a decreasing C k indicates the workers are reaching consensus. We measure the consensus error in three aspects. We first provide the results of the original paper in Figure 9 (a), where constant step size is adopted. We can see 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 can see in Figure 9 (b) and Figure 9 (c) that all the workers are able to reach consensus. The update rule of naive quantization on D-PSGD is

x k+1,i = x k,i W ii + n j=1,j =i Q(x k,j )W ji -α k g k,i = x k,i + n j=1,j =i (Q(x k,j ) -x k,i )W ji -α k g k,i

where α k is allowed to vary with any policy. Let

X k = [x k,1 , • • • , x k,n ] ∈ R d×n Ω k =   j =1 W j1 (Q(x k,j ) -x k,1 ) , • • • , j =n W jn (Q(x k,j ) -x k,n )   ∈ R d×n G k = [ g k,1 , • • • , g k,n ] ∈ R d×n

by rewritting the update rule, we obtain 

X k+1 = X k + Ω k -α k G k Let Y k = X k -x * 1 n ,

Y k+1 e i = Y k e i + Ω k e i -α k Y k e i + α k G k -G k e i

where G k -G k denotes variance in the gradient sampling.

Suppose that by using the update rule of naive quantization, worker i converges to x * . Then there must exist a K such that ∀k ≥ K,

E Y k+1 e i 2 ≤ E Y k e i 2 < φ 2 δ 2 8(1 + φ 2 ) (7)

Next we show that this assumption lets us derive a contradiction. Firstly, considering the property of linear quantizer,

δ 2 4 ≤ E Q(x k,i ) -x * 2 ≤ 2E Q(x k,i ) -x k,i 2 + 2E x k,i -x * 2

As a result

E Q(x k,i ) -x k,i 2 ≥ δ 2 8 - φ 2 δ 2 8(1 + φ 2 ) = δ 2 8(1 + φ 2 ) Since Q is unbiased, that means E[Q(x) -x] = 0, then we have E Ω k e i 2 =E j =i W ji (Q(x k,j ) -x k,i ) 2 = j∈Ni W 2 ji E (Q(x k,j ) -x k,i ) 2 + m =n =i E (Q(x k,m ) -x k,i ) W mi , (Q(x k,n ) -x k,i ) W ni ≥φ 2 j∈Ni E (Q(x k,j ) -x k,i ) 2 + m =n =i E (Q(x k,m ) -x k,i ) W mi , (Q(x k,n ) -x k,i ) W ni ( * ) = φ 2 j∈Ni E Q(x k,j ) -x k,i 2 ≥ φ 2 δ 2 8(1 + φ 2 )

where step ( * ) holds due to unbiased quantizer. Putting it back to the update rule, we obtain

E Y k+1 e i 2 =E Y k + Ω k -α k Y k + α k G k -G k e i 2 ( * ) = E (1 -α k )Y k e i 2 + E Ω k e i 2 + E α k G k -G k e i 2 ≥E Ω k e i 2 ≥ φ 2 δ 2 8(1 + φ 2 )

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

φ 2 δ 2 8(1+φ 2 ) ≤ E x k+1 -x * 2 < φ 2 δ 2 8(1+φ 2 ) . That being said, for ∀k, i E x k,i -x * 2 = E ∇f (x k,i ) 2 ≥ φ 2 δ 2 8(1 + φ 2 )

Thus we complete the proof.

E A MARKOV CHAIN ANALYSIS ON THE COMMUNICATION:

To better understand how the parallel workers reach consensus over a communication matrix, in this section we use theory from the analysis of Markov Chains to obtain some useful lemmas for proof of Moniqua on D-PSGD and AD-PSGD.

Since the communication matrix W is doubly stochastic (each row and column sum to 1), it has the same structure as the transition matrix of a Markov Chain with 1n n as its the stationary distribution W 1n n = 1n n . Now let t mix and d(t) denote the mixing time and maximal distance between initial state and stationary distribution as defined in Markov Chain theory.9 

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 1

W t I - 1 n 1 n n 1 ≤ 2 • 2 - t t mix

Proof For ∀x ∈ R d , let u ∈ R d be such a vector that every entry of u is the positive entry of x and 0 otherwise. Let v ∈ R d be such a vector that every entry of v is the absolute value of negative entry of x and 0 otherwise. The setting above means x = u -v. For example,

x = [2, -1] u = [2, 0] v = [0, 1]

And we have

W t I - 1 n 1 n n x 1 = W t I - 1 n 1 n n (u -v) 1 ≤ W t I - 1 n 1 n n u 1 + W t I - 1 n 1 n n v 1 =1 n u W t u 1 n u - 1 n n 1 + 1 n v W t v 1 n v - 1 n n 1 ≤2(1 n u + 1 n v)d(t) ≤2d(t) x 1

Considering the definition of L1-norm, we have

W t I - 1 n 1 n n 1 = max W t I - 1n1 n n x 1 x 1 ≤ 2d(t)

According to a well-known results on the theory of Markov Chains, 10 d(lt mix ) ≤ 2 -l holds for any non-negative integer l, so we have

W t I - 1 n 1 n n 1 ≤ 2d(t) ≤ 2d t t mix • t mix ≤ 2d t t mix t mix ≤ 2 • 2 - t t mix

That completes the proof.

Additionally, based on standard results in the theory of reversible Markov Chains, we also have 11

t mix ≤ log 1 1 4 • 1 n 1 1 -ρ ≤ log(4n) 1 -ρ .

E.2 AD-PSGD:

Note that unlike D-PSGD, here W k can be different at each update step and usually each individually have spectral radius ρ = 1, so we can't expect to get a bound in terms of a bound on the spectral gap as we did in Theorems 2 and 3. Instead, we require the following condition, which is inspired by the literature on Markov chain Monte Carlo methods: for some constant t mix (here t mix is the same as t mix in the paper) and for any k and any non-negative vector µ ∈ R d such that

1 n µ = 1, it must hold that tmix i=1 W k+i µ - 1 n n 1 ≤ 1 2 .

We call this constant t mix because it is effectively the mixing time of the time-inhomogeneous Markov chain with transition probability matrix W k at time k. Note that this condition is more general than those used in previous work on AD-PSGD because it does not require that the W k are sampled independently or in an unbiased manner. Based on the above analysis, we can prove the following lemma, which is analogous to the lemma used in the synchronous case.

Lemma 2 For any k ≥ 0 and for any b ≥ a ≥ 0, there exists t mix such that b q=a

W q I - 1 n 1 n n 1 ≤ 2 • 2 -b-a+1 t mix

10 Again, see Markov Chains and Mixing Times for more details.

11 Detailed analysis and proofs of this result can be found in chapter 12.2 of Markov Chains and Mixing Times.

Proof Note that for any x ∈ R d , and let u and v be two vectors having same definition as in Lemma 1 with respect to x, then we have for any k tmix q=1

W q+k I - 1 n 1 n n x 1 = tmix q=1 W q+k I - 1 n 1 n n (u -v) 1 ≤ tmix q=1 W q+k I - 1 n 1 n n u 1 + tmix q=1 W q+k I - 1 n 1 n n v 1 =1 n u tmix q=1 W q+k u 1 n u - 1 n n 1 + 1 n v tmix q=1 W q+k v 1 n v - 1 n n 1 ≤ 1 2 (1 n u + 1 n v) ≤ 1 2 x 1

Considering the definition of the induced 1 operator norm, we have tmix q=1

W q+k I - 1 n 1 n n 1 = max x tmix q=1 W q+k I - 1n1 n n x 1 x 1 ≤ 1 2

As a result, from the submultiplicativity of the matrix induced norm, we obtain b q=a

W q I - 1 n 1 n n 1 ≤ tmix q=1 W a-1+q I - 1 n 1 n n 1 • • • tmix q=1 W •••+q I - 1 n 1 n n 1 • tr q=1 W •••+q I - 1 n 1 n n 1 ≤2 -b-a+1 t mix tr q=1 W •••+q I - 1 n 1 n n 1

where t r = (b -a + 1) mod t mix . Note that tr q=1

W q I - 1 n 1 n n 1 ≤ 1 - 1 n + (n -1) 1 n = 2 - 2 n ≤ 2

Putting it back we obtain b q=a

W •••+q I - 1 n 1 n n 1 ≤ 2 • 2 -b-a+1 t mix

That completes the proof.

Note that in the analysis of Moniqua on AD-PSGD (Section H), 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 θ • Q δ x θ mod 1 instead of Q δ (x mod θ) for theoretical analysis and how it covers both linear and non-linear quantizers. Note that typically, a linear quantizer has:

Q δ (x) -x ∞ ≤ δ, ∀x ∈ R d mod 1 - x θ mod 1 ∞ ≤ θδ • 1 = θδ

As a result, we can use the same bound θδ for quantizers with both of the properties, which we will show in the rest of the proof.

F.1 PROOF TO THEOREM 2:

Proof For convenience, we define the following notation

X k = [x k,1 , • • • , x k,n ] , Q k = [q k,1 , • • • , q k,n ] G k = [ g k,1 , • • • , g k,n ] , G k = [g k,1 , • • • , g k,n ] X = X 1 n n , ∀X ∈ R d×n , Ω k = (Q k -X k )(W -I)

where g k,i denotes gradient computed via the whole dataset D i and x k,i

From a local view, the update rule of Algorithm 1 on worker i at iteration k can be written as

x k+1,i ← x k,i + j∈Ni (q k,j -q k,i ) W ji -α g k,i

which is equivalent to

x k+1,i = x k,i + n j=1 (x k,j -x k,i ) W ji -α g k,i + n j=1 ((q k,j -x k,j ) -(q k,i -x k,i )) W ji (8)

From a global view, the update rule can be written as

EQUATION

From Lemma 5 we have

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 4(f (0) -f * ) αK + 2αL n σ 2 + 8α 2 L 2 σ 2 + 3ς 2 (1 -ρ) 2 + 8L 2 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F Note that K-1 k=0 E Ω k 2 F = K-1 k=0 n i=1 E n j=1 ((q k,j -x k,j ) -(q k,i -x k,i )) W ji 2 Lemma 3 ≤ 4 K-1 k=0 n i=1 δ 2 θ 2 d ≤ α 2 G 2 ∞ dnK

The last step holds because δθ = 1 2 αG ∞ . Pushing it back we obtain

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 4(f (0) -f * ) αK + 2αL n σ 2 + 8α 2 L 2 σ 2 + 3ς 2 (1 -ρ) 2 + 8α 2 G 2 ∞ dL 2 (1 -ρ) 2 By setting α = 1 ς 2 3 K 1 3 +σ √ K n +2L

, we have

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 8(f (0) -f * )L K + 4σ(f (0) -f * + L/2) √ nK + 4ς 2 3 (f (0) -f * ) K 2 3 + 8L 2 σ 2 n (1 -ρ) 2 (σ 2 K + 4nL 2 ) + 24L 2 ς 2 3 (1 -ρ) 2 K 2 3 + 8L 2 G 2 ∞ dn (1 -ρ) 2 (σ 2 K + 4nL 2 ) 1 K + σ √ nK + ς 2 3 K 2 3 + σ 2 n σ 2 K + n + G 2 ∞ dn σ 2 K + n

That completes the proof of Theorem 2.

F.2 LEMMA FOR MONIQUA ON D-PSGD Lemma 3 If x t,i -x t,j ∞ ≤ θ, ∀i, j holds at iteration t, then n j=1 ((q t,j -x t,j ) -(q t,i -x t,i )) W ji ∞ ≤ 2δθ Proof n j=1 ((q t,j -x t,j ) -(q t,i -x t,i )) W ji ∞ ≤ n j=1 W ji (q t,j -x t,j ) -(q t,i -x t,i ) ∞ = n j=1 W ji θQ x t,j θ mod 1 -θQ x t,i θ mod 1 -(x t,j -x t,i ) ∞ = n j=1 W ji θQ x t,j θ mod 1 -θQ x t,j θ mod 1 -θ x t,j -x t,i θ mod 1 ∞ = n j=1 W ji θQ x t,j θ mod 1 -θ x t,j θ mod 1 -θQ x t,i θ mod 1 -θ x t,i θ mod 1 ∞ ≤ n j=1 W ji θQ x t,j θ mod 1 -θ x t,j θ mod 1 ∞ + n j=1 W ji θQ x t,i θ mod 1 -θ x t,i θ mod 1 ∞ ≤2δθ

Lemma 4 In any iteration k ≥ 0, and for any two worker i and j, we have:

X k (e i -e j ) ∞ ≤ θ = 2 log(16n) 1 -ρ αG ∞

Proof We use mathematical induction to prove this: I. When k = 0, X 0 (e i -e j ) ∞ = 0 ≤ θ, ∀i, j II. Suppose for X k (e i -e j ) ∞ ≤ θ, k ≥ 0, ∀i, j, we have

X k+1 (e i -e j ) ∞ = X k W -α G k + Ω k (e i -e j ) ∞ X0=0 = k t=0 -α G t + Ω t W k-t (e i -e j ) ∞ ≤ k t=0 -α G t + Ω t W k-t (e i -e j ) ∞ ≤ k t=0 -α G t + Ω t 1,∞ W k-t (e i -e j ) 1 ≤ k t=0 α G t 1,∞ + Ω t 1,∞ W k-t (e i -e j ) 1 induction hypothesis ≤ (αG ∞ + 2δθ) k t=0 W k-t (e i -e j ) 1 ≤ (αG ∞ + 2δθ) ∞ t=0 W t (e i -e j ) 1

For any t ≥ 0, on one hand

W t (e i -e j ) 1 ≤ √ n W t (e i -e j ) 2 ≤ √ n W t e i - 1 n n + √ n W t e j - 1 n n ≤ 2 √ nρ t

where the last step holds due to the diagonalizability of W . On the other hand,

W t (e i -e j ) 1 ≤ 1 n W t e i + 1 n W t e i = 1 n e i + 1 n e j = 2 So W t (e i -e j ) 1 ≤ min{2 √ nρ t , 2} Let T 0 = -log( √ n) log(ρ)

, so that nρ T0 ≤ 1, then we have

∞ t=0 W t (e i -e j ) 1 = T0-1 t=0 W t (e i -e j ) 1 + ∞ t=T0 W t (e i -e j ) 1 ≤ T0-1 t=0 2 + ∞ t=0 2 √ nρ t+T0 ≤2 -log( √ n) log(ρ) + ∞ t=0 2 √ nρ T0 ρ t ≤ 2 log( √ n) 1 -ρ + 2 + 2 1 -ρ ≤ log(16n) 1 -ρ As a result, we have X k+1 (e i -e j ) ∞ ≤ (αG ∞ + 2δθ) log(16n) 1 -ρ Since δ = 1-ρ 4 log(16n) , we have X k+1 (e i -e j ) ∞ ≤ (αG ∞ + 2δθ) log(16n) 1 -ρ ≤ 2 log(16n) 1 -ρ αG ∞ = θ

Combining I and II, we complete the proof.

Lemma 5 The output of Algorithm 1 has the following bound:

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 4(f (0) -f * ) αK + 2αL n σ 2 + 8α 2 L 2 σ 2 + 3ς 2 (1 -ρ) 2 + 8L 2 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F

Proof From Lemma 8, we have

1 -αL K K-1 k=0 E G k 2 + 1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + L 2 nK K-1 k=0 n i=1 E X k -x k,i 2 Lemma 6 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 2α 2 L 2 M 1 (1 -ρ) 2 σ 2 + 3ς 2 + 3 K K-1 k=0 E ∇f (X k ) 2 + 2L 2 M 1 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F

where

M 1 = 1 - 6α 2 L 2 (1 -ρ) 2

Rearrange the terms, we get

1 -αL K K-1 k=0 E G k 2 + 1 - 6α 2 L 2 M 1 (1 -ρ) 2 1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 2α 2 L 2 σ 2 + 3ς 2 M 1 (1 -ρ) 2 + 2L 2 M 1 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F Let M 2 = 1 - 6α 2 L 2 M 1 (1 -ρ) 2 we get 1 -αL K K-1 k=0 E G k 2 + M 2 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 2α 2 L 2 σ 2 + 3ς 2 M 1 (1 -ρ) 2 + 2L 2 M 1 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F Let M 1 , M 2 ≥ 1

2 and rearrange the terms, we have

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 4(f (0) -f * ) αK + 2αL n σ 2 + 8α 2 L 2 σ 2 + 3ς 2 (1 -ρ) 2 + 8L 2 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F

and that completes the proof

Lemma 6 Let M 1 = 1 -6α 2 L 2 (1-ρ) 2 > 0, we have L 2 nK K-1 k=0 n i=1 E X k -x k,i 2 ≤ 2α 2 L 2 M 1 (1 -ρ) 2 σ 2 + 3ς 2 + 3 K K-1 k=0 E ∇f (X k ) 2 + 2L 2 M 1 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F Proof K-1 k=0 n i=1 E X k -x k,i 2 = K-1 k=1 n i=1 E X k 1 n n -e i 2 = K-1 k=1 n i=1 E X k-1 W -α G k-1 + Ω k-1 1 n n -e i 2 x0,i=0 = K-1 k=1 n i=1 E k-1 t=0 -α G t + Ω t 1 n n -W k-t-1 e i 2 ≤2α 2 K-1 k=1 n i=1 E k-1 t=0 G t 1 n n -W k-t-1 e i 2 + 2 K-1 k=1 n i=1 E k-1 t=0 Ω t 1 n n -W k-t-1 e i 2 =2α 2 K-1 k=1 E k-1 t=0 G t 1 n 1 n n -W k-t-1 2 F + 2 K-1 k=1 E k-1 t=0 Ω t 1 n 1 n n -W k-t-1 2 F Lemma 10 ≤ 2α 2 K-1 k=1 E k-1 t=0 ρ k-t-1 G t F 2 + 2 K-1 k=1 E k-1 t=0 ρ k-t-1 Ω t F 2 Lemma 9 ≤ 2α 2 (1 -ρ) 2 K-1 k=1 E G k 2 F + 2 (1 -ρ) 2 K-1 k=1 E Ω k 2 F Lemma 7 ≤ 2α 2 (1 -ρ) 2 nσ 2 K + 3L 2 K-1 k=0 n i=1 E X k -x k,i 2 + 3nς 2 K + 3n K-1 k=0 E ∇f (X k ) 2 + 2 (1 -ρ) 2 K-1 k=1 E Ω k 2 F

Rearrange the terms, we have

1 - 6α 2 L 2 (1 -ρ) 2 K-1 k=0 n i=1 E X k -x k,i 2 ≤ 2α 2 (1 -ρ) 2 nσ 2 K + 3nς 2 K + 3n K-1 k=0 E ∇f (X k ) 2 + 2 (1 -ρ) 2 K-1 k=1 E Ω k 2 F Let M 1 = 1 -6α 2 L 2 (1-ρ) 2 > 0, we have L 2 nK K-1 k=0 n i=1 E X k -x k,i 2 ≤ 2α 2 L 2 M 1 (1 -ρ) 2 σ 2 + 3ς 2 + 3 K K-1 k=0 E ∇f (X k ) 2 + 2L 2 M 1 nK(1 -ρ) 2 K-1 k=1 E Ω k 2 F Lemma 7 K-1 k=0 E G k 2 F ≤ nσ 2 K + 3L 2 K-1 k=0 n i=1 E X k -x k,i 2 + 3nς 2 K + 3n K-1 k=0 E ∇f (X k ) 2

Proof From the property of Frobenius norm, we have

EQUATION

Next, we derive the upper bound of E g k,i

EQUATION

Proof Let 1 n denote a n-dimensional vector with all the entries be 1. And we have

X k+1 = (X k W -α G k + Ω k ) 1 n n = X k -α G k + (Q k -X k )(W -I) 1 n n = X k -α G k

And by Taylor Expansion, we have

Ef (X k+1 ) = Ef (X k W -α G k + Ω k )1 n n = Ef X k -α G k ≤ Ef (X k ) -αE ∇f (X k ), G k + α 2 L 2 E G k 2

And for the last term, we have

E G k 2 = E n i=1 g k,i n 2 = E n i=1 g k,i - n i=1 g k,i n + n i=1 g k,i n 2 = E n i=1 g k,i - n i=1 g k,i n 2 + E n i=1 g k,i n 2 +E n i=1 g k,i - n i=1 g k,i n + n i=1 g k,i n = E n i=1 g k,i - n i=1 g k,i n 2 + E n i=1 g k,i n 2 Assumption (A3) = 1 n 2 n i=1 E g k,i -g k,i 2 + E n i=1 g k,i n 2 Assumption (A3) ≤ σ 2 n + E n i=1 g k,i n 2

Putting it back, we obtain

EQUATION

putting it back, we have

EQUATION

summing over from k = 0 to K -1 on both sides, we have

EQUATION

That completes the proof.

Lemma 9 Given two non-negative sequences {a t } ∞ t=1 and {b t } ∞ t=1 that satisfying

a t = t s=1 ρ t-s b s with 0 ≤ ρ < 1,we have S k = k t=1 a t ≤ 1 1 -ρ k s=1 b s D k = k t=1 a 2 t ≤ 1 (1 -ρ) 2 k s=1 b 2 s Proof S k = k t=1 a t = k t=1 t s=1 ρ t-s b s = k s=1 k t=s ρ t-s b s = k s=1 k-s t=0 ρ t b s ≤ 1 1 -ρ k s=1 b s D k = k t=1 a t = k t=1 t s=1 ρ t-s b s t r=1 ρ t-r b r = k s=1 k t=s ρ t-s b s = k t=1 t s=1 t r=1 ρ 2t-s-r b s b r ≤ k t=1 t s=1 t r=1 ρ 2t-s-r b 2 s + b 2 r 2 = k t=1 t s=1 t r=1 ρ 2t-s-r b 2 s ≤ 1 1 -ρ k t=1 t s=1 ρ t-s b 2 s ≤ 1 (1 -ρ) 2 k s=1 b 2 s Lemma 10 For any X t ∈ R d×n , we have k-1 t=0 X t 1 n 1 n n -W k-t-1 2 F ≤ k-1 t=0 ρ k-t-1 X t F 2 Proof k-1 t=0 X t 1 n 1 n n -W k-t-1 2 F = k-1 t=0 X t 1 n 1 n n -W k-t-1 F 2 ≤ k-1 t=0 X t 1 n 1 n n -W k-t-1 F 2 ≤ k-1 t=0 X t F 1 n 1 n n -W k-t-1 2 ≤ k-1 t=0 ρ k-t-1 X t F 2

That completes the proof.

G MONIQUA ON D 2 (PROOF TO THEOREM 3)

G.1 ALGORITHM Algorithm 2 Moniqua with Variance Reduction on worker i Input: initial point x 0,i = x 0 , step size α, the discrepency bound θ, communication matrix W , number of iterations K, neighbor list of worker i:

N i 1: for k = 0, 1, 2, • • • , K -1 do 2:

Randomly sample data ξ k,i from local memory 3:

Compute a local stochastic gradient based on ξ k,i and current weight x k,i : g k,i 4:

if k = 0 then 5: Update local weight: x k+ 1 2 ,i ← x k,i -α g k,i

6:

else 7:

Update local weight:

x k+ 1 2 ,i ← 2x k,i -x k-1,i -α g k,i + α g k-1,i 8: end if 9:

Compute modulo-ed model:

q k,i ← θ • Q δ x k+ 1 2 ,i

θ mod 1 (element-wise division and mod) 10:

Average with neighboring workers:: x k+1,i ← x k+ 1 2 ,i + j∈Ni (q k,j -q k,i )W ji 11: end for Output:

X K = 1 n n i=1 x K,i

G.2 ASSUMPTIONS D 2 makes the following assumptions (1-4), and we add the additional assumption (5):

1. Lipschitzian Gradient: All the function f i have L-Lipschitzian gradients.

2.. Communication:

Matrix: Communication matrix W is a symmetric doubly stochastic matrix. Let the eigenvalues of W ∈ R n×n be λ 1 ≥ • • • ≥ λ n . We assume λ 2 < 1, λ n > -1 3 .

3. Bounded Variance:

E ξi∼Di ∇ f i (x i ; ξ i ) -∇f i (x) 2 ≤ σ 2 , ∀i

where ∇ f i (x; ξ i ) denotes gradient sample on worker i computed via data sample ξ i .

4. Initialization: All the models are initialized by the same parameters: x 0,i = x 0 , ∀i and with out the loss of generality x 0 = 0.

5.. Gradient magnitude::

The norm of a sampled gradient is bounded by

g k,i ∞ ≤ G ∞ for some constant G ∞ .

G.3 PROOF TO THEOREM 3:

Proof From a local view, define x -1 = g -1 = 0, the update rule of Moniqua on D 2 on worker i in iteration k can be written as

x k+ 1 2 ,i = 2x k,i -x k-1,i -α g k,i + α g k-1,i x k+1,i = n j=1 x k+ 1 2 ,j W ji + n j=1 (q k,j -x k+ 1 2 ,j ) -(q k,i -x k+ 1 2 ,i ) W ji

From a global view, the update rule can be written as

X k+ 1 2 = 2X k -X k-1 -α G k + α G k-1 X k+1 = X k+ 1 2 W + (Q k -X k+ 1 2 )(W -I) Define Ω k = (Q k -X k+ 1

2 )(W -I) Since W is symmetric, it can be diagonalized as W = P ΛP , where the i-th column of P and Λ are W 's i-th eigenvector and eigenvalue, respectively. And we obtain

X k+1 = 2X k P ΛP -X k-1 P ΛP -α G k P ΛP + α G k-1 P ΛP + Ω k and X k+1 P = 2X k P Λ -X k-1 P Λ -α G k P Λ + α G k-1 P Λ + Ω k P Denote Y k = X k P , H(X k ; ξ k ) = G k P ,

and denote y k,i , h k,i and r k,i as the i-th column of Y k , H k and Ω k P , respectively. Then we have

y k+1,i = λ i (2y k,i -y k-1,i -αh k,i + αh k-1,i ) + r k,i

From Lemma 15 (Constants C 1 , C 2 , C 3 andn C 4 are defined in the Lemma 11. Constants D 1 and D 2 are defined in Lemma 15) we get

1 - 3C 1 α 2 L 2 C 4 E ∇f (0) + 1 -αL -3 C 2 C 4 α 4 L 4 1 K K-1 k=1 E G k 2 + 1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 3C 1 α 2 L 2 (σ 2 + ς 2 0 ) C 4 K + 6 C 2 C 4 α 2 σ 2 L 2 + 3 C 2 nC 4 α 4 σ 2 L 4 + C 3 L 2 C 4 3D 1 n + 4 3D 2 n 2 α 2 G 2 ∞ d Let α = 1 σ √ K/n+2L

, we have

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 3C 1 α 2 L 2 (σ 2 + ς 2 0 ) C 4 K + 6 C 2 C 4 α 2 σ 2 L 2 + 3 C 2 nC 4 α 4 σ 2 L 4 + 3D 1 n + 4 3D 2 n 2 C 3 L 2 C 4 G 2 ∞ dα 2 ≤ 4(f (0) -f * )L K + 2σ(f (0) -f * + L/2) √ nK + 3C 1 L 2 (σ 2 + ς 2 0 )n C 4 (σ 2 K 2 + 4nL 2 K) + 6C 2 L 2 σ 2 n C 4 (σ 2 K + 4nL 2 ) + 3C 2 nσ 2 L 2 C 4 (σ 4 K 2 + 16n 2 L 4 ) + 3D 1 n + 4 3D 2 n 2 C 3 G 2 ∞ dL 2 n C 4 (σ 2 K + 4nL 2 ) 1 K + σ √ nK + (σ 2 + ς 2 0 )n σ 2 K 2 + nK + σ 2 n σ 2 K + n + σ 2 n σ 4 K 2 + n 2 + G 2 ∞ dn σ 2 K + n 1 K + σ √ nK + σ 2 n σ 2 K + n + G 2 ∞ dn σ 2 K + n That completes the proof. G.4 LEMMA FOR D 2 Lemma 11 Define D 1 = max |v n | + 2|λ n | 1 -|v n | , λ 2 1 -λ 2 + 2λ 2 1 -λ 2 D 2 = max 2 1 -|v n | , 2 √ 1 -λ 2 v n = λ n -λ 2 n -λ n Let δ = 1

6nD2 , and we have for ∀i, j

x k+ 1 2 (e i -e j ) ∞ ≤ θ = (6D 1 n + 8)αG ∞

Proof We use mathematical induction to prove this:

I. When k = 0, X 0+ 1 2 (e i -e j ) ∞ = -α G 0 (e i -e j ) ∞ ≤ α G 0 1,∞ e i -e j 1 ≤ 2αG ∞ ≤ (6D 1 n + 8)αG ∞ II. Suppose for k ≥ 0, ∀t ≤ k, we have X t+ 1 2 (e i -e j ) ≤ (6D 1 n + 8)αG ∞ , then for ∀i, j X k+1 (e i -e j ) ∞ ≤ X k+1 1 n n -e i ∞ + X k+1 1 n n -e j ∞ = X k+1 P P e i -X k+1 P       1 0 0 . . . 0 0 0 0 . . . 0 0 0 0 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 0       P e i ∞ + X k+1 P P e j -X k+1 P       1 0 0 . . . 0 0 0 0 . . . 0 0 0 0 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 0       P e j ∞ ≤ X k+1 P       0 0 0 . . . 0 0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1       1,∞ P e i 1 + X k+1 P       0 0 0 . . . 0 0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1       1,∞ P e j 1 ≤2 √ n X k+1 P       0 0 0 . . . 0 0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1       1,∞

From the update rule, we have

y k+1,i = λ i (2y k,i -y k-1,i -αh k,i + αh k-1,i ) + r k,i = λ i (2y k,i -y k-1,i ) + λ i β k,i + r k,i whereβ k,i = -αh k,i + αh k-1,i

, for all y i with -1 3 < λ i < 0, from Lemma 13 we have

y k+1,i = y 1,i u k+1 i -v k+1 i u i -v i + k s=1 (λ i β s,i + r s,i ) u k-s+1 i -v k-s+1 i u i -v i where u i = λ i + λ 2 i -λ i and v i = λ i -λ 2 i -λ i , we obtain y k+1,i ∞ ≤ y 1,i ∞ u k+1 i -v k+1 i u i -v i + |λ i | k s=1 β s,i ∞ u k-s+1 i -v k-s+1 i u i -v i + k s=1 r s,i ∞ u k-s+1 i -v k-s+1 i u i -v i Since u n+1 i -v n+1 i u i -v i ≤ |v i | n u i ui vi n -v i u i -v i ≤ |v i | n We obtain y k+1,i ∞ ≤ y 1,i ∞ |v i | k + |λ i | k s=1 β s,i ∞ |v i | k-s + k s=1 r s,i ∞ |v i | k-s

For β s,i , we have

β s,i ∞ = -αh k,i + αh k-1,i ∞ ≤ 2α( h k,i ∞ + h k-1,i ∞ ) ≤2α( G k 1,∞ P e i 1 + G k-1 1,∞ P e i 1 ) ≤2α √ nG ∞ For r s,i , we have r k,i ∞ = Ω k P e i ∞ ≤ Ω k 1,∞ P e i 1 ≤ 2 √ nδθ when λ i < 0, we have y k+1,i ∞ ≤ y 1,i ∞ |v i | k + |λ i | k s=1 β s,i ∞ |v i | k-s + k s=1 r s,i ∞ |v i | k-s ≤ y 1,i ∞ |v n | k + |λ n | k s=1 β s,i ∞ |v n | k-s + k s=1 r s,i ∞ |v n | k-s ≤α √ nG ∞ |v n | k + 2α √ nG ∞ |λ n | ∞ s=1 |v n | k-s + 2 √ nδθ ∞ s=1 |v n | k-s ≤α √ nG ∞ |v n | + 2α √ nG ∞ |λ n | 1 -|v n | + 2 √ nδθ 1 -|v n | where v n = λ n -λ 2 n -λ n .

On the other hand, when 0 ≤ λ i < 1, from Lemma 13 we have

y k+1,i sin θ i =y 1,i λ k 2 i sin[(t + 1)θ i ] + λ i k s=1 β s,i λ k-s 2 i sin[(k + 1 -s)θ i ] + k s=1 r s,i λ k-s 2 i sin[(k + 1 -s)θ i ]

By taking norm, we get

y k+1,i ∞ | sin θ i | = y 1,i ∞ λ k 2 i | sin[(t + 1)θ i ]| + λ i k s=1 β s,i ∞ |λ k-s 2 i || sin[(k + 1 -s)θ i ]| + k s=1 r s,i ∞ |λ k-s 2 i || sin[(k + 1 -s)θ i ]| ≤ y 1,i ∞ λ k 2 2 + 2α √ nG ∞ λ 2 ∞ s=1 λ s 2 2 + 2 √ nδθ ∞ s=1 λ s 2 2 ≤ α √ nG ∞ λ 2 + 2α √ nG ∞ λ 2 + 2 √ nδθ √ 1 -λ 2 Since | sin θ i | ≥ √ 1 -λ 2 , putting it back, we get y k+1,i ≤ α √ nG ∞ λ 2 1 -λ 2 + 2α √ nG ∞ λ 2 + 2 √ nδθ 1 -λ 2 So there exists D 1 , D 2 D 1 = max |v n | + 2|λ n | 1 -|v n | , λ 2 1 -λ 2 + 2λ 2 1 -λ 2 D 2 = max 2 1 -|v n | , 2 √ 1 -λ 2 such that y k+1,i ∞ ≤ D 1 α √ nG ∞ + D 2 √ nδθ

Putting it back we have ∀i, j

X k+1 (e i -e j ) ∞ ≤ D 1 αnG ∞ + D 2 nδθ

As a result

X k+ 1 2 (e i -e j ) ∞ = (2X k -X k-1 -α G k + α G k-1 )(e i -e j ) ∞ ≤2 X k (e i -e j ) ∞ + X k-1 (e i -e j ) ∞ + α G k 1,∞ e i -e j 1 + α G k-1 1,∞ e i -e j 1 ≤3(D 1 αnG ∞ + D 2 nδθ) + 4αG ∞ ≤(6D 1 n + 8)αG ∞

The last step is because δ = 1 6nD2

Combining I and II we complete the proof. Lemma 12

EQUATION

From the update rule, we obtain,

y k+1,i = λ i (2y k,i -y k-1,i -αh k,i + αh k-1,i ) + r k,i = λ i (2y k,i -y k-1,i ) + λ i β k,i + r k,i

whereβ k,i = -αh k,i + αh k-1,i , for all y i with -1 3 < λ i < 0, from Lemma 13 we have

y k+1,i = y 1,i u k+1 i -v k+1 i u i -v i + k s=1 (λ i β s,i + r k,i ) u k-s+1 i -v k-s+1 i u i -v i where u i = λ i + λ 2 i -λ i and v i = λ i -λ 2 i -λ i , we obtain y k+1,i 2 ≤ 3 y 1,i 2 u k+1 i -v k+1 i u i -v i 2 + 3λ 2 i k s=1 β s,i u k-s+1 i -v k-s+1 i u i -v i 2 + 3 k s=1 r s,i u k-s+1 i -v k-s+1 i u i -v i 2 Since u n+1 i -v n+1 i u i -v i ≤ |v i | n u i ui vi n -v i u i -v i ≤ |v i | n

We obtain

y k+1,i 2 ≤ 3 y 1,i 2 |v i | 2t + 3λ 2 i k s=1 β s,i |v i | k-s 2 + 3 k s=1 r s,i |v i | k-s 2

Summing over from k = 0 to t = K -1, we obtain

K-1 k=0 y k+1,i 2 = K k=1 y k,i 2 ≤3 y 1,i 2 K-1 k=0 |v i | 2k + 3λ 2 i K-1 k=1 k s=1 β s,i |v i | k-s 2 + 3 K-1 k=1 k s=1 r s,i |v i | k-s 2 ≤ 3 y 1,i 2 1 -|v i | 2 + 3λ 2 i (1 -|v i |) 2 K-1 k=1 β k,i 2 + 3 (1 -|v i |) 2 K-1 k=1 r k,i 2 ≤ 3 y 1,i 2 1 -|v n | 2 + 3λ 2 n (1 -|v n |) 2 K-1 k=1 β k,i 2 + 3 (1 -|v n |) 2 K-1 k=1 r k,i 2 where v n = λ n -λ 2

n -λ n . On the other hand, when 0 ≤ λ i < 1, from Lemma 13 we have

y k+1,i sin θ i =y 1,i λ k 2 i sin[(t + 1)θ i ] + λ i k s=1 β s,i λ k-s 2 i sin[(k + 1 -s)θ i ] + k s=1 r s,i λ k-s 2 i sin[(k + 1 -s)θ i ]

And we have

y k+1,i 2 sin 2 θ i ≤ 3 y 1,i 2 λ k i sin 2 [(t + 1)θ i ] + 3λ 2 i k s=1 β s,i λ k-s 2 i sin[(k + 1 -s)θ i ] 2 + 3 k s=1 r s,i λ k-s 2 i sin[(k + 1 -s)θ i ] 2 ≤ 3 y 1,i 2 λ k i + 3λ 2 i k s=1 β s,i λ k-s 2 i 2 + 3 k s=1 r s,i λ k-s 2 i 2

Summing from k = 0 to K -1, we have

EQUATION

Since sin 2 θ i = 1 -λ i , we have

EQUATION

By taking expectation we have

EQUATION

We next analyze β k,i :

n i=2 E β k,i 2 =α 2 n i=2 E h k,i -h k-1,i 2 =α 2 n i=2 E G k P e i -G k-1 P e i 2 ≤α 2 n i=1 E G k P e i -G k-1 P e i 2 ≤α 2 E G k P -G k-1 P 2 F Lemma 14 ≤ α 2 E G k -G k-1 2 F =α 2 n i=1 E G k e i -G k-1 e i 2 ≤3α 2 n i=1 E G k e i -G k e i 2 + 3α 2 n i=1 E G k-1 e i -G k-1 e i 2 +3α 2 n i=1 E G k e i -G k-1 e i 2 ≤6α 2 nσ 2 + 3α 2 n i=1 E G k e i -G k-1 e i 2 ≤6α 2 nσ 2 + 3α 2 L 2 n i=1 E x k,i -x k-1,i 2 ≤6α 2 nσ 2 + 3α 2 L 2 n i=1 E Y k P e i -Y k-1 P e i 2 ≤6α 2 nσ 2 + 3α 2 L 2 E Y k P -Y k-1 P 2 F Lemma 14 ≤ 6α 2 nσ 2 + 3α 2 L 2 E Y k -Y k-1 2 F ≤6α 2 nσ 2 + 3α 2 L 2 n i=1 E y k,i -y k-1,i 2

And Putting it back, we have

n i=2 K k=1 E y k,i 2 ≤C 1 E Y 1 2 F + C 2 n i=2 K-1 k=1 E β k,i 2 + C 3 K-1 k=1 n i=2 E r k,i 2 ≤C 1 E Y 1 2 F + C 2 K-1 k=1 6α 2 nσ 2 + 3α 2 L 2 n i=1 E y k,i -y k-1,i 2 + C 3 K-1 k=1 n i=2 E r k,i 2 Lemma 14 ≤ C 1 E Y 1 2 F + 6C 2 α 2 nσ 2 K + 3C 2 α 2 L 2 K-1 k=1 n i=1 E y k,i -y k-1,i 2 + C 3 K-1 k=1 E Ω k 2 F Since E y k,1 -y k-1,1 2 = E X k P e 1 -X k-1 P e 1 2 = E X k v 1 -X k-1 v 1 2 =E X k 1 √ n 1 n -X k-1 1 √ n 1 n 2 = nE X k -X k-1 2 = nα 2 E G k 2 ≤nα 2 E G k -G k 2 + nα 2 E G k 2 ≤ nα 2 σ 2 n + nα 2 E G k 2 =α 2 σ 2 + nα 2 E G k 2

Putting it back, and we obtain

n i=2 K k=1 E y k,i 2 ≤C 1 E Y 1 2 F + 6C 2 α 2 nσ 2 K + 3C 2 α 4 σ 2 L 2 K + 3C 2 α 4 nL 2 K-1 k=1 E G k 2 +3C 2 α 2 L 2 K-1 k=1 n i=2 E y k,i -y k-1,i 2 + C 3 K-1 k=1 E Ω k 2 F ≤C 1 E Y 1 2 F + 6C 2 α 2 nσ 2 K + 3C 2 α 4 σ 2 L 2 K + 3C 2 α 4 nL 2 K-1 k=1 E G k 2 +6C 2 α 2 L 2 K-1 k=1 n i=2 E y k,i 2 + y k-1,i 2 + C 3 K-1 k=1 E Ω k 2 F ≤C 1 E Y 1 2 F + 6C 2 α 2 nσ 2 K + 3C 2 α 4 σ 2 L 2 K + 3C 2 α 4 nL 2 K-1 k=1 E G k 2 +12C 2 α 2 L 2 K-1 k=1 n i=2 E y k,i 2 + C 3 K-1 k=1 E Ω k 2 F

Rearrange the terms, we get

(1 -12C 2 α 2 L 2 ) n i=2 K k=1 E y k,i 2 ≤C 1 E Y 1 2 F + 6C 2 α 2 nσ 2 K + 3C 2 α 4 σ 2 L 2 K + 3C 2 α 4 nL 2 K-1 k=1 E G k 2 + C 3 K-1 k=1 E Ω k 2 F ≤C 1 E X 1 2 F + 6C 2 α 2 nσ 2 K + 3C 2 α 4 σ 2 L 2 K + 3C 2 α 4 nL 2 K-1 k=1 E G k 2 + C 3 K-1 k=1 E Ω k 2 F Considering E X 1 2 F = α 2 E G 0 2 F = α 2 n i=1 E G 0,i -G 0,i + G 0,i -∇f (0) + ∇f (0) 2 ≤ 3α 2 n i=1 E G 0,i -G 0,i 2 + 3α 2 n i=1 E G 0,i -∇f (0) 2 + 3α 2 n i=1 E ∇f (0) 2 ≤ 3α 2 nσ 2 + 3α 2 nς 2 0 + 3α 2 nE ∇f (0) We finally get (1 -12C 2 α 2 L 2 ) n i=2 K k=1 E y k,i 2 =(1 -12C 2 α 2 L 2 ) n i=1 K k=1 E X k -x k,i 2 ≤3C 1 α 2 nσ 2 + 3C 1 α 2 nς 2 0 + 3C 1 α 2 nE ∇f (0) + 6C 2 α 2 nσ 2 K + 3C 2 α 4 σ 2 L 2 K +3C 2 α 4 nL 2 K-1 k=1 E G k 2 + C 3 K-1 k=1 E Ω k 2 F

That completes the proof.

Lemma 13 Given ρ ∈ -1 3 , 0 ∪ (0, 1), for any two sequence {a t } ∞ t=1 , {b t } ∞ t=1 and {c t } ∞ t=1 that satisfying

a 0 = b 0 = 0, a t+1 = ρ (2a t -a t-1 ) + b t -b t-1 + c t , ∀t ≥ 1 we have a t+1 = a 1 u t+1 -v t+1 u -v + t s=1 (b s -b s-1 + c s ) u t-s+1 -v t-s+1 u -v , ∀t ≥ 0 where u = ρ + ρ 2 -ρ, v = ρ -ρ 2 -ρ Moreover, if 0 < ρ < 1, we have a t+1 = a 1 ρ t 2 sin[(t + 1)θ] sin θ + t s=1 (b s -b s-1 + c s )ρ t-s 2 sin[(t -s + 1)θ] sin θ where θ = arccos ( √ ρ)

Proof when t ≥ 1, we have

a t+1 = 2ρa t -ρa t-1 + b t -b t-1 + c t since, u = ρ + ρ 2 -ρ, v = ρ -ρ 2 -ρ Proof n i=2 X t v i 2 ≤ n i=1 X t v i 2 = X t P 2 F = T r(X t P P X t ) = T r(X t X t ) = X t 2 F

And similarly,

n i=1 XP e i 2 = XP 2 F = T r(X t P P X t ) = T r(X t X t ) = X t 2 F

That completes the proof.

Lemma 15 If we run Algorithm 2 for K iterations the following inequality holds:

1 - 3C 1 α 2 L 2 C 4 E ∇f (0) + 1 -αL -3 C 2 C 4 α 4 L 4 1 K K-1 k=1 E G k 2 + 1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 3C 1 α 2 L 2 (σ 2 + ς 2 0 ) C 4 K + 6 C 2 C 4 α 2 σ 2 L 2 + 3 C 2 nC 4 α 4 σ 2 L 4 + C 3 L 2 C 4 3D 1 n + 4 3D 2 n 2 α 2 G 2 ∞ d

where

C 1 = max 3 1 -|v n | 2 , 3 (1 -λ 2 ) 2 C 2 = max 3λ 2 n (1 -|v n |) 2 , 3λ 2 2 (1 - √ λ 2 ) 2 (1 -λ 2 ) C 3 = max 3 (1 -|v n |) 2 , 3 (1 - √ λ 2 ) 2 (1 -λ 2 ) C 4 = 1 -12C 2 α 2 L 2 Ω k e i = n j=1 (q k,j -x k+ 1 2 ,j ) -(q k,i -x k+ 1 2 ,i ) W ji Proof Since X k+1 = (2X k -X k-1 -α G k + α G k-1 )W 1 n n + (Q k -X k+ 1 2 )(W -I) 1 n n = 2X k -X k-1 -α G k + α G k-1

and we have

X k+1 -X k = X k -X k-1 -α G k + α G k-1 = X 1 -X 0 -α k t=1 ( G t -G t-1 ) = -α G k

As a result, we can reuse Lemma 8 from D-PSGD, thus we have

EQUATION

From Lemma 12 we obatin

1 -αL K K-1 k=0 E G k 2 + 1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 3C 1 α 2 L 2 (σ 2 + ς 2 0 + E ∇f (0) ) C 4 K + 6 C 2 C 4 α 2 σ 2 L 2 + 3 C 2 nC 4 α 4 σ 2 L 4 +3 C 2 C 4 α 4 L 4 1 K K-1 k=1 E G k 2 + C 3 L 2 C 4 nK K-1 k=1 E Ω k 2 F

Rearrange the terms, we get

1 - 3C 1 α 2 L 2 C 4 E ∇f (0) + 1 -αL -3 C 2 C 4 α 4 L 4 1 K K-1 k=1 E G k 2 + 1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 3C 1 α 2 L 2 (σ 2 + ς 2 0 ) C 4 K + 6 C 2 C 4 α 2 σ 2 L 2 + 3 C 2 nC 4 α 4 σ 2 L 4 + C 3 L 2 C 4 nK K-1 k=1 E Ω k 2 F Lemma 16 ≤ 2(f (0) -f * ) αK + αL n σ 2 + 3C 1 α 2 L 2 (σ 2 + ς 2 0 ) C 4 K + 6 C 2 C 4 α 2 σ 2 L 2 + 3 C 2 nC 4 α 4 σ 2 L 4 + C 3 L 2 C 4 3D 1 n + 4 3D 2 n 2 α 2 G 2 ∞ d

That completes the proof.

Lemma 16

K-1 k=0 E Ω k 2 F ≤ 3D 1 n + 4 3D 2 n 2 α 2 G 2 ∞ dnK

Proof Similar to the case in D-PSGD, we have

K-1 k=0 E Ω k 2 F = K-1 k=0 n i=1 E n j=1 (q k,j -x k+ 1 2 ,j ) -(q k,i -x k+ 1 2 ,i ) W ji 2 Lemma 3 ≤ 4 K-1 k=0 n i=1 δ 2 θ 2 d ≤ 3D 1 n + 4 3D 2 n 2 α 2 G 2 ∞ dnK

That completes the proof.

H MONIQUA ON AD-PSGD (PROOF TO THEOREM 4)

H.1 ALGORITHM Algorithm 3 Moniqua with Asynchronous Communication Input: initial point x 0,i = x 0 , step size α, the discrepency bound θ, number of iterations K, quantization function Q, initial random seed 1:

for k = 0, 1, 2, • • • , K -1 do 2:

worker i k is updating the gradient while during this iteration the global communication behaviour is written in the form of W k .

Compute a local stochastic gradient with model delayed by

τ k : g k-τ k ,i k 4: Compute modulo-ed model: q k,i k ← θ • Q δ x k,i k θ

mod 1 (element-wise division and mod)

5:

Randomly select one of the neighbors j k and average local weights with remote weights while subtracting the biased term:

x k+ 1 2 ,i k ← x k,i k + 1 2 q k,j k -1 2 q k,i k 6:

Update the local weight with local gradient:

x k+1,i k ← x k,i k -α g k-τ k ,i k 7: end for Output: X K = 1 n n i=1 x K,i

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

f (x) = n i=1 p i f i (x)

where p i is a parameter denoting the speed of i-th worker gradient updates. In the rest of the proof, we denote p = max i {p i } For simplicity, we also define the following terms

∇F (X k ) = n [p 1 g k,1 , • • • , p n g k,n ] ∈ R d×n ∇ F (X k ) = n [p 1 g k,1 , • • • , p n g k,n ] ∈ R d×n G k = [• • • , g k,i k , • • • ] G k = [• • • , g k,i k , • • • ] Λ b a = 1 n 1 n n - b q=a W q H.3 ASSUMPTION

We makes the following assumptions:

1. Lipschitzian Gradient: All the function f i have L-Lipschitzian gradients. 2. Communication Matrix 12 : The communication matrix W k is doubly stochastic for any k ≥ 0 and for any b ≥ a ≥ 0, there exists t mix such that b q=a

W q I - 1 n 1 n n 1 ≤ 2 • 2 -b-a+1 t mix

3. Bounded Variance:

E ξi∼Di ∇ f i (x i ; ξ i ) -∇f i (x) 2 ≤ σ 2 , ∀i

12 Please refer to Section E for more details

E i∼{1,••• ,n} ∇f i (x) -∇f (x) 2 ≤ ς 2 , ∀i

where ∇ f i (x; ξ i ) denotes gradient sample on worker i computed via data sample ξ i . 4. Bounded Staleness: There exists T such that τ k ≤ T, ∀k 5. Gradient magnitude: The norm of a sampled gradient is bounded by g k,i ∞ ≤ G ∞ for some constant G ∞ .

H.4 PROOF TO THEOREM 4

Proof We start from

1 K K-1 k=0 E ∇f (X k ) 2 + 1 - 2αL n 1 K K-1 k=0 E ∇F (X k-τ k ) 2 Lemma 20 ≤ 2n(f (0) -f * ) αK + (σ 2 + 6ς 2 )αL n + 2L 2 + 12αL 3 n 1 K K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 + 2L 2 K K-1 k=0 E (X k -X k-τ k )1 n n 2 Lemma 21 ≤ 2n(f (0) -f * ) αK + (σ 2 + 6ς 2 )αL n + 2α 2 T 2 (σ 2 + 6ς 2 )L 2 n 2 + 4α 2 T 2 L 2 n 2 K K-1 k=0 E n i=1 p i g k-τ k ,i 2 + 2L 2 + 12αL 3 n + 24L 4 α 2 T 2 n 2 1 K K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 Lemma 19 ≤ 2n(f (0) -f * ) αK + (σ 2 + 6ς 2 )αL n + 2α 2 T 2 (σ 2 + 6ς 2 )L 2 n 2 + 4α 2 T 2 L 2 n 2 K K-1 k=0 E n i=1 p i g k-τ k ,i 2 + 128α 2 t 2 mix L 2 A 1   (σ 2 + 6ς 2 )p + 2p K K-1 k=0 E n i=1 p i g k-τ k ,i 2 + G 2 ∞ d  

where A 1 = 1 -192pα 2 t 2 mix L 2 as defined in Lemma 19. Rearrange the terms, we get

1 K K-1 k=0 E ∇f (X k ) 2 ≤ 2n(f (0) -f * ) αK + (σ 2 + 6ς 2 )αL n + 2α 2 T 2 (σ 2 + 6ς 2 )L 2 n 2 + 128pα 2 t 2 mix L 2 A 1 (σ 2 + 6ς 2 ) + 128α 2 t 2 mix L 2 A 1 G 2 ∞ d By setting α = n 2L+ √ K(σ 2 +6ς 2 ) 1 K K-1 k=0 E ∇f (X k ) 2 1 K + √ σ 2 + 6ς 2 √ K + pt 2 mix (σ 2 + 6ς 2 )n 2 (σ 2 + 6ς 2 )K + 4L 2 + n 2 t 2 mix G 2 ∞ d (σ 2 + 6ς 2 )K + 4L 2 1 K + √ σ 2 + 6ς 2 √ K + (σ 2 + 6ς 2 )t 2 mix n 2 (σ 2 + 6ς 2 )K + 1 + n 2 t 2 mix G 2 ∞ d (σ 2 + 6ς 2 )K + 1 H.5 LEMMA FOR MONIQUA ON AD-PSGD Lemma 17 E G k-τ k 1 n n 2 ≤ σ 2 n 2 + 1 n 2 n i=1 p i E g k-τ k ,i 2 , ∀k ≥ 0. Lemma 19 Let A 1 = 1 -192pα 2 t 2 mix L 2 , K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 ≤ 32α 2 t 2 mix A 1   (σ 2 + 6ς 2 )pK + 2p K-1 k=0 E n i=1 p i g k-τ k ,i 2 + G 2 ∞ dK   Proof n i=1 p i E X k 1 n n -e i 2 = n i=1 p i E X k-1 W k-1 -α G k-1-τ k-1 + Ω k-1 1 n n -e i 2 X0 = 0 = n i=1 p i E k-1 t=0 -α G t-τt + Ω t Λ k-1 t+1 e i 2 ≤2 n i=1 p i E k-1 t=0 α G t-τt Λ k-1 t+1 e i 2 + 2 n i=1 p i E k-1 t=0 Ω t Λ k-1 t+1 e i 2

Now for the first term, we have

EQUATION

Summing from k = 0 to K -1 on both sides, we obtain

K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 ≤8pα 2 K-1 k=0 E k-τ k -1 t=0 G t-τt F 2 - k-τ k -t-1 t mix 2 + 2 n i=1 p i K-1 k=0 E k-τ k -1 t=0 Ω t Λ k-τ k -1 t+1 e i 2 ≤8pα 2 K-1 k=0 E k-τ k -1 t=0 G t-τt F 2 - k-τ k -t-1 t mix 2 + 2 n i=1 p i K-1 k=0 E k-τ k -1 t=0 Ω t 1,2 Λ k-τ k -1 t+1 1 e i 1 2 ≤8pα 2 K-1 k=0 E k-τ k -1 t=0 G t-τt F 2 - k-τ k -t-1 t mix 2 + 8 n i=1 p i K-1 k=0 E k-τ k -1 t=0 Ω t 1,2 2 - k-τ k -t-1 t mix 2 Lemma 22 ≤ 8pα 2 K-1 k=0 E k-τ k -1 t=0 G t-τt F 2 - k-τ k -t-1 t mix 2 + 32t 2 mix n i=1 p i K-1 k=0 E Ω k 2 1,2 ≤8pα 2 K-1 k=0 E k-τ k -1 t=0 G t-τt F 2 - k-τ k -t-1 t mix 2 + 128δ 2 θ 2 dt 2 mix K Lemma 22 ≤ 32pα 2 t 2 mix K-1 k=0 E G k-τ k 2 F + 128δ 2 θ 2 dt 2 mix K

Note that for the first term, we have

EQUATION

Putting these two terms back, we obtain

K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 ≤32pα 2 t 2 mix   (σ 2 + 6ς 2 )K + 12L 2 K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 + 2 K-1 k=0 E n i=1 p i g k-τ k ,i 2  

+128δ 2 θ 2 dt 2 mix K Rearrange the terms, we obtain

1 -192pα 2 t 2 mix L 2 K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 ≤32pα 2 t 2 mix   (σ 2 + 6ς 2 )K + 2 K-1 k=0 E n i=1 p i g k-τ k ,i 2   + 128δ 2 θ 2 t 2 mix K Lemma 23 ≤ 32α 2 t 2 mix   (σ 2 + 6ς 2 )pK + 2p K-1 k=0 E n i=1 p i g k-τ k ,i 2 + G 2 ∞ dK   Let A 1 = 1 -192pα 2 t 2 mix L 2 , we obtain K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 ≤ 32α 2 t 2 mix A 1   (σ 2 + 6ς 2 )pK + 2p K-1 k=0 E n i=1 p i g k-τ k ,i 2 + G 2 ∞ dK   Lemma 20 1 K K-1 k=0 E ∇f (X k ) 2 + 1 - 2αL n 1 K K-1 k=0 E ∇F (X k-τ k ) 2 ≤ 2n(f (0) -f * ) αK + 2L 2 K K-1 k=0 E (X k -X k-τ k )1 n n 2 + 2L 2 + 12αL 3 n 1 K K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 + (σ 2 + 6ς 2 )αL n Proof We start from f (X k+1 ) Since X k+1 = X k W k 1 n n + (Q k -X k )(W k -I) 1 n n -α G k-τ k = X k -α G k-τ k

Then from Taylor Expansion, we have

EQUATION

Rearrange these terms, we can get

EQUATION

Summing over k = 0 to K -1 on both sides, we can get

1 K K-1 k=0 E ∇f (X k ) 2 + 1 K K-1 k=0 E ∇F (X k-τ k ) 2 ≤ 2n(f (0) -f * ) αK + 1 K K-1 k=0 E ∇f (X k ) -∇F (X k-τ k ) 2 + αLσ 2 n + αL nK K-1 k=0 n i=1 p i E g k-τ k ,i 2 For K-1 k=0 E ∇f (X k ) -∇F (X k-τ k ) 2 , we have K-1 k=0 E ∇f (X k ) -∇F (X k-τ k ) 2 ≤2 K-1 k=0 E ∇f (X k ) -∇f (X k-τ k ) 2 + 2 K-1 k=0 E ∇f (X k-τ k ) -∇F (X k-τ k ) 2 =2 K-1 k=0 E ∇f (X k ) -∇f (X k-τ k ) 2 + 2 K-1 k=0 E n i=1 p i ∇f i (X k-τ k ) -g k-τ k ,i 2 ≤2 K-1 k=0 E ∇f (X k ) -∇f (X k-τ k ) 2 + 2 K-1 k=0 E n i=1 p i ∇f i (X k-τ k ) -g k-τ k ,i 2 ≤2L 2 K-1 k=0 E (X k -X k-τ k )1 n n 2 + 2L 2 K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2

Putting it back, we have

EQUATION

Note that

E n i=1 p i g k-τ k ,i 2 = E ∇F (X k-τ k ) 2

Moving it to the left side, we finally get

1 K K-1 k=0 E ∇f (X k ) 2 + 1 - 2αL n 1 K K-1 k=0 E ∇F (X k-τ k ) 2 ≤ 2n(f (0) -f * ) αK + 2L 2 K K-1 k=0 E (X k -X k-τ k )1 n n 2 + 2L 2 + 12αL 3 n 1 K K-1 k=0 n i=1 p i E X k-τ k 1 n n -e i 2 + (σ 2 + 6ς 2 )αL n

That completes the proof.

Lemma 21 For all k ≥ 0, we have

EQUATION

Proof From Lemma 20, we know the fact

EQUATION

And we get

EQUATION

That completes the proof.

Lemma 22 Given non-negative sequences {a t } ∞ t=1 , {b t } ∞ t=1 and {τ t } ∞ t=1 and a positive number T that satisfying 

a t =

:

A worker could refer to any computing unit that is capable of 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.

Detailed pseudo-code in the supplementary material.

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 on Moniqua can be found in supplementary material.

Other algorithms are not applicable to non-convex DNN problems, so we are not comparing them here.

Since we are measuring the system performance, the specific number of bits is not the focus here. In later section we will discuss statistical performance with small number of bits.

Note that we only put results that's 'close to the limit of Moniqua' here

Here we are using notation from Chapter 4.5 of Markov Chains and Mixing Times (Levin 2009), available at https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

Figures and Tables:

require O(d • l) and Tang et al. (2019) requires O(d) extra memory compared to D-PSGD to implement quantized communication, where d denotes the dimension of the model and l denotes the number of connections in the network. In comparison, Moniqua is extra-memory-free.

Spectral gap. The communication matrix W is a symmetric doubly stochastic matrix and max{|λ 2 (W )|, |λ n (W )|} = ρ < 1, where λ i (W ) denotes the ith eigenvalue of W . (A3) Bounded variance. There exist non-negative σ and ς such that

Figure 1: Performance of different algorithms under different network configurations

Figure 1(b) to Figure 1(d), when the network latency increases, we observe similar behavior. On the other hand, from Figure 1(b) to Figure 1(c) and Figure 1(d), curves of all the quantized baselines (DCD/ECD-PSGD, ChocoSGD and DeepSqueeze) are getting closer to Moniqua. This is because, as shown in Figure 1(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 Figure1we can see that Moniqua outperforms all these other algorithms.

Figure 3: Performance of applying Moniqua on D 2 and AD-PSGD

0.05, = 2.0) Moniqua( = 0.03, = 2.0) Moniqua( = 0.01, = 0.08) Moniqua( = 0.01, = 0.04) (a) Performance of Moniqua on VGG16 under different θ and δ 0.03, = 2.0) Moniqua( = 0.03, = 1.0) Moniqua( = 0.01, = 0.8) Moniqua( = 0.01, = 0.4) (b) Performance of Moniqua on ResNet110 under different θ and δ Performance of algorithms under different quantizer C.4 PERFORMANCE ON THE TESTSET UNDER AGGRESSIVE QUANTIZATION

Figure 5: More statistics from Experiment of Aggressive Quantization under 3-bit communication

Figure 7: Test Accuracy and Consensus Error of Moniqua under decreasing step size.

Figure 9: Consensus Error of Moniqua with different number of bits.

and considering the fact that ∇f (x) = x -δ/2 = x -x * , we can rewrite the update rule as

Lemma 23 for ∀i, j and ∀k ≥ 0, we haveX k (e i -e j ) ∞ ≤ θ = 16t mix αG ∞

Wall Clock Time consumption (Seconds)/Epoch in average under different network in Experiment of Evaluation of Moniqua.

Table content: <table><tr><td/><td colspan="4">100mbps/0.15ms 20mbps/0.15ms 100mbps/10ms Extra Memory</td></tr><tr><td>Centralized</td><td>38.92</td><td>206.14</td><td>343.28</td><td>N/A</td></tr><tr><td>D-PSGD</td><td>36.25</td><td>189.48</td><td>310.98</td><td>N/A</td></tr><tr><td>DCD-PSGD</td><td>32.99</td><td>105.40</td><td>202.42</td><td>20.4 MB</td></tr><tr><td>ECD-PSGD</td><td>31.96</td><td>105.26</td><td>202.04</td><td>20.4 MB</td></tr><tr><td>ChocoSGD</td><td>32.03</td><td>105.18</td><td>201.18</td><td>20.4 MB</td></tr><tr><td>DeepSqueeze</td><td>30.01</td><td>103.67</td><td>193.92</td><td>13.6 MB</td></tr><tr><td>Moniqua</td><td>22.42</td><td>95.08</td><td>184.86</td><td>0 B</td></tr></table>

Bandwidth consumption under different θ and δ when applying linear quantizer in Moniqua

Table content: <table><tr><td>MODEL</td><td colspan="4">MOD PARAM θ QUANT STEP BYTES/EPOCH AVG BITS</td></tr><tr><td/><td>NONE</td><td>NONE</td><td>45594MB</td><td>32</td></tr><tr><td>VGG16</td><td>1.0</td><td>0.01</td><td>5206MB</td><td>3.65</td></tr><tr><td/><td>0.08</td><td>0.01</td><td>5192MB</td><td>3.64</td></tr><tr><td/><td>NONE</td><td>NONE</td><td>3430MB</td><td>32</td></tr><tr><td>RESNET110</td><td>2.0</td><td>0.01</td><td>609MB</td><td>5.67</td></tr><tr><td/><td>1.3</td><td>0.01</td><td>608MB</td><td>5.67</td></tr><tr><td colspan="2">2. Randomized Gossip (Non-linear)</td><td/><td/><td/></tr></table>

Peer review (iclr2020):
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. The 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. The 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. My 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. Major concerns: 1. 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. To 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. 2. 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. Other concerns that should be addressed: 3. 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. 4. 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. 5. Reproducibility of the experiments: Many experimental details are omitted: - What are the values of hyperparameters used in the plots? - How did you model asynchrony in experiments? - How did you choose the parameter 	heta in experiments? 6. 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. 7. Why taking mod 	heta is required? Cannot you assume that ||Q(x) - x|| <= theta delta? The whole analysis will stay true. 8. In Asynchronous communication section, why 	au_k are the same for all the workers? Cannot different workers have different delays? 9. 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. Questions: 10. Is there a way to compute theta it in practice beforehand? Minor comments: - x mod y is not defined when x is a float number. - Intuition behind Moniqua: do you assume that worker 1 has only one neighbour (worker 2)? does m_1 is one dimensional or high dimensional? - Algorithm 1, the notation _x0008_ar X_k might be confusing as in the proof big letters correspond to matrixes. Consider to change on _x0008_ar x_k. - why some equations are numbered and some are not? - In Asynchronous communication section: what are the assumptions on W_k? - it would be helpful for the clarity to remind what is the stochastic rounding quantization in configuration of experiments section. - which are the other algorithms you talk about in footnote 6? - 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? - wall-clock time evaluation section: the statement that “algorithms diverge” might be confusing. - Aggressive quantization add ”.” - why the number of epochs differ in different experiments? Fig. 3(a) and Fig. 4(a) ?