Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)
Year: 2022

Abstract:
We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others’ local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborative learning is equivalent to a new form of agreement, which we call averaging agreement. In this problem, nodes start each with an initial vector and seek to approximately agree on a common vector, which is close to the average of honest nodes’ initial vectors. We present two asynchronous solutions to averaging agreement, each we prove optimal according to some dimension. The first, based on the minimum-diameter averaging, requires n ≥ 6f+1, but achieves asymptotically the best-possible averaging constant up to a multiplicative constant. The second, based on reliable broadcast and coordinate-wise trimmed mean, achieves optimal Byzantine resilience, i.e., n ≥ 3f + 1. Each of these algorithms induces an optimal Byzantine collaborative learning protocol. In particular, our equivalence yields new impossibility theorems on what any collaborative learning algorithm can achieve in adversarial and heterogeneous environments.

heading: 1 Introduction
text: The distributed nature of data, the prohibitive cost of data transfers and the privacy concerns all call for collaborative machine learning. The idea consists for each machine to keep its data locally and to “simply” exchange with other machines what it learned so far. If all machines correctly communicate and execute the algorithms assigned to them, collaborative learning is rather easy. It can be achieved through the standard workhorse optimization algorithm: stochastic gradient descent (SGD) [37], which can be effectively distributed through averaging [26].
∗Authors are listed alphabetically.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
But in a practical distributed setting, hardware components may crash, software can be buggy, communications can be slowed down, data can be corrupted and machines can be hacked. Besides, large-scale machine learning systems are trained on user-generated data, which may be crafted maliciously. For example, recommendation algorithms have such a large influence on social medias that there are huge incentives from industries and governments to fabricate data that bias the learning algorithms and increase the visibility of some contents over others [6, 33]. In the parlance of distributed computing, “nodes" can be Byzantine [28], i.e., they can behave arbitrarily maliciously, to confuse the system. Given that machine learning (ML) is now used in many critical applications (e.g., driving, medication, content moderation), its ability to tolerate Byzantine behavior is of paramount importance.
In this paper, we precisely define and address, for the first time, the problem of collaborative learning in a fully decentralized, Byzantine, heterogeneous and asynchronous environment with non-convex loss functions. We consider n nodes, which may be machines or different accounts on a social media. Each node has its own local data, drawn from data distributions that may greatly vary across nodes. The nodes seek to collectively learn from each other, without however exchanging their data. None of the nodes is trusted, and any f < n nodes can be Byzantine.
Contributions. We first precisely formulate the collaborative learning problem. Then, we give our main contribution: an equivalence between collaborative learning and a new more abstract problem we call averaging agreement. More precisely, we provide two reductions: from collaborative learning to averaging agreement and from averaging agreement to collaborative learning. We prove that both reductions essentially preserve the correctness guarantees on the output. The former reduction is the most challenging one to design and to prove correct. First, to update nodes’ models, we use averaging agreement to aggregate nodes’ stochastic gradients. Then, to avoid model drift, we regularly “contract” the nodes’ models using averaging agreement. To prove correctness, we bound the diameter of honest nodes’ models, and we analyze the effective gradient [12]. We then carefully select a halting iteration, for which correctness can be guaranteed.
Our tight reduction allows to derive both impossibility results and optimal algorithms for collaborative learning by studying the “simpler” averaging agreement problem. We prove lower bounds on the correctness and Byzantine resilience that any averaging agreement algorithm can achieve, which implies the same lower bounds for collaborative learning. We then propose two optimal algorithms for averaging agreement. Our first algorithm is asymptotically optimal with respect to correctness, up to a multiplicative constant, when nearly all nodes are honest. Our second algorithm achieves optimal Byzantine resilience. Each of these algorithms induces an optimal collaborative learning protocol.
While our algorithms apply in a very general setting, they can easily be tweaked for more specific settings with additional assumptions, such as the presence of a trusted parameter server [30], the assumption of homogeneous (i.e. i.i.d.) local data or synchrony (Section 3.3 and Section 6).
We implemented and evaluated our algorithms in a distributed environment with 3 ResNet models [24]. More specifically, we present their throughput overhead when compared to a non–robust collaborative learning approach with both i.i.d. and non–i.i.d. data (i.e. we highlight the cost of heterogeneity). Essentially, we show that our first algorithm is more lightweight with a slowdown of at most 1.7X in the i.i.d. case and almost the triple in the non–i.i.d. case. Our second algorithm adds slightly more than an order of magnitude overhead: here the non-i.i.d. slowdown is twice the i.i.d. one.
Related work: Byzantine learning. Several techniques have recently been proposed for Byzantine distributed learning, where different workers collaborate through a central parameter server [30] to minimize the average of their loss functions [26]. In each round, the server sends its model parameters to the workers which use their local data to compute gradients. Krum and Multi-Krum [4] use a distance–based scheme to eliminate Byzantine inputs and average the remaining ones. Median-based aggregation alternatives were also considered [38]. Bulyan [13] uses a meta–algorithm against a strong adversary that can fool the aforementioned aggregation rules in high–dimensional spaces. Coding schemes were used in Draco [8] and Detox [35]. In [2], quorums of workers enable to reach an information theoretical learning optimum, assuming however a strong convex loss function. Kardam [9] uses filters to tolerate Byzantine workers in an asynchronous setting. All these approaches assume a central trusted (parameter server) machine.
The few decentralized approaches that removed this single point of failure, restricted however the problem to (a) homogeneous data distribution, (b) convex functions, and/or (c) a weak (non–
Byzantine) adversary. MOZI [22] combines a distance–based aggregation rule with a performance– based filtering technique, assuming that adversaries send models with high loss values, restricting thereby the arbitrary nature of a Byzantine agent that can craft poisoned models whose losses are small only with respect to the honest nodes’ incomplete loss functions. The technique is also inapplicable to heterogeneous learning, where nodes can have a biased loss function compared to the average of all loss functions2. BRIDGE [39] and ByRDiE [40] consider gradient descent (GD) and coordinate descent (CD) optimizations, respectively. Both rely on trimmed–mean to achieve Byzantine resilience assuming a synchronous environment and strongly convex loss functions3 with homogeneous data distribution (i.i.d.). In addition, none of their optimization methods is stochastic: at each step, each node is supposed to compute the gradient on its entire local data set. ByzSGD [12] starts from the classical model of several workers and one server, which is then replicated for Byzantine resilience. It is assumed that up to 1/3 of the server replicas and up to 1/3 of the workers can be Byzantine, which is stronger than what we assume in the present paper where nodes play both roles and tolerate any subset of 1/3 Byzantine nodes. More importantly, ByzSGD assumes that all communication patterns between honest servers eventually hold with probability 1; we make no such assumption here. Additionally, our present paper is more general, considering heterogeneous data distributions, as opposed to [12]. Furthermore, heterogeneity naturally calls for personalized collaborative learning [14, 23, 10, 15], where nodes aim to learn local models, but still leverage collaborations to improve their local models. Interestingly, our general scheme encompasses personalized collaborative learning.
Maybe more importantly, our reduction to averaging agreement yields new more precise bounds that improve upon all the results listed above. These are we believe of interest, even in more centralized, homogeneous, synchronous and convex settings. In particular, our reduction can easily be adapted to settings where parameter servers and workers with local data are different entities, as in [12].
Related work: Agreement. A major challenge in collaborative learning is to guarantee "some" agreement between nodes about the appropriate parameters to consider. Especially in non-convex settings, this is critical as, otherwise, the gradients computed by a node may be completely irrelevant for another node. The agreement could be achieved using the traditional consensus abstraction [28]. Yet, consensus is impossible in asynchronous environments [18] and when it is possible (with partial synchrony), its usage is expensive and would be prohibitive in the context of modern ML models, with a dimension d in the order of billions. In fact, and as we show in this paper, consensus is unnecessary.
An alternative candidate abstraction is approximate agreement. This is a weak form of consensus introduced in [11] where honest nodes converge to values that are close to each other, while remaining in the convex hull of the values proposed by honest nodes. In the one-dimensional case, optimal convergence rate has been achieved in both synchronous [16] and asynchronous environments [17], while optimal asynchronous Byzantine tolerance was attained by [1]. The multi-dimensional version was addressed by [31], requiring however nd local computations in each round, and assuming n > f(d+ 2). This is clearly impractical in the context of modern ML.
By leveraging some distributed computing techniques [36, 1], we prove that collaborative learning can be reduced to averaging agreement, which is even weaker than approximate agreement. This enables us to bring down the requirement on the number of honest nodes from n > f(d + 2) to n > 3f , and only require linear computation time in d.
Structure. The rest of the paper is organized as follows. In Section 2, we precisely define the problems we aim to solve. Section 3 states our main result, namely, the equivalence between collaborative learning and averaging agreement. Section 4 describes our two solutions to averaging agreement, and proves their optimality. Section 5 reports on our empirical evaluation and highlight important takeaways. Finally, Section 6 concludes. The full proofs are provided in the supplementary material, as well as the optimized algorithm for homogeneous local data.
2Besides, MOZI, focusing on convex optimization, assumes that eventually, models on honest nodes do not drift among each others, which may not hold for Byzantine nodes could influence the honest models to drift away from each other [3].
3Convexity greatly helps, as the average of good models will necessarily be a good model. This is no longer the case in non-convex optimization, which includes the widely used neural network framework.

heading: 2 Model and Problem Definitions

heading: 2.1 Distributed computing assumptions
text: We consider a standard distributed computing model with a set [n] = {1, . . . , n} of nodes, out of which h are honest and f = n− h are Byzantine. For presentation simplicity, we assume that the first h nodes are honest. But crucially, no honest node knows which h− 1 other nodes are honest. The f Byzantine nodes know each other, can collude, and subsequently know who the h remaining honest nodes are. Essentially, we assume a single adversary that controls all the Byzantine nodes. These nodes can send arbitrary messages, and they can send different messages to different nodes. In the terminology of distributed computing, the adversary is omniscient but not omnipotent. Such an adversary has access to all learning and deployment information, including the learning objective, the employed algorithm, as well as the dataset. We consider a general asynchronous setting [5]: the adversary can delay messages to honest nodes: no bound on communication delays or relative speeds is assumed. We denote BYZ the algorithm adopted by the adversary. Yet, we assume that the adversary is not able to delay all messages indefinitely [7]. Besides, the adversary is not able to alter the messages from the honest nodes, which can authenticate the source of a message to prevent spoofing and Sybil attacks.
Also for presentation simplicity, we assume that processes communicate in a round-based manner [5]. In each round, every honest node broadcasts a message (labelled with the round number) and waits until it successfully gathers messages from at most q ≤ h other nodes (labelled with the correct round number), before performing some local computation and moving to the next round. Even though the network is asynchronous, each round is guaranteed to eventually terminate for all honest nodes, as the h honest nodes’ messages will all be eventually delivered. Evidently, however, some of them may be delivered after the node receives q messages (including Byzantine nodes’). Such messages will fail to be taken into account. Our learning algorithm will then rely on main rounds (denoted t in Section 3), each of which is decomposed into sub-rounds that run averaging agreements.

heading: 2.2 Machine learning assumptions
text: We assume each honest node j ∈ [h] has a local data distribution Dj . The node’s local loss function is derived from the parameters θ ∈ Rd, the model and the local data distribution, typically through L(j)(θ) = E x∼Dj [`(θ, x)], where `(θ, x) is the loss for data point x, which may or may not include some regularization of the parameter θ. Our model is agnostic to whether the local data distribution is a uniform distribution over collected data (i.e., empirical risk), or whether it is a theoretical unknown distribution the node can sample from (i.e., statistical risk). We make the following assumptions about this loss function. Assumption 1. The loss functions are non-negative, i.e., L(j) ≥ 0 for all honest nodes j ∈ [h]. Assumption 2. The loss functions are L-smooth, i.e., there exists a constant L such that
∀θ, θ′ ∈ Rd, ∀j ∈ [h], ∥∥∥∇L(j) (θ)−∇L(j) (θ′)∥∥∥
2 ≤ L ‖θ − θ′‖2 . (1)
Assumption 3. The variance of the noise in the gradient estimations is uniformly bounded, i.e.,
∀j ∈ [h], ∀θ ∈ Rd, E x∼Dj ∥∥∥∇θ`(θ, x)−∇L(j)(θ)∥∥∥2 2 ≤ σ2. (2)
Moreover, the data samplings done by two different nodes are independent. Assumption 4. There is a computable bound Lmax such that, at initial point θ1 ∈ Rd, for any honest node j ∈ [h], we have L(j)(θ1) ≤ Lmax.
While the first three assumptions are standard, the fourth assumption deserves further explanation. Notice first that θ1 is a given parameter of our algorithms, which we could, just for the sake of the argument, set to 0. The assumption would thus be about the value of the local losses at 0, which will typically depend on the nodes’ local data distribution. But losses usually depend on the data only as an average of the loss per data point. Moreover, the loss at 0 for any data point is usually bounded. In image classification tasks for example, each color intensity of each pixel of an input image has a bounded value. This usually suffices to upper-bound the loss at 0 for any data point, which then yields Assumption 4.
In iteration t, we require each node to average the stochastic gradient estimates over a batch of bt i.i.d. samples. As a result, denoting θ(j)t and g (j) t , 1 bt ∑ i∈[bt]∇θ`(θ (j) t , x (j) t,i ) node j’s parameters and computed stochastic gradient in iteration t, we have
E x∼Dj ∥∥∥g(j)t −∇L(j)(θ(j)t )∥∥∥2 2 ≤ σ 2 bt , σ2t . (3)
As t grows, we increase batch size bt up to Θ(1/δ2) (where δ is a parameter of the collaborative learning problem, see Section 2.3), so that σt = O(δ) for t large enough (see Remark 2). This allows to dynamically mitigate the decrease of the norm of the true gradient. Namely, early on, while we are far from convergence, this norm is usually large. It is then desirable to have very noisy estimates, as these can be obtained more efficiently, and as the aggregation of these poor estimates will nevertheless allow progress. However, as we get closer to convergence, the norm of the true gradient becomes smaller, making the learning more vulnerable to Byzantine attacks [3]. Increasing the batch size then becomes useful. Our proofs essentially formalize this intuition. Note that, in the homogeneous setting, [25] theoretically proves that leveraging Momentum reduces variance and prevents Byzantine attacks without increasing the batch size, while [32] observes on several hundred experimental settings that Momentum indeed often offsets, or even cancels out, the effects of Byzantine attacks.

heading: 2.3 Collaborative learning
text: Given the `2 diameter ∆2(~θ) = maxj,k∈[h] ∥∥θ(j) − θ(k)∥∥
2 , collaborative learning consists in minimizing the average L̄ ( θ̄ ) , 1h ∑ j∈[h] L(j) ( θ̄ ) of local losses at the average θ̄ , 1h ∑ j∈[h] θ
(j), while guaranteeing that the honest nodes’ parameters have a small diameter.
This general model encompasses to the personalized federated learning problem introduced by [14, 23, 10, 15]. For instance, in [23], each node j aims to learn a local model xj that minimizes fj , with a penalty λ2 ‖xj − x̄‖ 2 2 on their distance to the average x̄ of all models. This framework can be restated by considering that nodes must agree on a common parameter θ = x̄, but have local losses defined by L(j) (θ) , minxj fj(xj) + λ2 ‖xj − θ‖ 2 2. The problem of [23] then boils down to minimizing the average of local losses. Definition 1. An algorithm LEARN solves the Byzantine C-collaborative learning problem if, given any local losses L(j) for j ∈ [h] satisfying assumptions (1,2,3,4) and any δ > 0, no matter what Byzantine attack BYZ is adopted by Byzantines, LEARN outputs a vector family ~θ of honest nodes such that
E∆2(~θ)2 ≤ δ2 and E ∥∥∇L̄ (θ̄)∥∥2
2 ≤ (1 + δ)2C2K2, (4) where K , supj,k∈[h], supθ∈Rd ∥∥∇L(j) (θ)−∇L(k) (θ)∥∥ 2 is the largest difference between the true local gradients at the same parameter θ, and where the randomness comes from the algorithm (typically the random sampling for gradient estimates).
In our definition above, the constant K measures the heterogeneity of local data distributions. Intuitively, this also captures the hardness of the problem. Indeed, the more heterogeneous the local data distributions, the more options Byzantine nodes have to bias the learning, the harder it is to learn in a Byzantine-resilient manner. Interestingly, for convex quadratic losses, our guarantee implies straightforwardly an upper-bound on the distance to the unique optimum of the problem, which is proportional to the hardness of the problem measured by K. In fact, our equivalence result conveys the tightness of this guarantee. In particular, the combination of our equivalence and of Theorem 5 implies that, for any ε > 0, asynchronous (2f/h− ε)-collaborative learning is impossible.

heading: 2.4 Averaging agreement
text: We address collaborative learning by reducing it to a new abstract distributed computing problem, which we call averaging agreement. Definition 2. A distributed algorithm AVG achieves Byzantine C-averaging agreement if, for any inputN ∈ N, any vector family ~x ∈ Rd·h and any Byzantine attack BYZ, denoting ~y , AVGN (~x,BYZ) the output of AVG given such inputs, we guarantee
E∆2(~y)2 ≤ ∆2(~x)
2
4N and E ‖ȳ − x̄‖22 ≤ C 2∆2(~x) 2, (5)
where ȳN = 1 h ∑ j∈[h] y (j) N is the average of honest nodes’ vectors, and where the randomness comes from the algorithm. We simply say that an algorithm solves averaging agreement if there exists a constant C for which it solves C-averaging agreement.
In particular, for deterministic algorithms, C-averaging on input N ensures the following guarantee
∆2(~y) ≤ ∆2(~x)
2N and ‖ȳ − x̄‖2 ≤ C∆2(~x). (6)
In Section 4, we will present two solutions to the averaging agreement problem. These solutions typically involve several rounds. At each round, each node sends their current vector to all other nodes. Then, once a node has received sufficiently many vectors, it will execute a robust mean estimator to these vectors, the output of which will be their starting vector for the next round. The nodes then halt after a number of rounds dependent on the parameter N .

heading: 3 The Equivalence
text: The main result of this paper is that, for K > 0, C-collaborative learning is equivalent to C-averaging agreement. We present two reductions, first from collaborative learning to averaging agreement, and then from averaging agreement to collaborative learning.

heading: 3.1 From collaborative learning to averaging agreement
text: Given an algorithm AVG that solves Byzantine C-averaging agreement, we design a Byzantine collaborative learning algorithm LEARN. Recall that LEARN must take a constant δ > 0 as input, which determines the degree of agreement (i.e., learning quality) that LEARN must achieve.
All honest parameter vectors are initialized with the same random values (i.e., ∀j ∈ [h], θ(j)1 = θ1) using a pre-defined seed. At iteration t, each honest node j ∈ [h] first computes a local gradient estimate g(j)t given its local loss function L(j) (·) and its local parameters θ (j) t , with a batch size bt. But, instead of performing a learning step with this gradient estimate, LEARN uses an aggregate of all local gradients, which we compute using the averaging agreement algorithm AVG.
Recall from Definition 2 that AVG depends on a parameter which defines the degree of agreement. We set this parameter at N(t) , dlog2 te at iteration t, so that 1/4N(t) ≤ 1/t2. Denoting ~γt the output of −−→ AVGN(t) applied to vectors ~gt, we then have the following guarantee:
E∆2 (~γt) 2 ≤ ∆2 (~gt)
2
t2 and E ‖γ̄t − ḡt‖ 2 2 ≤ C 2∆2 (~gt) 2 , (7)
where the expectations are conditioned on ~gt. We then update node j’s parameters by θ (j) t+1/2 = θ (j) t − ηγ (j) t , for a fixed learning rate η , δ/12L. But before moving on to the next iteration, we run once again AVG, with its parameter set to 1. Moreover, this time, AVG is run on local nodes’ parameters. Denoting ~θt+1 the output of −−→ AVG1 executed with vectors ~θt+1/2, we then have
E∆2 ( ~θt+1 )2 ≤ ∆2(~θt+1/2) 2
4 and E ∥∥∥θ̄t+1 − θ̄t+1/2∥∥∥2 2 ≤ C2∆2(~θt+1/2) 2, (8)
where the expectations are conditioned on ~θt+1/2. On input δ, LEARN then runs T , TLEARN(δ) learning iterations. The function TLEARN(δ) will be given explicitly in the proof of Theorem 1, where we will stress the fact that it can be computed from the inputs of the problem4 (L, K, C, n, f , σt, Lmax and δ). Finally, instead of returning ~θTLEARN(δ), LEARN chooses uniformly randomly an iteration ∗ ∈ [TLEARN(δ)], using a predefined common seed, and returns the vector family ~θ∗. We recapitulate the local execution of LEARN (at each node) in Algorithm 1. We stress that on steps 6 and 8, when the averaging agreement algorithm AVG is called, the Byzantines can adopt any procedure BYZ, which
4Note that upper-bounds (even conservative) on such values suffice. Our guarantees still hold, though TLEARN(δ) would take larger values, which makes LEARN slower to converge to ~θ∗.
consists in sending any message to any node at any point based on any information in the system, and in delaying for any amount of time any message sent by any honest node. Note that, apart from this, all other steps of Algorithm 1 is a purely local operation.
Data: Local loss gradient oracle, parameter δ > 0 Result: Model parameters θ
1 Initialize local parameters θ1 using a fixed common seed; 2 Fix learning rate η , δ/12L; 3 Fix number of iterations T , TLEARN(δ); 4 for t← 1, . . . , T do 5 gt ← GradientOracle(θt, bt); 6 γt ← AVGN(t)(~gt,BYZ) // Vulnerable to Byzantine attacks 7 θt+1/2 ← θt − ηγt;
8 θt+1 ← AVG1 ( ~θt+1/2,BYZ ) // Vulnerable to Byzantine attacks
9 end 10 Draw ∗ ∼ U([T ]) using the fixed common seed; 11 Return θ∗;
Algorithm 1: LEARN execution on a honest node. Remark 1. In practice, it may be more efficient to return the last computed vector family, though our proof applies to a randomly selected iteration. Theorem 1. Under assumptions (1, 2, 3, 4) and K > 0, given a C-averaging agreement oracle AVG, on any input 0 < δ < 3, LEARN solves Byzantine C-collaborative learning.
The proof is quite technical, and is provided in the supplementary material. Essentially, it focuses on the average of all honest nodes’ local parameters, and on the effective gradients that they undergo, given the local gradient updates and the applications of the averaging agreement oracle AVG.
Remark 2. Our proof requires TLEARN(δ) = Θ ( δ−1 max { δ−2, (t 7→ sups≥t σs)−1(δ) }) . To
prevent the noise from being the bottleneck for the convergence rate, we then need σt = Θ(δ), so that TLEARN = Θ(δ−3). Interestingly, this can be obtained by, for example, setting bt , t, for t ≤ T1 = Θ(δ−2), and bt , T1 for t > T1, where T1 is precisely defined by the proof provided in the supplementary material. In particular, we do not need to assume that bt →∞.

heading: 3.2 Converse reduction
text: We also prove the converse reduction, from averaging agreement to collaborative learning. Theorem 2. Given a Byzantine C-collaborative learning oracle, then, for any δ > 0, there is a solution to Byzantine (1 + δ)C-averaging agreement.
The proof is given in the supplementary material. It is obtained by applying a collaborative learning algorithm LEARN to the local loss functions L(j)(θ) , ∥∥θ − x(j)∥∥2 2 .
This converse reduction proves the tightness of our former reduction, and allows to straightforwardly derive impossibility theorems about collaborative learning from impossibility theorems about averaging agreement. In particular, in the sequel, we prove that no asynchronous algorithm can achieve better than Byzantine h+2f−qh -averaging agreement. It follows that no algorithm can achieve better than Byzantine h+2f−qh -collaborative learning. Similarly, Theorem 6 implies the impossibility of Byzantine asynchronous collaborative learning for n ≤ 3f .

heading: 3.3 Particular cases
text: Trusted server. It is straightforward to adapt our techniques and prove the equivalence between averaging agreement and collaborative learning in a context with a trusted server. Our lower bounds for asynchronous collaborative learning still apply to C-averaging agreement, and thus to C-collaborative learning. Note, however, that the trusted server may allow to improve the speed of collaborative learning, as it no longer requires contracting the parameters of local nodes’ models.
Homogeneous learning. In the supplementary material, we propose a faster algorithm for i.i.d. data, called HOM-LEARN, which skips the averaging agreement of nodes’ gradients. Despite requiring fewer communications, HOM-LEARN remains correct, as the following theorem shows.
Theorem 3. Under assumptions (1, 2, 3, 4), for i.i.d. local data and given a C-averaging agreement oracle AVG, on input δ > 0, HOM-LEARN guarantees E∆2(~θ∗)2 ≤ δ2 and E ∥∥∇L (θ̄∗)∥∥22 ≤ δ2.

heading: 4 Solutions to Averaging Agreement
text: We now present two solutions to the averaging agreement problem, called MINIMUM–DIAMETER AVERAGING5 (MDA) and RELIABLE BROADCAST - TRIMMED MEAN (RB-TM), each thus inducing a solution to collaborative learning. We prove each optimal according to some dimension.

heading: 4.1 Optimal averaging
text: Given a family ~z ∈ Rd·q of vectors, MDA first identifies a subfamily SMDA(~z) of q − f vectors of minimal `2 diameter, i.e.,
SMDA(~z) ∈ arg min S⊂[q] |S|=q−f ∆2
( ~z(S) ) = arg min
S⊂[q] |S|=q−f
max j,k∈S ∥∥∥z(j) − z(k)∥∥∥ 2 . (9)
We denote ~z(MDA) ∈ Rd·(q−f) the subfamily thereby selected. MDA then outputs the average of this subfamily, i.e.,
MDA(~z) , 1 q − f ∑
j∈SMDA(~z)
z(j). (10)
On input N ∈ N, MDAN iterates MDA TMDA(N) = dN ln 2/ε̃e times on vectors received from other nodes at each communication round such that the output of round t will be the input of round t+ 1. The correctness of MDA is then ensured under the following assumption.
Assumption 5 (Assumption for analysis of MDA). There is 0 < ε < 1 such that n ≥ 6+2ε1−ε f . This then allows to set q ≥ 1+ε2 h+ 5+3ε 2 f . In this case, we define ε̃ , 2ε 1+ε .
Theorem 4. Under Assumption 5, MDA achieves Byzantine (2f+h−q)q+(q−2f)fh(q−f)ε̃ -averaging agreement.
The proof is given in the supplementary material. It relies on the observation that, because of the filter, no Byzantine vector can significantly harm the estimation of the average.
Remark 3. Although MDA runs in linear time in d, it runs in exponential time in q. Interestingly, assuming that each honest node fully trusts its computations and its data (which may not hold if parameter-servers do not compute gradients as in [30]), each honest node can use its own vector to filter out the f most dissimilar gradients in linear time in q, and can average out all remaining vectors. Using a similar proof as for MDA, the algorithm thereby defined can be shown to achieve asymptotically the same averaging constant as MDA, in the limit q f ; but it now runs in O(dq), (requiring however n ≥ 7f + 1).
Theorem 5. No asynchronous algorithm can achieve better than Byzantine h+2f−qh -averaging agreement.
The proof is given in the supplementary material. It relies on the quasi-unanimity lemma, which shows that if a node receives at least q − f identical vectors x, then it must output x. We then construct an instance where, because of this and of Byzantines, honest nodes cannot agree. Note that, as a corollary, in the regime q = h → ∞ and f = o(h), MDA achieves asymptotically the best-possible averaging constant, up to a multiplicative constant equal to 3/2.
5Introduced by [13] in the context of robust machine learning, it uses the same principle as the minimal volume ellipsoid, that was introduced by [36] in the context of robust statistics.

heading: 4.2 Optimal Byzantine resilience
text: Our second algorithm makes use of reliable broadcast6: each Byzantine node broadcasts only a single vector (the uniqueness property of reliable broadcast in [1]). We denote ~w ∈ Rd·n the family of vectors proposed by all nodes. For each j ∈ [h], w(j) = x(j) is the vector of an honest node, while a Byzantine node proposes w(j) for each j ∈ [h + 1, n]. Moreover, [1] showed the existence of a multi-round algorithm which, by using reliable broadcast and a witness mechanism, guarantees that any two honest nodes j and k will collect at least q similar inputs. Formally, denoting Q(j) ⊆ [n] the set of nodes whose messages were successfully delivered to node j (including through relays), the algorithm by [1] guarantees that
∣∣Q(j) ∩Q(k)∣∣ ≥ q for any two honest nodes j, k ∈ [h]. At each iteration of our RB-TM algorithm, each node j exploits the same reliable broadcast and witness mechanism techniques to collect other nodes’ vectors. Now, given its set Q(j) of collected messages, each node j applies coordinate-wise trimmed mean, denoted TM, as follows. For each coordinate i, it discards the f smallest i-th coordinates it collected, as well as the f largest. We denote ~z(j) = ~w(Q (j)) the subfamily received by node j, and S(~z(j)[i]) ⊂ [n] the subset of nodes whose i-th coordinates remain after trimming. Node j then computes the average y(j) of the i-th coordinates of this subset, i.e.
y(j)[i] , 1∣∣Q(j)∣∣− 2f ∑
k∈S(~z(j)[i])
w(k)[i]. (11)
RB-TM consists of iterating TM, on vectors received from other nodes at each communication round. Namely, given input N ∈ N, RB-TM iterates TM TRB-TM(N) times, where
TRB-TM(N) ,
⌈ (N + 1) ln 2 + ln √ h
ε̃
⌉ . (12)
The correctness of RB-TM can then be guaranteed under the following assumption. Assumption 6 (Assumption for analysis of RB-TM). There is ε > 0 such that n ≥ (3 + ε)f . We then set q = n− f , and define ε̃ , ε1+ε .
Theorem 6. Under Assumption 6, RB-TM guarantees Byzantine 4f√ h -averaging agreement. This is optimal in terms of Byzantine resilience. Indeed, for n ≤ 3f , no algorithm can achieve Byzantine averaging agreement.
The proof is provided in the supplementary material. The correctness relies on a coordinate-wise analysis, and on the study of a so-called coordinate-wise diameter, and its relation with the `2 diameter. The lower bound exploits the quasi-unanimity lemma. Note that while RB-TM tolerates more Byzantine nodes, its averaging constant is larger than that of MDA by a factor of O( √ h).

heading: 5 Empirical Evaluation
text: We implemented our collaborative learning algorithms using Garfield library [20] and PyTorch [34]. Each agreement algorithm comes in two variants: one assuming i.i.d. data (See supplementary material) and one tolerating non-i.i.d. data (Algorithm 1). In each case, the first variants require fewer communications. We report below on the empirical evaluation of the overhead of our four variants when compared to a non–robust collaborative learning approach. Our baseline is indeed a vanilla fully decentralized implementation in which all nodes share their updates with each other and then aggregate these updates by averaging (a deployment that cannot tolerate even one Byzantine node).
We focus on throughput, measuring the number of updates the system performs per second. As we consider an asynchronous network, we report on the fastest node in each experiment. We consider image classification tasks, using MNIST [29] and CIFAR-10 [27] datasets. MNIST is a dataset of handwritten digits with 70,000 28× 28 images in 10 classes. CIFAR-10 consists of 60,000 32× 32 colour images in 10 classes. We use batches of size 100, and we experimented with 5 models with different sizes ranging from simple models like small convolutional neural network (MNIST_CNN and Cifarnet), training a few thousands of parameters, to big models like ResNet-50 with around 23M
6Note that MDA can also be straightforwardly upgraded into RB-MDA to gain Byzantine resilience.
MNIST_CNN CifarNet Resnet-18 Resnet-34 Resnet-500
100
200
300
400
Sl ow
do w
n
225.7X
187.9X
24.1X 24.2X 21.7X12.2X 10.2X 1.7X 1.5X 1.5X
40.8X 37.6X
3.9X 4.6X 4.8X
317.0X
442.4X
46.1X 50.6X 49.5X
LEARN-iid-MDA LEARN-non-iid-MDA LEARN-iid-RB-TM LEARN-non-iid-RB-TM
Figure 2: Slowdown of our algorithms normalized to the vanilla baseline throughput.
parameters. Our experimental platform is Grid5000 [19]. We always employ nodes from the same cluster, each having 2 CPUs (Intel Xeon E5-2630 v4) with 14 cores, 768 GiB RAM, 2×10 Gbps Ethernet, and 2 Nvidia Tesla P100 GPUs. We set f = 1, except when deploying our vanilla baseline.
Figure 1 compares the convergence of our algorithms to the vanilla baseline w.r.t. the training epochs. We use 7 nodes in this experiment, and we train Resnet–18 with CIFAR10. We verify from this figure that our algorithms can follow the same convergence trajectory as the vanilla baseline. It is clear from the figure that the i.i.d. versions outperform the non-i.i.d. ones.
Figure 2 depicts the throughput overhead of our algorithms (with both i.i.d. and non-i.i.d. data) compared to our vanilla baseline, with 10 nodes from the same cluster. Three observations from this figure are in order. First, the MDA–based algorithm performs better than the RB-TM one. The reason is that the latter incurs much more communication messages than the former as the latter uses reliable broadcast and a witness mechanism. Second, tolerating Byzantine nodes with i.i.d. data is much cheaper than the non-i.i.d. case. The reason is that it is harder to detect Byzantine behavior when data is not identically distributed on the nodes, which translates into more communication steps. Third, the slowdown is much higher with small models (i.e., MNIST_CNN and Cifarnet). This is because the network bandwidth is not saturated by the small models in the vanilla case, where it gets congested with the many communication rounds required by our algorithms. On the other hand, with the larger models, the vanilla deployment saturates the network bandwidth, making the extra communication messages account only for linear overhead.
Finally, it is important to notice that our evaluation is by no means exhaustive and our implementation has not been optimized. Our goal was to give an overview of the relative overheads. With proper optimizations, we believe the actual throughput could be increased for all implementations.

heading: 6 Conclusion
text: We defined and solved collaborative learning in a fully decentralized, Byzantine, heterogeneous, asynchronous and non-convex setting. We proved that the problem is equivalent to a new abstract form of agreement, which we call averaging agreement. We then described two solutions to averaging agreement, inducing two original solutions to collaborative learning. Each solution is optimal along some dimension. In particular, our lower bounds for the averaging agreement problem provide lower bounds on what any collaborative learning algorithm can achieve. Such impossibility results would have been challenging to obtain without our reduction. Our algorithms and our impossibility theorems are very general but can also be adapted for specific settings, such as the presence of a trusted parameter server, the assumption of i.i.d. data or a synchronous context7. In the latter case for instance, our two algorithms would only require n ≥ 4f + 1 and n ≥ 2f + 1, respectively. Limitations and potential negative social impacts. Like all Byzantine learning algorithms, we essentially filter out outliers. In practice, this may discard minorities with vastly diverging views. Future research should aim to address this fundamental trade-off between inclusivity and robustness. We also note that the computation time of MDA grows exponentially with q, when f is a constant fraction of q.
7In the synchronous case of MDA, with q = n, n ≥ 4+2ε 1−ε f is sufficient to guarantee q ≥ 1+ε 2 h+ 5+3ε 2 f in
Assumption 5. Also, note that no synchronous algorithm can achieve better than f h -averaging agreement.
Acknowledgments and Disclosure of Funding
We thank Rafaël Pinot and Nirupam Gupta for their useful comments. This work has been supported in part by the Swiss National Science Foundation projects: 200021_182542, Machine learning and 200021_200477, Controlling the spread of Epidemics. Most experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

Review summaries:
The paper considers collaborative learning in an (asynchronous) decentralized setup in the presence of Byzantine nodes. The authors define two problems: Byzantine-robust collaborative learning and Byzantine-robust ‘averaging agreement’. The main contribution is to show an equivalence between these two problems. Then, the paper proposes two algorithms for averaging agreement, which yield Byzantine-robust collaborative learning solutions. Finally, the paper shows that when the number of Byzantine nodes is larger than 1/3, then no algorithm can achieve Byzantine averaging agreement. 

The paper presents algorithms for collaborative learning which are distributed and robust wrt Byzantine nodes as long as these do not exceed either 1/3 or 1/6 of the total number of nodes.  This result is achieved by proving the equivalence of two concepts the authors introduce, C-learning and C-averaging where C is a constant.  Computational results are provided to support the claims of the paper.

The authors present a study on Byzantine collaborative learning. In it, n nodes try to learn from each other’s data collectively and some f < n nodes can be adversarial to the learning process and are defined Byzantine. Such problem of collaborative learning is in a fully decentralised, Byzantine, heterogeneous and asynchronous environment with non-convex loss functions.  In the first part, the authors formulate the collaborative learning problem; They then present an equivalence between collaborative learning and a problem called averaging agreement via two reductions from the former to the latter and vice versa.  Their reduction proves useful to draw impossibility results and optimal algorithms for collaborative learning through the averaging agreement problem. Therefore, they then move on to define a Byzantine collaborative learning algorithm called LEARN that allows to solve a Byzantine collaborative learning problem given an averaging agreement problem. In the last section, the authors present and discuss some empirical evaluations.