Title: SPARSE BINARY COMPRESSION: TOWARDS DIS-TRIBUTED DEEP LEARNING WITH MINIMAL COMMU-NICATION

Abstract: Currently, progressively larger deep neural networks are trained on ever growing data corpora. In result, distributed training schemes are becoming increasingly relevant. A major issue in distributed training is the limited communication bandwidth between contributing nodes or prohibitive communication cost in general. To mitigate this problem we propose Sparse Binary Compression (SBC), a compression framework that allows for a drastic reduction of communication cost for distributed training. SBC combines existing techniques of communication delay and gradient sparsification with a novel binarization method and optimal weight update encoding to push compression gains to new limits. By doing so, our method also allows us to smoothly trade-off gradient sparsity and temporal sparsity to adapt to the requirements of the learning task. Our experiments show, that SBC can reduce the upstream communication on a variety of convolutional and recurrent neural network architectures by more than four orders of magnitude without significantly harming the convergence speed in terms of forward-backward passes. For instance, we can train ResNet50 on ImageNet in the same number of iterations to the baseline accuracy, using ×3531 less bits or train it to a 1% lower accuracy using ×37208 less bits. In the latter case, the total upstream communication required is cut from 125 terabytes to 3.35 gigabytes for every participating client. Our method also achieves state-of-the-art compression rates in a Federated Learning setting with 400 clients.

1. INTRODUCTION:

Distributed Stochastic Gradient Descent (DSGD) is a training setting, in which a number of clients jointly trains a deep learning model using stochastic gradient descent (Dean et al., 2012; Recht et al., 2011; Moritz et al., 2015) . Every client holds an individual subset of the training data, used to improve the current master model. The improvement is obtained by investing computational resources to perform iterations of stochastic gradient descent (SGD). This local training produces a weight update ∆W in every participating client, which in regular or irregular intervals ("communication rounds") is exchanged to produce a new master model. This exchange of weight updates can be performed indirectly via a centralized server or directly in an all-reduce operation. In both cases, all clients share the same master model after every communication round (see figure 1 ). In vanilla DSGD the clients have to communicate a full gradient update during every iteration. Every such update is of the same size as the full model, which can be in the range of gigabytes for modern architectures with millions of parameters (He et al., 2016; Huang et al., 2017) . Over the course of multiple hundred thousands of training iterations on big datasets the total communication for every client can easily grow to more than a petabyte. Consequently, if communication bandwidth is limited, or communication is costly, distributed deep learning can become unproductive or even unfeasible. DSGD is a very popular training setting with many applications. On one end of the spectrum, DSGD can be used to greatly reduce the training time of large-scale deep learning models by introducing device-level data parallelism (Chilimbi et al., 2014; Zinkevich et al., 2010; Xing et al., 2015; Li et al., 2014) , making use of the fact that the computation of a mini-batch gradient is perfectly parallelizable. In this setting, the clients are usually embodied by hardwired high-performance computation units (i.e. GPUs in a cluster) and every client performs one iteration of SGD per communication round. Since communication is high-frequent in this setting, bandwidth can be a significant bottleneck. On the other end of the spectrum DSGD can also be used to enable privacy-preserving deep learning (Shokri & Shmatikov, 2015; McMahan et al., 2016) . Since the clients only ever share weight updates, DSGD makes it possible to train a model from the combined data of all clients without any individual client having to reveal their local training data to a centralized server. In this setting the clients typically are embedded or mobile devices with low network bandwidth, intermittent network connections, and an expensive mobile data plan. In both scenarios, the communication cost between the individual training nodes is a limiting factor for the performance of the whole learning system. For the synchronous distributed training scheme described above, the total amount of bits communicated by every client during training is given by

EQUATION

where N iter is the total number of training iterations (forward-backward passes) every client performs, f is the communication frequency, |W =0 | is the sparsity of the weight update, bpos , bval are the average number of bits required to communicate the position and the value of the non-zero elements respectively and K is the number of receiving nodes (if W is dense, the positions of all weights are predetermined and no position bits are required).

Substantial research has gone into the effort of reducing the amount of communication necessary between the clients via lossy compression schemes. Using the systematic of equation 1, we can organize prior approaches into three different groups:

Sparsification methods restrict weight updates to modifying only a small subset of the parameters, thus reducing |∆W =0 |. Strom (2015) presents an approach (later modified by Tsuzuku et al. (2018) ) in which only gradients with a magnitude greater than a certain predefined threshold are sent to the server. All other gradients are aggregated into a residual. This method achieves compression rates of up to 3 orders of magnitude on an acoustic modeling task. In practice however, it is hard to choose appropriate values for the threshold, as it may vary a lot for different architectures and even different layers. Instead of using a fixed threshold to decide what gradient entries to send, Aji & Heafield (2017) use a fixed sparsity rate. They only communicate the fraction p entries of the gradient with the biggest magnitude, while also collecting all other gradients in a residual. At a sparsity rate of p = 0.001 their method slightly degrades the convergence speed and final accuracy of the trained model. Lin et al. (2017) present modifications to the work of Aji et al. which close this performance gap. These modifications include using a curriculum to slowly increase the amount of sparsity in the first couple communication rounds and applying momentum factor masking to overcome the problem of gradient staleness. Their method achieves compression rates ranging from ×270 to ×600 on different architectures, without slowdown in convergence speed.

Communication delay methods try to reduce the communication frequency f . McMahan et al. (2016) propose Federated Averaging to reduce the cumulative communication. In Federated Averaging, instead of communicating after every iteration, every client performs multiple iterations of SGD to compute a weight update. The authors observe that this delay of communication does not significantly harm the convergence speed in terms of local iterations and report a reduction in the number of necessary communication rounds by a factor of ×10 -×100 on different convolutional and recurrent neural network architectures. In a follow-up work Konečnỳ et al. (2016) combine this communication delay with random sparsification and probabilistic quantization. They restrict the clients to learn random sparse weight updates or force random sparsity on them afterwards ("structured" vs "sketched" updates) and combine this sparsification with probabilistic quantization. While their method also combines communication delay with (random) sparsification and quantization, and achieves good compression gains for one particular CNN and LSTM model, it also causes a major drop in convergence speed and final accuracy.

Dense quantization methods try to reduce the amount of value bits bval . Different quantization methods have been proposed that reduce the bit-width of the gradients to ternary (Wen et al., 2017) , binary (Seide et al., 2014; Bernstein et al., 2018) or arbitrary (Alistarh et al., 2017) bitwidths. While these are theoretically well-founded and come with strong convergence guarantees, they are also limited to a maximum compression rate of ×32, compared to the regular 32-bit encoding. Communication delay and sparsification methods as described above already achieve impressive compression rates, however the phenomenon underlying their successes is still only poorly understood. We present a new information-theoretic perspective that is based on the observation that both of these approaches achieve compression by accumulating gradient information locally before sending it to the server. In the case of communication delay all gradients are accumulated uniformly for a fixed amount of iterations, while in the case of sparsification methods they are accumulated non-uniformly until they exceed some fixed or adaptive threshold. In both cases the rate of compression is proportional to the number of steps that the updates are being delayed on average.

2. ON THE ACCUMULATION OF GRADIENT INFORMATION:

Consider now the optimization path ∆W 1 , .., ∆W T taken by SGD on the loss-surface between some initialization point W 0 and the model W T = W 0 + T t=1 ∆W t trained for T iterations. Following this path, we can model the changes occurring to any individual weight in the network w as a noisy stochastic process via

EQUATION

where s t denotes the deterministic signal (i.e. the true direction of the minimum), while n t denotes the noise, induced by mini-batch sampling in SGD ("batch noise") and the stochasticity of the learning process itself ("optimization noise", see figure 2 for an illustration). For the sake of simplicity, and motivated by the central limit theorem we can assume (a) that this noise n t is normally distributed at every time-step n t ∼ N (0, σ 2 ) with the variance being constant in time V(n t ) = σ 2 for all t = 1, .., T . Since the optimization process has the tendency to damp noise as investigated for instance in LeCun et al. (2012) it is also reasonable to assume (b) that the noise is (negatively) self-correlated. The noise process is then given by n 1 = N 1 , n t = αn t-1 + N t , with N t normally distributed and all N t uncorrelated, α ∈ (-1, 0). Given these assumptions we can bound the variance of the accumulated parameter updates.

Theorem 2.1. Under assumptions (a) and (b), the variance of the accumulated noise can be bounded by

EQUATION

The proof can be found in the supplement. Theorem 2.1 directly leads us to a lower bound on the signal-to-noise ratio of the accumulated weight-updates: Corollary 2.1.1. Under assumptions (a) and (b), accumulation increases the signal-to-noise ratio from s/σ to SNR(

T t=1 ∆w t ) = E[ T t=1 s t + n t ] V[ T t=1 s t + n t ] ≥ T t=1 s t σ 2 (T (1 + α) + 1) ≈ √ T √ 1 + α s σ (4)

with s = 1 T T t=1 s t being the signal-average over time.

This means that a weight-update will be more informative the longer the accumulation period and the stronger the noise correlates temporally. Convergence speed will not be compromised for as long as the information content of the accumulated update is equal to the cumulative information content of the individual updates (c.f. fig. 2 (c )). This line of reasoning helps to shed light on both the successes of communication delay and gradient sparsification. In fact, it implies that both of these approaches are actually very similar in the way they affect the information flow from client to server on the individual weight level.

x 1 x 5 x 25 x 125 x 625

x 2500 x 10000

Gradient Sparsity

x 10000

x 2500

x 625

x 125

x 25

x 5

x We find that this intuition is also verified empirically. Figure 3 shows validation errors for ResNet32 model trained on CIFAR for 60000 iterations at different levels of communication delay and gradient sparsity. We observe multiple things: 1.) The validation error remains more or less constant along the off-diagonals of the matrix where the total sparsity (i.e. the product of communication delay and gradient sparsity) is constant. 2.) The existing methods of Federated Averaging (McMahan et al., 2016) (purple) and Gradient Dropping/ DGC (Aji & Heafield, 2017; Lin et al., 2017) (yellow) are just lines in the two-dimensional space of possible compression methods. 3.) There exists a roughly triangular area of approximately constant error, optimal compression methods lie along the hypotenuse of this triangle. We find this behavior consistently across different model architectures, more examples can be found in the supplement.

These results indicate, that communication delay and sparsification affect the convergence in a roughly multiplicative way and that there seems to exist a fixed information budged in DSGD, necessary to maintain unhindered convergence.

In the following we present a framework that allows us to smoothly trade of these two types of gradient accumulation against one another. By doing so our proposed framework can adapt to the requirements of the distributed learning environment and achieve state-of-the-art compression results by reaping the benefits from both approaches.

3. SPARSE BINARY COMPRESSION:

Inspired by our findings in the previous section, we propose Sparse Binary Compression (cf. In the following W will refer to the entirety of neural network parameters, while W ∈ W will refer to one specific tensor of weights. Arithmetic operations on W are to be understood componentwise. et al., 2009) . Lin et al. (2017) suggest to reduce the computational cost of this operation, by randomly subsampling from W . However this comes at the cost of introducing (unbiased) noise in the amount of sparsity. Luckily, in our approach communication rounds (and thus compressions) are relatively infrequent, which helps to marginalize the overhead of the sparsification. Quantizing the non-zero elements of the sparsified weight update to the mean reduces the required value bits bval from 32 to 0. This translates to a reduction in communication cost by a factor of around ×3. We can get away with averaging out the non-zero weight updates because they are relatively homogeneous in value and because we accumulate our compression errors as described in the next paragraph.

∆W i = SGD n (W i , D i ) -W i where SGD n (W i , D i )

Residual Accumulation, Fig. 4 (d): It is well established (Lin et al., 2017; Strom, 2015; Aji & Heafield, 2017; Seide et al., 2014) that the convergence in sparsified DSGD can be greatly accelerated by accumulating the error that arises from only sending sparse approximations of the weight updates.

After every communication round, the residual is updated via

EQUATION

Error accumulation has the great benefit that no gradient information is lost (it may only become outdated or "stale"). In the context of pure sparsification residual accumulation can be interpreted to be equivalent to increasing the batch size for individual parameters (Lin et al., 2017) . Moreover, we can show: Theorem 3.1. Let ∆W 1 , .., ∆W T ∈ R n be (flattened) weight updates, computed by one client in the first T communication rounds. Let ∆W * 1 , .., ∆W * T -1 ∈ S be the actual weight updates, transferred in the previous rounds (restricted to some subspace S) and R τ be the content of the residual at time τ as in equation 5. Then the orthogonal projection

v = Proj S (R T -1 + ∆W T ) (6)

uniquely minimizes the accumulated error

err(∆W * T ) = T t=1 (∆W t -∆W * t ) (7) in S. (Proof in Supplement.)

That means that the residual accumulation keeps the compressed optimization path as close as possible to optimization path taken with non-compressed weight updates.

Algorithm 1: Synchronous Distributed Stochastic Gradient Descent (DSGD)

input: initial parameters W outout: improved parameters W init: all clients C i are initialized with the same parameters W i ← W, the initial global weight update and the residuals are set to zero ∆W, R i ← 0 for t = 1, .., T do for i ∈ I t ⊆ {1, .., M } in parallel do Client C i does:

• msg ← download S→Ci (msg) • ∆W ← decode(msg) • W i ← W i + ∆W • ∆W i ← R i +SGD n (W i , D i )-W i • ∆W * i ← compress(∆W i ) • R i ← ∆W i -∆W * i • msg i ← encode(∆W * i ) • upload Ci→S (msg i )

end Server S does: 

• gather Ci→S (∆W * i ), i ∈ I t • ∆W ← 1 |It| i∈It ∆W * i • W ← W + ∆W • broadcast S→Ci (∆W), i = 1, ..,

4 • µ + ← mean(val + ); µ -← mean(val -) 5 if µ + ≥ µ -then 6 return ∆W * ← µ + (W ≥ min(val + )) 7 else 8 return ∆W * ← -µ -(W ≤ -min(val -)) 9 end

Algorithm 3: Golomb Position Encoding 1 input: sparse tensor ∆W * , sparsity p 2 output: binary message msg

3 • I ← ∆W * [:] =0 4 • b * ← 1 + log 2 ( log(φ-1) log(1-p) ) 5 for i = 1, .., |I| do 6 • d ← I i -I i-1 7 • q ← (d -1) div 2 b * 8 • r ← (d -1) mod 2 b *

9:

• msg.add(1, .., 1 q times , 0, binary b * (r)) 10 end 11 return msg Optimal Position Encoding, Fig. 4 (e): To communicate a set of sparse binary tensors produced by SGC, we only need to transfer the positions of the non-zero elements in the flattened tensors, along with one mean value (µ + or µ -) per tensor. Instead of communicating the absolute non-zero positions it is favorable to only communicate the distances between all non-zero elements. It is possible to show that for big values of |W | and k = p|W |, the distances are approximately geometrically distributed with success probability equal to the sparsity rate p. Therefore, we can optimally encode the distances using the Golomb code Golomb (1966) . Golomb encoding reduces the average number of position bits to

EQUATION

) with b * = 1 + log 2 ( log(φ-1) log(1-p) ) and φ = √ 5+1 2

being the golden ratio. For a sparsity rate of i.e. p = 0.01, we get bpos = 8.38, which translates to ×1.9 compression, compared to a naive distance encoding with 16 fixed bits. While the overhead for encoding and decoding makes it unproductive to use Golomb encoding in the situation of Strom (2015) , this overhead becomes negligible in our situation due to the infrequency of weight update exchange resulting from communication delay. The encoding scheme is given in algorithm 3, while the decoding scheme can be found in the supplement.

Momentum Correction, Warm-up Training and Momentum Masking: Lin et al. (2017) introduce multiple minor modifications to the vanilla Gradient Dropping method, to improve the convergence speed. We adopt momentum masking, while momentum correction is implicit to our approach. For more details on this we refer to the supplement. Our proposed method is described in Algorithms 1, 2 and 3. Algorithm 1 describes how compression and residual accumulation can be introduced into DSGD. Algorithm 2 describes our compression method. Algorithm 3 describes the Golomb encoding. Table 1 : Theoretical asymptotic compression rates for different compression methods broken down into components. Only SBC reduces all multiplicative components of the total bitsize (cf. eq. 1).

4. EXPERIMENTS 4.1 NETWORKS AND DATASETS:

We evaluate our method on commonly used convolutional and recurrent neural networks with millions of parameters, which we train on well-studied data sets that contain up to multiple millions of samples.

We perform experiments with client numbers ranging from 4 to 400 to cover both the distributed training and federated learning use-case.

Image Classification::

We run experiments for LeNet5-Caffe2 on MNIST LeCun (1998), ResNet18 and ResNet34 He et al. (2016) on CIFAR-10 and CIFAR-100 Krizhevsky et al. (2014) and ResNet50 on ILSVRC12 (ImageNet) Deng et al. (2009) . For the i.i.d. setting we split the training data randomly into equally sized shards and assign one shard to every one of the clients. For the non-i.i.d. setting every client is assigned samples from only two classes of the dataset, but the amount of data still remains the same for every client. All models are trained using momentum SGD, except for LeNet5-Caffe, which is trained using the Adam optimizer Kingma & Ba (2014) . Learning rate, weight intitiallization and data augmentation are as in the respective papers. / "WordLSTM*") with tied weights between encoder and decoder as described in Inan et al. (2016) .

The training data is split into consecutive subsequences of equal length, out of which we assign one to every client.

While the models we use in our experiments do not fully achieve state-of-the-art results on the respective tasks and datasets, they are still sufficient for the purpose of evaluating our compression method and demonstrate, that our method works well with common regularization techniques such as batch normalization Ioffe & Szegedy (2015) and dropout Srivastava et al. (2014) . A complete description of models and hyperparameters can be found in the supplement.

4.2. RESULTS:

We experiment with three configurations of our method: SBC (1) uses no communication delay and a gradient sparsity of 0.1%, SBC (2) uses 10 iterations of communication delay and 1% gradient sparsity and SBC (3) uses 100 iterations of communication delay and 1% gradient sparsity. Our decision for these points on the 2D grid of possible configurations is somewhat arbitrary. The experiments with SBC (1) serve the purpose of enabling us to directly compare our 0-value-bit quantization to the 32-value-bit Deep Gradient Compression (Lin et al., 2017) ).

Table 2 lists compression rates and final validation accuracies achieved by different compression methods, when applied to the training of neural networks on 5 different datasets. The number of iterations (forward-backward-passes) is held constant for all methods. On all benchmarks, our methods perform comparable to the baseline, while communicating significantly less bits.

Figure 5 shows convergence speed in terms of iterations (left) and communicated bits (right) respectively for ResNet50 trained on ImageNet. The convergence speed is only marginally affected, by our different compression methods. In the first 30 epochs SBC (3) even achieves the highest accuracy, using about ×37000 less bits than the baseline. In total, SBC (3) reduces the upstream communication on this benchmark from 125 terabytes to 3.35 gigabytes for every participating client.

After the learning rate is lowered in epochs 30 and 60 progress slows down for SBC (3) relative to the methods which do not use communication delay. In direct comparison SBC (1) performs very similar to Gradient Dropping, while using about ×4 less bits (that is ×2569 less bits than the baseline). Table 3 shows results for the federated learning setting with much higher numbers of clients trained on both i.i.d. and non-i.i.d. splits of data. We can see that in particular with growing numbers of clients and in the non-i.i.d. case, Federated Averaging significantly slows down the convergence and degrades the final accuracy. SBC (3) also suffers in this scenario as is also relies on 100 steps of communication delay. Conversely, our methods SBC (1) and ( 2) that rely more heavily on gradient sparsification perform much better in this setting and in some cases even beat the baseline. This behavior is expected, as the frequent exchange of gradient information in SBC ( 1) and ( 2) keeps all clients aligned, while they diverge further from one another for every iteration that communication is delayed in Federated Averaging.

Our experiments suggest that the distinction between the two formerly treated as separate distributed training settings of federated learning and data-parallel training is somewhat arbitrary and misleading and that better results can be achieved by combining the best approaches from both of these worlds. Contrary to the paradigm suggested in previous literature (McMahan et al., 2016) 

5. CONCLUSION:

The gradient information for training deep neural networks with SGD is highly redundant (see e.g. Lin et al. (2017) ). We exploit this fact to the extreme by combining 3 powerful compression strategies and are able to achieve compression gains of up to four orders of magnitude with only a slight decrease in accuracy. More fundamentally, we present theoretical and empirical evidence suggesting that the formerly treated as separate compression methods of communication delay and gradient sparsification in fact can be viewed as two very similar forms of gradient delay that affect the convergence speed in a roughly multiplicative way. Based on this insight we propose a framework that is able to reap the benefits from both compression approaches and can smoothly adapt to communication-constraints in the learning environment, such as network bandwidth and latency and (SGD-)computation time as well as temporal inhomogeneities therein. This leads to advantages in both federated learning and data-parallel training of deep neural networks. We would like to highlight, that in no case we did modify the hyperparameters of the respective baseline models to accommodate our method. This demonstrates that our method is easily applicable. Note however that an extensive hyperparameter search could further improve the results. Furthermore, our findings in sections 2 and 4 indicate that even higher compression rates are possible if we adapt communication delay and gradient sparsity to the particular training objective. It remains an interesting direction of further research to identify heuristics and theoretical insights that can help to find the optimal balance and thus guide sparsity towards optimality.

6. SUPPLEMENT:

6.1 MOMENTUM CORRECTION, WARM-UP TRAINING AND MOMENTUM MASKING:

Lin et al. introduce multiple minor modifications to the vanilla Gradient Dropping method. With these modifications they achieve up to around 1% higher accuracy compared to Gradient Dropping on a variety of benchmarks. Those modifications include:

Momentum correction: Instead of adding the raw gradient to the residuum, the momentum-corrected gradient is added. This is used implicitly in our approach, as our weight updates are already momentum-corrected.

Warm-up Training::

The sparsity rate is increased exponentially from 25% to 0.1% in the first epochs. We find that warm-up training can indeed speed-up convergence in the beginning of training, but ultimately has no effect on the final accuracy of the model. We therefore omit warm up training in our experiments, as it adds an additional hyperparameter to the method, without any real benefit. Momentum Masking: To avoid stale momentum from carrying the optimization into a wrong direction after a weight update is performed, Lin et al. suggest to set the momentum to zero for updated weights.

We adopt momentum correction in our method.

6.2. GOLOMB POSITION DECODING:

Algorithm 4 describes the decoding of a binary sequence produced by Golomb Position Encoding (see main paper). Since the shapes of all weight-tensors are known to both the server and all clients, we can omit the shape information in both encoding and decoding. WordLSTM: We use the implementation from the official PyTorch repository (configuration "medium"): https://github.com/pytorch/examples/tree/master/word_ language_model. (Features trainable word-embeddings, multilayer LSTM-cells, dropout.) 6.4 PROOF OF THEOREM 2.1.

init: ∆W * ← 0 ∈ R n • i ← 0; q ← 0; j ← 0 while i < size(msg) do if msg[i] = 0 then • j ← j + q2 b * + int b * (msg[i + 1], .., msg[i + b * ]) + 1 • ∆W * j ← µ • q ← 0; i ← i + b * + 1 else • q ← q + 1; i ← i +

Proof. Since n t = αn t-1 + N t = α(αn t-2 + N t-1 ) + N t = α 2 n t-2 + αN t-1 + N t = α τ n t-τ + τ -1 i=0 α i N t-i (9) it holds that cov(n t-τ , n t ) = cov(n t-τ , α τ n t-τ + τ -1 For negatively correlated noise α ∈ (-1, 0) we can bound this term by

EQUATION

EQUATION

≤ σ 2 (T (1 + α) + 1) (16)

6.5 PROOF OF THEOREM 3.1.

Proof. It holds that

EQUATION

)

Since S is a metric subspace, the projection

EQUATION

uniquely solves the minimization problem in S.

6.6. ADDITIONAL RESULTS:

Figure 6 shows validation error for WordLSTM trained on PTB at different levels of gradient sparsity and temporal sparsity. The total sparsity, defined as the product of temporal and gradient sparsity remains constant along the diagonals of the matrix. We observe that different forms of sparsity perform best during different stages of training. Phrased differently, this means that there is not one optimal sparsity setup, but rather sparsity needs to be adapted to the current training phase to achieve optimal compression. 

:

To clarify, we have put our contributions in emphasis.

A modified version of LeNet5 from LeCun et al. (1998) (see supplement).

Lin et al. (2017) at a sparsity rate p = 0.1% without warm-up training. The gradients are encoded with Golomb encoding prior to communication.

McMahan et al. (2016) at different rates of communication delay (the compression rate is equal to the communication delay).

ResNet18* onyl has half as many convolutional filters in every layer as ResNet18.

Figures and Tables:

Figure 1: One communication round of DSGD: a) Clients synchronize with the server. b) Clients compute a weight update independently based on their local data. c) Clients upload their local weight updates to the server, where they are averaged to produce the new master model.

Figure2: Sources of noise in SGD (illustration): Left: Optimization noise, caused by Gradient Descent overshooting. Bouncing between the walls of the ravine results in negatively correlated noise. Middle: Batch noise, caused by the batch loss being only a noisy approximation of the full empirical loss. Right: The compressed path converges equally fast, but requires only half of the information to be communicated.

Figure 3: Validation Error for ResNet32 trained on CIFAR at different levels of temporal and gradient sparsity (the error is color-coded, brighter means lower error). The prior approaches of Gradient Dropping and Federated Averaging can be embedded in a two-dimensional compression framework.

Figure4), to drastically reduce the number of communicated bits in distributed training. SBC makes use of multiple compression techniques simultaneously 1 to reduce all multiplicative components of equation 1.

Figure 4: Step-by-step explanation of techniques used in Sparse Binary Compression: (a) Illustrated is the traversal of the parameter space with regular DSGD (left) and Federated Averaging (right).With this form of communication delay, a bigger region of the loss surface can be traversed, in the same number of communication rounds. That way compression gains of up to ×1000 are possible. After a number of iterations, the clients communicate their locally computed weight updates. (b) Before communication, the weight update is first sparsified, by dropping all but the fraction p weight updates with the highest magnitude. This achieves up to ×1000 compression gain. (c) Then the sparse weight update is binarized for an additional compression gain of approximately ×3. (d) Finally, we optimally encode the positions of the non-zero elements, using Golomb encoding. This reduces the bit size of the compressed weight update by up to another ×2 compared to naive encoding.

Communication Delay, Fig. 4 (a): We use communication delay, proposed by McMahan et al. (2016), to introduce temporal sparsity into DSGD. Instead of communicating gradients after every local iteration, we allow the clients to compute more informative updates by performing multiple iterations of SGD. These generalized weight updates are given by

refers to the set of weights obtained by performing n iterations of stochastic gradient descent on W i , while sampling mini-batches from the i-th client's training data D i . Empirical analysis byMcMahan et al. (2016)  suggests that communication can be delayed drastically, with only marginal degradation of accuracy. For n = 1 we obtain regular DSGD.Sparse Binarization, Fig.4(b), (c): Following the works ofLin et al. (2017)Strom (2015)Shokri & Shmatikov (2015) and Aji & Heafield (2017) we use the magnitude of an individual weight within a weight update as a heuristic for it's importance. First, we set all but the fraction p biggest and fraction p smallest weight updates to zero. Next, we compute the mean of all remaining positive and all remaining negative weight updates independently. If the positive mean µ + is bigger than the absolute negative mean µ -, we set all negative values to zero and all positive values to the positive mean and vice versa. The method is illustrated in figure4and formalized in algorithm 2. Finding the fraction p smallest and biggest values in a vector W requires O(|W |) operations, where |W | refers to the number of elements in W (Cormen

Figure 5: Left: Top-1 validation accuracy vs number of epochs. Right: Top-1 validation error vs number of transferred bits (log-log). Epochs 30 and 60 at which the learning rate is reduced are marked in the plot. ResNet50 trained on ImageNet.

Golomb Position Decoding input: binary message msg, bitsize b * , mean value µ output: sparse tensor ∆W *

Figure 6: Perplexity for different levels of gradient sparsity and temporal sparsity at different stages of training. WordLSTM trained on PTB.

Table 1 compares theoretical asymptotic compression rates of different popular compression methods.

Table content: <table><tr><td/><td>Total Bits =</td><td>Baseline</td><td>SignSGD, TernGrad , QSGD</td><td>Gradient Dropping, DGC</td><td>Federated Averaging</td><td>Sparse Binary Compression</td></tr><tr><td/><td>Temporal Sparsity</td><td>100%</td><td>100%</td><td>100%</td><td>0.1% -10%</td><td>0.1% -10%</td></tr><tr><td>× ×</td><td>Gradient Sparsity Value Bits Position Bits</td><td>100% 32 0</td><td>100% 1 -8 0</td><td>0.1% 32 16</td><td>100% 32 0</td><td>0.1% -10% 0 8 -14</td></tr><tr><td/><td>Compression Rate</td><td>×1</td><td>×4 -×32</td><td>×666</td><td>×10 -×1000</td><td>-×40000</td></tr></table>

Final accuracy/perplexity achieved on the test split and average compression rate for different compression schemes in a distributed training setting with different numbers of clients. We experiment with multilayer sequence-to-sequence LSTM models as described inZaremba et al. (2014) on the Penn Treebank (PTB)Marcus et al. (1993) and Wikitext-2 corpora for next-word prediction. The PTB dataset consists of a sequence 923000 training, and 82000 validation words, while the Wikitext-2 dataset contains 2088628 train and 245569 test words. On both datasets we train a two-layer LSTM model with 650 and 200 hidden units respectively ("WordLSTM"

Table content: <table><tr><td>Language Modeling:</td></tr></table>

Final accuracy achieved on the test split and average compression rate for different compression schemes in a Federated learning setting with different numbers of clients.

Table content: <table/>

, communication delay does not seem to be a well-suited approach for communication reduction in the federated learning setting. Instead our experiments demonstrate, that drastically better performance can be achieved under an even lower communication budged, if individual weight-updates are sparsified instead of delayed. On the other hand, it's easy to see that communication delay has the potential to speed-up parallel training as it allows the individual computation devices to perform multiple steps of SGD without interruption. Our experiments with 4 clients demonstrate that introducing communication delay into data parallel training is not harmful to the convergence of the model in terms of training iterations.

Table content: <table/>

Below, we describe the neural network models used in our experiments. Table 4 list the training hyperparameters that were used. Hyperparameters used for our experiments in sections 2 and 4. LeNet5-Caffe: The model specification can be downloaded from the Caffe MNIST tutorial page: https://github.com/BVLC/caffe/blob/master/examples/mnist/lenet_ train_test.prototxt. (Features convolutional layers, fully connected layers, pooling.) We use the implementation from the official PyTorch repository: https://github.com/pytorch/examples/tree/master/imagenet. (Features skip-connections, batch-normalization.)

Table content: <table><tr><td>1</td></tr><tr><td>end</td></tr><tr><td>end</td></tr><tr><td>return ∆W  *</td></tr></table>

Peer review (iclr2019):
 The paper once again looks at the problem of reducing the communication requirement for implementing the distributed optimization techniques, in particular, SGD. This problem has been looked at from multiple angles by many authors. And although there are many unanswered questions in this area, I do not see the authors providing any compelling contribution to answering those questions. A big chunk of the paper is devoted to expressing some shallow theorems, which in some cases I do not even see their importance or connection to the main point of the paper; see my comments below. In terms of the techniques for reducing the communication burden, the authors seem to just put all the other approaches together with minimal novelty. More detailed comments: - I do not really understand what the authors mean by noise damping. I would appreciate it if they could clarify that point. This seems to be a very important point as the model they propose for the noise in the process is basically based on this notion. It is a great failure on the authors* part that such a crucial notion in their paper is not clearly described. - The model that is proposed for noise is too strong and too simplistic. Do you guys have any evidence to back this up? - Theorem 2.1 is not a theorem. The result is super shallow and relatively trivial. - In corollary 2.1 it seems that no matter what the randomness in the system is, the algorithm is going to converge to the same solution. This is not true even for the non-strongly convex objectives, let alone the non-convex problems where there are so many stationary solutions and whatnot. - With regards to Fig 3 (and other related figures in the appendix) and the discussion on the multiplicative nature of compression: The figure does not seem to suggest multiplicative nature in all the regimes. It seems to hold in high compression/ low-frequency communication regime. But on the other side of the spectrum, it does not seem to hold very strongly. - The residual accumulation only applies when all the nodes update in all the iterations. I do not believe this would generalize to the federated learning, where nodes do not participate in all the updates. I do not know if the authors have noted this point in their federated learning experiments. - Theorem 3.1 is very poorly stated. Other that than it is shallow and in my opinion irrelevant. What is the argument in favor of the authors* thought that could be built based on the result of Theorem 3.1? - One major point that is missing in the experiments (and probably in the experiments in other papers on the same topic) is to see how much do all these compressions affect the speed of learning in different scenarios in realistic scenarios? Note that in realistic scenarios many things other than communication could affect the convergence time.