DeepReduce: A Sparse-tensor Communication Framework for Federated Deep Learning
Authors: Hang Xu
Kelly Kostopoulou
Aritra Dutta
Xin Li
Alexandros Ntoulas
Panos Kalnis
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Learning
Compressed Communication
Sparse Tensors
Bloom Filter

Abstract: Sparse tensors appear frequently in federated deep learning, either as a direct artifact of the deep neural network’s gradients, or as a result of an explicit sparsification process.  Existing communication primitives are agnostic to the peculiarities of deep learning; consequently, they impose unnecessary communication overhead. This paper introduces DeepReduce, a versatile framework for the compressed communication of sparse tensors, tailored to federated deep learning. DeepReduce decomposes sparse tensors into two sets,  values and indices,  and allows both independent and combined compression of these sets.  We support a variety of common compressors, such as Deflate for values, or run-length encoding for indices. We also propose two novel compression schemes that achieve superior results: curve fitting-based for values, and bloom filter-based for indices.  DeepReduce is orthogonal to existing gradient sparsifiers and can be applied in conjunction with them, transparently to the end-user, to significantly lower the communication overhead. As proof of concept, we implement our approach on TensorFlow and PyTorch. Our experiments with large real models demonstrate that DeepReduce transmits 320% less data than existing sparsifiers, without affecting accuracy. Code is available at https://github.com/hangxu0304/DeepReduce.

DeepReduce: A Sparse-tensor Communication Framework for Federated Deep Learning
Hang Xu KAUST hang. www.kuut..eeeeeoooooooua edu.
Kelly Kostopoulou
Aritra Dutta KAUST aritra. dutta@kaust. edu. sa
Columbia University
kelkostecs. dolkostacs..cllmmia. cow.sbia..mbbbbaeoooooao....e. edu
Xin University of Central Florida xin. 1i fucu edu
Alexandros Ntoulas
Panos Kalnis KAUST
NKUA
antoulas@di www.odiioou.g.ooo uoa.gr
panos kalnisskaust, edu. sa
Abstract
Sparse tensors appear frequently in federated deep learning, either as direct artifact of the deep neural network's gradients, or, as result of explicit sparsifi- cation process. Existing communication primitives are agnostic to the challenges deep learning; consequently, they impose unnecessary communication overhead. This paper introduces DeepReduce, versatile framework for the compressed communication of sparse tensors, tailored to federated deep learning. DeepReduce decomposes sparse tensors into two sets, values and indices, and allows both inde- pendent and combined compression of these sets. We support a variety of standard compressors, such Deflate for values, and Run-Length Encoding for indices. We also propose two novel compression schemes that achieve superior results: curve-fitting based for values, and bloom-filter based for indices. DeepReduce is orthogonal to existing gradient sparsifiers and can be applied in conjunction with them, transparently to the end-user, significantly lower the communication overhead. As a proof of concept, we implement our approach on TensorFlow and PyTorch. Our experiments with real models demonstrate that DeepReduce transmits 320% less data than existing sparsifiers, without affecting accuracy. Code is available at hbttps://githuu: httpta/bwww//aaaggooo/////o/oooa
Introduction
the training is typically performed by large number of resource-constraing client devices (e.g., smartphones), operating on their private data and computing local model. Periodically, subset of the devices is polled by central server that retrieves their gradients, updates the global model and broadcasts it back to the clients. The most constrained resource in client devices the network, either because the practically sustained bandwidth between remote clients and the server is low (typically, in the order of 25-50Mbps), or, the financial cost (c.g., data plans for 4G/5G mobile connections) high. On the other hand, deep neural network model sizes have been steadily increasing at much faster rate than the available bandwidth. Consequently, federated learning, is imperative to reduce the communicated data volume.
In federated learning +
55
One key observation that can help with reducing this volume is that the data exchanged during the Deep Neural Network (DNN) training often correspond to sparse tensors, i.c., tensors with many zero-value elements. Sparse tensors may be: (i) direct artifacts the training process; for instance, the gradients of the NCF 35 and DeepLight (18] models consist of roughly 40% and 99% zero elements, respectively; or (ii) explicitly generated by sparsification
76
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

V@
1 b,
6-4.0
Index 0
1
2
3
(b)
(keyvalue)
P10 P1
I-3
Value
0.0
4.0
4.6
0.0
5.2
0.0
5.3
4.0) (2.4.6) (4. 5.2) (7.
Size
132-256
421822 132)=256
8rb1=72
Figure 1: (a) Dense tensor format needs 256 bits; (b) sparse (key, value) form also needs 256 bits; (c) our method sends parameters, (a, b) as well as an 8-bit string, ie., 72 bits in total.
commonly used lossy (e.g., Top-r or Random-r) compression approach that selects only a few elements (with r typically < 1%).
Figure a depicts an example tensor containing 8 real values, 4 of which are zero; its dense represen- tation would require 256 bits. Typically, sparse tensors are represented as set of (key, value) pairs (see Figure [ b). where key is the index; notice, however, that the (key, value) representation also requires 256 bits, negating the benefit of sparsity. We show an example of our improved approach in Figure cc. We consider the indices as ordered list represented by a Boolean array of bits, such that the 1th bit '1' if and only if the corresponding gradient clement is non-zero. Moreover, we fit function, (i)
i + to the gradient values, with parameters, transmitting only the bit string and parameters (a, b). we can reconstruct the original tensor while requiring only 72 bits.
0.6 and b 4.0. By
The above example demonstrates a significant margin for additional compression for sparse tensors. Recent works (e.g., SKCompress 40 take advantage of these opportunities, but rely on tightly coupled index and value compression algorithm that benefits only some scenarios (see Section (). In practice, there exist complex trade-offs among data volume, model accuracy, and computational overhead, conjunction with system aspects, such as the network bandwidth and the communication
library (e.g.. NCCL [2], Gloo )2 Given that no single solution fits all scenarios, practitioners need the flcxibility to adjust how sparse tensors are compressed and transmitted for each particular DNN model and system configuration.
In this paper, we propose DeepReduce, framework for transmitting sparse tensors via a wide-area network, tailored for large-scale federated DNN training. Our contributions include:
(i) The DeepReduce framework, described in Section S that decomposes the sparse tensor into two sets, indices and values, and allows for independent and combined compression. By decoupling indices from values, our framework enables synergistic combination of variety of compressors in way that benefits each particular DNN and training setup. DeepReduce resides between the machine learning framework (e.g., Tensorflow, PyTorch) and the communication library. exposes an easy- to-use API that encapsulates a variety of existing methods, such as Run Length [33] and Huffman +
encoding for index compression; as well as Deflate [20] and QSGD 7 for value compression. DeepReduce also provides an index reordering abstraction, which is useful for combining value with index compressors.
(ii) Two novel compressors for sparse tensors: a Bloom-filter based index compressor (Section that reduces the size of keys by 50%, compared to the traditional (key, value) sparse representation; and a curve-fitting based value compressor (Section 5 that reduces the large values array to a small set of parameters. Both of our compressors do not affect the quality of the trained model.
(iii) An evaluation of DeepReduce on a variety of DNN models and applications (Section G). We demonstrate the practical applicability of our framework by realistic federated learning deployments on geographically remote, large-scale cloud infrastructures, and show that DeepReduce compresses already-spand data by up 320%, without affecting the training quality.
Background
Notations. By [d] we denote the set of natural numbers 21, d). We denote the cardinality and complement of a set X, by X and X respectively; x is the hth component of vector æ. By ats E RRd we denote an [S]-sparse vector, where S C [d] is its support. ||ж||| and || are the &z and Lo norm of a vector x, respectively. Class C¹ consists of all differentiable functions with continuous derivative and Var(a.)( denotes the variance of function [a bj over interval [a, 6].

---

Federated Learning (FL) trains models collaboratively on data stored in resource- consstrie-n heterogeneous and geographically remote client devices (c.g.. smartphones). At each round, a fraction of the participating clients are selected. After synchronizing with the server-side global model, the selected clients perform local training for some epochs over their private data. The server collects those updates, aggregates and applies them to the global model. Federated averaging (FedAvg) (55), is a popular instantiation of this process. Other variants exist, such as SCAFFOLD EE), FedNova [00 parallel SGD 185, local SGD [68] and FedProx AР Owing to insufficient communication bandwidth in FL, lossy compression is used to reduce the transmitted data volume; examples include
FedBoost
31 FedCOM
30 and FedPAQ [60].
Compressor 609 is random operator, C(-) R - R. that satisfies Eel|= C(x)Il < 2/
where > 0 is the compression factor and the expectation is taken over the randomness of C. Q= 1 --- 8 and 8 E (0, 11. C is d-compressor, denoted by Cs.
Sparsification. A rank-1 tensor that has mostly zero components is said to be sparse. Many modern DNNs are inherently sparse T8 35
and so are their gradients. Sparse gradients can also be
generated by compressor that sparsifies [51 71 76, II the gradient g to generate ğ E Ie via: g|i] = [g [)) = gli]. if E S, otherwise g = O. We assume that S C [d] is the support set of
such that 0 is r-sparse if and only if [S] = Two commonly used sparsifiers, Random-r [69] and
Top-r 8 both are 5-compressors. We refer to further details in Appendix A
Bloom filter [2] is a probabilistic data structure that represents the elements of a set S. Initially, is a bit string B of bits, all set to O. To insert element yj E S in the Bloom filter, we apply k independent hash functions h; on y5. Each h; yields a bit location in B, and changes that bit to 1. To query if yj S, we apply all k hash functions it. If (v,) = 0 for any E [R], then the element surely does not belong to S (i.e., no false negatives). In contrast, if h2 hy())) = 1 for all E [k]. then yj may or may not belong to S (i.e., possible false positives). The false positive rate (FPR) of B is:
= (1 e #|51/m}> see Lemma in Appendix A.2
3 System Architecture
DeepReduce (see Figure 12 in the Appendix) resides between the machine learning framework (e.g.. TensorFlow, PyTorch) and the communication library, and is optimized for federated DNN training. It offers simple API whose functions can be overridden to implement, with minimal effort, wide variety of index and value compression methods for sparse tensors. At the transmitting side, the input to DeepReduce is sparse tensor directly from the MI framework, for the case of inherently sparse models; or, is generated by an explicit sparsification process. In our implementation, we employ the GRACE M library for the sparsification operation, since it includes many popular sparsifiers; other libraries can also be used.
Sparse tensors typically represented (key, value) tuples. DeepReduce decouples the keys from the values and constructs two separate data structures. Let ğ Rd be the sparse gradient, where the number of model parameters and ||ğl|o = r, is the number of nonzero gradient elements. Let S be the set of indices corresponding to those elements. DeepReduce implements two equivalent representations of S: (i) an array of r integers; and (ii) a bit string B with bits, where Vi E [1,d], B|i] = 1 if and only if gli] *f 0. These two representations are useful for supporting a variety of index compressors; e.g., the bit string representation is used in 14.. The Index Compression module encapsulates the two representations and implements several algorithms for index compression. It supports both lossy compressors (e.g.. our Bloom- filterr based proposal). as well as lossless ones, such as the existing Run Length (RLE) g and Huffman (see Appendix A. there is also an option to bypass index compression.
38 27
encoders
The Value Compression module receives the sparse gradient values and compresses them indepen- dently. Several compressors, such as Deflate 200, QSGD 77). and our own curve-fitting based methods, are implemented. Again, there is an option to bypass value compression. Some compressors (e.g., our own proposals), require reordering of the gradient elements, which is handled by the Index reorder module. DeepReduce then combines, in one container, the compressed index and value
In contrast to FL. conventional data paralea, distributed training 87 synchronizes the updates from all workers each iteration (see Appendix A)
3

---

structures, the reordering information and any required metadata. Then, the container is passed to the communication library.
The receiving side mirrors the structure of the transmitter, but implements the inverse functions, that is, index and value decompression, and index reordering. The reconstructed sparse gradient is routed to GRACE for de-sparsification, or passed directly to the ML framework. It is worth mentioning that DeepReduce is general enough to represent popular existing methods that employ proprietary combined value and index compression. For example, SKCompress [H)] can be implemented in DeepReduce as follows: SketchML [39 plus Huffman for values, no index reordering, and delta encoding plus Huffman for indices.
Bloom Filter for Indices
This section introduces our novel Bloom-filte filter based, lossy index compressor. Recall that S is the set of r indices (i.e.. |S| = r) corresponding to the nonzero components of sparse gradient g. Let us insert each item of S into Bloom filter B of size m, using & hash functions.
Naïve Bloom filter. Let V be array of size containing the elements of that are indexed by S: formally: Vi E [1, (i) = g [(]]] DeepReduce transmits V and B. The receiver initializes ptr 1 and reconstructs the gradient follows:
for to d do 1" all d elements of gradient ğ Rd
i then g [ptrr] ptr++; else g[t]= =0
If were lossless, the algorithm would have perfectly reconstructed the gradient. However, Bloom filters exhibit false positives (FP). Assume a single FP at ptr = j: then, for S ptr S r, every V[ptr] value will be assigned the wrong gradient element. Therefore, FPs cause a disproportionaaely large error to the reconstructed gradient, significantly affecting the quality of the trained model.
No-error approach: Policy PO. To address this drawback of the naïve approach, we initialize set P and we modify the previous reconstruction algorithm as follows:
for = to d do 1" all d elements of gradient ğ E R *f
i 1 then insert i in P
P contains the union of the true and false positive responses of B. The transmitting worker can execute this algorithm and determine P' prior to any communication. With that information, it constructs array as follows: Vi E [1, |P| (ii ğ [[P]]] Essentially, V contains the gradient elements that correspond to both true and false positives. Therefore, the receiving worker can reconstruct the sparse gradient perfectly. The trade-off is increased data volume compared to Naïve, since the size
of V grows to r S PP S [r (2) compression error due to gradient, Cpa,s(9) resulted from policy PO in Lemma in Appendix B.2
Tox(2) (d - r)]; see Lemma 6 in Appendix B.2 We measure the
Random approach: Policy P1. To address the increased data volume issue of policy PO, this policy defines a new set of indices Š C P, where |$| = S is generated by randomly selecting elements from P. Consequently, array V is constructed as Vi [1,r] (i) g[S[i]]- Since $ * S in general, expected the error to be affected. Let k; |5 S and assume that the input gradient is inherently sparse, i.e., sparsifier Cs is the identify function la. For the combined compressor CPI.7a with policy Pl, we show in Appendix B.4 that El,g (p1.ta = (1 & )lll/12 Specifically, policy P1 creates lossy compressor with compression factor as good as Random-k In practice, DeepReduce allows Cs to be any sparsifier (e.g., Top-r 66, (). In this case, policy P1 is essentially equivalent a combined sparsifier, similar Elibol et al. 24 and Barnes et al. [ We give the total
compression eтror due to the compressed gradient (p,,((g) and other detailed analysis and proofs of error bounds in Lemma D in Appendix B.4
Conflict sets: Policy P2. PO and P1 represent two extremes: PO eliminates errors but sends more data than P1, whereas P1 sends fewer data but may introduce errors. Here, we propose policy P2, which transmits the same amount data as P1, but closer to PO in terms of error. Similar to P1, this policy generates set 5 C P. but makes better probabilistic choices. Intuitively, false positives are due to collisions in the Bloom filter, resulting in conflicts. P2 groups all items of P into conflict sets. Two elements x and y belong to conflict set C₁ if x, y E P and h; (x) = hxx))) ý for i, E [k], where j is the 5th bit of B and U, C, = P. Figure 2 shows example, with 4 items and 3 hash

---

X30
Sorted Estimates
The postiwe
Twiar poctive
True
Bloom
Value
Fikker
0
1
0
0
O
D
Conflice
sees
fz2
I5
hop
F12
110
112
-4
Index
x10*
Figure 2: Policy P2, with 3 hash functions and con- Figure 3: Piece-wise (8 pieces) value fitting on a flict sets.
convolution layer gradient of ResNet20 (CIFAR-10).
functions; item iz is false positive and there exist 8 conflict sets. If a set Cj contains only one item, it is guaranteed to be a true positive, so it is added to S. Else, if Cj contains many items, random subset is inserted into S. Therefore, it is possible that some false positives are included in S. but the probability is smaller, compared to policy Pl. We present the pseudo-code of policy P2 in Algorithm Appendix B35 For Hash functions used and efficient GPU implementation PyTorch, refer to Appendix
5 Curve Fitting for Values
Figure B shows,, in light blue, the gradient values for one layer of ResNet20 on CIFAR-10. By sorting those values, we obtain a curve that can be approximated as a smooth conver curve. Taking advantage of this observation, we propose novel curve fitting- based value compression approach that results into high compression ratios, even after considering the overhead of mapping the original to the sorted values. contrast, modelling DNN gradients by using statistical distributions (26 54 both restrictive and model specific.
Formally, we sort the nonzero values of the sparse gradient, Cs(gt) resulting from stochastic gradient, Ie each iteration t, in descending order and denote (9() E Rd. Let Cs(9t) follow the hierarchical model: (gt) St + alt, where &. N0, Ia). Vfr E Rd is the sorted oracle gradient and a E + the model commonly used in signal processing for approximation problems [5] 4ll M. With these assumptions, we show how to fit regression models D == Ci,Cs (s( [i] V and calculate the fitting error.
Nonlinear approximation. We employ a nonlinear approximation by using splines with free knots, which consists of splitting the sorted curve into segments and fitting each segment individually. Finding the locations of the knots is where the nonlincarity and difficulties are (cf. (6].. Although existing numerical algorithms can find the best splines with free knots, they computationally inten- sive and unsuitable for our use at each iteration of DNN training. Because we aim at approximating a smooth convex curve, we use the following procedure by selecting the knot one by one. We explain how this is done for the positive sorted values; similar idea applies to the negative sorted values. Let the whole gradient be sorted in descending manner; set [1]. with 1 < d corresponds to indices of the sorted positive values. Let y = mæ + be the line joining (1, (1) and (I, (1)()) Calculate de = (y (()) where y; mi c. Choose the sorted gradient component that corresponds to max d; as the segmentation point (a knot). The process continues until the desired number of segments is reached. We stop segmentation if the number of points in a segment is less than (n' + 1), where n' is the degree of the polynomial used fit on each segment. The following Proposition justifies our procedure above.
Lemma 1. (Knot selection) If f is differentiable convex function on (a, b), then the point x" E (a, b) that gives the best approximation to f using line segments from (a, [a)) to (x", ff(x))) and then from ( f(x")) to (b, (b)) the same point + that maximizes the difference between f and the line segment connecting (a. f())) to (b, f(b).
Polynomial regression. Over each segment, we apply polynomial regression. Due to limited space, we focus on the piece-wise linear fit, and have the following result with explicit constants. For the results on picce-wise constant approximation, see Lemma in Appendix C
5

---

Table 1: Benchmarks and datasets; last column shows the best quality achieved by the no-compression baseline.
Type CNN
Model
Faramcicrs
Optimizer
Baselinc
RosNes-20 81
Image classif.
CIFAR-I0
269,722
SGD-M 53
TFlow
Tap-1 Acc.
90.949
DenseNettO-Kl K12 RM
Image classif.
CIFAR-10
18
357,491
SGD-M
TFlow
Top- Acc.
91.76%
ResNet-00
Inage classif.
ImaggNNe
25.557,032
SGD-M
TFlw
Top-1 Acc.
73.78%
MLP
NCP [S
Recommnenatiion
Maviclens- 20M 66
31,832577
Adam 46
Py lorch
Best Hir Rote
944.97%
RNN
LSTM
word piod.
Overllow
4,053,228
FedAvg 65
Porch
Top-1
13.56%
Lemma 2. (Error of piece-wise linear fit) For Cg(g) C² ((1, with Varp (C S M, we n² for some & E S set of piece-wise linear splines with p knots.
have ||s Cs(g))lac S
2M
Note that, the least squares error less than vdlls Cs(g) zo. and can be controlled by using large p (see Remark | in the Appendix). We provide here heuristic to calculate from Lemma 2 First, we calculate M = (Cs [1) Cs (g)g) (Cs(g)ld 1] (s(g)) By considering pe as a function of p. we can find the closed-form solution for p as [2
the error bound 2M
Nonlinear regression. We can use nonlinear regression for value fitting, e.g.. through double exponential model, y = ae + cede, where (a, b, c, d) E I are the parameters; refer to Section 6
For the theoretical analysis of compression error from regression, see Appendix we provide the compression error from joint value and index compression. Also, see Appendix D.I
In Appendix D
for comments regarding the convergence of the approach. Finally, refer to Appendix E for an efficient GPU and CPU implementation of our polynomial regression on PyTorch and TensorFlow. and the
combined index and value compression. For overall complexities of the compression methods we
also refer Appendix
Experimental Evaluation
Implementation. DeepReduce supports TensorFlow and Pytorch. We provide various versions of our index and value compressors, on CPUs and GPUs. We also instantiate our framework with combinations of existing methods, namely Huffman and RLE for index compression, as well as We denote implementations that use DeepReduce by DR val where idæ, val are the index and value compression methods, respectively.
Deflate and QSGD 7 for value compression; see Appendix F
Testbed. We set up realistic federated learning testbed on Amazon AWS. The server is an EC2 instance located in Ohio, whereas the clients are 56 geographically remote instances spread across regions throughout the globe (i.e., Tokyo, Central Canada, Northern Californaa, Seoul, São Paulo, Paris and Oregon). Each instance is equipped with a 4-core Intel CPU 2. 2,50Hz,, 16GB RAM, and an NVIDIA Tesla T4 GPU with 16 GB no-board memory (see Appendix F. for details). We also run simulated deployments on a local cluster of nodes, each with a 16 16-core Intel CPU 2.6GHz, 512GB RAM, one NVIDIA Tesla V100 GPU with 16 GB on-board memory and 100Gbps network.
Benchmarks. We employ the popular FedML 33 benchmark that uses LSTM model [59] to
perform next-word prediction in a federated learning setting, on the Stack Overflow [67] dataset with 135,818.733 training and 16,586,035 test examples; the dataset follows real-life partitioning
among 342,44 477 clients. We also use industry-standan benchmarks from TensorFlow [52] 75 and NVIDIA 57 on image classification and recomendation; refer to Table 1 for details.
6.1
Simulated deployment on local testbed
First, we run set of experiments on our local cluster to validate our index and value compressors.
Bloom filter-based index compression. Figure depicts the convergence timeline for our three index compression polices for ResNet-20 on CIFAR- 10; FPR is set to 10-3 (refer to Appendix F for the effect of varying FPR). We compare against the no-compression baseline, as well as the plain Top- r sparsifier (r = 1 1%). All our policies converge to the same top-1 accuracy as the no-compression baseline, but BF-PO converges in fewer training epochs. It is worth noting that BF-PO converges faster than the plain Top-r sparsifier, despite transmitting 33% fewer data (refer to Figure 15c in the Appendix). Note that BF-naive (Section B achieves much lower accuracy, justifying the need for our proposed policies. Similar results were observed for DenseNet40-KG K-12 see Appendix

---

Baseline
DR -aa DRG
Baseling
DR
Top-f
DRG.
Top-r
DR DRR
Top-1 Accuracy
Top-1 Accuracyy
0.6
0.4
0.4
0.2
0.2
6
8
Steps (x10²)
Steps (x10²)
Figure 4: Convergence timeline of bloom filter
Figure 5:
Convergence timeline of value pressors ResNet-20 on CIFAR- 1%. Pit-Poly
policies for ResNet-20 on CIFAR- 10: FPR 0.001,
r 1%. gr- converges the fastest.
DR Dixp is slightly better than DR
Curve fitting-based value compression. Figure shows the converge timeline for our two curve fitting-based value compressors, Fit-Poly and Fit-DExp, ResNet-20 with CIFAR-I0. The sparse input gradients were generated by Top-r (r = 1%). Fit-Poly uses polynomials with degree (i.e., coefficients). Fit-DExp requires 4 coefficients without segmentation. Both methods converge the same accuracy as the co-compresiion baseline; also, both converge in fewer steps than plain Top-r. Fit-DExp sends fewer data: it compresses the output of Top-r by roughly 50%, whereas Fit-Poly compresses it by around 40%. However, the computational overhead of compression for Fit-DExp is roughly 3.5x more than Fit-Poly's: s; details about the data volume and runtime in Figure
DeepReduce for inherently sparse model. DeepReduce is designed to work either in conjunction with sparsifier (e.g., Top-r), or be applied directly on models such as the NCF 65 and DeepLight [8] that exhibit inherently sparse gradients. In this experiment, we train NCF ML-20m, with 10 local batch size. We test DR which uses BF-PO (FPR=0.6) for indices, but combines with QSGD Fi. an existing method for value compression. This demonstrates that DeepReduce is compatible with various existing compressors. We compare against SKCompress 40., an improved version of SketchML [3 optimized for sparse tensors. Table66in the Appendix shows the results. All methods achieve virtually the same best hit rate (i.e., the quality metric for NCF), and both DR and SKCompress reduce the data volume by 5x compared with Bascline. However, in practice DR BF- 380x faster in terms of compression and decompression time. Appendix DeepReduce against 3LC (50) and SketchMI. 39
be more easily implemented GPUs; in Figure Sb show that it is
F we also compare
larger benchmark, ResNet-50 on ImageNet.
6.2 Realistic Federated Learning deployment in the cloud
In this section,
+ benchmark to deploy realistic federated learning system the FedML
dataset naturally partitioned among 342,477 clients. At each round, the server randomly selects 56 clients to communicate. Those clients activated on physical EC2 instances in Amazon AWS, located at geographically remote data centers all over the world. Each client executes 1 local epoch; the learning rate is 0.3 and the batch size is 16. Sparsification is performed on tensors with more than dimension, by bidirectional Top-r (r 10%) compression with error feedback on the model updates. We execute 200 rounds and achieve 18.56% test accuracy, which is consistent with the FedML benchmark. We give pseudocode of FedAvg with DeepReduce in Algorithm 2 in Appendix
in the cloud. The real Stack Overflow
677
Communication cost and computational overhead for compression. Since the most constrained resource in federated learning is the network, our main target is to minimize the amount of transferred data. We measure separately the amount of transferred data from server-to-client (S2C) and client- to-server (C2S). Our baseline is the popular FedAvg (55) algorithm; we also compare against the plain Top-r sparsifier (r 10%). Table shows the results for three instantiations of DeepReduce. In cases DeepReduce compresses significantly the already-sparse data. In particular, DR transmits only 6.2% of the original data, which is 3.2x less than Top-r, while the test accuracy
QSGD

---

Table 2: Time breakdown data volume of DeepReduce variants, Top-r, and Baseline (FedAvg 5SS ) a FL setting. (CLI, SER, S2C and C2S stand for Client, Server, Server-to- and Client-to-Server, respectively.)
Average Baroding/Kcccddigg Time
Avg. Comm.
Time (5)
Avg.
Data Volume haseline)
Accurncy
SER goods
SER
S2C
C2S
S2C
C2S
Baseline
0
0
0
1.6014
16117
1,0
10
0,1856
Top-r (10%)
0,0035
0.0266
0.0299
0.3033
0.1840
DR
0.0181
0.0623
0.0161
0.0574
0.7763
0.7986
0.1425
0,1426
0.1841
DR Pi--Pyy
0.0187
0.1178
0,0175
0.1024
0.6858
0.6876
0.1039
0.10.99
0.1838
e Pg
Uscap
0.0754
0,0691
0.0621
0.0621
0.1836
Test Accurady
0.175
Forward & Backward
Communication
Encoding Decoding
Baseline
100 Mbps (FP32)
10 Gaps (FP32)
0.125
Top-r
0.100
-R
-Pay
DRC
0.075
Tope
0.050
(R
Hauthe
25
50
75
100 Round
125
150
175
200
10
15
(6)
1
2
(5)
Figure 6: Convergence timeline of training RNN to do next-word-rredictinn datasets. DecpReduce on Top-r exhibits the same convergence rate as Top-r in FL setting.
Figure 7: Time breakdown in one iteration training of NCF on ml-20m. We show the speedup of training by DeepReduce on 4 nodes with different network bandwidth: 100Mbps vs. 10Gbps
Stack Overflow
remains virtually unaffected. The high quality of the resulting models is also confirmed in Figure 5 which shows the convergence timeline of the training. For completeness, Table 2 also reports the computational overhead for encoding and decoding, although this is not primary concern. DeepReduce is 1.5-3.4x slower than Top-r, but in practice the overhead is within acceptable limits (i.e., less than 19msec). Despite the higher computational overhead, the average communication time is still up to 15% lower for DeepReduce compared to Top-r, and up to 2.3x lower compared to Baseline; the moderate gain is due to the high latency between geographically remote data centers in the Amazon AWS cloud. See test-accuracy vs. wall clock time, and server to client and client to server communication time (with error bars) in Figures 20 and 21 respectively, in Appendix [
6.3 Practical applicability of DeepReduce
Any operation on the gradient imposes computational overheads that may exceed the benefits of the reduced data volume and affect the practical applicability, as discussed below.
Suitability for federated learning. We profile diverse deployments by training NCF on ML-20m and measuring the wall clock time of the various components. We employ gradient accumulation with 10 accumulations per iteration and 10 local batch size. We use NCCL Allreduce for baseline communication, and NCCL Allgather for Top-r (r 10%) and DeepReduce. We vary the network bandwidth from 100Mbps (typical for remote smartphones or IoT clients) up to 10Gbps (typical for local server clusters). Figure 7 shows the wall time, in three components: forward and back- propagation, encoding / decoding, and communication. Gradient compression is useful only when the ratio of communication over computation cost is high (i.c., lower bandwidth). This is consistent with the findings in [53 58 and reinforces our claim that DeepReduce is beneficial for federated learning deployments.
Data volume and computational overhead. In Figure Sa we show the data volume (relative to the no-compression baseline) separately for values and indices, for various instantiations of DeepReduce. We test Resnet-20 on CIFAR-10 10 and generate sparse tensors by Top-r. We compare against SKCompress, which also operates the sparse tensor. For fairness, parameters are selected such that all methods achieve similar accuracy. Although the ratio of index over value data volume differs for each combination of DeepReduce, all versions transmit fewer data than plain Top-r. Interestingly, SKCompress performs the best; however, this depends on the particular model.
Figure 8b shows, in logarithmic scale, the computational overhead of compression and decompression measured by the wall clock runtime. We implement all methods by utilizing the best available libraries either on CPUs or GPUs; acknowledge there remains margin for improvement. Nonetheless, this
8

---

2.00%
Vilee Irece
Decade
Relejive Deta Volume
10:7
2.00%
0.79%
Exccutton tim
Lond
UPU
0.50%
10
0.25%
Sitempees
10-1
Sizungres
(a) Data volume
(b) Run time
Figure 8: Comparing various compression methods on the Top-r(1 () values of convolution gradient in ResNet-20 (gradient size: 36,864). (a) Data volume (b) Encoding and decoding runtime
experiment demonstrates the significant variation in terms of overhead among methods; for instance, SKCompress is 3 orders of magnitude slower, compared to DR QSGD
The previous experiment demonstrates that the practical benefit of any compressor, including DeepReduce, depends on multiple factors that affect the communication over computation ratio. Those include the communication library (c.g., NCCL, Gloo), the implementation details of each compressor, the computing hardware (e.g., faster GPUs), possible accelerators (c.g., NICs with FPGAs), and others. The advantage of DeepReduce lies in its versatility to intermix various index and value compressors, match the requirements of each specific model and system configuration.
Discussion.
7 Related Work
Gradient compression is commonly employed alleviate the network bottleneck in distributed
training. Four main families of compression methods exist (refer to [84] for a survey): (i) Quantization
45
6
X2] where each tensor element is replaced by lower precision
(e.g., float8
instead of float32), to achieve in practice compression ratios in the order of 4x 8x 84 (ii)
Sparsification 6 ST
76. HТ. where only few elements (e.g., Top-r or Random-r) of
the tensor are selected; it can achieve compression ratios of 100x or more. (ii)) Hybrid methods
100
which combine quantization with sparsification to achieve higher compression. Low-rank methods
39 50
70
(iv)
[15 78
that decompose the tensor into low-rank components.
SketchML and SK SKCoppress. In SketchML [39], the nonzero gradient elements are quantized into buckets using a non-uniform quantile sketch. The number of buckets is further reduced via hash tables that resolve collisions by a Min-Max strategy. SK SKCompress 40 improves SketchML by additional Huffman coding on the bucket indices well as the prefix of delta keys. Both of these methods can be viewed as special cases of DeepReduce.
Hybrid compressors. Qsparse local SGD 10) combines quantization with Top-r or Random-r sparsifiers. Strom al. 770 and Dryden et al. (2 use fixed and adaptive threshold, respectively, to sparsify. Elibol et al. [24] combine Top-r with randomized unbiased coordinate descent. Barnes al. in 19. perform a Top-m selection of each local gradient and communicate r < m randomly chosen components. Double quantization
[86] is an asynchronous approach that integrates gradient sparsification with model parameter and gradient quantization. The output sparse gradient of hybrid methods can be the input to our framework; therefore, our work is orthogonal.
Sparse tensor communication. Communication libraries typically transmit sparse tensors via Allgather [1. because the more efficient Allreduce collective only supports dense tensors. In contrast, ScaleCom [|]] tailors Allreduce to sparse data. OmniReduce [25] also implements sparse Allreduce that sends the non-zero blocks to the workers in an all-to-all manner. SparCML [61] adaptively switches between Allreduce and Allgather based global gradient sparsity among the workers. SwitchMI. 622 is a hardware approach that aggregates the model updates in programmable network switches.

---

8 Conclusions
Sparse tensors are ubiquitous in federated DNN training. DeepReduce integrates seamlessly with popular machine learning frameworks and provides an easy-to-use API for the effortless implementa- tion of wide variety of sparse tensor communication methods. We instantiate DeepReduce both with existing index and value compressors, as well as with two novel methods: Bloom fller-based index compressor and a curve fitting-based value compressor. We demonstrate its practical applicability by realistic deployment in the cloud. DeepReduce is available open-source and can be used to significantly lower the communication overhead large-scale federated learning deployments.
References
[1] API Horovod documentation.
htm #mooull horoood......oo.ooo tensorflon
[2] Necl: Nvidia collective communication /btpyy....re///ooo........d..da.
[3] Numpy: API reference.
numpy. wow.yooolllfftttooe
[4] pybloomfilter library. https://axiak, http:///wwa....aaaa...o//ttoaaat
[5] Felix Abramovich, Yoav Benjamini, David L Donoho, lain M Johnstone, et al. Adapting to unknown sparsity by controlling the false discovery rate. The Annals of Statisstic,,44())) 34(2):584-653, 2006.
[6] Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proc. of EMNLP, pages 440-445, 2017.
[7] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effiiien SGD via gradient quantization and encoding. In Proc. of NeurlPS, pages 1709-1720, 2017.
[8] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Proc. of NeurlPS, pages 5977-5987, 2018.
[9] Leighton Pate Barnes, Huseyin A Inan, Berivan Isik, and Ayfer Özgüir. rTop-k: A Statistical Estimation Approach to Distributed SGD. IEEE Journal on Selected Areas in Information Theory, 2020.
[10] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-ee Distributed SGD with quantization, sparsification, and local computations. In Proc. of NeurIPS, pages 14668-14679, 2019.
[11] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. SIGNSGD: Compressed optimisation for non-convex problems. Proc. of ICML, pages 559-568, 2018.
[12] Andrei Broder and Michael Mitzenmacher. Network applications of bloom filters: A survey. Internet mathematics, 1(4):855550 509, 2004.
[13] Chia-Y Yu Chen, Jiamin Ni, Songtao Lu, Xiaodong Cui, Pin- Yu Chen, Xiao Sun, et al. Scalecom: Scalable sparsified gradient compression for communication-effiiennt distributed training. In NeurlPS, pages 13551-13563, 2020.
[14] Yu-Hsin Chen, Tushar Krishna, Joel S Emer, and Vivienne Sze. Eyeriss: An energy- efficite reconfigurable accelerator for deep convolutional neural networks. IEEE Journal of Solid- -tate Circuits, 52(1):127-138, 2016.
[15] Minsik Chol, Vinod Muthusamy, and Ruchir Nemanich1, Brad Puri. GradZip: Gradient Compression using Alternating Matrix Factorization for Large-scale Deep Learning. In Proc. of NeurIPS Systems for ML Workshop, 2019.
10

---

[16] Maurice Cox, Peter Harris, and Paul Kenward. Fixed- and free-knot univariate least-square data approximation by polynomial splines. In Proc. of ISAAC, pages 330-345, 2001.
[17] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: Large-Scale Hierarchical Image Database. In Proc. of CVPR, pages 248 225,225522 2009.
[18] Wei Deng, Junwei Pan, Tian Zhou, Deguang Kong, Aaron Flores, and Guang Lin. Deeplight: Deep lightweight feature interactions for accelerating ctr predictions in ad serving, In Proc. of WSDM, pages 922-930, 2021.
[19] Tim Dettmers. 8-bit approximations for parallelism in deep learning. Proc. of ICLR, 2016.
[20] Peter Deutsch. Deflate compressed data format specification version 1.3. IETF RFC 1951,
1996.
[21] Ronald A DeVore and George G Lorentz. Constructive approximation, volume 303. Springer Science & Business Media, 1993.
[22] Nikoli Dryden, Tim Moon, Sam Ade Jacobs, and Brian Van Essen. Communication quantization for data-parallel training of deep neural networks. In Proc. of MLHIP., pages 1-8, 2016.
[23] Aritra Dutta, EI Houcine Bergou, Ahmed M. Abdelmoniem, Chen- Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning, In
Proc. of AAAI, volume 34, pages 3817-3824, 2020.
[24] Melih Elibol, Lihua Lei, and Michael I Jordan. Variance reduction with sparse gradients. In Proc. of ICLR, 2019.
(25] Jiawei Fei, Chen- Yu Ho, Atal Narayan Sahu, Marco Canini, and Amedeo Sapio. Efficient sparse collective communication and its application to accelerate distributed deep learning. In Proc. of SIGCOMM, 2021.
[26] Fangcheng Fu, Yuzheng Hu, Yihan He, Jiawei Jiang, Yingxia Shao, Ce Zhang, and Bin Cui. Don't t waste your bits! squeeze activations and gradients for deep neural networks via tinyscript. In Proc. of ICML, pages
2020.
[27] Rishikesh R. Gajjala, Shashwat Banchhor, Ahmed M. Abdelmoniem, Aritra Dutta, Marco Canini, and Panos Kalnis. Huffmman coding based encoding techniques for fast distributed deep learning. In Proc. of ACM CoNEXT 1st Workshop on Distributed Machine Learning (DistributedML. '20), pages 21-27, 2020.
[28] Shiming Ge, Zhao Luo, Shengwei Zhao, Xin Jin, and Xiao Yu Zhang. Compressing deep neural networks for efficient visual inference. In Proc. of ICME, pages 667-672, 2017.
[29] Gloo: Collective communicationn library with various primitives for multi-machine training.
[30] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In Proc, of AISTATS, pages 2350-2358, 2021.
[31] Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. FedBoost: A communication- efficient algorithm for federated learning. In Proc. of ICML, pages 3973-3983 2020.
[32] Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Proc. of ICLR, 2016.
[33] Chaoyang He, Songze Li, Jinhyun So, Xiao Zeng. Mi Zhang, Hongyi Wang. Xiaoyang Wang. Pranceth Vepakomma, Abhishek Singh, Hang Qiu, et al. Fedml: A research library and benchmark for federated machine learning. arXiv preprint arXiv:2007.13518 2020.
[34] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. of CVPR, pages 770-778, 2016.

---

[35] Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural Collaborative Filtering. In Proc. of WWW, pages 173-182, 2017.
[36] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 1004.04770444611 2017.
[37] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely Connected Convolutional Networks. In Proc. of CVPR, pages 2261-2269, 2017.
[38] David A. Huffman. method for the construction of minimum-redundancy codes. In Proc. of IRE, volume 40, pages 1098- 1101, 1952.
[39] Jiawei Jiang, Fangcheng Fu, Tong Yang, and Bin Cui. SketchMI.: Accelerating distributed machine learning with data sketches. In Proc. of SIGMOD, pages 1269-1284, 2018.
[40] Jiawei Jiang, Fangcheng Fu, Tong Yang. Yingxia Shao, and Bin Cui. Skcompress: compressing sparse and nonuniform gradient in distributed machine learning. The VLDB Journal, pages 1-28, 2020.
[41] lain M. Johnstone, On minimax estimation of sparse normal mean vector. The Annals of Statistics, pages 271-289, 1994.
[42] Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazeer, and Yonghui Wu. Exploring the limits of language modeling. arXiv preprint arXiv:160..02410, 2016.
[43] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Bennis, et al. Advances and open problems in federated learning. arXiv preprint 191.:499, 2019.
[44] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Proc. of ICML, pages 1133,,143,00 2020.
[45] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Proc. of ICML, pages 3252-3261, 2019.
[46] Diederik P. Kingma and Jimmy Ba. ADAM: A Method for Stochastic Optimization. In Proc. of ICLR, 2015.
[47] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In Proc. of NeurlPS Workshop Private Multi-Party Machine Leurning, 2016.
[48] Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features From Tiny Images. Technical report, University of Toronto, 1(4), 2009.
[49] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proc. of MLSys, pages 429-450 2020.
[50] Hyeontaek Lim, David G. Andersen, and Michael Kaminsky. 3LC: Lightweight and Effictive Traffic Compression for Distributed Machine Learning. In Proc. of MI pages 53-64, 2019.
[51] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally, Deep gradient compression: Reducing the communication bandwidth for distributed training. In Proc. of ICLR, 2018.
[52] LSTM-PTB.
renn
[53] I.. Luo, J. Nelson, I. Ceze, A. Phanishayee, and A. Krishnamurthy, PHub: Rack-Scale Parameter Server for Distributed Deep Neural Network Training. In Proc. of SoCC, pages 41-54, 2018.
12

---

[54] Ahmed M Abdelmoniem. Ahmed Elzanaty, Mohamed-She Alouini, and Marco Canini. An Efficient Statistical-basel Gradient Compression Technique for Distributed Training Systems. In Proc. of MISSs,, 2021.
[55] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--Fficcenn Learning of Deep Networks from Decentralized Data. Proc. of AISTATS, volume 54, pages 1273-1282, 2017.
[56]
Movielens, httppe//ggooo..a...rrrrrraaattts
[57] Nvidia deep learning
[58] Yanghua Peng, Yibo Zhu, Yangrui Chen, Yixin Bao, Bairen Yi. Chang Lan, Chuan Wu, and Chuanxiong Guo. A Generic Communication Scheduler for Distributed DNN Training Acceleration. In Proc. of SOSP, pages 16-29, 2019.
[59] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. In Proc. of ICLR, 2021.
[60] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication--ffiiene federated learning method with periodic averaging and quantization. In Proc. of AISTATS, pages 2021-2031, 2020.
[61] Cèdric Renggli, Salch Ashkboos, Mehdi Aghagolzadeh, Dan Alistarh, and Torsten Hoefler. Spareml: High-performance sparse communication for machine learning. In Proc.of the Int. Conf. for High Performance Computing, Networking, Storage and Analysis, pages 1-15, 2019.
[62] Amedeo Sapio. Marco Canini, Chen- Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik. Scaling Distributed Machine Learning with In-Network Aggregation. In Proceedings of NSDI, 2021.
[63] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- mara-parlllel distributed training of speech DNNs. In Proc. of INTERSPEECH, pages 1058-1062, 2014.
[64] Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in TensorFlow. arXiv preprint (rxXiv:8802.00 00789999.999 2018
[65] Anil Shanbhag, Holger Pirk, and Samuel Madden. Efficient Top-K Query Processing Massively Parallel Hardware. In Proceedings of International Conference on Management of Data (SIGMOD), page 1557-1570, 2018.
[66] Shaohuai Shi, Xiaowen Chu, Ka Chun Cheung, and Simon See. Understanding top-k sparsifica- tion distributed deep learning.
2019.
[67] TensorFlow Federated Stack Overflow dataset. federated/agee http://......ttooo.../../oattatt
org/
[68] Sebastian U Stich. Local SGD converges fast and communicates little. In Proc. of ICLR, 2018
[69] Sebastian U Stich, -aptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Proc. of NeurlPS, pages 4447-4458, 2018.
[70] N. Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Proc. of INTERSPEECH, pages 1488-1499 2015.
[71] Haobo Sun, Yingxia Shao, Jiawei Jiang, Bin Cui, Kai Lei. Yu Xu, and Jiang Wang. Sparse Gradient Compression for Distributed SGD. In Proc. of DASFAA, pages
2019.
[72] Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed mean estimation with limited communication. In Proc. of ICML, pages - 0337,, 2017.
[73] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In Proc. of ICML, pages 1139-1147, 2013.
13

---

[74] TT. Cai, W. G. Sun, and W. Wang. Dovariate-assistee ranking and screening for large-scale two- sample inference. Journal of the Royal Statistical Society: Series (Statistical Methodology), 8 81(2):187-234, 2019.
[75] TensorFlow benchmark. httppp///ggthhooccc////oor/ooo/a
[76] Yusuke Tsuzuku, Hiroto Imachi, and Takuya Akiba. Variance-based gradient compression for efficient distributed deep learning. In Proc. of ICLR, 2018.
[77] Sharan Vaswani, Francis Bach, and Mark Schmidt, Fast and faster convergence of SGD) for over- parameterized models and an accelerated perceptron. In Proc. of AISTATS, pages 1195-1204, 2019.
[78] Thijs Vogels, Sai Praneeth Reddy Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. Proc. of NeurIPS, pages 14259-14268, 2019.
[79] Hongyi Wang. Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication- offficient learning via atomic sparsification, In Proc. of NeurlPS, pages 9850-9861. 2018.
[80] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, pages 761 1-11-76,3, 2020.
[81] Jianqiao Wangni, Jialei Wang. Ji Liu, and Tong Zhang. Gradient sparsification for communication-efiie -fffiiient distributed optimization. In Proc. of NeurlPS, pages 1316-1 2018.
[82] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Proc. of NeurlPS, pages 1508-1518, 2017.
[83] Ross N Williams. Adaptive Data Compression, volume 110. Springer Science & Business Media, 2012.
[84] Hang Xu, Chen-Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, Konstantinos Karatsenidis El Houcine Bergou, Marco Canini, and Panos Kalnis. GRACE: A Compressed Communication Framework for Distributed Machine Learning. In Proc. of ICDCS, 2021.
[85] Hao Yu, S. Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proc. of AAAI, pages 5693-5700, 2019.
[86] Yue Yu, Jiaxiang Wu, and Longbo Huang. Double quantization for communication-effioii distributed optimization. In Proc. of NeurlPS, pages 4438 4449, 2019.
[87] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient descent. In Proc. of NeurIPS, pages 2595-2603, 2010.
14


Reviews:
[{"review_id": "Q5XUjCfBfwq", "reviewer": "Reviewer_Rrbz", "summary": "Problem: Communication overheads in the current FL setup, especially while transferring deep model gradients from clients to server and vice-versa. \nSolution: The proposed DeepReduce framework offers to communicate sparse tensors in federated setup. Supports both the existing approaches for sparse communication as well as proposes two novel methods.\nResults: A significant reduction in the transfer of data over the existing techniques.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Distinction from state-of-the-art:\nWell motivated with a focus on network bandwidths and communication costs. Accurately positions with-in the literature with a discussion on implicit ([18], [35]) and explicit ([6],[51],[68], etc) sparse models, different sparsification techniques. The entire related work section is also interesting.\n\nPros:\nThe paper is well written, easy to understand and digest the concepts.\n\nThe proposed method is solid with theoretical proofs and upper bounds on the errors for various parts such as curve fitting, etc.\n\nThe details of communication and compute (encoding and decoding times) values in Figure 8 are also impressive. Yes, there is room for improvement but this is an interesting ablation study.\n\nCons:\n\nThis is really a useful approach to save memory, especially very useful in low resource scenarios. However, the proposed approach as it is requires a few more additions for better understanding. Read the main+supplementary material, I can not see a standardization of the savings in space and communication costs along with the overheads in compute. To address these, i) please provide an overall algorithm, even in the appendix, if needed; ii) provide Big-O notations for the space, compute and communications; iii) compare and contrast with the existing methods. This actually gives a better understanding of how the proposed approach differs from the state-of-the-art.\n\nThe overhead of fitting an equation, V(i) for representing a sparse tensor sounds expensive. How accurate are these curve fittings? How many equations does one need per gradient? Does the error not propagate further with an approximation on these values?\n\n\nThe number of references are too many for a conference paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have to describe the limitations in detail.\n\nHowever, my observation is that there is a significant room for improvement in overheads of computation, which will be useful for FL with meager resources on-device. The lossy compression with curve-fitting may need improvements", "review_text": "", "extra_scores": {"ethical_concerns": "None to the best of my knowledge", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "> 5 "}, "extra_text": {}}, {"review_id": "Dw_61icXzg", "reviewer": "Reviewer_E2i3", "summary": "This paper proposed framework DeepReduce for the compressed communication of sparse tensors. In practice, sparsed tensors will be represented by (Index, Value) set. DeepReduce contains a series of algorithm to further compress Indices and Values. \n\nFirstly,  Bloom filter is a space-efficient probabilistic data structure, that is used to test whether an element is a member of a set. This paper use Bloom-filter as a lossy index compressor to determine whether an index is corresponding to a nonzero gradient. Furthermore, this paper proposes to use interpolation functions to fit a curve for relation between index and value. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: \n\nThis paper can be considered as a good combination of existing techniques.  \n\n**Quality**: \n\n1. Bloom Filter is a random data structure with relatively high rate leading to false positives. Thus, some false positive indices may bring model divergence or unexpected outcome. \n2. The gradients selected by Gradient Sparsification algorithm  tend to be important to model convergence in distributed learning. Using lossy compressor with numerical error is kind of waste in resource limited federated learning.\n3. The trade-off between communication and precision is not well-explained. \n4. Bloom-filter based index compressor is a important part in this paper, but the detailed implementation of Bloom-filter used in this paper is not clearly described (especially Hash functions used in Bloom-filter and actual hyper-parameters of Bloom-filter in experiments and so on).   \n\n**Clarity**:\n\nThis paper is well-organized but some points are not clear.  Some figures (e.g., figure 11, figure 12, algorithm 1) can improve reading experience, but can be found only in supplementary. The interpretation of mathematical symbols is quitemessy. \n\n**Significance**:\n\nThe experimental evaluation is not sufficient.  The experiments in this paper did not show the advantages of its framework.\n\n1. Top-r is not good enough to be a compression baseline. DGC  is widely accepted as a SOTA in Gradient compression. Gradient Quantization methods is also influential in gradient compression. But the paper does not have any comparative experiment with them.  \n2. From my perspective of view, index error and fitting error may cause model divergence, especially used in Gradient Sparsification (which means gradient selected by algorithm tend to be important).\n3. In figure. 4, why  does the curve  of $DR_{BF-P2}^{\\empty}$ and $ DR_{BF-P1}^{\\empty}$ falls so much in 1000 - 2000 step?  Does it mean that BF compressor with great probability of loss information leading to model divergence.\n4. In my opinion, there should be some experiments of $DR_{BF}^{Fit}$.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "DeepReduce is a lossy gradient compression framework. Probabilistic and unpredictable errors is the biggest limitations. Compared with more stable compression algorithms, this framework does not show its superiority. ", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "8EhFGIxvNFw", "reviewer": "Reviewer_j5Bs", "summary": "This paper proposed a framework to compress sparse tensors in the context of federated learning, in order to further save the amount of transmitted data between the server and clients. The proposed method could be incorporated into the existing pipeline of distributed training with sparsification. The main idea is to compress/decompress the index and value separately with different compression methods. The paper comes up with two compression methods, i.e., Bloom-filter based index compressor and curve-fitting based value compressor. The paper shows some synthesized and realistic experiments to justify the proposed methods.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is targeting a meaningful problem, that is, minimizing the communication data amount in the distributed training, especially federated learning where the training devices (like mobile phones) are assumed to be massively distributed and could be charged by the data traffic. Also, the paper did a detailed analysis (in both theory and experiments) about compression methods of sparse tensors.  It is interesting to see the behavior of different combinations of compression methods on sparse tensors (Fig 4).\n\nHowever, I do have several concerns.\n1. As a FL algorithm, it is not clear that how exactly the training process works on server and client respectively. As we know, the distributed learning process can be very specific, e.g., what do you communicate, model or gradient? when do you communicate? how to update the model? and so on. If you are following the FedAvg stereotype where clients receive model parameters from the server and send gradients back to the server, then how do you apply your method on model parameters which are usually not sparse? If not, then you may have a different training process than FedAvg, which is not specified in the paper.\n\n2. As shown in Fig8, the SKcompression actually has lower data volume than the proposed method, but it takes more time for encoding. Therefore, we still don't know if the proposed method can be faster in the end-to-end comparison with SKcompression. I guess it depends on this is computation or communication that dominates the overall time. Maybe adding SKcompression result in Fig 7 can make it more clear.\n\n3. The experiment setting is a bit confusing for me. It seems you used 56 AWS instances in total, but in 6.2, the paper mentioned the dataset is partitioned among 342,477 clients, and the server randomly selects 56 clients to communicate. So I assume each instance has multiple clients? This part needs more descriptions.\n\n4. In Table 1, the optimizer column is a bit confusing. FedAvg is a distributed training algorithm, while SGD and Adam are optimization methods. I don't know how to compare these two concepts. \n\n5. The paper mentioned multiple times the \"easy-to-use API\" of the proposed framework, and has a section to describe the \"system architecture\". These may give the audience an expectation that this work is building up a system. But we didn't see the detailed information about the API and the system. Also, the limitation of the system is not discussed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussions about limitations are not enough. For example, the proposed framework is open to use different compressors and combinations for index and value. And we can see these combinations have very different behaviors. How to choose these combinations to get a good balance between accuracy and efficiency is not discussed.\n\nBesides, data privacy is one of the most important motivations of federated learning. However, the author didn't discuss the potential impact on data privacy. Since this is a framework specifically intended for FL, I think it's necessary to take data privacy into account.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "2tyMgIOeSc", "reviewer": "Reviewer_qVgi", "summary": "The work proposes a general framework for sparse gradient transfer in distributed deep learning, where the non-zero indices and values are considered and compressed separately. In addition, authors propose new mechanisms for both index and value compression, demonstrating their advantages both theoretically and empirically.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1) The work is well-written and easy to understand: specifically, the illustrations help the reader gain enough insight into the studied methods and their performance.\n2) Both proposed compression methods are simple to implement and have theoretical guarantees while exhibiting favorable performance when compared to the baselines.\n3) Authors provide a general framework for sparse data transfer, which might be used as a foundation for future methods.\n\nWeaknesses:\n1) The work cites recent works on gradient compression (for instance, via low-rank decomposition, such as PowerSGD), yet in the experiments, there are no comparisons with these methods — only the sparsity-based ones. To clarify the applicability and relative performance of DeepReduce, it might be useful to see a comparison with a broader range of communication-efficient distributed methods.\n2) Although Table 2 and Figure 7 provide time breakdowns for the methods, it might be useful to plot the convergence curves of Figure 6 with wall clock time on the X-axis. In addition, one important detail missing from the experimental setup is the distribution of client-server bandwidth, which can help the reader gain insight into the specifics of the studied setting.\n3) Despite the indication in the checklist, I could not find the error bars for the experiments. They would be especially helpful in Table 2, because decoding and communication times are quite similar for the compared versions of DeepReduce.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a compression algorithm to compress the tensor communicated in the FL application to reduce communication cost, with certain theoretical guarantee for the compression. Reviewers generally agree that there do exist novelty for this compression method.

All reviewers read the rebuttal. Reviewers (especially the ones with concerns) made serious 2nd or 3rd response to the rebuttal and participated the discussion seriously. Based on scores, this is really a borderline paper. We are trying to identify the real contribution of this paper to be 1) a new FL algorithm or 2) a new compression algorithm. This paper is somehow between 1) and 2). We suggest authors to revise this work to make one single point solid enough by appropriate experimental design, if this paper is accepted. 

If this paper is considered to sell a new communication efficient FL algorithm, the comparison to other recent FL algorithms should be comprehensively compared. For example, the tradeoff between computation and communication can be more clear; The memory issue (it requires a large memory to store historical models for communications efficient) needs to be treated and discussed seriously, as pointed out by a reviewer; How is the accuracy affected by the compression? 

The proposed key compression algorithm is quite general. It can be used to many different areas. FL is just one of them. If this paper's main contribution is considered to be a new compression algorithm, then the comparison to other compression algorithms need to be compared more carefully. The application to other fields need to be shown.
Decision: Accept (Poster)