F^2ed-Learning: Good Fences Make Good Neighbors
Authors: Lun Wang
Qi Pang
Shuai Wang
Dawn Song
Venue:  (2021)
Keywords: Byzantine-Robust Federated Learning
Secure Aggregation

Abstract: In this paper, we present F^2ed-Learning, the first federated learning protocol simultaneously defending against both semi-honest server and Byzantine malicious clients. Using a robust mean estimator called FilterL2, F^2ed-Learning is the first FL protocol with dimension-free estimation error against Byzantine malicious clients. Besides, F^2ed-Learning leverages secure aggregation to protect the clients from a semi-honest server who wants to infer the clients' information from the legitimate updates. The main challenge stems from the incompatibility between FilterL2 and secure aggregation. Specifically, to run FilterL2, the server needs to access individual updates from clients while secure aggregation hides those updates from it. We propose to split the clients into shards, securely aggregate each shard's updates and run FilterL2 on the updates from different shards. The evaluation shows that F^2ed-Learning consistently achieves optimal or sub-optimal performance under three attacks among five robust FL protocols. The code for evaluation is available in the supplementary material.

Under review as a conference paper at ICLR 2021
F'ED-LEARNING: GOOD FENCES MAKE GOOD NEIGH- BORS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we present EEED-LEANN the first federated learning protocol simultaneously defending against both semi-honest server and Byzantine mali- cious clients. Using robust mean estimator called Filter1.2, F'ED-LEARNING is the first FL protocol providing dimension-free estimation error against Byzan- tine malicious clients. Besides, LEARNNNGG leverages secure aggregation to protect the clients from semi-honest server who wants to infer the clients' infor- mation from the legitimate updates. The main challenge stems from the incompat- ibility between FilterL2 and secure aggregation. Specifically, run FilterL2, the server needs to access individual updates from clients while secure aggregation hides those updates from it. We propose split the clients into shards, securely aggregate each shard's updates and run FilterL2 on the updates from different shards. The evaluation shows that EEDD-LARNNNG consistently achieves opti- mal or close-to-optimal performance under three attacks among five robust FL protocols.
INTRODUCTION
Federated learning (FL) has drawn numerous attention in the past few years as new distributed learning paradigm. In federated learning, the users collaboratively train model with the help of centralized server when all the data is held locally to preserve the users' privacy. The privacy guaran- tee can be further enhanced using secure aggregation technique (Bonawitz et al. (217)) which hides the individual local updates and only reveals the aggregated global update. The graceful balance between utility and privacy popularizes federated learning in a variety of sensitive applications such as Google GBoard, healthcare service and self-driving cars.
The above threat model assumes that all the users honestly upload their local updates. However, it is likely that small number of clients are malicious in large-scale FL system with tens of thousands of clients. Besides, most SGD-based FL algorithms used today (McMahan the centralized server averages the local updates to obtain the global update, which vulnerable to even only one malicious client. Therefore, a malicious client can arbitrarily craft its update to either prevent the global model from converging lead it to sub-optimal minimum. This kind of attack federated learning is well-studied by [Bhaojj et al. (2019) Fang et al. (209)) Bagdasaryan et al. 2000)) Sun al. (2020).
Ramage 2017).
To mitigate these attacks, various Byzantine-robust FL protocols (Blanchard et al. 2017 Yin et al. 2018 Fu al. 2019 Pillutla al. 2019) are proposed to reduce the impact of the contaminated updates. These protocols replace trivial averaging with well-designed Byzantine-robuss mean esti- mators. These estimators suppress the influence of the malicious updates and output mean estima- tion as accurate as possible. Nevertheless, almost all of these aggregators suffer from the curse of dimensionality. Specifically, the estimation error scales up with the size of the model in a square- root fashion. As a concrete example, three-layer MLP on MNIST contains more than 50,000 parameters and leads to 223-fold increase of the estimation error, which is prohibitive tice. Draco (Chen et al. 2018), 8), BULYAN (Mhamdi al.) 2018) and ByzatineSGD (Alistarh et al.) 2018) are the only three works that state to yield dimension free estimation error. However, Draco designed for distributed learning and is incompatible with federated learning because it requires redundant updates from each worker. On the other hand, although Bulyan (Mhamdi et al. 2018) and ByzantineSGD (Alistarh al. 2018 provide dimension-free estimation error, based
prac-

---

Under review as a conference paper at ICLR 2021
much stronger assumptions than other works. When the assumptions are relaxed to the common case, Bulyan's 's estimation error still scales up with the square root of the model size as discussed in Section
In addition, these robust FL protocols have incompatible implementation with secure aggregation techniques. The robust estimators have access local updates while secure aggregation hides them from the server. Consequently, the system cannot simultaneously protect the server and the clients, but has to place complete trust in either of them. The lack of two-way protection severely harms the people's ' confidence in the FL system and prevents federated learning from being used in many sensitive applications such as home monitoring and self-driving cars.
Contribution. In this paper, we propose FEDERATED LEARNING WITH FENCE, abbreviately FEED-LEARNING. F'ED-LEARNING integrates a robust mean estimator with dimension-free er- ror (Steinbardi, 2018) and secure aggregation (Bonawitz et al. 2017) to defend against both the Byzantine malicious clients and the semi-hones server. In partieular, EEED-LEARNING the first Byzantine-robust FL system with dimension-fiee estimation error. To address the incompatibilityy the clients are split into multiple shards, the local updates from the same shard are securely aggre- gated at the centralized server, and the robust estimator is run on the aggregated local updates from different shards. Surprisingly, sharding also consolidates the independently and identically dis- tributed (IID) assumption required by the robust estimator even under heterogeneous data distribu- tion. According to Lindeberg central limitation theorem (Lindeberg) 1922), despite the heterogene- ity of the individual local updates, the aggregated local updates from the shards will approximately follow an IID Gaussian distribution.
2 LOOPHOLE BULYAN AND BYZANTINESGD & RELATED WORK
Byzantine-robust aggregation has drawn enormous attention in the past few years due to the emer- gence of various distributed attacks in federated learning. Fang et al. (2019) formalize the attack as an optimization problem and successfully migrate the data poisoning attack to federated learning. The proposed attacks even work under Byzantine-rohust federated learning. (unn et al. (2020) man- age to launch data poisoning attack on the multi-task federated learning framework. |hagoji et al.) (2019) and (Bagdasaryan et al. (2020) even manage to insert backdoor functionalities into the model via local model poisoning or local model replacement.
A variety of Byzantine-robust FL protocols are proposed to defend against these attacks. Krum (Blanchard et al.] 2017) picks the subset of updates with enough close neighbors and av- erages the subset. Yin et al. (2018) leverage traditional robust estimators like trimmed mean or median to achieve order-optimal statistical error rate under strongly convex assumptions. Yin et al. 2019) propose
robust mean estimators to defend against saddle point attack. Mhamdd et al. 2018 pointed out that Krum, trimmed mean and median all suffers from O(Vd) (d is the model size) estimation error and proposed a general framework Bulyan to reduce the error to O(1). How- ever, point that the improvement of Bulyan actually comes from its stronger assumption. In particular, Bulyan assumes that expectation of the distance between two benign updates is bounded by a constant 01, while Krum assumes that the distance is bounded by 02 d. We can easily see that if 01 dd Bulyan falls back to the same order of estimation eтror as Krum. The same loophole exists in the analysis of ByzantineSGD (Alistarh et al., 2018). Consequently, there is no known federated learning protocol with dimension-free estimation error against Byzantine adversaries.
PROBLEM SETUP
In this section, we review the general pipeline federated learning, introduce the threat model, 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 1...n with [n].
Federated Learning Pipeline. In a federated learning system, there are one server S and n clients C, E [n]. Each client holds data samples drawn from some unknown distribution D. Let e(w: z) be the loss function on the model parameter w e gd and a data sample z. Let L(w) = Ez-D[ [e(;; be the population loss function. Our goal is to learn the model such that the population loss function
2

---

Under review as a conference paper at ICLR 2021
is minimized:
arg min [(w). wEW
To learn w", the whole system runs a T-round federated learning protocol. Initially, the server stores a global model Wo. In the tth round, S broadcasts the global model w,-1 to the m clients. The clients then run the local optimizers (e.g. SGD, Adam, and RMSprop), compute the difference g." between the optimized model and the global model, and upload the difference to S. In the 1th round, S takes
the average of the differences and update the global model w, Wi-1 - - (8)
Threat Model & Defence Goal. We assume that the centralized server S is semi-honest. The server can launch whatever attacks such inference attack using legitimate updates from the clients as the only inputs. However, the server cannot deviate from the protocol for the sake of regulation or reputation pressure. Specifically, we want to emphasize there no collusion between the server and the clients. On the other hand, we assume that the clients are c- e-Byzantine malicious, which means at most em clients can be malicious. Malicious clients can arbitrarily deviate from the protocol and tamper with their own updates without being detected.
In this paper, we aim to achieve dimension- error for the mean estimation each round. Let be the true mean of the benign distribution and the output of protocol with contaminated inputs be fı. The estimation error defined by the l2 distance between the true mean and the estimation p p4l22-
4 FEDD-EARNING: ROBUST PRIVACY- DISTRIBUTED FL
In this section, we formally present our main protocol: FEED-LEARNING. We first introduce FRED- LEARNING step by step and formally establish the robustness and security guarantees. Then discuss the effect of sharding on the IID distribution assumption.
4.1 F EDD-LEARNNN:: BYZANTINE-ROBIE
PINVACY-RRESERVNG FEDERATED LEARNING
The complete F'ED-LEARNING protocol presented in Algorithm | F F'ED-LEARNING iteratively executes the following steps: (1) the server broadcasts the global model to the clients; (2) clients train the global model with their local data; (3) clients in the same shard run secure aggregation protocol to upload the mean of their updates to the server; (4) the server aggregates the received updates using robust mean estimation; (5) the server updates the global model with the aggregated global update. We highlight step (3) and (4) newly proposed in LFED-LEARNING.
Sharded Secure Aggregation (line 8-10, 12, 16). Secure aggregation is developed by Bonawitz al. (2017) to defend against the honest but curious server in federated learning. Secure aggregation allows the server to obtain the sum the clients' updates but hides the individual updates crypto- graphically. We introduce an oversimplified version of secure aggregation as follows for the ease of clarification. As the first step, each client samples random values for the other clients and send the values the corresponding clients (line 8-10). After receiving all the values from other clients, each client sums up the received values and subtracts the values generated by itself to produce a random mask (line 12). Each client blinds its local update with the random mask and sends the blinded update to the server (line 13). The server then sums up all the blinded updates and obtains the summed update in plaintext (line 15). Obviously, all the masks cancel out during aggregation and the server receives the plaintext sum. Secure aggregation provides strong privacy guarantee for the clients that the server cannot see anything but the aggregated global update and each client is hidden in thousands of other clients.
However, in our threat model, vanilla secure aggregation is insufficient since provides no protec- tion for the server. As the individual updates are completely hidden, there is way that the server can identify the malicious clients even after detecting the attack. To address the issue, we propose to split the clients into multiple shards and run secure aggregation within each shard. The size of the shards provides a trade-off between the protection for the server or the clients. The smaller the size is, the more information is revealed to the server, thus the easier to defend against Byzantine malicious clients and the harder to fight off the semi-honest server. The trade-off is discussed in detail in Section 4.2
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1: FEED-LEARNING: Robust Privacy-Preserving Sharded Federated Learning.
for t --- [2] do
Server:
Split n clients into p shards (Hy)jel))
Broadcast {Hy and the global model w:-1 to all the clients
Client:
foreach client i E [n]] do Locate its own shard
Generate random masks ie k Hf/i
foreach 1: E H i do
Send Uis to l
Train the local model w using w, as initialization
11
(()) W EkH,, u Exgiee u
12
13
Send gr to the server
14
Server:
foreach H, [He do (k)
g: = =kEE g:
16
[1, FilterL he(r) W: W 1-1+8 tg
17
18
Robust Mean Estimation (line 17). The core step in Byzantine-robust federated learning is to estimate the true mean of the benign updates as accurate as possible even with some malicious clients. The most commonly used aggregator, averaging, is proven to be vulnerable even only one malicious client. All other works addressing the issue such as Krum (Blanchard et al., (017)) and Bulyan (Mhamdi al., (0188) suffer from a cemeenennndeeendentt estimation error. Such error is unacceptable even for training a 3-layer MLP MNIST, not to mention more complicated tasks and models such as VGG16 ResNet50.
Actually, the above problem is well studied in statistics under the name "robust mean estimation" and there already exist several robust mean estimators with dimension-fin estimation error (Di- akonikolas et al. (2019); Charikar et al. (2017); Steinharrii (2018); Cheng et al. (2019); Dong et al. (2019)). Therefore, instead of reinventing the wheel, we choose leverage a representative robust mean estimator: FilterL2 (Algorithm 2). The following formulation is related to the presentation given Steinhardi (2018).
Algorithm 2: Filterl.2 2: dimension-free robust mean estimation (Steinhardi) (2018))
Input: ...... Bn RRd.
Let C1.
=1
f.c Li=1 Gg.. og Ei=1 (E
Σ. = EE Cg (e) Po) // 4)
Let be the maximum eigenvector of E., and let o: = VV
if' 0- < n then return fúc
else let 7 = (x, (=e)² and update c; + C Tm/Tm) where Tmax max;
Go back line 2
Specifically, FilterL2 assigns each update weight and iteratively updates the weights until the weights for the malicious updates are small enough. As mentioned, FilterL2 provides dimension- free error rate formally presented follows.
Theorem Steinhardi (018)). Let D be the honest dataset and D* be the contaminated version of D by inserting malicious samples. Suppose that [D*] < [D)((1 6), & iz. and further
4

---

Under review as a conference paper at ICLR 2021
suppose that MEAN μ and [[oovDD]lop o². Then given D", Algorithm 2 outputs p 1 ( using POLY (n, d) time.
Although Algorithm only takes polynomial time to run, the per-round time complexity is (ndd) implemented with power iteration. Given d is large, the running time is still quite expensive in prac- tice. To address the issue, we the update vectors into è sections and apply the robust estimator to each of the sections. The acceleration scheme reduces the per-round running time to Ond /k) but increases the estimation error to ((ovk). For instance, if we take is Vd, the per-round running time becomes ((nd) while the estimation error grows to O(o V Despite the compromise for acceleration, FilterL2 still gives the known optimal estimation error and outperforms other robust FL protocols by multiple magnitudes.
4.2 ROBUSTNESS SECURITY ANALYSIS
In this section, we rigorously present the security and robustness guarantee of FEED-LEARNING.
Security Guarantee. We first give the security guarantee of -FED-LEARNING as follows. Intu- itively, no more information about the clients except the averaged updates from the shards is revealed to the centralized server. Thus, each client's s update is hidden in all the other clients in its shard. The proof deferred to A]
Corollary (Security against nonest-buttcuurinn server, Informal). There exists a PPT (probabilis- tic polynomial Turing machine) simulator which can only see the averaged updates from the shards and its output is computationally indistinguishable from the transcript of LEAR-NNG
Robustness Guarantee. We now give the formal robustness guarantee of FºED-LEARNING. The proof is deferred to Appendix
Corollary (Robustness against Byzantine adversaries). Given the number of clients n, the number of shards p and the fraction of corrupted clients e, FFED-LEARNING provides a mean estimation with dimension-free error as long as 12en <.p.
Given the formal security and robustness guarantee, actually provides a convenient way to calibrate the protection for the server or the clients. Con- cretely, F update in the mean of I updates.
Remark.
that F'ED-LEARNING
tolerate up [ malicious clients and hide each honest client's
4.3 DISCUSSION ON THE I.I. DISTRIBUTION ASSUMPTION IN COROLLARY
To derive Corollary B assume that the updates from the benign clients are drawn IID from some distribution D. In this section, we explore the rationality of the assumption.
Source of Non-III updates in FL. is well known that in FL., data is heterogeneously distributed across clients. Therefore, the collected updates typically do not follow IID distribution under any proper distribution. Another source of non-IID updates in FL is the random initialization of local models. As known, many neural networks is aermutaaionniinaaiiant For instance, in a two-layer fully connected network, the neurons the two layers can be permuted correspondingly without changing the functionality of the network. Therefore, even with the same training data, different initialization can lead to different models within the same permutation-invarian class.
To overcome the second issue, we take the old-fashioned solution by requiring the clients to share the same initialization before the training phase starts. Note that there is line of work (Yurochkin) al. 2019a Wang al. 2020) focusing addressing the issue using matching algorithm and Bayesian nor-maraett model. We deem as an interesting future direction to integrate these works in F"ED-LEARNING.
For the rest of the section, we ignore the second issue and focus on the first issue. We formally model the heterogeneous data distribution under explicit assumptions and discuss how sharding ad- dresses the first issue under such assumptions. Note that with sharding we do not solve the slow convergence issue in Fl. due non-III updates. Instead, we only create IID distribution among
5

---

Under review as a conference paper at ICLR 2021
shards to solidate the IID assumption required in the proof of However, the distribution is highly biased and still suffers from low convergence rate due to the intrinsic non-lID data distribution.
From non-L..D. to LLD. It is widely accepted assumption in traditional distributed learning theory that the updates should be independently and identically distributed. The assumption is rea- sonable in the sense that the server can decide how distribute the data the workers in traditional distributed learning. However, in federated learning, the data is generated by the clients locally so the updates are not necessarily and typically not IID distributed. This poses a challenge on the ro- bustness analysis. Now we propose a novel perspective to conduct robustness analysis in federated learning. Succinetly, by aggregating the shards first, we are able to reduce the non-IID distribution to an III distribution. As the first step, we model the heterogeneous update distribution in federated learning as follows.
Definition (Heterogeneous Distribution). Let ID be of l distributions TD [Di))elW where E[D:] = pa and V[D:] off Each client Cj 's update 8, follows distribution Dets) where & is mapping from the client index to the distribution index.
Note that the definition we use scalar data for the ease of clarification. The formalization can be easily extended to data vectors by separately considering each dimension. The definition captures most important feature that each client's update drawn from different distributions.
As the second step, we analyze the influence of sharding on the update distribution. Surprisingly, sharding pushes the non-IlI distribution a well-regulated IID distribution according to Lindeberg central limit theorem.
Theorem 2 (Lindeberg Central Limit Theorem [innik 1959)). Suppose {X1,'.. [
} is a se- quence of independence random variables (not necessarily identically distributed), each with finite expected value and variance o. Define s =>i of Suppose that Ve > 0,
lim Σ B[(X; -4,² 11
pul cSn
Then the distribution of the standardized sums converges towards the standard normal distribution.
8n Σ (x. M4) 4 N(0.
(1)
Give Definition aand Theorem the following corollary follows naturally. The proof deferred to Appendix C
Corollary 3 (IID after Sharding). Assume that the updates from the clients follow Definition ]
where k < =. Besides, 1im 1
o Σieh E[(g, p4)² fl9 psl es } 0 where st
ΣieH 2. Given the uniform randomness of sharding, we can view the distribution index o(.)) as
drawn from some distribution & on [kt] Let j = ΣxE(H) 4 = i)ps and x² = ExE(H) 4(x = i)o?. Then,
9i
N 17,
H
REH
Empirical Validation. To validate the claim empir- ically, we simulate heterogeneous data distribution by assigning MNIST samples with different labels to 25 clients. These clients are split into shards. We plot the distributions of the updates before and after sharding as shown in Figure Each line represents the weight dis- tribution within one update. Figure Ia plots five updates from the same shard and Figure 1b plots the averaged updates from the five shards. It is obvious that after sharding the distributions are more densely and identi- cally distributed discussed above.
(a) Before sharding.
(b) After sharding.
Figure 1: Distribution w/ (w/o) sharding.

---

Under review as a conference paper at ICLR 2021
5 EVALUATION
In this section, we want to answer the following questions using empirical evaluation: (1) Does FilterL2 outperforms other aggregators when used alone? (2) Does EEED-EARNNNG outperform other robust FL protocols augmented with sharded secure aggregation?
5.1 ATTACKS
To answer the above questions, we evaluated the robust estimators without attack and with several representative attacks. We focus on three of these attacks in the main text and defer another attack to Appendix
The first and second attacks used are the model poisoning attacks from Fang al. 2019). The aim the model poisoning attacks is to increase the error rate of the converged model even facing Byzantine-robust protocols. In these attacks, the malicious clients search for poisoning updates by solving an optimization problem. We employ two attacks proposed in their work targeting at Krum and Trimmed Mean. These attacks are henceforth referred Krum attack (KA) and trimmed mean attack (TMA).
The third attack considered is backdoor attack from [Bhaooji al. (019)). The attack aims insert a backdoor functionality while preserving high accuracy on the validation set. Similarly, the search for the attack gradient is formalized as an optimization problem and the authors tweak the objective function with some stealth metrics to make the attack gradient hard to detect. We refer to the attack as Model Poisoning Attack (MPA) in the rest of the section.
5.2 EXPERIMENTAL SETUP
We selected two datasets: MNIST (LeCun et al. (2010) and FashionMNIST (Xiao et al. (0017)
and three other Byzantine-robust federated learning protocols to compare with: (1) Krum (Blan- chard et al. (017)); (2) Trimmed Mean (Yin et al. 2018)); and (3) Bulyan (Mhamdi et al. (018)). Note that Bulyan acts like a wrapper around other robust estimators in the evaluation we have two versions of Bulyan: Bulyan Krum and Bulyan Trimmed Mean. We ran all the protocols on the two datasets and present the attack performance under these protocols. Attack performance is measured differently according to the different attack targets. For KA and TMA, we use the model accuracy as the metric for characterizing attack performance. Higher model accuracy indicates stronger ro- bustness. For MPA, we the percentage of the remembered backdoors to represent the attack performance. The fewer backdoors remembered, the more robust the estimator is. In the IID setting, the data is shuffled and partitioned into all the clients, each receiving the same number of examples. In the non-IID setting, each client assigned data with 3 labels. Filter1.2 used in the evaluation is the accelerated version as discussed in Section 4.1
5.3 EVALUATION RESULTS
FilterL2 Performance. To answer question (1), we evaluated 6 aggregators on MNIST and Fash- ionMNIST as shown in Figure 2 and Figure We ran the protocols with 20 clients with IID data distributions. 5 of the clients are malicious under attacks. Note that the number of the malicious clients actually exceeds the bound in Corollary because some attacks only work with enough malicious clients.
Not surprisingly, FilterL2 achieves optimal performance among all 6 aggregators. Besides, FilterL2 is the only aggregator that consistently achieves good performance under all three attacks. The superiority of FilterL2 is owed to its quad-root estimation error. Due the theoretically stronger robustness, it is extremely hard to design targeted attacks for FilterL2 like Krum or trimmed mean. In the non-lID setting, all the estimators cannot perform well since the IID assumption broken.
F'ED- WEED-LEARNING Performance. To answer question (2), we evaluated six aggregators with shard- ing on MNIST and FashionMNIST shown in Figure (homogeneous distribution) and Figure (heterogeneous distribution). We ran the protocols with 100 clients, ten of which are malicious under attacks. The 100 clients were randomly split into 25 shards.

---

Under review as a conference paper at ICLR 2021
100
1000
100
(90
Madel Ascincy (10
60
40-
15
Model Accuncy
60
600
Atteck Sumooes
8
60
83
20
25
20
25
20
10
20
25
30
10
201
20
(a) MNIST non-attack.
(b) MNIST under K.A.
(c) MNIST under TMA.
(d) MNIST under MPA.
Arack Sucnoos Rate (83
100
Model Accunocy (%)
80
Model Accuray
8
10
20
25
10
20
25
50
10
16
20
Epoch
(e) FashionMNIST non-ettack.
(f) FashionMNIST under KA.
(g) FashionMNIST under TMA.
(b) FoshionMNIST under MPA.
HLTTRR22
AVERAGE
KRUM
TRIMMED MEAN ... BULYAN KRUM
BULYAN TRIMMED MEAN
Figure 2: Attack performance under different Byzantine-robust estimators with IID data distribution.
100
Modd Accuray (8)
Madd Accunay (90
Madi Ascunay (90
Attic Sicces Rate
80
Epoch
Epoch
Epoch
Epoch
MNNST
MNNSTT
MNIST
FILTERL2 ... AVERAGE ... KRUM
TRIMMED MEAN
BULYAN KRUM
BULYAN TRIMMED MEAN
Figure Attack performance under different estimators with non-IID data distribution.
100
100
100
Modld Accuncyy (%)
Model Accunacy (S)
Modll Aucunacy (%)
80
Attck Socrrs Rate (8)
1.00
00
40
200
3
70
Epach
Epacc
Epach
Ejsac
MNIST attack.
MNIST under KA.
MNIST under TMA.
MNIST under MPA.
100
100)
100
Attak Success Rate (S6)
80
80
Accuracy
Model Accuracy
6o
60
40
Model
6
40
10
15
20
25
5
10
15
30
25
50
10
15
20
25
30
15
20
25
90
Epoch
Epoch
Lipoch
(e) FashionMNIST non-attack.
(0) FashiioMNNSST under KAA
(g) FashionMNIST under TMA.
(h) FashionMNIST under MPA.
FLLTER22
AVERAGE
KRUM
TRIMMED MEAN
BULYAN KRUM
BULYAN TRIMMED MEAN
Figure 4: Attack performance under different estimators with sharded secure aggregation with IID data distri- bution.
8

---

Under review as a conference paper at ICLR 2021
100
100
100
Model Accuncy (1)
80-
Morkl Accunay (16
-00
Modil Accuncy (16
Amtack Attack Sunncaa Rutic (90
60-
60-
10
30
201
25
30
10
201
25
30
10
20
25
20
25
30
(4) MNIST non-attack.
(b) MNIST under K.A.
(c) MNIST under TMA,
(d) MNIST under MPA,
F.LTERI.2
AVERAGE
KRUM
TRIMMED MEAN
BULYAN KRUM
BULYAN TRIMMED MEAN
Figure S: Attack performance under different estimators with sharded secure aggregation with non-IID data distribution.
In both IID and non-Ill) settings, for the experiments without attack, with TMA with MPA (Fig- ure 4a 4d 4e 4g 4h 5a 5c 5d). FEED-LEARNING still achieves optimal or close-to-optimal per- formance. An interesting phenomenon is that KA can be successfully defended by all aggregators when the clients are sharded (Figure 4b 4f.. The reason is that KAA is targeted at Krum without sharding and wants to maximize the probability that a malicious update is chosen by Krum.
Once integrated with sharding, Krum selects from the averaged updates from the shards, and thus the effect of the malicious update is diluted. This demonstrates that sharding itself can defend against some attacks by diluting the effect of malicious updates. Compared with the non-lll) setting without sharding (Figure B), all of the aggregators perform better under different attacks which benefit from the approximate IID distribution among shards.
Influence of Shard Size. As a new hyper-parameter: the number of shards (aka the shard size 7), is introduced in FEED-LEARNNGG, we
300
Moddl Accunay (%)
empirically evaluate its influence as shown in Figure 6 The results in Figure also clearly exhibit the trade-off between security and robust- ness guarantee via tuning p. When the number of shards equals the number of clients, the system equivalent to FilterL2 without shard- ing and achieves optimal model accuracy. However, under such setting, the centralized server has access to each client's 's individual update and FEED-LEARNING provides further security guarantee than vanilla FL. When the number of shards converges to one, the system degrades to simple averaging with secure aggregation with the strongest security but the weakest robustness. When the number of shards lies between the extremes, the model accuracy gradually changes under TMA shown in Figure
60
10 shardi shorcke
stards
sharch
10
35
20
20 30
Figure 6: MNIST under TMA with different number of shards.
6 CONCLUSION & FUTURE DIRECTION
In this paper, we designed and developed FED--EARNINGG the first federated learning protocol defending against honest but curious server and Byzantine malicious clients simultaneously. We propose to use FilterL2 to robustly aggregate the possibly contaminated updates and secure aggrega- tion protect the privacy of the clients. We reconcile the contradictory components with sharding. The evaluation results show that F?ED-LEARNING consistently achieves the optimal or close-to- optimal performance among five robust FL protocols. As far we can see, F'ED-LEARNING addresses the two main privacy threats in FL. systems simultaneously and shows the potential to further popularize FL in sensitive applications.
We also identify several unsolved challenges in FEED-LEARNING which might motivate future works in FL with two-way protection. For instance, vanilla FilterL2 brings large overhead due to its high complexity. Although the accelerated FilterL2 partially addresses the issue, it sacrifices the asymptotic estimation error for the speedup. An interesting future direction is to integrate robust mean estimators with low complexity such as Cheng et al. (2019). However, Cheng al. 2019)'s 's approach is rather complicated so designing low-complexity robust mean estimator with simple in- tuition is also an intriguing direction.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 4613-4623, 2018.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2938-2948, 2020.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning, pp. 634- 643, 2019.
Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzan- tine tolerant gradient descent. In Advances in Neural Information Processing Systems, pp. 119- 129, 2017.
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.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceed- ings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 47-60, 2017.
Lingjaa Chen, Hongyi Wang. Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. arXiv preprint arXiv:1803.0987 2018.
Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly- linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pp. 2755-2771. SIAM, 2019.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimenssons without the computational intractability. SIAM Journal on Computing, (8(2):742-664, 2019.
Yihe Dong, Samuel Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. Advances in Neural Information Processing Systems, pp. 6067-
Minghong Fang, Xiaoyu Cao, Jinyuan Jía, and Neil Zhenqiang Gong. Local model poisoning attacks to byzantine-robust federated learning, arXiv preprint arXiv: 2019.
Shuhao Fu, Chulin Xie, Bo Li, and Qifeng Chen. Attack-resistant federated learning with residual- based reweighting, arXiv preprint arXiv:1912.1 1464,, 2019.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yammleecu..comm http:/yaww..lec...oo///dbbmmiii 2, 2010.
Jarl Waldemar Lindeberg. Eine neue herleitung des exponentialgesetzes in der wabrscheinlichkeit- srechnung. Mathematische Zeitschrift. 15(1):211-225 1922.
Ju V Linnik. An cesformatiionthhorrefee proof of the central limit theorem with lindeberg conditions. Theory of Probability Its Applications, 4(3):288-22) 1959.
Brendan McMahan and Daniel Ramage. Federated learning: Collaborative machine learning with- out centralized training data. Google Research Blog. 3, 2017.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of dis- tributed learning in byzantium. arXiv preprint wrXiv:180..07927 2018.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui, Robust aggregation for federated learning. arXiv preprint arXiv: /9/.. 13445, 2019.
10

---

Under review as a conference paper at ICLR 2021
Jacob Steinhardt. Robust learning: Information theory and algorithms. PhD thesis, Stanford Uni- versity, 2018.
Gan Sun, Yang Cong, Jiahua Dong, Qiang Wang, and Ji Liu. Data poisoning attacks federated machine learning. arXiv preprint arXiv:2004. 10020, 2020.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. arXiv preprint arXiv:2002.06444 06440, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. arXiv preprint arXiv:1803.014900 2018.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in bwwantine-robbliiee distributed learning, In International Conference on Machine Learning, pp. 7074-7084. PMIR, 2019.
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: 12022, 2019b.
A PROOF OF COROLLARY
Proof. Corollary is equivalent to the following lemma.
Lemma (Lemma 6.1 in Bonawitz et al. (017)). Given the number of the shards p. the parameter size d, the group size g, and the updates g where vi [p].g E 2d. we have
th:
(fui e Zuteesuui uij -ijs Vi >
j (g + Σ usj (mod v))ve(
jElPl/s
=(fv; e vepp) s.t.
Σ 5 Σ g H,
(mod q) : (viliel)
EE(p)
tE(p)
where "=" denotes that the distributions are identical.
We prove the above lemma with induction on n.
Base case: When n = 2, the first elements in the RHS of two distributions are both uniformly random. The second element the sum minus the first element. Thus the distributions are identical.
Inductive Hypothesis:
We assume that when n = k. the two distributions are identical.
Inductive Step:
If ignore all the randomness from and for client A 1, according to the inductive hypothesis, the distributions the first & clients are identical. Hence, after adding two independently uniformly random values, the distributions are still identical. The value for the 1+1 client the the sum minus & uniformly random values. Thus, the two distributions are still identical.
11

---

Under review as a conference paper at ICLR 2021
B PROOF OF COROLLARY 2
Proof. In the following analysis, we assume that the updates from the shards follow an IID distribu- tion. The reasonableness of the assumption is further discussed in Section 4.3
The fraction of malicious shards is bounded by the worst case where each malicious client exclu-
sively assigned different shards: e'
12. Given the assumption above, we have satisfied
all the requirements in Theorem [ Hence, FEED-LEARNING provides a mean estimation with dimension-free error as long as 12en < p.
C PROOF OF COROLLARY 3
Su have मे EieH 9i 4 SN( ( Eien Po(i)s
Proof. By reorganizing Equation multinomial distribution Φ,
Given the
[
E
MatE)
EiE(M) Φ(x 1)14 11, V
Zich Mose))
Eieim ((==1)(M(
0
1
[H]
E EmE(s] $xx = = 0², V o
(e)((
( -0"12
o
H
Thus, when |
00, EicH f1,
x
[2
D MODEL REPLACEMENT ATTACK
In this section, we focus on the backdoor attack introduced in Bagdasaryan et al. (2020). namely model replacement attack. Similar to MPA, we use Attack Success Rate as the metric to measure robustness of an estimator. The results are included in Figure
60
Attack Success Rate (%)
40
20
Ascrage
Krun Bulyan.Krum Balyun, Trimmed Mean
20
25
30
Epoch
Figure 7: FashionMNIST under Model Replacement Attack Bagdasaryan et al. 2020
12


Reviews:
[{"review_id": "pEgQ0yYGvry", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposes a simple protocol to allow for both robust mean estimation and secure aggregation by sharding users, applying secure aggregation between shards and then doing robust mean estimation on the means returned by each shard.\n\nPros:\n\nThe proposed method is simple.\n\nExperiments suggest the proposed method is more robust to various attacks than competitors.\n\nCons:\n\nGenerally the paper requires further editing as there are several places where the descriptions could be more clear (e.g. \"achieves\noptimal or sub-optimal performance\").\n\nIn all Theorems it should be noted whether this result is by the authors or whether it is from Steinhardt (2018). Any Theorems which are quoted should be fully attributed, and any which are novel should be accompanied by formal proofs.\n\nIt is quite unclear what value the discussion of creating IID shards brings. Non-IID data between clients is a concern in federated learning, and it can cause issues such as diverging model parameters when each client takes multiple steps of GD locally. However this issue is not solved by sharding the users (as any averaging takes place after all local updates are made), nor is it clear if this solves any other issues. The authors should identify what value having these IID shards brings. Additionally it is unclear that the Lindeberg CLT is required here, as the shards draw directly from the mixture distribution induced by the clients $D_i$ distributions. \n\nThe paper would benefit from a much stronger explanation of the value of the IID-ness of the shards and more exploration of the value added by sharding.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Oh7DHiMG2TB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The authors consider federated learning setting and how to defend the overall learning task against malicious clients and a semi-honest centralized server. Though there are known ways to prevent attacks, they suffer from a large error in the estimator and also do not preserve privacy of updates since the server sees them in the clear in order to adjust for error. This paper proposes a sharding technique and use of the estimator method whose error does not depend on the number of dimensions as previous work.\n\nNovelty:\n1. the sharding approach allows the proposed method to use masking-like techniques to avoid the server seeing values of individual clients. That is, the server only sees aggregates in the shard\n2. the paper proposes a different tradeoff in terms of the error of the estimate compared to mechanisms in related work. In particular, the error depends on the proportion of “malicious” clients.\n\nOverall it is a very nicely written and presented paper.\nI would suggest that the authors expand evaluation section to compare performance of the methods besides accuracy. That is how many rounds each algorithm takes, total communication cost and computation time of each approach.\n\nAlso I was not clear if one needs to make assumptions on the knowledge of the proportion of malicious clients in order to carry out the algorithm (Alg 2). Would that be known or there would be a known upper bound?\n\nPlease state if there is an assumption on non collusion between the server and the clients.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MinywGTnBR", "reviewer": "AnonReviewer3", "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\nPaper summary:\n\nThe paper considers robustness to poisoning and backdoor attacks in the context of federated learning. It proposes a defence based  on splitting the clients into shards, averaging their updates via secure aggregation and then using a robust mean estimation on top to ensure robustness. The authors point out that controlling the number of shards is a way to trade-off privacy vs robustness, thus potentially dealing with both malicious clients and an honest, but curious server. The paper provides some theoretical justification for the algorithm, as well as an experimental evaluation where its performance is tested against multiple attacks and compared to other existing methods.\n\n##########################################################################\n\nPros:\n\n- The paper studies an important problem. Federated learning is an increasingly popular way of training large-scale models. However, the privacy that it offers comes with the cost of vulnerability to training time attacks. Hence, the problem of guaranteeing robustness while preserving privacy is certainly important.\n- I find the idea of splitting clients into groups to trade-off privacy vs robustness very interesting. To my awareness the idea is novel in the context of robust federated learning.\n- Overall, the paper is well-written and it tries to justify the proposed method both theoretically and empirically. \n\n\n##########################################################################\n\nCons:\n\n1. While the papers aims to address the problem of robust federated learning, most of its theoretical analysis, as well as the optimization procedure that is described, is actually tailored to a classic (i.i.d.) distributed learning setting.\n\n- The analysis is Section 4.1 and 4.2 assumes that the data of the good clients is i.i.d.. In section 4.3 an informal argument is made as to why this can be safely ignored because of the averaging inside the shards. However, I find the argument unconvincing for two reasons. First, the CLT argument is tailored to scalar random variables. Applying it to each dimension independently does not seem trivial to me and, if at all possible, might involve an unfortunate dependence in the dimension of the problem. Secondly, even on the intuitive level the resulting distributions will be close to identical only when all clients are good. If some of them can behave arbitrarily, they can shift the mean of their shard, thus breaking the i.i.d. property.\n\n- Perhaps a smaller issue is that the plain optimization method considered in the paper (which is modified via the robust aggregation procedure later on) is SGD. In contrast, many federated learning algorithms, for example, FED-AVG, are based on averaging model parameters and in addition train a model for every client individually. It is unclear whether the analysis in this paper would transfer there as well.\n\n- The baselines considered in the experimental section are also taken from papers that study the i.i.d. version of the problem. Since little information is given about how the training data is distributed across clients, it's hard to know if the comparison to the i.i.d. baselines is fair and also if the experimental setup corresponds to i.i.d. or non-i.i.d. data.\n\n2. Overall, the theoretical analysis in the paper appears insufficient and is not backed up by any proofs.\n\n- Some of the presented theorems and corollaries seem to come from prior work, while others seem to be novel. I am assuming that Theorem 1 is from Steinhardt (2018), while Theorem 2 and 3 are novel. I think this should be made more clear. \n- Theorem 2 and 3 are just stated without any proof. I was also unable to find proofs in the supplementary material. This, together with the lack of intuitive explanation about why these results should hold, makes it impossible to judge the validity and novelty of these results.\n- Theorem 3 states that for small enough number of Byzantine workers, a dimension independent error can be obtained. To me this sounds rather vague. Does this mean that the mean of the true gradients can be estimated to a dimension-independent accuracy at each time step? Or does it mean that at the end the algorithm converges to an epsilon-stationary point, with a number of steps that features no dependence on the dimension of the problem? How would this compare to results in previous work on Byzantine robustness?\n\n3. While experiments are provided on two datasets and against a large amount of attacks, some of the comparisons seem unfair to me. \n\n- In particular, all attacks apart from the backdoor one are tailored against some of the baselines. Naturally, the corresponding baselines compare badly against the attacks tailored to them. At the same time, Krum performs quite well against trimmed mean attacks and similarly the trimmed mean works well against the Krum attack. It therefore would be more fair to also create an attack specifically towards the algorithm proposed in the paper and check the performance under this attack. Alternatively, defence-independent attacks can be used. \n- It would be nice to include more details about how the data was split among workers, so that i.i.d. and non-i.i.d. situations can be spaced out.\n- In the first set of experiments, what is the value of p? It would be interesting to see how the proposed algorithm performs for various values of p, both in terms of robustness and in terms of some notion of privacy.\n\n##########################################################################\n\nReview summary:\n\nI find the high-level idea and the approach taken in the paper quite interesting. However, due to a few concerns about the theoretical justification and the experimental setup I do not recommend acceptance. I believe that a more detailed theoretical analysis and a wider set of experiments are needed to strengthen the submission and make it easier to compare it to prior work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CgKziB55nPO", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Paper summary**\n\nThe paper claims to be the first paper that simultaneously handles Byzantine threats while ensuring privacy in a federated learning setup. One of their main claims is that this is the first algorithm that provides dimension independent robustness guarantees against byzantine threats (I have some concerns regarding this claim). The algorithm first divides all the machines into shards. Within each shard there is secure aggregation. Finally, the outputs of each shard is robustly aggregated such that the error isn't dimension dependent.\n\n**Strengths**\n1. The problem of handling privacy and tolerance to Byzantine adversaries (including data poisoning adversaries) is indeed very important and relevant to federated learning. \n2. The paper provides dimension independent guarantees against Byzantine adversaries, which is of critical importance since modern models can have huge dimensionality.\n3. The experiments show that the algorithm is better than other Byzantine resilient algorithms.\n\nI like the clarification about the assumptions of Bulyan done in Section 2. This will make comparisons between related works easier.\n\n**Concerns**\n1. The proof of Theorem 2 seems to be missing.\n2. I can see that Theorem 3 might be a direct corollary of Proposition 4.1 from (Steinhardt, 2018), but it would still be good to prove Theorem 3 for completeness.\n3. I am not able to see how sharding helps non-iid data become iid. Corollary 1 (CLT) says that $\\frac{1}{s_n}\\sum_{i=1}^n (X_i - \\mu_i) \\stackrel{d}{\\to} \\mathcal{N}(0,1) $. However, what is needed for sharding to make data become iid would be something like $\\frac{1}{n}\\sum_{i=1}^n X_i \\stackrel{d}{\\to} \\mathcal{N}(0,1)$. Note that there are two differences: The major difference is that we have $X_i$ instead of $X_i-\\mu_i$. The second difference is we have $n$ in the denominator instead of $s_n$. Below, I give a concrete example how the CLT is not applicable for sharding.\n\nAssume that we have $2n$ machines. We divided them into two shards of $n$ machines each (machines $1$ to $n$ go into shard $1$, and machines $n+1$ to $2n$ go into shard $2$). Now, what the paper claims would be that the mean of the two shards should converge to the same distribution, regardless of the distribution of the individual machine gradients. Now, assume that for some particular iteration, the gradient of the machines have the following distribution: Machines $1$ to $n$ have (iid) gradients equal to $1$ with probability $1$. Machines $n+1$ to $2n$ have (iid) gradients equal to $-1$ with probability $1$. Clearly, the mean of the first shard is the constant random variable $1$, whereas the mean of the second shard is the constant random variable $-1$. These two random variables don't have the same distribution. Thus, the distribution of the means of the shards is not identical and hence not iid.\n\n4. If concern 3 is valid, then the algorithm would not work on heterogenous data. Further even if concern 3 is invalid the CLT only gives asymptotic result. A key point of this paper is dimension independent resilience. However, if the convergence given by the CLT is very slow as the dimensions increase, then the dimension independent resilience may no longer be valid. \n\nFor these reasons, I think the paper needs some more justification for its theoretical claims.\n\n\n**Suggestions**\n\nI think there are some papers that use the dimension-independent robust mean estimation techniques for non-FL learning. For example (Yin et al., 2019) (this is different from the one cited in your paper). Also, Alistarh et al.(2018) give dimension independent guarantees. It would be good to talk about these in related works.\n\n**Score justification**\n\nAs mentioned in the Concerns section, I think the paper might be missing some justifications for its theoretical claims.\n\n**Post Author Feedback Comments**\n\nThe authors have tried to address my main concern by adding an assumption on the distributions of gradients. Essentially they have assumed that the gradient distributions are sampled from a small, finite set of distributions. I don't know how realistic this assumption is, because each client can potentially have a different distribution. However, in practice, this may be approximately true. A better assumption would have been based on probability distances (TV distance, Wasserstein distance, etc.). \n\nI have increased my score to 6.\n\n**References**\n\n\nYin, D., Chen, Y., Kannan, R. and Bartlett, P., 2019, May. Defending against saddle point attack in Byzantine-robust distributed learning. In International Conference on Machine Learning (pp. 7074-7084). PMLR.\nAlistarh, D., Allen-Zhu, Z. and Li, J., 2018. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems (pp. 4613-4623).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers federated learning in the presence of malicious clients and a semi-honest centralized server. The authors provide a novel secure aggregation technique (i.e. split the clients into shards, and securely aggregate each shard’s updates, and the estimating things based on the updates from different shards) to protect clients from the server. Furthermore, an important property of the proposed protocol is that the estimation error is (provably) dimension-free against Byzantine malicious clients. The paper is well-written. 

The reviewers had a number of concerns many of which were addressed during the rebuttal phase. There was also another round of discussion after the rebuttal phase. Overall, the reviewers felt that there are still some issues that need to be resolved (see the updated reviews--the main issues are: (i) the assumption of non-collusion between the server and the clients, (ii) assumptions and analysis of the non-iid case, and (iii)  comparing to attacks that are specifically targeted against the baselines). I believe that once these issues are addressed, the paper will provide an important contribution to the area of federated learning. 


Decision: Reject