Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a new to DP noise addition mechanism, based on the Skellem distribution.  The benefits of the Skellem distribution include closure under addition, a property lost on discrete Gaussians, and its discrete nature which makes it able to be exactly sampled from with finite machines, unlike continuous Gaussian noise.  Furthermore, this work bounds the increase in the scale of the noise compared with Gaussian noise for the same level of privacy.  Lastly, they provide experimental results of their approach.

main_review: I like how this paper makes a strong argument for using the Skellem Mechanism rather than the discrete Gaussian distribution.  The federated learning setting seems especially problematic for the discrete Gaussian, as one would like to analyze the utility of several terms added, which is no longer discrete Gaussian.  

However, the Skellem Mechanism is not new, as the paper points out in citing [36], but only for the scalar case. Section 3.2 goes into detail for how this paper’s analysis is tighter.  

My main criticism of this work also extends to the work on the discrete Gaussian.  The paper from Ilya Mironov gives the typical sampling routine of the Laplace distribution and shows how it can have catastrophic privacy loss, much more than intended.  This work and the work on the discrete Gaussian do not show such an attack on continuous Gaussian noise.  These papers would be much stronger if they showed a particular sampling routine had similar catastrophic privacy loss as the Laplace sampling routine.  Hence, I wish there would be more motivation in this paper for why continuous Gaussian noise should not be used rather than assuming some future attack.  

Minor Comments: 
- I believe the analysis for the PLD composition requires that the mechanisms are not chosen adaptively.  This applies for the settings you consider, since each coordinate has independent noise, but this limitation should still be explicitly stated.
- “regarding regarding” in line 178.


########### 
Update: I have read the author responses and the other reviewers comments.  The application of discrete noise to FL makes sense as it reduces communication cost, so the use case is crucial to demonstrate the need for such types of mechanism like Discrete Gaussian and Skellam.  Thanks for making this clearer, so I will increase my score.  However, there are still issues with presentation, like making it clear the improvement over the existing privacy guarantee for the d = 1 case as was stated in the response to reviewer WiXo.  However, I still do not see the real need for Skellam over Discrete Gaussian.  The 2 stated reasons are that Skellam is closed under addition and there are existing packages for Skellam.  The response to reviewer p2AR states that discrete Gaussian "is still not widely available in numerical analysis packages such as NumPy, TensorFlow, SciPy that ML / DP practitioners would use for development" which is a pretty simple fix.  
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduced and analyzed the multi-dimensional Skellam mechanism which is a discrete differential privacy mechanism based on the difference of two independent Poisson random variables to the federated learning setting. This paper also studies the experiment performance of such mechanism compared with existing continuous gaussian mechanism.

Contributions are, 1) analyzed the mechanism differentially private behavior in multi-dimensional federated learning setting. 2) experimented its performance and analyzed why this mechanism is suitable for real federated learning practice.

main_review: The skellam mechanism is not new, the mechanism exists previously. Considering that implementing DP in real life setting in federated learning requires significantly addressing the communication efficiency, sampling implementation and DP implementation in finite computer, this paper gives a good example.

Quality:
Proving the DP behavior of such mechanism does not contribute much theoretically. However, the experiment is comprehensive and the results are meaningful, the mechanism also bypasses the sampling difficulties of previous mechanisms. The implementation code or the engineering work is solid.

Clarity:
The content arrangement is clear and well organized.

Significance:
The mechanism proposed by this paper bypass the sampling difficulty in previous mechanisms in real-life setting thus making it practically valuable. Experiment result is meaningful, the mechanism shows comparable performance in real federated learning tasks with continuous gaussian mechanism.
-----------------------------------

After reading the authors rebuttal I raise my score. I think the authors provide a good feedback to solve my concerns. 
limitations_and_societal_impact: For the potential improvement, In the situation where n and d is large, seems like more bit width is required for the mechanism to reach comparable result with respect to continuous gaussian mechanism. More bit width means heavier communication overheads, so, from the perspective of experimenting, more elaborated discussion about this kind of trade-off is better to be given.

Moreover, the main concern is as the author mentioned, the Skellam mechanism has been studied previously and the main contribution of this paper is providing a tighter analysis based on the Renyi divergence. This is the main reason why I tend to reject the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed a new discrete differential privacy mechanism based on the difference between two independent poisson random variables, which may be a new attractive alternative of discrete Gaussian mechanism. The authors also carefully proves a sharp privacy guarantee via privacy loss distribution, and renyi divergences. Extensive experiments results on centralized, federated learning, demonstrate that the effectiveness of proposed methods. 
main_review: The task of achieving differential privacy on finite machines is important, since continuous mechanism of differential privacy may lead to privacy errors when implemented in floating point. 


Strengths: 
The paper is highly technical and in particular the properties are rather challenging to prove. All the technical parts seem solid, though I have not fully checked the appendices.

The paper is quite well-written, and I can follow it easily.  I also like that it presents a number of comparisons for the application of their proposed mechanism, including centralized and distributed privacy applications. 

Weakness: 
It’s better to have a comparison of noise sampling time with discrete Gaussian mechanism to further show the advantages
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces the multi-dimensional Skellam (difference of two Poisson random variables) mechanism for differential privacy. They show that the Skellam Mechanism is Renyi DP (RDP) with slightly worse guarantee than than Gaussian Mechanism. They also compare the privacy loss over several rounds against Gaussian and Discrete Gaussian using Renyi DP, Advanced Composition and the Privacy Loss Distribution. Results show that Skellam performs similarly to Discrete Gaussian and Gaussian when using RDP and PLD bounds.
As an application they consider using the Skellam Mechanism for distributed mean estimation and two Federated learning tasks (EMNIST and SO-NWP). Experiments show that they can match the performance of continuous Gaussian.

***
After rebuttal. I've read all the reviews and replies. Raising my score appropriately.
main_review: The paper is relatively easy to read. The technical claims seem to be correct and is novel in the sense that it introduces a mechanism that did not exist before. Unfortunately, I am not convinced this paper will really be impactful. One of the motivations for this work is that Discrete Gaussian is not part of Tensorflow, I’m almost certain this is just a matter of time. The main strength of this mechanism is that Skellam is closed under summation but DGaussian is not. It is unclear to me that this advantage is enough for publication of this paper. It is possible I missed something so please let me know if I did and I may revisit my score. 

Another question, why does the PLD section exist if you have at your disposal Theorem 3.5? 

Minor:
Line 130: I think the definition of f(x) is wrong. It should be P(M(D) = x), instead of M(D)=x (same with D’), right?
Line 106, typo. Z should be X.

limitations_and_societal_impact: NA
review_title: null

Meta-review: The reviewers were convinced by the technical content of the paper, but were somewhat unconvinced of the value over the distributed discrete Gaussian. The main claimed advantages seemed to be that the primitives were readily available in more libraries (which reviewers did not think was a strong argument), and that the discrete Gaussian is not closed under summation. There is some discussion of this comparison at the end of Section 4. It is requested that the authors place this comparison front-and-center, and expand more upon the points, in order to make the comparison crystal clear. In particular, the authors must be more detailed with their critiques of the discrete Gaussian. What is stopping the discrete Gaussian from being implemented in libraries besides initiative from some interested researcher? In terms of how the discrete Gaussian does not compose: how do you square this with the following sentence from [19]? "The bound of the theorem is surprisingly strong; if σ^2 = τ^2 = 3, then the bound is ≤ 10^{-12}". The plots (Figure 2 and 3) seem to indicate larger differences than what I would have expected from this statement, even in the parameter regime corresponding to this statement. The authors must precisely, thoroughly, and honestly detail why this method is favorable to the discrete Gaussian in the final version. Despite some cynicism about the motivation, this paper had a very thorough analysis of a natural mechanism, and thus should be accepted.
Decision: Accept (Poster)