Byzantine-Resilient Non-Convex Stochastic Gradient Descent
Authors: Zeyuan Allen-Zhu
Faeze Ebrahimianghazani
Jerry Li
Dan Alistarh
Venue: ICLR 2021 Poster (2021)
Keywords: distributed machine learning
distributed deep learning
robust deep learning
non-convex optimization
Byzantine resilience

Abstract: We study adversary-resilient stochastic distributed optimization, in which $m$ machines can independently compute stochastic gradients, and cooperate to jointly optimize over their local objective functions. However, an $\alpha$-fraction of the machines are Byzantine, in that they may behave in arbitrary, adversarial ways. We consider a variant of this procedure in the challenging non-convex case. Our main result is a new algorithm SafeguardSGD, which can provably escape saddle points and find approximate local minima of the non-convex objective. The algorithm is based on a new concentration filtering technique, and its sample and time complexity bounds match the best known theoretical bounds in the stochastic, distributed setting when no Byzantine machines are present. 

Our algorithm is very practical: it improves upon the performance of all prior methods when training deep neural networks, it is relatively lightweight, and it is the first method to withstand two recently-proposed Byzantine attacks. 

Published as a conference paper at ICLR 2021
BYZANTINE-RESILIEN NON-CONVEX STOCHASTIC GRADIENT DESCENT"
Zeyuan Allen-Zhuj Faeze Ebrahimian; Jerry Li Dan Alistarh
ABSTRACT
We study adversary-resilient stochastic distributed optimization, in which m machines can independently compute stochastic gradients, and cooperate jointly optimize over their local objective functions. However, an a-fraction of the machines are Byzantine. in that they may behave in arbitrary, adversarial ways. We consider a variant of this procedure in the challenging non-convex case. Our main result is a new algorithm SafeguardSGD which can provably escape saddle points and find approximate local minima of the non-convex objective. The algorithm based on a new concentration filtering technique, and its sample and time complexity bounds match the best known theoretical bounds in the stochastic, distributed setting when no Byzantine machines are present.
Our algorithm is very practical: it improves upon the performance of all prior methods when training deep neural networks, is relatively lightweight, and it is the first method to withstand two recently-propose, Byzantine attacks.
INTRODUCTION
Motivated by the pervasiveness of large-scale distributed machine learning, there has recently been significant interest in providing distributed optimization algorithms with strong fault-tolerance guarantees. In this context, the strongest, most stringent fault model is that of Byzantine faults (Lamport et al., 1982): given m machines, each having access to private data, at most an a fraction of the machines can behave in arbitrary, possibly adversarial ways, with the goal of breaking or slowing down the algorithm. Although extremely harsh, this fault model is the "gold standard" in distributed computing (Lynch, 1996, Lamport et al. 1982; Castro et al. 1999), as algorithms proven to be correct in this setting are guaranteed to converge under arbitrary system behaviour.
A setting of particular interest in this context has been that of distributed stochastic optimization. Here, the task to minimize some stochastic function [(x) [a-D[[a(xr)) over distribution D, where (+) can be viewed as the loss function for sample 8 ~ D. We assume there are m machines (workers) and an honest master, and a 1/2 fraction of the workers may be Byzantine. In each iteration f. each worker has access to a version of the global iterate Zt, which is maintained by the master. The worker can independently sample
DD compute (are), and then synchronously send this stochastic gradient to the master. The master aggregates the workers' messages, and sends an updated iterate xz-1 to all the workers. Eventually, the master has to output an approximate minimizer of f. Clearly, the above description only applies to honest workers; Byzantine workers may deviate arbitrarily and return adversarial "gradient" vectors to the master in every iteration.
This distributed framework is quite general and well studied. One of the first references in this setting studied distributed PCA and regression (Feng et al., 2014). Other early approaches (Blanchard et al., 2017| Chen al., 2017; Su & Vaidya 2016a b) Xie et al., 201 8a) relied on defining generalizations of the geometric median. These approaches can withstand but can have relatively high local computational cost (mm2d)) (Blanchard et al. 2017, Chen et al., 2017), where m is the number of nodes and d is the problem dimension, and usually have sub- optimal sample and iteration complexitics.
to half of the nodes being malicious,
Follow-up work resolved this last issue when the objective f(+) is convex, leading to tight sample
'The full and future editions of this paper can be found on
www./rt//////ooooooo//..../eeaee abs /2012 14368
I Microsofft Research Redmond, wttpruaacssil..i...com
# University of Waterloo, fae 2eceeb75@gmaa com 8 Microsoft Research Redmond,
IST Austria, dan. .anaa al i starhe st.sst.s. at

---

Published as a conference paper at ICLR 2021
complexity bounds. Specifically, Yin et al. (2018) provided bounds for gradient descent-type algorithms, and showed that the bounds are tight when the dimension is constant. Alistarh et al. (2018) provided stochastic gradient descent (SGD) type algorithm and showed that its sample and time complexities are asymptotically optimal even when the dimension is large.
Non-convex Byzintine-resilient stochastic optimization. In this paper, we focus on the more challenging non-convex setting, and shoot for the strong goal of finding approximate local minima nutshell, our main result the following. Fix d to denote (a.k.a. second-order critical points). _d + R be Lipschitz smooth and second-order smooth. the dimension, and let the objective We have m worker machines, each having access to unbiased, bounded estimators of the gradient of f. Given an initial point To, the SafeguardSGD algorithm ensures that, even if at most a 1/2 fraction of the machines are Byzantine, after
T Ō= (aa + )) d(s(zo)-min (x)))
parallel iterations,
ga
for at least a constant fraction of the indices I E [T]. the following hold:
[V)(( < 8 and [=x) 2 -Vol. If the goal is simply [+)(l I e, then T = Ō (a2 + ) ((to))-mim((=))) iterations suffice. Here, the Ô notation serves to hide logarithmic factors for readability. We spell out these factors in the detailed analysis.
g²
When < 1/ym, our sample complexity (= mI') matches the best known result in the non- Byzantine case (Jin et al. 2019) without additional assumptions, and enjoys linear parallel speed- up: with m workers of which < / are Byzantine, the parallel speedup is (2(m)
For a E [1//m, 1/2), our parallel time complexity is Ō(a²) times that needed when no parallelism is used. This still gives parallel speedup. This a factor appears in convex Byzantine distributed optimization, where it is tight (Yin et al.) 2018 Alistarh et al. 2018).
The Lipschitz and second-order smoothness assumptions are the minimal assumptions needed to derive convergence rates for finding second-order critical points (Jin et al. 2019).
Comparison with prior bounds. The closest known bounds are by Yin et al. (2019), who derived three gradient descent-type of algorithms (based on median, mean, and iterative filtering) to find a weaker type of approximate local minima. Since it relies on full gradients, their algorithm is arguably less practical, and their time complexities are generally higher than ours (see Section 2.1).
Other prior works consider weaker goal: to find approximate stationary points || [x)]]] S E only: Bulusu et al. (2020) additionally assumed there guaranteed good (i.e. con-Byzantine) worker known by the master, Xie et al. (2018b) gave practical algorithm when the Byzantine attackers have no information about the loss function or its gradient, Yang et al. (2019); Xie et al. (2018a); Blanchard et al. (2017) derived eventual convergence without explicit complexity bound, and the non-convex result obtained in Yin et al. (2018) is subsumed by Yin et al. (2019), discussed above.
Our algorithm and techniques. The structure of our algorithm is deceptively simple. The master node keeps track of the sum of gradients produced by each worker across time. It labels (allegedly) good workers as those whose sum of gradients "concentrate" well with respect to a surrogate of the median vector, and labels bad workers otherwise. Once worker is labelled bad, it is removed from consideration forever. The master then performs the vanilla SGD, by moving the negative direction of the average gradients produced by those workers currently labelled as good.
We call our algorithm Saf S since it behaves like having a safe guard to filter away bad workers. Its processing overhead at the master is (md)), negligible compared standard SGD.
As the astute reader may have guessed, the key non-trivial technical ingredient is to identify the right quantity to check for concentration, and make it compatible with the task of non-convex optimization. In particular, we manage to construct such quantities so that (1) good Byz-nizae workers never get mislabelled as bad ones; (2) Byzantine workers may be labelled as good ones (which is inevitable) but when they do, the convergence rates not impacted significantly; and (3) the notion does not require additional assumptions or running time overhead.
The idea of using concentration (for each worker across time) filter out Byzantine machines
By parallel speedup mean the reduction in wall-clock time due to sampling gradients in parallel among the m nodes. In each time step, the algorithm generates m new gradients, although some may be comupted.
2

---

Published as a conference paper at ICLR 2021
traces back to the convex setting (Alistarh et al., 2018). However, the quantities used in (Alistarh et al. 2018) to check for concentration are necessarily different from this paper, and our analysis is completely new, as deriving non-convex rates is known to be much more delicate and challenging. Recently, Bulusu et al. (2020) used similar concentration filters to Alistarh et al. (2018) in the non- convex setting, but under stronger assumptions, and for the simpler task of finding stationary points.
Many other algorithms do not rely on concentration filters. In each iteration, they ask each worker to compute a batch of stochastic gradients, and then use coordinate-wiss median or mean over the batch average (e.g. Yin et al. (2018; 2019); Yang et al. (2019)) iterative filtering (e.g. Su & Xu (2018); Yin et al. (2019)) by the master to derive a "robust mean." " These works fundamentally rely on each iteration to caleulate of full gradient descent. Such algorithms can introduce higher sample and time complexities (see Section 2), are less practical than stochastic gradient schemes, require additional restrictions on the resilience factor ar e.g. a < 1/4 (Su & Xu 2018), and, critically, have been shown to be vulnerable to recent attacks (Baruch al. 2019, Xie et a 2020).
almost precise full gradient, that they can apply a surrogate
Attack resilience and experimental validation. There is growing literature on customized attacks against Byziintne-resillennt algorithms, showing that many defenses can be entirely cireumvented in real-world scenarios (Baruch et al., 2019; Xie al., 2020). Our algorithm is provably correct against these attacks, a fact we also validate experimentally. We implemented SafeguardSGD to examine its practical performance against a range of prior works (Xie et al., 201 Blanchard et al., 2017; Chen et al. 2017, Yin et al., 2018; 2019), and against recent attacks on the distributed task of training deep neural networks. Our experiments show that Saf dafeguad generally outperforms previous methods in convergence speed and final accuracy, sometimes by wide accuracy margin. This is true not only against known Byzantine attacks, but also against attack variants we fine-crafted to specifically slow down our algorithm, and against transient node failures.
2 STATEMENT OF OUR THEORETICAL RESULT
We denote by || - || the Euclidean norm and [n] == {1, (1.2.....n)) n]. Given symmetric matrices A, B, let || ||2 denote the spectral norm of A. We use to denote Loewner ordering, i.e. A > B if
A- B is positive semi-definite. We denote by Amin (A) the minimum eigenvalue of matrix A.
We consider arbitrary d' d-dimensional non-convex functions f: Rd - R satisfying the following:
f(x) is L-Lipschitz smooth: meaning [[v - vf(i)] < L||x y/ for any I, 3/ E Rd.
f(x)) is Tn--second-order smooth: [|V² 22 2 S L2 ||x y/ for any 2;, E RR4;
For notational simplicity of the proofs, we assume L, = L2 V = 1.2 Note that we have also assumed the domain of f is the entire space Rd. If instead there a compact domain X' C Rdd then one use projected SGD and re-derive similar results of this paper. We choose to present our result in the simplest setting to convey our main idcas.
Byzantine non-convex stochastic distributed optimization. We let m be the number of worker machines and assume at most an a fraction of them are Byzantine for a E [0, 2). We denote by good C [m]] the set of good (i.e. non-Byzantine) machines, and the algorithm does not know good.
Assumption 2.1. In each iteration t, the algorithm (on the master) is allowed to specify a point æt and query m machines. Each machine E [m]] gives back a vector V1, E Rd satisfying
Iff E good, the stochastic gradient Ve,; satisfies E[V,,, (2,)) and [[V - Veall S V.T
Ifi E [m]] \ good, then Vt,; can be arbitrary (w.l.o.g we assume [ - Ve,ill S V)
Remark 2.2. For each and i good, the vector V,,, can be adversarially chosen and may depend
In the literature of convergence analysis for non-convex optimization, the final complexity bounds naturally and polynomially depend on these parameters L, Lz, V. and the way the dependence goes is typically unique (Allen-Zht 2018a bj Fang al. 2018, Jin et al. 2019). This is why it suffices to ignore their appearance and only compare the polynomial dependence on E and
'One can instead assume Pr[||V ((x) V..IIl > t] < 2 exp((t? /2v²) and the results of this paper continue to hold up logarithmic factors. To present the simplest theory, do not include that version in this paper. We refer interested readers to Jin al. (2019) for how to deal with such probabilistic assumption (when there is no Byzantine worker).
"This requirement || (xx)) S V is without loss of generality" hecause it is trivial for the algorithm catch had machines if they output V., more than 2 away from the majorities.
3

---

Published as a conference paper at ICLR 2021
Algorithm SafeguardSGD perturbed SGD with double safe guard
Input: point xp RRd rate > 0, lengths 7 2 Ti 2 To 1, threshold $1 Io > 0;
1: good, [m]:
2: for f 0 to do
3: last, + max E [t] t is multiple of Ti }:
4: lasto t ta tu E [t] to is a multiple To
5:
for each good, do
6:
receive V,, E Rdd from machine i; Vx. and B; + Ex=slatto lgood [j E good, {i E good, |B Bill S Tol > m/2
7:
A; Ek=last, [godg_]
V
8:
Amed < A where good, is any machine s.t.
|| A,ll 51 > m/2
9:
Bmed + B, where E good, is any machine s.t.
10:
good,+1 + {ie good, ||A; Amedl || S 2 A BB Beed || S 25o}
11:
T++1 = 17 ( + Igood,| Ziggood, Ves);
1
Gaussian noise & ~ N/O,
on (Veslestse(m) In particular, the Byzantine machines can even collude during an iteration.
2.1 OUR ALGORITHM AND THEOREM
Our algorithm is based on arguably the simplest possible method for achieving this goal, (perturbed) stochastic gradient descent (SGD) (Ge al. 2015). Our techniques more broadly apply more complicated methods (e.g. at least to Allen-Zhu (2018a b)), but we choose to analyze the simplest variant of SGD, since it is the most widely applied method in modern non-convex machine learning.
As illustrated in Algorithm 1, in each iteration 0, I,..., [' good machines good, S [m]. We begin with good, = [m]] and start to detect malicious machines and remove them from the set. We choose learning rate O, and perform the SGD update 1 F++1 22 & 7) /good_ Eiegood Vt,i
1, maintain set of (allegedly)
where &e ~ ~O, I² is random Gaussian perturbation that is added for theoretical purpose.
For each machine E [m]) we keep track of the history of its stochastic gradients up to two windows. Namely, A; < Ex=tase, |good,,| and B; < Ex=tosto [good, for windows sizes To S Ti < T. We compare among remaining machines in good,, and kick out those ones whose A, or B, deviate "more than usual" to construct good,41- Conceptually, we view these two as safe guards.
V..i
Va,i
Our theory makes sure that, when the "window sizes" and the thresholds for "more than usual" are defined properly, then good, shall always include good, and the algorithm shall proceed to find approximate local minima. Formally, we have (letting the Ô notion to hide polylogarithmic factors)
Theorem 2.3. Let C3 = =
Suppose we choose 2² = (Ca),, 7 Ō( To = 6(5))
T = 0 (1) To = @(VTo), and I = =O(VT)) then after
T = ( (f(ao) Melld (a² 11
iterations, with high probability. for at least constant fraction of the indices &. [T], they satisfy
[[ S and v² -
Remark 2.4. If one only wishes achieve significantly simpler goal finding first-order critical points [=(x)) < & - the analysis becomes much easier (see Section 3.1). In particular, having one safe guard without perturbation (i.e. / 0) suffices, and the iteration complexity reduces to = Ō f(z)))mmin f(w) (a² + 2)). Bulusu et al. (2020) achieves this easier goal but requires an 24
additional assumption: there is guaranteed good worker known by the master.
Our contribution. We reiterate our theoretical contributions from three perspectives. 1) When 1/ 1/mm, algorithm requires m.T Ō (f(zo) f(z))d stochastic gradient computations. 24
This matches the best known result (Jin et al. 2019) under our minimal assumptions of the non-
convex objective. (There exist other works in the stochastic setting that break the e- barrier
4

---

Published as a conference paper at ICLR 2021
and get rid of the dimension dependence d under stronger assumptions. | 2) When a 1/ym, our algorithm enjoys linear parallel speed-up: the parallel time complexity reduces by factor of (mm) When a E [1/ym, 1/2), our parallel time complexity is Ō(a²) times that needed when no parallelism used, still giving noticeable speedup. The a² factor also appeared in convex Byzantine distributed optimization (and is known to be tight there) (Yin et al. 2018, Alistarh et al., 2018).
Comparison to (Yin et al., 2019). Yin et al. (2019) derived three gradient descent-type algorithms to find points with weaker (and less standard) guarantee: [[)] - and (+)( > I Despite practical differences (namely, gradient descent may be less favorable comparing to stochastic gradient descent especially in deep learning applications), the parallel time complexities derived from their result are also generally larger than ours.
Their paper focuses bounding the number of sampled stochastic functions, number of stochastic gradient evaluations like we do. When translated to our language, each of the workers in their setting needs to evaluate 7 stochastic gradients, where (I) = Ō de vd if using coordinate-wiss median, (2) T Ō + g+m
opposed to the
mm ++)
d if using trimmed mean, and (3)
T T + if using iterative filtering. The complexities (1) and (2) are larger than ours (also with a weaker guarantee); the complexity (3) seems incomparable to ours, but when translating to the more standard (e, v guarantee, becomes T = Ō ad + g.m worth noting that (3) requires
d² ) so is also larger than ours. It is
1/4 cannot withstand half of the machines being Byzantine.
Resilience against practical attacks. Our algorithm's 's filtering is based upon tracking B; (resp- A,). the stochastic gradients of each machine averaged over a window of To (resp. Tí) iterations. This is a departure from previous defenses, most of which are history-less, and enables us to be provably Byzantine-resillent against ofate-of-the-art attacks (Baruch et al., 2019; Xie et al., 2020).
In Baruch et al. (2019), Byzantine workers collude to shift the gradient mean by factor 3 times the standard deviation of the (true stochastic) gradient, while staying within population variance. They noticed B can be quite large especially in neural network training. Their attack circumvent existing defenses because those defense algorithms are "historyless", while their attack is statistically indistinguishable from an honest execution in any single iteration. However, our algorithm can provably defend against this attack since it has memory: Byzantine workers following their strategy will progressively diverge from the (honest) "median" Bmed (by an amount proportional to (2(T) in T iterations as opposed to VT), and be marked as malicious by our algorithm. (See Figure 2(a). In Xie et al. (2020). Byzantine workers deviate in the negative direction of the gradient. However, to avoid being caught by our algorithm, the maximum "magnitude" of this attack has to stay within our thresholds. We implemented both attacks and showed our algorithm's 's robustness experimentally.
Finally, we note that prior "historyless" schemes, such as Krum or median-based schemes, could be thought of as providing stronger guarantees, as they in theory allow Byzantine nodes to change IDs during the computation: such schemes only require an upper bound on the number of Byzantine agents in each round. However, the attack of Baruch et al. (2019) essentially shows that all such schemes are vulnerable to variance attacks, and that such attacks are eminently plausible in practice. Thus, this suggests that the use of historical information, which requires that Byzantine nodes cannot change their IDs during the execution, may be necessary for Byzantine resilience.
Tolerating transient failures and node ID relabeling. Our algorithm can also withstand transient node failures and some degrees of ID) relabeling, by resetting the set of good nodes good, to include all nodes every Ti steps. The algorithm then proceeds as usual. The key observation behind this relaxation is the fact that our analysis only requires that the attack conditions hold inside the current window. (Please see the Theorem B.I for details.) We validate this experimentally in Section 5
3 WARMUP: SINGLE SAFE GUARD
As warmup, let us first analyze the behavior of perturbed SGD with single safe guard. Consider Algorithm 2, where we start with point Wo, set good, 2 good, and perform T steps of perturbed SGD. (We use the w. sequence instead of the x, sequence to emphasize that we are in Algorithm 2)
Worrs such as AAllenZZhu 2018a Lei et al. 2017 Tripuraneni et al. 2017; Zhu 2018b Fang et al. 2018 Nguyen et al. 2017) require f(x) = F (T) where each fzr) is second-order smooth and/or L Lipschitz smooth. This requirement may be too strong for certain practical applications.
5

---

Published as a conference paper at ICLR 2021
Algorithm 2 Perturbed SGD with single safe guard (for analysis purpose only)
Input: point wp E Rdd set good, 2 good, rate yj > 0, length 7 1, threshold $ 1: for < 0 to T - do
2: for each E good, do
3: receive V, E R2 from machine i;
4:
B₂ 4 Σ VEL;
ggood
5: Beedd <- B where E good, is any machine s.t. [i E good; | - BBl - $ > m/2.
6: good, ++1 f {i E good, |B; - Bmedll S 2
7: W1+1 We 17 E + good, EiEgood, Ve.):
Gaussian noise & N((0
Definition 3.1. We make the following definition simplify notations: let E; + where
good, Evegood (Vi,i V (w())
A good,| Eiegood, /good (V vf(w))
Therefore, we can re-write the SGD update as W641 = Wt (V](w::+ +x,)
The following lemma is fairly immediate prove:
Lemma 3.2 (single safe guard). In Algorithm 2, suppose we choose I = ToTlog((6mI))
Then, with probability at least p/4, for every o,...,T-
good, 2 good.
|,,11 I O log(T/p)
and 100 + o,-1 5 ( [log(T/p)
|Aill2 < a² and D + .... + A.-1 < 1og"Tlog(mII//
(V)(m)), S Vf
O(v//oo(T/p))) -
I1&.1 O(v2dlog(T/pp) 1l
11 < single (w))] 11111 p/4.
We call this probabilistic event Event Singl (wo) and Pr Event
(The third property above is ensured by our choice of and the use of safe guard, and the rest of the properties follow from simple martingale concentration arguments. Details are in Appeendix A.
3.1 CORE TECHNICAL LEMMA 1: OBJECTIVE DECREASE
Our first main technical lemma is the following:
Lemma 3.3. Suppose we choose T as in Lemma 3.2, Denote by C1 = /p) and C2
a log mT + log(T/p), Suppose 1) S 0.01 min(1, (1, Cz T= 100,(1+VC2) and we start from we and apply Algorithm 2 Under event Event single (wo), it satisfies
[(wp) - ((WT) 2 0.7m) E (IV - 1 O(C2 + (C2) OCC VC2))
Lemma 3.3 says after T steps of perturbed SGD, the objective value decreases by, up some small additive error and up to logarithmic factors, f(w)) f(wr) 2 0.7n ET= (IVV (w:))l
n/2)). This immediately implies, if we choose R C then by repeating this analysis for
- +1/m) iterations, can find approximate critical point with [+)( S
Proof sketch of Lemma 3.3 The full proof is in Appendix A.2 but we illustrate the main idea and difficulties below. After simple manipulations, it is not hard derive that
fwo)) - (wr) 2 0.9n ΣT- 1 (IIV - n) + n ETD (w)(),
remainder
where recall that E, = oe o.+41 A. When there are no Byzantine machines, we have E[E,] = E[a, so the remainder terms must be small by martingale concentration. Therefore, the main technical difficulty arises to deal with those Byzantine machines. who can adversarially design their V. (even by collusion) to negatively correlate with V (w:)) to "maximally destroy" the above inequality.

---

Published as a conference paper at ICLR 2021
Our main idea is to use second-order smoothness to write fwz) = ((y)) To illustrate our idea, let us ignore the constant vector and assume that the Hessian is the identity: that is, imagine as if V fw,)) se wt Wi- Using w, Wp Cket E + fr. we immediately have -VVS(m)), E.) - ( wo, Ex) Exce E.)
(ER,
(3.1)
For the first partial sum Ex<t E, in (3.1), is easy to bound its magnitude using our safeguard. 2 so we can apply Lemma 3.2 For the
Indeed, we have 1. E,g E,) s - || second partial sum Ee ExcelEE. Ei), can apply the concentration Proposition below.
Proposition 3.4. Fix the dimension parameter d 2 1. Suppose .......TT--I. E Rd are i.i.d. drawn from N0, I), and that . -1 are arbilrary vectors in R. Here, each vector D. with == 1,...; can depend on Eo..... E1-1 but not on
Er- Suppose that these vectors T - 1. Then, with probability at least p. satisfy 1 + + Aell < for every? t .....,
E (Eo + &1-1, Ai) S 5O(v AdVIIllog(1
3.2 CORE TECHIICALL LEMMA 2: RANDOMNESS COUPLING
Our next technical lemma studies that, if run Algorithm 2 from point wo that the Hessian (²)(w)) has a eigenvalue which less than - (think of wo as a saddle point), then with good probability, after sufficiently many iterations, the sequence W1, u2,-..., , WTT WT shall escape from we to distance at least Rt for some parameter R 2J 6. To prove this, motivated by Jin et al. (2017), we study two executions of Algorithm 2 where their randomness are coupled. We then argue that at least one of them has to escape from Wo. For any vector v, let [o]: denote the i-th coordinate of e.
Suppose we choose T as in Lemma 3.2) and C1, C2 as in Lemma 3.3) Suppose wo E Rd satisfies A (V²s(wo)) = -ô for some 8 Z O. Without loss of generality let e, be the eigenvector of ( with smallest eigenvalue. Consider now two executions of Algorithm 2 both starting from wî- = w = Wp. and suppose their randomness {52] h and {Eh Je are coupled so that [ -[3]] but [57]: [ i >> 1. In words, the randomness is the same orthogonal to
Lemma 3.5.
e, but along e,, the two have opposite signs. Now, suppose we perform T = 0 no log RÉ4 steps
qu²
of perturbed SGD from wî, w respectively using Algorithm 2, Suppose
R O( VCJ VCTTogggeeee (p)) and v² 2 (C log H²,) qp
Then, under events Event I|uq woll > R or lmul- woll > for some t [T'
and Eventiincee (wb), with probability at least 0.98, either
Proof details in Appendix A.4, The main proof difficulty is to analyze noisy version of the power method, where the noise comes from (1) Gaussian perturbation (which is the good noise), (2) stochastic gradients (which has zero mean), and (3) Byzantine workers (which can be adversarial).
4 FROM WARMUP TO FINAL THEOREM WITH DOUBLE SAFE GUARDS
At a high level, Lemma 3.3) ensures that if we keep encountering points with large gradient [V then the objective should sufficiently decrease; in contrast, Lemma 3.5 says that if we keep encountering points with negative Hessian directions (i.e., Amin (V2 fww)) < -ō), then the points must move lot (i.e., by more than R in T iterations, which can also lead to sufficient objective decrease, see Lemma B.4). Therefore, at a high level, when the two lemmas are combined, they tell that we must not encounter points with [x)())] being large, Amin (V²)(()) being very negative, for too many iterations. Therefore, the algorithm can find approximate local minima.
The reason we need two safe guards, is because the number of rounds T for Lemma 3.3 and Lemma 3.5 differ by a factor. We need two safe guards with different window sizes to ensure the two lemmas simultancously hold. We encourage the reader to examine the full analysis in Appendix
EXPERIMENTAL VALIDATION
We evaluate the convergence of SafeguardSGD to examine its practical performance against prior works. We perform the non-convex task of training a residual nenwork ResNer-20 (He et al.) 2016) on the CIFAR-10/100 datasets (Krizhevsky et al. 2014). More details are given in Appendix C.
7

---

Published as a conference paper at ICLR 2021
350
(a) variance attack
(b) sign-flipping attack
(c) label-flippigg attack
100
spacks
spacks
(d) delayed-gradient attack
(c)
safeguard(x0.6) attack
(f) safeguard(x0.7) attack
Figure I: Convergence comparison (CIFAR-16) 10 test accuracy) under different attacks. (In Appendix C.2 one can find additional CIFAR- 100 experiments, more discussions, and bigger plots.)
We instantiate m = 10 workers and one master node executing aata-parallel SGD for I 140 passes (i.e. epochs) over the training dataset. The results for higher number of workers and epochs are similar, and therefore omitted. We compare against Geometric Median (Chen et al., 2017). Coordinate- wise Median (Yin al., 2018, 2019), Krum (Blanchard al.) 2017), and Zeno (Xie al. 2018b). Overall, our experimental setup is very similar to Zeno (Xie et al. 2018b) but with additional attacks.
We implemented the approach of Yang et al. (2019), but found very sensitive to hyper- hypee-parameter values and were unable to make it converge across all attacks even after significant tuning of its y parameter. We also implemented the convex algorithm of Alistarh et al. (2018), and executed in our non-convex setting. We found their algorithm be easily attacked our ResNet training tasks. There exists a simple attack, described in Appendix C.4 which causes their algorithm to either mislabel most good workers Byzantine, diverge, or converge very poor solutions. This is not surprising, since their algorithm designed for, and only guaranteed to work in, the convex setting.
To make the comparison stronger, when implementing SafeguardSGD we have chosen fixed window sizes To epoch and Ti = 6 epochs across all experiments, and adopted an automated process to select To, 5, Determining these thresholds requires being able to pre-run the task on an honest worker. We have also implemented single safeguard variant of (SafeguardSGD with window size = epochs.
Attacks. We a 0.4, which means that there are 4 Byzantine workers. (This exceeds the fault-tolerance of Krum, and so we also tested Krum with only 3 Byzantine workers.)
LABEL-FLIPPING ATTACK: each Byzantine worker computes its gradient based on the cross- entropy loss with flipped labels: for CIFAR-10, label / E (O..... 9} is flipped to 9 6
DELAYED-GRADIENT ATTACK: each Byzantine worker sends an old gradient to master. In our experiments, the delay is of D 1000 iterations.
al.) 2019): Byzantine workers measure the mean and the standard-deviation of gradients at each round, and collude to move the mean by the largest value which still operates within population variance. (For our parameter settings, this is 0.3 times the standard deviation. We discuss results for additional parameter values in the Appendix.)
VARIANCE ATTACK (Baruch
SIGN-FLIPPING ATTACK: each Byzantine worker sends the negative gradient the master.
SAFEGUARD ATTACK: each Byzantine workers sends a negative but re-scaled gradient to the master. We use re-scale factors 0.6 and 0.7 in our experiments. The re-scale factor 0.6 avoids triggering the safe-gun safe-guard conditions at the master, and the re-scale factor 0.7 occasionally triggers the safe-guard conditions. This attack is an instantiation of the inner product attack (Xie et al., 2020), customized specifically to maximally affect our Saf SafeguardSGD algorithm.
Main experimental results. The ideal test accuracy is 91.7%. which corresponds to applying SGD using only the stochastic gradients from the honest workers. Figure 1 compares the performances
8

---

Published as a conference paper at ICLR 2021
100
Comparison Statiso Values
-00
140
badraadk)
60
220
220
140
spocts
(a) [BB Breall between good node (blue), and bad node (red) which pretends be honest and then starts to apply the variance attack.
(h) Convergence for our safeguard algorithms under the variance attack, after periodically resetting the set of good nodes.
Figure
in test accuracy. Below we summarize our main findings for the experiments, and we defer detailed discussions (and additional experiments for CIFAR-100) to Appendix C.
SafeguardSDD generally outperforms all the previous methods in test accuracy. The test accuracy difference can be "90% vs. < 40%" between our algorithm and the best prior work. The variance attack is indeed very strong, in that it severely affects the accuracy of all prior works (test accuracy < 35%). This because thesese defenses are "historyless." " By contrast, our algorithm not only provably but also empirically defends against it.
Our safeguard attack (especially with re-scale factor 0.7) is as strong as the variance attack, and even stronger on the CIFAR- 100 dataset; please see the results in Appendix C.2.5
The label-flipping attack is rather weak: although some defenses, such as Zeno, did not determine which of the workers are malicious, they still converge well under this attack.
The sign-flipping and delayed-gradien attacks are moderate: the best prior works can achieve accuracy 60% 70%. It is worth noting that the sign-flipping attack can already nullify the Zeno defence (test accuracy 20%). The issue seems to be that it can be very hard for Zeno to use relatively few samples to determine if the gradient direction is flipped negative.
SafeguardSGD can easily catch all the bad workers under sigre-lipping and variance attacks, and thus leads to gives ideal performance. It cannot catch any bad worker for lubel-fipping and delayed-ge graddent attacks, but there is no performance loss anyways if we use such bad gradicnts.
The safeguard attacks, designed to maximally impact the performance of our SafeguurdSSns can indeed affect our performance. Specifically, under re-scale factor 0.6, the test accuracy drops from 91.7% to 89.3% because Saf SaaeggudSSGD cannot catch any bad worker; however, under re- scale factor 0.7, the test accuracy no longer drops because Saf SafeguardSGD can begin to catch some bad workers (it can catch between O and 4 bad workers depending on the randomness.)
In most cases, the single-safeguard algorithm is close to double-safeguard, except for the safeguard(x0.7) attack, in which using double-safeguard one can more easily catch bad workers. (This is more apparent in the CIFAR- 100 experiment, see Appendix C.2.5)
We conclude that SafeguardSGD can be practical, and outperforms previous approaches.
deeper dive: how the algorithm works. Let us explain the inner workings of our algorithm in the context of a "delayed" attack, where the Byzantine nodes collude to execute attack only after a specific, given point in the execution (in this case, the first half-epoch). Figure 2(a) presents the results from the perspective of the value of |BB B registered at the master server, for two nodes, an honest one, and a Byzantine one. The value of [BB - Bmeall increases for all the nodes (at a rate of roughly vi at step f); but, once the attack starts, the statistic for the Byzantine node grows linearly in leading to fast detection.
Transient attacks and node ID relabeling. Finally. in Figure 2(b) we analyze the behaviour of our algorithm when periodically (every 3 epochs for single safeguard and 6 epochs for double safeguard) resets the set of good nodes to include all nodes, restarting the detection process from scratch. Our theoretical result still applies after this relaxation. This relaxation has two benefits. First, it benefits from bad workers that under transient failures (e.g., the node fails for 10 epochs but resumes to work correctly after a while), and thus benefits from the data stored on this worker. Second, it defend against certain degree of node ID relabeling: it supports the case when good and bad workers exchange their IDs every 6 epochs. In Figure 2(b), we see even under the (very strong) variance attack, relaxed safeguard maintains good performance.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
and D. A. were supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleMI.).
REFERENCES
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances Neural Information Processing Systems, pp.
2018.
Zeyuan Alu. Natasha 2: Faster Non-Convex Optimization Than SGD. In NeurlPS, 2018a. Full version available at htttp: / /ww.iaiivvv/// www.oo/g//aa//..oooo/ooo/...///a 708. 7
Zeyuan Allen-Zhu. How To Make the Gradients Small Stochastically. In NewrlPS, 2018b. Full version available at
abs/ 110111111111 02982
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep
learning. arXiv preprint Xrv: 10/90, 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Advances in Neural Information Processing Systems, pp. 8635-8645, 2019.
Peva Blanchard, EI Mahdi El Mhamdi, Rachid Guerraoui. and Julien Stainer. Machine learning with
adversaries: Byzantine tolerant gradient descent. In NIPS, pp. 118-128, 2017.
Saikiran Bulusu, Prashant Khanduri, Pranay Sharma, and Pramod K Varshney. On distributed stochastic gradient descent for nonconvex functions in the presence of byzantines. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3137-3141. IEEE, 2020.
Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, 1999.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1(2):-25,, 2017.
Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689 1999699,220 2018.
Jiashi Feng, Huan Xu, and Shie Mannor. Distributed robust learning. arXiv preprint arXiv: 1409.5937, 2014. Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. In Proceedings of the 28th Annual Conference on Learning Theory, COLT 2015, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778 2016. Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances Neural Information Processing Systems, pp. 125-136, 2019.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pp. 1724- 1732. JMLRR org, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham Kakade, and Michael I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv preprint (902.::900.045)) 1, 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint a1X1::1610. 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10/100 dataset. [oroont..... edu/ www.:eru..ieeeeeeeeee lxriz/ciiaaa htmm 55, 2014.
https::/ htnp:://www.co cs.
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382-401, 1982.
Lihua Lei. Cheng Ju. Jianbo Chen, and Michael Jordan. Nonconvex Finite-Sum Optimization Via SCSG Methods, In NIPS, 2017.
Nancy A Lynch. Distributed algorithms. Elsevier, 1996.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In ICLR. arXiv preprint wcXiv:1706.0600 2018.
Lam M Nguyen, Jie Liu, Katya Seheinberg, and Martin Takás. Sarah: novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on
10

---

Published as a conference paper at ICLR 2021
Machine Learning- Volume 70, pp. 2613-2621. JMLR. org, 2017.
Iosif Pinelis. Optimum bounds distributions of martingales banach spaces. The Annals of Probability. pp. 1679-1706, 1994.
Lili Su and Nitin Н Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms.
In PODC, pp. 425-434. ACM, 2016a.
Lili Su and Nitin H Vaidya. Defending non-bayesian learning against adversarial attacks. 2016b.
Lili Su and Jiaming Xu. Sccuring distributed machine learning in high dimensions. arXiv preprint arXiv: 1014,0 2018.
Nilesh Tripuraneni, Mitchell Stem, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochastic Cubic
Regularization for Fast Nonconvex Optimization. ArXiv e-prints, 0bs/1711.02883 November 2017.
Cong Xie. Oluwasanmi Koyejo, and Indranil Gupta. Generalized Byzantine tolerran SGD. arXiv preprint arXiv:1802.101I3 2018a.
Cong Xic, Oluwasanmi Koyejo, and Indranil Gupta. Zeno: Byzantine-suspicionn stochastic gradient descent. arXiv preprint 1805 10032, 2018b.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerat SGD by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270. PMLR, 2020.
Haibo Yang. Xin Zhang. Minghong Fang, and Liu. Byzantine-resilien stochastic gradient descent for distributed Icarning: A lipschitz-inspreed coordinate-wis median approach.
arXiv preprint
arXiv:1909.044: 2019.
Dong Yin. Yudong Chen, Kanna Ramchandran, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. arXiv preprint arXiv:1803.01 000188003.19,,,. 2018.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett Defending against saddle point attack in byzantine-roke robuust distributed learning. International Conference on Machine Learning, pp. 7074-7084, 2019.

---

Published as a conference paper at ICLR 2021
APPENDIX
A MISSING PROOFS FOR SECTION
A.1 PROOF OF LEMMA 3.2
Recall the following, useful inequality.
Lemma A.1 (Pinelis' 1994 inequality (Pinelis 1994)), Let X Xx ER' be random process satisfying
E[X,|XI,... X,-1] 0 and [x]] S M. Then, Pr [[]X] + Xxl1* 2l)g(2/8) s 8.
Lemma 3.2 is in fact direct corollary of the following claim, whose proof is quite classical. Denote by C = log( 16mT/p)) Denote by
Vo. good
VI-1
and _ Vi(wn)
(S(W--)
good
good,l
good
Recall at iteration 1. Algorithm 2 computes {B ..... B well as some B = B where is any
machine in good,-1 such that at least hall of [mn]] satisfies 1B0)) - B || 8vIC/m.
Claim A.2. Ler C = log( (16mm//p) Then, with probability ar least 1 p/4, we have (a) for all good and [7]. | B s 4VIC/m
(b) for all E [T'. each E good a valid choice for B B(C)
(c) for all E good and E [2]] [|B(() B & 16VIC/m and [B B S 12v10/m
(d) for all good and [T], we also have i E good
(e) Σ Eigood (B - s O(yllog(T/))/
Proof of Claim A.2 We prove by induction. Suppose the statements hold for t and we now move to f.
(a) For each E
good, note V. = V. and V/,,, V.ll S Let X, V..-V: so that
[good,
[Xell S
igood,1 (1-a)m <
1
We can thus apply Lemma A.1 to the Xx and then take a union
bound over all i good. Thus, with probability at least 1 2r we have || - B 4v10/m for all i good. The result follows from a further union bound over E [T].
(b) Claim A.2a implies for every i, E good we have || 1 z 8VIC/m. Therefore each i E good is valid choice for setting ( = B(()
(c) This is a consequence of the previous items and the definition of (((t) med*
(d) This is consequence of the previous item.
(e) We can apply Lemma A.I with (X1, X2. Xe/good] V Ve.c-V,(ww) lesod- It holds with [goody]
probability at least 1 87 that Eiegodd (B!0) B!u S 0 (1//
Proof Lemma 3.2,
The property good, 2 good is from Claim A.2d
The property [|or_]? S O log(T/n) is by standard concentration inequalities for sums of bounded random vectors.
The property 0o ... 11- 11 < O Tlog(T/p) from Claim A.2e.
The property A I a obvious as we have at most a fraction of the bad machines.
The bound on ||An + ... + 11 can be derived as follows. For every i E [m]] \ good, let / be the last iteration satisfies good,- Then, by the triangle inequality.
( (
B(*1
On the other hand, t. E good, implies | (09 |l < 16/tC/m by the algorithm; combining this with [| Bffi < 12v/C /m, and summing over all such bad machines finishes the proof.
The final two properties follow from standard facts about Gaussian random vectors.
12

---

Published as a conference paper at ICLR 2021
A.2 PROOF OF LEMMA 3.3
Proof of 3.3. Using the Lipschitz smoothness of f(-), we have
[wi)) - ((w++1) 2 (VS(we), we w+-1) 2 I - wr+1ll
[ + ( 1 - w1+11 + vr -
We first show:
+ | - Wetill = - (1V || 1
T-1
Σ [Vf(m))11 o(voa) < 0.05m Σ (V O(Civ'n)
(W) m
The first follows since (a + b + c)* < 3(0² 0² + c²) for any a, R, and the second follows from
Lemma 3.2 Combining them, and also using that || < O(C2). I|E.||* s O(dv and n S 0.01, we have
T-1
Σ (IV 0()(2)) + Σ fw.)). E.) O Cr(ndd + 7))
(um) - f(WT) 2 0.9g)
(A.1)
For the inner product on the right hand of (A.1) we have that
T-1T-1
(W))), E.) /
Vl(.)) Σ
(V())) - v)(W)).
(A.2)
For the first term
we have
1
(V()))
E
11
[ )l1
ΣΣ |
1=0
+ O(1)
Σ Σ=
$ 0.1n
|V [Vw,2))
T
[V[(2))] + 0(02))
0.1nm
where the last inequality follows from Lemma 3.2 For the second term we have
T-1 T-1
2 f(wo)(w: ua)); Ex)
T T
wall + lw,, woll - | (1|w
y=0
Using |wm- woll S ||ue woll + ||00 we one can derive
T
(1 - woll + 11,86 - wo 1)) O(VC
t=
m
| (O(C22)
[Vf(wo)+ (..(:)))+...V( Vf(wi-)++ 1..1 + O(VCz)
1m/
$ O(VC2n
13

---

Published as a conference paper at ICLR 2021
As for Q.
9-1
Σ (wm)) - ww 3i) - t=0
Σ V (w
- wy), Ei) m.),
v
(wn)
- my),
1=
For the first term (and the second term is analogous), we have
- v' -w.))
7
V (Vn)(((V [ +...--1111 + &
+... 4...........11 (.)))
+ +.... G..))
119
[Vv + V[(W))))), E.) +
Σ 1=
v
(... -....,
5 dPPTC VTC+)+
"
Sep +...+++BB ((W)
7 v2 f(wb) + (...) + -rr-))
2
T-2
Sn. On VTC2) + Σ
| + + + + 1r-
+
Above, inequality @ uses | ..... E.|l < ((VTTT2) for C2 = a² log wT [og(T/p) (see Lemma 3.2) and a delicate application Azuma's inequality Inequality @ uses Young's inequality and Lemma 3.2
we state at the end of this subsection (see Proposition 3.4);
Putting this back to the formula of Q we have
OO Σ -
0.1m
Finally, putting & and 2 back to and putting and back to and and (A.I). we have
f(wo) - -[(rr) 2 0.8q
[ O O T
[[(.))]
C2 O 212 VCn - C. o ( }
together with (00g(1+v005)
and 0.01 min 2 }. we have
f(wo) - f(wr) 2 0.7m
C2 + hh
T-1
0.7n
C2 -l |1T:::/:...cc.ooooo...7777770170 vC2))
(-d
T-1
0.7m
-
14

---

Published as a conference paper at ICLR 2021
A.3 PROOF OF PROPOSITION 3.4
Proposition 3.4, Fix the dimension parameter d 2 1. Suppose Eo...., Er-1 E IPs are i.i.d. drawn from
N( 1), and that A....., A1-1 arbitrary vectors in R.. Here, each vector D. with t 1...., 1 can
depend on Eo. ... Ee-1 but Ety.... - Suppose that these vectors satisfy || + D 1| _ for every t
Then, with probability at least - p.
Σ Enn (Co + +... E Ao)
S Ol log(T/p)
Proof of Proposition 3.4. Using the identity formule
ΣET (50 +
A.) Ei== &t)
EEET (.) -EE 16, A + +
have
Ai} $ Ei= Et
E de || + EE (5t, A +
<0 CT'S log (Tpp) + Σ (Ee, ....+AA))
where the last inequality uses llEo +.... 2-l O(vdT (1))) with probability least p/2.
Furthermore, we note that & independent of Eo. .......r E A..... A. and [ 0. Therefore, letting = 0: furthermore, with probability at least - p/2. it
S. = (Ee, A +... + Ac). we have E[St Eo...., [1-1] satisfies S.l S O(Vdd (Tg(T/))) for every Finally, by Azuma's inequality, we have
E
An) s O(ydT' (log///
A.4 PROOF OF LEMMA 3.5
Let us denote by rs [5 11 and we know ~ N =²- We can write
Proof of Lemma 3.5,
wi+1 w/+1 mree + wi w -VVf(w)) - VV((w)) n - )
Using the second-order smoothness, we have
f((w)) -Vf()) = ['' 4 f² w/ + -(w? ())) w
= V2 (wo) (w) - wh:) + 0,
for some vector ||0.1| < maxillu0 will, | w ||} 1| will Therefore, we have
w b = ryrer + (I -I- V (wo)) (w? - w/) nn? - = 0t)
Now, giving 1/o vo = 0, imagine two sequences
Mh+1 = er + (T - 2) the and
144 = mrre + (1 - v (wo) v. (3 - = 0,) = wi w
We will inductively prove ||x// 11 S Ilvell- On one hand, it is easy to see that the is zero except in the
first coordinate, in which it bchaves as Gaussian with zero mean and variance E1=b (1 + 75) 2k. 2²0²
θ (1+n6) r)²v²) By Gaussian tail bounds, we know that
with probability at least 0.99, it satisfies |[ S O (2 for every 1
(vFu(1+n6))"
* with probability least 0.99, it satisfies || 2 1000
v3
In the rest of the proof, condition this event happens. We prove towards contradiction by assuming |lw]- wgll < R and |m will I for all E [T).
We will inductively prove that 1| v.l1 S 2006
(1)()- We calculate the difference
3.
-- V ((²)) ( = +.)
Let g
1i- V then we can inner-product the above equation by vector g. which gives 1t w
11 3,
0,
We thank an anonymous reviewer on openreview who pointed out this simpler proof to us.
15

---

Published as a conference paper at ICLR 2021
11 (2] -, -I- ((m)) R. O VntCiul + ,665 + ) ) 770)
R.O(
v8
3 E, (T - イフ パー (woo) 9) ORrrT VryCi
v11 + n8))))
vō
where the inequality ① uses ||01| - R |لحل| - R (Ilv:ll + 11vi - 35 1|1I- ((oo))
9/1
(1 + 76)5-1-1, 1-:-111,,00 and the inductive assumption. Iet us call M (I - 7 f (wo)) and focus on
1ル²² ((oo))
9)
+
+
Σ = + , M 9- M
< 1
|alel Σ
- + 31| 11M-~~~1 g- M 2 gll
< OVVTC,
|16|| +
1-1
9 M 22 اll
(using Lemma 3.2)
$ O(VTC2 (1 n6)
Together, we have
11 - S TCT) (1 (1) + ORRIT VnCi v8 u(1 + n6)')
Under assumption, we have 1 Flll 2000
V and therefore , 2 || - | 1 v5
176(1+ ). Thus, within T iterations, we have | >
this gives contradiction.
2000
B FINAL:: DOUBLE SAFE GUARD
final Algorithm which is our perturbed SGD algorithm with safeguards. The safeguard algorithm naturally divides itself into epochs, each consisting of Ti iterations. We will demonstrate that within most epochs, we make good progress. Thus, consider some iterate Zm7; for some m < T T/T,. Our goal will be to argue that we make good function value progress by iterate I(m+1)) and that we do not settle into any saddle points. To slightly simplify notation, let wh ImT, and let the sequence of iterates be wo: .... uT, 1, that uT, I(m++1)7 -1- For completeness' sake we rewrite this Algorithm I
We now come
Algorithm 3 Perturbed SGD with double safe guard (for analysis purpose)
Input: wi E IRd, set good, 2 good, rate > 0, lengths Ti 2 To 2 1, threshold 3₃ > To > 0:
1: for t t Ti do
2: last +- max to E [t] to is multiple of To}
3: for each E good, do
4: receive Vt, E Rd from machine i;
5: A 2 lgood. and B; + -- [good
Va.i
Vi.i
6: Amed + A; where i good, is any machine s.t. { E good, ||A, - A:ll S 51
> m/2
7: Biedd < B; where i E good, is any machine s.t. {j E good, [Bj B
& 5n
> m/2
8:
good,41 1 + (i E good, ||A, Amedl S 25, A [ Bmedl
|l < <2.,}
9: Wi+1 Wt 1 {1 + gooo Σ Diggood, Ves):
Our main result is the following theorem.
Theorem B.I. Let Ca = a² 1 m- Suppose we pick parameters p. E (0. 1), S Ō )( v ē(C.).
To - Ti = 6( 2 Tb. Ti = =O(TT), and To = @(vTo). Then, starting from wo.
16

---

Published as a conference paper at ICLR 2021
(a) with probability least p have
f(wo) - f(wr)) 2 0.7n) Σ [[V Ö((Ca))))))))))))))))))))
(b) As long as l/we woll 2 foror some E f1,2,.... Ti for R = =66) s 2. then with probability at least 1 p we have then
f(wo) - f(wr,)) 2 0.5n
Σ (-o(rCad)) + -2(80)
(c) if Amini (ini (V2 $ -6, we also have with probability at least 0.45,
f(wo) - ((wrr) 2 0.5n
(-o(1Cad)) + +2(00)
B. WHY THEBOREM B. IMPLIES THEOREM 2.3
Using the parameter choice things:
O Cigd
from Theorem 2.3 we know Ö(nO3d) S 0.1g². We claim two
For at least 90% of the epochs, they must satisfy (denoting by wp and uy, the beginning and ending points of this epoch)
f(wo) - f(wn) - 20 (100 - min f(x) S S
T/T,
The last inequality our choice of I and θ(VE).
The reason for this is by way of contradiction. Suppose for at least 10% of the epochs it satisfies f(wo)) [wrr) ) > 20 [(mp) [(mo)-min -in f(xe) then, for the remainder of the epochs, they must at least satisfy
777,
- 0.1s Summing over all the epochs, shall obtain f(xo) f(oT) > f(zo) min (xx) but this gives contradiction.
f(wo) [ww,)
For at least 40% of the epochs, they must satisfy the three properties from Theorem B.1 particular, at least 30% the epochs, they must satisfy both. Since e-166 11.6
small that
Ti-1
1.5 2 (wo) - ((wr,) ) 2 0.5z)
Σ
(-o(rCsdi) + 0((8)) 2 ā(6") 0.05y/ii²
would give a contradiction (for instance, one can choose 5 to be slightly larger than ve by some log factors), this means, for those 30% of the epochs, they must satisfy:
2.5 2 0.7m Σ -1 ( [1 0.16²)
0=
||., wel < / for every / = 2. and
V2 f(w)) ž 81.
The latter two properties together implies V ((n) 2 - T for every t. = 1,2,..., Ti (by the second-order smoothness). The first property implies for least 90% of the iterations in this epach, they must satisfy This finishes the proof Theorem 2.3
[[V[())| <
B.2 PROOF OF THEOREM B.1
We first have the following lemma
Lemma B.2 (double safe guard). In Algorithm 3 suppose
8/Ti log(16mTi//g /p) and To
every 1 forevery 8 / To log (6mmmi/mm) Then, with probability least 2/2.
......11
good, 2 good.
||o.1| < O (og(T:/2) ), || < a². 11E.1P S O(v (lg(///)))))) m
|| + ... .... 1 2| < O log(T ), Flast + + oz-1ll² < O To log(T)/))
||Ao +... Ac-1l < O(a² log(mTi/p)) and |iast + ... + A. < O(a"" To log(mTi/p))
[|Eu +.... 0 2dT log(Ti/p)) and [| +... + E 11 < O lTg(Ti /p)).
We call this probabilistic event Eventdyyale (wo) and Pr[Eventhyjbe
double
doubio (wo)] 1 p/2.
The proof direct corollary of Lemma 3.2 by combining events Event sinst (wo)). Eventginat (wo).
17

---

Published as a conference paper at ICLR 2021
single (wer,) ) and on. The next lemma simple corollary by repeatedly applying Lemma 3.3 It proves Theorem B.la
Event single (wr.). Eventya
Lemma B.3 (modified from 3.3maa33), Denote by C₁ = log(Ti/p) and C2 = a² log mIs
Tog(Ti \/m)
Suppose S 0.01 min(1, T2 To 100 and Ti 2 To- We start from wo and apply Algorithm Under event Event?,,7y (wo), satisfies
Ji-1
(wo) - (wr, 0.7m)
Σ
(IV)( +C2) (C2) -((iirnd( v(aa)
1=0
The next lemma can be easily derived from Lemma 3.5
Lemma B.4 (modified from Lemma 3,5), Suppose
R = 0 VCi /1C2) and v² = O log 8a
6
1
Suppose n S 0.01 min(1, C. To I0un(1+ vos) and Ti = e n8 Tp 2 To. Let we E Rd be any
log
point in the spuce and suppose Amin (V (V=)(w))) I 8 for some 5 2 0. Given two coupled sequences defined as before, under events Eventfr (wî) and Event (wr),, we have with probability at least 0.98
max (S(w)) - fww,, ((ub) (w
Ti-1
2 0.5n
Σ O (C3) -
+ 9
C1
log
83 nC
Lemma B.4 directly proves the second half of Theorem B.le because given two coupled sequences with the same marginal distribution, have
Pr[f(wō) f(w),) 2 x] Pr|max {f(w)) (, - f(w x]
Proof of Lemma B.4, Our choice and R. satisfy the requirement of Lemmna 3.5 Suppose without loss of generality that the wi sequence leaves Wo by more than R. Let 7i be the first iteration t S Ti in which ||w] woll 2 1 will (()))
Vf((w
3
-
+ -
0 Ti)
Combining this with Lemma B.3 we have
T
| - will
f(w8) f(wāç) 2 0.5m
100y7
twu
R²
2 0.5m
- VCa)) + 100nTi
Combining this with Lemma B.3 a.gjn but for the remainder iterations, have
R² 100r/Ti
f(w() - f(w[)) ) 2 0.5m
[[V](())1 O(C2 (C+) O(Ch'' vCa))) +
In fact, the above same proof of Lemma B.4 also implies Theorem B.lb These together finish the proof of Theorem B.
C
MORE ON EXPERIMENTS
We conduct experiments training residual network ResNet-20 (216)) on the CIFAR-10/100 image classification tasks Krizhevsky et al. (2014).
18

---

Published as a conference paper at ICLR 2021
C.1 SETTING AND IMPLEMENTED METHODS
In all of experiments, defender algorithm, we run SGD three times for 140 epochs, cach time with different initial learning rate We let the learning rate decrease by a factor of 10 on epochs 80 and 110, and present present the best testing accuracies in the three runs (cach corresponding to a different initial learning rate).
10 workers and mini-batch size 10 per worker. Given any attacker and any
? E {0.1, 1, 0.2, 0.4) [?]
We use standard data augmentation (random crops, random flips, and channel normalization).
We compare against Geometric Median Chen et al. (2017), Coordinate-win Median Yin et al. (2018) 2019), Krum Blanchard et al. (2017), and Zeno Xie et al. (2018b) with attacks. We set a = 0.4 so there are Byzantine workers. (This exceeds the fault-toerrance of Krum, and so we also tested Krum with only 3 Byzantine workers.) We formally define those prior works as follows.
Definition C.I (GeoMed Chen et al. (2017)). The geometric median of (vi,... Um.. denoted by geo med yr y Vm
= arg min weRd E 1ly 3ill In our experiments, we choose the geometric median from set {y1, ... Um
geo
Definition C.2 (coordinatc-wise median Yin al. (2018 (019)).
Coordinate-wise median g
medKy1, y1..., -.., ym + defined as a vector with its k-th coordinate being g(k] k E [d], where med is the usual (one-dimensional) median.
med yı [k), ..., ym [k) for each
Definition C.3 (Krum Blanchard et al. (2017)).
KR 3m == where == arg min :E[ml
Σ 11s Uill
and i + j is the indices of the m b- nearest neighhours of y in {ui, ..., Dm Kve by Euclidean distances.
Note that Krum requires 2b + 2 < So, have also repeated the experiments for Krum with 3 Byzantine workers (out of 10 workers) to be more fair.
Definition C.4 (Zeno Xie et al. (2018b)).
Zeno
( (yi, Hm.) m
(1)
where (i)1) i [m]} are the gradient estimators with the b highest "scores", and the so-called stochastic descendant score for any gradient estimator based the current parameter æ. learning rate n, and a constant weight p >> 0, is defined as:
Scoren (u, = fx())- f-(x)) 17)) p|lul
J-(x)-f(xx - f-(x is the estimated descendant of the loss function and pl|u|] is the magnitude of the update.
In experiments, we let fx( he the estimated objective over mini-hatch of size n, 10 the time perform this estimation on the same magnitude as the gradient evaluation for each individual worker). We also chose p = 0.0005 (and this value does not affect our experimental results by much).
Safeguard SGD. Our Algorithm is stated in way to make theoretical proof's clean as possible. Here, we discuss how we actually implement in practice.
First of all, as common in the literature, we omit the Gaussian noise & that is added for theoretical purpose, and instead rely on the natural noise in the training process escape saddle points.
Also, we make universal choices for our safeguard window sizes (across all attackers): for our algorithm with a single safeguard we have used universal window size T safeguards we have used window sizes To = epoch and Ti = 6 epochs.
epochs, and for our algorithm with double
We also provide an automatic empirical process select safeguard thresholds and eliminate bad workers The process to determine Amed (and likewise for Bmes) is described as follows. In each iteration, for every worker i E [m), we sort Al - Ayll), se[m) and pick the smallest mm/2 + 1]-th entry, and let this number the "score" for worker i. We select worker with the smallest "score" as Amed and call its "score" S. Then, we use 1.5 min(S, (S, 5} as the safeguard threshold for this iteration. Namely, we declare any worker satisfying
'Recall typical suggested initial learning rate is 0.1 for training ResNet with SGD+4momnttum; since we are using SGD without momentum, the initial learning rate can appropriately enlarged. In our first version of the paper, pre-run the algorithm for 20 epochs to determine safeguard thresholds; in the newer version, we have avoided the pre-run.
19

---

Published as a conference paper at ICLR 2021
IIA,- Amedl 2 1.5 ma 5) as bad worker" 9
C.2 EXPERIMENT RESULTS BY ATTACKS
The ideal accuracies 91.7% / 68.0% for CIFAR-10/100, which correspond to applying SGD using only the stochastic gradients from the honest workers. Below we discuss about the experimental results one atlack at a time.
C.2.1 VARIANCE ATTACK
We begin by looking the hardest proposed attack from prior works. The Variance attack follows the strategy prescribed by Baruch et al. (2019), by which Byzantine workers collude in order to shift the mean among all gradients by factor 3 times the standard deviation of the gradient, while staying within population variance. More precisely, the maximal change to the mean that can be applied by attacker without the fear of being detected, by using the properties of the Normal distribution, specifically the cumulative standard normal function, and compute the maximal possible shift so that attackers's values stay within population variance. (See (Baruch et al., 20199 Algorithm 3) for a precise description. Our 3 is 2max in their notation.) We implement this strategy coordinate-ve wiit, the same way as they did. Their work observes that the shift /3 can be non-trivial in practice, since stochastic gradients tend to have large variance in neural network training (which we also observed in our setup). Critically, the attack cannot be defended against by historyless algorithms, as the attacker's 's values are statistically indistinguishable from a regular execution a single iteration.
In our setting, for 10 total nodes and a = 0.4, 3 is upper bounded by 0.3 (following the classic tables for the cumulative normal). We also the same attack in the setup from their paper (50 nodes total, of which 24 Byzantine, which allows S 1.5) and observed similar outcome. Results for this experiment are given in Figure
100
1IFAR10 aest accuracy
80
ongie singieni
Engle sllgued
double sofeguard
double saleagard
60
modian
coard modian
Kur
Kium (3 bod node
CIFAR100
30
40
Kram nodeoo
fram
medion
20
10
20
40
100
120
140
20
40
60
80
100
120
140
epochs
epachs
(a) CIFAR-10
(b) CIFAR-IOU
Figure 3: Performance comparison under the variance attack.
As shown by the results, our algorithm provably circumvents this attack, and recovers full accuracy. This is explained by the fact that the algorithm has memory: in particular, Byzantine nodes following this strategy will progressively diverge from the (honest) "median" Amad (at a "linear" rate, recall Figure 2(a)), and therefore will eventually exceed the threshold and be marked malicious by the algorithm.
Specifically, both variants of the algorithm successfully catch all the bad nodes after at most 150 iterations. Indeed, at the 100-th iteration, the pair-wise distances ||A,, 144-A4 AAll among good workers i,j E good are between 5.3 and 6.3, but the wase distance between a good and bad worker is at least 12.5.
C.2.2 FLIP-IGI ATTACK
We next move onto the sign-fipping attack. Recall that, in a sign-flipp fign-flippin attack, each Byzantine worker sends the negative gradient to the master. This is still a strong attack since if one does not avoid any bad workers, the test accuracy will suffer from significant drop, The results are in Figure 4)
From the plots, one can see that again our single and double safe-guard algorithms both outperform prior works. They also successfully catch all the bad workers within 150 iterations. (For instance, at iteration 150 for CIFAR- 10 training, the distance ||.Amed A, || for good worker E good is at most 6.9, but for bad
This process appears little different from Algorithm 1, but a similar proof also holds for this new empirical process. The constant factor 1.5 requires tuning, and the constant threshold 5 is chosen so that the stochastic gradient of batch size 500 random initialization has Fuclidean norm no more than 5.
20

---

Published as a conference paper at ICLR 2021
100
80
70
CIFARIO test accuraty
60
Sigle salepuard
druble sntepuudd
50
median
40
Enum
noden)
Veseeee douile safoquord
20
cocrd median
geoimedian
Krum bod nodes
Zire
20
40
100
120
140
epochs
epochs
(a) CIFAR-10
(b) CIFAR-I00
Figure 4: Performance comparison under the sign-flipping attack.
worker j good it can more than 11.)
In contrast, prior work Zeno completely fails because locally at training step, using merely 10 samples evaluate the objective, it statistically not possible flipped not. prior works Krum and GcoMedian, although they appear have some non-negligible performances, but they are actually no better than simply applying SGD with the naive mean gradients from all the workers (including those from bad workers) Therefore, we conclude that prior works all fail to be Byzantine fault tolerant under this attack.
distinguish if the sign of the stochastic gradient
C.2.3 DELAYED-GRADIENT ATTACK
Recall that, in a delayed-gradien attack, each Byzantine worker sends an old gradient to the master. In our experiments, the delay is of D = 1000 iterations (= 2 epochs). We believe this is not a very strong attack, because delayed gradients not sufficiently malicious: they still "correct" to certain extent albeit being delayed. The results are shown in Figure 5
100
80
70
CIFAR10 test accuratyy
60
50
40
single safegrard
degle safeguord eesseee deable sateguord
sessee double safeguord
20
oxerd medion
gen
csced median
Krum bod nodes]
Krum bod nodes) Zoro
Zoro
20
opochs
epachs
CIFAR-10
(b) CIFAR-100
Figure 5: Performance comparison under the btlayed-gradient attack.
From the plots, one can see that our single and double safe-guard algorithms again both match the ideal accuracies. All the prior works suffer from significant performance loss under this attack.
is worth noting that our single and double safe-guard algorithms do catch any bad worker under this attack, so they simply use "naive mean" " gradients from the workers (including those delayed gradients from bad workers). However, there is no performance loss even we use those delayed gradients. That is why we believe the delayed-gradieed attack is not very strong, the gradients are not sufficiently malicious.
Prior work Zeno suffers from some performance loss, because only uses workers of 10, in which statistically only x 0.6 z 3 ~ gradients are correct Other prior works suffer from performance loss,
1eWe did not include this "naive mean" algorithm in the plots for cleanness, but under the sign gen-flipping attack, it gives 81.4% test accuracy on CIFAR- 10 and 38.3% CIFAR-100. (This should not be surprising, since using (1 a
6 positive gradients plus am negative gradients still gives non-negligible information about the true gradient.)
In fact, we observed Zeno slightly favors delayed gradients, where each delay gradient is chosen with probability 63%, comparing to stochastic gradients each chosen with probability 58%.
21

---

Published as a conference paper at ICLR 2021
because they only pick one single stochastic gradient from the 10 workers, and is sometimes even from the bad worker.
C.2.4 LABEL- ATTACK
Recall that, in the label-fipppng attack, each Byzantine worker computes its gradient based the cross-entropy loss with flipped labels: for CIFAR-IO, 10, label E (0....99) 9} is flipped l, and for CIFAR-100, label flipped to 99 L. The results are shown in Figure
100
80
70
CIFARO test acourscy
inggle origuaad
60
coard medan modian
50
Krum
single srregeard
GIFR100
double seleguard
Zono
median
~ 1yggo Appn
Krum
Krum bed rodert
opochs
opochs
(a) CIFAR-10
(b) CIFAR-I00
Figure 6: Performance comparison under the label-flippigg attack.
From the plots, accuracies." (92.4% accuracy "ideal accuracy" 91.7% under CIFAR-IO; 69.4% accuracy "ideal accuracy" 68.0 under CIFAR-100.) In addition, we have found out that the safeguard algorithms did not catch any had worker. This should not he surprising, since lahel-flipping (a.k.a. label smoothing) is known to be regularization technique to actually improve test accuracy, opposed to hurt performance.
that single and double safe-guard algorithms outperform the "ideal
Zeno also performs well under this attack (but it does outperform ideal accuracy). We have investigated into Zeno, and found out that it cannot distinguish good workers from bad workers under label flipping attack; and therefore Zeno effectively always runs under 6 random workers as opposed to using the full power of the 10 workers (recall Zeno picks 6 workers with the topmost scores, see Definition C.4), This explains its (minor) mnder-performanee comparing safeguard.
Other prior works perform significantly worse, and this should be alarming since label-fipping is one type of smoothing technique to improve test accuracy, as opposed to an actual "attack" to hurt performance.
C.2.5 SAFEGUARD ATTACKS
Finally, in the safeguard attack we design, Byzantine workers send negative re-scaled gradient to the master. We choose the re-scale factor so that it hardly triggers the safe-guard conditions at the master. From our experiment, choosing the re-scale factor 0.6 in all the cases do not trigger the safe-guard conditions, while choosing re-scale factor 0.7 enables the algorithm catch Byzantine workers occasionally. Our results shown Figure (for re-scale factor 0.6) and Figure (for re- scale factor 0.7).
100
70
CIFARI0 test accurity
50
My
double
30
coard modias
single
820 midian
diuulle selegiord
20
cocrrd median
Knum bod nodeed
Zero
opochs
opochs
(a) CIFAR-10
(b) CIFAR-100
Figure 7: Performance comparison under the safeguard attack with re-seale factor 0.6. (Recall this attack designed to maximally impact the performance our algorithm.)
22

---

Published as a conference paper at ICLR 2021
Re-seale factor 0.6. In Figure the performance of (single and double) safeguard algorithms indeed get hurt bit. Recall Figure the re-scale factor 0.6 is chosen maximally impact our algorithm. The accuracy drops from 91.7% to 89.3% under CIFAR-10; and drops from 68.0% to 60.0% under CIFAR- 100 (for both single and double safeguards). In these cases, we confirm that both versions of the safeguard algorithms did not catch any bad worker. However, this still significantly outperforms all prior works.
100
70
CIARCO accuracy
80
sinlle saleguard
exlegoors
60
40
Jigll salogaars suleguard
Trum
Krum nodel]
$20 modian
20
Srum
noden)
20
epochs
epochs
(a) CIFAR-10
(h) CIFAR-100
Figure 8: Performance comparison under the safeguard attack with re-scale factor 0.7. (In this case, our our algorithm can catch some bad workers, and thus perform nearly optimally.)
Re-scale factor 0.7. In Figure 8, we present the scenario when the re-scale factor is 0.7, so that the safeguard algorithms occasionally catch some bad workers (depending the randomness and learning rate). We confirm that in the three runs of single safeguard, catches 3 bad workers for CIFAR-10 10, and 0, bad workers for CIFAR-100 respectively; in the three runs double safeguard, catches 1, 2, bad workers CIFAR-10, and 2, 2, bad workers for CIFAR- 100 respectively.
Since there is significant performance gain when safeguard algorithms catch had workers, this explains why safeguard algorithms Figure outperform their counterparts Figure 7 with rescale factor 0.6. the same time, we notice the double safeguard algorithm has the ability to catch bad workers more easily. This why double safeguard significantly outperforms single sageguard in Figure
In contrast, all other prior algorithms perform extremely bad under this attack. To some extent, safeguard attack even stronger than the previously proposed variance attack, since can drag the 100-class accuracy on CIFAR-100 for prior defense algorithms to nearly 1%, while variance attack can only drag them down to around 10%.
C.3 FULL COMPARISON TABLE
also include full test accuracy comparison table in Table
single safeguard
double safeguard
coord
geo
Krum
Zeno
fodey
variance attack
92.02
91.75
21.43
22.01
21.47
22.4
33.42
flipping attack
91.93
92.08
22
59.65
57.03
70.87
22.4
label flipping attock
92.33
92.44
31.93
83.07
83.18
83.52
91.66
deloyed-gradient attack
sofeguard(x0.6) attack
89.01
89.26
21.44
23.12
12.48
28.66
74.46
sofeguord(x0.77
single
double
coord
Krum fustyrodes
safeguard
safeguard
median
median
variance attack
68.27
67.95
6.5
5.81
5.05
6.1
10.87
sign-flipping
label-filppng atteck
69.43
68.8
5.34
51.85
52.13
51.66
67.86
deloyed gradient attock
67.03
66.42
4.04
36.34
31.43
44.85
36.6
safeguard(x0.0g 6) attack
59.87
60
2.01
1.25
1.72
5.02
sofeguard(o..7 7) attack
59.84
64.91
2.07
1.97
1.32
1.55
3.31
Table 1: Table accuracy performances CIFAR-10 10 (above) and CIFAR-100 (below).
23

---

Published as a conference paper at ICLR 2021
C.4 ATTACK AGAINST THE CONVEX ALGORITHM OF ALISTARH ET AL. (2018)
We briefly describe attack against this algorithm. The attack specifically leverages the fact that the algorithm does use sliding windows.
One can first run the vanilla SGD to compute "the maximum deviation per good worker" for the accumulation vector used by the algorithm Σ V.. This maximum deviation therefore lower bound for the threshold used in their algorithm. Next, we design an attacker who evenly distributes this total allowed deviation to e.g. 5 consecutive epochs, and behaves honestly for the remaining epochs. Such an attacker cannot be identified by this algorithm, because its total deviation across all the iterations is identical to that of a good worker. However, this leads the algorithm divergence.
Specifically, suppose 4 Byzantine workers all maliciously report their stochastic gradients multiplied by the scalar -5, and the remaining good workers report their true stochastic gradicnts. One can verify numerically that this attacker can for consccutive epochs (say, epochs + 1, caught by the algorithm. Now,
3, + 4) without being
if a S 75, within just epoch of attack, the neural net weights diverge (value NAN)
if 80 S a S 115, this attack is applied after the first learning rate decay. Within just epoch the attack, the objective explodes and accuracy becomes 10% (random), and within 3 epochs the algorithm diverges completely.
if 120 < S 155, this attack after the second learning rate decay. Within just epochs of attack, the accuracy drops 11%. Later, the accuracy never recovers above 40%.
24


Reviews:
[{"review_id": "r7Ec0BSw3OA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers stochastic gradient descent convergence in a distributed setting with m workers, where up to α workers can be Byzantine, i.e. perform in an arbitrarily adversarial way. In this setting, they develop a variant of SGD which finds a second-order stationary point, prevents Byzantine workers from significantly affecting convergence, and achieves α^2 + 1/m speedup compared with the sequential case. The main idea of the algorithm is to measure deviations of gradient updates for a certain number of rounds and detect Byzantine machines which must have a significant deviation to noticeably affect the algorithm’s behavior.\n\n\nIf I’m correct, Lemma 3.1 allows a much simpler proof:\n|\\sum_{t=1}^{T-1} (ξ_0 + … + ξ_{t-1}) * Delta_t|\n<= |\\sum_{t=1}^{T-1} ξ_t| * |\\sum_{t=1}^{T-1} Delta_t| + |\\sum_{t=1}^{T-1} ξ_t * (Delta_1 + … + Delta_t)|\nThe first term is estimated as a sum of independent Guassians. The second term can be estimated using Azuma’s inequality (it’s a martingale since E[ξ_t] = 0 and ξ_t is independent on ξ_1, …, ξ_{t-1}, Delta_1, …, Delta_t). We can bound their norms of ξ_t by O(log (T/p)) with probability 1 - p/T.\n\nQuestions:\nIn Jin et al. (2019), dependence on d can be avoided when an additional assumption (Lipschitz stochastic gradient) is made. Can this work use this assumption? I believe that footnote 3 on page 4 talks about this assumption and argues that it may be too strong for practical applications, but I don’t see a reason to not get a result with this assumption. Are there technical obstacles?\nAssumption 2.1, both items: the bounds are typically taken in expectation: E[||∇f(x_t) - ∇_ti ||^2] <= σ^2. Can this paper handle this kind of assumption? At the very least, one can’t immediately detect byzantine machines that deviate from the mean by more than σ.\nAlgorithm 1, line 11: it shouldn’t matter, but isn’t it more natural to take an average over good_{t+1}, not good_t?\nPage 13, last equation: while the inequality seems to be true (since ξ_t are independent Gaussians), I don’t see how it follows from Lemma 4.2.\nPage 14, Equation B.2: isn’t this way to bound the sum too loose? What’s the intuition behind this approach? Can we get a better bound with some other approach?\n\nThe following parts would benefit from an additional discussion:\nWhile it’s clear that α^2 + 1/m comes from bounds on σ_t and Delta_t, the intuitive meaning behind the α^2 term is not clear. The reason why α=1/sqrt(m) is a threshold is also not clear.\nWhile it may be clear from the algorithm (namely how the median behaves), I think it’s also worth explaining why the algorithm doesn’t significantly degrade when α is close to ½, unlike what one can expect.\n\nI believe that the following places would benefit from the further expansion:\nPage 13, bound on ||Delta_0 + … + Delta||^2: it’s better to explicitly write relation between B^t and Delta_t.\nPage 15, “for some vector ||θ_t||”: I would explain the bound.\nPage 15, “ψ_t is zero except in the first coordinate”: I would explain why.\nPage 16, right after M is introduced: I would explain the first transition.\n\nMinor issues:\nWhile assuming that smoothness constants are 1 slightly simplifies the presentation, I believe that it makes some transitions harder to understand. E.g. bound on θ_t on page 15 would be more clear if the Hessian Lipshitz constant was in the equation.\nnu should be an input/parameter of Algorithm 1\nPage 13, proof of Claim B.2: it’s said that the proof is by induction, by I don’t think you use induction anywhere.\nPage 13, Proof of Lemma 4.3: “Lipschitz smoothness” -> “smoothness”?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MZycKG3DSe", "reviewer": "AnonReviewer1", "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": "In this paper, the authors propose a new algorithm called SafeguardSGD, which solves the Byzantine detection problem, and tolerate less than half Byzantine workers with theoretical guarantees. Both theoretical and empirical results are provided. Compare to the baselines, the proposed algorithms show better performance on fixed Byzantine workers. In overall, I think this is a good paper.\n\nHowever, there are some issues to be resolved:\n\n1. The problem solved in this paper is actually not Byzantine tolerance, but Byzantine worker detection, which is a special case of Byzantine tolerance with stronger assumptions. The main difference is that, in this paper, the proposed method assumes that the malicious workers never change their roles (once Byzantine, always Byzantine), i.e., the indices of the Byzantine workers never change. Such assumption is not required by most of the previous works (Krum, median, Zeno), although it may not be emphasized in the previous work. With such assumption, the proposed algorithm could make the use of the historical info and remove the Byzantine worker permanently, which is why it could perform better than the baselines. I'm ok with the scenario (which is also used in [1]), but the authors should clearly state that the threat model in this paper is weaker than the previous work.\n\nWhy this assumption matters?  Note that it is unnecessary that the Byzantine workers always behaves maliciously.\n\nConsidering the following cases:\n\n(1) The Byzantine workers behave as honest workers at the beginning, and start the attack at the middle of the training. I believe the proposed algorithm could handle this case, but it will be better if such experiments could be added.\n\n(2) On some workers, there are some occasional and temporal hardware/software failures that produce results with huge error (flipped bits, large random noise), but such workers will recover later. In this case, it seems unreasonable to remove the failed workers from the list of good workers permanently.\n\n\n2. It seems that the proposed algorithm is highly related and similar to [1]. However, the difference to [1] is not discussed in details in this paper. Furthermore, since [1] uses the same weakened threat model as this paper, it should be the most important baseline to compare to, which is not included in the experiments. I understand that there is not experiments in [1], so doing experiments for it may be difficult, but I'm not sure whether it's just difficult or totally infeasible. At least, the authors should explain why [1] is not included in the experiments.\n\n[1] Alistarh, D., Allen-Zhu, Z., & Li, J. Byzantine stochastic gradient descent. NeurIPS 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "K_snPXBw0ND", "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 non-convex learning that is Byzantine resilient. The main contribution of the paper is an algorithm that is based on perturbed stochastic gradient descent, that is provably resilient to Byzantine failures, and that is guaranteed to reach near second-order stationary points of non-convex objective functions. Compared to similar works in the literature, this paper focuses on identifying Byzantine workers using a \"concentration of gradients\" argument that are then permanently removed from consideration for future iterations. The paper has a nice blend of algorithmic development, theoretical analysis, and detailed experiments. Overall, it is a good paper, worthy of publication in the proceedings. Before the final decision, however, I would like the authors to help address the following questions / comments of mine.\n\n**Major Comments**\n\n1. The permanent removal of workers from each iteration appears to be a risky strategy when one is dealing with workers' data that are not i.i.d. In particular, \"RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets\" is one such work that seems to be able to deal with non-i.i.d. datasets in Byzantine settings. It would be useful to see how does the proposed approach work in the presence of non-i.i.d. datasets and how does it compare to works such as the one referenced earlier.\n   - A minor point, which is more of a curiosity: Is it possible for the Byzantine workers to play a colluding game where they force convergence **before** the algorithm had a chance to go through the two windows and eliminate the Byzantine workers?\n2. While the paper refers to its strategy as \"stochastic gradient descent\", the method is really \"perturbed stochastic gradient descent\" that involves adding white Gaussian noise of variance $\\nu^2$ to the iterates. This adds one more parameter to the problem and it is not clear how would one tune this parameter. Theorem 2.3 in the paper requires $\\nu^2$ to be set according to knowledge of $\\alpha$, the fraction of Byzantine workers. It is not clear from reading the paper as to how the authors set this parameter in their experiments.\n3. Related to the above point, Theorem 2.3 only provides scaling guidelines for the different parameters (including the stepsize) in SafeguardSGD and even those scaling guidelines involve knowledge of $\\alpha$. How does one fix these parameters and how were these parameters set for the experiments? In particular, one wonders why does the stepsize need to be a function of the fraction of Byzantine workers?\n4. The statement of Theorem 2.3 needs a bit of clarification. First, it would be useful to specify the \"high probability\" part. What's the scaling of this high probability and it scales with which parameters? Second, what is the practical significance of \"for at least constant fraction of the indices $t$\"? Does this mean that the algorithm can, at the final stages of the algorithm, actually leave the neighborhood of the stationary point?\n5. In Theorem C.1, part (c), the probability is lower bounded by 0.45. This does not seem like \"high probability\" at all. What are the implications of this assumption in Theorem C.1, part (c) on the overall results reported in the paper?\n6. The experimental results are done for fixed numbers of Byzantine workers. It would have been useful to see how the performance scales with the increase in the number of Byzantine workers.\n7. While this paper discusses distributed learning, Byzantine resilience in decentralized learning has also been investigated in recent works (see, e.g., Adversary-resilient distributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model). Are there any lessons for distributed Byzantine resilience from this paper that can be translated to decentralized Byzantine resilience?\n\n**Minor Comments**\n\n1. The range of $p \\in (0,1)$ should be specified in Lemma 3.1 for complete rigor.\n\n***Post-discussion period comments***\n\nI am pleased with the revision the authors have posted during the discussion phase. I am also satisfied with the authors' response to my comments and to the comments of the other reviewers. I therefore recommend that this paper be accepted into proceedings of ICLR 2021.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7bk_pRkiDX_", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\nThe authors present quite an interesting approach where they focus on the number of stochastic gradient evaluations rather than bounding the number of sampled stochastic functions. They converted other aggregation functions in their own formulation and then did a fair comparison. The results are in favor of the authors' method. The SafegaurdSGD algorithm is presented with several formal analysis and authors shows that why it is theoretically better to have two matrices (history record or safeguards) to mark the working machines good or bad/byzantine. The time complexity they present seems a bit difficult to understand and the argument they present for parallel speedup is also difficult to grasp as the machines are already running in a distributed environment how one can do parallel speedup? This should be presented in a clear way. The formal analysis is though rigorous but it requires a lot of time to understand as some of these notations are not defined and clearly mentioned and one has to assume some of the arguments presented to follow on.  The author presents that their method offers stronger bounds.  I appreciate the formal work and it clearly aligns with the results they have shown in the paper and in the supplementary part. The authors have studied the latest attacks introduced in literature and experimented other methods in their own introduced attack for a fair comparison which is great. Although there are several parameters that the authors do not discuss how they are chosen for the experiments they just show the experiment results for some selected values of parameters. \nThe paper needs some format organization and need to define and clear something so it might become clear to other readers to understand and grasp concepts. \nThe authors have already talked about the parallel speed in the introduction and instead of iterating in after Theorem 2.3, space can be used to fill with other detail or definition as it can be seen the authors are already short on space due to page limit. \nIn the end, I want to say that please define notations before using them. It is quite an issue while reading the paper, you have to stop and have to find the definition. $\\Omega(m^2d)$ in the introduction $d$ is not defined before. While mentioning the number of iteration required $x_0$ is not defined, $\\Tilde O$ is not defined and is defined at section $2$. Lemma 3.2 $\\Delta_t$ is used and then defined later. The spelling of Loewner is wrong. \n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new algorithm for byzantine resilient nonconvex distributed optimization. The presentation is clear, the motivation is solid, and the problem setting is interesting. The novelty of the present work is sufficient for publicaiton. The new scheme comes with some provable guarantees, improving the prior state of the art. Some of these guarantees are arguably not corresponding to strong operational robustness guarantees, however they compare well with convergence proofs of the related literature. Some concerns were raised with regards to comparison with some prior work, but the authors addressed it in the rebuttal.
Decision: Accept (Poster)