Voting-based Approaches For Differentially Private Federated Learning
Authors: Yuqing Zhu
Xiang Yu
Yi-Hsuan Tsai
Francesco Pittaluga
Masoud Faraki
Manmohan Chandraker
Yu-Xiang Wang
Venue:  (2021)

Abstract: While federated learning (FL) enables distributed agents to collaboratively train a centralized model without sharing data with each other, it fails to protect users against inference attacks that mine private information from the centralized model. Thus, facilitating federated learning methods with differential privacy (DPFL) becomes attractive. Existing algorithms based on privately aggregating clipped gradients require many rounds of communication, which may not converge, and cannot scale up to large-capacity models due to explicit dimension-dependence in its added noise. In this paper, we adopt the knowledge transfer model of private learning pioneered by Papernot et al. (2017; 2018) and extend their algorithm PATE, as well as the recent alternative PrivateKNN (Zhu et al., 2020) to the federated learning setting. The key difference is that our method privately aggregates the labels from the agents in a voting scheme, instead of aggregating the gradients, hence avoiding the dimension dependence and achieving signiﬁcant savings in communication cost. Theoretically, we show that when the margins of the voting scores are large, the agents enjoy exponentially higher accuracy and stronger (data-dependent) differential privacy guarantees on both agent-level and instance-level. Extensive experiments show that our approach signiﬁcantly improves the privacy-utility trade-off over the current state-of-the-art in DPFL.

Under review as a conference paper at ICLR 2021
VOTING-BASED APPROACHES FOR DIFFERENTIALLY PRIVATE FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
While federated learning (FL) enables distributed agents to collaboratively train a centralized model without sharing data with each other, fails to protect users against inference attacks that mine private information from the centralized model. Thus, facilitating federated learning methods with differential privacy (DPFL.) becomes attractive. Existing algorithms based on privately aggregating clipped gradients require many rounds of communication, which may not converge, and cannot scale up to large-capacity models due to explicit dimension-deper dependence in its added noise. In this paper, we adopt the knowledge transfer model of pri- vate learning pioneered by Papernot et al. (2017; 2018) and extend their algorithm PATE, as well as the recent alternative KNi (Zhu et al., 2020) to the fed- erated learning setting. The key difference is that our method privately aggregates the labels from the agents in voting scheme, instead of aggregating the gradi- ents, hence avoiding the dimension dependence and achieving significant savings in communication cost. Theoretically, we show that when the margins of the vot- ing scores are large, the agents enjoy exponentially higher accuracy and stronger (data-dependent) differential privacy guarantees on both agent-level and instance- level. Extensive experiments show that our approach significantly improves the privacy-utility trade-off over the current state-of-the-ard in DPFL.
INTRODUCTION
With increasing ethical and legal concerns on leveraging private data, federated learning (McMahan et al., 2017) (FI.) has emerged as a paradigm that allows agents to collaboratively train a central- ized model without sharing local data. In this work, we consider two typical settings of federated learning: (1) Local agents are in large number, i.e., learning user behavior over many mobile de- vices (Hard et al., 2018). (2) Local agents are in small number with sufficient instances, i.e., learning a health related model across multiple hospitals without sharing patients' data (Huang et al., 2019).
When implemented using secure multi pallt- computation (SMC) (Bonawitz et al., 2017), federated learning eliminates the need for any agent to share its local data. However, it does not protect the agents or their users from inference attacks that combine the learned model with side information. Extensive studies have established that these attacks could lead to blatant reconstruction of the pro- prietary datasets (Dinur & Nissim, 2003) and identification of individuals (a legal liability for the participating agents) (Shokri et al., 2017). Motivated by this challenge, there had been number of recent efforts (Truex al., 2019b; Geyer et al., 2017; McMahan al., 2018) in developing federated learning methods with differential privacy (DP), which is a well-established definition of privacy that provably prevents such attacks.
Among the efforts, DP-FedAvg (Geyer et al., 2017; McMahan et al., 2018) extends the NoisySGD method (Song et al., 2013; Abadi et al., 2016) to the federated learning setting by adding Gaussian noise to the clipped accumulated gradient. The recent state-of-the-an DP-FedSGI (Truex et al., 2019b) is under the same framework but with per-sample gradient clipping. A notable limitation for these gradient-based methods is that they require clipping the magnitude of gradients to and adding noise proportional to F to every coordinate of the shared global model with d parameters. The clipping and perturbation steps introduce either large bias (when is small) or large variance (when is large), which interferes the SGD convergence and makes it hard to scale up to large- capacity models. In Sec. 3, we concretely demonstrate these limitations with examples and theory.

---

Under review as a conference paper at ICLR 2021
Particularly, we show that the FedAvg may fail decrease the loss function together with gradient clipping, and De-FedAvg requires many outer-loop iterations (i.e., many rounds of communication to synchronize model parameters) to converge under differential privacy.
To avoid the gradient clipping, we propose to conduct the aggregation over the label space, as shown to be effective approach in standard ( learning settings, i... voting-base based model- agnostic approaches (Papernot et al., 2017: 2018; Zhu et al., 2020). To achieve it, we relax the traditional federated learning setting to allow unlabeled public data the server side. We also consider a more complete scenario for federated learning, where there are a large number of local agents or a limited number of local agents. The agent-level privacy introduced in DP-FedAvg, works seamlessly with our setting having many agents. However, when there are few agents, hiding each data belonging to one specific agent becomes burdensome or unnecessary. To this end, we provide a more complete privacy notion, i.e., agent-level and instance-level. Under each of the setting, we theoretically and empirically show that the proposed label aggregation method effectively removes the sensitivity issue caused by gradient clipping or noise addition, and achieves favorable privacy-utility trade-off compared to other DPFL algorithms.
Our contributions are summarized as the following:
1. We propose two voting-based DPFL. D algorithms via label aggregation (PATE-FL. and Private- KNN-FL) and demonstrate their clear advantages over gradient aggregation based DPFL methods (c.g., DP-FedAvg! in terms of communication cost and scalability to high-capacity models.
2. We provide provable differential privacy guarantees under two levels of granularity: agent- level DP and instance-level DP. Each is natural in a particular regime of FL depending on the number of agents and the size of their data.
3. Extensive evaluation demonstrates that our method improves the privacy-utility trade-off over randomized gradient- based approaches in both agent-level and instance-level cases.
remark of our novelty. Though PATE-FL and -Ni-ate- are algorithmically similar the original PATE (Papernot et al., 2018) and Private-KNN (Zhu et al., 2020), they are not the same and we are adapting them new problem - federated learning. The adaptation itself is nontrivial and requires substantial technical innovations. We highlight three challenges below.
Several key DP techniques that contributed to the success of PATE and Private-KNN in the standard setting are no longer applicable (e.g., Privacy amplification by Sampling and Noisy Screening). This is partly due to that in standard private learning, the attacker only sees the final models; but in FL, the attacker can cavesdrop all network traffic.
Moreover, PATE and Private-kNN only provide instance-level DP. We show PATE-FL and Private-kNN-FL. also satisfy the stronger agent-level DP. PATE-FL's agent-level DP param- eter is, surprisingly, factor of 2 better than its instance-level DP parameter. And Private- kNN-FL in addition enjoys a factor of k amplification for the instance-level DP.
A key challenge of FL is the data heterogeneity of individual agents, while PATE randomly splits the dataset so each teacher is identically distributed. The heterogeneity does not affect our privacy analysis but does make it unclear whether PATE would work. We are the first to report strong empirical evidence that the PATE-style DP algorithms remain highly effective in the non-iid case.
PRELIMINARY
In this section, we start with introducing the typical notations of federated learning and differential privacy. Then, two randomized gradient-based baselines, DP-FedAvg and DP-FedSGD, are intro- duced as the DPFL background.
2.1 FEDERATED LEARNING
Federated learning (McMahan et al., 2017; Bonawitz et al., 2017; Mohassel & Zhang, 2017; Smith et al., 2017) is a distributed machine learning framework that allows clients to collaboratively train a global model without sharing local data. We consider N agents, each agent has n, data kept locally
2

---

Under review as a conference paper at ICLR 2021
Server
Server
Server
Pullic
Server
Public
Public Feature Extractor
ciopetan
SMC
SMC
Pubblic nota
Notley Labho
SMC
Roil Labee
Pobiic
Pubble Data
Noily Huiley Lebets
SMC
Pubbic
fv(-)
Model
SGD
Nolsy
Private Data
f1
fnC
Agent
Agent N
Agent
Agent
Agent 1
Agent
Agenc 1
Agemt
DP-FedAvg Figure 1: DP-FedAvg and PATE-FL are used for agent-level DP. DP-FedSGD and Private-kNN-FL. are used for instance-level DP.
DP-FedSGD
PATE-FL
Private-kNN
and privately from a party-specific domain distribution D, C' is the number classes. The objective output global model that performs well the target (server) distribution. Most prior works consider the target distribution as a uniform distribution over the union of all local data, which is restrictive in practice. Here we consider an agnostic federated learning scenario (Mohri al., 2019; Peng et al., 2019c), where the server distribution De can be different from all agent distributions. In light this, we assume each agent has access to part of unlabeled server data drawn from the target distribution De.
FedAvg (MeMahan al., 2017) is a vanilla federated learning algorithm that we consider as a non-DP baseline. In this algorithm, a fraction of agents is sampled at each communication round with a probability q. Each selected agent downloads the shared global model and improves it by learning from local data using E iterations of stochastic gradient descent (SGD). We denote this local update process as an inner loop. Only the gradient is sent to the server, where it is averaged with other selected agents' gradient improve the global model. The global model is learned after communication rounds, where each communication round denoted as one outer loop.
2.2 DIFFERENTIAL PRIVACY FOR FEDERATED LEARNING
Differential privacy (Dwork et al., 2006) is quantifiable and composable definition of privacy that provides provable guarantees against identification of individuals in a private dataset.
Definition 1. A randomized mechanism M D + R with a domain 'D and range R satisfies (e. differenntall privacy, for any two adjacent datasets D, D' DD and for any subset of outputs S S R, it holds that Pr(M(D) E S] < PriiM(D") E S] S] 8.
The definition applies to variety of different granularity, depending how the adjacent datasets are defined, i.e., if we are to protect whether one agent participates into training. the neighboring datasets defined by adding removing the entire local data within that agent. It is known as agent-level (user-level) differential privacy, which has been investigated in DP-FedAvg (Geyer et al., 2017; McMahan al., 2018). Compared FedAvg, DP-FedAvg (Figure enforces clipping of per- agent model gradient to threshold S' and adds noise to the scaled gradient before it is averaged at the server. Note that this DP notion is favored when data samples within one agent reveal the same sensitive information, c.g., cell phone agents send the same message.
However, when there are only a few agents, hiding the entire dataset from one agent becomes difficult and inappropriate. We then consider the instance-level DP, where the adjacent dataset is defined by differing one single training example. This definition is consistent with the standard non-federated learning differential privacy (Abadi et al., 2016; Bassily et al., 2014; Chaudhuri et al., 2011). Model training with instance-level DP restricts the adversary's power detecting a specific training instance's presence or absence. DP-FedSGD (Truex al., 2019a; Peterson et al., 2019), one such state-of-the-ar for the instance-level DP, performs NoisySGD (Abadi et al., 2016) for fixed number of iterations each agent. The gradient updates averaged each communication round at the server, as shown in Figure 1.
SMC is cryptographic technique that securely aggregates local updates before the server receives it. While SMC does not have a differential privacy guarantee, it can be combined with DP to amplify the privacy guarantee (Bhowmick al., 2018; Agarwal et al., 2018 8; Truex al., 2019b) against attackers
3

---

Under review as a conference paper at ICLR 2021
that eavesdrop what sent by each agent. In our experiment, assume that the aggregation is conducted by SMC for all prevacy-pesservngg algorithms that we consider.
3 CHALLENGES FOR GRADIENT-BASEE FEDERATED LEARNING
In this section, we highlight the main challenges of the conventional DPFL frameworks in terms of accuracy, convergence and communication cost. For other challenges, we refer the readers to survey (Kairouz et al., 2019). The details of DP-FedAvg are summarized in appendix algorithm section.
3.1 CHALLENGE 1: BIASED GRADIENT ESTIMATION
Recent works (Li et al., 2018) have shown that the FedAvg may not converge well under heterogene- ity (e.g., non-identical distributions). Here, we provide simple example show that the clipping step of DP-FedAvg may raise additional challenge.
Example (clipping). Let N = 2, each agent i's local update is As (E iterations of SGD). We
enforce clipping of per-agent update D; by performing /i/ max( 1, [&l,le), ). where is the clipping threshold. Consider the special case when ||Ail|2 = ++ and [A S v. Then the global update
will be )( TA.
- + A22), which is biased.
The unbiased global update shall be (4) + D2). Such simple example can be embedded in more realistic problems, causing substantial bias that leads non-convergence.
3.2 CHALLENGE 2: SLOW CONVERGENCE
Recent works (Li et al., 2019; Wang et al., 2019) have investigated the convergence rate in FL methods. Here, we draw connections to DP-FedAvg's convergence rate and demonstrate that using many outer-loop iterations (T) could have a similar convergence issue under differential privacy.
When E = 1 in the local update (inner loop), the FedAvg algorithm is equivalent to SGD with distributed data, which requires many rounds of communication. The appeal of FedAvg is to set E to be larger that each agent performs E iterations to update its own parameters before synchro- nizing the parameters to the global model, hence reducing the number rounds communication. However, setting E may not improve convergence at all.
Now, we take a closer look at the effect of increasing E in the case of piecewise lincar functions. Let v be the learning rate for individual agents. In appendix convergence section, establish that the effect of increasing E is essentially increasing the learning rate for a large family of optimization problems with piecewise linear objective functions. It is known that for the family of G Lipsschhiz functions supported on B--bounded domain, any Krylov-space method has a rate of convergence that is lower bounded by S2 (2BG/vT (Nesterov, 2003, Section 3.2.1). This indicates that the variant of FedAvg that aggregates only the loss function part the gradient or projects only when synchro- nizing requires ((1/a²) rounds of outer loop (i.c., communication), in order to converge to an a stationary point, i.e., increasing E does not help, even if no noise is added.
This also says that De-FedAvg is essentially the same stochastic subgradient method in almost all locations of piecewise linear objective function with gradient noise being (0, o² /N The additional noise in DP-FedAvg imposes more challenges to the convergence. If we plan to run T logg//
rounds and achieve (e, DD-, we need to choose et al., 2018, Thcorem 1). which results in a convergence rate upper bound of
(see, e.g., McMahan
GB(
2T log( 1.25/8)
N
GB
v /log(1.25//))
Ne
for an optimal choice of the learning rate Em,.
One that outputs solution in the subspace spanned by sequence of subgradients.
4

---

Under review as a conference paper at ICLR 2021
The above bound is tight for stochastic subgradient methods, and in fact also information- theoretically optimal. The GB/VT part of upper bound matches the cetemmttiiotthooetice lower bound for all methods that have access to T'calls of stochastic subgradient oracle (Agarwal et al., 2009, Theorem 1). while the second matches the cooommtiion-teoretiicn lower bound for all (c, 5)- differentially private methods on the agent level (Bassily et al., 2014, Theorem 5.3). That is, the first term indicates that there must be many rounds of communications, while the second term says that the dependence in ambient dimension d is unavoidable for DP-FedAvg. Clearly, our method also has such dependence the worst case, but it is easier for our approach adapt to the structure that exists in the data (i.c.. high consensus among voting), as we will illustrate later. In contrast, it has larger impact on DP-FedAvg, since it needs to explicitly add noises with variance (2(d).
Another observation is that when N is small, no DP method with reasonable c, ô parameters is able to achieve high accuracy. This partially motivates us to consider the other regime that deals with instance-level DP.
3.3 OTHER CHALLENGES
Expensive Communication Cost: Up-stream communication cost (Konečný et al., 2016), i.e., to- tal transmitted updates from local agent to server, is another key concern in FL. For FedAvg, our convergence analysis suggests that increasing F does not speed up the convergence. nication cost is expected till the model converges. CpSGD (Agarwal et al., 2018) is another DPFL. method, aiming at reducing the communication cost by gradient quantization with binomial noise. However, sampling from binomial distribution can be difficult devices, which prevents it from being practical real-world scenarios.
high commu-
Network Complexity: DP-FedAvg requires to clip gradient magnitude to r at each coordinate in parameters, which is hard to scale up to large models, as the noise level increases proportional to the network capacity. To address this issue, recent works apply delicate clipping strategies (McMahan et al., 2018; 8; Geyer et al., 2017) and reduce data dimension with PCA (Abadi et al., 2016). In this work, we propose avoid such dimension dependence and empirically investigate how network architecture affects performance in various DPFL approaches.
ALGORITHM
We assume there are unlabeled data drawn from De at the server, which public and accessible from any agent. The goal is design (e, dDD algorithm (either on the agent-level instance- level) that outputs pseudo-labels for a subset of server's s unlabeled data, Then a global model is trained in semi-supervised way, using pseudo-labeled and unlabeled data.
PATE-FL In PATE-FL (Algorithm 1), each agent trains a local "teacher" model fi using its own private local data. For each "student" query 22, every agent adds Gaussian Noise to her prediction (i.e., C-dim histogram), aggregates their noisy predictions via SMC and the label with the most votes is returned the server the "pseudo-label" of vt. Similar the original PATE, the idea behind the privacy guarantee is that by adding or removing any instance, it can change at most one agent's s prediction. The same argument also naturally applies to adding or removing one agent. In fact we gain a factor of 2 in the stronger agent-level DP due to a smaller sensitivity (see the proof for details)! Another important difference is that in the original PATE, the teachers are trained on random splits of the data, while in our case, the agents are naturally present with different distributions. We propose to optionally use domain adaptation techniques to mitigate these differences when training the "teachers".
Private-kNN-FIL Next we present how the teachers fa is constructed in Private-KNN-FZZ. method (see Algorithm 2). Each agent has data-independent feature extractor d. For every unlabeled query Zt. agent finds the k; nearest neighbor to 2, from its local data by measuring their Euclidean distance in the feature space Rd and f(( outputs the frequency vector of the votes for these nearest neighbors. Subsequently. (x,e) from all agents are privately aggregated with the argmax of the noisy voting scores returned to the server.
Different from the original Private-KNN (Zhu et al., 2020), we apply kNN on each agent's local data instead of the entire private dataset. This distinction allows us receive up to I: neighbors while
5

---

Under review as a conference paper at ICLR 2021
Algorithm PATE-FL
Algorithm 2 Private-KNN-FLL
Input: Noise global data Da. Q query
Input: Noise o, global data Dc, Q query
1: for in N clients do
1: for = 0, 1, Q. pick ay E Dz do
2: Train local model fi using D;
2: for each agent i in 1, L..., do
3: for & = 0, i.... Q, pick E De do
3: Apply 6 on D; and æt
for each agent in 1,... N do
4: V1...., yk top-k closest labels
5: f((2)) f(())) + NO, of Ic).
(O, N Ic) 5: f((2,) = ( Us)
6: end for
6: end for
7: Dr. = arg max, y y (L...., Ei fi(1)))
7: Dt arg max yEl.,.E E fi(x)))
8: end for
8: end for
9: Train global model using (2t,, Dr (=1
9: Train a global model 0 using (0t, 30
bounding the contribution of individual agents by k. Comparing to PATE-FL, this approach enjoys a stronger instance-level DP guarantee since the sensitivity from adding or removing one instance a factor of k/2 times smaller than that of the agent-level.
4.1 PRIVACY ANALYSIS
We provide our privacy analysis based on Renyi differential privacy (RDP) (Mironov, 2017). RDP inherits and generalizes the information thoomatton-thhoreticall properties of DP, and has been used for privacy analysis in De-FedAvg. We defer the background about RDP, its connection to DP and all proofs of technical results the appendix RDP section.
Theorem 3 (Privacy guarantee). Let PATE-FL and Private-kNN-FL. answer Q queries with noise scale a. For agent-level protection, both algorithms guarantee (a, Qa/ (2n2)) )-RPP for all a 1. For instance-level protection, PATE-FL and Private-KNN-FL.ohe obby (ax, Quja² and (a, Qa Qa/(ko²)) RDP respectively.
This theorem says that both algorithms achieve agent-level and instance-level differential privacy. With the same noise injection to the agent's output, Private-kNN-FLA enjoys a stronger instance-level DP (by factor of k/2) compared to agent-level guarantee, while PATE-FL's instance-level DP is weaker by a factor of 2.
C- where A C-1 denotes the probability simplex - the soft-label space. Note that both algorithms we propose can be viewed as voting of these local agents, which output a probability distribution in C-1 First, let us define the margin parameter ((x) that measures the difference between the largest and second largest coordinate of t Einf(())
Improved accuracy and privacy with large margin: Let fi, JN
Lemma 4. Conditioning on the teachers, for each public data point I, the noise added to each coordinate of 2/4 I is drawn from N a² N22),, then with probability 2 1 C' C'expl-N2 (x))/(/))))/""" /80²) }, the privately released label matches the majority vote without noise.
The proof (in Appendix) is a straightforward application of Gaussian tail bounds and a union bound over C coordinates. This lemma implies that for all public data point such that 7(x) >
2/2log(C/8) the output label matches noiseless majority votes with probability at least 1 - d.
Next we show that for those data point x such that ((x) is large, the privacy loss for releasing arg max; + Ein J((x)) is exponentially smaller.
Theorem 5. For each public data point x, the mechanism that releases arg max, EN f((z) + No (o² (N)) obeys (a,
where
E E Ce
1
log (1
(1+e
12m-1022 x2 208 1607
+
+log
C
where 1 for PATE-FL, and 8 for Private-KNN-FL.
This bound implies that when the margin of the voting scores is large, the agents enjoy exponentially stronger (data-dependent) differential privacy guarantees in both agent-level and instance-level. In

---

Under review as a conference paper at ICLR 2021
Datasets
# Agents
Methods
Accuracy
4
FedAvg
87.6 0.1%
FedAvg+DA
$6.9
DP-FedAvg
76.3 0.3%
SVHN, MNIST - USPS
200
De-FedAvg-DA
1.4%%
3.6
PATE-FL (Ours)
83.8
3.6
PATE-FL+ FL+DA (Ours)
92.5 0.2%
2.8
FedAvg
0.1%
CelebA
300
DP-FedAvg
83.2
4.0
PATE-FL (Ours)
15.0
4.0
FedAvg
9
MNIST
100
DP-FedAvg
84.2 - 0.2%
PATE-FL (Ours)
95.1 + 0.3%
4.3
Table 1: Agent-level DP Evaluation. We compare the state-of-the-an DPFL methods with ours on the Digit and CclebA datasets. For (e. 8DD setting, set 10-3 across all the methods.
other words, our proposed methods avoid the dependence on model dimension d that are inherited in De-FedAvg and can release models for free privacy cost when high consensus among votes from local agents.
4.2 COMMUNICATION COST
Finally, regarding the communication issue, our proposed methods are parallel as each agent work independently without any synchronization. Overall, reduce the up-stream communication cost from T floats (model size times 7 rounds) to C floats in one round.
EXPERIMENTAL RESULTS
We verify our PATE-FL for agent-level DP on Digit (LeCun et al., 1998: Netzer et al., 2011) and CelebA (Liu et al., 2015). Then, evaluate Private-KNN-FI
Office-CaltechlO (Gong et al., 2012) and DomainNet (Peng et al., 2019a) 9a) for instance-level DP. Five independent rounds of exper- iments conducted to report unlabeled data on Digit datasets but only labeled data for all other datasets. We defer the experimen- tal details to appendix.
accuracy and its standard deviation. We use both labeled and
5.1 EVALUATION ON AGENT-LEVEL DP
Digit Datasets Evaluation: MNIST, SVHN and USPS together as Digit datasets, is con- trolled setting mimic the real case, where distribution of agent-to-server or agent-to-agent can be different. We simulate 140 agents using SVHN with 3000 records each and 60 agents using MNIST with 1000 records each. USPS serves as unlabeled public data, where 3000 records can be accessed by the local agents and the remaining records are used for testing.
PATE DP-FedAvg
Accuracy
85
80
75
In Table 1, methods PATE-FL and PATE- FL+DA are compared to private and non- private baselines. PATE-FL+DA is based on PATE-FL, where each agent model is trained with domain adaptation (DA) technique (Ganin et al., 2016). FedAvg+DX is the variant of Fe- dAvg with the same DA technique, We observe:
Figure 2: Privacy-accuracy tradeoff for MNIST dataset with Non-i.i. partition. The z-axis is the privacy budget and the y-axis reports the corre- sponding accuracy.
(1) When the privacy cost of DP-FedAvg and PATE-FL is close, method significantly improves the accuracy from 76.3% to 83.8%. (2) The further improved accuracy 92.5% PATE-FL+DA demonstrates that framework
orthogonally benefit from DA techniques, where it is highly uncertain yet for the gradient-bases based methods. (3) Both FedAvg and D--FedArg perform better than their DA variants. The possible reason might be that FL with domain adaptation more closely

---

Under review as a conference paper at ICLR 2021
Network
Methods
4, C, -> W (Acc.)
C,C,W -> D(Acc.)
c
FedAvg
0.1%
96.8
DP-FedAvg
-.71%
46.6
0.8%
47.1
AlexNet
DP-FedSGD
32.6.1
4.1
48.3
DP-FedSGD
75.2 0.5%
12.4
4.67
7.9
Private-KNN- (Ours)
0.3%
3,9
0.3%
3.7
FedAvg
96.5 0.1%
ResNet50
DP-FedSGD
25.8 0.6%
4.0
42.7 0.5%
Private-KNN-FL
86.3 + 0.4%
2.8
91.9 + 0.2%
2.0
Table 2: Instance-level DP on Office-Caltech using different backbones.
Clipart (Acc.)
Painting (Acc.)
c J
Real (Acc.)
4
FedAvg
81.8 0.2%
72.8 0.2%
82.0 0.3%
DP-FedSGD
44.2 + 0.2%
4.4
42.6 + 0.3%
4.6
39.1 + 0.6%
4.3
DP-FedSGD
55.6 0.2%
11.6
60.0 + 0.6%
14.6
55.1 + 0.6%
11.9
Private-NNN-FI. (Ours)
55.8 + 0.6%
4.4
61.2 + 0.8%
4.7
55.5 + 0.7%
4.2
Table 3: Instance-level DP on DomainNet. We compare our method with DP-FedSGD and the
non-private baseline FedAvg. Total number of local agents is 5. We set 10-4.
related to multi-source domain adaptation (Peng et al., 2019b) than the traditional domain adapta- tion. other words, averaging gradients of domain adaptation methods implies averaging different trajectories towards the server's distribution, which may not work in practice. How to improve DP-FedAvg variants with DA techniques remains an open problem.
CelebA Dataset Evaluation: CelebA is a 220k face attribute dataset with 40 attributes defined. 300 agents are designed with partitioned training data. We split 600 unlabeled data at server, and the rest 59,400 images are for testing. Detailed settings referred to appendix. Consistent to Digits dataset, our method achieves clear performance gain by 1.8% compared to DP-FedAvg while maintaining the same privacy cost.
MNIST Dataset with Non-i.i. Partition Evaluation: In both CelebA and Digit experiments, we ii.d partition each dataset into different agents. To investigate our proposed algorithm under non- ii.d partition scenario, we choose a similar experimental setup as (McMahan et al., 2017) did. We divide the training set of sorted MNIST into 100 agents, such that each agent will have samples from digits only. This way, each agent gets 600 data points from classes. We split 30% of the testing set in MNIST the available unlabeled public data and the remaining testing set used for testing. As shown in Table 1, our method achieves consistent better performance than DP-FedA Fedye. Moreover, we plot the privacy-aceurage tradeoff in Figure 2. For every fixed privacy budget the æ-axis, we do grid search on all hyperparameters (e.g., #queries and noise scale for PATE-FL and #communication round, noise scale for DP- FedAvg.. the figure, the accuracy of PATE-FL is consistently higher than DP- De-FedAvg.
5.2 EVALUATION ON INSTANCE-LEVEL. DP
When agents few, preserving privacy across agents becomes hard and meaningless. We then focus on preserving each instance's 's privacy, a.k.a instance-level DP. FedAvg is non-private baseline.
Office- OfficeCCaltech Evaluation: Vifice-Caltech consists of data from four domains: Caltech (C), Ama- zon (A), Webcam (W) and DSLR (D). We pick one domain as server each time and the rest ones for local agents (e.g., in A, D, + W, Webcam treated as the server). We split 70% data from the server domain as public available unlabeled data while the remaining 30% data is used for testing. For -NL-L, we instantiate the public feature extractor using the network backbone without the classifier layer. Both AlexNet and Resnet50) are Imagenet pre-trained. We set = 15 for Private-KNN-FL. with AlexNet and a = 25 for ResNet50. To address the domain adaptation issue, each agent choose & to be smaller if they observe the domain gap is large, implies more selective set of neighbors. In our experiment, we set & to be the 5% of the local data size (i.e., each agent returns the noisy top-5% neighbors' predictions).
smaller k
We observe in Table 2, De-FedD degrades when backbone changes from light load AlexNet to heavy load ResNet50. while ours is improved by 10%. It is because larger model capacity leads to more sensitive response to gradient clipping or noise injection. In contrast, our Private-kNN FL avoids the gradient operation by label aggregation and can still benefit from the larger model
8

---

Under review as a conference paper at ICLR 2021
100
95
95
Accunsty
85
Accincy
85
80
90
75
No Plivacy DR-FAAAy
Dr-TwdAsy
PATE
PATE
100
200
300
400
500
600
200
400
600
8in
Data per agent
Number of agent
(a) Effect on the amount of data per agent
(b) Effect on the number of agent
Figure 3: Ablation study on amount of data per agent and number of agent. The non-private model, FedAvg, is served as the performance upper bound.
capacity. Again, our method achieves consistently better utility-privage trade-off maintaining same privacy cost and can achieve significantly better utility, or maintaining same utility and can achieve much low privacy cost.
DomainNet Evaluation: DomainNet contains 0.6 million images of 345 categories, ranging from Clipart, Painting, Real, Quickdraw, Infograph and Sketch. As challenging dataset even for non-private setting (Peng et al., 2019c), we only consider seven fruit classes (apple, banana, grapes, strawberry, watermelon, pear, pineapple) for demonstration. Large domain shift exists be- tween infograph/quickdraw and other domains (Peng et al., 2019c). Thus we only report results on cases where servers are chosen from Clipart, Painting and Real. Five domain data are assigned to five agents respectively. 70% of the left domain data is split for server and 30% rest for testing.
six domains:
Table 3 compares our Private-kNV Matiee-NN-FFFF FL method with De-FedDGD We observe that when the privacy cost is aligned close, our method outperforms DP-FedSGD by more than 10% in accuracy gain across all the three cases. When the accuracy is aligned close, method saves more than 60% privacy cost, showing consistent ad advantaee over DP-FedSGD.
5.3 ABLATION STUDY
In this section, we investigate the agent-level privacy-utility trade-off with respect to the number of agents and the volume of local data. MNIST is utilized for generality and simplicity. We randomly pick 1000 testing data as the unlabeled server data and the remaining 9000 data for testing. We adopt the model structure proposed in (Abadi et al., 2016) for both of our methods.
Effect of Data per Agent: We fix the number of agent to 100 and range the number of data per agent from {50, 100, 200, 400, 6003. By only relaxing the "data per agent" factor, we fairly tune the other privacy parameters for all the methods to its maximized performance. In Figure (a), as "data per agent" increases, all the methods improves the overall dataset volume increases. Our method achieves consistently higher accuracy over De-FedAvg. The failure cases for both methods when "data per agent" is below 50, which cannot ensure the well-trained local agent models. Label aggregation over such weak local models results in failure or sub-optimal performance.
Effect of Number of Agents: In Figure 3 (b), vary N (50, 100, 200, 400, 800} and set overall privacy budget fixed as = 5, 5 = 30 Following (Geyer et al., 2017), each agent has exactly 600 data, where data samples are duplicated when N {200, 400, 800). We conduct grid search for each method to obtain optimal hyper-parametent Our method shows clear performance advantage over FedAvv. We also see DP-FedAvg gradually approaches our method as the number of agents increases.
CONCLUSIONS
In this work, we propose based approaches for differentially private federated learning (DPFL) under two privacy regimes: agent-level and instance-level. We substantially investigate the real-world challenges of DPFL and demonstrate the advantages of our methods over gradient aggregation-basse based DPFL methods utility, convergence, reliance network capacity, and com- munication cost. Extensive empirical evaluation shows that our methods improve the privacy-utie utility trade-off in both privacy regimes.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-300-000 -188-18, 2016. 1, 3, 5, 9, 16
Alekh Agarwal, Martin J Wainwright, Peter L. Bartlett, and Pradeep K Ravikumar. Information- theoretic lower bounds on the oracle complexity of convex optimization. In Advances in Neural Information Processing Systems, pp. 1-9, 2009. 5
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMa- han. epsgd: Communication--fficiii and differeetiilll-priine distributed sgd. In Advances in Neural Information Processing Systems, pp. 7564-7575, 2018. 3,5
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Effi cient algorithms and tight error bounds. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 464-473, 2014. 3,5
Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications in private federated learning. arXiv preprint 18X.00181,,00094, 2018. 3
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017. 1,2
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3):109-11109 2011.
Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. Proceedings of the srenty--econd A ACM SIGMOD-SIGACT-SIGAN symposium Principles of database systems, pp. 202-210 2003.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006. 3
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural net- works. The Journal of Machine Learning Research, (71):2096-20334 2016.
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv: 1712.075777 2017. 1, 5, 9, 13, 14, 16
Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman. Geodesic flow kernel for unsupervised domain adaptation. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp- 2066-2073. IEFF, 2012.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint 1tXXi:181I..3604 2018.
Li Huang, Andrew L Shea, Huining Qian, Aditya Masurkar, Hao Deng, and Dianbo Liu. Patient clustering improves efficiency of federated machine learning to predict mortality and hospital stay time using distributed electronic medical records. Journal of biomedical informatics, 99:103291, 2019. 1
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International Conference on Machine Learning (ICML-15), 2015. 13
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv: arXiv: (et.//921..9999 2019. 4
10

---

Under review as a conference paper at ICLR 2021
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492 2016. 5
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11): 86(11):228--2324 1998. 7
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization heterogeneous networks, arXiv preprint arXiv:18/2.06127 2018.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint arXiv:1907.021660 2019. 4
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pp. 3730-3738, 2015.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. coammuiccaioonefffciin learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017. 2,
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations (ICLR-18), 2018. 1, 3, 4,5
llya Mironov. Rényi differential privacy. In Computer Security Foundations Symposium (CSF), 2017 IEEE 30th, pp. 263-275. IEEE, 2017. 6, 13
Payman Mohassel and Yupeng Zhang, Secureml: A system for scalable crivacy-preserving machine learning. 2017 IEEE Symposium on Security and Privacy (SP), pp. 19-38. IEEE, 2017.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. arXiv preprint 1eXiv:1902.00/ 2019. 3
Yurii Nesterov. Introductory Lectures Conver Optimization: Basic Course, volume 87.
Springer Science & Business Media, 2003. 4
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In International Conference on Learning Representations (ICLR-17) 2017. 1,2
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Er- lingsson. Scalable private learning with pate. In International Conference on Learning Represen- tations (ICLR-18) 2018. 2. 15
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference Computer Vision, pp. 1406-1415, 2019a.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference Computer Vision, pp. 1406-1415, 2019b. 8
Xingchao Peng, Zijun Huang. Yizhe Zhu, and Kate Saenko. Federated adversarial domain adapta- tion. arXiv preprint /xXvv:/91..0205.. 2019c. 3,
Daniel Peterson, Pallika Kanani, and Virendra Marathe. Private federated learning with domain adaptation. arXiv preprint arXiv:1912.067.33 2019.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In IEEE Symposium on Security and Privacy (SP), pp- 3-18. IEFE, 2017.
11

---

Under review as a conference paper at ICLR 2021
Virginia Smith, Chao-Kat Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems, pp. 4424 4434, 2017. 2
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In Conference on Signal and Information Processing, 2013.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and federated learning. In AlSec, 2019a. 3
Yi Zhou. A hybrid approach to
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach to privacy-preservngg federated learning. In Proceedings of the 12th ACM Workshop Artificial Intelligence and Security, pp. 1-11, 2019b. 1,3
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 37(6): 120--1211, 2019, 4
Yuqing Zhu, Xiang Yu, Manmohan Chandraker, and Yu-Xiang Wang. Private-knn: Practical dif- ferential privacy for computer vision. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2020. 1, 2, 5, 16
12


Reviews:
[{"review_id": "hzVZNcMXBUT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Objective of the paper:\nThe objective of the paper is to provide new federated learning algorithms based on aggregating labels from a voting scheme, instead of aggregating the gradients directly, to achieve more efficient differentially private algorithms.\n\n\nStrong Points:\n1)  It looks like the methods get strong results.\n2)  Mix of theoretical results (in supplemental materials) and practical results.  \n\nWeak Points:\n1)   The paper is not written as well as I would like.  Terms like clipping threshold are never actually defined in the main text.  Expressions like \"each data\".  Example 2 isn't well explained (why will it be clipped to 0)?  Statements like \"lower bounded by O(BG/√T)\"  (if it's a lower bound, shouldn't that be Omega not O?).  Tables are confusing (what is epsilon followed by a down-arrow?).  \n2)  The paper assumes a lot of background knowledge on the recent related work.  (I suppose that can't be helped, but it does make it a hard read.)  I don't understand how the \"votes\" work, in that I don't know what are the \"labels\" being voted on, or why the label with maximum vote is a reasonable approach.   (If I asked for a rating for a product and 10 people chose 1 but 9 people chose 8, 9, and 10, would I think the right rating is 1?)  \n\nOverall Rating:   I am left with the paper being borderline;  I will tentatively place it above the threshold based on the results looking good, and see what other reviewers suggest.  \n\nQuestions for Authors:\n\nOther Feedback:  I think in the end I was not the right reviewer for this paper, and I would defer to other reviewers (and raise my score as needed).  The paper suffers perhaps from being \"too big\" for the too-low page limit offered by ICLR.  The authors have tried to cram in a lot of experiments up front (and some theory in the supplemental materials), but the paper seems written essentially for people in the area.  Not enough up front explanation;  lots of assumed knowledge on the part of the reader in my mind.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gyqU8BSrGXM", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Voting-based approaches for DP\n\n1/ Summary of the paper\n\nThis paper addresses the problem of learning a private model in an FL setting. It assumes that the server has an unlabelled dataset on which learning has to be performed. The paper proposes two extensions of known algorithms, PATE and Private-KNN in this setting. In both cases, up to variations, the approach is \"one-shot\" and amounts to getting consensus labels for the public dataset from the different FL agent, the consensus being obtained with DP guarantees. Then, a model is trained on the server using these consensus labels.\nThe paper provides Rényi DP guarantees for both algorithms. Experiments on real datasets in 2 settings (many agents and few ones) show an improved performance over baseline DP FL algorithms.\n\n2/ Strong and weak points\n\n- The paper makes a very good distinction of the number of agents and the DP guarantees it implies in both settings, with the notion of instance-level (i.e. at the individual sample level) vs agent-level (i.e. client) DP.\n- The paper is well-motivated, and section 3 is very helpful in this regard (even if I have some remarks, see additional comments)\n- The paper is well written and easy to follow\n\n- A weakness of the paper is its limited algorithmic novelty: as far as I understand, PATE already considered N subsets of a large dataset, while here the subsets are already provided by the agents; Private-KNN-FL is more novel insofar as private-KNN only considered a single dataset, but here as well the jump from 1 to N is the only novelty.\n- Another weakness of the paper is its experimental validation, see supporting arguments.\n\n3/ Recommendation\n\nGiven the limited algorithmic novelty and the limitations of the experimental validation, I think this paper is marginally above acceptance threshold despite its interesting viewpoint and theoretical contributions.\n\n4/ Supporting arguments\n\n- All results in Table 1 and Table 2 rely on domain adaptation approach, with the final model being tested on a domain held by the server. While the proposed approaches really train a model on this domain (at least for the samples, not the labels), the baselines FedAvg, DP-FedAvg and DP-FedSGD are not designed for this setting by default, as they minimise the average losses of the clients and never see the server distribution. Out-of-domain generalisation is an issue of its own in FL, and the mix of both issues at the same time makes it impossible to really compare results with one another, rendering all these results less significant.\n- Theorem 3 provides privacy guarantees of both approaches in the agent-level and instance-level DP cases, allowing to compare the proposed approaches with one another. However, in the experimental section, PATE-FL is compared to a baseline agent-level method, and Private-KNN-FL approach is compared with instance-level methods. Private-KNN-FL and PATE-FL are never compared with one another experimentally, which would have been helpful to understand when one is better than the other (especially for the ablation experiments of Fig 2).\n\n5/ Questions and comments\n\n- Could you detail the experimental methodology to get results from table 3? In particular, from which domain were the different agents extracted from? Does each column correspond to a different training?\n- What Domain adaptation method is used for SVHn and MNIST in Table 1? What is the corresponding performance of FedAvg and DP-FedAvg when applying it to them as well?\n- In Section 3.1, example 2 appears a bit artificial to me insofar as it is more the heterogeneity of the different clients (with positive and negative x_i) which yields a null gradient than the clipping. In particular, this is a low-dimensional example, whereas in high-dimensions it is well known that the magnitude of the gradients play less of a role, see e.g. the effectiveness of SignSGD, Adam or TernaryGrad compression methods in the FL setting.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WZxDK3dur9O", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Federated learning enables distributed clients to train a model without sharing the data with each other. This is typically achieved by a gradient descent type algorithm such as federated averaging. The paper argues that federated learning via gradient updates has issues and proposes to use a voting based method for training machine learning models using unlabeled global data.\n\nI have several concerns about the paper:\n\n1. The novelty in the new algorithms is not clear.  PATE-FL and Private-kNN-FL are largely similar to the original PATE and Private-kNN algorithms.\n2. The paper argues that the existing gradient descent type algorithms suffer from slow convergence. However, recent works such as SCAFFOLD (https://arxiv.org/pdf/1910.06378.pdf) provide fast convergence rates for gradient based federated learning. It would be good to add comparisons with these new algorithms.\n3. In Example 2, the problem can be mitigated by setting the threshold to \\tau + \\alpha. Hence its not clear if this is an inherent issue in gradient based methods or if it is just an issue with hyperparameter tuning.\n4. Unlike standard works, the proposed algorithms assume the existence of a global unlabeled dataset, which is not always feasible. Furthermore, the approach inherently requires that the global data is similar to the private datasets, which has not been quantified. For a fair comparison in experiments, one should consider variations of federated averaging with the global public data.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-xEbLI3yp1U", "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": "Summary:\nThe paper proposes two approaches (i.e., PATE-FL and Private-kNN-FL) to train a differentially private global model in a federated setting based on [1] and [2]. In PATE-FL, each client first trains a teacher model using their local dataset. The teacher models are used to make noisy predictions on a public dataset. Then, the public dataset with predicted labels is used to train a final model. In Private-kNN-FL, instead of training a teacher model, the prediction depends on the labels of the nearest neighbors. The experiments show that PATE-FL and Private-kNN-FL can outperform DP-FedAvg in terms of agent-level DP and instance-level DP, respectively.\n\n[1] Scalable Private Learning with Pate   ICLR 2018\n\n[2] Private-kNN: Practical Differential Privacy for Computer Vision   CVPR 2020\n\nPros:\n\n(1) The studied problem is interesting and important.\n\n(2) The proposed approaches have quite good performance compared with DP-FedAvg.\n\nCons:\n\n(1) The work does not have sufficient algorithmic contributions. PATE-FL simply applies PATE [1] in the federated setting without the data splitting since the data are naturally partitioned. Also, Private-kNN-FL uses Private-kNN [2] in local clients to label the public dataset. The algorithms are an extension of existing algorithms in the federated setting without proposing new techniques. The theoretical analysis seems can be easily derived from the existing theorems with a modified sensitivity.\n\n(2) The proposed approach lacks some important details. In Private-kNN-FL, a data-independent feature extractor is used. However, the authors did not mention how to get the extractor. In federated learning scenarios, the training data are usually sensitive and thus it is challenging to get a good and public feature extractor for the data. If the quality of the feature extractor is bad, then the labeling may be quite bad especially when the data are non-i.i.d. distributed (which is a common case in federated learning). Also, it is not clear how to set $k$ for Private-kNN-FL. \n\n(3) The experiments are not clear and solid enough. Some experimental details are missing. Also, more experiments are needed. Please see the detailed comments. \n\nDetailed comments:\n\n(1) The experimental details are missing: the number of communication rounds for FedAvg, the value of $k$, the feature extractor, the test dataset of Digit task.\n\n(2) I’d like to see the experiments given different numbers of queries/$\\varepsilon$. The authors may add a figure to show the accuracy versus $\\varepsilon$ of all approaches.\n\n(3) The experiments for agent-level DP evaluation can be further improved. It seems that each dataset is i.i.d. partitioned into different clients. The authors can try non-i.i.d. partition [3,4], which is a key feature in federated learning.\n\n[3] Communication-Efficient Learning of Deep Networks from Decentralized Data \t\tAISTATS 2017\n\n[4] Federated Learning with Matched Averaging  \tICLR 2020\n\n\n=======Post-rebuttal comments=========\n\nThanks for the authors' response. However, my main concerns on the feature extractor and the contributions are still not well addressed. Moreover,\n\n(1) The authors agree that a good feature extractor is usually hard to obtain in practice. The feature extractor will significantly limit the applicability of the proposed approach.\n\n(2) I found that the authors use ImageNet pretrained models in the experiments. This setting is weird. In my knowledge, the pretrained models are seldom used in the existing federated learning studies. The model may already be good enough before training and thus cannot well show the effectiveness of the algorithms. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper adapts the semi-supervised DP learning methods based on voting to FL. Specifically, PATE and private-kNN. The adaptation is fairly straightforward as those methods rely on averaging of votes a primitive that is a standard part of FL. The framework assumes that unlabeled data from the same distribution is available to the server, a very strong assumption.
As pointed out in the reviews, the empirical evaluation has a number of major issues. For example, the comparison is with fully-supervised SGD based techniques instead of a gradient-based semi-supervised approach.

Decision: Reject