FEDERATED LEARNING FRAMEWORK BASED ON TRIMMED MEAN AGGREGATION RULES
Authors: Wang Tian Xiang
Meiyue Shao
Yanwei Fu
Riheng Jia
Feilong Lin
Zhonglong Zheng
Venue: ICLR 2022 Submitted (2022)
Keywords: Tmean，Byzantine attack，Byzantine-resilient

Abstract: This paper studies the problem of information security in the distributed learning framework. In particular, we consider the clients will always be attacked by Byzantine nodes and poisoning in the federated learning. Typically, aggregation rules are utilized to protect the model from the attacks in federated learning. The classical aggregation methods are Krum(·) and Mean(·), which however, are not capable enough to deal with Byzantine attacks in which general deviations and multiple clients are attacked at the same time. We propose new aggregation rules, Tmean(·), to the federated learning algorithm, and propose a federated learning framework based on Byzantine-resilient aggregation algorithm. Our novel Tmean(·) rules are derived from Mean(·) by appropriately trimming some of the values before averaging them. Theoretically, we provide rigorous theoretical proof and understanding of Tmean(·). Extensive experiments validate the effectiveness of our approaches.

Under review as a conference paper at ICLR 2021
FEDERATED LEARNING FRAMEWORK BASED ON TRIMMED MEAN AGGREGATION RULES
Anonymous authors Paper under double-blind review
ABSTRACT
This paper studies the problem of information security in the distributed learn- ing framework. In particular, we consider the clients will always be attacked by Byzantine nodes and poisoning in the federated learning. Typically, aggrega- tion rules are utilized to protect the model from the attacks federated learning. However, classical aggregation methods such as Krum(-) and Mean(.) are not capable enough to deal with Byzantine attacks in which general deviations and multiple clients are attacked at the same time. We propose new aggregation rules, T-ean(-), to the federated learning algorithm, and propose federated learning framework based Byzantine resilient aggregation algorithm. Our Tmean(-) rules are derived from Mean(-) by appropriately trimming some of the values before averaging them. Theoretically, we provide theoretical analysis and under- standing of T-man(-). Extensive experiments validate the effectiveness of our approaches.
INTRODUCTION
As special of distributed machine learning, federated learning (FL) draws increasing search attention recently. FL has become one promising approach to enable clients collaboratively learn a shared model with the decentralized and private data on each client node. Thus it of central importance to keep the node information secured in FL. Unfortunately. FL is very vulnera- ble software/hardware eттоrs and adversarial attacks; especially Byzantine attack from distributed systems has arose to be a key node attack sample for federated learning.
To ensure the FL model resistance to Byzantine attack, research focuses are made on how to intro- duce aggregation rules into the gradient information iteration process, and how to ensure that this aggregation rule can make the data robust. In particular, classical approaches to avoid the Byzan- tine failures would employ the state machine replication strategy (Alistarh et al. 2018), which can be roughly categorized into two ways in distributed machine learning: (1) the processes agree on a sample of data based on which the clients update their local parameter vectors; (2) the clients agree on how the parameter vector should be updated (Blanchard et al. 2017). The former ones demand transmitting data samples to each individual node, resulting in high costs. The latter ways not liable neither, as we cannot detect whether clients are trustworthy or not, from the mixed Byzantine vectors. The attacker can know any information about the process of FL, and can use any vectors to initiate the attack during the node's information transmission (Yin et al. 2018). More specifically, the data between machines can be replaced by any value. This problem not fully addressed in previous works.
When facing the attacks from Byzantine nodes, the FL models have to rely on robust aggregation rules to minimize the influence of the Byzantine attack on the data model (Bottoul 2010). For in- stance, Krum(-) is a strong aggregation rule designed to identify an honest node such that it can effectively prevent Byzantine attacks in most cases (Blanchard et al. 2017). However, if the Byzan- tine node attack changed from the original single miner node attack to multiple server attacks, Krum(-) is not able to ensure the learning process robustness aggregation rules, simple mean mean-based aggregation rules can maintain learning robustness if is not attacked by Byzantine nodes. However, the Byzantine attack will make the update direction of node gradient information largely deviate from the original function by using simple mean based aggre- gation rules. Some variants of mean-based aggregation rules, such as geometric median (Blanchard
noisy data. As another class of

---

Under review as a conference paper at ICLR 2021
Master
feeBtck
(a) Federated learning gradient update iteration
(b) SGD gradient update
Figure I: (a) is the procession of FL gradient updating. consists four parts: master server, master server distributed network, miner servers and miner network. (b) represents the schematic diagram of the gradient update direction: blue dashed lines represent the estimated gradients of miner nodes; red dashed lines represent the Byzantine update gradients under the attack of the Byzantine nodes; black solid line represents the ideal gradient.
al. 2017). marginal median (Alistarh et al. 20118) are the classical methods to solve the Byzantine node attack problem. But they not much robust than simple mean-based aggregation rules in the case of some large deviation Byzantine attacks. The main difficulty that prevents mean-based
aggregation rules from robust is the unstable distribution of data (Jin al., 2020). We find that the difficulty can be tackled, if the data is averaged by trimming a part of the data and then imported into the aggregation rules. This motivates our work in this paper.
Most of FL approaches are built upon the Stochastic Gradient Descent (SGD) algorithm (Castro al. 1999) its variants, and the statistical properties of SGD such as convergence are well developed. Our approach also employs the SGDD; and the typical iterative process of SGD algorithm distributed system represented by Figure [ First, client, known as a miner node, estimates the gradient of the node, makes an estimate of the deviation between the estimated information and the ideal gradient information (El-Mhamdi et al.) 2020), then passes this information the server node in the network, and finally update the gradient there. So the miner node network transmits the information to the master server, and the master server then passes the gradient update information through series of aggregation operations. When the aggregation conditions transmits the information to the distribution network, and then transmitted to the miner nodes. This is cyclic process, such that the gradient information is continuously updated in the entire network (Li et al. 2014).
met, the server
In this paper, we mainly propose new aggregation rules, Tmean(-), by trimming part of the data before the average operation. We provide theoretical understandings of our aggregation rules, espe- cially, why they are robust to the Byzantine attack. Through attack experiments and mathematical proofs, we have concluded that appropriately trimming the original data and averaging can make the model more robust from the decentralized data.
Specifically, in section 3 we introduce the federated learning Byzantine distributed system model, briefly describes the working principle of SGD, and summarizes the update iteration rules based on aggregation rules. Then, we present the concept of Byzantine resilience, and the conditions to satisfy the aggregation rules of Byzantine resilience. We provide concept of trimmed mean and the rigorous theoretical proof and understanding of T-mean()) based aggregation rules in section Then, we prove the convergence of the proposed federated learning aggregation rules in section S In section 6 we conduct experiments by Gaussian attack, omniscient attack and multiple servers attack. Under these attacks, Tmean(-) b-abeed FL aggregation rules can still maintain robustness. These experiments thus validate the effectiveness of approaches.
2

---

Under review as a conference paper at ICLR 2021
Contributions: (1) We present new aggregation rules, Tmean(-), to the Byzantine resilient feder- ated learning algorithm, and propose federated learning frameworks based on aggregation algorithm. Our proposed approaches are shown to be robust to Byzantine attacks.
(2) We provide rigorous theoretical proof and understanding of our approaches and aggregation rules. To the best of our knowledge, these theorems and theoretical understandings are for the first time contributed to the community. Critically, we make convergence certificates and prove that Tmean(-) can converge in the general convex optimization setting.
(3) Empirically, we demonstrate that the effectiveness of our approaches can make the FL model robust Byzantine attack.
RELATED WORK
Federated Learning. Federated learning has become a prominent distributed learning paradigm. In (Jin al., 2020), the authors proposed Stochastic-Sign SGD, parameter estimation method with convergence guarantees. uses gradient compressor based on random symbols to unify that the gradient is updated in the framework. The FedAvg algorithm was first proposed by (Konečný ett al. 2016). and many scholars subsequently improved it based on this algorithm. (Karimireddy al. 2020) pointed out that FedAvg can be improved by adding one additional parameters control variables to correct the client drift, and proved that FedAvg may be seriously affected by the gradient difference of different clients, and may even be slower than SGD.
Byzantine attack in FL. To make the secure transmission of the master server node, the FL mod- els have to deal with the Byzantine attack. (Yin et al.] (018)) showed that certain aggregation rules in the master server node can ensure the robustness of the data. (Blanchard et al., 2017 pointed out that Krum(-) can be used to make the robustness of data by computing the local sum of squared Euclidean distance the other candidates, and outputting the one with minimal sum. When the gra- dient is updated to the saddle point, there is no guarantee that the SGD algorithm converges to the global optimum. Some scholars have proposed ByzantinePGD (Yin et al. 2019), which can escape saddle points and false local minimums, and can converge to an approximate true local minimum with low iteration complexity. Later, in the strong anti-Br -azi-Byzantine model, some scholars carried out poisoning attacks Byzantine robust data, from the original data collection process to the subse- quent information exchange process, and at the same time, these attacks were defended accordingly, in (Zhao al.,, 2021). The research on the Byzantine structure model of federated learning has been expanded once again (Zhao et al. 2021)
Attack and Defence. In the framework of federated learning, miner nodes are usually attacked, such Byzantine node attacks, poisoning attacks (Zhao et al. [021), gradient leakage (Wei et al. 2020), etc. There exist various defense methods also, such as robust aggregation, secure aggregation, encryption, etc. Our paper mainly studies Byzantine node attacks. Byzantine node attacks can usually be summarized into two types: (1) To update gradient information of nodes, nodes are replaced by Byzantine nodes, and normal worker nodes cannot make judgments that the gradient estimates deviate from the actual gradient update direction. (2) During the gradient process, the local node suffering from the interference of the Byzantine node, cannot reach a consensus with the master node, making the entire process unable to proceed normally (Lamport et al.) 2019). Krum(-) is popular aggregation rule to deal with these node attacks. We shall propose Tmeaan()) as alternative aggregation rules.
PRELIMINARY AND PROBLEM SETUP
3.1 FEDERATED LEARNING SETTING
Federated learning was first proposed in (Konečný et al. 2016). where the prevalent asynchronous SGD is used to update a global model in a distributed fashion. A pioneering work in this field proposed the currently most widely used algorithm, FedAvg (MeMahan al.) (017). which is also the first synchronous algorithm dedicated to federated setting. Recent studies attempt to expand federated learning with the aim of providing learning in more diverse and practical environments
3

---

Under review as a conference paper at ICLR 2021
Server:
Initialize To < rand();
for ( 0, L, ...., 7 do
Broadcast (1)) to all the workers;
Wait until all the gradients ( a(e) im arrive;
Compute GK = Aggr( (t(t) (()
02 pm )
Update the parameter x (f+1) + (()) G
end
Worker:
for 0, L, ..., T do
Receive ((() from the server;
Compute and send the local randomized gradient v(() Vx(x10 Ex) to the server,
end
Algorithm 1: Distributed synchronous SGD with robust aggregation server.
such as multi-task learning, generative models, continual learning, and data with noisy labels. How- ever, these algorithms may obtain suboptimal performance when miners participating in FL have non-independently and identical distributions (non-i.i.d.) (Zhao et al.) 2018).
While the convergence of FedAvg on such settings was initially shown by experiments in (McMahan et al. 2017). it does not guarantee performance as good as that in an i.i.d. setting. These algorithms pointed out the issue have major limitations, such privacy violation by partial global sharing of local data (Zhao et al. 2018) or no indication of improvement over baseline algorithms such as FedAvg (Hsich et al. 2020). Our paper focuses on a general federated setting.
In order to better study the problem of aggregation in federated learning, we consider the following optimization problem:
min F(x),
(1)
#CRd
where F(x) [f {)] is a smooth convex function, is sampled from some unknown distri- bution D. Ideally, the problem [ can be solved by the gradient descent method as
x (++1)
(t) 70 (z:'"))
where (1) is the learning rate /-th round. We assume that there exists at least one minimizer of F(x), denoted by x", that satisfies VF (x*)= O.
The problem 1 is solved in distributed manner with miner nodes, and up q of them may be Byzantine nodes. The detailed algorithm of distributed synchronous SGD with aggregation rule Aggr(-) shown in Algorithm [ In each iteration, each miner samples n i.i.d. data points from the distribution DD, and computes the gradient of the local empirical loss. Using a certain aggregation rule Aggr(-), the server collects and aggregates the gradients sent by the miners, and estimate the gradient through ()((())) Rs Aggr(v1; 122,.... um) Without Byzantine failures, the k-th worker calculates tx G()), where (t)) = vf(x("),)) When there exist Byzantine faults, ux can be replaced by any arbitrary value of and hence
VF(x(") Aggr(01, Uz,..., 8m)
(3)
3.2 BYZANTINE RESILIENCE
In the following we introduce the concept of Byzantine resilience. Suppose that in specific it- eration, the correct vectors U1, U2 Um are i.i.d. samples drawn from the random variable unbiased estimator of the gradient based the current parameter z. Thus, E[uy] = E G| = for l: E (1, m). We simplify the notations by omitting the index of iteration t. The following Definition I defines the concept of A A-Byzantine resilience. For simplicity, we sometimes use Byzantine resilient in short when the concrete value of A is either clear from the context or not important.
G -= Vf(x;; Ex), where E[G]
4

---

Lk=1 is the Under review as a conference paper at ICLR 2021
Definition 1 (Byzantine Resilience). Suppose that 0 0
and A is given positive number.
Let U1, V2 Um be ii.d. random vectors in R where Uk ~ G with E|G] = g. Let U1, V/. om be attacked copies of Uk 's, such that least q of which are equal to the corresponding Uą while the rest are arbitrary vectors in Rd. An aggregation rule A Aggr()) is said to be A-Byzantine resilient if
E E[llAggr(ns (ū1, , - 9ll S A
4 FL FRAMEWORK WITH ROBUST AGGREGATION
Nowadays, the aggregation rules based on the FL framework are mainly based on Krum(-) and Mean(-). They are usually used in the defense of Byzantine node attacks, However, the aggregation rules based on Mean(-) often cannot exhibit strong robustness, it is affected by Byzantine nodes. The attack makes the gradient estimation direction deviate too far from the actual gradient update direction; and it cannot guarantee the robustness of the data. Thus we shall propose trimmed mean- based aggregation rules to resolve this issue.
4.1
KRUM
The Krum rule is a strong aggregation rule that attempts to identify an honest computing node, and discards the data of other computing nodes. The data from the identified honest computing node is used in the next round of algorithm. The selection strategy is to find one whose data is closest to that on other computing nodes. In other words, computes the local sum of squared Euclidean distances to the other candidates, and outputs the one with minimal sum A notable property of Krum(-) is shown in Lemma 11
2017 Let U1, Um E Rdd be any i.i.d. random vectors such that [|I g S V. Let Ú1, 02 ..., Um attacked copies of ug 's, where up to q of them are Byzantine. 2q + 2 m, then Krum(-) is ---Byzantine resilient, where
Lemma 1 ((Blanchard et al.
e G with E[G] = y and E
6m - 6g + 4g(m - 2) + 4m 24 -
1-1)
Ao
4.2 MEAN- BASED AGGREGATION RULES
An important class of aggregation rules is mean-based aggregation rules. Mathematically, an ag- gregation rule Aggr(-) is a mean-based one if Aggr(U1, ......, Um) is guaranteed to be convex combination of 01, 02 .... Um Roughly speaking, mean-based rule produces an averaged value of the input data. For instance, the arithmetic mean Mean(v1, U2, ...,, Um) 1 m simplest mean-based aggregation rule. However, simple mean-based aggregation rules are gen- eral not robust under Byzantine attacks, in the sense that they do not satisfy Byzantine resilience conditions (Yin et al. 2018).
In the following, we show that by carefully handling the data, certain mean-based rules can satisfy Byzantine resilience conditions. We first introduce the concept of b-trimmed means based on order statistics in Definition 2 This concept is closely related the coordinate -iss trimmed mean defined in (Yin et al. 2018).
Definition 2. Let U1, U2 .... Um be scalars whose order statistics is
4(1) U22) .... ((m)-
For an integer with 0 S < m/2, 2, the b-trimmed mean of u1, U2, Um is defined as
T Tmeans(u,, U2, ..., Wmm)
((K)-
2h k=b+1
For d-vectors U1 U2 Um E RRd, the b-trimmed mean Tmeans(),, U2,... Um) E IRd is defined in the component-wis sense, i.e.
Tmcans(1n U2 Um)) = Σ e.
Tmean, ((12, eil (V2, es), (Bm, cz)),
5

---

Under review as a conference paper at ICLR 2021
where eş is the i-th column of the d d identity matrix.
Intuitively, aggregation rules using b-trimmed means have opportunities to discard abnormal values from the input data. Lemma shows that b-trimmed means are usually within meaningful range under mild assumptions.
Lemma 2. Let Ug U2. .... Um be scalars whose order statisties
u(1) S u(2) I ... S ((m).
and ū1 ü2 .... Um be attacked copies of 111 U2. um with up q Byzantine elements. If the order statistics of ùn is
(()) 4(2) S ((m))
then for q S b m/2, we have
b()-b) S u(k-o) - (1)) I ((k4g) I ((+b))+
(b (b+1sksM m
Proof. Let (()))) be the largest non- non- non-BByantine element in {ū(I): ((2) ..... ((y) Since the number of
Byzantine elements less than equal q, have (())) 2 u(ka) u(k-g) u(k-b) if 2 b+ 1.
The proof of U(()) S u(k-4) S b(k+b) for k S m - is similar.
With the help of Lemma 2 we can prove that (-) is Byzantine resilient when is greater or equal the number of Byzantine nodes. The result formulated Theorem [
Theorem 1. Let U1, ... Um E R be i.i.d. random vectors such that Us G with E[G] g and E|G g|2 I V. Let ún 02 ..., Um attacked copies of 0g 's, where up to q of them are Byzantine. If < b m/2, then Tmeans(-) is A A1-Baann resilient, where
mVV
A
(m 6)2
Proof. See the Appendix.
The exact time complexity for evaluating T'meang (U U.,..., 0m) has no closed-form expression in terms of (m, b, d). However, by sorting in each dimension, we can evaluate Tmean (01, ..,.... Cm
using Oddm log m) operations. The cost is almost linear in practice, and is not much more expensive than evaluating Mean(-). Hence, Tmean()) improves the robustness with only negligible overhead compared to Mean(.).
5 CONVERGENCE ANALYSIS
In this section, we conduct convergence analysis for SGD using Byzantine resilient aggregation rule. such as Krum(-) and T-ean(-). Since general convex optimization setting used, we quote some classic convex analysis theories (see, e.g., (Bubeck 2014), shown in Lemma 3
Lemma 3. Let F; Rd + R be a pustrongly convex and L-smooth functionn Then for I. y E Idd and [0, 1], one has
(VF(2) VF(y), - 2 apllx vll2 1 a [IVF(x)) VF())11
Proof. The p-strong convexity and L-smoothness of F(x) implies
(VF(x) (v)), v) 2 /|| - yl
(VF(x)
-
The conclusion is simple convex combination of these inequalities.
Using Lemma we establish the convergence of SGD as shown in Theorem 2 bound consists linear convergence term similar to that for usual gradient descent methods, and a term caused by randomness. The theorem also suggests theoretically the largest step size: y I--1
The expected error

---

Under review as a conference paper at ICLR 2021
Table 1: Structure of ML.P
Layer type
sotta Mull:
Parameters
Previous Layer
data http=//hathpnt11>>>>d-1111------
Table 2: Experiment Summary.
data set MNIST
#train
#test
#rounds
Batch size
Evaluation metric
60,000
10.000
600
0.1
32
Top-1 accuracy
CIFARIO
50,000
10,000
3,000
5 10
128
Top-3 accuracy
Theorem 2. Suppose that the SGD method with (3) adopted solve problem
where
F: Rdd R p-strongly convex and L-smooth function. Let vi...., Um be local gradi-
(t)
ents at t-th iteration, and (i] ..... -/1)) be the corresponding attacked copies. If the aggregation rule Aggr(.) A-Byzantine resilient, and the step size n satisfies 7 L- then
S 1/111=000) - x²11 1 VI 7P VA,
Elll x²1l]
where x² is the exact solution, and
= V mp 2 1 - L
Proof. See the Appendix.
We remark that if we allow general a E [0, 1] in the proof of Theorem 2 and adjust the correspond- ing step size as S 2(1 aLL-! -1, the decay ratio v is then bounded through
1 200m 2 V1
4a(1 11-44((1- 2)
v1 1-1 L
The optimal lower bound is achieved when 1/2 and y 1-1
EXPERIMENTS
In this section verify the robustness and convergence of Tmean aggregation rules by experi- ments. We use multi-layer perceptron with two hidden layers to handwritten digits classification on the MNIST data set, in take the average value. Table T shows the detailed network structures of the MI.P used in our ex- periments. Then, conduct recognition repeat each experiment for ten times and report the averaged value. In our experiments, we use Mean(-) without Byzantine attack the evaluation metrics. Table 2 lists the details of the data set and the default the corresponding model. Our experiments are implemented by Python 3.7.4 with packages Tensor- Flow 2.4.1 and NumPy 1.19.2, physical node Intel i7-9700 CPU with 32 GB of memory and two NVIDIA GeForce RTX 1080 Ti.
20 worker processes, repeat each experiment for ten times and
convolutional neural network in the Cifar10 dataset,
reference. We use top-1 top-3 accuracy on testing sets as for
6.1 EXPERIMENT SETTING
In our experiment setting, out of the 20 vectors Byzantine vectors (i.e., 20, = 6). different values of will affect different convergence performance. For the MNIST dataset, we take 6 6 and recognition task.
train the experiment: and we take on the Cifar10 dataset to conduct
6.2 GAUSSIAN ATTACK
In Gaussian attack experiment, We use the Gaussian random vector with zero mean and isotopic covariance matrix with standard deviation 200 instead of some correct gradient vectors.

---

Under review as a conference paper at ICLR 2021
From Table B for the MNIST dataset, find that compared with Mean(-) without Byzantine, Tmeans(>) (-) works well, and is more robust when b = 8. However, without trimming the data, Mean(-) is not robust under Byzantine attack. The method of Krum(-) is also robust, while it is relatively weaker than T-eean-))-
For the Cifar10 dataset, set b = 8. From Table 4 the aggregation rule based on the Mcan(.) is not as robust as other aggregation rules, but after trimming the Mcan(-), the output is more robust than before.
Table Accuracy of different aggregations under Gaussian attack MI..
Aggregation rule
Number of iterations
100
150
200
250
300
350
400
450
500
550
600
Mean without Byzantine
0.87
0.88
0.89
0.89
0.90
0.90
0.91
0.91
0.92
0.92
0.93
Krum
0.71
0.82
0.85
0.86
0.87
0.87
0.88
0.89
0.88
0.89
0.89
Mean
0,63
0,62
0,62
0.63
0.64
0.64
0.64
0.65
0.65
0.65
0.66
Tbean(b-
0.80
0.82
0.83
0.84
0.84
0.85
0.85
0.86
0.86
0.86
0.87
Thean(b-
0.82
0.85
0.88
0.89
0.89
0.91
0.89
0.90
0.91
0.91
0.92
Table 4: Accuracy of different aggregations under Gaussian attack in Cifar10.
Aggregation rule
Number of iterations
500
1000
1500
2000
2500
3000
Mean without Byzantine
0.63
0.71
0.73
0.75
0.77
0.79
Krum
0.62
0.70
0.72
0.75
0.76
0.78
Mean
0.51
0.55
0.56
0.57
0.57
0.58
Tb 8)
0.62
0.71
0.73
0.74
0.76
0.77
6.3 OMNISCIENT ATTACK
Assuming that the attackers (Byzantine nodes) know all the correct gradients information. For each Byzantine gradient vector, all correct gradients of the gradient are replaced by their negative sum. In other words, this attack attempts to make the parameter server go into the opposite direction.
For the MNIST dataset, we from Table 5 that when the Byzantine node makes the gradient update direction deviate from the maximum actual update direction, Mean(.) cannot be robust. On the contrary, Krum(-) is more robust, while Tmean(-) shows only weak robustness. Because trim a part of the data intercepted from the mean value for aggregation, it removes the head and tail parts of the entire data set; such that does not decrease much compared to the overall set mean accuracy when is attacked by Byzantine.
For the Cifar10 dataset, Table 6 shows that Krum(-) is more robust than others. Mean-basee ag- gregation behaved badly in data robustness under omniscient attack. If we trim Mean(-), it can be clearly seen that, the output becomes more robust. However, under this attack, Tmean(-) is not as robust as Krum(.).
Table 5: Accuracy of different aggregations under omniscient attack in MLP.
Aggregation rule
Number of iterations
100
150
200
250
300
350
400
450
500
550
600
Mean without Byzantine
0.82
0.83
0.84
0.84
0.85
0.85
0.86
0.86
0.87
0.87
0.88
Krum
0.79
0.81
0.82
0.83
0.83
0.84
0.85
0.85
0.86
0.87
0.87
Mean
0.26
0.26
0.27
0.27
0.28
0.29
0.29
0.30
0.31
0.31
0.32
Tbean(6-
0.23
0.28
0.32
0.38
0.47
0.55
0.61
0.66
0.70
0.73
0.75
Tbean(b- 8)
0.50
0.52
0.57
0.61
0.64
0.67
0.70
0.72
0.74
0.77
0.79
Table 6: Accuracy of different aggregations under omniscient attack in Cifar10.
Aggrogation rule
Number of iterations
500
1000
1500
2000
2500
3000
Mean without Byzantine
0.62
0.71
0.74
0.76
0.78
0.79
Krum
0.64
0.72
0.73
0.74
0.76
0.78
Mean
0.31
0.31
0.32
0.32
0.32
0.33
Tmean(b- 8)
0.42
0.43
0.45
0.45
0.46
0.48
8

---

Under review as a conference paper at ICLR 2021
6.4 GENERAL ATTACK WITH MULTIPLE SERVERS
We evaluate the robust aggregation rules under more general and realistic type of attack. It very popular to partition the parameters into disjoint subsets, and use multiple server nodes to store and aggregate them. We assume that the parameters nodes. The attacker picks one server, and manipulates any floating number by multiplying 10020 with probability of 0.05%. Because the attacker randomly manipulates the values, with the goal that in some iterations the assumpions/prercqqiiittss of the robust aggregation rules are broken, which crashes the training. Such attack requires less global information, and can be concentrated on one single server, which makes it more realistic and easier to implement.
evenly partitioned and assigned to the server
For the MNIST dataset, in Table we evaluate the performance of all robust aggregation rules under multiple serves attack. The number of servers is 20. For Krum(-) and Mean(-), we set the estimated Byzantine number q = 6. We find that Krum(-) and not passed. The intercepted Mean(-) aggregation rules cannot be robust. In this case, they cannot converge to the global optimum. On the other hand, for Tmean(-). different values of will affect different convergence performance. And if we take b = 6, it can also behave robustly.
For the C0 dataset in Table 8 we can find the advantage of the Tmean(.). Neither Krum(-) nor Mean(-) is robust, while Tmean(-) can make the learning robust.
Table 7: Accuracy of different aggregations under multiple server attack in MLP.
Aggregation rule
Number of iterations
100
150
200
250
300
350
400
450
500
550
600
Mean without Byzantine
0.83
0.83
0.84
0.84
0.85
0.85
0.86
0.86
0.87
0.87
0.87
Krum
0.28
0.20
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
Mean
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
Tb 6)
0.80
0.81
0.81
0.82
0.82
0.83
0.83
0.84
0.84
0.84
0.85
Tm 8)
0.81
0.82
0.82
0.83
0.83
0.83
0.84
0.84
0.85
0.86
0.86
Table 8: Accuracy of different aggregations under multiple server attack in Cifar10.
Aggregation rule
Number of iterations
500
1000
1500
2000
2500
3000
Mean without Byzantine
0.65
0.70
0.73
0.75
0.77
0.78
Krum
0.30
0.30
0.30
0.30
0.30
0.30
Mean
0.30
0.30
0.30
0.30
0.30
0.30
Tbean(b 8)
0.64
0.69
0.73
0.74
0.76
0.77
6.5 EXPERIMENT CONCLUSION
From the above experiments, we find that it is difficult for Mean(-) to ensure the robustness of the data when it is attacked by any Byzantine node. When multiple server nodes are used at the same time, Krum(-) also becomes vulnerable. However, after the data is properly trimmed, Tmean(-) can maintain data robustness. Under omniscient attacks, Tmean(.) is not as robust as Krum()) (ruum Tmean(-) still improves a lot compared Mean(.) in this case. The data robustness of T-man(-) is also related to the value of b. We find that when the value of b is closer m/2, it achieve stronger robustness.
CONCLUSIONS
We analyzed the aggregation rules of Tmean(-). We demonstrated that the effectiveness of our approaches can make the FL model robust to Byzantine attacks. We used three different Byzan- tine node attacks to show that the original data be more robustly handled after partial data trimming and averaging operations.
This work focuses T-ean(-). In future work plan to refine the trimming range of Tmean(-) and prove its convergence in a non-convex environment. At the same time, we will add momentum on the basis of Tmean(-), add some constraints strengthen its robustness.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dan Alistarh, Zeyuan Alu, and Jerry Li. Byzantine stochastic gradient descent. arXiv preprint I003:0803 2018.
Peva Blanchard, EI Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Byzantine-tolcrant machine learning. In Conference and Workshop on Neural Information Processing Systems, pp-
118-128, 2017.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT, pp. 177-186. Springer, 2010.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends R in Machine Learning. 2014.
Miguel Castro, Barbara Liskov, et al. Practical Byzantine fault tolerance. In OSDI, volume 99, pp- 173-186, 1999.
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Le Nguyên Hoang, and Sébastien Rouault. Genuinely distributed Byzantine machine learning. In Proceedings of the 39th Sym- posium on Principles of Distributed Computing, pp. 355-364, 2020.
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference on Machine Learning, pp. 4387- 4398. PMLR, 2020.
Richeng Jin, Yufan Huang, Xiaofan He, Tianfu Wu, and Huaiyu Dai. Stochastic-sign SGD for federated learning with theoretical guarantees. arXiv preprint arXiv:2002 10940, 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143. PMLR, 2020.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492 2016.
Leslie Lamport, Robert Shostak, and Marshall Pease, The Byzantine generals problem. In Concur- rency: the Works of Leslie Lamport, pp. 203-226, 2019.
Mu Li, David G. Andersen, Alexander J. Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 27:19-27, 2014.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficieent learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, 1273-1282. PMLR, 2017.
Wenqi Wei, Ling Liu, Margaret Loper, Ka-Ho Chow, Mehmet Emre Gursoy, Stacey Truex, and Yanzhao Wu. A framework for evaluating gradient leakage attacks in federated learning. arXiv preprint arXiv:2004. 2ttt22000.1397, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in Byzantine-robur distributed learning. International Conference on Machine Learn- ing, pp. 7074-7084. PMLR, 2019.
Bo Zhao, Peng Sun, Liming Fang, Tao Wang, and Keyu Jiang. FedCom: A Byzantine-robust local model aggregation rule using data commitment for federated learning. USENIX Security Sympo- sium, 2021.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint /000::/800000822. 2018.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
Proof of Theorem 4 We first assume that uk 's, 0g s, and are all scalars (i.e., d= 1), with variance
== 0². Let (()) 2(2) I ... S ((m) and (()). S ((2)
mm)) respectively, be order
statistics of U1 1/2 ...,, Um and 11 U2 Um Notice that
)
2
1
E
(o(a) g)²
172 25
mm 26)2
(M(()) g)²
(m 2b)²
(uz g)²
(m - 26)²
k==
mo²
(m 2b)²
Similarly, we have
((k] - 9) ))
mo²
m
2h
(m 26)
k=
follows from Lemma 2 that
2b
((k) - S Tmeans (2,, 8m) - 5 2b
((k) g.
2b
k=1
2=
Therefore
E( [(TTeann (01, Ug...., 0m) - =]
m
(Kk) - })}
max
E
(K)) 9
E
Σ
m 26
m
26
k=2b+1
mg²
(m 26)
Now we consider the general case 0k ss 01. is and g are d-vectors, with variance V= = E of, where
g, e.):) -[ S o0²
Using the result for the scalar case, we have
mo?
E| [[(Tmeans(ãn U2,..., 8m) g. 2]
mm 26)
Thus we conclude that
[[| [[lmmmm,n,;,, 0o..., - - g| S d mo?
mV
E|
(m 26)
(m - 22b)
Proof of Theorem 2 Let (()) = Aggr(1) (1)1) ,.... 0m Then
[|x((++1] x"1 = (0)( - (1) x²1l S ||,(10] x [V 99 (4)
It follows from Lemma 3 that
(VF(2())), (0) xx*) [z(00 x²1 + 1
[F(x())111
2L
Then we obtain
(1) x- (FFo((((
11

---

Under review as a conference paper at ICLR 2021
||x(()) - x²11 7 /FF 2x(x!1) - -x", VF((((1))
S [|x0() - x²1 + ( -2) -22 - x1 + 1- a
(aullze!
T.
= (1 2011w)1l000 - + >7- + 2(1 -a) |VF
L
Taking a 1/2 yields
- | -" VVxx' S /1 - 7/1 (|2(() xz11 - =n]|=((0) x=11-
The estimate simplifies to
(|x( x² S 7/1 - /V - -9
By taking the expectation on both sides, we obtain
E[l|ott - x |]] - v [|x0(() - x²1 1I] + E VF. - [00
S v E [| x=' I|] + + E[IVFF(x(0) 119
S n ||x)(1) x= II] AvA.
It can then be easily verified that
E E|l - x=1|| 2n/1l=100) x1 + 77++VVV
S <11111=(00) - xI'l + +2
1=0
1 vT 7H A.
- x1 --11000->''11
4
Finally, the decay ratio can be bounded through
/1 7/1 2
1 11 T.
1
12


Reviews:
[{"review_id": "sKUzyXvhEcG", "reviewer": "Reviewer_j3Cv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "The problem of robust aggregation in FL is very relevant, and the solution investigated in this study is meaningful.\nMy main concern with this paper consists in the lack of originality, as there are already a number of works and frameworks focusing on robust FL aggregation. In particular, Trimmed mean has been already proposed in the previously published work of Yin et al [1]. In that work, FL aggregation based on trimmed mean was already proposed and theoretically investigated, along with other additional aggregation methods. This work is not cited by the authors. In particular, Theorem 2 of this paper seems to be already present in Yin et al.\n\nMoreover, this work is not necessarily focused on FL. The authors assume that clients have the same data distributions and perform $K=1$ SGD at every optimization round. The theoretical setting considered is the one of Distributed Learning and its resilience to Byzantine attacks has already been heavily investigated too.\n\n[1] Yin, Dong, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. \"Byzantine-robust distributed learning: Towards optimal statistical rates.\" In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.\n", "summary_of_the_paper": "This work analyses the use of trimmed mean as robust aggregation rule in federated learning. The study proposes a convergence analysis of the proposed framework, while the robust aggregation schement is assesed on different benchmarks with respect to standard averaging, and to the previous work of Blanchard et al.", "summary_of_the_review": "The novelty of the contribution seems questionable.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Zen1lOq2VQc", "reviewer": "Reviewer_VRXh", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\n# Major Issues\n- The trimmed mean studied in this paper has already been thoroughly analyzed in (Yin et al, 2018). Their analysis is much more general, including strongly convex, non-strongly convex, and non-convex case whereas this paper only prove for strongly convex case. Besides, Yin et al. (2018) also presented a near optimal statistical performance while this paper did not, e.g. theorem 2 does not reflect the actual number of Byzantine worker $q$ influence the rate.\n\n- The studied attack is very weak. The proposed method is not robust against SOTA attacks (Xie et al., 2020; Baruch et al., 2019). \n\n- Lack of baselines. There are abundant aggregation rules for Byzantine resilient learning. Even the simple median based algorithms are not thoroughly compared.\n\n# Obvious mistakes\nThere are many obvious mistakes in the paper\n- Last line of page 1, why is the geometric median a variant of mean-based aggregation rule?\n- Page 3, \"Based on these attack methods, there exist defense methods, such as robust aggregation, secure aggregation, encryption, etc\". The secure aggregation and encryption are not defense to these attacks.\n- Theorem 2, $0<L\\le \\mu$?\n\n# Minor Issues\n- The reference style should be improved\n    - e.g. paragraph 2 of page 1: \"...state machine replication strategy (Alistarh et al. (2018))\" should be \"...state machine replication strategy (Alistarh et al., 2018)\".  \n- \"... on the data model Bottou (2010)\" should be \"... on the data model (Bottou 2010)\" \n- \"This is the problem not fully addressed in previous works\" should be \"This problem is not fully addressed in previous works\"\n- Page 1 paragraph 3, the \"single miner attack\" and \"multiple server attacks\" seem not very common, could you provide definition or some explanation?\n- Figure 1 (a) \"Master serves\" => \"Master servers\", caption \"miner serves\" => \"miner servers\".\n- Page 3, \"Zhao et al. expanded\" no year information.\n- Page 3, \"gradient leakage (Bag\u0002dasaryan et al. (2020)\", however, the reference is backdoor attack, not the graident leakage attack.\n- Page 4, Definition 1 needs reformulated.\n- In many occurances, the authors says they trimmed the data while they only trimmed the gradient.\n\n====\n\n# Reference\n\n- Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650–5659. PMLR, 2018.\n- Xie C, Koyejo O, Gupta I. Fall of empires: Breaking Byzantine-tolerant SGD by inner product manipulation[C]//Uncertainty in Artificial Intelligence. PMLR, 2020: 261-270.\n- Baruch M, Baruch G, Goldberg Y. A little is enough: Circumventing defenses for distributed learning[J]. arXiv preprint arXiv:1902.06156, 2019.", "summary_of_the_paper": "This paper considers the trimmed mean function as the aggregation rule for the byzantine resilient distributed learning. The authors provide a theoretical convergence for strongly convex objectives. Besides, the authors empirically compare trimmed mean with krum and average.", "summary_of_the_review": "The theoretical contribution of this work is limited and they have ignored many existing defenses and attacks. Besides this paper contains too many obvious mistakes, typos, and the writing/template clearly does not follow the ICLR guideline.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "MSv2WXFLHw", "reviewer": "Reviewer_AKLN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper is of good readability. The main idea of this work is not difficult to understand. However, there are some concerns as listed below:\n\n1. The proposed aggregation rule Tmean seems identical to 'coordinate-wise trimmed mean' [1]. Also, the theoretical estimation and analysis in the paper seem rougher than that in [1]. Could the authors comment on this and compare their work with [1]?\n\n2. The empirical results in this work are not solid enough. The authors only compare their methods with Krum and mean. There are many other aggregation rules, such as geometric median, centered-clipping [2], and so on. Also, the authors do not evaluate their methods under some advanced attacks [3, 4].\n\n3. The authors propose Tmean for federated learning (FL), where the data of different clients can be heterogeneous. However, their analysis is based on the i.i.d. assumption, which usually does not hold in FL.\n\n\n[1] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650–5659. PMLR, 2018.\n\n[2] Sai Praneeth Karimireddy, Li He, and Martin Jaggi. Learning from history for Byzantine robust optimization. In ICML 2021 - 37th International Conference on Machine Learning, 2021.\n\n[3] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation. In UAI - Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, 2020.\n\n[4] Moran Baruch, Gilad Baruch, and Yoav Goldberg. A Little Is Enough: Circumventing Defenses For Distributed Learning. NeurIPS, 2019.", "summary_of_the_paper": "The authors propose the aggregation rule Tmean for federated learning. They show the effectiveness and Byzantine robustness of Tmean by both theoretical analysis and empirical evaluation. ", "summary_of_the_review": "Generally speaking, although most of the results are correct, the main contribution of this work seems very similar to existing works and the empirical evaluation is not solid enough. Due to these reasons, this submission is below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper suggests a new aggregation rule for federated learning in order to mitigate Byzantine attacks. However, as the reviewers pointed out, the theoreticial results of the paper are weak and incremental and the experiments are not solid.
Decision: Reject