The Skellam Mechanism for Differentially Private Federated Learning
Authors: Naman Agarwal
Peter Kairouz
Ziyu Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Distributed Learning
Federated Learning
Secure Aggregation

Abstract: We introduce the multi-dimensional Skellam mechanism, a discrete differential privacy mechanism based on the difference of two independent Poisson random variables. To quantify its privacy guarantees, we analyze the privacy loss distribution via a numerical evaluation and provide a sharp bound on the Rényi divergence between two shifted Skellam distributions. While useful in both centralized and distributed privacy applications, we investigate how it can be applied in the context of federated learning with secure aggregation under communication constraints. Our theoretical findings and extensive experimental evaluations demonstrate that the Skellam mechanism provides the same privacy-accuracy trade-offs as the continuous Gaussian mechanism, even when the precision is low. More importantly, Skellam is closed under summation and sampling from it only requires sampling from a Poisson distribution -- an efficient routine that ships with all machine learning and data analysis software packages. These features, along with its discrete nature and competitive privacy-accuracy trade-offs, make it an attractive practical alternative to the newly introduced discrete Gaussian mechanism. 

The Skellam Mechanism for Differentially Private Federated Learning
Naman Agarwal 'Google Research
Peter Kairouz" Ziyu Liut"
*Cameeie Mellon University
(namanagarwal, kairouz) kairouz)@googaa @google. com, ziyuliuecs. cmu, edu
Abstract
We introduce the multi-dimensional Skellam mechanism, a discrete differential privacy mechanism based on the difference of two independent Poisson random variables. To quantify its privacy guarantees, we analyze the privacy loss distribu- tion via numerical evaluation and provide sharp bound on the Rényi divergence between two shifted Skellam distributions. While useful in both centralized and distributed privacy applications, we investigate how it can be applied in the context of federated learning with secure aggregation under communication constraints. Our thcoretical findings and extensive experimental evaluations demonstrate that the Skellam mechanism provides the same tinuous Gaussian mechanism, even when the precision is low, More importantly, Skellam is closed under summation and sampling from it only requires sampling from a Poisson distribution an efficient routine that ships with all machine learn- ing and data analysis software packages. These features, along with its discrete nature and competitive privacy-accuracy trade-offs, make an attractive practical alternative the newly introduced discrete Gaussian mechanism.
trade-offs as the con-
1 Introduction
The Gaussian mechanism is the workhorse for a multitude differentially private learning algorithms [46, 10, 1]. While simple enough for mathematical reasoning and privacy accounting analyses, its continuous nature presents a number of challenges represented finite computers, making it prone to numerical errors that break its privacy guarantees [35]. Moreover, it cannot be used in distributed learning settings with cryptographic aggregation [12, 11].
practice. For example, cannot be exactly
multi-party computation primitives involving modular arithmetic, such To address these shortcomings, the binomial and (distributed) discrete Gaussian mechanisms were recently introduced [19, 2, 15, 25J. Unfortunately, both have their own drawbacks: the privacy loss for the binomial mechanism can be infinite with a non-zero probability, and the discrete Gaussian: (a) is closed under summation (i.e. sum discrete Gaussians is not discrete Gaussian), complicating analysis in distributed settings and leading to a performance worse than continuous Gaussian in the highly distributed, low-noise regime [25]; (b) requires a sampling algorithm that is not shipped with mainstream machine learning or data analysis software packages, making it difficult for engineers to use in production settings (naive implementations may lead catastrophic privacy errors).
Our contributions To overcome these limitations, we introduce and analyze the multi- malti--imeessonall Skellam mechanism, a mechanism based on adding noise distributed according to the difference of two independent Poisson random variables. The Skellam noise is closed under summation (i.e. sums of Skellam random variables is again Skellam distributed) and be sampled from easily efficient Poisson samplers are widely available in numerical software packages. Being discrete in nature also
Work done while Google Research. 'Alphabetical authorship.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

means that it can mesh well cryptographic protocols and can lead to communication savings.
To analyze the privacy guarantees of the Skellam mechanism and compare it with other mechanisms, we provide a numerical evaluation of the privacy loss random variable and prove a sharp bound on the Rényi divergence between two shifted Skellam distributions. Our careful analysis shows that for a multi-dimensional query function with é sensitivity A and & sensitivity 42, the Skellam mechanism with variance μ achieves (a,e(a) Rényi differential privacy (RDP) [36] for =(a) S
(see Theorem 3.5). This implies that the RDP guarantees are at most 1 + +0 (1/m) times worse than those of the Gaussian mechanism.
ad2 + min (2a-1)A,+62) 2y
3A1
4n
2p
To analyze the performance of the Skellam mechanism in practice, consider differentially private and communication constrained federated learning (FL) setting [26] where the noise is added locally to the d-dimensional discretized client updates that are then summed securely via cryptographic protocol, such as secure aggregation (SecAgg) [11, 12]. We provide an end-to-end algorithm that appropriately discretizes the data and applies the Skellam mechanism along with modular arithmetic to bound the range of the data and communication costs before applying SecAgg.
We show distributed mean estimation and two benchmark FL datasets, Federated EMNIST [14] and Stack Overflow [8], that our method can match the performance of the continuous Gaussian baseline under tight privacy and communication budgets, despite using generic RDP amplification via sampling [51] for our approach and the precise RDP analysis for the subsampled Gaussian mech- anism [37]. Our method is implemented in TensorFlow Privacy [32] and TensorFlow Federated [24] and will be open-sourced." While we mostly focus on FL applications, the Skellam mechanism can also be applied in other contexts of learning and analytics, including centralized settings.
Related work The Skellam mechanism was first introduced in the context of computational differ- ential privacy from lattice- based cryptography [49] and private Bayesian inference [45]. However, the privacy analyses in the prior work do not readily extend to the multi-dimensional case, and they give direct bounds for pure or approximate DP which makes only advanced composition theorems [28, 22] directly applicable in learning settings where the mechanism is applied many times. For example, the guarantees from [49] lead to poor securrcy-ppivace trade-offs demonstrated in Fig. 1. Moreover, we show in Section 3.1 that extending the direct privacy analysis to the multi-dimensional setting non-trivial because the worst-case neighboring dataset pair is unknown in this case. For these reasons, our tight privacy analysis via a sharp RDP bound makes the Skellam mechanism practical for learning applications for the first time. These guarantees (almost) match those of the Gaussian mechanism and allow us to use generic RDP amplification via subsampling methods [51].
The closest mechanisms to Skellam are the binomial [2, 19] and the discrete Gaussian mechanisms [15, 25]. The binomial mechanism can (asymptotically) match the continuous Gaussian mechanism (when properly scaled). However, it does not achieve Rényi a privacy loss that can be infinite with a non-zero probability, leading to catastrophic privacy failures. The discrete Gaussian mechanism yields Rényi DP and can be applied to distributed settings [25], but it requires a sampling algorithm that is not yet available in data analysis software packages despite being explored in the lattice-based cryptography community (e.g.. [43, 18, 38J. The discrete Gaussian is also not closed under summation and the divergence can be large in highly distributed
nero-concentrated DP [36, 13] and has
low-noise settings (e.g. quantile estimation [6] and federated analytics [42]), which causes privacy degradation. See the end of Section 4 for more discussion.
2 Preliminaries
We begin by providing formal definition for (E, ddiffeerretl privacy (DP) [20]. Definition 2.1 (Differential Privacy). For e, 8 2 O, a randomized mechanism M satisfies (c, 8)-P for all neighboring datasets D, D' and all S in the range of M, we have that
(D) E S) S é P (M(')) E S) + 5,
where D and D' are neighboring pairs they can be obtained from each other by adding removing all the records that belong to a particular user.
In our experiments we consider user-level differential privacy - i..., D and D' are neighboring pairs ex

---

if one of them can be obtained from the other by adding or removing all the records associated with single user [33]. This stronger than the commonly-use notion of item level privacy where, if user contributes multiple records, only the addition or removal of one record is protected.
We also make of Rényi differential privacy (RDP) [36] which allows for tight privacy accounting.
Definition 2.2 (Rényi Differential Privacy). mechanism M satisfies (orE))RRP if for any two neighboring datasets D, D', we have that D divergence between P and Q and is given by
S where Do (P, Q) is the Rényi
1)
P(x)
1)
(a(P,Q) & Q-1 log
B
a a- log
EnnP
Q(xx)
A closely related privacy notion is zero-concentratee DP (zCDP) [21, 13]. In fact, 2 is equivalent simultaneously satisfying an infinite family RDP guarantees, namely (a, a)) Rényi differential privacy for all E (o). The following conversion lemma from [13, 15, 7] relates RDP to (e, 0)-DP.
Lemma 2.3. M satisfies (a, SRDD, then, for any d > M satisfies (EDr()), where
( = inf E log(1/ao) a>
- + log(1 - 1//a).
For any query function f. we define the Ap sensitivity as maxp, If (((())-(DD)))) f(D')lpp where D and D' are neighboring pairs differing by adding or removing all the records from particular user. We also include the RDP guarantees of the discrete Gaussian mechanism (same RDP guarantees as the continuous Gaussian mechanism) to which we compare our method.
Definition 2.4 (The Discrete Gaussian Mechanism [15]), Given integer-valued query S(D) E zd and noise variance μu, the Discrete Gaussian (DGaussian) Mechanism is given by
J(D) + Z, where Z (0,
and N2(0, p)) denotes the discrete Gaussian distribution defined in Equation (1) of [15]. The discrete Gaussian mechanism achieves (o,, aه3
Rééný DP.
2p
3 The Skellam Mechanism
We begin by presenting the definition of the Skellam distribution, which is the basis of the Skellam Mechanism for releasing integer ranged multi-dimensional queries.
Definition 3.1 (Skellam Distribution). The multidimensional Skellam distribution Ska, e over zd with mean A e zd and variance is given with each coordinate X; distributed independently as
X; Ska.., with P(X; = "I,-A,,
for & E Σ. Here, (x) is the modified Bessel function of the first kind. A key property of Skellam random variables which motivates their use in DP that they are closed under summation, i.e. let X1 ~ Ska,, and X₂ ~ SkA2.02 then X1 X2 ~ Ska, 12 This follows from the fact that Skellam random variable X can be obtained by taking the difference between two independent Poisson random variables with means μ. We are now ready to introduce the Skellam Mechanism.
Definition 3.2 (The Skellam Mechanism). Given an integer-valued query f(D) Zd, we define the Skellam Mechanism as
= f(D) + Z. where Z ~ Sko and the total la error of the mechanism is bounded by E (I()),, S dp.
We only consider the symmetric version of Skellam, but it is often more generally defined as the difference of independent Poisson random variables with different variances.

---

The Skellam mechanism was first introduced in [49] for the scalar case. As our goal is to apply the Skellam mechanism in the learning context, we have to address the following challenges. (1) Tighr privacy compositions: Learning algorithms are iterative in nature and require the application of the DP mechanism many times (often > 1000). The current direct approximate DP analysis [49] can be combined with advanced composition (AC) theorems [28, 22] but that leads to poor privacy-accuracy trade-offs (see Fig. 1). (2) Privacy analysis for multi-dimensional queries: In learning algorithms, the differentially private queries are multi-dimensional (where the dimension equals the number of model parameters, typically 2 10%). Using composition theorems lead to poor accuracy-privace trade-offs and direct extension of approximate DP guarantee [49] for the multi-dimensional case leads to a strong dependence on & sensitivity which is prohibitively large in high dimensions. (3) Data discretization: The gradients are naturally continuous vectors but would like to apply an integer based mechanism. This requires properly discretizing the data while making sure that the norm of the vectors (sensitivity of the query) is preserved. We will tackle challenges (1) and (2) in the remainder of this section and leave (3) for the next section.
3.1 Tight Numerical Accounting via Privacy Loss Distributions
We begin by defining the notion privacy loss distributions (PLDs).
d
1, 4g -2= 10=100
Definition 3.3 (Privacy Loss Distribution). For a dinees-immensonnll discrete privacy
Gaussian (AC)
Privacy (6 10-9
10a
Geussian (RDP)
Gaussian (PLD)
mechanism M and neighboring datasets
DGaussian (AC)
D,D', for any x. E Zd, we define f(xx)
10
DGaussian (RDP)
DGaussian (PLD)
log PPM(D)=a) ((M() ) The privacy loss ran-
Skellam (AC)
dom variable of M (D, D') is Zp.D:
10"
Skellam (PLD)
Skellam (RDP)
fMM [22]. The privacy loss distribu-
50
100
150
200
250
300
tion (PLD) of M, denoted by PL.DD,D', is
Numbor Stops
the distribution of ZD.
Figure Comparing privacy compositions across vari- ous mechanisms and accounting methods.
The PLD of mechanism M can be used to characterize its (e, 8DDP guarantees.
Lemma 3.4. A mechanism M is (EP if and only if 8 2 EE-PLD [1- [1-e5-2 1 all neighboring datasets D, D' where [x]+ max(0, x).
When mechanism M applied T' times on a dataset, the overall PLD of the composed mechanism at (D, D') is the -'-fold convolution of PLDD,D [22]. Since discrete convolutions can be computed efficiently using fast Fourier transforms (FFTs) and the expectation in Lemma 3.4 can be numerically approximated, PLDs are attractive for tight numerical accounting [30, 34, 17]. Applying the above to the Skellam mechanism, direct calculation shows that with X, are i.i.d. according to Sko,p
(xx-1O))(())
Ix Ix,-F(D).(1) Ix (p)
DD log
When d = 1, suffices look at 7 = log(Tx- (1) and ~ Ska, Since X has a discrete and symmetric probability distribution and the log function monotonic, the distribution of Z can be easily characterized. This gives us tight numerical accountant for the Skellam mechanism in the scalar case, which we use to compare it with both the Gaussian and discrete Gaussian mechanisms. Fig. shows this comparison, highlighting the competitiveness of the Skellam mechanism and the problem of combining the direct analysis of [49] with advanced composition (AC) theorems. When d > 1, there are combinatorially many Zp. D that need to be considered, even when the & sensitivity of (D) is bounded. The discrete Gaussian mechanism faces a similar issue (see Theorem 15 of [15]). To provide a tight privacy analysis the multi-dimensionn case, we prove bound on the RDP guarantees of the Skellam mechanism in the next subsection. Fig. and show that our bound is tight and the competitiveness of the Skellam mechanism in high dimensions.
(n) Ix (n)), where A maxp (((D)-

---

3.2 Tight Accounting via Rényi Differential Privacy
The following theorem states our main theoretical result, providing a relatively sharp bound on the RDP properties for the Skellam machanism.
Theorem 3.5. For a 1 and sensitivity A E, the Skellam Mechanism is (a, E)-DDP with
ad2 + min
(2a
1) + 6A
3A
E(a) S
(3.1)
2μ
4p²
24
To remind the reader in comparison, the Gaussian mechanism (a, RDD with s(a) aه
2n The
bound we provide is at most 1 + O(1/p) worse than the bound for the Gaussian, which is negligible for all practical choices of ju, especially as the privacy requirements increase." Next we show simple corollary which follows via the independent composition of RDP across dimensions. Corollary 3.6. The multi- ciatttddimensonnll Skellam Mechanism is (a, (a,=)-RDP with
(2a
1) 6A1
3A1
:(a) S
min
(3.2)
2p
4p²
2/1
where A and 22 are the and lg sensitivities respectively.
3.2.1 Proof Overview for Theorem 3.5
In this subsection, we provide the proof Theorem 3.5 assuming a technical bound on the ratios of Bessel functions presented as Lemma 3.7, which is the core of our analysis and may be of independent interest. We provide a proof overview for Lemma 3.7, deferring the full proof to the appendix.
On macroscopic level, our proof structure mimics the RDP proof for the Gaussian mechanism [36]. and the main object of our interest bound the following quantity, defined for any X, a,
Ix- (x-as(1))
(Ix a-1
Xx (n) - log
(3.3)
Tx(1)
The following lemma states our main bound on this quantity.
Lemma 3.7. For any X, a E N, with a > and A E Z, we have that for all μ 2 0
(x)a(H)) a(a - 1) + min (2a 1) - 1)42 + 3(a - |
3(a - 1)|
2/z
44²
2μ
2p
Note that in contrast if we consider the analogous notion of & for the Gaussian mechanism (replacing Ix (14) with the Gaussian density e-x²/2np /2n), readily get the bound a(a-1) which is the same
2μx
our bound up to lower order terms. We now provide the proof of Theorem 3.5.
Proof of Theorem 3.5. By RDP definition (2.2), we need to bound the following for any A, a 2 1,
(xxa(u)) a-1 1
Da (SkA Sko,u) = Now consider the following calculations on the log term:
log
e-IIxa(m))
(x(u)
(x-
[xx=(m))
Ix-as(H) e (xas((e))
log
log
ea
[x(
Xm- el
X 00
< log
Σ e-"Ix-a(())
max $ (x.a,A(H) XEZ
X=-00
< a(a - 1)A2
(2a - 1)(a
(2a-1)(a - 1)A2
3(a 3(a- 1
3(a - 1) -
+ min
4u2
24
2μ
where the inequality follows from Lemma 3.7.
'The restriction that needs to be an integer is a technical one owing to known bounds on Bessel functions. In practice show, this restriction has negligible effect.

---

We now provide an overview for the proof of Lemma 3.7 highlighting the erux of the argument. As first step we collect some known facts regarding Bessel functions. known that for 2 0 and
V E Z, V 2 0, (xx) is a decreasing function in v. [_)(x) = (x) and 4u- is an increasing function in y [47]. A succession of works consider bounding the ratio of successive Bessel functions T (x)1())//)()), which a natural quantity to considering the objective in Lemma 3.7. We use the following very tight characterization for this recently proved in [44, Theorem 5].
[x)
Lemma 3.8. For any v 2 1/2, x 2 0 define the following function we have that (e0innh660(,,30 x)) < log(Iu-1(1)
log(I, (x)) I aresinh (12(,))))
where (u x) is defined as 5, (v, v-1/2
(a-12/ 22V (v+(a)))2222)))
Standard bounds such as those appearing in [5, 49] lead to the following conclusion:
arcsinh (1v- - 1/2)/a) S log(4--1(x)) (o)(4 S arcsinh (M/z)).
While the above bound is significantly easier work with, it leads an RDP guarantee of Gaussian RDP O A ). In high dimensions this manifests as O ( and overall leads to constant multiplica-
tive factor over the Gaussian. On the other hand we prove Gaussian RDP + og (1) bound. Our proof
of Lemma 3.7 splits into various cases depending on the signs of the quantities involved. We show
the derivation for a single case below and defer the full proof to the appendix.
Proof of Lemma 3.7 in the case X 2 aA, A 2 O. Replacing Y X - ad we get that
1y+(a-1)a(1) (lY+(a-n)a()) a-1
$ 4x (P) = =log
(p)
lY+as(H)
Y+jA+A
(1-14(0-1-5)(14 log 1:(1)
[I-1(1)
Σ
log
++J
Y+jA+A
Σ
(52 1a-1- 50(1.11))
1=0
i+++)++
a(a
1)A²
min a(la 1)A2 + 2(a 1)A
(a 1)A
2/1
2
where the first inequality follows from Lemma 3.8 and the fact that for all S S y, arcsinh(y)
arcsinh(z) < y and the second inequality follows from Lemma A. (provided in the appendix):
11
1/2
1/1 - 1/2
82(v1, x) - 6o(u2, x) S
min
2x
Applying the Skellam Mechanism to Federated Learning
With sharp RDP analysis for the multi-dimensional Skellam mechanism presented in the previous section, we are now ready to apply it to differentially private federated learning. We first outline the general problem setting and then describe our approach under central and distributed DP models.
Problem setting At a high-level, we consider the distributed mean estimation problem. There are clients each holding vector 2; in Rd such that for all i, the vector norm is bounded as ||x:]|2 S for some e 2 0. We denote the set of vectors as X = {x,) and the aim is for each client to communicate the vectors z; to a central server which then aggregates them as ă 1 Σ, z; for an external analyst. In federated learning, the client vectors 2; are the model gradients or model deltas (typically d 2 10%) after training the clients' local datasets, and this procedure be repeated for many rounds (T > 1000). A large d and T thus necessitate accounting methods that provide tight privacy compositions for nigh-dimensional queries.
We are primarily concerned with three metrics for this procedure and their trade-offs: (1) Privacy: the mean o should be differentially private with reasonably small (E, (2) Error: we wish to

---

1, 100, T-1
T
Skellam (RDP, )=
Skellam (RDP, ==
Skellam (RDP, 2m
Skellam (RDP. 2
Princcy (d- (d-1o.00)
Skellam (RDP,
Privacy (0-1+-06)
DDGauss (RDP, s=2)
DDCauss (RDP; 2-2
Gaussian (RDF)
Gausstan (KDP)
Gaussian (Anelytic)
6-
Gaussian (Analytio)
Gaussian (PLD)
Gaussian (PLD)
DCaussian (PLD)
DGaussian (PLD)
Skellam (PLD)
Siclllmm (PLD)
Sxellam (Direct)
Skellam (Direct)
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
20
40
60
80
100
Centrol noise multipller
Centrol maltiplter dth
Figure 2: Benchmarking Skellam on sensitivity-1 queries under various accounting methods. RDP: Rényi DP. PLD: privacy loss distributions. Skellam (Direct): [49]. Gaussian (Analytic): [9]. DGaus- sian [15]/ DDGauss [25]: central distributed discrete Gaussian. is the scaling factor applied to both A and a. For Skellam and DDGauss [25], the central noise with std is split into n shares each applied locally with std a /n; large n and small can thus exacerbate the sum divergence term of DDGauss (left). Left: S 10. Right: S 1.
100, 22 1, n 100, 1. 1-1
d
20
A2 0.03, 100, q n/N, T 1500
15.0
30
Skellam (RDP, s=2")
Skellam (RDP, s-2
Privacy e (6-1e-06)
12.5
Skellam (RDP, s=2*)
Privacy (6=1/N)
25
(RDP, s=2th)
Skellam (RDP, s=29)
Skellam (RDP, s=2
DDGauss (RDP, 2=
DDGauss (RDP, s=2
7.5
DDCauss (RDP, 2-25)
DDGauss (RDP, 2=24)
15
DDGauss (RDP, s=2
DDGauss (RDP, s=216)
5.0
Gaussian (RDP)
Gaussian (RDP)
2.5
0.0
0.5
3.0
Contral noise multiplier o/0g
Contral noise multiplier o/8g
Figure 3: Comparing Skellam and Distributed Discrete Gaussian (DDGauss) rellevalued queries, rounded to integers with B = e 0.5 -05 (Prop. 4.2). s is the scaling applied to both o and Ag; larger reduces the rounding error and norm inflation. q is the sampling rate. For Skellam and DDGauss [25], the central noise with std is split into n shares each applied locally with std exacerbate the sum divergence term of DDGauss. Left: Simple setting with A = 1. Right: FL-llike setting for training CNNs on Federated EMNIST.
multi-dimensional
a/ /n; large and small
minimize the expected &2 error; and (3) Communication: we wish minimize the average number of bits communicated per coordinate. Characterizing this trade-off is an important research problem. For example, it has been recently shown [50] that without formal privacy guarantees, the client training data could still be revealed by the model updates z;; on the other hand, applying differential privacy [48] to these updates can degrade the final utility.
Skellam for central DP The central DP model refers to adding Skellam noise onto the non-private aggregate 26 before releasing to the external analyst. One important consideration is that the model updates in FL are continuous in nature, while Skellam a discrete probability distribution. One approach is to appropriately discretize the client updates, e.g., via uniform quantization (which involves scaling the inputs by a factor 8 ~ 2 for some bit-width followed by stochastic rounding" for unbiased estimates), and the server can convert the private aggregate back real numbers at the end. Note that this allows us to re-parameterize the variance of the added Skellam noise as s² μ, giving the following simple corollary based on Cor. 3.6:
Corollary 4.1 (Scaled Skellam Mechanism). With a scaling factor E IR the multi-dimensionn
Skellam Mechanism is (a, RDDP with
ad3 2p
(2a (2a-1)43
1)43
3A,
3A1
E(a) <
+ min
(4.1)
4s2
2s
2sμ
'Example of stochastic rounding: 42.3 has 0.7 and 0.3 probability to be rounded to 42 and 43, respectively. Other discretization schemes possible; do not explore this direction further in this work.
7

---

As increases, the RDP of scaled Skellam rapidly approaches that of Gaussian as the second term above approaches suggesting that under practical regimes with moderate compression bit-width, Skellam should perform competitively compared to Gaussian. Another aspect worth noting is that rounding vector coordinates from reals to integers can inflate the fz-sensitivity 42, and thus more noise is required for the same privacy. To this end, we leverage the conditional rounding procedure introduced in [25] to obtain a bounded norm on the scaled and rounded client vector:
Proposition 4.2 (Norm of stochastically rounded vector [25]. Let I be a stochastic rounding of vector I E I to the integer grid Zt. Then, for 3 E (0, 1), we have
P | S ||=112 + d/4 /2 - ([all2+va/2)) 2 - B.
(4.2)
Conditional rounding is thus defined as retrying the stochastic rounding on I; until | 12 is within the probabilistic bound above (which also gives the inflated sensitivity Σ2). We can then add Skellam noise to the aggregate 2, I; according to 2S before undoing the quantization (unscaling). Note that a larger scaling s before rounding reduces the norm inflation and the extra noise needed (Fig. right).
Skellam for distributed DP with secure aggregation A stronger notion of privacy in FL can be obtained via the distributed DP model [25] that leverages secure aggregation (SecAgg [12]). The fact that the Skellam distribution is closed under summation allows us to easily extend from central DP to distributed DP. Under this model, the client vectors are quantized as in central DP model, but the Skellam noise is now added locally with variance //n.. Then, the noisy client updates are summed via SecAgg (b bits per coordinate for field size 2n) which only reveals the noisy aggregate to the server. While the local noise might be insufficient for local DP guarantees, the aggregated noise at the server provides privacy and utility comparable to the central DP model, thus removing trust away from the central aggregator. Note that the modulo operations introduced by SecAgg does not impact privacy as it can be viewed as a post-proces post-processing of an already differentially private query.
We remark on several properties of the distributed Skellam compared to the distributed discrete Gaussian (DDGauss [25]). (1) DDGauss is not closed under summation, and the divergence between discrete Gaussians can lead to notable privacy degradation in settings such as quantile estimation [6] and federated analyties [42] with sufficiently large number of clients and small local noises (see also the left side of Fig. 2 and Fig. 3). While scaling mitigates this issue, it also requires additional bit-width which makes Skellam attractive under tight communication constraints. (2) Sampling from Skellam only requires sampling from Poisson, for which efficient implementations are widely available in numerical software packages. While efficient discrete Gaussian sampling has also been explored in the sratice-based cryptography community (e.g., [43, 18, 38)), we believe the accessibility of Skellam samplers would help facilitate the deployment of DP to FL settings with mobile and edge devices. See Appendix D for more discussion. (3) In practice where 8 >>>>> 1 (dictated by bit-width b), both Skellam (cf. Cor, 4.1) and DDGauss (with an exponentially small divergence) quickly approaches Gaussian under RDP, and any differences will be negligible (Fig. 3).
5 Empirical Evaluation
In this section, we empirically evaluate the Skellam mechanism on two sets of experiments: distributed mean estimation and federated learning. In both cases, we focus on the distributed DP model, but note that the Skellam mechanism can be easily adapted to the central DP setting as discussed in the earlier section. Unless otherwise stated, we use RDP accounting for all experiments due to the high- eigh-dimensional data and the ease of composition (Section 3). To obtain A₁ for Skellam RDP, we note that A I A2 min(vd, A2) since A S VdA, in general and A S A2 for integers.
Under the distributed DP model, we also introduce a random orthogonal transformation [29, 2, 25] before discretizing and aggregating the client vectors (which can be reverted after the aggregation); this makes the vector coordinates sub-Gaussian and helps spread the magnitudes of the vector coordinates across all dimensions, thus reducing the errors from quantization and potential wrap- around from SecAgg modulo operations. Moreover, by approximating the sub-exponential tail of the Skellam distribution as sub-Gaussian, we can derive a heuristic for choosing s following [25] based on a bound on the variance 5² of the aggregated signal, as 8² < c²n /d + (/(22)) + p. We choose 8 such that 2kō are bounded within the SecAgg field size 29, where k is small constant.
Algorithm 1 summarizes the aggregation procedure for the distributed Skellam mechanism via secure
8

---

Algorithm 1 Aggregation Procedure for the Distributed Skellam Mechanism
Inputs:
Private vector æ; E IRd for each client i; &2 clip norm >> O; Bit-width b; Target central
noise variance μ > O: Number of clients nı Signal bound multiplier 0; Bias [0. 1).
Shared randomness: d x d diagonal matrix D with uniformly random { (- +1) values, where
2 is the nearest power of 2.
Shared scale: Obtain scaling factor such that 2 2kō - 2 +n Procedure CLIENTROCCDDRREES 8, D)
(/(53) +
Clip and scale vector 2,
(1/,c/|/z.112)) 2, and pad to d dimensions with zeros. Random rotation: f; = HaDd; where Ha va Ha is the normalized x d Hadamard matrix. repeat fconditional stochastic rounding]
Stochastically round the coordinates of of ã; to the integer grid to produce ã;
until ||a:112 - min { {sc vd) 2
=²c² d/4+ v 2log(1//3 (sc + vd/2)
Local noising: Sample noise vector y/ E zd where each entry is sampled from Sko,, return 2; 3. y/ under the SecAgg protocol with modulo bit-width b.
Procedure SERVERPROCEDDREES
8, D) {a is the modular sum of under bit-width b)
return F ! D 2, with ē = Σ, I2 E Rd
n= 100, 250 k=2 2
n= 1000,
d= 250, k 2
n= 10000, d= 2000, k =
Skellam (b- 10)
Skellam (b- 100
10"4
Skaillam (b 14)
Skellam (b- 12)
10
Skollam (b 12)
Skeillm (b - 16)
Skcllam (b = 14)
Skellam (b-14)
Skellam (b = 18)
MSE
10:
Skellam (b=16 16)
MSE
Skellam (b-16)
MSE
Skellam (b (020
Analyte Gaussian
10-2
Analytic Gaussian
10-3
Analytic Caussian
10-2
10"4
10-4
Privacy (6 10 5)
Privacy (5
10
Privacy (6 10
Figure 4: Distributed mean estimation with the distributed Skellam mechanism.
aggregation as well as the parameters used for the experiments. In summary, we have an le clip norm 0; per-coordinate bit-width b; target central noise variance μ O: number of clients n; signal bound multiplier& & >> O; and rounding bias 3 E [0, 1). We fix 3 = 11/2 for all experiments. Note that the per-coordinate bit-width b for the aggregated sum as determines the field size of SecAgg. For federated learning, we also consider the number of rounds T and the total number of clients N (thus the uniform sampling ratio q = n/N at every round). Our experiments are implemented in Python, TensorFlow Privacy [32], and TensorFlow Federated [24]. See also Appendix for additional results and more details on the experimental setup.
5.1 Distributed Mean Estimation (DME)
We first consider DME as the generalization of (single round) FI.. We randomly generate n client vectors X = {z,
}= from the d-dimensional & sphere with radius = 10, and compute the
true mean 2 1 Σ. Zz. We then compute the private estimate of T with the distributed Skellam mechanism (Algorithm 1) as T. For a strong baseline, we use the analytic Gaussian mechanism [9] with tight accounting (see also Figure 2). In Figure 4, we plot the MSE as || x1fš/d with 95% confidence interval (small shaded region) over 10 dataset initializations across different values of b, d, and n. Results demonstrate that Skellam can match Gaussian even with n = 10000 clients as long as the bit-width is sufficient. We emphasize that the communication cost b depends logarithmically on n, and to put numbers into context, Google's 's production noxt-word prediction models [23, 39] use 500 and the production DP language model [40] uses 20000.
5.2 Federated Learning
Setup We evaluate on three public federated datasets with real-workd characteristics: Federated EM-
NIST [16]. Shakespeare [31, 14], and Stack Overflow next word prediction (SO-NWP [8]. EMNIST an image classification dataset for hand-written digits and letters; Shakespeare a text dataset for cest-character-rrdiittte based on the works of William Shakespeare; and SO-NWP is a large-scale

---

2200,
100, 7- 1500, 3-3
2 n 100, 7- 1200, k
22, 100. 1600, k
0.8
0.52
Tell Accusey
Teat Accuracy
DoGius (b-12)
DDGauss (b-12)
0.50
DDGsuss (b-12)
Dodiuse (b-14)
0.6
DDGaus (b-14)
DDGGuss (b-16)
DDGsuss (b-14)
DDG (B-16)
0.16
bocaus (b-16)
0.5
Steoliam (2-12)
Skellam (b- 16)
Skeliam (b-14) 14)
Tol
0.48
Skellam 14)
Skellam (D- 16)
Skellam 12)
Stxllan (b-120
Strilan (b-14)
Skrilan (--10)
Gauseian
-6
Gaussian
5
10
15
EMNIST, User-level Privacy
Shakespeare, User-level Privacy e
SO-NWP, User-leval Privacc
Figure 5: Federated learning with the distributed Skellam mechanism. DDGauss: Distributed Discrete Gaussian [25]. Left Middle Right: Test accuracies on EMNIST/ Shakespeare / Stack Overflow NWP across different and b. 6 is set to 1/N, 10 10-0, respectively. For Shakespeare, privacy is reported with a hypothetical population size = 10%.
text dataset for next-word- poodd-peeicction based on user questions/amswers from stackoverflow.com We emphasize that all datasets have natural client heterogeneity that are representative of practical FL problems: the images in EMNIST are grouped the writer of the handwritten digits, the lines in Shakespeare are grouped by the speaking role, and the sentences in SO-NWP are grouped by the corresponding Stack Overflow user. We train a small CNN with model size d < 22 for EMNIST and the recurrent models defined in [41] for Shakespeare and SO-NWP. The hyperparameters for the experiments follow those from [25, 6, 27, 41] and tuning is limited. For EMNIST, we follow [25] and fix 0.03, n 100, T 1500, client learning rate Veelient 0.32, server learning rate 7/ervvr and client batch size m = 20. For Shakespeare, we follow [6] and fix n = 100, T = 1200, T]client 1, {0.25, 0.5]. For SO-NWP, we follow [27] and fix c = 0.3, n = 100, T' = 1600. Melicnt = 0.5, and m = 16, and we sweep Tservvr E {(0.3, } and limit max examples per client to 256. all cases, clients train for epoch on their local datasets, and the client updates are weighted uniformly (as opposed to weighting by number of examples). See Appendix for more results and full details on datasets, models, and hyperparameters.
Thevver 0.32, and m 4, and we sweep
Results Figure 5 summarizes the FL experiments. For EMNIST and Shakespeare, we report the average test accuracy over the last 100 rounds. For SO-NWP, we report the top-1 accuracy (without padding, out-of-vocab, or begining/end-of-senteeee Skellam performs as good as Gaussian despite relying on generic RDP amplification via sampling [51] (ef. Fig. 3) and that Skellam matches DDG consistently under realistic regimes. This bears significant practical relevance given the advantages of Skellam over DDG in real-world deployments.
tokens) on the test set. The results indicate that
Conclusion
We have introduced the multi-dimensional Skellam mechanism for federated learning. We analyzed the Skellam mechanism through the lens of approximate DP, privacy loss distributions, and Rényi divergences, and derived sharp RDP bound that enables Skellam to match Gaussian and discrete Gaussian in practical settings as demonstrated by our large-scale experiments. Since Skellam closed under summation and efficient samplers are widely available, it represents an attractive alternative to distributed discrete Gaussian as it easily extends from the central DP model to the distributed DP model. Being discrete mechanism can also bring potential communication savings over continuous mechanisms and make Skellam less prone to attacks that exploit floating hoating-point arithmetic on digital computers. Some interesting future work includes: (1) our scalar PLD analysis for Skellam suggests room for improvements on our multi-dimensional analysis via a complete PLD characterization, and (2) results on FL may be further improved via a targeted analysis for RDP amplification via sampling akin to [37]. Overall, this work is situated within the active area of private machine learning and aims at making ML more trustworthy, One potential negative impact is that our method could be (deliberately or inadvertently) misused, such as sampling the wrong noise or using minuscule scaling factor, to provide non-existent privacy guarantees for real users' data. We nevertheless believe our results have positive impact as they facilitate the deployment of differential privacy in practice.
10

---

Funding Transparency Statement
The authors were employed at and directly supported by Google. No third party funding was received by any of the authors to pursue this work.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMa- han. epSGD: Communication-efficae and differentially-prinn private distributed sgd. In Advances Neural 2018.
Information Processing Systems, pages
[3] Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh. Federated learning via posterior averaging: A new perspective and practical algorithms. In ICLR, 2021.
[4] Martin R. Albrecht and Michael Walter. dgs, Discrete Gaussians over the Integers. Available at https: //bitbuckett / 2018.
[5] Donald E Amos. Computation of modified bessel functions and their ratios. Mathematics of Computation, 28( 28(125):239 251, 1974.
[6] Galen Andrew, Om Thakkar, H Brendan McMahan, and Swaroop Ramaswamy. Differentially private lcarning with adaptive clipping. arXiv preprint arxivv/905.05: 03877, 2019.
[7] S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar. A better bound gives hundred rounds: Enhanced privacy guarantees f-divergences. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 920-925, 2020.
[8] The TensorFlow Federated Authors. Tensorflow federated stack overflow dataset. 2019.
[9] Borja Balle and Yu-X Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394-403. PMI.R 2018.
[10] Racf Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Anmual Symposium on Foundations of Computer Science, pages 464 473. IEEE, 2014.
[1I] James Bell, K. A. Bonawitz. Adrià Gascón. Tancrède Lepoint, and Mariana Raykova. Secure single- server aggregation with (paat)log overhead. Cryptology ePrint Archive, Report 2020/704, 2020. attps://eprint.. iacr. org/ 2020/4000/704
[12] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for triacc-preeerving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175 1191, 2017.
[13] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-655 Springer, 2016.
[14] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu. Tian Li. Jakub Konečný, H Brendan McMa- han, Virginia Smith. and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 1812.01077, 2018.
[15] Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. In NeurIPS, 2020.
[16] Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist handwritten letters. 2017 International Joint Conference on Neural Vetworks pages 2921-2926. IEEE, 2017.
[17] Google Differential Privacy Team. Privacy loss distributions. differential wawaaaa--ivaaaacbb/aeeeeeee 2020.
https://gtthub.com//ee http://///..tttteeocc/ct///tttta Distribbbtttitiitiiiins pdf..

---

[18] Nagarjun C Dwarakanath and Steven D Galbraith. Sampling from discrete gaussians for lattice-based cryptography on constrained device. Applicable Algebra Engineering. Communication and Computing. 15(3):159-180, 2014.
[19] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry. Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503. Springer, 2006.
[20] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 365-284. Springer. 2006.
[21] Cynthia Dwork and Guy Rothblum. Concentrated differential privacy. arXiv preprint arXiv: 2016.
[22] Cynthia Dwork, Guy Rothblum, and Salil Vadhan. Boosting and differential privacy. 2010 JEEE S Annual Symposium on Foundations of Computer Science, pages 51 51-60. IEEE, 2010.
[23] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein. Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: 1a0118811100044 2018.
[24] Alex Ingerman and Krzys Ostrowski. Introducing tensorflow federated, 2019.
[25] Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning. PMLR, 2021.
[26] Peter Kairouz, Brendan McMahan, et al. Advances and open problems federated learning. arXiv preprint arXiv: arXiv: 1912.4977 2019.
[27] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling arXiv preprint arXiv:2 103.00.0,3 2021.
[28] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy, In International conference machine learning, pages 1376-1385. PMLR, 2015.
[29] Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492,, 2016.
[30] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft.
In Intermational Conference Artificial Intelligence and Statistics, pages 2560-2569, PMLR, 2020.
[31] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ffiidee learning of deep networks from decentralized data. In Artificial Intelligence and Statisticx, pages 1273-1282, 2017.
[32] H Brendan Mchannn, Galen Andrew, Ulfar Frlingsson, Steve Chien, Ilya Mironov, Nicolas Papernot, and Peter Kairouz. A general approach to adding diffcrential privacy to iterative training procedures. arXiv preprint ar
10, 2018.
[33] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In ICLR, 2018
[34] Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differ- ential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 247-264, 2018
[35] Ilya Mironov, On significance of the least significant hits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security, pages 650-661, 2012.
[36] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEF, 2017.
[37] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi diffcrential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: /908. 10530, 2019.
[38] Thomas Prest, Thomas Ricosset, and Mélissa Rossi. Simple. fast and constant constant-time gaussian sampling over the integers for falcon. In Second PQC Standardization Conference, 2019.
12

---

[39] Swaroop Ramaswamy, Rajiv Mathews. Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction in mobile keyboard. arXiv preprint (9XX::9906604329, 2019.
[40] Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H Brendan McMahan, and Françoise Beaufays. Training production language models without memorizing user data. arXiv preprint arXiv:2009. 10031, 2020.
[41] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295 2020.
[42] Google Research. Federated analyties: Collaborative data science without data collection, May 2020.
[43] Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. High precision discrete gaussian sampling on fpgas. International Conference on Selected Areas Cryptography, pages 381-401. Springer, 2013.
[44] Diego Ruiz-Antolin and Javier Segura. A new type of sharp bounds ratios of modified bessel functions. Journal of Mathematical Analysis and Applications, 443(2):1232-1246, 2016.
[45] Aaron Schein, Zhiwei Steven Wu, Alexandra Schofield, Mingyuan Zhou, Hanna Wallach. Locally private bayesian inference for count models. In International Conference on Machine Learning, pages PMLR, 2019.
[46] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages IEEE, 2013.
[47] VR Thirwvenkatachar and TS Nanjundiah. Inequalities concerning bessel functions and orthogonal polynomials. In Proceedings of the Indian Academy of Sciences- A, volume 33, page 373. Springer, 1951.
[48] Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). arXiv preprint arXiv:2011.1166. 2020.
[49] Filipp Valovich and Francesco Alda. Computational differential privacy from lattice-based cryptography. In International Conference on Cumber-Theoretie Methods Cryptology, pages 121 221-11.. Springer, 2017.
[50] Hongxu Yin, Arun Mallya, Arash Vahdat. Jose M Alvarez, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. arXiv preprint arXiv:2104.077 075566 2021.
[51] Yuqing Zhu and Yu-Xiang Wang. Poission subsampled rényi differential privacy. In International Conference on Machine Learning, pages 7634-7642. PMLR, 2019.
13


Reviews:
[{"review_id": "vGfoFDfo96c", "reviewer": "Reviewer_P222", "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. ", "questions": "", "limitations": "", "rating": 7, "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": "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. \n\n\nStrengths: \nThe 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.\n\nThe 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. \n\nWeakness: \nIt’s better to have a comparison of noise sampling time with discrete Gaussian mechanism to further show the advantages", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "hcsUZoKjmA4", "reviewer": "Reviewer_WiXo", "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.\n\nContributions 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "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.\n\nQuality:\nProving 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.\n\nClarity:\nThe content arrangement is clear and well organized.\n\nSignificance:\nThe 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.\n-----------------------------------\n\nAfter reading the authors rebuttal I raise my score. I think the authors provide a good feedback to solve my concerns. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nMoreover, 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8h"}, "extra_text": {}}, {"review_id": "JorHy8WEF1w", "reviewer": "Reviewer_p2AR", "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.\nAs 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.\n\n***\nAfter rebuttal. I've read all the reviews and replies. Raising my score appropriately.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "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. \n\nAnother question, why does the PLD section exist if you have at your disposal Theorem 3.5? \n\nMinor:\nLine 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?\nLine 106, typo. Z should be X.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7NnkoNvP-Gn", "reviewer": "Reviewer_SqyM", "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.\n", "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": "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.  \n\nHowever, 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.  \n\nMy 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.  \n\nMinor Comments: \n- 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.\n- “regarding regarding” in line 178.\n\n\n########### \nUpdate: 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.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "This paper deals with rigorous notions of privacy.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}]

Author rebuttal:

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)