Fast Machine Learning with Byzantine Workers and Servers
Authors: El-Mahdi El-Mhamdi
Rachid Guerraoui
Arsany Guirguis
Venue:  (2020)
Keywords: Distributed machine learning
Byzantine resilience
Fault tolerance

Abstract: Machine Learning (ML) solutions are nowadays distributed and are prone to various types of component failures, which can be encompassed in so-called Byzantine behavior. This paper introduces LiuBei, a Byzantine-resilient ML algorithm that does not trust any individual component in the network (neither workers nor servers), nor does it induce additional communication rounds (on average), compared to standard non-Byzantine resilient algorithms. LiuBei builds upon gradient aggregation rules (GARs) to tolerate a minority of Byzantine workers. Besides, LiuBei replicates the parameter server on multiple machines instead of trusting it. We introduce a novel filtering mechanism that enables workers to filter out replies from Byzantine server replicas without requiring communication with all servers. Such a filtering mechanism is based on network synchrony, Lipschitz continuity of the loss function, and the GAR used to aggregate workers’ gradients. We also introduce a protocol, scatter/gather, to bound drifts between models on correct servers with a small number of communication messages. We theoretically prove that LiuBei achieves Byzantine resilience to both servers and workers and guarantees convergence. We build LiuBei using TensorFlow, and we show that LiuBei tolerates Byzantine behavior with an accuracy loss of around 5% and around 24% convergence overhead compared to vanilla TensorFlow. We moreover show that the throughput gain of LiuBei compared to another state–of–the–art Byzantine–resilient ML algorithm (that assumes network asynchrony) is 70%.

Under review as a conference paper at ICLR 2020
FAST MACHINE LEARNING WITH BYZANTINE WORKERS AND SERVERS
Anonymous authors
Paper under double-blind review
ABSTRACT
Machine Learning (ML) solutions are nowadays distributed and are prone to various types of component failures, which can encompassed so-called Byzantine behavior. This paper introduces LIUBEI, that does not trust any individual component in the network (neither workers servers), nor does it induce additional communication rounds (on average), compared to standard non- -nnzByyaniine resilient algorithms. LIUBEI builds upon gradient aggregation rules (GARs) tolerate a minority of Byzantine workers. Besides, LIUBEI replicates the parameter server on multiple machines instead of trusting it. We introduce a novel filtering mechanism that enables workers to filter out replies from Byzantine server replicas without requiring communication with all servers. Such a filtering mechanism is based on network synchrony, Lipschitz continuity of the loss function, and the GAR used to aggregate workers' gradients. We also introduce a protocol, scatter/gather, bound drifts between models on correct servers with small number of communication messages. We theoretically prove that LIUBEL achieves Byzantine resilience to both servers and workers and guarantees convergence. We build LIUBEI using TensorFlow, and show that LIUBEI tolerates Byzantine behavior with an accuracy loss of around 5% and around 24% convergence overhead compared to vanilla TensorFlow. We moreover show that the throughput gain of LICBEI compared to another state-of the-rrrrr Byzintine-resilient MI. algorithm (that assumes network asynchrony) is 70%.
ressllet ML algorithm
INTRODUCTION
Scaling Machine Learning (ML) algorithms with existing datasets and models 21 calls for dis- tributed solutions 25 27 12). The standard distribution approach nowadays is the parameter server architecture (26). Such an architecture employs two types of machines: workers and parameter servers. Typically, workers perform the model update computation, following today's 's standard workhorse algorithm for ML: stochastic gradient descent (SGD). The parameter server updates the model in each iteration after aggregating gradients from workers. Based on this, the typical iteration execution includes two communication rounds: workers pull a model from the server, which in turn then pulls gradients from workers.
However, such a solution is prone to a various amount of failures of the distributed system components. Centralizing the parameter server in one machine makes it prone to a crash failure that can then stop the entire learning procedure. Various kinds of failures, including software bugs, hardware defects, or even hacked machines, can lead to corrupted gradients, diverging the learning process (6) 35)
Such behavior can be abstracted in the most general form of failures, namely Byzantine failures (3
modeling the very fact that a machine in the system behaves arbitrarily. Given the increasing use of ML in mission-critical applications (17 30), tolerating such failures is crucial.
Byzantine ML solutions so far mostly focused on Byzantine workers, ignoring the possibility of gradient aggregation rule (GAR) is employed by
Byzantine servers. Typically, statistically-robet the parameter server to aggregate gradients received from workers, rather than using the vulnerable averaging of gradients. Such GAR e.g., Krum (8), Median (34) is statistically proven to guarantee convergence of the learning processes even in the presence of minority of Byzantine workers, under some assumptions the correct workers.

---

Under review as a conference paper at ICLR 2020
Guan (15) is, so far, the only proposal that solves the tota Byzantine ML problem. Guan Yu uses a GAR, e.g., Bulyan (I6) for aggregating workers' gradients and Median (34) for aggregating models received from servers. Since uses GAR (i.e., Median) for aggregating models, it requires workers to communicate with a majority of servers in each iteration. Moreover, Guan assumes network asynchrony, namely that there is no bound on communication delays. But this comes with cost: First, it requires three communication rounds, instead of two in the vanilla case, and it requires an assumption on the maximum distance between parameter vectors, i.e., models at correct servers, which might be hard to obtain in certain cases. Also, Guan Yu requires a large number of compute nodes and server replicas work, as one cannot differentiate between a Byzantine machine and a slow one in such network (18).
Having a synchronous network is common in practice for many distributed environments (19 36) as practitioners can usually predict a conservative upper bound on the network delays. Assuming network synchrony allows tolerating Byzantine failures using the standard solutions of state machine replication (SMR). e.g., (2)). But SMR in the ML context raises few concerns: First, SMR requires multiple communication rounds per iteration for agreement on the current state of the model and the updating step. Given the typical sizes of models nowadays. the overhead of communication rounds is big enough to hide the effectiveness of distributing the learning task (19; 20). Second, SMR requires replicated workers that the same data batch (II) This reveals problematic in the case of using private data that cannot be shared with others (32).
In this paper, we present LIUBEI, a total rrzantine-toleraae ML algorithm that does not trust any individual component, while almost not adding any communication overhead, compared to standard non-Byzantine deployments. LIUBEI introduces a novel mechanism that filters out replies from Byzantine servers without requiring to communicate with all servers. Moreover, LIUBEI introduces a novel protocol to reduce the number of communication rounds. Essentially, LIUBEI operates in two phases: scalter and guther. In the scatter phase, servers work independently and do not communicate with each other. In the gather phase, correct servers communicate to bring their view of models back close to each other. The number of gather steps is usually very small and hence, their overhead is insignificant. We prove that LIUBEI tolerates Byzantine failures and guarantees learning convergence.
LIUBEI uses GAR to aggregate workers' gradients and hence, tolerates Byzantine gradients. Tolerating Byzantine servers relies on our filtering technique and the scatter/gather protocol; both assume network synchrony. In each iteration in the scatfer phase, each worker pulls the updated model from only one server and then uses two filters to check the legitimacy of such a model: the Lipschitz filter and the models filter. On the one hand, the Lipschitz filter checks the growth of the model with respect to its gradient. A Lipschitz value is computed for a received model, which is then compared Lipschitz values of other correct models. On the other hand, the models filter bounds the difference between models in two consecutive rounds. Based on the guarantees given by the used GAR, a worker can speculatively compute an updated model that should be close to the received model. Bounding the difference between both models allows workers to suspect whether a received model is Byzantine or not. After T scatter iterations, LIUBEI does one gather step with the goal of bringing the models correct servers back close to each other. Hence, LIUBEI does not require an assumption on the maximum distance between two correct models, as in Guan Yu (15).
We implement LIUBEI over TensorFlow to show its performance on typical workloads. We show that LIUBEI can tolerate both Byzantine servers and workers while guaranteeing convergence. We also show that LIUBEI can achieve the same performance Guan Yu, with 5% accuracy loss compared to vanilla TensorFlow. We quantify LIUBEI overhead, compared to vanilla TensorFlow, to around 24% and with a throughput gain of 70% compared to Guan Yu. Our source code is available (4). The passphrase for decrypting the code is: <FF22=+|0ODDDDAAMMLLLSSSSSS:S::: Rj.y3KfmF)
MODEL AND ASSUMPTIONS
2.1 BYZANTINE MACHINE LEARNING
The Byzantine problem was first introduced in the context of distributed services (23 in which minority of the distributed system components could behave arbitrarily. Such a behavior could be the result of software bugs, hardware defects, message omissions, or even hacked machines. Similarly, the Byzantine failure in a distributed ML system occurs when one of the components in such a
We use the total Byzantine resilience to denote resilience against both workers and parameter servers.
2

---

Under review as a conference paper at ICLR 2020
system behaves arbitrarily, i.e., not following the algorithm. For example, Byzantine machine can send a biased estimate of gradient to another machine, which leads to a corrupted learning model accordingly even learning divergence (6). Byzantine failures also abstract the data poisoning problem (Z), which happens when a machine owns maliciously labeled data (i.e., misleading data); this may result in learning a corrupted model especially-crafee crafted by the adversary. If the learning is centralized in one machine (as with the standard parameter server architecture (26)), things can go worse if such a machine is Byzantine as this case, the adversary (which hacked such a machine) can write whatever it wants to the final model, making the learning process almost useless. Such behavior should be tolerated as ML is nowadays used mission critiicl applications.
2.2 SYSTEM MODEL
We consider the standard parameter server archi- tecture (26), where a logically centralized server holds the learning parameters, and workers do the gradient computation task. In each learn- ing step, workers pull the latest version of the learning model from the parameter server and then, towards the end of the iteration, the param- eter server aggregates the gradients computed by workers and updates the model. We assume synchronous training: both the parameter server and workers synchronize their iteration num- ber. We also assume synchronous communica- tion model and therefore, we assume an upper bound on communication and computation de- lays. Thus, all machines expect a response from
Parameter Server
Worker
Network
Byzantine
Figure 1: A setup with workers (3 are Byzantine) and 4 servers (1 is Byzantine). Byzantine machines form together a single adversarial entity, where they communicate over their own covert network. other machines within this bound, and non-responding machines can be safely flagged crashing.
Unlike most of the existing work in Byzantine ML literature, we do not assume trusted parameter server. We replicate the parameter server on pps machines, among which up to fps machines could be Byzantine, i.e., behave arbitrarily, with nps 2 3fps + 1. In addition, we assume that up to fwr out of nw workers could be also Byzantine with nw 2 2 + Figure depicts such a setup.
The goal of the Byzantine nodes, be they workers or servers, is to impair the learning, by making it converge to a state different from the one that would have been obtained if no adversary had stymied the learning process. Byzantine nodes can cooperate to achieve this goal. We assume these nodes have unbounded computation power and arbitrarily fast communication channels (covert network in Figure D. We also assume these nodes have access to the full training dataset and can overhear gradients sent by the correct workers. We assume that honest nodes can authenticate the source of a prevent spoofing and Sybil attacks (10).
message
We follow the usual assumptions in the Byzantine ML literature II
(see supplementary material, Section 3.1). We assume that the training data is identically and independently distributed (iid) on workers (24) so that they can compute, at step t E N, an unbiased estimate (gt) of the true gradient L (0) (where 0 represents the learning model of size d) with sufficiently low variance.
16)
LIUBEI
In this section, describe LIUBEI algorithm. First, describe how tolerate Byzantine workers and servers, explaining our filtering technique and providing an intuition on why it works. Then, we present the training loop of both servers and workers.
3.1 TOTAL BYZANTINE RESILIENCE
Byzantine workers. Tolerating Byzantine workers is well-studied in the ML literature. Usually, the parameter server uses a statistically robust gradient aggregation rule (GAR), e.g., (34, [6) that ensures having a correct gradient despite the presence of minority of Byzantine gradients. LIUBEI can use any existing synchronous GAR that follows the robustness definition of (8, which is also formally given in the supplementary material, Section 1.1. We choose MDA (31) for our algorithm
as it gives practical resilience guarantees (supplementary material, Section 4) with a reasonable overhead confirmed in our evaluation (Section 4). MDA requires nhw 2 2ʃ. + 1.
3

---

Under review as a conference paper at ICLR 2020
Byzantine servers. Tolerating Byzantine servers using robust aggregation requires communication with all servers in each round, which results in a big communication overhead. We follow another route: We let each worker pull only one model from any of the server replicas and then checks if the pulled model is suspicious or not. A worker does this check by applying two filters on the pulled model (the Lipschitz filter and the models filter), which we describe below. If the model is suspicious, the worker discards it and pulls a new model from another parameter server. Thus, the maximum number of models that can be pulled by a worker in one iteration is fp= +1.
Lipschitz filter. Based on the standard Lipschitz continuity of the loss function assumption ( g previous work uses empirical estimations for the Lipschitz coefficient to filter out gradients (from Byzantine workers) in asynchronous learning (14). We use similar idea, yet to filter out models (on the workers' side) from Byzantine servers. The filter works as follows: Assume a worker j that owns a model o[3) and a gradient it computed 9:" based on that model at some iteration t. A correct server i should include g( while updating its model 0,9) given network synchrony. The worker then does two steps in parallel: (I) estimates the updated model locally based on its own gradient: (((( and (2) pulls a model ((4) from a parameter server i. If server is correct then, the growth of the pulled model a44 (with respect to gradients) should be close to that of the estimated local model o(((1) based on the guarantees given by the used GAR. Such growth rate is encapsulated in the Lipschitz coefficient. If the pulled model is correct then, the worker expects that the Lipschitz coefficient computed based on that model is close to those of the other correct models received before by the worker. Concretely, worker computes an empirical estimation of the Lipschitz coefficient =
| o. o/
af.)
and then, ensures that follows the condition S K, _ quantile upo pen--pp fpm [K]. where K is the list of
Rpp
all previous Lipschitz coefficients lo (i.e., with Eprev < f).
Note that such a filtering technique requires Rys > fp as Byzantine machines can craft models with Lipschitz coefficients that are deliberately placed in the first 2fp= places of the set K. Hence, the tradeoff here between the communication overhead and the required number of parameter server replicas: one can use robust aggregation of models, which requires only 1ps > 2fps yet requires communicating with all servers in each round. In our design, we strive for reducing the communication overhead as much as possible, given communication is the bottleneck (36.
Models filter. Although the Lipschitz filter can bound the model growth with respect to gra- dients, server trick this filter by sending well-crafted model that is arbitrarily far from the other correct models. To overcome this problem. LIUBEI uses another filter, which we call models filter, bound the distance between models in any two successive iterations. We assume all correct machines initialize models with the same state. Building upon the guar- antees given by the used GAR, iteration f, worker can estimate an upper bound the distance between two successive states of a correct model. Mathematically, the distance be- ((i()) and pulled model o(2) is upper- apper-bounded as follows: tween a local estimate of a model 0++1
10 - 0
TT-(t mod T) ||or-( mod Till
(3T + 2) fw)/4s_ + 2(( - mod m)-
with T 1 1/3tm., where is the Lipschitz coefficient and n/ is the learning rate at iteration t. Such bound is also based on the scatterigather scheme we are using. The details of deriving this term is in the supplementary material, Section 3.4.2.
3.2 ALGORITHM
LIUBEI's algorithm operates in two phases: scatter and gather. One gather step is executed every T iterations (line 8 to 11 in Algorithms [ and we call the whole T iterations a scatter step.
Algorithms D and 2 depict the training loop applied by workers and servers respectively. As an initialization step, all machines the network, be they workers or servers, initialize the model with the same random values, i.c., using the same seed. Empirical results show that this step is crucial in achieving high accuracy. Moreover, each worker j chooses some random integer Ty with 1 < ry I Ros-- Then each worker does backpropagation step compute its gradient estimate the initial model. The subsequent steps E N work as follows.
The algorithm starts with scatter step, which includes doing a few iterations. In each iteration, each parameter server pulls gradients g, from all workers and aggregates them using MDA, computing
(8) Jagg- Then, each server uses its own computed gngs update the model. While parameter servers
(1)
4

---

Under review as a conference paper at ICLR 2020
doing such computation, each worker j does speculative step by computing local view of the updated model using its local computed gradient and its latest local model.
Then, each worker j pulls one parameter vector from server where, = (ry +t+1) mod Nps- Such a worker does a backpropagation step, computing the new gradient based on the pulled model. Based on this computation and the local estimate of the updated model, the worker applies the Lipschitz filter and the models filter to check the legitimacy of the pulled model. If the model fails to pass the filters, the worker pulls a new model from the parameter server i, where (r, +) mod Nps- This process is repeated until pulled model passes both filters,
Algorithm 1 Worker Algorithm
1: Calculate the value of and a value for seed
2: model +- iniiiittiooo model(ed)())ed))
3: r rt random_into int(mn,p)
4: / 4-
5: grad <- model.
6: repeat
7: local_model + (rodyggrammmddl..raadd
8:
if mod T 0 then
To bound the drifts between parameter vectors at correct
9:
models <- read models()
10:
model <- MeaMed((moell))
servers, every I" iterations, global gather step is executed on both servers and workers sides: Each server sends to all other servers its current view of the model 0!" After
11:
else
12:
6-0 0 i
13:
repeat
gathering models from all servers, each server aggre-
14:
new new_model +- model((
gates the received models using Mean Around Median
(r+t+1) i) mod nps)
(MeaMed) computing 0f o(((099)) Then, each worker j pulls such models of o((((99)) from all servers and aggregates them using MeaMed, before starting a new scatter step.
15:
new <- new www.modde.baccprop0
16:
i i i +++
17:
until pass filters(new m. model <- new m_odee
The interplay between using MDA to tolerate Byzantine
18:
workers and filters to tolerate Byzantine servers results in a convergence rate of O ( fw))fn.. The formal
19:
grad + new-grad
20:
end if
proof of LIUBEr'S Byzantine resilience is provided in the supplementary material (Section 3).
21:
t t + 1+
22:
until > num nttrattrat
4
IMPLEMENTATION AND EVALUATION
4.1 IMPLEMENTATION
Algorithm 2 Parameter Server Algorithm
We use TensorFlow 5), a popular ML framework, as an underlying system for our implementation of LIUBEL. We
1: Calculate the value of T and a value for seed
2: model <- init model(seed)
use it only as a local library to compute gradients (on the workers' side) and update the model (on the parameter
3: [ 1- 0
4: repeat
server side). In this sense, we do not rely on the shared graph design followed by TensorFlow. Yet, we allow each machine in the network, be it server or a worker, to build its own independent graph. This gives better control over communication and disallows access of Byzantine machines to correct machines' memory (13). Moreover, this modular
5: grads + read- -radienta))
6: grad MDA(grads)
7: model.updatte(raad
8: if mod T then
9:
model <- read_ (rdddlso
10:
model + MeaMee((moeels)
design allows LIUBEI to be integrated easily with other ML
11:
end if
frameworks, e.g., Py MoTcch (28).
12: t+
As consequence of our design, we build our own commu-
13: until t > num iterations
nication abstractions. We use gRPC for communication and Protocol Buffers for serializing and deserializing data. Each machine in the network creates a gRPC server that serves requests coming from other machines. Such a request could be either asking for a gradient (usually from a server) or asking for an updated model (either from worker or a server). We parallelize requests multiple machines (for example when a server asks for gradients from all workers).
4.2 SETUP
Baselines. We compare LIUBEI to two baselines: TensorFlow (5) and Yu (5) The first baseline shows the performance of training using a non non- aon-yaantine resilient distributed framework and hence, comparing LIUBEI to it quantifies the cost of Byzantine resilience. Guan Yu is (so far) the only algorithm that tolerates both Byzantine servers and workers. Comparing LIUBEI to Guan Yu highlights the performance gain achieved by algorithm.
5

---

Under review as a conference paper at ICLR 2020
Metrics. We use two standard metrics for evaluating LIUBEI: Accuracy and Throughput. Accuracy denotes the fraction of correct answers a model gives (correct classifications) among all its answers, using the test set. We show the progress of accuracy with the number of iterations and time. Throughput measures the numher of updates the system, i.e., the parameter server does per second.
Testbed. Our experimental platform is Grid5000 (2. We employ nodes, each having CPUs (Intel Xeon E5-2630 v4) with 10 cores, 256 GiB RAM and 2 10 Gbps Ethernet. Unless otherwise stated, we employ 20 compute nodes (workers), out of them (up to) nodes could be Byzantine. In the case of vanilla TensorFlow deployment, we use only machine as parameter server. Otherwise, we employ machines for LIUBEI deployment and machines for Guan'Y Yu deployment; these numbers are to tolerate at most I Byzantine server, based on the requirements of each algorithm.
Dataset and Model. We consider the im- age classification task due to its wide adoption as benchmark for distributed MI. systems, e.g., (12). We use MNIST 3 and CIFAR-10 (I) datasets, MNIST is dataset of handwritten dig-
Table 1: Models used to evaluate LIUBEI.
Model
# parameters
Size (MB)
MNIST_CNT
79510
0.3
CifarNet
1756426
6.7
its. It has 70,000 28 x 28 images in 10 classes. CIFAR-10 10 a widely-usee useed dataset in image
Inception
5602874
21.4
ResNet-50
23539850
89.8
classification (33 36). It consists of 60,000 32 x 32 colour images in 10 classes.
ResNet-200
62697610
239.2
We employ different models with different sizes ranging from simple models like small convolutional neural network (CNN) for MNIST, training a few thousands of parameters to big models like ResNet-200 with around 63M parameters. All models are listed in Table T
4.3
RESULTS
We show here the key results of the evaluation of LIUBEI. First, show the progress of accuracy over training iterations and time (i.e., convergence) and then, we discuss the throughput of LIUBEI compared to Guan Yu (I5); both sets of experiments we show the performance of LIUBEI in Byzantine environment, i.e., under a recent attack. Finally, describe the effect of changing the value of T on the filters' performance and convergence.
done in Byzantine- environment. Then,
20.5
20.5
0.4
0.44
Terastion
Turaerion
0.3
Udds - -0
6.3
LAGG - G-
0.2
uas it.
0.2
00.00 (--0)
0.1
0.1
200
400
600
200
1000
1400
200 400
800 000012001400160010000
Model Updates
Time
(a)
(b)
mini- batch size = 250
0.7
0.7
0.6
0.6
00.5
2o.5
0.4
0.4
0.3
U.Bs -u- 4-
40.3
Ludi -u- G-
usa 16,
C-00
LaGu 16, C-
eaams 0e G-
Quarti v,- 6
Coantt -1,
200
800
1600
Updates
(d)
mani-batch size = 100
Figure 2: Convergence in non- non-Byyantine environment.
Convergence. Figure shows the convergence all experimented systems with both time and training iterations. We experiment with two batch sizes and two values for declared Byzantine servers and workers (only for the Byzantine-toll toleraan deployments). Figure 2a shows that all deployments have almost the same convergence, with slight loss in final accuracy for the Byzantine- deployments, which we quantify to around 5%. Such a loss is emphasized with the smaller batch size (Figure 2c). This accuracy loss is admitted in previous work (34 15) and inherits from using

---

Under review as a conference paper at ICLR 2020
statistical methods (basically, GARs) for Byzantine resilience. Such GARs ensure convergence only to ball around the optimal solution, i.., local minimum 16). As LIUBEI builds on these GARs, expect it achieve accuracy similar to that achieved by such GARs. Moreover, the figures confirm that using a higher batch size gives a better performance for both LIUBEI and Guan Yu. Figures 2a and show that LIU achieves the same convergence behavior as GuanYu.
The cost of Byzantine resilience is more clear when convergence is observed over time (Figure 2b). especially with the lower batch size (Figure 2d). Using a bigger batch size helps the Byzantine- tolerant systems achieve a performance close to vanilla TensorFlow. We quantify the overhead of LIUBEI compared vanilla TensorFlow around 24% and the performance gain of LIUBEI compared to Guan Yu by around 70%. We analyze this overhead with more scenarios later on in the section. We draw two main observations from these figures: First, unlike with Guan Yu, changing the number of declared Byzantine machines does not affect the progress of accuracy while deploying LIUBEI. This is because servers and workers in BIU deployments always wait for replies from all machines, regardless of the number of Byzantine machines (unlike in Guan Yu, where the number of expected replies depends on the number of Byzantine machines). Second, LIUBEI always outperforms Guan Yu, especially with non-zero values for declared Byzantine servers and workers. Such result is expected as LIUBEI uses less number of communication rounds and less number of messages per round compared to Guan Yu. Given that distributed ML systems are network-bound (19) (6),, reducing the communication overhead significantly boosts the performance and the scalability of such systems.
Throughput. We do the same experiment again, yet with different state-of-the-ar models so to quantify the through- put gain of LIUBEI compared to Guan Yu. Figure shows the
1.6
114
31.2
310
throughput of LIUBEI divided by the throughput of Guan Yu
568
in each case. For the current version of our implementation, we use CPUs for computation; we expect that using GPUs will emphasize more the effectiveness of our LIUBEI protocol as the communication overhead is generally highlighted more that LIUBEI outperforms
206
F04
02
0.0
Figure 3: Throughput gain of LI-
with GPUs From this figure, Guan Yu in all cases, where the performance gain is emphasized more with large models. This is expected because the main advantage of LIUBEI is decrease the number of communication messages, where bigger messages are transmitted with bigger models.
uBEI compared to Guan (15).
Byzantine workers. We study here the performance of LIUBEI in the presence of Byzantine workers. Simple misbehavior like message drops, unresponsive machines or reversed gradients are well-studied and have been shown to be tolerated by Byzantine- -esiiiene-resilientt GARs (34 (5), which LIUBEl also uses. Thus, here we focus on a more recent attack that is coined as little is enough attack (6). Such an attack states that changing each dimension in gradients of Byzantine machines, even by a very small value, can trick some of Byzantine-resilien GARs like X 16).
0.5
0.4
K.3
United
m-1 f-2
nx23
0.1
200
400
600
800
Updates
(a) The ratio fw.
We apply this attack to multiple deployments of LIUBEL. In each scenario, we apply the strongest possible change in gradients' coordinates so as to hamper the convergence the most. We study the effect of this attack on the convergence of LIUBEI with both the ratio of Byzantine machines to the total number of machines (Figure 4a) and the batch size (Figure 4b). We use the deployment with no declared Byzantine behavior (that is presented in Figure 2a) as a baseline in this experiment.
0.7
0.5
0.4
Uodel Allaco
0.2
pw259
pwd53
450
605
Nodel Updates
(b) Batch size Figure 4: Convergence in the presence of Byzantine workers.
Figure 4a shows that the effect of the attack starts to ap- pear clearly when the number of Byzantine nodes is significant fraction (more than 20%) of the total number of nodes. This is intuitive as the attack tries to increase the variance between the submitted gradients to the parameter servers and hence, increases the ball (around the local minimum) to which the used GAR converges (see e.g. (6) for theoretical analysis of the interplay between the variance and the Byzantine resilience). Stretching
7

---

Under review as a conference paper at ICLR 2020
the number of Byzantine machines to the maximum allowed (f 8) downgrades the accuracy to around 40% (compared to 67% in "No Attack" case). The main reason for this is that the assumption on the variance between gradients required by MDA (the used GAR in this deployment) is not satisfied. We discuss this issue in details in the supplementary material (Section 4).
Increasing the batch size only improves the accuracy per training iteration but also the robustness of LIUBEI (by narrowing down the radius of the ball around the convergence point, where the model will fluctuate as proven in 16). Figure 4bb fixes the ratio of fw to nw to the biggest allowed value to see the effect of using a bigger batch size on the convergence behavior. This figure confirms that increasing the batch size increases the robustness of LIUBEI. Moreover, based on our experiments, setting 25% of nodes to be Byzantine while using a batch size of (up to) 256 does not experimentally satisfy the assumption on the variance of MDA in this deployment, which leads lower accuracy after convergence (see supplementary material, Section 4).
Byzantine servers. Figure 5 shows the performance of LIUBEI in the presence of Byzantine server out of a total of 4 servers. We experimented with 4 Byzantine behavior: 1. Reversed, in which the server sends a correct model multiplied by a negative number, 2. Partial Drop, in which the server randomly chooses 10% of the weights and set them to zero (this simulates using unreliable transport protocol in the communication layer, which was proven beneficial, e.g.. (13)). 3. Random, in which the server replaces the learned weights by random numbers, and 4. LIE, an attack inspired from the little is enough attack (6), in which the server multiplies each of the individual weights by a small number 2, where |z 1| < 8 with 5 very close to zero; = 1.035 in our experiments. Such a figure shows that LIUBEI can tolerate the experimented Byzantine behavior and that the learning converges to the same accuracy observed before in Figure 2a We noted that both filters together do not pass any false positives. i.c. the models submitted from the Byzantine server never pass both filters (although could trick one filter individually).
0.7
0.6
20.5
0.4
0.3
Ravered
0.2
Farta Drop
0.1
200
400
600
800
1000
Model Updates
Figure 5: Convergence in the presence Byzantine server.
Effect of changing T. The value of T denotes the number of iterations done in scatter step (i.e., before executing one gather step). Figure [ shows the effect of changing the value of T on convergence with both time and model updates in a Byzantine- environment. Figure 6a shows that the value of T'' almost does not have any effect on the convergence w.r.t. the model updates. This happens because models on correct servers almost do not drift from each other (as all the servers are correct). Interestingly, Figure [66] shows that using a higher value for T helps converge faster. This is because increasing T decreases the communication overhead, achieving faster updates and higher throughput. However, it is important note that as the value of T increases, the expected drifts between models on correct servers increases, and it becomes easier for the Byzantine server to trick the workers.
0.7
0.6
20.5
0.4
1=1
0.3
T=30
0.2
Tw200
0.1
15333
200
1000
Modal Updates
(a)
0.7
0.6
Accuras
20.5
0.4
T-1
0.3
1-50
T-10
T-200
0.2
T-332
200
400
600
800
1000 1200
Figure 7 the ratio of false negatives (i.e., the number of falsely-rejected correct models by filters on the workers) to the total number of submitted models, with different values for T. Although we declare fps 1, we do not employ any Byzantine behavior in this experiment. We observe the number of rejected models on workers after 500 learning iterations. In general, the ratio of false negatives never exceeds 1% in this experiment, and it is almost stable with increasing T. Note that 333 is the maximum value allowed for T in this setup (to follow the safety rules of LIU)EI). With T = 1, the false negatives are always zero, simply because the filters do not work in this setup (i.c., the gather step is executed in every iteration). Such a figure shows that our filtering mechanism is effective in not producing many false negatives and hence, do not waste communication rounds (when a model is rejected, the worker asks for another model from a different server).
Time [s]
(b)
Figure 6: The effect of changing T on performance.
8

---

Under review as a conference paper at ICLR 2020
5 RELATED WORK
The closest approach to ours is Guan Yu (15), which toler- ates Byzantine workers and servers, considering however asynchronous network. Guan Yu uses GAR to toler-
Falce Nenatvve Ratio
0.006
ate Byzantine workers and Median (34) twice in a row in each iteration both workers and parameter servers tolerate Byzantine servers. We note two limitations in this work. First, Guan Yu's design induces an overhead both in computation and communication: the algorithm requires three communication rounds and applies aggregation rules three times in each iteration. In addition, it requires more compute nodes than the vanilla case to tolerate network asynchrony. Such overhead limits scalability for large-scale applications that models with millions of parameters. Second, for Guan to work, the authors assume that the difference between models correct parameter servers is always bounded; this cannot be fulfilled in some cases. We address these two problems by using a new filtering mechanism instead of models aggregation and by employing gather step every few iterations accordingly.
0.004
7.0002
Figure 7: False negative percentage with different values of T'.
Several proposals tolerate only Byzantine workers in syndhronous/ayychhroouus network and syn- chronous/asynchroone learning, all assuming a single correct parameter server. (34) proposed three Median- based aggregation rules that can resist both Byzantine and Dimensional attacks. Krum (8) and Multi-Krum (13) use distance-based algorithm filter the Byzantine inputs and average the correct ones. Bulyan (16) proposes meta mega--agorithm that guarantees a strong Byzantine resilience, i... resist strong adversary that can fool the aforementioned algorithms. Draco (TT) uses coding schemes and redundant gradient computation for Byzantine resilience, where Detox (29) combines coding schemes with robust aggregation for better resilience and overhead guarantees. Kardam (14)
uses filtering techniques to filter out Byzantine workers in asynchronous learning setup.
CONCLUDING REMARKS
Summary. This paper proposed LIUBEI, robust Machine Learning (ML) algorithm that does not trust any individual component in the network almost without adding communication rounds compared to vanilla distributed MI systems. LIUBET relies on the server/worker architecture and assumes network synchrony. LIUBEI introduces a novel filtering mechanism used by workers to check whether a pulled model (from parameter server) is suspicious not, without requiring to pull models from all servers. LIUBEI also introduces a novel protocol, scatter/gather, to reduce the communication overhead. We theoretically prove that LIUBEI tolerates Byzantine servers and workers and ensures convergence. Our experiments with TensorFlow based implementation show that LIUBEI's overhead, in terms of convergence, is around 24% compared to vanilla TensorFlow, where its throughput gain is around 70% compared to a state-of-the-art solution that tolerates Byzantine workers and servers in asynchronous networks.
Open question. The relation between the frequency of applying the gather step and the variance between models on correct servers data-dependen. and model--ependent. our analysis, we provide safety guarantees on this relation that will always ensure Byzantine resilience and convergence. However, we believe that some cases applying the gather step more frequently may lead noticeable improvement in the convergence speed as it decreases the variance. The trade-off between this gain and the overhead of communication (to gather) remains data-dependent and model- dependent question that is out of the scope of this work.
REFERENCES
[1] Cifar http://tttpppp../o.....ooootooot html
[2] Grid5000. https:// Tttp::://ww.gr.55000..5
[3] Mnist dataset. http://////aaa...oo...oo///////a
[4] LIUBEI source httppp/:/ggthhb..cc//aaoooooooos submi

---

Under review as a conference paper at ICLR 2020
[5] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al. Tensorflow: A system for large-scale machine learning. In OSDI, 2016.
[6] M. Baruch, G. Baruch, and Y. Goldberg. A little is enough: Cireumventing defenses for distributed learning. arXiv preprint arXiv:1902.000 0 56, 2019.
[7] B. Biggio and P. Laskov. Poisoning attacks against support vector machines. In ICML, 2012.
[8] Blanchard, E. M. El Mhamdi, R. Guerraoui, and Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Neural Information Processing Systems, pages 118-128, 2017.
[9] L. Bottou. Online learning and stochastic approximations. Online learning in neural networks, 17(9):142, 1998.
[10] M. Castro, B. Liskov, et al. Practical Byzantine fault tolerance. In OSDI, volume 99, pages 173-186 1999.
[11] L. Chen, H. Wang, Z. Charles, and D. Papailiopoulos. Draco: Byzantine-resilient distributed training via redundant gradients. In International Conference on Machine Learning, pages 2018.
[12] T. M. Chilimbi, Y. Suzue, J. Apacible, and K. Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In OSDI, volume 14, pages 571-582, 2014.
[13] G. Damaskinos, E. M. EI Mhamdi, R. Guerraoui, A. Guirguis, and S. Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. In SysML. 2019.
[14] G. Damaskinos, E. M. El Mhamdi, R. Guerraoui, R. Patra, M. Taziki, et al. Asynchronous byzantine machine learning (the case of sgd). In ICML, pages 1 1153-1162, 2018.
[15] E.-M. El-Mhamdi, R. Guerraoui, A. Guirguis, and S. Rouault. Sgd: Decentralized byzantine resilience. arXiv preprint (rXiv:1905.03853, 2019.
[16] E. M. EI Mhamdi, R. Guerraoui, and S. Rouault. The hidden vulnerability of distributed learning in Byzantium. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3521-3530, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[17] A. Esteva, B. Kuprel, R. A. Novoa, Ko, S. M. Swetter, H. M. Blau, and S. Thrun. Dermatologist-Ievé classification of skin cancer with deep neural networks. Nature, 542(7639): 15, 15, 2017.
[18] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. JACM, 32(2):374-382, 1985.
[19] K. Hsieh, A. Harlap, N. Vijaykumar, D. Konomis, G. R. Ganger, P. B. Gibbons, and O. Mutlu. Gaia: Geo-distributed machine learning approaching lan speeds. NSDI, pages 629-647, 2017.
[20] N. Ivkin, D. Rothchild, E. Ullah, V. Braverman, I. Stoica, and R. Arora. Communication-efficccnn distributed sgd with sketching. arXiv preprint arXiv:1903.04488 2019.
[21] L. Kim. How many ads does google serve day? htt:://ooo.lVoliaaX0 November 2012.
[22] L. Lamport et al. Paxos made simple. ACM Sigact News, 32(())18-22 2001.
[23] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. TOPLAS, 4(3):382- 401, 1982.
[24] S. Lee, J. K. Kim. X. Zheng, Q. Ho. G. A. Gibson, and E. P. Xing. On model parallelization and scheduling strategies for distributed machine learning. In Advances in neural information processing systems, pages
2014.
10

---

Under review as a conference paper at ICLR 2020
[25] M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V. Josifovski, J. Long, E. J. Shekita, and B.-Y. Su. Scaling distributed machine learning with the parameter server. In OSDI, volume I, page 3, 2014.
[26] M. Li, L. Zhou, Z. Yang, Ai, F. Xia, D. G. Andersen, and A. Smola. Parameter server for distributed machine learning. In Big Learning NIPS Workshop, volume 6, page 2, 2013.
[27] X. Meng, J. Bradley, B. Yavuz, E. Sparks, S. Venkataraman, D. Liu, J. Freeman, D. Tsai,
M. Amde, Owen, al. Milib: Machine learning in apache spark. JMLR, 17(1):1235-1241 2016.
[28] A. Paszke, S. Gross, S. Chintala, and G. Chanan. Pytorch. Computer software. Vers. 0.3, 2017.
[29] S. Rajput, H. Wang, Z. Charles, and D. Papailiopoulos. Detox: A redundancyybased framework for faster and more robust gradient aggregation. arXiv preprint arXiv:1907.12200 2019.
[30] Q. Rao and J. Frtunikj. Deep learning for self-driving cars: chances and challenges. 2018 IEEF/ACM 1st International Workshop Software Engineering for Al in Autonomous Systems (SEFAIAS), pages 35-38. IEFF, 2018.
[31] J. Rousseeuw. Multivariate estimation with high breakdown point. Mathematical statistics and applications. 8:283 297, 1985.
[32] R. Shokri and V. Shmatikov. Privacy-preserving deep learning. In SIGSAC, pages 1310-1321, 2015.
[33] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. JMLR, 15())1929-11988 2014.
[34] C. Xie, O. Koyejo, and Gupta. Generalized Byzantine- tolerran sgd. arXiv preprint
1802: 10/ 2018.
[35] C. Xie, S. Koyejo, and Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner 2019.
product manipulation. arXiv preprint
[36] H. Zhang, Z. Zheng, S. Xu, W. Dai, Q. Ho. X. Liang, Z. Hu, J. Wei, P. Xie, and E. P. Xing. Poseidon: An efficient communication architecture for distributed deep learning on GPU clusters. In USENIX ATC, pages 181-193, 2017.

---

Fast Machine Learning with Byzantine Workers and Servers
Supplementary Material
Quick Note
We give here the convergence proof of LIUBEr along with its resilience guarantees. LIUBEr addressos the total Byzantine resilience problem in distributed Machine Learning (ML) context (following the parameter server architecture [8]) where, both workers and servers could behave arbitrarily. LIUBEr assumes the network to be synchronous, i.e., there is an upper bound (not necessarily known) on the computation and communication delay. LIUBEI uses a Byzantine- resilient gradient aggregation rule (GAR) to tolerate Byzantine workers, which Minimum- Diameler Averaging [9] (or in short MDA). Such a GAR can be safely replaced with any other GAR that gives similar guarantees given by the used GAR such as Krum [2] or Median [11]. The main goal of LIUBEI is to reduce communication overhcad guaranteeing resilience against Byzantine workers and servers. This is mainly achieved by novel filtering technique and our scatter/gather protocol.
much as possible, while
Note about the name. Lui Bei was the warlord of Guan Yu, the general whose name is given to the first algorithm to tolerate both Byzantine workers and servers. We show that LIUBEI performs better than Guon Yu.
Preliminary Material
1.1 Robust aggregation
Robust aggregation of gradients the key for Byzantine workers' resilience. To this end, gradi- ents are processed by a gradient aggregation rule (GAR), which purpose is to ensure that output of aggregation is as close as possible to the real gradient of the loss function.
In the general theory of stochastic gradient descent (SGD) convergence, typical validity as- sumption is that the gradient estimator is unbiased [3]. The role of GAR is to ensure relaxed version of this assumption in order to accommodate for the presence of malicious workers (whose gradients potentially biased).
Definition 1 gives such relaxation, which we adapt from [2, 7] and which was used as standard for Byzantine resilience in, e.g. [12, 13, 11].
Definition Let
< 7/2 be any angular value and 0 < J with the total number of imput vectors to the GAR and f the marimum number of Byzantine vectors. Let g be an unbiased estimate of the true gradient G, i.e., EG = g. GAR (which output noted as F) is robust (said to be (a. f) Byzanitne resilient) if (EF,g) g) 2 (1 (i-sina) a) || >0
LIuBEI uses two GARs: Minimum Diameter Averaging [7] and Mean Around Median [11].
1

---

1.2 Minmuum-Diameter Averaging (MDA)
MDA is a gradient aggregation rule (GAR) that ensures resilience against a minority of Byzantine input gradients. Mathematically, this function was introduced in [9] and its Byzantine resilience proof was given in [7]. MDA satisfics the (o Byzantine resilience guarantees introduced in [2]. Formally, let X' be the set of input gradients (all follow the same distribution), out of them are Byzantine, and y be the output of the Byzantine resilient GAR. Then, the following properties hold:
1. Ey is in the same half space E...
2. the first 4 statistical moments of y are bounded above by a linear combination of the first statistical moments of x X.
Such conditions are sufficient to show that the output of this GAR guarantees convergence of the learning procedure. More formally, these conditions enable the GAR to have a proof that follows from the global confinement proof of Stochastic Gradient Descent (SGD) [3].
In order to work, MDA assumes the following (as any other GAR):
2f n n V (100
(0) Egg 11) S (V)I, (1)
[ ((1,4,0)(11.. M|NXR"
where is the model state at the training iteration t, n is the total number input gradients, f is the maximum number of Byzantine gradients, 9t is an unbiased estimate of the gradient at iteration and L is the loss function.
The MDA function works as follows: Consider that the total number of gradients is and the maximum number of Byzantine gradients is with 2 2 + 1. MDA emumerates all subsets of size - f from the imput gradients and finds the subset with the minimum diameler among all subsets of this size, i.c., n - f- The diameter of a subset is defined as the maximum distance between any two clements of this subset. The output of the MDA function is the average of gradients in such a subset. More formally, the MDA function is defined as follows [7]:
Let (g) ...... 9m) E (Rd"), and X a { ... .n } the set containing all the input gradients. 1Q- n f} the set of all the subsets of X with a cardinality of n f-ff f,
Let R A {Q X.
and let S arg min QER
max (11a: 251)) (B.9;)EE2
Then, the aggregated gradient is given by MDA (9) In) = Σ
BES
1.3 Mean Around Median (MeaMed)
The MeaMed function a fairly intuitive function to remove outliers from an input set. As an aggregation rule, MeaMed was proven to be () Byzantine resilient in [11]. Even more than that, MeaMed can resist dimensional attacks, i.e., dimensional (a, Byzantine resilient. In this paper, we apply MeaMed to models, rather than gradients not only to exclude Byzantine models but also to bring models on correct servers close to cach other.
MeaMed works as follows: For each dimension (in d), MeaMed finds the median value among all input models and then averages the closest n - f values to this value, along with the median value. Formally, the MeaMed function defined follows:
Let X be the set of input models of size n, where the maximum number of Byzantine models is f with > 2f + 1. Let the output of MeaMed be p, with Pj is the dimension//coordintee j ee [1...d] in the output model.
Basically, any CAR that satisfies such form of resilience [2, 7, 11] can be used with LIUBEr; MDA is just instance.
2

---

Let mj be the median value of all values in dimension j at all imput models 0 in X. 1 Σ jg where Sj the set of closest values my in dimension j among all Then, Pj R-f 0,ES,
imputs, including mj, i.., |5 n.
2
LiuBei's Algorithm
2.1 Notations
Let (Nor Peps Sui Sys: d) E No, each representing:
Tps 2 35ps + 1 the total number of parameter servers, among which fps are Byzantine
nww 2 2f + the total number of workers, among which fw are Byzantine
d the dimension of the parameter space Rd
Let (without loss of generality):
1ps fps] be indexes of correct parameter servers
Mps Jps 1 Nlps] be indexes of Byzantine parameter servers
[1. nw sw] be indexes of correct workers
nnw fw + [ww] be indexes of Byzantine workers
Let o, be notation for the parameter vector (i.e., model) at parameter server i E [1 npe - fpe] for step f E N. (4) Let St be a notation for the gradient estimation at worker i [1 the - fwl for step E N.
Let G. be notation for the gradient distribution at worker [1 th Swl for step N.
Let L be the loss function we aim to minimize, let V (0) be the real gradient of the loss function at 0, and let (0) be a stochastic estimation of the gradient, following G, of L at 0. Let be the learning rate at the learning iteration t E N with the following specifications:
1. The sequence of learning rates is decrcasing" with i, i..., if > then, It < To, Thus, the initial learning rate no is the largest value among learning rates used in subsequent
steps.
2. The sequence of learning rates " satisfies E. 7 oo and E. n2 x0.
2.2 Algorithm
Initialization. Fach correct parameter server and worker j starts (at step t 0) with the same parameter vector:
Vi E .. nps Spel. 0f" - 0o
Vj E [1..nw sw], 0 - Oo
Each correct worker j generates a random integer r, E [1 npel and does one backpropagation step compute ( at the initial model 6g-
Training loop. Each training step N, the following sub-steps are executed sequentially (unless otherwise stated).
1. Each parameter server pulls gradients 9: from all workers and then applies the MDA function on the received gradients, computing the aggregated gradient Jagg- Then, each
(5)
(8) server uses its own computed gagg to update the model as follows: 0(9) - 0.00 7.
2. While parameter servers are doing step 1, each worker j does a speculative step as follows:
a worker j calculates its local view to the updated model: 0/100 = 0,5) - -gg (5)
IIn fact, it sufficient that the sequence is decreasing only once every T steps, with = sh where the Lipschitz coefficient of assumption 5 (cf Section 3.1).
3

---

3. Each worker j pulls one parameter vector o( from server where, i = (ry+++1) mod nps-
4. Each worker j does the backpropagation step, computing g at the pulled model 0
5. Each worker j tosts the legitimacy of the received model off using the Lipschitz criterion (i.e.; Lipschitz filter) and the difference on model norms (i.e., models filter) as follows. First, a worker j calculates k, an empirical estimation of the Lipschitz coeflicient, which defined as:
9/1) 9 D6"
6))
k
( 1+1
-600
Then, the worker tests whether this value &o lies in the non-Byzantine quantile of Lipschitz coefficients: & S Kp quantile -pp- (K} where, K the list of all previous Lipschitz "ps
coefficients ls (i.e., with Eprev <t). Second, the worker j computes the distance between the local and the pulled (from server i) models as follows: | o44) and makes sure
that such a difference is < TT mod т) |90- mod Tyll (8T+2)(m (un) + 2 mod m)),
4fw
with - 1/3tn: where is the Lipschitz coefficient (assumption 5). Such a difference is instructed by a correct execution of the MDA algorithm. If both conditions are satisfied, the received model 0!" is approved and the algorithm continues normally. Otherwise, the parameter server is suspected and its model is ignored; worker j continues by repeating iteration again from step 3.
6. To bound the drifts between parameter vectors at correct servers, each T 1/st,, steps, a global gather step executed on both servers and workers sides. This step is executed as follows:
Each server sends to all other servers its current view of the model 0,00 After gathering models from all servers, each server i aggregates such models with MeaMed, computing of g(5(e99)) Then, each worker j pulls the model g(élage)) from all parameter servers and aggregates the received models using MeaMed. Finally, each worker j uses the aggregated model to compute the backpropagation step, and the algorithm continues normally from step 1.
We call steps 1 through 5 scatter step and step 6 gather step. During scatter step(s) servers do not communicate and hence, their views of the model deviate from each other. The goal of the gather step is to bring back the models at the correct servers close to each other.
3 LiuBei's Convergence
In this section, we show that LIUBEI guarantees convergence and tolerates Byzantine workers and servers. We first state the assumptions for LIUBEI to work and then dive into the proof, which is shown step by step: First, show that the result of execution of MDA on two correct servers results in models that are close each other. Then, we show how we bound the distance between models on correct servers throughout the learning procedure using the scotter ccafter/gather protocol. After that, we explain our novel filtering mechanism and show why they can tolerate Byzantine servers. Finally, we put everything together to show the convergence of LIUBEI.
3.1 Assumptions
1. Vt E N, ( .t. (nw-Sw) are mutually independent.
1

---

2. 3o' E., (i, [1.. nww ful x N, E ot Egg (
1 s
3. is positive, and 3 times differentiable with continuous derivatives.
4. Vr c [], (л, B,) E IR? (i,2,0) c [ [1... T swl x xx Rd, E Di
S A, + Br 1101"
is Lipschitz continuous, i.e. IE > 0, A (z,g) E (RT)² [VL V - 1 y||
6. 3D E R, v e IRd |0|2 2 D, E (c, B) E R4 x 10. - 7/
[L 2 e, (0, VL (0)) Z cos (3) |0| (0)l..
Assumptions 1 to (ii.d, bounded variance, differentiability of the loss, bounded statistical moments, and Lipschitz contimuity of the gradient) are the most common ones in classical SGD analysis [3, 4].
Assumption 6 was first adapted from [3] by [2, 7, 5] to account for Byzantine resilience. It intuitively says that beyond certain horizon, the loss function is "steep enough" (lower bounded gradient) and "convex enough" (lower bounded angle between the gradient and the parameter vector). The loss function does not need to be convex, but adding rogularization terms such ||0]|2 ensures assumption 6, since close to infinity, the regularization dominates the rest of the loss function and permits the gradient (I()) point the same half space as The original assumption
[3] is that (0, L > 0; [2, 7] was argued that requiring this scalar product to be strictly positive is the same as requiring the angle between 0 and (0) to be lower bounded by an acute angle (3 < 7/2).
3.2 Bounded gradient aggregation on correct parameter servers
Consider two correct servers and this section discusses the maximum difference between aggregated gradients (using MDA) on both servers at any step / E N.
Let fw) e (N - (0))² and n. 2 25 + 1. Let H. be the set of indices of correct gradients received at server x (and the same notation for H₂) and g. be the gradient received from worker at server j (only for this section).
the following, we show that:
R A (1.0)) E ((Rx)
(2d) Rp.
MDA 0i (lodd MDA (01-) (())...(())
(2)
sc.
max (..))(H)
19:: 9j
Proof. Based on the definition of the MDA function (Section 1.2), let S be the set of the chosen gradients by the MDA algorithm, i.e., with the minimum diameter among all subsets of size now fw. Then, the aggregated gradient is given by MDA (g) ... Irw.
Σ
Based on this definition, the following holds:
3 (i.j) E H & (2,2) S², 11y- vll $ 11 - -
Then, observing that n fw sw 3k Ha gh E S. Using the triangle inequality, we
5

---

have:
MDA (g1 .......gna.. ...r.. 9kll
l Σ
9k
Nw
gES
Σ
9kb
The - lw
gES
Σ
l1g
gkll
J
9CS
119 9اد1
max
Thw fw 9ES
(iJ)EH,
max
19:
gjll
(iJ)
Based this, we have
|MD (2) ... g.. - MDA
91
MDA
(a)
Inw
(ar)
9k
+ 9k
+ 91
MDA (2) g
MDA
(r))
Dnw
9k
+ 11
øill + +1|||110 MDA (of:) - 9
S
max (HJ))(HuUH,)
19:
Thus,
MDA (0)0) 0. MDA (g1* ((())
...
53
11 9,1 (L)))(,.,)))
max
(2)
In plain text, this equation bounds the difference between aggregated gradients at two different correct servers, based on the maximum distance between two correct gradients, i.e., aggregated gradients on different servers will not drift arbitrarily.
3.3 Bounded distance between correct models
To satisfy Equation (the required assumption by MDA, Section 1.2), models at correct pa- rameter servers should not go arbitrarily far from each other. Thus, a global gather step (step 6 in Section 2.2) is executed once in a while to bring the correct models back close to each other. Such gather step is close to the distributed contraction module of [6]. which is based on apply- ing Median on both servers and workers sides (with the difference that the gather step applies MeaMed instead of Median and does not execute in all iterations).
In this section we quantify the maximun number of iterations that can be executed in one scatter step before executing one gather step. From another perspective, the goal to find the maximum possible distance between correct models that still satisfies the requirement of MDA on the distance between correct gradients (Fquation 1).
Without loss of generality, assume two correct parameter servers x and z starting with the samc initial model f-- After the first iteration, their updated models are given by:
0(0) O, MDA (g ..
(nw)
((3) 0 71 MDA (1)
(nw)
6

---

Thus, the difference between them is given by:
|0:00 - - -
| |DA (of")
(1) s/m=)) ...gh/))))) MDA (of) 9. gi (nw)
In perfect environment, with no Byzantine workers, this difference is zero, since the input gradients to the MDA function at both servers are the same (no worker lies about its gradient estimation), and the MDA function deterministic (i.e., the output of MDA computation on both servers is the same). However, a Byzantine worker can send diffcrent gradients to different servers while crafting these gradients carefully to trick the MDA function to include them in the aggregated gradient (i.c., force MDA to select the malicious gradients in the set S). In this case, [|(T) 0f+1 is not guaranteed to be zero. Based on Equation 2, the difference between the result of applying MDA in the same iteration is bounded and hence, such a difference can be given by:
|0 - -0+0| 33.70
5
max (H,
91
Following the same analysis, the updated models in the second iterations at subject param- eter servers are given by:
g 0/0) MDA
(1)
(nw)
92 92
8/3) = o(+) 72 MDA (1)
(nw)
Thus, the difference between models now will be:
1 -0/-0 -
(0 - MDADA 02 ...92 sl(m))))) (0)+)
22MDA
(
...g (mw)
0 - + 72 MDA
(1) (mm))
MDA (96") 92 (nw)
92
92
The bound on the first term is given in Equation 3 and that on the second term is given in Equation 2 and honce, the difference between models the second itcration is given by:
( 0511 2 3.3..1 21
max (KJ)E(HLUH.))
91
9
3 72
max (H,)
92
(
(4)
By induction, we can write that the difference between models on two correct parameter servers at iteration is given by:
10.00 -0(0
(
(1)
3
max (H.
(5)
t=1
Since of and ( computed different workers, they be computed based dif- ferent models of and 8(1) Following assumption 5, | ())l is bounded from above with
ge
(|le()) o(:) Noting that the sequence y monotonically decreasing with t + oo (Section 2.1),
Equation 5 be written
1000 of <
53 13377-0
10(0) - 0.51|
max (H.
Assuming that the maximum difference between any two correct models is bounded by K,, this difference can be written as:
(oft)
o(+) < 3. m..m 1. ..
7

---

Now, to ensure the bound on the maximum difference between models, we need the value of [0(0)= ofا² < K. At this point, the number of steps = T should be bounded from above
follows:
T 3 1.
66)
T here represents the maximum number of iterations that are allowed to happen in the scatter step ie., before doing one gather step. Doing more iterations than this number leads to break- ing the requirement of MDA on the variance between input gradients, leading to breaking its Byzantine resilience guarantees. Thus, this bound is safety bound that one should not pass to guaranice convergence. One can do less number of itcrations (than T) during the scatter phase for a better performance (as we discuss Section in the main paper). Moreover, this bound requires that the initial setup satisfies the assumptions of MDA. Having a. deployment that does not follow such assumptions leads to breaking guarantees of our protocol (as we show in Section 4 in the main paper).
3.4 Byzantine models filtering
This section shows that the filtering mechanism that is applied by workers (step 5 in Section 2.2) accepts only legitimate models that are received from servers which follow the algorithm, i.e., correct servers.
Such a filter is composed of two components: (1) a Lipschitz filter, which bounds the growth of models with respect to gradients, and (2) a models filter, which bounds the distance between models two consecutive iterations. We first discuss the Lipschitz filter then the models filter; we show that using cither of them only does not guarantce Byzantine resilience.
3.4.1 Lipschitz filter
The Lipschitz filter is defined in Step 5, Section 2.2. Roughly speaking, it runs on worker side, where it computes the Lipschitz coefficient of the pulled model and suspects it if its com- puted coefficient is far from Lipschitz coefficients of the previous correct models (from previous iterations).
The Lipschitz filter, by definition, accepts average mps Sps models cach pulled nps models. Such a bound makes sense given the round robin fashion of pulling models from servers (by workers) and the existence of (at most) fys Byzantine servers. Based on this filter, each worker pulls, on average, rps + fps each Nps iterations. Due to the presence of fps Byzantine servers, this is a tight lower bound on the commuicatiin between cach worker and parameter servers to pull the updated model. The worst attack an adversary can do is to send model that passes the filter (looks like a legitimate model, i.e., very close to a legitimate model) that does not lead to computing large enough gradient (i.e,, leads to minimal learning progress); in other words: attack that drastically slows down progress. For this reason, such filter requires Nys > 3fp-- With this bound, the filter ensures the acceptance of at least fps + 1 models for each pulled Aps models, ensuring a majority of correct accepted models anyway and hence, cnsuring the progress of learning. Moreover, due to the randomness of choosing the value ry and the round robin fashion pulling the models, progress is guaranteed in such a step, as correct and useful models are pulled by other workers, leading to computing correct gradients.
Based on assumption 5 and the round robin fashion of pulling models, a Lipschitz coefficient that is computed based on a correct model is always bounded between two Lipschitz coefficients resulting from correct models. Based on this, the global confinement property is satisfied (based the properties of models that passes the Lipschitz filter) and hence, we can plug LIUBEI in the confinement proof in (3). Precisely, given assumptions 4 and 5, and applying [3] (of which these assumptions are prerequisite). the models accepted by the Lipschitz filter satisfy the following property:
8

---

Let r-2,3,4, JA, and B3 0 such that Ai 2 1. S A + B₁ 10,1""
where 0r is the model accepted by the Lipschitz filter at some worker and 9. is the gradient calculated based such a model.
3.4.2 Models filter
The Lipschitz filter is necessary, yet not suffieient to accept models from parameter server. A Byzantine server can craft some model that is arbitrarily far from the correct model, whose gradient satisfies the Lipschitz filter condition. Thus, is extremely important that the received model is close to the expected, correct model. Such a condition verified by the second filter at the worker side, which we call the models filter. Such a filter is based on the results given in Section 3.3 and the local model estimation on the workers side.
make sure
Without loss of generality, consider correct worker j that pulls models from parameter servers v E [1 .. Mps] in a round robin fashion. In each itcration t > 1, the worker computes a local estimation of the next (to be received) model 0(301) based on the latest model it has 0(4) and its own gradient estimation 1- The local model estimation is done as follows:
af10)) = -(0) "tt 191-1-
(1)
Without loss of generality, assume that worker j pulls the model from some server i in iteration L. If such a server is correct, it computes the new model o!0) as follows:
0.0 - n MDA (9/-1-. ... (
Thus, the difference between the local model estimation at worker j and the received model from server i (if it is correct) is given by:
10000 0f = (00²) - 72-19h (.) ( - (0 1 - (9f 1 1... (...ggr
(nw)
< - 0/41]] x-1 |A-I||MAA MDA ( (mm) -
Based on the guarantees given by MDA [7]. the following bound holds:
MDA g ......".))) )m))) 06
now Jw
2f
Based on the results of Section 3.3, the maximum distance between two correct models just after T. By induction, we can find the bound
a gather step is Rw- fu P(r-(t mod r)) ((r mod ry) Ju
on the value | 0 and hence, we can write:
(0000
0 (( mod T>) g mad mill (2((t mod T) -1) (Ne S3T 2)
4fw
Thus, received model 0 that satisfies Equation 7 is considered passing the models filter. Such model is guarantcod to be in the correct cone of models in scatter step. Note that such filter cannot be used alone without the Lipschitz filter. A Byzantine server can craft a model that satisfies such filter (i.e., the models filter) while being on the opposite direction of minimizing the loss function. Such a model then will be caught by the Lipschitz filter.
Combining the Lipschitz filter and the models filter guarantecs that the reccived model at the worker side is close to the correct one (at the current specific scaller step), representing a reasonable growth, compared to the latest local model at the worker.
9

---

3.5 Proof of LiuBei
The algorithm works iteralively in two main phases, which we call scalter and gather phases. In the scatter phase, each parameter server works on its own local data without communicating with other servers. Also, workers pull the model from at most Sps + servers in each iteration, without requiring to communccate with all other servers. Such a step lasts for T learning iterations. In the gather phase, parameter servers communicate together to gather their models close to each other, and workers also gather models from all parameter servers. Such step is done for only one learning iteration. Naively, if we do the galher step in all learning iterations, the algorithm becomes very similar to Guan [6] (with even better guarantees due to the network synchrony assumption); and the proof of convergence can be adapted directly (basically in this case we do not need the filters). On the other extreme, if the gather step is never executed (i.e., only the scatter step execnted), the models at different servers will become arbitrarily far form each other (Section 3.3) and hence, the assumptions of the Byzantine-resilent GAR, i.e., MDA are violated, leading to (possibly) divergence.
Based on this, the gist of the proof is lo show that the maximum distance between models at correct servers is always small enough to satisfy the assumptions of MDA. Based this and the fact that workers do SGD steps during the scatter phase, it is trivial to show that there is a progress in learning between two gather steps, i.e., the loss function is minimized and hence, the proof reduced to the standard proof of SGD convergence [3]. Formally, we show:
(
o[-3]] 1)
lim EE to00
max nps-
(1.s)c
fpel lim 80
V 12)
Proving these two equalitics implics necossarily the convergenec of the learning procodure, or formally:
lim E ( 0 300
Proof. From Equation 7, we know that the difference between correct models is bounded by (T mod I Based on our assumptions (Section 3.1), lim t000
[r mod r) ||| =0.
(o()) 0!-3 0!-3|| = O.
lim max Therefore, t000 (a.s)e(L Rps fae]
A direct consequence of Section 3.3 is that beyond a certain time le (with e >> O be any positive real number), the standard deviation of the gradient estimators as well as the drift between (correct) parameter vectors can be bounded arbitrarily close to each other. More formally, the following holds (and is a direct consequence of the limits stated above):
|00 - E E99..
max E
<o' +e
iE TElT..Tu The
ful
3t O, Vt ter
(6(0) of
E max
(r.))c[1.... fpol2
The first inequality provides the bounded variance guarantee needed to plug LIUBEr into the convergence proof of [2], and the second inequality provides the remaining requirement, i.e. the bound on the statistical higher moments of the gradient estimator as if there was single parameter. More precisely, we have the following, let (x, be any two correct parameter servers, using triangle inequality, the second inequality above, and assumption 4 (bounded moments) we have (as given in Section 3.4):
14 > L.Vr E 1]. (A,, B.) R
Y (i,t,0) E 1.. nyw - ful x X Rd,
(x) gi
< A + B₁ 00010
10

---

where A, and B3 are positive constants, depending polynomially (at most with degree r, by using the second inequality above, the triangle inequality and a binomial expansion) on E, a and (A,, B,) from assumption 1, allowing us to use the convergence proof of [2] (Proposition 2) regardless of the identity of the (correct) parameter server.
Convergence rate. Using MDA is shown to induce convergence rate of O(V
Rww
We note that if we do the gather step in each iteration (i.e., T = 1), this rate would not change since the MeaMed function will always choose a correct model to proceed with. Moreover, the variance between models at the correct parameter servers will be minimum (zero in the case of absence of Byzantine machines). Gathering the models cach 2 iterations (i.c., T 2) doubles the distance between models correct parameter servers (in the worst case). By induction, doing the gather step after T iterations stretches the difference between correct models by a factor of T in the worst case. Hence, the slowdown induced by the filtering techniques only is (+))
and the convergence rate of LIUBEI is O(V fw=
4 Validating the bounded gradients variance assumption
To make progress at every step, any of Byzintine-roslleen gradient aggrega- tion rule (GAR), that is based solely on statistical robustness, requires a bound on the ratio variance/norm of the correct gradient estimations. Intuitively, not having such a bound would allow the correct gradients to become indistinguishable from some random noise. This is prob- lematic, since these Byzantinc- resilicnt GARs [2, 10, 7, 12] rely on techniques analogous to voting (i.e. median like techniques in high dimension): if the correct majority does not agree (appears "random"), ), then the Byzantine minority controls the aggregated gradient. For example, not satisfying these bounds makes the used GARs vulnerable against recently prcently-roooose attacks like A little is enough attack [1], which we experimented in Section 4.3 in the main paper. Such a bound is to ensure that, no matter the received Byzantine gradients, the expected value of the aggregated gradient does lie in the same half-space as the real gradient, leading for every step taken to more optimal parameters (smaller loss).
Here, we try to understand when this assumed bound on the variance to norm ratio (e.g., Equation 1) holds, and when it does not. The most straightforward way to fulfill such an assumption is to increase the batch size used for training. The question is then what the minimum batch size (that can be used while satisfying such bound) is, and whether it is small enough for the distribution of the training to still make sense.
Methodology. We use the same sctup, along with syper-parameters, used in our evaluation of LIUBEI (Section 4.2). We estimate over the first 100 steps of training the variance to norm ratio of correct gradient estimations for several batch sizes. We plot the average (line) and standard deviation (error bar) of these ratios over these 100 steps (Figure 1). We show the bound required by two Byzantinc-resilient GAR: MDA, and Kruti [2]. We find example on a widely- used GAR that unfortunately does not seem to provide any practical guarantee, due to its unsatisfied assumption". We also experimented with two values of the number of declared Byzantine workers: = 1,5. Increasing the value of f calls for tighter bound on the variance to norm ratio.
a very good
Results. Figure depicts the relation between the variance (of gradients) to norm ratio with the batch size. According to such a figure, Multi Krum cannot be safely used even with the largest experimented batch size, i.c., 256. Otherwise, the variance bound assumption such a GAR builds on is not satisfied and hence, an adversary can break its resilience guarantees [1]. MDA gives a better bound on the variance, which makes it more practical in this sense: typical batch size of 128 for example can be safely used with f = 1. However, MDA is not safe to
At least on academic model and dataset. IIt needs very low variance norm ratio of correct gradient estimations, e.g. 0.08 for (n. f) = (18,5).
11

---

12
Real
Real
MDA threshold
MDA threshold
8
Multi-Krum threshold
8
Multi-Krum threshold
4
2
0
0
2 2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
Batch size
Batch size
(a) f 1
(b) f =
Figure 1: Variance to norm ratio with different batch sizes, compared to the bound/threshold required by two resiinnt GARs: MDA and Mulfi -ruii. To satisfy a GAR assump- tion/ cion/condition, the real variancs/norm value should be lower than the GAR bound. For instance, MDDA can be used with batch-size-32 with f f= 1, but not with f = 5 (as the real aarance/norm value is higher than the MDA threshold).
use with f = even with the largest experimented batch size (b = 256). This confirmed in Section 1.3 in the main paper, where we show that an adversary can use such a vulnerability (due to the unsatisfied assumption) to reduce the learning accuracy. Having the optimal bound on variance while guaranteeing Byzantine resilience and convergence remains an open question.
References
[1] Moran Baruch, Gilad Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. arXiv preprint arxi:: 099000000566 2019.
[2] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machinc learning with adversaries: Byzantine tolerant gradient descent. In Neural Information Processing Systems, pages 118-128, 2017.
33 Léon Bottou. Online learning and stochastic approximations. Online learning in neural networks, 17(9):142, 1998.
(4 Olivier Bousquet and Léon Botton. The tradeoffs of large scale learning. In Neural Infor- mation Processing Systems, pages 161-168, 2008.
55] Georgios Damaskinos, El Mahdi El Mhamdi, Rachid Guerraoui, Rhicheek Patra, Mahsa Taziki, et al. Asynchronous byzantine machine learning (the case of sgd). In ICML, pages 1153 1162, 2018.
66 El-Mahdi El-Mhandi, Rachid Guerraoui, Arsany Guirguis, and Sebastien Rouault. Sgd: Decentralized byzantine resilience. arXiv preprint ar Xrx::1905500880 2019.
7 El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouanlt. The hidden vulnerability of distributed learning in Byzantium. In Jennifer Dy and Andreas Krause, editors, Proceed- ings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3521-300 1-230, Stockholnsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR
8 Mu Li, Li Zhou, Zichao Yang, Aaron Li, Fei Xia, David G Anderson, and Alexander Smola. Parameter server for distributed machine learning. In Big Learning NIPS Workshop, vol- ume 6, page 2, 2013.
12

---

Peter J Rousseeuw. Multivariate estimation with high breakdown point. Mothemalical statistics and applications, 8:283 297, 1985.
[10] Lili Su. Defending distributed systems against adversarial atlacks: consensus, conscnSUs- based learning, and statistical learning. PhD thesis, University of Illinois Urbana- Champaign, 2017.
[11] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized tolaattnn-tolerant sgd. arXiv preprint arXiv:1802. 10116, 2018.
[12] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Phocas: dimensional byzantine- resilient stochastic gradient descent. arXiv preprint 1805.1800.0900 2018.
[13] Cong Xie, Olwasanmi Koyejo, and Indranil Gupta. Zeno: Byzantine-suspicions stochaatt gradient descent. arXiv preprint Xiv: 10032, 2018.
13


Reviews:
[{"review_id": "r1lEfZxCKr", "reviewer": "AnonReviewer2", "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": "This paper introduces an algorithm to build distributed SDG-based training algorithm that are robust to Byzantine workers and servers.\n\nI am not very familiar with this area of research, but I feel the authors did a good job providing clear explanations and introducing all the relevant concepts needed to understand the proposed algorithm. Overall, I found the paper an interesting read.\n\nThe experimental section of the paper is lacking in some aspects:\n- One of the main ideas introduced in the paper is that of filters to check the legitimacy of models from model servers. While these ideas are sensible from a technical point of view, I feel the experimental section is not properly demonstrating all the robustness claims made in the paper. For example, in the beginning of training with high learning rates the models will change a lot, are these filters effective in this situation as well? How are these filters working in terms of false positive/negatives in the experiments?\n- How are models corrupted during training? What's the performances of the filters with different corruption techniques (e.g. adversarial attacks)?\n- What's the impact of the choice of T in the experiments?", "extra_scores": {"experience_assessment": "I do not know much about 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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hklqi8B45S", "reviewer": "AnonReviewer1", "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": "The paper considers distributed stochastic gradient descent, where some (unknown) compute nodes may be unreliable. New heuristics for filtering out replies from unreliable servers are introduced alongside a new protocol that helps keeping nodes in sync.\n\nIn general, I miss a more clear indication of how the individual contributions are different from other methods. I am also missing more detailed ablation studies showing which of the new ideas contribute the most to efficient learning. As far as I can tell, the experiments do not really show an improvement over existing methods in this domain.\n\nThis is not my area of expertise, but I cannot recommend the paper for publication in its current form as\n(a) it's not clear to me that the paper improves on existing methods, and\n(b) it's not clear to me what the real novelty of the work is.\n\nPost-rebuttal:\nI acknowledge the response of the authors. They clarified some aspects for me, and the paper appears to have improved over the rebuttal period.\nI did not change my rating, but I want to emphasize that this is only because my knowledge of this field is so limited. My rating is largely based on \"gut feeling\" rather than actual knowledge, and I won't argue against acceptance.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BkxhT9ISqB", "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": "My review got deleted because the title kept creating an unexplained error.\nHere's another shorter attempt\n\nI haven't really followed along the literature for this. But from the results, it's not immediately clear to me what practical setup this is useful in. The authors assume perfect network synchrony, they have a 25% overhead on TensorFlow and they have a comparison to another algorithm that operates under different assumptions.\n\nWho would ever use this and why? What's the plan for getting data to the untrusted workers?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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: This paper is concerned with learning in the context of so-called Byzantine failures. This is relevant for for example distributed computation of gradients of mini-batches and parameter updates. The paper introduces the concept and Byzantine servers and gives theoretical and practical results for algorithm for this setting.

The reviewers had a hard time evaluating this paper and the AC was unable to find an expert reviewer. Still, the feedback from the reviewers painted a clear picture that the paper did not do enough to communicate the novel concepts used in the paper.

Rejection is recommended with a strong encouragement to use the feedback to improve the paper for the next conference.
Decision: Reject