Title: ATTACK-RESISTANT FEDERATED LEARNING WITH RESIDUAL-BASED REWEIGHTING

Abstract: Federated learning has a variety of applications in multiple domains by utilizing private training data stored on different devices. However, the aggregation process in federated learning is highly vulnerable to adversarial attacks so that the global model may behave abnormally under attacks. To tackle this challenge, we present a novel aggregation algorithm with residual-based reweighting to defend federated learning. Our aggregation algorithm combines repeated median regression with the reweighting scheme in iteratively reweighted least squares. Our experiments show that our aggregation algorithm outperforms other alternative algorithms in the presence of label-flipping, backdoor, and Gaussian noise attacks. We also provide theoretical guarantees for our aggregation algorithm.

1. INTRODUCTION:

Federated learning is a machine learning methodology for training a global model with decentralized data stored on multiple or even millions of devices (McMahan et al., 2017) . In federated learning, private data is stored locally in isolated devices and will not be revealed to other parties during training. Federated learning can enable numerous real-world machine learning applications by utilizing massive training data that are privacy-sensitive and scattered on different devices (Bonawitz et al., 2017) . For instance, multiple hospitals can collaborate to train a global model for classifying diseases using X-ray images without compromising patient privacy. Note that these hospitals may possess X-ray images in different quantities and varieties, resulting in the non-IID (independent and identically distributed) data distribution. Federated learning is different from distributed learning in the sense that the training data is often non-IID and we have no control over data distribution in federated learning.

The default federated learning aggregation algorithm FedAvg (McMahan et al., 2017) that takes the average of locally updated models is vulnerable to various attacks. We find that federated learning suffers from label-flipping, backdoor, and Gaussian noise attacks in our experiments. When a local model is poisoned, the aggregated global model can also be poisoned and fail to behave correctly. A label-flipping attack (Biggio et al., 2012) happens where an attacker assigns incorrect labels to some data. For example, an attacker can train a local model with cat images mislabelled as dogs and then share the poisoned local model for aggregation.

Mitigating attacks in federated learning or distributed learning has been explored in recent research (Chen et al., 2017; Yin et al., 2018; Fung et al., 2018; Blanchard et al., 2017) . Although the median or trimmed mean aggregation algorithms (Yin et al., 2018) may seem plausible in distributed learning, their performance degrades in federated learning when data is non-IID. FoolsGold (Fung et al., 2018) is a defense algorithm that identifies participants with similar models as attackers but this strategy may not work when some harmless participants have similar local data. To make federated learning more attack-resistant, we develop an aggregation algorithm that is robust against label-flipping, backdoor, and Gaussian noise attacks in a general non-IID setting. We derive our aggregation algorithm by adopting the repeated median estimator (Siegel, 1982) and the reweighting scheme in iteratively reweighted least squares (IRLS) (Holland and Welsch, 1977; Rand R, 1997) . We estimate the confidence of each parameter in the local models and then the weight of each local model can be computed by heuristically accumulating all the parameter confidence in each local model. Our algorithm is straightforward to implement. Furthermore, we provide theoretical guarantees for our aggregation algorithm.

We compare our proposed algorithm to several baselines by conducting experiments on four datasets, the MNIST dataset (LeCun et al., 1998) , CIFAR-10 dataset (Krizhevsky et al., 2009) , Amazon Reviews dataset (Ruining and Julian, 2016) and the Lending Club loan dataset (Kan, 2019) . Our proposed aggregation significantly mitigates the impact of attacked models in non-IID federated learning and outperforms other baselines in our evaluation.

2. RELATED WORK:

Adversarial attacks on federated learning. Several attacks have been studied against federated learning (Wang et al., 2018; Biggio et al., 2012; Fung et al., 2018; Hayes et al., 2019; Hitaj et al., 2017; Melis et al., 2019) . The label-flipping attack (Biggio et al., 2012) is shown to have great harm to a federated system even with a very small number of attackers (Fung et al., 2018) . In this attack, the attacker flips the labels of training data in one class to another class and trains the model accordingly. Bagdasaryan et al. (2018) propose a backdoor attack so that the global model behaves incorrectly on adversarial targeted input. In our work, we mainly focus on defending against label-flipping attack, backdoor, and Gaussian noise attacks. Note that an attacker can perform any type of attacks, such as modifying any model values and training the local model on poisoned data for arbitrary epochs.

Robust distributed learning. Statistical methods have been studied and applied in robust distributed learning where data is IID (Feng et al., 2014; Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Alistarh et al., 2018) . The median method and the trimmed mean method (Yin et al., 2018) are effective approaches in robust distributed learning, but may not be attack-resistant in federated learning where data distribution is non-IID. To tackle the challenge in robust federated learning, we propose a reweighted aggregation algorithm that dynamically assigns weights to the local model based on the residual to a regression line estimated by the repeated median estimator (Siegel, 1982) .

Defending federated learning. Recently, some researchers have proposed some defense strategies for robust federated learning (Fung et al., 2018; Blanchard et al., 2017) . FoolsGold (Fung et al., 2018) is a defense mechanism against Sybil attacks by adjusting the learning rates of local models based on contribution similarity. The algorithm identifies grouped actions as Sybil attacks and promotes the diversity of local model update. However, FoolsGold may identify harmless participants as attackers when these participants have similar local data. Gu et al. (2018) proposed a model, CalTrain, that represents data with fingerprints to identify poisoned data and models. Konstantinov and Lampert (2019) propose to maintain a small reference dataset to justify the quality and accountability of models. While this method is effective, it requires a lot of time to evaluate each model in every single round. Our algorithm does not need an additional reference dataset before or after each aggregation process. Some researchers proposed to improve the privacy preservation of federated learning (Bonawitz et al., 2017; Geyer et al., 2017; Truex et al., 2018; Thakkar et al., 2019) . Bonawitz et al. (2017) propose a privacy-preserving protocol for model aggregation in federated learning. Geyer et al. (2017) introduce differential privacy into federated learning. Instead of enhancing privacy preservation, we focus on the robustness of federated learning so that the global model should behave correctly even when there is a large portion of malicious participants.

3. OUR ALGORITHM:

In federated learning, there are multiple rounds of communication between participants and a central server for learning a global model. In each round, the global model is shared among the K participants and a local model on each device is trained on its local private data with the shared global model as initialization. Then all the K local models are sent to the central server to update the global model with an aggregation algorithm. The original aggregation scheme uses a simple averaging algorithm to aggregate all the local models (McMahan et al., 2017) . Suppose the participant k has a local model M (k) , and we can update the global model M global by taking the (weighted) average of all the K local models. 

3.1. AGGREGATION ALGORITHM:

Median is a robust estimator widely used in statistics. However, when the data distribution is non-IID, median neglects a significant amount of information by merely taking a single median value. Hence, in our aggregation algorithm, the global model is designed to be a reweighted average of all the local models where the model weights are estimated robustly.

Algorithm 1 summarizes our aggregation algorithm, and a detailed step-by-step description is provided below. We perform a weighted average of all the local models at the model level by assigning a weight to each local model. The weight of each local model is computed by accumulating the parameter confidence in the local model. The parameter confidence is computed based on the residual to a regression line estimated by the repeated median estimator (Siegel, 1982; Rand R, 1997) . Inspired by the reweighting scheme in IRLS (Rand R, 1997) , we reweight each parameter by its vertical distance (residual) to a robust regression line. For the robust regression line estimation, we use the repeated median estimator (Siegel, 1982) since it has a high breakdown point of 50%.

Let y (k):

n be the n-th parameter of the k-th local model. We use y n to indicate the list of n-th parameters in all the local models. Let x n be the indices of y n sorted in an ascending order. Then (x n , y n ) is a point set in 2D with increasing values in the y direction.

Repeated median. We use the repeated median estimator (Siegel, 1982) to estimate a linear regression line y = β n0 + β n1 x. The slope β n1 and intercept β n0 are estimated as follow,

EQUATION

EQUATION

Residual computation. We can calculate the residuals of the n-th parameters in all the local models:

r n = y n -β n0 -β n1 x n .

Since r n can be very different in magnitude for different parameters, we can normalize r n similar to the reweighting scheme in IRLS (Rand R, 1997) :

EQUATION

|r n | = median(|r n |).

(4) where γ is a constant. We set γ = 1.48 recommended by Wilcox et al. (Rand R, 1997) . Then the normalized residuals become

EQUATION

)

Algorithm 1 Our aggregation algorithm

Input: Models M (1) , M (2) , ..., M (K) , with parameters y 

n , ..., y

(K) n ] T do 2:

x n ← indices of y n sorted in an ascending order assign indices 3:

β n0 , β n1 ← RepeatedM edian(x n , y n ) get robust line estimation 4:

r n ← y n -β n0 -β n1 x n compute residual 5:

|r n | ← M edian|r n | 6: τ n ← γ |r n |(1 + 5 K-1 ) normalize residuals 7:

e n ← rn τn 8:

H n ← x n (x T n x n ) -1 x T n compute Hat matrix 9: w n ← √ 1-diag(Hn) en Ψ( en √ 1-diag(Hn)

) compute parameter confidence 10:

y n , w n ← CorrectExtremeValue(y n , w n ) 11:

w n ← w n σ(w n ) reweight confidence by its standard deviation 12: for each k = 1 → K do 13:

W (k) ← N n=1 w (k) n accumulate weights 14: M global ← K k=1 W (k) K i=1 W (i) M (k)

the global model aggregation on the residual which is the distance from a point to the regression line. In the green area, the parameter confidence is 1; in the orange area, the confidence decays from 1 to δ; in other areas, the confidence is set to 0.

Parameter confidence. After obtaining the normalized residuals, the parameter confidence can be determined accordingly (Rand R, 1997) :

EQUATION

where w

(k)

n is the confidence of the n-th parameter in M (k) , Ψ(x) = max{-Z, min(Z, x)} with Z = λ 2/K and λ is a hyperparameter. We use λ = 2 in our experiments. Ψ here acts as a trusted interval and we can expand or shrink the interval by tuning λ. h kk is the k-th diagonal element of matrix in H n :

EQUATION

where

x n = [x (1) n x (2) n . . . x (K) n ] T .

Extreme value correction. Extremely large values, even multiplied with a small weight in model aggregation, can damage the global model. We address this issue by involving a a threshold δ.

If a parameter has a confidence value lower than δ, then it should be corrected as follows,

EQUATION

y (k) n = y (k) n 1(w (k) n > δ) + (β n0 + β n1 x (k) n )1(w (k) n ≤ δ).

(9) The process of selecting proper δ is discussed in the appendix.

Model weight. To obtain the weight of each local model, we can simply aggregate the parameter confidence in the local model but this is not ideal. Imagine an attacker trains a model honestly, but then alters only 10% of the parameters to some extremely large values. This adversary model still receives about 90% of the parameter confidence. To address this problem, we measure the importance of a parameter by the standard deviation of w n . A confidence assignment with a large standard deviation indicates a great disagreement among this parameter in all models and should be more critical when being accumulated towards model weights:

EQUATION

where W (k) is the weight for model k, N is the number of parameters,

w n = [w (1) n w (2) n . . . w (K) n ] T .

Global model. Finally, we can obtain the updated global model by

EQUATION

3.2. THEORETICAL GUARANTEE:

For simplicity, we consider the bound of the error rate for training a single-parameter model on K devices, each storing S IID samples of data. Suppose that there are K devices and U of them are corrupted. We denote the set of adversarial devices as B and the corruption ratio α = U K . We define the parameter of the local model i as ŷ(i) and let µ be the optimal model that minimizes the population loss. Based on our algorithm, the residuals can be simplified as (ŷ (i) -ỹ), where ỹ is the median of {ŷ (i) } for i = 1, 2, ..., K. Let |r| be the median of absolute residuals, i.e., |r| = median(|ŷ (i) -ỹ|).

Then, the normalized residual can be expressed as

EQUATION

)

and the parameter confidence is defined as

EQUATION

Then we will prove that the error of the global model M global :=

EQUATION

The details of the proof are presented in the appendix. The bound indicates that when the amount of data and the number of models are sufficiently large, we can achieve a small error rate Õ( 1

√ S + 1 √ SK + 1 S + 1 √ Kδ ) with high probability.

4. EXPERIMENTS:

We compare our approach with other aggregation algorithms, including FedAvg (McMahan et al., 2017) , the coordinate-wise median method (Yin et al., 2018) , the coordinate-wise trimmed mean method (Yin et al., 2018) , FoolsGold (Fung et al., 2018) , and a coordinate-wise repeated median approach we adopt from (Siegel, 1982) . We perform experiments on the MNIST handwritten digit dataset (LeCun et al., 1998) , the Amazon Reviews dataset (Ruining and Julian, 2016) , the CIFAR-10 dataset (Krizhevsky et al., 2009) , and the Lending Club loan dataset (Kan, 2019) . We implement attack strategies and defense algorithms in PyTorch (Paszke et al., 2017) .

We use a two-layer convolutional neural network (CNN) for our MNIST experiments and the network architecture is shown in the appendix. With this simple CNN model, our goal is to evaluate different aggregation algorithms for defending federated learning in the presence of attacks. On the CIFAR-10 dataset, we use ResNet-18 (He et al., 2015) for image classification. The text classification model FastText (Joulin et al., 2016 ) is adopted for evaluation on the Amazon Reviews dataset. It is a two-layer deep neural network where the first layer is an embedding layer, and the second layer is a fully connected layer. For the Lending Club loan dataset, we use a simple neural network with three fully-connected layers to classify loan status. We use the last two models to demonstrate that our algorithm can be generalized to a natural language processing task and to a real-work financial problem. All the evaluation results are the average of running the same experiments 3 times.

4.1. DATASETS AND EXPERIMENTAL:

MNIST dataset. The MNIST dataset contains 70,000 real-world handwritten images with digits from 0 to 9. We evaluate different methods by learning a global model on these training images distributed on multiple devices in a non-IID setting with adversarial attacks.

CIFAR-10 dataset. The CIFAR-10 dataset contains 60,000 natural images in ten object classes. The experimental setup is also non-IID on CIFAR-10.

Amazon Reviews dataset. The Amazon Reviews dataset (Ruining and Julian, 2016) contains product reviews and ratings collected from the Amazon website. Every review is paired with a sentiment rating from 1 to 5. We categorize comments with rating 1 or 2 as negative and comments with rating 4 or 5 as positive. We discard reviews with rating 3, and we only train a binary classifier. We only use the book reviews from the Kindle Store. 20% of the reviews are used for testing, while the rest is for training. We obtain a training set of 86,164 reviews and a test set of 13,260 reviews.

Lending Club Loan dataset. The Lending club dataset LOAN (Kan, 2019) contains financial information such as credit scores and the number of finance inquiries for loan status prediction ("Current", "Late", or "Fully Paid"). There are 1,808,534 data samples in 9 types of loan status. We divide them by US states to simulate the federated learning scenarios with non-IID data distribution where each state represents a participant.

4.2. RESULTS ON LABEL-FLIPPING ATTACKS:

We evaluate the overall classification performance of different aggregation methods on three datasets under label-flipping attacks, the MNIST dataset (Biggio et al., 2012) , the CIFAR-10 dataset (Krizhevsky et al., 2009) , and Amazon Reviews dataset (Ruining and Julian, 2016) . In label-flipping attacks, attackers flip the labels of training examples in the source class to a target class and train their models accordingly.

In the MNIST experiment, we simulate federated learning with 100 participants, within which 0 to 10 of them are attackers. Each participant contains images of two random digits. The attackers are chosen to be some participants with images of digit 1 and another random digit since they are flipping the label of 1 to 7. We run 200 synchronization rounds with δ set to 0.01. In each round of federated learning, each participant is supposed to train the local model for 5 epochs, but the attackers can train for arbitrary epochs. The results are shown in Figure 3 where attackers train the models with 5 more epochs to enhance the attacks. Our algorithm outperforms all other methods and is robust when the number of attackers increases. Median methods (Median and Repeated Median) have relatively low accuracy due to discarding most of the information in model aggregation. Our algorithm, on the other hand, takes the reweighted average of all local models and thus gathers more information in an unsupervised way. We also compare our algorithm with the state-of-the-art algorithm FoolsGold (Fung et al., 2018) . Though their algorithm also maintains a low attack success rate, our algorithm is more stable and surpasses FoolsGold by 6% on average.

For the CIFAR-10 experiment, following Bagdasaryan et al. (2018) , we adopt a Dirichlet distribution (Minka, 2000) with a hyperparameter 0.9 to generate non-IID data distribution for totally 10 participants. The experimental setup is the same for the CIFAR-10 and MNIST experiments under backdoor attacks in Section 4.3. The attackers flip the label of "cat" to "dog" since they are the most similar classes in CIFAR-10. The experiment results can be found in Table 1 . In this experiment, baseline methods perform fairly well because the data distribution is not immensely non-i.i.d., where each user has all the labels but in different amounts. FoolsGold (Fung et al., 2018) fails because they assume that the gradients of honest models are very different because of the non-i.i.d. data, and the gradients of outliers are close because they share the same objective. However, it may not always be the case when the data distribution is not so extremely non-i.i. baseline methods fail, and is also suitable for common non-i.i.d. situations such as the CIFAR-10 and the Amazon Review experiments.

In the experiment on Amazon Reviews, there are 10 participants, where 0 to 4 participants are attackers who flip all their labels. Attackers also train for 5 more epochs. We run 10 synchronization rounds in the experiment. The result is summarized in 

4.3. RESULTS ON BACKDOOR ATTACKS:

For pixel-pattern backdoor attacks (Gu et al., 2019) in federated learning (Bagdasaryan et al., 2018) , attackers manipulate their local models so that the learned global model predicts some backdoor target label for any image embedded with certain patterns. An example is shown in Figure 6 in the Appendix. The global model can behave normally for clean data. We choose "bird" in CIFAR-10 and "2" in MNIST as the backdoor target labels. Similarly, for the preprocessed LOAN dataset that contains 92 features, we manipulate 6 features by assigning certain large values to them and change the labels of manipulated data to "Does not meet the credit policy. Status:Fully Paid." The training data is mixed with manipulated data and clean data to fit both the backdoor task and the main task. We compare the performance of aggregation algorithms under two backdoor attack scenarios, which

Under review as a conference paper at ICLR 2020 are called the naive approach and the model replacement in Bagdasaryan et al. (2018) . For the naive approach, an attacker poisons its local model and submits the malicious update in every round. For the model replacement, an attacker only poisons in one round to embed some patterns into the global model, so the attacker needs to scale up its malicious update before submission. In our experiment, the malicious participant attacks in round 6 and scales up its update by 100. We run 200 rounds for MNIST and 100 rounds for CIFAR and LOAN.

Table 3 summarizes the results of backdoor attacks. Our method is the highest in terms of accuracy on MNIST under both backdoor attack scenarios. Moreover, on the more challenging CIFAR-10 dataset, our algorithm is the only one that can defend the naive approach backdoor attack. In Figure 4 , we plot the attack success rates over time under different aggregation algorithms except for FoolsGold because it completely fails in both main and backdoor tasks. Intuitively, backdoor attacks can easily succeed under FedAvg, and other baselines slow down the process but still reach high attack success rate into over 70% within 100 rounds. Our algorithm effectively defends the attack and remains stable with 9.65% attack success rate when being attacked continuously for 100 rounds. On the LOAN dataset, our method achieves higher accuracy 94.50% (FedAvg 93.65%) and 0.00% attack success rate (FedAvg 99.71%) under the naive approach attack after 100 rounds. Similarly, our method has 95.06% accuracy (FedAvg 94.11%) and 0.00% attack success rate (FedAvg 98.96%) under model replacement attacks after 100 rounds. Other baselines also have 0.00% attack success rate in two attacking scenarios except FoolsGold, whose attack success rate is 99.96% under the naive approach attack.

It is also interesting to notice that all the baselines on the CIFAR-10 dataset for the naive backdoor attack approach while they perform fairly well on the MNIST dataset. This is because the model used for CIFAR-10 experiments, ResNet-18, is more complicated and has more parameters (1000×) than the simple CNN used for the MNIST dataset. To explore the effect of complex models, we trained a ResNet-18 model on the MNIST dataset and performed the same backdoor attack on it.

The results are shown in Figure 7 in the appendix. All the baselines fail to defend but our algorithm remains stable, which is similar with the result of CIFAR-10. Besides, most baseline methods (FedAvg, Median, Trimmed Mean, and Repeated Median) are coordinate-wise operations, while our algorithm accumulates a weight for each model rather than each parameter. We believe the modelwise reweighting scheme preserves the structure of the parameters and can perceive higher-level information.

4.4. RESULTS ON GAUSSIAN NOISE ATTACKS:

In Gaussian noise attacks, we try to simulate real-world model corruption with 10 corrupted users at different scales of noise. Gaussian noise attacks are performed by multiplying each parameter by a scale sampled from a Gaussian distribution with a mean of 1. In the experiment on MNIST, we have 100 participants where some may be attackers. Each participant has 300 images from a random digit and other 300 images from another random digit. Table 4 summarizes the results when is sampled from a Gaussian distribution with different standard deviations and there are 10 attackers.

Our aggregation algorithm outperforms other approaches under Gaussian noise at multiple scales.

4.5. ALTERNATIVE SCHEMES:

Though our algorithm is inspired by the reweighting scheme from IRLS (Rand R, 1997) , some alternative linear estimators and weighting schemes can replace the original ones. In this section, we replaced the repeated median estimator in our algorithm with Theil-Sen estimator or median estimator and replaced the weighting scheme with a zero-mean Gaussian function where smaller residual means larger weight. We tuned the λ (in the Gaussian weighting it is the variance σ), and the results are shown in table 7 in the appendix. The experiments are performed on the MNIST dataset with label-flipping attacks. Median and Theil-Sen estimators achieve similar results as the Repeated Median estimator, but they can be attacked in a few cases. For example, λ = 5 and δ = 0.01 for Median estimator and λ = 5 and δ = 0.05 for Theil-Sen estimator. Theil-Sen estimator, especially, only has a breakdown point of 29.3%, meaning that it will more easily be broken when the number of attackers increases. The alternative Gaussian weighting scheme is fairly robust against label-flipping attacks. This demonstrates that the robustness comes from our framework rather than intricate hyperparameter tuning.

5. CONCLUSION:

Federated learning utilizes private data on multiple devices to train a global model, but the simple aggregation algorithm in federated learning is vulnerable to malicious attacks. To tackle this problem, we present a novel aggregation algorithm with residual reweighting. Our experiments on computer vision, natural language processing, and financial data show that our approach is robust to labelflipping, Gaussian noise, and backdoor attacks while prior aggregation methods are not. Our algorithm is easy to implement and readily incorporated into existing federated learning frameworks. We hope our proposed aggregation algorithm can make federated learning more practical and robust in the future. Our source code will be made public.

A APPENDIX:

A.1 PROOF For simplicity, we consider the bound of the error rate for training a single-parameter model on K devices, each storing S IID samples of data. We define the parameter of the local model i as ŷ(i) . Suppose that training data points are sampled from some unknown distribution D. Let f (y; x) be a loss function of the parameter y ∈ Y associated with the data point x, where Y is the parameter space, and F (y

) := E x∈D [f (y : x)].

Our goal is to learn an optimal model defined by the parameter that minimizes the population loss:

EQUATION

The parameter space Y is assumed to be convex and compact with diameter D, i.e., ||y -y || 2 ≤ D, ∀y, y ∈ Y. Suppose that there are K devices and U of them are corrupted. We denote the set of adversarial devices as B and the corruption ratio α = U K . Based on our algorithm, the residuals can be simplified as (ŷ (i) -ỹ), where ỹ is the median of {ŷ (i) } for i = 1, 2, ..., K. Let |r| be the median of absolute residuals, i.e., |r| = median(|ŷ (i) -ỹ|). Then, the normalized residual can be expressed as

EQUATION

and the parameter confidence is defined as

EQUATION

Then we will prove that the error of the global model M global :=

EQUATION

Proof. We adopt assumptions 1, 2, 3, and 6, Theorem 8 and Lemma 3 from Yin et al. (2018) here. We can separate Equation 18 into two sets with adversarial participant B and normal users [K] \ B where [K] = {1, 2, . . . , K}.

EQUATION

Now we state here the assumptions and theorems from Yin et al. (2018) .

Assumption 1 (Smoothness of f and F, Assumption 1 from Yin et al. (2018) ). For any x ∈ D, the derivative of f (y; x) is L-Lipschitz, and the function f (y; x) is L-smooth.

Assumption 2 (Sub-exponential gradients, Assumption 6 from Yin et al. (2018) ). We assume that the derivative of f (y; x) with respect to y is v-sub-exponential.

Proposition 1 (Theorem 8 from Yin et al. (2018) ). Define the median of y (i) :

EQUATION

Suppose that Assumption 1 holds, F(y) is λ F -strongly convex.Then, with probability at least 1 -4 1+SKLD , we have

EQUATION

Proposition 2 (Lemma 3 from Yin et al. (2018) ). Suppose that the derivative of the loss function f is i.i.d. v-sub-exponential. Then with a high probability, we have

EQUATION

Yin et al. (2018) prove the difference between the median of models and the optimal model is bounded in Proposition 1, and the maximum difference between an honest model and the optimal model is bounded in Proposition 2 with a high probability, which are exactly the third and the first term respectively in Equation 19.

Now let us consider:

1 K j=1 z (j)

i∈B z (i) ŷ(i) -ỹ . For an attacker a ∈ B, there are two cases:

• |e a | ≤ √ 2λ √ K . From Equation 16 and |e a | ≤ √ 2λ √ K , we have ŷ(a) -ỹ ≤ C √ K , where C = γ √ 2λ |r|(1 + 5 K-1 ). • |e a | > √ 2λ √ K . If |e a | > √ 2λ √

Kδ then it can be eliminated from Equation 17. From Equation 16and

|e a | > √ 2λ √ K , we have C √ K < ŷ(a) -ỹ ≤ C √ Kδ .

Combine two cases, we know that ŷ(a) -ỹ ≤ C √ Kδ , and we have the following inequality,

EQUATION

Therefore, we prove that

EQUATION

A.2 MODEL DETAILS

The models we use in the experiments are described here. The CNN model used for classifying MNIST images (LeCun et al., 1998) can be found in Table 5 . CIFAR-10 is trained with Resnet-18 (He et al., 2015) . The learning rate for both MNIST classifier and CIFAR-10 classifier is 0.01 with a SGD optimizer. We train MNIST classifier for 200 synchronous rounds and CIFAR-10 classifier for 100 rounds, with batch size 128 and 64 respectively. The Amazon Reviews (Ruining and Julian, 2016) classifier FastText (Joulin et al., 2016) 

A.3 HYPERPARAMETERS:

We have two hyperparameters in our method,λ and δ, where λ controls the confidence interval, and δ controls the clipping threshold. We did a grid search to prove that the selection is robust and efficient.

We conduct experiments on the MNIST dataset in i.i.d. and non-i.i.d. settings with various λ and δ.

The results can be found in table 6. In the i.i.d. setting of the MNIST dataset, the results are almost the same for our selections of λ and δ. It is mainly because the parameters for honest models are very close, thus outliers are more easily to be excluded. Still, since the honest models are close and outliers can be easily detected, a larger δ yields a lower error bound as also shown in our proof. In the non-i.i.d. Experiments, however, the models are more diverse, so it is important to find a balance between excluding adversarial models while embracing models trained on different data distributions.

Luckily, the hyperparameter is robust in a large range, as shown in table 6 . Larger δ means it has a lower tolerance of differences and thus may eliminate some of the honest models when data is non-i.i.d. While increasing λ brings insensitivity to the variance of δ. A.4 ALTERNATIVE SCHEMES Though our algorithm is inspired by the reweighting scheme from IRLS (Rand R, 1997) , some alternative linear estimators and weighting schemes can replace the original ones. In this section, we replaced the repeated median estimator in our algorithm with Theil-Sen estimator or median estimator and replaced the weighting scheme with a zero-mean Gaussian function where smaller residual means larger weight. We tuned the λ (in the Gaussian weighting it is the variance σ), and the results are shown in table 7 . The experiments are performed on the MNIST dataset with labelflipping attacks. Median and Theil-Sen estimators achieve similar results as the Repeated Median estimator, but they can be attacked in a few cases. For example, λ = 5 and δ = 0.01 for Median estimator and λ = 5 and δ = 0.05 for Theil-Sen estimator. Theil-Sen estimator, especially, only has a breakdown point of 29.3%, meaning that it will more easily be broken when the number of attackers increases. The alternative Gaussian weighting scheme is fairly robust against label-flipping attacks. This demonstrates that the robustness comes from our framework rather than intricate hyperparameter tuning.

Number of attackers:

A.5 UNDERREPRESENTED DATA

We admit that underrepresented data samples might be rejected by our scheme. To investigate how it may affect the final result, we did a few experiments on the non-i.i.d. MNIST dataset. The experiment setting is the same as the label-flipping attack, where there are 100 users, and each of them holds images of 2 random digits (each digit has 20 holders). Now we remove the holders of digit 0 one by one until there are no user holding digit 0. The experiment result is plotted in figure 5. Our method performs significantly worse than FedAvg after removing 15 holders (75% images of digit 0). However, we observe similar effects on other algorithms, and we perform no worse than other algorithms.

A.6 BACKDOOR EXPERIMENTAL SETUP Experiment setup of backdoor attacks is provided here. There are 10 total participants each round where one of them is the attacker. In each round of federated learning, benign participants train their local models for 5 epochs and attackers train for 10 epochs. Benign participants always use a learning rate of 0.01. In MNIST and CIFAR, the attacker uses a learning rate of 0.1, and in LOAN, the attacker uses 0.002. The batch size is 64 for all participants. The attacker poisons 20 samples per batch in the training process. An example of backdoor patterns we use for image datasets is shown in Figure 6 . For the LOAN dataset, we assign certain values that are slightly larger than their maximum value to the six features (num_tl_120dpd_2m, num_tl_90g_dpd_24m, pub_rec_bankruptcies, pub_rec, acc_now_delinq, tax_liens).

A.6.1 DISCUSSION ON BACKDOOR ATTACK While our algorithm can successfully defend pixel-pattern backdoor attacks (Gu et al., 2019) , some interesting phenomena emerge in our experiments, as shown in table 3 and figure 4 .

The first issue is the failure of all the baselines on the CIFAR-10 dataset for the naive backdoor attack approach while they perform fairly well on the MNIST dataset. This is because the model used for CIFAR-10 experiments, ResNet-18, is more complicated and has more parameters (1000×) than the simple CNN used for the MNIST dataset. To explore the effect of complex models, we trained a ResNet-18 model on the MNIST dataset and performed the same backdoor attack on it. The results are shown in Figure 7 except for FoolsGold because it completely fails in both main task (about 10.00% accuracy) and backdoor task. All the baselines fail to defend but our algorithm remains stable, which is similar with the result of CIFAR-10. Besides, most baseline methods (FedAvg, Median, Trimmed Mean, and Repeated Median) are coordinate-wise operations, while our algorithm accumulates a weight for each model rather than each parameter. We believe the model-wise reweighting scheme preserves the structure of the parameters and can perceive higher-level information.

The second phenomenon is that the attack success rate starts increasing for the baseline methods only after around 25 iterations, as shown in Figure 4 . The global model converges in the main task after 25

:



Figures and Tables:

Figure 1: The overview of our aggregation algorithm for attack-resistant federated learning.

The global model M global 1: for n-th parameter where n = 1 → N , and let y n = [y

Figure2: Parameter confidence assignment based on the residual which is the distance from a point to the regression line. In the green area, the parameter confidence is 1; in the orange area, the confidence decays from 1 to δ; in other areas, the confidence is set to 0.

Figure 3: Results of label-flipping attacks on the MNIST dataset. The number of participants is 100, within which 0 to 10 of them are attackers.

Figure 5: Results of removing users with digit 0.

Figure 7: Results of backdoor attack success rate on the MNIST dataset with ResNet-18. Our algorithm is still stable while others fail for the complicated model.

Our algorithm achieves comparable state-of-the-art results, and our performance does not degrade when there are less than 50% attackers.

Table content: <table><tr><td># of attackers</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>Average</td></tr><tr><td>FedAvg (McMahan et al., 2017)</td><td colspan="6">88.96% 85.74% 82.49% 82.35% 82.11% 84.33%</td></tr><tr><td>Median (Yin et al., 2018)</td><td colspan="6">88.11% 87.69% 87.15% 85.85% 82.01% 86.16%</td></tr><tr><td>Trimmed Mean (Yin et al., 2018)</td><td colspan="6">88.70% 88.52% 87.44% 85.36% 82.35% 86.47%</td></tr><tr><td>Repeated Median (Siegel, 1982)</td><td colspan="6">88.60% 87.76% 86.97% 85.77% 81.82% 86.19%</td></tr><tr><td>FoolsGold (Fung et al., 2018)</td><td>9.70%</td><td>9.57%</td><td colspan="2">10.72% 11.42%</td><td>9.98%</td><td>10.28%</td></tr><tr><td>Ours</td><td colspan="6">89.17% 88.60% 86.66% 86.09% 85.81% 87.27%</td></tr></table>

Results of label-flipping attacks on CIFAR-10 dataset with different numbers of attackers.

Table content: <table><tr><td colspan="2">The total number of participants is 10.</td><td/><td/><td/><td/><td/></tr><tr><td># of attackers</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>Average</td></tr><tr><td>FedAvg (McMahan et al., 2017)</td><td colspan="4">91.81% 86.91% 24.97% 12.52%</td><td>9.78%</td><td>45.20%</td></tr><tr><td>Median (Yin et al., 2018)</td><td colspan="6">91.73% 91.87% 91.79% 91.43% 91.17% 91.60%</td></tr><tr><td>Trimmed Mean (Yin et al., 2018)</td><td colspan="6">91.81% 91.82% 91.82% 91.49% 91.26% 91.64%</td></tr><tr><td>Repeated Median (Siegel, 1982)</td><td colspan="4">91.55% 88.41% 23.22% 11.70%</td><td>9.62%</td><td>44.90%</td></tr><tr><td>FoolsGold (Fung et al., 2018)</td><td colspan="6">50.79% 49.45% 47.44% 49.71% 49.95% 49.47%</td></tr><tr><td>Ours</td><td colspan="6">91.71% 91.79% 91.76% 91.67% 91.38% 91.66%</td></tr></table>

Results of label-flipping attacks on Amazon Reviews dataset with different numbers of attackers. The total number of participants is 10.

Table content: <table/>

Results of backdoor attacks on MNIST and CIFAR-10. There are 10 participants, 1 of whom is an attacker. We denote the accuracy as Acc. and the attack success rate as A.S.R.

Table content: <table><tr><td>Standard deviation</td><td>0%</td><td>100%</td><td>200%</td><td>300%</td><td>Average</td></tr><tr><td>FedAvg (McMahan et al., 2017)</td><td>93.17%</td><td>78.80%</td><td>53.74%</td><td>9.26%</td><td>58.74%</td></tr><tr><td>Median (Yin et al., 2018)</td><td>73.92%</td><td>64.35%</td><td>71.54%</td><td>63.24%</td><td>68.26%</td></tr><tr><td>Trimmed Mean (Yin et al., 2018)</td><td>87.59%</td><td>74.87%</td><td>73.76%</td><td>75.74%</td><td>77.99%</td></tr><tr><td>Repeated Median (Siegel, 1982)</td><td>61.86%</td><td>75.53%</td><td>67.76%</td><td>73.63%</td><td>69.69%</td></tr><tr><td>FoolsGold (Fung et al., 2018)</td><td>86.72%</td><td>90.31%</td><td>86.96%</td><td>89.94%</td><td>88.48%</td></tr><tr><td>Ours</td><td>90.06%</td><td>90.91%</td><td>89.06%</td><td>92.28%</td><td>90.58%</td></tr></table>

Results of Gaussian noise attacks on the MNIST dataset when is sampled from a Gaussian distribution with different standard deviations. There are 100 participants where 10 are attackers.

Table content: <table/>

is a two-layer deep neural network where the first layer is an embedding layer of dimension 100 and the second layer is a fully connected layer of dimension 1. We use binary cross entropy loss to train the model with Adam optimizer (Kingma and Ba, 2014) and learning rate 0.05. The input dimension (vocabulary size) of the model is 25,000. For the preprocessed LOAN dataset, the input data consists of 91 features. We use a simple neural network with three fully-connected layers whose feature channels are 46, 23, and 9 respectively. The CNN architecture for MNIST classification.

Table content: <table><tr><td>Layer</td><td colspan="3"># of Channels Kernel size Image size</td></tr><tr><td>Conv1</td><td>4</td><td>5x5</td><td>24x24</td></tr><tr><td colspan="2">Max-pool 4</td><td/><td>12x12</td></tr><tr><td>Conv1</td><td>8</td><td>5x5</td><td>8x8</td></tr><tr><td colspan="2">Max-pool 8</td><td/><td>4x4</td></tr><tr><td>fc1</td><td>16</td><td>16</td><td/></tr><tr><td>fc2</td><td>10</td><td>10</td><td/></tr></table>



Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">Number of attackers</td><td/></tr><tr><td>λ</td><td>δ</td><td>0</td><td>5</td><td>9</td><td>λ</td><td>δ</td><td>0</td><td>5</td><td>9</td></tr><tr><td colspan="5">0.5 0.01 97.58% 97.71% 97.81%</td><td colspan="4">0.5 0.01 93.63% 95.22%</td><td>94.93%</td></tr><tr><td/><td colspan="4">0.05 97.70% 97.00% 97.39%</td><td/><td colspan="3">0.05 86.22% 82.66%</td><td>91.89%</td></tr><tr><td/><td>0.1</td><td colspan="3">97.68% 97.38% 97.76%</td><td/><td>0.1</td><td colspan="2">83.61% 87.90%</td><td>87.70%</td></tr><tr><td/><td>0.2</td><td colspan="3">97.74% 97.15% 98.05%</td><td/><td>0.2</td><td colspan="2">79.87% 87.64%</td><td>88.86%</td></tr><tr><td>1</td><td colspan="4">0.01 97.72% 97.68% 97.44%</td><td>1</td><td colspan="3">0.01 94.41% 94.92%</td><td>94.54%</td></tr><tr><td/><td colspan="4">0.05 97.75% 97.65% 97.94%</td><td/><td colspan="3">0.05 93.36% 93.99%</td><td>91.15%</td></tr><tr><td/><td>0.1</td><td colspan="3">97.69% 97.60% 97.26%</td><td/><td>0.1</td><td colspan="2">86.93% 92.20%</td><td>89.39%</td></tr><tr><td/><td>0.2</td><td colspan="3">97.31% 97.45% 97.26%</td><td/><td>0.2</td><td colspan="2">84.77% 84.91%</td><td>91.40%</td></tr><tr><td>2</td><td colspan="4">0.01 97.59% 97.68% 97.75%</td><td>2</td><td colspan="3">0.01 94.95% 94.21%</td><td>94.86%</td></tr><tr><td/><td colspan="4">0.05 97.64% 97.85% 97.51%</td><td/><td colspan="3">0.05 91.45% 93.39%</td><td>93.14%</td></tr><tr><td/><td>0.1</td><td colspan="3">97.94% 97.97% 97.76%</td><td/><td>0.1</td><td colspan="2">93.08% 92.84%</td><td>91.84%</td></tr><tr><td/><td>0.2</td><td colspan="3">97.39% 97.26% 97.98%</td><td/><td>0.2</td><td colspan="2">86.09% 90.83%</td><td>91.43%</td></tr><tr><td>3</td><td colspan="4">0.01 97.70% 97.70% 97.51%</td><td>3</td><td colspan="3">0.01 93.83% 91.67%</td><td>94.89%</td></tr><tr><td/><td colspan="4">0.05 97.50% 97.90% 97.56%</td><td/><td colspan="2">0.05 93.76%</td><td colspan="2">95.37% 95.68%</td></tr><tr><td/><td>0.1</td><td colspan="3">97.39% 97.49% 97.65%</td><td/><td>0.1</td><td colspan="2">94.74% 91.93%</td><td>94.13%</td></tr><tr><td/><td>0.2</td><td colspan="3">97.44% 97.79% 97.57%</td><td/><td>0.2</td><td colspan="2">89.11% 92.03%</td><td>93.25%</td></tr><tr><td>5</td><td colspan="4">0.01 97.63% 97.82% 97.60%</td><td>5</td><td colspan="3">0.01 92.62% 94.90%</td><td>93.77%</td></tr><tr><td/><td colspan="4">0.05 97.83% 97.61% 97.86%</td><td/><td colspan="3">0.05 94.53% 93.91%</td><td>95.28%</td></tr><tr><td/><td>0.1</td><td colspan="3">97.69% 97.68% 97.65%</td><td/><td>0.1</td><td colspan="2">94.23% 94.57%</td><td>94.47%</td></tr><tr><td/><td>0.2</td><td colspan="3">97.26% 97.55% 97.39%</td><td/><td>0.2</td><td colspan="2">92.60% 93.05%</td><td>94.23%</td></tr></table>

Results of replacing linear estimator and weighting schemes with other methods. All experiments are performed on MNIST dataset with label-flipping attacks.

Table content: <table/>

Peer review (iclr2020):
The paper proposes an algorithm for mitigating poisoning attacks in federated learning settings and compares it , on four different datasets, against state-of-the-art baselines. Except for some minor issues (see the list below), the paper is well-written and -organized. The description of the proposed algorithm (in pseudo code and using the illustration in Figure 2) is very clear. Overall, the experiments are carefully described. My main concern is that many choices in the design of the proposed algorithm lack context/discussion and thus appear rather ad-hoc. For instance, - Why is the repeated median estimator used for estimating the linear regression? Could other robust estimators have been used? - Similarly, could alternative weighting schemes be used in equations (3)-(5)? I think it*s important to provide more context and discuss possible alternatives. An important element is the exact threat model that the authors are considering. E.g., in the last paragraph on page 4, the authors mention specific attack strategies like altering only 10% of the model parameters. It appears that the design of the model weighting scheme aims at defending against these specific types of attacks. It will be good to either discuss or evaluate empirically how this scheme performs against other strategies. The theoretical guarantee in Section 3.2 is a bit sketchy in my opinion. In what sense is the *expected value of the global model*? I.e. what is the expectation over? Consequently, I could not follow the statement in equation (14). Some explanation in plain text is needed here, too: in what sense does this equation provide a guarantee? In the experiments, several aspects deserve further discussion: (1) the poor performance of FoolsGold almost across the entire board (except for the Gaussian noise attacks), which may indicate that this method was applied outside the threat model it was designed for; (2) the failure of all the baselines on CIFAR-10 for the naive attacking approach, while they perform fairly well on MNIST; (3) why does the attack success rate starts increasing in Figure 4 for the baseline methods only after ~25 iterations? (4) why do the baseline methods perform so poorly against label-flipping against on MNIST (Figure 3) while performing fairly well on CIFAR-10 and Amazon reviews (Table 1/2)? - I think that answering those questions may shed insights into the type of attacks that the different defences can / cannot withstand. I*d also like to challenge the authors to address whether they expect their defence to match or outperform the baselines on *any* attack strategy, or whether they can come up with scenarios where some of the baselines perform better? I would expect that the latter should be possible; it would not diminish the value of the proposed defence but shed more clarity on its possible limitations. List of minor issues: - in the abstract: *aggression* -> *aggregation* - p.1: I would omit the statement in brackets *less than 100 lines*. - p.2: some of the related work discussion repeats content from the introduction - p.3: *summaries* -> *summarizes* - p.3: what does that mean: *has a high breakdown point of 50%*? Please explain/clarify. - p.4: *is the k-the diagonal of matrix in Hn* -> *is the k-th diagonal element of the matrix Hn* - p.4: my pdf reader couldn*t render the binary operator on the right hand side of equation (8) - p.5: *the details of the proof is presented* -> *are* - p.8: *that of which* -> *whose* - p.8: upper case *We* after comma - p.8: first column *Acc* in Table 3: FedAvg has the highest accuracy. Generally, bold numbers in tables do not always mark the best-performing method. Sometimes, bold numbers are entirely missing. In cases where the difference is insignificant (which often appears to be the case) I would mark multiple numbers in bold, as appropriate.