Year: 2021

Abstract:
Deep neural networks have strong capabilities of memorizing the underlying training data; on the flip side, unintended data memorization can be a serious privacy concern. An effective and rigorous approach to addressing this problem is to train models with differential privacy (DP), which provides information-theoretic privacy guarantees by injecting random noise to the gradients. This paper focuses on the scenario where sensitive data are distributed among individual participants, who jointly train a model through federated learning, using both secure multiparty computation (MPC) to ensure the confidentiality of individual gradients, and differential privacy to avoid data leakage in the resulting model. A major challenge in this setting is that common mechanisms for enforcing DP in deep learning, which inject real-valued noise, are fundamentally incompatible with MPC, which exchanges finite-field integers among the participants. Consequently, most existing DP mechanisms require rather high noise levels, leading to poor model utility. Motivated by this, we design and develop distributed Skellam mechanism (DSM), a novel solution for enforcing differential privacy on models built through an MPC-based federated learning process. Compared to existing approaches, DSM has the advantage that its privacy guarantee is independent of the dimensionality of the gradients; further, DSM allows tight privacy accounting due to the nice composition and sub-sampling properties of the Skellam distribution, which are key to accurate deep learning with DP. The theoretical analysis of DSM is highly non-trivial, especially considering (i) the complicated math of differentially private deep learning in general and (ii) the fact that the Skellam distribution is rather complex, and to our knowledge, has not been applied to an iterative and samplingbased process, i.e., stochastic gradient descent. Meanwhile, through extensive experiments on various practical settings, we demonstrate that DSM consistently outperforms existing solutions in terms of model utility by a large margin.

heading: 1 INTRODUCTION
text: Deep neural networks, especially large-scale ones such as GPT-3 (Brown et al., 2020), are known for their excellent memorization capabilities (Song et al., 2017; Feldman, 2020; Zhang et al., 2021). However, it is rather difficult to control what exactly the neural net memorizes, and unintended data memorization can be a serious concern when the underlying training data contains sensitive information (Carlini et al., 2019). For instance, consider a bank that trains a GPT-like language model on call center transcripts. Due to data memorization, it is possible to extract sensitive information by letting the model auto-complete a prefix, e.g., “my account number is: ”. Clearly, if such a model (or its API) is ever exposed to the adversary, it becomes a ligation machine as attackers can attempt with various prefixes to extract sensitive data, and subsequently sue the bank for privacy violations. Shokri et al. (2017) report that simple and intuitive measures often fail to provide sufficient protection, and the only way found to completely address the issue is to train the model with the rigorous guarantees of differential privacy (DP) (Dwork et al., 2006).
This paper focuses on the scenario that multiple individual participants jointly train a machine learning model using federated learning (FL) (McMahan et al., 2017) through distributed stochastic gradient descent (SGD) (McDonald et al., 2010; Dean et al., 2012; Coates et al., 2013; Abadi et al.,
2016a). Specifically, in every iteration, each individual computes the gradients with respect to the current model weights based on her own data; then, gradients from all participants are aggregated to update the model. Note that the gradients from each individual may reveal sensitive information about her private dataset (Shokri et al., 2017; Pyrgelis et al., 2018; Yeom et al., 2018; Nasr et al., 2019; Melis et al., 2019). A common approach to addressing this problem is by employing a secure multiparty computation (MPC) protocol (Yao, 1986; Chaum et al., 1987; Gennaro et al., 2002; Ishai et al., 2010; Beimel et al., 2014; Cramer et al., 2015; Ananth et al., 2018), which computes the aggregate gradients while preserving the confidentiality of the gradients from each individual participant. One advantage of MPC is that it is a decentralized approach that does not require a trusted third party, which can be difficult to establish in some applications, e.g., in finance and healthcare.
Note that although MPC protects individuals’ privacy in the gradient update process by concealing the gradient values of each participant, it does not provide any protection against data extraction attacks caused by unintended data memorization (Dwork et al., 2015; Song & Shmatikov, 2019; Melis et al., 2019; Song & Shmatikov, 2020). As mentioned earlier, an effective methodology to defend against such attacks is to perturb the gradients to satisfy differential privacy (Shokri et al., 2017). Since there is no trusted third-party in our setting, such gradient perturbations need to done in a decentralized fashion, i.e., each FL participant adds noise to her own gradients, such that the aggregated gradients over all participants satisfies DP, which is referred to as distributed differential privacy (Goryczka et al., 2013; Kairouz et al., 2021).
Although gradient perturbation under DP has been studied in previous work (notably, DPSGD (Abadi et al., 2016b)), it is far from trivial to adapt centralized DP solutions to our setting, due to a fundamental problem: that the MPC protocol requires gradients to be represented as integers (more precisely, finite field elements (Paillier, 1999; Bonawitz et al., 2017; Bell et al., 2020)). DPSGD, on the other hand, injects real-valued Gaussian noise to the gradients. Although real numbers can be quantized and (approximately) represented using large integers, the quantized random noise have rather different mathematical properties, which render a tight privacy cost analysis much more difficult, especially under the decentralized setting of FL. For instance, a nice property of the continuous Gaussian distribution is that summing up n continuous noise values following i.i.d. unit-variance Gaussian distribution results in an amplified continuous Gaussian noise of variance n. This property does not hold, however, if the Gaussian noise values are first quantized before aggregated. Further, the privacy analysis (specifically, the moment accountant analysis technique) of the DPSGD algorithm also replies on other important properties of the continuous Gaussian distribution, which do not hold when the noise is quantized. Hence, DPSGD does not directly apply to our setting. This issue has been neglected by many existing distributed DP solutions, e.g., (Goryczka et al., 2013; Valovich & Aldà, 2017; Truex et al., 2019).
Existing Solutions. Agarwal et al. (2018) propose cpSGD, which injects binomial noise (i.e., the sum of multiple binary values drawn from independent Bernoulli trials) to the discretized gradients at each participant of FL, to satisfy DP. Similar to Gaussian noise in the continuous domain, binomial noise can also be aggregated, i.e., the sum of multiple i.i.d. binomial noise values also follows a binomial distribution. However, compared to the continuous Gaussian distribution, existing theoretical tools for analyzing binomial noise aggregation leads to rather loose bounds; further, the bionomial distribution is incompatible with the moment accountant analysis technique in DPSGD (Kairouz et al., 2021). Consequently, cpSGD leads to poor utility, as demonstrated in Section 4.
Recently, the distributed discrete Gaussian mechanism (DDG) (Kairouz et al., 2021) addresses the above issues by injecting independent discrete Gaussian noise (Canonne et al., 2020) to the gradients at each participant. Similar to the binomial distribution, the discrete Gaussian distribution is also defined over an integer domain; meanwhile, DDG is fully compatible with the moment accountant analysis technique in DP-SGD, and, thus, enjoys the tight privacy cost analysis. However, the discrete Gaussian distribution is not aggregatable, meaning that the sum of noise drawn from multiple i.i.d. discrete Gaussian distributions does not follow another discrete Guassian distribution, which renders analysis difficult under in the decentralized setting of FL, and leads to looser bounds in the privacy analysis. Further, the privacy guarantee of the aggregated noise in DDG degrades linearly with the dimensionality d of the gradients, leading to poor scalablity to large neural networks.
Our contribution. In this work, we propose a new mechanism for enforcing distributed differential privacy for federated learning: the distributed Skellam mechanism (DSM), which injects random noise drawn from the symmetric Skellam distribution. Although the Skellam distribution has been
used before in the DP literature (Valovich & Aldà, 2017), the privacy analysis therein does not cover the decentralized setting of FL, or the iterative, sampling-based SGD algorithm, both of which require highly non-trivial mathematical analysis.
Specifically, we prove that DSM satisfies both Rényi-DP and ( , δ)-DP, defined in Section 2. Similar to our competitor DDG described above, DSM is compatible with the DPSGD framework and its moment accountant analysis technique, leading to tight bounds on the privacy loss analysis. Meanwhile, unlike DDG, the privacy guarantees of DSM are independent of the dimensionality of the gradients, which scales well to large models. Further, similar to the continuous Gaussian distribution (and unlike the discrete Gaussian distribution in DDG), i.i.d. Skellam noise values can be aggregated to form an amplified noise that still follows the Skellam distribution, which leads to clean and elegant proofs in the decentralized setting of FL, and tight bounds in the privacy analysis.
We apply DSM to federated learning with distributed SGD, with quantized gradients, e.g., as required by the MPC protocol, and present the complete training algorithm. Extensive experiments using benchmark datasets show that our solution leads to consistent and significant utility gains over its competitors, under a variety of settings with different privacy and communication constraints.

heading: 2 PRELIMINARIES
text: A random variable Y follows a Poisson distribution of parameter λ if its probability distribution is Pr[Y = k] = exp(−λ)λ k
k! , k = 0, 1, 2, . . .. Both the mean and variance of Y is λ. A random variable Z follows a Skellam distribution if it is the difference between two independent Poisson variables Y1 and Y2. In this work, we restrict our attention to the case where Y1 and Y2 have the same parameter λ. In that case, the probability distribution of Z is
Pr[Z = k] = exp(−2λ)I|k|(2λ), k = 0,±1,±2, . . . , (1)
where Iv(u) , ∑∞ h=0 1 h!Γ(h+v+1) ( u 2 )2h+v is the modified Bessel function of the first kind. We write that Z ∼ Sk(λ, λ). By linearity of expectation, Z has mean 0 and variance 2λ. We say that two datasets X and X ′ are neighboring if one can be obtained by adding or removing one tuple from the other. The main idea of differential privacy (DP) is to ensure that the outcomes of a randomized mechanism on neighboring datasets are always similar; intuitively, this provides plausible deniability on whether a given data record x belongs to the dataset X or not, and, thus, protects the privacy of the individual whose record is x. A classic definition of differential privacy is ( , δ)-DP (Dwork et al., 2006), as follows. Definition 1 (( , δ)-Differential Privacy (Dwork et al., 2006)). A randomized mechanismM satisfies ( , δ)-differential privacy (DP) if
Pr[M(X) ∈ O] ≤ exp( ) · Pr[M(X ′) ∈ O] + δ, (2) for any set of output O ⊆ Range(M) and any neighboring datasets X and X ′.
Note that ( , δ)-DP can be considered as a worst-case privacy guarantee for a mechanism, as it enforces an upper bound on the probability ratio of all possible outcomes. An alternative definition called Rényi-Differential Privacy (RDP) (Mironov, 2017), which is built upon the concept of Rényi Divergence, considers the average case privacy guarantee instead. Definition 2 (Rényi Divergence (van Erven & Harremoës, 2014)). Assuming that distributions P and Q are defined over the same domain, and P is absolute continuous with respect to Q, then the Rényi divergence of P from Q of finite order α ∈ (0, 1) ∪ (1,∞) is defined as:
Dα(P‖Q) = 1
α− 1 logEX∼P
[( P (X)
Q(X)
)α−1] , (3)
where we adopt the convention that 00 = 0 and y 0 = ∞ for any y > 0, and the logarithm is with base e. Definition 3 (Rényi Differential Privacy (Mironov, 2017)). A randomized mechanismM satisfies (α, τ)-Rényi differential privacy (RDP) if Dα(M(X)‖M(X ′)) ≤ τ for all neighboring datasets X and X ′.
Given a function of interest, the canonical way make it differentially private is to perturb its outcome through noise injection. Roughly speaking, the scale of the noise should be calibrated to the sensitivity of the function of interest (Dwork et al., 2006), formally defined as follows. Definition 4 (Sensitivity). The sensitivity S(F ) of a function F : D → Rd, denoted as S(F ), is defined as
S(F ) = max X∼X′
‖F (X)− F (X ′)‖,
where X ∼ X ′ denotes that X and X ′ are neighboring datasets, and ‖·‖ is a norm.
In particular, injecting continuous Gaussian noise sampled from N (0, σ2) to each dimension of function F satisfies (α, αS
2(F ) 2σ2 )-RDP (Mironov, 2017), where S(F ) stands for the L2 sensitivity
of function F . In many applications, we also need to analyze the overall privacy guarantee of a mechanism consisting of multiple components (e.g., training neural networks with SGD). We have the following composition and sub-sampling lemmata for RDP mechanisms. Lemma 1 (Composition Lemma (Mironov, 2017)). If mechanisms M1, . . . ,MT satisfies (α, τ1), . . . , (α, τT )-RDP, respectively, thenM1 ◦ . . . ◦MT satisfies (α, ∑T t=1 τi)-RDP. Lemma 2 (Subsampling Lemma (Zhu & Wang, 2019; Mironov et al., 2019)). LetM be a mechanism that satisfies (l, τ(l))-RDP for l = 2, . . . , α (α ∈ Z, α > 2), and Sq be a procedure that uniformly sample each record of the input data with probability q. Then M ◦ Sq satisfies (α, τ)RDP with
τ = 1
α− 1 log
( (1− q)α−1(αq − q − 1) +
α∑ l=2 ( α l ) (1− q)α−lqle(l−1)τ(l) ) .
Finally, any mechanism that satisfies (α, τ)-RDP also satisfies ( , δ)-DP, for values of and δ as follows. Lemma 3 (Converting (α, τ)-RDP to ( , δ)-DP (Canonne et al., 2020)). For any α ∈ (1,∞), if Dα(M(X)‖M(X ′)) ≤ τ for any neighboring databases X and X ′, thenM satisfies ( , δ)-DP for
= τ + log(1/δ) + (α− 1) log(1− 1/α)− log(α)
α− 1 . (4)

heading: 3 DISTRIBUTED SKELLAM MECHANISM
text: Section 3.1 first formalizes the problem of distributed sum estimation, and presents the proposed distributed Skellam mechanism (DSM) for this problem. Section 3.2 establishes the privacy guarantees of DSM. Then, in Section 3.3, we apply DSM to our main problem setting: differentially private federated learning.

heading: 3.1 FORMAL DESCRIPTION
text: Suppose that an integer-valued multi-dimensional dataset X = (x1, . . . , xn) is distributed to n individuals (referred to as clients in the following), where client i possesses data point xi ∈ Zd, for i = 1, . . . , n. Without loss of generality, we assume that theL2 andL∞ norms of each xi is bounded by constants ∆2 and ∆∞, respectively, i.e., ‖xi‖2 ≤ ∆2 and ‖xi‖∞ ≤ ∆∞ for any xi ∈ X . An untrusted server aims to compute the (approximate) sum of the dataset, i.e., x̄ = ∑n i=1 xi, from the clients. The computation of x̄ must satisfy differential privacy. In particular, we focus on the RDP definition (Definition 3), which can be converted to the classic ( , δ)-DP (Definition 1) through Lemma 3.
Specifically, we aim to design a private mechanismM, such that for all neighboring datasetsX,X ′,
Dα(M(X)‖M(X ′)) ≤ τ, (5)
for some α > 1. We measure the error ofM by
ErrM = max X⊂Zd
E ∥∥∥M(X)−∑ x∈X x ∥∥∥2 2 , (6)
Algorithm 1: Distributed Skellam mechanism Input: Private dataset X = (x1, . . . , xn). Noise parameter λ. Secure aggregation protocol A(·). Output: x̃, a private estimation of ∑ x∈X x.
1 for xi ∈ X do 2 x̃i ←− xi + Z, where Z = (Z1, . . . , Zd) is sampled as in Eq. (7). 3 x̃←− A(x̃1, . . . , x̃n); secure aggregation.
where the expectation is taken over the randomness inM. Next, we present the proposed solution DSM for the above distributed sum estimation problem, outlined in Algorithm 1. Each client i first independently samples a noise vector following the Skellam distribution, and injects this noise to her data (Line 2 in Algorithm 1). In particular, the client samples a random d-dimensional noise vector Z = (Z1, . . . , Zd), where each element is identically and independently distributed, and follows the Skellam distribution of parameter λ, i.e.,
Z1, . . . , Zd i.i.d∼ Sk(λ, λ). (7)
We assume the clients have black-box access to a secure aggregation protocol A, following the convention in (Agarwal et al., 2018; Kairouz et al., 2021). The clients then compute the sum of their perturbed data using A, and release the sum to the server (Line 3 in Algorithm 1). Modular Arithmetic with communication constraints. When each element xi inX is represented using a limited number B of bits, each client needs to perform an extra step of modulo operation depending on B after injecting Skellam noise (Line 2), so as to avoid overflows. Accordingly, after obtaining the sum (Line 3), the server also needs to unwrap the modulo operation to recover the original noisy sum. We refer the reader to (Kairouz et al., 2021) for a detailed discussion on this issue. In our experiments in Section 4, we demonstrate that the proposed solution DSM achieves significant accuracy gains compared to existing approaches with various settings of the bit limit B.

heading: 3.2 THEORETICAL ANALYSIS
text: The following theorem states the privacy guarantee for Algorithm 1, which is the main theoretical result of this paper. Theorem 1 (Privacy guarantee of the distributed Skellam mechanism). When 1 < α < 2nλ∆∞ + 1, Algorithm 1 with noise parameter λ satisfies (α, τ)-Rényi Differential Privacy with
τ = 1.09α+ 0.91 2 · ∆
2 2
2nλ . (8)
Proof. To prove the privacy guarantee of Algorithm 1, it suffices to derive the privacy guarantee of the sum of {Skλ(xi)}ni=1. Note that the secure aggregation protocolA (used as a black-box) ensures that only the sum of the perturbed data is revealed to the server. In addition, according to properties of the Skellam distribution, aggregating n independent Skellam noise vectors Z ∼ Sk(λ, λ) results in a single Skellam noise Z̄ ∼ Sk(nλ, nλ) (Skellam, 1946). Hence, we only need to focus on the privacy guarantee achieved by Z̄. Further, in what follows, we focus on the one dimensional case of the problem, i.e., d = 1. The proof in the general case where d > 1 then follows from the additivity of Rényi divergence for product distributions (van Erven & Harremoës, 2014).
Without loss of generality, we let s > 0, Z ∼ Sk(λ, λ) and compute Φ = exp((α−1)Dα(Z+s‖Z)). We first present several useful inequalities, whose proofs can be found in the appendix. Let
Qs,t(v) := s∏ i=1
v + i+ √ (v + i)2 + t2
t . (9)
According to Lemma 4 in the appendix, we have:
I|v|(t)
I|v+s|(t) ≤ Qs,t(v). (10)
In addition, for any 0 < a ≤ w, according to Lemmata 5-7 in the appendix, we have w + √ w2 + 1
(a− w) + √ (a− w)2 + 1 ≤ e2w−a, (11)
and ( w + √ w2 + 1 ) · ( (a− w) + √ (a− w)2 + 1 ) ≤ ea. (12)
By the definition of Skellam distributions and Eq. (9)
Φ = ∞∑ z=−∞ ( I|z|(2λ) I|z+s|(2λ) )α−1 Pr[Z = z] ≤ ∞∑ z=−∞ (Qs,2λ(z)) α−1 Pr[Z = z]
= ∑ |z|≤s (Qs,2λ(z)) α−1 Pr[Z = z] + ∑ z>s ( (Qs,2λ(z)) α−1 + (Qs,2λ(−z))α−1 ) Pr[Z = z].
We compute
(Qs,2λ(z)) α−1 + (Qs,2λ(−z))α−1 = (Qs,2λ(z)Qs,2λ(−z)) α−1 2 · ( Rs,2λ(z) +
1
Rs,2λ(z)
) ,
where Rs,2λ(z) :=
( Qs,2λ(z)
Qs,2λ(−z)
)α−1 2
.
By Eq. (11), when z ≥ i, z + i+ √ (z + i)2 + (2λ)2
−z + i+ √ (−z + i)2 + (2λ)2 = z+i 2λ +
√ ( z+i2λ ) 2 + 1
−z+i 2λ + √ (−z+i2λ ) 2 + 1 < exp( z λ ).
Therefore, when z ≥ s, we have Qs,2λ(z)Qs,2λ(−z) < exp ( sz λ ) , and Rs,2λ(z) < exp ( s(α−1)z 2λ ) . Since the function v 7→ v + 1v is increasing,
Rs,2λ(z) + 1
Rs,2λ(z) < exp
( s(α−1)z
2λ
) + exp ( − s(α−1)z2λ ) .
By Eq. (12), when z ≥ i, z + i+ √ (z + i)2 + (2λ)2
2λ · −z + i+
√ (−z + i)2 + (2λ)2
2λ
= ( z+i 2λ + √( z+i 2λ )2 + 1 ) · ( −z+i 2λ + √(−z+i 2λ )2 + 1 ) ≤ exp ( i λ ) .
Hence, when z ≥ s, we haveQs,2λ(z)·Qs,2λ(−z) < exp ( s(s+1)
2λ
) . Meanwhile, when−s < z < s,
according to Lemma 8 in the appendix, we have: Qs,2λ(z) ≤ exp ( s(s+z)
2λ
) .
Therefore, Φ ≤ exp ( s(s+1)(α−1)
4λ
) · ∑∞ z=s ( exp( s(α−1)z2λ ) + exp(− s(α−1)z 2λ ) ) Pr[Z = z]
+ ∑s−1 z=−s+1 exp ( s(α−1)(s+z) 2λ ) Pr[Z = z]
≤ exp ( s2(α−1)
2λ )∑∞ z=−∞ exp ( s(α−1)z 2λ ) Pr[Z = z]
= exp ( s2(α−1)
2λ
) E [ exp ( s(α−1)Z
2λ
)] .
The moment generating function of Sk(λ, λ) is E[etZ ] = eλ(et+e−t−2). When 0 < t < 1, we have et + e−t − 2 < 1.09t2. Thus, when λ > s(α−1)2 ,
E [ exp ( s(α−1)Z
2λ
)] ≤ exp ( 1.09λ( s(α−1)2λ ) 2 ) = exp ( 1.09s2(α−1)2 4λ ) .
As a result, when λ > s(α−1)2 , we have Φ ≤ exp ( s2(α−1) 2λ + 1.09s2(α−1)2 4λ ) .
Algorithm 2: Federated learning with distributed Skellam mechanism Input: Private dataset X = (x1, . . . , xn). Sampling parameter q. L2 norm clipping bound C > 0.
Quantization granularity γ. Conditional rounding parameter k. Noise parameter λ. Black-box secure aggregation protocol A(·). Initial model parameters θ. Number of iterations T .
Output: θ model parameters learnt on X . 1 for h ∈ 1..T do 2 The server shares the current model parameters θ to all clients. 3 C u.a.r←− {1, 2, . . . , n} ; // sample a subset of clients uniformly at random from all clients using Poisson sampling with rate q. 4 for i ∈ C do 5 gi ←− ∇θ(xi); // gradient computation. 6 gi ←− Clip(gi, C); // gradient clipping based on L2 norm. 7 gi ←− gi/γ; // quantization. 8 gi ←− Round(gi, k); // conditional rounding. 9 g̃ ←− Distributed Skellam mechanism ({gi}i∈C , λ,A(·)).
10 g̃ ←− γ · g̃; // re-scaling 11 θ ←− Update(θ, g̃); // model update based on the approximate gradient sum
Note that the privacy guarantee of DSM in Theorem 1 is independent of the data dimensionality d. Next we analyze the error incurred by Algorithm 1, which has the following bound: Corollary 1 (Error bound of the distributed Skellam mechanism). With 1 < α < 2nλ∆∞ + 1, the error incurred by Algorithm 1 that satisfies (α, τ)-RDP is bounded by
ErrM ≤ 1.09α+ 0.91 2 · d∆
2 2
τ .
The proof for the above corollary is omitted for brevity, which directly follows from Theorem 1 and the linearity of expectation. Note that the error bound in the above corollary is comparable with (i.e., within a constant factor) that of adding continuous Gaussian noise in the centralized setting, which is (α−1)·d·∆22/(2τ) (Mironov, 2017). Meanwhile, since Algorithm 1 satisfies RDP, by Lemmata 1 and 2, it allows the tight privacy accounting in DPSGD through composition and subsampling. Note that although the above analysis restricts the value of α to 1 < α < 2nλ/∆∞ + 1, this constraint only affects the utility of DSM, not its privacy guarantees. Further, in practice, n (i.e, the number of training data points) is usually much larger than ∆∞, leading to a large range of values for α. In addition, the optimal α (order of RDP) is often relatively small (e.g. less than 10) in our experiments, and the above range represents a sufficiently large space for tuning α.
Comparing the theoretical results DSM with those of existing solutions described in Section 1, cpSGD (Agarwal et al., 2018) does not satisfy RDP, and does not have the corresponding composition and sub-sampling properties that are crucial for tight privacy analysis. Meanwhile, DDG (Kairouz et al., 2021) ensures (α, τ ′)-RDP with τ ′ = α2 ·
min ( 1 n · ∆22 σ2 + 1 2ρ · d, ( 1√ n · ∆2σ + ρ · √ d )2) when each client independently injects discrete
Gaussian noise of variance σ2 to her data, where ρ is defined as ρ := 10 · ∑n−1 k=1 exp(−2π2σ2 · k k+1 ). Note that the above τ ′ term increases with the data dimensionality d, which is not scalable for large d. In contrast, the privacy guarantee of DSM is independent of d. These advantages of DSM lead to significant utility gains in our target application: FL under differential privacy, described next.

heading: 3.3 FEDERATE LEARNING WITH DISTRIBUTED SKELLAM MECHANISM
text: We apply the proposed DSM described in Algorithm 1 to enforce DP on federated learning with distributed SGD, assuming that the clients have access to a black-box secure aggregation protocol. Algorithm 2 outlines the training process. In each iteration, the server releases the current model parameters to all clients (Line 2). Then, DSM randomly selects a subset of clients, whose identities are not known to the server (Line 3). Each client in the selected subset then computes the gradients based on the current model weights and her own data (Line 5), and performs gradient clipping (Line 6), which is a standard step introduced in DPSGD to bound the sensitivity of deep learning with
DP. After that, the client quantizes the gradients (Line 7), as required by typical MPC protocols for gradient aggregation. Here, a parameter γ controls the quantization granularity: a smaller γ leads to more precise quantization, and vice versa. Subsequently, the client randomly rounds the gradient to the integer grid Zd (Line 8, explained soon). Next, we apply the distributed Skellam mechanism (Algorithm 1) to the integer-valued gradients (Line 9). Finally, the server re-scales the approximate gradient sum by a factor of γ (Line 10) and updates the shared model accordingly (Line 11). We omit additional details on the updating process (e.g., learning rate schedule, weight decay, etc.) as they do not affect the general framework or the privacy guarantees. After repeating the above process for T iterations, the training terminates, and the server obtains the final model weights θ.
Next we clarify the conditional rounding step (Line 8 of Algorithm 2). This step is necessary since after gradient clipping (Line 6) and quantization (Line 7), we still have real-valued gradients, which are not compatible with the MPC protocol (i.e., the black-box secure aggregation protocolA used in DSM). To explain the conditional rounding in Line 8, we first define an element-wise unconditional rounding process as follows: for input x ∈ R, x is rounded to floor(x) with probability ceil(x) − x, and to ceil(x) otherwise. The problem with this unconditional gradient rounding process is that it introduces an additional O(d) term on the L2 sensitivity of the resulting integer gradients. To mitigate this issue, Kairouz et al. (2021) propose to repeatedly run the unconditional rounding algorithm until the L2 norm of the rounded result satisfies a pre-defined condition. The stopping condition in (Kairouz et al., 2021) is rather complex, and increases the sensitivity of the resulting gradients by a factor of O( √ d). Algorithm 2 adopts this general idea, but sets a much simpler stopping condition than the one in DDG, as follows: the rounded gradient’s L2 norm must not exceed a pre-defined constant k (e.g., 5 in our experiments) times C/γ, where C is the L2 clipping bound in Line 6, and γ is the quantization granularity in Line 7. With this stopping condition, the increase in L2 sensitivity in Line 8 is a constant independent of the gradient dimensionality d. Regarding privacy guarantees of Algorithm 2, observe that each iteration of the training process can be seen as running the distributed Skellam mechanism on a random subset of rounded gradients. This is because the model sharing (Line 2), gradient sum re-scaling (Line 10), and model updating (Line 11) do not incur any additional privacy loss, as the updated model can be reconstructed by the re-scaled perturbed gradient sum, which, in turn, can be computed from the perturbed gradient sum. In addition, since the identities of the random subset of clients are not known to the server, the privacy guarantee benefits from amplification by subsampling. (We refer the reader to (Kairouz et al., 2021) for a detailed discussion on this issue.) Hence, the privacy guarantee of Algorithm 2 follows by applying the composition lemma (Lemma 1) and the amplification lemma (Lemma 2) on the privacy analysis of DSM (Theorem 1). A formal statement of the privacy guarantees of Algorithm 2 is presented in Theorem 2 in the appendix.

heading: 4 EXPERIMENTS
text: We evaluate the performance of the proposed solution DSM (Algorithm 2) on two classic benchmark datasets: MNIST (Lecun et al., 1998) and Fashion MNIST (Xiao et al., 2017), which contains grayscale images of handwritten digits and clothing, respectively. Both datasets represent 10-class classification tasks with 60, 000 training data records. We regard each data record in the training data as a client. For both tasks, we train a three-layer neural network with fully connected layers and ReLu activation, following previous work (Agarwal et al., 2018). We set the number of neurons per layers to 80, resulting in a model with d = 63, 610 weights. For DDG and DSM, we use the same L2 clipping norm (C = 1) and quantization granularity (γ = 0.1). In addition, for cpSGD, we apply the tighter privacy analysis presented in (Koskela et al., 2021), which leads to improved prediction accuracy. For all experiments, we use the Adam optimizer (Kingma & Ba, 2015) with learning rate η = 0.005. We do not tune the hyper-parameters in favor of any particular solution and omit additional experiments on hyper parameter tuning. We remark that our approach is compatible with existing differentially private parameter tuning techniques (Gupta et al., 2010; Liu & Talwar, 2019), which is an orthogonal topic to this paper.
Our evaluation uses the ( , δ)-DP (Definition 1) definition instead of RDP (Definition 3, since a competitor cpSGD supports the former but not the latter. We fix δ to 10−5, and vary the privacy parameter from {1, 2, 3, 4, 5}, batch size m from {120, 240, 480, 960}. The model is trained for 1 epoch, i.e., when m equals to 120, 240, 480, and 960, we train the model for 500, 250, 125, and
62 rounds, respectively. For (DDG) and our solution DSM, we also vary the bit limit per weight B from {6, 8, 10, 12} bits; for cpSGD, we fixB to 32. This is because the amount of noise injected by cpSGD is rather large, and smaller values of B lead to very poor model utility. Note that a large B leads to higher communication costs between the clients. We report the average test accuracy over 5 runs. The results are shown in Figures 1 and 2. In addition, we have also included the non-private baseline and the centralized-DP baseline DPSGD (Abadi et al., 2016b) in the figures.
Overall, the proposed solution DSM (marked as “Skellam” in the figures) significantly outperforms its competitors cpSGD and DDG on all settings. In particular, the accuracy improvement over DDG is consistently around 15% and 10% for MNIST and Fashion MNIST, respectively. From Figures 1(a) and 2(a), we observe that the performance gap expands as decreases, which corresponds to stronger privacy protection and requires higher noise levels. According to Figures 1(b) and 2(b), our solution is the only mechanism that achieves acceptable accuracy when the number of bits B is as low as 8 per weight, which corresponds to a stringent constraint on the communication costs in the underlying MPC protocol. The test accuracy obtained with cpSGD is rather low (no more than 30%), even though it is given a generous value of B = 32. Finally, according to Figures 1(c) and 2(c), the accuracy for all methods remains stable with varying batch size m.

heading: 5 CONCLUSION
text: In this work, we propose the distributed Skellam mechanism (DSM), a novel solution for enforcing differential privacy on machine learning models built through an MPC-based federated learning process using distributed stochastic gradient descent. Compared to existing solutions, DSM achieves privacy guarantee that is independent of the dimensionality of the weight vector, while allowing tight privacy accounting due to its nice composition and sub-sampling properties. We conduct extensive experiments on two classic benchmark datasets and various practical settings, and the result demonstrate the consistent and significant accuracy gains DSM over existing solutions.
Regarding future work, we plan to further reduce the constant factor in the privacy analysis for DSM to improve model utility under the same level of privacy protection. Another promising direction is to open up the black box of the MPC protocol and perform careful privacy analysis with considerations for the details of MPC protocol, which might help lower the noise level further, leading to a more favorable privacy-utility trade-off for federated learning.

heading: REPRODUCIBILITY STATEMENT
text: We provide our source code for our distributed Skellam mechanism implementation for reviewing purposes, available at https://anonymous.4open.science/r/Distributed_ Skellam_Mechanism. Our implementation simulates federated learning with a single machine.

heading: A APPENDIX

heading: A.1 PROOFS
text: Lemma 4. Let Qs,t(v) = ∏s i=1 v+i+ √ (v+i)2+t2 t . Then, I|v|(t) I|v+s|(t) ≤ Qs,t(v).
Proof. By properties of the modified Bessel function of the first kind (Andrea & Pierpaolo, 2010), we have inequality
Iv−1(t) Iv(t) < v + √ v2 + t2 t , v ≥ 0
and recurrence relation Iv+1(t) = Iv−1(t)− 2v
t Iv(t)
which leads to Iv+1(t)
Iv(t) < −v +
√ v2 + t2
t , v ≥ 0.
When v < 0, substituting v for −v − 1 in the previous formula,
I|v|(t)
I|v+1|(t) =
I−v(t) I−v−1(t) < v + 1 +
√ (v + 1)2 + t2
t
When v ≥ 0, we also have
I|v|(t)
I|v+1|(t) =
Iv(t) Iv+1(t) < v + 1 +
√ (v + 1)2 + t2
t
Therefore, for every v,
I|v|(t)
I|v+s|(t) < s∏ i=1
v + i+ √ (v + i)2 + t2
t := Qs,t(v).
Lemma 5. For any w ≥ 0, w + √ w2 + 1 ≤ ew.
Proof. The inequality holds whenw = 0. By taking the derivative, it can be verified that the function ew − (w + √ w2 + 1) is increasing with respect to w.
Lemma 6. For any 0 < a ≤ w,
w + √ w2 + 1 (a− w) + √ (a− w)2 + 1 ≤ e2w−a.
Proof. By Lemma 5, w + √ w2 + 1 ≤ ew. Then, by Lemma 5 again, 1
(a− w) + √ (a− w)2 + 1 = (w − a) +
√ (w − a)2 + 1 ≤ ew−a.
Lemma 7. For any 0 < a ≤ w, (w + √ w2 + 1) · ((a− w) + √ (a− w)2 + 1) ≤ ea.
Proof. By Lemma 5, the inequality holds when w = a. By taking derivative, it can be verified that the left hand side is decreasing with respect to w.
Lemma 8. When −s < z < s, we have Qs,2λ(z) ≤ exp ( s(s+ z)
2λ
) .
Proof. Use Lemma 5. When 0 ≤ z < s,
Qs,2λ(z) ≤ s∏ i=1 exp ( z + i 2λ ) = exp ( s(s+ 1 + 2z) 4λ ) ≤ exp ( s(s+ z) 2λ ) .
When − s2 ≤ z < 0, using the equality
b+ √ b2 + (2λ)2
2λ · −b+
√ (−b)2 + (2λ)2
2λ = 1,
we have
Qs,2λ(z) = s∏ i=1
z + i+ √ (z + i)2 + (2λ)2
2λ
= s∏ i=−2z
z + i+ √ (z + i)2 + (2λ)2
2λ
≤ s∏
i=−2z exp
( z + i
2λ ) = exp ( s(s+ 2z − 1)
4λ ) ≤ exp ( s(s+ z)
2λ
) .
When −s < z < − s2 , we have
Qs,2λ(z) = −2z−s−1∏ i=1
z + i+ √ (z + i)2 + (2λ)2
2λ
≤ 1 ≤ exp ( s(s+ z)
2λ
) .

heading: A.2 PRIVACY GUARANTEE OF ALGORITHM 2
text: Theorem 2 (Privacy guarantee of Algorithm 2). Let α ∈ Z, 2 < α < 2nλγCk + 1. Then for L2 norm clipping bound C, noise parameter λ, quantization granularity γ, conditional rounding parameter k, sampling parameter q, and iterations T , Algorithm 2 satisfies (α, τ)-Rényi Differential Privacy with
τ = T · 1 α− 1 log
( (1− q)α−1(αq − q − 1) +
α∑ l=2 ( α l ) (1− q)α−lqle(l−1)τ(l) ) , (13)
where τl is defined as τl := 1.09l+0.912 · C2k2 2nλγ2 , for l = 2, . . . , α.
We omit the proof for brevity, which follows from our main theoretical result Theorem 1, as well as subsampling (Lemma 2) and composition (Lemma 1).

heading: A.3 OVERFLOWING IN MODULAR ARITHMETIC
text: The key to avoid overflowing is to restrain the perturbed gradient weights within the range of the finite integer filed, namely [−2B−1, 2B−1 − 1]. We first review the concentration property of the symmetric Skellam distribution Z ∼ Sk(λ, λ) of mean 0. Note that Z has MGF exp(λ(exp(λ) + exp(−λ)− 2)). In addition, since x · (exp(x) + exp(−x)− 2) ≤ 1.09x2 for 0 ≤ x < 1. We have that Z is sub-exponential with parameters ( √ 2.18, 1). Namely,
E[exp(tZ)] ≤ exp(1.09t2), for |t| ≤ 1. (14)
From here we obtain the tail bound for Z,
Pr[Z ≥ x] ≤ exp(−x/2), for x ≥ 2.18. (15)
Hence, to avoid overflowing due to the Skellam noise, it suffices to set 2B ≥ h log d, where d is the dimension of the gradient weights, and h is some constant to balance the communication cost and the error due to overflowing. A relatively large h limits the error due to overflowing while incurring a large communication cost; and vice versa. Note that a more precise reasoning can be obtained by observing that Z approaches a normal distribution with mean 0 and variance 2λ, when Z is of order √ 2λ. In fact, in our experiments, we observe that overflows are rare under a reasonable communication constraint. To be more specific, no overflow was observed when the number of bits per dimension reaches 10 or above, and very few overflows occured when the number of bits per dimension is 8 (once every a thousand weights).

heading: A.4 CONCURRENT WORK
text: Agarwal et al. (2021) also suggest using the Skellam noise in the distributed DP setting. Different from our work, their privacy analysis for the Skellam noise is dependent on both the L2 norm and L1 norm of the private input vector. Since the L1 norm of a high dimensional vector can be much larger than its L2 norm, the privacy analysis we present is tighter. Further tightening the analysis is a promising future direction.

Review summaries:
### update after the discussions  I am satisfied with the responses from the authors' and the updated paper. I therefore recommend accepting the paper.  ---  The paper considers the problem of distributed differentially private (DP) learning using black-box secure multi-party computation (MPC) for aggregating gradients for learning the model.  In principle, using e.g. secure aggregation allows each party to add a small amount of noise scaled so that the noise level after aggregation matches what one needs with a trusted central party. However, since the existing tools (mainly Gaussian mechanism) typically assume continuous space, while MPC works with discrete values, this does not work in practice: the main problem is that the discretised noise is not infinitely divisible so the sum is not guaranteed to follow the same distribution as the individual contributions.  To remedy the problem, the authors propose the distributed Skellam mechanism, which is both dicrete and infinitely divisible. The authors show that the Skellam mechanism privacy cost can be calculated using Rényi DP (RDP), and continue to show that it performs significantly better than the existing methods based on binomial noise and discrete Gaussian noise using MNIST and Fashion MNIST data for testing.

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

This paper presents a mechanism based on Skellam distribution (called Distributed Skellam Mechanism (DSM)) to prevent privacy leakage for federated learning. It provides analysis of privacy guarantee in the decentralized setting. Specifically, DSM is shown to be both RDP and (\epsilon, \delta)-DP. Also, DSM is applied to differentially private federated learning with distributed SGD and quantized gradients.