Byzantine-Robust Learning on Heterogeneous Datasets via Resampling
Authors: Lie He
Sai Praneeth Karimireddy
Martin Jaggi
Venue:  (2021)
Keywords: Byzantine robustness
distributed training
heterogeneous dataset

Abstract: In Byzantine-robust distributed optimization, a central server wants to train a machine learning model over data distributed across multiple workers. However, a fraction of these workers may deviate from the prescribed algorithm and send arbitrary messages to the server. While this problem has received significant attention recently, most current defenses assume that the workers have identical data distribution. For realistic cases when the data across workers are heterogeneous (non-iid), we design new attacks that circumvent these defenses leading to significant loss of performance. We then propose a universal resampling scheme that addresses data heterogeneity at a negligible computational cost. We theoretically and experimentally validate our approach, showing that combining resampling with existing robust algorithms is effective against challenging attacks.


Under review as a conference paper at ICLR 2021
BYZANTINE-ROBUST LEARNING ON HETEROGE- NEOUS DATASETS VIA RESAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
In Byzantine robust distributed optimization, central server wants to train a machine learning model over data distributed across multiple workers. However, fraction of these workers may deviate from the prescribed algorithm and send arbitrary messages to the server. While this problem has received significant attention recently, most current defenses assume that the workers have identical data. For realistic cases when the data across workers are heterogeneous (non-iid), design new attacks which circumvent these defenses leading to significant loss of performance. We then propose a simple resampling scheme that adapts existing robust algorithms to heterogeneous datasets a negligible computational cost. We theoretically and experimentally validate our approach, showing that combining resampling with existing robust algorithms effective against challenging attacks.
INTRODUCTION
Distributed or federated machine learning, where the data is distributed across multiple workers, has become an increasingly important learning paradigm both due to growing sizes datasets, as well privacy and security concerns. In such setting, the workers collaborate to train single model without transmitting their data directly over the networks (McMahan et al.] 2016 Bonawitz) al. 2019 Kairouz et al. 2019). Due to the presence of either actively malicious agents in the network, or simply due to system and network failures, some workers may disobey the protocols and send arbitrary messages; such workers are also known Byzantine workers (Lamport et al. (001)). Byzantine robust optimization algorithms combine the gradients received by all workers using robust aggregation rules, ensure that the training is not impacted by the malicious workers.
While this problem has received significant recent attention, (Alistarh et al. 2018 Blanchard et al. 2017 Yin al. 2018a), most of the current approaches assume that the data present on each different worker has identical distribution. In this work, we show that existing Byzantine-robust methods catastrophically fail the realistic setting when the data is distributed heterogeneously across the workers. We then propose simple resampling scheme which can be readily combined with existing aggregation rules to allow robust training on heterogeneous data.
Contribution. Concretely, our contributions in this work are
We show that when the data across workers is heterogeneous, existing robust rules might not converge, even without any Byzantine adversaries.
We propose two new attacks, normalized gradient and mimic, which take advantage of data heterogeneity and circumvent median and sign-based defenses (Blanchard et al, 2017] Pillutla et al., 2019 Li et al.) 2019).
We propose simple new resampling step which can be used before any existing robust aggregation rule. We instantiate our scheme with KRUM and theoretically prove that the resampling generalizes it to the setting of heterogeneous data.
Our experiments evaluate the proposed resampling scheme against known and new attacks and show that it drastically improves the performance of 3 existing schemes realistic heterogencously distributed datasets.
Setup and notations. We study the general distributed optimization problem
L. min Rd (L(x)) 1 -.' ((()))

---

Under review as a conference paper at ICLR 2021
where L; Rd - R are the individual loss functions distributed among n workers, each having its own (heterogeneous) data distribution (D:) The case of empirical risk minimization with m, datapoints &: ~ Di on worker i is obtained when using L.(x) == -.. شド= Li 4. The (stochastic) gradient computed by a good node i with sample j is given as g.( == VL,(x, { with mean μ4; and variance of- We also assume that the heterogeneity (variance across good workers) is bounded i.e.
V((=)]| S 0², Vx
We write gi instead of gi (xx") aggregation rule is given as
when there is no ambiguity. A distributed training step using an
x x' - - Agggge (xg, : [m]))
(2)
If the aggregation rule is the arithmetic mean, then recovers standard minibatch SGD.
Byzantine attack model. In each iteration, there is set Byz of at most f Byzantine workers. The remaining workers are good, thus follow the described protocol. A Byzantine worker j eByz can deviate from protocol and send arbitrary vecter to the server. Besides, we also allow that Byzantine workers can collude with each other and know every state of the system. Unlike martingale- based approaches like (Alistarh al., 2018)) allow the set Byz to change over time (Blanchard et al.) 2017
Chen et al. 2017] Mhamdi et al. 2018).
RELATED WORK
There has been significant recent work of the case when the workers have identical data distributions
(Blanchard et al. 2017 Chen et al., 2017:
Mhamdi et a 20118 Alistarh et al. 2018 Mhamdi et al.,
2018|[Yin et al. 2018a b Su & Xu 2018: Damaskinos et al. 2019). We discuss the most pertinent
of these methods next. Blanchard et al. (0017) formalize the Byzantine robust setup and propose a distance-based approach KRUM which selects a worker whose gradient is very close to at least half the other workers. A different approach involves using the median and its variants (Blanchard
ct al. 2017 7 Pillutla et al.] 2019: Yin et al. 2018a). Yin et al. (2018a) propose to use and analyze the coordinate-wise median method (CM). Pillutla et al. (2019) use smoothed version of Weiszfeld's algorithm to iteratively compute an approximate geometric median of the input gradients. In a third approach, (Bernstein et al. 2018) propose use the signs of the gradients and then aggregate them by majority vote. however, (Karimireddy et al. 2019) show that it may not always converge. Finally, Alistarh et al.) (2018) use a martingale- based aggregation rule which gives a sample complexity optimal algorithm for iid data. The distance-based approach of KRUM was later extended in Mhamdi jet al. (018)) who propose BULYAN to overcome the dimensional leeway attack. This is the so called strong Byzantine resilience and is orthogonal to the question of non-iid-ness we study here. Recently, (Peng & Ling] 2020 Yang & Bajwa 2019a by studied Byzantine-resiliet algorithms in the decentralized setting where there is no central server available. Extending our techniques to the decentralized setting is an important direction for future work.
In different line of work, (Lai et al. 2016 Diakonikolas al., (019) develop sophisticated spectral techniques to robust estimate the mean of high dimensional multi-variate standard Gaussian distribution where samples are evenly distributed in all directions and the attackers concentrated in one direction. Very recent work (Data & Diggavi 2020) extend the theoretical analysis to non-convex, strongly-conve convex and non-i.i.d setup under a gradient dissimilarity assumption and propose gradient compression scheme on top of it. Our resampling trick can be combined with it to further reduce gradient dissimilarity.
Many attacks have been devised for distributed training. For the iid setting, the state-of-the-art attacks are (Baruch et al., 2019 Xie et al.) (019b)). The latter attack is very strong when the fraction of adversaries is large (nearly half), but in this work we focus on settings when this fraction is quite small (e-g. S 0.2). Further our normalized mean attack Section 3.2 is inspired by (Xie al., 2019b). The former work focuses on attacks which are coordinated across time steps. Developing strong practical defenses even in the iid case against such time-coordinated attacks remains an open problem. In this work, we sidestep this issue by restricting ourselves to new attacks made possible by non-iid data and studying how to overcome them. We focus on schemes which work in the iid setting, but fail with non-iid data. Once new method which can defend against (Baruch et al.) 2019) is developed, our proposed scheme shows how to adapt such a method to the important non-iid case. For the non-iid setting, backdoor attacks are designed to take advantage of heavy-tailed data and manipulate
2

---

Under review as a conference paper at ICLR 2021
model inference on specific subtask, rather than lower the overall accuracies of training (Bagdasaryan ct al. 2018: Bhagoji et al., (0118). In contrast, this paper is not intended to address aforementioned challenges but rather to defend the attacks that lower the training accuracies in the non-iid setting.
As far as we are aware, only (ii ct al. 2019 Ghosh et al. 2019 Sattler et al. 2020 explicitly investigate Byzantine robustness with non-iid workers. Li al. (2019) proposes SGD variant
(RSA) which modifies the original objective by adding an & penalty. Ghosh et al. (2019): Sattler et al.
(2020) assume that all workers belong to an apriori fixed number of clusters and use an outlier-robust clustering method to recover these clusters. If we assume that the server has the entire training dataset and can control the distribution of samples to good workers, Xie al. (2019a); Chen et al. (2018);
Rajput et al. (2019) show that non-iid-ness can be overcome. Typical examples of this is distributed training of neural networks on public cloud, or volunteer computing Meeds et al. (2015); Miura & Harada (2015). However, none of these methods are applicable in the standard federated learning setup we consider here. We aim to minimize the original loss function over workers while respecting the non-iid data locality, i.e. the partition of the given heterogeneous dataset over the workers, without data transfer.
3 ATTACKS AGAINST EXISTING AGGREGATION SCHEMES
In this section show that when the data across the workers is heterogeneous (non-iid), then can design new attacks which take advantage of the heterogeneity, leading to the failure of existing aggregation schemes. We study three classes of robust aggregation schemes: i) schemes which select a representative worker in each round (e.g. KRUM (Blanchard et al. (017)), ) ii) schemes which use normalized means (e.g. RSA (Li et al. 2019), and iii) those which use the median (e.g. REA (Pillutla et al. 2019)). We show realistic settings under which each of these classes would fail when faced with heterogeneous data.
3.1 FAILURE OF REPRESENTATIVE WORKER SCHEMES ON NON-IID DATA
Algorithms like KRUM select workers who representative of majority of the workers, by relying on statistics such as pairwise differences between the various worker updates. Let (gi...., .n) be the gradients by the workers, ff of which are Byzantine (e.g. n 2 2 + for KRUM). For * j. let i + j denote that gj belongs to the n f - 2 closest vectors to 9:- Then KRUM is defined as follows
KRUM(91 ... ...) == arg min, Σ,-, |6:
1
However, when the data across the workers is heterogeneous, there is no 'representative' worker. This is because each worker computes their local gradient over vastly different local data. Hence, for convergence it is important to not only select a good Byzantinn)) worker, but also ensure that each of the good workers is selected with roughly equal frequency. Hence KRUM suffers a significant loss in performance with heterogeneous data, even when there are no Byzantine workers.
For example, when KRUM is used for iid datasets without adversary (f 0,, see left of Figure Ta]. the test accuracy is close to simple average and the gap can be filled by MULTI-KRUM (Blanchard et al. 2017). The right plot of Figure la also shows that KRUM'S 's selection of gradients is biased towards certain nodes. When KRUM is applied non-iid datasets (the middle of Figure Iap. KRUM performs poorly even without any attack. This is because KRUM mostly selects gradients from few nodes whose distribution is closer to others (the right of Figure Tap. This is an example of how robust aggregation rules may fail realistic non-iid datasets.
3.2 ATTACKS ON NORMALIZED AGGREGATION SCHEMES
Instead of simply averaging the gradients, some methods first normalize them and then average. This limits the influence of the Byzantine workers since they cannot output extremely large gradients, and hence is more robust. For example RFA (Pillutla et al. 2019) with 7=1 uses following aggregation rule:
NM ...) E galla
(4)
Other methods such as RSA (L et al. 2019) or signum (Bernstein et al. 2018) normalize entries coordinate-wise before taking majority vote i.e. update the server model To on server using local model x; from node i (not gradient) using
RSA (SSA( #1.... F..) Vio(m)) > sign(x0 m.))
(5)
3

---

Under review as a conference paper at ICLR 2021
iid
non-iid
Selections
iid
non-iid
Accuracy
Test Accuracy (%
100
Test Accuracy (%)
600
75
iid non -id
50
25
Avg
200
25
Krum
%
012345 Nodes
0
8
2 #Byzantine (f)
Iteration
lteration
Iteations
Reeations
(a) Left & middle: Comparing arithmetic with (b) Comparing normalized mean (RFA with T=1) under
KRUM on non-iid datasets, without any Byzan- the normalized mean attack with f 1, attack- tine workers. Right: Histogram of selected gradients.
ers.
f=0 iid
f=2 iid
f=2 non-iid
Test Accuracy (%)
90
CM
80
70
60
50
4
2
4
0
2
Iterations
Iterations
Iterations
(c) Comparing coordinate-wise median (CM) and ge- ometric median (RFA with T=8) under the mimic2 attack on iid and non-iid datasets.
Figure 1: Failures of existing aggregation rules on the non-iid MNIST dataset. experiments, there are 8 good and Byzantine workers.
where is strongly convex penalty term and À 0 is relaxation parameter.
However, a Byzantine worker can still craft an "omniscient" attack to foil robust aggregations, using approach similar the negative sum for the arithmetic mean (Blanchard al. 2017 Li al. :
Eiegood ||
On the right side of Figure 16
we can see that this attack lowers the accuracy of RFA-TI significantly, as the number of Byzantine workers increases. Comparing to its iid counterpart, the normalized mean attack is even more impactful in the non-iid setting.
3.3 ATTACKS ON MEDIAN- BASED SCHEMES
Geometric median and its variants are popular in robust learning research (Blanchard et al., 2017]
Chen al. 2017: Pillutla et al. 2019 Yin et al. 2018a Mhamdi et al. 2018). Given gradients ( ........ jo , we use the estimator
GM 9..) argnin, Σ g:ll
If the vectors [g), (91,-..,58 .n.) are drawn independently from the same distribution, intuitively most of them would concentrate around their mean. Then, even if there are some Byzantine outputs, the median would ignore those outliers and output 'central' point close the mean.
However, when [g..... }n are gradients over heterogeneous data, they may be vastly different from each other and do concentrate around the mean. In such scenario, the median such as (7) can be even less robust than simply taking the mean. Suppose that worker 0 is Byzantine and the remaining workers (I..... 2n} are good, with a total of 2n + workers. Now suppose that gi (-1)* for all the workers, with half the good workers having -1 and the other half +1. This means that the true mean 0, however, the median estimator will output 1.
Mimic attack. This motivates our mimic attack in which all Byzantine workers collude and agree to always send gradients from the same worker. We define a specialized attack, called mimic2, where half of the good workers have same datasets and send gi while the rest good workers send g2; then all Byzantine workers send e = 91 such that the geometric median of the gradients received by the -eeemnn
server is always 91- Therefore, this attack breaks by leading them to wrong solutions. The left plot of Figure II shows the impact the mimic2 attack. Test accuracies of CM and RFA both drop drastically around 50%.
robust aggregation rules,
4

---

Under review as a conference paper at ICLR 2021
Algorithm Robust Learning with Resampling
Sctup:
workers, f of which are Byzantine; resampling T times, each time samples gradients. robust learning algorithm AGGR on iid datasets; 7 is the learning rate.
Workers:
Each good worker randomly samples a datapoint j and computes a stochastic gradient
== (ax { where E ~ Dj; each Byzantine worker sends arbitrary vector g:-
2. Send gi server.
Servers:
Receive )- from all workers.
2. S. = Resampling (q: : : [n]] f. f. See Algorithm 2
Compute x' a AGGR(SS):
4. Broadcast x' to all workers.
Algorithm 2 Resampling with s-replacement
Input: {g:
[n]].
{dli] == 0:de [n]}
for t := 1,..., T do
for i: : 1, I...., do
while Select ji ~ Uniform([n]] (n]) do
if c(ia] then ciid +
If c[.. = Break:
Compute average := -E=19 9j. Return (g: : e [2]], fof :t i [s]}
ROBUST AGGREGATION ON NON-IID DATA
In Section 3 we have demonstrated how existing robust aggregation rules can fail in realistic non-iid scenarios, with and without attackers (Sections 3.2 and 3.3 and Section 3.] respectively). To overcome this problem, we propose simple new resampling based aggregation rule for training, shown in Algorithm[] More specifically, we choose s-resampling without replacement in Algorithm wheree each gradient can be sampled at most times. The key property of our rule is that after resampling, the resulting set of averaged gradients {g: E [T]} are much more homogeneous (lower variance). Then these averaged gradients are fed to existing Byzantine robust aggregation schemes, such as KRUM, see Section Given an existing aggregation rule AGGR, we denote by AGGR Resampling the resulting new robust aggregation rule for non-iid input gradients.
In the following proposition, we list the desired properties Algorithm Proposition I. Given population {g: i E
[n]] C Rd of mean μ E and variance ²² E l|g: #ll?, let {g. :t [T]} be the output of Algorithm 2 on {g. : [n]]- Then
If there are no Byzantine workers, then {g. : n-1
[T]} are identically distributed
Llg.] = var(g.)
Vt [2]
an
If f of the n inputs are Byzantine, then at least T f gradients in {g. : E [T]] are good; that is, good 9: is the average gradients {g E [s]} Cgood [m]. Then such good {g.} are identically distributed with
Elge] j, var(g.
1- 02 sn
where Ø
Σ
Eiegood 9s. and ÿ2 good Σ Eiegood llg: Eg..112
Igond
Proof. Since Algorithm resamples s gradients to estimate population of sn samples, we can use Ch. Survey Sampling) to compute the sample mean (10)
sampling theory (Middleton) 1988
E [RS(g....... 9n) #
and the sample variance
E (RS(g...... 9..) - 1
=-))
(11)
sn
Since the gradients are sampled at most s times, at most sf out of the T gradients are affected by a Byzantine worker. Its mean and variance can be calculated in the same way shown above. n
5

---

Under review as a conference paper at ICLR 2021
Remark 1. For = 1, resampling simply becomes shuffling of the input elements, and var(gi) o² is unchanged. For > 1. the resampling scheme reduces the heterogeneity (variance) by approximately 1/s. Thus. increasing leads to the resulting resampled gradients being a better estimator of the population mean, thus improving training convergence speed. On the other hand, increasing also increases the number of resampled gradients which can be affected by a Byzantine worker. In particular, if f workers are Byzantine, then up to fs resampled gradients can be incorrect, which has be taken into account by the employed robust aggregation rule. In practice, we found that using a small value s = 2 was already sufficient to overcome heterogeneity.
Remark 2. A natural question to ask is what happens if we resample with replacement but do not limit on the number of replacements, We discuss this additional algorithm variant in Appendix C
Note that the (ğ+ E [T]} are identically distributed but not independent. This does not directly fit into the original assumptions of Byzantine robust algorithms like KRUM and hence the robustness has to be reproved for our more general setting.
5 CONVERGENCE ANALYSIS WITH KRUM
In this section, we analyze the convergence of SGD with robust aggregation on non-iid data. Since the definition of robustness and other conditions vary from paper to paper, it is not possible to give a uniform proof perfectly fit for all methods. For example, (Yin et al.] 2018a) assumes the gradients have bounded variance and skewness whereas others like KRUM, REA, BULYAN does not. Thus we only analyze KRUM for its simplicity and popularity, and show that analysis is only slightly different from the original version. For other algorithms, we show by experiments that resampling helps them achieve better performance on heterogeneous data, see Section
Definition A generalizes the Byzantine resilience of (Blanchard et al. 2017 Definition 1) to the cases where we have non-iid data. Let G be an estimator of the good gradients.
Definition A ((a, f)- Resilience.). Let S < x/2 be any angular value, and any integer O S f < n. Let B = {Ji.....J .5s 51 S i1 < ... < js S n) be the indices of Byzantine workers. Let {V: E DD : B) be independent random vectors in Rd. Let G = G(E) be an independent random variable which randomly selects a good worker and samples a vector from Dj and EG= g. Let B1, .... Bj be any Byzantine vectors in Rd, possibly dependent on the V: 's. An aggregation rule F is said to be (ox, D--yaanntnne resilient if
F F(V.....
B ..... Vn,)
h
satisfies (i) (, 2 (1 - sin a) ||g|| 0 and (ii) for r 2, FI
Then conclude the almost sure convergence similar to (Blanchard et al.
2017 Proposition 2)
Theorem II (Resampling KRUM). We assume that (i) the cost function C is three times differentiable
with continuous derivatives and non-negant non-negative L(x) 2 0; (ii) the learning rates satisfy E. 2tt = do and Ee ri <, 50. Let the good workers have stochastic gradients Gx for i E good C [m]. We assume that for uniformly chosen j E good, the following is true (iii) [,,g(G((x,E)) E)] v v(()) and Vr E {2, 3, 43, Ej.e| [[, E)Il" S A, + Br|( for some constants Ap, B,; (iv) there exists a constant 0 < a < / such that for all x we have Tj(T, 8f) vd axx) < [[V[())] sin a where o² (x) := 2-1 0² (z); (v) finally, beyond certain horizon, ||0|| > D, there exist E > 0 and
S B < n/ 7/2- a such that [[V](()]] 2 E > and (xx VL(x)) 2 cos |||=|| (VV[() If
and f + 3 < n, then
KRUM oResampling is (ar, 8f -yy-mninn resilient where 0 S a < 7/2 is defined by
-(I.=))-Vd- nn,, f) == /2(n - f -10-1-))- [[(()]]
sin
(12)
a-25-2
the sequence of gradients v v((:)) converges almost surely to zero.
We defer the proof to Appendix A The above convergence result for heterogeneous data is nearly identical to (Blanchard et al. 2017 Proposition 2) for iid data, except for the slightly stronger
restriction on the number of Byzantine workers 2x + 3 &

---

Under review as a conference paper at ICLR 2021
iid
non-iid
Selections
iid
non-iid
Accuracy
Test Accuracy (%)
100
Test Accuracy (%)
600
75
50
non- id+RS
Avg
Xvv Knum
non-
25
Krum
200
25
222
1l8 non
0
6 lteration
6
01234567 Nodes
0
8
Iteration
Iteraioons
Reeations
#Byzantine (1)
(a) Left & middle:
Comparing arithmetic KRUM on and non-iid datasets, without any Byzan- the normalized mean attack with f 1, attack- tine workers. Right:
with
(b) Comparing normalized mean (RFA with T=1) under
Histogram of selected gradients.
ers.
Test Accuracy (%)
f=0 iid
f=2 iid
f=2 non-iid
90
80
CM REA-TO REA-TO-RS
70
CM
CM RFA-TB RFA-TB-RS
60
REA-TB
50
RB+
4
4 Iterations
4 Iterations
lterations
(c) Comparing coordinate wise median (CM) and geo- metric median (RFA with T=8) under mimic2 attack on iid and non-iid datasets.
Figure 2: Combining resampling with existing aggregation rules on non-iid MNIST dataset. In all experiments, there are 8 good and f Byzantine workers. For each aggregation we resample and average s gradients for T n times.
EXPERIMENTS
In this section, we demonstrate the effect of resampling on datasets distributed in a non-iid fashion. Throughout the section, we illustrate the challenge, attacks, and defense by example of training an MLP on the MNIST dataset (LeCun et al.) 1998). In Appendix D. we present the results of similar experiments on - (Xiao et a 2017) and CIFAR-10 (Krizhevsky et al., 2009). The dataset is sorted by labels and sequentially divided into equal parts among good workers; Byzantine workers have access to the dataset on all good workers. Implementations are based on PyTorch (Paszke et al., 2019) and will be made publicly available.
6.1 RESAMPLING AGAINST THE ATTACKS ON NON-IID DATA
In Section we have presented how heterogeneous data can lead failure of existing robust aggregation rules. Here we apply our proposed resampling with T'=n, s=2 to the same aggregation rules, showing that resampling overcomes the described failures. Results are presented in Figure 2 In Figure 2a we show that using resampling helps KRUM to achieve better test accuracy on non- iid data. Since resampling KRUM with s=2 actually averages 2 gradients, we compare with MULTIKRUM with m=22 The middle of Figure 2a shows that MULTIKRUM with m=2 performs better than KRUM, but KRUM with resampling is even better which suggests the resampling step improves the performance
non-iid data. The selection histogram the rightmost part of Figure 2a shows that after resampling, KRUM'S selection much more evenly distributed between the good workers. In Figure 2b we show that resampling fixes RFA with T=1 and allows it defend against the normalized mean attack. The resampling-bases aggregation can almost reach same accuracy for both iid and non-iid setup. In Figure 2c while mimic attack does not work for median-based rules in the iid setting, resampling still slightly improves the performance due to variance reduction. In the non-iid setting, resampling drastically improves the accuracy to the same level the iid setting.
6.2 RESAMPLING AGAINST GENERAL BYZANTINE ATTACKS
In Figure| we present thorough experiments on non-iid data over 10 workers with 2 Byzantine workers. In each subfigure, compare aggregation rule with its variant with resampling. Three aggregation rules are compared: KRUM, CM, REA. In particular, we compare to REA with both T=1 (normalized mean) and T=8 (geometric median).
7

---

Under review as a conference paper at ICLR 2021
BF Aggr
Altact Aggr
Altack Aggr RFATT
Allack AAgr RPA-T8
Accuroyy 198
60
40
20
Aggr
Aggr
Aggr
80
Accurcc (58)
40
Allack G KRUM
Allakk Aggr
Altack Aggr RFA-T1
Allack Aggr RFA-T8
80
Accurscy 158)
60
40
False
Thue
Allack MMC Augr - KIIU
Allack MMC Agg
Allack NMC Aggr IIFA-11
Allack MMC
Aggi IFA-TB
Accuriyy (58)
60
20
MMC2 Aggr KRUM
Aggr
Agge
Aggr
80
Accurccy (56)
60
40
20
430
100
200
4:00
Itorations
Figure 3: Test accuracies of KRUM, CM, REA under 5 kinds of attacks (and without attack) non-iid datasets. There are workers and of them are Byzantine according to each attack row. Columns show each aggregation rule applied without (red) and with resampling (blue). Dashed lines for comparison are showing the same method without any Byzantine workers =0= For RFA, T1, T8 refers to the number of inner iterations of Weiszfeld's algorithm.
Attacks. different kinds of attacks are applied (one per row in the figure): bitflipping, labelflipping. gaussian attack, as well as the mimic and mimic2 attacks.
Bittlipping: A Byzantine worker flips the sign bits and sends - f((x) instead of V f because of problems like hardware failures etc.
Labelftipping: The dataset on workers have corrupted labels. For the MNIST dataset, we let Byzantine workers transform labels by T(y) : y-
Gaussian: A Byzantine worker sends a Gaussian random vector of 0 mean and isotropic covariance matrix with standard deviation 200 (Xie et al. 2018).
mimic & mimic2: Explained in Section 3.3
we can see that resampling improves the accuracy on most of the tasks. The final accuracies achieved vary with the aggregation rules we use. Notice that RFA-TI is more robust to the mimic attack than RFA-T8 in Figure because more inner iterations lead to better approximate geometric median and less robust to normalized mean attacks. The normalized mean attack has been addressed in Section
From Figure
7 CONCLUSION
In this paper, initiated study of robust distributed learning problem under realistic heterogeneous data. We showed that many existing Byzantine-robust aggregation rules fail under simple new attacks, sometimes without any Byzantine workers. As solution, propose resampling scheme
8

---

Under review as a conference paper at ICLR 2021
which effectively adapts existing robust algorithms to heterogeneous datasets negligible computa- tional cost. We believe robustness under heterogeneous conditions has been an overlooked direction of research thus far and hope to inspire more work on this topic. Extending to the decentralized setting, stronger Byzantine adversaries, as well as obtaining optimal algorithms are other challenging directions for future work.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dan Alistarh, Zeyuan Allen-Zhu, and Jemry Li. Byzantine stochastic gradient descent. In NeurIPS Advances in Neural Information Processing Systems, pp. 4613-4223, 2018.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning, 2018.
Moran Baruch, Gilad Baruch, and Yoav Goldberg, A little enough: Circumventing defenses for distributed learning, arXiv preprint arXiv:1902.06156 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar, signSGD with majority vote is communication efficient and fault tolerant. arXiv preprint arXiv:1810.0529) 2018.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens, 2018.
Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent. NeurlPS. Advances Neural Information Processing Systems 30, pp- 119-129, 2017.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning scale: System design. In SysMI. Proceedings of the 2nd SyxMI. Conference, Palo Alto, CA, USA, 2019.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. arXiv preprint arXiv:1803.09877 2018.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings. Proceedings of the ACM Measurement and Analysis of Computing Systems,, 1(2):1-25, Dee 2017. ISSN 2476-1 1249. doi: 10.1 10.114/3154033 URL /
dex.
Georgios Damaskinos, El Mahdi EI Mhamdi, Rachid Guerraoui, Arsany Hany Abdelmessih Guirguis, and Sébastien Louis Alexandre Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. Conference on Systems and Machine Learning (SysML) 2019, Stanford. CA, epfl www.c///rrrrreeeeee
USA. pp. 19, 2019. URL httL:tttt://Afocciieeee
Deepesh Data and Suhas Diggavi. Byzannine-resilient sgd in high dimensions on heterogeneous data. arXiv preprint arXiv:2055.07866, 2020.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2),742-864, 2019.
Avishek Ghosh, Justin Hong, Dong Yin, and Kannan Ramchandran. Robust federated learning in a heterogeneous environment. arXiv preprint /rXiv: 996606629, 2019.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu. Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, arXiv preprint arXiv: 19922.099777 2019.
10

---

Under review as a conference paper at ICLR 2021
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes. In JCML 2019 Proceedings of the 36th International Conference on Machine Learning, 2019.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 665-674. IEEE, 2016.
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concur- rency: the Works of Leslie Lamport, pp. 203-226. 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--2324, 1998.
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling, RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544 1551- 2019.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication--fffiieeee learning of deep networks from decentralized data. arXiv preprint arXiv:1602.05629, 2016.
Edward Meeds, Remco Hendriks, Said Al Faraby, Magiel Bruntink, and Max Welling. Mlitb: machine learning in the browser. PeerJ Computer Science, I:ell, Jul 2015. ISSN 2376-5992. doi: 10.7717/peerj-os.11 11. URLhttp::/dae http://xxxdooi..ooooooo org. 10. /ttp///e00.77//rrr-ccc..._.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in byzantium. arXiv preprint arXiv:/802.00927, 2018.
D Middleton. Mathematical statistics and data analysis, by john a. rice. pp 595.19559 isbn 0-534- 08247-5 (wadsworth & brooks/cole). The Mathematical Gazette, 72(462):330-331, 1988.
Ken Miura and Tatsuya Harada. Implementation of a practical distributed calculation system with browsers and javascript, and application to distributed deep learning. arXiv preprint /503.05533 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-perffrmancc deep learning library. In Advances in Neural Information Processing Systems, pp. 8024-8035, 2019.
Jie Peng and Qing Ling. Byzantine-robus decentralized stochastic optimization. In ICASSP 2020- IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 5015-59335333 55339. IEEE, 2020.
Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust Aggregation for Federated Learning. arXiv preprint arXiv:1912.13445 2019.
Shashank Rajput, Hongyi Wang. Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy- based framework for faster and more robust gradient aggregation. arXiv preprint arXiv:1907.12200 12205, 2019.
Sattler, K. Müller, T. Wiegand, and W. Samek. On the byzantine robustness of clustered federated learning- In ICASSP 2020- 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8861-8865 2020.
Lili Su and Jiaming Xu. Securing distributed gradient descent in high dimensional statistical learning. arXiv preprint arXiv: 101400 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: a novel image dataset for benchmarking machine learning algorithms, 2017.
11

---

Under review as a conference paper at ICLR 2021
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized prizantiine-oleramn SGD. arXiv 2018.
preprint
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent
with suspicion-based fault-tolerance. In ICML 2019 35th International Conference on Machine Learning, 2019a.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation. arXiv preprint 1403::9903339950 2019b.
Zhixiong Yang and Waheed U Bajwa. Bridge: Syzantine-resilien decentralized gradient descent. arXiv preprint arXiv: / 1199980.099. 2019a.
Zhixiong Yang and Waheed U Bajwa. ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning, IEEE Transactions on Signal and Information Processing over Networks, 2019b.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. arXiv preprint arXiv: 18030048,, 2018a
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Defending against saddle point attack in byzantine-robust distributed learning. arXiv preprint arXiv: arXiv.1806.05358, 2018b.
12

---

Under review as a conference paper at ICLR 2021
A CONVERGENCE ANALYSIS OF KRUM WITH RESAMPLING
Theorem II (Resampling KRUM), We assume that (i) the cost function is three times differentiable
with continuous derivatives and non-negative ((x) 2 O; (ii) the learning rates satisfy Et = co and Et vi. < Jc. Let the good workers have stochastic gradients Gi(æ, for i E good C [n]. We assume that for uniformly chosen j E good, the following is true (iii) 5,,[G,(æ,, [)] V((x) and vr & {2,3, 3, 43. E. (2, E)Il I A, + +,,l "I for some constants Aç, B,; (iv) there exists < / such that for all we have nTT, <dd oxx) I [VV[())] sin
constant 0 2-1 _- where o² o²(x) ==
5² (x)) (v) finall, beyond a certain horizon, ||=|| 2 D, there exist E > 0 and
0 S 3 < / - at such that [IV 2 > 0 and (xx, vl(()) 2 cos ||| [VL())] If 1
and f + 3 < n,, then
KRUM RRsampplngg is (a, sf) resilient where 0 S < //2 is defined by
sin a n(T.af)-váo [VC(m]] nm,, f) == 22(n f ((n-1-2)-(-11--111
(12)
a-
the sequence of gradients VL(xx) converges almost surely to zero.
Proof. We only prove the first statement. The second one follows from applying (Blanchard et al. 2017
Proposition 2) directly.
After resampling, we have ń == 7 gradients, and at most f == 8f of them are Byzantine. Without loss of generality, we assume that Byzantine vectors B,,..., By occupy the last f positions in the arguments of KRUM We denote as KRUM KRUM( (V,M(V,,...... ,,... Vn- Bi,.... By). For each index i, we denote by (i) (resp. di)))) the number of correct (resp. Byzantine) indices j such that + j (recall again that denotes that Vj belongs the f - 2 closest vectors V, We have
(i) + (1) ñ ñ- -2 ñ 2f (1) S f-f-2 (1(1) < f
We focus first on the condition (i) of (a, /)yyynnntinee resilience as in Definition A We determine an upper bound on the squared distance ||ERUMM g| Note that, for any correct j. EV, = 9. Let i, be the index chosen by KRUM.
KRRMMM- g|l S ||E(KRUM Tx(t.] in correctj V
< El| KRUM Tc(t.] En i. eorrect 1
$ E correct & [E|[V; [2) coneecy
V1l121(i. = i)
Σ byz B [k]
1 = k)
ccoroct))
where 1 is the indicator function. Examine for correct index i.
11V
(2( Σ sconret 1 [c(
Σ ccrreet
V 1/112
Σ, i +oorrect/
14: V2112
ElIV; 6c()) E Eiooonnat 1 < 6c())
Σ, Ei-rcorrecj ElIV, V/112
< 2do
where o² : m-1 22 in Proposition I We now examine the case is = k for some Byzantine index k. sn
The fact that minimizes the score implies for all correct
Ex-oonneyj || 111 + Ex 1 By BB < E,
- Er byz 114/ BB
(13)
Then, for all correct indices
|| 1B - (.) Σ Ex-cconecy V1112 < a((k)
1
1. Σ Ek-comnes) [ 1/112
< (.(k] E Ex 11Ve 0,112 + ,,(R] Ei 11V - Bill²
13

---

Under review as a conference paper at ICLR 2021
Focus (i) == : 1 ||V Bill? each correct worker has ñ f 2 neighbors, and f + 1 non-neighbors. Thus there exists correct ((t) which farther from than any of the neighbors of i. In partieular, for each Byzantine index such that I, IIV; B1ll = I|V; V((s)l2. Whenee
|
B.(R] Σ ocooreeyy
1
1/1l²= - (.(k) Ei VV; 1 11 + [ [x)
IIV; VEcai12
1 E k ccooree E|| BB 8.1K]
V/l1a
8.(1)
2do + [.(k]
b.(() Ecorret j E||V (/(13 =)
8.1k)
- 6.(0)
8.(1)
(n - 1
kk(k)
k.(k)
< f-2
f ii f - 1))2do
2f
n 2-
Putting everything together we have
[[RRUM- gl1 (ñ F)2do² +f.
a-f-2
A-2/-2 (ī f 1))2do2
B-2f-2
S 1/ (ñi, Nd
By assumption (ñ, f) < || we know
(EKRUM, g) 2 (l||) nf, f) V a) ||9|| = (1 - sin ax) 1
(14)
To sum up, (i) of Byzantine resilience holds. Now we focuse on (ii).
F [RUM|| Exorect : 1 = i) + Enyz [
We think of G as the estimator of gradients among good workers. More specifically, G is random variable which uniformly samples one worker among good workers and samples one gradient from the worker. Then P(G =) - E P(V; = v)), and
E||G||- = E. P(G = u))l=""' = E. P(V = ->]+=ll== = EIVI
(15)
Thus
Econect ElIV S EE' V|| (n -)E
(16)
We have
E| KRUM|| S (n - ]EEGGG + Enyz BI k)
Denoting C' a generic constant, when i, = ki we have for all correct indices
|| BB
be(k) E Ex-reenect j 1ill S V Tz(k) E, Ei- V1, 1/112 +
(3) (k
Ve
s C. (V I Ei 1IV/ Vill +
do(l) (k)
(c)
SC C Eomea, y ||V,|
Now
|| S [
Σ
V (k)
Σ Vyll
(k)
k j
k
0
Σ
|
| 1l" S C
M
Take expectation to both sides and apply generalized Young's 's inequality
af Per S p1aj
Pm
(17)
where +... + = 1, we have
E||B&|I' < SC C
EI + + - S CEI|GI
(18)
the last inequality comes from (16). Thus we have proven property (ii) (a:, f) Byzantine resilience.
14

---

Under review as a conference paper at ICLR 2021
A.1 ALTERNATIVE CONVERGENCE PROOF OF KRUM WITH RESAMPLING
For completeness we also provide an alternative proof for slight variation of the Byzantine Resilience definition, under the same algorithm KRUM with resampling.
Definition B ((a, /))yyyantine Resilience Alternative.). Let 0 S a < < be any angular value, and any integer 0 S S Let V1, .... Vn be any identically distributed random vectors in RV, V1 ~ G. with IGG = g. Let B1, ...... By be any Byzantine vectors in R possibly dependent on the V₁'s. An aggregation rule F is said be (a,, -Byyannnnene resilient if. for any 1 S J1 < < <jf S then
F F(V.
B1
Bj B.....Vn)
35 satisfies (i) (E (.) 2 (1 (I-sina) sin - ||||0 and (ii) for = 2,3, 3 4, E| EE|G
h1
Again, similarly as for the above Theorem II we can obtain almost sure convergence analogous to (Blanchard et al.) 2017 Proposition 2)
Theorem III (Resampling KRUM, Alternative). We assume that (i) the cost function L is three times difserentiable with continuous derivatives and non-negative L(x:) 2 0; (ii) the learning rates satisfy Et "tt
and L 72 < oo; (iūi) the gradient estimator satisfies E G(r, E) = V ((x) and dr E (2,3,4) 4), F (a E)1l" S A,+ B, ||==]] for some constants Ap, B,; (iv) there exists a constant
0 S a < n/2 such that for all x we have (T, . /d (xx) I [V[(=)]] sin o (V) finaly, beyond
certain horizon, || 2 D, there exist > 0 and 0 S 3 x/2
such that [VL(x)]] 2 =>
and (x, vl(x)) 2 cos || (IVIII(V(ar)) If x > and 28 + 3 < n, then
KRUM cesampling is (a, (f) -Byzantine resilient as in Definition defined by
B where 0 S
sin
u(Tafivaa n(n, f) = 2( f /2 [VC(
f( f2
(19)
the sequence of gradients V((x)) converges almost surely to zero.
Proof. A key difference between Definition
B and (Blanchard et al. 2017
Definition 1) is that
Definition B removes the independence requirement for the input good gradients [V:)/-// In
(Blanchard et al. (0177). there are two propositions: (Blanchard et al. 2017 Proposition 1) proves
that KRUM satisfy [Blanchard et al. 2017 Definition 1), and (Blanchard al. 2017 Proposition 2)
shows almost surely convergence of the gradient V..
In our case, we only need show that KRUM ceeammping satisfy Definition B because the conver-
gence of V is identical to the proof of (Blanchard et al. 2017] Proposition 2). Since the gradients after resampling is identically distributed according to Proposition]] [|
we can keep all of the proofs of
(Blanchard et al. [017]] Proposition 1) except for the last inequality where the independence is used.
B&ll" S C
Σ
|1/ ... 1I-III [|2=-
(20)
By applying expectation to both sides of the inequality and the independence of (V.)"=/ they conclude that
E||
E ElIV,,,(|**
| ||G||T TM
(21)
We can immediately show that BxI < C'IGGI" with the help of general form of Young's inequality. We prove this using the standard Young's inequality. The Young's inequality states that for > 1, 1, = 1, a. 2 0, we have
ab
<
be
(22)
p
Let | b = 1| R2 IIV 8-
I q= م we apply Young's 's inequality and p
| ... | - 7-t = -يب
V
15

---

Under review as a conference paper at ICLR 2021
We can apply Young's inequality agin for the second term of right hand side. Let |V2l " V3
b
1 and p r=r1,
we apply Young's inequality
r2
"... ................................ IVn
| 7
I f1|r-- S EEST + [
where the second inequality results from recursively applying Young's inequality. Then we apply expection to both sizes of the inequality gives
E||V|||**-. ||--s||'->>
Di=l =EIVII" = |[]|"
Then applying expectation to Equation 20 gives
E| B&ll" 3 C Cr E/
1/--111n~ C||
(23)
where C' a general coefficient.
B CONVERGENCE OF BYZANTINE RESILIENT SGD
In this section, obtain finite-time convergence guarantee for any algorithm which satisfies (o,, /)-Bynantine resilience. As far as we are aware, this is the first convergence result for KRUM.
From Theorem I know that Suppose that the following condition holds for any iterations k for some constants E (0, 1] and B 2 such that
|IE gll s (1 l)1l11 and E| EF < 32,
(24)
where is the output the obbst-aggrregation algorithm and g = V fxxx). This first condition bounds the bias wheras the second part bounds the variance of F.
Convergence.
Theorem IV. Given any biased stochastic estimator F satisfying 22
the following holds for the
update F++1 = Tk F and an L-smooth potentially non-convex
x lower-bounded by f*:
1 K
2L(f(ro)-1 fr) + EI|
(f f*)
8K
82K
Proof. The following holds for any S :
2
Eg]f(r++1] < f(xx) - En(g, F) +
|F||2
2
L
3L
< f(x) - En(g, F)
2
82
S fxx)
" S/2 110112
"
1
g||²
2
170
3²
n S f(x))
2 ||ا||
2
The first inequality uses the smoothness of f. the second separated and bounded the variance of F by 83, third inequality follows from rearranging terms and using I 1, and the final inequality used bound on the bias of F. Now rearranging the terms and averaging over gives:
1
K
2(f(xo) f(xx)) + nL3
2(f(xo) f²)
nōK + LL
5 S
K
nöK
8
K=O
Picking 77 = min + V
2(f(zo) (*)
gives the desired rate.
LK
16

---

Under review as a conference paper at ICLR 2021
Relation to other conditions. If F is unbiased stochastic gradient E[F) æx] g and variance o², then (24) holds with 6 = 1 and 5 = a. this case, Thm. recovers the standard convergence of SGD for smooth non-convex functions.
instead, we have (EF,g) g) 2 (1 - sin(a)))lsll. and E|| < |gl & GP.
||E F g/l =llb|l - 2(E[F)))) + ||[]]]|
=|9b|1 - - + F|
Thus, in this case (24) holds with (a). and G. Here, we only get convergence sin(a) I 2- Further, the assumption that F|| ||lll < G2 is extremely strong.
C RESAMPLING WITH REPLACEMENT FOR ROBUST LEARNING
Algorithm 3 Resampling with replacement
Input: (g: : [m]]]. T.
for /o 1,.., do Uniformly sample {g), Ji=1 from (ge i [n]]
Compute average 9r == -.: 9J,
Return (g: : E [T]} U/ (T)
Contrary to resampling without replacement which has an explicit bound for malicious gradients after resampling, its with-replacement version has no guarantee for the honest majority.
Lemma 3. Given set of vectors {g: E [n]} of any distributions, the ouiput of Algorithm {g: E [T]} are identically distributed with expectation
Eg:
Egi
VIE
(25)
If f of the inputs are Byzantine, then subset S c. (ge :E [TT) are not faulty. The cardinality of S [E|]]= [T(1 f/n]]* and the gradients are identically distributed with expectation
Eg
Σ Eg:
VOES
(26)
good
iEgood
Proof.
Eg: - Ei= E 9: Ei Egi
There are (1- (1-f/n) /n) chance that sampled gradient 9;, is good and (1 -1--fll f/n)** chance that all of the
s sampled gradients are good. Repeat the resampling for times gives E|S] = [T(] f f/n)*]- D
Remark The gi has same expectation minibatch sgd.
We denote the expected number of Byzantine gradients in {g. [T]} follows:
= = T E|S] = 7(1 [(1 [1)-m())1
(27)
Since the vectors in S are identically distributed, we can apply robust aggregation rule A, like Multik-KRUM, to (g. / [T]]- The convergence of Algorithm for Multi-KRUM is stated below.
Theorem V (Resampled KRUM), Assume the dataset is decentralized stored. Assume other con- ditions (Blanchard et al. 2017 Prop. 2) hold true. is the number of aggregations. If 2f 2 < T, then with a probability DK KRUM&RSWR is Byzantine robust and the sequence of gradients almost surely converges to zero. The p is defined as
[/2]
Σ
9 [//2 (-/))
(28)
where q == s/n)*
17

---

Under review as a conference paper at ICLR 2021
Proof. The probability of gi is good is (1 f/n)". The probability of non-faulty majority after RSWR is thus
7/22
p Σ
(1))) (1)))
q [11
The output of RSWR are identically distributed by Lemma Thus we know that the robust aggregation rule converge with probability p"
Remark 5. Consider the range of T, f- Since Theorem requires 2 + 2 < T, we need
(og(1/2+//T) Furthermore, 2 1 is lower bounded, T n-2f which only requires 2f < Tog(I-1/n)
Remark 6. Notice that the cardinality |S] is stochastic which means it is possible to have faulty majority any round. if the Byzantine gradients are very large, like gaussian attack, the model Byzantine grudient is selecied. On the other hand, in the experiment section, we show that for muny attacks (labelflipingg bitflipping, etc.) the error introduced by faulty majority rounds are amortized overtime. To fix this issue, the server can normalize all the gradient by their norm such that a faulty majority round would not lead to catestrophic consequences.
diverges soon
18

---

Under review as a conference paper at ICLR 2021
D ADDITIONAL EXPERIMENTS
D.1 FASHION-MNIST
In this subsection, we demonstrate that our algorithm also works on modern dataset like Fashion- MNISTXiao et al. (2017). Since the Fashion-MNIST is designed to be drop-in replacement of MNIST, we conduct experiments on Pashion-MNIS" with same setups as Figure The results are presented in Figure
KRUM
CM
RFA-T1
RFA-T8
bitlipping
labelfiipiig
15
gaussian
15
30
mimic
mimic
20
20
Iterations
Iterations
lterations
Iterations
Aggr
Resa-mesn
Aggr- Resamliianpiing (f=0)
Figure 4: Test accuracies of KRUM, CM, RFA under 5 kinds of attacks (and without attack) non-iid FasSion-MNIST datasets. There are 12 workers and of them are Byzantine according to each attack row. Columns show each aggregation rule applied without (red) and with resampling (blue). Dotted lines for comparison are showing the same method without any Byzantine workers (f 0). For REA, T1. T8 refers the number of inner iterations of Weiszfeld's algorithm.
19

---

Under review as a conference paper at ICLR 2021
D.2 CIFAR-10
We run experiments on CIFAR-10 (Krizhevsky et al. 2009) with ResNet-20 (He et al. 2015). We train our model on 12 nodes which includes Byzantine attacker with mimic attack. We use KRUM as the aggregation rule for demonstration. We choose learning rate to be 0.1 and batch size per node to 120. The CIFAR-I0 dataset is splitted across good nodes such that 50% of samples on each good node has same distribution overall distribution, the rest 50% samples from single class which is different among good workers. We present our results in Figure
krum
krum krum-nesn
Accuracy (%)
40
30
20
10
500
1000
1500
2000
2500
3000
3500
4000
Batches
Figure 5: Compre KRUM and KRUM oResampling for training ResNet-20 on CIFAR-10 dataset. There are 10 good workers and 2 Byzantine workers.
Note that the accuracy in this example is lower than the normal setting because krum may bias towards certain nodes. Besides, the batch norm maybe influenced by the heterogenous distribution of data.
20

---

Under review as a conference paper at ICLR 2021
D.3 RESAMPLING OR FIXED GROUPING
In (Chen et al. 2017), workers are grouped the beginning of training, and they are trained on i..dd datasets. contrast, resampling is performed every round, and applies to non-iid datasets. If Byzantine worker can predict the random bits on server, resampling becomes grouping in each round which is still stronger than (Chen ct al. 2017).
In Figure 7 we compare KRUM oresampling with vanilla KRUM and KRUM with fixed grouping. As we can see, the fixed grouping has better accuracy than vanilla KRUM, but weaker than resampling as expected.
KRUM
CM
RFA-T1
RFA-13 REA-TU
80-
80
40
75
2
4
2
2
Atbak (o
85
87.5
40
75
05.0
85.
70
62.5
82.5
65
80
00.0
90-
800
08.0
20
62.5
00
20
2
6
6
80
70
70
80
60-
50
90
minid
80
115
70
80
70
60-
Agg
Ag21 4155/ON
Itraatons
Figure 6: Comparing aggregation rules under 5 kinds of attacks on non-iid datasets. There are 10 workers and 2 of them Byzantine. In the grid of experiments, the same column and same attacks are applied to the same row. The aggregation rules are KRUM (Blanchard et 2017), CM (Yin et al. 2018a), RFA (Pillutla al. 2019). The RFA-TI, T3, T8 refers to the number of inner iterations.
aggregation rules used in
Krum
Test Accuracy (%))
Selection counts
vanilla resampling
500
fixed
20
0
1
2 3
5
Iterations
Nodes
Figure 7: Comparison with resampling, and fixed grouping for KRUM non-i.i.d datasets.
21

---

Under review as a conference paper at ICLR 2021
D.4 RESAMPLING HYPERPARAMETER
The resampling hyperparameter controls the variance reduction, as has been stated in Proposition In Figure 8 we compare the performance of no resampling and resampling with 2,3, 4 on heterogenous MNIST dataset. There are 10 workers in total and no Byzantine workers. Each experiment has been run for 5 times.
As from Figure 8 higher leads to faster convergence. It matches with the Proposition | that higher s leads to greater variance reduction.
krum
cm
80
Accuracy (%)
60
no-rs
20
10000
20000
30000
10000
20000
30000
Iteration
Iteration
Figure 8: Compare no resampling with s 2,3, 4 on MNIST data. There are 10 workers and Byzantine worker.
22


Reviews:
[{"review_id": "alf9ZPkSo0l", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose the resampling mechanism to improve the performance of existing robust statistics method for Byzantine-robust distributed SGD. Both theoretical and empirical analysis are provided. In overall, the proposed method is technically sound, and works well in practice.\n\nHere is some detailed comments:\n\n1. According to my understanding, the resampling mechanism is actually trying to convert non-iid gradients into iid ones. If an averaged random subsample of gradients contains only good gradients, then sampling with replacement makes it an unbiased estimator. If the averaged random subsample contains Byzantine gradients, then it is corrupted anyway and we don't care it's biased or not. Thus, for the averaged subsamples containing no Byzantine gradients, they actually become iid. Is my understanding correct?\n\n2. The idea is simple and easy to implement upon all the previous work. Some people may think this work is incremental, but I think the simplicity of the proposed method is an advantage.\n\n3. It will be better if the authors also provide the convergence analysis of resampling with CM. For Krum, note that larger n (number of workers) actually results in worse convergence in Theorem II, which questions whether we should use distributed training.", "extra_scores": {}, "extra_text": {}}, {"review_id": "91A7OlOBouV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Many existing researches on distributed deep learning works in byzantine robustness in a centralized PS setting under the assumption of i.i.d. data distribution on workers, e.g. KRUM. This paper presents a simple resampling scheme that adapts the existing robust algorithms to heterogeneous datasets (referred as KRUM-RS later in this review). It firstly proposes two new attacks under non-iid data distribution that fooled byzantine fault tolerant algorithms like KRUM, Coordinate Median (CM), and RFA (Normalized Median-NM or Geometric Median-GM). Then it proposes the RS algorithm and proved its theoretical convergence guarantee the of KRUM algorithm over non-iid data, and when the parameter server (PS) does not control the dataset distribution. Experiments showed the convergence guarantee over KRUM and even CM, NM/GM algorithm. \n \nThe proposed resampling algorithm is somewhat novel and can be applied to KRUM to guarantee its convergence. The paper is technically sound. The organization of this paper is OK, but it lacks clarifications on its intuition on the sampling method (why and how it improves other methods by sampling). The technical part is not self-contained. For example, in Def. A, what does it mean for r=2,3,4 that E(F) <= E(G)?  More clear explanation and definition should be present.\n\n\nThis paper seems to over-claim some of its results: for example, this paper claims that \"We propose a simple new resampling step which can be used before any existing robust aggregation rule\", but the theoretical analysis only applies to the rule from KRUM. How could one should the new resampling method work for any robust aggregation rule? There seems to be a large gap here.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5H8WQjxSMc", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper summary:\n\nThe paper studies Byzantine robustness in the context of distributed learning from heterogeneous datasets. This problem has been widely studied previously, but under the additional assumption that the data of the good workers is i.i.d.. The authors give examples of situations and poisoning attacks with which current defences designed for the i.i.d. situation can be overcome.  They also propose a simple resampling scheme that can be used as a preprocessing step before applying any standard robust aggregator from the i.i.d. literature. They provide theoretical guarantees for their resampling scheme when used together with KRUM. The also test their algorithm against the i.i.d. baselines and multiple attacks. \n\n##########################################################################\n\nPros:\n\n- The paper is well-written and motivated and addresses an important problem. Indeed, in the context of distributed and federated learning, where privacy and communication costs are of particular importance, the problem of corrupted or adversarial updates becomes very relevant.\n- The gap between existing defences and the non-i.i.d. setup is well-motivated, with various examples and attacks proposed in the paper.\n- The proposed resampling scheme is simple and easy to incorporate into previously proposed algorithms. It is also amendable to theoretical analysis, as shown in the paper.\n- The experimental evaluation does show clear improvements in many cases when the resampling scheme is used.\n    \n##########################################################################\n\nCons/suggestions:\n\n- While heterogeneous data is allowed, the assumption on the top of page 2 that the variance between the gradients of the local datasets is bounded is somewhat unintuitive to me. It seems like this is not just the usual assumption that the variance of the stochastic updates is bounded, but it's also a measure of how non-i.i.d. the datasets are. Is there an intuitive explanation of what such a bound means in terms of how the distributions of the clients vary?\n-  While the resampling method is indeed relatively simple and easy to understand, I think that the paper will benefit from a discussion on why it actually helps. For example Remark 1 could be followed by some examples of situations when mixing the gradients in advance will help or alternatively some comparison to other fields where such resampling approaches were found useful. Similarly, it would be interesting to see a discussion of how much and in what respect does the proof of Krum change once dependence between the vectors is introduced. \n- For the experiments, it would be nice to see plots for different values of $s$, not only $s = 2$, so as to see if the method effectively trades-off convergence speed with robustness, as claimed in Remark 1.\n- It will also be nice to get more information about the data splits between the clients, as well as experiments with multiple repeats and error bars and/or multiple amount of heterogeneity introduced, so that the significance of the improvements can be easier to evaluate.\n  \n##########################################################################\n\nMinor points:\n\n- In Algorithm 1 the inputs passed on to Algorithm 2 are different that the inputs received in Algorithm 2. It would be nice to make these consistent.\n- In Proposition 1 it is assumed that the input is a set of gradients. However, in the second bullet point $f$ gradients are assumed to be Byzantine. It's a bit unclear what this means given that we are just talking about $n$ arbitrary vectors. I think I understand what is meant, but it will be nice to clarify.\n\n\n##########################################################################\n\nReview summary:\n\nThe paper shows that a simple, but effective resampling scheme can be used to transfer i.i.d. Byzantine-robust algorithms to a non-i.i.d. setup. The paper is generally well-written and provides some theoretical and experimental evidence to support the proposed method. Therefore, I recommend acceptance, together with a few suggestions for improving the discussion and the experimental section. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an algorithm for distributed optimization in that aims to be "Byzantine-robust", in the sense that it learns successfully when some of the workers send arbitrary messages.  The goal in this work is to remain robust when each worker samples data from a different distribution.

While reviewers found the work interesting, issues about the theoretical development arose during the discussion period, and it appears that the paper cannot be accepted in its current form.

The most serious issue was with Proposition I, which appears to be incorrect.  In its putative proof, the authors write that each gradient is sampled at most $s$ times.  This naturally leads to the conclusion that, in Algorithm 2, when the Break statement is reached,  $g_{j_i}$ is not used to compute $\bar{g}_t$.

Given this interpretation of Algorithm 2, it seems that Proposition I cannot be true. For example, if $s=1$, once $t \geq n/2$, fairly often, gradients will be sampled that had previously been sampled. In such cases, would be zero, so that, on average, $\bar{g}_t$ would be biased toward zero in later rounds.

Their putative proof of Proposition I refers to a whole chapter of a statistics text. We couldn't find anything in that chapter that implies what they claim about Algorithm 2 (or that treats a sampling scheme like Algorithm 2 at all).

Throughout the paper, when the authors took expectations, it was not always clear what was random and what was fixed.  After some discussion, disagreement remained about how to interpret some of the assumptions.  This was true in particular about the assumption in the first displayed equation on page two.  
Decision: Reject