The Skellam Mechanism for Differentially Private Federated Learning
Year: 2021

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.

heading: 1 Introduction
text: The Gaussian mechanism is the workhorse for a multitude of 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 in practice. For example, it cannot be exactly represented on finite computers, making it prone to numerical errors that can break its privacy guarantees [35]. Moreover, it cannot be used in distributed learning settings with cryptographic multi-party computation primitives involving modular arithmetic, such as secure aggregation [12, 11]. To address these shortcomings, the binomial and (distributed) discrete Gaussian mechanisms were recently introduced [19, 2, 15, 25]. 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 not closed under summation (i.e. sum of discrete Gaussians is not a 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 it in production settings (naïve implementations may lead to catastrophic privacy errors).
Our contributions To overcome these limitations, we introduce and analyze the multi-dimensional 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 can be sampled from easily – efficient Poisson samplers are widely available in numerical software packages. Being discrete in nature also
⇤Work done while at Google Research. §Alphabetical authorship.
35th Conference on Neural Information Processing Systems (NeurIPS 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 `1 sensitivity 1 and `2 sensitivity 2, the Skellam mechanism with variance µ achieves (↵, "(↵)) Rényi differential privacy (RDP) [36] for "(↵)  ↵ 2 2µ +min ⇣ (2↵ 1) 2+6 1 4µ2 , 3 1 2µ ⌘ (see Theorem 3.5). This implies that the RDP guarantees are at
most 1 +O (1/µ) times worse than those of the Gaussian mechanism.
To analyze the performance of the Skellam mechanism in practice, we consider a 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 a 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 on 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 mechanism [37]. Our method is implemented in TensorFlow Privacy [32] and TensorFlow Federated [24] and will be open-sourced.2 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 differential 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 accuracy-privacy trade-offs as demonstrated in Fig. 1. Moreover, we show in Section 3.1 that extending the direct privacy analysis to the multi-dimensional setting is 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 or zero-concentrated DP [36, 13] and has 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, 38]). The discrete Gaussian is also not closed under summation and the divergence can be large in highly distributed 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.

heading: 2 Preliminaries
text: We begin by providing a formal definition for (", )-differential privacy (DP) [20]. Definition 2.1 (Differential Privacy). For ", 0, a randomized mechanism M satisfies (", )-DP if for all neighboring datasets D,D0 and all S in the range of M , we have that
P (M(D) 2 S)  e"P (M(D0) 2 S) + , where D and D0 are neighboring pairs if they can be obtained from each other by adding or removing all the records that belong to a particular user.
In our experiments we consider user-level differential privacy – i.e., D and D0 are neighboring pairs
2https://github.com/google-research/federated/tree/master/distributed_dp
if one of them can be obtained from the other by adding or removing all the records associated with a single user [33]. This is stronger than the commonly-used notion of item level privacy where, if a user contributes multiple records, only the addition or removal of one record is protected.
We also make use of Rényi differential privacy (RDP) [36] which allows for tight privacy accounting. Definition 2.2 (Rényi Differential Privacy). A mechanism M satisfies (↵, ")-RDP if for any two neighboring datasets D,D0, we have that D↵(M(D),M(D0))  " where D↵(P,Q) is the Rényi divergence between P and Q and is given by
D↵(P,Q) , 1 ↵ 1 log ✓ Ex⇠Q ✓ P (x) Q(x) ◆↵ ◆ = 1 ↵ 1 log Ex⇠P "✓ P (x) Q(x) ◆↵ 1#! .
A closely related privacy notion is zero-concentrated DP (zCDP) [21, 13]. In fact, 12" 2-zCDP is equivalent to simultaneously satisfying an infinite family of RDP guarantees, namely (↵, 12" 2↵)- Rényi differential privacy for all ↵ 2 (1,1). The following conversion lemma from [13, 15, 7] relates RDP to (", )-DP. Lemma 2.3. If M satisfies (↵, ")-RDP, then, for any > 0, M satisfies ("DP( ), )-DP, where
"DP( ) = inf ↵>1
"+ log(1/↵ )
↵ 1 + log(1 1/↵).
For any query function f , we define the p sensitivity as maxD,D0 kf(D) f(D0)kp, where D and D0 are neighboring pairs differing by adding or removing all the records from a 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 an integer-valued query f(D) 2 Zd and noise variance µ, the Discrete Gaussian (DGaussian) Mechanism is given by
f(D) + Z, where Z ⇠ NZ(0, µ),
and NZ(0, µ) denotes the discrete Gaussian distribution defined in Equation (1) of [15]. The discrete Gaussian mechanism achieves (↵, ↵ 2 2
2µ )-Rényi DP.

heading: 3 The Skellam Mechanism
text: 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 Sk ,µ over Zd with mean 2 Zd and variance µ is given with each coordinate Xi distributed independently as
Xi ⇠ Sk i,µ with P (Xi = k) = e µIk i(µ),
for k 2 Z. Here, I⌫(x) is the modified Bessel function of the first kind. A key property of Skellam random variables which motivates their use in DP is that they are closed under summation, i.e. let X1 ⇠ Sk 1,µ1 and X2 ⇠ Sk 2,µ2 then X1 + X2 ⇠ Sk 1+ 2,µ1+µ2 . This follows from the fact that a Skellam random variable X can be obtained by taking the difference between two independent Poisson random variables with means µ.3 We are now ready to introduce the Skellam Mechanism. Definition 3.2 (The Skellam Mechanism). Given an integer-valued query f(D) 2 Zd, we define the Skellam Mechanism as
Sk0,µ(f(D)) = f(D) + Z, where Z ⇠ Sk0,µ,
and the total `2 error of the mechanism is bounded by E ⇥ k Sk0,µ(f(D)) f(D)k22 ⇤  dµ.
3We 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) Tight 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 in [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 106). Using composition theorems lead to poor accuracy-privacy trade-offs and a direct extension of approximate DP guarantee [49] for the multi-dimensional case leads to a strong dependence on `1 sensitivity which is prohibitively large in high dimensions. (3) Data discretization: The gradients are naturally continuous vectors but we 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.

heading: 3.1 Tight Numerical Accounting via Privacy Loss Distributions
text: We begin by defining the notion of privacy loss distributions (PLDs).
Definition 3.3 (Privacy Loss Distribution). For a multi-dimensional discrete privacy mechanism M and neighboring datasets D,D0, for any x 2 Zd, we define f(x) = log ⇣
P (M(D)=x) P (M(D0)=x)
⌘ . The privacy loss ran-
dom variable of M at (D,D0) is ZD,D0 = f(M(D)) [22]. The privacy loss distribution (PLD) of M , denoted by PLDD,D0 , is the distribution of ZD,D0 .
The PLD of a mechanism M can be used to characterize its (", )-DP guarantees. Lemma 3.4. A mechanism M is (", )-DP if and only if EZ⇠PLDD,D0 ⇥ 1 e" Z ⇤ +
for all neighboring datasets D,D0 where [x]+ = max(0, x).
When a mechanism M is applied T times on a dataset, the overall PLD of the composed mechanism at (D,D0) is the T -fold convolution of PLDD,D0 [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, a direct calculation shows that with Xi are i.i.d. according to Sk0,µ,
ZD,D0 = dX
i=1
log
✓ IXi f(D)i(µ)
IXi f(D0)i(µ)
◆ .
When d = 1, it suffices to look at Z = log(IX (µ)/IX(µ)), where = maxD,D0 |f(D) f(D0)| and X ⇠ Sk0,µ. Since X has a discrete and symmetric probability distribution and the log function is monotonic, the distribution of Z can be easily characterized. This gives us a 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. 1 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 ZD,D0’s that need to be considered, even when the `2 sensitivity of f(D) is bounded. The discrete Gaussian mechanism faces a similar issue (see Theorem 15 of [15]). To provide a tight privacy analysis in the multi-dimensional case, we prove a bound on the RDP guarantees of the Skellam mechanism in the next subsection. Fig. 1 and 2 show that our bound is tight and the competitiveness of the Skellam mechanism in high dimensions.

heading: 3.2 Tight Accounting via Rényi Differential Privacy
text: 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 ↵ 2 Z, ↵ > 1 and sensitivity 2 Z, the Skellam Mechanism is (↵, ")-RDP with
"(↵)  ↵ 2
2µ +min
✓ (2↵ 1) 2 + 6
4µ2 , 3 2µ
◆ , (3.1)
To remind the reader in comparison, the Gaussian mechanism is (↵, ")-RDP with "(↵) = ↵ 2
2µ . The bound we provide is at most 1 +O(1/µ) worse than the bound for the Gaussian, which is negligible for all practical choices of µ, especially as the privacy requirements increase.4 Next we show a simple corollary which follows via the independent composition of RDP across dimensions. Corollary 3.6. The multi-dimensional Skellam Mechanism is (↵, ")-RDP with
"(↵)  ↵ 2 2
2µ +min
✓ (2↵ 1) 22 + 6 1
4µ2 , 3 1 2µ
◆ . (3.2)
where 1 and 2 are the `1 and `2 sensitivities respectively.

heading: 3.2.1 Proof Overview for Theorem 3.5
text: In this subsection, we provide the proof of 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 a macroscopic level, our proof structure mimics the RDP proof for the Gaussian mechanism [36], and the main object of our interest is to bound the following quantity, defined for any X, ,↵:
X,↵, (µ) , log
IX (µ)
IX ↵ (µ)
✓ IX (µ)
IX(µ)
◆↵ 1! . (3.3)
The following lemma states our main bound on this quantity. Lemma 3.7. For any X,↵ 2 N, with ↵ > 1 and 2 Z, we have that for all µ 0
X,↵, (µ)  ↵(↵ 1) 2
2µ +min
✓ (2↵ 1)(↵ 1) 2
4µ2 + 3(↵ 1)| | 2µ2 , 3(↵ 1)| | 2µ
◆ .
Note that in contrast if we consider the analogous notion of for the Gaussian mechanism (replacing IX(µ) with the Gaussian density e X 2/2µ), we readily get the bound ↵(↵ 1) 2
2µ , which is the same as 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 , ↵ 1,
D↵ (Sk ,µ, Sk0,µ) = 1 ↵ 1 log 1X
X= 1 e µIX (µ)
✓ IX (µ)
IX(µ)
◆↵ 1!
Now consider the following calculations on the log term:
log
1X
X= 1
IX (µ)
eµ
✓ IX (µ)
IX(µ)
◆↵ 1! = log
1X
X= 1
IX ↵ (µ)
eµ e X,↵, (µ)
!
 log 1X
X= 1 e µIX ↵ (µ)
! +max
X2Z X,↵, (µ)
 ↵(↵ 1) 2
2µ +min
✓ (2↵ 1)(↵ 1) 2
4µ2 + 3(↵ 1)| | 2µ2 , 3(↵ 1)| | 2µ
◆ ,
where the inequality follows from Lemma 3.7.
4The restriction that ↵ needs to be an integer is a technical one owing to known bounds on Bessel functions. In practice as we show, this restriction has a negligible effect.
We now provide an overview for the proof of Lemma 3.7 highlighting the crux of the argument. As a first step we collect some known facts regarding Bessel functions. It is known that for x 0 and ⌫ 2 Z, ⌫ 0, I⌫(x) is a decreasing function in ⌫, I ⌫(x) = I⌫(x) and I⌫ 1(µ)I⌫(x) is an increasing function in ⌫ [47]. A succession of works consider bounding the ratio of successive Bessel functions I⌫ 1(x)/I⌫(x), which is 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]. Lemma 3.8. For any ⌫ 1/2, x 0 define the following function we have that
arcsinh( 0(⌫, x))  log(I⌫ 1(x)) log(I⌫(x))  arcsinh( 2(⌫, x))
where ↵(⌫, x) is defined as ↵(⌫, x) , ⌫ 1/2x + ⌫+(↵ 1)/2 2x p (⌫+(↵ 1)/2)2+x2 .
Standard bounds such as those appearing in [5, 49] lead to the following conclusion:
arcsinh ((⌫ 1/2)/x)  log(I⌫ 1(x)) log(I⌫(x))  arcsinh (⌫/x)) .
While the above bound is significantly easier to work with, it leads to an RDP guarantee of Gaussian RDP + O( µ ). In high dimensions this manifests as O( 1 µ ) and overall leads to a constant multiplicative factor over the Gaussian. On the other hand we prove a Gaussian RDP + oµ(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 ↵ , 0. Replacing Y = X ↵ we get that
X,↵, (µ) = log
IY+(↵ 1) (µ)
IY (µ)
✓ IY+(↵ 1) (µ)
IY+↵ (µ)
◆↵ 1!
= ↵ 2X
j=0
0 @ Y+j + X
i=Y+j +1
✓ log ✓ Ii 1+(↵ 1 j)(µ)
Ii+(↵ 1 j) (µ)
◆ log ✓ Ii 1(µ)
Ii(µ)
◆◆1
A
 ↵ 2X
j=0
0 @ Y+j + X
i=Y+j +1
2(i+ (↵ 1 j) , µ) 0(i, µ)
1
A
 ↵(↵ 1) 2
2µ +min
✓ ↵(↵ 1) 2 + 2(↵ 1)
4µ2 , (↵ 1) 2µ
◆ ,
where the first inequality follows from Lemma 3.8 and the fact that for all 0  x  y, arcsinh(y) arcsinh(x)  y x and the second inequality follows from Lemma A.1 (provided in the appendix):
2(⌫1, x) 0(⌫2, x)  ⌫1 ⌫2
x +
1
2x min
✓ ⌫1 ⌫2 + 1
x , 1
◆ .

heading: 4 Applying the Skellam Mechanism to Federated Learning
text: With a 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 n clients each holding a vector xi in Rd such that for all i, the vector norm is bounded as kxik2  c for some c 0. We denote the set of vectors as X = {xi}ni=1, and the aim is for each client to communicate the vectors xi to a central server which then aggregates them as bx = 1n P i xi for an external analyst. In federated learning, the client vectors xi are the model gradients or model deltas (typically d 106) after training on the clients’ local datasets, and this procedure can be repeated for many rounds (T > 1000). A large d and T thus necessitate accounting methods that provide tight privacy compositions for high-dimensional queries.
We are primarily concerned with three metrics for this procedure and their trade-offs: (1) Privacy: the mean bx should be differentially private with a reasonably small (", ); (2) Error: we wish to
minimize the expected `2 error; and (3) Communication: we wish to 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 xi; 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 bx before releasing it to the external analyst. One important consideration is that the model updates in FL are continuous in nature, while Skellam is 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 s ⇠ 2b for some bit-width b followed by stochastic rounding5 for unbiased estimates), and the server can convert the private aggregate back to real numbers at the end. Note that this allows us to re-parameterize the variance of the added Skellam noise as s2µ, giving the following simple corollary based on Cor. 3.6:
Corollary 4.1 (Scaled Skellam Mechanism). With a scaling factor s 2 R, the multi-dimensional Skellam Mechanism is (↵, ")-RDP with
"(↵)  ↵ 2 2
2µ +min
✓ (2↵ 1) 22
4s2µ2 + 3 1 2s3µ2 , 3 1 2sµ
◆ . (4.1)
5Example of stochastic rounding: 42.3 has 0.7 and 0.3 probability to be rounded to 42 and 43, respectively. Other discretization schemes are possible; we do not explore this direction further in this work.
As s increases, the RDP of scaled Skellam rapidly approaches that of Gaussian as the second term above approaches 0, 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 `2-sensitivity 2, 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 x̃ be a stochastic rounding of vector x 2 Rd to the integer grid Zd. Then, for 2 (0, 1), we have
P h kx̃k22  kxk22 + d/4 + p 2 log(1/ ) · ⇣ kxk2 + p d/2 ⌘i 1 . (4.2)
Conditional rounding is thus defined as retrying the stochastic rounding on xi until kx̃ik22 is within the probabilistic bound above (which also gives the inflated sensitivity ̃2). We can then add Skellam noise to the aggregate P i x̃i according to ̃2 before undoing the quantization (unscaling). Note that a larger scaling s before rounding reduces the norm inflation and the extra noise needed (Fig. 3 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 2b) 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-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 analytics [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 lattice-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 s 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).

heading: 5 Empirical Evaluation
text: 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-dimensional data and the ease of composition (Section 3). To obtain 1 for Skellam RDP, we note that 1  2 ·min( p d, 2) since 1  p d 2 in general and 1  22 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 wraparound 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 ̃2 of the aggregated signal, as ̃2  c2n2/d+ n/(4s2) + µ. We choose s such that 2k̃ are bounded within the SecAgg field size 2b, where k is a small constant.
Algorithm 1 summarizes the aggregation procedure for the distributed Skellam mechanism via secure
Algorithm 1 Aggregation Procedure for the Distributed Skellam Mechanism Inputs: Private vector xi 2 Rd̄ for each client i; `2 clip norm c > 0; Bit-width b; Target central noise variance µ > 0; Number of clients n; Signal bound multiplier k > 0; Bias 2 [0, 1). Shared randomness: d⇥ d diagonal matrix D with uniformly random { 1,+1} values, where d d̄ is the nearest power of 2. Shared scale: Obtain scaling factor s such that 2b = 2k̃ = 2k p c2n2/d+ n/(4s2) + µ.
Procedure CLIENTPROCEDURE(xi, s,D) Clip and scale vector x̂i = s ·min(1, c/kxik2) · xi, and pad to d̃ dimensions with zeros. Random rotation: x̌i = H̃dDx̂i where H̃d = 1pdHd is the normalized d⇥ d Hadamard matrix. repeat {conditional stochastic rounding}
Stochastically round the coordinates of of x̌i to the integer grid to produce x̃i
until kx̃ik22  min ⇢⇣ sc+ p d ⌘2 , s2c2 + d/4 + p 2 log(1/ ) · ⇣ sc+ p d/2 ⌘ .
aggregation as well as the parameters used for the experiments. In summary, we have an `2 clip norm c > 0; per-coordinate bit-width b; target central noise variance µ > 0; number of clients n; signal bound multiplier k > 0; and rounding bias 2 [0, 1). We fix = e 1/2 for all experiments. Note that the per-coordinate bit-width b is for the aggregated sum as it 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.

heading: 5.1 Distributed Mean Estimation (DME)
text: We first consider DME as the generalization of (single round) FL. We randomly generate n client vectors X = {xi}ni=1 from the d-dimensional `2 sphere with radius c = 10, and compute the true mean bx = 1n Pn i xi. We then compute the private estimate of bx with the distributed Skellam mechanism (Algorithm 1) as x̄. 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 kbx x̄k22/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 production next-word prediction models [23, 39] use n  500 and the production DP language model [40] uses n = 20000.

heading: 5.2 Federated Learning
text: Setup We evaluate on three public federated datasets with real-world characteristics: Federated EMNIST [16], Shakespeare [31, 14], and Stack Overflow next word prediction (SO-NWP [8]). EMNIST is an image classification dataset for hand-written digits and letters; Shakespeare is a text dataset for next-character-prediction based on the works of William Shakespeare; and SO-NWP is a large-scale
text dataset for next-word-prediction based on user questions/answers 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̄ < 220 for EMNIST and use 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 c = 0.03, n = 100, T = 1500, client learning rate ⌘client = 0.32, server learning rate ⌘server = 1, and client batch size m = 20. For Shakespeare, we follow [6] and fix n = 100, T = 1200, ⌘client = 1, ⌘server = 0.32, and m = 4, and we sweep c 2 {0.25, 0.5}. For SO-NWP, we follow [27] and fix c = 0.3, n = 100, T = 1600, ⌘client = 0.5, and m = 16, and we sweep ⌘server 2 {0.3, 1} and limit max examples per client to 256. In all cases, clients train for 1 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.
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-sentence tokens) on the test set. The results indicate that Skellam performs as good as Gaussian despite relying on generic RDP amplification via sampling [51] (cf. 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.

heading: 6 Conclusion
text: 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 a sharp RDP bound that enables Skellam to match Gaussian and discrete Gaussian in practical settings as demonstrated by our large-scale experiments. Since Skellam is 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 a discrete mechanism can also bring potential communication savings over continuous mechanisms and make Skellam less prone to attacks that exploit floating-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) our 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 a 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.
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.

Review summaries:
This paper introduced and analyzed the multi-dimensional Skellam mechanism which is a discrete differential privacy mechanism based on the difference of two independent Poisson random variables to the federated learning setting. This paper also studies the experiment performance of such mechanism compared with existing continuous gaussian mechanism.  Contributions are, 1) analyzed the mechanism differentially private behavior in multi-dimensional federated learning setting. 2) experimented its performance and analyzed why this mechanism is suitable for real federated learning practice. 

The paper introduces the multi-dimensional Skellam (difference of two Poisson random variables) mechanism for differential privacy. They show that the Skellam Mechanism is Renyi DP (RDP) with slightly worse guarantee than than Gaussian Mechanism. They also compare the privacy loss over several rounds against Gaussian and Discrete Gaussian using Renyi DP, Advanced Composition and the Privacy Loss Distribution. Results show that Skellam performs similarly to Discrete Gaussian and Gaussian when using RDP and PLD bounds. As an application they consider using the Skellam Mechanism for distributed mean estimation and two Federated learning tasks (EMNIST and SO-NWP). Experiments show that they can match the performance of continuous Gaussian.  *** After rebuttal. I've read all the reviews and replies. Raising my score appropriately.

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. 

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.