D2p-fed:Differentially Private Federated Learning with Efficient Communication
Authors: Lun Wang
Ruoxi Jia
Dawn Song
Venue:  (2021)
Keywords: Differential Privacy
Federated Learning
Communication Efficiency

Abstract: In this paper, we propose the discrete Gaussian based differentially private federated learning (D2p-fed), a unified scheme to achieve both differential privacy (DP) and communication efficiency in federated learning (FL). In particular, compared with the only prior work taking care of both aspects, D2p-fed provides stronger privacy guarantee, better composability and smaller communication cost. The key idea is to apply the discrete Gaussian noise to the private data transmission. We provide complete analysis of the privacy guarantee, communication cost and convergence rate of D2p-fed. We evaluated D2p-fed on INFIMNIST and CIFAR10. The results show that D2p-fed outperforms the-state-of-the-art by 4.7% to 13.0% in terms of model accuracy while saving one third of the communication cost. The code for evaluation is available in the supplementary material.

Under review as a conference paper at ICLR 2021
D'P-FED: DIFFERENTIALLY PRIVATE FEDERATED LEARNING WITH EFFICIENT COMMUNICATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose the discrete Gaussian based differentially private federated learning (D?P-FED), a unified scheme to achieve both differential pri- vacy (DP) and communication efficiency in federated learning (FL.). particular, compared with the only prior work taking care of both aspects, D2P-FED provides stronger privacy guarantee, better composability and smaller communication cost. The key idea is to apply the discrete Gaussian noise to the private data transmis- sion. We provide complete analysis of the privacy guarantee, communication cost and convergence rate of D We evaluated DPP-FED INFIMNIST and CIFARIO. The results show that D²P-FED outperforms the-state-of of-the-art by 4.7% to 13.0% in terms of model accuracy while saving third of the commu- nication cost. The results might be surprising at its first glance but is reasonable because the quantization level k in DDP-FED is independent of q. As long as is large enough, the probability that the noise exceeds is small and thus has negligible impact on the model accuracy.
INTRODUCTION
Federated learning (FL) is popular machine learning paradigm that allows central server train models over decentralized data sources. In federated learning, each client performs training locally on their data source and only updates the model change to the server, which then updates the global model based on the aggregated local updates Since the data stays locally, FL can provide better privacy protection than traditional centralized learning. However, FL facing two main challenges: (1) FL lacks rigorous privacy guarantee (e.g., differential privacy (DP)) and indeed, it has been shown to be vulnerable to various inference attacks (Nasr et al. 2019, Pustozerova & Mayer) Xie et al. 2019); ; (2) FL. incurs considerable communication costs. In many potential applications of FI. such as mobile devices, these two challenges are present simultaneously.
However, privacy and communicationn-eficiiene. have mostly been studied independently in the past. As regards privacy, existing work has applied a gold-standard privacy notion - differential privacy (DP) - to FL, which ensures that the server could hardly determine the participation of each client by observing their updates (Geyer et al. (017)). To achieve DP, each client needs to inject noise to their local updates and side effect, the performance of the trained model would inevitably degrade. To improve model utility, secure multiparty computation (SMC) has been used in tandem with DP reduce noise (Jayaraman al., [2018) Truex al., 2019). The key idea to prevent the server from observing the individual updates, make only the aggregate accessible, and thus transform from local DP central DP. However, SMC introduces extra communication overhead to each client. There has been extensive research on improving communication efficiency of FL while ignoring the privacy aspect (Tsitsiklis & Luo 1987: Balcan al. 2012 Zhang et al.) 2013 Arjevani & [Shamir] 2015 Chen et al.) 2016). However, these communication reduction methods either have incompatible implementations with the existing DP mechanisms or would break the DP guarantees when combined with SMC.
The only existing work that tries to reconcile DP and communication efficiency FL is epSGD (Agarwal al. 2018). The authors leveraged the Binomial mechanism, which adds Bi- nomial noise into local updates to ensure differential privacy. The discrete nature of Binomial noise allows it to be transmitted efficiently. However, epSGD faces several limitations when applied to real-world applications. Firstly, with Binomial noise, the output of learning algorithm would have different supports different input datasets; as a result, Binomial noise only guarantee approx-

---

Under review as a conference paper at ICLR 2021
imate DP where the participation of the client can be completely exposed with nonzero probability. Also, there lacks a tight composition for DP with Binomial noise and the resulting privacy budget skyrockets in a multi-round FL protocol. Hence, the Binomial mechanism cannot produce a useful model with a reasonable privacy budget on complex tasks. Last but not least, the Binomial mecha- nism involves several mutually constrained nyper-parametens and the privacy formula is extremely complicated, which makes nyper-parameter tuning a difficult task.
In this paper, we propose the discrete Gaussian based differential private federated learning (D*p- FED), an alternative technique to reduce communication costs while maintaining differential privacy in FL. Our key idea to leverage the discrete Gaussian mechanism in FL, which adds discrete Gaussian noise into client updates. We show that the discrete Gaussian mechanism satisfies Rényi DP which provides better composabilityy We employ secure aggregation along with the discrete Gaussian mechanism to lower the noise and exhibit the privacy guarantee for this hybrid privacy protection approach. To save the communication cost, we integrate the stochastic quantization and random rotation into the protocol. We then cast FL as a general distributed mean estimation problem and provide the analysis of the utility for the overall protocol. Our theoretical analysis sheds light on the superiority of D FED to epSGD. Our experiments show that DdP-FEE can lead to state-of- the-art performance in terms of managing the trade-off among privacy, utility, and communication.
D-D
RELATED WORK
is well studied how to improve the communication cost in traditional distributed learning set- tings (Tiissiklis & Luo 1987); Balcan al.] ZZhng al. (Arjevani & Shamir (2015); Chen et al. (2016)). However, most of the approaches either require communication between the workers or are designed for specific learning tasks so they cannot be applied directly to general- purpose FL. The most relevant work is Suresh et al. (2117) which proposed to use stochastic quan- tization save the communication cost and random rotation to lower mean squared error of the estimated mean. We follow their approach to improve the communication efficiency and model util- ity of D'P-FED. Nevertheless, our work differs from theirs in that we also study how to ensure DP for rotated and quantized data transmission and prove a convergence result for the learning algorithm with both communication cost reduction and privacy protection steps in place.
On the other hand, differentially private FL is undergoing rapid development during the past few years (Geyer et al. (2017); McMahan et al. (2017); Jayaraman et al. (2018)). However, these meth- ods mainly focus improving utility under small privacy budget and ignore the issue of com- munication cost. In particular, we adopt a similar hybrid approach to Truex et al. (2019), which combines SMC with DP for reducing the noise. SMC ensures that the centralized server see the aggregated update but not individual ones from clients and as a result, the noise added by each client can be reduced by a factor of the number of clients participating in one round. The difference of our work from theirs is that we inject discrete Gaussian noise to local updates instead of the continuous Gaussian noise. This allows us to use secure aggregation (Bonawitz et al. (017) which is much cheaper than threshold homomorphic encryption used by Truex et al. (2019). We further study the interaction between discrete Gaussian noise and the secure aggregation as well as their effects on the learning convergence.
only
We identify epSGD (Agarwal et al. (2018) as the most comparable work to DPP-FED. Just like DDP-FED, epSGD aims to improve both the communication cost and the utility under rigorous privacy guarantee. However, epSGD suffers from three main defects discussed in Section [ This paper proposes to use the discrete Gaussian mechanism to mitigate these issues in epSGD.
3 BACKGROUND AND NOTATION
In this section, we provide an overview of FL and DP and establish the notation system. We use bold lower-case letters (e.g. a.b,c) to denote vectors, and bold upper-case letters (e.g. A, B, C) for matrices. We denote 1 .n. by [n].
FL Overview. In a FL system, there are one server and n clients C,, E [n]. The server holds global model of dimension d. Each client holds (IID or non-lID) samples drawn from some unknown distribution D. The goal is to learn the global model w e Rd that minimizes some loss function L(w, D). To achieve this, the system runs T-round FL protocol. The server initializes
2

---

Under review as a conference paper at ICLR 2021
the global model with wy- In round t [T], the server randomly sub sub-samples "yn clients from [n] with sub-sampling rate y and broadcasts the global model w;-1 to the chosen clients. Each chosen client C. then runs the local optimizers (e.g. SGD, Adam, and RMSprop), computes the difference
between the locally optimized model w. and the global model w gi =,," w,-1, I. and
(f) uploads 9: to the server. The server takes the average of the differences and update the global model wt 1 Eg!" !
Communication in FL. The clients in FL are often edge devices, where the upload bandwidth is fairly limited; therefore, communication efficiency is of uttermost importance to FL. Let π denote a communication protocol. We denote the per-round communication cost as C(T,, g (l). To lower the communication cost, the difference vectors are typically compressed before sent to the server. The compression would degrade model performance and we measure the performance loss via the mean squared error. Specifically, letting 9 denote the actual mean of difference vectors Ei=1 g()) and g denote the server's estimated mean of difference vectors using some protocol such as D FED, we could measure the performance loss by E { (l))) E[[l gl i.c., the mean squared error between the estimated and the actual mean. This mean squared error is directly related to the convergence rate of FL (Agarwal et al. 2018).
Threat Model & Differential Privacy. We assume that the server is conest-but-curions Namely, the server will follow the protocol honestly under the law enforcement or reputation pressure. but is curious to learn the client-side data from the legitimate client-side messages. In the FI. context, the server wants to get information about the client-side data by studying the local updates received without deviating from the protocol.
The above attack, widely known as the inference attack (Shokri et al., 2017; Yeom et al. 2018 Nasr et al., 2019), can be effectively mitigated using canonical privacy notation namely differential privacy (DP). Intuitively, DP, in the context of ML, ensures that the trained model is nearly the same regardless of the participation of any arbitrary client.
Definition ((c, 8)-DP) A randomized algorithu f D + R is (c, diffferrent private if for every pair of neighboring datasets D and D' that differs only by one datapoint, and every possible (measurable) output set E the following inequality holds: P(f(D) S E] S e P(f((D)) S E] +
(c, DDD has been used privacy notion in most of the existing works of privacy-presse seevacy-pesservng FL. However, in this paper, we consider a generalization of DP, Rényi differential privacy (RDP). which is strictly stronger than (c, 6D for 5 > 0 and allows tighter analysis for compositing multiple mechanisms. This second point is particularly appealing, as FL. mostly comprises multiple rounds yet the existing works suffer from skyrocketing privacy budgets for multi-round learning.
Definition 2 ((a, c)-RD)). For two probability distributions P and Q with the same support, the
Rényi divergence of order a > 1 is defined by (PII)) - - log En-Q( P(x) ja randomized
Q(a)
mechanism f D + R. is (ae, C)-DP, if for any neighboring datasets D, D' E D it holds that (((())))((D))) S.
The intuition behind RDP is the same as other variants of differential privacy: "Similar inputs should yield similar output distributions," and the similarity is measured by the Rényi divergence under RDP. RDP can also be converted to (c, 5)DP using the following transformation.
Lemma 1 (RDP-DP conversion (Mironoy (2017)). If . obeys (a, R)-RDP, then M obeys (e + log(1/6)/((= 1), 6DP for all <
RDP enjoys an operationally convenient and quantitatively accurate way of tracking cumulative privacy loss when compositing multiple mechanisms (Lemma ( or being combined with subsam-
pling (Wang et al. 2018). As result, RDP is particularly suitable for the context of ML.
Lemma (Adaptive composition of RDP (Mironov (2017)). If (fnddooiieed) mechanism M1 obeys (a, 61 RDDP, and M2 obeys (a,, RR)P then their composition obeys (ax, + -DDP.
DISCRETE GAUSSIAN MECHANISM
In this section, we present the discrete Gaussian mechanism and establish its privacy guarantee. We first introduce discrete Gaussian distribution.
3

---

Under review as a conference paper at ICLR 2021
Definition 3 (Discrete Gaussian Distribution). Discrete Gaussian is a probability distribution a discrete additive subgroup LL (for instance, a multiple of Z) parameterized by o. For a discrete Gaussian distribution (o) and x E L, the probability mass on x is proportional to e -
Discrete Gaussian mechanism works by adding noise drawn from discrete Gaussian distribution. Canonne et al.] (2020) proved concentrated DP for the discrete Gaussian mechanism. However, there lacks tight privacy amplification and composition theorem for concentrated DP. To address, we turn to RDP and provide the first RDP analysis for the discrete Gaussian mechanism. The proof is delayed to Appendix due to space limitation.
Theorem (RDP for discrete Gaussian mechanism). I has sensitivity 1 and range( C T, then the discrete Gaussian mechanism: f()) + (a) satisfies (a, (e/o(22))))))))))
Under RDP, discrete Gaussian exhibits tight privacy amplification bound under sub-sampling (Wang al. 2018). This suits FL well since a subset of clients is sub- sampsa to upload the updates in each round.
Corollary 1 (Privacy amplification for discrete Gaussian mechanism (Wang et al. 2018)). If discrete Gaussian mechanism (a, 2 RRDP, then augmented with subsampling (without replace-
ment), the privacy guarantee is amplisied to (1) (ar, (gg)) )) in the high privacy regime; or (2) (a, ((ar(e:))) in the low privacy regime.
Besides. RDP enables discrete Gaussian mechanism to be composed tightly with analytical moments accountant (Wang et al. (2018), which saves a huge amount of privacy budget in a multi- FL. Analytical moments accountant is data structure that tracks the cumulant generating function of the composed mechanisms symbolically. Since it has no closed-fore solution, we instead introduce the canonical composition of RDP (Mironov] 2017) below for the ease of discussion in Section 6.3
Corollary 2 (Composition for discrete Gaussian mechanism (Wang et al. 2018)) If a discrete Gaussian mechanism is (a,, 20z -RDP, then the sequential composition of T such mechanisms yield (a, 20t RDDP guarantee. If we convert all the RDP guarantees back to (c, 5)DP, the growth of e under the same 8 is asymptotically O(VT).
Note that both privacy amplification and composition are given in an asymptotic form for the clarity of presentation. For tight bound, we refer the readers to Theorem 27 and Section 3.3 in Wang et al. 2018
5
D2P-FED: ALGORITHM AND PRIVACY ANALYSIS
In this section, we formally present D2P-FED and provide rigorous privacy analysis.
5.1 ALGORITHM
Algorithm provides the pseudocode for D*P-FED. It follows the general FL pipeline which itera- tively performs the following steps: (1) the server broadcasts the global model to subset of clients; (2) the selected clients train the global model on their local data and upload the resulting model difference; and (3) the server aggregates the model differences uploaded by the clients and updates the global model. Grounded on the general FL. pipeline, D2P-FED introduces some additional steps at the client side follows to improve communication efficiency and privacy.
Stochastic Quantization & Random Rotation (line 11-14). To lower the communication cost, the clients stochastically quantize the values in the update vectors to some discrete domain. Com- pared with real number encoding which costs 32 or 64 bits per dimension, the quantized value only requires log,(k) bits per dimension where k is the level of quantization (see line 12-14 in Algo- rithm I and McMahan et al. (2016) for detailed explanation.). On the other hand, quantization lowers the fidelity of the update vector and thus leads to some emror in estimating the mean of gra- dients. To lower the estimation error, the clients apply randomized rotation to the updates before quantization proposed by McMahan al. (2016). The details are discussed in Section
4

---

Under review as a conference paper at ICLR 2021
Discrete Gaussian Mechanism (line 15). We apply the discrete Gaussian mechanism to ensure DP. To determine the noise magnitude to added, we need to bound the lz-sensitivity (defined in Section (.2) of the gradient aggregate. Without quantization and random rotation, one could clip the individual gradient update and consequently the fz-sensitivity is just the clipping threshold. However, the inclusion of compression steps makes the analysis of fz-sensitivity more sophisticated. We provide the analysis of sensitivity and RDP guarantees for the entire algorithm in Section 5.2 Each client samples the noise from the discrete Gaussian distribution. In contrast to prior work where each client adds independent noise, we require the clients to share the same random seed, generate the same noise and add an average share of the noise in each round. This is because the sum of multiple independent discrete Gaussians is no longer a discrete Gaussian. Note that the same random seed is also required for communication reduction secure aggregation so we can conveniently reuse it here without introducing more further overhead (see Bonawitz et al. (2017) for details). The noise magnitude is set to ensure that the aggregate noise from all clients provides the global DP.
Algorithm 1: D2P-FED Protocol.
Input: Support Lattice: IL 26-T Z, Noise Scale:
Rotation Matrix: R, Random Seed:
Quantization Level: k, (x(x) = 2g 2gmaa
k-1
2g max
A-1
+
2-1
mod
-=1 ), is odd.
2
for i < [T] do
Server:
Sub-sample subset of clients S [n],|S] -y and broadcast w;-1 and g max
Client:
foreach client i E do Send usj to j. uij ~ UUni((L)) = f00==x000 EL, S 2=1
Client:
foreach client i do
Train the model w with w. as initialization
9t
W
/N Compute the difference //
lg 1
dllippedd
9: max(1,
/ clip the difference +/
It.rotated R (8)
(1)
Ii.clipped
/ Random Rotation +/
let b[r] = - mux + 2rg for every E k)
/+ Quantize +/
for j E d,, b(r) & L.
Di.quantizedlL] S b(r + 1] do (6)
9 rt - b[r]
Uggantizeelll
b/r +1++]
w.p.
bir + 1| b[r]
b/rl
gr.dp 9t Iuquniizeed
M 2 (o(())
/* Discrete Gaussian +/
9: (1) ( ( (g,dp)
Σ EjtiJEs Ui Σ Ejtiees Uza)
/x Mask */
Send g.
(i) the server
Server:
19
9: 77 Σ iE 9t
(
/ Aggregate
+/
20
w. w:- gt
Secure aggregation. (line 5,16,19) To reduce the noise magnitude for ensuring DP, we hide clients' individual updates from the central server and only allow it see the aggregated updates via the technique of secure aggregation. If the individual updates were available to the central server, they should also be protected with the same privacy guarantee as the averaged update; in this case, the required noise scales up with ((y)). On the other hand, if the central server can only access the aggregated updates, then the required noise is (1). Hence, secure aggregation of local updates can lead to significant noise reduction. However, there exists challenge for integrating secure aggrega- tion with discrete Gaussian mechanism: discrete Gaussian variables have infinite support, thereby incompatible with secure aggregation which operates on finite field. In Section 5.2 we propose to address this challenge by mapping the noised vector to cyclic additive group and then applying secure aggregation and show that the RDP guarantees are preserved under the mapping.
5

---

Under review as a conference paper at ICLR 2021
5.2 PRIVACY ANALYSIS
Before applying discrete Gaussian mechanism to DDP-FED, we need to figure out how to calibrate the added noise. In differential privacy, the calibration is guided by sensitivity of the function as defined below.
Definition 4 ((2=sensitivity). Given a function f :: R and two neighboring datasets D and D', the fz-sensitivity of J: A is defined as D5- maxp, ((D'))
In DP for deep learning, the traditional way to bound fz-sensitivity is to clip the update vector. However, quantization will further influence the sensitivity after clipping. We provide the sensitivity after quantization as below. The proof is delayed Appendix [ due space limitation.
Theorem 2. If we clip the l2 norm of g D, and quantize it to Vd + 1 levels, then the Eg sensifivity of the difference is 4D.
Given Theorem 1 and Theorem
we provide the RDP bound for D2P-FED. Corollary 3 (RDP for D²P-FED). Given the clipping bound D, the noise scale o, Follows (a, D -RDP.
Remark 1: Comparison with epSGD It seems unclear how to interpret the above bound when compared with Theorem in cpSGD (Agarwal et al. 2018). Indeed, the claim that DDP-FED has a better privacy guarantee than epSGD can be mainly justified by the following three aspects: (1) D'P-FED follows RDP which is a strictly stronger privacy notion than cpSGD which is intrisically limited to (e, 6)DP; (2) DEP-FED enjoys a tighter composition compared to cpSGD. This of critical significance in FL protocol with potentially thousands of rounds; (3) Our experimental results in Figure la also empirically show that D2P-FFDD enjoys tighter composition than epSGD. The total privacy budget for DDD grows much more slowly than cpSGD as training proceeds.
Remark 2: Privacy Effeet of Secure Aggregation. Corollary is built on the assumption that the centralized server only has access the summed updates but not the individual ones. If the centralized server has access to individual updates, the noise has to scale up yn times to maintain the same privacy guarantee which severely hinders the model accuracy. To consolidate the assumption, we leverage a cryptographic technique, secure aggregation (Bonawitz et al.) 2017) which guarantees that the centralized server can only the aggregated result. The basic intuition is to mask the inputs with random values canceling out in pairs. However, since discrete Gaussian has infinite support, we cannot directly apply random masks it. To reconcile secure aggregation with discrete Gaussian, we propose to project the involved values into a quotient group after shifting and then apply the random masks as shown in line 16 in Algorithm [ According the post-processing theorem of RDP [Mironov] (2017)). the result still follows rigorous Rényi differential privacy as proved Appendix [C] Note that we consider a simplified version of the full secure aggregation protocol (Bonawitz et al. (2017)) in Algorithm [ and omit many interesting details such as the generation of the random masks and how to deal with dropout. We deem this to be enough to clarify the idea behind the reconciliation. The complete version of secure aggregation can be reconciled using exactly the same trick.
Theorem 3 (Informal). Distributed discrete Gaussian mechanism with secure aggregation obeys the same RDP guarantee as vanilla global discrete Gaussian mechanism with the same parameters.
6 COMMUNICATION PROTOCOL & UTILITY ANALYSIS
In this section, we present our communication protocol detail and discuss the communication cost and the estimation error of D2P-FED with direct comparison to epSGD. The drastic improvement of D2P-FED mainly comes from the tight composition of discrete Gaussian mechanism compared to binomial mechanism in epSGD.
6.1 COMMUNICATION PROTOCOL
As the first step, we leverage stochastic k-level quantization proposed by McMahan et al. (2016) to lower the communication cost as described in line 12-14 in Algorithm | If we denote vanilla

---

Under review as a conference paper at ICLR 2021
stochastic k-level quantization with Tey then we successfully reduce the per-round communication cost C( n (d[log, k1 + ((1).
However, stochastic quantization sacrifices some accuracy for communication efficiency. Con- cretely, E (()) O 2 n Ei (او [Ig Since the dimension of parameters d is tens of thousands to hundreds of thousands in federated learning, the estimation error of the mean is too large. Thus to reduce the estimation error, we randomly rotate the difference vector (McMahan et al. 2016) as the second step. The key intuition is that the MSE of stochastic uniform quanti-
zation is O( (a With random rotation, we can limit gmax V log w.h.p. the MSE will be improved O (oogd) Agarwal al. (2018) also leverages random rotation reduce MSE. However, in their setting, random rotation intrinsically harms their privacy guarantee because the 20 -ennsitiivy might increase with rotation. A natural advantage of discrete Gaussian is that the privacy guarantee only depends on fg-sensitivity which is an invariant under rotation. Thus, random rotation does not harm our privacy guarantee at all. We omit the details here and refer the interested readers to McMahan et al. (2016). We denote the protocol using k-level quantization and random
rotation with [rat) We know that C( glrl) remains the same while the MSE error is reduced m
(rot) to {
o (n) O logd
1 E
l1g 122)
6.2 CONVERGENCE RATE OF D2P-FED
In this section, we relate the convergence rate with mean squared error using Corollary and analyze the mean squared eгrоr of mean estimation in D Note that we assume each client executes one iteration each round so g equals to the gradient or belongs to the sub-gradients.
Corollary 4 Ghadimi & Lan (2013)) Let F(w) F(w) be L-moohhh and Ye, VF w))l rounds
L(w, D) for some given distribution D. Let S Let w satisfy F(w") - F(w") I PF. Then after T
2pFL
2 2V2XV +pB pB
(Unif VF(w:)
T
VT
where X² maxigisT 2TE (w)) FF(ww)) maxigigr E
g(w,)113), and
B = max (l:) (w.) ğ( (w))l
As corollary Liddicates, for given gradient bound, the convergence rate approximately grows with the reciprocal MSE. Thus, we analyze D'P-FED's MSE and obtain the following theorem. The proof is delayed to Appendix due to space limitation.
Theorem 4. we choose 1/v 2m, the mean squared error is
ma(g) E M g)) ml) S 1 3c 2 (1- (1-)() n(k - 1)2 4 ?2n²
a²
(rat)
where &e is the cumulative distribution function (CDF) of the standard normal distribution.
Remark 1: Choice of max, As indicated by Theorem 4 the dominant term in MSE is pro- portional to the square of gm A natural choice of gamax is the clipping bound D. If we want log(d)
), we need to inherit their choice to match up with the MSE guarantee in cpSGD: O "n(k m(-=
of max = O(DV log(d) and this can be achieved by clipping Lo norm of the gradient after random rotation. For instance, according to Lemma 8 in Agarwal et al. (2018), we can choose g max log( 2nd DD
In that case, the possibility that the maximum of g exceeds max is at most follows that the possibility that the los -lipppigg really changes the update bounded by 5. Hence, the RHS of the MSE bound in Theorem 4 evolves to (1 1-3e- 2=2g (1 - ((ng)) 8)
/d
4dig maxx
+ (1 ((n(q- 1)) + 6) q². which is on the same order with the original
bound given 5 is small.
Remark 2: Comparison with epSGD. As the MSE bound is on the same order with epSGD (even the constants are close!), natural question is "what is the advantage of D2P-FED over epSGD in
7

---

Under review as a conference paper at ICLR 2021
terms of MSE?" Indeed, the advantage stems from smaller standard deviation of the noise. Given a fixed privacy budget, due to the tighter composition sub-sampled RDP (Wang et al. 2018). each round of D can have more privacy budget and thus smaller noise scale. Plugging smaller a into Theorem 4 will give a better MSE and thus a better convergence rate as epSGD follows a similar convergence rate bound. Moreover, according to Figure in Agarwal al. (2018). even with the same noise scale, Gaussian noise provides stronger privacy guarantee than Binomial noise. As discrete Gaussian noise follows the same RDP bound Gaussian noise, we believe discrete Gaussian can map the same-scale noise to lower privacy cost.
6.3 COMMUNICATION COST OF DOP-FED
First, we provide the trivial per-round communication cost which is exactly the same as epSGD. Theorem 5. The per-round communication cost of D22-FED is
ClT (o.M gl = n (dlog(nq + 1) + Ō(1)
Now let's compare the number of rounds in epSGD and DDP-FED qualitatively. Note that during the following discussion, we usually omit 5 for the of clarification and assume that is fixed. For cpSGD, the known tightest bound by the combination of standard privacy amplification (Balle) et al. 2018) and advanced composition (Dwork et al., (2110). Concretely, if mechanism costs pri- vacy budget, then after composed with sub-sampling the privacy budget is reduced to ((ye) where y is the sub-sampling rate. If the mechanism is composed sequentially T times, the privacy budget grows to O( (VVTII "oooool///// (1/8)e). Thus, the total privacy budget cpSGD O log((/))) On the other hand, D'P-FED provides total privacy budget of O(yvTe), saving a factor of Vlog(1/o). Since is typically very small, the saving is quite significant. If the privacy budgets for the two protocols are the same, then D2P-FED
use noise with O ((vlog(1//))) (1/5) smaller scale than epSGD each round. This will lead to a O (1o) faster convergence. Then for a given gradient bound, DED can reach with (log(1 (1/6)) /6))-time -tim fewer rounds and thus save (log(1 (00g((1))) --ime communication cost.
Both D2P-FED and epSGD intrinsically require secure aggregation to establish their privacy guar- antee. Agarwal et al. (2018) did not discuss the issue explicitly. As pointed out in Bonawitz et al.) (017). once combined with secure aggregation, each field has to expand at least yn times (7yn is the number of chosen clients) to prevent overflow of the sum.
7 EVALUATION
We would like to answer the following three questions using empirical evaluation: (1) How D FED performs in a multi-round federated learning compared to epSGD under either the same privacy guarantee the same communication cost? (2) How different choices of hyper-parameters affect the performance of D*P--EE? (3) Does D'P work under heterogeneous data distribution? Due to space limitation, present main results for (1) in this section and defer the results for (2) and (3) to Appendix E
7.1 EXPERIMENT SETUP
To answer the above questions, we evaluated DDP-FED and cpSGD on INFIMNIST (Bottou 2007 and CIFARI0 (Krizhevsky et al. (200)). We sampled 10M hand-written digits from INFIMNIST and randomly split the data among 100K clients. In each round, 100 clients are randomly chosen to upload their difference vectors to train a three-layer MLP. For CIFAR10, we select 10 out of 2000 clients in each round to train 2-layer convolutional network. All RDP bounds are converted to (c, 8DP for the ease of comparison and the total 8 is set to 1e-5 for all experiments.
7.2 MODEL ACCURACY VS. PRIVACY BUDGET
To answer the first question, we studied model accuracy under the same privacy budget as shown in Figure Ta Compared with epSGD), DPP-FED achieves 4.7% higher model accuracy INFIMNIST
8

---

Under review as a conference paper at ICLR 2021
Modd
rytch, byra Neaettracc
opt 1ight Poerr bypo
2007 Skyle
22500, Josns
D'PNeabio B201 20y10
Nartticaa bynts
INFIMNIST
CIFARIO
INFIMNIST
CIFARIO
(a) Privacy Budget vs. Model Accuracy.
(b) Communication Cost Model Accuracy,
Figure I: D²P-FED vs. epSGD.
and 13.0% higher model accuracy on CIFAR1O after convergence. As expected, D2P-FED com- poses far tighter under sub-sampling as the lines are much sharper than those of cpSGD. Conse- quently, D converges at a smaller privacy budget than cpSGD as well. Although in Figure la epSGD has better accuracy in the high privacy region, is necessarily the case but depends on the scale of the discrete Gaussian noise, as studied in Section E. Note that the results for cpSGD in Figure different from the results in Figure 2 in the original paper (Agarwal et al. 2018). The rea- son is that in the original paper, they do not sub-sample clients in each round but assign each client exactly one round beforehand to avoid composition which epSGD cannot handle well. However, the scheme is far from practical in the real world due the dynamic nature of the clients.
7.3 MODEL ACCURACY COMMUNICATION COST
To answer the second question, we also studied the model accuracy under the same communication cost. As shown Figure Ib DPP-FED consistently achieves better model accuracy under the same communication cost on both INFIMNIST and CIFARIO. The main reason is that the tight composition property allows D2P-FED to use smaller per-feature communication cost while still achieving better accuracy. As concrete instance, D2P-FED with 50% compression rate achieve better accuracy than epSGD with 25% compression rate. cpSGD with 50% compression rate either leads to unacceptable privacy budget does converge.
CONCLUSION
In this work, we developed D2P-FED to achieve both differential privacy and communication ef- ficiency in the context of federated learning. By applying the discrete Gaussian mechanism to the private data transmission, D'P-FED provides stronger privacy guarantee, better composability and smaller communication cost than the only prior work, epSGD, both theoretically and empirically.
REFERENCES
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan Yu, Sanjiv Kumar, and Brendan McMa- han. cpsgd: Communication-effee and differentially-privvee distributed sgd. In Advances in Neural Information Processing Systems, pp. 7564-7575, 2018
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in neural information processing systems, pp. 1756-1764, 2015.
Maria Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. Distributed learning, commu- nication complexity and privacy. In Conference on Learning Theory, pp. 26-1, 2012.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, pp. 6277-6287, 2018.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Kamn Seth. Practical secure aggregation for privacy-

---

Under review as a conference paper at ICLR 2021
preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference Computer and Communications Security, pp. 1775-1191, 2017.
Leon Bottou. The infinite mnist dataset. 2007.
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy, arXiv preprint arXiv:2004.00010, 2020.
Jiecao Chen, He Sun, David Woodruff, and Qin Zhang. Communication opttial distributed clus- tering. In Advances in Neural Information Processing Systems, pp. 3727-3735, 2016.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 5/st Annual Symposium on Foundations of Computer Science, pp. 51-60. IEEE, 2010.
Robin Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv: 17Xiv:171..07557, 2017.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-2366) 2013.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-presevving empirical risk minimization. In Advances in Neural Information Processing Systems, pp. 6343-6354, 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
2009.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et Communication efficcient learning of deep networks from decentralized data. arXiv preprint arXiv:1602.05629 2016.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint 9rXiv:1710.06963 2017.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Sym- posium (CSF), pp. 263-275. IEEE, 2017.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE Symposium on Security and Privacy (SP). pp. 739-753. IEEE, 2019.
Anastasia Pustozerova and Rudolf Mayer. Information leaks federated learning.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International Conference on Machine Learning, pp- 3329-3337, 2017.
2017.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach privacy-preserving federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pp. 1-11,2019.
John N Tsitsiklis and Zhi-Quan Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3):231-243 1987.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. arXiv preprint arXiv:2002.06-440. 2020.
Yu-Xiang Wang, Borja Balle, and Shiva Kasiviswanathan. Subsampled r\ 'enyi differrnnial privacy
and analytical moments accountant. arXiv preprint arXiv: 00087, 2018.
Wikipedia. Theta function - wikipedia, the free encyclopedia.
URL https:
wi wikipedi httg//wii/Thetaaa wwttttttaaaaeeeeeeeeeeaaae fictt_ffuuiioo
10

---

Under review as a conference paper at ICLR 2021
Chulin Xie, Keli Huang, Pun-Yu Chen, and Bo Li. Dba: Distributed backdoor attacks against feder- ated learning. In International Conference on Learning Representations, 2019.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learn- ing: Analyzing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pp. 268-2822 282. IERE, 2018.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, and Nghia Hoang. Sta- tistical model aggregation via parameter matching. Advances in Neural Information Processing Systems, pp. 10956- 10966, 2019a.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Trong Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. arXiv preprint arXiv: /2022, 2019b.
Yuchen Zhang, John Duchi, Michael Jordan, and Martin Wainwright. information-theorer lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems, pp. 2328-2336, 2013.
A PROOF FOR THEOREM
We consider the Rényi divergence between discrete Gaussian distributions differing in the mean value.
Proof.
1
log
Et. exple - 11)2/(20)) exp(-aa² /20²)) exp(-(1 (1)((( -n)//////000 (202)
log
Σ @exp((=20 2(1 a)ue (1 - o))
Σt. expppp(x 11)2 12)2/(202))
(2) 1
log(exp((a²- (202)) (2))))))2)))
a a-
= 0//2/(20 (200)
(I) Because range(f) C L, we only consider E LL. Thus the denominator of N2 and (L, o?) cancels out as Σn exp(-(x - 2)2/(20²)) is periodic. (2)
E1 (xxx)(-(2_))7((20))
(Fi((1 -o)mp.e- < where is the Jacobi theta function (Wikipedia).
(0,5)
B PROOF FOR THEOREM
Proof. The la sensitivity of 8 is naturally bounded by 2D, The rotation does not change the sensi- tivity. The k-level quantization might expand the space as shown in Figure 2 An upper bound on the radius of the red circle is + vd When we take = vd reduces to 2D. Thus, the upper bound on sensitivity is 4D.
C PROOF FOR THEOREM
We first prove the following lemma.
11

---

Under review as a conference paper at ICLR 2021
clipped gradient space quantized gradient space
Figure 2: Sensitivity after Quantization.
Lemma 3.
Σ [x)(x) 2g
25(E²1 x)
Proof.
Σ [x(())
Σ max
1
9 9-1
mod 9
9-1 1
k
mgx
2g max
k
q 8-1
9 - 2
x + 2
mod
2gi
0g x))
Then we prove Theorem as follows.
Proof. Given Lemma
3
(1)
g:
gt
d
(1)
Σ Uij
Σ
Ujii)
iE9
jFiJES
jfi.EES
Σ j#ijES
Uij
Σ
(;;))
j#ijES
dg
91.dp
ES
The expression Eies It.dp forms centralized discrete Gaussian mechanism and according to the post-processing theorem, the same RDP guarantee still holds.
D PROOF FOR THEOREM
Proof Sketch. Before starting the proof, we introduce two lemmas for the proof.
Lemma (Proposition 19 from Canonne et al. 20200). For all a E IR with o > 0,
4
V(Na(0, < o2
- < o
Moreover, of 1. then V[Nz(0,03)] 53.
+
12

---

Under review as a conference paper at ICLR 2021
Lemma 5 (Proposition 23 from Canonne et al. (2020)) For all m Z with 2 1 and all E R with 0 > 0,
Px,N210,02) [X 2 m| S Px [X m
Moreover if 2 1/V2T, we have
P Px~N300.0)1X 1+ 3e 2n2a2 Px Px~N(0,02)X ml
Now start proof. MSE can be rewritten in the following format.
Bi| 1121
1
-(((,))))()))
n j=l
For each Lemma
(x,()) we need to consider two cases. If overflow happens, due
E(( 2X ) (V(Ber(p, V(NL()))
4(xmax)2
o²
(
(k: 1)2 4
22
If overflow happens, trivially we have I 2.2 Thus, we have
P[-o] *-o + P(o] * I (x [X 9) *-o + Px 2 kk] -
With Lemma we can bound the probabilities and get the final MSE result in the theorem.
E OTHER EVALUATION
E.1 INFLUENCE OF NOISE SCALE
100
Accuracy
D*P-FED (a 0.6), bytes
D*P.FED (rr 0.8 bytes
DPP-FED byses
Non-Privare, bytes
2-1
21 Budget
Figure D²P-FED under different
The hyper-parameter of the most vital interest in D²P-FED is the scale of the noise. To understand the effect of the noise scale, we evaluated D2P-FED on INFIMNIST, with 3 different choices of noise scale as shown in Figure 3 It is no surprise that the higher the noise scale, the smaller the privacy budget and the lower the model accuracy. This also illustrates the claim we have in Section 7.2 that D'D can also have relatively good performance in the high privacy region at the cost of the model accuracy.
E.2 INFLUENCE OF HETEROGENEOUS DATA DISTRIBUTION
well known that data is sometimes heterogeneously distributed among clients federated learning system. Thus, to better understand D FED'ss behavior under heterogeneous data distribu- tion, we simulated heterogemenous data distribution by distributing the INFIMNIST data according to the classes and evaluated D"P-FED on these clients. The results are shown in Figure 4 and we can see that under heterogeneous data distribution the model accuracy drops by more than 10%. This complies with the previous empirical results and there have been line of researches focusing on addressing the issue (Yurochkin et al., 22199a b. Wang et al.] 2020). Although orthogonal to this paper, we deem it interesting open problem how integrate these works with D2P-FED.
13

---

Under review as a conference paper at ICLR 2021
100
Model Accumey
60
D7P-PEU
4.5 Budget
5.5
Figure 4: DOP-FED under homnggenccou/hheeeeggennssss distribution.
E.3 INFLUENCE OF GROUP SIZE 4
We also ran D'P-FED with multiple choices of discrete group size q. We observe that once the noise scale fixed, the performance is relatively robust to g.
100
Model Accunacy
80
byses
DPP-Pau (o 0.6), 3 bytes
byses
Non-Private. 4 bytes
20
60
80
100
#Bound
Figure 5: D2P-FED under different group size
14


Reviews:
[{"review_id": "aoeg7d6_eUz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose D2P-FED to achieve differential privacy and communication efficiency in FL tasks. The framework is interesting and the problem studied is important. However, this paper suffers from some major deficiencies. \n\nMajor comments:\n\n1) It is claimed that the privacy guarantee for D2P-FED is better than that of cpSGD. However, this is not substantiated after the privacy results of Theorem 5. Furthermore, the bound here depends on D, the clipping threshold on the l_2 norm of g, which clearly affects the privacy guarantee per Theorem 5. \n\n2) The algorithm here depends on the lattice being defined as 2g^{max}/(k-1) Z. It is not clear how one can set the g^{max} in practice. The differences of the parameters w_t are generated on the fly for each client. Thus, this algorithm has limited applicability in practice. \n\n3) Similarly to point 1), it is not clear in what way the communication cost is better than that of cpSGD. From the convergence result in Theorem 7, it seems like there is no improvement. Further, g^{max} needs to be set in a very specific way that is dependent on D and d, which is again not known in practice. So whether we can attain the convergence rate is unclear. \n\n4) The authors acknowledge in their experiments that the results are sensitive to the scale of the discrete Gaussian noise. Hence, the privacy-communication cost-convergence rate tradeoff is not clearly delineated. \n\nMinor comments:\n\n1) The writing is not sufficiently precise and clear. For example, before the statement of Thm 1, it is mentioend that the proof is delayed to Appendix A. However, the proof of Thm 1 is not provided therein. Rather the proof of Thm 3 is in that appendix. The proof of Thm 4 in Appendix B is not sufficiently precise. It is not clear what the authors mean by \"expand the space a little bit\". How much is \"a little bit\"? Since this is a \"theorem\", the proof should be watertight. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "a8S6qKUyXZ0", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThis paper proposes to use a discrete gaussian distribution the generate noise for differential privacy.\nWhile it is claimed that the discrete Gaussian distribution is better than the binomial distribution, no in-depth comparison is made.  The discrete Gaussian distribution, a discretized version of the Gaussian distribution, works as expected, and provides all properties the Gaussian distribution provides (if the discretization is sufficiently fine-grained).\nAn advantage is that the communication cost can be reduced by stochastic quantization of the values to be transmitted.  It is unclear whether the same stochastic quantization technique can be used for the classic Gaussian distribution.\nThe ideas of discretizing, of stochastic quantization to reduce communication cost, and the use of discrete distributions for differential privacy are all already known, the (limited) novelty is in the proper combination of these ideas.\nThe text is understandable for readers who know already the meaning of all symbols and names used, but a broader audience could be reached by properly introducing all concepts and notations in an understandable, coherent and self-contained way.  This would be valuable, even if it would mean that some more technical elements would need to be moved to an appendix.\n\n\nIn conclusion, while the idea is interesting, I have some concerns with the presentation and the insufficiently motivated novelty (and the related lack of more in-depth comparison with existing work).\n\n\n* The paper points to a few shortcomings in the literature, but exaggerates their importance.  E.g., when the text says \"However, cpSGD faces several limitations when applied to real-world applications. Firstly, with Binomial noise, the output of a learning algorithm would have different supports when any client participates or withdraws from learning\", it may be true this is the case when literally considering the cpSGD paper, but such problem typically can be overcome easily.  When the text concludes \"can only guarantee approximate DP where the participation of the client can be completely exposed with nonzero probability.\" I guess \"approximate DP\" means (epsilon,delta)-differential privacy where delta is strictly larger than zero (which is usually anyway already the case for Gaussian and binomial mechanisms).\n\n* Definition 3: I wonder why the numerator and denominator of the exponent in the probability e^{-\\pi x^2/(2\\pi\\sigma^2)} both contain \\pi and this fraction isn't simplified.\n* Definition 3: please clarify what kind of \"discrete additive subgroup\" you have in mind: is it a finite group (where addition is possibly modulo the group order) or is it a multiple of the set of integers \\mathbb{Z} ? (much later in the paper, it becomes increasingly clear that the latter option is the correct one)\n* Section 5.1: please explain the meaning of all used variables at their first use. E.g., the k in an expression log(k) isn't explained, until Section 6.1 cites another work for the meaning of k-level quantization (without even explaining the gist of quantization idea briefly).\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RBksuMjFVvT", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\n \nThe paper proposes the discrete Gaussian based differentially private federated learning algorithm to achieve both differential privacy and communication efficiency in federated learning. In particular, it adds discrete Gaussian noise into client updates and uses secure aggregation to prevent the server from observing the individual updates. The algorithm satisfies RDP and has lower communication cost compared to the previous method cpSGD.\n\n##########################################################################\n\nReasons for score: \n \n I like this work. 1. The problem is critical in federated learning. The D2P-Fed algorithm has nice performance on the trade-off among privacy, utility, and communication cost. 2. It has several algorithmic novelties. To employ secure aggregate, it's natural to use a mechanism with discrete support (or discretize that). The discrete Gaussian mechanism is indeed a better candidate than the binomial mechanism. But there is much more beyond a simple combination of the discrete Gaussian mechanism and secure aggregation. They use several other techniques, such as stochastic quantization and random rotation. The mapping to a cyclic additive group is novel. 3. They provide strong theoretical guarantees and empirical validation.\n\n##########################################################################\nMinor comments:\n\n1. In Section 3 under FL Overview, I don't think $k$ is clearly defined. I guess $k=\\gamma n$. It is also confusing in Algorithm 1. It should be clearly defined. The same for $d$ in Algorithm 1. \n\n2. The probability $g[j]-b[r]/b[r+1]-b[r]$ doesn't seem make sense. Like if $g[j]=b[r+1]$, it will be set to $b[r]$ with probability 1. Should it be $1-(g[j]-b[r]/b[r+1]-b[r])$?\n\n3. In Figure 1(b), the x-axis should be communication cost for CIFAR10.\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-7hEkhI8I4v", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a privacy-preserving federated learning algorithm with efficient communication. To save communication costs, they integrate stochastic quantization and random rotation. Moreover, they apply the discrete Gaussian mechanism with Renyi DP analysis for privacy guarantee.\n\n\nNovelty & Significance\n-----------------------------\n\nSolving federated learning with a privacy guarantee is of increasing practical importance, and certainly trying to do so with efficient communication efficiency is more important.\n \nThe RDP analysis for discrete Gaussian mechanism is nice, which allows a tighter composition with analytical moments accountants.\n\n\nTechnical concern:\n-----------------------------\n\n I have concerns regarding the claim ''D2P-FED is more communication efficient compared to cpSGD'' due to a $log(1/\\delta)$ factor in big O. Note that constant matters in differential privacy. Without knowing other constants hidden in big O, I feel hard to follow the conclusion there.\n\n\nExperimental Evaluation:\n----------------------------\n\nMy major concern is that empirical evaluation is limited.\n(1) In Figure 1, three methods use different quantization. There lacks clarification on the choice of bytes.  Moreover, it would be much better to add a non-private baseline without quantization.\n(2) Noting the privacy budget greater than 10 is no longer meaningful; it may be better to focus on the practical privacy regimes in Figure 1 (a).\n(3) In Figure 1 (b), is the privacy budget aligned? If not, how to set the noise scale for cpSGD and D2P-FED?  Is it possible to align both the privacy budget and communication cost? For example, the per-round communication is the same for both algorithms with the same bytes. Set the x-axis to be the communication cost, the privacy cost is fixed for all points, and the y-axis reports the model accuracy.\n(4) INFIMNIST and CIFAR10 are still two toy datasets. Perhaps authors can add more experiments with real-world datasets in the next version.  \n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers differentially private federated learning --- a well-motivated problem. The proposed algorithm is a simple modification to existing methods, e.g., DP-FedAvg, but uses a different DP mechanism for noise-adding.  The reviewers liked the motivation but criticized the work for its incremental nature and for somewhat overselling the contributions.

Pros:

- The paper used advanced Renyi DP accounting to get a stronger privacy-utility tradeoff.

- The experimental results improve over cp-sgd that uses Binomial mechanisms

Cons: 

- It is a bit incremental in its contribution.  The main contribution is to applying "discrete Gaussian mechanism" to the federated learning problem for the interest of reducing the communication cost.   Discrete Gaussian mechanism and its RDP analysis are both from existing work.

- The improvement in privacy-utility tradeoff over cp-sgd seems to be due to that the discrete Gaussian mechanism has an RDP bound, which plugs right into the subsampling bound and moments accountant.    It is unclear whether the improvement is coming from the different noise or a stronger privacy accounting.  Notice that the privacy accounting of Binomial mechanism in the initial cp-sgd paper was rather crude, thus a fair comparison would be to also conduct an RDP analysis for the Binomial mechanism.  

Overall, there weren't sufficient support among the reviewers and the experimental results alone are not so groundbreakingly strong to carry the paper single-handedly.

Decision: Reject