Secure Distributed Training at Scale
Authors: Eduard Gorbunov
Alexander Borzunov
Michael Diskin
Max Ryabinin
Venue: ICLR 2022 Submitted (2022)
Keywords: distributed training
byzantine tolerance
volunteer computing

Abstract: Some of the hardest problems in deep learning can be solved via pooling together computational resources of many independent parties, as is the case for scientific collaborations and volunteer computing. Unfortunately, any single participant in such systems can jeopardize the entire training run by sending incorrect updates, whether deliberately or by mistake. Training in presence of such peers requires specialized distributed training algorithms with Byzantine tolerance. These algorithms often sacrifice efficiency by introducing redundant communication or passing all updates through a trusted server. As a result, it can be infeasible to apply such algorithms to large-scale distributed deep learning, where models can have billions of parameters. In this work, we propose a novel protocol for secure (Byzantine-tolerant) decentralized training that emphasizes communication efficiency. We rigorously analyze this protocol: in particular, we provide theoretical bounds for its resistance against Byzantine and Sybil attacks and show that it has a marginal communication overhead. To demonstrate its practical effectiveness, we conduct large-scale experiments on image classification and language modeling in presence of Byzantine attackers.

Under review as a conference paper at ICLR 2022
SECURE DISTRIBUTED TRAINING AT SCALE
Anonymous authors
Paper under double-blind review
ABSTRACT
Some of the hardest problems deep learning can solved via pooling together computational resources of many independent parties, as is the case for scientific collaborations and volunteer computing. Unfortunately. any single participant such systems can jeopardize the entire training run by sending incorrect updates, whether deliberately or by mistake. Training in presence of such peers requires spe- cialized distributed training algorithms with Byzantine tolerance. These algorithms often sacrifice efficiency by introducing redundant communication or passing all updates through a trusted server. As result, it can be infeasible to apply such algorithms to large-scale distributed deep learning, where models can have billions of parameters. In this work, we propose novel protocol for secure (Byzantine- tolerant) decentralized training that emphasizes communication efficiency. We rigorously analyze this protocol: in particular, we provide theoretical bounds for its resistance against Byzantine and Sybil attacks and show that it has marginal communication overhead. To demonstrate its practical effectiveness, we conduct large-scale experiments on image classification and language modeling in presence Byzantine attackers.
INTRODUCTION
Many hard scientific problems were solved through collaboration between many nations, groups and individuals. This especially evident in natural sciences, where researchers formed multinational collaborations to run large-scale experiments and share compute infrastructure (Aad et al., 2012 2; Ruttley et al., 2017; Abbott et al., 2016). Projects like Folding @ home (Beberg et al., 2009) and BOINC (Anderson, 2004) push this trend even further by recruiting volunteers that donate their compute to collectively run computational experiments at an unprecedented scale (Merritt, 2020).
Similar techniques were recently proposed for machine learning. They aim to solve the challenges related to the sheer computational complexity of many machine learning tasks, such as pretraining transformers for NLP (Devlin et al., 2019; Brown et al., 2020; Liu et al., 2019) learning huge datasets in vision (Sun et al., 2017: Kolesnikov et al., 2020; Goyal et al., 2021). Recent works propose several systems (Kijsipongse et al., 2018; Ryabinin & Gusev, 2020; Atre al., 2021; Diskin et al., 2021) that can share the computation across many volunteers that donate the idle time of their computers to train large models on public datasets.
Despite their strengths, volunteer computing systems have so far seen limited practical applica- tions (Kijsipongse al., 2018). A major roadblock towards the global adoption of these techniques trust in reliability of each participant. For distributed training, all progress made by the collaboration can be undermined a single peer sends incorrect outputs due to an error in computation (Smith, 2019) or malicious intent (Tolpegin et al., 2020).
Prior art in decentralized optimization proposed several optimization algorithms that are resistant to such "Byzantine" faults. However, most Syzaantne-toleran training protocols require either passing all updates through a trusted central server or exchanging additional messages that increase the network load by several times (Chen et al., 2018; Rajput et al., 2019). This is major problem for large-scale distributed deep learning, where hundreds of peers must exchange updates for millions of parameters regular intervals (Li et al., 2020; Sergeev & Balso, 2018; Shoeybi et al., 2019). Thus, in many practical scenarios, the computation and communication overhead of Byzantine-tolerant algorithms outweighs the potential benefits of collaborating with others.

---

Under review as a conference paper at ICLR 2022
In this work, set out to solve this problem by proposing novel distributed training protocol designed for large-scall deep learning workloads. Our approach combines the scalability and communication efficiency of modern distributed training techniques such All-Reduce SGD (Sergeev & Balso, 2018) with resilience against Byzantine and Sybil attackers. To achieve this, we leverage distributed system security techniques verify the integrity of training with minimal overhead that does not depend on the model size. Our protocol does not require trusted peers, operating under the assumption that anyone can be an attacker. Our contributions can be summarized as follows:
We propose a novel strategy for decentralized Byzantine-tolerant training on data available to all participants, where the extra communication cost does not depend on the number of parameters.
We rigorously analyze the proposed strategy and prove convergence bounds for convex and non- convex losses with Byzantine attackers. Furthermore, we derive accelerated convergence rates for the same task under realistic assumptions about model gradients.
Based on the above algorithm, we describe a system that allows multiple parties to train a shared model with zero trust assumptions. We prove that this system is resistant to both Byzantine and Sybil attacks from a computationally constrained attacker.
We verify the effectiveness of our algorithm through both controlled experiments and actual large-scale training runs. Specifically, we start with ResNet-18 18 for CIFAR-10 classification and follow up with pretraining ALBERT-large in a setup where almost half all peers are malicious.
2 RELATED WORK
2.1 DISTRIBUTED DEEP LEARNING
Nowadays, training neural networks often requires the amount of computation that is infeasible to achieve on any single machine. As a result, one has to train such models on multiple machines using specialized distributed training methods. Most of these methods fall into two groups: in duta-parallel training, each worker trains the entire model by sampling batches from the training data (Sergeev Balso, 2018; Goyal et al., 2017); 7); in contrast, model- maade-laalllll training allocates parts of the model on different workers (Huang et al., 2019; Narayanan et al., 2019; Shocybi et al., 2019). In this study, we consider only the first group; notably, most model-paralle systems still rely on data parallelism between nodes at the same stage (Rajbhandari et al., 2020; Narayanan et al., 2021).
Usually, Kata-parallel training consists of two phases: first, each worker computes the gradients over its data; then, all workers aggregate the gradients and run an SGD step. The simplest aggregation strategy is known as Parameter Servers (PS) (Li, 2014; Dean et al., 2012; Recht et al., 2011) 1): one of the servers stores and updates the model parameters, while all others iteratively compute the gradients, send them the PS, and download the updated parameters. This strategy can be quite efficient with small number of workers; as it increases, the parameter server eventually becomes unable to handle the load. Gradient compression (Seide et al., 2014; Lin et al., 2018; Mishchenko et al., 2019; Koloskova et al., 2020) or local updates (Zinkevich et al., 2010) can partially alleviate this issue, but it remains a fundamental bottleneck of the approach.
In practice, most distributed training systems leverage All-Reduce (AR) (Goyal et al., 2017: Mikami et al., 2019; You et al., 2020) - a family of collective communication protocols that allow servers to average their data and receive the result on each machine. The resulting method, named All-Reduce SGD (AR- DGD), runs AR on local gradients of each peer to compute the global average. Usually, AR-SGD uses bandwidth-optina. versions of All-Reduce (Sergeev & Balso, 2018; Patarasuk & Yuan, 2009); depending on the exact algorithm, they require each peer to transfer (d)) or (d n) data when averaging vector of size d across n peers (compared to (dn)) for PS).
2.2 BYZANTINE- TOLERANT OPTIMIZATION
Standard distributed training methods are not robust against Byzantine attacks. In the vanilla parallel SGD, one malicious worker can break the convergence of the whole method by shifting the mean of the resulting vector in an arbitrary way. Therefore, the research community invented specialized
Source code for the experiments is available htttt:://githhhi rt-pn/eerrrpprrrr r-parerrr//eaa paaper/BTARD /BTRDD
2

---

Under review as a conference paper at ICLR 2022
algorithms that train models even in this setup. These algorithms are different in nature and provide an extra layer of complexity on top of distributed training methods described in Section 2.1.
Parameter-server (PS) based approaches. Majority of the algorithms designed to be Byzantine- resilient rely on the existence of trusted parametcr-server. In such approaches, the standard mean estimator, e.g., the one used in parallel SGD, is typically substituted by more robust aggregation rule (Blanchard et al., 2017; Yin et al., 2018; Damaskinos et al., 2019; EI Mhamdi et al., 2018; Pillutla al., 2019). However, recent works show that it not enough via proposing the special types of Byzantine attacks (Baruch et al.. 2019; Xie et al., 2020) and showing that permutation-invarian algorithms cannot converge to any predefined accuracy of the solution (Karimireddy et al., 2020).
Although several approaches aiming to circumvent this issue exist, most of them have significant limitations such as no convergence analysis (Chen et al., 2018: Rajput et al., 2019; Rodríguez- et al., 2020; Xu & Lyu, 2020), too restrictive assumptions in the analysis (Alistarh et al., 2018; Allen-Zhu et al., 2021; Regatti et al., 2020), or the usage of variance-reduced estimators (Wu et al., 2020), which are known to converge slowly in deep learning applications (Defazio & Bottou, 2019). The only paper without such limitations is (Karimireddy et al., 2020), where the authors propose a new aggregation rule called CENTEREDCLIP. apply it to SGD with client momentum, and prove convergence results for the obtained method in the non-convex case under reasonable assumptions. We provide more details on cetantinnetoleran PS based approaches in Appendix A.1.1.
Decentralized approaches for Byzantine-toleran optimization are studied only in a few papers. Unfortunately, the known approaches are not well-suited for distributed deep learning since they either rely on full gradient computations ( (Yang & Bajwa, 2019a;b) or use redundant communications with multiple servers (EI-Mhamdi et al., 2020), or require peer-to-peer communication of full vectors at each step (Gupta et al., 2021; Gupta & Vaidya, 2021), which is not scalable, or provide the convergence guarantees that are inferior to non-pan non-parallel SGD (Peng et al., 2021), which has prohibitively slow convergence on modern deep learning tasks, Further details on Byzantine-toleran decentralized approaches are deferred to Appendix A.1.2.
2.3 SECURITY IN DISTRIBUTED SYSTEMS
In this work, we circumvent the restrictions of existing cecantine-tlerran techniques using the following approaches from the field of distributed system security.
Broadcast channels. Several key stages of our algorithm require peers to send certain value to all their groupmates. Since we rely exclusively on peer-to-peer connections, a malicious peer could violate this process by deliberately sending different values to each participant. To protect against this attack, distributed systems can use broadcast channels built on top of the protocol for Byzantine broadcast from Dolev & Strong (1983). This protocol ensures that the peers agree on the same broadcasted value even if some of them are malicious. We provide more details on its guarantees in Appendix 1 I and review its communication cost in Appendix B.
Multi- Palti-partyyao random number generators. To ensure that peers compute gradients honestly, our approach verifies a random subset of all computed gradients. These verifications would not be effective if malicious peers could predict (or influence) whether they are going to be verified. Hence, we need to choose who is going to be checked in such a way that the attackers can neither predict nor influence the random draw. This can be done with a multi-party random number generator (MPRNG) based on multi party coin tossing protocol, such as the protocol from Blum (1983). We provide an overview of this protocol in Appendix A.2.2 and review its communication cost in Appendix B.
3 METHOD
We consider secure distributed training on public datasets, where each peer can access the entire training data and communicate with any other peer. In this scenario, multiple parties cooperate by combining their computational resources for a single large-scale training run. More precisely, we consider data-pan data-parallel training setup with All-Reduce SGD, as described previously in Section 1. We describe our strategy in several stages, progressively moving from the theoretical setup to real-world distributed training:
Section 3.1 outlines approach for Byzantine- ByzantiineTooerratt All- All-Reduce (BTARD).
3

---

Under review as a conference paper at ICLR 2022
gt Viz', ()
ChvmrnnnCrar
Varify that
CenteredClip performed cocredtly
BROADCAST hash (i))
0
Generate MPRNG
projections
V(x',
Outlen
a(r')
clisped
Peer validates gj from the previons step, and j are randomly chosen using
Figure 1: An intuitive scheme demonstrating one step of Byzantine-Tolerant All- This is part of the Algorithm executed between the consecutive SGD steps. Here, t the step number, x is the model weights, and 5 is publicly known random seed for sampling minibatch.
In Section 3.2, formulate the underlying optimization problem and derive convergence bounds. In Section 3.3, we propose a decentralized system design for distributed training with zero trust.
3.1 DYZANTINE-TOLERAT ALL-REDUCE
We assume that some workers can be malicious, i.e., they can arbitrarily deviate from our algorithm: for instance, send arbitrary vectors instead of the stochastic gradients violate the communication protocol. Such workers are denoted as Byzantine nodes or just Byzantines. We assume them to be omniscient (Karimireddy al., 2020) (except for the honest nodes' private keys and the internals of MPRNG) and able to collude with each other. We denote the set of all "good" workers as G and the set of Byzantine workers as B. We further assume that B is fixed throughout the optimization process, and less than half of the nodes are Byzantine: |B] < ôn, where â E [0, 1/2). Finally, we assume that all workers have access to the data defining the objective function, so they can sample minibatches from the full dataset.
We design our algorithm in such a way so that all types of Byzantine faults have limited effect and chance of being discovered. Together, these properties impose limit on the total damage that an attacker can do over the entire training run. To control the magnitude of attacks over a single SGD step, we modify All-Reduce with robust aggregation technique known as CENTEREDCLIPP (Karimireddy et al., 2020). Specifically, we use Butterfly All-Reduce (Li et al., 2017) and apply CENTEREDCLIP in parallel to each partition of the gradient vector. We refer to this procedure as BUTTERFLY YCLIP (Algorithm 2).
However, Byzantine peers can circumvent robust aggregation by attacking over many iterations. To protect against this, BTARD periodically chooses random peers to serve as validators. The validators must recalculate the gradients of other peers and report any discrepancies instead of computing their own gradients. However, such tests are only effective if the attackers cannot predict when they will be validated*. To ensure that, we use the multi-party random number generator described in Section 2.3.
After each training step, peers use MPRNG to choose validators and m peers to validate (each validator checks one peer). As result, malicious peers cannot predict "safe" iterations before they commit to an attack. Thus, any persistent attacker will eventually be found by an honest validator.
However, since validators can also malicious, BTARD uses separate accuse procedure to root out false reports. Before each averaging round, peers broadcast the hash of their gradients for that round. These values serve the same purpose as commitments MPRNG. peer accuses peer j of modifying gradients, all other peers must also recalculate j's gradients. If the majority finds that is innocent, the accusing peer i is banned instead (Hammurabi & Harper. 1904).
The resulting algorithm is resilient to attacks made through incorrect gradients. However, malicious peers may also harm training by violating the CENTEREDCLIP procedure for the portion of gradients they aggregating. Fortunately, we design test through which peers can verify that the vector
2 'e et al. (2020) show that it is impossible to achieve any predetined accuracy of the solution without this assumption, i.c., in the heterogencous case (see discussion in Appendix F.2).
We choose Butterfly All-Reduce that peers aggregate non-overlapping parts of the gradient vector. This helps to identify the attacker if the gradients are aggregated incorrectly. Jiang et al. (2020) report that Butterfly All- All-Reduce is oparmaptimal for distributed training over high-latency networks such as the Internet.
Otherwise, Byzantine peers simply defer the attack subsequent steps when they are not validated.
4

---

Under review as a conference paper at ICLR 2022
they received indeed the output of CENTEREDCLIP. To formulate this test, need to view CENTEREDCLIP as a fixed-point iteration for the equation:
Σ
C min 1,
(1)
The workers are not able to test whether (1) holds directly since collecting Zi would lead to ((dn) extra communication, defeating the purpose of our algorithm. Instead, workers should use MPRNG to sample random direction in the space of model gradients. Then, each peer computes the inner product (2) and sends it through the broadcast channel (as described Section 2.3):
9,= 2, (g.
min
g
Finally, all peers verify that Σx= 82 O. Similarly to our previous of MPRNG, all aggregatirs must commit to their aggregation results before they learn ž. This ensures that malicious aggregator cannot modify the results such way that the difference would be orthogonal complex attack vectors are reviewed and analyzed in Appendices C and D.3).
(this and more
We combine all these procedures in Algorithm (see its intuitive scheme in Figure 1 and a more formal version in Algorithm 6). While gradients 9s, random vector and some other variables are not the same during different steps, we omit the step index / their notation for brevity. We review communication and computational complexity of the algorithm in Appendix B.
Algorithm BTARD-SGD for peer (informal)
Algorithm 2 BUTTERFLY YCLIP for peer
Input: rank model æ9, seed < step count T.
peer count n
Input: rank i, gradients g:
1: for E O,....; T- do
1: 9: [1] ... 9: [ SPLIT n))
2: 9: COMPUTEGRADIENTS(C""
2: broadcast Vj. h? hash(g(())
BUTTERFLYCLIP(iist 4: r MPRNN()
3:
3: send Vj. 9 + peer,
4: receive Vj, 9 + peer,
5: GETRANDOXVECTOR(P""
5: verify Vj. hash(g) [i]) hj
6:
for j E 1....,7 do
6: 9: CENTEREDCLIP(OL
Inlil)
7:
[[]] is the aggregated part from peer
7: send Vj. 0i - peer,
8:
() 9(il) min 1, [s.. 95
8: receive Vj, O3 peer,
9:
broadcast s! (=()),a)
9: return MERGE( .... 9n)
10:
for j E 1, ....., do We know A from CENTEREDCLIP if s * (=b)),A) AJ) then AcCUsE(i. s² wrong)
11:
Algorithm 3 ACCUSE (i. j. allegation)
12:
Input: accuser i, target
13:
1: 9j = COMPUTEGRADIENTS(C E
14:
if ET of 0 then
2: if EK (hash( وj (+) # h
// Peer verified that s! are correct
3: or s)>(<<|)) Af)) or Σ $0
16:
AcCUsE(i, j. ]l.] is wrong)
then
17:
1+1 SGDSTEP(2',5
4: VoTEFORBAN(perr)
18:
2+1 hrsh(r*11))
5:
... and everyone who covered up
19:
if i E CHOOSE (ALIDATORS(")) then
6: else
20:
j = CHOOSETARGEE((71)
7:
VOTEFORBAN((eer)
21:
VALIDDATEPERR
C, h h),8)) 87))
8: for À 1,.... n do
instead of computing gradients
()MVor)s(peerr. 2 n/2 then 10: (AN(r))r,)
9:
23:
// for step 1+1
24:
return T
3.2
CONVERGENCE ANALYSIS
From the perspective of optimization theory, task is the expectation minimization problem:
min (f(x) = EgWD [f(x,
(3)
ZEQER4
5

---

Under review as a conference paper at ICLR 2022
Here, the objective function f is smooth and uniformly lower bounded, C IR is a closed convex set of admissible parameters and { is the source of stochasticity, such as minibatch indices. We assume that the problem (3) can be solved in a distributed manner, i.c., one can workers performing (mini-batched) stochastic gradients calculations in parallel and communicating according to some
protocol. For simplicity, will define the set of workers [m]] == (1, ... n) L
There are many ways for Byzantines to affect the training. For example, a malicious peer may perform: (i) gradient attacks, where Byzantines modify their g²¹, but otherwise behave normally; (ii) aggregation attacks, where Byzantine aggregator returns wrong 0i and relies on others to cover it up by misreporting s;; (iii) reputation attacks such as frame-up or slander via false ACCUSE(i. :); and finally, (iv) protocol errors are any other deviations from the steps of Algorithm 1, e.g. refusing to send any data. We elaborate on each attack type Appendix
For the purpose of this analysis, the latter two attacks can be repelled with an extra policy that allows an active worker to eliminate any other worker at the cost of also being banned. Whenever a benign peer i encounters a protocol error from another peer j. it invokes that policy to remove both himself and peer j from training. The design of this policy ensures that every invocation, whether by normal or Byzantine peers, eliminates at least 1 Byzantine peer and at most 1 benign peer. Thus, if a Byzantine minority uses this against benign peers, this will only decrease their relative numbers: (ôn 1) 2) < 5. This leaves with two attacks that both target the aggregated gradients.
We provide convergence guarantees for variants of BTARD-SGD with Q = g under different sets of assumptions about the function f and its stochastic gradients. Our first two setups assume, that: Assumption 3.1. There exist such constant a 2 O, E [d] that for any set of indices S = < <is S d, s 2 Sy stochastic gradient f {) satisfy
(i1. 1x), Ish < 12 <...
- - V[s][(>)) so² where (ss)f(x, = (V,, (() (a, (1) (V,, (x, {). fz)) are j-th components of fz, and f(z) respectively.
EV - Vi())
E
(4)
d
and
Here, (4) is an extension of the classical uniformly bounded variance (UBV) assumption (Nemirovski et al., 2009; Ghadimi & Lan, 2012: 2013) ensuring that the noise in all subvectors of large enough dimension has the variance dependent on the ratio between the dimension of the subvector s and the dimension of the full vector d. For example, it holds when the noise is isotropic. Moreover, one can relax this assumption to the standard UBV assumption, if blocks for aggregation in BTARD are chosen uniformly at random (see Appendix 1.3. for further details). In order to further reduce overhead from Verification 3 in the full Algorithm 6, also assume that the stochastic gradient distributions have sub-quadratically decreasing tails (see details in Appendix E.3.I).
Assumption 3.2. There exist such constant a 2 O, 8o E [d] that for any set of indices S = (i....., ie), 1 S i < i2 < < i S d, 2 so stochastic gradient V ff(x, E) satisfy
tso
1 12'
P [Iss((,, VisiS(())
41 0,
(5)
kd
where Es. are i.i.d. samples from D, and (ss) E), (z)) are defined in As. 3.1.
Under these assumptions, we derive the following convergence bounds for strongly convex, generally convex, and non-convex objectives (see Table 1). The respective proofs are deferred to Appendix E.4.
Let us briefly discuss the main properties of the derived results. When 8 0, i.e., there are no Byzantine peers, we recover the tightest known rates for parallel SGD for strongly convex, generally convex, and non-convex objectives with both sets of assumptions. Next, we notice that in all complexity bounds in the known [ case, the term depending on the ratio of Byzantine workers (the third one in all bounds) has better dependence on the accuracy of the solution e than the classical variance term (the second one in all bounds). Therefore, for sufficiently small E, the derived complexity bounds are the same as in the case when there are no Byzantine workers and parallel SGD is used. However, these bounds are obtained under the assumption that all participants know the exact number of attacking Byzantine workers at each iteration, which is not realistic but helps to better adjust clipping parameter 7 in CENTEREDCL.IP.

---

Under review as a conference paper at ICLR 2022
Table I: Summary of complexity bounds for BTARD-SGD in different scenarios. By complexity we mean the number of iterations sufficient to find such point T that B[[[V [ < E² for non non-convex problems and E[S(T) [a=")] I for convex and p-strongly convex problems (see Def. E.2) with x² being the solution. Notation: "known [3%, I" = the exact number of attacking Byzantine workers at iteration is known to each participant, L = smoothness constant (see Def. E. Ao f(a") f+. fo uniform lower bound for f. o² variance parameter from As. 3,1, n = the initial number of peers, b= = the initial number of Byzantine workers,
8 = n/, number of peers checked each iteration, Rg = || 2=I
Convexity of f
Assumptions
Non-convex
Convex
Strongly convex
As. 3.1+ As. knowww [B%]
Lå
LAno? net
udo? ma?
L.
a² Rd nea
ny/aa Bi me
L
log
o² upe
avōe myRe
As. 3.1 + As. 3.2
1.p
LAge² 2g LR
o² Rd.
log
RR ga
ne"
me
ne"
me
npe
m. my/pE
As for the more general case, the third term is much worse than the corresponding term in the previous setup. Nevertheless, the term that depends on the ratio of Byzantine workers has the same dependence e as in the known [8[] case. This implies that for sufficiently small e the derived complexity bounds are the same as in the case when there are no Byzantine workers and parallel SGD used. For complete formulations, proofs and other details we refer the reader Appendix E.3.
So far, all our convergence results rely on As. 3.2, i.e., that the stochastic gradients have not too heavy tails. This assumption holds for many real-world neural networks. However, there are important NLP tasks such as BERT training (Zhang et al., 2020), where the noise in the stochastic gradient has such a heavy noise that As. 3.2 becomes unlrealistic. The third and final setup in our analysis aims to address such heavy-tailed problems with STARD-CLIPPED-I Algorithm 8 in appendix). We analyse the method under the assumption that a-th moments of the stochastic gradients are uniformly upper-bounded for some
(see full
(1, 2]. We notice that for a < 2 this assumption allows the variance of the stochastic gradient to be unbounded. In this setting, we prove that SEAARD-CLIPPE---C
finds an e-solution of the convex problem after o (---)-))) (1+ (RVB/m) f(a--)) ") iterations when the number of attacking Byzantine peers is known at each iteration and O (g-%/u 1) (1 + (1²6% ( iterations otherwise. One can find
the full statements and complete proofs of our results in Appendix E.
3.3 RESISTING SYBIL ATTACKS
The algorithm described in Section 3.1 operates with pre-defined list of peers that can only decrease in size. However, many real-world scenarios would benefit from new peers joining midway through training. Unfortunately, this exposes the system to Sybil attacks (Douceur, 2002), when a single computationally constrained attacker adopts multiple pseudonymous identities in order to establish a dishonest majority and break the algorithm.
To handle this, one may augment BTARD with a heuristic protocol that dictates how new peers can join. A new participant must prove that it has honestly computed enough gradients over multiple continious iterations before it allowed to actually contribute to the training. This ensures that the influence of Sybil attackers is proportional to their computing power (see details in Appendix F).
EXPERIMENTS
4.1 CIFAR10 CLASSIFICATION
First, we evaluate our approach with a realistic image-classification workload controlled conditions. Our setup is a ResNet-18 (He et al., 2015) model trained to solve the CIFARIO classification task (Krizhevsky et al.). We train the model on 16 peers (each peer processes samples per batch) using the SGD with Nesterov (1983) momentum and the cosine annealing learning rate (Loshchilov & Hutter, 2017). We deliberately use a tuned setup that achieves 93.5% % test accuracy in order to measure how Byzantine attacks affect this training outcome.
7

---

Under review as a conference paper at ICLR 2022
Convergenoe
Convergence (zoomed in)
Ours, T 1, attack slep
0.94
0.8
Baseline (AR-SGD)
1:st occuncyy
0.5
Coerd-wise median
0:58
0.6
Grometric median
0.4
CenteredClip lip with PS
0.92
0.4
Ours, T-]
0.2
Ours, == 10
0.91
0.2
10000
15000 20000
25000
14000
16000
15000
20000
22000
1000
2000
4000
Ours, T- 10, atlack at step 1000
Ours, T- 10, allack step 10000
Ours, T 1, allack at step 10000
0.95
0.95
0.8
Tost sccuney
0.90
0.90
0.5
No artocks
0.85
0.85
Sign flppiing
0.4
0.80
0.80
Ramdom direction
Label flipping
0.2
0.75
0.75
Delayed grudients
1000
4000
9500
10000
19500
11500
120000
95:00
10000
10500
11500 12000 Theining step
11000
Trinning stop
Trining step
Figure 2: (Upper-Left, Upper-Middle:) ResNet-18 test accuracy with different robust aggregation techniques (without attacks). (Other plots:) Effectiveness of Byzantine attacks on BTARD-SGD.
We evaluate our method with constant - = 10 (weaker clipping) and with r = (stronger clipping). These values were chosen based on the maximal standard deviation of the gradient parts averaged by the workers during normal training, so that almost no vectors are clipped for the weaker clipping and approximately half of the vectors are clipped for the stronger clipping scenario. BTARD randomly selects validator on each step. If the validator happens to be Byzantine, it does not accuse its peers.
We compare our method to the regular All-Reduce without clipping and the baselines that use a trusted parameter server (the original variant of CENTEREDCLIP (Karimireddy et al., 2020), the coordinate-wise and geometric medians). Some other popular robust aggregation techniques are omitted because they were shown to be inferior (Karimireddy et al., 2020). We run all iterative algorithms (such as CENTEREDCLIP) to convergence with e = 10 6 as we have found that limiting the number of iterations significantly decrease the final model quality (see Fig. 7 in Appendix I.1).
In addition to training convergence, we evaluate our setup in presence of malicious peers. To test pessimistic conditions, we pick setting where 7 of 16 peers are Byzantine (other setups can be found in Appendix I.1). We experiment with the following attack types:
SIGN FLIPPING: each attacker sends the opposite of its true gradient.
RANDOM DIRECTION: all attackers send large vectors pointed at a common random direction.
LABEL FLIPPING: each attacker computes its gradient based on the cross-entropy loss with flipped labels. For CIFAR-10, replace label 1 {o.... ..., 9} with 9 I.
DELAYED GRADIENT: attackers send their real gradients delayed by 1000 steps.
We further amplify the Byzantine gradients from the first two attacks by a large coefficient À 1000 so they would dominate the aggregated gradient if no clipping is used. While in practice such attacks can be identified right away due to the large gradient norms, we deliberately avoid doing that to test our clipping approach. We also evaluate common low- magnitude attacks (Baruch et al., 2019; Xie et al., 2020: Allen-Zhu et al., 2021) in Appendix I.4.
For each experiment configuration, Byzantines behave honestly prior to step 8, then simultaneously attack on each subsequent step until they are banned (another setup with the Byzantines attacking periodically is reported in Appendix I.I). We consider attacks in two training regions: early stages (s = 1000) and closer to convergence (s = 10,000). We repeat each experiment times and report the mean and range of the test accuracy during at least 2000 steps after all Byzantines are banned. In our experiments, this usually happened within 150 steps after s.
The results are shown in the Fig. 2. Comparing to the All-Reduce baseline, we note that our method does not worsen the speed of convergence. On average, the final test accuracy is 0.6% worse for 1 and 0.1 % better for 7 10. The two most effective attacks (in terms of accuracy) the
8

---

Under review as a conference paper at ICLR 2022
Convergence
Ours, T 0.125, slep 1000
Baseline (AR-SGD)
Ours, 0.125
10.0
8
Ours, 0.25
9.-
4
0
1000
2000
3000
4000
5000
1000
1050
1100
1150
Ours, 0.5, attack step 1000
Ours, 0.5, attack at step 5000
Ours,
0.125, atlack step 5000
12
No attacks
Sign flipping
11
Random direction
Label flipping
3-
10
1000
1050
1100
1150
5000
5050
5100
5150
5000
5050
5100
5150
Tmining step
Training
Training step
Figure 3:
(Upper-Left:) ALBERT-large training objective using AR-SGD and BTARD-CCiped-SSG (without attacks). (Remaining plots:) Effectiveness of Byzantine attacks on BTARD.
random direction and sign flipping. The effect of label flipping is smaller, and the effect of delayed gradients is almost undetectable.
4.2 PRE-TRAINING TRANSFORMERS
For our second experiment, we choose a more compute-intensing and hyperparameter-sensiinne model with adaptive optimizers demonstrate that our approach may be applied to models that are commonly used in distributed training scenarios. Our setup is pre-training the ALBERT-large model (Lan al., 2019) on the Wikitext 103 dataset (Merity et al., 2017) using LAMB (You et al., 2020). Since the original ALBERT setup uses gradient clipping, we use STARD-CLIPPED SGD (see Alg. 8 Appendix). We train the model on 16 machines that jointly accumulate 4096 samples for every batch. Similarly to the previous section, we evaluate two configurations with r = 0.5 (weaker clipping) and 0.125 respectively, in addition to an All-Reduce baseline. To evaluate Byzantine tolerance, we also use 7 out of 16 Byzantine workers, 1 validator and two attack regions: s = 1000 and s = 5000. We omit reporting of the delayed gradient attack as we have found it completely ineffective. The full configuration of this experiment is provided in Appendix H.
The results shown in Figure 3 demonstrate a pattern similar to the previous section. During normal training, both values had no significant effect on the training progress, reaching 1.3% larger loss in the worst case. However, 7 = 0.125 shows significantly faster recovery from all three attacks. One important observation from these experiments is that while some attacks significantly increase the loss function, the model returns to the previous loss value much faster than it takes to reach the same loss when training from scratch. We further study the computation overhead of BTARD in this setup in Appendix 1.2 and provide the experiments with a larger number of peers in Appendix I.3.
5 CONCLUSION
In this work, we formulated BTARD--GD- -a Byzantine-tolerant training strategy for large neural networks. We verified its robustness and effectiveness through rigorous theoretical analysis and large-scale distributed training experiments. While our research is mostly algorithmical, it can open new opportunities in many deep learning applications.
Perhaps the most important one is making it possible to train large neural networks in a cooperative manner. BTARD- could allow small research groups to host open cooperative training projects where the training hardware is crowdsourced by volunteers around the world. Alternatively, group of small companies could collectively compete with larger corporations by combining their compute clusters. While these applications also require engineering effort to become practical, our algorithm ensures that they can run securely without the need to carefully screen every potential participant.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Georges Aad, Tatevik Abajyan, and The ATLAS Collaboration. Observation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC. Physics Letters B, 716:1-29, 09 2012.
Benjamin Abbott, LIGO Scientific Collaboration, and Virgo Collaboration. Observation of Gravi- tational Waves from a Binary Black Hole Merger. Physical Review Letters, 1 116, 02 2016. doi: 10. 1..1103/Physev..ccm 11.066 102.
Ittai Abraham, TH Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 317-326, 2019.
Dan Alistarh, Zeyuan Allen-Zhu, and Jenry Li. Byzantine stochastic gradient descent. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 4618 (618-4628, 2018.
Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzantine-resilient non- convex stochastic gradient descent. In International Conference on Learning Representations. 2021. URL hwwps:ttt//o http://peeeeeeeeeeeeeeeeeee forum? ddPbEHqqFtcs..
David P Anderson. Boinc: A system for public-resource computing and storage. In Fifth IEEE/ACM international workshop on grid computing, pp. 4-10. IEEE, 2004.
Medha Atre, Birendra Jha, and Ashwini Rao. Distributed deep learning using volunteer computing- like paradigm, 2021.
Hari Balakrishnan, M Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in p2p systems. Communications of the ACM, 46(2):43-48, 2003.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. little is enough: Circumventing defenses for distributed learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. l'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL / ec1c5914 4 04 6cd1 8 36bbboddfbaaeedddppapeeee.
/
A. L. Beberg. D. Ensign, G. Jayachandran, S. Khaliq, and V. Pande. Folding@home: Lessons from eight years of volunteer distributed computing. 2009 IEEE International Symposium on Parallel & Distributed Processing, pp. 1-8, 2009.
Walid Ben-Ameur, Pascal Bianchi, and Jérémie Jakubowicz. Robust consensus in distributed networks using total variation. arXiv preprini arXiv:13000 7264, 2013.
Peva Blanchard, Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 118-128, 2017.
Manuel Blum. Coin flipping by telephone a protocol for solving impossible problems. ACM SIGACT News, 15(1)233-27, 1983.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voos Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot leamers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL https: http://ppoeeeeei..n.eec ips.ce/ paper/2020/
Saikiran Bulusu, Prashant Khanduri, Pranay Sharma, and Pramod K Varshney. On distributed stochastic gradient descent for nonconvex functions in the presence of byzantines. In ICASSP 2020- 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp- 3147-3141. IEEE, 2020.
10

---

Under review as a conference paper at ICLR 2022
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. In International Conference on Machine Learning, pp. 903-912 PMLR. 2018.
Richard Cleve. Limits on the security of coin flips when half the processors are faulty. In Proceedings of the eighteenth anmual ACM symposium on Theory of computing, pp. 364-369, 1986.
Georgios Damaskinos, EI Mahdi EI Mhamdi, Rachid Guerraoui, Arsany Hany Abdelmessih Guirguis, and Sébastien Louis Alexandre Rouault, Aggregathor: Byzantine machine learning via robust gradient aggregation. In The Conference on Systems and Machine Learning (SysML), 2019, 2019.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc Le, and Andrew Ng. Large scale dis- tributed deep networks. In F. Pereira, C. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances Neural Information Processing Systems, volume 25, pp. 1223-1231. Curran As- sociates, Inc., 2012. URL httpps::/prceeeeggggs. Bb.37706663112062221155111111882 Pappeee...
ips.ii..scc. http:/ppprrr//// /ttp.cc//ppp///22/////..
Aaron Defazio and Leon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL http://:/pppcceeeegggneeeppppppe
/ille/
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances In Neural Information Processing Systems, 2014.
Jacob Devlin, Ming-Wai Chang. Kenton Lee, and Kristina Toutanova. BERT. Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT,, 2019.
Michael Diskin, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, Quentin Lhoest, Anton Sinitsin, Dmitriy Popov, Dmitry Pyrkin, Maxim Kashirin, Alexander Borzunov, Albert Villanova del Moral, Denis Mazur, Ilia Kobelev, Yacine Jernite, Thomas Wolf, and Gennady Pekhimenko. Distributed deep learning in open collaborations. CoRR, abs/2106.102000 2021. URL https: // //arxiv.org/ abs / 221.1.0276...
Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983.
John R. Douceur. The sybil attack. In IPTPS, 2002.
EI Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of dis- tributed learning in Byzantium. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3521-3530. PMLR, 10-15 Jul 2018. URL 080/mhamdi11 18.hhtml.
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lê Nguyên Hoang, and Sébastien Rouault. Genuinely distributed byzantine machine learning. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 355-364, 2020.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4):1465 2244):166-11992 1492, 2012.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (3(4):2341-2366 2013.
Shafi Goldwasser, Silvio Micali, and Ronald L Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal computing, 17(2):281-308 1988.

---

Under review as a conference paper at ICLR 2022
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour, 2017.
Priya Goyal, Quentin Duval, Jeremy Reizenstein. Matthew Leavitt, Min Xu. Benjamin Lefaudeux, Mannat Singh, Vinicius Reis, Mathilde Caron, Piotr Bojanowski. Armand Joulin, and Ishan Misra. Vissl, 2021. URL https: : / / thw..com///cooo..tooooooo fa cebook recoookkeeeeeeeeeeee resea rch/vissl
Nirupam Gupta and Nitin H Vaidya. Byzantine fault-tolerance in pecr-to-peer distributed gradient- descent. arXiv preprint arXiv:
2021.
Nirupam Gupta, Thinh T Doan, and Nitin H Vaidya. Byzantine fault-tolerance in decentralized optimization under 2f-redundancy. In 2021 American Control Conference (ACC), pp. 3632-3637. IEEE, 2021.
King of Babylon Hammurabi and Robert Francis Harper. The Code of Hammurabi, King of Babylon: About 2250 BC: Autographed Text, Transliteration, Translation, Glossary Index of Subjects, Lists of Proper Names, Signs, Numuerals... University of Chicago Press, 1904. URL https: Page 11, $1.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2015.
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via resampling, arXiv preprint (rXh::2006.0936651 2020.
Martin Hirt and Pavel Raykov. Multi-valued byzantine broadcast: The t< n case. In International Conference on the Theory and Application of Cryptology and Information Security, pp. 448-465. Springer, 2014.
Y. Huang, Yonglong Cheng, Dehao Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V. Le, and Z. Chen. Gpipe: Efficient training of giant neural networks using pipeline parallelism. ArXiv, abs/1811.06965. 2019.
Yimin Jiang, Yibo Zhu, Chang Lan, Bairen Yi, Yong Cui, and Chuanxiong Guo. A unified architecture for accelerating distributed DNN training in heterogeneous gpu/cpu clusters. In 14th USENIX Symposium Operating Systems Design and Implementation (OSDI 20), pp. 463-479, USENIX Association, November 2020. ISBN 978-1-939133-199 URL https: / /ww.uueniix.org////// pwteeeeecceeccaal///reeeeeaaeeae jiing.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. arXiv preprint arXIv:2012.10333::3 2020.
Ekasit Kijsipongse, Apivadee Piyatumrong, and Suriya U-ruekolan. A hybrid gpu cluster and volunteer computing platform for scalable deep learning. The Journal of Supercomputing, 04 2018. doi: 10. (0007//1122-008--27555
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, S. Gelly, and N. Houlsby. Big transfer (bit): General visual representation learning. In ECCV, 2020.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2020. URL http:s:///oeeneeeieee..tettttt formm wtw.oounnnnnnnncceeeeeeee Skkkkkgk
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar 10 (canadian institute for advanced research). URL http:pp:/ww..c..toootceeeteeeeee
fam.
Zhen-Zhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. ArXiv, abs/1999..1194 2019.
12

---

Under review as a conference paper at ICLR 2022
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. Rsa: Byzantine-robus' stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544-1551, 2019.
Mu Li. Scaling distributed machine learning with the parameter server. In Proceedings of the 2014 International Conference on Big Data Science and Computing, BigDataScience 14, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450328913. doi: 10.1145/2640087 2644155. URL https: /ttp://l....r.....11154400000000
Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, and Soumith Chintala. Pytorch distributed: Experiences on accelerating data parallel training. Proc. VLDB Endow. 13(12):3005-301 August 2020.
ISSN 2150-8097, doi: 10. (14778/3415478.3415555 URL https: 3415478.34155..
Zhenyu Li, James Davis, and Stephen Jarvis. An efficient bask-based all-reduce for machine learning applications. In Proceedings of the Machine Learning HPC Environments, MLHPC 17, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450351379. doi: URL httpp::/f....rrg/1..1555////////
10.1145/3146347.31
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep Gradient Compression: Reducing the communication bandwidth for distributed training. In The International Conference on Learning Reprexentations, 2018.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. ArXiv, abs/1907. 1692, 2019.
I. Loshchilov and F. Hutter. Sgdr: Stochastic gradient descent with warm restarts, In International Conference on Learning Representations (ICLR) 2017 Conference Track, April 2017.
Lingjuan Lyu, Han Yu, Xingjun Ma, Lichao Sun, Jun Zhao, Qiang Yang, and Philip S Yu. Privacy and robustness in federated learning: Attacks and defenses. arXiv preprint arXiv:2012.06337 2020.
Petar Maymounkov and David Mazieres. Kademlia: A peer-to peer information system based on the xor metric. In International Workshop on Peer-to-Peer Systems, pp. 53 65. Springer. 2002.
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Aguera y Arcas. Communication-efin effficient learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
Stephen Merity, Caiming Xiong, James Bradbury, and Socher. Pointer sentinel mixture models. 2017.
ArXiv,
Rick Merritt.
Folding @ home gets 1.5+ Exaftops to Fight COVID-19, 04 2020. https://blogs: aww.coa.aaoooooooooooooooo.oooo. htom/bbor coronavi rus (accessed on Apr 29, 2021).
exaflop-
Hiroaki Mikami, Hisahiro Suganuma, Pongsakorn U-chupala, Yoshiki Tanaka, and Yuichi Kageyama. Massively distributed sgd: Imagenet/resnet-50 training in flash, 2019.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning 2019.
with compressed gradient differences. arXiv preprint
Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R. Devanur, Gre- gory R. Ganger, Phillip B. Gibbons, and Matei Zaharia. Pipedream: Generalized pipeline parallelism for dnn training. In Proceedings of the 27th ACM Symposium on Operating Sys- tems Principles, SOSP '19, pp. 1-15, New York, NY. USA, 2019. Association for Com- puting Machinery. ISBN 9781450368735. doi: 10.1145/3341 101.34111113339944 URL https: //dbb..rg/11..114/344433000
13

---

Under review as a conference paper at ICLR 2022
Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, et al. Efficient large-scale language model training gpu clusters. arXiv preprint arXi:21004.04473 2021.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Y. Nesterov. A method for solving the convex programming problem with convergence rate o(1/k9). Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances Neural Information Processing Systems, pp. 8024-8035, 2019.
Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Parallel Distrib. Comput., 1972):117-124, February 2009. ISSN 0743-7315. doi: 10.1016 j-jpdc. sipdc.2008.com 00008.09.002 URL httthttss///oo// http::/rggg11111///.pp...0000000 3.jpdc.2008.09.c00
6/
Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228-234 1980.
Jie Peng, Weiyu Li, and Qing Ling. Byzantine-robust decentralized stochastic optimization over static and time-varying networks. Signal Processing, 183:108020, 2021.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint 1912: 2019.
Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 73-85, 1989.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimizations toward training trillion parameter models. SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-16, 2020.
Shashank Rajput, Hongyi Wang. Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy-based framework for faster and more robust gradient aggregation. In H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gameet (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL 415185ea244eai 222.5522222222222200000022222223 Paper.ddf.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pp. 693-701, 2011.
Jayanth Regatti, Hao Chen, and Abhishek Gupta. Bygars: Byzantine sgd with arbitrary number of attackers. arXiv preprint arXiv:2006. 13421, 2020.
Ronald Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21 1978.
Nuria Rodríguez-BBi Barroso, Eugenio Martínez-Cámant M Luzón, Gerardo González Seco, Miguel Án- gel Veganzones, and Francisco Herrera. Dynamic federated learning model for identifying adver- sarial clients. arXiv preprint arXiv:2007. 2020.
14

---

Under review as a conference paper at ICLR 2022
Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to to- to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms and Open Distributed Processing, pp. 329-350 Springer, 2001.
Tara Ruttley, Julie Robinson, and William Gerstenmaier. The international space station: Collabora- tion, utilization, and commercialization:: The international space station. Social Science Quarterly, 98:1 160-1174, 12 2017. doi: 10.1 1/ssqu. 12469.
Max Ryabinin and Anton Gusev. Towards crowdsourced training of large neural networks using decentralized mixture-of-experts. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3659-3672. Curran Associates, Inc., 2020. URL
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 1..18653/11/11- 1162. URLhttpst http://wwww.b.brr/ggg//ooo////// Pothologyy/P16111
Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow, 2018.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billio parameter language models using gpu model parallelism. arXiv preprint arXiv: 08053, 2019.
Bob Smith. Flakey amd/ati gpus, including rx 5700 xt, cross validating, polluting the database, 2019. URL https:: /ppps://eee //see/iatteeeeeeeeeeeeee hww.///rweeeeeeeeeeeeeeeeeeeeeee forum wttpthh.pppp.ddddaee Accessed: 2021-05-20.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning In Proceedings of the IEEE International Conference Computer Vision (ICCV), Oct 2017.
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems. In ESORICS, 2020.
Zied Trifa and Maher Khemakhem. Sybil nodes mitigation strategy against sybil attack. Procedia Computer Science, 32:1 135-1140, 2014.
Guido Urdaneta, Guillaume Pierre, and Maarten Van Steen. A survey of dht security techniques.
ACM Computing Surveys (CSUR), 43(2):1-49, 2011.
Liang Wang and Jussi Kangasharju. Real-world sybil attacks in bittorrent mainline dht. 2012 IEEE Global Communications Conference (GLOBECOM), pp. 826-832. IEEE, 2012.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variaeee-reduced
stochastic gradient descent with robustness byzantine attacks. IEEE Transactions on Signal Processing, 68:4583-4596 2020.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270. PMLR, 2020.
Xinyi Xu and Lingjuan Lyu. Towards building robust and fair federated learning system. arXiv preprint arXiv:2011. 1..-24441.1444. 2020.
Zhixiong Yang and Waheed U Bajwa. Bridge: Byzantine-resille decentralized gradient descent. arXiv preprint arXiv: /908.000000 08098, 2019a.
15

---

Under review as a conference paper at ICLR 2022
Zhixiong Yang and Waheed U Bajwa. Byrdie: Byzantine-resilien distributed coordinate descent for decentralized learning. IEEE Transactions on Signal and Information Processing over Networks, (4):611-627, 2019b.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantinerrobust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Reprexentations. 2020. URL https: http//ppeeeeeeeeeeeeeeee
forum? id=Syx444ia. wn.
En Zhang, Feng-Hao Liu, Qiqi Lai, Ganggang Jin, and Yu Li. Efficient multi-party private set intersection against malicious adversaries. In Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, pp. 93-104, 2019.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15383-15393, Curran Asso- ciates, Inc., 2020. URL b0BSFFEaaad100bb70066666660----3
Ben Zhao, Ling Huang, Jeremy Stribling, Sean Rhea, Anthony Joseph, and John Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications, 22, 07 2003. doi: 10.1009//A... 818784.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradi- ent descent. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta (eds.), Advances Neural Information Processing Systems, volume 23, pp. 2595-2603, Curran As- sociates, Inc., 2010. URL abea47ba2. 41 42edl Pap.
f/file/
16

---

Under review as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL
TABLE OF CONTENTS
Introduction
2 Related work
2.1
Distributed deep learning
Byzantine-toleran optimization
2.3
Security in distributed systems
3
Method
Byzantine- Tolerant Byzeraine-Tolerant All-Reduce
3.2
Convergence analysis
3.3
Resisting Sybil attacks
Experiments
4.1
CIFAR10 classification
4.2
Pre-training transformers
Conclusion
Additional related work
18
A.1
Byzantine-toleran optimization: additional details
18
A.1.1
Parameter-server (PS) based approaches
18
A.1.2 Decentralized approaches
18
A.2 Security in distributed systems: additional details
20
A.2.1
Broadcast channels
20
A.2.2
Multi-party random number generators
20
Network and compute overhead of BTARD-SGD
21
Overview attack vectors
22
D Detailed algorithm description
24
D.I BTARD and CenteredClip
24
D.2 Protocols for banning Byzantine peers
26
D.3
BTARD-SGD and detecting protocol violations
27
E Convergence analysis: missing proofs and extra details
29
E.1
Preliminaries..
................................
E.2
Impossibility of toleeant learning in heterogeneous case
................................
29
E.3
Convergence guarantees for BTARD-SGD
30
E.3.1
On Assumptions 3.1 and 3.2
30
E.3.2
Quality of the aggregation
31
E.3.3
Non-convex case
34
E.3.4
case: Restarted-BTARD-SGGI Convex case
37
E.3.5
Strongly
41
E.4
Convergence guarantees for BTARD-CCipped-SGGI
44
E.4.1
Quality of the aggregation
45
E.4.2
Convex
47
E.4.3
Strongly convex case: -aaauuedd--ADD-Ciiipppp
F Reputation system for public collaborations
57
Secure distributed hash tables
59
ALBERT experiment setup
59
T Additional experiments
60
L.
Extra evaluations the CIFARIO classification task Evaluating computation overhead terms wall time Experiments at larger scale Experiments with low-magnitude attacks
60
1.2
1.3
62
1.4
64
17

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL RELATED WORK
A.1 BYZANTINE-TOLERAA OPTIMIZATION: ADDITIONAL DETAILS
In this section, we provide extra details the related work discussed in Section 2.2. The summary of complexity results is presented in Table 2.
A.1.1 PARAMETER SERVER (PS) BASED APPROACHES
There is a quite large number of papers on Byzantine-tolerant optimization that aim robustify parallel SGD in the case when a trusted parameter-server (PS) is available. Since in the classical parallel SGD even one Byzantine worker can break the convergence of the whole method by shifting the mean of the resulting vector in an arbitrary way, it is natural to substitute averaging of the vectors received from the workers by more robust aggregation rule, e.g., Krum (Blanchard et al., 2017), coordinate-wise median, trimmed median (Yin et al., 2018), Multi-Krum (Damaskinos et al., 2019), Bulyan (El Mhamdi et al., 2018), geometric median (Pillutla et al., 2019). However, all these methods were shown to be brittle and not robust to special types of Byzantine attacks (Baruch et al., 2019; Xie et al., 2020; Karimireddy et al., 2020). Moreover, Karimireddy et al. (2020) show that all permutation-invatie meaning that simple application of some aggregation rules on top of SGD does not lead to Byzantine tolerance.
algorithms cannot converge to any predefined accuracy of the solution,
There are several approaches to circumvent this issue. Alistarh et al. (2018) propose BYZANTINESGI and prove the convergence results for convex problems. Allen-Zhu et al. (2021) extend this approach to handle non-convex problems as well. In both papers, the key idea is based on applying the concentration properties of the sums depending on the stochastic gradients as well as iterative removing of Byzantine peers. However, theoretical guarantees from Alistarh et al. (2018); Allen-Zhu et al. (2021) rely on the restrictive assumption that the noise in the stochastic gradients is uniformly bounded with probability 1. Bulusu et al. (2020) propose similar approach to the one from (Allen- Zhu et al., 2021) but analyze their method under more restrictive assumptions (boundedness of the gradient). Next, Wu et al. (2020) propose Syzantine-toleram version of parallel SAGA (Defazio et al., 2014), i.., variance-reduced version of SGD, with geometric median as an aggregation rule- BYRD-SAGA and prove its convergence for strongly convex objectives. However, the authors do not establish the convergence of BYRD-SAGA to any predefined accuracy of the solution. Moreover, variance-reducee methods are known to converge slowly in deep learning applications (Defazio & Bottou, 2019), which limits the practical utility of BYRD-SAGA Finally, Karimireddy et al. (2020) propose new aggregation rule called CENTEREDCLIP, apply it to SGD with client momentum, and prove convergence results for the obtained method in the non-convex case under reasonable assumptions. Alternative lines of work achieve Syzantine-toleran optimization through redundant computations (Chen et al., 2018; Rajput et al., 2019) or apputation-based approaches (Rodríguez- Barroso al., 2020; Regatti et al., 2020; Xu & Lyu, 2020). Unfortunately, these papers either do not contain theoretical (non-asymptotic) convergence results for the proposed methods or rely on too restrictive assumptions in the analysis. See more references in the recent survey by Lyu et al. (2020).
A.1.2 DECENTRALIZEI APPROACHES
Byzantine-tolerant optimization methods for decentralized communication architectures studied only in a couple of papers. Yang & Bajwa (2019a;b) consider a specific scenario when workers compute full gradients, local loss functions on peers are heterogeneous, and the trimmed coordinate- wise median is used as an aggregation rule. In this setup, the authors prove convergence results in the strongly convex case to some accuracy depending on the heterogeneity level of local loss functions, which is natural in the presence of Byzantine peers. However, these results are not applicable to a wide range of practically important problems where stochastic gradients have to be used. This issue was partially resolved in Peng et al. (2021), where the authors propose version of GOSSIP SGD applied to the equivalent reformulation of the original problem based on TV-regularization (Ben-Ameur et al., 2013). However, the established convergence results in the strongly convex case do not show any benefits of using communications with other workers in the homogeneous data regime that appears in large-batcl batch training of deep learning models. Li et al. (2019) use the same idea for parameter- sereeerer--eeerreeeeee architecture. Next, there are approaches requiring peer-to-peer communications of full vectors at each step (Gupta al., 2021; Gupta & Vaidya, 2021), which is not scalable.
18

---

Under review as a conference paper at ICLR 2022
Table 2: Summary the complexity results for Snrameter-Server (PS) based and distributed Byzantine- tolerant optimization. By default, columns "Non-convex", "Convex", and "Strongly convex" contain the complexity bounds for L-smooth non-convex, convex, and p-strongly convex problems respectively. By complexity we mean the number of iterations sufficient to find such point 3º that F[[[V[ S E² for non-convex problems and (3) f(x') }] S & for convex and p-stroonly convex problems (see Def. F.2) with x² heing the solution. For simplicity we omit numerical factors, logarithmic terms depending on the parameters of the problem, and factors, quantifying suboptimality of the starting point, i.e., Ro || x=I| and ((=") inf / ((). Notation: 8 = 18//n, m number of peers checked at each iteration. The results from (Yang & Bajwa, 2019a;b) not included in the table since they rely full-gradient computations.
Non-PS?
Work
Non-convex
Convex
Strongly convex
(Alistarh et al., 2018 (M)))
8²
8-
nC?
MC
(Allen-Zhu et al., 2021)
6
x
X
27
(Wu et al., 2020)()
x
2
(Karimireddy et al., 2020)
x
x
6
(Peng et al., 2021) ((077)
X
X
+
no
A NN
This work
22
nág?
2
///0
d2
nydo
ORE
This work
22
+
ne?
me?
nzz
o
+
1
o2
MyREE
n 5g
This work (0)
GA
a-r
GºA
JEE
This work (1))
GA2
G
ps
Vf((x)] S a for all x and Ç. ()) The results are proven under uniformly bounded noise assumption: f
Highh-robability guarantees are established, i.e., it proven that with probability at least - 3 algorithms from
(Alistarh et al., 2018) find & such that (() - f(x²) I and algorithms from (Allen-Zhu et al., 2021) find f such that | [+)l] S e.
(2) Dependencies on 8 are logarithmic and, therefore, omitted. Optimization problems is assumed to be define on bounded set, the rates depends on the diameter of this set. The results are derived for the case
1. Allen et al. (2021) also derive convergence guarantees for finding second-order stationary points.
Wu et al. (2020) consider finite-sum case of (3), i.c., f(z) Σn= f(z, j). The results derived under uniformly bounded variance assumption: E, [I] f - f(x) ['] s o² for all a E R where j is sampled uniformly at random from {I.....N) ... Wu et al. (2020) also derive convergence guarantees under (-bounded
dissimilarity assumption, i.e., when [x) = [s] Eieo f((), f.(x) n En f( for all i G, and
[ Eieg [[V](()) - I <²
(5) This result is obtained the main result of (Wu et al., 2020) and states that the method from (Wu et al., 2020)
finds á such that f()) - f(x") ) S only for 2 < ////(t -1)?, which can be large.
(6 The result is derived under uniformly bounded variance assumption, i.c., Eg-D | fzx () f(()) < o²
for all w E Rd
@ Peng et al. (2021) consider the case. when peers are allowed to communicate with their neighbors that are defined via some communication graph. The result establishes the total number of iicaations/commuiicatinn
1| < E for e 2 Aid Eigg [B, where À 2 0 is any non-negative number and B, is the set of Byzantine peers neighboring with the i-th peer. In the complexity result, we use the notation 22 = ( + |B, 1), where G, is the set good neighbors of the i-th peer. When À = O, the workers do not communicate at all. Moreover, Peng et al. (2021) analyze the case of heterogencous local functions, composite optimization problems and time-varying setup but in that case À is lower bounded by strictly positive quantity depending on the heterogeneity level and minimal non-zero singular value of the node-edge incidence matrix, i.e., any predefined accuracy cannot be achieved.
rounds needed to find å such that BlI@
(8) The results are derived for B STARD-SE SSD (in the strongly convex case, for RESTARTED B BTARD-SGIE under Assumptions 3.1 and 3.2 in the case when the exact number of attacking Byzantine workers at iteration & is known to each participant. See Theorems E.2, E.4, and E.6.
The results are derived for BTA SDDDD (in the strongly convex case, for RESTARTED- B TARD-SGD) under Assumptions 3.1 and 3.2. See Theorems F.3, F.5, and F.7.
(10) The results are derived for CLIPPED-SGD) under Assumption E. without any additional assumptions on the tails of the distribution. Moreover, it is assumed that the exact number of attacking Byzantine workers at iteration l: is known each participant. See Theorems E.8 and E. In the complexity results, we the notation A: = 1+ " (1)) The results are derived for CLIPPED-SGD under Assumption E. without any additional assumptions the tails of the distribution. See
(in the strongly convex case, for RESTARTED-BTASE
(in the strongly convex case, for RESTARTED-BTARD
Theorems E.9 and E. In the complexity results, we the notation A2 1 n²8
19

---

Under review as a conference paper at ICLR 2022
Finally, El-Mhamdi et al. (2020) propose an algorithm based on the usage of multiple servers. The authors assume that both workers and servers can be Byzantines, which is realistic scenario. However, their approach requires the workers to send their gradients to all servers at each iteration and receive parameters from all servers as well. This leads to a significant communication overhead in practice. Moreover, El-Mhamdi et al. (2020) do not provide non-asymptotic convergence rates, making it problematic to provide an in-depth comparison with existing works and with our results as well. Therefore, it unclear whether the usage of multiple servers speeds up training or it just leads to overhead in the communications and computations.
In contrast, our results do benefit from the communications between workers. First of all, as one can see from Table 2, the terms depending on the fraction ó of Byzantine peers in our complexity bounds for BTARD-SGD and RESTARTED- BTAR
(the third terms) have better dependence on the target accuracy& e than the corresponding terms in the complexity bounds from all previous works (even from those relying on the existence of a PS). Moreover, for sufficiently small & these terms in our complexity results are smaller than the second terms, which correspond to the main term in the complexity of parallel SGD. That is, BTARD-SGD/RESTARPTI problem with Byzantine peers has convergence guarantees that are not worse than the corresponding guarantees for parallel SGD applied to the problem without any Byzantine workers. In such regimes, our theoretical convergence results outperform even ones derived for PS-based algorithms.
BTARD-SGD applied to the
We notice that Assumptions 3.1 and 3.2 used in the analysis of STARD-SGIDREESARTTESS SGD) are slightly stronger than uniformly bounded variance assumption used in (Wu et al., 2020; Karimireddy et al., 2020; Peng et al., 2021). However, as we explain in Appendix E. our analysis allows to relax Assumptions 3.1 to uniformly bounded variance assumption, and Assumption 3.2 is reasonable for many practically important problems. Finally, we also propose and analyze BTARD- CLIPPED- SGD and RESTARTED- BAARRTE--BARRR STARD-CLIPPED
T-
under Assumption E. that may hold even in the case of unbounded variance of the stochastic gradient. To the best of our knowledge, this the first time in the literature on the Byzantine-tolerant optimization when the complexity results are obtained without assuming boundedness of the stochastic gradient's 's variance.
A.2 SECURITY IN DISTRIBUTED SYSTEMS: ADDITIONAL. DETAILS
In this section, we provide extra details on the related work discussed in Section 2.3.
A.2.1 BROADCAST CHANNELS
Many distributed systems rely exclusively on direct peer-to-peer connections, avoiding any centralized servers to increase reliability and avoid the performance bottleneck. In presence of malicious participants, this introduces additional security challenges since an attacker can send corrupted data to one participant and behave honestly with others. a peer accuses another peer in sending corrupted data, it is impossible for remaining peers to determine whether the accusation is fair since only these two peers had access to the contents of the communication channel between them.
To overcome this, distributed systems can build secure broadcast channels over the peer-to-pen connections using the protocols for Byzantine broadcast. These protocols guarantee that a peer p sends a message, (a) all honest peers receive the same message and (b) the received message coincides with the original one if p is honest.
Pease et al. (1980) suggest such protocol for the case when the share of malicious peers ó < 1/3, and Dolev & Strong (1983) suggest a protocol tolerating any < 1 assuming the presence of a public key infrastructure and usage of the digital signatures (Rivest et al., 1978; Goldwasser et al., 1988).
Hirt & Raykov (2014) review how the communication complexity of various Byzantine broadcast protocols depends on the maximal tolerated 8 and the length of the broadcasted message. Abraham et al. (2019) 9) review protocols with additional practical assumptions improving the communication complexity.
A.2.2 MULTI-PARTY RANDOM NUMBER GENERATORS
Many distributed systems may benefit from the multi random number generators (MPRNG) where group of malicious peers would have little influence (bias) the generator output. MPRNGs
20

---

Under review as a conference paper at ICLR 2022
Legend
PARE PAREE
Peers
h,
Local command
Broadcast protocol
Verily
maddi
A, Ait
Figure 4: An intuitive scheme of MPRNG based on the generalization of Blum (1983). Here, denotes concatenation, denotes bitwise XOR, h(x) is common cryptographic hash function. The hashed values include the peer identifier i to protect from replay attacks and large random string 8; resist dictionary attacks.
are usually based on multi-party coin tossing protocols, such as the protocol from Blum (1983). As an example, MPRNG allows to choose participant winning lottery or choose a peer whose calculations are going to be validated by other peers to detect possible cheating.
While Blum (1983) formally introduces protocol for bit and two parties, its generalization to multiple bits and parties (as necessary for MPRNG) is trivial assuming the presence of the broadcast channel. This modification is widely known in literature, e.g., described in Zhang et al. (2019). According to this generalization, peers should execute the following protocol to obtain & random bits (see the intuitive scheme in Figure 4):
1. Each peer generates its random string 2; made of k bits.
2. Each peer broadcasts commitment h; common cryptographic hash function, i the peer's unique identifier (known by other peers), and
where || denotes concatenation, h(x)) is
8; is large random string.
3. Peers wait until all of them finish broadcasting the commitments. After that, no peer can alter its Tę influence the protocol output (otherwise, peers would notice that the new value 2 does match the commitment).
Each peer reveals their random string by broadcasting its æ; and 84-
Each peer verifies that all other peers revealed values xy and 8j that match their commitments h, h ||,)).
6. If a peer detects that peer aborted the procedure or its commitment does not match its revealed values, it concludes that we cannot trust peer j. Since other peers read the same broadcast channel,
all of them can make the same conclusion. In this case, the system repeats the protocol.
peers do not detect any mismatches, they calculate the protocol output x = 21 @ @ on. where denotes the bitwise XOR operation.
In this protocol, the commitments include the peer identifier to protect from replay attacks (when an attacker repeats someone else's message) and the large random string 8; resist dictionary attacks (when attacker reverses the hash function using large dictionary of its values).
While there are MPRNGs (Rabin Ben-Or, 1989) with a negligible bias for the case when more than half parties are honest (assuming the presence of the broadcast channel), Cleve (1986) proves that it is impossible to reach the negligible bias for the case dishonest majority, which may be reached in practice with the Sybil attacks.
However, we note that the bias in Blum (1983) (and its modification above) appears only in the case when attacker learns the result earlier than other peers and forces the protocol be repeated. If we are using MPRNG to choose peer that to be checked for cheating, we may ban all peers that aborted the procedure and restart from scratch without them, therefore eliminating the bias problem.
B NETWORK AND COMPUTE OVERHEAD OF BTARD-SGD
Communication overhead. Despite having complex structure, BTARD-SCE SGD has only limited communication overhead, when compared to regular All-Reduce SGD. A single step B BTARD requires each peer to send each gradient tensor exactly for aggregation, then download the
21

---

Under review as a conference paper at ICLR 2022
results, exactly in Butterfly All-Reduce. On top of that, peers are only required to broadcast (n) scalars that are independent of the total size of the trained model. This includes the communication cost for MPRNG: as shown in Figure 4, one round of the MPRNG based on the generalization of Blum (1983) requires each peer to only broadcast 3 scalars.
Hirt & Raykov (2014) discuss that simple modification of the protocol from Dolev & Strong (1983)
leads to the communication complexity of O( + II²²) bits for each peer in the worst case, where / the length of the broadcasted message. For the (n) scalars, this gives O(n²) communication.
As a result, the communication complexity of a single BTARD-SGD step for each peer is O(d + n²) bits. We note that for models that benefit from distributed training, the n component is usually dominated by the vector size d, as they usually contain at least tens of millions of trainable parameters.
Still, necessary, the n² component may be improved using the Byzantine broadcast protocols with additional practical assumptions, such as allowing small probability of error. Abraham et al. (2019) review such protocols, their assumptions, and communication complexity.
We do not restrict the way of getting the data (whether the samples are downloaded on each step, the whole dataset is distributed before the training, or the data is generated on the fly) and do not consider it part of our algorithm, leaving the related communication cost out of scope of this analysis.
Synchronization points. Another important aspect of BTARD performance is synchronization. The naive implementation of Algorithm would have many global synchronization "barriers" per step: one for aggregating gradients, another for choosing a random direction 2, yet another for electing validators, etc. These frequent synchronizations could undermine the practical training performance of BTARD in high-latency networks, such as when training over the Internet.
Fortunately, it possible to reduce the number of synchronizations by bundling them together. For instance, peers use a single MPRNG round for sampling and for electing validators. Furthermore, this MPRNG round and subsequent checks can be done in background, while a peer accumulates gradients for the next step. The only restriction is that this "shared" MPRNG round must be performed after all peers declare their checksums for that round.
With these optimizations, BTARD-SGD requires only two points of synchronization per round. The first one occurs right before gradient aggregation, and the second one is in a background task that performs verifications. Finally, there is non-regular need for synchronization when one peer accuses another of being Byzantine. However, as we elaborated earlier, each accusation will result in at least one Byzantine being banned. Therefore, this additional cost will occur only limited number of times over the training run.
Computation overhead. In terms of computation, BTARD-SGD introduces two main overheads: from validators and CENTEREDCLIP respectively. As we have shown empirically, both BTARD- SGD and STARD-CLIPED-SGD can withstand attacks even with random validator chosen from 16 peers. As such, the computation overhead for these validators is under 10% of the total compute.
As for the CENTEREDCLIPP, our algorithm executes the same amount of computation as the original CANTEREDCLLIP (Karimireddy et al., 2020), except that now the extra load is distributed evenly across all peers. We provide an empirical evaluation of such overhead in Appendix I.2.
Finally, we note that generating shared vector = from a scalar seed nd (as defined in Algorithm 1) has a negligible cost and can be done with any standard pseudo-random number generator. For instance, generating for ALBERT-large (the setup from Section 4.2) takes 30 + 1.2 ms on the same T4 GPU that we use in our experiments.
C OVERVIEW OF ATTACK VECTORS
In Section 3.2, we have outlined the main types of Byzantine attacks that can affect BTARD-SGD. Here, we analyze each of these types in detail and provide list of attacks that fit these types.
Gradient attacks. This attack vector encompasses all attacks where Byzantine peers replace their true gradients with something else, but otherwise act normally. With this attack, b Byzantine peers can collectively shift the outputs of CENTEREDCL.P by up to 7 bbnn in any chosen direction. However,
22

---

Under review as a conference paper at ICLR 2022
since Byzantine peers will need to commit hash of their incorrect gradients, every honest validator can accuse one of these peers with probability b/n.
Aggregation attacks. A similar, but opposite attack type can be attempted when a Byzantine peer performs gradient aggregation. Instead of honestly computing CENTEREDCLIP, an attacker may modify the returned vector to incorporate the same kinds of changes as in gradient attacks (see above). This time, the maximum difference that can be applied through such attacks larger, but it only affects b/n of vector coordinates that are aggregated by Byzantines.
Done naively, such attacks can be detected and banned by the gradient checksum (see L15-17 in Algorithm 1). In order to ensure that the above check passes, Byzantines can misreport their of in such a way that E; =0= However, since actual sy depend only on of and gf, these values can be verified by the chosen validators, and, in case of mismatch, reported via ACCUSE. We rigorously prove this in Appendix D.3.
Furthermore, if an honest validator finds that a certain peer has broadcast incorrect sy the validator can simultaneously accuse the corresponding Byzantine aggregator that should have notified about the incorrect s? (see L12-14 in Algorithm 1).
Reputation abuse. Since BTARD-SGD provides means by which benign participants can ban Byzantine attackers, it is important ensure that the same means cannot be exploited by Byzantine peers to eliminate benign ones or otherwise abuse the system. There are three potential attack vectors that fit this description:
Falsely accusing a benign peer,
Persistently calling the ACCUSE procedure to slow down training,
Automatically approving gradients without actual validation,
In BTARD-SCH SGD, we protect against slander (issues 1. and 2.) by the design of ACCUSE protocol, by which a peer that initiates false allegations will itself be banned. As such, Byzantines can only invoke ACCUSE protocol a limited number of times before they are all permanently banned.
In turn, the attack vector (3.) is more effective: if one Byzantine was chosen as validator for another Byzantine, they can automatically report successful validation without negative consequences for either of them. However, since all validators are chosen through MPRNG, an attacker has no way of predicting whether its validator will be benign or Byzantine. Thus, any malicious activity will always have a chance of being caught by an honest validator.
Protocol violations. Finally, a Byzantine attacker can deviate from the protocol prescribed by BTARD-SGD in simpler ways ways, for instance:
1. Not committing the hash of its gradient when required by 4,
Not sending data to a particular peer when required (or sending data twice),
3. Deliberately broadcasting hash that mismatches the subsequently sent data,
4. Sending metadata (e.g. gradient norm) that is inconsistent with previously sent gradient part,
5. Sending s; that is inconsistent with previously sent gradient,
6. Not validating when chosen validator, validating when not chosen, validating different peer than was chosen by B BTARD-SGD.
For protocol deviations that are visible to all benign participants, such as in (1.) or (6.), benign peers can ban the offender instantancously. However, this is not the case for attacks such as (2.), where the deviation is only visible to one or few peers.
As described earlier in Section 3.2, we address this issue with a special procedure that allows any peer to ban any other peer the cost of also being banned. Thus, if an attacker sends inconsistent gradients, norms or inner products to only one benign peer, that peer can still get the attacker banned even though it wouldn't 't be able to call ACCUSE.
Protecting from attacks 3, and 5 from the above list also relies on this mutual climination procedure. Specifically, if an attacker sends provably incorrect data to benign peer, that peer will immediately
23

---

Under review as a conference paper at ICLR 2022
trigger the mutual elimination procedure. The only exception to this rule is if one Byzantine peer sends incorrect data to another Byzantine peer: this behavior is neither punishable nor, in itself, harmful. In turn, the mutuality of this elimination procedure prevents potential misuse by Byzantines: an attacker decides to ban someone through this procedure, that attacker will also be banned.
D DETAILED ALGORITHM DESCRIPTION
In this section, we provide more formal versions of the BTARD (Alg. 4) and BTARD-SGI SGD (Alg. 6) algorithms, well auxiliary subroutines and further details. For completeness, describe approach in bottom-up manner. First, in Appendix D.I, we describe Algorithm and one of its main building block called CENTEREDCLIP (Karimireddy et al., 2020). Then, formulate the ACCUSE and ELIMINATE subroutines for blocking malicious peers in Algorithm and comment on them in Appendix D.2. Finally, we formulate the full BTARD-SGD in Algorithm 6 using the above subroutines as building blocks and rigorously analyze its robustness to the violations of its steps by Byzantine peers in Appendix D.3.
D.1 BTARD AND CENTEREDCLIP
We begin with glossary of basic functions used in the algorithms:
CHECKCOMPUTATIONNS() or VALIDATEPEER - run COMPUTEGRADIENTS (Z',, ,') and com- pare against the cj hi broadcasted by that peer. If there is mismatch, ACCUSE.
send message declaring intent to ban peer j over the broadcast channel (the message signed with the sender's private key).
VoTEFoRBAN
(pMVorss(peer.) count the number of messages declaring the intent to ban peer and received via the broadcast channel.
BAN(peer,). add peer j to local blocklist, ignore any subsequent messages from that peer, and continue training without it.
SPLIT(U, n) split vector of size d into parts. The first df mod parts are of size [d/n] and the remaining parts have size [d/n].
MERGE( v,) concatenate vectors U U, into one.
Algorithm 4 defines single gradient aggregation step (outlined earlier in Alg. 2) with additional verifications needed to reduce the negative influence of Byzantine peers. For simplicity, we assume that workers run each line in a synchronous manner (e.g. wait for all peers to broadcast hash(g;) before communicating the actual gradients). In practice, this restriction can be lifted favor of asynchronous steps with several explicit synchronization barriers, but that would further complicate the pseudo-code.
One of the key building blocks of BTARD is CENTEREDCLIP robust aggregation nule proposed in (Karimireddy et al., 2020). Unlike a number of other aggregation rules as coordinate-wist median, Krum, geometric median, CENTEREDCLIP is provably robust against Byzantine attacks (see Theorem III from (Karimireddy et al., 2020) and Lemma E.I).
Let be the of good peers, B be the set of Byzantine workers, and, for simplicity, let [n] G B. [ = ön & dgn n/2. Assume that we have random vectors 21, .1,...: such that Vi,j E G
E[c.] E[ry] = x, E[ix; - 2, 11 0².
and for all B vectors x; can be arbitrary. CENTEREDCLIP works follows: it is an iterative procedure generating a sequence { h2o satisfying
rl+1 = v
1
a vt) min
1,
π
(CenteredClip)
| w'
where
(1 5) (B2/3 + 02)
7 4
B 6.458B + +52
(6)
/88
24

---

Under review as a conference paper at ICLR 2022
Algorithm 4 Byzantine- Tolleaan All- All-Reduue (BTARD)
Input: number workers n, gradient vectors on the workers gl, 92. ... IR., n, Amax
parameter for verification 3
1: for workers = ....., n in parallel do
2: Split 9i into parts: 9,
. E R2 for all i,j e [n]
3:
4: broadcast c; hash(g:)
5: for j= ...., n do broadcast (i) hash(g:(1)
6:
7:
8: Aggregate gradients (same Alg. 2):
9: Send 9:(5) to peer j for all j 7 and receive (1) from peer for all j +
for ..... do (1)) & Cy(i) then ELIMINATE((..) Signed with peer, private key
11:
13: ((t) = CENTEREDCLIP(gI) (i).
broadcast c(i) (t))
15:
Send 7(t) to each worker and receive 7(j) for all j * i from other workers
for j ......
..... n do if hash( * (()) then Signed with peer, private key
17:
ELIMINATE(i.))
19:
9 ()..
21:
Send metadata for verification:
22:
Generate r via MPRNN NG GETRANDOM VECTOR for j E I..., n do
23:
24:
(g:(()()) m(1) min {1, "1.00) sc0lla
25:
26:
broadcast of = (=[i), A
27:
broadcast norm, = (1) F(1)l12
28:
for 1 1....,7 72 do
29:
wi min
narms
30:
31:
for 1,................. n
32:
Verification 1:
33:
if normy * AcCUSE(i, normjs does not mach (i)
- (i))( then
34:
35:
Verification
36:
I/ peer i knows Ai from CenteredClip
37:
if 83 * (z* then
38:
ACCUSE(i sf does not match (i))
39:
E of #0 then
40:
// peer, already verified that all s! are correct AcCusÉ(i. j. ς()) wrong)
42:
Verification 3:
43:
broadcast checkiz = [1l9:()) 70)ll2 Amax]
44:
if Σ, checklj > 2 then
return 9 CHECKAVERAGING(()
46:
Intuitively, CENTEREDCLIP behaves like the mean for all points within the sphere of radius and like the median for "outliers". In turn, choosing different values of 7 allows one to smoothly interpolate between the mean (7 inf) and the geometric median aggregation rules.
25

---

Under review as a conference paper at ICLR 2022
The goal of this procedure is natural: find good enough approximation E of [ Eieg Ty- In (Karimireddy et al., 2020), is shown' that for - 0.1 the sequence {2r generated by CENTEREDCLIP satisfies
E o ক b| (9.70)
b| + 40005a
Moreover, Karimireddy al. (2020) prove that for all possible aggregation rules producing I and given do, there exists such set of vectors Tt Fn and such a partition [>i] = 9 LJ B that
E| =| 92(6o²).
Therefore, CENTEREDCLIP can be seen an optimal aggregation rule neglecting numerical constants. The usage CENTEREDCLIP helps the good peer to produce a good enough approximation the ideal average of the i-th parts of stochastic gradients among good peers in BTARD.
Moreover, since S 0.1 we have that 6.458 S 0.645 implying that Bi + B o² when - oc, and T. > 7 ~ V These limits can be easily computed from (6). Next, for I - co CenteredClip converges to the solution of the following equation:
Σ (z.
min
el 0.
1,,
In other words, CenteredClip for large enough I approximates the fixed point iteration process of solving (8). This property plays a key role in Verification 2 of BTARD.
Algorithm 5 ACCUSE ji allegation), detailed version
Input: accuser i, target j. peer count n, all values exchanged in Algorithm 4
1: Recalculate of COMPUTEGRADDEETS(( E.)
2: Split 9: into n parts: 9i (9:(1) ................................ ........ (n) T)T 9:(5) E Rd for all i.j [n]
3:
4: for 1111-..... do
5:
if hashh(g)) # of or bash (1)) # h² then
6:
VOTEFORBAN(Peer.) // For gradient attack
7:
- - T(1) min {1, TTG))
8:
if (1g,(() - m())l2 # norm,r or (Ai 2n) + of or Σ of + then VOTTFORBAN(Peer.) // For aggregation attack for o = 1,...,
9:
10:
12:
if peer approved normjo o sy then VOTEFORBAN(peer) // For covering up the j-th peer's aggregation attack
13:
15:
for 1 -1 1.....ne do if NUNoorrssppee)) 2 n/2 then
16:
17:
BaN(peer,)
D.2 PROTOCOLS FOR BANNING BYZANTINE PEERS
ACCUSE and ELIMINATE are the two protocols by which peers ban Byzantine attackers from training. The ACCUSE protocol is only invoked if there the malicious activity of the target peer be proven to others (we detail the exact mechanism Algorithm 3). In contrast, ELIMINATE a mechanism that allows any peer to ban any other peer j from training without proof but at the cost of peer also being banned. We have described this protocol carlier as countermeasure for protocol violations (see Appendix C).
'In fact, Karimireddy et al. (2020) derive this result for two-staged version of CENTEREDCLIP One can derive similar result for the original CENTEREDCI.I under the assumption that for all i, E we have El| 2 a.
26

---

Under review as a conference paper at ICLR 2022
Both ACCuSE(i,)) and ELIMINATH(i,.) imply that peer uses the broadcast channel to declare its intent to ban peer j. All peers collect such messages during a training step and process them at the end of the step in some specific order (e.g. sorted by (type, public key,, publii key,), where type E (ACCUSE, ELIMINATE) and ACCUSE ELIMINATE). If processing one of the messages results in banning peer further messages involving p are ignored regardless of the p role, This way, it is impossible for Byzantine to eliminate more than one honest peer along with itself. Peers reach consensus since their decisions on banning someone are based solely on the messages from the broadcast channel (sorted in the common order) and the calculations with identical results.
D.3 BTARD-SGD AND DETECTING PROTOCOL VIOLATIONS
Finally, the Algorithm 6 incorporates the two above procedures into a secure decentralized SGD training loop. This algorithm is intended as a more formal version of Alg. I from Section 3.1.
Algorithm 6 -TARD--SD
Input: x - starting point, 7 stepsize, K number of iterations, {8t,k) 1,k000
K= seeds for batches
computations
Co Banned
2: for k = 0, 1,..,.,,K K 1 do
Vs(a EE,))
if E GN \ Ck.
3: Worker computes oft
where & is generated via seed if i E BR \ Ca.""
8i.6 available to every worker
4:
(T*: public_info,) = BTTADD (A 0
Li ). where (
t = (Gx U Bx) C2
5:
BTARD described in Algorithm 4
6: Choose 2m workers of A++1
k+1 k+1
k+1 uniformly at random without replace-
ment, C++1 = {c/+t1 ..... Cm L.+1), ). Uk+1 = {ut
u 1
7:
Banned, CHECKCOMPUTATIONS/(( , public info,)
8:
+t projo (x -ng²) argmin | (x -
9:
Gx+1 Gk Bannede-1
10:
B&+1 = Bx Banned;-1
Verifications and While good peers always run CENTEREDCLIP. Byzantine peers can arbitrary violate the protocol meaning that they can send arbitrary vector instead of sending the result of CENTEREDCLIP. Verification and are needed to prevent such violations and make it possible to identify them during the check of computations.
First of all, both verifications are split into rounds in order to let the aggregators of the corresponding part accuse those peers who send inconsistent norms inner products. Next, in theory, we assume that all good peers find exactly the solution of CENTEREDCLIP equaition (8). Therefore, is possible compute the weights from (8) for each worker and each component j knowing only norm of the difference of corresponding vectors, i.e., one can compute min(1, [] ()-)) by (l d()]]-
T
That is, if Byzantine peer i sends norm; * (j) I())l it will be either revealed by j-th worker if j E G or it will be revealed with some probability during the subsequent checks of computations.
However, Verification 1 is insufficient prevent malicious behavior: iteration i Byzantine peer can send (j) such that (i))()) - 7th (i)ll = V (V (a* Ei,,) - g [-ll if E B, then it can be the case that i-th worker commits the hash of V fa* Ev.,) not identify the violation of the protocol. That why, Verification 2 is required.
and the check of gradient computation will
is function that generates random unit vector in the space of model parameters. This vector is based on random seed r obtained from MPRNG.
The goal of Verification 2, is to check that CENTEREDCLIP equation (8) holds for the received vector. The idea is simple:
Σ (1)(1) 7(1) min {1,
[lor(1) g()) } 0,
(9)
27

---

Under review as a conference paper at ICLR 2022
then for any 2, of an appropriate dimension
E (a(()) g(1), min
0.
(10)
Since 2; in BTARD is generated from the uniform distribution on the unit Euclidean sphere, we have
P {(9) does not hold & (10) holds} = 0.
(11)
However, it is impossible to verify (10) explicitly for workers # i. Therefore, in the algorithm, good workers check
ot 0, where of (g)(1) ②(1), 22) min {I, (o BOT ( Σ
}. if G, if B.
(12)
Unfortunately, Byzantine peers can send arbitrary st. This can lead to the situations when (12) holds while (10) and, as a consequence, (9) do not. Below, we rigorously show that all possible violations of the protocol that are not detected by verifications of BTARD be detected by the auxiliary check of computations with some probability.
This is additional verification that serves limit the potential scope of aggrega- tion attacks (as described in Appendix C). If the result of CenteredClip landed far from too many benign participants, BTARD will verify it by re-running the same aggregation across all peers. While this procedure is costly, our analysis proves that it is has a very small probability of triggering unless some of the peers perform aggregation attacks. In the latter case, verifying the gradient accumulation will root out such attacks and ban the corresponding peers.
Verification 3.
Check of computations. As we mentioned earlier, is possible violate the protocol without being detected by the verifications of BTARD. Therefore, extra checks of computations are required. In particular, after each aggregation in BTARD- -EDDD-SDD& 2m workers are selected uniformly at random: m workers check the computations at the previous step of other m workers. That is, each Byzantine peer checked iteration with probability ~ m/n by some good worker (see the proof of Thm. E.2). Consider an arbitrary Byzantine peer j and all possible violations of the protocol at iteration 1: that are not detected by verifications of BTARD.
First of all, we notice that if (i) * (ash(V(s) fx ,5,,))) then it will be detected during the check of computations with some probability". Moreover, if i G. then j-th worker has to send (i) = (g (f)) to avoid ban.
Therefore, the only non-trivial case is when i B well. In this case, j-th worker can mit (1) = hash( V fxr Efxx) since is meaningless for i-th worker to accuse j-th one. Since normij, sf and î(t) are known for all and j. j-th worker has to broadcast no normi (1) kai) (t)]l and 8) = (f {ax) g(1), 2.) min {1,
(e -(0] to
avoid the ban during the check of the computations. Therefore, regardless to the choice gj (i), to pass Verification 2 i-th worker should send such ((1) that
Σ (a) E..,) 0(1), 2x) min LEGU())
T (of E1,)) 2(1
+
Σ
8 0.
(EB
In this case, the behavior of the j-th worker along i-th component is equivalent to the behavior of the good one. It means, that to avoid ban during the check of computations, each Byzan- tine worker should broadcast normy () (i,s) {()] and s (V ( EL,))
g(),, 2.) min {I, (ee)) implying that i-th worker should send such (i) that
(V (.,) - -()) 2.) min 1,
(ot (..) 7(01 O.
T
1=1
In view of (11), it implies that
(1) = CENTEREDCLIP(V (x* S1,)), f E..)...., (o (2,k))))),)),
i.., there are violations of the protocol along the i-th component.
6 Here and below, this means that the attack/violation will he detected iff non- non-Byzantine peer is chosen to validate the perpetrator.
28

---

Under review as a conference paper at ICLR 2022
E CONVERGENCE ANALYSIS: MISSING PROOFS AND EXTRA DETAILS
E.
PRELIMINARIES
For convenience, we provide the classical definitions and facts on smooth and strongly convex functions below.
Definition E.1 (I-smoothness). We say that function differentiable and
R. Q S Rd is L-smooth if it is
Vr, E Q
-V L|I yll-
(13)
One can show (Nesterov, 2003) that L-smoothness implies
L - |yy x||
Vx f(v) f(x) (V/(z), +
(14)
V [Vf(z)]I (f(z) - fa):
(15)
where f. is uniform lower bound for f- Definition E.2 (u-strong convexity). f f IR Q S Rdd is called p-strongly convex if
Vx, E Q f()) f(x) + (Vf(x), x) lly x/
(16)
E.2
IMPOSSIBILITY OF BYZANTINE LEARNING IN HETEROGENEOL'S CASE
Several papers Byzantine-toleran optimization consider non-homogeneous setup, when good workers have different local functions (Wu et al., 2020; He et al., 2020). Formally, it means that instead of solving
min (f(x) == BE-D [f(,,
(17)
REQURd
where good peers sample stochastic gradients from the full dataset (i.e., they can sample from D), the following problem is considered:
[(x) = Σ fl(x)
min EEQRR
(18)
iEg
where f((z) EE (f(x,,)) and there exists Ç 2 such that for all x E Q
1
[Vf(z)) {f
(19)
icg
However, under (-bounded heterogeneity assumption (19) is impossible general solve (18) with any predefined accuracy in the presence of Byzantine peers (He et al., 2020). Moreover, this is true even when trusted Parameter-Server available.
Theorem E.1 (Theorem from (He al., 2020)). For any optimization method Alg there exist functions fi (x),...., fn(x) such that at least (1 5'yn of them are good (corresponding workers belong to G), 1-smooth, j-strongly convex and satisfy (19) such that the output & of Alg given the access to these functions has error at least
OC2 1
E [(G)
min (xx) ZER
2 S
and
E [ 2 (B(3),
(20)
where the expectation is taken w.r.t. the randomness of Alg.
The intuition behind this negative result is following: since the only assumption on the similarity of "good" functions is (19). Byzantine peers can shift the gradients by a vector with norm ~ without being detected. In this case, it is impossible to distinguish good peers from Byzantines but the solution of (18) depends on which workers are good and which are bad. Therefore, the best one can hope for is the convergence
neighhorhood of the solution.
29

---

Under review as a conference paper at ICLR 2022
The lower bounds from (20) are proportional to óç² and cannot be made arbitrary small for given and ç² It means that the convergence to any predefined accuracy of the solution is impossible to achieve when local loss functions g-heterogeneous. In this sense, Byzantine-tolerant learning is impossible in the heterogeneous case. Moreover, in some practical applications (e.g., in Federated Learning (McMahan al., 2017)); ( from (19) can be large implying that one cannot achieve reasonable accuracy of the solution when å is not too small (e.g., 6 2 0.01). Finally, strong convexity parameter μs typically much smaller than (assuming that the smoothness parameter is 1). In these cases, 6c²/a can be too large and, as result, all methods are not converging at all.
E.3 CONVERGENCE GUARANTEES FOR BTARD-SGD
E.3.1 ON ASSUMPTIONS 3.1 AND 3.2
First of all, Assumption 3.1 holds whenever standard uniformly bounded variance (UBV) assumption is satisfied. Indeed, if R V / (s. 5) (z)) - x2, then (V
6²
for all i = 1,.... d, since VV - ff(=)) - that Assumption 3.1 holds with o² S dō². However, x² can be significantly smaller than do?. For example, if the noise in stochastic gradients is isotropic, e.g., Gaussian, then
(V.(z))) This implies
V=f(z))) = ... (Vaf(())( vaf(x))
implying that
Eg (V.f( v.f(=)) - http:///0g/////////////////////0
-
d
for all 1......dd d. Therefore, in this case, Asssumption 3.1 holds with x² 02.
Next, it is possible to relax Assumption 3.1 to the classical UBV assumption. Indeed, in our proofs, we use Assumption 3.1 to bound the variance in the blocks of the stochastic gradients, where the blocks of components are chosen for workers to execute B BTARD. If these blocks are chosen uniformly at random, i.e., the vector is split into several parts of the given sizes uniformly at random, then is enough to have
so² d
E [I V (x) V(s) S
(21)
for a random subset S of {I...., d} such that [S] = 8, where expectation is taken w.r.t. & and S. To derive inequality (21) from UBV assumption Bę - 2² we use tower property of the expectation:
- E [[s E) [+s][( = EE-D Es - [Is]((>)]1]]
Eş
PfiE (V.f((z) vef(z)))
BEWD
(V.f(x, 5 v.f(a))²
d
sō2
= BeWD [[] [+ <
d
i... (21) holds for o² g2.
Finally, as we show in Lemmas E.2 and E.4, under As. 3.2 Verification 3 at BTARD leads to extra checking of computations with probability 1/n at each iteration when all workers honestly follow the protocol and under a proper choice of Amax. Therefore, extra computations either appear due to malicious manipulations of Byzantine peers, and lead eventually to the ban for the Byzantine peers who deviate from the protocol, or, when all workers honestly follow the protocol, only once per n iterations on average. There are number of important machine learning tasks, such as training ResNet-50 on Imagenet (Zhang et al., 2020) and many others image classification problems, where the noise in the stochastic gradient has much "lighter" (sub-Gaussian) tails. That is, As. 3.2 is reasonable for large class of practically important problems. Moreover, in Appendix E.4, we also provide an analysis of BTARD- CLIPPED- SGD and RESTARTED-BTTR EETARD-CLIPPED SGD without any assumptions on the tails of the stochastic gradients distribution.
30

---

Under review as a conference paper at ICLR 2022
E.3.2 QUALITY OF THE AGGREGATION
The quality of the aggregation each iteration of BTARD-SGD significantly affects the rate of the method. That is, properties g are highly important for the convergence of BTARD STARD-SGD. This aggregator is obtained via BTARD that requires know tight estimate of the total number of Byzantine workers violating the protocol at iteration k - clipping parameter r depends on this quantity. Therefore, it natural start with relatively simple setup when the number of Byzantine workers violating the protocol is known at each iteration.
Before we formulate the first result introduce some useful notations. Let ny be the total number of peers iteration k, be the total number of Byzantine peers iteration k, b be the total number of Byzantine peers violating the protocol at iteration k, and 8x nu
fx. 8x hn In view of new
notation, we start with the ideal situation when by is known for each worker at each iteration k. First of all, needed to estimate the quality of the aggregation for good workers.
Lemma E.1 (Theorem IV from Karimireddy al. (2020)). Let As. 3.1 hold, 5 s 0.1((n m), and i 9K Cg. Assume that by known for each worker iteration and 8g used compute clipping parameter Ti for CenteredClip. If the total number of iterations T of CenteredClip satisfies 80² T 2 loga.78 38]]|0 g" p..
then
E [1I (1) (i)12 | 4001 a²
(22)
T2g m
where gi)
Σ (1).
jECx VC*
Proof.
The proof follows directly from (7).
Unlike the good peers, Byzantine workers can cooperate and shift the result of CENTEREDCLIP in the components they aggregate without being revealed Verification 2 of BTARD. However, they cannot produce an arbitrary large shifts due to Verification 3. The next lemma estimates the maximal possible magnitude of shift together with probability of triggering CHECKAVERAGING at iteration k for at least one worker.
Lemma E.2. Let As. 3.1 and 3.2 hold, b & 0.1(n - m), and E Bk \ Ck- Assume that by known for each worker at iteration k. Ak (1+v3)2z and 8y is used to compute /ue clipping parameter TI for CemteredClip. If the total number of iterations T of CenteredClip satisfies 60² T > logo.78 anll]u - and CHECKAVERAGINGG() is not triggered, then
- (1) - 9" (0)1 1 4(11+ v3)² +4) 02
(23)
m
where (1)
Σ
(1). Moreover, b = 0 and ni - m 2 170, then (i) = -z
/C
and
149
P [CHECKAVERAGING is triggered for 2 peer x²} < 49(ng m)
(24)
Proof. If CIIECKAVERAGINGGI is not triggered at iteration k, then for Th - good workers 1,, i2,
......,ry .2,...,, fiv E Gr. \ CC have ||o,, (i) g+(li) A A Therefore, due to the independence of
31

---

Under review as a conference paper at ICLR 2022
g. E Gz \. Ck for fixed x² we have
2
E || (t) {0)l =*]
2B
g
(1)
1
of (i)
1z
Th
/2
+2B
1
g (0) -0()
1x
rk 3=1
< 2E
1
10th (i) oh (1)1
+ +4E [I] (1)((²)) - |x*]
Fh f=1
Fkk
4E
J (i)
1z
Th j=1
4a²
802
2( max
2² + 99 \ Ckl
m
4 ((1 / + 4) 0²
Tig - m
Finally, let us estimate the probability of triggering CHECKAVERAGING when all workers follow the protocol. In this case, g(1) = g" (i). Next, due to As. 3.2 and S 0.1 m) we have
where we use 19 \ C2 2 r4 2 n and V( =g 1*)
=
02
1
100
IP
(1 (ien(=")ll
V
1i m
19
Cx12
49
m))²
and for all j E Gk \ C
30²
1
IP (10)(1) -
la
n2k m
9
Consider the independent random variables 77 j E Gh ) Ck. where
1. if 1lg (t) Vin(+>>) S
3
M 0. otherwise.
V
126
where & is fixed. Then, My is a Bernoulli random variable with parameter of "success" q 2 8/0. Applying Hoeffding's 's inequality we get that
PPC.
Σ CC
n1
x
exp
2((ne m) q
n& m
2 \ C+1
JEGN
8 -2(n m)
m 1.4(n m))
exp
9
242 m)
exp
3969
Since for all j E G% A. we have (1) (i)l2 < | (i) V ff -
the obtained bounds imply that CHECKAVERAGING is triggered for least worker at iteration with probability not greater than
100
+ (na m) exp 242 - m)
149
<
49 m)
3969
49 m)
where we use that exp
(-
242m
for all 170.
3969
32

---

Under review as a conference paper at ICLR 2022
We notice that Byzantine peers can trigger CHECKAVERAGING by violating the protocol. However, each Byzantine is checked at iteration & with probability p ~ "/n (see Thm. E.2). Therefore, Byzantine workers trigger only O (fn//m) extra rounds of communications and computations on average via triggering CHECKAVERAGING In contrast, when there are no Byzantine workers or all workers follow the protocol CHECK is a negligible communication an computation overhead when 12 is large.
is triggered only once per O(n m) iterations that
Combining two previous lemmas we get the following result.
Lemma E.3. Let As. 3.1 hold and S 0.1 - m.) Assume that by is known for each worker al iteration ki A Amax (1ty3)y2o and = 5n used to compute clipping parameter TI for Vnx--
CenteredClip. the total number of iterations T of CenteredClip satisfies T 2 logg.76 3Elle- [F]] and CHECKAVERAGING is not triggered for any worker, then
E [IT - 1²112 x²] S C8
(25)
20²²
E [1 | 1*1 s 220 211 V >1
(26)
2b
where
Σ /C
Jf and C = 4001 + 4 ((1 + v3)² +44 4).
16 VCl
Proof. We have
E [lI@* 8²1 10]]
Σ
E [11g (1)l |x4]+
Σ 1EB
E [110 -1))1) |x*]
NEGN IC
(3) S
a²
4 4(1 + v3)² + 4) a²
(1 (1) m) 40018
+ (x( (ark-m)) m)
n m
n2k m
O2L02.
Next, using the independence of 03 for j E 9x \ Cv and fixed x we derive
E
x
JAB Wn
2E [| - g01 JM + 2F [1 s
20 + 2 f(= |1 2E
[lIg*
V fz(*)) |22 P|at]
202
2C + +2 ||
20
200 + 2
71 26 m
In view of the definition of (8, crobust aggregator from Karimireddy al. (2020), the result of BTARD at iteration i is (5e, C'-robust. However, we derive this property under assumption that ön is known to all workers at each iteration k. which is impractical.
When by is unknown the situation changes dramatically: in general, good peers only know some upper bound for the fraction of Byzantine peers at iteration kt Unfortunately. if used without bans, this is not enough to converge to any accuracy of the solution since BTARD- SGD is permutation- invariant algorithm in terms of Karimireddy et al. (2020). Therefore, in this case, we always use CENTEREDCLIP with 77 oo for all / > 0, i.e., good peers compute an exact average. In this settings, even 1 Byzantine worker can significantly shift the average in all parts of the vector. The next lemma quantifies the negative effect of Byzantine workers in this case.
Lemma E.4. Let As. 3.1 and 3.2 hold, b 0.1(n -)), m I (n-2b1/2. Assume that
Ak k max Vnu-m CHECKAVERAGING is not triggered for any worker, then
(1+v3)v22 and 8 = 0 is used to compute clipping parameter for CenteredClip. If
[1gh
11
N
11 k.
(27)
33

---

Under review as a conference paper at ICLR 2022
20
E [| x²) 5 <20o0 +2
(28)
n1 26 m
where 76
Σ Jj.C C 4 ((1 + v3)² (31+3)3 + 4), and 1x, is an indicator function of the jESK CCx
event that at least 1 Byzantine peer violates the protocol at iteration k. Moreover, by 0 and V. m 2 170, then g" (1) = 5 (i) and
149
TP (CHECKAVFRAGIIN AGING is triggered for 2 peer x²) S 49(n= m)
(29)
Proof. If CHECKAVERRGGNNG is not triggered for any worker, then 1 (i)- (i)l = (Amax) 1
for all i E (G& UC2)) C₁ implying
E [I 3011 x*]
E
[ (1)- (i)] x*1
iE(GEUCC))CC
(n+ - -m)- 2( v3) + 8) a²
1 S Co21
n
Next, using the independence of o for j E 9k \ C2 and fixed ,² we derive
E || ||
2E | - -" 1|? x + 2E
x²1
2Co²1 2
)1
+ 2E [II
ff(x*)]]
x*]
20
< 2Co 2 V )12
9K CA
202
s 2Co 2 //
2b m
The proof of the final part of the lemma is identical to the proof of the same result from Lemma E.2.
E.3.3 NON-CONVEX CASE
In this section, we provide the complete statements and the full proofs of the convergence results for BTARD-SGD when the objective function f is smooth, but can be non-convex. We start with the case when the number of attacking Byzantine workers is known each iteration.
Theorem E.2. Let As. 3.1 and As. 3.2 hold, Q Rd, and be L-smooth (see Def. E.1) and uniformly lower bounded by Ja. Moreover, assume that b S 0.1 - -m), m S (n-20)/2, and the exact number of attacking Byzantine peers is known to all good peers each iteration. Next. assume that
1 4L
Don LooK J
(1+ V3)220
7 min
A A
(30)
VTR m
max is the parameter for verification 3 at iteration k of BTARD-SGD. Then, we have f( 11 I x² after K iterations of BTARD-SGD, where
where Dn = ((=)) and A k
LAn 22
ndo²
K=
(31)
ngt
ms²
and K is picked uniformly at random from {2 x ,x.,,.,,==K1)
K-13.
Proof. From L-smoothness of f we have
(14) s(x 5 f(x*) + (VS(c*)) - -x²) [lattl 111
L
In²
= f(x)) - ~VV +
2 11
34

---

Under review as a conference paper at ICLR 2022
Taking the conditional expectation E|| x²] from the both sides of the previous inequality obtain
E
2d1
f(x*) - >|V -
g" |xx1)
+ | E [11 |²*
(26)
x ((xh) - - 1/ll ||
E L0tt 5" x 11
2
L7²0²
*CL 1
n1
2h
< f(x²) - 2 (1 21 | )| + 2 [lIg*
2
In20²
+CL7"0R0²2
nt - 2b - m
Since 7 S 4f. we continue our derivations as
I~20²
E [f(x*+1) I |²1 $ f(x²) 4 +L +
2b
L720² 12 2b mm
s -
- -1==
Taking the full expectation from the both sides of the obtained inequality and summing up the results for k = 0, 1, ..... K we get
K-1
8Co² 6k
K-1
4L
E [I S
E((((
-
+
E
K
K
K
n2 2b -
m
4 (f(x9) [xf(x*)))
8C'²
K
by
4L
E
K
m
2b 177.
k=0
4(f(x") fa)
8Co²
4Ly0²
E
bk
K K(n 2b
m)
2b
171
If a Byzantine peer deviates from the protocol at iteration A; it will be detected with some probability Pk during the next iteration. One can lower bound this probability as
1
m
8z)
Pk
n2
12k
n2g
n
Therefore, each individual Byzantine worker can violate the protocol no more than 1/2 times average implying that
1 K-1
4(f(x0)- - Sa)
8Cnbo²
4L
Σ km 0
+
Km(n - 26 - mm) +
K
7K
2b
4(f(x²)- - -Ra)
16Cnbo²
8Ly02
7K
Km(n -26) n 26
4(f(x") - S2)
160Cnào2
80
7K
7Km
7n
Since zK is picked uniformly at random from {x0 x
x k
K-13 1)
we have
[IV < 4(f(x=) - fa)
160Cn802
80Lyo²
7K
7Km
7n
Using the stepsize rule
Agn
min
4L.
Lo K
35

---

Under review as a conference paper at ICLR 2022
derive
(
LAo
vLAgo
nōo²
V )1
K
VnK
mK
meaning that after
LAo
LAgo²
nóo²
== O
E
net
mE?
iterations BTARD-SGD guarantees E
[ [ K |13]
In the main part of the paper, we notice that the rate of BTARD- in the presence of bad workers asymptotically the same as for SGD without Byzantine peers when is sufficiently small? This phenomenon has a clear intuition. When the target accuracy & is small, the stepsize y is also needed to be small enough. However, only a bounded shift independent of the stepsize. Moreover, they can violate the protocol at only n// iterations average. Therefore, the overall impact of Byzantine workers the convergence of BTARD-SGD decreases when the stepsize 7 decreases.
show in Lemmas E.3 and E.4, Byzantine workers can produce
Next, we derive the result without assuming that 8d is known to all peers at each iteration.
Theorem E.3. Let As. 3.1 and 3.2 hold, Q = Rd, and f be L-smooth (see Def. E.1) and uniformly lower bounded by fa. Moreover, assume that b S 0.1 m). m I (n (o-261/2 and 0 is used to compute clipping parameter Ti for CenteredClip. Next, assume that
Dnn Lo*K S
(1 v3)22
7 min
A max
(32)
4L
VT m
where Ao - [(=0) So and A max is the parameter for verification 3 at iteration k of BTARD--GD. Then, we have [[[[] (x k ) S e² after K iterations of BTARD-SGD, where
LDo
LAgo²
nbo²
K=O
(33)
E
n
ms²
and & is picked uniformly at random from {x") , ,...............................
K K-13.
Proof. The proof is almost identical to the proof of Theorem E.2. Following the same steps and using (27) and (28) instead of (25) and (26) respectively we obtain the same sequence of incqualities to the following change: instead of &R. we should use 1 Therefore, we have
K-
4(l(x)) - S.)
8Co2
K
4L
Σ E K=
[[V
S
E
Σ
1 1KT
K
K
n.
2b
k=0
a Byzantine peer deviates from the protocol iteration k; it will be detected with some probability Pk during the next iteration. One can lower bound this probability
1
m 0x)
Pk
n2K
T2g
72g
n
That is, each individual Byzantine worker can violate the protocol no more than 1/p times on average. However, Byzantine peer create shift of the order Ak A each part of the resulting vector. Therefore, all Byzantine peers can violate the protocol no more than h/p times on average implying that
K
A[f(x") - fa).
8Cnbo2
4L
Σ k=U
B[IVS
<
+
K
7K
Km
n..
2h
A(f(x²) fa)
8Onbo²
8L
K
Km
n 2h
4(s(x") fa)
8Cnbo2
80
K
Km
7n
"This for and strongly convex well.
36

---

Under review as a conference paper at ICLR 2022
Since hh is picked uniformly at random from {u², ,..., xx11 we have
4(f(x=) fa)
8Cnbo²
80Lyo?
E
V |1?] -
+
Km
7n
Using the stepsize rule
onn
= min
4L
L
we derive
[IV || = 0 (
LAD
VL
nbo²
+
K
VnK
mK
meaning that after
K= 1.A.
T.Qg²
nho²
nea
mE²
iterations BTARD-SGD guarantees E [ fl K 1| E
As notice in the main part of the paper, the third term of the obtained complexity result is significantly worse than in (31): it is proportional to b instead of = n/n. However, (33) is derived without assuming that by is known for all workers at each iteration. Moreover, as in (3 the third term (33) has better dependence on E than the second term implying that for small enough e the rate of BTARD-SGD in the presence of bad workers without assuming that by is known at each iteration is asymptotically the same as for SGD without Byzantine peers".
E.3.4 CONVEX CASE
In this section, we provide the complete statements and the full proofs of the convergence results for BTARD-SGD when the objective function is smooth and convex. We start with the case when the number of attacking Byzantine workers is known at each iteration.
Theorem E.4. Lel As. 3.1 and 3.2 hold, Q = Rd, f be L-smooth (see Def. E.1), convex, and x² be some optimum of f. Moreover, assume that b < 0.1 m), m S (n-2b)/2, and the exact number of attacking Byzantine peers is known to all good peers at each iteration. Next, assume that
1 4L
7nRg
m R
(1+ V3)
7 min
A K
(34)
120g2K'
1440Co2n'0
V7gg 178
where Ro 2 11000 - xx"1 and A is the parameter for verification 3 at iteration k of BTARD-SGD. Then, we have [x - f(x") } < E after K iterations of BTARD-SGD, where
LR
Q²R2
no
K = 0
(35)
ne²
me
and K
R
2k=0
Proof. Lemma E.3 implies
E || x² 1 x*
E || x² -7 1|2 k
1 x x=112 122 -2,BB (/att - x=" xx'gh) + 110+12 1
=
(26)
<
| - x² x²112 2 (7 x²" (z + 112
27202
-2 22 [(00 - x² 36  1 + 2y 22
- 26 m
*This for and strongly convex cases well.
37

---

Under review as a conference paper at ICLR 2022
Next, we use convexity (see (16) with μ = 0) and L-smoothness of f:
(15),116 S
[[la - x01 xe
11 x 112 - 27 2y -217) (f(x*) - [(x)))
bk
2x20²
-2,B [(x - x² x¹ - 5t) xe1 + 20²
Rik
m
n1 2b m
To estimate the inner product in the right-hand side we apply
inequality:
-2-B [(a* x².0" - r²)) x
27/1x* - x= R 1|0 g01l xM
2 27/10² k xz" |1 E [l1 - - x
27v Coloo - 0011 Vl 0h S 27V 21 1| - x x1'I Th
Vnk m
27vCo 11.5 x² 111 3m.
vn 2b m
Putting all together and using b S 0.1(n m), m S (n (n-22i/2, 7 S 1/s1, nu 1mmm -m 2 2b m, we obtain
E || - -x=11 xx*]
11at xx y (f(x*)) - f(("))
4nv5Co 1| - xx =0'lll Tu +
407"
40-20²
In +
vn
7n
7n
Taking the full expectation from the both sides of the above inequality and summing up the results for k 0, 1, ...., K- we derive
K
K
40720²
E|f(**) - f(x") <
E
[|
x
[13] - E [llabt] - =0113]] +
K k=
K
7n
k=U
4nv 50o
K-1
40y2Co²
K-1
Σ E
1 x 11 Ox
Σ
E3
bbb
Vnk
TnK
||
x² 112
-x=113
40720²
K
7n
4nV55o
K-1
20y2Co² K-1
E
x - 12) +
[[ba].
Vik
7nK
From Jensen's 's inequality we have f(a*) S K Ek=0 f(a²),, where L² = K EK-1 att Using this
and new notation R4 = ||اا/ - 2²11. t: > 0, Ro
2 1
- x²1
we get
RB - E(N&]
402202
0 5 7B - [(x))]
K
7n
4yV5Co
K-1
2072Co2 K-1
V [E Eb
Σ
136
VnK
7nK
km
km
implying (after changing the indices) that
20
4yV5Co R-1
20y k-1
E R
R3 +
E [
Σ
E[b:]
(37)
7n
7n
holds for all k 2 0. In the remaining part of the proof we derive by induction that
40
47v5Co
40y2Ca2
k-1
R +
+
VERR
Eb +
Ebbil
< 2 2R
(38)
7n
Vn
7n
1=0
38

---

Under review as a conference paper at ICLR 2022
for all k 0,... K. For k 0 this inequality trivially holds. Next, assume that it holds for all k = 0, .......TT--11 -, < K - 1. Let us show that holds for k = T as well. From (37) and (38)
we have that [[ 2R for all k 0,1..... T - Therefore,
4072
ANV5Co Vn
2 T-1
B[
R
[R Bbb
Elbi]
7n
7n
20T"OTT
4yv10CoRo Ro
40
COo
T-1
R6
E bb
B(6.).
7n
Vn
7n
1=0
1=0
If a Byzantine peer deviates from the protocol at iteration k, it will be detected with some probability Pk during the next iteration. One can lower bound this probability as
m - 5x) m
Pk
Therefore, each individual Byzantine worker can violate the protocol no more than 1/p times on average implying that
40y20²T
1ncy/10Cbo Ro
C0
E[R
R
+
7n
myn
7nm
407202T
100/10080
207
Ry
+
7n
m
7m
Taking
1
7nl
m
m²Rg
7 min
4T.
120g2
1440Co2n28
ensure that
00T
4m 10C8oa
2022Co²n8 7m
R2
R2
Rb
S
+
R2.
7n
m
3
3
3
and, as a result, we get R < 2 Therefore, (38) holds for all k = 0, 1, (36) implies
K. Together with
2R
EE
<
7k
Next, from stepsize rule (34) it follows that
LR
o Ro
nvooo Ro mK
E [[((=*) f(x)] =
+
+
K
VnK
meaning that after
LRG
R2
nvod Ro
==O
ne²
me
iterations BTARD- SGD guarantees Bif(zk) - f(x")) SE.
In the convex case, similar observations hold as in the non-convex case. Next, we derive the result without assuming that 6 is known to all peers at each iteration.
Theorem E.S. Let As. 3.I and 3.2 hold, Q = Rd, f be L-smooth (see Def. E.1), convex, and x² be some optimum of f. Moreover, assume that S 0.1(n m), m I (n-2b)/2, and d 0 is used to compute clipping parameter Ti for CenteredClip. Next, assume that
1 4L
7n
m² R3
(1+ V3)22
min
k max
(39)
120g2K
72Co2n212
Vnu- m
where Ro 2 11000 xx and A is the parameter for verification 3 at iteration k of BTARD-SGD. Then, we have [lf(T*) - -f(x((())))))))))()))))) ] < E after K iterations of BTARD-SGD, where
L.R
R2
abo Ro
K 0
+
(40)
ng
me
and x:
KK-1 R
2k=0
39

---

Under review as a conference paper at ICLR 2022
Proof. The proof is almost identical to the proof of Theorem E.4. Following the same steps and using (27) and (28) instead of (25) and (26) respectively we obtain the same sequence of inequalities up to the following change: instead of 8% we should use 1 Therefore, we have
E [1 =12 x=]]
I
|0e
x² - 2 (1 - 21 (f(x*) -
(f(x")-((x") -f(x))
2720² n1 24 m11
-2y1 [Rot x² x² - - | x²]] + +2y2Co²21a
2 (xtt
x², g" -n x S 2 -x= -2,00
that result in
E [| h+ 1²1 x4]
12 - 10 - 7 (f(a*)- - f(x'))
40720²
+2WVCollz* - x | + 22² +
7n
Taking the full expectation from the both sides of the above inequality and summing up the results for l = 0, I...., K we derive
K K
1
K
40y20²
E[f(E*) f(x')
E
E [11 - =211|²] + 2²113]
K
7n
k=0 0
27v Co
K-1
2x²C0²
K-1
E [|I=** x² [1,,] +
B[1g,]
K
K
k=
k=0
11000
x² 112
E[|l " - xx"
407202
K
7n
24
2y² K-1
E I||a*
20 [19]
B[1a,vl-
K
K
From Jensen's 's inequality we have f(**) <
Ekzo f(at)) where FK = EK= xtt Using this
and new notation Rs ||a-
2=1|. xo 2 0 get
RB E
R
407202
0 5 (SEE - f(x')]
K
7n
20
K-1
Σ
V E
[
E1,
2x²C0² K-1
Σ
E3
(4,4
1
K
K
k=0
k=
implying (after changing the indices) that
20
k-1
E E[
R
+ 2y
[R
E
E[1,,]] + Co2
Σ
B[L,ol
(42)
7n
holds for all k 2 0. In the remaining part of the proof we derive by induction that
20 7n
k-1 E[1,,d] S 2R
RØ-
+ 2yvCo
Σ
V E [ E(1,d
Co2
Σ 1=0
(43)
for all 1: = 0,..., ... K. For h = 0 this inequality trivially holds. Next, assume that it holds for all
0, 1,..,.... , 1, T < K- 1. Let us show that holds for k = T as well. From (42) and (43)
we have that [8(R)) 2R for all k O, T 1. Therefore,
40-202k
ELRNJ
R3 +
2 VCo
B
+ 22 2
E E
7n
1=0
20 k
1
T-1
<
R² +
+ 2
RD
E L1,1
+ 22²Co*
Σ
E
[1,
7n
1=0
1=0
40

---

Under review as a conference paper at ICLR 2022
If a Byzantine peer deviates from the protocol at iteration k. it will be detected with probability Pk: during the next iteration. One can lower bound this probability as
1k
1
m
5k)
m
n2
T2g
That is, each individual Byzantine worker can violate the protocol no more than l/p times on average. However, even one Byzantine peer can create shift of the order A at each part of the resulting vector. Therefore, all Byzantine peers can violate the protocol no more than h/p times on average implying that
40720²T
2 Ro
nbCo²
E[R
S
Rg
7n
m
m
Taking
TnR
m
R R
= min
4L
120g²
72Ca2n²62
ensure that
2yndv2CoR, 2yPnbCo² 20-202T
R2
R
R
S
Rg:
7n
m
m
3
and, as result, get E[R?] < 2 Therefore, (43) holds for all k == 0, (41) implies
K. Together with
2R
E - <
?k
Next, from stepsize rule (39) it follows that
LR
RRo
nbo Ro mK
E ((x)))))((+))=--))))
K
vnk
meaning that after
LR
σ² Rg
nbo
K 0
+
ns2
me
iterations BTARD-SGD guarantees Bif(Tk)
{xx* S.
E.3.5 STRONGLY CONVEX CASE:
In this section, we provide the complete statements and the full proofs the convergence results for the restarted version of BTARD-SGD BUSTTAREED-BTRD-SOE Alg. 7) when the objective function f is smooth and strongly convex.
Algorithm 7 BASSTARTED--TARD-SOOE
Input: 20 starting point, r number of restarts, {rdr= stepsizes for BTARD-SGD (Ki)_= -l, K seeds for batches computations
number of iterations for BTARD-SGD, (s....)),
1: 8 = 0
2: for 2,,...., do
3: Run BTARD-SGD (Alg. 6) for K2 iterations with stepsize 7h starting point Øf-1,
and
K.
seeds for batches computations {suu, Kn.K-
Define a' as x
x
where
K.
k=
0e ,0t xlt Ked are the iterates produced by BTARD-SGD.
Output: Fr
We start with the when the number of attacking Byzantine workers is known at each iteration.
41

---

Under review as a conference paper at ICLR 2022
Theorem E.6. LetAAs 3.1 and 3.2 hold, Q R be L-smooth (see Def. E.1). p-strooggy convex (see Def. E.2), and x² be some optimum of f. Moreover, assume that b I 0.1(n - m), m S (n-2b)/2, and the exact number of attacking Byzantine peers is known all good peers at each iteration. Next, assume that
R 120
m² 2 R
(1 v3)/20
7 min
A
k,t max
(44)
41
2'
1440 C'Co2
Vnk m
16L
320 15V10CN/0022
u.
K,
max
log2
(45)
1
1 R
my
where Ro 2. |1 - x²'] Aktt is the parameter for verification 3 at iteration k of BTARD-SGD max
during the t-th restart, nig is the total number of workers at iteration k of t-th restart. Then, we have E[f(2") - f(x")] I E after r restarts of BTARD-SGD and the total number of executed iterations of BTARD-SSG is
BRg
nyōo
Σ K2 =0=0
log
(46)
nye
mi/uE
Proof. Theorem E.4 implies that BTARD-SGD with
1
7n
m RS
= min
4L
120g²
1440Co2
guarantees
2R5
E - -
S
after K iterations. Therefore, after the first restart we have
2R
HR
B[s(E') [(x))]
7 K
4
From j-strong convexity of f and Vf(x*) 0 we have
R2
x ʃ(x*) f(x' - Bi|l - -
-
<
2
2
Next, assume that we have [ā' f(z))] I Then, Theorem E.4 implies that
21TT.
Elll x²1 ||
R -
for some t r- 1.
2 2 x= 12
Elf f(x
7't Kr
Taking the full expectation from the both sides of previous inequality we get
B[f( f(x")] [ x= 1=1
2R 2t,,
1R3 21+2
KKK
From y-strong convexity of f and vf(x*) = we have
-1st1- 201 < -()--))-(())) f(x))
E E||
x² 21 <
21+1
Therefore, by mathematical induction we have that for all t = 1....,r
RR
Rd
Elf(E') f(x*)]
E ||| x x1| <
2
2
42

---

Under review as a conference paper at ICLR 2022
Then, after r
log2
R
restarts of BTARD-SGD we have B[f(²') - f(x²)] S S. The total
number of iterations executed by BTARD-SGD is
L
2² R2
ny nvdo22
})
Kr =
Σ
max
14
my
2"
nv0022 muRo
0
1 R
1 log
R
o²
R
nvoo
R 6
0
1 R
Ry
R
nvoo
o
log
+
+
E
npe
m
m
In the strongly convex case, similar observations hold in the non-convex case. Next, derive the result without assuming that b² known to all peers at each iteration.
Theorem E.7. Let As. 3.1 and 3.2 hold, Q = Rdd be L-smooth (see Def. E.1), p-strongly convex (see Def. E.2), and x² be some optimum of f. Moreover, assume that b S 0.1(n - m). m S (n-2b)/2, and 8 = 0 is used to compute clipping parameter TI for CenteredClip. Next, assume that
7n 120
m²Rg R
(1 /3)
7 min
2'OKK," V 7 2'C2nB2
A
(47)
4L
1
m
16L
32
24 24
H.
K,
max
log2
(48)
P.
myRo
where Ro 2. 110000 11 Akit max is the parameter for verification 3 at iteration i of BTARD-SGD
during the t-th restart, ni. is the total number of workers at iteration of t-th restart. Then, we have B[f(²") f(=")] S after restarts of BTARD-SGD and the total number of executed iterations
BTARD-SSD is
Σ K. K₁=00 = O (" log 1=1
nRG o²
nho my/uE
+
(49)
nue
Proof. Theorem E.5 implies that BTARD- SGD with
1
7nli
m RS
min
4T.
120g2
22
guarantees
2R
E -((x*))((xx)))
- ?
after K iterations. Therefore, after the first restart we have
2
HRR
E[s(E') f(x))) S
7/2 K₁
4
From j-sttoong convexity of f and vx(x*) we have
# 1 - f(3') f((²) - E||la 2
- x= 1 <
R
2
Next, assume that we have E[f(F* f(x")] s 2 Then, Theorem E.5 implies that
uRd
Elil x x11 <
R z
for some t Sr-- --
21 x 1|
B[f(a++l) - f(x²) | 1
7
43

---

Under review as a conference paper at ICLR 2022
Taking the full expectation from the both sides of previous inequality we get
|[ - [(**)] 2|||| x= 1=1
2R
1Rg
20+2
From ju-strong convexity of f and Vf(x") we have
Rg
デ - - 2²11 - f( -(x)
- B1|
x=11
21+1
Therefore, by mathematical induction we have that for all f 1....,r
Rg
EI f(x))
E
[|
x² |1 S
2
2
Then, after log2 R
restarts of BTARD-SGD we have B[f( - f(x2)( S E. The total
number of iterations executed by BTARD-SGD. is
L 0²2' nbo22 1 42 Rg muRo }
K2 = 0
max
1=1
a 22
nbo22
0
11
112 R
myrRo
1
a²
Tbbo
0
log
1
muRo
E
RRg
0²
nbo
0
log
nie
m o /
E.4 CONVERGENCE GUARANTEES FOR STARD-CLIPPED--C
The results for BTARD-SGD and RESTARTED-BTARD-SON rely As. 3.2 that the stochastic gradients have not too heavy tails, i.e., sub-quadratically decreasing tails. The main reason why needed in the analysis is prevent too often extra computations because of Verification 3 from BTARD when workers honestly follow the protocol. However, in many important NLP tasks such BERT training (Zhang et al., 2020), the noise in the stochastic gradient has such heavy noise that As. 3.2 becomes unnatural.
Algorithm 8 SEAAR-CLLIPEED....
Input: 00 starting point, 7 stepsize, number of iterations, (8t, K-K seeds for batches computations, {A K /==0 gradient clipping parameter
1: Co = Banned Ø
2: for k 0, .....: K do
min
Vf(a", Ei,k), if E Gk \ Cb., where
3: Worker i computes /.
if i E B, Cr.
E is generated via seed 8 available to every worker ak
4:
(āt, public_info,)) = BTARD(
(T, , .q......
.
Fea.
). where .it,..., 1 } = (Gs U Bx) \ Ca.
5: Choose 2m workers c
em u1
k+1
um uniformly at random without replace- =
ment, Cx+1 {ck+1 ..... o ,++1), Uk+1 (u k+1
6: Banned, = CHECKCOMPUTATIONS(C (C Uk.1 public info,)
7:
k+l projo(2* -r = argmin || - (x* - 21 ||
8: GE+1 = GR Bannedg-1
9: B++1 = Br Banned;-1
To handle the problems with heavy-tailed noise distributions we consider
(see Alg. 8 in Appendix) applied to solve (3) such that Q is bounded. Essentially, this algorithm
44

---

Under review as a conference paper at ICLR 2022
coincides with STARD-SGD up to the following change: all good peers E Gk \ C2 use clipped stochastic gradients /. (g. (1)" (ml - m)) where of (l) - min 1, d 1 1= 1,...... Tig. m. and o is the stochastic gradient. Next, we introduce the following assumption.
(ls of (1),
Assumption E.1. There exist such constant G O, 80 E [d], and a E (1,2) that for any set of indices S = (i1......o) id). 1 S in < is < < is S d, s 2 so and arbitrary x E Q stochastic
gradient V fa, {) satisfy
VVG vd
=
(50)
where Vis][(z, E) is defined in As. 3.1.
This is a modified version of the assumption used in Zhang et (2020). When a < 2 the variance of the stochastic gradient can be unbounded. One can show that in such a regime vanilla SGD can diverge (Zhang et al., 2020).
Under As. E.1 we derive the convergence results for convex and strongly convex problems.
E.4.1 QUALITY OF THE AGGREGATION
Since now we have As. E. instead of As. 3.1 and 3.2 it is needed to derive new guarantees for the quality the aggregation. We start with the following useful lemma about the properties of clipped stochastic gradeints.
Lemma E.5 (See also Lemma 9 from Zhang et al. (2020)). Let As. E.1 holds and i,j E Gk \ Ck-
Then, for all = 1,2..... n2 m we have
E |1 (1) (1)) 1nk]
4 1-a
G
(51)
Vnk
m
G 10= 2-a
E [10g(())1 IAl
(52)
(nu mm 4
G2a
[l) | - [o)
(53)
(n m) X2 2(a
where (²) Be Veal
Σ (lr all l = 1,
77
Proof. First of all, we derive
E [| (1) - o3 (1)1 at]
E [[]T (1)
(1 (0) 1
8X "E (1) &xx))l + [o Eax))l sM
G
16
4-
Vnn
implying (51). Next, for all é E G% Cj we have
E (1)
E
[1a 11 (1))
<
X2 [[ (1
(()))))))))))1))111))))1))1))))1 1 x
(50)
G x²-2--
(nu - m) 2
implying
Go 2o222-0 2-a
E [[lo*((]] (1) [+1] S 19h \. Cvl
E (17) 1 S
(nx - m)
+EG. VCa
45

---

Under review as a conference paper at ICLR 2022
Finally, for all i Gk Cs we derive
[[[]) (1) | x²1 - (x+(()
| (1) War Eix) |2
=
E
I (1) Van Ecx)) |
E
1o (1) Vent(at, Gix)l 1 (1 xx
E
V [w) (xx))l))) 1
I a
(o) EaN) 1 V (w0ll) 1
E
(50)
Ga
(nk m) 1
implying
Elgh (1) | x²11 - vwn(+tt)
Σ
E (I) - (nnf(=)))3 |x
Gh Cal
iEDx (Cc
Gza
(nu - m)aa 2(x-1)
Next, we derive the guarantees for the quality of the aggregation in the case when the number of Byzantine peers violating the protocol by is known at each iteration.
Lemma E.6. Let As. E.1 hold and S 0.15(n - mi) Assume that by is known for each worker at iteration k, Amuxx = 2
2A and 8 = 6y is used to compute clipping parameter Ti for
-ng-m
CenteredClip. If the total number of iterations T of CenteredClip satisfies T 2 +loga.44 Ellldo 5" [P] and CHECKAVERAGING is not triggered for any worker, then
26
E [ g²112
1
(e G² C222),
(54)
E ||0 1| 1 S 25 (C1 3 _ + C2X2) + 22
(55)
where gh G6 Call
Σ gf. C1 = =384, and C2 4.
iE
Proof. Consider the i-th part of g², i.e., consider (+). If E GR \ Cr. then, in view of (51), we can
directly apply Lemma E.1 and get
E ||| (i) g"
1*1 (1)
S 384022 1-
G
384 3 G
(n+ - m)
T4g m
Next, i e B& \ CR. then
4X2
E [1Ia (i) - (0)]1 2*1 < (A )
,2= = = =
71k-
Putting all together, we derive
E [IIø* 111 [+]
Σ VE
E [[I (1)- | + Σ
E
[[1T* (1) - ((0)) (0)-g(()) wM1
iEB& CC
(1 - --0))(m - -m)- 3846 x 1-0 G
4X2
+ (m m)
n4 m
m m
(A1 50 G + C2
46

---

Under review as a conference paper at ICLR 2022
Using (52) we obtain
E [11g 12
xx*]]
21 [1
g"1 x1
21E [1 1=*]
G 1 2-a
x
20
+ +2
Σ
(nx m)
iE(GL.B.)1C
20x( G 20a
We notice that Veritication 3 can be simplified in the following way: if at least on good peer i notices that | (i) ()_l A 2Λ,, then peer i should accuse j-th peer and both are removed from the training process. In this scenario, there is no sense for Byzantine workers in triggering to deviate significantly from the clipped stochastic gradients of the good peers.
As for BTARD-SGD. when by is unknown we always use CENTEREDCLIP with 77 = oo for all 1 Z O, i.e., good peers compute exact average. In this settings, even Byzantine worker can significantly shift the average in all parts of the vector. The next lemma quantifies the negative effect of Byzantine workers in this case.
Lemma E.7. Lel As. E.I hold and b < 0.15(n - m)) Assume that by is known for each worker 22 at iteration k; Amaxx = 22 Vng-m and 8 8g is used to compute clipping parameter TI for
CenteredClip. If the total number of iterations of CenteredClip satisfies T 2 logg.94 -1llib-31 [|]] and CHECKAVERAGING is not triggered for any worker, then
250²
E [lIT* - F²11 1 s*] < 1 k,
(56)
E
2 10*1 S 2C22² 1N 2-a
(57)
where gh 1oxACa
Σ
0 C2 = 4, and k is an indicator function of the event that at least 1
Byzantine peer violates the protocol at iteration k.
Proof. For all i E (Gx U BB) \. Cs we have
4X2
E LIlg (t) g" (1) x** I (A (Amax) max) 11,, -17
k.u
7
implying
E | -
Σ
- (t)) 24
iE(BLUB Lick
412
< (n - m)
1 = C2A2LK.0
m
Using (52) we obtain
|| 1
<
2E [|ig* - -111 2 201 + 2E |||g* x*
(54)
2C2A21km +2
Σ
2 2-a
202x 2-m
(n+ - m)
(E(G,LBB))CC.
E.4.2 CONVEX CASE
In this section, we provide the complete statements and the full proofs of the convergence results for STARD-CLIPPED-SSE when the objective function f is smooth and convex. We start with the case when the number of Byzantine peers violating the protocol by is known each iteration.
47

---

Under review as a conference paper at ICLR 2022
Theorem E.8. Let As. E.1 hold, Q is bounded, f be convex, x² be some optimum of f. and Vf(a*) O. Moreover, assume that I 0.15(n m). m S (n-26/2. and the exact number of attacking Byzantine peers is known to all good peers each iteration. Next, assume that
Ro VGGK.
mR
min
A A max
2Xx
(58)
A=D 12Gm/ 12Gm/108(C,E 105(C du + C2K
GK
(59)
where Ro 2 1|x0 x= and A max is the parameter for verification 3 at iteration of BTARD- ) s after K iterations of BTARDD-CLLPPED-SGII
CLIPPED-SGID Then, we have ) f(x")] where
GRo
-
nv nvoGRo
K = 0
+
(60)
and x
5K-1 K 2===0
Proof. Non-expansiveness of the projection operator and convexity of imply
|| - 1²11
||proja(*** (x* - - projo (I²
1/:0 5¹¹ - -12
1 - x² 1²1 122 27/xx²t x², x², +
1 11
l1 =2 2-/s.*t xx, V.((=))) - 27/12" x², Vf(a*)) + 11
I|a x=1 27 (J(x*) - -((x)) -27 xx" ,0
()(²²) + 11
Taking conditional expectation E[. x*1 from the both sides of previous inequality we derive
|||a+
x=112 x
<
||0 - x 2=1 27 (f(x²) - f(x"))
-2yB 100t x². v)(x')) | | + 2 11@5|12 | 1
(55)
| xx 2 27 (5(**) f(x')) 2-
-2y (0 x², [g+ g" 1201) + 2
to G + C2X2)
|| x² - 27 (f f(x')) + K 200
22 (x* x= E [ g" 1 + 27 G (C + C2K
To estimate the inner product in the right-hand side we apply Sauchy-Schwarz inequality:
-2 (1* x² E g
2>11x* - x E [
g 1*
27|1 x" I
* x
27|1x0 - x '1 E
[llh - Tz1 xt
(54)
I
27|1=* k - x 11
8e
(C - G + +2222
2yGl| - x 11 Ci + CoK? bb
VTk - m
27Glla* - x² -x + C2K2)
Vox.
77n
48

---

Under review as a conference paper at ICLR 2022
where in the last inequality use b - 0.15(n-m), m (n (m-226/2,, 1/4L, n4 n n n 2b-m 20 n. Putting all together we obtain
I
EE ||| x 11 x01
| - x21 - 217 - -(=))) +
2 x 11 111/20CC/K T + C2K b
V
G* +c
7n Taking the full expectation from the both sides of the above inequality and summing up the results for l 0, 1, ... T 1 we derive
27 T
- [(x))] <
E
|| &
x 113] - E [||e - xx1113)) + G2 =
T K=
T km0
4yG V 5(C, K + C2K
E
11 x² 20Ily bk
VnT
k=0
40, G2 T + C2K
T-1
E(bal
E
7nf
1
x²113 - B|[| - x11
222 2=
K
4GG
5(C,K A-a
+ C2K3)
T-1
[| - x 1|
VnT
km0
407 G2 2a
+ C2K3)
E B(bal-
7nT
From Jensen's inequality we have f(x") S 1
Ei-
fxx where x- x= we get
Di=o xtt Using this
and new notation R4 1|a-* x=
k > 0, Ro
1
R
R
$ 2yB [f(=") - f(x')] s
+ +2 222 20
T
4GG 5(0 4-
+ +C2K ?
[R
by
VnT
40,"K"(CKK' + C2K
T
E(by]]
(61)
7nT
implying (after changing the indices) that
4,G 5(C 3 + C2Ka)
E[R]]
RB 22
E
R
E
by
Vn
KO + C2K
k-1
bb]
(62)
7n
1=
holds for all & 2 0. In the remaining part of the proof we derive by induction that
4/G/5(CCKk _
+ C2K
R3 + 22 -
ir
E
E
Vn
10
K
- +
C2
k-1
Σ Elbil
$
2R
(63)
7n
49

---

Under review as a conference paper at ICLR 2022
for all k 0,..., K. For l 0 this inequality trivially holds. Next, assume that it holds for all k = 0, 1..... -T < K - 1. Let us show that it holds for k = T as well. From (37) and (38)
we have that [E < 2R for all k 0.1....,, T 1. Therefore,
22 G + 47G / 5 20 +C2K3)
B
R
E by
vn
40 4072 20
C2Ka)
T-1
R(bi]]
7n
< RB 2 3 4;GRo
10(C - + C2K
B 61
Vn
40 30 To O2K2)
T-1
B(bi]
7n
If a Byzantine peer deviates from the protocol at iteration A; it will be detected with some probability Pk during the next iteration. One can lower bound this probability as
1
m(1
5τ)
m n
Pk
2
Tkk
7kk
Therefore, each individual Byzantine worker can violate the protocol no more than 1/D times on average implying that
RnG / 10 - + C2K
E(Rē]
R2 + 2 2n <
myn
40 K - + ))b
7nm
4y K0'0 K' + C2K3))
TSK S
R + O²
m
G To + C2K33
7m
Taking
Ro VOGK
mRo
7 min
(GG//10S(C,K' - + C2K2
ensure that
4yGRon K - + CZK330
=²
m KC To + C2K
R2
R2
R2
R2
7m
3
3
and, as a result, we get E[R2) < 2Rg Therefore, (63) holds for all k: = 0, (61) implies
K. Together with
R g
B[S(**) - [(x') 5
Next, from our stepsize rule (58) it follows that
GR
n ny B
E [{(*) - f(x")) f(x))==0)
0
K --
mK
50

---

Under review as a conference paper at ICLR 2022
meaning that after
GRo
nVoGRo
K = O
+
iterations WTARD-CLIPPED--SSS guarantees E[f(*k) f(x²)1 Se.
If there are no Byzantine peers (d = 0), the theorem establishes new result for the convergence of CLIPPED-SGD for convex objectives. In the strongly convex case, the theorem recovers the rates that are optimal in this setting as shown in Zhang et al. (2020). Next, when the number of attacking Byzantines is known each iteration and av (1), the complexity bound is the same as the case when 8 0. This means that the negative impact of Byzantine workers is negligible. Finally, the derived theoretical guarantees do not benefit from the increase of the total number of peers n. However, the result holds even for non-smooth problems and it is known that parallelization does not help to improve the complexity bounds in such generality. Nevertheless, our results show that BTARD DECLPEEEDDD- SGG provably converges to any predefined accuracy >> 0. This is property that the majority of previous methods does not have (Karimireddy et al., 2020).
Next, we derive the result without assuming that 8h is known to all peers at each iteration.
Theorem E.9, Let As. E.1 hold, Q is bounded, f be convex, x² be some optimum of f. and f(x") = O. Moreover, assume that b S 0.15(n m). m S (m-2b)/2, and = 0 is used to compute clipping parameter Ti for CenteredClip. Next, assume that
Ro VIGK?
mRo
2
min
k max
2A
(64)
12/22
VTL
A= GK
(65)
where Ro 2 1| - 1= and A max is the parameter for verification 3 at iteration of BTARD- CLIPPED-SGD. Then, we have E [xx")) < after K iterations of BTAADD-CLIPPDDDSGIDD where
K = 0 ( GRo
a
nbGRo
+
(66)
and k 1 K- 2===U
Proof. The proof is almost identical to the proof of Theorem E.8. Following the same steps and using (56) and (57) instead of (54) and (55) respectively we obtain the same sequence of inequalities to the following change: instead of & we should use L Therefore, we have
|| h+1 x²
I
||
x²11 27 -(==)) 27 (x - x,  1+
27 (z xx E lggh 7h xrd)) I 2-G|2** - x -
and
E |||a x0112 1
S
1|-"- - x112 - 27 (f(x*) - ((x)) +2 2 2-0
+27GV C2 - =,'l| + C2 K
51

---

Under review as a conference paper at ICLR 2022
Taking the full expectation from the both sides of the above inequality and summing up the results for ls 0, ..,...... T 1 we derive
2
B[f(=*) [(x))| s T
EE [11.*
x" x*11 - EE [| x² 11]]
TM
T
G GVVV
V2Ka &
T-1
27 C2 T-1
EE [|| - 2011 +
B [
T
T
|1000
x 112
E[|| [
x²1
+ +22" 2
K
24GV
EE |||a* x [1k,]]
T
2 C2G
E [[
T
From Jensen's inequality we have f(x") 1
2k=0 f(=*), where x-' = EK= at Using this
T-1
and new notation R2
-|1
2211, k > 0, Ro
x=
we get
R
R
0 s 2y [ f(x))] <
02 2:0
T
T-1
[ E [1x,o]
T
27 K
E3 [[
(67)
T
implying (after changing the indices) that
E[R S
RB 18+2222 2B=222Pkk== + +2,G C2k
V E [T]] E [1,,)]
1=0
G Σ B[1
(68)
holds for all & 2 0. In the remaining part of the proof we derive by induction that
+ 2 +C,G/C.k² &
E E
C2 K =h
Σ B[1
2n
(69)
1=0
for all k = 0,...,, K. For l: = 0 this inequality trivially holds. Next, assume that it holds for all
A = T.I. 1, < K - 1. Let us show that it holds for k = T as well. From (42) and (43)
we have that [[ < 2R for all 0. - 1. Therefore,
E E
<
R + 2x G 7- +2
[ [[,o]]
T-1
C2 Σ E[1,vl
< R3 +x GTT == + 22 V 2C
E [Ir,.]]
T-1 G2 k
Σ
52

---

Under review as a conference paper at ICLR 2022
If a Byzantine peer deviates from the protocol at iteration k. it will be detected with probability Pk: during the next iteration. One can lower bound this probability as
1 m 5x)
Pk
T&
Tkk
π2
That is, each individual Byzantine worker can violate the protocol no more than 1/D times on average. However, even one Byzantine peer can create a shift of the order A max at each part of the resulting vector. Therefore, all Byzantine peers can violate the protocol no more than h/p times on average implying that
20 nb + Cr
EIAA! 2
R2 2 2n
Taking
Ro
mRo
7 = min
VOGKE G2bkK
we ensure that
2rG =T² +
27 C2
Rb
R
R5
+
R
m
3
3
and, as a result, we get E[RG] < 2 Therefore, (69) holds for all k: = 0, (67) implies
K. Together with
R
- s
gk
Next, from stepsize rule (64) it follows that
GRo
nbGRo
E -(=)))
0
K
m.
meaning that after
GRo á
no
K 0
me
iterations
guarantees [xf( f(x))] Se.
That is, when the number of attacking Byzantines is unknown the complexity bound becomes (1b/m)"/oo)))) 2/(o-1) times worse in comparison to (60).
E.4.3 STRONGLY CONVEX CASE: RESTARTED SAAARTEDDDDTARD-CLIPE-SSSOO
In this section, we provide the complete statements and the full proofs of the convergence results for the restarted version of BTARD-CC MERD-CLIPPED-SCII when the objective function f is smooth and strongly convex.
Alg, 7)
Algorithm 9 RESSTARTED-BTARD BTARD- BTARD-CLIPPED-DSSS CLIPPED-SGD
Input: z0 starting point, r number restarts, {1)) - stepsizes for WWARRD-CLIPPED-GGD
(K Kr number of iterations for BTARD- BTARD-CLIPPED- SGD, {ss. (.....1
1n.--1r
seeds for
batches computations, (Ar.a { gradient clipping parameters
1: 8 o
2: for t- 1,2....., do 3: Run STARD-CLIPPED-C
(Alg. for K, iterations with stepsize Yr, starting point 2t-1 K-1 gradient clipping parameters { and seeds for batches computations {_
--
kit where 0.1 x.1 ...., "...,.KKe K..t are the iterates produced by BTARD- K.
Define El as F
Σ k=0
K.
CLIPPED-SGD.
Output: Gr
We start with the when the number of attacking Byzantine workers is known at each iteration.
53

---

Under review as a conference paper at ICLR 2022
Theorem E.10. Ast E.1 hold, Q is bounded, f be ju-strongly convex (see Def. E.2), x= be some optimum of f. and Vx(²)) = O. Moreover, assume that S 0.15(n m.. m S (n-2h/2, and the exact number of attacking Byzantine peers is known to all good peers each iteration. Next. assume that
Ro /6 24 G
mRo
2
7
ymmin min
Akt max
2Ax,
1-0 12- 22 10 + C22
Vnk m
(70)
(2ri Pio
2$
24Gny 106(C) + (2)
K, max
d GKP
(71)
mjj Ro
BuRi E
r=
loga
(72)
where Ro 2 ||000 - x²1 and k.t is the parameter for verification 3 at iteration k of BTARD- max
CLIPPED-SGD, n the total number of workers iteration k of t-th restart. Then, we have E[f(i') - f(x']] S. after restarts of BTARD-CLIPPED-SON and the total number of executed
iterations of BTTARD-CLPPEDD-SCI
G
ny8
G² ae
K₁
0
O
+
(73)
IuE
1=1
Proof. Theorem E.8 implies that BTARD-CLIPPED-SGD with
Ro VBGK
mRo
7 min
12Gm/ 108(C, A-a
+ C2K
guarantees
12
E [f((*)) f(x))] <
?
after K iterations. Therefore, after the first restart we have
R Ki
HRg
B[s(E') f(x))] S
4
From f-stroog convexity of f and vf(z*) = we have
# -1
x f()') ) - f(x')()))))))))r))) = El|
11
R
2
Next, assume that we have ([ - f(x*)] < ult Elil x11 <
R 2
for some / S --1 1.
Then. Theorem E,8 implies that
1 x 112
Elf( f (x*) x
Taking the full expectation from the both sides of previous inequality we get
) |0 x11
S
<
WK,
2
21+2"
From μ-strong convexity of f and vz(z*) 0 we have
1 " 2+112 < |( f(x)(( - B[ll -x 113] <
R2
20+1
Therefore, by mathematical induction we have that for all /. - 1,...,r
RR
Rd
Elf(E') f(x*)] 21+1
E ||| 111 <
2
54

---

Under review as a conference paper at ICLR 2022
Then, after r
log2
restarts of -LADD-CCIPPEDDSGD we have Elf(3') f(x²){ Se.
The total number of iterations executed by BTARD-CLIPPED-SOOT is
G 22
Gnv
K2 = o
max
uRo
muRo
==1
G
n-1
Gnvō
O
max
2 2)
12
1.oo
mpRo
G
H.R
1)
Gnvō
[uR
2(0-1)
o
max
HRo
E
muRo
E
G
nvo
G²
Ia-
o
m
u
In the strongly convex case, similar observations hold as in the convex case. Next, derive the result without assuming that 8 known to all peers at each iteration.
Theorem E.11. Let E.1 hold, Q is bounded, f be p-strongly convex (see Def. E.2), x² be some optimum of f, and fx(") = O. Moreover, assume that b S 0.15(n - m). m S (n-261/2, and 5 = used compute clipping parameter for CenteredClip. Next, assume that
Ro
mRo
7 == min
kit max
-2Ax.t
(74)
V6.22 2iGK?
12. 22,
Vnj. m
(2V6G--0 . 25
24Gnby
K2 = max
(URo RRo
A = GK
(75)
MitR
HR
T=
log2
1
(76)
where Ro > 1|200 x''l and A is the parameter for verification 3 at iteration k of BTARD- CLIPPED-SGD, ni is the total number of workers at iteration k of t-th restart. Then, we have [[f(2') - fxx"]] < after restarts of BTARD-CLIPEED-SC
and the total number of executed
iterations of BTARD-CLPPEDDSSGD
G2
(nb)
2
2aa-1]
Σ K. =
(77)
pE
m
LIE
Proof. Theorem E.9 implies that
with
{
Ro
mRo
7 min
VOGK=* 12, 12
guarantees
R2 yk
E [f(*k) (0=-(((()) <
after K iterations. Therefore, after the first restart we have
R2
Rg
Elf(E*) f(x))) <
7/ K1
4
From p-strong convexity of f and vf(z*) = 0 we have
# || 1 < f(*)) - f(x') -
x
211
R3 2
2
55

---

Under review as a conference paper at ICLR 2022
Next, assume that we have (E[S(**) - [(x")]
#Rg -
Ellla*
x²11 S 2
R
for some r
Then, Theorem E.9 implies that
1
1² 11
Blf f(x") x
Taking the full expectation from the both sides previous inequality we get
B| f(x))] Eil x 2=11
R
HR
S
2
20+2
From fu-strong convexity of f and vf(x*) = we have
- - - x011 < [( - [(x²) = Bll| - xx113] z
R
21+1
Therefore, by mathematical induction we have that for all / = 1,...,r
R.
Rg
Elf(E') f(x))) S
E
||| z²113] - 2
2
Then, after logz
restarts of BTARD- SAADD-CLIPEDDSGD we have E[f(F') f(x'(()))) SE.
The total number of iterations executed by BTARD-CLIPPED-SONI is
G. 2
Gnv822
Ke =
O
max
1Roo
muRo
G
Gnb
max
2 23
2 22
RRo
mpRo
G
R
Gnb
Zco-1j
max
mpRo
E
2(0-1)
nb
m
G²
2(a-1)
+
WE
m
56

---

Under review as a conference paper at ICLR 2022
F REPUTATION SYSTEM FOR PUBLIC COLLABORATIONS
In this section, we address Byzantine-tolerant training in a setup where new participants can join or leave collaboration midway through training. This requirement arises naturally if a given training run relies on volunteers or an open pool of paid participants (Kijsipongse et al., 2018; Ryabinin & Gusev, 2020: Atre et al., 2021; Diskin et al., 2021). In addition to all existing concerns from Section 3, this new setup allows Byzantine attackers to assume new identity each time they are blocked. Further yet, Byzantine participants can simultaneously use multiple identities in order to obtain majority in the voting procedure, which is known as Sybil attacks (Douceur, 2002; Trifa & Khemakhem, 2014; Wang & Kangasharju. 2012).
In this analysis,, we consider training run where Byzantine peers collectively possess ò < 6maz of all compute resources (we explore the role of 8max < 1/2 later in this section). Intuitively, one can think of this setting as distributed training with n identical computers, [ō n of which are controlled by Byzantines. The "Byzantine GPUs" can be allocated between an arbitrary number of identities. For instance, one accelerator can run full BTARD-SGD protocol for one peer or drop some of the computation and use the freed "compute cycles" to run computation for another participant Theoretically, a device can run computation for an arbitrarily large number of peers, as long as it actually computes as many gradients as one benign participant does in the same time-frame.
To protect against this new attack type, we augment BTARD- SSD with reputation system designed to limit the impact of pseudonymous identities with the actual underlying compute. We base this system on the following three assumptions:
1. Unique and optimal computations: the gradients computed by peer at step is cannot be circumvented or reused from other peers and/or previous steps.
2. Public key infrastructure: peers have unique public/private key pairs and know each other's public keys.
3. Cryptographic hash: peers have access to a hash function such that finding vector satisfying hash(z) = y is infeasible for [ n2] compute over the entire training duration.
We associate each participant with public record that is used to verify that peer's legitimacy. These records can be securely stored in a Distributed Hash Table (see Appendix G). When a new peer joins the network, it begins with empty record and is therefore "untrusted". Untrusted peers compute gradients normally, but cannot aggregate vectors from others and cannot serve as validators. More importantly, other peers exclude untrusted gradients from aggregation, using them only for the purpose of validating those peers.
Each time a peer computes gradients 9¹ over publicly known batch et must write hash(g,)) to its own public record and sign it with its private key, As in the original BTARD-SGD, some of those entries will be validated by other peers chosen by MPRNG. In turn, the chosen validators will either approve their entry or invoke ACCUSE to ban the peer.
In order to become trusted, a given peer must report consecutive gradients until it accumulates T entries approved by (provably) random peers. Here, T is hyperparameter that should be large enough for the training to recover from any previous attacks and make some progress before previously banned malicious peers can earn trust again. In practice, T may be chosen experimentally by observing the number of iterations it takes to improve the loss upon its pre-attack value in case of the most effective attacks, as reported in Section 4.
While T may be application-dependent, we note that its minimal value is small in terms of the relative training time in all our experiments. T corresponding to the 10% of total training time is more than times larger than the worst "recovery time" for both setups considered in Section 4, where almost a half of the peers are Byzantine. Moreover, Appendix I.1 suggests that recovery from the worst-case attack may happen even faster in case of a smaller share of Byzantines. In that setup (with sy 20% of peers being Byzantine), T' corresponding the 1% of training time is already enough.
Once a peer becomes trusted, it must continue reporting gradient hashes to maintain trust. Even single missing or invalidated hash breaks the chain and results in the corresponding peer being
Note that we only provide rigorous convergence guarantees for the case of the Byzantine attacks. However, heuristic described in this section helps with resisting the Sybil attacks in practice.
57

---

Under review as a conference paper at ICLR 2022
banned. To maintain this invariant, peers chosen as validators add the recalculated hashes into their own record instead of the skipped iteration.
To protect against dilution attacks, cooperative training can simultaneously consider at most as many "untrusted" peers as there are trusted ones: all subsequent peers wait in a queue until one the untrusted peers becomes either trusted or banned.
Analysis. Under this formalism, a Sybil attacker will attempt to maximize the number of trusted identities it can control with limited amount of compute. In the simplest case, an attacker has exactly one GPU that can be used to either run all computations for identity or partial computation for multiple identities.
In the latter case, an attacker can honestly compute gradients for identity with probability p E [o, 1] and for identity B with probability p. To breaking the chain, the identity that does not compute gradients at a given step can report arbitrary (e.g. random) entries instead of hash(g"")
Consider the expected number of "trusted" identities after enough steps for TT validations by honest validators (on average, T. 1-(1-8] steps). Identity A becomes trusted with probability p" otherwise is banned. Similarly, identitiy survives with probability (1 - pp)"" Thus, the expected number of trusted identities after T steps is p" + (1-p)²
For T > this expectation is maximal iff p E (0. Thus, if a peer needs more than one validation to become trusted, the "optimal strategy" for a Sybil attacker is to fully support one identity instead of spreading the resources between multiple ones. This observation can be generalized for distributing [8 n over m 2 18 n pseudonymous identities, where maximizing the expected number of trusted identities requires fully supporting any [5 n identities and disregarding the rest (for T > 1, as before).
Overhead computation. When training without Byzantine participants, this modified version of BTARD-SGD requires, on average, T additional gradient computations per participant the very beginning. However, once all peers become trusted, the algorithm computes exactly the same number of gradients as regular BTARD-SGD, effectively training at n-k efficiency of AR-SGD, plus the same communication overhead.
Remark 1: Temporary majority. Despite the fact that spreading 1 'compute unit" across multiple identities reduces the expected number of trusted identities, may still be useful to establish a temporary majority, albeit with small probability. For instance, splitting one compute unit evenly among m identities (each with p-1/m) may result in both m identities temporarily gaining trust with probability:
m
P(peer, A A Apeer,)
m
Tm
(78)
m
T
Sybil attacker can simply repeat this procedure on every step until it can establish a temporary majority and use this majority to harm training (e.g. ban non-malicious peers). A natural way to remedy this is to increase T to such an extent that (78) becomes negligibly small.
Remark 2: Extra compute for Byzantine nodes. Unlike benign peers, Byzantine attackers do not need to honestly validate each other. When a Byzantine peer is chosen as validator, can approve its target without actually computing the gradients. In turn, the freed compute resources can be used to support additional Byzantine identities.
Thus, if given training has trusted peers and chooses k validators each step, Sybil attackers can control slightly more than [8 n2] of all identities by using the free compute cycles from validation support additional peers. Thus, the proposed reputation system requires that the total computational 1 by a (typically small) margin that depends on n, power Brna available to Byzantines is less than ; k. and T.
Remark 3: Perpetual attacks. When training in open collaborations, one canmot ban the Byzantine peers entirely: a Byzantine attacker will always be able assume new identity at the cost of running
58

---

Under review as a conference paper at ICLR 2022
honestly for T k-(1-a) gradient steps. Thus, unlike in Appendix E, cannot make BTARD- unbiased by increasing 7. However, SGD with constant can still train real- deep learning models with the same or virtually the same learning curves as regular SGD.
demonstrated in Section 4, the biased variant of BTARD-
G SECURE DISTRIBUTED HASH TABLES
Distributed Hash Tables (DHT) are protocols that establish a decentralized key-value storage over decentralized unreliable participants (Maymounkov & Mazieres, 2002; Balakrishnan et al., 2003; Zhao et al., 2003; Rowstron & Druschel, 2001). To determine which DHT peers are responsible for given key-value pair, each participant samples unique binary identifier (ID) sampled uniformly from the space of hash function outputs. When "storing (key, value)" on the DHT, one finds peers whose IDs are nearest to hash and sends the data to each one of those peers. In turn, peer that wants to read the value or a given key will also search for neighbors whose IDs are close to hash key) and request the data from those peers. Thus, the data be accessed long at least one o i chosen peers remains active, with some DHT variants introducing additional replication protocols.
Our specific implementation is based on Kademlia (Maymounkov & Mazieres, 2002), a popular DHT variant that determines nearest neighbors based on XOR distance function or their IDs: d(s,, y) int 4 y). More importantly, Kademlia protocol organizes nodes in such a way that each individual peer only "knows" small subset of (llgg, n) direct neighbors, however, it is possible navigate the neighborhood graph to find the globally nearest neighbors in Ollog, N) network requests.
DHT protocols were originally designed for large-scale distributed systems such as BitTorrent, IPFS and several cryptocurrencies. To maintain integrity in these applications, modern DHT protocols also employ security measures that make them resistant to Byzantine and Sybil attacks (Urdaneta et al., 2011).
In our specific scenario, the most sensitive DHT entries are personal records that determine whether or not a given peer is trusted. We protect thee records by enforcing that every value stored in the DHT must be signed by their author's digital signature (Rivest et al., 1978). Thus, if malicious peer attempts to modify a record it was not supposed to, all other peers will be able to detect that and eliminate such peers from the collective.
However, digital signature are known to be vulnerable replay attacks: every time non-B Byzantinne peer stores an given key-value pair signed with its private key, a Byzantine eavesdropper can record the signed entry and replay it in future. For ordinary DHTs, this would allow attacker to revert any key-value pair to its previous state by replaying such pre-recorded messages.
Our algorithm protects against replay attacks by associating each key-value pair with third value denoted as expiration time. Given two entries for the same key, DHT nodes will now prioritize the ones with the latest expiration time and consider it valid up that time. Furthermore, in order to store a new entry to the DHT, a peer must now sign the entire key-value-expiration tuple. Thus, if a Byzantine peer replays a pre-recorded message, will not be able overwrite newer DHT entries that were signed for more recent expiration time.
H ALBERT EXPERIMENT SETUP
In Section 4.2, we pretrain ALBERT (Lan et al., 2019) self-supervised Transformer model for learning representations of language data. We deliberately choose ALBERT instead of other models like BERT (Devlin et al., 2019) due to its high communication efficiency, which is caused by layerwise weight sharing and embedding layer factorization. In particular, we focus on a communication- efficient model, because the connection speed between the workers can become a noticeable constraint when averaging gradients of models with hundreds of millions of parameters. We train ALBERT- large sequences of 512 tokens from the WikiText- 103 (Merity al., 2017) dataset. The training procedure starts from a random initialization, but the subword vocabulary (Sennrich et al., 2016) is the same as created by the authors of the original ALBERT models.
59

---

Under review as a conference paper at ICLR 2022
Ours, T = 10, attack at step 1000
Ours, T= 10, attack at step 10000
0.94
0.8
0.92
Test accurecy
0.6
0.90
0.4
0.88
0.2
0.86
0.84
1000
2000
3000
4000
10000
11000
12000
13000
Ours, == 1, attack step 1000
Ours, == attack at step 10000
0.94
0.92
Test occuracy
0.6
attacks
0.90
Sign flipping
0.4
0.88
Random direction
0.2
Label flipping
0.86
Delayed gradients
0.84
1000
2000
4000
10000
11000
12000
13000
Training step
Training step
Figure 5: Effectiveness of attacks against BTARD-SCE RGD for the case when of 16 participants are Byzantine.
This model trained with two objectives: masked language modeling (given a sentence with several masked tokens, predict the tokens that were masked) and sentence order prediction (given two segments from the same document, determine they were swapped). We use LAMB optimizer (You et al., 2020) with batches that contain 4,096 examples, training with peak learning rate equal to 0,00176 and a warmup of 5,000 gradient descent steps. In addition, we use gradient clipping with maximum norm of and weight decay regularization with the weight of 0,01. We run distributed training on 16 cloud instances, each equipped with a single Tesla T4 GPU. Each training run takes 2-3 days, depending the instance availability.
I ADDITIONAL EXPERIMENTS
1.1 EXTRA EVALUATIONS ON THE CIFAR1O CLASSIFICATION TASK
In this section, we perform several additional experiments with BTARD-SGD used to train the ResNet-18 18 model to solve the CIFARIO classification task.
To better explore the space of possible attack vectors, we also evaluate two alternative settings. First, we consider a situation where Byzantine peers are less numerous. For this experiment, we use the same configuration in Section 4.1, but with only Byzantine peers out of 16 (just under 20%). Figure 5 demonstrates similar behavior to our original setup, but with significantly weaker in magnitude across all attacks.
Next, we explore a situation where Byzantine peers send incorrect gradients periodically, e.g. once per iterations. This reduces the attack intensity, but allows them to stay undetected for longer. In this setting, consider Byzantine peers and reuse all parameters from the original setup, except for the new attack period. We consider I' = 10 for both scenarios (carly and late attacks). The attacks performed at steps ke T, A E N until the attacker is eventually banned. As expected, this setup increases the duration each attack by a factor of T, but decreases the peak attack influence (see Figure 6).
Finally, we evaluate the convergence and the final test accuracy of the less computationally intensive variants of BTARD-SGD that limit the maximal number of iterations in the CenteredClip procedure
60

---

Under review as a conference paper at ICLR 2022
Ours, T = 10, attack at step 1000
Ours, T= 10, attack at step 10000
0.94
0.8
0.92
Test accurecy
0.6
0.90
0.4
0.88
0.2
0.86
0.84
1000
2000
3000
4000
10000
11000
12000
13000
Ours, = 1, attack step 1000
Ours, T= attack at step 10000
0.94
0.92
Test occuracy
0.6
attacks
0.90
Sign flipping
0.4
0.88
Random direction
0.2
Label flipping
0.86
Delayed gradients
0.84
1000
2000
4000
10000
11000
12000
13000
Training step
Training step
Figure 6: Effectiveness of attacks against BTARD SGD for the case when Byzantines send incorrect gradients once per T 10 steps.
0.8
Test accuracy
0.6
M
50
0.4
10
0.2
M
5000
10000
15000
20000
25000
Training step
Figure 7: Convergence BTARD-SGD with r = depending on the maximal number of iterations
M in the CenteredClip procedure.
to M, where M varies from 1 to 50. In the setup with = 1, we observe that M = 50 iterations always enough for CenteredClip converge with 10 in absence of the attacks. Figure demonstrates that stopping the procedure earlier has negative effect on the final test accuracy. The effect becomes more significant for the smaller values of M.
I.2 EVALUATING COMPUTATION OVERHEAD IN TERMS OF WALL TIME
For this analysis, we consider the ALBERT-large training setup from Section 4.2. Our training "swarm" contains 16 peers with T4 GPUs and GiB/s network bandwidth. average over 1000 training steps, the full training step for this model takes up 28.56 seconds. Of this, approximately 23.96 seconds were used up for communication and the remaining 4.60 seconds were spent for gradient aggregation CENTEREDCLIP.
Since MPRNG is running in the background, the only part of BTARD that affects the training time Algorithm 2 BUTTERFLYCLPP Thus, measure the time complexity of this algorithm with different numbers of internal iterations. During "normal" epochs where all Byzantines remained passive, the algorithm converged in 2-3 iterations for 0.25 and 5- 10 iterations with 0.125.
61

---

Under review as a conference paper at ICLR 2022
Table 3: Computation overhead of BTARD in terms of wall time.
No. of iterations
Wall time (CPU), see
Wall time (GPU), sec
3
0.362 + 0.003
0.040 + 0.002
5
0.430 + 0.002
0.042 + 0.002
10
0.601 + 0.003
0,056 = 0.005
20
0.943 + 0.002
0.085 # 0.009
We also noticed that this value has temporarily increased by 2-3 times while Byzantine peers were performing their attack.
In Table 3, we report the average wall time of our algorithm with different number of iterations in two hardware setups: running on a 8-core VM with 3. G.1 Intel Xcon 6148 CPU and on a single 1080 Ti GPU. We report the average wall time and the standard deviation over 10 runs.
Thus, even the worst case overhead (r = 0.125, CPU) less than the 3% of the total step time without attacks and less than the 4% when the attack is active. One important consideration here is that the overhead is constant with respect to the number of peers due to the scaling properties of All-Reduce. Thus, if we train with hundreds of peers, the 0.3-0.6 second overhead can eventually become significant. However, can be easily offset by moving the CENTEREDCL.I execution to GPU, which this stage is waiting for the CENTEREDCLIP results anyway.
1.3 EXPERIMENTS AT A LARGER SCALE
In this section, we evaluate the most effective attacks against BTARD-SGD case of a larger number of peers to ensure that our algorithm scales well.
We still consider the ALBERT-large training setup from Section 4.2 and increase the number of peers to 64 (the largest hardware setup available to us), setting up 31 of them to be Byzantine. To balance for the increased number of peers, we divide the individual batch size of each peer by 4 and set the number of validators to be 4 as well.
Due to the large computation costs, we only evaluate the two most effective strategies for Byzantines based on Figure 3. making only training run for each of them. We choose the random direction attack starting at the step 1000 and the sign flipping attack starting at the step 5000.
The results shown in the Figure 8. Similarly our previous experiments, the Byzantine peers managed to temporarily offset the training loss. As the case with 16 peers, the sign flipping attack the step 5000 obtains the "peak" distortion approximately 20 steps into the attack, and the random direction attack at the step 1000 has longer but less intensive effect. However, BTARD-SGD is able quickly detect and ban the attackers, banning all 31 Byzantines in 100-150 steps and catching up with the original learning curve after approximately 1 150 steps (it is fair to take the original curves from Figure 3 since the aggregation results in the vanilla All-Reduce do not depend on the number of workers). We conclude that WARD-SGD maintains its efficiency even at this scale.
Attack at step 1000 (random direction)
Attack at step 5000 (sign flipping)
10.0
9.9
9.8
Loss
9.7
9.6
9.5
1000
1050
1100
1150
1200
5000
5050
5100
Training step
Training step
Figure 8: Effectiveness of attacks against BTARD-SGD for the case when 31 of 64 participants are Byzantine.
62

---

Under review as a conference paper at ICLR 2022
Ours, t= 10, attack at step 1000
Ours, T= 10, attack at step 10000
0.8
Test aecuracy
0.6
0.6
No attacks
0.4
0.4
ALIE, 1 validator
0.2
ALIE, 2 validators
1000
3000
4000
9500
10500
11000 11500 12000
Ours, T 1, attack at step
1000
Ours, 1, attack step 10000
0.8
0.8
Test accuracy
0.6
0.4
0.4
0.2
0.2
0
1000
2000
3000
4000
9500
10000
10500
11000
11500
12000
Training step
Training step
Figure 9: Effectiveness of the "A LITTLE IS ENOUGH" (ALIE) attack (Baruch et al., 2019) against BTARD-SGD.
Ours, T 10, attack step 1000
Ours,
10, attack at step 10000
0.8
0.8
Test accuracy
0.6
No attacks
0.4
0.4
IPM (E = 0.1)
0.2
0.2
IPM (E = 0.6)
0
1000
2000
3000
4000
9500
10000
10500
11000
11500 12000
Ours, T= 1, attack at step 1000
Ours, 7 = 1, attack at step 1 10000
0.8
0.8
Test accuracy
0.6
0.6
0.4
0.2
0.2
0
1000
2000
3000
4000
9500
10000
10500
11000
11500
12000
Training step
Training step
Figure 10: Effectiveness of the INNER PRODUCT MANIPULATION (IPM) attack (Xie al., 2020; Allen-Zhu et al., 2021) against BTARD-SGD.
63

---

Under review as a conference paper at ICLR 2022
1.4 EXPERIMENTS WITH LOW-MAGNITUDE ATTACKS
In this section, we evaluate several low-magnitude attacks against BTARD-SGD used for training the ResNet-18 model solve the CIFARIO classification task. We the configuration from Section 4. and consider the following attacks:
"A LITTLE IS ENOUGH" (ALIE): attackers collude to move the coordinate- wise median while still sending values inside the population variance. Baruch et al. (2019) show that this attack is effective against TrimmedMean (Yin et al., 2018) and Krum (Blanchard et al., 2017).
INNER PRODUCT MANIPULATTION (IPM)) attackers send the average of all honest peers' gradients multiplied by -c. We test = 0.1 (Xie et al. (2020) demonstrate its efficiency against the coordinate-wiil wise median and Krum) and e = 0.6 (Allen-Zhu et al. (2021) state that is the most efficient attack against their method among the reported ones).
As in Section 4.1, we report the mean and range of the test accuracy over 5 runs for E {1,10}.
Regarding the ALIE attack (see Figure 9), we that BTARD-SGD needs either validators, or one validator and the weaker clipping (r = 10) to guarantee the fast recovery in the worst case (with 7 out of 16 peers being Byzantine).
This observation coincides with Baruch et al. (2019) demonstrating that the ALIE attack is more harmful against median- based and clipping approaches than to the usual mean aggregation without any defenses. Indeed, since T in CENTEREDCLIP allows to smoothly interpolate between the geometric median (r + 0) and the mean (r + inf) aggregation rules (as explained Appendix D.I), is natural to expect that the setups where is too small are more sensitive to the ALIE attack.
In turn, the IPM attack (see Figure 10) has a short negative effect for é) and an almost unnoticeable effect for 10. One validator is enough to combat all variants of this attack.
increases for larger
We conclude that BTARD-SGD remains practical in case of the considered low-magnitude attacks. able to defend the training from the worst-case attacks (with almost half of the peers being Byzantine) while requiring more than = 13% of the compute to be dedicated for validation.
64


Reviews:
[{"review_id": "hhU6-odV74A", "reviewer": "Reviewer_63QJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Thanks for submitting your work to ICLR2022. The paper addresses a very important and timely problem. While there is a lot of work addressing Byzantine resilience in ML, we need works that focus on their practicality in terms of performance and assumptions about the environment. I also like the motivating example of crowdsourcing computational resources from (possibly) untrusted parties. I appreciate the convergence rates that the authors derive in different scenarios (strongly convex, convex, and non-convex functions), and I like the fact that the overhead of the proposed algorithm does not depend on the model size. We, as a community, need to always think of such solutions (whose overhead is decoupled from the model size).\n\nYet, I believe the paper cannot be accepted as-is as it requires to be revised in a few aspects. In summary, (1) the authors make several assumptions that seem unrealistic and unjustified. (2) The most important parts of the paper are either unclear or deferred to the appendices; this makes it hard to understand the algorithm and to see its benefits. (3) As the main aim of the paper is to provide a computationally efficient algorithm, the paper should give clearly the computation complexity of all parts of the algorithm.\n\nThe first area of improvement is to clarify and back up the assumptions. Specifically, I'd like to point out 3 assumptions: The first is the public dataset assumption. Doesn't that make the problem trivial? Can you give examples in which this assumption is practical? Furthermore, many parts of the main algorithm require synchronous networks. It's important that the authors clearly state this in their assumptions. Synchronous networks are easy to achieve in a controlled environment like a datacenter. Yet, in a more challenging environment that the authors consider, I'm not sure how synchronicity can be achieved. The third uncommon assumption is about adversary capabilities. I do not understand the need for the second paragraph on page 6 (which describes the possible attacks). Byzantines should be able to do whatever they want [1,2]. Putting them in categories in which they can do only limited things raises the question of whether the considered model is really for Byzantine attacks or not.\n[1] Lamport, Leslie. \"The weak Byzantine generals problem.\" Journal of the ACM (JACM) 30.3 (1983): 668-676.\n[2] Castro, Miguel, and Barbara Liskov. \"Practical byzantine fault tolerance.\" OSDI. Vol. 99. No. 1999. 1999.\n\nThere are essential parts in the paper that are not described clearly and left to the appendices. One example is how the broadcast channels work in Section 2.3. The authors seem to describe consensus. Is that it? If yes, this concept is orthogonal to multi-party computation (MPC). If not, then what is the difference between the suggested method and consensus? The same comment goes for the main algorithm in the paper. Essentially, there is no appropriate (even high-level, intuitive) explanation of why it works, with all the proofs deferred to the appendices. The most important example is the CenteredClip algorithm, which is the main tool to tolerate the Byzantines. For example (more examples below in the additional comments/questions), from the description, I understand that the input to this algorithm is two gradients: the local one and the one gathered from all peers (by merging a small part of the gradient from each peer). If my understanding is correct, I do not see how clipping (based on two inputs only) can be effective in tolerating Byzantine behavior. It's crucial to understand at least intuition without looking at complex mathematical proofs. I also expected to see even proof sketches in Sections 3.2 and 3.3. The absence of these parts makes it very hard to judge the effectiveness of the proposed work.\n\nParts of the algorithm are not clear and the computation complexity is not rigorously quantified. For example, what is the cost of the validation step? If we need a lot of validators, why do we need distributed learning in the first place? If peers can compute their gradients and the others' gradients (for validation), why bother distributing? In addition, I believe many parts of the algorithm rely on consensus (even if that was never explicitly mentioned by the authors). Consensus is costly, and a careful analysis of its complexity is required. Along the same direction, I have two issues with the \"accuse\" procedure: (1) it's very costly because all peers have to compute the gradient of the accused peer; a Byzantine can use this trick to make learning very slow. (2) The procedure relies on consensus, which is also costly. Another unclear part is the cost of sampling the random direction z among all peers.\n\nAdditional comments/questions:\n1. The authors mentioned that existing solutions either require a trusted server or have prohibitive communication costs. I know at least one paper [3] that does not require either. Can the author comment on that?\n[3] El-Mhamdi, E. M., Guerraoui, R., Guirguis, A., Hoang, L. N., & Rouault, S. (2020, July). Genuinely distributed byzantine machine learning. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 355-364).\n\n2. The third paragraph on page 6 is problematic. The authors mentioned an attack in which the system removes one Byzantine and one benign node. In this case, the Byzantines can do this attack until 2f nodes are removed (with f being the original number of Byzantines). Since the algorithm requires n > 2f+1 then, in extreme cases, this attack leaves the system with only 1 node! In other words, the authors seem to acknowledge that a Byzantine node can defeat the distribution of the algorithm, making it behave as if there is only one central node.\n\n3. I do not understand the last line of Section 2.1. Why does **each** peer require O(dn) in the PS architecture? I believe each one requires only 2d: 1d to upload the gradient and 1d to download the model. Can you please clarify this?\n\n4. The first sentence of Section 3.1 (\"The core design principle behind our algorithm is that all types of Byzantine faults must have limited effect and a chance of being discovered.\") is a bit weird. Usually, Byzantine attacks are posed as the strongest attack to diverge learning. It is strong because Byzantine peers can do whatever they want (i.e., it's also called: behave arbitrarily).\n\n5. It's not clear if clipping is effective against random attacks? I understand it will be robust against gradients with big magnitudes (like the attacks in the evaluation section) but what about the other attacks?\n\n6. It's not clear how the butterfly method works? If you only broadcast a part of the gradient, then what is aggregated in this case? Is it only the local part of a peer and a corresponding part received from another peer?\n\n7. In Algorithm 2, a Byzantine can equivocate as follows. It can send different hashes (for the same part of the gradient) to different peers. It can then send different values for that part to different peers so that the hashes match the received gradients on each peer. Is that a problem for your algorithm?\n\n8. The validation step is not rigorous because you might be unlucky and get the Byzantine node to validate another Byzantine node in one iteration. Clearly, Byzantines can get away with their attack (without being caught) in this iteration. What are the practical/theoretical results of such a situation?\n\n9. The solution to Sybil attacks (in Section 3.2) is not convincing. A Byzantine node can prove its honesty only to enter the system and then it can do whatever it wants. This problem (i.e., tolerating Sybil attacks) is interesting and I encourage the authors to give it more discussion in the main paper.\n\n10. The authors seem to rely on (Karimireddy et al., 2020) a lot. What are the main differences between this work compared to this work? Is it only PS architecture vs. decentralized architecture? If so, what are the additional challenges that you solved?\n\n11. The federated learning (FL) example in the motivation does not fit nicely. As mentioned in the paper, one important aspect of FL is data privacy yet, the solution in the paper relies on the assumption that the dataset is public and can be accessible by anybody. I advise the authors to remove FL from their motivating examples.\n\n12. The authors chose the clipping value (\\tau) based on out-of-band experiments. Can the authors add a discussion on how to choose a clipping value practically (without initial experiments)?\n\n13. What are the coordinate-wise trimmed median and geometric median baselines? It's clear how to use these aggregators with a central server yet, they are not well-defined in the decentralized case. If the authors are referring to some work in the literature, please add the necessary citations.\n\n14. As the authors mentioned, they use only specific parts of MPC rather than a fully-fledged MPC protocol. I suggest the authors do not use this term and use specific terms of the specific algorithms they use instead.\n\n15. The expression \"zero trust assumption\" is a bit of a stretch. For example, you need at least 50% of honest peers.\n\n16. What is the percentage of the validators (i.e., what is the inequality between m and n)? How does this percentage affect the correctness of the algorithm?\n\n17. The authors mentioned that m validators will validate the work of m peers. It seems from the evaluation section that there is a one-to-one mapping, in this case, i.e., each validator validates one peer. Please make this clear while describing the algorithm.\n\n18. How can one report a Byzantine node? This again requires consensus, right?\n\n19. It will be great if the authors can add to the paper an explanation of how CenteredClip works.\n\n20. I suggest you better explain \\tau in Equation (2). Currently, it is not clear in the text; I understood what it means only in the evaluation section.\n\n21. In Algorithm 2, Step 7: you either mean \"broadcast\" instead of \"send\" or you mean g_i[j] instead of g_i. The same fro Step 8. I believe you mean the latter though (given Step 9 is \"MERGE\" rather than \"AGGREGATE\").\n\n22. A few important function definitions are missing: CenteredClip, ValidatePeer, VoteForBan, and Ban. Other functions are also missing, but they are less important.\n\n23. Footnote 4 is a bit off because the paper does not consider the heterogeneous case.\n\n24. I do not buy the omission of \"common low-magnitude attacks (Baruch et al., 2019; Xie et al., 2020; Allen-Zhu et al., 2021)\". These are the SOTA attacks, and it is important to show how your algorithm behaves under these attacks.\n\n25. What is the attack in Figure 2 (first two figures)?\n\n26. The upper-middle plot of Figure 2 shows that the geometric median is almost as good as your algorithm. What is the benefit of your algorithm in this case?\n\n27. Why does the coordinate-wise median diverge in the upper-left figure in Fig. 2?", "summary_of_the_paper": "The paper proposes BTARD-SGD, which is a Byzantine-tolerant training algorithm (via stochastic gradient descent) in decentralized environments (i.e., peer-to-peer architectures). BTARD-SGD does not require the presence of a trusted central server and introduces only a marginal overhead compared to a vanilla All-Reduce SGD algorithm. BTARD-SGD relies on an existing clipping algorithm in the literature called CenteredClip in addition to a series of checks to catch Byzantine nodes which might not follow the algorithm. The authors provide theoretical analysis in addition to a fair amount of experiments.", "summary_of_the_review": "Though the paper addresses a very important and timely problem, I believe it cannot be accepted as-is as it requires to be revised in a few aspects. In summary, (1) the authors make several assumptions that seem unrealistic and unjustified. (2) The most important parts of the paper are deferred to the appendices; this makes it hard to understand the algorithm and to see its benefits. (3) As the main aim of the paper is to provide a computationally efficient algorithm, the paper should give clearly the computation complexity of all parts of the algorithm. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Uzr-r89Xc2L", "reviewer": "Reviewer_38p5", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "### Strengths\n\n[Significance]\n\nAll reduce is a very popular architecture for large scale distributed training with the case of Byzantine tolerance being an open problem. The results of this paper are important.\n\n[Novelty] \n\nThe proposal builds on multiple existing schemes that come from both the ML optimization literature (centered clip, butterfly all reduce) and distributed algorithms (e.g., DHT, MPRNG).\n\n[Quality] \n\nThere is sufficient technical depth for the main claims of the paper (both for theoretical guarantees and for system design choices). The authors discuss their main assumptions and clarify cases in which they don't apply. \n\n[Presentation / Clarity]\n\nThe paper is well written and easy to follow. Parameter choices are provided and the extensive supplementary material contain the necessary details for the proofs and complementary explanations of the method.\n\n### Weaknesses\n\n[Significance]\n\n- The assumptions needed for the algorithm, prohibit an extension of the work to a setup with decentralized data (such as in federated learning). The problem of Byzantine tolerance is less motivated in the case where each node can access the entire training dataset as in this case it is often preferable to scale out in a more controlled environment (e.g., data centers) where crash failures are present but Byzantine ones are much less likely to occur. The strict IID assumptions for the paper are limiting. Convergence guarantees can still be achieved with some bound on the dissimilarity among the datasets as in practice the datasets are not arbitrarily different. Byzantine-resilient learning on decentralized data is a challenging yet open problem. For reference see the submission and discussion here: https://openreview.net/forum?id=7JSTDTZtn7-\n\n- The reputation system for nodes that join and leave introduces another limitation for the proposal, as it requires an additional application-dependent hyperparameter (T).\n\n[Evaluation] \n\n- The paper targets the large-scale setup. However, there is no evaluation of the scalability of the proposal and only experiments with up to 16 participants are shown. \n\n- Missing experimental results for the case of nodes joining.\n\n", "summary_of_the_paper": "This paper introduces BTARD-SGD as a new algorithm for distributed training among untrusted Byzantine nodes. The underlying all reduce architecture makes the proposal appealing for large scale applications due to the reduction in the communication cost. The paper contains a convergence analysis for convex and non-convex loss functions and a proof for resilience against Byzantine and Sybil attacks. The authors verify the efficacy of their proposal on image classification and NLP tasks.", "summary_of_the_review": "Although the paper has some significant weaknesses, I tend to recommend an acceptance given the technical depth and significance of the problem addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Sjng72CqEct", "reviewer": "Reviewer_w1BH", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "+The paper develops a careful protocol utilizing cryptographic primitives (MPC), unlike similar works that mainly aim to eliminate byzantine behavior by comparing the gradients provided by various nodes. The utilization of  MPC is novel, and the provable convergence guarantee is a strength of the paper. \n+/- While the paper's protocols work only in the case where nodes are able to sample i.i.d. from the overall data set (the \"homogenous\" setting), the paper refers to recent lower bounds that preclude byzantine tolerant algorithms in the heterogenous setting (at least in the worst-case).   \n- The implementation of the cryptographic primitives to keep the byzantine behavior in check requires a number of all-to-all communication exchange. While the lack of a centralized trusted node is expected to make the protocols more expensive, a key missing ingredient of the paper is an explicit accounting for this communication cost. I believe it will greatly improve the contribution if this cost is explicitly characterized and reported.\n- The algorithm explanation could improve in terms of clarity. For instance, the paper refer's to a butterfly all reduce procedure, which seems to suggest that each node receives the sum of all the numbers (gradients) that are transmitted in the step. However, the descriptions in Algorithms 1,2, only include \"Send\" and \"Receive\" primitives, and the algorithms in the appendix do not seem to do aggregation as a part of the communication primitives - it is done separately and explicitly in the centeredclip procedure. This can be explained more clearly. Note that the peer-to-peer communication (i.e., n^2 different messages being sent) also has an impact on the communication cost (referred to above). \n- The paper seems to provide distinct converge behavior for the case where the number of byzantine adversaries is explicitly known. A clear/intuitive explanation of why the behavior is distinct can enhance the paper.  \n", "summary_of_the_paper": "The paper develops a byzantine resilient algorithm for distributed training via SGD without a trusted centralized node. The key idea is that it improves upon recent decentralized algorithms by using cryptographic primitives. In particular, a multiparty random number generator is used to randomly verify subsets of devices in each iteration, enabling the algorithm to learn byzantine behavior that deviates sufficiently from the protocol. The paper provides rigorous theoretical result in terms of convergence guarantee, with a rate that depends on the number of byzantine adversaries. The derived rate depends on the fraction of nodes that are byzantine (capped by 50%, which is standard in this literature). In cases where no node is adversarial, the derived convergence rate matches that of the standard algorithms.", "summary_of_the_review": "Overall solid piece of work. It is worth considering the paper modulo addressing the comments above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KbttF_2rWrx", "reviewer": "Reviewer_ojVo", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper addresses a very interesting task of machine learning under a decentralized setting. As the authors mention, ensuring Byzantine fault tolerance in the learning system is very hard under a general learning setting. Some of the requirements will need to be relaxed, as is the case in recent decentralized learning works (just a few examples: I know they do not discuss Bizantine):\n\n- Tran et al., \"An efficient approach for privacy preserving decentralized deep learning models based on secure multi-party computation,\" Neurocomputing 422(2021) 245-262\n- Ide et al., \"Efficient Protocol for Collaborative Dictionary Learning in Decentralized Networks,\" Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 19,  August 10-16, Macao, China), pp.2585-2591\n \nIn this paper, the authors use leader selection schemes for \"validator\" and \"accuse\", which does not make the protocol entirely decentralized even if the selection is random. The authors need to clarify the main challenge of the existing methods and the key achievement of the paper. The first half of the paper does not look very successful in clarifying research motivation.\n\nQuestions \np.3\n\"that permutation-invariant algorithms cannot converge to any predefined accuracy of the solution\" sounds unreasonable because the original aggregation is permutation symmetric. Please elaborate. \n \np.4\nIs there any risk assessment of the validator selection step?\n \np.5\nNo definition of Split.\n", "summary_of_the_paper": "This paper seems to propose a new use-case of an existing Byzantine fault-tolerant protocol called CenteredClip in a federated learning setting. Although the authors state that their approach fits the decentralized learning setting, the protocol relies on some sort of leader selection.\n \nThe authors bring CenterClip's equation without explaining the problem setting to a reasonable clarity. It seems the use of multi-party random number generation for Eq.(1) is the main novelty, but its context is not clear.\n \nThe authors make two assumptions on the objective function on which distributed members strive to compute the gradient, but the novelty and the context are unclear.", "summary_of_the_review": "- unclear description\n- limited novelty", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CbD8YgYB0i-", "reviewer": "Reviewer_yAgj", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "While there are a large number of papers on Byzantine robustness in the parameter server setting, there are relatively few papers for the decentralized setting. In this sense, the paper is timely and relevant. However, the paper lacks in giving sufficient details, which makes it difficult to understand the contributions and novelty. Detailed comments are as follows.\n\nMajor comments:\n\n1. How can one ensure that the policy on page 6 where a worker can eliminate one other worker along with themselves, cannot be exploited by Byzantine workers? Can it happen that a Byzantine worker b eliminates an honest worker h, and ensures that another honest worker h’ eliminates b. In this case, (b,h) and (b,h’) will be eliminated. In other words, Byzantine worker b could eliminate two honest workers. It needs a proof that this type of attacks are not possible. Moreover, since the setup is decentralized how consensus happens to determine if a pair of workers to be eliminated. It will be important to give more details.\n\n2. What is the computation and communication complexity at each peer for BTARD? Validators need to recompute the gradients, and in addition, in case if a peer accuses another peer, all other peers need to recompute the gradient. This suggests huge computation overhead. Would this recalculation of gradients outweigh the benefits of parallelism? It is crucial to quantify computation and communication costs explicitly. \n\nMoreover, how much additional communication cost is incurred by using secure broadcast and MPRNG? Appendices A.2.1 and A.2.2 treat these primitives at a very high level. It would be helpful to select a suitable protocol from the literature, and give enough details.\n\n3. In experiments, baseline methods include coordinate-wise median and geometric median, How are these computed in the decentralized setting? It will be important to give more details. \n\n4. How much improvement the proposed BTARD algorithm gives as compared to baseline methods? From Figures 2 and 3, it seems like the improvements are very marginal. Can the authors quantify the improvements in terms of percentage increase in accuracy (or decrease in loss), and add a discussion on comparison?\n\n5. The authors mention that they omit common (and powerful) attacks in [Baruch et al. 2019, Xie et al. 2020, Allen-Zhu et al. 2021] as these attacks are designed to bypass certain checks, which are not used by the proposed algorithm. The proposed algorithm does not use variance and magnitude checks does not mean that these attacks will fail. These attacks were proposed to show inefficiency of several well-known Byzantine robust schemes such as Krum and coordinate-wise median. So, it will be important to test BTARD against some of these attacks.\n\nOther comments:\n\n1. The paper assumes that training is performed on a public dataset, which can be accessed by all peers. It would be helpful to justify this assumption. In the Byzantine robustness literature, many papers consider data parallelism, where data is distributed across peers. In such a setup, it would not be possible to validate by recalculating gradient. It would be helpful to add a discussion on this assumption. \n\n2. The paper does not formally introduce the decentralized training setup being considered. How many peers in total, and how many are Byzantine? Can any peer talk with any other peer? Can Byzantine peers collude? A few details are given in Sec. 3.2 after the proposed methods. It will be important to describe these details up front.\n\n3. The authors do not give any description or details about Algorithms 1-3 in the main text. It is difficult to understand the algorithms, and takes a long time for the reader. \n", "summary_of_the_paper": "The paper considers the problem of decentralized training in the presence of Byzantine peers. The paper proposes a Byzantine-tolerant algorithm which uses randomly chosen peers as validators. A validator recomputes the gradient and ‘accuses’ a peer if the computation is not correct. Towards this end, the paper proposes to leverage two primitives from secure Multi-Party Computation (MPC) literature: secure broadcast and multi-party random number generator. For robust aggregation, the paper relies on Centered Clipping proposed recently in [Karimireddy et al. 2020].", "summary_of_the_review": "The paper considers a challenging problem of Byzantine-tolerant learning in the decentralized setup (without a parameter server). However, the paper lacks in many details and does not quantify costs and gains of the proposed algorithm.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents promising and ambitious work in the context of Byzantine-tolerant learning in the decentralized setup. The reviews raised several critical points of concern: completeness of technical derivations and details, experimental results and comparisons to other work, excluding several state of the art attacks. The reviewers provided with a generous amount of feedback, that should be incorporated in the paper before publication. Unfortunately the camera ready timeline is quite sort for such an extensive feedback to be integrated in this paper.  The authors are urged to resubmit after taking into account all the suggestions that were made during this review cycle.
Decision: Reject