Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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).

However, I do have several concerns.
1. 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.

2. 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.

3. 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.

4. 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. 

5. 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.
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.

Besides, 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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths:
1) 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.
2) Both proposed compression methods are simple to implement and have theoretical guarantees while exhibiting favorable performance when compared to the baselines.
3) Authors provide a general framework for sparse data transfer, which might be used as a foundation for future methods.

Weaknesses:
1) 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.
2) 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.
3) 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

Firstly,  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. 
main_review: **Originality**: 

This paper can be considered as a good combination of existing techniques.  

**Quality**: 

1. 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. 
2. 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.
3. The trade-off between communication and precision is not well-explained. 
4. 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).   

**Clarity**:

This 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. 

**Significance**:

The experimental evaluation is not sufficient.  The experiments in this paper did not show the advantages of its framework.

1. 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.  
2. 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).
3. 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.
4. In my opinion, there should be some experiments of $DR_{BF}^{Fit}$.


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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Problem: Communication overheads in the current FL setup, especially while transferring deep model gradients from clients to server and vice-versa. 
Solution: 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.
Results: A significant reduction in the transfer of data over the existing techniques.

main_review: Distinction from state-of-the-art:
Well 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.

Pros:
The paper is well written, easy to understand and digest the concepts.

The proposed method is solid with theoretical proofs and upper bounds on the errors for various parts such as curve fitting, etc.

The 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.

Cons:

This 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.

The 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?


The number of references are too many for a conference paper.

limitations_and_societal_impact: The authors have to describe the limitations in detail.

However, 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_title: null

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)