Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies differentially private algorithms in federated learning, and proposes to take advantage of the randomness in Relative Entropy Coding (REC) to achieve good privacy-utility trade offs while significantly saving the communication costs. On four benchmark datasets (MNIST, FEMNIST, Shakespeare, Stack Overflow linear regression), under same privacy epsilon, the proposed method can save communication for ~(4000, 20, 800, 100)  times with accuracy loss ~(15, 6, 10, 1) compared to DP-FedAvg. 




======= after rebuttal ============
I appreciate all the clarification and improvement on the draft. This paper is a borderline to me for the remaining concerns.

I want to be more specific here on "apples-to-apples" comparison. There are three things considered: differential privacy, communication and accuracy. It would be useful to show how this method can help achieve a reasonably good metric by tuning the other two metrics. Only working in the low accuracy regime sounds like a big limitation, and did not compare with other stronger compression method further weaken the claim (as also mentioned by other reviewers).

The authors mention secure aggregation in their rebuttal. IIUC, secure aggregation is future work in this draft. It is not very convincing.

That being said, The idea seems to be interesting, and I will raise the score from borderline reject to borderline accept.


main_review: I have a few questions that I hope the authors can help clarify. 
- How is sensitivity controlled? It seems not quite clear to me the sensitivity control over \phi_s can transfer to \Delta_k*.  
- It is a bit hard to interpret Table 1 and Figure 1 as both communication cost and accuracy are different. And it seems that aggressive compression will cause more accuracy drop. Since the communication-accuracy tradeoff of DP-REC can be tuned by K, or for different numbers of parameters/layers, can DP-REC match DP-FedAvg accuracy with less aggressive compression?
- Could the authors provide the clip norm and noise for both DP-FedAvg and DP-REC with some explanation? Appendix C.2 provides some, but I would appreciate an “apple-to-apple” comparison and some explanation on why from a first glance, the noise in DP-REC can be much smaller. 
- Is it possible to provide more baselines? For example, DP-FedAvg with compression?
- The two versions of EMNIST (3.4K vs 3.5K) may have different numbers of labels, probably want to double check that the comparison is correct for table 1. Or even better, try to reproduce DDG with the same setting. 

summary_of_the_review: It is a bit hard to justify the significance as it is not an apples to apples comparison as both communication and accuracy are different.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a compression and privatization technique to federated learning based on Relative Entropy Coding (REC). For each round, client $s$ aims to privatize its local model update $w_s$ by releasing $\Delta_s = w_s + N(0, \sigma I)$. However, instead of directly adding Gaussian noise, the client first picks $K$ random vectors from a prior distribution (which is independent of $w_s$) with shared randomness and then performs importance sampling according to the law of $w_s + N(0, \sigma I)$. It can be shown that as long as $K$ large enough (i.e., when $\log_2 K$ is much larger than the Renyi divergence of the prior and the target distributions), the sample obtained from importance sampling has a law close to the target distribution (i.e. the Gaussian perturbation) and thus can potentially preserve privacy. Moreover, the communication needed is $\log_2 K$ bits per round per client. By accounting the privacy loss over $T$ rounds, the authors characterize the overall privacy guarantees, which have a clean form and connect to the communication budgets nicely.
main_review: Pros:

The idea of applying REC to compress a (distributed) DP mechanism is novel and elegant, and the connection between the communication budges and the privacy guarantees are also interesting. The comparisons with previous works and the experiments, in my opinion, are adequate. I also appreciate the authors' discussions on whether DP-REC is compatible with other privacy amplification techniques.

Cons:


1. My major concern is the correctness of "per-parameter compression". All of the theorems, including the privacy guarantee and the communication bound, are derived for the network-wise compression, and the authors claim that one can directly apply these results to parameter-wise compression since both the prior distribution $p_\theta$ and the target distribution $q_\phi$ are product measures. However, I am not very sure about this statement. Though the target distribution $q_\phi$ is a product measure, the law of the outcome of DP-REC (Algorithm 3) $q_{\tilde{\pi}}$ may not be of a product form. Similarly, I don't see how $\pi_k$ in Algorithm 3 can be decomposed into a product form.  Therefore, in general, I am not so sure about whether equation (4) will still hold if we decompose it coordinate-wisely. 

Since the main theorem is based on equation (4) and all experiments are carried out with per-tensor compression, I think it is important to give a formal statement and proof to show that the results also hold for per-parameter compression.


2. It would be good if the authors can provide a detailed end-to-end algorithm for the overall FL framework, including how to pick parameters such as $b$ and $\sigma$.


3. When comparing with DDG on the FMNIST dataset, it seems that the accuracy of DP_REC is still significantly lower than the accuracy of DDG. Is it possible to increase the communication budgets and reduce the gap?
summary_of_the_review: The paper is well-written and the proposed idea is novel. Discussion and comparison with related works are adequate. However, my major concern is the correctness of the per-parameter compression. If the authors can clarify this point, I am happy to further increase my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a differentially private and communication-efficient method to aggregate the client updates in federated learning. The method is based on a recently proposed compression technique relative entropy coding. The authors further modify this technique to satisfy differential privacy guarantees and perform various experiments to back their claims.
main_review: **Strengths**
1) The Bayesian approach taken by this paper is different from the worst-case guarantees provided in many papers studying a similar problem (Agarwal 18, Chen 20, Girgis 20). The promising results in this paper could therefore a inspire a new line of research in this area.
2) The paper introduces plenty of new ideas to the federated learning community, both in the main algorithm and its analysis.
3) Experiments validate that the proposed algorithm provides very high compression in the high privacy regime ($\varepsilon < 1$).

**Weaknesses**
1) Computational complexity: The algorithm in its general form requires $b$ samples to be drawn from a high-dimensional distribution. This is computationally costlier than many other known methods.

2) Given that Chen 2020 is known to be optimal under joint privacy and communication constraints, a *theoretical* comparison with results in Chen would have to theory of this paper. This could have been done for both *good* and *bad* prior. 
summary_of_the_review: Overall, I like this paper and recommend it be accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a compression scheme for federated learning built upon previous relative entropy encoding works. It then proves that with some small modification (clipping the model updates), the algorithm is inherently differentially private. Empirical evaluation shows that the proposed method can achieve much more communication reduction at the cost of accuracy degradation.
main_review: I think the most interesting part of this paper is that it leverages the randomness in the sampling process to achieve differential privacy, and gives privacy bounds. I didn't check the proof in the appendix in detail, but the analysis makes sense to me at the high level.

This work also considers local privacy in addition to client-level privacy. It describes the relations with previous works and the experimental setups reasonably well.

My major concerns are that (1) the recovered model updates at the server side (even without clipping for privacy) are biased wrt the true model updates; (2) the algorithm doesn't support selecting multiple clients at each round, and (3) experiments can be improved.

Regarding (1), I think it is probably fine (and not difficult) to give a convergence bound with a small error term. Regarding (2), if there are many clients in the entire network, picking only one of them at each communication round can make the convergence unstable, or reach a lower accuracy. I am wondering if it is possible to extend the current algorithm by selecting a subset of clients, allowing each of them to run Alg 3 independently (with their own random seeds), and aggregating these model updates at the server (after the server recovers each update with the corresponding random seed)? This will affect both privacy and convergence.

Accuracy drops significantly under the same privacy budget in the experiments (e.g., on the simple MNIST dataset, the accuracy is 10% lower than DP-FedAvg for a large epsilon value), but the compression ratio is very high. DP-REC allows for different compression granularities such as per-parameter clipping. Is it possible that such kind of more fined-grained compression can increase the final accuracy, although transmitting more bits each round?

I think there are multiple potential baselines on compression + DP. E.g., apply DP on top of any gradient compression method. These should be considered or at least discussed in the experiments. The goal of DDGauss is not compression (though it results in quantized model updates). Therefore it may not be a strong compression baseline.
cpSGD, ATOMO (https://arxiv.org/abs/1806.04090) + DP, selecting top-k coordinates (measured by magnitudes)+DP are all reasonable baselines.


Minor:

* I think some notations might be a bit confusing, e.g., w \sim q_{\phi}(w) (the third line in Sec 2.1). It would be more clear to use different notations for random variables and samples. In algorithm 3, can note k \in {1, ..., K}.

* Moving the discussions on the choice of sigma values to the main text could be better.

* Experiments: It would be helpful for readers to further understand the behavior of the proposed method if it also includes results on applying compression alone with a good \sigma without clipping (i.e., not considering privacy budgets). That will demonstrate how good the (biased) compression itself can be.

* What does 'tensor'(generally understood as multi-dimensional arrays) mean in the context of this work? Does it refer to different sets of named parameters in the model? 
summary_of_the_review: I think the most interesting part of this paper is that it leverages the randomness in the sampling process to achieve differential privacy. My major concerns are that (1) the recovered model updates at the server side (even without clipping for privacy) are biased wrt the true model updates; (2) the algorithm doesn't support selecting multiple clients at each round, and (3) experiments can be improved.


=== update ===

After reading the authors' responses, some of my concerns have been addressed. Therefore, I increase my score to 6.
review_title: null

Meta-review: This submission describes an approach to compressing the communication in federated learning. The key idea is using a set of random samples from a prior distribution and then performing importance weighed sampling. The work performs an analysis of the privacy guarantees of this process and experimental evaluation.
The main issue with this work is the authors appear to be unaware that the basic problem they pose is solved in a more comprehensive and lossless way in a recent work https://arxiv.org/abs/2102.12099 (Feldman and Talwar, ICML 2021). That work shows that any differentially private randomizer can be compressed via a simpler algorithm that performs rejection sampling using a PRG. The algorithm does not loose privacy or utility (under standard cryptographic assumptions) while guaranteeing low communication. In contrast this work loses significantly in utility and provides opaque privacy guarantees.
This submission analyzes  a randomized that adds Gaussian distribution and, in particular, the compression technique in (Feldman and Talwar) applies to it. The technique proposed in this work is very similar in spirit (with prior distribution corresponding to reference distribution in the earlier work.
In light of the earlier work I do not think the contributions in this submission are sufficient for publication.
Decision: Reject