Distributed Momentum for Byzantine-resilient Stochastic Gradient Descent
Authors: El Mahdi El Mhamdi
Rachid Guerraoui
Sébastien Rouault
Venue: ICLR 2021 Poster (2021)
Keywords: Byzantine SGD
Distributed ML
Momentum

Abstract: Byzantine-resilient Stochastic Gradient Descent (SGD) aims at shielding model training from Byzantine faults, be they ill-labeled training datapoints, exploited software/hardware vulnerabilities, or malicious worker nodes in a distributed setting.
Two recent attacks have been challenging state-of-the-art defenses though, often successfully precluding the model from even fitting the training set.
The main identified weakness in current defenses is their requirement of a sufficiently low variance-norm ratio for the stochastic gradients.
We propose a practical method which, despite increasing the variance, reduces the variance-norm ratio, mitigating the identified weakness.
We assess the effectiveness of our method over 736 different training configurations, comprising the 2 state-of-the-art attacks and 6 defenses.
For confidence and reproducibility purposes, each configuration is run 5 times with specified seeds (1 to 5), totalling 3680 runs.
In our experiments, when the attack is effective enough to decrease the highest observed top-1 cross-accuracy by at least 20% compared to the unattacked run, our technique systematically increases back the highest observed accuracy, and is able to recover at least 20% in more than 60% of the cases.

Published as a conference paper at ICLR 2021
DISTRIBUTED MOMENTUM FOR BYZANTINE- RESILIENT STOCHASTIC GRADIENT DESCENT
El-Mahdi El-Mhamdi
Ecole Polytochnique, France
el-mahd1.co el -mhamd 1
edu
Rachid Guerraoui
Ecole Polytochnique Fédérale de Lausanne (EPFL), Switzerland
rachid. guerraoui@epfl.co
Sébastien Rouault *
Ecole Polytochnique Fédérale de Lausanne (EPFL), Switzerland
sebastien www.ullteppl...c..
ABSTRACT
rryaantinereeiilient Stochastic Gradient Descent (SGD) aims at shielding model training from Byzantine faults, be they ill-labeled training data- points, exploited software/ software/hardwaro hhadware vulnerabilities, or malicious worker nodes in a distributed setting. Two recent attacks have been challenging state-of-the-arl defenses though, often successfully precluding the model from even fitting the training set. The main identified weakness current defenses is their requirement. of sufficiently low cariance-norm ratio for the stochastic gradients. We propose a practical method which, despite increasing the variance, reduces the variance-norm ratio, mitigating the identified weakness. We assess the effectiveness of our mothod over 736 different training configurations, comprising the 2 statc-of-the-ar attacks and 6 defenses. For confidence and reproducibility purposes, each configura- tion run times with specified seeds to 5), totalling 3680 runs. In experiments, when the attack is effective enough lo decrease the highest ob- served top-1 cross-accuracy by at least 20% compared to the unattacked run, our technique systematically increases back the highest observed accuracy, and able to recover least 20% in more than 60% of the cases.
1 INTRODUCTION
Stochastic Gradient Descent (SGD) is one of the main optimization algorithm used throughout machine learning. Scaling SGD can mean aggregating more but inevitably less well-sanitized data, and distributing the training over several machines, making SGD even more vulnerable to Byzantine faults: corrupted/ seruuteed/maliiious malicious training datapoints, software vulnerabilities. etc. Many Byzantine-rresilenn techniques have been proposed to keep SGD safer from these faults, e.g. Alistarh al. (2018): Damaskinos al. (2018); Yang & Bajwa (219b)) TianXiang al.
(2019): Bernslein el. al. (2019); Yang & Bajwa (019aa) Yang el al. 2019): Rajput et al. (2019); Muroz-
al. (2019). These techniques mainly use the same versarial model (Fig- ure central, trusted parameter server distributing gradient computations to several work- ers, a minority which is controlled by an adversary and can submit arbitrary gradients.
Two families of defense techniques schemes, inspired by coding thcory. This approach has strong resilience guarantees, but
be distinguished. The first employs redundancy
Author list written in alphabetical order, as for all the papers from the DCL EPFT.

---

Published as a conference paper at ICLR 2021
Max. top-1 anrurry
1.0
0.8
0.6
0.4
0.2
0.0
Standard
Our formulation
Our formulation formulation
Standard
Standard formulation
Our formulation
Standard formulation formulation
Our
formulation
[d] Figure We report on the highest measured top-1 cross-accuracy while training under either of the two studied, state-of-the-art attacks. [a. bl: convolutional model (Section 4.1% for
[a]
[b]
CIFAR-10 10 under the attack from Baruch et al. (2019), and [c, d]: a fully connected model for Fashion-MNIST (Xiso et all 2017) under the attack from Xie et al. (2019a). Roughly half the workers implements the attack in la, c], and a quarter does [b, d] see Section
4.1 Each experiment is run 5 times. The dotted blue line is the median of the maximum top-1 cross-accuracy of the 5 runs without attack, and the boxcs aggregate the maximum top-1 cross-accuracy obtained under attack with each runs of the studied defenses. Over 736 different combinations of attacks, defenses, datasets, elc (tolalling of 3680 runs), our method consistently obtain least similar, if not substantially better performances (lower minimal loss, higher maximal top-1 I cross-accuracy) than the standard formulation. Notably, our formulation obtains these results with no additional computational complexity.
its requirement, to share data between workers makes this approach unsuitable for several classes of applications, e.g. when data cannot be shared for privacy, scalability or legal reasons. The second family uses statistically-robut this paper. The underlying idea is simple. At each training step, the server aggregates the stochastic gradients computed by the workers into one gradient, using a function called Byzantino-resilien Grudient Aggregation Rule (GAR). These statistically-robust GARs are designed to produce at each step gradient that is expected to decrease the loss.
aggregation schemes, and is the focus of
Intuitively, one can think of this second lamily different formulations of the multivariate median. In particular, if the non-Byzantine gradients were all equal al each step, any different (adversarial) gradient would be rejected by each of these medians, and no attack would succeed. But due to their stochastic nature, the non- non-Byzantine gradients are different: their variance is strictly positive. Formal guarantees typically require that the variance-norm ratio, the ratio between the voriance of the non- Byzantine gradients and the norm of the expected non-Byzantine gradient, remains below certain constant (constant which depends on the GAR itself and fixed hyperparameters) Intuitively, this notion of variance-norm ratio can be comprehended quite analogously to the inverse of the signal-to-noie noise ratio (i.e. the "noise-to-sigee signal" ratio) in signal processing.
any given statistically-robust GAR
However, Baruch et al. (2019) noted that an attack could send gradients that are close to non-Byzantine outlier gradients, building an apparent majority of gradients that could be sufficiently far from the expected non- non-Byzantine gradient increase the loss. This can happen against most statistically-robus GARs in practice, as the variance-norm ratio is often too large for them. Two recent attacks (Baruch et al. 2019 Xie et al. 2019a) were able to exploit this fact to substantially hamper the training process (which
experiments confirm).
The work presented here aims at (substantially) improving the resilience of stat statistiaally robust GARs "also in practice", by reducing the variance-nome ratio of the gradients received by the server. We do that by taking advantage of an old technique normally used for acceleration: momentum. This technique is regularly applied at the server, but instead propose to confer upon each distributed worker, offeetively making the Byzantine-rosilient GAR aggregate accumulated gradients. Crucially, there is no computational complexity attached to our reformulation: it only reorders operations in existing (distributed) algorithms.
Contributions. Our main contributions can be summarized follows:
2

---

Published as a conference paper at ICLR 2021
A reformulation of classical/Nesterog momentum which can significantly improve the effectiveness (Figure [ of any statistically Gradient Aggregation Rule (GAR). We formally analyze the impact of our reformulation on the variance-norm ratio of the aggregated gradients, ratio on which the studied GARs assume an upper bound.
An extensive and reproducible set of experiments substantiating the effectivemess of our reformulation of momentum in improving existing defenses against state-of-the-art atlacks.
Paper Organization. Section 2 provides the necessary background. Section B] presents our distributed momentum scheme and provides some intuitions on its effects. Formal develop- ments of these intuitions are given in the appendix. Section describes our experimental settings in details, before presenting and analysing some of our experimental results. The appendix reports on the entirety of our experiments, and details how they can be reproduced (in one command, graphs included). Section 5 discusses related and future work.
BACKGROUND
2.1 BYZANTINE DISTRIBUTED SGD
Stochastic Gradient Descent, (SGD). We consider the classical problem of optimizing a non-convex, differentiable loss function Q: gd + R, where Q (0,) & E ENDD [q (0,, for a fixed data distribution D. Ideally, we seek 0* such that 0 arg ming (Q (0)).
We employ mini-batch SGD optimization. Starting from initial parameter 0g E Rd, at every step t 0, b samples (xt²) ...II xx()) are sampled from D to estimate one stochastic gradient 9. - Ek Vq 02 F7
(1)
(k) VQ (0,). This stochastic gradient then used to update the
parameters 0,, with: 0(41 0. Ot 9t. The sequence ar 0 is called the learning rate.
Classical and Nesterov momentum One field-tested amendment to mini-batch SGD is clossical momentum (Polyak) 1964p. where each gradient keeps an exponentiall-decressing effect on every subsequent update. Formally: 0.41 0, at En p
"yu with < p < 1. proposed another revision. Noting 1, the velocily vector, v 0, formally:
Nesterov 1983
b Σ Vg (0, a4 14 x(1) k=1
2441 -2 +
0.11 0, at 1/41
Compared classical momentum, the gradient is estimated 0 ar μ un instead of 0,.
Distributed SGD with Byzantine workers. We follow the parameter server model ct ct al. 2014h: one single process (the parameler server) holding the parameter vector 02 E IRd, and n other (the workers) estimating gradients. Among these n workers, up < are said Byzantine, iee adversarial. Unlike the other n - honest workers, these f Byzantine workers can submit arbitrary gradients (Figure P
Parameter server
Byzantine workers (colluding)
Honest workers
Figure 2: A parameter server sctup with n = 8 workers, among which 3 are Byzantine (i.e., adversarial) workers. A black line represents bidirectional communication channel.
At each step t, the parameter server receives dif- (n) among which f are arbi- trary (submitted by the Byzantine workers). So the
ferent gradients giz) ...g;. (1)_.))()),
update equation becomes: 0,41 = 0, ar G,, where:
G, A Σ
--- (1))
g
(1)
NNamely 736 3680 seeded rums, and one single script reproduce all of results.
3

---

Published as a conference paper at ICLR 2021
Function Fis called Gradient Aggregation Rule (GAR). In non-Byzantine settings, averaging ...
used; formally: F(gi (1) ......9''' () = - ( In the presence of Byzantine workers, more robust aggregation is performed with Byeantine-resllien GAR. Sections 2.2 and 2.3 respectively describe the 6 existing GARs and attacks studied in this paper.
Adversarial Model. The goal of the adversary is to impede the learning process, which is defined as the maximization of the loss Q or, more judiciously for the image classification tasks tackled in this paper, as the minimization of the model's top-1 cross-aceuracy, The adversary cannot directly overwrite 02 at the parameter server. The adversary only submits arbitrary gradients to the server per step, via the f Byzantine workers control We assume omniscient adversary. In particular, the adversary knows the GAR used by the parameter server and, at each step, the adversary can generate Byzantine gradients dependent the honest gradients submitted at the same step and any previous step.
2.2 BYZANTINE-RESIALE GARs
We briefly present below the 6 studied Gradient Aggregalion Rules (GARs). These Rs are Byzamfine-resllint (Section A), a notion first introduced by BBlacchadd et al. (2017) under the name (a, BByzantine-reiileneett Byzantine- resilien GAR guarantees convergence even in an adversarial setting.
When used within its operating assumptions,
Let n be the number of gradients the parameter server received from the workers (Figure 2). and let f be the maximum number of Byzantine gradients the GAR must tolerate.
Krum (Blanchard al. 2017). Each received gradient is assigned score. The score of gradient 2 is the sum of the squared fz-distances between x and the n - f- - closest gradients 2 gradients with
to The aggregated gradient is then the arithmetic mcan of the the smallest scores. This variant is called Multi-Krum in the original paper.
To be proven (a, fy-Byzantine resilient, Krum requires the variance of the honest gradients E|G - E to be bounded above follows:
2 n- f (n maa-fam f- 2) f2 (m ( 111)
E ||G, Eg < ||
n 1- -2
Median Yin et al. 2018). The coordinate-wits wise median of the n reccived gradients. Median proven (a., Byzantii resilience with the following condition on the variance-norm ratio:
(n - n) ||
F.G < |,
Trimmed Mean YYn et al. 2018). The coordinate-wist trimmed-mean of the n received gradients. The brimmed-mean of values the arithmetic mean, after the f smallest and the f largest values have been discarded, of the remaining values. From Theorem 1 of Xie et al. (2018b), we can derive the following condition on the pariance-nore ratio:
2(f+1) E 119, EG,1 || (n 2f-
(4)
The coordinato-wist wise arithmetic mean of the f closest values to the coordinate-wise trimmed-mean. From Theorem 2 of Xie et al. (2018b):
Phocas Xie et al.
2018b).
4 12 (f( E E - -EG,1 < |E
(5)
(n-
EExempli gratia, with 10 classes, the worst possible final accuracy is arguably 0.1. "Said otherwise, the Byzantine workers can collude.
4

---

Published as a conference paper at ICLR 2021
McaMed Xie et al.
2018a). Same Phoeas, but with median replacing trimmed-mean.
Theorem of Xie et al.
(2018a] provides the following condition:
10 (n - 1) E E < ||
(6)
Bulyan El-Mhamdi et al. 2018). This is composite GAR, iterating on another GAR in
a first selection phase. In the remaining of this paper, Bulyan will use Krum, so the first phase selects 1 f- gradients, at each iteration removing the highest scoring gradient. The aggregated gradient is the coordinate- -wiee arithmetic mean of the 4 2 closest values the (coordinate-wise) median of the selected gradients.
The theoretical requirement on the variance-norm ratio are the same as the ones of the underlying GAR. That is, in this paper, they are the same as Krum (Equation 2
2.3 STUDIED ATTACKS
The two state-of-tho-art attacks, that recently appeared in the literature, follow the same core principle. Let Rzo be a non-negative factor, and a, E Rd allack vector which value depends on the actual attack used (see below for possible values of a,) At each step i, each of the f Byzantine workers submits the same Byzantine gradient: It t where Ii is an approximation of the real gradient VQ (0,) at step t. The value of is fixed (see below).
A Little is Enough (Baruch et al. 2019 In this attack, each Byzantine worker submits Ir + ae with a, - -d, the opposite of the coordinate-wis standard deviation of the honest gradient distribution G, Our experiments use E = 1.5, as proposed by the original paper.
Fall of Empires (Xie al. 2019a). Each Byzantine worker submits (1 --5) 5) Te. i.e., at 9c- c 1010 -1, 0, 0.1, 0.5, 1, 10, 100), our experiments use
The original paper tested c CE
1.1, corresponding in the notation of the original paper to A (1 - -) - (1 1.1) = 0.1.
3 MOMENTUM AT THE WORKERS
Intuitively, the Byzintinc-rosilient GARs (Section 2.2 rely the honest gradients being sufficiently clumped (formalized in e.g. Equation 2 to Equation G). In the edge case where every honest gradient equal (i.e. no stochastic noise), no atlack can affect the learning: there is by assumption strict majority of identical honest gradients. On the contrary when the honest gradients are "spread", L.e their variance is large enough compared to their norms, the attack vectors can form a majority by relying on a few outlier (but honest) gradients (Baruch et al. 2019), and so substantially influence the aggregated gradient.
Momentum makes the paramcters 0, travel down the loss function with inertia, accumulating both the real gradient VQ (1) and the error (i.e. here, the slochastic noise) 9, VQ (t)- Intuitively, the accumulation of errors grows at moderate rale, as past errors can be partially compensated by future ones. But when consecutive VQ (1) have sufficiently low solid angles, past real gradients do not compensate future real gradients: the norm of G, grow "faster" (for each new step) than its variance, mitigating the potential impact of an attack.
3.1 FORMULATION
From the formulation of momentum SGD in a distributed setting (Equation 1
G,
(1)
(m)
we instead confer the momentum computation on the workers:
G, a F
Du (n)
(7)
(1)
"This factor made this attack consistently successful in the original paper.
5

---

Published as a conference paper at ICLR 2021
Notations. In the remaining of this paper, we call the original formulation (momentum) at the server, and the proposed, revised formulation (momentum) at the worker(s). The quantities G. .....)) will be called the submitted gradients (at step t). At step t, the variance-none ratio is computed on the honest subset of: 9i ... oi if momentum at the server is employed, otherwise (((") if momentum at the workers is used instead.
Formal analysis. The formal analysis of the impact of our technique on the variance-norm
ratio of the aggregated gradients available in the appendix, Section
EXPERIMENTS
Our experiments cover 2 models, datasets, the 6 studied defenses under cach of the 2 state- of-the-art attacks different fractions of Byzantine workers (cither half or a quarter), using Nestorov instead of classical momentum, plus unattacked settings where each worker is honest and the GAR R. is mere averaging. Since our theoretical results (Section B] suggest that smaller learning rates may reduce the variance-none ratio, two learning rate schedules (an optimal and a smaller one) are also tested. For reproducibility and confidence in the empirical benefits of our reformulation, we test every combination of the hyperparameters mentioned above, and each combination is repeated times with specified seeds (1 to 5, totally 3680 runs).
The tools we developed to implement our reformulation captures ~0 metrics, including the evolution of the average loss, top-1 cross-accuracy and variance-norm ratio of the submitted gradients. In this section and Section F we specifically report on these metrics.
4.1 EXPERIMENTAL SETUP
We use compact notation to define the models: L L(#outputs) for fully-connected linear layer, R for ReLU activation, S for log-softmax, C(#channels) for a fully-connected 2D-con- volutional layer (kernel size 3, padding 1, stride 1), M for 2D-maxpool (kernel size 2), B for batch-normalivation, and D) for dropout (with fixed probability 0.25).
We use the models from respectively Baruch al.
2019 and Xie et al. 2019a
Fully connected
Convolutional
Model
(3, (.B-CC(18)-R-BBMB.
-C((28)-RF (11128)-RBBC(IUE
Datasets
MNIST, Fashion MNIST (83 samples/ (aamplesggrdient) gradient)
CIFAR-10, CIFAR-100 (50 samples comples/gradient /gradient) n = 25 f E (11,5}
#workers
n= 51 f f (24, 12]
For model training, we use the negative log likelihood loss and respectively 10-4 and 10-2 l-regulaariztion for the fully connected and convolutional models. We also clip gradients, en- suring their norms remain respectively below 2 and 5 for the fully connected and convolutional models. Regarding evaluation, we use the top-1 cross-accuracy over the whole test set.
Datasets are pre- processed before training. MNIST receives the same pre-processing as in Baruch al. (2019): an input image normalization with mean 0.1307 and standard deviation 0.3081. Fashion MNIST, CTFAR-10 and CTFAR- 100 are all expanded with horizontally flipped images. For both CIFAR- 10 and CIFAR- 100, a per-channel normalization with means 0.4914, 0.4822, 0.4465 and standard deviations 0. 0.2023, 0.1994, 0.2010 (Lu 2019) has been applied.
We denote by f the number Byzantine workers either to the maximum for which Krom can be used (roughly an half: f m=3 the maximum for Bulyan (roughly quarter, n=3 J). The attack factors e, (Section 2.3 set to constants proposed in the literature, namely é = 1.5 for Baruch et al. (2019) and Et = 1.1 for Xie et al. (2019a).
TTo the best of our knowledge, putting aside simple attacks (e.g. sending attack gradients sampled from Gaussian distribution) tested in each defense papers, other attackk has been published.

---

Published as a conference paper at ICLR 2021
We also experiment two different learning rates. The first and largest is selected as to maximize the performance (highest final cross-accuracy and accuracy gain per step) of the model trained without Byzantine workers. The second and smallest is chosen as to minimize the performance loss under attack, without substantially impacting the final accuracy when trained without Byzantine workers. The fully connected and convolutional models are trained respectively with μ = 0.9 and & = 0.99. These values were obtained by trial and error, to maximize the accuracy gain per step when there is no attack.
Reproducibility. Particular care has been taken to make our results reproducible. Each of the runs per experiment are respectively seeded with seed 5. For instance, this implies that two experiments with same seed and same model also starts with the same parameters 9.- To further reduce the sources of non-determinism, the CuDNN backend is configured in de- terministic mode (our experiments ran on two GeForce GTX 1080 Ti) with benchmark mode turned off. We also used log-softmar + nll loss, which is equal to softmar + cross-entropy loss, but with improved numerical stability on PyTorrh.. We provide our code along with script reproducing all of our results, both the experiments and the graphs, in one command. Details, including software and hardware dependencies, are available in Section
4.2 EXPERIMENTAL RESULTS
This section reports on the evolution of the average loss, top-1 cross-accuracy and variance- norm ratio of the submitted gradients. Scction E the appendix reports on the entircty of
our experimental results, and Section D additionally experiments with much larger model.
One first important remark that our new formulation either obtain similar, or (subtantially) increased maximum top-1 cross-accuracy measured, compared to the standard formulation in the exact same settings. Namely, in only 4 pairs of runs (0.23% of all the tested pairs) did our formulation lead to decreased maximum top-1 cross-accuracy. Also, these decreases were only observed with the fully conmected model, using Krum against [ie et al. (019a)), and for each of these 4 runs using any of the 4 other seeds made the decrease disappear.
In all of our experiments, we observe a strong correlation between higher top-1 cross- accuracies and lower average losses; e.g. see Figure 4 The two ffate-of-thh-atte attacks decreased the accu- racy by at least 20%, compared to the unattacked case (see "No attack" in Figure 3), in 25.80% and 70.80% of the runs with respectively the fully connected and connolutional models.
Focusing on the convolutional model, when roughly an half of the workers are Byzantine, both attacks actually succeed in decrcasing the accuracy by at least 20% in 100% of our rums. Our technique manages to recover at least 10% and 20% in respectively 79.75% and 49.25% of these runs. When roughly quarler of the workers are Byzantine, the attacks decrease the accuracy by at least 20% in 46.46% of our runs. Our technique then manages to recover at least 20% in 95.07% of these runs. Figure 3 shows a fraction of these runs.
Technically, our reformulation aims at reducing the variance-norm ratio of the aggregated gradients. Intuitively, this ratio expected to increase as the loss docreasos; more corroctly as the norm of the gradient decreasos. For instance, Figure 5 displays the veriance-norm ratios of Trimmed Mean and Bulyun using the same settings as Figure At least before the final cross-accuracy is reached, our technique consistently decreases the variance-norm ratio of the aggregated gradients. Also, we consistently observed in the experiments that reducing the learning rate indeed reduces the variance-norm ratio (e.g. Figure 5 t> 1500).
RELATED AND FUTURE WORK
Approaches. The Byzantine abstraction is very general fault model that has long been studied in distributed computing (Lamport et al.] 1982). The standard, golden solution for Byzantine fault tolerance is the state machine replication approach (Schncidor) 1990). This approach is howevcr based on replication, which is known to be unsuitable for distributed machine lcarning and stochastic gradient descent.
Alternative Byzantine-resilett
Chen et al. (2018) was the first Byzantine-resiliss mechanism based on a redundoncy scheme rather than statistical robustness. While the proposed mechanism is not vulnerable to the
7

---

Published as a conference paper at ICLR 2021
Momentum at the server
Momentum at the workers
Classical momentum
0.8
10g-1 11100000000000000000000000000000 (1oss-acuussc
Krum
Thee1 enve-eeeeee
No attack
03.6
Median
0.6
Krum
Trmasc
Median
Phanaa
Trmoon
Meamed
Phoeos
0.2
Bulyan
0.3
Meamed
Bulyan
0.0
0.0
Step number
Step number
Nesterov momentum
Tap-1 07005 000 wwcurary
No atlack
Top-1 mmno-acctiiee
0.8
No atlack
0.6
0.6
Median
Median
Trmeaa
0.4
Trmeno
Phoacss
Phocse
Moxmed
Moxmed
Bolyan
Bolyan
0.0
0.0
2500
9000
Step uimber
Step
Figure 3: CIFAR-10 and the convolutional model (Section 4.1 with 25, f 5 and ar 0.01 i < 1500 else a₂ = 0.001, under attack from [Barcch et al. 2019). Each line and colored surface correspond to respectively the average and standard deviation of the top-1 cross- accuracy over 5 seeded runs. Only two parameters change between graphs: where momentum is computed (at the
at the workers), and which flavor of momentum is employed.
Momentum
Momentum the
Nesterov momentum
100. 1100000-0000 o10e-00uuic
0.8
No attack
Krum
Tost prreerrettir
0.8
No attack
Mislian
Melian
Trmcon
Trmoun
Phocas
0.4
Phocas
Mestzed
Mexzned
0.2
Bulyan
0.2
Hulyan
0.11
500
1000
1501
2000
25101
3000
S001
10II
1500
2001
25011
3001
Step number
Step number
Nesterov momentum
No attack
No attack
Krum
Krum
Averuge
Median
Average
Mecion
TriDean
Trmsen
Phonaa
Phoeus
Mouned
Menmed
Bulyan
Bulyan
300
1000
1500
2000
20000
3000
2001
1000
1500
2000
2500
300I
Step number
Step cumber
Fig Figure Accuracy and average loss, CIFAR-100 and the convolutional model. with 25, f and a, = 0.01 if < 1500 else 0.001, under attack from (ie et al.
2019a)
Trimmed Mean
Bulyan
20
15
45
10-
Varionoe-non
30
Trmcan 'sample' Trmea "eubmit"
Bulyan "sample' Bulyan "subenis"
800
1000
1500
2000
2500
3000
0
500
1000
1500
2000
2500
3000
Step number
Step number
Figure 5: Same settings as in Figure variance-nore ratios of Trimmed Mean and Bulyan with momendum al the workers. "sample" corresponds to the variance-norm ratio of the sampled gradients, and "submit" to the variance-norm ratio of the submitted gradients.

---

Published as a conference paper at ICLR 2021
attacks discussed in this paper, it induces (due to the redundancy) substantial computational costs compared to statistically-robrs techniques. [Rajput et al. (2019) combines Chhn GARs into hybrid system, and achieves an improved aggregation time. Under the requirements of both redundancy-basse
et al. (2018) with statistically-
schemes and statistically- robust GARs, Rajputt et al. (2019) can significantly decrease the voting power of the advensary, and can consequently also deflect attacks in these cases. [ et al. (2019b), and its follow-up Xiee 2019), introduced the concept of suspicion-baseee fault-tolerance: each gradient is assigned a score based on the loss obtained by descending with this gradient only. The lowest scoring gradicnts are then filtered-out, and the remaining gradients are averaged and used to update the model. Compared to slalislically-robusl approaches, such a scheme does not rely on sufficiently low variance-norm ratios, and gradients could be processed independently. This advantage comes at the expense of a substantial computational load on the parameter server, as the server has to compute several forward passes for each received gradients, basically doing half the work of each worker again (the workers also have backpropagation passes). Most importantly, the success of such a technique is conditioned to the quality of the loss estimations at the server: if the cstimation is biased (e.g. the server's dataset is "different" than the workers' ones), : has a high variance (e.g. the server's ' batch size is "too" small), or if the "hard threshold" e used is too large (would accept. Byzantine gradients) /Loo small (would refuse even honest gradients) the defense might be muefective/harmne
Momentum-based Variance Reduction. Our algorithm is different from Cutkosky &
Orabona 2019). as instead of reducing the variance of the gradients, we actually increase it (Equalion What we seek to reduce is the mariance-morry ratio, which is the key quantity for any Byzantin-resslient GAR approximating a high dine-siimniioaall median, e.g. Krum, Median, as well as Yang & Bajwa (2019b Chen et al. (2017):
et al. (2019 Some of the ideas introduced in Cutkosky & Orabona (2019) could heless help Turther improve Byzantine resilience. For instance, introducing an adaptive learning rate which decreases depending on the curvature of the parameter trajectory is an appealing approach
to further reduce the variance-norm ratio (Equation 10). The computation of momentum at the workers has also been used in the literature for the purpose of gradient compression ct al. 2018). These techniques are nevertheless not (meant to be) Byzantino-resilien
(Lin
Future Work. The theoretical condition to reduce the variance-norm ratio of the submitted gradients (compared to the variance-norm ratio of the sampled gradients at the same step), in Section B shows that momentum at the workers is a doublo-edged sword. The problem is that st can become negative: the norm of the momentum gradient would then be decreased, increasing the variance-norm ratio. While the ability to cross narrow, local minima is recognized as an accelerator (Gohl 2017): for the purpose of Byzantine-resillenee we want to ensure momentun at the workers does not increase the variance-norm ratio (compared to the variance-nore norm ratio of the sampled gradients at the same step). The theoretical condition for this purpose is given in Equation
9 One simple amendment would then be to use momentum at the workers when Equation g is satisficd, and fallback to computing at the server otherwise. Also, a more complex, possible future approach could be to dynamically adapt the um factor μ4, decreasing it as the curvature increases.
Asynchronous SGD. We focused in this work on the synchronous setting, which received most of the attention in the Syzantine-resilient literature. Yet, we do not soe any issue that would prevent our work from being applied in asynchronous settings. Specifically, combining our idea with filtering scheme such as Kardam (Damaskinos et al., 2018) is in principle possible, as this filter and momentum commute. However, further analysis of the interplay between the dynamics of stale gradients and the dynamics of momentum remain necessary.
Byzantine Servers. While most of the research on Byzantine-resilienee gradient descent has focused on the workers' side, assuming reliable server, recent efforts have started tackling Byzantine servers (El-Mhamdi et al.] 2020). Our reduction of the variance-norm ratio strengthens the gradient aggregation phase, which is necessary whether we deal with Byzantine workers or Byzantine servers. An interesting open question is whether the dynamics of momentum could positively affect the model drift between different parameter servers in a Byzantine context. Any quantitative answer to this question could enable the use of our method in fully decentralised Byzantine resilient gradient descent.
9

---

Published as a conference paper at ICLR 2021
6
ACKNOWLEDGMENTS
This work has been supported part by the Swiss National Science Foundation (FNS grant 1220001_1825444
We would also like to acknowledge here and thank the anonymous individuuls who partook in the review of this work and its code, in this final version and previous drafts, for their valuable time and inputs.
REFERENCES
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in Newral Information Processing Systems 31: Anvuuul Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 4618 4628, 2018
Moran Baruch, Gilad Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Advances in Newral Information Processing Systems 32: Annual Conference on Nearal Informalion. Processing Systems 2019, 8-14 December 2019, 9, Long Beach, CA, USA, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Peva Blanchard, El-Mahdi El-Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 119 129, 2017.
Lingjiao Chen, Hongyi Wang, Zachary B. Charles, and Dimitris S. Papailiopoulos. DRACO: byzantine-resilient distributed training via redundant gradients. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmssüsssan, Slockholm, Sweden, July 10-15, 2018, pp. 902 911, 2018.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. CoRR, abs/ Abs/1705.000 054999 2017.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non- convex SGD. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Informa- tion Processing Systems 32: Annuul Conference on Neural Information Processing Sys- tems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 15210- 15219, 2019. URL http::/paperr: http:/paprrs.ips...... nips. cttpccccpppee wwtpppppp//////ecceeoccceeeeeeet http:/ppppp9999/0 http://655..mmmtmmttmmmooooaaaaa waw.-------a-deeae-ae-eeeea reduction in- non- convex sgd
Georgios Damaskinos, El-Mahdi El-Mhamdi, Rachid Guerraoui, Rhicheck Patra, and Mahsa Taziki. Asynchronous byzantine machine learning (the case of SGD). In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssmüsssnn Stockholm, Sweden, July 10-15, 2018, pp. 1153 1153-1162, 2018
El-Mahdi El-Mhamdi, Rachid Guerraoui, and Sébasticn Rouault. The hidden vulncrability of distributed learning in byzantium. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssm, Stockholm, Sweden, July 15, 2018, pp. 3518 3527, 2018.
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lê Nguyên Hoang, and Sébastien Rouault. Gemuinely distributed byzantine machine learning. In Yuval Emak and Christian Cachin (eds.), PODC '20: ACM Symposium
Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pp. 355 364. ACM, 2020. doi: 10.1145/3382734.
3405695. URL https: https://doi.orgge 1ttp://0..111533333333334443 3405699
10

---

Published as a conference paper at ICLR 2021
Gabriel Goh. Why momentum really works. Distill, 2017. doi: 10.23915/distill.oom distill.00006 URL
Bumsoo Kim. Best cifar- cifar-100 results with wide-residual networks using pytorch.
https://github. com htts://gttttuoccoooo/lllelo//o/p http:///idddereeeet..ttoooroooo 2020. MIT license, using com- mit 299204006615//000666000400002220
Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-440)) 1982. doi: 10.1145/3571772.5771
Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor- Vin- Su. Scaling distributed machine learning with the parameter server. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI '14, Broomfield, CO, USA, October 6-8, 2014. pp. 583-598, 2014.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Doep gradient compression: Reduc- ing the communication bandwidth for distributed training. In International Conference Learning Represenlations, 2018. URL http:////ppaaerreeeeeeeefrrrrrnn
Kuang Liu. Train ci with pytorch, 2019. URL http:p::///ittbbbcco///uum
Luis Muñoz- Muñoz-Gonzálee González, Kenneth Co, and Emil C Lupu. Byzantine-robust federated machine learning through adaptive model averaging, orXiv preprint arXiv:1909.0512 05111, 2019.
Yurii Nesterov. A method for solving a convex programming problem with convergence rate (1/k2)). Soviet Mathematics Doklady, 27:372 367, 1983.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4:1 4:1-17, 12 1964. doi: 10.1016/004 /0011- 3533(344)
Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy-basse framework for faster and more robust gradient aggregation. Neural Information Processing Systems, 2019.
Fred B Schncider. Implementing fault-tolcrant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR), 22(4):299-319 1990.
WANG TianXiang, ZhongLong ZHENG, TANG ChangBing, and PENG Hao. Aggregation rules based on stochastic gradient descent byzantine consensus. In 2019 IEEE 8th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), pp. 317-324 TEFF, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist. novel image dataset for benchmarking machine learning algorithms. arXie preprint arXiu: 708. 0774077777 2017.
Cong Xie. Zeno++: robust asynchronous SGD with arbitrary number of byzantine workers. CoRR, abs/ abs/1903.07700, 2019.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine- tolerann SGD,
CoRR, abs/1802.10116, 2018a. URL http:://rxii... org/abs//8000 10116
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Phocas: dimensional byzantine-resilien stochastic gradient descent. CoRR, 180500985.,,, 2018b. URL http://arxiv org/
Abs/1806.09683
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall empires: Breaking byzantine- tolerant SGD by inner product manipulation. In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv Israel, July 22-25, 2019, pp. 83, 2019a.
11

---

Published as a conference paper at ICLR 2021
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with puspicion-based foult-tolerance. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 6893 6901, 2019b.
Zhixiong Yang and Wahcod U Bajwa. Bridge: Byzantinc-resilient decentralized gradient descent. arXiv preprint arXiv:1905 0900.00088,,,, 2019a.
Zhixiong Yang and Waheed U Bajwa. Byrdie: Byzantine-resilient distributed coordinate descent for decentralized learning. JEEE Transactions on Signal and Information Processing Networks, 2019b.
Zhixiong Yang, Arpita Gang, and Waheed U Bajwa. Adversary-resiliett inference and machine learning: From distributed to decentralized. ar preprint arxiv: 1ix:1908..0 908.000499...9 2019.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter L. Bartlett. Byzantinc-robust distributed learning: Towards optimal statistical rates. In Proceedings of the 35th Inter- national Conference on Machine Learning, ICML 2018, Slockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 5636-5645, 2018.
A BYZANTINE RESILIENCE: DEFINITION
Let n be the number of gradients the parameter server received from the workers (Figure 2. and let f be the maximum number of Byzantine gradients the GAR must tolerate. Some other notations below are reused from Section 2.1
G. be f independent, "honest" gradients following the same distribution GG and let (n-1+1) gin) E (IR)) be arbitrary gradients, each possibly dependent G, and the "honest" gradients. A GAR F is
Definition 1. Without loss of generality, let 9. "..
gf gi..!""""""" (n-f)
said (a, -yyzantne resilient if and only if 9t F (() ..... ......!()) satisfies:
(1)
(n)
1. E 91, gt
(1)
2. Vr E 324344)
E 99.
is bounded above by linear combination of the terms with (k, (Nr)k+1 and rı +... Fk =.
E
(1)
E
9:
(1)
B MOMENTUM AT THE WORKERS: EFFRCTS
We compare the variance-norm ratio of the non non-Byzantine subset of the sampled gradients ...g,")
ge ...9; g.") against the variance-norm ratio of the non- non-Byzantine subset of the submitted
gradients G. ... ....(") when classical momentum computed at the workers.
We denote by Eg, A (0,) the "real" gradien at step
Let X₂ E 9, be the real gradient's norm at step
Let 0, A V | E 1 be the standard deviation of the real gradient at step t. The variance-norm ratio of the non-Byzantine subset of the sampled gradients at step t is:
A
0,
X
"In this analysis, the expectations are by default conditioned on the past randomness (all what happened up step f) from the (n (n-ftt b data-points sampled, at each past step, by the (n f) honest workers estimate their respective gradients.
12

---

Published as a conference paper at ICLR 2021
We will now compute the variance-nome ratio of the non-Byzantine subset of the submitted gradients. Let G with _ å 0, be the gradient sent by any honest worker i at step t, i.c.:
G
(8)
Iu
u 0
The numerator of the variance-niom ratio is, for any two honest worker identifiers o j:
G
(
E
=E
gt μ G
(1)
(1)
9t G
(5) (()) 1|²
=
gt
(0)
+ 2² E
G 0L 1|
+ +2
E
gi E
(1)
Eg
(5)
[BG
-.9,
=E 06 Dt
(0) (
+ + 2 E
_ G 2
20,² 2 + 2 (20,- 2 + (20,_2 1² (...)))
= 2
1 2( 2) u
(8)
==0
= E c
E ((00
And the denominator of the variance-norm ratio is:
G = Eg C 2
2p
EG n² B
| |
x22 2 Egg ( (Eg (1)
1
+
+ 2²
(M__1 + 2p Eg-
+p² 2 E G/
Σ # 2(t-u)
Σ 1
E E
Eg
BBG EG
Thus, assuming honest gradients E.G!!) do not become null:
Ω2 Eteo (0t- o) o,, 2
(w)
A
( (*
2 + sw)
where the expected "straightness" of the gradient trajectory at step u is defined by:
8 2
E.G Eg,
P=0
Su quantifics what intuitively the curvature of the gradient trajectory. Straight trajectories can make s, grow up to (1 (1-14)-1 -1 1 times the expected squared-norm of the honest gradients, while highly "curved" trajectooris (e.g. close to local minimum) can make 8a negative.
13

---

Published as a conference paper at ICLR 2021
This observation stresses that this formulation of momentum sometimes be harmful for the purpose of Byzantine resilience. We measured 8u for every step u> 0 in our experiments, and we always observed that this quantity is positive and increases for short window of (dozen) steps (depending on 04), and then oscillates between positive and negative values. While the empirical impact (decreased or cancelled loss in accuracy) concrete, we believe there is room for further improvements, as discussed in Section 5
The purpose of using ummentum at the workers is to reduce the variance-norm ratio (w)
compared to ri Since 90 = G( we verily that r(a)) To Then Vi > 0, assuming P > 0 and 0, 0, we have:
(w) S
11 Q
o,
2 5
X + St + 42 A,
X2
μ Q 2²,² $
(st + nt A o,
(m))
e 8 2 A
(9)
The condition for decreasing ((00) can be obtained similarly, assuming 94-1 > 0 and o, >
r S < +
To study the impact of a lower learning rate a on St, we will assume that the real gradient VQ is L-Lipschitz. Namely:
1-
(t, E u <L EEG, - EGGl s 12 110 - 0.11 1
Σ
av G
v=
Then, (t, u) E N2, u < 1, we can rewrite:
| G. E EG,
|E,,11 E L. 2
-2 EE 9. EG
And finally, we can lower-bound st as:
|EG EG,1?
(>, 2 + 2)
p Eg, E
Σ n
Go
1)
[-1
+
Σ
X X 12
Σ ar Go
(10)
x=
1-1
> 1 11
Σ
t-u
x
12
Σ a G
1 4
==D
When the real gradient VQ is (locally) Lipschitz continuous, reducing the learning rate or can suffice ensure 5, satisfies the conditions laid above for decreasing the variance-none
ratio rt (("), the purpose of momentum at the workers. Importantly this last lower bound, namely Equation 10 sets how the practitioner should choose two hyperparameters, μ and ag, Basically, as long as it does not harm the training without adversary, i should be set. high and a low possible.
for the purpose Byzantine-resilien
14

---

Published as a conference paper at ICLR 2021
C REPRODUCING THE RESULTS
Our contributed code available at ZIP archive from OpenReview https://opaaneeeee...ae//ooorotd
Software dependencies. Python 3.7.3 has been used, over several GNU/Limux distribu-
tions (Debian 10, Ubuntu 18). Besides the standard libraries associated with Python 3.7.3,
our scripts also depend on
Library numpy
Version
Library
Version
Library
Version
1.19.1
requests 2.21.0
pytz
2020.1
torch
1.6.0
urllib3 1.24.1
datcutil
2.8.1
torchvision
0.7.0
chardet 3.0.4
pyparsing
2.2.0
pandas
1.1.0
certifi
2018.08.24
cycler
0.10.0
matplotlib
3.0.2
idna 2.6
kiwisolver
1.0.1
PIL
7.2.0
six 1.15.0
cffi
1.13.2
Hardware dependencies. We list below the hardware components used:
Intel(Rt) CTr) 17-8700K CPU @ 3.70GHz
2 Nvidia GeForce GTX 1080 Ti
64 GB of RAM
C.1
COMMAND
Our results are reproducible one command. In the root directory of the ZIP file:
$ python3 reproduce.py
On our hardware, reproducing the results takes bit less than week. Please be this script will require non-negligible disk space: 2.1 GB of run data, and 132 MB of graphs.
Depending the hardware, instructing the script to launch several per available GPU may reduce the total runtime. For instance, to push up to 4 concurrent runs per GPU:
$ python3 reproduce. suueerchaaree
D LARGER MODELS
To assess our method on even larger models, we consider the "wide-resnet" model family implemented by Kim 2020). We use the same model-specific parameters as the ones proposed by the original author, namely: (depth). 10 (widen factor), 0.3 (dropout rate), and 10 output classes (for CIFAR-10). This model contains 36 489 290 trainable parameters, almost 28 times more than the 310922 trainable parameters the convolutional model.
We employ the same hyperparameters model (Section 4.1), except for the number of workers (set to n = 11), the mini- batch size per worker (set to 20), and the learning rate schedule (0.02 for t 8000, 0.004 for 8000 St < 16000, 0.0008 for i. 2 16000).
in our main experiments with the convolutional
The training procedure lasts for 20000 steps and only employs Nesterov momentum, proposed by the original author (Kim 2020). We report on the maximum observed top-1 cross-accuracy in Figure and evolution of the top-1 cross-accuracy in figures 7 and g
These results are also reproducible one command. In the root directory of the ZIP file:
$ python3 reproduce-appendix. py
On our hardware, reproducing these results takes several weeks. Some of the 6 presented GARs could not be employed, they repeatedly trigger out-of-memory errors GPUs.
Thhis list was automatically generated (see get loaded dependencies in tools/misc.pii
15

---

Published as a conference paper at ICLR 2021
1.0
0.8
0.6
Max. top-1
0.4
0.2
0.0
Our formulation formulation
Standard
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation formulation
Our
formulation
a]
[b]
[c]
[d]
Figure 6: CIFAR-10 10 and wide-nesnet model. [a] Roughly an half (f = 4) Byzantine workers implementing (Baruch et al. 2019).
[b] Roughly a quarter (f= = 2) Byzantine workers
implementing (Baucch et al." 2019
[e] Roughly an half Byzantine workers implementing
Xie et al. 2019a [] Roughly a quarter Byzantine workers implementing (Xie et al, 2019a).
Momentum at the server
Momentum at the workers
Tog. cros aceuracy
Altack
attack
Krom
Krum
al.
0.6
Median
0.6
Median
0.1
041
0.0
2500
5000
7500
10000
12500
15000
17500
20000
2500
5000
7500
10000
12500
15000 17500 20000
Shop
Step number
TTpp-1 crosi actursy
No attack
Krum
Tapp1 cooooacttte
0.6
Modiisn
0U6
0.4-
0.4
ct
Krum Median
0.0
2500
5000
7500
10000
12500
15000
17500
20000
2500
5000
7500
10000
12500
15000
17500
20000
Step
Step number
Figure 7: CIFAR-10 10 and wese-resnet model, roughly an half of Byzantine workers.
Momentum at the server
Momentum at the workers
Top cross acrurncy
0.8
01.
0.6
No altack
0.6
Median
No atlack
Baruch
Bulyan
Krum
0.2
0.2
Bulyan
11.0
0.0
7500
10000
15000
17600
20000
2500
10000
12500
15000 17500 20000
Step namber
Step number
Top-1 crcos uceuncy
0.8
0.8
atlack
Thy-1 cmna-tretrrey
Krum
0.6
0.6
Median
Bulyan
No Attack Ketma
0.2
Bulvan
0.0
0.0
7500
15000
17500
Step number
Step number
Figure 8: CIFAR-10 and wide-resmel model, roughly quarter of Byzantine workers.
16

---

Published as a conference paper at ICLR 2021
E MORE EXPERIMENTAL RESULTS
This section reports on the entirety of the main experiments, completing Section 4 the
main paper. For every pair model-dataset, the following parameters vary:
Which attack: Baruch et al. 2019) or Xie et al. (2019a]
Which defense: Krum, Median, Trimmed Mean, Phoeas, MeaMed, Bulyan
How many Byzantine workers (an half or a quarter)
Where momentum is computed (server workers)
Which flavor of momentum is used (classical or Nesteroo)
Which learning rate is used (larger or smaller)
Every possible combination is tested leading to a total of 736 different experiment setups. Each setup is tested 5 times, each run with a fixed seed from 5, enabling verbatim reproduction of our results 10 In this specific section, we report on:
the maximum observed top-1 cross-aceuracy with each of the studied GARs, the evolution of the average and standard deviation of the top-1 cross-aceuracy for every tested setup.
The results regarding the maximum observed top-1 cross-accuracy are layed out by "block" of experiment setups, amnng which only the flavor of momentum and the attack used are different. Namely: [a] classical momentun under allack from Baruch et. al. (2019) [b] nesterov momentum under attack from Baruch et al. (2019), [c] classical momentum under attack from Xie et al. (2019a). [c] nesterov momentum under attack from Xie et al. (2019a).
The results regarding the evolution of the top-1 cross-accuracy are layed out by "blocks" of 4 experiment setups presenting the same model, dataset, learning rate schedule, nunber of Byzantine workers and attack. These results are presented from Figure 25 to Figure 56
9 AAlong with baselines using averaging without attack. 10 Desppte our best efforts, there may still exist minor sources of non-determinism, like race- conditions in the evaluation of certain functions (e.g., parallel additions) in GPU. Nevertheless believe these should affect the results in any significant way.
17

---

Published as a conference paper at ICLR 2021
1.0
0.8
0.6
Max. top-1
0.4
0.2
+0+
0.0
Standord
Our formulation
Standord formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
formulation
[a]
[b)
[d]
Figure CIFAR-10 and convolutional model, with n 25, f 11 and ar = 0.01 if < 1500
else 02
0.001.
1.0
0.8
Max. top-1 croos--te
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
formulation
a
[b]
[d]
Figure 10: CIFAR-10 and convolutional model, with 25, 11 and a2 0.001.
1.0
0.8
0.6
Max. top-1
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard
Our
formulation
formulation
formulation
[a]
[
[d]
Figure CIFAR-10 and convolutional model, with 25, f and aq 0.01 if < 1500
elsc 0₂ = 0.001.
1.0
0.8
Max. top-1 cross-acmi
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our
formulation
formulation [d]
[a]
[b]
Figure 12: CIFAR-10 and convolutional model, with 25, f f= and 04 0.001.
18

---

Published as a conference paper at ICLR 2021
1.0
0.8
0.6
Max. top-1
0.4
0.2
0.0
Standord
Our formulation aa]
Standord formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our
formulation
formulation
[b)
[d]
Figure 13: CIFAR-100 and connolutional model, with n 25, f and az 0.01 t < 1500 else oz = 0.001.
1.0
0.8
Max. croos-
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation [d]
formulation
a
[b]
Figure 14: CIFAR- 100 and convolutional model, with 25, ʃ 11 and or 0.001.
1.0
0.8
0.6
Max. top-1
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our Standard formulation
Our
formulation
formulation
formulation
[a]
b
[d]
Figure 15: CIFAR-100 and convolutional model, with n 25, f and az 0.01 t < 1500 else a₂ = 0.001.
1.0
Max. cross-acming
0.8
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our
formulation
formulation
a
[b]
[c]
[d]
Figure 16: CIFAR-100 and convolutional model, with
25, f = 5 and a, 0.001.
19

---

Published as a conference paper at ICLR 2021
1.0
Max. top- crose-act coss-eccurayy
0.8
0.6
0.4
0.2
0.0
Our formulation formulation
Standard
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation formulation
Our
aa]
[b]
[d]
Figure 17: Fashion MNIST and fully connected model, with 51, f 24 and or 0.5.
1.0
Max. aroe-accuracy
0.8
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our Standard formulation formulation
Our
formulation
formulation
la]
[b]
[d]
Figure 18: Fashion MNIST and fully connected model, with 51, 24 and ar 0.02.
1.0
Max. top-1 cross- mnes-arcuracy
0.8
0.6
0.4
0.2
0.0
Our formulation formulation
Standard
Standard formulation
Our formulation
Standard formulation
Our Standard formulation formulation [d]
Our
formulation
a]
[b]
Figure 19: Fashion MNIST and fully connected model, with 51, f 12 and o 0.5.
1.0
Max. top-1 accurarcrrr
0.8
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation formulation
Our
formulation
[
[b]
[c]
[d]
Figure 20: Fashion MNIST and fully connected model, with 51, - 12 and a: 0.02.
20

---

Published as a conference paper at ICLR 2021
1.0
Max. top-1 cross-aee coss-accurayy
0.8
0.6
0.4
0.2
0.0
Standard
Our
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation formulation
Our
formulation formulation
[a]
[b]
[d]
Figure 21: MNIST and fully connected model, with 51, f 24 and dt 0.5.
1.0
Max. top-1 mree-accuracy
0.8
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation formulation
Our
formulation
[a]
[b]
[d]
Figure 22: MNIST and fully connected model, with n 51, 24 and a 0.02.
1.0
Max. cross- mnes-arcuracy
0.8
0.6
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our Standard formulation formulation [d]
Our
formulation
formulation
a
[b]
Figure 23: MNIST and fully connected model, with 51, f 12 and ar 0.5.
1.0
0.8
0.6
Max. top-1
0.4
0.2
0.0
Standard
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
Standard formulation
Our formulation
formulation
a]
[b]
Figure 24: MNIST and fully connected model, with n 51, 12 and a 0.02.
21

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentun
0..
0.8
10p-1 cross-uucctun
No attack
The-1 mree-rrtteee
No attack
0.6
Krum
0.6
Krum
Trmean
Trmean
Phoras
Phocas
0.2
Menmor
0.0
0.0
Step number
Step number
Nesterov momentum
0.8
10p-1 c1000 Proos-accuuayy
Krum
The-1 ervesseemies
0.6
Median
0.6
allack
Trmesc
Krum
Phanaa
Modiia
Meamed
Tymcan
0.3
Meamed
0.0
0.0
2500
Step number
Step number
Figure 25: CIFAR-10 dataset and convolutional model, with 25, f = 11 and ar 0.01 if t < 1500 else a₂ = 0.001, under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
0.8
attack
0.8
10p-1 cro.e---cooo croi--ucuuu
Krom
The-1 erse--reeee
0.6
Median
0.6
attack
Trmmen
Krum
Phocss
Median
Meamed
Trmean
0.2
Menmed
0.0
0.0
1500
1000
2500
3000
Step number
Step number
Nesterov momentum
10p-1 c1000 -0e--
Krum
attack
Thy-1 cre-sirrtzae
0.8
Krum
0.6
Median
0U6
Meriion
Temman
Trmmssn
Phocas
Phocas
Meamed
Meamed
0.2
0.0
0.0
1500
2000
2500
500
2000
2500
3000
Step number
Step number
Figure 26: 10 dataset and concolutional model, with under attack from Baruch et al. (2019).
25, f 11 and a2 0.001,
22

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
Classical momentun
0..
No allck
0.8
100-1 cross--uccuun
Krom
Thes erose-rettae
No attack
0.6
Median
0.6
Krum
Trmean
Phora
Trmmon
Meamed
Phoess
0.2
Bulyan
0.2
Meamed
Bulyan
0.0
0.0
1000
Step number
Step number
Nesterov momentum
0.8
10g-1 c1000 Pros--acuusry
No attack
Thge1 enve-sernns
No attack
0.6
Krum
0.6
Krum
Median
Median
Timssn
Trmone
Phocas
Phocan
0.3
Meamed
Bulyan
Bulyan
0.0
0.0
2500
Step number
Step number
Figure 27: CIFAR-10 dataset and convolutional model, with 25, f 5 and 02 0.01 if t < 1500 else a₁ = 0.001, under attack from Baruch et al. (0019).
Momentum at the server
Momentum at the workers
Classical momentum
0.8
attack
0.8
10p-1 cro00 (uvv--uccuaaey
Kram
The-1 erseearrteee
Krum
0.6
Median
0.6
Median
Trmeac
Trmeen
Phanaa
Phoeus
Meamed
Mcomed
Bolyan
0.2
Buiyan
0.0
0.0
1500
2500
3000
Step number
Step number
Nesterov momentum
10p-1 c1000 are-a
attack
0.8
Krum
Thy-1 covessortres
Krum
0.6
Median
006
Modian
Trmmsc
Trmsnes
Phocas
Phocan
Mosmed
Meamed
Bulyan
0.2
Bubyan
0.0
0.0
1500
2500
500
1500
2000
2500
3000
Step number
Step number
Figure 28: CIFAR-10 dataset and convolutional model, with under attack from Baruch et al. (2019).
25, f 5 and 0.001,
23

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentun
0.8
No allack
0.5
100-1 cross-uccuue
Krom
Thes1 mwnde-rtttee
No attack
0.6
Median
0.6
Krum
Trmeon
Phonse
Trmean
Meamed
Phocas
0.2
0.2
Menmor
0.0
0.0
Step number
Step number
Nesterov momentum
10g-1 cross cromsuccusec
attack
0.8
Krum
No attack
2.6
Median
0.6
Krom
Trmson
Phonas
Tymean
Meamed
Phoroe
Thge1
0.3
Mosmed
0.0
0.0
Step number
Step number
Figure 29: CIFAR-10 dataset and convolutional model, with 25, f = 11 and ar 0.01 if t < 1500 else a₁ = 0.001, under attack from Xie et al. (2019a)
Momentum at the server
Momentum at the workers
Classical momentum
0.8
attack
0L8
Krum
The-1 erse-arrt0e
Krum
10p-1 cio.--uccuuu
0.6
Median
0.5
Median
Trmmen
Trmmen
Phocss
Phoons
Meamed
Meamed
0.2
0.0
0.0
1500
500
2500
3000
Step number
Step number
Nesterov momentum
1op-1 cooos cros-arcueg
Krum
attack
Thy-1 cne-ssrrirae
0.8
Krum
8.6
Median
0U6
Meriion
Trmmon
Trmmssn
Phocas
Phocas
Meamed
Meamed
0.2
0.0
0.0
1500
2500
500
Step number
Step number
Figure 30: CIFAR-10 dataset and concolutional model, with under attack from Xie et al. (2019a)
25, f 11 and a2 0.001,
24

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentun
0.8
0.5
100-1 cross-uuchunn
No attuck
The-1 eroee-retto
No attack
0.6
Krum
0.8
Krum
Trmean
Trmmon
Phana
Phoess
0.2
Moamed
0.2
Mcamed
Bulyan
Bulyan
0.0
0.0
2500
Step number
Step number
Nesterov momentum
10p-1 c1000 woos--acuusccy
0.8
No attack
Thge1 erveesaennie
0.8
No attack
6.6
Krum
0.6
Krum
Median
Median
Timmsn
Trmone
Phocas
Phocan
Meamed
0.3
Meamed
Bulyan
Bulyan
0.0
2500
0.0
2500
Step number
Step number
Figure 31: CIFAR-10 dataset and convolutional model, with t < 1500 else a₁ = 0.001, under attack from Xie et al. (2019a)).
25, f 5 and 02 0.01 if
Momentum at the server
Momentum at the workers
Classical momentum
0.8
0.8
10p-1 c1000 Sivve-uccuuaey
Krum
The-1 erse-aertaee
Krmm
0.6
Median
0.6
Median
Trmeaa
Trmeen
Phana
Phoeus
Meamed
Meamed
Bolyan
0.2
Buiyan
0.0
0.0
1500
2500
3000
Step number
Step number
Nesterov momentum
10p-1 c1000 aoe--
attack
0.8
Krum
Thy-1 cov-sientres
Krum
0.6
Madian
006
Madian
Trmmwr
Trmsnes
Phocas
Phocan
Moamed
Mesmed
Bulyan
0.2
Bubyan
0.0
0.0
1500
2500
500
1500
2000
2500
3000
Step number
Step number
Figure 32: CIFAR-10 10 dataset and convolutional model, with under attack from Xie et al. (2019a).
25, f 5 and 0.001,
25

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentun
0.5
No attack
0.8
No allak
1agh 01 croe-sectnee
Krum
Kram
0.6
Median
0.0
Median
Trmcon
Trmoan
Phooss
Mearaed
Meamed
0.2
0.0
0.0
Strp number
Step number
Nesterov momentum
0.8
ottack
0.8
1app-1 c1000- cras--xxunayy
Krum
Topa croe-nominey
Krun
0.6
Median
0,6
Median
Trmeon
Trmmsn
Phenzu
Pleesn
Meunee
Meinal
0.2
0.2
0.0
0.0
Somp number
Step number
Figure 33: CIFAR- 100 dataset and convolutional model, with 25, f = 11 and a2 0.01 t < 1500 else a, = 0.001, under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
0.5
No attack
0.8
1ap-11 c1 croes-ocnruayy
Krum
Krum
0.
Median
0.0
Median
Trmeon
Temoom
Ploxtas
Phaxee
Maamee
Meamed
0.2
0.0
0.0
1000
1000
3000
Stmp momber
Step number
Nesterov momentum
11pp-1 1100 (ras-uxcurcy
0.8
Krum
Kruz
0.6
Medisn
0JR
Median
Trmmon
Trommnn
Phoeas
Phoosa
Mearzed
Meamed
0.2
0.0
0.0
1500
300
1500
Stmp momber
Step miher
Figure 34: CIFAR-100 dataset and convolutional model, with 25, f 11 and ag 0.001, under attack from Baruch et al. (2019).
26

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
Classical momentun
0.5
No attack
0.8
No allak
1agh 01 crdee-ectnee
Krum
Kram
0.6
Median
0.0
Median
Trmcon
Trmoan
Pheess
Mesrzed
Meanel
Bolyan
0.2
Dulyan
0.0
0.0
Strp number
Step number
Nesterov momentum
0.8
ottack
0.8
1app-1 c1000- cras--xxunaay
Krum
Topel croe-noninay
Krun
0.-
Median
0,6
Median
Trmeon
Trmmsn
Phonzus
Pleesa
Mestaed
Mexnal
Bulyan
0.2
Dulyan
0.0
0.0
500
Somp number
Step number
Figure 35: CIFAR-100 dataset and convolutional model, with 25, and ar 0.01 if t < 1500 else a₁ = 0.001, under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
0.5
No attack
0.8
1ap-1 c1 droe--rcnruay
Krum
Krum
0.
Median
0.0
Median
Trmeon
Trmoom
Ploxtus
Phacas
Miameed
Meamed
Dolyan
0.2
Dulyan
0.0
0.0
1000
1500
2000
1000
3000
Stop mimber
Step number
Nesterov momentum
11pp-1 1100 (ras-uxcuray
0.8
Krum
Krum
0.6
Medisn
DJR
Median
Trmmon
Trommnn
Phoeas
Phoosa
Mearzed
Meamed
Bolyan
0.2
Dulyan
0.0
0.0
1000
1500
300
1500
Stmp momber
Step
Figure 36: CIFAR-100 dataset and convolutional model, with 25, f 5 and ag 0.001, under attack from Baruch et al. (2019).
27

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
Classical momentun
0.5
No attack
0.8
No allak
1agh 01 crde-sectnee
Krum
Kram
0.6
Median
0.0
Median
Trmcon
Trmoan
Phooss
Mearaed
Meamel
0.2
0.0
0.0
Strp number
Step number
Nesterov momentum
0.8
ottack
0.8
1app-1 c1000- cras--xxunayy
Krum
Topa croe-nomnney
Krun
0.6
Median
0,6
Median
Trmeon
Trmmsn
Phenzu
Pleesa
Meusee
Meanal
0.2
0.2
0.0
0.0
Somp number
Step n.mber
Figure 37: CIFAR- 100 dataset and convolutional model, with 25, f = 11 and a2 0.01 t < 1500 else a, = 0.001, under attack from Xie et al. (2019a).
Momentum at the server
Momentum at the workers
Classical momentum
0.5
No attack
0.8
1ap-11 c1 droes-ocnruayy
Krum
Krum
0.
Median
0.0
Median
Trmeon
Temoom
Ploxtas
Phaxes
Maamee
Meamed
0.2
0.0
0.0
1000
1000
3000
Stmp momber
Step number
Nesterov momentum
11pp-1 1100 (ras-uxcurcc
0.8
Krum
Kruz
0.6
Medisn
0JR
Median
Trmmon
Trommnn
Phoeas
Phoosa
Mearzed
Meamed
0.2
0.0
0.0
1000
1500
Stmp momber
Step miher
Figure 38: CIFAR-100 dataset and convolational model, with 25, f 11 and ag 0.001, under attack from Xie et al. (2019a).
28

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
Classical momentun
0.5
No attack
0.8
No allak
Krum
Top- cn-e-erttinr
Knam
0.6
Median
0.0
Median
Trmcon
Trmoan
Pheoss
Mistzeed
Meanel
Bolyan
0.2
Dulyan
0.0
0.0
Strp number
Step number
Nesterov momentum
0.8
0.8
1app-1 c1000- cras--xcunayy
Krum
Topel croe-noiitay
Krun
0.6
Median
0,6
Median
Trmeon
Trmmsn
Phenzus
Pleess
Mestaed
Mexnaa
0.2
Dulyan
0.2
Dulyan
0.0
0.0
500
Somp number
Step number
Figure 39: CIFAR-100 dataset and convolutional model, with 25, and ar 0.01 if t < 1500 else a, = 0.001, under attack from Xie et al. (2019a).
Momentum at the server
Momentum at the workers
Classical momentum
0.5
No attack
0.8
1ap-1 c1 droe--rcnnuay
Krum
Krum
0.
Median
0.0
Median
Trmeon
Trmoom
Ploxtus
Phacas
Maameed
Meamed
Dolyan
0.2
Dulyan
0.0
0.0
1000
1000
3000
Stop momber
Step number
Nesterov momentum
11pp-1 1100 (ras-uxcuray
Krum
Thpp- cronspniiac
0.8
Krum
0.6
Medisn
DJR
Median
Trmmon
Trommnn
Phoeas
Phoosa
Mearzed
Meamed
Bolyan
0.2
Dulyan
0.0
0.0
1500
500
1500
Stmp momber
Step miher
Figure 40: CIFAR- 100 dataset and convolutional model, with 25, f 5 and ag 0.001, under attack from Xie et al. (2019a).
29

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentum
1.0
100- c1000 cros0- uccuracy
Thee mos-urcnaa
No attack
No atrack
0.6
Krum
Median
Medion
Trussun
0.4
Thmmsn
Phocas
Meamed
Meamed
0.0
0.0
250
Step number
Step number
Nesterov momentum
1.0
10p-1 c1000 cross-accu accuary
Thyel mrod-armraar
0.8
No atlack
No altack
0.6
Krum
0.6
Krum
Modian
Median
Trmsan
044
Trmson
Phocas
Meamed
Mesmed
0.0
0.0
Step number
Step number
Figure 41: MNIST dataset and fully connected model, with n 51, f = 24 and 02 0.5,
under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
1.0
10p-1 c1000 cross-accuu accuracy
Tope1 eroee-rzmme mma0--22m/arr
No attack
No attack
0.6
Krum
0.6
Median
Mediom
Trmean
0.4
Timean
022
Phocas
Meamod
Menmed
0.0
0.0
Step number
Step
Nesterov momentum
1.0
Top-1 c1000 cross-aroo accurory
0.8
0.8
No attack
0.6
Krann
0.6
Kramn
Median
Median
Trmeon
0.4
Trmzon
Tops
Phocas
Moameei
Mismedi
0.0
0.0
150
Step number
Step number
Figure 42: MNIST dataset and fully connected model, with n 51, f 24 and 0₁ 0.02,
under attack from Baruch et al. 20199)
30

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentum
1.0
100- c1000 uccuracy
No attack
Kram
mose-
Krom:
No attack
0.6
Trmean
0U
Phone
0.4
Trmee
Phonas
Dulyan
Meamed
Bulyan
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
10p-1 cross-un coo--accusry
Thpel maraarrrrrrrr
No attack
0.8
No attack
Krum
Krum
0.6
Median
0.6
Median
Timmun
Trman
Phocas
044
Plaoaa
Meamed
Bulyan
Balyan
0.0
50
1001
150
0.0
Step number
Step number
Figure 43: MNIST dataset and fully connected model, with n 51, f 12 and 02 0.5, under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
1.0
10p-1 c1000 cross-accum accurayy
No attack
Tope1 mmw--emmae
No attack
Krum
Krum
0.6
Median
0.6
Medion
Trmaun
Thmaan
Phocas
044
Phocas
Meamed
Meamed
Bilyan
Bulyan
0.0
0.0
250
Step number
Step number
Nesterov momentum
1.0
T0p-1 c1000 cross-aroo accurory
0.8
No attack
0.8
No attack
Krom
0.6
Median
0.6
Median
Trmean
Trmcan
Phocas
0.4
Phocas
Meamed
Top-1
Boiyan
Balyan
0.0
0.0
150
Step number
Step number
Figure 44: MNIST dataset and fully connected model, with n 51, f 12 and 0₁ 0.02,
under attack from Baruch et al. 20199)
31

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentum tum
1.0
100-3 c1000 cro00- uccuracy
No atlack
Kram
No attack
0.6
Trizan
Krum:
Phoce
0.4
Median
Trneus
Meamed
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
10p-1 cr000 cross-acco accuary
No attack
Thye- eroo-armiin corrary
Krum
0U8
Medaan
sttack
0.6
Trmmen
0.6
Krum
Meamed
Phoese
04
Timean
Meriion
Meamed
0.0
0.0
50
100
Step number
Step number
Figure 45: MNIST dataset and fully connected model, with n 51, f = 24 and 0g 0.5, under attack from Xie et al. (019a)).
Momentum at the server
Momentum at the workers
Classical momentum
1.0
10p-1 cross-un accuracy
No Attark
Tope1 com
Krum
No attack
0.6
Timeon
0.6
Phocss
041
Timean
Mediom
012
Phocas
Menmed
0.0
0.0
250
300
Step number
Step
Nesterov momentum
1.0
Top-1 c1000 arcurory
No attack
0.8
Krom
0.8
Median
No attack
0.6
Trmman
0.6
Kramn
Phoeas
Median
Trmzon
Tope
Phocas
Mismed!
0.0
0.0
50
Step number
Step number
Figure 46: MNIST dataset and fully connected model, with n 51, f 24 and 0₁ 0.02, under attack from Xie et al. (0019a).
32

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentun
10p- c1000 cross- uccuracy
1.0
No altack
No attack
Toee mose-rcmaa
Krum
Krom
0.6
Median
Trmean
Phooss
Trmean
0.4
Phoess
Moamed
Dulyan
Bulyan
0.0
0.0
250
Step number
Step number
Nesterov momentum
1.0
10p-1 c1000 cross-acco arcuaay
Thyel enoo-armee manrary
No attack
No attack
0.8
Krum
Krum
Median
0.6
Median
0.6
Triee
Phocas
Trmmnn
04
Phana
Meamed
Balyan
Bulyan
0.0
0.0
Step number
Step number
Figure 47: MNIST dataset and fully connected model, with n 51, f 12 and 02 0.5,
under attack from Xie et al. (019a)).
Momentum the server
Momentum at the workers
Classical momentum
1.0
10p-1 c1000 cross-accom accuracy
No attack
Tope1 mmw--1mmee
No attack
Krum
Krum
0.6
Median
0.6
Medion
Trmaun
Thmaan
Phocas
041
Phocas
Meamed
022
Meamed
Bilyan
Bulyan
0.0
0.0
250
Step number
Step number
Nesterov momentum
1.0
Top-1 c1000 cross-aroo accurory
0.8
No attack
Tops crve-emmma
0.8
No attack
Krom
0.6
Median
0.6
Median
Trmean
Trmcan
Phocas
0.4
Phocas
Meamed
Boiyan
Balyan
0.0
0.0
150
Step number
Step number
Figure 48: MNIST dataset and fully connected model, with n 51, f 12 and 0₁ 0.02,
under attack from Xie et al. (0019a).
33

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
1.0
Classical momentum
100- c1000 cro00- uccuracy
Tope mode-rrmna
No attack
No attack
0.6
Krum
0.6
Median
Medion
Trussu
0.4
Thmmsn
Phocas
Meamed
Meamed
0.0
0.0
250
Step number
Step number
Nesterov momentum
1.0
10p-1 c1000 c1oss-accum accuaay
Thyel erso-arrneee morrrry
0.8
No attack
No altack
0.6
Krum
0.6
Krum
Modian
Median
Trmsan
04
Trmson
Phocas
Meamed
Mesmed
0.0
0.0
Step number
Step number
Figure 49: Fashion MNIST dataset and fully connected model, with 51, f 24 and
a, = 0.5, under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
1.0
10p-1 c1000 cross-accuu accuray
Tope1 mm0e-22m0a
No attack
attack
0.6
Krum
0.6
Median
Mediom
Trmean
0.4
Timean
Phocas
Meamod
Menmed
0.0
0.0
Step number
Step
Nesterov momentum
1.0
10p-1 c1000 cross-atoo accurory
0.8
Top-1 cove-emmras
0.8
No altack
0.6
Krain
0.6
Kramn
Median
Median
Trmeon
0.4
Trmzon
Phocas
Moameei
Mismedi
0.0
0.0
50
Step number
Step number
Figure 50: Fashion MNIST dataset and fully connected model, with 51, f 24 and a, = 0.02, under attack from Baruch et al. (2019).
34

---

Published as a conference paper at ICLR 2021
Momentum the server
Momentum at the workers
Classical momentun
1.0
100- c1000 uccuracy
No attack
No atrack
Kram
Topa mose-
Krum
Median
0.6
Trmean
Trmean
Phone
0.4
Phoess
Dulyan
Dulyon
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
10p-1 cro0s-u accuaay
No attack
No attack
Kram
Thyel emoo-armee
0.8
Krum
Medaa
Median
0.6
Trmeen
0.6
Trmmn
Phonaa
04
Phana
Meamed
Bulyan
Balyan
0.0
0.0
Step number
Step number
Figure 51: Fashion MNIST dataset and fully connected model, with 51, f 12 and
a, = 0.5, under attack from Baruch et al. (2019).
Momentum at the server
Momentum at the workers
Classical momentum
1.0
10p-1 c1000 cross-accuu accuray
No attack
No attack
Kram
Tope1 mmwe-emmar
Krum
Median
Median
0.6
Trmson
0.6
Trmeon
Phoee
044
Phocus
Meamed
Meamed
Bulyan
022
Bulyan
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
T0p-1 c1000 cross- accurory
No attack
No attack
Kram
0.8
Krom
Melian
Median
0.6
Trmean
0.6
Trmenn
Phocas
0.4
Phocas
Meamed
Mesmed
Top-1
Bulyan
Bulyan
0.0
0.0
50
Step number
Step number
Figure 52: Fashion MNIST dataset and fully connected model, with 51, f 12 and a, = 0.02, under attack from Baruch et al. (2019).
35

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
Classical momentun
1.0
c1000 uccuracy
No atlack
Kram
Toee mooe-urcmm
No atrack
0.6
Trmzan
008
Phone
0.4
Thmmsn
Medion
Phocas
Meamed
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
10p-1 c10000 c1oos-accom accuaay
No attack
Kram
Thyel enoo-armeee
0.8
Medaan
No attack
0.6
Trmeen
0.6
Krum
Meamed
Phonss
04
Median
Trmson
Plocas
Mesmed
0.0
0.0
Step number
Step number
Figure 53: Fashion MNIST dataset and fully connected model, with 51, f 24 and
a, = 0.5, under attack from Xie et al. (201aa)
Momentum at the server
Momentum at the workers
1.0
Classical momentum
10p-1 cro6s- accuracy
No Attark
Krum
Medaan
No attack
0.6
Timeon
0.6
Phucss
041
Timean
Mediom
Top-1
012
Phocas
Meamed
0.0
0.0
100
250
300
Step number
Step
Nesterov momentum
1.0
Top-1 cross--in arcurory
No attack
0.8
Krum
0.8
Median
attack
0.6
Trmma
0.6
Kramn
Phoeas
Median
Meanedd
Trmzon
Tope
Phocas
Mismer
0.0
50
0.0
50
Step number
Step number
Figure 54: Fashion MNIST dataset and fully connected model, with 51, f 24 and ag = 0.02, under attack from Xie et al. (2019a).
36

---

Published as a conference paper at ICLR 2021
Momentum the
Momentum at the workers
Classical momentum
1.0
100- c1000 cross------- uccuracy
No attack
No atrack
Kram
Thea mode-
Krum
0.6
Trmzan
Trmean
Phoce
0.4
Phoess
Dulyan
Dulyon
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
10p-1 cro0s-u accuaaycuyyy
No attack
Thyel enoo-arneee momrary
No attack
Kram
0.8
Krum
Medaan
Median
0.6
Trmeen
0.6
Trmen
Phonaa
04
Phana
Meamed
Bulyan
Balyan
0.0
0.0
Step number
Step number
Figure 55: Fashion MNIST dataset and fully connected model, with 51, f 12 and
a, = 0.5, under attack from Xie et al. (2019a)
Momentum at the server
Momentum at the workers
Classical momentum
1.0
10p-1 c1000 cross-accum accuracy
No attack
No attack
Kram
Tope1 mmwe-emmar
Krum
Median
Median
0.6
Trmson
0.6
Trmeon
Phoee
044
Phocus
Meamed
Meamed
Bulyan
Bulyan
0.0
0.0
Step number
Step number
Nesterov momentum
1.0
10p-1 c1000 cross-aroo accurory
No attack
No attack
Krom
0.8
Krom
Median
Median
0.6
Trmean
0.6
Trmenn
Phocas
0.4
Phocas
Meamed
Mesmed
Topp
Bulyan
Bulyan
0.0
0.0
50
150
Step number
Step number
Figure 56: Fashion MNIST dataset and fully connected model, with 51, f 12 and a, = 0.02, under attack from Xie et al. (2019a).
37


Reviews:
[{"review_id": "pg5JgNwCKju", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper's method is quite simple and it argues that the latest distributed stochastic gradient descent (SGD) state-of-the- based on the Byzantine model can be tackled using momentum-based versions of (SGD). There is a slight issue with the Nesterov variant that the authors are using. I don't know they have used the formulation to calculate gradients at $\\theta_t-\\alpha v_t$ instead of calculating gradients at $\\theta_t-\\mu v_t$, where $\\mu$ is called momentum. Other than that they have used the aggregating functions which are previously studied and known to $(\\alpha, f)$-resilient. There is not much contribution by the authors in this area. Although they studied these aggregation rules under recently presented attacks. \nIn supplementary material, authors show that computing momentum-based gradient at workers under some assumptions they can keep the variance-norm ratio low but they already have discussed that this might be an issue as standard deviation can be negative. More insight and analysis are required and I am not sure how it may behave other attacks that are not studied in this paper. The results are quite detailed but due to the huge number of combinations, it is difficult to summarize all settings, and the numbers already stated are not in favor. When half of the machines are Byzantine 20\\% accuracy is recovered in 49.25\\% cases which is not a favorable number. The number of stats for results are missing like average recovered accuracy, median and basic analysis charts could be more useful than adding charts of different combinations of possible experiments.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "VwJCrWb7zwb", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I am having trouble identifying the contribution of this paper. A slight distributed tweak on the completely standard approach of running SGD with momentum is proposed as a defense to Byzantine attacks. A number of defenses augmented with this approach is studied experimentally against two recent attacks. There are no clear guarantees of the proposed mechanism that I could find as the paper seems to be focused exclusively on experimental results. \n\nThe experimental results by themselves, while they have a certain merit, seem of little lasting value -- there is only two (rather ad hoc) attacks considered, which I didn't find particularly natural or important otherwise. Overall, combined with the fact the Byzantine setting itself is already a stretch in terms of realism, this paper doesn't seem to have much lasting value. I would suggest identifying and studying broader classes of attacks/defenses of which presented ones are special cases and giving at least some guarantees in terms of what the proposed approach provides. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "LyZs96-L23-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe paper describes an approach to counteract Byzantine attacks for distributed stochastic gradient descent by using the momentum of the gradient computed at the workers, which relies only on memory of the previous momentum. This seems to thwart current attacks in the majority of scenarios tested. The theoretical analysis seems appropriate. The empirical results are accompanied by precise details and should facilitate reproducibility (given a week of computation time). \n\nStrengths:\nThe paper is well organized. The proposed approach addresses known attacks. The results are done in a rigorous and reproducible manner. Related work is highlighted.\n\nWeaknesses:\nThe text in the introduction is a bit overreaching. Perhaps, \"main driving force behind the successes of machine learning\" replaced by \"main optimization algorithm used throughout machine learning\". Also, is not clear that data that are not \"well-sanitized\" and the existence of \"software bugs\" could be considered colluding adversaries. These situations certainly do not constitute omniscient adversaries.  Their inclusion does not seem within the scenarios considered.  In this vein, I don't find much realism of the addressed attack scenarios. \n\nThe nature of the failure mechanism for cases when the defense is not successful could be made more clear or investigated more.\n\nThe related and future work section were helpful, but the text in that section are too terse, especially when new concepts are introduced. More text describing these concepts and relating them to the situations addressed by the paper would be helpful. \n\nConclusion:\nI think the paper is  well written contribution to the literature on Byzantine attacks for stochastic gradient descent.  I think it will be significant to researchers in the area. However, it is outside my expertise and I found interpreting the contribution difficult. \n\nOther suggestions:\nFigure 5 is difficult to understand without a contrast of what it would be without the proposed momentum at the workers.  \t\n\nSection 5 could be expanded. It is not clear why the \"suspicious-based\" fault tolerance is considered a more appropriate defense. Could the proposed momentum at worker approach make it easier to detect attacks (rather than defend)?\n\nThe detailed results of learning curves in the Appendix are easy to grasp, but the number of figures seems excessive versus summarizing the loss at a certain iteration or the number of iterations to a certain performance level.\n\nMinor:\nThe font seems different as compared to other submissions.  \n\nIn the abstract, \"with seeds 1 to 5\" -> \"with specified seeds (1 to 5)\"\n\nIn section 3.1 the definition and then redefinition in equation 2 is a bit confusing. Why not differentiate the notation?\n\nReferences to books titles like Bottou's should be capitalized. \n\nPage 14  \"Basically, and\" -> \"Basically,\" ", "extra_scores": {}, "extra_text": {}}, {"review_id": "EHkv1EtpefS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Contributions\n\nThis paper presents a novel method to tackle the Byzantine faults problem. By using a local momentum, this method can be extended to all other existing robust algorithms. The authors also provide some theoretical analysis of the effect of their algorithm. Finally, comprehensive experiments are shown and analyzed.\n\n# Strong points\n\n1. The local momentum can be easily combined with other existing robust algorithms, which makes it more practical.\n\n3. This paper has comprehensive experiments that compare the combination of different attacks, defenses and datasets.\n\n4. The authors provide well-written code to reproduce all experiments.\n\n# Weak points\n\n1. The experiments can be improved by running on larger datasets and larger models. Higher dimensionality may also impact the performance. But it is unrealistic to run thousands of large scale experiment, so this weak point is understandable.\n\n2. The assumption is too strong. Namely, each worker can sample from the global dataset, and the norm of \"real\" gradients are bounded.\n\n3. In the theoretical analysis, the variance-norm ration is defined as $r_t^{(s)} = \\frac{\\mathbb {E} \\| \\mathcal{G} - \\mathbb {E} \\mathcal{G} \\|^2}{\\| \\mathbb {E} \\mathcal{G} \\|^2}$. However, when at the (local) optimal, $\\lambda_t^2 = \\| \\mathbb {E} \\mathcal{G} \\|^2 = \\mathbf 0$. Maybe define $r_t^{s}$ as $r_t^{(s)} = \\frac{\\| \\mathbb {E} \\mathcal{G} \\|^2}{\\mathbb {E} \\| \\mathcal{G} - \\mathbb {E} \\mathcal{G} \\|^2}$ can resolve this problem and remove the requirement that $\\lambda_t > 0$.\n\n4. When stating the definition of $\\nabla Q$ being Lipschitz, I think it should be $\\| \\mathbb {E} \\mathcal{G}_t - \\mathbb {E} \\mathcal{G}_u \\| \\leq l^2 \\| \\theta_t - \\theta_u \\|^2$. But it doesn't affect the final result.\n\n# Recommendation\nAccept. This paper proposes a new way to solve the Byzantine faults problem, along with some theoretical analysis, extensive experiments and well-written code.\n\n# Optional improvements\n\n1. Page 3, the first sentence of Adversarial Model paragraph, \"... as the minimization of ...\", do you mean maximization?\n\n2. Definition 1, $(\\alpha, f) \\in [0, .... \\frac{\\pi}{2} [ \\times [0, ..., n]$, is it a typo?\n\n# Update\nThough the theoretical analysis is a bit weak, I think the experiments are quite good. The code can also run without any issue, which is a significant contribution in my opinion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a simple modification of existing byzantine resistant techniques for training in the presence of worst case failures/attacks. The paper studies two of the strongest attacks to date, that no other method, till now, has been able to address. The novelty is significant for the related byzantine ML literature. The authors further do a fantastic job in their experiments and sharing reproducible code. Some weak aspects of theory are in fact attributed to what the metrics and guarantees that the related literature studies. The novelty of this paper does not lie so much in the theory contribution, but more so on their experiments and presented intuition. I believe this will be a paper that people will build up on and the ideas presented here are of solid value and importane.
Decision: Accept (Poster)