Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 

This paper proposes to use a discrete gaussian distribution the generate noise for differential privacy.
While it is claimed that the discrete Gaussian distribution is better than the binomial distribution, no in-depth comparison is made.  The discrete Gaussian distribution, a discretized version of the Gaussian distribution, works as expected, and provides all properties the Gaussian distribution provides (if the discretization is sufficiently fine-grained).
An advantage is that the communication cost can be reduced by stochastic quantization of the values to be transmitted.  It is unclear whether the same stochastic quantization technique can be used for the classic Gaussian distribution.
The ideas of discretizing, of stochastic quantization to reduce communication cost, and the use of discrete distributions for differential privacy are all already known, the (limited) novelty is in the proper combination of these ideas.
The text is understandable for readers who know already the meaning of all symbols and names used, but a broader audience could be reached by properly introducing all concepts and notations in an understandable, coherent and self-contained way.  This would be valuable, even if it would mean that some more technical elements would need to be moved to an appendix.


In conclusion, while the idea is interesting, I have some concerns with the presentation and the insufficiently motivated novelty (and the related lack of more in-depth comparison with existing work).


* The paper points to a few shortcomings in the literature, but exaggerates their importance.  E.g., when the text says "However, cpSGD faces several limitations when applied to real-world applications. Firstly, with Binomial noise, the output of a learning algorithm would have different supports when any client participates or withdraws from learning", it may be true this is the case when literally considering the cpSGD paper, but such problem typically can be overcome easily.  When the text concludes "can only guarantee approximate DP where the participation of the client can be completely exposed with nonzero probability." I guess "approximate DP" means (epsilon,delta)-differential privacy where delta is strictly larger than zero (which is usually anyway already the case for Gaussian and binomial mechanisms).

* Definition 3: I wonder why the numerator and denominator of the exponent in the probability e^{-\pi x^2/(2\pi\sigma^2)} both contain \pi and this fraction isn't simplified.
* Definition 3: please clarify what kind of "discrete additive subgroup" you have in mind: is it a finite group (where addition is possibly modulo the group order) or is it a multiple of the set of integers \mathbb{Z} ? (much later in the paper, it becomes increasingly clear that the latter option is the correct one)
* Section 5.1: please explain the meaning of all used variables at their first use. E.g., the k in an expression log(k) isn't explained, until Section 6.1 cites another work for the meaning of k-level quantization (without even explaining the gist of quantization idea briefly).






review_title: An interesting idea, but it could be presented more clearly and more convincingly.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposed a privacy-preserving federated learning algorithm with efficient communication. To save communication costs, they integrate stochastic quantization and random rotation. Moreover, they apply the discrete Gaussian mechanism with Renyi DP analysis for privacy guarantee.


Novelty & Significance
-----------------------------

Solving federated learning with a privacy guarantee is of increasing practical importance, and certainly trying to do so with efficient communication efficiency is more important.
 
The RDP analysis for discrete Gaussian mechanism is nice, which allows a tighter composition with analytical moments accountants.


Technical concern:
-----------------------------

 I have concerns regarding the claim ''D2P-FED is more communication efficient compared to cpSGD'' due to a $log(1/\delta)$ factor in big O. Note that constant matters in differential privacy. Without knowing other constants hidden in big O, I feel hard to follow the conclusion there.


Experimental Evaluation:
----------------------------

My major concern is that empirical evaluation is limited.
(1) In Figure 1, three methods use different quantization. There lacks clarification on the choice of bytes.  Moreover, it would be much better to add a non-private baseline without quantization.
(2) Noting the privacy budget greater than 10 is no longer meaningful; it may be better to focus on the practical privacy regimes in Figure 1 (a).
(3) In Figure 1 (b), is the privacy budget aligned? If not, how to set the noise scale for cpSGD and D2P-FED?  Is it possible to align both the privacy budget and communication cost? For example, the per-round communication is the same for both algorithms with the same bytes. Set the x-axis to be the communication cost, the privacy cost is fixed for all points, and the y-axis reports the model accuracy.
(4) INFIMNIST and CIFAR10 are still two toy datasets. Perhaps authors can add more experiments with real-world datasets in the next version.  




review_title: This paper proposed a privacy-preserving federated learning algorithm with efficient communication.

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################

Summary:

 
The paper proposes the discrete Gaussian based differentially private federated learning algorithm to achieve both differential privacy and communication efficiency in federated learning. In particular, it adds discrete Gaussian noise into client updates and uses secure aggregation to prevent the server from observing the individual updates. The algorithm satisfies RDP and has lower communication cost compared to the previous method cpSGD.

##########################################################################

Reasons for score: 
 
 I like this work. 1. The problem is critical in federated learning. The D2P-Fed algorithm has nice performance on the trade-off among privacy, utility, and communication cost. 2. It has several algorithmic novelties. To employ secure aggregate, it's natural to use a mechanism with discrete support (or discretize that). The discrete Gaussian mechanism is indeed a better candidate than the binomial mechanism. But there is much more beyond a simple combination of the discrete Gaussian mechanism and secure aggregation. They use several other techniques, such as stochastic quantization and random rotation. The mapping to a cyclic additive group is novel. 3. They provide strong theoretical guarantees and empirical validation.

##########################################################################
Minor comments:

1. In Section 3 under FL Overview, I don't think $k$ is clearly defined. I guess $k=\gamma n$. It is also confusing in Algorithm 1. It should be clearly defined. The same for $d$ in Algorithm 1. 

2. The probability $g[j]-b[r]/b[r+1]-b[r]$ doesn't seem make sense. Like if $g[j]=b[r+1]$, it will be set to $b[r]$ with probability 1. Should it be $1-(g[j]-b[r]/b[r+1]-b[r])$?

3. In Figure 1(b), the x-axis should be communication cost for CIFAR10.

 
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose D2P-FED to achieve differential privacy and communication efficiency in FL tasks. The framework is interesting and the problem studied is important. However, this paper suffers from some major deficiencies. 

Major comments:

1) It is claimed that the privacy guarantee for D2P-FED is better than that of cpSGD. However, this is not substantiated after the privacy results of Theorem 5. Furthermore, the bound here depends on D, the clipping threshold on the l_2 norm of g, which clearly affects the privacy guarantee per Theorem 5. 

2) The algorithm here depends on the lattice being defined as 2g^{max}/(k-1) Z. It is not clear how one can set the g^{max} in practice. The differences of the parameters w_t are generated on the fly for each client. Thus, this algorithm has limited applicability in practice. 

3) Similarly to point 1), it is not clear in what way the communication cost is better than that of cpSGD. From the convergence result in Theorem 7, it seems like there is no improvement. Further, g^{max} needs to be set in a very specific way that is dependent on D and d, which is again not known in practice. So whether we can attain the convergence rate is unclear. 

4) The authors acknowledge in their experiments that the results are sensitive to the scale of the discrete Gaussian noise. Hence, the privacy-communication cost-convergence rate tradeoff is not clearly delineated. 

Minor comments:

1) The writing is not sufficiently precise and clear. For example, before the statement of Thm 1, it is mentioend that the proof is delayed to Appendix A. However, the proof of Thm 1 is not provided therein. Rather the proof of Thm 3 is in that appendix. The proof of Thm 4 in Appendix B is not sufficiently precise. It is not clear what the authors mean by "expand the space a little bit". How much is "a little bit"? Since this is a "theorem", the proof should be watertight. 
review_title: Some deficiencies 

Meta-review: The paper considers differentially private federated learning --- a well-motivated problem. The proposed algorithm is a simple modification to existing methods, e.g., DP-FedAvg, but uses a different DP mechanism for noise-adding.  The reviewers liked the motivation but criticized the work for its incremental nature and for somewhat overselling the contributions.

Pros:

- The paper used advanced Renyi DP accounting to get a stronger privacy-utility tradeoff.

- The experimental results improve over cp-sgd that uses Binomial mechanisms

Cons: 

- It is a bit incremental in its contribution.  The main contribution is to applying "discrete Gaussian mechanism" to the federated learning problem for the interest of reducing the communication cost.   Discrete Gaussian mechanism and its RDP analysis are both from existing work.

- The improvement in privacy-utility tradeoff over cp-sgd seems to be due to that the discrete Gaussian mechanism has an RDP bound, which plugs right into the subsampling bound and moments accountant.    It is unclear whether the improvement is coming from the different noise or a stronger privacy accounting.  Notice that the privacy accounting of Binomial mechanism in the initial cp-sgd paper was rather crude, thus a fair comparison would be to also conduct an RDP analysis for the Binomial mechanism.  

Overall, there weren't sufficient support among the reviewers and the experimental results alone are not so groundbreakingly strong to carry the paper single-handedly.

Decision: Reject