BYZANTINE-RESILIENT NON-CONVEX STOCHASTIC GRADIENT DESCENT∗
Year: 2021

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 α-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.

heading: 1 INTRODUCTION
text: 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 α 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 is to minimize some stochastic function f(x) = Es∼D[fs(x)] over a distribution D, where fs(·) can be viewed as the loss function for sample s ∼ D. We assume there are m machines (workers) and an honest master, and α < 1/2 fraction of the workers may be Byzantine. In each iteration t, each worker has access to a version of the global iterate xt, which is maintained by the master. The worker can independently sample s ∼ D, compute ∇fs(xt), and then synchronously send this stochastic gradient to the master. The master aggregates the workers’ messages, and sends an updated iterate xt+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 et al., 2017; Su & Vaidya, 2016a;b; Xie et al., 2018a) relied on defining generalizations of the geometric median. These approaches can withstand up to half of the nodes being malicious, but can have relatively high local computational cost Ω(m2d) (Blanchard et al., 2017; Chen et al., 2017), where m is the number of nodes and d is the problem dimension, and usually have suboptimal sample and iteration complexities. 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 https://arxiv.org/abs/2012.14368. †Microsoft Research Redmond, zeyuan@csail.mit.edu ‡University of Waterloo, faezeeb75@gmail.com §Microsoft Research Redmond, jerrl@microsoft.com ¶IST Austria, dan.alistarh@ist.ac.at
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 a 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 Byzantine-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 (a.k.a. second-order critical points). In a nutshell, our main result is the following. Fix d to denote the dimension, and let the objective f : Rd → R be Lipschitz smooth and second-order smooth. We have m worker machines, each having access to unbiased, bounded estimators of the gradient of f . Given an initial point x0, the SafeguardSGD algorithm ensures that, even if at most α < 1/2 fraction of the machines are Byzantine, after
T = Õ (( α2 + 1m ) d(f(x0)−min f(x)) ε4 ) parallel iterations,
for at least a constant fraction of the indices t ∈ [T ], the following hold: ‖∇f(xt)‖ ≤ ε and ∇2f(xt) − √ εI.
If the goal is simply ‖∇f(xt)‖ ≤ ε, then T = Õ ( ( α2 + 1m ) (f(x0)−min f(x)) ε4 ) iterations suffice. Here, the Õ notation serves to hide logarithmic factors for readability. We spell out these factors in the detailed analysis.
• When α < 1/ √ m, our sample complexity (= mT ) matches the best known result in the non-
Byzantine case (Jin et al., 2019) without additional assumptions, and enjoys linear parallel speedup: with m workers of which < √ m are Byzantine, the parallel speedup is Ω̃(m).1 • For α ∈ [1/ √ m, 1/2), our parallel time complexity is Õ(α2) times that needed when no
parallelism is used. This still gives parallel speedup. This α2 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 a weaker goal: to find approximate stationary points ‖∇f(x)‖ ≤ ε only: Bulusu et al. (2020) additionally assumed there is a guaranteed good (i.e. non-Byzantine) worker known by the master, Xie et al. (2018b) gave a 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 an 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 a worker is labelled bad, it is removed from consideration forever. The master then performs the vanilla SGD, by moving in the negative direction of the average gradients produced by those workers currently labelled as good. We call our algorithm SafeguardSGD, since it behaves like having a safe guard to filter away bad workers. Its processing overhead at the master is O(md), negligible compared to 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 non-Byzantine 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 are 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) to filter out Byzantine machines
1By parallel speedup we 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 corrupted.
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 nonconvex 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-wise median or mean over the batch average (e.g. Yin et al. (2018; 2019); Yang et al. (2019)) or 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 calculate an almost precise full gradient, so that they can apply a surrogate 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 α, e.g. α < 1/4 (Su & Xu, 2018), and, critically, have been shown to be vulnerable to recent attacks (Baruch et al., 2019; Xie et al., 2020). Attack resilience and experimental validation. There is a growing literature on customized attacks against Byzantine-resilient algorithms, showing that many defenses can be entirely circumvented in real-world scenarios (Baruch et al., 2019; Xie et 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., 2018b; 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 SafeguardSGD generally outperforms previous methods in convergence speed and final accuracy, sometimes by a 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.

heading: 2 STATEMENT OF OUR THEORETICAL RESULT
text: We denote by ‖ · ‖ the Euclidean norm and [n] := {1, 2, . . . , n}. Given symmetric matrices A,B, we let ‖A‖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 λmin(A) the minimum eigenvalue of matrix A. We consider arbitrary d-dimensional non-convex functions f : Rd → R satisfying the following:
• f(x) is L-Lipschitz smooth: meaning ‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖ for any x, y ∈ Rd; • f(x) is L2-second-order smooth: ‖∇2f(x)−∇2f(y)‖2 ≤ L2 · ‖x− y‖ for any x, y ∈ Rd;
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 is a compact domain X ⊂ Rd, then one can 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 ideas. Byzantine non-convex stochastic distributed optimization. We let m be the number of worker machines and assume at most an α fraction of them are Byzantine for α ∈ [ 0, 12 ) . We denote by good ⊆ [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 xt and query m machines. Each machine i ∈ [m] gives back a vector∇t,i ∈ Rd satisfying
• If i ∈ good, the stochastic gradient∇t,i satisfies E[∇t,i] = ∇f(xt) and ‖∇f(xt)−∇t,i‖ ≤ V .3
• If i ∈ [m] \ good, then∇t,i can be arbitrary (w.l.o.g. we assume ‖∇f(xt)−∇t,i‖ ≤ V).4
Remark 2.2. For each t and i 6∈ good, the vector ∇t,i can be adversarially chosen and may depend 2In the literature of convergence analysis for non-convex optimization, the final complexity bounds naturally and polynomially depend on these parameters L,L2,V , and the way the dependence goes is typically unique (Allen-Zhu, 2018a;b; Fang et al., 2018; Jin et al., 2019). This is why it suffices to ignore their appearance and only compare the polynomial dependence on ε and d.
3One can instead assume Pr[‖∇f(xt) − ∇t,i‖ > t] ≤ 2 exp(−t2/2V2) and the results of this paper continue to hold up to logarithmic factors. To present the simplest theory, we do not include that version in this paper. We refer interested readers to Jin et al. (2019) for how to deal with such probabilistic assumption (when there is no Byzantine worker).
4This requirement ‖∇f(xt)−∇t,i‖ ≤ V is “without loss of generality” because it is trivial for the algorithm to catch bad machines if they output∇t,i more than 2V away from the majorities.
Algorithm 1 SafeguardSGD: perturbed SGD with double safe guard
Input: point x0 ∈ Rd, rate η > 0, lengths T ≥ T1 ≥ T0 ≥ 1, threshold T1 > T0 > 0; 1: good0 ← [m]; 2: for t← 0 to T − 1 do 3: last1 ← max{t1 ∈ [t] : t1 is a multiple of T1}; 4: last0 ← max{t0 ∈ [t] : t0 is a multiple of T0} 5: for each i ∈ goodt do 6: receive∇t,i ∈ Rd from machine i; 7: Ai ← ∑t k=last1 ∇k,i |goodk| and Bi ← ∑t k=last0 ∇k,i |goodk| ;
8: Amed ← Ai where i ∈ goodt is any machine s.t. ∣∣{j ∈ goodt : ‖Aj −Ai‖ ≤ T1}∣∣ > m/2.
9: Bmed ← Bi where i ∈ goodt is any machine s.t. ∣∣{j ∈ goodt : ‖Bj −Bi‖ ≤ T0}∣∣ > m/2.
10: goodt+1 ← { i ∈ goodt : ‖Ai −Amed‖ ≤ 2T1 ∧ ‖Bi −Bmed‖ ≤ 2T0 } ;
11: xt+1 = xt − η ( ξt +
1 |goodt| ∑ i∈goodt ∇t,i ) ; Gaussian noise ξt ∼ N (0, ν2I)
on {∇t′,i}t′≤t,i∈[m]. In particular, the Byzantine machines can even collude during an iteration.

heading: 2.1 OUR ALGORITHM AND THEOREM
text: Our algorithm is based on arguably the simplest possible method for achieving this goal, (perturbed) stochastic gradient descent (SGD) (Ge et al., 2015). Our techniques more broadly apply to 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 t = 0, 1, . . . , T − 1, we maintain a set of (allegedly) good machines goodt ⊆ [m]. We begin with good0 = [m] and start to detect malicious machines and remove them from the set. We choose a learning rate η > 0, and perform the SGD update
xt+1 = xt + ξt − η 1|goodt| ∑ i∈goodt
∇t,i where ξt ∼ N (0, ν2I) is a random Gaussian perturbation that is added for theoretical purpose. For each machine i ∈ [m], we keep track of the history of its stochastic gradients up to two windows. Namely, Ai ← ∑t k=last1 ∇k,i |goodk| and Bi ← ∑t k=last0 ∇k,i |goodk|
, for windows sizes T0 ≤ T1 ≤ T . We compare among remaining machines in goodt, and kick out those ones whose Ai or Bi deviate “more than usual” to construct goodt+1. Conceptually, we view these two as safe guards. Our theory makes sure that, when the “window sizes” and the thresholds for “more than usual” are defined properly, then goodt shall always include good, and the algorithm shall proceed to find approximate local minima. Formally, we have (letting the Õ notion to hide polylogarithmic factors)
Theorem 2.3. Let C3 = α2 + 1m . Suppose we choose ν 2 = Θ̃(C3), η = Θ̃( ε
2
dC3 ), T0 = Θ̃( 1η ),
T1 = Θ̃( 1 η √ ε ), T0 = Θ̃(
√ T0), and T1 = Θ̃( √ T1), then after
T = Õ (
(f(x0)−min f(x))d ε4 (α 2 + 1m ) )
iterations, with high probability, for at least constant fraction of the indices t ∈ [T ], they satisfy ‖∇f(xt)‖ ≤ ε and ∇2f(xt) − √ εI .
Remark 2.4. If one only wishes to achieve a significantly simpler goal — finding first-order critical points ‖∇f(xt)‖ ≤ ε — 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 T = Õ ( f(x0)−min f(x) ε4 (α 2 + 1m ) ) . Bulusu et al. (2020) achieves this easier goal but requires an additional assumption: there is one guaranteed good worker known by the master.
Our contribution. We reiterate our theoretical contributions from three perspectives. 1) When α < 1/ √ m, our algorithm requires mT = Õ ( (f(x0)−min f(x))d ε4 ) stochastic gradient computations. This matches the best known result (Jin et al., 2019) under our minimal assumptions of the nonconvex objective. (There exist other works in the stochastic setting that break the ε−4 barrier
and get rid of the dimension dependence d under stronger assumptions.)5. 2) When α < 1/ √ m, our algorithm enjoys linear parallel speed-up: the parallel time complexity reduces by a factor of Θ(m). When α ∈ [1/ √ m, 1/2), our parallel time complexity is Õ(α2) times that needed when no parallelism is used, still giving noticeable speedup. The α2 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 a weaker (and less standard) guarantee: ‖∇f(x)‖ ≤ ε and ∇2f(x) −(ε2d)1/5I. 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 on bounding the number of sampled stochastic functions, as opposed to the number of stochastic gradient evaluations like we do. When translated to our language, each of the workers in their setting needs to evaluate T stochastic gradients, where (1) T = Õ ( α2d ε4 + d2 ε4m+ √ d ε3
) if using coordinate-wise median, (2) T = Õ ( α2d2
ε4 + d2 ε4m
) if using trimmed mean, and (3)
T = Õ ( α ε4 + d ε4m ) 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 (ε, √ ε) guarantee, becomes T = Õ ( αd2
ε5 + d3 ε5m
) so is also larger than ours. It is
worth noting that (3) requires α < 1/4 so cannot withstand half of the machines being Byzantine. Resilience against practical attacks. Our algorithm’s filtering is based upon tracking Bi (resp. Ai), the stochastic gradients of each machine i averaged over a window of T0 (resp. T1) iterations. This is a departure from previous defenses, most of which are history-less, and enables us to be provably Byzantine-resilient against state-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 a factor β times the standard deviation of the (true stochastic) gradient, while staying within population variance. They noticed β 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 Ω(T ) in T iterations as opposed to √ T ), 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 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 goodt to include all nodes every T1 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.1 for details.) We validate this experimentally in Section 5.

heading: 3 WARMUP: SINGLE SAFE GUARD
text: As a warmup, let us first analyze the behavior of perturbed SGD with a single safe guard. Consider Algorithm 2, where we start with a point w0, a set good0 ⊇ good, and perform T steps of perturbed SGD. (We use the wt sequence instead of the xt sequence to emphasize that we are in Algorithm 2.)
5Works such as (Allen-Zhu, 2018a; Lei et al., 2017; Tripuraneni et al., 2017; Allen-Zhu, 2018b; Fang et al., 2018; Nguyen et al., 2017) require f(x) = Es∼D[fs(x)] where each fs(x) is second-order smooth and/or Lipschitz smooth. This requirement may be too strong for certain practical applications.
Algorithm 2 Perturbed SGD with single safe guard (for analysis purpose only)
Input: point w0 ∈ Rd, set good0 ⊇ good, rate η > 0, length T ≥ 1, threshold T > 0; 1: for t← 0 to T − 1 do 2: for each i ∈ goodt do 3: receive∇t,i ∈ Rd from machine i; 4: Bi ← ∑t k=0 ∇k,i |goodk| ;
5: Bmed ← Bi where i ∈ goodt is any machine s.t. ∣∣{j ∈ goodt : ‖Bj −Bi‖ ≤ T}∣∣ > m/2.
6: goodt+1 ← { i ∈ goodt : ‖Bi −Bmed‖ ≤ 2T } ;
7: wt+1 = wt − η ( ξt +
1 |goodt| ∑ i∈goodt ∇t,i ) ; Gaussian noise ξt ∼ N (0, ν2I)
Definition 3.1. We make the following definition to simplify notations: let Ξt := σt + ∆t where • σt := 1|goodt| ∑ i∈good ( ∇t,i −∇f(wt) ) • ∆t := 1|goodt| ∑ i∈goodt\good ( ∇t,i −∇f(wt)
) Therefore, we can re-write the SGD update as wt+1 = wt − η(∇f(wt) + ξt + Ξt) .
The following lemma is fairly immediate to prove: Lemma 3.2 (single safe guard). In Algorithm 2, suppose we choose T = 8 √ T log(16mT/p). Then, with probability at least 1− p/4, for every t = 0, . . . , T − 1, • goodt ⊇ good.
• ‖σt‖2 ≤ O( log(T/p)m ) and ‖σ0 + · · ·+ σt−1‖ 2 ≤ O(T log(T/p)m )
• ‖∆t‖2 ≤ α2 and ‖∆0 + · · ·+ ∆t−1‖2 ≤ O(α2T log(mT/p)) • |〈∇f(wt), ξt〉| ≤ ‖∇f(wt)‖ ·O(ν √ log(T/p)),
• ‖ξt‖2 ≤ O(ν2d log(T/p)), ‖ξ0 + · · ·+ ξt−1‖2 ≤ O(ν2dT log(T/p)) We call this probabilistic event EventsingleT (w0) and Pr[Event single T (w0)] ≥ 1− p/4.
(The third property above is ensured by our choice of T and the use of safe guard, and the rest of the properties follow from simple martingale concentration arguments. Details are in Appendix A.1.)

heading: 3.1 CORE TECHNICAL LEMMA 1: OBJECTIVE DECREASE
text: Our first main technical lemma is the following:
Lemma 3.3. Suppose we choose T as in Lemma 3.2. Denote by C1 = log(T/p) and C2 = α2 log mTp + log(T/p) m . Suppose η ≤ 0.01 min{1, 1 C2 }, T = 1 100η(1+ √ C2) and we start from w0 and apply Algorithm 2. Under event EventsingleT (w0), it satisfies
f(w0)− f(wT ) ≥ 0.7η ∑T−1 t=0 ( ‖∇f(wt)‖2 − η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) Lemma 3.3 says after T ≈ 1η steps of perturbed SGD, the objective value decreases by, up to some small additive error and up to logarithmic factors, f(w0) − f(wT ) ≥ 0.7η ∑T−1 t=0 (‖∇f(wt)‖2 − ηC2). This immediately implies, if we choose η ≈ ε 2
C2 , then by repeating this analysis for
O(C2ε4 ) = O( α2+1/m
ε4 ) iterations, we can find approximate critical point x with ‖∇f(x)‖ ≤ ε. 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 to derive that
f(w0)− f(wT ) ' 0.9η ∑T−1 t=0 ( ‖∇f(wt)‖2 − η ) + η ∑T−1 t=0 〈∇f(wt),Ξt〉︸ ︷︷ ︸
remainder terms
where recall that Ξt = σt+∆t. When there are no Byzantine machines, we have E[Ξt] = E[σt] = 0 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∇t (even by collusion) so as to negatively correlate with∇f(wt) to “maximally destroy” the above inequality.
Our main idea is to use second-order smoothness to write∇f(wt) ≈ ∇f(w0)+∇2f(w0)·(wt−w0). To illustrate our idea, let us ignore the constant vector and assume that the Hessian is the identity: that is, imagine as if∇f(wt) ≈ wt −w0. Using wt −w0 = − ∑ k<t Ξt + ξt, we immediately have
−〈∇f(wt),Ξt〉 ≈ −〈wt − w0,Ξt〉 = ∑ k<t〈Ξk,Ξt〉+ ∑ k<t〈ξk,Ξt〉 (3.1)
For the first partial sum 〈 ∑ k<t Ξk,Ξt〉 in (3.1), it is easy to bound its magnitude using our safeguard.
Indeed, we have ∣∣∑ t〈 ∑ k<t Ξk,Ξt〉 ∣∣ ≤ ‖∑t Ξt‖2+∑t ‖Ξt‖2 so we can apply Lemma 3.2. For the second partial sum ∑ t ∑ k<t〈ξk,Ξt〉, we can apply the concentration Proposition 3.4 below.
Proposition 3.4. Fix the dimension parameter d ≥ 1. Suppose ξ0, . . . , ξT−1 ∈ Rd are i.i.d. drawn fromN (0, I), and that ∆1, . . . ,∆T−1 are arbitrary vectors in Rd. Here, each vector ∆t with t = 1, . . . , T − 1 can depend on ξ0, . . . , ξt−1 but not on ξt, . . . , ξT−1. Suppose that these vectors satisfy ‖∆1 + · · ·+ ∆t‖2 ≤ T for every t = 1, . . . , T − 1. Then, with probability at least 1− p,∣∣∣∑T−1t=1 〈ξ0 + · · ·+ ξt−1,∆t〉∣∣∣ ≤ O(√dTT log(T/p)) .

heading: 3.2 CORE TECHNICAL LEMMA 2: RANDOMNESS COUPLING
text: Our next technical lemma studies that, if run Algorithm 2 from a point w0 so that the Hessian ∇2f(w0) has a eigenvalue which is less than −δ (think of w0 as a saddle point), then with good probability, after sufficiently many iterations, the sequence w1, w2, . . . , wT shall escape from w0 to distance at leastR for some parameterR ≈ δ. 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 w0. For any vector v, let [v]i denote the i-th coordinate of v.
Lemma 3.5. Suppose we choose T as in Lemma 3.2 and C1, C2 as in Lemma 3.3. Suppose w0 ∈ Rd satisfies λmin(∇2f(w0)) = −δ for some δ ≥ 0. Without loss of generality let e1 be the eigenvector of∇2f(w0) with smallest eigenvalue. Consider now two executions of Algorithm 2, both starting from wa0 = w b 0 = w0, and suppose their randomness {ξat }t and {ξbt }t are coupled so that [ξat ]1 = −[ξbt ]1 but [ξat ]i = [ξbt ]i for i > 1. In words, the randomness is the same orthogonal to e1, but along e1, the two have opposite signs. Now, suppose we perform T = Θ( 1ηδ log R2δ ην2 ) steps of perturbed SGD from wa0, w b 0 respectively using Algorithm 2. Suppose
R ≤ O (
δ√ C1 log(R2δ/ην2)
) and ν2 ≥ Ω ( C2 log R2δ ην ) .
Then, under events EventsingleT (w a 0) and Event single T (w b 0), with probability at least 0.98, either ‖wat − w0‖ > R or ‖wbt − w0‖ > R for some t ∈ [T ].
Proof details in Appendix A.4. The main proof difficulty is to analyze a 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).

heading: 4 FROM WARMUP TO FINAL THEOREM WITH DOUBLE SAFE GUARDS
text: At a high level, Lemma 3.3 ensures that if we keep encountering points with large gradient ‖∇f(wt)‖, then the objective should sufficiently decrease; in contrast, Lemma 3.5 says that if we keep encountering points with negative Hessian directions (i.e., λmin(∇2f(wt)) < −δ), then the points must move a 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 ‖∇f(x)‖ being large, or λmin(∇2f(x)) 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 simultaneously hold. We encourage the reader to examine the full analysis in Appendix B.

heading: 5 EXPERIMENTAL VALIDATION
text: We evaluate the convergence of SafeguardSGD to examine its practical performance against prior works. We perform the non-convex task of training a residual network ResNet-20 (He et al., 2016) on the CIFAR-10/100 datasets (Krizhevsky et al., 2014). More details are given in Appendix C.
We instantiatem = 10 workers and one master node executing data-parallel SGD for 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), Coordinatewise Median (Yin et al., 2018; 2019), Krum (Blanchard et al., 2017), and Zeno (Xie et 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 it very sensitive to hyper-parameter values and were unable to make it converge across all attacks even after significant tuning of its γ parameter. We also implemented the convex algorithm of Alistarh et al. (2018), and executed it in our non-convex setting. We found their algorithm can be easily attacked on our ResNet training tasks. There exists a simple attack, described in Appendix C.4 which causes their algorithm to either mislabel most good workers as Byzantine, or diverge, or converge to very poor solutions. This is not surprising, since their algorithm is 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 T0 = 1 epoch and T1 = 6 epochs across all experiments, and adopted an automated process to select T0,T1. Determining these thresholds requires being able to pre-run the task on an honest worker. We have also implemented a single safeguard variant of SafeguardSGD, with window size T = 3 epochs. Attacks. We set α = 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 crossentropy loss with flipped labels: for CIFAR-10, label ` ∈ {0, ..., 9} is flipped to 9− `.
• DELAYED-GRADIENT ATTACK: each Byzantine worker sends an old gradient to master. In our experiments, the delay is of D = 1000 iterations.
• VARIANCE ATTACK (Baruch et 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.)
• SIGN-FLIPPING ATTACK: each Byzantine worker sends the negative gradient to 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-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 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
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.
• SafeguardSGD 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 is 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-gradient 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 to negative.
• SafeguardSGD can easily catch all the bad workers under sign-flipping and variance attacks, and thus leads to gives ideal performance. It cannot catch any bad worker for label-flipping and delayed-gradient attacks, but there is no performance loss anyways if we use such bad gradients.
• The safeguard attacks, designed to maximally impact the performance of our SafeguardSGD, can indeed affect our performance. Specifically, under re-scale factor 0.6, the test accuracy drops from 91.7% to 89.3% because SafeguardSGD cannot catch any bad worker; however, under rescale factor 0.7, the test accuracy no longer drops because SafeguardSGD can begin to catch some bad workers (it can catch between 0 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. A 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 an 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 ‖Bi −Bmed‖ registered at the master server, for two nodes, an honest one, and a Byzantine one. The value of ‖Bi−Bmed‖ increases for all the nodes (at a rate of roughly √ t at step t); but, once the attack starts, the statistic for the Byzantine node grows linearly in t, leading to fast detection. Transient attacks and node ID relabeling. Finally, in Figure 2(b) we analyze the behaviour of our algorithm when it 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 can 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.

heading: ACKNOWLEDGMENTS
text: F. E. 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 ScaleML).

heading: APPENDIX

heading: A MISSING PROOFS FOR SECTION 3

heading: A.1 PROOF OF LEMMA 3.2
text: Recall the following, useful inequality.
Lemma A.1 (Pinelis’ 1994 inequality (Pinelis, 1994)). Let X1, . . . , XT ∈ Rd be a random process satisfying E[Xt|X1, . . . , Xt−1] = 0 and ‖Xt‖ ≤M . Then, Pr [ ‖X1 + · · ·+XT ‖2 > 2 log(2/δ)M2T ] ≤ δ.
Lemma 3.2 is in fact a direct corollary of the following claim, whose proof is quite classical. Denote by C = log(16mT/p). Denote by
B (t) i := ∇0,i |good0| + · · ·+ ∇t−1,i|goodt−1| and B(t)? := ∇f(w0) |good0| + · · ·+ ∇f(wt−1)|goodt−1| .
Recall at iteration t− 1, Algorithm 2 computes {B(t)1 , . . . , B (t) m } as well as some B(t)med = B (t) i where i is any machine in goodt−1 such that at least half of j ∈ [m] satisfies ‖B (t) j −B (t) i ‖ ≤ 8 √ tC/m.
Claim A.2. Let C = log(16mT/p). Then, with probability at least 1− p/4, we have
(a) for all i ∈ good and t ∈ [T ], ‖B(t)i −B (t) ? ‖ ≤ 4
√ tC/m.
(b) for all t ∈ [T ], each i ∈ good is a valid choice for B(t)med = B (t) i .
(c) for all i ∈ good and t ∈ [T ], ‖B(t)i −B (t) med‖ ≤ 16 √ tC/m and ‖B(t)? −B(t)med‖ ≤ 12 √ tC/m (d) for all i ∈ good and t ∈ [T ], we also have i ∈ goodt+1.
(e) ∥∥∑ i∈good ( B (t) i −B (t) ? )∥∥ ≤ O(√t log(T/p)/√m). Proof of Claim A.2. We prove by induction. Suppose the statements hold for t− 1 and we now move to t.
(a) For each i ∈ good, note E[∇t,i] = ∇t and ‖∇t,i − ∇t‖ ≤ 1. Let Xt = ∇t,i−∇t|goodt| , so that ‖Xt‖ ≤ 1|goodt| ≤ 1 (1−α)m ≤ 2 m . We can thus apply Lemma A.1 to the Xt and then take a union
bound over all i ∈ good. Thus, with probability at least 1 − p 8T we have ‖B(t)i − B (t) ? ‖ ≤ 4
√ tC/m for
all i ∈ good. The result follows from a further union bound over t ∈ [T ].
(b) Claim A.2a implies for every i, j ∈ good we have ‖B(t)i − B (t) j ‖ ≤ 8
√ tC/m. Therefore each i ∈ good
is a valid choice for setting B(t)med = B (t) i .
(c) This is a consequence of the previous items and the definition of B(t)med.
(d) This is a consequence of the previous item.
(e) We can apply Lemma A.1 with {X1, X2, . . . , Xt|good|} = { ∇k,i−∇f(wk) |goodk|
}k∈[t],i∈good. It holds with probability at least 1− p
8T that ∥∥∑ i∈good ( B (t) i −B (t) ? )∥∥ ≤ O(√t log(T/p)/√m).
Proof of Lemma 3.2. The property goodt ⊇ good is from Claim A.2d.
The property ‖σt‖2 ≤ O( log(T/p)m ) is by standard concentration inequalities for sums of bounded random vectors.
The property ‖σ0 + · · ·+ σt−1‖2 ≤ O(T log(T/p)m ) is from Claim A.2e. The property ‖∆t‖ ≤ α is obvious as we have at most α fraction of the bad machines. The bound on ‖∆0 + · · · + ∆t−1‖2 can be derived as follows. For every i ∈ [m] \ good, let t be the last iteration i satisfies i ∈ goodt. Then, by the triangle inequality,
‖B(t+1)i −B (t+1) ? ‖ ≤
2 m + ‖B(t)i −B (t) ? ‖
On the other hand, t ∈ goodt implies ‖B (t) i − B (t) med‖ ≤ 16
√ tC/m by the algorithm; combining this with
‖B(t)? −B(t)med‖ ≤ 12 √ tC/m, and summing up over all such bad machines i finishes the proof.
The final two properties follow from standard facts about Gaussian random vectors.

heading: A.2 PROOF OF LEMMA 3.3
text: Proof of Lemma 3.3. Using the Lipschitz smoothness of f(·), we have
f(wt)− f(wt+1) ≥ 〈∇f(wt), wt − wt+1〉 − 1
2 ‖wt − wt+1‖2
= η‖∇f(wt)‖2 + η〈∇f(wt),Ξt〉 − 1
2 ‖wt − wt+1‖2 + η〈∇f(wt), ξt〉
We first show:
‖wt − wt+1‖2 = η2‖∇f(wt) + Ξt − ξt‖2 ≤ 3η2(‖∇f(wt)‖2 + ‖Ξt‖2 + ‖ξt‖2)
| T−1∑ t=0 η〈∇f(wt), ξt〉| ≤ η √√√√T−1∑ t=0 ‖∇f(wt)‖2 ·O(ν √ C1) ≤ ( 0.05η T−1∑ t=0 ‖∇f(wt)‖2 ) +O(C1ν 2η)
The first follows since (a + b + c)2 ≤ 3(a2 + b2 + c2) for any a, b, c ∈ R, and the second follows from Lemma 3.2. Combining them, and also using that ‖Ξt‖2 ≤ O(C2), ‖ξt‖2 ≤ O(dν2C1), and η ≤ 0.01, we have
f(w0)− f(wT ) ≥ 0.9η T−1∑ t=0 ( ‖∇f(wt)‖2 −O(ηC2) ) + η T−1∑ t=0 〈∇f(wt),Ξt〉 −O(ηTν2C1(ηd+ 1 T ))
(A.1)
For the inner product on the right hand of (A.1), we have that
η T−1∑ t=0 〈∇f(wt),Ξt〉 = η T T−1∑ q=0 〈 ∇f(wq), T−1∑ t=0 Ξt 〉
︸ ︷︷ ︸ ♠
+ η
T T−1∑ q=0 T−1∑ t=0
〈∇f(wt)−∇f(wq),Ξt〉︸ ︷︷ ︸ ♣
(A.2)
For the first term ♠, we have
|♠| ≤ η T T−1∑ q=0 ∣∣∣〈∇f(wq), T−1∑ t=0 Ξt 〉∣∣∣ ≤ η T T−1∑ q=0 ‖∇f(wq)‖ · ∥∥∥ T−1∑ t=0 Ξt ∥∥∥ ≤ 0.1η
T−1∑ q=0 ‖∇f(wq)‖2 + O(η) T 2 T−1∑ q=0 ∥∥∥ T−1∑ t=0 Ξt ∥∥∥2 ≤ 0.1η
T−1∑ q=0 ‖∇f(wq)‖2 +O ( ηC2 ) where the last inequality follows from Lemma 3.2.
For the second term ♣, we have
|♣| ≤ η T T−1∑ q=0 ∣∣∣ T−1∑ t=0 〈∇f(wt)−∇f(wq),Ξt〉 ∣∣∣ ≤ η T T−1∑ q=0 ∣∣∣ T−1∑ t=0 〈∇2f(w0)(wt − wq),Ξt〉 ∣∣∣︸ ︷︷ ︸
♦
+ η
T T−1∑ q=0 T−1∑ t=0
(‖wt − w0‖+ ‖wq − w0‖)‖wt − wq‖‖Ξt‖︸ ︷︷ ︸ ♥
Using ‖wt − wq‖ ≤ ‖wt − w0‖+ ‖wq − w0‖, one can derive
♥ ≤ η T T−1∑ q=0 T−1∑ t=0 (‖wt − w0‖+ ‖wq − w0‖)2 ·O( √ C2)
≤ η T−1∑ t=0 ‖wt − w0‖2 ·O( √ C2) ≤ η3 T−1∑ t=0 ‖∇f(w0) + · · ·+∇f(wt−1) + Ξ0 + · · ·+ Ξt−1 + ξ0 + · · ·+ ξt−1‖2 ·O( √ C2)
≤ O( √ C2η 3T 2) T−1∑ t=0 ‖∇f(wt)‖2 +O( √ C2C2η 3T 2) +O(η3ν2T 2dC1 √ C2)
As for ♦,∣∣∣ T−1∑ t=0 〈∇2f(w0)(wt − wq),Ξt〉 ∣∣∣ ≤ ∣∣∣ T−1∑ t=q+1 〈∇2f(w0)(wt − wq),Ξt〉 ∣∣∣+ ∣∣∣ q−1∑ t=0 〈∇2f(w0)(wt − wq),Ξt〉 ∣∣∣
For the first term (and the second term is analogous), we have∣∣∣ T−1∑ t=q+1 〈∇2f(w0)(wt − wq),Ξt〉 ∣∣∣
= η ∣∣∣ T−1∑ t=q+1 〈∇2f(w0)(∇f(wq) + · · ·∇f(wt−1) + Ξq + · · ·Ξt−1 + ξq + · · ·+ ξt−1),Ξt〉 ∣∣∣
≤ η ∣∣∣ T−1∑ t=q+1 〈∇2f(w0)(ξq + · · ·+ ξt−1),Ξt〉 ∣∣∣+
η ∣∣∣ T−1∑ t=q+1 〈∇2f(w0)(∇f(wq) + · · ·∇f(wt−1)),Ξt〉 ∣∣∣+ η∣∣∣ T−1∑ t=q+1 〈∇2f(w0)(Ξq + · · ·Ξt−1),Ξt〉 ∣∣∣
¬ ≤ η ·O( √ dν2TC1 · √ TC2)+
η ∣∣∣ T−2∑ t=q 〈∇2f(w0)∇f(wt) ,Ξt+1 + · · ·+ ΞT−1〉 ∣∣∣+ η 2 〈 ∇2f(w0)(Ξq + · · ·ΞT−1), (Ξq + · · ·ΞT−1) 〉
≤ η ·O( √ dν2TC1 · √ TC2) + η T−2∑ t=q ‖∇f(wt)‖‖Ξt+1 + · · ·+ ΞT−1‖+ η 2 ‖Ξq + · · ·ΞT−1‖2
 ≤ O(η √ TC2) · T−1∑ t=0 ‖∇f(wt)‖+O(TηC2 + Tην2dC1) .
Above, inequality ¬ uses ‖Ξ0 + · · ·Ξt‖ ≤ O( √ TC2) for C2 = α2 log mTp + log(T/p) m
(see Lemma 3.2) and a delicate application of Azuma’s inequality that we state at the end of this subsection (see Proposition 3.4); Inequality  uses Young’s inequality and Lemma 3.2.
Putting this back to the formula of ♦, we have
♦ ≤ O(η2 √ TC2) · T−1∑ t=0 ‖∇f(wt)‖+O(Tη2C2 + Tη2ν2dC1)
≤ 0.1η T−1∑ t=0 ‖∇f(wt)‖2 +O(η3T 2C2 + Tη2C2 + Tη2ν2dC1)
Finally, putting ♦ and ♥ back to ♣, and putting ♣ and ♠ back to (A.2) and (A.1), we have f(w0)− f(wT ) ≥ 0.8η T−1∑ t=0 ‖∇f(wt)‖2 −O( √ C2η 3T 2) T−1∑ t=0 ‖∇f(wt)‖2
− C2 ·O(η + η2T + η3T 2 + √ C2η 3T 2)− C1 ·O(Tη2ν2d+ T 2η3ν2 √ C2 + ηTν 2(ηd+ 1
T ))
together with T = 1 100η(1+ √ C2) and η ≤ 0.01 min{1, 1 C2 }, we have f(w0)− f(wT ) ≥ 0.7η T−1∑ t=0 ‖∇f(wt)‖2 − C2 ·O(η + η2T + η3T 2 + √ C2η 3T 2)− C1 ·O(Tην2η(d+ √ C2))
= 0.7η T−1∑ t=0 ( ‖∇f(wt)‖2 − C2 ·O( 1 T + η + η2T + √ C2η 2T )− C1 ·O(ηTν2η(d+ √ C2)) ) ≥ 0.7η T−1∑ t=0 ( ‖∇f(wt)‖2 − η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) .

heading: A.3 PROOF OF PROPOSITION 3.4
text: Proposition 3.4. Fix the dimension parameter d ≥ 1. Suppose ξ0, . . . , ξT−1 ∈ Rd are i.i.d. drawn from N (0, I), and that ∆1, . . . ,∆T−1 are arbitrary vectors in Rd. Here, each vector ∆t with t = 1, . . . , T − 1 can depend on ξ0, . . . , ξt−1 but not on ξt, . . . , ξT−1. Suppose that these vectors satisfy ‖∆1 + · · ·+ ∆t‖2 ≤ T for every t = 1, . . . , T − 1. Then, with probability at least 1− p,∣∣∣∑T−1t=1 〈ξ0 + · · ·+ ξt−1,∆t〉∣∣∣ ≤ O(√dTT log(T/p)) . Proof of Proposition 3.4. Using the identity formula6∑T−1
t=1 〈ξ0 + · · ·+ ξt−1,∆t〉 = (∑T−2 t=0 ξt )(∑T−1 t=1 ∆t ) − ∑T−2 t=1 〈ξt,∆1 + · · ·+ ∆t〉
we have∣∣∣∑T−1t=1 〈ξ0 + · · ·+ ξt−1,∆t〉∣∣∣ ≤ ∥∥∥∑T−2t=0 ξt∥∥∥ · ∥∥∥∑T−1t=1 ∆t∥∥∥+ ∣∣∣∑T−2t=1 〈ξt,∆1 + · · ·+ ∆t〉∣∣∣ . ≤ O( √ dTT log(T/p)) +
∣∣∣∑T−2t=1 〈ξt,∆1 + · · ·+ ∆t〉∣∣∣ . where the last inequality uses ‖ξ0 + · · · + ξT−2‖ ≤ O( √ dT log(1/p)) with probability at least 1 − p/2. Furthermore, we note that ξt is independent of ξ0, . . . , ξt−1,∆1, . . . ,∆t and E[ξt] = 0. Therefore, letting St = 〈ξt,∆1 + · · ·+ ∆t〉, we have E[St|ξ0, . . . , ξt−1] = 0; furthermore, with probability at least 1− p/2, it satisfies |St| ≤ O(
√ dT log(T/p)) for every t. Finally, by Azuma’s inequality, we have∣∣∣∑T−2t=1 〈ξt,∆1 + · · ·+ ∆t〉∣∣∣ ≤ O(√dTT log(T/p)) .

heading: A.4 PROOF OF LEMMA 3.5
text: Proof of Lemma 3.5. Let us denote by rt = [ξat]1 2 = − [ξ b t]1 2 and we know rt ∼ N (0, ν 2 4 ). We can write wat+1 − wbt+1 = ηrte1 + wat − wbt − η(∇f(wat)−∇f(wbt ))− η(Ξat − Ξbt) Using the second-order smoothness, we have
∇f(wat)−∇f(wbt ) = ∫ 1 τ=0 ∇2f ( wat + τ(w b t − wat) ) (wat − wbt )dτ
= ∇2f(w0) · (wat − wbt ) + θt for some vector ‖θt‖ ≤ max{‖wa0 − wat‖, ‖wb0 − wbt‖} · ‖wat − wbt‖. Therefore, we have
wat+1 − wbt+1 = ηrte1 + ( I− η∇2f(w0) ) (wat − wbt )− η(Ξat − Ξbt + θt)
Now, giving ψ0 = ψ0 = 0, imagine two sequences • ψt+1 = ηrte1 + ( I− η∇2f(w0) ) ψt and
• ψt+1 = ηrte1 + ( I− η∇2f(w0) ) ψt − η(Ξat − Ξbt + θt) = wat+1 − wbt+1
We will inductively prove ‖ψt − ψt‖ ≤ 12‖ψt‖. On one hand, it is easy to see that ψt is zero except in the first coordinate, in which it behaves as a Gaussian with zero mean and variance ∑t−1 k=0(1 + ηδ) 2k · η 2ν2 4 =
Θ ( (1+ηδ)2t
ηδ · η2ν2
) . By Gaussian tail bounds, we know that
• with probability at least 0.99, it satisfies ‖ψt‖ ≤ O( √ ηC1ν(1+ηδ)
t √ δ ) for every t
• with probability at least 0.99, it satisfies ‖ψT ‖ ≥ 11000 ( √ ην(1+ηδ)T√ δ )
In the rest of the proof, we condition on this event happens. We prove towards contradiction by assuming ‖wat − wa0‖ ≤ R and ‖wbt − wb0‖ ≤ R for all t ∈ [T ]. We will inductively prove that ‖ψt − ψt‖ ≤ 12000 ( √ ην(1+ηδ)t√ δ ). We calculate the difference
ψt − ψt = η t−1∑ i=0 ( I− η∇2f(w0) )t−1−i (Ξai − Ξbi + θi)
Let g = ψt−ψt‖ψt−ψt‖ , then we can inner-product the above equation by vector g, which gives
‖ψt − ψt‖ = η t−1∑ i=0 〈 Ξai − Ξbi + θi , ( I− η∇2f(w0) )t−1−i g 〉
6We thank an anonymous reviewer on openreview who pointed out this simpler proof to us.
¬ ≤ η t−1∑ i=0 (〈 Ξai − Ξbi , ( I− η∇2f(w0) )t−1−i g 〉 +R ·O( √ ηC1ν(1 + ηδ) i √ δ ) · (1 + ηδ)t−1−i )
≤ η t−1∑ i=0 〈 Ξai − Ξbi , ( I− η∇2f(w0) )t−1−i g 〉 +O(RηT √ ηC1√ δ ν(1 + ηδ)t)
where the inequality ¬ uses ‖θi‖ ≤ R · ‖ψi‖ ≤ R · (‖ψi‖ + ‖ψi − ψi‖), ∥∥(I − η∇2f(w0))t−1−ig∥∥ ≤
(1 + ηδ)t−1−i, and the inductive assumption. Let us call M = ( I− η∇2f(w0) ) , and focus on∣∣∣∣∣ t−1∑ i=0 〈 Ξai , ( I− η∇2f(w0) )t−1−i g 〉∣∣∣∣∣
= ∣∣∣∣∣〈Ξa0 + · · ·+ Ξat−1 , g〉+ t−2∑ i=0 〈 Ξa0 + · · ·+ Ξai ,M t−1−ig −M t−2−ig 〉∣∣∣∣∣ ≤ ‖Ξa0 + · · ·+ Ξat−1‖ · ‖g‖+
t−2∑ i=0 ‖Ξa0 + · · ·+ Ξai‖ · ‖M t−1−ig −M t−2−ig‖
≤ O( √ TC2 ( ‖g‖+
t−2∑ i=0 ‖M t−1−ig −M t−2−ig‖
) (using Lemma 3.2)
≤ O( √ TC2 · (1 + ηδ)t−1)
Together, we have
‖ψt − ψt‖ ≤ O(η √ TC2) · (1 + ηδ)t +O(RηT √ ηC1√ δ ν(1 + ηδ)t)
Under our assumption, we have ‖ψt−ψt‖ < 12000 ( √ ην(1+ηδ)t√ δ ) and therefore ‖ψT ‖ ≥ ‖ψT ‖−‖ψT −ψT ‖ ≥
1 2000
( √ ην(1+ηδ)t√
δ ). Thus, within T iterations, we have ‖ψt‖ > R and this gives a contradiction.

heading: B FINAL: DOUBLE SAFE GUARD
text: We now come to our final Algorithm 3 which is our perturbed SGD algorithm with two safeguards. The two safeguard algorithm naturally divides itself into epochs, each consisting of T1 iterations. We will demonstrate that within most epochs, we make good progress. Thus, consider some iterate xmT1 , for some m < T/T1. Our goal will be to argue that we make good function value progress by iterate x(m+1)T1 , and that we do not settle into any saddle points. To slightly simplify notation, let w0 = xmT1 , and let the sequence of iterates be w0, . . . , wT1−1, so that wT1−1 = x(m+1)T1−1. For completeness’ sake we rewrite this as Algorithm 1.
Algorithm 3 Perturbed SGD with double safe guard (for analysis purpose)
Input: w0 ∈ Rd, set good0 ⊇ good, rate η > 0, lengths T1 ≥ T0 ≥ 1, threshold T1 > T0 > 0; 1: for t← 0 to T1 − 1 do 2: last← max{t0 ∈ [t] : t0 is a multiple of T0} 3: for each i ∈ goodt do 4: receive∇t,i ∈ Rd from machine i; 5: Ai ← ∑t k=0 ∇k,i |goodk| and Bi ← ∑t k=last ∇k,i |goodk| ;
6: Amed ← Ai where i ∈ goodt is any machine s.t. ∣∣{j ∈ goodt : ‖Aj −Ai‖ ≤ T1}∣∣ > m/2.
7: Bmed ← Bi where i ∈ goodt is any machine s.t. ∣∣{j ∈ goodt : ‖Bj −Bi‖ ≤ T0}∣∣ > m/2.
8: goodt+1 ← { i ∈ goodt : ‖Ai −Amed‖ ≤ 2T1 ∧ ‖Bi −Bmed‖ ≤ 2T0 } ;
9: wt+1 = wt − η ( ξt +
1 |goodt| ∑ i∈goodt ∇t,i ) ;
Our main result is the following theorem.
Theorem B.1. Let C3 = α2 + 1m . Suppose we pick parameters p, δ ∈ (0, 1), η ≤ Õ( δ3 C3 ), ν2 = Θ̃(C3), T0 = Θ̃ ( 1 η ) , T1 = Θ̃ ( 1 ηδ ) ≥ T0, T1 = Θ̃( √ T1), and T0 = Θ̃( √ T0). Then, starting from w0,
(a) with probability at least 1− p we have
f(w0)− f(wT1) ≥ 0.7η T1−1∑ t=0 ( ‖∇f(wt)‖2 − Õ(ηC3d) ) .
(b) As long as ‖wt − w0‖ ≥ R for some t ∈ {1, 2, . . . , T1} and for R = Θ̃(δ) ≤ δ2 , then with probability at least 1− p we have then
f(w0)− f(wT1) ≥ 0.5η T1−1∑ t=0 ( −Õ(ηC3d) ) + Ω̃(δ3)
(c) if λmin(∇2f(w0)) ≤ −δ, we also have with probability at least 0.45,
f(w0)− f(wT1) ≥ 0.5η T1−1∑ t=0 ( −Õ(ηC3d) ) + Ω̃(δ3)

heading: B.1 WHY THEOREM B.1 IMPLIES THEOREM 2.3
text: Using the parameter choice η = Θ̃( ε 2
C3d ) from Theorem 2.3, we know Õ(ηC3d) ≤ 0.1ε2. We claim two
things:
• For at least 90% of the epochs, they must satisfy (denoting by w0 and wT1 the beginning and ending points of this epoch)
f(w0)− f(wT1) ≤ 20 f(x0)−min f(x)
T/T1 ≤ ε1.5
The last inequality uses our choice of T and δ = Θ̃( √ ε).
The reason for this is by way of contradiction. Suppose for at least 10% of the epochs it satisfies f(w0) − f(wT1) > 20 f(x0)−min f(x) T/T1
, then, for the remainder of the epochs, they must at least satisfy f(w0) − f(wT1) ≥ −0.7ηT1 · 0.1ε2. Summing over all the epochs, we shall obtain f(x0) − f(xT ) > f(x0)−min f(x) but this gives a contradiction.
• For at least 40% of the epochs, they must satisfy the three properties from Theorem B.1.
In particular, for at least 30% of the epochs, they must satisfy both. Since ε1.5 is so small that
ε1.5 ≥ f(w0)− f(wT1) ≥ 0.5η T1−1∑ t=0 ( −Õ(ηC3d) ) + Ω̃(δ3) ≥ Ω̃(δ3)− 0.05ηT1ε2
would give a contradiction (for instance, one can choose δ to be slightly larger than √ ε by some log factors), this means, for those 30% of the epochs, they must satisfy:
• ε1.5 ≥ 0.7η ∑T1−1 t=0 ( ‖∇f(wt)‖2 − 0.1ε2 ) , • ‖wt − w0‖ ≤ δ2 for every t = 1, 2, . . . , T1, and • ∇2f(w0) −δI.
The latter two properties together implies ∇2f(wt) − δ2I for every t = 1, 2, . . . , T1 (by the second-order smoothness). The first property implies for at least 90% of the iterations t in this epoch, they must satisfy ‖∇f(x)‖ ≤ ε. This finishes the proof of Theorem 2.3.

heading: B.2 PROOF OF THEOREM B.1
text: We first have the following lemma Lemma B.2 (double safe guard). In Algorithm 3, suppose T1 = 8 √ T1 log(16mT1/p) and T0 =
8 √ T0 log(16mT1/p). Then, with probability at least 1− p/2, for every t = 0, . . . , T1 − 1,
• goodt ⊇ good.
• ‖σt‖2 ≤ O( log(T1/p)m ), ‖∆t‖ 2 ≤ α2, ‖ξt‖2 ≤ O(ν2d log(T1/p)),
• ‖σ0 + · · ·+ σt−1‖2 ≤ O(T1 log(T1/p)m ), ‖σlast + · · ·+ σt−1‖ 2 ≤ O(T0 log(T1/p) m ) • ‖∆0 + · · ·+ ∆t−1‖2 ≤ O(α2T1 log(mT1/p)) and ‖∆last + · · ·+ ∆t−1‖2 ≤ O(α2T0 log(mT1/p)) • ‖ξ0 + · · ·+ ξt−1‖2 ≤ O(ν2dT1 log(T1/p)) and ‖ξlast + · · ·+ ξt−1‖2 ≤ O(ν2dT0 log(T1/p)).
We call this probabilistic event EventdoubleT1,T0(w0) and Pr[Event double T1,T0(w0)] ≥ 1− p/2.
The proof is a direct corollary of Lemma 3.2, by combining events EventsingleT1 (w0), Event single T0 (w0),
EventsingleT0 (wT0), Event single T0 (w2T0) and so on. The next lemma is a simple corollary by repeatedly applying Lemma 3.3. It proves Theorem B.1a.
Lemma B.3 (modified from Lemma 3.3). Denote by C1 = log(T1/p) and C2 = α2 log mT1p + log(T1/p) m . Suppose η ≤ 0.01 min{1, 1 C2 }, T0 = 1100η(1+√C2) and T1 ≥ T0. We start from w0 and apply Algorithm 3. Under event EventdoubleT1,T0(w0), it satisfies
f(w0)− f(wT1) ≥ 0.7η T1−1∑ t=0 ( ‖∇f(wt)‖2 − η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) The next lemma can be easily derived from Lemma 3.5.
Lemma B.4 (modified from Lemma 3.5). Suppose
R = Θ( δ√
C1 log(δ3/ηC2) ) and ν2 = Θ(C2 log
δ3
ηC2 )
Suppose η ≤ 0.01 min{1, δ 3
C2 }, T0 = 1100η(1+√C2) and T1 = Θ( 1 ηδ
log δ 3
ηC2 ) ≥ T0. Let w0 ∈ Rd be any
point in the space and suppose λmin(∇2f(w0)) ≤ −δ for some δ ≥ 0. Given two coupled sequences defined as before, under events EventdoubleT1,T0(w a 0) and Event double T1,T0(w b 0), we have with probability at least 0.98
max { f(wa0)− f(waT1), f(w b 0)− f(wbT1) } ≥ 0.5η
T1−1∑ t=0 ( −η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) + Ω(
δ3
C1 log 3 δ3
ηC2
)
Lemma B.4 directly proves the second half of Theorem B.1c, because given two coupled sequences with the same marginal distribution, we have
Pr[f(wa0)− f(waT1) ≥ X] ≥ 1
2 Pr[max
{ f(wa0)− f(waT1), f(w b 0)− f(wbT1) } ≥ X]
Proof of Lemma B.4. Our choice on r and R satisfy the requirement of Lemma 3.5. Suppose without loss of generality that the wat sequence leaves w0 by more than R. Let T a1 be the first iteration t ≤ T1 in which ‖wat − wa0‖ ≥ R.
‖waT a1 − w a 0‖2 = η2‖∇f(wa0) + · · ·+∇f(waT a1−1) + Ξ a 0 + · · ·+ ΞaT a1−1 + ξ a 0 + · · ·+ ξaT a1−1‖ 2
≤ O(η2T1) T a1−1∑ t=0 ‖∇f(wat)‖2 +O(C2η2T1) +O(C1η2ν2T1d)
Combining this with Lemma B.3, we have f(wa0)− f(waT a1 ) ≥ 0.5η T a1−1∑ t=0 ( ‖∇f(wat)‖2 − η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) + ‖waT a1 − w a 0‖2 100ηT1
≥ 0.5η T a1−1∑ t=0 ( ‖∇f(wat)‖2 − η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) + R2 100ηT1
Combining this with Lemma B.3 again but for the remainder iterations, we have
f(wa0)− f(waT1) ≥ 0.5η T1−1∑ t=0 ( ‖∇f(wat)‖2 − η ·O(C2 + (C2)1.5)−O(C1ν2η(d+ √ C2)) ) + R2 100ηT1
In fact, the above same proof of Lemma B.4 also implies Theorem B.1b. These together finish the proof of Theorem B.1.

heading: C MORE ON EXPERIMENTS
text: We conduct experiments on training a residual network ResNet-20 He et al. (2016) on the CIFAR-10/100 image classification tasks Krizhevsky et al. (2014).

heading: C.1 SETTING AND IMPLEMENTED METHODS
text: In all of our experiments, we use 10 workers and mini-batch size 10 per worker. Given any attacker and any defender algorithm, we run SGD three times for 140 epochs, each time with a different initial learning rate η ∈ {0.1, 0.2, 0.4}.7 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 (each corresponding to a different initial learning rate).
We use standard data augmentation (random crops, random flips, and channel normalization).
We compare against Geometric Median Chen et al. (2017), Coordinate-wise Median Yin et al. (2018; 2019), Krum Blanchard et al. (2017), and Zeno Xie et al. (2018b) with attacks. We set α = 0.4 so there are 4 Byzantine workers. (This exceeds the fault-tolerance of Krum, and so we also tested Krum with only 3 Byzantine workers.) We formally define those prior works as follows.
Definition C.1 (GeoMed Chen et al. (2017)). The geometric median of {y1, ..., ym}, denoted by geo med{y1, ..., ym}, is
geo med{y1, ..., ym} := arg miny∈Rd ∑m i=1 ‖y − yi‖
In our experiments, we choose the geometric median from set {y1, ..., ym}. Definition C.2 (coordinate-wise median Yin et al. (2018; 2019)). Coordinate-wise median g = med{y1, ..., ym} is defined as a vector with its k-th coordinate being g[k] = med{y1[k], ..., ym[k]} for each k ∈ [d], where med is the usual (one-dimensional) median. Definition C.3 (Krum Blanchard et al. (2017)).
KR{y1, ..., ym} := yk where k = arg min i∈[m] ∑ i→j ‖yi − yj‖2
and i→ j is the indices of them−b−2 nearest neighbours of yi in {y1, ..., ym}\{yi} by Euclidean distances.
Note that Krum requires 2b + 2 < m. So, we 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)).
Zenob{y1, ..., ym} = 1
m− b m−b∑ i=1 ỹ(i)
where {ỹ(i) : i ∈ [m]} are the gradient estimators with the m − b highest “scores”, and the so-called stochastic descendant score for any gradient estimator u, based on the current parameter x, learning rate η, and a constant weight ρ > 0, is defined as:
Scoreη,ρ(u, x) = fr(x)− fr(x− ηu)− ρ‖u‖2
fr(x)− fr(x− ηu) is the estimated descendant of the loss function and ρ‖u‖2 is the magnitude of the update.
In our experiments, we let fr(x) be the estimated objective over a mini-batch of size nr = 10 (so the time to perform this estimation is on the same magnitude as the gradient evaluation for each individual worker). We also chose ρ = 0.0005 (and this value does not affect our experimental results by much).
Safeguard SGD. Our Algorithm 1 is stated in a way to make our theoretical proofs as clean as possible. Here, we discuss how we actually implement it in practice.
First of all, as common in the literature, we omit the Gaussian noise ξt that is added for theoretical purpose, and instead rely on the natural noise in the training process to 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 a universal window size T = 3 epochs, and for our algorithm with double safeguards we have used window sizes T0 = 1 epoch and T1 = 6 epochs. We also provide an automatic empirical process to select safeguard thresholds and eliminate bad workers.8 The process to determine Amed (and likewise for Bmed) is described as follows. In each iteration, for every worker i ∈ [m], we sort { ‖Ai − Aj‖ } j∈[m] and pick the smallest dm/2 + 1e-th entry, and let this number be the “score” for worker i. We select the worker with the smallest “score” as Amed and call its “score” S. Then, we use 1.5 min{S, 5} as the safeguard threshold for this iteration. Namely, we declare any worker j satisfying
7Recall a typical suggested initial learning rate is 0.1 for training ResNet with SGD+momentum; since we are using SGD without momentum, the initial learning rate can be appropriately enlarged.
8In our first version of the paper, we pre-run the algorithm for 20 epochs to determine safeguard thresholds; in the newer version, we have avoided the pre-run.
‖Aj −Amed‖ ≥ 1.5 max{S, 5} as a bad worker.9

heading: C.2 EXPERIMENT RESULTS BY ATTACKS
text: The ideal accuracies are 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 attack at a time.
C.2.1 VARIANCE ATTACK
We begin by looking at 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 a factor β 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 an 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 the attackers’s values stay within population variance. (See (Baruch et al., 2019, Algorithm 3) for a precise description. Our β is zmax in their notation.) We implement this strategy coordinate-wise, the same way as they did. Their work observes that the shift β 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 values are statistically indistinguishable from a regular execution in a single iteration.
In our setting, for 10 total nodes and α = 0.4, β is upper bounded by 0.3 (following the classic tables for the cumulative normal). We also ran the same attack in the setup from their paper (50 nodes total, of which 24 are Byzantine, which allows β ∼ 1.5) and observed a similar outcome. Results for this experiment are given in Figure 3.
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”Amed (at a “linear” rate, recall Figure 2(a)), and therefore will eventually exceed the threshold and be marked as 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 ‖Ai−Aj‖ among good workers i, j ∈ good are between 5.3 and 6.3, but the pair-wise distance between a good and a bad worker is at least 12.5.

heading: C.2.2 SIGN-FLIPPING ATTACK
text: We next move onto the sign-flipping attack. Recall that, in a sign-flipping 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 a 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 − Aj‖ for a good worker j ∈ good is at most 6.9, but for a bad
9This process appears a little different from Algorithm 1, but a similar proof also holds for this new empirical process. The constant factor 1.5 requires no tuning, and the constant threshold 5 is chosen so that the stochastic gradient of batch size 500 at random initialization has Euclidean norm no more than 5.
worker j 6∈ good it can be more than 11.) In contrast, prior work Zeno completely fails because locally at a training step, using merely nr = 10 samples to evaluate the objective, it is statistically not possible to even distinguish if the sign of the stochastic gradient is flipped or not. For prior works Krum and GeoMedian, although they appear to have some non-negligible performances, but they are actually no better than simply applying SGD with the naive mean of gradients from all the workers (including those from bad workers).10 Therefore, we conclude that prior works all fail to be Byzantine fault tolerant under this attack.

heading: C.2.3 DELAYED-GRADIENT ATTACK
text: Recall that, in a delayed-gradient 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 are not sufficiently malicious: they are still “correct” to certain extent albeit being delayed. The results are shown in Figure 5.
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 a significant performance loss under this attack.
It is worth noting that our single and double safe-guard algorithms do not catch any bad worker under this attack, so they simply use the “naive mean” of gradients from all the workers (including those delayed gradients from bad workers). However, there is no performance loss even if we use those delayed gradients. That is why we believe the delayed-gradient attack is not very strong, as the gradients are not sufficiently malicious.
Prior work Zeno suffers from some performance loss, because it only uses 6 workers out of 10, in which statistically only 6 × 0.6 ≈ 3 ∼ 4 gradients are correct.11 Other prior works suffer from performance loss,
10We did not include this “naive mean” algorithm in the plots for cleanness, but under the sign-flipping attack, it gives 81.4% test accuracy on CIFAR-10 and 38.3% on CIFAR-100. (This should not be surprising, since using (1 − α)m = 6 positive gradients plus αm = 4 negative gradients still gives non-negligible information about the true gradient.)
11In fact, we observed Zeno slightly favors delayed gradients, where each delay gradient is chosen with probability 63%, comparing to true stochastic gradients each chosen with probability 58%.
because they only pick one single stochastic gradient from the 10 workers, and it is sometimes even from the bad worker.

heading: C.2.4 LABEL-FLIPPING ATTACK
text: Recall that, in the label-flipping attack, each Byzantine worker computes its gradient based on the cross-entropy loss with flipped labels: for CIFAR-10, label ` ∈ {0, ..., 9} is flipped to 9 − `, and for CIFAR-100, label ` is flipped to 99− `. The results are shown in Figure 6.
From the plots, one can see that our single and double safe-guard algorithms even outperform the “ideal accuracies.” (92.4% accuracy vs “ideal accuracy” 91.7% under CIFAR-10; 69.4% accuracy vs “ideal accuracy” 68.0 under CIFAR-100.) In addition, we have found out that the safeguard algorithms did not catch any bad worker. This should not be surprising, since label-flipping (a.k.a. label smoothing) is known to be a regularization technique to actually improve test accuracy, as opposed to hurt performance.
Zeno also performs well under this attack (but it does not outperform the 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 m = 10 workers (recall Zeno picks 6 workers with the topmost scores, see Definition C.4). This explains its (minor) under-performance comparing to safeguard.
Other prior works perform significantly worse, and this should be alarming since label-flipping is one type of smoothing technique to improve test accuracy, as opposed to an actual “attack” to hurt performance.

heading: C.2.5 SAFEGUARD ATTACKS
text: Finally, in the safeguard attack that we design, Byzantine workers send negative but 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 as 0.6 in all the cases do not trigger the safe-guard conditions, while choosing a re-scale factor as 0.7 enables the algorithm to catch Byzantine workers occasionally. Our results are shown in Figure 7 (for re-scale factor 0.6) and Figure 8 (for re-scale factor 0.7).
Re-scale factor 0.6. In Figure 7, the performance of our (single and double) safeguard algorithms indeed get hurt a bit. Recall in Figure 7 the re-scale factor 0.6 is chosen to maximally impact our algorithm. The test 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.
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 can occasionally catch some bad workers (depending on the randomness and learning rate). We confirm that in the three runs of single safeguard, it catches 1, 2, 3 bad workers for CIFAR-10, and 1, 0, 0 bad workers for CIFAR-100 respectively; in the three runs of double safeguard, it catches 1, 2, 4 bad workers for CIFAR-10, and 2, 2, 2 bad workers for CIFAR-100 respectively.
Since there is a significant performance gain when our safeguard algorithms catch bad workers, this explains why safeguard algorithms in Figure 8 outperform their counterparts in Figure 7 with rescale factor 0.6. At the same time, we notice that the double safeguard algorithm has the ability to catch bad workers more easily. This is why double safeguard significantly outperforms single sageguard in Figure 8.
In contrast, all other prior algorithms perform extremely bad under this attack. To some extent, safeguard attack is even stronger than the previously proposed variance attack, since it can drag the 100-class test accuracy on CIFAR-100 for all prior defense algorithms to nearly 1%, while variance attack can only drag them down to around 10%.

heading: C.3 FULL COMPARISON TABLE
text: We also include the full test accuracy comparison table in Table 1.
safeguard(x0.7) attack 59.84 64.91 2.07 1.97 1.32 1.55 3.31

heading: C.4 ATTACK AGAINST THE CONVEX ALGORITHM OF ALISTARH ET AL. (2018)
text: We now briefly describe an attack against this algorithm. The attack specifically leverages the fact that the algorithm does not 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 ∑T t=0∇t. This maximum deviation is therefore a 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 to divergence.
Specifically, suppose 4 Byzantine workers all maliciously report their stochastic gradients multiplied by the scalar −5, and the remaining 6 good workers report their true stochastic gradients. One can verify numerically that this attacker can run for 5 consecutive epochs (say, epochs a, a + 1, a + 2, a + 3, a + 4) without being caught by the algorithm. Now,
• if a ≤ 75, within just 1 epoch of attack, the neural net weights diverge (value NAN). • if 80 ≤ a ≤ 115, this attack is applied after the first learning rate decay. Within just 1 epoch of the attack,
the objective explodes and accuracy becomes 10% (random), and within 3 epochs the algorithm diverges completely.
• if 120 ≤ a ≤ 155, this attack is after the second learning rate decay. Within just 2 epochs of attack, the accuracy drops to 11%. Later, the accuracy never recovers above 40%.

Review summaries:
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.