GAIN: Enhancing Byzantine Robustness in Federated Learning with Gradient Decomposition
Authors: Yuchen Liu
Chen Chen
Lingjuan Lyu
Fangzhao Wu
Tianlei Hu
Sai Wu
Gang Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Byzantine Robustness.

Abstract: Federated learning provides a privacy-aware learning framework by enabling participants to jointly train models without exposing their private data. However, federated learning has exhibited vulnerabilities to Byzantine attacks, where the adversary aims to destroy the convergence and performance of the global model. Meanwhile, we observe that most existing robust AGgregation Rules (AGRs) fail to stop the aggregated gradient deviating from the optimal gradient (the average of honest gradients) in the non-IID setting. We attribute the reason of the failure of these AGRs to two newly proposed concepts: identification failure and integrity failure. The identification failure mainly comes from the exacerbated curse of dimensionality in the non-IID setting. The integrity failure is a combined result of conservative filtering strategy and gradient heterogeneity. In order to address both failures, we propose GAIN, a gradient decomposition scheme that can help adapt existing robust algorithms to heterogeneous datasets. We theoretically show that integrating exisiting robust AGRs into our GAIN can mitigate the deviation of aggregated gradient, thus improve the performance. Experiments on various real-world datasets verify the efficacy of our proposed GAIN

Under review conference paper ICLR 2023
GAIN: ENHANCING BYZANTINE ROBUSTNESS IN FEDERATED LEARNING WITH GRADIENT DECOMPO- SITION
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning provides privacy-aware learning framework by enabling par- ticipants to jointly train models without exposing their private data. However, federated learning has exhibited vulnerabilities to Byzantine attacks, where the adversary aims to destroy the convergence and performance of the global model. Meanwhile, we observe that most existing robust AGgregation Rules (AGRs) fail to stop the aggregated gradient deviating from the optimal gradient (the average honest gradients) in the non-lID setting. We attribute the reason of the failure of these AGRs to two newly proposed concepts: identification failure and integrity failure. The identification failure mainly comes from the exacerbated curse dimensionality in the non-IID setting. The integrity failure is a combined result of conservative filtering strategy and gradient heterogeneity. In order address both failures, we propose GAIN, a gradient decomposition scheme that can help adapt existing robust algorithms to heterogeneous datasets. We also provide con- vergence analysis for integrating existing robust AGRs into GAIN, Experiments on various real-world datasets verify the efficacy of our proposed GAIN.
INTRODUCTION
Federated Learning (FL) (McMahan et al. 2017) is a privacy-aware distributed machine learning paradigm. It has recently attracted widespread attention result of emerging data silos and grow- ing privacy awareness. In this paradigm, data owners (clients) repeatedly use their private data compute local gradients and send them to a central server for aggregation. In this way, clients can collaborate to train a model without exposing their private data. However, the distributed property of FL also makes it vulnerable Byzantine attacks (Blanchard al. 2017 Guerraoui al.) 2018). During the training phase, Byzantine clients can send arbitrary messages to the central server to bias the global model. Moreover, it is challenging for the central server to identify the Byzantine clients, since the server can neither access clients' training data nor monitor local training processes.
order to defend against Byzantine attacks, the community has proposed wealth of defenses (Blanchard et al. 2017; Guerraoui et al. 2018 Yin et al., 2018). Most defenses abandon the aver- aging step adopted by conventional FL frameworks, e.g., FedAvg (McMahan et al. (017). Instead, they use robust AGgregation Rules (AGRs) to aggregate local gradients order to defend against Byzantine attacks. Most existing robust AGRs assume that the data distribution on different clients is identically and independently distributed (IID) (Bernstein al. 2018 Ghosh al. (2019). However, the data is usually non- independent and identically distributed (non-llD) in weal-world FL applica- tions (McMahan et al. 2017]] Karimireddy et al., 2020; Kairouz et al. 2021). As result, in more realistic non-lll settings, most robust AGRs fail to defend against Byzantine attacks, and thus suffer from significant performance degradation (Karimireddy et al., 2022 Acharya et al. 2022).
To investigate the cause of the degradation, we perform a thorough experimental study on various ro- bust AGRs. Close inspection reveals that the reason behind the degradation is different for different AGRs with different types of aggregation strategies. For conservative AGRs that only aggregate few gradients to get rid of Byzantines, they suffer from integrity failure. The integrity failure describes that an AGR can only identify few honest gradients for aggregation. This failure will lead to an Karimireddy
gregated gradient with limited utility due the gradient heterogeneity (Li al. 2020:

---

Under review conference paper ICLR 2023
et 2020p the non-III setting. For radical AGRs that aggregate as many gradients as possible to avoid such deviation, they suffer from another identification failure. The identification failure means that an AGR fails to distinguish between honest and Byzantine gradients. This failure is mainly due the curse of dimensionality (Guerraoui et al. 2018 Diakonikolas et al. 2017) aggravated by the non- non-IIDness. Both failures deviate the aggregated gradient from the optimal gradient (the average of honest gradients). As result, most existing AGRs fail to achieve satisfactory performance in the non-IID setting.
Motivated by the above observations, we propose a GrAdient decomposItioN method called GAIN that can handle both failures in various non-llI settings. In particular, to address the identification failure due the curse of dimensionality, GAIN decomposes each high-dimensional gradient into tow-dimensional groups for gradient identification. Then, GAIN incorporates gradients with low identification scores into final aggregation to tackle the integrity failure.
Our contributions in this work are summarized below.
We reveal the root reasons for the performance degradation of current robust AGRs in the non-IID setting by proposing two new concepts: integrity failure and identification failure. Integrity failure origins from the gradient heterogeneity, and identification failure is result of the aggravated curse of dimensionality in the non-lll setting,
We propose novel and compatible approach called GAIN, which applics robust AGRs on the decomposed gradients, followed by identification before aggregation, rather than di- rectly operating on the original gradients as the existing defenses (Multi-Krun Krum (Blanchard) et al. 2017). Bulyan (Guerraoui et al. 2018), etc) do.
We also provide convergence analysis for integrating existing robust AGRs into GAIN. In particular, we provide an upper bound for the sum of gradient norms.
We also offer empirical experiments on three real-world datasets across various settings to validate the effectiveness and superiority of our GAIN.
2 RELATED WORKS
Byzantine robust learning first introduced by Blanchard et al. (2017). Subsequently, a range of works study the robustness against Byzantine attacks by proposing various robust AGgregation Rules (AGRs) under the IID setting. Generally, categories: conservative AGRs and radical AGRs.
classify the current robust AGRs into two
Typical conservative AGRs, including Bulyan (Guerraoui et al. 2018), Median (Yin et al. 2018). Trimmed Mean (Yin et al. (018), etc., only aggregate few gradients to reduce the risk of the intro- duced Byzantine gradients. Bulyan (Guerraoui et al. 2018) applies variant of trimmed mean post-processing method handle the curse of dimensionality. Yin al. (2018) theoretically ana- lyze the statistical optimality of Median and Trimmed Mean. The radical AGRs, c.g., Multi-Krum (Blanchard et al. 2017). DnC (Shejwalkar & Houmansadr 2021). incorporate many gradients possible to avoid such deviation. Multi-Krum is distance- based AGR proposed by Blanchard et al.] (0117). (Pillutla et al.] 2019) discuss the Byzantine robustness of Geometric Median and propose computationally efficient approximation. [Shejwalkar & Houmansadr (2021) propose to perform dimensionality reduction using random sampling, followed by spectral bbased outlier removal. Re- cently, a quantity of works (Allen-Zhu et al., 2020; Karimireddy et al.] [202T] I, [aarhakkhami et al.] 2022) discuss the effect of distributed momentum Byzantine robustness from different perspec- tives. However, in more realistic FL applications where the data non-IID, the efficacy of these defenses are quite limited. They fail to obtain high-quality aggregated gradient in the non-IID set- ting, thus suffer from significant performance degradation.
-rased
Recently works have also explored defenses that be applicable the non-IID setting. Park et al. (2021) can only achieve Byzantine robustness when the server has a validation set, which compro- mises the privacy principle of the FL (McMahan et al., (2017). Data & Diggavi (2021) adapt robust mean estimation algorithm to FL combat Byzantines in the non-llD setting. However, requires (dd²) time (d is the number of model parameters), which is unacceptable due to the high dimen- sionality of model parameters. [EI-Mhamdi et al. (2021) consider Byzantine robustness in the asyn- chronous communication and unconstrained topologies settings. AAcharya et al. (2022) propose

---

Under review conference paper ICLR 2023
apply geometric median only to the sparsified gradients to save computation cost. Karimireddy et al. (2022) perform bucketing process before aggregation to reduce the gradient heterogeneity. These methods guarantee convergence of SGD in the existence of Byzantines. However, convergence is not enough the context non-convex, high dimensional case neural networks (Guerraoui al.) 2018). These methods lack of the guarantee that the aggregated gradient does not deviate from the optimal gradient (the average of honest gradients). As result, they may lead to convergence towards ineffectual models.
3 NOTATIONS AND PRELIMINARIES
Notations. For any positive integer N+, denote the set [1. [l....,.t] by [n]. The cardinality of a set denoted by #S or [S]. For a real number x: E E, we use |a|] to denote the absolute value number We denote the & norm of vector by |æ]|| We use [z]; to represent the j-th component of vector The sub-vector of vector indexed by index set I denoted by [x), ([æ],) ..... [ and l J the number indices. For a random variable X, we use [[X] and Var[X] to denote the expectation and variance of X, respectively.
where J = (ji..... Jx .......................
Federated learning. We consider the federated learning system with a center server and n clients following Blanchard et al. (2017); Yin et al. (2018); Guerraoui al. (2018). Then the ohjective minimize loss ((w) defined as follows.
((w) n Σ (iww), where (.()) 1Eg, (Cw; E:)], [n]]
(I)
where t is the model parameter, L is the loss function on the i-th client, is the data distribution on the i-th client, and L(w; {) is the loss function.
In the 1-th communication round, the server distributes the parameter w' to the clients. Each client i conducts several epochs of local training local data to obtain the updated local parameter w/. Then, client computes the local gradient g as follows and sends the server.
gi = w wi.-
(2)
Finally, the server collects the local gradients and uses the average gradient to update the global model.
w w" g', g
g
This process is repeated until the global model converges or the number of communication rounds reaches the value T.
Byzantine threat model. In real-world applications, not all clients in FL systems are honest. In other words, there may exist Byzantine clients in FL systems (Blanchard et al. (017). Suppose that adversary controls f Byzantines clients among the total clients. Let B [m]] denote set of
Byzantine clients and H [m] \ B denote the set of honest clients. In the presence of Byzantine clients, the uploaded message of client in the 1-th communication round is
w
w'. i H,
gi
(4)
i B,
where represents arbitrary value.
Robust AGRs. Most solutions replace averaging step by robust alternative to defend against Byzantine attacks. More specifically, the server aggregates the gradients and updates the global model as follows.
w' O¹, g'
(5)
where g' the aggregated gradient, and A a robust AGR, e.g., Multi- Krum (Blanchard et al. 2017). Bulyan (Guerraoui et al. 2018).
For notation simplicity, we omit the superscript i of the gradient symbols when there is no ambiguity the rest of this paper.

---

Under review conference paper ICLR 2023
4 FAILURES OF EXISTING ROBUST AGRS IN THE NON-IID SETTING
Most robust AGRs focus on Byzantine robustness in the IID setting (Blanchard et al. 2017 Guer- raoui al. 2018). When the data is non-III,, the performance of these robust AGRs drop drastically (Shejwalkar & Houmansadr] 202T: Karimireddy et al. 2022). order to understand the root cause of this performance drop, we perform an experimental study on various robust AGRs. Particularly, we examine the behaviors of robust AGRs under the attack of 20% Byzantines in both IID and non- IID settings on CIFAR- 10 (Krizhevsky et al. 2009) in Figure I More detailed setups are covered in Appendix A A close inspection reveals that AGRs of different types demonstrate different failures in the non-III setting. As mentioned earlier in Sec. 2 most robust AGRs fall under the umbrella of either conservative AGRs or radical AGRs. Next, we choose two representative AGRs (Bulyan and Multi-Krum) from both types, and summarize how they fail in the non-IlD setting.
Non-IID
Attack
Attack
Honest Ratio
1.0
Aceuracy (%5
80 60
Honest Ratio
Accuracy (%)
60
60
0.5
40
05
20
28
0.0
0
200
400
200
400
0.0
200
400
200
400
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
(a) Honest ratio of conservative AGR.
(b) Performance of conservative AGR.
(c) Honest ratio of a radical AGR.
(d) Performance of radical AGR.
Figure The behaviors conservative AGR (Bulyan) and a radical AGR (Multi-Krum) under the attack of 20% Byzantines in both IID and non- non-III settings on CIFAR-10 10 dataset. More detailed setups covered in Appendix A The dotted lines represent the performance without Byzantines.
Integrity failure of conservative AGR. We take closer look at a representative conservative AGR Bullan (Guerraoui et al. 2018). Specifically, we consider am indicator called honest ratio the ratio of selected honest client number to all selected client number (# selected honest clients # selected clients) of a robust AGR in each communication round. A higher honest ratio suggests a higher proportion of honest gradients among the gradients aggregated by AGR. In particular, honest ratio (0) suggests that all gradients that the AGR aggregates are honest ( (Byzantine). In Figure [(a] report the honest ratio of the conservative AGR (Bulyan) in both IID and non-IID settings. The results show that in both settings, all the gradients aggregated by the conservative AGR are honest, which demonstrates the strong Byzantine filtering ability of a conservative AGR. Unfortunately, we find that Byzantine filtering is not enough in the non-IID setting. The results in Figure ([bb) illus- trate that the accuracy significantly lower in the non-IID setting. This performance degradation implies a sharp deviation of the aggregated gradient from the optimal gradient (the average of hon- est gradients) in the non-IID setting. Honest gradients are heterogeneous when the data is non-IID (Li et al. 2020; Wang et al. 2021 Karimireddy et al. (2000). As result, aggregating only partial honest gradients will deviate the aggregated gradient from the optimal gradient, and eventually lead to ineffectual models. Therefore, in addition to Byzantine filtering, it is also crucial incorporate sufficient honest gradients into aggregation in the non-IID setting.
Identification failure of a radical AGR. We closely examine a typical radical AGR Multi-Krum (Blanchard et al. 2017). In Figure [[c] we demonstrate the honest ratio of the radical AGR in both II and non-III settings. As shown in the figure. the radical AGR succeeds in identifying honest gradients for aggregation in the IID setting but fails in the non- IID setting. The critical reason behind is that while the curse of dimensionality (Guerraoui et al. 2018) can be provably addressed in the IID setting, it will be aggravated and intractable in the IDD setting. When the data is non- IID, Byzantines can easily exploit the curse of dimensionality to compromise radical AGRs, thus degrade the utility of global model as shown in Figure [[d] Therefore, it is critical to overcome the aggravated curse of dimensionality in the non-III setting.
As analyzed above, most robust AGRs suffer from identification failure and integrity failure due to gradient heterogeneity and the aggravated curse of dimensionality in the non-Ill setting. As a result, they fail to stop the aggregated gradient deviating from the optimal gradient, which leads to unsatisfactory performance in the non-III setting.

---

Under review conference paper ICLR 2023
5 PROPOSED METHOD
Our observations in Sec. clearly motivate the need for a more robust defense to defeat Byzan- tine attacks in the non-llI setting. Inspired by these observations, we propose a novel GrAdient decomposItioN method called GAIN, which consists of three stages follows.
Decomposition. First, GAIN decomposes the gradients gradient identification. The decompo- sition is specified by a partition of set [d,, where is the dimension of gradients. Let (JI....-hp Tpl denote the partition, where p is the number of groups. Particularly, the partition satisfies:
Jq + 0.
4q E lpl and
[
J.: and To Jn 0. Vq. e lll.9 d'
Jg.
(6)
where represents empty set, V respresents the union of sets, and n respresents the intersection of sets. Each gradient is correspondingyy decomposed into p sub-vectors as follows.
g, (4)
19,3,,, i [m]. [p],
(4) is the q-th sub-vector of gradient g.- where g. Identification. Then, GAIN applies any robust AGR A each group of sub-vectors corresponding Tgi
goo)
A(gi") (9)
E [p).
(8)
where g(9) is the aggregation result of group q. By performing aggregation groups of low- dimensional sub-vectors, GAIN can circumvent the curse of dimensionality. thus avoid the identifi- cation failure discussed in Sec. In other words, g(s) can get rid of Byzantines.
Note that gl may still suffer from deviation due to the integrity failure of the AGR A as illustrated
Sec. 4 Therefore, it is inappropriate to directly use the aggregation results (g(z), : E [p] as the final output. Instead, we use g( honest reference to compute identification scores for each client as follows.
(c) = |gg gl E [n], E [p].
(9)
Since the grie aggregation result glo) can get rid Byzantines, the identification score (()) can provably characterize the potential for the (4) being sub-vector of an honest gradient. Then,
GAIN collects the identification scores from all groups and computes the final aggregation result.
In particular, the final identification score 8; of each client is composed of its identification scores received from all groups as follows.
E [m].
(10)
Aggregation. To avoid integrity failure, GAIN selects total n f gradients with the lowest identi- fication scores for aggregation. Let denote the index set of selected gradients, then the average of selected gradients is output as the final aggregation result as follows:
Σ 9. RE
(II)
Note that in the first stage (Decompositionn) of GAIN, A could be any e-resilient AGR (Definition) I The key difference lies in that all the existing robust AGRs (Multi-Krum, Bulyan, etc) directly operate on the original gradients before aggregation; instead we propose to apply robust AGRs on the decomposed gradient, followed by identification before aggregation. In this way, we help enhance the identification ability and integrity of the current robust AGRs that satisfy the c-resilient property (Definition [T in the non-lID setting. Detailed theoretical analysis and empirical support be referred Sec. 6 and Sec. respectively.

---

Under review conference paper ICLR 2023
THEORETICAL ANALYSIS
In this section, we provide theoretical convergence analysis for GAIN.
analyze popular FL model widely considered by KKrrmireddy al. (2021 2022): Acharya et al. 2022). In particular, each local gradient is computed by SGD as follows.
g (www"; : E E [n]]
(12)
where ? represents minibatch uniformly sampled from the local data distribution & in the t-th communication round, and VL(w" <.) represents the gradient of loss over the minibatch c:-
We make the following assumptions, which are standard in FL (Karimireddy et 2021 2022 AAcharya et al. (022).
Assumption (Unbiased Estimator). The stochastic gradients sampled from any local data distri- bution are unbiased estimators of local gradients over Red for all clients, i.e.
E [V:: E = VL((w), Yw E R
(13)
Assumption (Bounded Variance). The variance of stochastic gradients sampled from any local data distribution uniformly bounded over B for all clients, i.e,, there exists Z 0 such that
V[ + VL,(w))l' o², Yw E RR [n).tE
(14)
Assumption (Gradient Dissimilarity). The difference between the local gradients and the global gradient uniformly bounded over R for all clients, i.e, there exists x 2 such that
[V) V[ [[w))] <
Ve E R [m].
(15)
We consider arbitrary non-convex loss function C(-) that satisfies the following Lipschitz condition. This condition widely applied in convergence amalysis of Byzantine-robur federated learning (Karimireddy et al. 2022, AlleenZhu et al. 20200) El-Mhamdi et al. (022))
Assumption 4 (Lipschitz Smoothness). The loss finction is L--Lipschitz smooth with respect over Rd, L.e.
[V[(w) - VL(w")Il & l|w - -w'],, Vw, w' e R.d.
(16)
Assumption M establishes the unbiased property of stochastic gradient. Assumption bounds the variance of the stochastic gradients within a client. And Assumption 3 a common measure of the non-IID level federated learning (Data Diggavi 2021 Karimireddy et al. 2020 2022).
We further establish the Byzantine resilience the base AGR A.
Definition 1 (c-resilient AGR). Let A be an AGR. If for any input (æi...., In) such that there exists set H E [n] of size at least [H]] > n1/2 that satisfies:
E E|xx - x 112 S p², Vi,
(17)
the oulput of A satisfiex:
El xn)) æ1 $ < ep² where x |7|
Σ Rh. NER
(18)
then the AGR called c-resilient.
In fact, most popular AGRs (Blanchard et al. 2017 Guerraoui et al. 2018 Karimireddy al. 2021 2022) are shown to satisfy this e-resilient definition (Faahadkhaai et al. 2002).
We show that given any c-resilient base AGR A, our GAIN can help the global model to reach a better parameter point.
Proposition 1. Suppose Assumptions 7 t1 (oold and let 1/2L. Given c-resilient robust AGR A, we start from un and run GAIN for communication rounds, it satisfies
3
((w0)
(19)
161.
where
f2
è² =
0
(N²
+
+ +
](1 m).
(20)
(n
f)z

---

Under review conference paper ICLR 2023
Please refer to Appendix [ for the proof. From one hand, Proposition provides an upper bound for the sum of gradient norms in presence of Byzantine gradients. Equation (19) indicates that as the number of communication rounds increases, we can find an approximate optimal parameter w with [VL(w) S e. Furthermore, as the number of sub-vectors p increases, the approximation becomes better, Le., c² decreases, which validates the efficacy of our method. From another hand, Proposition | characterizes the fundamental difficulties of Byzantine-robust federated learning in the non-IlD setting. The negative term -e² on the RHS implies that FL may never achieve a con- vergence point. By contrast, the global model may wander among sub-optimal points. What's more, even after reaching the convergence point, the glohal model may step to sub-optimal in the next communication round. A detailed comparison of the convergence rate between our method and recent works is presented in Appendix B.2
7 EXPERIMENTS
7.1 EXPERIMENTAL SETUPS
Datasets. Our experiments are conducted on three real-world datasets: CIFAR-10 (Krizhevsky et al. 2009). CIFAR-100 (Krizhevsky et al.] 22099, subset of ImageNet (Russakovsky al.) 2015) refered as ImageNct-12 and FEMNIST (Caldas et al, 2018). CIFAR-I0 dataset consists of 60,000 x2 32 color images in 10 classes, with 6,000 images per class. There are 50,000 training images and 10,000 test images in CIFAR-IO dataset. CIFAR-100 dataset consists of 60,000 x2x32 color images in 100 classes, with 600 images per class. There are 50,000 training images and 10,000 test images in CIFAR-100 dataset. ImageNet-12 consists of 15,600 color images in 12 classes, with 1,300 images per class. There are 12,480 training images and 3,120 test images in this subset of ImageNet. FEMNIST consists of 817,851 28x28 gray-scale images in 62 classes. There are 772,066 training images and 857,85 test images in FEMNIST.
For FEMNIST, the data naturally partitioned into 3,597 clients based the writer of the digit/character. For each client, we randomly sample a 0.9 portion of data as the training data and let the remaining 0.1 portion of data be the test data following Caldas et al. (2018). Intuitively, the data distribution across different clients is non-III.
Evaluated attacks. We consider six representative attacks BitFlip (Allen-Zhu al. 2020). La- belFlip (Allen-Zhu et al., 2020), LIE (Baruch et al. 2019), Min-Max (Shejwalkar & Houmansadr 2021). Min-Sum (Shejwalka war & Houmansadr] [02 and TPM (Xie et al. 2020). The detailed hy- perparameter setting of the attacks are shown in Table 5 in Appendix(D)
Baselines. We consider 6 robust AGRs: (Blanchard et al. 2017), Bulyan GGurraoui et al. 2018)
Median (Yin et al.) 2018), RFA (Pillutla et al. 2019). DnC (Shejwalkar & Houmansadri 2021
RBTM (EI-Mhamdi et al., 2021). Among the above six defenses, Bulyan, Median, and RBTM
are conservative, and Multi-Krum RFA, and DnC are radical. We compare each AGR with its
variant with GAIN. The detailed hyperparameter settings of the robust AGRs are listed in Table 6 in Appendix D
We use top-1 accuracy, i.c., the proportion of correctly predicted testing samples total testing samples, to evaluate the performance of global models. We run each experiment for 5 times and report the mean and standard deviation of the highest accuracy during the training process.
Evaluation.
Other settings. We utilize AlexNet (Krizhevsky et al. 2017). SqueezeNet (landola et al. 2016). ResNet- 18 (He al. 2016) and four-layer CNN (Caldas et al. 2018) for CIFAR-IO. CIFAR- ImageNet-12 12 and FEMNIST, respectively. The number of Byzantine clients of all datasets is set to f = 0.2 n. For the partition of set (1...., d). we randomly partition {l,..., d} into p disjoint subsets 0.2
with equal size. Please refer to Table in Appendix D for more details.
7.2 EXPERIMENT RESULTS
Main results. Table Dibletillsttrate the results of different defenses against popular attacks on CIFAR- 10, CIFAR- 100, ImageNet-12 and FEMNIST. From these tables, observe that:

---

Under review as conference paper ICLR 2023
(1) Integrating current defenses into our GAIN generally outperform all their original versions on all datasets, which verifies the efficacy of our proposed GAIN. For example, GAIN improves the accuracy of Median by 15.93% under Min-Sum attack on CIFAR-IO.
(2) The improvement of DnC+GAIN to DnC' is relatively mild on CIFAR-IO. Our interpre- tation is that when the dataset is relatively small and simple, DnC is capable of obtaining a rational gradient estimation. Nevertheless, FEMNIST and ImageNet-12. DnC fails to achieve satisfactory performance under Byzan- tine attacks.
larger and more complex datasets, i.e.,
(3)
We find that although RFA collapses on FEMNIST, integrating into our GAIN can still improve it to satisfactory performance. Our illustration is that although the aggregated gra- dient of RFA deviates from the optimal gradient, gradients when combined with GAIN, As a result, GAIN-RFA is still effective on FEM- NIST.
still assist in identifying honest
(4) Note that the improvement GAIN on conservative methods is greater. We contribute this phenomenon to the gradient heterogeneity due to non-IID data. Excluding honest gradi- ents deviates the aggregated gradients from the average of honest gradients, thus degrading the performance of conservative methods. When the non-IlD degree increases, the gra- dient heterogeneity increases. As a result, the impact of excluding honest gradients may even be larger than incorporating Byzantine gradients. Therefore, the improvement the conservative AGRs greater.
Table 1: Accuracy (mea of different defenses under attacks on CIFAR-10, ImageNet- 12, FEMNIST, and CIFAR-100.
CIRAR-IE
CIAR-IE
T/ldFsy
Vile Mes
IFM
1/6
Min
MLB loum
1300 836
13:0 0.33
37.53 A 1.0
31.8 MLL
3u6 6:33
11.3 1/03
35.5
17:17
338
36.77
23.85 3.41
15:40 1-200-00
34bys
0.14
2010
35.1
35.541 1:8
2013 1113
99.4 0m
09.33
68.99 0.0
1.54
$1344 0.7
56.3
43.68
4377
02.84 1.11
99.56 8 0:24
69:4402
1:34
65.99 0.15
40.3
9:35
53.30
190
56.30 031
40.43
62.92
36.16
1.34
36.86
0.0
40/4
0 8.64
03.63 2:00
2 833
44.39 2.31
0357
16.22
4015
21:55 0:55
25.662
22.03
3.00
23:40
20.33 01 8.53
28.96 1136
REN-GARN
$1.85
030
0.30
32,99
54.36
5.001
42.44
42.42
26.36
38.39
1612
8 1.89
Duc
25.5 + 135
0003
-1
01.07 9/1
9:31
21.1
1UN
S00W 0.2
42.55
$3.0
85
41
2000 01 1.53
6.25-:20
-GAN
BITIN-AAI
96.1 1 630
66.55
0.19
$2.00 & 1.56
313
53.63
0.56
40.01
346
394
3135 8 676
41.51
0441
03.39 1970
FESINERT
1.33
Mil KAEHCAAN
86.6- 1.10
14.6 8
61.0
1:35
63.0
0114
3.99
660 -
60.0 000
1:0
540
-11)
00.57
11.44 1.0
6633
11.%
14
66.66
62.24
07.44
08.11
600
6616
1164
000
76:5
1:40
01
2196
6.33
55.90 0.55
58.00
1115
7660
18.07
1.16
50-0-113
13.0 1150
BEA
556-555
(001
546.5
5:5
526.1
559 0.39
6113
01.31
2354
0130 1.67
REA-GAIN
6666 079
DRC-GAIN
6471 009
8038-04 0.4
82.4 033
7657
359
15.41
0.2
62.75 33
66.19 1.53
63.1
66.42
319
65,85
1.20
6538 1148
65.85 1 100
$237
2334
76.
6618
11:30
52.44
35.77
0:00
0000
30:39:
BUTIL-CAIN
$499 2 134
85.44
033
13.91.0
06.4 334
7539 113
02.6 133
6639
1-3
61.32
2037
332
2131 1 1.4
6634 032
63.40 4:07
Number of sub-vectors. We study the influence of sub-vector number p on the heterogencous CIFAR-10 dataset. Shows the performance and honest ratio of a conservative AGR (Bulyan) and a radical AGR (Multi-Krum) across p = (100, 1000}. The results show that for both conser- vative and radical AGRs, GAIN with a larger sub-vector number p can select a higher proportion of honest clients and achieve better performance. When the sub-vector number p increases, GAIN can better handle the identification failure and the integrity failure, which corresponds to our theoretical analysis in Sec. 0
Results on different levels of non-lID. We discuss the impact of non-lID level of data distribu- tions. We modify the concentration parameter 3 to change the non-IID level. smaller ,9 implies a higher non-III level. Table 2 demonstrates the accuracy of different defenses under LIE attack on CO dataset across 3 10.3 0.7). Other setups follow the default setup of the main exper- iments illustrated in Sec. 7 and Appendix D As shown in Table 2 all the existing AGRs that combined with GAIN achieve better performances than their original versions, which validates that integrating into our GAIN can effectively defend against Byzantine attacks under different non IID levels. Moreover, when the level of non-IID higher, the improvement on robust AGRs more

---

Under review conference paper ICLR 2023
p
100
1000
Aceuracy (%)
Soopase (%)
Accuracy (%)
1.0
1.0
Accuracy
40
40
100
200
200 Communication Rounds
0.0
100
100
200
0.0
100
200
Communicattio Rounds
Communication Rounds
Communication Rounds
(a) Performance of a conservative AGR.
(b) Honest ratio of a conservative AGR.
Performance of radical AGR.
(d) Honest ratio of radical AGR.
Figure 2: The behaviors a conservative AGR (Bulyan) and radical AGR (Multi-Krum) across sub-vector number p 100, 1000 under the attack of 20% Byzantines in the non-IID setting on 10 dataset. More detailed setups covered in Appendix D.2
significant. The results further confirm that our GAIN can overcome the failures aggravated under a higher non-IlD level.
Table 2:
Accuracy (sda of different defenses against LIE attack under different non-IID levels on CIFAR-10. A smaller 3 implies a higher non-IID level.
Multi-Krum
Mull-Krum+GAIN
Bulyan
Bulyus<GiAIN
Malian
MalianaGAIN
0,3
12.19
100
$2.0 1 0.74
2816 1. 0.41
42.81
0.833
25.62 0.8
40.97 0.88
0.7
31.11 = 0.54
55.4 = 0.60
46.72 145
51.29 0.35
34,04 = 0.29
53.34 0.08
8
RBA
RFA+GAIN
DaC
DaCAGAIN
RATM
RATM&GAIN
0.3
20.08
0.13
48.7 + 0.84
59.99 = 181
69.21 00062
37.67 = 0.18
49.27 0.05
0.7
18.11
= 0.24
53.25 + 1.41
62:15 0.75
62.48 0.55
48.43 = 0.22
52.25 = 1.36
Results different number of Byzantine clients. We also conduct experiments across differ- ent number of Byzantine clients. Other setups follow the default setup of the main experiments in Sec. [7.] and Appendix D Table 33 demonstrates the results of different defenses under LIE at- tack across f = (5, 15} Byzantine clients CIFAR-IQ 10 dataset. As shown in Table our GAIN outperforms the corresponding baselines across all Byzantine client numbers.
Table 3: Accuracy (sd) of different defenses against LIE attack with different Byzantine client numbers f = (5, 15) on C0 The number of total clients is n = 50.
Multi Knum
Muki KrumeGAIN
Bulyan
DulynnGGAIN
Median
MediuneGAIN
5
41.65 1.78
61.24 = 001
56.28 = 1.44
58,27 0.17
46.91 # 1.36
57.69 LS5 30.95 + 0.42
i5
10.00 0/00
34.70 + 028
10.00 - 0.00
3167 0,19
18.85 + 1.54
RIA
REA+GAIN
DoC
DRC+GAIN
RBEM
RUIM-GAIN
22.37 1.00
5K.06 1. 1.29
6227
0.0
6314
0.20
55.90 1 0.10
59.72 0.16
16.16
0.14
40.37 + 0.26
$7.08
1.37
68.1
1.64
34.01 + 1,36
35.78 1.5I.
Results on different number of clients. We further analyze the efficacy of GAIN under differ-
ent number of clients. Detailed setups can be found in Appendix And the experimental results are shown in Table 7 in Appendix F All results demonstrate that AGRs that combine with our GAIN consistently outperform all their original versions, which validates that integrating with our GAIN can effectively defend against Byzantine across different number of clients.
8 CONCLUSTON
In this work, we identify two root causes of performance degradation of robust AGRs in the non-IID setting. The first cause is the integrity failure of conservative AGRs. Conservative AGRs aggregate only few honest gradients, which is unreliable due to the gradient heterogeneity in the non-IID setting. The second cause is the identification failure of radical AGRs. Radical AGRs inevitably introduce Byzantine gradients into aggregation due to the curse of dimensionality aggravated by the -DDnes. Both failures result in a sharp deviation of the aggregated gradient. Motivated by the above discoveries, we propose novel GrAdient decomposItioN (GAIN) method that can be combined with most existing defenses and overcome both failures. We also provide convergence analysis for integrating existing robust AGRs into GAIN, Empirical studies on three real-world datasets justify the efficacy of our proposed GAIN.

---

Under review conference paper ICLR 2023
ETHICS STATEMENT
In this paper, our studies are not related to human subjects, practices to dataset releases, discrimina- tion/biasffairess concerns, and also do not have legal compliance or research integrity issues. Our work proposed achieve Byzantine robustness when applying federated learning to real-world applications. In this case, if federated learning is applied for good, we believe our proposed method will not cause any ethical problems pose any negative socictal impacts.
REPRODUCIBILITY STATEMENT
The implementation code provided in Supplementary Materials. All datasets and the code plat- form (Py (orch))) we use are public. Detail experiment setups are provided in the Appendices and D
REFERENCES
Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Robust training in high dimensions via block coordinate geometric median descent. In International Conference on Artificial Intelligence and Statistics, pp. 11145 1115--1118...1111111111111111111 PMLR, 2022.
Zeyuan Allen-Zhu, Faeze Ebrahimiangharani, Jerry Li, and Dan Alistarh. Byzantine-resilien non- convex stochastic gradient descent. In International Conference on Learning Representations, 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Peva Blanchard, El Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Sehastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint 1rXiv:1812.01097, 2018.
Deepesh Data and Suhas Diggavi. Syzantine-resilice high- dineh-immnsionnl sgd with local iterations on heterogeneous data. In International Conference Machine Learning, pp. 2478-2488. PMLR, 2021.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference Machine Learning, pp. 999-1008. PMI.R, 2017.
Mahdi El-Mhamdi, Sadegh Parhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyēn Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralived, byzantine, hetero- geneous, asynchronous and nonconvex learning). Advances in Neural Information Processing Systems, 34:25044 25007, 2021.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 6246-626 6666.623. PMLR, 17-23 Jul 2022.
Avishek Ghosh, Justin Hong. Dong Yin, and Kannan Ramchandran. Robust federated learning in heterogeneous environment. arXiv preprint 1906.0906699999 2019.
10

---

Under review conference paper ICLR 2023
Rachid Guerraoui, Sébastien Rouault, et The hidden vulnerability of distributed learning byzantium. In International Conference on Machine Learning, pp. 3521-3530. PMLR, 2018.
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning image recog- nition. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp.
770-778, 2016.
Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and; 0.5 mb model size. arXiv preprint arXiv: 073660, 2016.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, 7achary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning, Foundations and Trends in Machine Learning, 14(1 (M(12)):122 2):1-210,, 2021.
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 on Machine Learning, pp. 5132-5143. PMLR, 2020.
Sai Praneeth Karimireddy. Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pp. 5311-5319, PMLR, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. International Conference on Learning Representations, 2022. URL
https:://ppeneev
net. Forum? ? di JXKKDE15VJE
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Communicatioon of the ACM, 60(6):84990, 2017.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning on non-iid data silos: An experimental study, arXiv preprint 1rXiv:2102.0200 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- lems,
2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcceent learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 12822 PMLR, 2017.
Jungwuk Park, Dong-Jum Han, Minseok Choi, and Jackyum Moon. Sageflow: Robust federated learning against both stragglers and adversaries. Advances in Neural Information Processing Systems, 34:840-851, 2021.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint arXiv: 13445, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3)211-2555 2015.
Virat Shejwalkar and Amir Houmansadr. Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning. In NDSS, 2021.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, al. field guide feder- ated optimization. arXiv preprint arXiv:2107.069/ 2021.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine- tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270, PMLR, 2020.

---

Under review conference paper ICLR 2023
Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. Advances in neural information processing systems, 30, 2017.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartleu. Byzantine-robust distributed
learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659, PMLR. 2018.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Interna- tional Conference on Machine Learning, pp. 7252-7261, 2019.
12

---

Under review conference paper ICLR 2023
A SETUPS FOR EXPERIMENTS IN SEC.
The experiments are conducted on CIFAR-I0 Krizhevsky et al. 2009
For both IID and non-IID settings, the number of client is set to n = 50. For IID data distribution, all 50,000 samples are randomly partitioned into 50 clients each containing 1,000 samples. For non- ITD data distribution, the samples are partitioned in Dirichlet manner with concentration parameter
| = 0.5. Please refer to Sec. 7.1 for the details of Dirichlet partition.
The number of Byzantine clients is set to f = 10. LIE (Baruch et al. 2019 attack with 1.5 considered.
We use AlexNet KKrihhvskyy al. 2017) the model architecture. The number of communication rounds is set to 500. In each communication round, all client participate in the training.
For local training, the number of local epochs is set to I, batch size is set to 64, the optimizer is set to SGD. For SGD optimizer, learning rate is set to 0, momentum is set to 0.5, weight decay coeffecient set 0.0001. We also adopt gradient clipping with clipping norm 2.
Two defenses are considered: a radical AGR Multi-Krum (Blanchard et al. 2017) and a conservative AGR Bulyan (Guerraoui et al. 2018).
PROOF FOR PROPOSITION
Here we restate the assumptions and the proposition for the integrity of this section.
Assumption (Unbiased Estimator). The stochastic gradients sampled from any local duta distri- bution are unbiased estimators of local gradients over Bd for all clients, i.e.,
[V [ = VL,(w), Vw E Bd 7E E [n),tE
(13)
Assumption 2 (Bounded Variance), The variance of stochastic gradients sampled from any locul data distribution uniformly bounded over Rd for all clients, i.e., there exists 2 0 such that
V[[ E (..(w))l S o², Ve E ER [n).tENN.
(14)
Assumption (Gradient Dissimilarity). The difference between the local gradients and the global gradient is uniformly bounded over Rd for all clients, i.e., there exists K 2 0 such that
[V) V [[ S x2, Vi E R [n].
(15)
Assumption (Lipschitz Smoothness). The loss function is L-Lipschitz smooth with respect over Rdd i.e.
[V - VL(w"))l S 1|w - w'll, Vwe, w/ E IRd.
(16)
Definition 1 (c-resilient AGR). Let A be an AGR. If for any imput (#1...., and such that there exists set 7 E [n)] of size at least [7[| > n1/2 that satisfies:
Elix, x 1|2 < p²,
(17)
the output of A satisfies:
E| x.) z0|2 S cp², where x
Σ Bhe NEH
(18)
|7
then the AGR A is called c-resilient. Proposition 1. Suppose Assumptions I [oo [oold, and let 1/2L. Given c-resilient robust AGR A, we start from w" and run GAIN for communication rounds, it satisfies
3
f(w0)
(19)
16L
where
f2
e² = 0
(N² +
)1 + 2 )(1 )))
(20)
(n
f)2
13

---

Under review conference paper ICLR 2023
B.1 KEY LEMMA AND PROOF
Before starting the proof of the main proposition, we first state and prove the following lemma. Lemma 1 (Estimation error). Suppose Assumptions Ito 3hold. Given a c-resilient robust AGR A. for any & > O, with probability at least - &, where is the number of sub-vectors in GAIN, the aggregated gradient of GAIN is unbiased estimator of the optimal gradient ([(w) with bounded variance.
Eg = 9. Var[g] S
(21)
--- S
when gi ø11 = (1 1/vn-
+o -o VN/DE(11 vC+
We state and prove the following lemma for the proof of Lemma] Lemma 2. For any random vector X, we have
1
Varll
(22)
Proof.
From the definition of variance, we have
Var
||]
B[| B|
(23)
[5(1) X
|||_X|] )
(|IEX|
E||x1
(24)
[ X ||EX|]]
(25)
E X |
(26)
The second inequality comes from triangular inequality.
liquipped with Lemma 2 we start the formal proof for Lemma !
Proof. For all honest clients i,j E H. parameter group E [p]. we have
18 |g (4) (4) 112
(27)
Eg (0) g!0)) (g. ( + (g)))
0 (0) -g
(28)
< 4 (0) g. (9) + |1g g 1 + |lg g. 112 + |[g] 9
(4)
(4)
(9)
(29)
< 88 + 8x2.
(30)
Here the first inequality comes from the Cauchy inequality, and second inequality follows As- sumptions and Then according to the Definition] 1 we have
Elgg( g 1| So(a" + +*)
(31)
Then for honest client h, the expectation of abnormal score (4) from group g can be bounded as follows.
E
(0)
( (4) g(
(32)
Ell (.) g( || Ig (() (g) g
(33)
Ellgi (9) (9) || +E
(g) g( (llg
(34)
V Elggh
(g)
9
0 12
g00) ( 1
(35)
< 2220 +
(36)
Here the first inequality is result of triangular inequality, the second inequality comes from Cauchy inequality, and the third inequality is combined result of Equation 31) and Assumptions 2
and
14

---

Under review conference paper ICLR 2023
The variance of (9)
A can also bounded as follows.
Var[s [9)] = [B((s, ) - ()
(37)
I )²
(38)
Ellg (4) g(*) |
(39)
S 4E|| gh gh (0) 1 + +1
(2)
-2 +1 - 12 |1 13
+
(40)
Here the second inequality is a result of Cauchy inequality.
We bound glgg( (0)
g 1|2 follows.
E ()) g 1012
EE|
G 9 )1
(g)
(41)
VER
El 9. 9 12
(4)
(42)
(n - f)²
S (n 5
(43)
EHH
(44)
71 f
Here the second equality comes from the independence of minibatches sampling across different clients, and the first incquality is a result of Assumption 2 Applying Assumptions
and 3 and Equations
31 and
to Equation (40) we have
o²
Varls 1 4( x²
+ 8c(az + x²))
(45)
f
(4 32c
Jo (4 + 32c)
(46)
According to Equations (36) and score 8/ of an honest client h.
46
we can bound the expectation and variance of total abnormal
E(sa] = E
S p(a + = 02 + x²) = A,
(47)
9=1
Var[sa]
Varls (0) S p((4 32c + n )0² + (4+ 32r)mx ==
(48)
Here the addictive property of variance is result of the independence of group abnormal scores
(x(a) (4) g E [p]}. which comes from the independence of components in gradient Yang & Schoen-
holz 2017].
From Chebyshev's inequality, for any A₁ > and honest client & E [m] \ B, we have
Var[sM]
P(sa
E 1/ A 2
(49)
A
Consider the expectation of abnormal score (9) from group for Byzantine client E B
E[s [
(l]lg)" ((
(50)
E|| (g)")) g( (g(0) (4) g(o)
(51)
2 Elllg! (4)
g - (g( gd ||]
(52)
Ellgg! g(() | ( اامه (0)( -
(53)
El b (4) (0) Blg | + v (1g (4) (1))
(54)
2 2/ 0² x²
(55)
15

---

Under review conference paper ICLR 2023
where 6, = Ellg2 ()) -g(4) the expected deviation of Byzantine client from the average of honest gradients. Here the first and second inequalities come from triangular inequality, the third inequal- ity is based on Cauchy inequality, and the 4-th inequality is combined result of Equations (31
and 44
The variance of abnormal score
% (n)
can be bounded follows.
Varls = Varl1 (9) g [I]
(56)
1 g( B (9) 1002
(57)
(0) (0) Eg (0) (g 4) - Kg )1
(58)
2E[ (0) Eg, 0 1 + (g Eg
(59)
2 (4) Egg (1) 1 + 2E g(9) - 11
(60)
The first inequality results from Lemma 2 and the second inequality comes from Cauchy inequality.
bound || (e) (g(()) as follows.
E g (v)
Eg 1 = (g g (0) + (g)0) - Eg - Elg 1|
(61)
S 3Elllg
g 1 + (g |1 + |B|g g 1
(62)
s 6E g()) 0 ( - 1/
(63)
30²
s 48(02 + x²) + n -
(64)
3
(48 + n
00² + 48k²
(65)
Apply Equation (65 to Equation 60
we have
Varls [0) s 20 + (96
6 )0² + 96x²
(66)
where of
13 (0)
Egg 112 the variance.
Similar to Equations (77 and (48), we utilize Equations (55) and (66) to bound the expectation and variance of total abnormal score of byzantine client b.
E [(6]]
E
(v) 2 p(o, 2V22V
+22
vn = C,
σ
(67)
g=1
Var[ss]
Varls (9) - p(2coss + (96 +
6 )0² + 96x²) ) D
(68)
where & Ellgg, const.
9ll According SShewaalaa & Houmansadr (022)) of is bounded, i.e., of
Similarly, we apply Chebyshev's inequality to the abnormal score of a Byzantine client b E B.
Var[su] A
Pr(ss 2 E(ss) Av)
b B.
(69)
16

---

Under review as conference paper ICLR 2023
Combine Equations (47) to (49) and take 4A = 41 (1+
vD/B), we have
Pr(sA < VDA+ + vBC
Pr(ss < <A + AA)
(70)
vB + VD
2 Pr(sh < <B/sn] + An)
(71)
[ar[sk]
2
(72)
A
2 B
(73)
A
(VB + VD)²
=
(74)
(C - A)2
Combine Equations (67 to (69
and take A, = (C- A)/(1 + /B/D), we have
VDA+ + v BC
Pr(ss 2
2 PT(.) > Cn)nn)
(75)
VB + VD
Pr(st > B[su] A)
(76)
2 1 Var[sp]
(77)
A
1 D
(78)
AT
(VB + VDJ²
1
(79)
(C A]2
Then consider the probability all the Byzantines are filtered
./DA+ /BC ,th H, /B+VD
VDA+ + VBC
Pr(fit..... 1n = 71) z Pr(sa- <
vbb B)
/B+ VD
(80)
= II PI(SA < VDA+ + VBC
VDA+ VBC
II Pr(s, 2
(81)
VB+ + VD
VB+ VD
NEW
iEB
(VB + VDY2
(VB+VDD)
+
II
II
(82)
(C A)2
(C- A)2
NER
BEB
(VB+VDD:
2
)m
(83)
(C-A)²
(VB WB+vDD
21-n (C (C-A) AA2
(84)
Solve 1 n (VB+ (VB+VDD VD/ A)2 2 1 e//, we have
E BBgg 911 2 (1+
Vn )o + 4v2cN
02 + +x2
(85)
4 )0² + (4 + 32c)
+ Pe
((4 32c +
(86)
n- f
6
+ (2const + +(96+ +
)0 + 96x2))
(87)
that is,
(1 + ao. (1++ c1 1
1
Elig. Ø11 = Q[s (1 + c+
(1
ve+
V pe
- pe
vn
(88)
17

---

Under review conference paper ICLR 2023
B.2 PROOF FOR THE MAIN PROPOSITION
Proof. According to the Lipschitz property of loss function L, we have
[(w") [(w N (VL(w"), wt w w L
I''
w 1+1
(89)
2
Since w' wtt = vL(w')) (g' - vL(w")) )) can write Equation L
89 as follows
L(w") L(w (1 2 (1 [
L カシ (VL(w")) vL(W'))
+ (1
(90)
L
" g' vL(w2)11
Take the expectation on both sides of Equation
90
we have
L
EL(ww) L(ve*t1) 2 (1
z" V
L " ) (VC(w"), -' vL((w))
+ (1
(91)
2 = - vL(w")1
We further bound terms E (VL(ww)) VL(w")) and Ellğ² VL(w")11
First, we bound term EE lل vL(w")II"
For notation simplicity, we define 7i' = HnI and B BUI Then g' can be written as follows:
f
8' n
Σ IEI
gi
gi.
gi)
Ih + n Is
(92)
NEW
BEB
Here h = HH4) = 18) U2 = EnER gh/h, and g/x- Eves g./b.
Term E نl VL(w (1² 2
then bounded follows
f
B v [[((w\)| E3
IH
0/ VL(w'))12
(93)
n
h
f
E
(
vL(w'))
+
( vL(w")))
(94)
f
n2
212
2
El
g¹112
Elg g'11
(95)
f)z
(n f)z
We further bound E g¹112 and Elig's 1.
First, we bound || 1>ee gh vL(w')) ||| as follows.
Blgh V[(w')11 (((w)))>=El[ie))
1
Σ VL,(w")) + +(; Σ VL,(w")-
1
(96)
i.
hER
NER
Σ NeW
VL.(w))) (2 11+++11 21
1
Σ
VLi(w')
-
(97)
h
h
he#
S 0² /h x2
(98)
Then we bound E El g'll g' According to Lemma Byzantine gradients away from the optimal gradient will be directly filtered. Therefore, with probability 1 -
1 (1 +
l - VL(W")] & O((s +0)(1 +c+
}), b
(99)
vn
pe
(100)
18

---

Under review conference paper ICLR 2023
Then, we have
Ellg's ( + (2 n n-f )1 +1++
1) 1)= ci
(101)
The elimination of is due to the sub-Gaussian property of g3g VL(w"), which comes from the Gaussian property benign gradients.
Combine Equations (98 and 101 p.
Bllg'
VL(w"))] is finally bounded as follows
Blgg' Vl(w")11
(102)
21
2F²
(o² / + xス2)
f1= c((++1/p)
(103)
(n f)3
2(n 21}²
2ʃ
(0² 2f) +x²) (n f)z Ci
(104)
[n f)?
C2
(105)
Then, we bound inner product term B(VL(w'), -' [B(VL(w"). - vL(w")) = (KV((w")) VL(w"))
(106)
(l(V((w)) ).9' v[(w"))
(107)
B (VL(w")) (Il -1/g" - vL(w'))
(108)
B15 ((V((w")) 2 V[(w')I
(109)
[ 202
(110)
Combine Equations (91). 104
and 110
we have
L
L [[E
[(w") L(w
2n
4
20-2-1 n2
(111)
Sum Equation 90 over 1 I.....T 1 and take expectation, then we have
B(C(w") [(w=)( (7" 4
1 L 1²)
Σ 2|
L C)
(112)
2
Take " = 1/2L, and consider that the loss function is generally non-negative, e.g., cross-entropy
loss, l2 loss,
T
3
2 C2).
BC(w") 2
E [[(("))
(113)
161.
which completes the proof.
C COMPARASION AGAINST RECENT WORKS
Recent works (Karimireddy lyze the convergence of Byzantine-robbeeiee FL in the non- IID setting. We all provide an upper bound on the gradient norms for the convergence analysis. We all admit that convergence in presence of Byzantines may be impossible due to non-IID data, i.e /V may never decrease zero. And the non-IID degree plays key role in the upper bound. Technically, we improve convergence dif- ferent ways. In particular, Allen- Zhu et al. (2020) show how server momentum or history gradients help convergence. Karimireddy et al. 2022 considers the combined effect of server momentum
2022 Allen-Zhu al. 2020 EI-Mamdi 2021) also ana-
19

---

Under review conference paper ICLR 2023
and gradient bucketing. El-Mhamdi et al. (201)) considers a decentralized setting and minimizes the upper bound from the point of view of the robust AGR design. Our method considers how gradient decomposition can help convergence. In this sense, our convergence analysis is orthogonal to the above works and may be combined with them to achieve better upper bound.
D EXPERIMENT SETUP
D.1 SETUP FOR MAIN EXPERIMENTS IN SECTION 7
Data distribution. CIFAR-IO, CIFAR- 100 Krizhevsky al. 2009) and ImageNet- 12, we use Dirichlet distribution to generate non- IID data by following Yurochkin et al. (2019): Li et al. (2021). In particular, for each client we sample p (3) and allocate a p. proportion of the data of label y client i, where (ir(3) represents the Dirichlet distribution with a concentration parameter
3. We follow Li et al. 2022 ) and set the number of clients n = 50 and the concentration parameter
g 0.5 as default.
Other setups. The setups for datasets FEMNIST (Caldas et al. 2018), CIFAR-I0 Krizhevsky al. 2009), CIFR-106 100 (Krizhevsky et al. 2009) and ImageNet- 12 (Russakovsky et al. 2015) are listed below T
Table 4: Default experimental settings for FEMNIST, CIFAR-IO, CIFAR-100 and ImageNet- 12.
Datasel
FEMNIST CNN
CIFAR-10
CIFAR-100 100
ImageNet. 12
Alex
SqueezeNel
Res Nei- Nei-18 18 (He et 2016
Architecture
Caldas et
2018
Krizhevsky et 2017
landola et 2016
Communication rounds
Client sample ratio
0.005
0.1
0.1
0.1
# Local epochs
5
Optimizer
SGD
SGD
SGD
SGD
Batch
Learning rute
0.5
0.1
0.1
0.1
Momentum
0.5
0.5
0.5
0.9
Weight decay
0.0001
0.0001
0.0001
0.0001
Reduce 0.01
after 100-th
Learning decay
No
No
No
communication round
Gradient clipping Clipping norm
Yes
Yes
Yes
Yes
Three types of attacks based on the adversary's knowledge are considered:
Agnostic attack: the adversary knows neither honest gradients nor the AGR.
Partial knowledge attack: the adversary only has the knowledge honest gradients.
Omniscient attack: the adversary knows both honest gradients and the AGR.
Among the six attacks considered: BitFlip (Allen-Zhu et al. 2020). LabelFlip (Allen Zhu et al. 2020) are agnostic attacks; LIE (Baruch et al. 2019). Min-Max (Shejwalkar & Houmansadr] 202 Min-Sum (Shejwalkar & Houmansadr 2021 are partial knowledge attacks; and IPM (Xie et al.
2020 is an omniscient attack.
The hyperparameters of six attacks: BitFiip (Allen-Zhu et al. 2020). LabelFiip Allen-Zhu el al.
2020). LIE (Baruch al.) 2019), Min-Max (Shejwalkar & Houmansadr 2021) Min-Sum (She-
jwalkar Houmansadr (021), IPM (Xie et al. 2020), are listed in below Table
The hyperparameters of six defenses: Multi-Krum (Blanchard et al. (017). Bulyan (Guerraoui et al.
2018). Median (Yin et al. 2018). RFA (Pillutla et al.) 2019). DnC (Shejwalkar & Houmansadr
2021
RBTM (El-Mhamdi et al. 202 are listed in below Table
20

---

Under review conference paper ICLR 2023
Table 5: The hyperparameters of six attacks.
Attacks
Hyperparameters
BitFlip
N/A
LabelFlip
N/A
LIE
1.5
Min-Max
Minit = 10, r = x 10 10-6, ô: coordinate- wise standard deviation
Min-Sum
Vinit = 10, 10 6: coordinate-wil standard deviation
IPM
evall=
Table 6: The default hyperparameters of the AGRs.
AGRs
Hyperparameters
Multi-Krum
N/A
Bulyan
N/A
Median
N/A
RFA
T 3
DnC
4, niterrsrrsrr 1, b = 10000
RBTM
N/A
D.2 SETUP FOR EXPERIMENTS ON THE NUMBER OF SUB-VECTORS IN SECTION 7
The number of client is set to n 50. The samples are partitioned Dirichlet manner with
concentration parameter 3 = 0.5. Please refer to Sec. 7.1 for the details of Dirichlet partition.
The number Byzantine clients is set to 10. LIE (Baruch al. 2019) attack with 1.5 considered.
We use AlexNet KKizhevsky et al. 2017) as the model architecture. The number of communication rounds is set to 500. In each communication round, all client participate in the training.
For local training, the number of local epochs is set to batch size is set to SGD. For SGD optimizer, learning rate set to 0.1, momentum is set to 0.5, weight decay coeffecient is set to 0.0001. We also adopt gradient clipping with clipping norm 2.
64, the optimizer is
Two defenses are considered: radical AGR Multi-Krum (Blanchard et al. 2017) and conservative
AGR Bulyan (Guerraoui et al. 2018).
GAIN MITIGATES THE DEVIATION OF AGGREGATED GRADIENTS
Sec. 6 we claim that our GAIN method can reduce the deviation of aggregated gradient 9 from the average of honest gradients To verify this fact, we compare the deviation of the aggregated gradient different defenses and their GAIN variants in Figure 3 In particular, the distance between the aggregated gradient 9 and average of honest gradients g to measure the deviation degree. As shown in Figure 3 the gradient deviation degree of GAIN- eehnnnenancedd defenses much lower than their original versions expected, which validates that GAIN can mitigate the gradient deviation.
9 gll.
RESULTS ON DIFFERENT NUMBER OF CLIENTS.
We also conduct experiments across different number clients. Table demonstrates the results different defenses under LIE attack across n = (75, 100} clients on CIFAR-10 dataset. Note that the number of Byzantine clients is to f 0.2 correspondingly. Other setups follow the default
21

---

Under review conference paper ICLR 2023
wi GAIN
GAIN
Multi-Krun
Bulyan
Median
Grdieen Deviction
nan An
Gradiens Deviation Grddient Deviation
Gradient Deviation
4.5
2.0
0.3
0.0
300
150
200
50
1.00
150
250
50
200
150
203
Communnacatoonn Acation Rounds
Conmnuniicaton Rounds
Communicction Rounds
RFA
DnC
RBTM
Gradiem: Deviation
mn My MMlmo Mm mn
Gradient Devistion
1.0
20
202
Communication
Communication Rounds
Communication
Figure 3: The gradient deviation llğ gl of six different defenses w/ and w/o GAIN under L.E
attack on CIFAR-10. The lower the better.
setup of the main experiments in Sec. Bl and Appendix D As evidenced by Table 7 integrating current robust AGRs into our GAIN outperforms their original versions across client numbers.
Table 7: Accuracy (mean-istd) of different defenses against LIE attack under different client num- bers on CIFAR-I0.
Multi-
Bulyan
Bulyan+GAIN
Median
Median+GAIn
75
28.72 + 0.71
54.89 + 0.16
23.37 1.22
51.11 +: 0.00
44.89 t 2.98
52.22 + 1.64
100
32.49 + 1.22
56.51 = 0.01
21.93 0.55 DnC
46.49 + 1.33
33.82 = 0.21
46.12 + 0.17
RFA
RFA+GAIN
DrC+GAIN
RBTM
RETM+GAIN
75
16.89 1: 1,38
49.85 + 0.06
59.31 1.33
59.75 1: 0.42
45.06 +: 0.96
50,24 0.31
100
14.01 + 1.34
49.85 = 1.97
58.88 1.45
59.61 + 1.19
40.38 + 0.48
47.02 + 0.03
22


Reviews:
[{"review_id": "Lil-9ugZcD", "reviewer": "Reviewer_TG9e", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a comprehensive study on the Byzantine robustness of federated learning under the non-IID setting. The authors show that existing robust aggregation rules fail to defend against Byzantine attacks under the non-IID setting, and explain the root reasons by proposing two novel concepts: identification failure and integrity failure. Then, the authors propose a novel gradient decomposition scheme (GAIN) that can address both failures. Under standard assumptions, the authors derive that GAIN can mitigate the deviation of aggregated gradient, thus improving the performance. Experiments show the benefits of the proposed GAIN.", "summary_of_the_review": "While there are some weaknesses, I think this work is above the threshold given the novelty and sound results in tackling the challenge of Byzantine robustness under the non-IID setting.", "strength_and_weaknesses": "Strength\n\n1. This paper tries to tackle Byzantine attacks in FL under non-IID setting. The topic is interesting and useful since data distribution is mostly non-IID in the real world. \n2. The authors point out the root reasons from a new lens, in order to explain why the existing aggregation rules fail under the non-IID setting. Then they propose a novel gradient decomposition scheme (GAIN) to mitigate the gradient deviation and improve the performance. The method is novel and easy to follow. \n3. Empirical results are sound. Extensive experiments under three different types of attacks can well support the effectiveness of GAIN.\n\nWeaknesses\n\n1. There are various types of non-IID. Does the proposed method apply to all these types of non-IID settings? More discussion is expected.\n2. In the proof for Proposition 1: the illustration for inequality (32) is confusing, more explanation is expected; the illustration for inequality (33) is missing.\n3. What is $\\delta_b$ in equation (51)?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "J766FCwVfr", "reviewer": "Reviewer_bm6A", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors discuss Byzantine robustness in federated learning when the data is non-iid. In the non-iid setting, the gradient decomposition scheme (GAIN) is used to address the identification and integrity failures of existing defences. GAIN can be combined with a variety of robust aggregation rules to help them adapt to heterogeneous datasets. The authors theoretically demonstrate that GAIN can reduce aggregated gradient deviation, thereby improving performance. The authors provide sufficient experimental results to support GAIN's superiority.", "summary_of_the_review": "This paper begins a pilot investigation into the root causes of current robust AGR performance degradation in non-IID settings by proposing two new concepts: integrity failure and identification failure. The authors then propose a novel way to defend against Byzantines in FL. Sufficient theoretical analysis and extensive experiments can well support their proposed method's superiority. I believe that this paper will have an impact on the community.", "strength_and_weaknesses": "Strength:\n\n1) This paper begins a pilot study on the root causes of current robust AGR performance degradation in non-IID settings by proposing two new concepts: integrity failure and identification failure. To the best of my knowledge, this is a groundbreaking study.\n2) Following that, the authors propose a novel gradient decomposition scheme (GAIN) to reduce gradient deviation and improve performance. The method is novel and observationally supported.\n3) The entire paper is simple to understand. The authors thoroughly review all related work and summarise its benefits and drawbacks.\n4) The gradient decomposition technique proposed here is simple but effective, and it works well with existing methods.\n\n\nWeaknesses:\n\n1) Which of the six defences discussed in Section 7 is conservative and which is radical? GAIN appears to be more appropriate for conservative methods. This phenomenon can be explained further in more detail.\n2) According to the paper, the proposed method can reduce the deviation of the aggregated gradient. It is better to provide experiments to prove this.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9wM-18BU-8m", "reviewer": "Reviewer_Fwja", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on byzantine robustness of FL. Typically, the server uses robust aggregation rules to ensure that byzantine clients do not hinder learning. However, the performance of most aggregation rules is degraded when data is non-IID across different clients. The authors reveal the root causes of the performance degradation -- identification failure and integrity failure. Then they propose a novel gradient decomposition scheme that can address the above failures and adapt existing aggregation rules to non-IID data. Theoretical analysis and numerical experiments validate the efficacy of the proposed method.", "summary_of_the_review": "This paper provides an interesting insight on byzantine-robust FL over non-IID data. The proposed gradient decomposition method is well motivated. The authors also theoretically analyze the efficacy of the proposed method. Further experiments on larger datasets are expected. In general, this paper has publication merits, but some issues need to be addressed.", "strength_and_weaknesses": "Strength:\n\n•\tThe investigated problem, byzantine-robust FL over non-IID data, is important. The failure mechanism of existing aggregation rules over non-IID data is well investigated.\n\n•\tThe proposed method is novel and can adequately address the failures of existing aggregation rules over non-IID data.\n\n•\tThe authors theoretically justify the efficacy of the proposed gradient decomposition technique.\n\nWeaknesses:\n\n•\tSeems that Eq. (8) should belong to the identification phase?\n\n•\tPlease explain why computing identification score is put in the aggregation phase. It would be better to reorganize Sec. 5.\n\n•\tThe paper mentioned \"We consider six representative attacks covering the three attack types described in Sec. 3\". It would be clearer to explicitly define three attack types in Sec. 3. \n\n•\tIt would be better if the authors can test on 1-2 additional larger datasets, e.g., cifar100. This could make the results more convincing.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "7UFlmGidWJF", "reviewer": "Reviewer_Bimn", "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": "", "summary_of_the_paper": "In this paper, the authors try to solve the identification failure and integrity failure in federated learning for non-iid setting. In order to address\nboth failures, they propose GAIN, a gradient decomposition scheme that can help adapt existing robust algorithms to heterogeneous datasets. In theory, they show that integrating exisiting robust AGRs into GAIN can mitigate the deviation of aggregated gradient, thus improve the performance. Experiments on various real-world datasets verify the efficacy of proposed GAIN.", "summary_of_the_review": "Maybe it is not suitable for this top conference", "strength_and_weaknesses": "Weaknesses: \n1. The writing is not clear, where partition of set {1,...,d}, which may be very critical?\n\n2. The word \"decomposition\" may not fit.\n\n3. The method is very simple. They stack other's method except set partition?\n\n ", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject