Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The main contribution of the paper is a differential private mechanism for federated learning. Further, they provide experimental evaluation of the same using MNIST and Fashion MNIST datasets.
main_review: Strengths of the paper: 

They study a problem that is of fundamental importance in privacy preserving machine learning. The use of Skellam distribution seems novel and interesting.

Weaknesses of the paper:

Firstly from a theoretical point of view, the contribution seems quite incremental. In the abstract the authors claim "highly non-trivial" analysis -- which is nothing more than elementary calculus and statistical analysis. The central theoretical contribution seems to be a differentially private multi-party protocol to compute sum of vectors. In a nutshell, the protocol is simply to add noise (based on "Skellam distribution") by each participant and adding them up in a distributed fashion. 

Secondly, I feel the experimental section is unsound and unconvincing. For example, getting an accuracy of ~80% on MNIST is unacceptable. To some perspective, the original paper on differentially private deep learning (by Abadi et al 2016) yields an accuracy of 95% on MNIST. Further, there is no "non-private" baseline provided.
summary_of_the_review: There are significant drawbacks both from a theoretical and empirical point of view. I am not sure how to strengthen the paper theoretically, but I think from an empirical point of view a more thorough comparison with various DP mechanism (Abadi et al. for instance) and including a baseline would strengthen the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies federated learning under the distributed DP framework [KLS 2021] and proposes the distributed Skellam mechanism (DSM). Compared to the existing approach [KLS 2021] that uses distributed discrete Gaussian (DDG) noise, DSM perturbs each local gradient with independent Skellam noise. This gives the advantage that the privacy guarantee is independent of the dimensionality of the gradients; further, DSM allows tight privacy accounting due to the nice composition and sub-sampling properties of the Skellam distribution and hence enjoys a better constant compared to the DG. Experimental results also imply that the DSM improves the previous DDG scheme (proposed in [KLS 2021]) when the communication is limited, say 12 bits per parameter.
main_review: Pros:

1. The privacy guarantee of DSM is non-trivial yet the analysis is clean. 


2. From Theorem 1, the variance of the DSM that preserves an $(\alpha, \tau)$-RDP is very close to the variance of the (centralized) Gaussian mechanism. This thus results in a small utility loss compared to the centralized model.


3. The experimental results also support that DSM outperforms the existing DDG scheme in some parameter regimes, such as when the communication budget is limited.


Cons:

1. Theorem 1 only holds when $ 1 < \alpha < \frac{2n\lambda}{\Delta_\infty}+1$. Is this the particularly interesting parameter regime in practice? Since the proposed algorithm does not perform random rotation on $x$ in the pre-processing steps, in the worst-case scenario, $\Delta_\infty$ can be as large as $\Delta_2$. I guess it should be fine if $n\lambda$ is large enough, but it would be great if the authors can briefly comment on whether $ 1 < \alpha < \frac{2n\lambda}{\Delta_\infty}+1$ is a reasonable regime or not.


2. In Algorithm 1 and 2, it seems that the summation is over $\mathbb{Z}$ instead of over $\mathbb{Z}_m$. In other words, there should be a modular clipping step before the aggregation (because SecAgg only works on a finite group). Moreover, similar as in [KLS 2021], when aggregating with a coordinate-wise modular sum, there should be a random rotation step that spreads the mass of $x_i \in \mathbb{R}^d$ evenly to each coordinate. I believe all these issues can be fixed by simply pre-processing $x_i$ with a random rotation and replacing the summation with modular sum though.


3. Following the previous point, since the aggregation should be carried out under modular arithmetic, Corollary 1 may not hold since the error due to modular clipping should also be incorporated. 


4. In the experiments, DSM is compared with DDG and cpSGD. It would be good if the authors can also include the accuracy of the (centralized) Gaussian mechanism as a baseline, which would let us know how close the DSM is to the centralized error.
summary_of_the_review: Overall, the paper is well-written and the proofs are easy to follow. The contribution is solid since the result directly improves the previous DDG scheme. However, there are some minor issues that the authors should clarify or address.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents a mechanism based on Skellam distribution (called Distributed Skellam Mechanism (DSM)) to prevent privacy leakage for federated learning. It provides analysis of privacy guarantee in the decentralized setting. Specifically, DSM is shown to be both RDP and (\epsilon, \delta)-DP. Also, DSM is applied to differentially private federated learning with distributed SGD and quantized gradients.
main_review: Strengths:
1. The paper is clearly structured and the theoretical proof is very logical.
2. Some nice properties of Skellam mechanism are considered, i.e., sum of Skellam random variables is Skellam distributed.


Weaknesses: 
1. Lack of novelty. Similar to this paper, the idea of applying the Skellam mechanism to federated learning has already been explored, and extended to high-dimensional settings in a recent paper. https://arxiv.org/abs/2110.04995
2. Doubt about the accuracy-privacy trade-offs. Due to composition theorems applicable in learning settings, the mechanism will be applied many times.
summary_of_the_review: Compared to other approaches to address privacy issues in joint learning, the Skellam mechanism is very compatible with MPC. However, a similar work has already been done.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: ### update after the discussions

I am satisfied with the responses from the authors' and the updated paper. I therefore recommend accepting the paper.

---

The paper considers the problem of distributed differentially private (DP) learning using black-box secure multi-party computation (MPC) for aggregating gradients for learning the model.

In principle, using e.g. secure aggregation allows each party to add a small amount of noise scaled so that the noise level after aggregation matches what one needs with a trusted central party. However, since the existing tools (mainly Gaussian mechanism) typically assume continuous space, while MPC works with discrete values, this does not work in practice: the main problem is that the discretised noise is not infinitely divisible so the sum is not guaranteed to follow the same distribution as the individual contributions.

To remedy the problem, the authors propose the distributed Skellam mechanism, which is both dicrete and infinitely divisible. The authors show that the Skellam mechanism privacy cost can be calculated using Rényi DP (RDP), and continue to show that it performs significantly better than the existing methods based on binomial noise and discrete Gaussian noise using MNIST and Fashion MNIST data for testing.
main_review: Strong points:
* The proposed method addresses some main weaknesses in the existing methods (mainly: avoid bad scaling with dimensionality that cripples the discrete Gaussian mechanism, allow for RDP-based privacy accounting)
* The results seem to work clearly better than existing methods

Weak points:
* There is no discussion on how tight the resulting privacy bounds are, i.e., how much do you lose when using the inequalities in Section 3.2
* I am not totally sure if the comparison against existing work is done entirely properly (see questions for authors below for details)

Questions and comments for the authors:
1) Can you quantify how tight or loose the RDP bound in Thm1 actually is?

2) On p. 2 you state that "existing theoretical tools for analyzing binomial noise aggregation leads to rather loose bounds". I get the impression that you mean RDP bounds. Still, there are other accounting methods like the Fourier accountant that operates directly in with (epsilon,delta)-DP, and Gaussian DP (GDP) based accounting. For example, looking at [1], there does seem to be calculations for some tighter bounds for the binomial mechanism. Is there some reason not to consider this in the comparisons?

3) Very minor comment: there seem to be lot of small typos, please fix.

References:
[1] Koskela et al. 2021: Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT.
summary_of_the_review: Overall I think this is a nice paper. However, I would like to hear the author response (questions 1 and 2) before recommending acceptance.
review_title: null

Meta-review: This paper proposes the distributed Skellam mechanism for differentially private federated learning that relies on secure aggregation. Since multi-party computation protocols rely on finite precision, the Skellam distribution meets the criteria of closure under addition and discreteness. During the discussion, the reviewers raised a concern that the proposed idea is highly similar to a recently published NeurIPS paper (https://arxiv.org/abs/2110.04995). However, since the timelines of the two papers are close, they can be considered concurrent work. Both results advance the study of private federated learning that leverages secure aggregation techniques. Through a more in-depth comparison, the current paper also provides sufficiently different proof techniques than the ones in the concurrent paper. The authors should provide an extensive comparison between their work and the NeurIPS paper in their next revision. 

While the paper provides new results, there are several concerns in the reviews. First, even though the proof techniques are different from concurrent work, the reviewers still think that the main technique of Skellam perturbation has limited novelty. Second, the presented experiments also appeared to be quite weak. For example, the accuracy on MNIST is much lower than simple baselines in earlier work. While the authors tried to justify this reduction of accuracy through their decentralized training setting, the argument is not fully convincing. In particular, even though the noise addition is done in a decentralized fashion, the proposed algorithm is still subject to the same (standard) differential privacy constraint (as opposed to local differential privacy). The authors could consider improving the experiments or providing a more principled justification for the reduction of accuracy in their algorithm. Due to these issues, the paper does not clear the bar for acceptance at ICLR.
Decision: Reject