BASGD: Buffered Asynchronous SGD for Byzantine Learning
Authors: Yi-Rui Yang
Wu-Jun Li
Venue:  (2021)
Keywords: Distributed optimization
asynchronous Byzantine learning

Abstract: Distributed learning has become a hot research topic due to its wide application in cluster-based large-scale learning, federated learning, edge computing and so on. Most traditional distributed learning methods typically assume no failure or attack on workers. However, many unexpected cases, such as communication failure and even malicious attack, may happen in real applications. Hence, Byzantine learning (BL), which refers to distributed learning with failure or attack, has recently attracted much attention. Most existing BL methods are synchronous, which are impractical in some applications due to heterogeneous or offline workers. In these cases, asynchronous BL (ABL) is usually preferred. In this paper, we propose a novel method, called buffered asynchronous stochastic gradient descent (BASGD), for ABL. To the best of our knowledge, BASGD is the first ABL method that can resist malicious attack without storing any instances on server. Compared with those methods which need to store instances on server, BASGD takes less risk of privacy leakage. BASGD is proved to be convergent, and be able to resist failure or attack. Empirical results show that BASGD significantly outperforms vanilla ASGD and other ABL baselines when there exists failure or attack on workers.

Under review as a conference paper at ICLR 2021
BASGD: BUFFERED ASYNCHRONOUS SGD FOR B YZANTINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Distributed learning has become a hot research topic due to its wide application in cluster-based large-scale learning, federated learning, edge computing and so on. Most traditional distributed learning methods typically assume no failure or attack on workers. However, many unexpected cases, such as communication failure and even malicious attack, may happen in real applications. Hence, Byzantine learning (BL), which refers to distributed learning with failure or attack, has recently attracted much attention. Most existing BL methods are synchronous, which impractical in some applications due to heterogeneous or offline workers. In these cases, asynchronous BL (ABL) is usually preferred. In this paper, propose novel method, called buffered asynchronous stochastic gradient descent (BASGD), for ABL. To the best of our knowledge, BASGD the first ABL method that resist malicious attack without storing any instances on server. Compared with those methods which need store instances on server, BASGD takes less risk of privacy leakage. BASGD is proved to be convergent, and be able to resist failure or attack. Empirical results show that BASGD significantly outperforms vanilla ASGD and other ABL baselines when there exists failure or attack on workers.
INTRODUCTION
Due to the wide application in cluster- based large-scale learning, federated learning (Konevený et al.
2016; Kairouz al.) 2019),, edge computing (Shi al. (0166) and so on, distributed learning has
recently become a hot research topic (Zinkevich et al. 2010 Yang. 2013 Jaggi et al. 2014 Shamin
al. 2014| Zhang& & Kwok, 2014, Ma al. 2015: Lee et al. 2017 Lia et al.) 2017 Zhao et al.
2017 Sun et al. 201 Wangni et 2018 Zhao et al. 2018 Zhou et al. 2018 8 Yu et al. 2019a b
Haddadpour et al. 2019). Most traditional distributed learning methods are based on stochastic
gradient descent (SGD) and its variants (Bottou 2010; Xiao 2010; Duchi et al., 201T Johnson &
Zhang 2013: Shalev- Shwarrt & Zhang 2013) Zhang et al.) 2013] Lin et al. 2014)] Scchmidt et al.
2017
Zheng et al. 2017 Zhao et al. 2018), and typically assume failure attack workers.
However, in real distributed learning applications with multiple networked machines (nodes), different kinds of hardware software failure may happen. Representative failure include bit-flipping in the communication media and the memory of some workers (Xie et al.) 2019). In this case, a small failure on some machines (workers) might cause distributed learning method fail. In addition, malicious attack should not be neglected in an open network where the manager (or server) generally has not much control on the workers, such as the cases of edge computing and federated learning. Some malicious workers may behave arbitrarily or even adversarially. Hence, Byzantine learning (BL), which refers distributed learning with failure or attack, has recently attracted much attention (Diakonikolas et al. 2017 Chen et al. 2017 Blanchard et al.) 2017 Alistarh et al. 2018
Damaskinos 2018 Xie et al. 2019 Baruch et al. 2019 Diakonikolas & Kane 2019).
Existing BL methods can be divided into two main categories: synchronous BL (SBL) methods and asynchronous BL (ABL) methods. In SBL methods, the learning information, such as the gradient in SGD, of all workers will be aggregated in synchronous way. On the contrary, in ABL methods the learning information of workers will be aggregated in an asynchronous way. Existing SBL methods mainly take two different ways achieve resilience against Byzantine workers which refer those workers with failure or attack. One way is to replace the simple averaging aggregation operation with some more robust aggregation operations, such as median and trimmed-mean (Yin et al., 2018).

---

Under review as a conference paper at ICLR 2021
Krum (Blanchard et al. 2017) and ByzantinePGD Yin et al. 2019) take this way. The other way is to filter the suspicious learning information (gradients) before averaging. Representative examples include ByzantineSGD (Alistarh et al. 2018) and Zeno (Xie et al. 2019). The advantage of SBL methods is that they are relatively simple and easy to be implemented. But SBL methods will result in slow convergence when there exist heterogeneous workers. Furthermore, in some applications like federated learning and edge computing, synchronization cannot even be performed most of the time due to the offline workers (clients or edge servers). Hence, ABL is preferred in these cases.
To the best of our knowledge, there exist only two ABL methods: Kardam (Damaskinos et al. 2018) and Zeno++ (Xie et al. (020). Kardam introduces two filters to drop out suspicious learning information (gradients), which can still achieve good performance when the communication delay heavy. However, when face of malicious attack, some work finds that Kardam also drops out most correct gradients in order to filter all faulty (failure) gradients. Hence, Kardam cannot resist malicious attack (Xie et al. 2020p. Zeno++ scores each received gradient, and determines whether to accept it according to the score. But Zeno++ needs to store some training instances server for scoring. In practical applications, storing data on server will increase the risk privacy leakage or face legal risk. Therefore, under the general setting where server has no access to any training instances, there have not existed ABL methods to resist malicious attack.
In this paper, propose novel method, called buffered asynchronous stochastic gradient descent (BASGD), for ABI.. The main contributions of BASGD are listed as follows:
To the best of our knowledge, BASGD is the first ABL method that resist malicious attack without storing any instances on server. Compared with those methods which need to store instances on server, BASGD takes less risk of privacy leakage.
BASGD is theoretically proved to be convergent, and be able to resist failure or attack.
Empirical results show that BASGD significantly outperforms vanilla ASGD and other ABL baselines when there exist failure or malicious attack on workers. In particular, BASGD can still converge under malicious attack, when ASGD and other ABL methods fail.
2
PRELIMINARY
This section presents the preliminary of this paper, including the distributed learning framework used in this paper and the definition of Byzantine worker.
2.1 DISTRIBUTED LEARNING FRAMEWORK
Many machine learning models, such as logistic regression and deep neural networks, can be formulated as the following finite sum optimization problem:
n Σ (w::))) n
min F(w)= weRd
where w is the parameter to learn, d is the dimension of parameter, n is the number of training instances. f(w; 2,) the empirical loss on the training instance 24. The goal of distributed learning to solve the problem in (T) by designing learning algorithms based on multiple networked machines.
Although there have appeared many distributed learning frameworks, in this paper we focus on the widely used Parameter Server (PS) framework (Li et al., 2014). In a PS framework, there are several workers and one or more servers. Each worker can only communicate with server(s). There may exist more than one server in a PS framework, but for the problem of this paper servers can be logically conceived as a unity. Without loss of generality, we will assume there only one server in this paper. Training instances training instances on worker_k, we have Lg= Dx = {1, 2,...... n) and Dj n Dx
disjointedly distributed across workers. Let D& denote the index set of
if k of k', In this paper, assume that server has no access to any training instances. If two instances have the same value, they are still deemed as two distinct instances. Namely, 2; may equal žn (i * i').
One popular asynchronous method to solve the problem in ( under the PS framework is ASGD (Dean ct al. 2012) (see Algorithm T in Appendix [A). In this paper, we assume each worker samples one instance for gradient computation each time, and do not separately discuss the mini-batch case.
2

---

Under review as a conference paper at ICLR 2021
In PS based ASGD, server is responsible for updating and maintaining the latest parameter. The number of iterations that server has already executed is used as the global logical clock of server. At the beginning, iteration number immediately. The parameter after i iterations denoted as w'. If server sends parameters to worker iteration E', some SGD steps may have heen excuted before server receives gradient from worker_k _k next time at iteration f. Thus, we define the delay of worker_k k at iteration t as Th = t t-t t'. Worker_k heavily delayed iteration if k > Tmaas where Tman pre-defined non-negative constant.
0. Each time SGD step is executed, t will increase by 1
2.2 BYZANTINE WORKER
For workers that have sent gradients (one or more) to server at iteration f, we call worker Jk loyal worker if has finished all the tasks without any fault and each sent gradient is correctly received by the server. Otherwise, worker.A k is called Byzantine worker. If worker l is a Byzantine worker, it means the received gradient from worker ke not credible, which can be an arbitrary value. In ASGD, there is one received gradient at time. Formally, we denote the gradient received from worker _ at iteration as gi. Then, we have:
ff(w"; ;2))
if worker is loyal at iteration é; if worker.k is Byzantine at iteration t,
gi
arbitrary value,
where 0 0st S t, and i is randomly sampled from 2x-
Our definition of Byzantine worker is consistent with most previous works (Blanchard al. 2017; Xie et al. 2019 2020). Either accidental failure or malicious attack will result in Byzantine workers.
BUFFERED ASYNCHRONOUS SGD
In synchronous BL, gradients from all workers are received at each iteration. During this process, we can compare the gradients with each other, and then filter suspicious ones, or use more robust aggregation rules such as median and trimmed-mean for updating. However, in asynchronous BL, only one gradient is received by the server at a time. Without any training instances stored on server, is difficult for server identify whether a received gradient credible or not.
In order to deal with this problem in asynchronous BL, we propose a novel method called buffered asynchronous SGD (BASGD). BASGD introduces B buffers gradient used for updating parameters will be aggregated from these buffers. The detail of the learning procedure of BASGD is presented in Algorithm 2 in Appendix [ In this section, we will introduce the details of the two key components of BASGD; buffer and aggregation function.
B m) on server, and the
3.1 BUFFER
In BASGD, the m workers do the same job as that in ASGD, while the updating rule on server is modified. More specifically, there are B buffers (0 < B S m) server. When a gradient g from worker_s is received, will temporarily stored in buffer b, where b = 8 mod B, as illustrated in F Only when each buffer has stored at least one gradient, a new SGD step will be executed. Please note that no matter whether a SGD step is executed or not, the server will immediately send the latest parameters back to the worker after receiving gradient. Hence, BASGD introduces barrier, and is an asynchronous algorithm.
For each buffer b, more than gradient may have been received iteration We will store the average of these gradients (denoted by h2) in buffer Assume that there are already (N - -1) gradients g1, g......... .........-11 which should be stored in buffer b, and ho(oda) Nー ΣN g: When the N-th gradient g&v is received, the new average value in buffer b should be: S.... N-1
N-1
ho(new)
hb(old) 1/4 gN.
This is the updating rule for each buffer b when gradient is received. We use N to denote the total number of gradients stored in buffer b at the t-th iteration. After the parameter w is updated, all buffers will be zeroed out at once. With the benefit of buffers, server has access B candidate gradients when updating parameter. Thus, a more reliable (robust) gradient can be aggregated from the B gradients of buffers, if proper aggregation function Aggr(.) ) is chosen.
3

---

Under review as a conference paper at ICLR 2021
Workers
Durfeo
Buther
Bufter22
Buffer_3
Battera
Butters the servor
Figure I: An example of buffers. Circle represents worker, and the number is worker ID. There are 15 workers and 5 buffers. The gradient received from worker_s is stored in buffer-(s mod 5).
3.2 AGGREGATION FUNCTION
When SGD step is ready to be executed, there are B buffers providing candidate gradients. An aggregation function needed to get the final gradient for updating. A naive way is to take the mean of all candidate gradients. However, mean value is sensitive to outliers which common in BL. For designing proper aggregation functions, we first define the q-Byzantine Robust (q-BR) condition to quantitatively describe the Byzantine resilience ability of an aggregation function.
Definition (q-Byzantine Robust). For an aggregation function Aggr(-): Aggr((bi.... he)) = G. where G G ........ Ga] and h, [ho1:... ..... hoa]" vb [B]. we call Aggr(-) q-Byzantine Robust (q E Z, 0 < 9 < B/ B/2), if satisfies the following two properties:
(a). Aggr( [h, h', ..,, hg + h']) Aggr((h...... b.l,)))) + h', Vhi....,hg E Rd, Vh' RR;
(b). (ha) S Gy S max.es(hajh Vj E [d], AS C [B] with IS B
Intuitively, property (a) in Definition says that if all candidate gradients h, are added by a same vector h', the aggregated gradient will also be added by h'. Property (b) says that for each coordinate j. the aggregated value Gj will be between the (g + 1)-th smallest value and the (q 1)-th largest value among the j-th coordinates of all candidate gradients. Thus, the gradient aggregated by a q-BR function is insensitive to at least q outliers. We can find that q-BR condition gets stronger when increases. In other words, if Aggr(.) is g-BR, then for any 0 < q < q. Aggr( (.) is also gBRR.
Remark 1. It is not hard to find that when B > 1, mean function is not q- (--yzantine Robust for any q O. We illustrate this by one-dimension example: hy...., hB-- [0, 1], and ag 10 B. Then 1 ΣB hb hg 10 E [0, 1). Namely, the mean is larger than any of the first
values.
B
We find that the following two aggregation functions satisfy Byzantine Robust condition.
Definition (Coordinate-wise median (Yin et al. 2018)). For candidate gradients h1, l2...., h
Rd h, [161, ......., ... hood! ". vb 1, 2, B. Coordinate median is defined as: Med( Med(hi...... ha,.hh, ha)) = [Med(h.)).... ".ed.(.)))))))
where Med(h.) is the scalar median of the j-th coordinates, Vj = 1,,,.... Definition 3 (Coordinate-wvl wise g-trimmed-mean (Yin et al.
2018)). For any positive interger 9 <
B and candidate gradients h1 h2...., hg E T9 hg [ ho2...., hbd)) wb = 1,2.... .... B. Coordinate-win g-trimmed mean is defined as:
Trm([b....., hy)) = [Trm(h. 1)............ Trm(h.a))
where Trm(h.;) is the scalar g-trimmed-ment menn: Trm(h,;) B-29 EsEM, haj- Mj is the subset of (he ) obtained by removing the q largest elements and smallest elements.
In the following content, coordinate-wise median and coordinate-wee wise q- g-trimmed-meen mene also called median and trmean, respectively. Proposition I Proposition 1. Coordinate q-trmean is q- BR, and coordinate-wit median is B -BR.
shows the B-RR property of these two functions.
Here, [x] is the maximum integer not larger than æ. According to Proposition I both median and trmean are proper choices for aggregation function in BASGD. The proof can be found in Appendix
4

---

Under review as a conference paper at ICLR 2021
Now we define another class of aggregation functions, which is also important in analysis in Section 4 Definition (Stable aggregation function). Aggregation Aggr(-) (-) is said to be stable provided
that wh....., hi...., hg E R,, letting 6 = (Et= lb h ( 8. we have:
Aggr(hi,..... ha) - Aggr(hi,... hn)l S 8.
If A-gr(-) is stable aggregation function, it means that when there is disturbance with L2-norm d on buffers, the disturbance of aggregated result will not be larger than 6. Definition 5 (Effective aggregation function). A stable aggregation function Aggr(-) is called an (A1, Aefeefecctvve aggregation function, provided that when there are at most Byzantine workers and Th = for each loyal worker_k J. (vt 0, o,,,.... T --11 1), it satisfies the following two properties:
(i). EEV F(WF(W")
G aym w'] 2 VVVEE w I|? AA, Vw E : (ii). B sgnl wf (A2)². Vw R
(" )
where A1, A2 E I.,, are two non non-negative constants, Go is the gradient aggregated by A-gr(-) at the t-th iteration in cases without delay (Tmaz = 0).
For different aggregation functions, constants A1 and Ae may differ. A1 and Ag are also related to loss function F--). distribution of instances, buffer number B, maximum Byzantine worker number r and so on. Inequalities (i) and (ii) in Definition are two important properties in convergence proof of synchronous Byzantine learning methods.
revealed (Yang et al.] 2020). there are many existing asynchronous Byzantine learning methods. Krum, median, and trimmed-mean are proved to satisfy these two properties (Blanchard et al.) 2017 Yin et al. 2018). SignSGD (Bernstein et al,, 2019) can be seen combination of 1-bit quantization and median aggregation, while median satisfies the properties. Bulyan (Guerraoui et al.) 2018) uses an existing aggregation rule to obtain a new onc, and the property of Bulyan is difficult be analyzed alone. Zeno (Xie et al., 2019) has asynchronous version called Zeno++ (Xie et al. 2020), and it is meaningless to check the properties for Zeno
Please note that too large B will slow down the updating frequency and damage the performance, which is supported by both theoretical (in Appendix B and empirical (in Section (5) results. In practical application, we could estimate Byzantine worker number r' in advance, and set B to make Aggr(-) (-) be rBR. Specially, B is suggested to be (2r + 1) for median, since median is B-1 -BR.
4 CONVERGENCE
In this section, we theoretically prove the convergence and resilience of BASGD against failure or attack. There are two main theorems. The first theorem presents a relatively loose but general bound for all q-BR aggregation functions. The other one presents a relatively tight bound for each distinct (A1, Aef-efectivv aggregation function. Since the definition of (A1, A2) Ag)-effective aggregation function is usually more difficult to verify than q-BR property, the general bound also useful. Here we only present the results. Proof details are in Appendix B We first make the following assumptions, which also have been widely used in stochastic optimization.
Assumption 1. Global loss function F(w) is bounded below: 3 E R. F(w) 2 F,, E Rd. Assumption 2 (Bounded bias). For any loyal worker, it use locally stored training instances to estimate global gradient with bounded bias k: [I[[f[(w 2:)] [F(w)]l S K, Vw E Rd.
Assumption 3 (Bounded gradient). V F((w) is bounded: 3D E Rt / < D, Vw E Rd. Assumption 4 (Bounded variance). [E[[ fww; E 24) w|ll w] 0 Vw E Rd
Assumption 5 (L-smoothnesss) Global loss function F(w) differentiable and L-smooth: [VV(()) VF(w")l S L|(w - w'Il, Vw, w' E IRd.
Remark 2. Please note that do not give any assumption about convexity. The analysis in this section is suitable for both convex and non-convex models in machine learning. such as logistic regression and deep neural networks. Also, we do not give any assumption about the behavior of Byzantine workers, which may behave arbitrarily.
Let QO be the (g + 1)-th smallest value in (N{)bE(B) NŁ is the total number of gradients stored in (B-r)yB-r41 which will appear buffer b at the (-th iteration. We define the constant A Agg. V(B ((8---19--44)
in Lemma 1 and Lemma
5

---

Under review as a conference paper at ICLR 2021
Lemma 1. If Aggr(-) (.) is q-BR, and there are most r Byzantine workers (r S 9), have:
BiI G'I w'] AB...dd (D² + o² (N(").
Lemma 2. If Aggr(-) is q q-BR, and the total number of heavily delayed workers and Byzantine workers is not larger than (r S 9). have:
|B|G' VF(w") w'll S A. (TmarL- (AB.,, + o /2((0)) + + n))
Theorem 1. Ler D Ei= + o² d2/N(0)3. If Aggr(-) is q- q-BR, B O(r), and the total
number of heavily delayed workers and Byzantine workers not larger than (r q). set learning rate 1) = O TVT ). we have:
1= E VF w I1S
[[F(W9)
F*]
rdD
Ddo
SO
+0
+0
T2
Th - -
(r-++1
+0
rDdx
riLDDd Tmar
(q 10-r+11] (g-r+1)3
(q 1q-rth 1)
Please note that the convergence rate of vanilla ASGD is O(T-)). Hence, Theorem indicates that BASGD has theoretical convergence rate fast vanilla ASGD, with extra constant variance. The term (r sacrifice for Byzantine resilience. The term (rDddk(q r + 1)=b)) ) caused by the differences of training instances among different workers. In independent and identically distributed (i.i..)) cases, and the term vanishes. The term Orr LD Tmaz and related to parameter Tmaz- The term is also related to the buffer size. When N increases, (() may increase, and thus D will decrease. Namely, larger buffer size will result in smaller D. Besides, the factor (q r + 1)- (g + 1 decreases as increases, and increases increases.
1)= ) is caused by the aggregation function, which can be deemed as
+ 1)- is caused by the delay,
Although general, the bound presented in Theorem | is relatively loose in high-dimensional cases, since d appears in all the three extra terms. To obtain tighter bound, introduce Theorem 2 for BASGD with (A1, Aef-effective aggregation function (Definition 5).
Theorem 2. If the total number heavily delayed workers and Byzantine workers is not larger than r. B (r). and Aggr(.) is an (A1, (aal))effffff eeffective aggregation function in this case. Set learning
rate 17 O (IT) and in general asynchronous cases, we have:
E V F 11
L (F(")) -F=]
F=]
Li Tmaa DAgr2
(A2)
SO
+0
+0
T
T
T
T
LE (A2) 22
+
+ A
T
Theorem indicates that if Aggr(-) makes a synchronous BL method converge (i.e., satisfies Definition BASGD converges when using Aggr(-) )) as aggregation function. Hence, BASGD can also be seen as technique of asynchronization. That to say, new asynchronous methods can be obtained from synchronous ones when using BASGD. The extra constant term Ai is caused by gradient bias. When there is no Byzantine workers (r = 0), and instances are i.i.d. across workers, letting B = 1 and Aggr(h hg) Aggr(h,) = h, BASGD degenerates to vanilla ASGD. Under this circumstance, there is no gradient bias (A1 = 0), and the extra constant term vanishes.
In general cases, Theorem 2 guaranttees BASGD find a point such that the squared L2-norm of its gradient is not larger than Ai (but not necessarily around a stationary point), in expectation. Please note that Assumption 3 already guarantees that gradient's 's squared L2 L2-norm is not larger than D We introduce Proposition 2 to show that A₁ is guaranteed to be smaller than D under a mild condition. Proposition 2. Aggr(.) (-) is an (A₁, A2) -effectivee aggregation function, and G syn is aggregated by Aggr(-) () in synchronous setting. If ! sym FF(w')l w!] < D, Vw RRd, then A < D?.
G ey is the aggregated result of Aggr()). and is robust estimator of V F(w") used for updating. Since [|VF(w')] < D. VF(w") locates in ball with radius D. E[[| G syn FF(w")l w'| D means that the bias of G sym is not larger than the radius D, which is mild condition for Aggr(-).

---

Under review as a conference paper at ICLR 2021
ASGD
BASGD with median (8=5)
BAS with mmian 18 gm1)
BASGD with median [8-10)
BASGD with mmian (8
BASGD winh median [8-15]
BASGD with mmean (8+15 Q-5)
BA5GD win median [B+30)
BAS wit tmeen -30 q-10)
- <ardam [x=2]
---aadamm (y=2)
Cardam (,x10)
K---Kaaddmmmm (v=20)
242
100
E poch
pooch
(a) no attack
(b) no attack
80
Top Aecuryy
Top3 1.cuurss
ASGO
50-
BASGD with median (B-)))
BASED with ttmmed mean (B-40)
Kardom (y=3)
Kardom (yc8)
A5500
Kardem (ym)
with median
DASSD with tiimmed
Kardam (yaū)
Kandam (ymbb)
Eooch
Eooch
(c) Byzantine workers (RD-attack)
(d) Byzantine workers (NG-attack)
80
80
Top3
ASGD with (B:13)
Kardam (y=10) Kardam (sa14)
(y=10)
(e) 6 Byzantine workers (RD-attack)
(1) 6 Byzantine workers (NG-attack)
Figure 2: Average top-1 test accuracy w.r.t. epochs when there are no Byzantine workers (the first row), 3 Byzantine workers (the second row) and 6 Byzantine workers (the last row), respectively.
Subfigures (c) and (e) are for RD-attack, while Subfigures (d) and (f) for NG-attack.
As many existing works have indicated (Assran et al. 2020 Nokleby et al. 2020), speed-up is also an important aspect of distributed learning methods. In BASGD, different workers can compute gradients concurrently, make each buffer be filled more quickly, and thus speed up the model updating. However, we mainly focus on Byyaanine-resillenn in future work. Besides, heavily delayed workers are considered as Byzantine in the current analysis. We will analyze heavily delayed worker's behavior more finely to obtain better results in future work.
in this work. Speed-up will be thoroughly studied
EXPERIMENT
In this section, we empirically evaluate the performance of BASGD and baselines in both image classification (IC) and natural language processing (NLP) applications. Our experiments are con- ducted on a distributed platform with dockers. Each docker bound an NVIDIA Tesla V100 (32G) NVIDIA Tesla K80 GPU (in NLP). Please note that different GPU cards do not
GPU (in IC) affect the reported metrics in the experiment. We choose 30 dockers as workers in IC, and 8 dockers in NLP. An extra docker is chosen server. All algorithms implemented with PyTorch 1.3.
7

---

Under review as a conference paper at ICLR 2021
Table 1: Filtered ratio of received gradients in Kardam under NG-attack (3 Byzantine workers)
TERM
By FREQUENCY FILTER
BY LIPSCHITZ FILTER
IN TOTAL
LOYAL GRADS (7 3)
10.15% (31202/307530)
40.97% (126000/ /30700))))73
51.12%
BYZANTINE GRADS (7 3)
10.77% (3681/34170)
40.31% (18773/34170)
51.08%
LOYAL GRADS (7 8)
28.28% (86937 06993/330530) /307530)
28.26% (86893/ /307530))
56.53%
BYZANTINE GRADS (7 8)
28.38% (9699/34170)
28.06% (9588/34170)
56.44%
LOYAL GRADS (7 14)
85.13% (261789/ (261789/307530)
3.94% (12117/307530)
89.07%
BYZANTINE GRADS ( = 14)
84.83% (28985/344) /34170)
4.26% (1455/34170)
89.08%
5.1 EXPERIMENTAL SETTING
We compare the performance of different methods under two types of attack: negative gradient attack (NG-attack) and random disturbance attack (RD-attack). Byzantine workers with NG-attack send gNG = - Kkak g to server, where g is the true gradient and hass E R. a parameter. Byzantine workers with RD-attack send ÉRD g + grnd server, where grnd is a random vector sampled from normal distribution (O, | 2 I). Here, Jatk is a parameter and I is an identity matrix. NG-attack typical kind of malicious attack, while RD-attack can be seen an accidental failure with expectation O. Besides, each worker is manually set to have a delay, which is kdel times the computing time. Training set randomly and equally distributed to different workers. We use the average top-1 test accuracy (in IC) or average perplexity (in NLPP) on all workers w.r.t. epochs as final metrics. For BASGD, we use median and trimmed-ment mean as aggregation function.
Because BASGD is an ABL method, SBL methods cannot be directly compared with BASGD, The ABL method Zeno++ either cannot be directly compared with BASGD, because Zeno++ needs to store some instances on server. The number of instances stored on server will affect the performance of Zeno++ (Xie et al. 2020). Hence, we compare BASGD with ASGD and Kardam our experiments. We set dampening function A(T) I+r for Kardam suggested in (Damaskinos et al. 2018
5.2 IMAGE CLASSIFICATION EXPERIMENT
In IC experiment, algorithms are evaluated on CIFAR-10 10 (Kizhevsky et al. 2009) with deep learning model ResNet-20 (He al. 2016). Cross-entropy used as the loss function. We set katk 10 for NG-attack, and aatk = 0.2 for RD-attack. kaet is randomly sampled from truncated standard normal distribution within [0, +oo). As suggested in (He et al. 2016), learning rate 7j is set to 0.1 initially for each algorithm, and multiplied by 0.1 at the 80-th epoch and the 120-th epoch respectively. The weight decay is set to 10-4. We run each algorithm for 160 epochs. Batch size is set to 25.
Firstly, compare the performance of different methods when there Experimental results with median and trmean aggregation functions are illustrated in Figure 2(a) and Figure 2 respectively. ASGD achieves the best performance. BASGD (B 1) and Kardam have similar convergence rate to ASGD, but both sacrifice a little accuracy. Besides, the performance of BASGD gets worse when the buffer number B increases, which is consistent with the theoretical results. Please note that ASGD is a degenerated case of BASGD when B = 1 and Aggr(h;) h Hence, BASGD can achieve the same performance as ASGD when there is failure attack.
Byzantine workers.
Then, for each type of attack, we conduct two experiments in which there are 3 and 6 Byzantine workers, respectively. We respectively set 10 and 15 buffers for BASGD in these two experiments.
For space saving, we only present average top-1 1 test accuracy in Figure 2(c) and Figure 2 (3 Byzantine workers), and Figure 2 and Figure 2() Byzantine workers). Results about training loss are in Appendix [ We can find that BASGD significantly outperforms ASGD and Kardam under both RD-attack (accidental failure) and NG-attack (malicious attack). Under the less harmful RD-attack, although ASGD and Kardam still converge, they both suffer significant loss on accuracy, Under at-attac, both ASGD and Kardam cannot converge, even we have tried different values of assumed Byzantine worker number for Kardam, which is denoted by paper. Hence, both ASGD and Kardam cannot resist malicious attack. On the contrary. BASGD still has relatively good performance under both types of attack.
y in this
8

---

Under review as a conference paper at ICLR 2021
932
130
703
regleis
000
500
ASGD attcc))
BASGD with median (0=3)
493
attacki
BASGD median (B-3)
393
203
AD
200
20 Epoch
35
Epoch
(a) RD-attack
(b) RD-attack (magnified)
.002
900
Logetion of Perolesly
893
201
attecil BBSGD with makkan 18-3)
Perplecly
090
--- ASGD Ino atack)
Kardom Iylll
500
-
BASGG with median (8
403
390
200
100
40
10
23
Epach
Epoch
(c) NG-attack
(d) NG-attack (magnified)
Figure 3: Average perplexity w.r.t epochs with 1 Byzantine worker. Subfigures and (b)
for RD-attack, while Subfigures [c] and (d) for NG-attack. Due to the differences in magnitude of perplexity, y-axes of Subfigures (a) and are in log-scale. In addition, Subfigures (b) and (d)
illustrates that BASGD converges with only a little loss in perplexity compared to the gold standard.
Moreover, we count the ratio of filtered gradients in Kardam, which is shown in Table 1 We can find that in order to filter Byzantine gradients, Kardam also filters approximately equal ratio of loyal gradients. It explains why Kardam performs poorly under malicious attack.
5.3 NATURAL LANGUAGE PROCESSING EXPERIMENT
In NLP experiment, the algorithms are evaluated on the WikiText-2 dataset with LSTM networks. We only use the training set and test set, while the validation set not used in our experiment. For LSTM, we adopt 2 layers with 100 units in each. Word embedding size is set to 100, and sequence length set to 35. Gradient clipping size is set to 0.25. Cross-entropy is used as the loss function. For each algorithm, we run each algorithm for 40 epochs. Initial learning rate is chosen from {1, 2,5, 10, 20), and is divided by 4 every 10 epochs. The best test result is adopted as the final one.
The performance of ASGD under attack is used gold standard. We set katk 10 and aatk = 0.1. One of the eight workers is Byzantine. kdet is randomly sampled from exponential distribution with parameter À 1. Each experiment carried out for times, and the average perplexity is reported in Figure g We can find that BASGD converges under each kind of attack, with only a little loss in perplexity compared to the gold standard (ASGD without attack). On the other hand, ASGD and Kardam both fail, even if we have set the largest (y = 3) for Kardam.
CONCLUSION
In this paper, we propose a novel method called BASGD for asynchronous Byzantine learning. To the best of our knowledge, BASGD is the first ABL method that can resist malicious attack without storing any instances on server. Compared with those methods which need to store instances on server, BASGD takes less risk of privacy leakage. BASGD is proved be convergent, and be able to resist failure or attack. Empirical results show that BASGD significantly outperforms vanilla ASGD and other ABL baselines, when there exists failure attack workers.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent, In Advances in Neural Information Processing Systems, pp. 4613 4623, 2018.
B. M. Assran, A. Aytekin, H. R. Feyzmahdavian, M. Johansson, and M. G. Rabbat. Advances in asynchronous parallel and distributed optimization. Proceedings of the IEEE, 108(11):2013-2031, 2020. doi: 10.1
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little enough: Circumventing defenses for distributed learning. In Advances in Neural Information Processing Systems, pp. 8635-860 05558865,,4 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadeneshelii and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In International Conference Learning Representations, 2019. URL httpp::/
net lttp:///ooommmmddBBddo.- (iccixxxiixx
Peva Blanchard. Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pp. 119-129, 2017.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of the International Conference on Computational Stutistccs, pp. 177-186. Springer, 2010.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1()): 2017.
Georgios Damaskinos, Rachid Guerraoui, Rhicheek Patra, Mahsa Taziki, et al. Asynchronous Byzantine machine learning (the case of SGD). In Proceedings of the International Conference on Machine Learning, pp. 1145-1155 1154, 2018.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthicu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, pp. 1231, 2012.
Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv: 1001110911. 2019.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the International Conference on Machine Learning, pp. 999-1008, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, (20ul):2121-2133 2011.
Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability distributed learning in byzantium. International Conference on Machine Learning, pp. 3521-3530, 2018.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 2545-2555 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference Computer Vision and Patlern Recognition, pp. 770-778, 2016.
Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael Jordan. Communication-efiinn distributed dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 5068-30777 2014.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp. 315-323, 2013.
10

---

Under review as a conference paper at ICLR 2021
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXfv:1112.04497,, 2019..
Jakub Konevený, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv:1610.05492 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Jason D Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed stochastic variance reduced gradient methods by sampling extra data with replacement. The Journal of Machine Learning Research, 18(1)440044446, 2017.
Mu Li, David G Andersen, Alexander J Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. In Advances Neural Information Processing Systems, pp. 19-27, 2014.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu, Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances Neural Information Processing Systems, pp. 5330-5340, 2017.
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method. In Advances in Neural Information Processing Systems, pp. 3059-30090000 3067,,067000 2014.
Chenxin Ma, Virginia Smith, Martin Jaggi, Michael Jordan, Peter Richtárik, and Martin Takác. Adding averaging in distributed primal-dual optimization. In Proceedings of the International Conference on Machine Learning, pp. 1973-1982, 2015.
Matthew Nokleby, Haroon Raja, and Waheed U Bajwa. Scaling-up distributed processing of data streams for machine learning. arXiv preprint arXiv:2005.088: 08854, 2020.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2)::3-113 2017.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(Feb):567-599 2013.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiienn distributed optimization using an approximate newton-type method. In Proceedings of the International Conference on Machine Learning, pp. 1000-1008, 2014.
Weisong Shi, Jie Cao, Quan Zhang, Youhuizi Li, and Lanyu Xu. Edge computing: Vision and challenges. IEEE Internet of Things Journal, 3(5):637-646 2016.
Shizhao Sun, Wei Chen, liang Bian, Xiaoguang Liu, and Tie-Yan Liu. Slim-dp: a multi-agent system for communication-effiieennn distributed deep learning. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 721-729, 2018.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang, Gradient sparsification for communication efficient distributed optimization. In Advances in Neural Information Processing Systems, pp. 1299-1308 2018.
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(0ct):2543-255) 2010.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-basee based fault-tolerance. In Proceedings of the International Conference on Machine Learning, pp. 6893-6901, 2019.
Cong Xie. Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous SGD. In Proceedings of the International Conference Machine Learning, 2020.
11

---

Under review as a conference paper at ICLR 2021
Tianbao Yang. Trading computation for communication: Distributed stochastic dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 629 6079-6372220 2013.
Zhixiong Yang, Arpita Gang, and Waheed U Bajwa. Adversary-resilient distributed and decentralized statistical inference and machine learning: An overview of recent advances under the byzantine threat model. JEEE Signal Processing Magazine, 37(3):144-1555 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robusi distributed learning: Towards optimal statistical rates. In Proceedings of the International Conference on Machine Learning, pp. 5650-5659, 2018.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in byzantine-robust distributed learning. In Proceedings of the International Conference on Machine Learning, pp. 7074-70770 7084, 2019.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 7184-7193, 2019a.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number indepen- dent access of full gradients. In Advances Neural Information Processing Systems, pp. 980-988, 2013.
Ruiliang Zhang and James Kwok. Asynchronous distributed admm for consensus optimization. In Proceedings of the International Conference on Machine Learning, pp. 1701-1709, 2014.
Shen-Yt Yi Zhao, Ru Xiang, Ying-Hao Shi, Peng Gao, and Wu-Jun Li. SCOPE: scalable composite optimization for learning spark. In Proceedings of the Thirty- First AAAI Conference on Artificial Intelligence, pp. 2928 2934. AAAI Press, 2017.
Shen-Yi Yi Zhao, Gong-Duo Zhang, Ming-Wei Li, and Wu-Jun Li. Proximal SCOPE for distributed sparse learning. In Advances in Neural Information Processing Systems, pp. 6551-6560, 2018.
Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Yan Liu. Asynchronous stochastic gradient descent with delay compensation. In Proceedings of the Interna- tional Conference on Machine Learning, pp. 4120-4129, 2017.
Yi Zhou, Yingbin Liang. Yaoliang Yu, Wei Dai, and Eric P Xing. Distributed proximal gradient algorithm for partially asynchronous computer clusters. The Journal of Machine Learning Research, (0(1):733-764 2018
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 2595-2603, 2010.
12

---

Under review as a conference paper at ICLR 2021
Algorithm I Asynchronous SGD (ASGD)
Server:
Initialization: initial parameter w learning rate
Send initial w all workers;
for = 0 to maar-
do
Wait until a new gradient g is received from arbitrary worker k; Execute SGD step: w +- w' 7) g
Send w+1 back to worker_k;
end for
Notify all workers to stop;
Worker k:
(A: (k= 0, 1,
repeat
Wait until receiving the latest parameter from server;
Randomly sample an index from Da;
Compute V f[(; 2:);
Send V (w: 2;) to server;
until receive server's notification stop
A ALGORITHM DETAILS
A.1 ASYNCHRONOUS SGD (ASGD)
One popular asynchronous method to solve the problem in T under the PS framework is ASGD (Dean al. 2012), which is presented in Algorithm
A.2 BUFFERED ASYNCHRONOUS SGD (BASGD)
The details of learning procedure in BASGD is presented in Algorithm
B
PROOF DETAILS
B.1 PROOF OF PROPOSITION 1
Proof. Firstly, we prove coordinate-wise g-trimmed-mean is q-BR. It is not hard to check that trmean satisfies the property (a) in the definition of q-BR, then we prove that it also satisfies property (b).
Without loss of generality, we assume h haj are already in descending order. By definition, Trm(h.g) the average value of My, which is obtained by removing q largest values and smallest values of { Therefore.
hot max {x} Trm(h,,) min {z) h(n-g)5 q)5 =EM;
MM
For any S C [B] with [S] = B q, by Pigeonhole Principle, S includes at least one of byj.-.. 11g+ and includes least of (ma- Therefore,
max(haaj 2 hig+1)i
min S hiin-))- #ES
#E8
Combining these two inequalities, we have:
max (hay) Trm(h.) 2 min min #ES
sES
Thus, coordinate- wise q- t-rimmed-mman is BB By definition, coordinate-wise median can be seen as B -rimmedd-mann and thus is B-1 JBR.
13

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Buffered Asynchronous SGD (BASGD)
Server:
Input: learning rate buffer number B,
aggregation function: Aggr(-);
Initialization: initial parameter w", learning rate
Send initial w to all workers;
Set t <- O;
Set buffer: ha + O, N2 + 0:
repeat
Wait until receiving g from some worker_s;
Choose buffer: 4- mod B;
Ng < No + 1;
h2 < (Ng-1)ba+g.
Nj
if Ng 0 for each E [ then
Aggregate: G' Aggr [h..... hal):
Execute SGD step: w't - w G.; for b to B do
Zero out buffer: h2 + 0, No + 0: end for 1
end if
Send back the latest parameters back to worker-s, no matter whether a SGD step is executed or not.
until stop criterion is satisfied Notify all workers to stop:
Worker k: = 1,..., m repeat
Wait until receiving the latest parameter w from server;
Randomly sample index from Dx;
Compute V ffww;;);
Send V (w; 2,) to server;
until receive server's 's notification to stop
B.2 PROOF OF LEMMA 1
To begin with, we will introduce a lemma to estimate the ordered statistics.
Lemma 3. X1...., XM non-negative, independent and identically distributed (i.id.) random variables sampled from distribution D, and have limited expectation E(X). Denote the K-th largest value in K1,...,MMM as X(K), then E[X(K)) CM. E[X], where
M,
K ==
CM.K
MICK M (K-IJ(M- KMM-))
1< K<K<
Proof. Denote the Probability Density Function (PDF) and Cumulative Density Function (CDF) of D as p(x) and P(x), respectively. Then the PDF of ((K) is:
M!
(x) = (K- 1)!(M KY!" - P(=)) M-x)
Thus.
+o0
E E[X
x (2)))())d
+000
M!
M(x) M-K xp(x)dr [1 P(x))) K-1 ((x))*->P(()M--
(K - 1)!(M K)!
14

---

Under review as a conference paper at ICLR 2021
(4)
+00
M!
(K 11)-1-1MMMM -A) M-K
(M 11 (zp(z)dd
0 (K - 1)M(M - K)!
MI(K - - K [[[]]
KK 1)((M-K)M(M 1141--1)--1
Incquality (a) is derived based on [] ([P))] 2 obtained by the following process:
[K-1] (K-1)R-1((M)) (MM-1MM--000 M-
which is
(M-1)
Let 0(xr) = (1 - -=))KI1a-- I E [0, 1].
Then 8' (x(x (1 2 I[M K) x) (K 1).)
Let ('(xx 0. Solving the equation, we obtain
M-K 0 or
11-1
Also, we have (0) = 0(1) = and 0 k- (K-1) x (-M-K) KYAr
(M 1111
Then have [0.1 0(x) 01 M- M-1 (K (K-1)* 1) (M ( K K) M
(N5 1-
(K-1) -1-1))-110 (M-K) M-X
Thus, [
((P(x)) I
(M-1)2-1
Proposition 3. yB,gr E 24,055555 B 2'
CB-rg-rtl (B (B-r)VB r+
q 1 r+
Proof. By Stirling's approximation, we have:
2 nee <n! ev n e", An E Z..
Therefore,
n! nd S Sevn Vn E
Vmnn-e e "
By definition of CM,
MIKK - -1) (M 1 -
KK
CM.K-
(K 1)!(M - K]I(M - 1)
=M (M- 1K-1)K- (M K) K)M
(M-1)--1 (K 1I!
(M -KK!
k-1
M-
SM e.
[TkK-1)
(M -
MVM-T
2T V(M-K)(K
where the inequality uses Inequality
Case (i). When q.
(B r) -
CB- 2x V(B BB- 9
(B-r) -++
VB- 1 1)(9 r++1
Case (ii). When q, by definition of CM.K, we have:
(B B-rr\B-r+1
C CB-rg-rti = = B -
/B-
In conclusion, when r S 9, we have:
(B (B-r)BB-Tt
CB-rgertl 5
1Ba
15

---

Under review as a conference paper at ICLR 2021
When B and q fixed, the upper bound of CB-r.- will increase when r (number of Byzantine workers) increases. Namely, the upper bound will be larger if there are more Byzantine workers. When B and are fixed, q measures the Byzantine Robust degree of aggregation function Aggr (-)
The factor [B q [) r)]
monotonically decreasing with respect to q, when q < B-1+r
Since r S 9 < 2. the upper bound will decrease when increases. Also, B q decreases when increases. Namely, the upper bound will be smaller if Aggr(-) has stronger q-BR property.
g_
In the worst case (q = r), the upper bound of CB-r.g-r+t is linear to B. Even in the best case (r 0 - D. the denominator is about _ and the upper bound of CB-r.g-++ is linear to v B. Thus, larger B might result larger error. Hence, buffer number is not supposed be too large.
Now we prove Lemma]
Proof.
E EIIG'112 w']
B|| AlgrAg (hi,...,
ha)ll w']
([lgggr(hi,.... ha))) w'].
where Aggr((bi..... hB]); represents the j-th coordinate of the aggregated gradient.
We use Ht to denote the credible buffer index set, which is composed by the index of buffers, where the stored gradients all from loyal workers.
For each b E H-' hy has stored N5 gradients at iteration t: gi,-.., ,8ag, and we have:
N
h N ==1
Then,
hg 2
w*]
=I[[ h,
[bs w w']]1 2 w*] + |B w"1]1²
[I[
(g.
Elg:
w/ w²] +
| N7
Σ g: w*]l
NO
+
|
gi w']ll
N
NØ
1=1
Ng
+
Σ
E gg w*1l1
Ng
(N2))²
Ng Σ
(8)
+ (Ng)²
.
|
w']l1
Ng
(0) 0²
+ +
N
Inequality (a) is derived based on Assumption and the fact that gi mutually uncorrelated. Inequality (b) is derived by the following process:
N
g
w 11
111
E.g.
[[g] w*]
15 ISKPENG
Ng
| g
w 21 +
Σ
w w']l E| w w'll + Eig
16

---

Under review as a conference paper at ICLR 2021
N2.
E gi w w'll + -No - 1) Σ
[g w']l
Ng w'll?
No
Inequality (c) is derived based Assumption
Because there are no more than r Byzantine workers at iteration i, no more than r buffers contain Byzantine gradient. Thus, the credible buffer index set H' has at least (B r) elements. In that H has more than (B - r) elements, we take the indices of the smallest (B q) elements in (hog NEN compose Hy and have (7t) B q.
Note that Aggr(.) is q-BR, and by definition have:
min (haj} S Aggr((hi, hells S max (haj) bENg
DERg
Therefore,
E[Aggr( (0igr((hi.... (h...... hell)l -
max (bg Hw*]. BE
There are (B- -) r) credible buffers, and we choose the smallest (B 9) buffers to compose H. Therefore, for all E Hy. hay is not larger than the (q - + 1)-th largest one in hozee. Let N() be the (q + 1) smallest value in (N%)eE[B) Using Lemma 3 we have:
E Emmax /ww1]
<E| max
{
bEH;
a2 No Hww
< E max
2
bENs
-CB- (D2 + a²
No
Thus,
mmax { [ S CB CB- DD2 o² DEN
G w*1 <
NO0
By Proposition we have:
(BB-q- 1)(g - -r (D2 σ²
(B 12-r)a r-r --1
|||
w < d.
NO0
B.3
PROOF OF LEMMA
2
Proof.
E VF(w') |
w']
= EE[Aggr((h,... hn]) VF(w') w']
-E[Aggr(hh, VF ha VF(w"))) w'],
where the second equation derived based on the Property (b) in the definition of q-BR. For each b H' hy has stored Nţ gradients at iteration t: g1, B1..... BNy. and we have:
N
M
h VF(w")= = No Σ g: - VF(w") = N
1
V((w (w VF(w'))
17

---

Under review as a conference paper at ICLR 2021
where 0 S t
t+ S Tmazs Vk = 1,2,.................. ..b.
Taking expectation on both sides, we have:
E h
VF(w")Il |w']
N
N #f(w"+:20)
-VF(())] /w']
N
fll'/ -//[\\" [w']
N
(0) 1
(B[IIFF(w**) - VF(w")| |w/]
No 1=1
=
25g IIl [w']
+ E (F(W"))] [w'),,
where (a) is derived based Triangle Inequality.
The first part:
E V F w*)) - (F((")) [w']
(8)
L. L. BB|| w ww'll ww!
=L-
IBl1
Σ G [w']
n'=
L BEI| [w/]
L. v |||| /w]2
[||l B|| [w']
K=th
1-1
L CB-ng-rrid (D2 + 02//N(1)
Iimal L.
V VCB-rg--id (D2 + d2/N()).
where (b) is derived based on Assumption 5. (c) is derived based on Lemma and (d) is derived based on L - 1 S Tmaz.
The second part:
BIII f( (. / 2ig II1l [w]]
= =VEIIIV 2;))
(w*+ 42; )11 [w]2
V (w**; )112 [w(]
where (e) is derived based on Assumption 4
By Assumption 2 we have the following estimation for the third part:
VF(W**)]] /w'] E
18

---

Under review as a conference paper at ICLR 2021
Therefore,
E hi
VF(w")ll /w']
N2
1
Tmax LV CB- (D2+ o² o2/N(() +
No
-Tmax v CB-ne-r-id -d (D2 (2*+ +
(4)
Similar to the proof of Lemma
Vj E [d]. we have:
min {hay - VF(w")j} BER
<Aggr( [h1 VF(w").... ..... .......,, hg VF(w'))),
< max (haj BEH)
VF(("),)
where Hj is composed by the indices of the smallest (B - 4) elements in (hos VF(w"), BEEE.
Therefore,
[[[Agr(( [h: VF(w")..... hB VF(w"))) w']ll
[[gggr((h: VF(W"),.......... hn vF(w"))) w"]ll
Bl| E[lAggr((h, FF((') ha (F(w"))))l [w"]
E mmax |/n - VVP("')lll w']
BER
CB BB-rag- 1 r+1 BB[liba - VF(w"),ll ww]]
Cn CB-rg-r+183 BlIlbb F(('')l [w"]
Cn-rg-rt1 (Tmas T.V CD-rg-r+id (D2 + o2/N(0) + + k)
1=1
=C --a----rit r+id- (TmazTiy CD-rg-r4id (D2 + /2/N(9) + x),
(5)
where (f) is derived based on definition of q-BR, (g) is derived based on Lemma 3 and (h) is derived
based on Inequality (4). Combining Equation
3 and Inequality (5 we obtain:
| VF(w') w S CB-rg-rrid dd (Fmar L CB-rg-rrdd (D² (22/NN))
By Proposition 3), we have:
d(B-r)BB-
[ - VF(w") w'lll < V(B - 9 1)(1 r+1
(B (B-rVBBrt+ (D2 OD2+0//N(0)+ +
.(Fmao 1 d
VBB 1B-
19

---

Under review as a conference paper at ICLR 2021
B.4 PROOF OF THEOREM
Proof.
B[F(w'+1) (1) w'| =E FE[F(w' (w' - 17 17. - w
R w') 1
" w']
L 2
w'I+ + T
=F(w') 1
E|ll E [w]]
2
=F(w') VF(WW) w'| + n
Elll 2
[w]
2
=F(w') VF(W VF + T/LL
E | w"]
2
7) VF(w") VF(w') w']
<F(w') - 77 1| "/ B B|||G*||2 w']
+ |/F | VF(ww) w']l,.
where (a) is derived based on Assumption 5
Using Lemma I and Lemma 2 we have:
B[F(w++1) w']
L CB-ra-r-add (D² 0² 02/N(0)
<F(w") n [|VF((")]
2
+ CB CB-r.g-rrid (Tmaw Ly CBB-r-rrrdd (D2 -o))
Also, by Assumption 3 V || S D.
Taking total expectation and combining [[V ||| S D, we have:
B(F(w'+1) SB(F(w')] - 17 B[I || + rf CB CB-ng-rtid (D² + (2/N(()
2
+ 17 CB-r.-r+t Dd Tmaz CB-rg-rtad (D2 + o2/ +o RK).
Let 5 = T T' D2 o2/N( By telescoping, we have:
T-1
Σ
[[ [ [[F(w?]]]
"
1=0
L Cn-rg-riid
+ + TT 2
Σ DD2 + o² /2/N(()
T 1=
+ TTT
D
Note that E 2 and
and let 1 = LITT):
Σ (w
[[[F(W9)- FM] 1
+0 CB-na-rtiDd
00
VT
VT
+0
(Tmaz +0 Dd (
When g = and B = O(r), we have CB CB-rq-rt15 < (B-r)-B-rt 0 ( Thus,
(18-4-11(--41)
VF
L[F(w9)) FF
rdD
DDd
50
+0
+0
T
T
Té - +11
(g (g-r+1)}
20

---

Under review as a conference paper at ICLR 2021
rDdn
r² LDDd Taax
+0
+0
r (
(q - (
B.5 PROOF THEOREM 2
Proof. Let hj be the value of the b-th buffer, if all received loyal gradients were computed based on w'. Note G Aggr(h (hi........ ,h))-
E[F((w ( +1) w²]
=I[[F(w* - 17. G²) w']
(a)
3I[[F(w") n VP(W*) G² + _ 1 w']
=F((') - - w'I n²4 E G w'].
(6)
where (a) derived based on Assumption (5)
Firstly, we estimate the value of E ((W"((")" w*].
Since there Without loss of generality, suppose only the first r buffers may contain Byzantine gradients.
most Byzantine workers, most buffers may contain Byzantine gradients.
Let G syy Aggr(hi..... h,, h +1....... h'g), where h,,...: h, may contain Byzantine gradients and be arbitrary value, and 1,.1...... h's each stores loyal gradients computed based on w'. Thus,
E[VF(w') agn w'] 2 |VF[(')] A
(7)
E| & %ymml || w'1 S (A2)².
(8)
Let = L2 max BB r) < 1.
We claim that
E|||
G G ||
w <
<(2att]
1 + a
_ (A2)2
1-a
and
E G [
++ + 1-a - (A2)²
Now prove it by induction on t.
Step 1. When = 0, all gradients are computed according to w and we have G
GO syn Thus,
|||| G
Go Il 2 w = 0 s { 1/a² +
a +i (A2)²
2
E|| | w = G| 1|2 //] s (A2)² s saa + = a
) (A2)
Step 2. If
G
Gt sy 1|3 w" (5 aa
1
1 (A2)
2
12 || (a
(A2)
1-a
holds for all /' = 0, 1,..., 1 (induction hypothesis). then:
E E|||
- G synl 1|2 w*]
Aggr(h h, h h hg) Aggr(hi,.... hr, h b/ h2))l1 w']
Σ
hb b1ll w']
6=1+1
21

---

Under review as a conference paper at ICLR 2021
B
Σ
VJ(W"; |w]
NO
b=++1
(0)
B
N
E
V - V V/(w"; 2i. )11 [w]]
NO
b
N
E
L 2 || -
w'1l w']l
N
No
LB
r)
- wi]
211
No
LB - r)
B1|
Σ
1| ww1l
1=1
E'=N
(e) 1 (B
N
BI(L-
(x)
|IGH11 1 [
NE
1=
L r)
Nº
1-1
2
(tt - (4)
Σ
(a
T-a (A2)
1=1
8=
Nİ
2/2 LL T)
2 ) (A2)
Σ
[01 (2)
Σ
(a' +
Ng.
T-a a
1'=/2
2
2 211 - r)
(a +
1- ) (A2)²
(1)
2 a
(a
+
1 (A2)²
a
(A2)²,
where (b) is derived based on the definition of stable aggregation function, (c) is derived based on Cauchy's Inequality, (d) is derived based on Assumption 5 (c) is also derived based on Cauchy's s
Inequality, (f) is derived based on induction hypothesis, (g) is derived based on that t t S Tiaax and (h) is derived based that 2nj² L [ r).
Therefore,
E G w*] = syn + (G' G 11 w']
(0)
52 E|| |
_ w"] + 2 B[l[ G 112 w*]
(
22. (A2)² +2 E||| - G sym 1|2 ||]]
(8)
22 (A2)² + (a
+ a
(A2)²
2
2
=(a +1 + 1-a
(A²)
(10)
where (i) is derived based on that ||x + yl < 2| + | Vx. E Rd, (j) is derived by the definition of (A1,42) -fffecctev aggregation function, and (k) is derived based on Inequality (9)
By Incquality 9 and (10). the claimed property also holds for t' = t.
In conclusion, for all 0, 1, I....,T T 1, we have:
1
[||] G Gi 112 w'] S (5 (+1
(A2)
(11)
22

---

Under review as a conference paper at ICLR 2021
and
E|| E|| w'] S (a ++ + 1-a
- -A2)²
(12)
Also,
||||
w Varl | w/| = | w/]. Therefore,
w / w/12 $ a 2
E|||''||
1-a A2.
(13)
We have:
77 EVV w']
= V G sym
w + EVV
GG G w"]
(
2n: (I w A1) - -G w/]
21 VF
|I |E[(G' G G'gg)) w']l
(*)
IV w
D. D. [
G² sgm)
w'll
.. [/ A1 17. D ++1 1 - A2
(14)
where (1) is derived based on the definition of (A1, Aefeefectivve aggregation function, (m) is derived by Assumption 3 and (n) is derived based on Inequality (II)
Combining Inequalities (6
and taking total expectation, we have:
B[F(w++])] <E(F( 7y E (IIIFF(('))1
+ + Ai + D altl + a
1-a Az L
+
2 +-2 (A2)².
2
1-a
By telescoping, we have:
2
1
(IVF(("))))((((()) E[F(w")]]
"
TL
I-a (A2)²
a
TTA + TTD
0
A2.
2
1
Divide both sides of the equation by r/T, and let 0
1
VT.
ET- T-1
T
[F(w") [[F(WW])]
1
- (A2) +A+ 1
2
1/T
2
1-
V
A2
VL(F(W") - F*]
VI(ga
a 1-a) (A2)²
3 3 2(1-a) DA2-
A + at
VT
VT
Note that a 27,² T? Tmam
(B-r)= =0
Lrr (/
finally we have:
E VE 12
VL [F((") -F
VI(AA))(11 +
50
+0
T
VT
VT
+ +
a DA2)
+ Ai
4 [F(") - -F*
L (B (B- - (B-r)+
+
T
T
23

---

Under review as a conference paper at ICLR 2021
La (A2)2
L (A2)) Tmaz (B -r) r)
+ +0
A1.
T
T
Specailly, when B = Or)), we have:
El BIIIV w ||
L (F(w") FT)
D
00
+0
T
T
L (Ag)2
L (A2)
"aax
+
+0
+ AA.
T
T
B.6 PROOF OF PROPOSITION
Proof. Under the condition that V'w E R E[I -VF(')] D w"], we have:
F T Gt syn w']
E F )T [VF(W') + (G' (gag VF(w')) w']
V w )11 + E//F((W") (G'' syn VF(w")) w']l
2 V wx) )112 (VVF("))))) I|| [[]| syn
VF(W")]I | w']
N [F - D
|VF(w)] -D?
Combining with the property (i) of (A,, A2), effecctcvv aggregation function, we have A s D2.
24

---

Under review as a conference paper at ICLR 2021
C MORE EXPERIMENTAL RESULTS
Figure Figure and Figure illustrate the average training loss w.r.t. epochs when there are no Byzantine workers, 3 Byzantine workers and 6 Byzantine workers. Please note that in Figure 5 and Figure 6 some curves do not appear, because the value of loss function is extremely large or even exceeds the range of floating-poin point numbers, due to the Byzantine attack. ? is the prper-paraeeter about the assumed number of Byzantine workers Kardam. The experimental results about training loss give further support to the experimental summary in Section 5
- BD WR redion BBe)
BASG with tomsue 18-0, ond)
BAGEO WiT median
BASS wilh 18-15, mrees 18-al,, cold) Evviin bulld)
BASCD wi medion (B-20)
- KarSam Inl)
KarSam
Fpech
Foothh
Figure 4: Average training loss w.r.t. epochs when there are no Byzantine workers. The aggregation function in BASGD is set to be median (left) and trimmed-mean (right), respectively.
AVAS 10500 ar' cinmed mesncRett
X150 RESE dilonne mans (i-EE
Figure 5: Average training loss w.r.t. epochs in face of random disturbance attack (left) and negative gradient attack (right), when the number of Byzantine workers r = 3. Some curves do not appear in the figure, because the value of loss function is extremely large or even exceeds the range of floating-pon numbers.
Dr ASGO
ASGD
SASCO Ats birmad ERArEED
SACCD anD baBwnd B411
Lardam 1-40))
Cater 1-42))
Figure 6: Average training loss w.r.t. epochs in face of random disturbance attack (left) and negative gradient attack (right), when the number of Byzantine workers r = 6. Some curves do not appear in the figure, because the value of loss function is extremely large even exceeds the range of floating-pon point numbers.
25


Reviews:
[{"review_id": "xMO55oHz00h", "reviewer": "AnonReviewer2", "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": "The paper proposes a practical asynchronous stochastic gradient descent for Byzantine distributed learning where some of transmitted gradients are likely to be replaced by arbitrary vectors. Specifically, the server temporarily stores gradients on multiple  (namely $B$) buffers and performs a proper robust aggregation to compute a more robust from them. When $B = 1$,  BASGD is reduced to ASGD. They also conduct experiments to show the performance of BASGD. \n\nThe paper is well written and easy to follow. All proof seems correct though I didn’t check very carefully. However, there are some issues:\n1. Compared to other asynchronous SGD methods, one advantage of BASGD is it doesn’t have the need of storing any samples on the server. However, I didn’t understand why such property is meaningful. The authors declare that it helps BASGD take less risk of privacy leakage. Noting the server store gradients on buffers and gradients may leak privacy [1]. If a third party can have access to the buffers, privacy leak can still happen. BASGD didn’t use techniques like differential privacy, so it seems ill-founded to say “BASGD takes less risk of privacy leakage”.\n2. In my opinion, Theorem 1 doesn’t guarantee that BASGD is able to find a stationary point of $F$ since the extra constant variance will not vanish when $T$ goes infinity. By contrast, ZENO++, a robust fully asynchronous SGD, could ensure convergence to a stationary point. This strikes me that the theorem is quite weak. Theorem 2 has the same problem.\n3. It makes me feel strange to assume the gradient is biased (Assumption 2). For example, If we want to minimize $F(w)$ but we use stochastic gradients computed from another $\\tilde{F}(w)$ (that is totally different from $F(w)$), could we still guarantee the algorithm converges to the stationary point of $F(w)$? I am afraid the answer is NO. This thought experiment not only shows using biased gradients doesn’t help convergence but also shows Theorem 1 doesn’t guarantee the convergence of BASGD.\n4. Some parts of the algorithm are not well explored. For example, how the performance of BASGD changes when we vary the value of $q$ or the value of $B$. The experiment didn’t explore these aspects. Besides, Noting that the number of buffers $B$ is quite important for good performance, however, there is no investigation on how $B$ affects convergence and no suggestion on how to choose a proper $B$. In experiments, $B$ is set in advance for no reason.\n\n[1] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, pages 14747–14756, 2019.\n\n---------\nI have read the authors' response. The authors have addressed most of my concerns, but I still think the motivation is a little farfetched. Considering the paper indeed explorees some aspects (in theories and experiments) of the use of buffers in asynchronous Byzantine Learning, I will improve my point to 5.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "l7PAhFUPDa6", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary\n\nThis work proposes a method for Byzantine learning in a parameter-server setting using asynchronous updates, and without the need for storing training instances on the master node. They provide theoretical guarantees and some experiments on small-scale tasks.\n\n---\n\n#### Originality\n\nSynchronous methods for byzantine learning enable one to compare communicated gradients with one another in order to filter out byzantine workers. When updates are asynchronous, such a procedure cannot be employed because gradients are not necessarily communicated to the master node at the same time. Previous work on Asynchronous byzantine learning stores training instances on the master node to alleviate this issue. This work proposes instead to use gradient buffers on the server to eliminate the need to store training instances on the master node; this is the main selling point of the algorithm, and deems the method sufficiently novel in my opinion.\n\nHowever, the motivation for avoiding storing instances on the master node is not well fleshed out in my opinion. Though the applications to Federated Learning are mentioned, updates are typically performed locally on-device and *parameters* are communicated back to the master, and therefore this method is not applicable to that setting. It is unclear exactly what the privacy concerns are, but I would suggest reworking the motivation exposition a little.\n\n---\n\n#### Significance and Quality\n\nThe method is actually quite nice and intuitive. The significance relates back to improving the motivation, but the method may be of sufficient interest to the community.\n\n*On the theory*:\n\nNote that the bounded gradient assumption is very strong! when combined with the L-smoothness assumption, it implies a convergent subsequence a priori! In short, it is like assuming ahead of time that the algorithm convergence.\n\n$N^t_b$ is used in the main paper (e.g., page 5), but is only defined in the appendix on page 14. I would suggest including a one sentence description that these are the number of gradients stored in buffer $b$ at iteration $t$.\n\nUnder asynchrony or non-iid data, theorem 1 does not guarantee convergence to a stationary point… even with a diminishing step-size. Moreover, even with iid data and fully synchronicity and a diminishing step-size, the algorithm still does not converge to a stationary point due to the extra variance term on the r.h.s. I do not mean to criticize the results; only to point out this fact. Moreover, these bounds are somewhat vacuous due to the presence of the non-degrading $D$ gradient boundedness term on the r.h.s of Theorem 1 in the variance term. With L-smoothness and the assumption of $D$-bounded gradients, as I mentioned above, all iterates of any objective (regardless of the algorithm), will remain with a ball of a stationary point, the size of which is proportional to $D$. (To the authors credit, I have seen similar bounds in previous byzantine learning methods).\n\nFor Theorem 2, as I understand it, the $\\alpha^{1/2}$ term actually has a $\\mathcal{O}(1/\\sqrt{T})$ dependence, so unless i’m missing something, why not remove the constant $\\alpha$ and substitute in a quantity that decays with $1/\\sqrt{T}$, and state the theorem results for all $T \\geq$ some threshold (to satisfy the current $\\alpha < 1$ constraint). this reformulation will make it clearer that the only lingering (non-decaying factor) is $A_1$, which is due to gradient bias.\n\nMore generally, I am curious if there is a way to correct for the convergence errors and improve the results to guarantee convergence to a stationary point (and not some neighborhood thereof), given that a $\\frac{1}{\\sqrt{T}}$ step-size is employed. \n\n---\n\n#### Clarity\n\nWork is sufficiently clear. One minor point is that Asynchronous SGD is missing a reference (common references for this method include Dean et al., or Bengio et al.)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-iwnXc6c6GC", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review: This paper proposes BASGD which uses buffers to perform asynchronous Byzantine learning. In each SGD step, all workers compute gradients and send them to the server where their ad buffer is updated. When all of the buffers are updated, the server performs an model update. When a worker send a gradient to the server, it also pulls the latest model and compute the gradient on it no matter the server update the model or not. The main contribution in this paper is to introduce a new approach to do asynchronous Byzantine learning without storing training samples on the server like zeno++.\n\n=======================================================\n\nPros:\n\n+ The problem of Byzantine learning in the asynchronous environment is interesting and has rarely been studied, especially under the assumption that the server has no training data.\n\n+ The idea of using buffer on the server to achieve (partial) asynchrony is interesting.\n\n+ This paper provides extensive experiments to demonstrate its effectiveness.\n\n=======================================================\n\nConcerns:\n\n- BASGD is not fully asynchronous as the paper claims to be. The server only updates the model when all of the buffers are non-zero. That is, the whole system will be slowed down by the slowest buffer. The remaining good workers, at the time of waiting, are computing the gradients on the same model weight. In this case, BASGD resembles SBL with larger batch size but at the cost of tolerating less Byzantine workers.\n\n- This paper does not explicitly state how to choose the number of buffers $B$ in order to achieve both asynchrony and Byzantine-robustness. In page 3, there are \"BASGD introduces $B$ buffers ($0<B\\le m$) on server\". However, when $B$ is small, there is no robustness; when $B$ is large, there is no asynchrony.\n\n- The Definition 1, 4, 5, are not common in Byzantine robust learning. Are these definitions used only to make the proof easier?\n\n- The results in the theorems are not clearly presented. The $O(1/T)$ in Theorem 1 and 2 does not reflect how $B$, $q$ influence the convergence rate.\n\n=======================================================\n\nMinor comments:\n\n- The negative gradient attack and random disturbance attack are very easy to defend. It would be better to choose some more challenging attacks.\n\n- It is better to improve the writing in section 4 for better readability.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-fOfnXQ_GqG", "reviewer": "AnonReviewer4", "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": "This paper studies distributed learning in the presence of Byzantine workers in the asynchronous setting. Its main contributions include generalization of the existing literature on Byzantine fault tolerance in distributed learning to incorporate the case of asynchronous learning. This generalization involves an algorithm, convergence analysis for the algorithm, and experimental results. While the results presented in the paper appear to be correct, I would like the authors to focus on the following points during their revision.\n\n1. In Section 2.2, the definition of Byzantine worker, it is not clear why the worker is being indexed with $k_t$? What is the meaning of $t$ in this usage of the worker index?\n2. The writing of the paper could use some proofreading. Some of the sentences are hard to parse on first read, while some other sentences suffer from grammatical errors. As a specific example, I could not understand the meaning of \"Only when all buffers have got changed since the last SGD step, ...\" in Section 3.1 until I reread the main parts of the paper.\n3. Related to the previous point, the discussion in Section 3.1 in general is hard to parse because of the notation and could benefit from revision. Also, $m$ in this section is undefined up to this point in time and it is not clear what it means.\n4. A number of aggregation functions have been proposed in prior works (see e.g. Adversary-resilient distributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model). Do all of these previous aggregation functions satisfy the characterization of Section 3.2? It would be helpful to have some discussion of this.\n5. Theorem 1 and Theorem 2 leave something to be desired. Since the task is to engage in distributed learning, one expects to see some sort of speedup from the fact that $n$ workers are being used to divide up the work. However this speed-up does not seem to be coming up in the analysis or the discussion. In the absence of such a speed-up, it is not clear if the authors are really providing guarantees that are useful for distributed learning.\n6. It would be useful to discuss the impact of heavily delayed workers on the algorithm. What if the sum of the number of heavily delayed workers and Byzantine workers exceeds $r$?\n7. The plots corresponding to the experimental results are too small and should be modified to have bigger font and size.\n\n***Post-discussion period comments***\nThe authors have done an adequate job of responding to my queries and have also revised the paper in light of the comments of all the reviewers. While the paper could always be improved, I believe it is now above the threshold of acceptance and it should be accepted into the program, if possible. I am raising my score for this paper in light of the discussion and the revised paper.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present BASGD and asynchronous version of SGD that attempts to be robust against byzantine failures/attacks. 
The papers is overall well written and clearly presents the results. Some novelty is present as there have been limited work in asynchronous algorithms for byzantine ML. 

However, there have been several concerns raised by the reviewers, on which I agree, and they have not been fully addressed:
1) the tradeoff between asynchrony and robustness, as BASGD cannot handle the case of a buffer being straggler, which limits some of the novelty in this work
2) issues with the definition of privacy leakage has not been fully addressed
3) some reviewers mentioned the theoretical results being of limited importance, but arguably this is true for other related work in this area. Perhaps a general criticism is valid as to what is the operational value of the proposed guarantees. That is convergence does not exclude a model that has undesirable properties, eg has bad prediction accuracy for a small subset of tasks.
4) Finally, the motivation of the system model of the paper ( eg storing gradients as opposed to instances) paper is of unclear practical relevance, as was raised by multiple reviewers. 

Overall the consensus was that the paper does have merits, however, some of the most major concerns were not properly addressed. This paper can potentially be improved for a future venue.


Decision: Reject