Year: 2018

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.

heading: 1 INTRODUCTION
text: 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
btotal ∈ O( Niter × f︸ ︷︷ ︸ # communication rounds × |∆W6=0| × (b̄pos + b̄val)︸ ︷︷ ︸ # bits per communication × K︸︷︷︸ # receiving nodes ) (1)
whereNiter is the total number of training iterations (forward-backward passes) every client performs, f is the communication frequency, |W6=0| is the sparsity of the weight update, b̄pos, b̄val 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 (ifW 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 |∆W6=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 Konečnỳ 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 b̄val. 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.

heading: 2 ON THE ACCUMULATION OF GRADIENT INFORMATION
text: 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.
Consider now the optimization path ∆W1, ..,∆WT taken by SGD on the loss-surface between some initialization pointW0 and the modelWT =W0 + ∑T t=1 ∆Wt 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
∆wt = st + nt, t = 1, .., T (2)
where st denotes the deterministic signal (i.e. the true direction of the minimum), while nt 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 nt is normally distributed at every time-step nt ∼ N (0, σ2) with the variance being constant in time V(nt) = σ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 n1 = N1, nt = αnt−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
V( T∑ t=1 nt) ≤ σ2(T (1 + α) + 1). (3)
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 ∆wt) = E[ ∑T t=1 s t + nt]√ V[ ∑T t=1 s t + nt] ≥
∑T t=1 s
t√ σ2(T (1 + α) + 1) ≈ √ T√ 1 + α s̄ σ (4)
with s̄ = 1T ∑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.
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.

heading: 3 SPARSE BINARY COMPRESSION
text: Inspired by our findings in the previous section, we propose Sparse Binary Compression (cf. Figure 4), to drastically reduce the number of communicated bits in distributed training. SBC makes use
of multiple compression techniques simultaneously1 to reduce all multiplicative components of equation 1.
In the followingW will refer to the entirety of neural network parameters, while W ∈ W will refer to one specific tensor of weights. Arithmetic operations onW are to be understood componentwise. 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
∆Wi = SGDn(Wi, Di)−Wi where SGDn(Wi, Di) refers to the set of weights obtained by performing n iterations of stochastic gradient descent onWi, while sampling mini-batches from the i-th client’s training dataDi. Empirical analysis by McMahan 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 of Lin 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 figure 4 and 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 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 b̄val 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.
1To clarify, we have put our contributions in emphasis.
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
Rτ = τ∑ t=1 (∆Wt −∆W∗t ) = Rτ−1 + ∆Wτ −∆W∗τ . (5)
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 ∆W1, ..,∆WT ∈ Rn 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) andRτ be the content of the residual at time τ as in equation 5. Then the orthogonal projection
v = ProjS(RT−1 + ∆WT ) (6) uniquely minimizes the accumulated error
err(∆W ∗T ) = ‖ T∑ t=1 (∆Wt −∆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)
1 input: initial parametersW 2 outout: improved parametersW 3 init: all clients Ci are initialized with the
same parametersWi ←W , the initial global weight update and the residuals are set to zero ∆W,Ri ← 0
4 for t = 1, .., T do 5 for i ∈ It ⊆ {1, ..,M} in parallel do 6 Client Ci does: 7 • msg← downloadS→Ci(msg) 8 • ∆W ← decode(msg) 9 • Wi ←Wi + ∆W
10 • ∆Wi ← Ri+SGDn(Wi, Di)−Wi 11 • ∆W∗i ← compress(∆Wi) 12 • Ri ← ∆Wi −∆W∗i 13 • msgi ← encode(∆W∗i ) 14 • uploadCi→S(msgi) 15 end 16 Server S does: 17 • gatherCi→S(∆W∗i ), i ∈ It 18 • ∆W ← 1|It| ∑ i∈It ∆W∗i 19 • W ←W + ∆W 20 • broadcastS→Ci(∆W), i = 1, ..,M 21 end 22 returnW
Algorithm 2: Sparse Binary Compression 1 input: tensor ∆W , sparsity p 2 output: sparse tensor ∆W ∗ 3 • val+ ← topp%(∆W ); val− ← topp%(−∆W ) 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 ∗[:] 6=0 4 • b∗ ← 1 + blog2( log(φ−1)log(1−p) )c 5 for i = 1, .., |I| do 6 • d← Ii − Ii−1 7 • q ← (d− 1) div 2b∗ 8 • r ← (d− 1) mod 2b∗ 9 • msg.add(1, .., 1︸ ︷︷ ︸
q times
, 0, binaryb∗(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
b̄pos = b ∗ +
1
1− (1− p)2b∗ , (8)
with b∗ = 1 + blog2( log(φ−1)log(1−p) )c and φ = √ 5+1 2 being the golden ratio. For a sparsity rate of i.e. p = 0.01, we get b̄pos = 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 compares theoretical asymptotic compression rates of different popular compression methods.

heading: 4 EXPERIMENTS

heading: 4.1 NETWORKS AND DATASETS
text: 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 LeNet5Caffe, which is trained using the Adam optimizer Kingma & Ba (2014). Learning rate, weight intitiallization and data augmentation are as in the respective papers.
2A modified version of LeNet5 from LeCun et al. (1998) (see supplement).
Language Modeling: We experiment with multilayer sequence-to-sequence LSTM models as described in Zaremba 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" / "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.

heading: 4.2 RESULTS
text: 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
3Lin et al. (2017) at a sparsity rate p = 0.1% without warm-up training. The gradients are encoded with Golomb encoding prior to communication.
4McMahan et al. (2016) at different rates of communication delay (the compression rate is equal to the communication delay).
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), 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
5ResNet18* onyl has half as many convolutional filters in every layer as ResNet18.
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.

heading: 5 CONCLUSION
text: 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.

heading: 6 SUPPLEMENT

heading: 6.1 MOMENTUM CORRECTION, WARM-UP TRAINING AND MOMENTUM MASKING:
text: 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.

heading: 6.2 GOLOMB POSITION DECODING
text: 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.
Algorithm 4: Golomb Position Decoding 1 input: binary message msg, bitsize b∗, mean value µ 2 output: sparse tensor ∆W ∗ 3 init: ∆W ∗ ← 0 ∈ Rn 4 • i← 0; q ← 0; j ← 0 5 while i < size(msg) do 6 if msg[i] = 0 then 7 • j ← j + q2b∗ + intb∗(msg[i+ 1], ..,msg[i+ b∗]) + 1 8 • ∆W ∗j ← µ 9 • q ← 0; i← i+ b∗ + 1
10 else 11 • q ← q + 1; i← i+ 1 12 end 13 end 14 return ∆W ∗

heading: 6.3 MODEL SPECIFICATION
text: Below, we describe the neural network models used in our experiments. Table 4 list the training hyperparameters that were used.
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.)
ResNet18, ResNet32, ResNet50: We use the implementation from the official PyTorch repository: https://github.com/pytorch/examples/tree/master/imagenet. (Features skip-connections, batch-normalization.)
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.)

heading: 6.4 PROOF OF THEOREM 2.1.
text: Proof. Since
nt = αnt−1 +N t = α(αnt−2 +N t−1) +N t = α2nt−2 + αN t−1 +N t
= ατnt−τ + τ−1∑ i=0 αiN t−i (9)
it holds that
cov(nt−τ , nt) = cov(nt−τ , ατnt−τ + τ−1∑ i=0 αiN t−i) = ατσ2 + τ−1∑ i=0 αi cov(nt−τ , N t−i)︸ ︷︷ ︸ =0 = ατσ2
(10)
With equation equation 10 it follows that
V( T∑ t=1 nt) = T∑ t1=1 T∑ t2=1 cov(nt1 , nt2) (11)
= T∑ t=1
cov(nt, nt)︸ ︷︷ ︸ Tσ2 +2
T−1∑ t=1
cov(nt, nt+1)︸ ︷︷ ︸ α(T−1)σ2 +2
T−2∑ t=1
cov(nt, nt+2)︸ ︷︷ ︸ α2(T−2)σ2 +..+ 2 cov(n1, nT )︸ ︷︷ ︸ αT−1(1)σ2
(12)
For negatively correlated noise α ∈ (−1, 0) we can bound this term by
V( T∑ t=1 nt) = σ2(T + 2 T−1∑ τ=1 ατ (T − τ)) (13)
= σ2(T + 2 αT+1 − α2T + αT − α
(α− 1)2 ) (14)
= σ2(T + 2 (α− α2) (α− 1)2︸ ︷︷ ︸ ≤ 12α T + 2 αT+1 − α (α− 1)2︸ ︷︷ ︸ ≤ 12 ) (15)
≤ σ2(T (1 + α) + 1) (16)

heading: 6.5 PROOF OF THEOREM 3.1.
text: Proof. It holds that
err(RT−1 + ∆WT ) = ‖ T∑ t=1 ∆Wt − T−1∑ t=1 ∆W ∗t −RT−1 −∆WT ‖ = 0. (17)
Since S is a metric subspace, the projection ∆W ∗T = ProjS(RT−1 + ∆WT ) (18) uniquely solves the minimization problem in S.

heading: 6.6 ADDITIONAL RESULTS
text: 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.
x 1 x 5 x 25
x 12 5 x 62 5
x 25
00
Gradient Sparsity
x 2500 x 625 x 125
x 25 x 5 x 1
Te m
po ra
l S pa
rs ity Iteration 10000
114.3 115.2 121.6 168.8 517.6 3095.2
Iteration 20000
97.0 97.9 104.3 151.5 500.3 3077.9
Iteration 30000
90.4 91.3 97.6 144.8 493.7 3071.2
Iteration 50000
87.6 88.4 94.8 142.0 490.9 3068.4
Iteration 60000
87.5 88.4 94.8 142.0 490.8 3068.3
Figure 6: Perplexity for different levels of gradient sparsity and temporal sparsity at different stages of training. WordLSTM trained on PTB.

Review summaries:
Lowering costs for communicating weights between workers is an important intermediate goal for distributed optimization, since presumably it can limit the parallelization achievable once available bandwidth is saturated.  This work reports reasonable approaches to try to overcome this through a mix of techniques, though none in particular seem especially novel or surprising.  For example, the abstract claims a novel binarization method, but what is described in the paper does not seem especially novel (e.g. zero the negative weights and replace positives with their mean, if negative's mean < positive's mean, else vice versa); but more importantly, the experiments don't explore/support why this approach is any better (or when worse) than other schemes.