Distributed Skellam Mechanism: a Novel Approach to Federated Learning with Differential Privacy
Authors: Ergute Bao
Yizheng Zhu
Xiaokui Xiao
Yin Yang
Beng Chin Ooi
Benjamin Hong Meng Tan
Khin Mi Mi Aung
Venue: ICLR 2022 Submitted (2022)
Keywords: Differential Privacy
Federated Learning
Skellam Distribution
Renyi Divergence

Abstract: Deep neural networks have strong capabilities of memorizing the underlying training data; on the flip side, unintended data memorization can be a serious privacy concern. An effective and rigorous approach to addressing this problem is to train models with \textit{differential privacy} (\textit{DP}), which provides information-theoretic privacy guarantees by injecting random noise to the gradients. This paper focuses on the scenario where sensitive data are distributed among individual participants, who jointly train a model through \textit{federated learning}, using both \textit{secure multiparty computation} (\textit{MPC}) to ensure the confidentiality of individual gradient updates, and differential privacy to avoid data leakage in the resulting model. We point out a major challenge in this problem setting: that common mechanisms for enforcing DP in deep learning, which require injecting \textit{real-valued noise}, are fundamentally incompatible with MPC, which exchanges \textit{finite-field integers} among the participants. Consequently, existing DP mechanisms require rather high noise levels, leading to poor model utility.

Motivated by this, we design and develop \textit{distributed Skellam mechanism} ({\sf DSM}), a novel solution for enforcing differential privacy on models built through an MPC-based federated learning process. Compared to existing approaches, {\sf DSM} has the advantage that its privacy guarantee is independent of the dimensionality of the gradients; further, {\sf DSM} allows tight privacy accounting due to the nice composition and sub-sampling properties of the Skellam distribution, which are key to accurate deep learning with DP. The theoretical analysis of {\sf DSM} is highly non-trivial, especially considering (i) the complicated math of differentially private deep learning in general and (ii) the fact that the Skellam distribution is rather complex, and to our knowledge, has not been applied to an iterative and sampling-based process, i.e., stochastic gradient descent. Meanwhile, through extensive experiments on various practical settings, we demonstrate that {\sf DSM} consistently outperforms existing solutions in terms of model utility by a large margin.

Under review as a conference paper at ICLR 2022
DISTRIBUTED SKELLAM MECHANISM: A NOVEL APPROACH TO FEDERATED LEARNING WITH DIFFERENTIAL PRIVACY
Anonymous authors Paper under double-bling blind review
ABSTRACT
Deep neural networks have strong capabilities of memorizing the underlying train- ing data; on the flip side, unintended data memorization can be serious privacy concern. An effective and rigorous approach to addressing this problem is to train models with differential privacy (DP), which provides information theoretic vacy guarantees by injecting random noise to the gradients. This paper focuses on the scenario where sensitive data are distributed among individual participants, who jointly train model through federated learning, using both secure multiparty computation (MPC) to ensure the confidentiality of individual gradients, and dif- ferential privacy to avoid data leakage in the resulting model. A major challenge in this setting is that common mechanisms for enforcing DP in deep learning, which inject real-valued noise, are fundamentally incompatible with MPC, which ex- changes finite-field integers among the participants. Consequently, most existing DP mechanisms require rather high noise levels, leading poor model utility.
information-theoreiic pri-
Motivated by this, we design and develop distributed Skellam mechanism (DSM), a novel solution for enforcing differential privacy models built through an MPC-based federated learning process. Compared to existing approaches, DSM has the advantage that its privacy guarantee is independent of the dimensionality the gradients; further, DSM allows tight privacy accounting due to the nice composition and sub-sampling properties of the Skellam distribution, which are key to accurate deep learning with DP. The theoretical analysis DSM is highly non-trivial, especially considering (i) the complicated math of differentially pri- vate deep learning in general and (ii) the fact that the Skellam distribution rather complex, and to knowledge, has not been applied to iterative and sampling- based process, i.e., stochastic gradient descent. Meanwhile, through extensive experiments on various practical settings, we demonstrate that DSM consistently outperforms existing solutions in terms of model utility by a large margin.
INTRODUCTION
Deep neural networks, especially large-scale ones such as GPT-3 (Bronn et al. 2020), are known for their excellent memorization capabilities (Song al. 2017 Feldman 2020 Zhang al. 2021). However, it is rather difficult to control what exactly the neural net memorizes, and unintended data memorization can be serious concern when the underlying training data contains sensitive infor- mation (Carlini et al., 2019). For instance, consider bank that trains a GPT-like language model on call center transcripts. Due to data memorization, is possible to extract sensitive information by letting the model auto-complete a prefix, e.g., "my account number is: ". Clearly, if such model (or API) is ever exposed to the adversary, becomes a ligation machine as attackers can attempt with various prefixes to extract sensitive data, and subsequently sue the bank for privacy violations. Shokri et al. (2017) report that simple and intuitive measures often fail to provide sufficient protec- tion, and the only way found to completely address the issue is to train the model with the rigorous guarantees of differential privacy (DP) (Dwork et al., 2006).
This paper focuses the scenario that multiple individual participants jointly train machine learn ing model using federated learning (FL) (McMahan et al. 2017) through distributed stochastic gra- dient descent (SGD) (McDonald al. 2010 Dean et al. 2012 Coates al. 2013 Abadi et al.)

---

Under review as a conference paper at ICLR 2022
2016a).
Specifically, in every iteration, each individual computes the gradients with respect to the current model weights based on her own data; then, gradients from all participants are aggregated to update the model. Note that the gradients from each individual may reveal sensitive information
about her private dataset (Shokri et a 2017: Pyrgelis et al. 2018 Yeom et al., 2018: Nasr et al.) [209 Melis et al. 2019). A common approach to addressing this problem by employing secure multiparty computation (MPC) protocol (Yao 1986 Chaum et al. 1987 Gennaro et al. [200 Ishai ct al., 2010; Beimel et al. 2014 Cramer et al.) 2015 Ananth et al., 2018). which computes the aggregate gradients while preserving the confidentiality of the gradients from each individual par- ticipant. One advantage of MPC is that is a decentralized approach that does not require a trusted third party, which can be difficult to establish in some applications, e.g., in finance and healthcare.
Note that although MPC protects individuals' privacy in the gradient update process by concealing the gradient values of each participant, it does not provide any protection against data extraction attacks caused by unintended data memorization (Dwork et al.) 2015] [Song& & Shmatikov, 2019 Melis et al. 2019; Song & Shmatikov) 2020). As mentioned earlier, an effective methodology to defend against such attacks is to perturb the gradients to satisfy differential privacy (Shokri et a 2017). Since there is no trusted third-party in our setting, such gradient perturbations need to done in a decentralized fashion, i.e., each FL participant adds noise to her own gradients, such that the aggregated gradients over all participants satisfies DP, which is referred to distributed differential privacy (Goryczka et al. 2013 Kairouz et al.] 2021).
Although gradient perturbation under DP has been studied in previous work (notably, DPSGD (Abadi et al. (2016b)), it is far from trivial to adapt centralized DP solutions to our setting, due to a fundamental problem: that the MPC protocol requires gradients to be represented as inte- gers (more precisely, finite field elements (Paillier 1999. Bonawitz et al. 2017 [ell et al., (0200). DPSGD, on the other hand, injects real-valued Gaussian noise to the gradients. Although real num- bers can be quantized and (approximately) represented using large integers, the quantized random noise have rather different mathematical properties, which render a tight privacy cost analysis much more difficult, especially under the decentralized setting of FI.. For instance, a nice property of the continuous Gaussian distribution is that summing up n continuous noise values following i.i.d. unit- Gaussian distribution results in an amplified continuous Gaussian noise of variance n. This property does not hold, however, if the Gaussian noise values are first quantized before aggre- gated. Further, the privacy analysis (specifically, the moment accountant analysis technique) of the DPSGD algorithm also replies on other important properties of the continuous Gaussian distribu- tion, which do not hold when the noise is quantized. Hence, DPSGD does not directly apply to our setting. This issue has been neglected by many existing distributed DP solutions, e.g., (Goryczkal
al. 2013 Valovich & Alda 2017
Truex al. 2019).
Existing Solutions. Agarwal et al. 2018 propose cpSGD, which injects binomial noise (i.e., the sum of multiple binary values drawn from independent Bernoulli trials) to the discretized gradients at each participant of FL., to satisfy DP. Similar to Gaussian noise in the continuous domain, bino- mial noise can also be aggregated, i.e., the sum of multiple i.i.d. binomial noise values also follows a binomial distribution. However, compared to the continuous Gaussian distribution, existing the- oretical tools for analyzing binomial noise aggregation leads to rather loose bounds; further, the bionomial distribution is incompatible with the moment accountant analysis technique in DPSGD Kairouz et al. 2021). Consequently, cpSGD leads to poor utility, as demonstrated in Section 4
Recently, the distributed discrete Gaussian mechanism (DDG) [Kairouz et al.. 1021 addresses the above issues by injecting independent discrete Gaussian noise (Canonne et al. (0200 to the gradients at each participant. Similar to the binomial distribution, the discrete Gaussian distribution is also defined over an integer domain; meanwhile, DDG is fully compatible with the moment accountant analysis technique in DP-SGD, and, thus, enjoys the tight privacy cost analysis. However, the dis- crete Gaussian distribution is not aggregatable. meaning that the sum of noise drawn from multiple i.idd. discrete Gaussian distributions does not follow another discrete Guassian distribution, which renders analysis difficult under in the decentralized setting of FL, and leads to looser bounds in the privacy analysis. Further, the privacy guarantee of the aggregated noise in DDG degrades linearly with the dimensionality d of the gradients, leading to poor scalablity to large neural networks.
Our contribution. In this work, we propose a new mechanism for enforcing distributed differential privacy for federated learning: the distributed Skellam mechanism (DSM), which injects random noise drawn from the symmetric Skellam distribution. Although the Skellam distribution has been
2

---

Under review as a conference paper at ICLR 2022
used before in the DP literature (Valovich & Alda 2017). the privacy analysis therein does not cover the decentralized setting of FL, or the iterative, sampling- sanpling-bbsed SGD algorithm, both of which require highly non-trivial mathematical analysis.
Specifically, we prove that DSM satisfies both Rényi-DP and (e, 6)-D,, defined in Section Similar to competitor DDG described above, DSM is compatible with the DPSGD framework and its moment accountant analysis technique, leading to tight bounds on the privacy loss analysis. Meanwhile, unlike DDG, the privacy guarantees of DSM are independent of the dimensionality of the gradients, which scales well to large models. Further, similar to the continuous Gaussian distribution (and unlike the discrete Gaussian distribution in DDG), i.i.d. Skellam noise values can be aggregated to form an amplified noise that still follows the Skellam distribution, which leads to clean and elegant proofs in the decentralized setting of FI., and tight bounds in the privacy analysis.
We apply DSM to federated learning with distributed SGD, with quantized gradients, e.g., re- quired by the MPC protocol, and present the complete training algorithm. Extensive experiments using benchmark datasets show that our solution leads to consistent and significant utility gains over its competitors, under a variety settings with different privacy and communication constraints.
PRELIMINARIES
random variable Y follows Poisson distribution of parameter À if its probability distribution is Pr[Y A-] =xp(= Z follows Skellam distribution it is the difference between two independent Poisson variables Yi and Yg. In this work, restrict attention to the where Y1 and Y2 have the same parameter A. In that case, the probability distribution of is
E k 0, 1, 2.... Both the mean and variance of Y is X. A random variable
Pr|Z- = k] exp( exp((22A44p ln| (2A), k =1, #2,
(I)
where [u) A En=o (I++h+++ write that Z Sk(A, A). By linearity of expectation, Z has mean 0 and variance 2X.
(Ø) (4) 2 is the modified Bessel function of the first kind. We
We say that two datasets X and X' are neighboring if one can be obtained by adding or removing one tuple from the other. The main idea of differential privacy (DP) is to ensure that the outcomes of a randomized mechanism on neighboring datasets are always similar; intuitively, this provides plausible deniability on whether given data record belongs to the dataset X or not, and, thus, protects the privacy of the individual whose record is z. A classic definition of differential privacy (c, 8)-DP (Dwork et al. 2006), as follows.
Definition 1 ((E, 8) Diffferental Privacy (Dwork et al. 2006 ). A randomized mechanism M satis- fies (c, diffeerrrtt privacy (DP) if
Pr(M(X) E O] S exp(e) Pr[M(X') E O] + 5,
for any set of output C Ronge(M) and any neighboring datasets X and X'.
Note that (e, 5)DD can be considered as a worst-case privacy guarantee for a mechanism, as it enforces an upper bound on the probability ratio of all possible outcomes. An alternative definition called Rénfi-Diifcrential Privacy (RDP) (Mironov) 2017). which is built upon the concept of Rényi Divergence, considers the average case privacy guarantee instead.
Definition 2 (Rényi Divergence (van Erven & Harremoës 2014)). Assuming that distributions P and Q are defined over the same domain, and P is absolute continuous with respect to Q, then the Rényí divergence of P from Q of finite order (0, (1, oo) is defined as:
P(X)
(P(l))
Ex
(3)
Q(X)
where we adopt the convention that 8 buse e.
0 and
= =0 for any y > 0, and the logarithm is with
Definition 3 (Rényi Differential Privacy Mironov 2017 ). A randomized mechanism M satisfies (a, 7) Réényi differential privacy (RDP) if (M, (X')) & T all neighboring datasets X and X'.
3

---

Under review as a conference paper at ICLR 2022
Given function of interest, the canonical way make it differentially private is perturb its out- come through noise injection. Roughly speaking, the scale of the noise should be calibrated to the sensitivity of the function of interest (Dwork et al. 2006), formally defined as follows.
Definition 4 (Sensitivity). The sensitivity S(F) of function F D Rd, denoted S(F), is defined as
S(F) X-X F(X')ll
where X' denotes that X and X' are neighboring datasets, and ||-I|| a nomm
In particular, injecting continuous Gaussian noise sampled from .V( each dimension of function F satisfies (a, as*(F)) >
2n >-RDP (Mironov 2017), where S(F) stands for the Le sensitivity of function F. In many applications. we also need analyze the overall privacy guarantee of mechanism consisting of multiple components (e.g.. training neural networks with SGD). We have the following composition and sub-sampling lemmata for RDP mechanisms.
Lemma 1 (Composition Lemma (Mironov 2017)). If mechanisms MI satisfies
(a, TT),.... (a, TT) -RD,, respectively, then M, o... o MM satisfies (a,, Ei=1 T.D-RDP.
Lemma 2 (Subsampling Lemma (Zhu & Wang 2019; Mironov et al. 2019)). Let M be mech- anism that satisfies (I, ( for l 2..... a (a E E, > 2), and Sq be procedure that uniformly sample each record of the input data with probability q. Then M Sq satisfies (a, T)- RDP with
1 a-1 log (1-9)"-1(ag 9
Finally, any mechanism that satisfies (o,T))-DP also satisfies (c,8)-DP, for values of and ō as follows.
Lemma 3 (Converting (a, RDDP to (c, (DD (Canonne et al. 2020 For any a E (1, if Da(M(X)))M(X)) S T for any neighboring databases X and X", then M satisfies (e, DDD for
1og(1/5) + (a log( 1/a) - log(a)
(4)
3 DISTRIBUTED SKELLAM MECHANISM
Section 3.1 first formalizes the problem of distributed sum estimation, and presents the proposed distributed Skellam mechanism (DSM) for this problem. Section 3.2 establishes the privacy guar- antees of DSM. Then, in Section 3.3 private federated learning.
we apply DSM to our main problem setting: differentially
3.1 FORMAL DESCRIPTION
Suppose that integer-valued multi multi-dimensional dataset X individuals (referred to as clients in the following), where client possesses data point &; E Zd for assume that the L2 and f.x. norms of each x; is bounded
(......, Ir,) is distributed to
i == .,....;h.. n. Without loss of generality, by constants A₂ and A respectively, i.c., ||æi||2 S A and || < Ao for any I; E X. An untrusted server aims to compute the (approximate) sum of the dataset, i.c., the clients. The computation of æ must satisfy differential privacy. In particular, we focus on the RDP definition (Definition which can be converted the classic (c, 5)-DP (Definition) T through
Σ" Iy, from
Lemma 3
Specifically, we aim to design a private mechanism M, such that for all neighboring datasets X, X',
(a(M(X)IMMX))) ST,
(5)
for some > 1. We measure the error of M by
Err. max E Xc2
M(X)
Σ
(6)
xeX
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Distributed Skellam mechanism
Input: Private dataset X (a1,..... un). Noise parameter Secure aggregation protocol A(-).
Output: ă, a private estimation of >nex a.
for xq E X do
#1 - Zi + Z, where Z = (Z',..., ,..,,""""
) is sampled as in Eq.
A ..... In); secure aggregation.
where the expectation taken over the randomness in M.
Next, present the proposed solution DSM for the above distributed estimation problem, outlined in Algorithm [ Each client i first independently samples a noise vector following the Skellam distribution, and injects this noise her data (Line in Algorithm []. In particular, the client samples a random d-dimensional noise vector Z = (Z) , 2d,, where each element is identically and independently distributed, and follows the Skellam distribution of parameter X, i.e.,
7 ,,...., 2d iid Ak(
We assume the clients have black-box access to secure aggregation protocol A, following the convention in (Agarwal et al., 2018 Kairouz et al. 2021). The clients then compute the sum their perturbed data using A, and release the sum to the server (Line 3 in Algorithm I
Modular Arithmetic with communication constraints. When each element zy in X is represented using limited number B of bits, each client needs perform extra step of modulo operation depending on B after injecting Skellam noise (Line 2), so as to avoid overflows. Accordingly, after obtaining the sum (Line 3), the server also needs to unwrap the modulo operation recover the original noisy sum. We refer the reader to (Kairouz et al.) (021) for a detailed discussion on this issue. In our experiments in Section 4 demonstrate that the proposed solution DSM achieves significant accuracy gains compared to existing approaches with various settings of the bit limit B.
3.2 THEORETICAL ANALYSIS
The following theorem states the privacy guarantee for Algorithm T which the main theoretical result of this paper.
Theorem 1 (Privacy guarantee of the distributed Skellam mechanism). When 1 < <
2nd
+ 1,
Algorithm / with noise parameter À satisfies (a, Ré-één Differential Privacy with Ax
1.09a + 0.91
A3
2nA
Proof. To prove the privacy guarantee of Algorithm it suffices derive the privacy guarantee of the sum of (5kx(x;))) ) Note that the secure aggregation protocol AA (used as a black-box) ensures that only the sum of the perturbed data is revealed to the server. In addition, according properties of the Skellam distribution, aggregating n independent Skellam noise vectors Z ~ Sk(A, A) results in single Skellam noise Z ~ Sk(nn,, nı) (Skellam 1946). Hence, we only need focus on the privacy guarantee achieved by Z. Further, in what follows, we focus on the one dimensional case of the problem, i.e., d = 1. The proof in the general case where d >> 1 then follows from the additivity of Rényi divergence for product distributions (van Hrven & Harremoës 2014).
Without loss of generality, we 0, Z Sk(A, A) and compute We first present several useful inequalities, whose proofs can be found in the appendix. Let
(( +|)))
(v + 1)2 +
Qu,(v)= =
(9)
According to Lemma in the appendix, we have:
(t) (t) S (v.
(10)
5

---

Under review as a conference paper at ICLR 2022
In addition, for any 0 < S w, according to Lemmata 7 in the appendix, we have
+ V 12 +1
I e2w-a
(11)
(a - w) + v (a w)2 +
and w Vuz u2 +1
((a- w) V(a Va- w)2 +1) Sc:
(12)
By the definition of Skellam distributions and Eq.
9
(2A)
a-1
Φ = Σ
Pr(z =
Σ (Q..x(z)))~1 Pr(z
|r|Z =
|kt0 (2x)
2--00
2=-20
Σ (Q.2)())) a-1
Pr|z =] 3 (()2212))) (Q02)(=))))-) Pr[Z z/.
I=|S
We compute
(Q.2x(z)))-11 +
= (0=21(1)))222222) = (R.2x())+ + Re)2((2)
1
where
Ra,2((2)= Q22x(2)
7
(2,2x(=z)
By Eq.
when 2 2 i.
zti+ + ()) (21)2
نtي + v 24
2x
)2
+1
expl
<
-i+++ v( 2 +) (2A)²
( 23
12+1
2A
Therefore, when 2 2 8, we have Q22x(2)
Q,22((-5) < exp (*) ) and R2,2((z) < exp
ss(a-1)=)
Since the
function e + o + is increasing,
Rx,2(()) + R.22(()] < exp
=/a-112)) 23
+ eexp
21
By Eq. 12 when 2 2 i,
2 ztit 122 + 1)2 + (2X)²
-2 (-2 1)2 + (2X)2
21
21
)
2
(=s
الج 2 v (
=
2x
2X
2x
+1
S exp (i)
Hence, when 2 8, we have Qs (z). < <exp
s(s+1)
MMenwwhle, when -8<26
according to Lemma in the appendix, we have:
Q2.2x(2) S exp
(s(*t))
2A
Therefore,
4 < exp
s(s+1)(a-1)
Lee (exp(
+ exp( - 2x 11)= Priz = 2]
42
2x
+ Diー > exp
s(a-1)(ote) 21
Pr|Z = 2]
S exp
3(aa-))
Dx
-==-o0
exp
s(a-1))
Pr|Z = =]
exp
((a--)
E.
exp
s(ax-))
The moment generating function of Sk(A, A) is B[e = co When 0 < < 1, we have
e' +t - 1.09t?. Thus, when x s(a-1)
2
E exp s(a-1)22 2\
S exp (1.09>( (100)(((==1)))) 11)= = exp (1099((a-112)
2x
As a result, when A >> s(a-1)
2 we have +b < exp
((aa-1) +
2x
11

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Federated learning with distributed Skellam mechanism
Input: Private dataset X
(..,,..,, F.). Sampling parameter q, La norm clipping bound C' >> 0.
Quantization granularity ?. Conditional rounding parameter k. Noise parameter A. Black-box secure aggregation protocol A(-). Initial model parameters 6, Number of iterations T.
Output: 9 model parameters learnt X.
for E 1..T
The server shares the current model parameters clients, sample subset of clients uniformly at random from all clients using Poisson sampling with rate q.
C "--."" (1.2)...,
for i E C do
9:
Vo(as);
I/ gradient computation.
9:
Cléplars C);
If gradient clipping based on C2 norm.
gk/m;;
I/ quantization.
Roundlyg k); I/ conditional rounding.
9
Distributed Skellam mechanism ((g. (eg, X, A(-)).
10
9
Y g:
I/ re-scaling
11
0
Update(0.
// model update based on the approximate gradient sum
Note that the privacy guarantee of DSM in Theorem i independent of the data dimensionality d. Next we analyze the error incurred by Algorithm [ which has the following bound:
Corollary (Error bound of the distributed Skellam mechanism). With < a < 2nd
+ 1, the error
A
incurred by Algorithm 7 that satisfies (a, -RDD is bounded by
1.09a + 0.91
dA
Errm S
2
The proof for the above corollary is omitted for brevity, which directly follows from Theorem aadd the linearity of expectation. Note that the error bound in the above corollary is comparable with (i.e., within a constant factor) that of adding continuous Gaussian noise in the centralized setting, which is (a-1 1) A (2+) (Mironov) 2017). Meanwhile, since Algorithm|] [ satisfies RDP, by Lemmata 2 it allows the tight privacy accounting DPSGD through composition and subsampling. Note that although the above analysis restricts the value of to 1 < a < 2nA/A.o 1. this constraint only affects the utility of DSM, not its privacy guarantees. Further, in practice, n (i.e, the number of training data points) is usually much larger than A leading to a large range of values for a. In addition, the optimal (order of RDP) is often relatively small (e.g. less than 10) in our experiments, and the above range represents sufficiently large space for tuning a.
Comparing the theoretical results DSM with those of existing solutions described in Sec- tion 1 cpSGD (Agarwal et al. 2018) does not satisfy RDP, and does not have the cor- responding composition and sub-sampling properties that are crucial for tight privacy anal- ysis. Mcanwhile, DDG (Kairouz et al. 2021) ensures (a, RDP with T'
min
1 - + p.p.p. d,
when each client independently injects discrete
Gaussian noise of variance o² to her data, where p is defined p = 10 10-E exp(-2x20' E+1 Note that the above r' term increases with the data dimensionality d, which not scalable for large d. In contrast, the privacy guarantee of DSM is independent of d. These advantages of DSM lead to significant utility gains in our target application: FL under differential privacy, described next.
3.3 FEDERATE LEARNING WITH DISTRIBUTED SKELLAM MECHANISM
We apply the proposed DSM described in Algorithm 1 to enforce DP on federated learning with distributed SGD, assuming that the clients have access to a black-box secure aggregation protocol. Algorithm 2 outlines the training process. In each iteration, the server releases the current model parameters to all clients (Line 2). Then, DSM randomly selects a subset clients, whose identities not known to the server (Line 3). Each client in the selected subset then computes the gradients based on the current model weights and her own data (Line 5), and performs gradient clipping (Line 6), which is standard step introduced in DPSGD bound the sensitivity of deep learning with

---

Under review as a conference paper at ICLR 2022
DP. After that, the client quantizes the gradients (Line 7). required by typical MPC protocols for gradient aggregation. Here, a parameter y controls the quantization granularity: a smaller y leads to more precise quantization, and vice versa. Subsequently, the client randomly rounds the gradient to the integer grid Zd (Line 8, explained soon). Next, we apply the distributed Skellam mechanism (Algorithm[]] 1 the integer-valued gradients (Line 9). Finally, the server re-seales the approximate gradient sum by a factor of y (Line 10) and updates the shared model accordingly (Line 11). We omit additional details on the updating process (e.g., learning rate schedule, weight decay, etc.) they do not affect the general framework or the privacy guarantees. After repeating the above process for T iterations, the training terminates, and the server obtains the final model weights A.
This step is necessary since after gradient clipping (Line 6) and quantization (Line 7), we still have real-valued gradients, which are not compatible with the MPC protocol (i.e., the black-box secure aggregation protocol A used in DSM). To explain the conditional rounding in Line 8, we first define an element -wise unconditional rounding process as follows: for input E IR, is rounded to floor(x) with probability ceil(z)) T, and to cail(a)) otherwise. The problem with this unconditional gradient rounding process is that it introduces an additional ((d) term on the Le sensitivity of the resulting integer gradients. To mitigate this issue, Kairouz et al. (2021) propose to repeatedly run the unconditional rounding algorithm until the L2 norm of the rounded result satisfies a pre-defined condition. 'he stopping condition in (Kairouz et al. (02T) is rather complex, and increases the sensitivity of the resulting gradients by a factor of d(d)). Algorithm 2 adopts this general idea, but sets much simpler stopping condition than the one in DDG, as follows: the rounded gradient's La norm must not exceed a pre-defined constant & (e.g.. 5 in our experiments) times C/y, where C' is the Lg clipping bound in Line 6, and y the quantization granularity in Line 7. With this stopping condition, the increase in L2 sensitivity in Line 8 is a constant independent of the gradient dimensionality d.
Next we clarify the conditional rounding step (Line 8 of Algorithm 2
Regarding privacy guarantees of Algorithm 2 observe that each iteration of the training process can be seen as running the distributed Skellam mechanism on random subset of rounded gradients. This is because the model sharing (Line 2), gradient sum re-scaling (Line 10), and model updating (Line 11) do not incur any additional privacy loss, as the updated model can be reconstructed by the re-scaled perturbed gradient sum, which, in turn, can be computed from the perturbed gradient sum. In addition, since the identities of the random subset of clients not known to the server, the privacy guarantee benefits from amplification by subsampling. (We refer the reader to (Kairouz let al. (021)) for detailed discussion this issue.) Hence, the privacy guarantee of Algorithm follows by applying the composition lemma (Lemma T and the amplification lemma (Lemma 2 on the privacy analysis of DSM (Theorem 1. A formal statement of the privacy guarantees of Algorithm is presented in Theorem 2 in the appendix.
4 EXPERIMENTS
We evaluate the performance of the proposed solution DSM (Algorithm 2 on two classic benchmark datasets: MNIST (Lecun et al., 1998) and Fashion MNIST (Xiao et al.] 2017). which contains grayscale images of handwritten digits and clothing, respectively. Both datasets represent 10-class classification tasks with 60, 000 training data records. We regard each data record in the training data as client. For both tasks, we train three-layer neural network with fully connected layers and ReLu activation, following previous work (Agarwal et al.) 2018). We set the number of neurons per layers to 80, resulting in model with d = 63, 610 weights. For DDG and DSM, we use the same L2 clipping norm (C = 1) and quantization granularity (y = 0.1). In addition, for cpSGD, we apply the tighter privacy analysis presented in (Koskela et al. (02T), which leads to improved prediction accuracy. For all experiments, we use the Adam optimizer (Kingma & Ba] (0155) with learning rate 7) = 0.005. We do not tune the saper-pprameters favor of any particular solution and omit additional experiments on hyper parameter tuning. We remark that our approach is compatible with existing differentially private parameter tuning techniques (Gupta et al. 2010 2019). which is orthogonal topic to this paper.
Liu & Talwar,
Our evaluation uses the (c, 6D- (Definition D definition instead of RDP (Definition 3 since a competitor cpSGD supports the former but not the latter. We fix 8 to 10 and vary the privacy parameter e from 21,2,3, 3, 4, 5). batch size m from {120, 240, 480, 960). The model is trained for 1 epoch, i.e., when m equals 120, 240, 480, and 960, we train the model for 500, 250, 125, and
8

---

Under review as a conference paper at ICLR 2022
MNIST, # (12, 32).
MNIST. 3.m 120.
MNNST. 3, B (12,32)
100
2001
100
50-
80
1cst aocurncc
LosE Sccuracy
30-
30-
20
20-
120
2.0
350
B
(a) Varying
(b) Varying B
(c) Varying m
Figure 1: Evaluations on MNIST with varying privacy parameter e, bit limit per weight B, and batch
size m.
Fashion MNIST, B E (12, 22). m 120.
Fashion MNIST. + 3, 120.
Fachion MNIST. 3, (12,32).
accurncy
Test aocuraycy
70
Iest ascummcy
70
60
10-
10
12
32
190
(a) Varying
(b) Varying B
(c) Varying
Figure 2: Evaluations on Fashion MNIST with varying privacy parameter bit limit per weight B, and batch size m.
62 rounds, respectively. For (DDG) and our solution DSM, we also vary the bit limit per weight B from {6, 8, 10, 12) bits; for cpSGD, we fix B to 32. This is because the amount of noise injected by cpSGD is rather large, and smaller values of B lead to very poor model utility. Note that a large B leads to higher communication costs between the clients. We report the average test accuracy over 5 runs. The results are shown in Figures and 2 In addition, we have also included the non-private baseline and the centralized-DP baseline DPSGD (Abadi et al. 20166b in the figures.
Overall, the proposed solution DSM (marked as "Skellam" in the figures) significantly outperforms its competitors cpSGD and DDG on all settings. In particular, the accuracy improvement over DDG is consistently around 15% and 10% for MNIST and Fashion MNIST, respectively. From Fig- ures a)) and aa)) we observe that the performance gap expands as e decreases, which corresponds to stronger privacy protection and requires higher noise levels. According to Figures bb) and (2bb) our solution is the only mechanism that achieves acceptable accuracy when the number of bits B is as low as 8 per weight, which corresponds to a stringent constraint on the communication costs in the underlying MPC protocol. The test accuracy obtained with cpSGD is rather low (no more than 30%), even though it is given generous value of B 32. Finally, according to Figures [c) and Cic), the accuracy for all methods remains stable with varying batch size m.
5 CONCLUSION
In this work, we propose the distributed Skellam mechanism (DSM), a novel solution for enforcing differential privacy on machine learning models built through an MPC-based federated learning pro- cess using distributed stochastic gradient descent. Compared to existing solutions, DSM achieves privacy guarantee that is independent of the dimensionality of the weight vector, while allowing tight privacy accounting due to its nice composition and sub-sampling properties. We conduct ex- tensive experiments on two classic benchmark datasets and various practical settings, and the result demonstrate the consistent and significant accuracy gains DSM over existing solutions.
Regarding future work, we plan to further reduce the constant factor in the privacy analysis for DSM to improve model utility under the same level of privacy protection. Another promising direction is to open up the black box of the MPC protocol and perform careful privacy analysis with consider- ations for the details of MPC protocol. which might help lower the noise level further, leading to a more favorable privacy-utility off for federated learning.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We provide our source code for our distributed Skellam mechanism implementation for re- viewing purposes, available httphttpss///noyyaaan 4open.
Skellam [xellam_Mechanisee Our implementation simulates federated learning with single machine.
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large- scale machine learning. OSDI, pp. 265-283, 2016a.
Martín Abadi, Andy Chu, lan J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Zhang. Deep learning with differential privacy. In CCS, pp. 308-318, 2016b.
Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H. Brendan McMahan. Cpsgd: Conmunication-efficeent and differentially distributed sgd. In NeurIPS, pp- 7575-7586, 2018.
Naman Agarwal, Peter Kairouz, and Ziyu Liu. The skellam mechanism for differentially private federated learning, 2021.
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, and Abhishek Jain, Round-optimal secure multiparty computation with honest majority, In CRYPTO, pp. 395-424, 2018.
Laforgia Andrea and Natalini Pierpaolo. Some inequalities for modified bessel functions. Journal of Inequalities and Applications, 2010.
Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, and Anat Paskin- Cherniassky. Non-interactive secure multiparty computation. In CRYPTO, pp. 387-404, 2014.
James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly)logarithmic overhead. In CCS, pp. 1253-1269, 2020.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In CCS, pp. 1175-1191, 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In NeurIPS, pp. 1877-1901, 2020.
Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. In NeurlPS, 2020.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In SEC. pp. 267-284, 2019.
David Chaum, Ivan Damgård, and Jeroen van de Graaf. Multiparty computations ensuring privacy of each party's 's input and correctness of the result. In CRYPTO, pp. 87-119. Springer, 1987.
Adam Coates, Brody Huval, Tao Wang, David J. Wu, Bryan Catanzaro, and Andrew Y. Ng. Deep learning with COTS HPC systems. In ICML,, pp. 1337-1345, 2013.
Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015.
10

---

Under review as a conference paper at ICLR 2022
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoe V. Le, Mark Z. Mao, Marc' Aurelio Ranzato, Andrew W. Senior, Paul A. Tucker, Ke Yang, and Andrew Ng. Large scale distributed deep networks. In NeurIPS, pp. 1232-1240, 2012.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pp. 265-284, 2006.
Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan R. Ullman, and Salil P. Vadhan. Robust traceability from trace amounts. In FOCS, pp. 650-669, 2015.
Vitaly Feldman. Does learning require memorization? a short tale about long tail. In STOC, pp- 954-959, 2020.
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin. On 2-round secure multiparty computation. In CRYPTO, pp. 178-193, 2002.
Slawomir Goryezka, Li Xiong, and Vaidy Sunderam. Secure multiparty aggregation with differential privacy: A comparative study. In Joint EDBT/ICDT 2013 Workshops, pp. 155-163, 2013.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In SODA, pp. 1106-1125, 2010.
Yuval Ishai, Eyal Kushilevitz, and Anat Paskin. Secure multiparty computation with minimal inter- action. In CRYPTO, pp. 577-594, 2010.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In ICML, pp. 5201-5212, 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015,
Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valuee mechanisms and for the subsampled gaussian mechanism using FFT, In Arindam Banerjee and Kenji Fukumizu (eds.), AISTATS, volume 130, pp. 3358-3366. PMLR, 2021.
Y. Lecun, L.. Bottou, Y. Bengio, and P. Haffner. Gradient-hased learning applied to document recog- nition. Proceedings of the IEEE, 86(1 86(11):222)) 1):22722222238 1998.
Jingeheng Liu and Kunal Talwar. Private selection from private candidates. In STOC, pp. 298-309, 2019.
Ryan T. McDonald, Keith B. Hall, and Gideon Mann. Distributed training strategies for the struc- tured perceptron. In HLT-NAACI, pp. 456-464, 2010.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Commuication--fficient learning of deep networks from decentralized data. In AISTATS, pp- 1273-1282, 2017.
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. In S&P. pp. 691-706, 2019.
Ilya Mironov. Rényi differential privacy. In CSF, pp. 263-275, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. CoRR, abs/1908. 10530, 2019.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Stand-alone and federated learning under passive and active white-box inference attacks. In S&P, pp. 739-753, 2019.
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EURO- CRYPT, pp. 223-238, 1999.
Apostolos Pyrgelis, Carmela Troncoso, and Emiliano De Cristofaro. Knock knock, who's there?
membership inference aggregate location data. In NDSS, 2018.
11

---

Under review as a conference paper at ICLR 2022
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In S&P, pp. 3-18, 2017.
J. Gordon Skellam. The frequency distribution of the difference between two poisson variates be- longing different populations. Journal the Royal Statistical Society, 109:296-296, 1946.
Congzheng Song and Vitaly Shmatikov. Auditing data provenance in text-generation models. In KDD, pp. 196-206 206, 2019.
Congzheng Song and Vitaly Shmatikov. Overlearning reveals sensitive attributes. In ICLR, 2020.
Congzheng Song, Thomas Ristenpart, and Vitaly Shmatikov. Machine learning models that remem- ber too much. In CCS, pp. 587-601, 2017.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach privacy-pree preeeeriig federated learning (extended abstract). In- form. Spektrum, (2(():356- (111)))363357,2222 2019.
Filipp Valovich and Francesco Alda. Computational differential privacy from lattice-based cryptog- raphy. In NuTMiC, pp. 121-141, 2017.
Tim van Erven and Peter Harremoës. Rényi divergence and kullback-leibler divergence. IEEE Trans. Inf. Theory, 60(7):3797-38200 2014.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnine a novel image dataset for benchmark- ing machine learning algorithms. CoRR, abs/1708.07747, 2017.
Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In FOCS, pp. 162-167, 1986.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learn- ing: Analyzing the connection to overfitting. In CSP, pp. 268 282, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun, ACM, 64(3):077-11,, February 2021.
Yuqing Zhu and Yu- Xi-ni Wang. Poission subsampled Rényi differential privacy. ICMI, Pp- 7634-7642, 2019.
12

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
A.1 PROOFS
Lemma 4, Let (5,((v)= = =I 044t (144)2442
1 (0) Then, (1)+ S Qs,
Proof. By properties of the modified Bessel function of the first kind (Andrea & Pierpaolo 2010). have inequality
1--1(t) In(1)
4+ 22
w 2 0
1
and recurrence relation
20 Lo(
lo41(t) 1--1(t)
which leads to
lu+1(t) - V22 (t)
v 020 0.
When O, substituting for - 1 in the previous formula,
(t) I_t(t)
++1+ + V (u + +
(t) ----1(t)
t
When 2 0, we also have
(t)(t) 1o(1)
u+l+
( +
+
[++1((() T0+1(()
t
Therefore, for every v.
(t)(t)
+ + V(u + 1)2 +
Qu)(v).
luto (t)
t
Lemma 5. For any w 2 0,
+ V w2 +1 6
Proof. The inequality holds when 0. By taking the derivative, it can be verified that the function e (w Vu² +1] 1) is increasing with respect w.
Lemma 6. For any a S w.
W + 2
S 2w-
(a - w) + aa - 2
Proof. By Lemma 5 w + V +1 < "" Then, by Lemma again,
+1 "0a (a-w) + V (a - w|=+ (w a) + V(w +1
Lemma 7. For any < a < w,
(w + V +1) ((a-w) w) + V(a w)² + 11 S ea
Proof. By Lemma 5 the inequality holds when w = a. By taking derivative, it can verified that the left hand side is decreasing with respect w.
13

---

Under review as a conference paper at ICLR 2022
Lemma 8. When < we have
[s(++)) + 2)
[((s
Qs,2x(2) S exp
22
Proof. Use Lemma 5
When 0 S 2 < 8,
2 +
(s(++1 +1+1+00 [ 22)
(s(s + 2)
Qx22(2) S
exp
= exp
cxp
2X
41
2A
==1
When - S < O, using the equality
b b+ /b2 + (2X)²
+b+ V(-b) + (2X)2
1,
2\
2X
we have
2 2+14 (z+ 8)2 (2X)
2x,2x (z)
2X
i=1
2 (z + 1)2 + (2X)²
2\
2+1
II exp
8(s 22 1)
exp
41
8(8 2)
I exp
2A
When - <<2 < - have
-25-8-1
2
(2 + 1)2 (2X)²
Qx.2((2)= =
2x
51
3(3 + 2)
S exp
2X
A.2 PRIVACY GUARANTRE OF ALGORITHM
Theorem (Privacy guarantee Algorithm 2. Let a E Z,2 < a < + Then for L2 norm
2ndy
CE
clipping bound C, noise parameter quantization granularity 7, conditional rounding parameter k, sampling parameter q, and iterations T, Algorithm satisfies (a, Réééé Differential Privacy with
T
log (1- (ag y 1)
á
1 (1)1 -'-'g(e(-1)7()) (13)
a
where Ti is defined as T.
1.091+0.91
C²K² 2n for / 2, ...
We omit the proof for brevity, which follows from our main theoretical result Theorem as well as subsampling (Lemma 2 and composition (Lemma
14

---

Under review as a conference paper at ICLR 2022
A.3 OVERFLOWING IN MODULAR ARITHMETIC
The key to avoid overflowing is to restrain the perturbed gradient weights within the range of the finite integer filed, namely [-2B-1, 2 I]. We first review the concentration property of the symmetric Skellam distribution ~ Sk(2, X) of mean O. Note that Z has MGF exp(A(exp(A) + exp(-A) 2)). addition, since x (exp(z) + exp(-x) - 2) S 1.09x for
1. We have
that Z is sub-exponential with parameters (v2.18, 1). Namely,
E| [[exp(t2]] - exp((.09t for |t| S 1.
(14)
From here obtain the tail bound for Z,
Pr[Z 2 z] I exp(-x/2), for 2.18.
(15)
Hence, to avoid overflowing due to the Skellam noise, it suffices to set 2 2 h log d, where is dimension of the gradient weights, and some constant to balance the communication cost and the error due to overflowing. A relatively large h limits the error due to overflowing while incurring a large communication cost; and vice versa. Note that a more precise reasoning can be obtained by observing that Z approaches normal distribution with mean and variance 2 when Z is of order 22. In fact, in experiments, we observe that overflows are rare under reasonable communication constraint. To be more specific, no overflow was observed when the number bits per dimension reaches 10 above, and very few overflows occured when the number of bits per dimension is 8 (once every a thousand weights).
A.4 CONCURRENT WORK
Agarwal al. (20TT) also suggest using the Skellam noise in the distributed DP setting. Different from our work, their privacy analysis for the Skellam noise is dependent both the L2 norm and LI norm of the private input vector. Since LI norm of a high dimensional vector can be much larger than its L2 norm, the privacy analysis we present is tighter. Further tightening the analysis is a promising future direction.
15


Reviews:
[{"review_id": "gEx3_q3ei3j", "reviewer": "Reviewer_ecND", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths of the paper: \n\nThey study a problem that is of fundamental importance in privacy preserving machine learning. The use of Skellam distribution seems novel and interesting.\n\nWeaknesses of the paper:\n\nFirstly 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. \n\nSecondly, 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QTCDK2_Ccxv", "reviewer": "Reviewer_85EN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper is clearly structured and the theoretical proof is very logical.\n2. Some nice properties of Skellam mechanism are considered, i.e., sum of Skellam random variables is Skellam distributed.\n\n\nWeaknesses: \n1. 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\n2. 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LWdtLgVFWv", "reviewer": "Reviewer_QVkQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n* 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)\n* The results seem to work clearly better than existing methods\n\nWeak points:\n* 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\n* I am not totally sure if the comparison against existing work is done entirely properly (see questions for authors below for details)\n\nQuestions and comments for the authors:\n1) Can you quantify how tight or loose the RDP bound in Thm1 actually is?\n\n2) 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?\n\n3) Very minor comment: there seem to be lot of small typos, please fix.\n\nReferences:\n[1] Koskela et al. 2021: Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT.", "summary_of_the_paper": "### update after the discussions\n\nI am satisfied with the responses from the authors' and the updated paper. I therefore recommend accepting the paper.\n\n---\n\nThe 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.\n\nIn 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.\n\nTo 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GmlRtILOHIZ", "reviewer": "Reviewer_VptB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. The privacy guarantee of DSM is non-trivial yet the analysis is clean. \n\n\n2. 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.\n\n\n3. The experimental results also support that DSM outperforms the existing DDG scheme in some parameter regimes, such as when the communication budget is limited.\n\n\nCons:\n\n1. 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.\n\n\n2. 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.\n\n\n3. 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. \n\n\n4. 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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