Zeno++: Robust Fully Asynchronous SGD
Authors: Cong Xie
Oluwasanmi Koyejo
Indranil Gupta
Venue:  (2020)
Keywords: fault-tolerance
Byzantine-tolerance
security
SGD
asynchronous

Abstract: We propose Zeno++, a new robust asynchronous Stochastic Gradient Descent~(SGD) procedure which tolerates Byzantine failures of the workers. In contrast to previous work, Zeno++ removes some unrealistic restrictions on worker-server communications, allowing for fully asynchronous updates from anonymous workers, arbitrarily stale worker updates, and the possibility of an unbounded number of Byzantine workers. The key idea is to estimate the descent of the loss value after the candidate gradient is applied, where large descent values indicate that the update results in optimization progress. We prove the convergence of Zeno++ for non-convex problems under Byzantine failures. Experimental results show that Zeno++ outperforms existing approaches.

Under review as a conference paper at ICLR 2020
+ ROBUST FULLY ASYNCHRONOUS SGD
Anonymous authors
Paper under double-blind review
ABSTRACT
We propose Zeno++, a new robust asynchronous Stochastic Gradient De- scent (SGD) procedure which tolerates Byzantine failures of the workers. In contrast to previous work, Zeno++ removes some unrealistic restrictions on worker- server communications, allowing for fully asynchronous updates from anonymous workers, arbitrarily stale worker updates, and the possibility of an unbounded number of Byzantine workers. The key idea is estimate the descent of the loss value after the candidate gradient is applied, where large descent values indicate that the update results in optimization progress. We prove the convergence of Zeno++ for non-convex problems under Byzantine failures. Experimental results show that Zeno++ outperforms existing approaches.
INTRODUCTION
Synchronous training and asynchronous training are the two most common paradigms of distributed machine learning. On the one hand, synchronous training requires, periodically, the global updates at the server to be blocked until all the workers respond. In contrast, for asynchronous training, the server updates the global model immediately after worker responds. Theoretical and experimental analysis (Dutta et al. 2018) suggests that synchronous training is more stable with less noise, but can also be slowed down by the global barrier across all the workers. Asynchronous training is generally faster, but needs to address instability and noisiness due to staleness. In this paper, we focus on asynchronous training.
We study the security of distributed asynchronous Stochastic Gradient Descent (SGD) in a centralized worker-server architecture, also known as the Parameter Server (or PS) architecture. In the PS architecture, there are server nodes and worker nodes. When combined with an asynchronous SGD approach, each worker pulls the global model from the servers, estimates the gradients using the local portion of the training data, then sends the gradient estimates to the servers. The servers update the model as soon as a new gradient is received from any worker.
The security of machine learning has gained increasing attention in recent years. In particular, tolerance to Byzantine failures (Blanchard et al. 2017 Chen et al.) 2017; Yin et al.] 2018 Feng Alistarh al. [018] Cao and Lai 2018)
et al. 2014 Su and Vaidyal 2016a b Xie al.] 2018b;
has become an important topic in the distributed machine learning literature. Byzantine failures are well-studied for the distributed systems (Lamport al.
1982a). However, in distributed machine learning, Byzantine failures have unique properties. brief, the goal of Byzantine workers is to prevent convergence of the model training. By construction, Byzantine failures (Lamport al.) 1982b) assume the worst case, i.e., the Byzantine workers can behave arbitrarily. Such failures may be caused by a variety of reasons including but limited to: hardware/software bugs, vulnerable communication channels, poisoned datasets, or malicious attackers. To make things worse, groups of Byzantine workers can collude, potentially resulting in more harmful attacks. It is also clear that as the worst case, Byzantine failures generalize benign failures such as hardware or software errors.
Unlike previous work (Damaskinos et al. 2018), we tackle Byzantine tolerance in more general scenario. The Byzantine tolerance of asynchronous SGD is challenging in this case because of:
Asynchrony. The lack of synchrony incurs additional noise for the stochastic gradients. Such noise makes it more difficult to distinguish the Byzantine gradients from the benign ones, especially as Byzantine behavior may exacerbate staleness.
Unpredictable successive updates. The lack of synchronous scheduling makes it possible for the server to receive updates from Byzantine workers successively. Thus, even in the standard scenario,

---

Under review as a conference paper at ICLR 2020
where less than half of the workers are Byzantine, the server can be suffocated by successive Byzantine gradients.
Unbounded number of Byzantine workers. For the Byzantine tolerance fully asynchronous training, the assumption of bounded number of Byzantine workers is meaningless. In Byzantine- tolerant synchronous training (Blanchard et al. 2017 Chen et al., 2017:) Yin et al.) 2018 Xic ct al. 2018b a). the servers can compare the candidate gradients with each other, and utilize the majority assumption to filter out the harmful gradients, or use robust aggregation to bound the error. However, such strategies are infeasible in asynchronous training, since there is nothing compare to or aggregate. Aggregating the successive gradients is also meaningless since the successive gradients could all be pushed by the same Byzantine worker. Furthermore, although most of the previous work Bllanchard et al., 2017 Chen et al. 2017: Yin et al. [2018] Feng et al. [2144] Suu and Vaidya 2016a bj Alistarh al.) 2018; Cao and Lai (0188) assumes a majority of honest workers, this requirement not guaranteed to be satisfied in practice.
The key idea of our approach is to estimate the descent of the loss value after the candidate gradient is applied the model parameters, based the Byzantine-toleran synchronous SGD algorithm, Zeno (Xie et al. (2018). Intuitively, if the loss value decreases, the candidate gradient is likely to result optimization progress. For computational efficiency, we also propose a lazy update.
To the best of our knowledge, this paper is the first to theoretically and empirically study Byzantine- tolerant fully asynchronous SGD with anonymous workers, and potentially an unbounded number of Byzantine workers. In summary, our contributions are:
We propose Zeno++, a new approach for Byzantine-tolerant fully asynchronous SGD with anony- mous workers.
We show that Zeno++ tolerates Byzantine workers without any limit either the staleness the number of Byzantine workers.
We prove the convergence of Zeno++ for non-convex problems.
Experimental results validate that 1) existing algorithms may fail in practical scenarios, and 2) Zeno++ gracefully handles such cases.
2 RELATED WORK
Most of the existing Byzantine-tolerant SGD algorithms focus synchronous training. Chen et al. (201)); Su and Vaidya (2016a b): Yin et al. 2018); Xie et al. (2018a) use robust statistics (Huber) 2011) including the geometric median, coordinate wise median, and trimmed mean Byzantine- tolerant aggregation rules. Blanchard et al. (2017); Mhamdi et al. (2018) propose Krum and its variants, which select the candidates with minimal local sum of Euclidean distances. Alistarh et al. (2018) utilize historical information to identify harmful gradients. Chen et al. (2018) use coding theory and majority voting to recover correct gradients. Most of these synchronous algorithms assume that most of the workers are non- Non-Byzantine. However, in practice, there are no guarantees that the number of Byzantine workers can be controlled. Xie et al. (2018b); [Co and Lai (2018) propose synchronous SGD algorithms for unbounded number of Byzantine workers.
Recent years have witnessed an increasing number of large-scale machine learning algorithms, including asynchronous SGD (Zinkevich et al. 2009 Lian et al. 2018 Zheng et al. 2017 Zhou jet al. 2018). Damaskinos et al. (2018) proposed Kardam, which to our knowledge is the only prior work to address Byzantine-toleram asynchronous training. Kardam utilizes the Lipschitzness of the gradients to filter out outliers. However, Kardam assumes a threat model much weaker than ours. The major differences in the threat model are listed follows:
Verification of worker identity. Unlike Kardam, we do not require verifying the identities of the workers when the server receives gradients. Kardam uses the so-called empirical Lipschitz coefficient, to test the benignity of the gradient sent by specific worker. Such mechanism keeps the record the empirical Lipschitz coefficient of each worker. Thus, whenever a gradient is received, the Kardam server must be able to identify the identity/index of the worker. However, since Byzantine workers can behave arbitrarily, they can fake their identities/indices when sending gradients the servers. Thus, Kardam assumes threat model much weaker than the traditional
2

---

Under review as a conference paper at ICLR 2020
Byzantine failure/threat model. Note that for synchronous training, the server partially counter the index spoofing attack by simply filtering out all the gradients with duplicated indices. However, such an approach is infeasible for asynchronous training.
Bounded staleness of workers/imit of successive gradients. Unlike Kardam, we do not require bounded staleness of the workers. Kardam requires that the number of gradients successively received from a single worker is bounded above. To be more specific, on the server, any sequence of successively received gradients of length 2q + must contain least + gradients from honest workers. However, in real-world asynchronous training, such an assumption is very difficult to satisfy.
A majority of honest workers. Unlike Kardam, we do not require majority of honest workers. Kardam requires that the number of Byzantine workers is less than one-third of the total number of workers much stronger restriction than the standard setting that allows for the number of Byzantine workers to be up to 50% of the total number of workers. Zeno++ further extends this guarantee to allow for not only 50%, but also majority of Byzantine workers.
3 MODEL
We consider the following optimization problem: mingeR Fxx), where F(x)
m Eiemm] ff 24), for Vi [m]. 23 is sampled from the local data D; on the ith device.
We solve this problem in a distributed manner with m workers. Each worker trains the model on local data. In each iteration, the äth worker will sample n independent data points from the dataset D,
and compute the gradient of the local empirical loss (z n شي= f(x; 2, Vi E [m], where ZiJ ~ Dj the jth sampled data on the ith worker. When there are no Byzantine failures, the servers update the model whenever new gradient is received:
Σ V(( 1,1 E [m].
F++1 Tt TeTr: 9T
n
jE(m)
When there are Byzantine failures, 9r can be replaced by arbitrary value (Damaskinos et al. 2018). Formally, we define the threat model as follows.
Definition 1. (Threat Model). When the server receives gradient estimator 9-. it is either correct or Byzantine. If sent by Byzantine worker, År assigned arbitrary value. sent by an honest worker, the correct gradient is n - Vs(rri 2.s, 1, E [mi]. Thus, we have
- arbitrarry value, gr -==1 Σ V
sent by Byzantine worker, [m]. otherwise.
We assume that q out of m workers are Byzantine, where S m. Furthermore, the indices of Byzantine workers can change across different iterations.
Table 1: Notation
Notation
Description
m, m...
Number of workers, set of integers [I.... ., m number Byzantine workers
D.. S
D, is the training dataset the vth worker, S is the validation dataset Zeno++ + server
n. nl
Mini-batch size of workers, mini-batch size of Zeno++ server
T. Y.
Number of global iterations, index of global iteration, learning rate
k
Hyperparameter of Zeno++, & is the maximum delay of also called "server delay"
hw
Maximum delay workers, also called "worker delay", different from the "server delay"
All the norms in this paper are ln-norms
4
METHODOLOGY
In this section, we introduce Zeno+t, a Byzantine-tolenan asynchronous SGD algorithm based on inner-product validation. Zeno++ is computationally efficient version of its prototype: Zenot.
4.1 ZENO+
Like Zeno (ie et al. 2018b), we compute a score for each candidate gradient estimator by using the stochastic zero-order oracle. However, in contrast the existing synchronous SGD with majority-
3

---

Under review as a conference paper at ICLR 2020
based aggregation methods, need hard threshold to decide whether gradient is accepted, as sorting is not meaningful in asynchronous settings. This descent score is described next.
Definition 2. (Stochastic Descent Score Xie et al. 2018b)) Denote fa(z) = 1 Ej= fx;; 2z), where 2j are i..dd samples drawn from S, where S F D2 Vi E [m]] and n. is the batch size of fa()). For any gradient estimator (correct or Byzantine) 9. model parameter æ, learning rate 7/s and a constant weight > O, we define its stochastic descent score as follows:
Score,,plg.20
fz(z) fa(x 79) -ll91
Remark 1. Note that we assume that the dataset S for computing fa(+) is different from the training dataset, e.g., can be a separated validation dataset. In other words, S + D1 ... # Dm # U D;.
The score defined in Definition is composed two parts: the estimated descent of the loss function, and the magnitude of the update. The score increases when the estimated descent of the loss function, fz(2) - fz 7g), gets larger. We penalize the score by -pllg|1 so that the change of the model parameter will be too large. A large descent suggests faster convergence. Observe that even when gradient is Byzantine, small magnitude indicates that it will be less harmful to the model.
Using the stochastic descent score, we can set hard threshold parameterized by filter out candidate gradients with relatively small scores. The detailed algorithm is outlined in Algorithm |
Algorithm Zeno+
Server:
1: Zo rradd))
Initialization
2: repeat
3: Randomly sample 2, S, Vj [n,] to compute fo (Note: 8 8 Dj + ... Dm)
4: Receive /j from an arbitrary worker
5: Normalize g = cÿ such that |- [V
6: if Score,,, Tz-1) 2 -y then
7:
21 c It-1 ng..tttt
8: end if
9: until Convergence
Worker = ...., =I,..., m:
1:
function WORKER (HONEST)
2: repeat
3: Pull z, from the server
4: Draw random samples ži,j ~ D,, Vj E [m]. compute ğ + 1 E)j(m)) (f(Tr
5: Push to the server
6:
until Convergence
7:
end function
4.2 ZENO++
Calculating the stochastic descent score for every candidate gradient can be computationally expen- sive. To reduce the computation overhead, we approximate it by its first-order Taylor's expansion.
Definition 3. (Approximated Stochastic Descent Score) Denote fa(x) + E`= (x; Zz). where 2j are i.i.d. samples drawn from S, where S + 'D, Vi [m], and n, the batch size of fo(.). For any gradient estimator (correct or Byzantine) model parameter learning rate and a constant weight > O, we approximate its stochastic descent score as follows:
Score-,p(g,.1 7 (V), 9) p||g11?
In brief, Zeno++ is computationally efficient version of Zeno+ which uses this approximated stochastic descent score, combined with lazy updates. The detailed algorithm is shown in Algorithm 2 Compared Zeno, we highlight several new techniques in Zeno++ (Algorithm 2). specially designed for asynchronous training: 1) re-scaling the candidate gradient (Line 6); 2) first-order Taylor's expansion (Line 7); 3) hard threshold instead of comparison with the others (Line 7); 4) lazy update for reducing the computation overhead (Line 9).
Before moving forward, wish to highlight several practical remarks for Zenot+:
4

---

Under review as a conference paper at ICLR 2020
Preparing the validation dataset for Zeno++: The dataset S used for calculating (the validation gradient of Zeno++) can be collected in many ways. can be a separate validation dataset provided by trusted third party. Another reasonable choice is that, group of trusted workers can upload local data perturbed by additional noise (to help protect the users' privacy). Typically, the validation dataset is small and different from the training dataset, thus only be used to validate the gradients, and cannot be directly used for training, as shown in Section
Scheduling ZenoU' triggered when the global model n2 is updated and the server is idle. Another scheduling strategy is to trigger ZenoU pdater(x) after every k iterations. Thus, k is the upper bound of the delay of v. reasonable choice is k m, so that ideally is updated after all the m workers respond.
(enot'pdater(11)) pdater(<): ZenoU Kenol/pdater(1) pdater(x) updates in the background. It will only be
Computational efficiency:
can reduce the computation overhead of the Zeno++ server by decreasing the mini-batch size nas the frequency of the activation of RenooUpaleerle However, doing so will potentially incur larger noise for v, which makes trade-off.
Algorithm 2 Zeno++
Server:
1: zo < -rand(), t
Initialization
2: repeat
3: repeat
4:
Receive 7 from an arbitrary worker
5: Read with lock (v may be from old version of a: V[((E,,,
6:
Normalize cg such that l|a|| = ||ull,
7:
until 7 (v. - pllg11 -7E 1--1 79. t + ++1
8:
9:
Lazy update of v: Run non-blocking RenoUppdaeer(tn if idle, or after every i iterations
10:
until Convergence
11: function ZENOUPDATER(c)
12:
Randomly sample 2, ~ S, Vj E [ng] to compute fa (Note: S 8 D1 X .... Dm)
13: Write with lock: t (z) 1 ΣE= 2f(=;z))
14:
end function
Worker = 1,...,, m:
1: function WORKER (HONEST)
2: repeat
3: Pull xt from the server
4: Draw random samples 2. D,, Vj [m]. compute 1/2 Eje(() (f())4)))
5:
Push the server
6:
until Convergence
7:
end function
THEORETICAL GUARANTEES
In this section, we prove the convergence Zenot+ (Algorithm) 2 under Byzantine failures. We start with definitions used in the convergence analysis.
Definition 4. (Smoothness) Differentiable (x: satisfies L-smoothness if there exists L such
that Vx. fV) f(x) < ( 2), x) f z1|2.
Definition 5. (Polyak-Lojasiewel) (PL) inequality) Differentiable f(z) satisfies the PL inequal- ity PPllykk 1963) if there exists μ > 0, such that Vx: f(x) - f(x.) S [[))(2
CONVERGENCE GUARANTEES
We prove the convergence of Algorithm 2 for non-convex problems with the following assumption. Assumption 1. (Bounded server delay) For Zeno++, assume that the delay of the validation gradient is apper-bounded. Without loss of generality, suppose the current model is I, and (x)()) where T S We assume that for Vl, k.
5

---

Under review as a conference paper at ICLR 2020
Remark 2. + does not require bounded delay for the workers. The bounded delay requirement in Assumption is only for the validation gradient e on the server, not for the workers.
We first analyze the convergence of functions that satisty the PL inequality.
Theorem 1. Assume that F(x) and fa(a) are L-smooth and satisfy the PL inequality Assume that for Va. the correct gradients and validation gradients are upper-bounded: [[VF(z)]] S V1 fx(])l] < V1, and the validation gradients are always non-zero and lower-bounded:
(r) 2 V2, where O < V/2 S V1. Furthermore, we assume that the validation set is close to the training set, which implies bounded variance: E [[IV [VF())]]* S V3, Va, Taking
avFV, after I global updates, Algorithm converges to a global optimum: 7 < min(1, 7.) and 2 3u12
E (((ET)-F((zz) s (1-av7)² [F(ao) F(x.)) + O(K2 + V3+
Remark 3. The assumption of the lower bounded gradient [Vf2())]I* 2 V22 necessary. We need fz(z)) * O, so that the normalization in Line 6 and inner product in Line 7 of Algorithm 3 are feasible. In practice, if we have a mini-batch with zero gradient fa (z) = 0 on server, we can simply draw additional samples and add them the mini-batch until such gradient is non-zero.
For general smooth but non-convex functions, we have the following convergence guarantee.
Theorem 2. Assume that F(x) and (z) are L-smooth and potentially non-convex, Assume that for Vr, the true gradients and validation gradients are upper-bounded: [[V = V1, [f((())
[[ 2 V2, where 0 1/2 I V1. Furthermore, we assume that the validation set is close to the training set, which implies
V1, and the validation gradients are always non-zero and lower- bounded:
bounded variance: E [.) [=))]]] S
V3. Vx. Taking
< minn(1 +)
and 2
avVV
V/
after global updates, AlgorithmP
2 converges to a critical point:
E
Eierry [V((==))
E [F((z)) F(x+)] VO + +V
T
Furthermore, if we take 7 1
L.T then we have
Dee VF(( DIP
SO (-117)
Remark 4. controls the trade-off between the acceptance ratio and the convergence rate. Large positive p makes the convergence faster. but fewer candidate gradients pass the test of Zeno+ Small positive increases the acceptance ratio, but may also potentially slow down the convergence or incur larger variance. We makes p larger, which improves the convergence rate, but also enlarges the variance. Using non-zero e potentially results in negative thresholds, which enlarges the acceptance ratio, but also increases the false negative ratio (the ratio of Byzantine gradients that are not filtered out by Zeno++).
to bridge p to the convergence rate and the variance. Larger
6 EXPERIMENTS
In this section, we evaluate the proposed algorithm, Zeno++. Note that we do not evaluate the prototype algorithm Zenot, since its computation overhead too large for practical settings. Due to the space limitation, zoomed figures and additional experiments (including evaluation on an additional label-flipping attack, and testing the sensitivity to hyperparameters) are presented in the appendix.
6.1 DATASETS AND EVALUATION METRICS
We conduct experiments on the benchmark CIFAR-10 10 image classification dataset (Krizhevsky and Hinton 2009), which is composed of 50k images for training and 10k images for testing. We use a convolutional neural network (CNN) with convolutional layers followed by 2 fully connected layers. The detailed network architecture can be found in our submitted source code (will be released upon publication). the 50k images for training, we randomly extracted 2.5k them as the validation set for +, the remaining are randomly partitioned onto all the workers. In each experiment, we launch 10 worker processes. We repeat each experiment 10 times and take the average. Each experiment is composed of 200 epochs, where each epoch is full pass of the training dataset. We simulate asynchrony by drawing random delay from a uniform distribution in the range of [0, km], where kn is the maximum worker delay (different from the maximum server delay k of Zeno++).

---

Under review as a conference paper at ICLR 2020
We top-1 accuracy the testing set and the entsspy loss function the training the evaluation metrics. We also report the false positive rate (FP), which is the ratio of correct gradients that are recognized as Byzantine and filtered out by Zeno++ or the Kardam baseline.
6.1.1 BASELINES
We use the asynchronous SGD without failures/attacks as the gold standard, which is referred to as AsyneSGD without attack. Since rdam is the only previous work on Byzantine-tolerant asynchronous SGD, we use it as the baseline.
One may conjecture that Zeno+- is analogous training on the validation data. To explore this, we consider training only on S assumed to be clean data on the server, i.e., update the model only using v V (2r) on the server, without using any workers. We call this baseline Server-on We fine-tune the learning rate and show the best results of Server-only.
6.2 No ATTACK
We first test the convergence when there are no attacks. In all the experiments, we take the learning 0.002, 0.1, = 10. For Kardam, take = (i.e. here Kardam assumes that there are Byzantine workers). The result shown in Figure I] Zeno++ converges little bit slower than AsyneSGD, but faster than Kardam, especially when the worker delay is large. When kw = 10, Zeno+ converges much faster than Kardam. Server-only performs badly on both training and testing data.
rate 0.1, mini-batch size 71, 128,
MayreSDD whout stack
MsyneBCD wihhuut Kardam, FP-5777
eegunocy
Kardam, FP-30.8
Panoes, FPu47
Top uoo
Looe
Zenos- FPu4B4
only
only
50
108
158
50
130
150
53
102
150
103
153
Gital Esech
Gobel Epach
Gotal
Global Epoch
(a) Top-1 accuracy on (est-(b) Cross entropy train-(c) Top-1 accuracy test-(d) (d) Cross entropy on train- ing set, k.
ing set, kw.
5.
ing set, K.
10.
ing set, kw 10.
Figure 1: Convergence without attacks, with different maximum worker delays kin- P = 0.002, 0.1, k = 10 for Zeno++. FP refers to the fraction of false positive detect ions i.e. incorrect prediction that a message is Byzantine.
6.3 SIGN-FLIPPING ATTACK
We test the Byzantine-tolerance to the "sign-flipping" attack, which was proposed in Damaskinos et al. (2018). In such attacks, the Byzantine workers send - instead the correct gradient fz to the server. In all the experiments, we take the learning rate 0.1, mini-batch size n, 128, = 0.002, = 0.1, l 10. The result is shown in Figure 2 with different number of Byzantine workers q. It is shown that when q = 4, Zeno++ converges slightly slower than AsyneSGD without attacks, and much faster than Kardam. Actually, we observe that Ka Kardam fails to make progress when the worker delay is large. When the number of Byzantine workers gets larger (q 8), the convergence of + gets slower, but it still makes reasonable progress, while AsyneSGD and Kardam fail. Note that Kardam performs even worse than Server-only. which means that Kardam is not even as good as training on single honest worker. Thus, when there are Byzantine workers, distributed training with Ka rdam meaningless.
6.4 DISCUSSION
Kardam performs surprisingly badly in our experiments. The experiments in Damaskinos al. (2018) focus on dampening staleness when there are no Byzantine failures. For Byzantine tolerance, Damaskinos et al. (2018) only reports that Kardam filters out 100% of the Byzantine gradients, which matches the results in our experiments. However, we observe that addition to filtering out 100% of the Byzantine gradients, Kardam also filters nearly 100% of the correct gradients. In Figure

---

Under review as a conference paper at ICLR 2020
08
AsyrrSGD atack
AayneSED shack
Asyro830
AayneSGD
Kardam, FP-98.5
Lose
Kardam, FP-53d
00rooe, FP-47
Peross, FP-55.7
802
Server only
80.3
Server only
50
100 Epoch
156
130
15)
Global
Global
Oktel Epoch
(a) Top-1 accuracy on test-(b) Cross entropy train-(c Top-1 accuracy test- (d) Cross entropy train-
ing set, kw
5. ing set, kiw 5.
ing set, Aiw
15, q ing set, Ai 15, g
Mayre93D whohu stack
MsyneBCD wihhout slack
Asyr:S3D
AsyneSCD
Kardem, FP:9677
Bood 19
Kardam, FP:EBd
Zonou,,
Zenos. FP-615 Sevvr-nnly
Server only
50
108
158
56
100
130
13
100
150
50
130
153
Gital Escch
Gibci Eprch
Gobal
Gibbl Epoch
(e) Top-1 accuracy on (f) Cross entropy train-(g) (g) Top-1 accuracy test- (h) Cross entropy on train- 15, 8. ing set, kw 15.
ing set, kw = ing set, k = 8. ing
Figure 2: Convergence with sign-flipping attacks with different maximum worker delays k For any correct gradient g. if selected to be Byzantine, will be replaced by - 10g. E {4, 8} out of the 10 workers are Byzantine. = 0.002, = 0.1, k = 10 for Zeno+ FP refers to the fraction of false positive detect ions i.e. incorrect prediction that message is Byzantine.
report that the false positive rate Ka Kardam is nearly 99%, which makes the convergence extremely slow. To make things worse, Kardam does not even perform as good as Server-only, which makes the distributed training with Kardam totally meaningless. One reason why Kardam performs badly is that we use more general threat model in this paper, which does guarantee an important assumption of Kardam, namely "any sequence of successively received gradients of length 2g + 1 must contain at least q + gradients from honest workers". It is clear that this assumption is quite strong, as in an asynchronous setting, Byzantine workers can easily send long sequences of erroneous responses. Our approach does not depend on such strong assumption.
In all the experiments, Zeno++ converges faster than the baselines when there are Byzantine failures. Although the convergence of Zeno++ is slower than AsyrcSGD when there are no attacks, we find that it provides reasonable trade-off between security and convergence speed. In general, larger worker delay kw and more Byzantine workers q add more error and noise to the gradients, which slows down the convergence, because there are fewer valid gradients for the server to use. Zeno++ can filter out most of the harmful gradients at the cost of FP x 50%.
Note that Server-on] ly is extreme that only uses the server and the validation dataset to train the model in a non-distributed manner, which will not be affected by Byzantine workers. However, only using the validation data not enough for training, shown in Figure Similarly in practice, we can use small dataset separated from the training data for cross-validation but will never directly train the model only on such validation dataset. Furthermore, as shown in Figure 2 Zeno++ performs much better than Server-one Zenott is efficiently training the model on the honest workers in a distributed manner, which not equivalent to training on the validation dataset only.
Thus, we can draw to the conclusion that
On average, the server computes 1h, 12.8 gradients in each iteration, since the validation gradient of Zeno++ is updated after every & = 10 iterations. Thus, the workload on the server is much smaller than worker. Furthermore, since we can parallelize the workload on the server and workers, the computation overhead of can be hidden, so that Zeno++ can benefit from distributed training.
7 CONCLUSION
We propose novel eyrantine-toleran fully asynchronous SGD algorithm: Zeno++. The algorithm provably converges. Our empirical results show good performance compared to previous work. In future work, will explore variations of our approach for other settings such federated learning.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
D. Alistarh, Z. Alu, and J. Li. Byzantine stochastic gradient descent. 1PXiv:1803008111 2018.
arXiv preprint
Blanchard, R. Guerraoui, J. Stainer, al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pages 118-128, 2017.
X. Cao and L. Lai. Robust distributed gradient descent with arbitrary number of byzantine attackers. 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6373 6377,
L. Chen, H. Wang, Z. B. Charles, and D. S. Papailiopoulos. Draco: Byzantine-resilient distributed training via redundant gradients. In ICML., 2018.
Y. Chen, Su, and J. Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. POMACS, 1:44:1-44:25, 2017.
G. Damaskinos, E. M. E. Mhamdi, R. Guerraoui, R. Patra, and M. Taziki. Asynchronous byzantine machine learning. arXiv preprint arXiv:1802.07923 2018.
Dutta, G. Joshi, S. Ghosh, Dube, and P. Nagpurkar. Slow and stale gradients can win the race: Error-runtime trade-offs in distributed sgd. In A/STATS, 2018.
J. Feng, H. Xu, and S. Mannor. Distributed robust learning. arXiv preprint arXiv:1409.5937, 2014.
P. J. Huber. Robust statistics. In International Encyclopedia of Statistical Science, pages 1248-1251 Springer, 2011.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.
L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382 1982a.
L. Lamport, R. E. Shostak, and M. C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4:382-401, 1982b.
X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.
Merity, N. Keskar, and R. Socher. Regularizing and Optimizing LSTM Language Models. arXiv preprint 17Xiv:1708.02182, 2017.
S. Merity, N. S. Keskar, and R. Socher. An Analysis of Neural Language Modeling at Multiple Scales. arXiv preprint arXiv: 08240,, 2018
E. M. E. Mhamdi, R. Guerraoui, and Rouault. The hidden vulnerability of distributed learning in 2018.
byzantium. arXiv preprint arXiv:
B. T. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki i Matematicheskoi Fiziki, 3(4):643-653, 1963.
L. Su and H. Vaidya Fault-tolerant multi-agent optimization: Optimal iterative distributed algorithms. In PODC, 2016a.
L. Su and N. H. Vaidya. Defending non-bayesian learning against adversarial attacks. arXiv preprint arXiv:1606.0888 08883, 2016b.
C. Xie, O. Koyejo, and I. Gupta. Phocas: dimensional byzantine-resilient stochastic gradient descent. arXiv preprint arXiv: 1XX5:1880500682 2018a.
C. Xie, O. O. Koyejo, and Gupta. Zeno: ceanntiin--usppcioo stochastic gradient descent. CoRR, abs/1 Abs/1805.11g 005.800.1100 10032, 2018b.
D. Yin, Y. Chen, K. Ramchandran, and P. Bartlett. Byzantine-rofe -obuust distributed learning: Towards optimal statistical rates. arXiv preprint arXiv: IrXiv:1803.0142 1803.01498, 2018.

---

Under review as a conference paper at ICLR 2020
S. Zheng, Q. Meng, T. Wang, W. Chen, N. Yu, Z.-M. Ma, and T.-Y. Liu. Asynchronous stochastic gradient descent with delay compensation. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 4120-4122 JMLR. org, 2017.
Z. Zhou, P. Mertikopoulos, N. Bambos, P. W. Glynn, Y. Ye, L.-J. Li, and L. Fei-Fei. Distributed asynchronous optimization with unbounded delays: How slow can you go? In ICML, 2018.
M. Zinkevich, J. Langford, and J. Smola. Slow learners are fast. In Advances in neural information processing systems, pages 2331 2331-2339, 2009.
10

---

Under review as a conference paper at ICLR 2020
Appendix
A PROOFS
A.1 ZENO++
We first analyze the convergence of the functions whose gradients grow quadratic function of sub-optimality.
Theorem 1. Assume that F(x) and fa(x) have L-smoothness and PL inequality (potentially non- convex). Assume that for Vx, the true gradients and stochastic gradients are upper-bounded: [V)(()) S V,, [[ < V1, and the stochastic gradients for Zeno testing are al- ways non-zero and lower-bounded: [x)
V22, where
V2 S V1. Furthermore,
we assume that the validation set is close to the training set, which implies bounded variance: 0,7Vi
(z) [[())]]]] S V3, Vx. Taking y min(1, +) and p 2 2uV2
after I global updates.
Algorithm 2 converges global optimum:
E| ((F(z))- s (1 - -av) (F(ao) F(x)))+ v +
Proof. If any gradient estimator g passes the test of Zeno+t, then we have (V ~g) I -plgg 76
where 11-1.
Thus, we have
(VF(Iz-1), -79)
+ S (VF(L)-1) -V( +
V/2 [F ( Vf. (1+
S -PP PV
S P Vi
- -77
-VFx))) Iv + +
< V/2
V/2
V F
+ + -/
7 7E.
[|VF(x=-1)
VF can be upper-b using I-smoothness and the bounded delay: |V (f -
x, 22
Again, using smoothness, taking p
av 2μV²
we have
E [F((z) F(x+)]
S F( - F(x,) (VF (z. (VE + L
Elg
2
V2
(21-1))1 + L3 -i+ L
< F( F(x,) -V
VF
Vi + ge
V2
S F(x - F(x.)
[ - +(+
PV
< 2pp V2
[F(xz-1) F(x + 70 +(+
$ < (1-a a1-a (F(r)) F(x))) + 7 + V/)+)).
By telescoping and taking total expectation, after T global updates, we have
[[F(zT) - F(x.)] s (1 - a/ - F(x.)] v o + +c).

---

Under review as a conference paper at ICLR 2020
For general smooth but non-convex functions, have the following convergence guarantee.
Theorem 2. Assume that F(z) and fz(z) are L-smooth and potentially non-convex. Assume that for Va, the true gradients and stochastic gradients are upper-bounded: [>) < V1, [. 12 S V1, and the stochastic gradients for Zeno testing are always non-zero and lower- bounded: [[)](= 2 V2, where < V22 S V1. Furthermore, we assume that the validation set close the training set, which implies bounded variance: E [IV[[(x) VF V3, Vr. aViVi
Taking y min(1, })
and p V/2
after T global updates, Algorithm converges critical
point:
E EiEr [VF
[[ - F(x.))
v OOOP + +
+
T
aVI
Furthermore, if we take
IT. then we have
E Eiery [VF
1
0
avTT
Proof. Similar to Theorem ! we have
V2
(VF(# -79) ~ [F(==))+++((( + +V+++ + +e).
Using smoothness, taking
2
a/7V/ V/2
we have
[x{)) E
+ 4 2
< F(xe-1) +
Ellg|2
1/2
S F(((-1) - P V/ VF(I + +e)
- F(x--1) - a/>>//11// VE [[ + +e).
Thus, have
[V E ( F + L +c)
0v7
By telescoping and taking total expectation, after T global updates, have
E
Eietry [V)((=))) [FF(z)) F(æ+)
+ o + vc).
T
a/TT
Furthermore, if we take
LT then we have
Every [V(
1 0
T
avTT)
A.2 ZENO+
Theorem 3. Assume that F(x) and fa(x) have L-smoothness has j-stroog convexity. Assume that for Vx, the true gradients and stochastic gradients are upper-bounded: [/VF(z)]2 < Vi, [V 12 < V1, and the stochastic gradients for Zeno testing are always non-zero and lower- bounded: f Z Vz, where 0 < V22 S V1. Furthermore, we assume that the validation set close the training set, which implies bounded variance:
S V3, Vn. a, ur² after T global updates, Algorithm converges 24V4
- F(x) (1)V)(())
Taking 7 < min(1, }) and p 2
global optimum:
B[F(xT) [(x.)) S (1 a/7)² [F(xo) [xx))) +) V1 O(V ce)
12

---

Under review as a conference paper at ICLR 2020
Proof. Using j-strong convexity, we have
nn²
(Vis(r), ~79) +
|1l1 S fa(x (1(x-19)) -
-9( -a(()) S -1llgl1 + ye.
2
Note that [V [VF(2)] 2 V/2 V. Thus, we have
(V s - ( 1122
|V[[(0)| +76 p+ un2 V22 [VF(())] +
2
Vi
Then, have
(VF(a),
(V), 79) -VF())-V((0))
- Vf((2), (V), -79) +7 - (z(())) -9)
& (V).(x). ~99) + 2 [VF(2)) - V/(())1 + 7 "11l"².
2
Taking the expectation on both sides, we have
p 2
V/2 Vi
Fz)))) > <
VF (V1 + V/)) + tye.
2
Using L-smoothness, conditional on x. we have E [F 79) F (
(Elgg)
Ellg|1
s p+ 2
V/2
[F(2))
2 (V)+ +
L
V1
+ye
2
V1
2
2
2
V2
s p +
(VF + +1)
2
Vi
Again, using p-strong convexity, we have
1 [VF))]1
F(x) - F(x.) S
2/
Thus, we have
[[ - 79) - f(xx))]x] S 1 2p p+ 1r2
V/2
[F(x) - + V/3 cc).
2
V1
Taking I;-1 x, and It = 7g. we have
112
V/2
E [[F(x)) - l(x. [|(s,)]==
< >5
2/0 p
- + 1/3) +
Take p 2 a 2
2 we have
2413
E - f(x)) )1 s (1-av7) f(==
V/3 + c).
By telescoping and taking total expectation, after global updates, we have E [F(xr) fII))
$ (1-a0 - /5 [F((o) f(x.) + 1- (1-
(1- 70(1 + v3+
S (1 - ( [(x)) + 5 0(Vi ve).
a
B ADDITIONAL EXPERIMENTS
B. No ATTACK
We first test the convergence when there are no attacks. In all the experiments, we take the learning
rate 7 0.1, mini-batch size n, 128, p 0.002, 0.1, k = 10. For Ka raam, we take
13

---

Under review as a conference paper at ICLR 2020
q 2 (Kardam pretends that there Byzantine workers). The result is shown in Figure We can see that Zeno++ converges little bit slower than AsyneSCD, but faster than Kardan, especially when the worker delay is large. When kw 10, 2eno+ converges much faster than Kardam.
0.8
2.5
Top-1 accuracy
AsyncSGD without attack Kardam, FP=80.6 Zeno++, FP=47.4
0.6
Loss
1.5
Server-only
0.4
0.5
0
100
50
150
Global Epoch
Global Epoch
(a) Top-1 Accuracy on Testing Set, max delay is 5
(b) Cross Entropy on Training Set, max delay is
0.8
AsyncSGD without attack Kardam, FP=87.7 Zeno++, FP=49.4 Server-only
Top-1 accuracy
1.5
0.6
Loss
0.44
0.2
50
100
150
50
100
150
Global Epoch
Global Epoch
(c) Top-1 Accuracy on Testing Set, max delay is 10 (d) Cross Entropy on Training Sct, max delay is 10
Figure 3: Convergence without attacks, with different maximum delays of workers. P = 0.002, c
0.1 for Zenot+.
B.2 SIGN-FLIPPING ATTACK
We test the Byzantine-tolerame to "sign-flipping attack, which is proposed in Damaskinos et al. (2018). In such attacks, the Byzantine workers send f1) instead of the correct gradient Vf(z) to the server. In all the experiments, we take the learning rate 0.1, mini-batch size size
n, = 128.
p 0.002, 0.1, 10. The result is shown in Figure 4 and with different number of Byzantine workers
B.3 LABEL-FLIPPING ATTACK
We test the Byzantine tolerance to the label-flipping attacks. When such kind of attacks happen, the workers compute the gradients based on the training data with "flipped" labels, i.c., any label (O....,9) 9}. is replaced by 9 label. Such kind of attacks can be caused by data poisoning or software failures. all the experiments, 0.002, 0.1, k 10. The result is shown in Figure 6 and with different number of Byzantine workers q.
take the learning rate y 0.1, mini-batch size n n, 128.
B.4 SENSITIVITY TO LLYPERPARAMETERS
In Figure 8 and 9 show how the hyperparameters p. c, and affect the convergence. In general, Zeno++ is insensitive to c. Larger and & slow down the convergence.
14

---

Under review as a conference paper at ICLR 2020
0.8
3
AsyncSGD without attack AsyncSGD
Top-1 accuracy
0.6
2
Loss
Kardam, FP=98.5
Zeno++, FP=47.9
Server-only
0.2
0
100
Global Epoch
Global Epoch
Top-I Accuracy on Testing Set, A...
(b) Cross Entropy on Training Set, A:.
0.8
AsyncSGD without attack
Top-1 accuracy
0.6
AsyncSGD Kardam, FP=99.8 Zeno++, FP=56.7
Loss
0.4
Server-only
0.2
50
100
150
50
100
150
Global Epoch
Global Epoch
(c) Top-1 Accuracy on Testing Set, kw = 15.
(d) Cross Entropy on Training Set, A.. 15.
Figure 4: Convergence with sign-flipping attacks, with different maximum worker delays kin- For any correct gradient g. selected to be Byzantine, & will be replaced by -10g. q out of the 10 workers are Byzantine. p = 0.002, 0.1, = 10 for Zeno+t.
0.8
3
AsyneSGD without attack AsyneSGD Kardam, FP=99.7 Zeno++, FP=52.7
Top-1 accuracy
0.6
2
Loss
Server-only
0.2
0
100
Global Epooh
Global Epoch
Top-I Accuracy on Testing Set, k.. 5.
(b) Cross Entropy on Training Set, Aiu
0.8
AsyncSGD without attack
Top-1 accuracy
0.6
AsyncSGD Kardam, FP=99.8 Zeno++, FP=60.5 Server-only
Loss
0.4
0.2
50
100
150
50
100
150
Global Epoch
Global Epoch
(c) Top-1 Accuracy on Testing Set, Aww = 15.
(d) Cross Entropy on Training Set, A: 15.
Figure 5: Convergence with sign-flipping attacks, with different maximum worker delays kin- For any correct gradient g, selected to be Byzantine, g will be replaced by -10g. q 8 out of the 10 workers are Byzantine. p = 0.002, 0.1, k = 10 for Zeno+t.
15

---

Under review as a conference paper at ICLR 2020
0.8
3
AsyncSGD without attack AsyncSGD
Top-1 accuracy
Loss
Kardam, FP=97.9 Zeno++, FP=41.1
0.4
Server-only
0.2
0
50
100
150
50
100
150
Global Epoch
Global Epoch
Top-I Accuracy Testing Set, k.. 5.
Cross Entropy on Training Set, ki.
0.8
AsyncSGD without attack AsyncSGD Kardam, FP=99.8 Zeno++, FP=48.7
Top-1 accuracy
0.6
Loss
0.4
Server-only
0.2
50
100
150
50
100
150
Global Epoch
Global Epoch
(c) Top-1 Accuracy on Testing Set, l = 15.
(d) Cross Entropy on Training Set, A:w 15.
Figure 6: Convergence with label-flipping attacks, with different maximum worker delays kw C = out of the 10 workers are Byzantine. p 0.002, 0.1, k 10 for Zeno+t.
0.8
AsyneSGD without attack AsynoSGD
Top-1 accuracy
Kardam, FP=99.8 Zeno++, FP-33.7
Loss
0.4
Server-only
0.2
50
100
150
50
100
150
Global Epoch
Global Epoch
Top-1 Accuracy Testing Set, k.. 5.
Cross Entropy Training Set, k..
0.8
AsyncSGD without attack AsyncSGD Kardam, FP=99.7 Zeno++, FP=40.5 Server-only
Top-1 accuracy
0.6
LOss
0.2
0
50
150
50
100
150
Global Epoch
Global Epoch
(c) Top-1 Accuracy on Testing Set, lig = 15.
(d) Cross Entropy on Training Set, Aig 15.
Figure 7: Convergence with label-flipping attacks, with different maximum worker delays knp & = out of the 10 workers are Byzantine. p = 0.002, 0.1, k = 10 for *eno+t.
16

---

Under review as a conference paper at ICLR 2020
200
# of global epochs
6=
150
6= 0.05
0.1
100
50
0
1
2
3
x x
P
Figure 8: Number of global epochs to reach training loss value 0.2, with sign-flipping attacks and q 4 Byzantine workers. 10 for Zeno+ P and varies.
200
# of global epochs
p= 0.001
150
0=0.00
100
50
0
5
10
15
k
Figure 9: Number of global epochs to reach training loss value 0.2, with sign-flippigg attacks and q 6 Byzantine workers. 0 for Zeno++. and varies.
17

---

Under review as a conference paper at ICLR 2020
200
# of global epochs
q=4 q-8
150
100
50
0
32
64
96
128
n
Figure 10: Number of global epochs to reach training loss value 0.7, with sign-flipping attacks and q E (4,8) Byzantine workers. p = 0.001, 0, 15 for Zeno+t. The batch size of zenott, varies.
18

---

and Under review as a conference paper at ICLR 2020
B.5 RESNET20 ON CIFAR-10
We test the Byzantine-tolerance on ResNer20 v1 CIFAR-10 dataset. We show the top-1 accuracy on the testing set.
In Figure I we show the convergence when there are no attacks. Zeno+ converges as good as we show the convergence when there are sign-flipping attacks.
AsyneSGD. In Figure
12
In Figure 13 and 14 we test Zeno++ with different types of random attacks. In Figure 13] for any correct gradient g. if selected be Byzantine, any element of will be replaced by IID random value drawn from a Gaussian distribution with 0 mean and 5 variance, while in Figure [1] any element of Byzantine g will be added by a IID random value drawn from Gaussian distribution with 0 mean and 5 variance.
0.9
Top-1 - accuracy
0.7
0.5
AsyncSGD without attack
Kardam, FP=99.9
0.3
Zeno++, FP=25.8
0.1
Sync. SGD
50
100
150
Global Epoch
Figure 11: Convergence (top-1 accuracy the testing set) without attacks, with 20 workers and maximum worker delays kw 15. p = 0.00005, e = 0, = for Zeno+t.
0.9
Top-1 1 accuracy
0.7
0.5
AsyncSGD without attack
AsyncSGD
0.3
Kardam, FP-99.7
0.1
Zeno++, FP=39.5
50
100
150
Global Epoch
Figure 12: Convergence (top-1 accuracy on the testing set) with sign-flipping attacks, with 20 workers and maximum worker delays k., 15. For any correct gradient if selected to be Byzantine, g will
be replaced by- 100g = 12 out of the 20 workers are Byzantine. p = 0.00005, = 0, = 15 for Zeno+t.
B.6 LSTM ON WIKITEXT-2
We test the Byzantine-toleran http:///hhuub.coomassssfsooreeee
LSTM-based language model. The model is from Im (Merity et al.) trained on WikiText-2 dataset. We use 600 hidden units per layer. We show the perplexity (the smaller the better) on the testing set.
19

---

Under review as a conference paper at ICLR 2020
0.9
Top-1 accuracy
0.7
0.5
AsyncSGD without attack
AsyncSGD
0.3
Kardam, FP=99.7
0.1
Zeno++, FP=43.8
50
100
150
Global Epoch
Convergence (top-1 accuracy on the testing set) with random attacks (type D), with 20 workers and maximum worker delays k. = 15. For any correct gradient g, if selected to be Byzantine, any element of g will be replaced by IID random value drawn from Gaussian distribution with mean and 5 variance. q = 12 out the 20 workers are Byzantine. p = 0.00005, 0, = 15 for Zeno+t.
Figure 13:
0.9
Top-1 accuracy
0.7
0.5
AsyncSGD without attack
AsyncSGD
0.3
Kardam, FP=99.7
0.1
Zeno++, FP=45.5
50
100
150
Global Epoch
Figure 14: Convergence (top-1 accuracy the testing set) with random attacks (type II), with 20 workers and maximum worker delays kn = 15. For any correct gradient g, if selected to be Byzantine, any element of will be added by IID random value drawn from Gaussian distribution with mean and 5 variance. 4 = 12 out of the 20 workers are Byzantine. = 0.00005, 0, k 15 for Zenott.
show the convergence when there are attacks. Zeno+ converges as good as AsynesCD, In and we show the convergence when there are sinnflipping attacks, with different number of Byzantine workers.
In Figure 15
20

---

Under review as a conference paper at ICLR 2020
160
AsyncSGD without attack
140
Kardam, FP=89.9 Zeno++, FP=11.8
Perplexity
120
100
80
50
100
150
Global Epoch
Figure 15: Convergence (perplexity the testing set) without attacks, with 10 workers and maximum 0.005, e 0.001, k 10 for Zeno++.
worker delays kw 5.
180
AsyncSGD without attack AsyncSGD Kardam, FP=99.9 Zeno++, FP=16.7
160
Perplexity
140
120
100
80
50
100 Global Epoch
150
Figure 16: Convergence (perplexity on the testing set) with sign-flipping attacks, with 10 workers and maximum worker delays k 5. For any correct gradient g. if selected to be Byzantine, g will be replaced by - 10g. q = 4 out of the workers are Byzantine. = 0.005, e 0.001, for Zeno+t.
180
AsyncSGD without attack AsyncSGD
160
Perplexity
Kardam, FP=99.9
140
Zeno+t, FP-24.5
120
100
80
50
100
150
Global Epoch
Figure 17: Convergence (perplexity on the testing set) with sign-flipping attacks, with 10 workers and maximum worker delays h 5. For any correct gradient g. if selected to be Byzantine, will be replaced by 100. q out of the 10 workers are Byzantine, p 0.005, 0.0004, 10 for Zenott.
21


Reviews:
[{"review_id": "r1gcFKXAFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper investigates the security of distributed asynchronous SGD. Authors propose Zeno++, worker-server asynchronous implementation of SGD which is robust to Byzantine failures. To ensure that the gradients sent by the workers are correct, Zeno++ server scores each worker gradients using a “reference” gradient computed on a “secret” validation set.  If the score is under a given threshold, then the worker gradient is discarded. \n\nAuthors provide convergence guarantee for the Zeno++ optimizer for non-convex function. In addition, they provide an empirical evaluation of Zeno++ on the CIFAR10 datasets and compare with various baselines.\n\nOriginality:\nI would argue that the paper novelty is limited.  Paper builds upon the Zeno algorithm.  From the paper, the main changes with respect to Zeno algorithm is the use of a hard-threshold instead of a ranking to adapt Zeno to the asynchronous case, and the use of a first-order Tayler approximation of the score to speed up its computations.\n\nClarity:\nPaper is clear and easy to follow.\n\nQuality:\nMy main concerns are related to the experimental section. Authors only report results for one model on one dataset. It is unclear how those results would transfer to different tasks and architectures. In addition, the experiments are relatively small scale (10 workers), how does the system scale as you increase the number of workers?\n\nThe top-1 reported on CIFAR10 seems pretty low with respect to the current state-of-art. It would be nice to use a more competitive model such as a Resnet-18 to verify that one can achieve similar performance with Zeno++ compared to AR-SGD (without attack).\n\nAuthors introduced Zeno++ to reduce the computation overhead over Zeno+. Did you empirically quantify this speed-up, and do you achieve similar accuracy than Zeno+?\n\nSignificance:\nAuthors only compare with asynchronous baseline. It would be nice to demonstrate the advantage of asynchronous methods over synchronous one (such as Zeno and All-Reduce SGD without attack). Can you show a speed benefit of asynchronous Zeno++ and show similar accuracy than synchronous approaches? \n\nMinor:\n-\tIt would be to reports use a log scale in Fig 1 b), c) and Fig 2. b), d).\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HkgKt242tr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 addresses security of distributed optimization algorithm under Byzantine failures. These failures usually prevent convergence of training neural network models. Focusing on the asynchronous SGD algorithm implemented with a parameter-server, the authors propose to use stochastic line search ideas to detect whether the gradients are good descent directions or not. It applies to a general scenario including repeated and unbounded Byzantine failures. \n\nTheoretical results of this paper seem to me to have some flaw. In the proof of Theorem 1, line 6, it is not clear to me why the gradient norm ||g||^2 is replaced by || grad f_s (x_tau) ||^2. Clearly the g comes from any worker which can be very different to grad f_s (x_tau). Therefore, I recommend the authors check the proof of both theorem 1 and 2 more carefully.\n\nNumerical results show that the proposed algorithm Zeno++ works well with sign-flipping attacks. However, this scenario is very limited to validate all imaginable Byzantine failures that this paper would like to address. For example, one can use random gradients instead of sign-flipped gradients as a Byzantine attack, would the algorithm still work? \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1gQx88Ctr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "\nThis paper proposes an approach to Byzantine fault tolerance in asynchronous distributed SGD. The approach appears to be novel. Theoretical convergence guarantees are provided, and an empirical evaluation illustrates very promising results.\n\nOverall, the paper is well-written and the results appear to be novel and interesting. Although I have a few questions, listed below, I generally lean towards accepting this paper.\n\n\nThe assumption of a lower bound on validation gradients is somewhat troubling, especially for over-parameterized problems where so-called \"interpolation\" may be possible. I realize that validation samples are never used explicitly for stochastic gradient updates, but the algorithm does ensure that the stochastic gradients used are similar to gradients of validation samples. If one is converging to a (local) minimizer, one wants the gradient to vanish. How do we reconcile these points? Also, to properly set $\\rho$, for the theory to be valid, one needs to know this bound (or a lower bound on $V_2$). Is this practical?\n\nThe paper claims that the computational overhead of Zeno+ is too great to evaluate for comparison with Zeno++. From my reading of the two methods, it isn't immediately obvious to me why this is the case. Including experiments which at least compare the per-iteration runtime (even if not running Zeno+ for training to completion) would make the paper more compelling. After all, Zeno++ still involves periodically evaluating the gradient at a validation sample.\n\nThe paper makes the reasonable point that it is not reasonable to assume a bounded number of adversaries in the asynchronous setting, and the theorem statements make no assumption about the number of adversaries or rate at which received gradients are from a Byzantine worker. However, there are also no guarantees about whether the algorithm will ever make progress (i.e., will line 8 ever be reached?). This should be stated more transparently in the paper. Also, I was wondering, given that a gradient has been computed on the parameter server's validation set, which is assumed to be \"clean\", why not take a step using this gradient when the test in line 7 fails?\n\nFinally, the paper titles includes SGD, but the description in Def 1 doesn't appear to involve stochastic gradients. Typical parameter server implementations have workers compute mini-batch stochastic gradients, not full gradients on their shard of the training set. Does Zeno++ need to be modified to run in this setting? Does the theory still hold?\n\n\nMinor:\n- Is there a typo in line 5 of Zeno++? Should this be $\\nabla f_s$ instead of $f_s$? Otherwise, what does it mean to take the inner product of $v$ and $g$ in line 7?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Main content:

Blind review #2 summarizes it well:

This paper investigates the security of distributed asynchronous SGD. Authors propose Zeno++, worker-server asynchronous implementation of SGD which is robust to Byzantine failures. To ensure that the gradients sent by the workers are correct, Zeno++ server scores each worker gradients using a “reference” gradient computed on a “secret” validation set.  If the score is under a given threshold, then the worker gradient is discarded. 

Authors provide convergence guarantee for the Zeno++ optimizer for non-convex function. In addition, they provide an empirical evaluation of Zeno++ on the CIFAR10 datasets and compare with various baselines.

--

Discussion:

Reviews are generally weak on the limited novelty of the approach compared with Zeno, but the rebuttal of the authors on Nov 15 is fair (too long to summarize here).

--

Recommendation and justification:

I do not feel strongly enough to override the weak reviews (but if there is room in the program I would support a weak accept).
Decision: Reject