Byzantine-robust Decentralized Learning via ClippedGossip
Authors: Lie He
Sai Praneeth Karimireddy
Martin Jaggi
Venue: Submitted to ICLR 2023 (2023)
Keywords: Byzantine-robustness
distributed machine learning
robustness
optimization
decentralized learning

Abstract: In this paper, we study the challenging task of Byzantine-robust decentralized training on arbitrary communication graphs. Unlike federated learning where workers communicate through a server, workers in the decentralized environment can only talk to their neighbors, making it harder to reach consensus and benefit from collaborative training. To address these issues, we propose an algorithm, termed ClippedGossip, for Byzantine-robust consensus and optimization, which is the first to provably converge to a $O(\delta_{\max}\zeta^2/\gamma^2)$ neighborhood of the stationary point for non-convex objectives under standard assumptions. Finally, we demonstrate the encouraging empirical performance of ClippedGossip under a large number of attacks.

Under review as a conference paper at ICLR 2023
BYZANTINE-ROBUST DECENTRALIZED LEARNING VIA CLIPPEDGOSSIP
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we study the challenging task of Byzantine-robus decentralized training on arbitrary communication graphs. Unlike federated learning where workers communicate through server, workers in the decentralized environment can only talk to their neighbors, making it harder to reach consensus and benefit from collaborative training. To address these issues, we propose CLIPPEDGOSSIP algorithm for Byzantine-robus: consensus and optimization, which is the first to provably converge 066max<2//7 neighborhood of the stationary point for non-convex objectives under standard assumptions. Finally, we demonstrate the encouraging empirical performance of CLIPPEDGOSSIP under large number of attacks.
INTRODUCTION
"Divide et impera".
Distributed training arises as an important topic due to privacy constraints of decentralized data storage (McMahan et al. [0177] Kairouz et al. (019). As the server- server-worker paradigm suffers from single point failure, there is growing amount of works on training in the absence of server (Lian et al. 2017 Nedic 2020 Koloskova al. 2020b). We are particularly interested in decentralized scenarios where direct communication may be unavailable due to physical constraints. For example, devices in a sensor network can only communicate devices within short physical distances.
failures-from malfunctioning or even malicious participants-arr ubiquitous in all kinds of dis- tributed computing. A Byzantine adversarial worker can deviate from the prescribed algorithm and send arbitrary messages and is assumed to have the knowledge of the whole system (Lamport et al. 2019). It means Byzantine workers not only collude. but also know the data, algorithm. and models of all regular workers. However, they cannot directly modify the states on regular workers, nor compromise messages sent between two connected regular workers.
Defending Byzantine attacks in a commumicationncconttaaaa broadcast protocols are no longer available (Pease al. 1980] Dolev Strong 1983; Hirt Raykov 2014). regular workers can only utilize information from their own neighbors who have heterogeneous data distribution or are malicious, making very difficult to reach global consensus. While there are some works attempt to solve this problem (Su & Vaidya [0166; Sundaram & Gharesifard] 2018), their strategies suffer from serious ktaabacks 1) they require regular workers to be very densely connected; 2) they only show asymptotic convergence or convergence proof; 3) there is no evidence their algorithms are better than training alone.
graph is challenging. As secure
In this work, study the byzzantne-robustte address the aforementioned issues. The main contributions of our paper are summarized as follows:
decentralized training in constrained topology and
We identify novel network robustness criterion, characterized in terms of the spectral gap of the topology (?) and the number of attackers (d), for consensus and decentralized training, applying to much broader spectrum of graphs than (Su & Vaidyal 2016at [Sundaram & Gharesifard 2018).
We propose CLIPPEDGOSSIP as the defense strategy and provide, for the first time, precise rates of robust convergence to a (5maax)" <2 //²)) neighborhood of a stationary point for stochastic objectives under standard assumptions We also empirically demonstrate the advantages of CLIPPEDGOSSIP over previous works.
Along the way, we also obtain the fastest convergence rates for standard non-robust (Byzantine-free) decentralized stochastic non-convex optimization by using local worker momentum.
In previous version, we referred CLIPPEDGOSSIP self-centered clipping.

---

Under review as a conference paper at ICLR 2023
2 RELATED WORK
Recently there have been extensive works on Byzantine-resilient distributed learning with a trust- worthy server. The statistics- robust aggregation methods cover wide spectrum of works
including median (Chen et al. 2017 Blanchard et al. [017] Yin et al. 2018 Mhhadi et al.) 20188)
Xie et al.) 2018: Yin et al. 2019), geometric median (Pillutla et al.) 2019), signSGD (Bernstein
et al., 2019; Li et a 2019 yong Sohn et al. 2020), clipping (Karimireddy et al.] 202 la b). and
concentration filtering (Alistarh et 2018| Alhen-Zhu et al. 2020; Data Diggavi 2021 Other
works explore special settings where the server owns the entire training dataset (Xie et al. 2020a
Regatti et al., 2020 SSu & Vaidyal 2016b; Chen et al., 2018 Rajput et al. 2019 Gupta et al.
2021)
The sfate-of-the-arr attacks take advantage of the variance of good gradients and accumulate bias over time (Baruch et al., 2019; Xie et al. 2019). ). A few strategies have been proposed to provably defend
against such attacks, including momentum (Karimireddy et al. a02 El Mhamdi al. 202 1 and concentration filtering (Allen-Zhu et al. 2021)
Decentralized machine learning has been extensively studied in the past few years (Lian et al. 2017 Koloskova et al., |020b) Li et al.
2021| Ying et al. [202 Lin et al.) 2021 Kong et al. [2021] Yuan
al. 2021 Kovalev et al., 2021).
The state-of-the-ar convergence rate established in (Koloskova) o²
ct al. 2020b is (
+
V/=
where the leading ne is optimal. In this paper we improve this
rate O
2/8
using local momentum.
77/5g475
Decentralized machine learning with certified Byzantine-robustnes is less studied. When the communication is unconstrained, there exist secure broadcast protocols that guarantee all regular workers have identical copies of each other's update (Gorbunov et al./ 2021 El-Mhamdi et al. 2021). We are interested in more challenging scenario where not all workers have direct communication links. In this case, regular workers may behave very differently depending on their neighbors in the topology. One line of work constructs Public- Key Infrastructure (PKI) so that the message from each worker can be authenticated using digital signatures. However, this is very inefficient requiring quadratic communication (Abraham al., 2020). Further, it also requires every worker to have a globally unique identifier which is known to every other worker. This assumption is rendered impossible on general communication graphs, motivating our work to explicitly address the graph topology in decentralized training. Sybil attacks are an important orthogonal issue where a single Byzantine node can create innumerable "fake nodes" overwhelming the network (cf. recent overview by |Frd (02TT). Truly decentralized solutions to this are challenging and sometimes rely on heavy machinery, e.g. blockchains (Poupko et al. 2021 or sooo-oofPerronhood (Borge et al. 2017).
More related to the approaches we study, Su & Vaidya (2016a); [Snddara & Gharesifard (2018);
Yang & Bajwa (2019b a) use trimmed mean at each worker to aggregate models of its neighbors. This approach only works when all regular workers have an honest majority among their neighbors and are densely connected. Guo et al. (202I) evaluate the incoming models of a good worker with its local samples and only keep those well-perform models for its local update step. However, this method only works for IID data. [Peng& & Ling (2020) reformulate the original problem by adding TV-reuularization and propose a GossipSGD type algorithm which works for strongly convex and non-lID objectives. However, its convergence guarantees are inferior to non-parallel SGD. In this work, we address all of the above issues and are able to provably relate the communication graph (spectral gap) with the fraction of Byzantine workers. Besides, most works do not consider attacks that exploit communication topology, except (Peng & Ling 2020) who propose zero-sum attack. We defer detailed comparisons and more related works to S
3 SETUP
3.1 DECENTRALIZED THREAT MODEL
Consider an undirected graph G (V, where V= .L.....,) n) denotes the set of workers and E denotes the set of edges. Let N C V be the neighbors of node and Ni == NG {i). In addition, we assume there are no self-loops and the system is synchronous. Let V/8 C V be the set of Byzantine workers with
Dill and the set of regular (non-By -yza-Byzan workers is VR == Vg. Let GR be the subgraph of G induced by the regular nodes VRR which means removing all Byzantine nodes and their associated edges. If the reduced graph GR is disconnected, then there exist two regular workers who cannot reliably exchange information. In this setting, training on the combined data of all the good workers is impossible. Hence, we make the following necessary assumption.
2

---

Under review as a conference paper at ICLR 2023
(A1) Connectivity. GR is connected.
Remark 1. In contrast, Su & Vaidya (2066a; Sundaram & Gharesifard (2018) impose a much stronger assumption that the subgraph of GR of the regular workers remain connected even after additionally removing any [Va] number of edges. For example, the graph in Fig. D with I Byzantine worker Vi satisfies (AI) but does not satisfy their assumption as removing an additional edge at A or B1 may discard the graph cut.
In decentralized learning, each regular worker E VR locally stores vector { W of mixing weights, for how to aggregate model updates received from neighbors. We make the following assumption on the weight vectors.
(A2) Mixing weights. The weight vectors on regular workers satisfy the following properties:
Each regular worker i VR stores non-negative [Ws)}==1 with Wij iff j E N₁ The adjacent weights to each regular worker i E VR sum up to 1, i.e. Σj=1 Wi; = 1; For j E VR, Wij = W
We can construct such weights even in the presence of Byzantine workers, using algorithms that only rely on communication with local neighbors, e.g. Hattopslis-Hastinns (Hastings) 1970). We defer details of the construction to C.2 Note that the Byzantine workers Ve might also obtain such weights, however, they can use arbitrary different weights in reality during the training.
We define 6; : EjEn Way to be the total weight of adjacent Byzantine edges around regular worker i, and define the maximum Byzantine weight as 6max maxieve dz.
Remark 2. In the decentralized setting, the total fraction of Byzantine nodes [Vs] /n is irrelevant. Instead, what matters is the fraction of the edge weights they control which are adjacent to regular nodes {as defined by 8; and 6max). This is because a Byzantine worker can send different messages along each edge. Thus, single Byzantine worker connected all other workers with large edge weights can have a large influence on all the other workers. Similarly, a potentially very large number of Byzantine workers may overall have very little effect-if the edges they control towards good nodes have little weight. When we have a uniform fully connected graph (such as in the centralized setting), the two notions of bad nodes edges become equivalent.
To facilitate our analysis of convergence rate, we define a hypothetical mixing matrix W e ((n-b)x(n-b) for the subgraph GR of regular workers with entry i,j E VR defined as
W
if if
Wi
W 6
By the construction of this hypothetical matrix W, the following property directly follows. Lemma 3. Given A2)) then W is symmetric and doubly stochastic, i.e.
W WT. E Wi, 1, Σド= Wi, =1
Vi,j E [n-b]
Further, the spectral gap of the matrix W is positive. Lemma 4. By A/) and (22), there exists 7 (0, 1] such that V x R and 1T R
n-b
W ã 2| - (1 1] øl|2
The (W) the spectral gap the subgraph of regular workers GR. We have y = 0 if and only GR is disconnected, and = if and only if GR is fully connected.
In summary, Y measures the connectivity of the regular subgraph GR formed after removing the Byzantine nodes, whereas ò; and 6nax are a measure of the influence of the Byzantine nodes.
3.2 OPTIMIZATION ASSUMPTIONS
We study the general distributed optimization problem
mingeR f(x): = [ Eieva (f(z)) Fi {.)
(3)
on heterogeneous (non-IID) data, where fa is the local objective worker i with data distribution D; and independent noise & We assume that the gradients computed over these data distributions satisfy the following standard properties.
3

---

Under review as a conference paper at ICLR 2023
(A3) Bounded noise and heterogeneity. Assume that all E VR and Z E RD, we have
F FE-D,IIV E) - V]i(())]l? S so² [)>(a\VV((>>> - v((z))>>>
(4)
(A4) L-smoothness. For i E VR. fi(x)) Rd + IR is differentiable and there exists constant
sL 2 0 such that for each 2, y E R
(V) V fi(())l S L| -yl-
(5)
We denote ax E IRd as the state of worker i E VR at time 1.
4 ROBUST DECENTRALIZES CONSENSUS
Agreeing on one value (consensus) among regular workers is one of the fundamental questions in distributed computing. Gossip averaging is a common consensus algorithm in the Byzantine-free case (6 0). Applying gossip averaging steps iteratively to all nodes formally writes as
+++
Wiy
t = 0,1, 1,...
(GOSSIP)
Suppose each worker i initially owns different xf and AA and A2 hold true, then each worker's iterate ot asymptotically converges to x; a Σ ンー= x for all i [v]]. which is also known as average consensus (Boyd et al. 2006). Reaching consensus in the presence of Byzantine workers more challenging, with a long history of study (LeBlanc et al. 2013 Su & Vaidya 2016a).
4.1 THE CLIPPED GOSSIP ALGORRITM
We introduce novel decentralized gossip-basee based aggregator, termed CLIPPEDGOSSIP. for Byzantine- robust consensus. CLIPPEDGOSSIP uses its local reference model as center and clips all received neighbor model weights. Formally, for CLIP(Z, = min(1, // /|l) ) z, we define for node
プラ
t= == 10.
(CLIPPEDGOSSIPP)
Theorem I. Let कe = PR Eiev, xt be the average iterate over the unknown set of regular nodes. If the initial consensus distance is bounded as [Vrl Σien, El|a - 1²12 S p²: then for all i E VR. the output xt ++1 of CLIPPEDGOSSIP with an appropriate choice of clipping radius satisfies
[vl Eier. Ell 1²1 < 7 ) p2 and E| 1011 < e² Fmmax
where the expectation is over the random variable {æt and c > 0 is a constant.
We inspect Theorem I on corner cases. If regular workers have already reached consensus before aggregation (p 0), then Theorem [ shows that retain consensus even in the f'cc of Byzantine agents. In this case, we can use a simple majority, which corresponds to setting clipping threshold = 0. Further, if there is no Byzantine worker (Omax=0)) then the robust aggregator must improve the consensus distance by a factor of (1 - 7)² which matches standard gossiping analysis (Boyd al. 2006). Finally, for the complete graph (x= 1) CLIPPEDDOSSIP satisfies the centralized notion of (0max. c -robust aggregator in (Karimireddy et al. 2021a Definition C). Thus, CLIPPEDGOSSIP recovers all past optimal aggregation methods as special cases.
Note that if the topology is poorly connected and there are Byzantine attackers with (7 < CV Omax). then Theorem gives no guarantee that the consensus distance will reduce after aggregation. This is unfortunately not possible to improve upon, as we will show in the following $ $4.2 if the connectivity poor then the effect of Byzantine workers can be significantly amplified.
4.2 LOWER BOUNDS DUE TO COMMUNICATION CONSTRAINTS
Not all pairs of workers have direct communication links due to constraints such as physical distances in sensor network. It is common that subset of sensors are clustered within a small physical space while only few of them have communication links to the rest of the sensors. Such links form cut-set of the communication topology and are crucial for information diffusion. On the other hand, attackers can increase consensus errors in the presence of these critical links.
Theorem II. Consider networks satisfying Al of nodes, each holding a number in {0, 1}, and only O(1n2²) of the edges are adjacent to attackers. For any robust consensus algorithm A, there exists a network such that the output of A has an average consensus error of at least 21(1).
4

---

Under review as a conference paper at ICLR 2023
2
NonlID
Group global
Accurtcy (N))
diaue
A Cut B
Clique A
Clique
GlopedGSss
CippedGos.
Dumbbell
Agg
Agg
Figure A dumbbell topology of two cliques Figure 2: Accuracies of models trained with robust and B of regular workers connected by edge (graph cut). Byzantine workers (red) may attack the graph at different places.
aggregators over dumbbell topology and CIFAR- 10 dataset = 0). The models are averaged within clique A, B, or all regular workers separately.
CippeddSascip
Median
TM
1/y2
5
Bly²
Figure 3: Performance of CLIPPEDGOSSIP and baselines (TM and MEDIAN) under Byzantine attacks with varying y and max. Each point represents the squared average consensus error of the last iterate of an algorithm. MEDIAN and TM have identical performance and ClIPpEDGOSSIP is consistently better. Further, the performance of CLIPPEDGOSSIP is best explained by the magnitude of (6/~²)- it is excellent when the ratio is less than threshold and degrades as it increases.
average
Proof. Consider two cliques A and B with nodes each connected by an edge to each other and to Byzantine node V2, c.f. Fig. [ Suppose that we know all nodes have values in {0, 1}. Let all nodes in A have value O. Now consider two settings:
World 1. All B nodes have value O. However, Byzantine node 1/2 pretends to be part of a clique identical to B which it simulates, except that all nodes have value 1. The true consensus average is O. World 2. All B nodes have value This time the Byzantine node V22 simulates elique B with value 0. The true consensus average here is 0.5.
From the perspective of clique A, the two worlds are identical-it seems to be connected to one clique with value 0 and another with value 1. Thus, it must make ?(11) error at least in one of the worlds. This proves that consensus is impossible in this setting.
While arguments above are similar to classical lower bounds in decentralized consensus which show we need 5 S 1/3 (Fischer al., 1986). in our case there is only 1 Byzantine node (out of 2n + regular nodes) which controls only 2 edges i.e. 5 = 0(1 /n² This impossibility result thus drives home the additional impact through the restricted communication topology. Further, past impossibility results about robust decentralized consensus such as (Sundaram & Gharesifard, 2018 Su & Vaidya 2016a) use combinatorial concepts such as the number of node-disjoint paths between the good nodes. However, such notions cannot account for the edge weights easily and cannot give finite-time convergence guarantees. Instead, our theory shows that the ratio of 6max/7² accurately captures the difficulty of the problem. We next verify this empirically.
In Fig. 3 we show the final consensus error of three defenses under Byzantine attacks. TM and MEDIAN have large enror even for small 8max and large 7. The consensus of CLISPEDGOSSIP increases almost linearly with / However, this phenomenon not observed by looking at -2 2 or δmax alone, validating our theoretical analysis in Theorem Details are deferred to $ D.I
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Byzantine- Decentralized Optimization with CLIPPEDGOSSIP
Input: xº Rd, a, 7) {T/). m = (x(")
1: for 0, 1, 1......du do
2: for I...., n1 in parallel
3:
m ++1 (1 a)m; + (g.();)
141/2 = ot rym +1 if E VR else
4:
Exchange x; 1+//2 with N₁
5:
6:
x
+++
CLIPPEDGOSSIP, 1+/2 Dn 3T 11
7:
end for
Table 1: Comparison with prior work of convergence rates for non-convex objectives (
neighborhood of stationary points. We recover comparable or improved rates as special cases.
Reference
Setting
Convergence a e-accuracy
Regular (6 0)
Koloskova
2020b
0 nc?
3/3/2
vFe3/a + qc
Decentralized
This work
6=0
?
2/3
7g372
72/3.473 72
Guo al. 2022
Byzantine-robust Fully-connected (y = 1) ITD (Ç
Gorbunov et al.
2021
ó known
O
nóo"
+ +
Gorbunov et al.
2021
8 unknown
0 nc?
n'
This work
7=1,ç=0
0 0²
mc
Byzantine-robust Federated Learning
Karimireddy et al.
2021b
O (8+
This work
==1
(6+
This method does not generalize to constrained communication topologies.
5 ROBUST DECENTRALIZED OPTIMIZATION
The general decentralized training algorithm can be formulated as
x (x))
E VR
2 r+1 = AGG 1/1/2 E N.))
*
i VB
where v) the learning rate, g:(x)) VF E,) is stochastic gradient, and ~D is the random batch at time i on worker The received message x 141/ can be arbitrary for Byzantine nodes & E VB. Replacing AGG with plain gossip averaging (GossIP) recovers standard gossip SGD (Koloskova et al. 2019). ). Under the presence of Byzantine workers, which is the main interest of our work, we will show that can replace AGG with CLIPPEDGOSSIP and use local worker momentum to achieve 2021a). The full procedure is described in Algorithm
Byzantine robustness (Karimireddy et al.
Theorem III. Suppose Assumptions
hold and 6max = O(?2). Then for a == 3n,L, Algorithm
reaches T+1 D
Smaxe y + & in iteration complexity
22/3
fmuxx)
7E3/2 + 2/3 NE
nEa
n
Furthermore, the consensus distance satisfies the upper bound
Eee
x11 < O ((
Va
We compare our analysis with existing works for non-convex objectives in Table
Regular decentralized training. Even if there Byzantine workers (8max =0,, our convergence rate is slightly faster than that of standard gossip SGD Koloskova et al. 2020b). The difference is
2/3 that our third term O 2//3 ) is faster than their O 37a) for large and small e. This is because we use local momentum which reduces the effect of variance a. Thus momentum has a double use in this paper in achieving robustness as well as accelerating optimization.

---

Under review as a conference paper at ICLR 2023
Byzantine-robust federated learning. Federated learning uses a fully connected graph (y 1). We compare state of the art federated learning method (Karimireddy et al., (021b)) with our rate when y = 1. Both algorithms converge to a (oog)"))nihbbohoooo of stationary point and share the same leading term. This neighborhood can he circumvented with strong growth condition and over- parameterized models (Karimireddy et al.] 2021b] Theorem III.. We incur additional higher-order
terms 1 ye57z + 53755473 as a penalty for the generality of our analysis. This shows that the trusted server in federated learning can be removed without significant slowdowns
2/3
Byzantine-robus decentralized SGD with fully connected topology. If we limit our analysis to a special case of a fully connected graph ( 1) and IID data (ç= 0). then our rate has the same leading term as (Gorbunov et al., (02T), which enjoys the scaling of the total number of regular nodes. The
second term ( n ba²) of (Gorbunov et al. 2021 1 is better than our O 5o") for small & because they additionally validate yn random updates in each step. However, (Gorbunov et al. 2021 relies on
secure protocols which do not easily generalize to constrained communication.
Byzantine-robust decentralized SGD with constrained communication. MozI (Goo et al. 202
does not provide a theoretical analysis on convergence and TM (Sundaram & Gharesifard Su & Vaidya, 2016a; Yang & Bajwa 2019a) only prove the asymptotic convergence of full gradient under very strong assumption on connectivity and local honest majority Peng & Ling (2020)
2018
don't prove a rate for non-convex objective: Gorbuuoy et al. (202T) which shows convergence of (Peng& & Ling 2020) on strongly convex objectives at rate inferior to parallel SGD. In contrast, our convergence rate matches the standard stochastic analysis under much weaker assumptions than
Sundaram & Gharesifard (2018); [Su & Vaidya (2066a) Yang & Bajwa (2019a). Unlike these prior works, our guarantees hold even if some subsets of nodes are surrounded by a majority of Byzantine attackers. This can also be observed in practice, as we show in $ $D2..3
Consensus for Byzantine-robus decentralized optimization. Theorem gives a non-trivial result that regular workers reach consensus under the CLIPPEDGOSSIIP aggregator. In Fig. 2 we demonstrate the consensus behavior of robust aggregators on the CIFAR- 10 dataset on a dumbbell topology, without attackers (6 (0) We compare the accuracies of models averaged within cliques A and B with model averaged over all workers. In the IID setting, the clique-averaged models of GM and TM are over 80% accuracy but the dlobally-averagee clique A and clique B are converging to two different critical points and GM and TM fail to reach consensus within the entire network! contrast, the globally-averag as good as or better than the clique-averaged models, both in the III) and non-IlD> setting.
models are less than 30% accuracy. It means
model of CLIPPEDGOSSIP
Finally, we point out some avenues for further improvement: our results depend on the corst-case 5max- We believe it is possible to replace it with a (weighted) average of the {6:} instead. Also, extending our protocols to tiryingrying topologies would greatly increase their practicality.
Remark 5 (Adaptive choice of clipping radius T/). In D.5 we give an adaptive rule to choose the clipping radius Tę for all i E VR and times t, based on the top percentile of close neighbors. This adaptive rule results Byzantine robustness. In experiments, we found that the performance of optimization is robust to small perturbations of the clipping radius and that the adaptive rule performs well in all cases.
value tf slightly smaller than the required theoretical value to preserve
EXPERIMENTS
In this section, we empirically demonstrate successes and failures of decentralized training in the presence of Byzantine workers, and compare the performance of CLIPPEDGOSSIP with existing robust aggregators: 1) geometric median GM (Pillutla et al. 2019); 2) coordinate-wise trimmed mean TM (Yang & Bajwa 2019a): 3) MOzI (Guo et al.) (2220). Coordinate-wise median (Yin et al.) 2018) and Krum (Blanchard et al, (017) usually perform worse than GM so we exclude them in the experiments. All implementations are based on PyTorch (Paszke al. 2019) and evaluated on different graph topologies, with distributed MNIST dataset (LeCun & Cortes 2010). We defer the
experiments on CIFAR1O Krizhevsky et al. 2009) to $ D.3
We defer details of robust aggregators to $ A attacks to S topologies and mixing matrix to $ Caand Cand experiment setups and additional experiments
D
MMzz is renamed to URAR in the latest version.
'The code is available at this anonymous repository

---

Under review as a conference paper at ICLR 2023
IID
NonlID
NonlID
NonlID R.
NonilD + R.
100
Accuracy (%)
90
GlpsondGsssip
70
GM
MOZI
TM
50
Ideal Comm
250
500
7500
250
500
7500
250
500
7500
250
500
7500
250 500 750
Iterations
llteaaioons
Iterations
Ittraaionns
lleralions
Figure 4: Accuracy of the averaged model in clique for the dumbbell topology. In the plot title "B." stands for the bucketing (aggregating means of bucketed values) and "R." stands for adding I additional random edge between two cliques. We see that i) CLIPPEDGOSSIP is consistently the best matching ideal averaging performance, ii) performance mildly improves by using bucketing, and iii) significantly improves when adding a single random edge (thereby improving connectivity).
6.1 DECENTRALIZED DEFENSES WITHOUT ATTACKERS
Challenging topologies and data distribution may prevent existing robust aggregators from reaching consensus even when there is no Byzantine worker (5 = 0). In this part, we consider the "dumbbell" topology c.f. Fig. [ As non-IID data distribution, we split the training dataset by labels such that workers in clique A are training This entanglement of topology and data distribution is motivated by realistic geographic constraints such continents with dense intra-connectivity but sparse inter-connection links e.g. through an undersea cable. In Fig. we compare CLIPPEDGOSSIP with existing robust aggregators GM, TM, MozI in terms of their accuracies of averaged model in clique A. The ideal communication refers aggregation with gossip averaging.
digits O to 4 while workers in clique B are training on digits 5 to 9,
Existing robust aggregators impede information diffusion. When cliques A and B have distinet data distribution (non-lID), workers in clique A rely on the graph cut to access the full spectrum of data and attain good performance. However, existing robust aggregators in clique A completely discard information from clique B because: 1) clique B model updates are outliers to clique A due to data heterogeneity; clique B updates are outnumbered by clique A updates - clique can only observe update from B due to constrained communication. The 2nd plot in Fig. 4 shows that GM, TM, and MozI only reach 50% accuracy in the non-IID setting, supporting that they impede information diffusion. This is in contrast to the 1st plot where cliques A and B have identical data distribution (IID) and information on clique A alone is enough to attain good performance. However, reaching local models does not imply reaching consensus, c.f. Fig. 2 On the other hand, CLIPPEDGOSSIP is the only robust aggregator that preserves the information diffusion rate as the ideal gossip averaging.
Techniques that improve information diffusion. To address these issues, we locally employ the bucketing technique of (Karimireddy al., (021bb for the non-Ill) case in the 3rd subplot. Plots 4 and 5 demonstrate the impact of one additional edge between the cliques to improve the spectral gap.
The bucketing technique randomly inputs received vectors into buckets of equal size, averages the vectors in each bucket, and finally feeds the averaged vectors to the aggregator. While bucketing helps TM to overcome 50% accuracy, TM is still behind CLIPPEDGOSSIP. GM only improves by 1% while MozI remains at almost the same accuracy.
Adding one more random edge between two cliques improves the spectral gap y from 0.0154 to 0.0286. CLSSPEDGOSSII and gossip averaging converge faster as the theory predicts. However, TM, GM, and MOzI are still stuck at 50% for the same heterogeneity reason. Bucketing and adding a random edge help all aggregators exceed 50% accuracy.
6.2 DECENTRALIZED LEARNING UNDER MORE ATTACKS AND TOPOLOGIES.
In this section, we compare robust aggregators over more topologies and Byzantine attacks in the non- IID setting. We consider two topologies: randomized small world (? = 0.084) and torus 0.131... They much less restrictive than the dumbbell topology (-= 0.043) where all existing aggregators fail to reach consensus even 8=0 0. For attacks, we implement state of the art federated attacks Inner product manipulation (IPM) (Xie et al. 2019) and A little is enough (ALIE) (Baruch et al. 2019) and label-ffing foipping (LF) and bit bit- flippining (BF). Details about topologies and the adaptation of FL attacks to the decentralized setup are provided in C.1 and $
8

---

Under review as a conference paper at ICLR 2023
Small-world BF
Smail-world |L
Small-world ALIE
woald-word IPM
90
Accuracy (%)
8
50
Torus BF
Tonu LF
Torus ALIE
Torus IPM
80
GlaspedGGossi
GM
MOZI
600
400
Itarations
Horations
Itrratios
iterations
Figure 5: Robust aggregators on randomized small-worke (10 regular nodes) and torus topology (9 regular nodes) under Byzantine attacks (2 attackers). We observe that across all attacks and networks, clipped gossip has excellent performance, with the geometric median (GM) coming second.
The results in Fig. 5 show that CLIPPEDGOSSII has consistently superior performance under all topologies and attacks. All robust aggregators are generally performing better easier topology (large 7). The GM has a very good performance on these two topologies but, as we have demon- strated in the dumbbell topology, GM does not work in more challenging topologies. Therefore, CLIPPEDGOSSIP is recommended for a general constrained topology.
6.3 LOWER BOUND OF OPTIMIZATION
We empirically investigate the lower bound of optimization Of 22) in Theorem III In this experiment, we fix spectral gap % heterogeneity ç and use different 8max fractions of Byzantine edges in the dumbbell topology. The Byzantine workers are added to V1 in clique A and its mirror node in clique B. We define the following dissensus attack for decentralized optimization
Definition A (DISSENSUS attack). For VR and 8
dissensus altacker j N₁ n VB sends LNeN, "Vp War(a -x,)
3j
ESENmn W.
(6)
The resulting Figure shows that with increas- ing δmax the model quality drops significantly. This is in line with our proven robust conver- gence rate in terms of mmax- Notice that for large maxx the model averaged over all workers performs even worse than those averaged within cliques. It means the models in two cliques are essentially disconnected and are converging to different local minima stationary points of non-convex landscape. See $ D.2.2 for details.
Swss 0.0
0.125
0.1875
80
All
Accuracy (%)
Clique
60
Ci quequ
60
500
1000
0.0
0.1
0.2
Iterations
5mex
Figure 6: Effect of the number of attackers on the accuracy of CLIPPEDGOSSIP under dissensus attack with varying 5max and fixed 7, 52. The solid (resp. dashed) lines denote models averaged over all (resp. clique A or B) regular workers. The right figure shows the performance of the last iterates of curves in the left figure.
7 DISCUSSION
The main takeaway from our work is that ill- connected communication topologies can vastly magnify the effect of bad actors. As long as the communication topology is reasonably well connected (say ? = 0.35) and the fraction of attackers is mild (say 5 = 10%), clipped gossip provably ensures robustness. Under more ex- treme conditions, however, no algorithm can guarantee robust convergence. Given that decentralized consensus has been proposed as a backbone for digital democracy (Bulteau et al. 2021). and that decentralized learning touted to be alternative to current centralized training paradigms, findings are significant. A simple strategy we recommend (along with using CLIPPEDGOSSIP) is adding random edges to improve the connectivity and robustify the network.

---

Under review as a conference paper at ICLR 2023
BIBLIOGRAPHY
Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Commu- nication complexity of byzantine agreement, revisited, 2020.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Samy Bengio. Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Ro- man Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8. 2018, Montréal, Canada, pp. 4618-46242 2018, bt http:/ppps//proceciinnn.o http://occccngg....c wew.eeeeecinnnn...ee...e... wttpss.cppppppe 2018/ 8/aahh/
wttp://eeeeeeeeeee-aaaeeeeeee wwwttaat................ww.ww... htmm
Zeyuan Allen-Zhu. Faeze Ebrahimian. Jerry Li, and Dan Alistarh. Byzantine- non-convex stochastic gradient descent. arXiv preprint arXiv:2012.14366, 2020.
Zeyuan Allen-Zhu, Faeze Ebrahimianghazani. Jemry Li, and Dan Alistarh. Byzantine-resillent non-convex stochastic gradient descent. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL JRI.httss: http///ppwwveweeeee.eeeee
id
PoKHqVFtCS
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning, 2019.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buuc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pp. 8632 8642, 2019, URL/t: /ttp:ppppp/ppoocecngga nwwrips...rpppppp wwtppppppp/p////aaeeeeeeeee Iec (5955411117 6ed (ww.16666666666co6o
Abstract html
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant, 2019.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries:
Byzantine tolerant gradient descent. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long nnwrrps..c...mm.. cc/ wttp::/pppppp././o///ea/// Beach, CA, USA, pp. 119 129, 2017. URL httpttpss:ppocccellilit/ htmll
hash/
Maria Borge, Eleftherios Kokoris Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, and Bryan Ford. Proof-of personhood::: Redemocratizing permissionless cryptocurrencies. In 2017 IEEE European Symposium on Security and Privacy Workshops (EursS&PW), pp. 23-26. IEEE, 2017.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE trunsactions on information theory, 5206):250- 2006.
Laurent Bulteau, Gal Shahaf, Ehud Shapiro, and Nimrod Talmon, Aggregation over metric spaces: Proposing and voting in elections, budgeting, and legislation. Journal of Artificial Intelligence Rexearch, 70:1413-1439 2021.
Lukas Burkhalter. Hidde Lycklama, Alexander Viand, Nicolas Küchler, and Anwar Hithnawi. Rofl: Attestable robustness for secure federated learning, 2021.
Lingjao Chen. Hongyi Wang, Zachary B. Charles, and Dimitris S. Papailiopoulos. DRACO: byzantine-resitte distrihuted training via redundant gradients. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 902-911. PMIR, 2018. URL http: httt:://proceedkngs.o mir pwwss//eeppeeepee 0 chen181: 1...1....mmmmm..
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Syxtems, 1(2):1-25. 2017.
Georgios Damaskinos, El Mahdi EI Mhamdi, Rachid Guerraoui, Rhicheek Patra, and Mahsa Taziki. Asyn- chronous byzantine machine learning (the case of SGD). In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässen. Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1 1153- 1162. PMLR, 2018. URL http: //pp: //pp:ce/r/cceeeeee ngs www.pressss. www.eeas..veeeeeeeeeeeeeeeeeeeee /amad nos 8a html
10

---

Under review as a conference paper at ICLR 2023
Deepesh Data and Suhas Diggavi. wyzaatine-rrsillenn sgd in high dimensions heterogeneous data, In 202/ IEEE International Symposium on Information Theory (ISIT), pp. 2310-2315, IEEE, 2021.
Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Comput., 12: 656-666, 1983.
Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyēn Hoang, and Sébastien Rouault. Collaborative learning the jungle (decentralized, byzantine, heterogencous, asyn- chronous and nonconvex learning). Advances in Neural Information Processing Systems, 34, 2021.
EI Mahdi EI Mhamdi, Rachid Guerraoui, and Séhastien Louis Alexandre Rouault. Distributed momentum for byzantine-resilient stochastic gradient descent. In 9th International Conference on Learning Representations (ICLR), number CONF, 2021.
Michael Fischer, Nancy A Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26-39, 1986.
Bryan Ford. 10. technologizing demoeracy or democratizing technology? lacheed-archiiectuuee perspective potentials challenges. In Digital Technology and Democratic Theory, pp. 274-321. University of Chicago Press, 2021.
Eduard Gorbunov, Alexander Borzunov, Michael Diskin, and Max Ryahinin. Secure distributed training at scale, 2021.
Shangwei Guo, Tianwei Zhang, Xiaofei Xie, Lei Ma, Tao Xiang, and Yang Liu. Towards -yzantine-rssilient learning in decentralized systems. arXiv 08569, 2020.
Shangwei Guo, Tianwei Zhang, Han Yu, Xiaofei Xie, Lei Ma, Tao Xiang, and Yang Liu. Byzantine-resilient decentralized stochastic gradient descent, 2021.
Nirupam Gupta, Thinh T Doan, and Nitin Vaidya. Byzantine fault-tolerance in federated local sgd under 2f-redundancy. arXiv preprint arXiv:2108.I 11769 2021.
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National (lb..(.,,..),, Los Alamos, NM (United States), 2008.
W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. 1970.
Lie He. Sai Praneeth Karimireddy, and Martin Jaggi. Secure byzantine-robut machine learning. arXiv 04747, 2020.
Martin Hirt and Pavel Raykov. Multi-valued byzantine broadcast: The case. In ASIACRYPT, 2014.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet. Mehdi Bennis, Arjun Nitin Bhagoji. Keith Bonawitz, Zachary Charles. Graham Cormode, Rachel Cummings, Rafael G. D' O'Ivveei.. Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie Hc, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Koncený, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittl,, Mehryar Mohri, Richard Nock. Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song. Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv 1912.04977, 2019.
Sai Pranceth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Muchine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 Proceedings of Machine Learning Research, pp. 5311-5319. PMLR, 2021a. URL htttp:://prcceedinggs wttp:eceeeeiinnsm......e...m mlr. wwwpppresssseee sttesss/v139 http://eeeaaaannn..pppee//////// http:///ww1//aaaaimdeaeaaa html
Sai Pranceth Karimireddy, Lie He, and Martin Jaggi. Byzantine-rohust learning on heterogeneous datasets via bucketing, 2021b.
Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication, 2019.
Anastasia Koloskova, Tao Lin, Sebastian U. Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression, 2020a.
11

---

Under review as a conference paper at ICLR 2023
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. A unified theory of decentralized SGD with changing topology and local updates. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 5381-5381558 5393. PMLR, 2020b. URL http::/procceedngg mlr press/ press/vii3g htte/vv19////6 wtw.///kllooooaaaaa..oo html
Anastasiia Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for decentral- ized machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Lingjing Kong. Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian U Stich. Consensus control for decentralized deep learning. arXiv preprint arXiv:2102.04882 2021.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, and Scbastian Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Statistics, pp. 4087-4095. PMLR, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Lestie I Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concurrency: the Works of Leslie Lamport. pp. 203 226. 2019.
Heath LeBlanc, Haotian Zhang, Xenofon Koutsoukos, and Shreyas Sundaram. Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications, 31(4),766-781, 2013.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http::/yann Lecun com/exdb// /xdb/ exdb/nnist/
Liping Li, Wei Xu, Tianyi Chen, Georgios B. Giannakis, and Qing Ling. RSA: byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In The Thirty-Third AAAI Confer- ence on Artificial Intelligence, AAAI 2019, The Thhrtt-FFrrtt Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii USA, January 27 February 1, 2019, pp. 1544-1551, AAAI Press, 2019. doi: 10. 1609/669aiii...mmmmm v33001 333011544, wttp:tts::t///ttttt /tt.ttts://oo........ org/ / 10t. aaai v33101 033101.3311111... 33011544
Xiang Li, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Communication local decentralized sgd methods, 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent, 2017.
Tao Lin, Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. arXiv preprint arXiv:2 102.0761, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas, Communication- efficient learning of deep networks from decentralized data. In Aarti Singh and Xiaojin (Jerry) Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research. pp. 1273-1282 PMLR, 2017. URL httt::::::///eeeee
mlr. r. www.pprsssssseee. //s/s/////o Cttee//s//////mmmaaaaaaa mwmamannlnanncccmmmmmmmmm.maa a .ttm
Mahdi EI Mhandi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability distributed learning in byzantium. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International
Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 3518-33110 -5277 PMLR, 2018. URL https //proceedingss mwr. press/ v mw/a//aammd/// Minedii8aa. 13a. htm
Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEFE Signal Processing Magazine, 37(3)992-101, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alch Bucc Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver. BC. Canada, pp. 8024 2019. URL ht ht http:///occccccocoocoooooc neur ips. 62/ paper /201 9/hash/ @dbca288fee7f9225
12

---

Under review as a conference paper at ICLR 2023
Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27:228 234, 1980.
Jie Peng and Qing Ling. Byzantine-role robust decentralized stochastic optimization. In 2020 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2020, Barcelona, Spain, May 4-8, 2020, pp. 3935-5939, IEEE, 2020. doi: 10.1 1A111///AASP4447600000000000
URI.https: //do1 .org/
1109/ CA777 2020. 9054377
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint arXiv: 13445, 2019.
Ouri Poupko, Gal Shahaf, Ehud Shapiro, and Nimrod Talmon. Building a sybil-resilient digital community utilizing trust-graph connectivity. IEEE/ACM Transactions Networking, 2021.
Shashank Rajput, Hongyi Wang. Zachary B. Charles, and Dimitris S. Papailiopoulos.. DETOX: redundancy-basee framework for faster and more robust gradient aggregation. In Hanna M. Wal- lach, Hugo Larochelle, Alina Beygelzimer, Florence d' ''lch-BBuc, Emily B. Fox, and Roman Gar- nett (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neu- ral Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 10320- 10330, 2019. URL httttp::/pproceedingg neur ins.ips.... tt/ 221p / 2e155556ee2242222eeeeeeeee 2boeee2bb....4222222----111.. htcml
Jayanth Regatti, Hao Chen, and Abhishek Gupta. Bygars: Byzantine sgd with arbitrary number of attackers, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409, 1556, 2014.
Lili Su and Nitin Vaidya. Multi-agent optimization in the presence of byzantine adversaries: Fundamental limits. In 2016 American Control Conference (ACC), pp. 7183-7188. IEEÉ, 2016a.
Lili and Nitin H Vaidya. Robust multi-agent optimization: coping with byzantine agents with input redundancy. In International Symposium on Stabilization, Safety, and Security of Distributed Syxtems, pp. 088-382. Springer, 2016b.
Shreyas Sundaram and Bahman Gharesifard. Distributed optimization under adversarial nodes. IEEE Transac- tions on Automatic Control, 64(3):1063-1076 2018.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D²: Decentralized training over decentralized data, 2018
Thijs Vogels, Sai Pranceth Karimireddy, and Martin Jaggi. Practical low-rank communication compression in decentralized deep learning. NeurlPS, 2020.
Thijs Vogels, Lie He, Anastasia Koloskova, Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Relaysum for decentralized deep learning on heterogeneous data, 2021.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world networks. nature, 393(6684); 440-442, 1998.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd. arXiv 1802. 16, 2018.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant SGD by inner product manipulation. In Amir Globerson and Ricardo Silva (eds.), Proceedings of the Thirty- Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Aviy, Israel, July 22-25, 2019. volume 115 of Proceedings of Machine Learning Research, pp. 261-270. AUAI Press, 2019. URL pttp //proceedings..o mlr prwss//eee/eeeeeeee..e v115/ xie20a htm.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous SGD. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 10495 10503, PMLR, 2020a. URL httpt
//proceeding i ngs, mlr, . wwwps//esseeee / vlllvvll99 9/ wxwxxixeccccmm html
Cong Xie, Sanmi Koyejo, and Indranil Gupta. 7eno+::
Robust fully asynchronous sgd. In International Conference on Machine Learning, pp. 10495-10503. PMLR, 2020b.
13

---

Under review as a conference paper at ICLR 2023
Yi-Rui Yang and Wu-Jun Li. BASGD: buffered asynchronous SGD for byzantine learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virual Event, volume 139 of Proceedings of Machine Learning Research, pp. 11751-11761. PMLR, 2021. hRL.attp://prrccod....
-mlr pww.sppsssss...... wttpppsssws/..asgeeppeeeee html
Zhixiong Yang and Wahced Bajwa. Bridge: Byzamtine-resliiet docentralized gradient descent. arXiv 1908,08098, 2019a.
Zhixiong Yang and Waheed U Bajwa. Byrdie:
Byzantine resilient distributed coordinate descent for decentralized learning. IEEE Transactions on Signal and Information Processing over Networks, 2019b.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter L. Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In Jennifer G. Dy and Andreas Krause (cds.), Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockhollmmmdssann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 5636-5645. PMLR, 2018. URL html
mlr. prwss wwwpe///e/eeilleeeeeeeee http://proceedin http://www.m.....//seeeees///e
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in byzantine-robust distributed learning. International Conference on Machine Learning, pp. 7074-7084. PMLR, 2019.
Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34, 2021a.
Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin. Blucfog: Make decentralized algorithms practical for optimization and deep learning. arXiv preprint arXiv:2111.04287, 2021b.
Jy yong Sohn, Dong-Jun Han, Beongjun Choi, and Jackyun Moon. Election coding distributed learning: Protecting signsgd against byzantine attacks, 2020.
Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Decentlam: Decentralized momentum sgd for large-batch deep training. arXiv preprint arXiv:2104. 11881, 2021.
Chengeheng Zhao, Jianping Hc, and Qing-Guo Wang. Resilient distributed optimization algorithm against adversarial attacks. IEEE Transactions on Automatic Control, 65 65(10):4308-45 -315, 2019.
14

---

Under review as a conference paper at ICLR 2023
Appendices
CONTENTS OF THE APPENDIX
Existing robust aggregators
15
Byzantine attacks in the decentralized environment
16
B. Existing attacks in federated learning
16
B.2 Dissensus attack and other attacks in the decentralized environment
16
Topologies and mixing matrices
17
Constrained topologies
17
Constructing mixing matrices
18
Experiments
18
D.I
Byzantine-robust consensus
18
D.2
Byzantine-robust decentralized optimization
19
D.2.1
Setup for "Decentralized defenses without attackers
20
D.2.2
Setup for "Effects of the number of Byzantine workers'
21
D.2.3
Setup for "Defense without honest majority"
D.2.4
Setup for "More topologies and attacks."
21
D.3
Experiment: CIFAR-IO task
22
D.4
Experiment for "Weaker topology assumption"
22
D.5
Experiment: choosing clipping radius
23
Analysis
24
E.1
Definitions, and inequalities
................................
24
E
Lemmas
25
E,3
Proof of the main theorem
F
Other related works and discussions
36
A
EXISTING ROBUST AGGREGATORS
In this section, we describe existing robust aggregators mentioned in this paper. Regular nodes can replace gossip averaging (GossIP) with robust aggregators in the federated learning. Let's take geometric median and trimmed mean for example.
Geometric median (GM). Pilluda et (2019 implements the geometric median
GM(
..) ..,,))...,Z,)
arg min Ei= 1/1 x:ll2.
Coordinate-wise trimmed mean (TM). Yin al. (2018): Yang & Bajwa (019a) computes the k-th coordinate of TM as
TM(
mn)) = 1
23 Σve,, [as]
where U3 is subset of [n] obtained by removing the largest and smallest 9-fraction of its elements.
These aggregators don't take advantage the trusted local information and treat all models equally.
The MOzI algorithm (Guo et al. 2021) leverages local information to filter outliers.
Mozi. Guo al. 2022 applies two screening steps on worker VR
N arg min CA, W I= JEN
Σ ||=; æ,
Ni = 0 (j (n] ((x,, < l(x,, (()
15

---

Under review as a conference paper at ICLR 2023
where & ~ Dj is random sample. If WV = 00 then redefine MP {arg ((a,,,)); Then they update the model with
=
az
NT EJEN; ojj - (.F(
where E [0, 1] is hyperparameter.
B BYZANTINE ATTACKS IN THE DECENTRALIZED ENVIRONMENT
In this section, we first describe how to transform attacks from the federated learning to the decentral- ized environment. Then we introduce the dissensus attack for decentralized environment.
B.1 EXISTING ATTACKS IN FEDERATED LEARNING
A little is enough (ALIE). The attackers estimate the mean μ.N and standard deviation dN, of the regular models, and send MwN N to regular worker where z a small constant controlling the strength of the attack (Baruch et al. 2019). The hyperparameter for ALIE is computed according to (Baruch al. 2019)
max ((=) <
where 8 = 1 + +1 - and @ is the cumulative standard normal function.
Inner product manipulation attack (IPM). The inner product manipulation attack is proposed in (Xie et al. 2019) which lets all attackers send same corrupted gradient u based on the good gradients
U Av :
VR)) Vj VB-
If e is small enough, then uy can be detected good by the defense, circumventing the defense. There are 3 main differences where IPM need to adapt to the decentralized environment:
1. Byzantine workers may not connected to the same good worker.
2. The model vectors are transmitted instead of gradients.
3. The AvG should be replaced by its equivalent gossip form.
This motivates our dissensus attack in the next section.
B.2 DISSENSUS ATTACK AND OTHER ATTACKS IN THE DECENTRALIZED ENVIRONMENT
In this section, we introduce a novel dissensus attack inspired by our impossibility construction in Theorem II and the IPM attack described above. The dissensus attack aims prevent regular worker models from reaching consensus. Roughly speaking, dissensus attackers around worker send its model weights that symmetric to the weighted average of regular neighbors around i. Then after gossip averaging step, the consensus distance drops slower even grows which motivates the name "dissensus".
X3
X2
We can parameterize the attack through hyperparameter E, and sum- marize the attack in Definition A
Figure Example of the DISSENSUS attack. The gray (8)
Fi F3 Ei Encr,my Win
L W,,
(resp. red) denotes regular (resp. Byzantine) nodes. The blue dots represents the pa- rameters of regular nodes after gossip steps.
The E; determines the behavior of the attack. By taking smaller EG, Byzantine model weights are closer to the target updates and difficult to be detected. On the other hand, a larger e, pulls the model away from the consensus.
Note that this attack requires omniscience since exploits model information from across the network. If the attackers in addition choose which node to attack, then they can choose either to spread about the attack across the network or focus on the targeting graph cut, that is min-cut of the graph.
16

---

Under review as a conference paper at ICLR 2023
Effect of the dissensus attack. The dissensus attack enjoy the following properties.
Proposition IV. (i) For all i E VR. under the dissensus attack with = 1, the gossip averaging step (GossIP) equivalent to no communication on i, x x æ Secondly, (ii) If the graph is fully connected, gossip averaging recovers the correct consensus even in the presence of dissensus attack.
The above proposition illustrates two interesting aspects of the attack. Firstly, dissensus works by negating the progress that would be made by gossip. The attack in (Peng & Ling 2020) also satisfies this property (see Appendix for additional discussion). Secondly, it is a uniquely decentralized attack and has no effect in the centralized setting. Hence, its effect can be used measure the additional difficulty posed due to the restricted communication topology.
Proof. For the first part, by definition GoSSIIP) we know that
++1 Eド= W,, xt + EJEN, Wiy(2) - x;)
By setting E; in the attack (6), the second term O and therefore az!1 æ/. For part (ii), note that in a fully connected graph the gossip average is the same as standard average. Averaging all the perturbations introduced by the dissensus attack gives
Eijev W Way(aj x 0.
All terms cancel and sum to 0 by symmetry. Thus, in fully connected graph the dissensus perturba- tions cancel out and the gossip average returns the correct consensus.
Relation with zero-sum attack and dissensus, Peng Ling (020) propose the "zero-sum" attack
which achieves similar effects as Proposition IV part (i). This attack is defined for j E VB
ExEMCry mt (N
The key difference between zero-sum attack and our proposed attack is three-fold. First, zero-sum attack ensures EjeN; 3. O which means the Byzantine models have be far away from af and therefore easy to detect. This attack pull the aggregated model to O. On the other hand, our attack ensures
EjEN; WA EjEN, W Waja = x
and the Byzantine updates can be very close to æf and it is more difficult to be detected. Second, our proposed attack considers the gossip averaging which prevalent in decentralized training (Koloskova et al. 2020b) while the zero-sum attack only targets simple average. Third, our attack has an additional parameter & controlling the strength of the attack with e > 1 further compromise the model quality while zero-sum attack is fixed to training alone.
C TOPOLOGIES AND MIXING MATRICES
C.1 CONSTRAINED TOPOLOGIES
Topologies that do not satisfy the robust network assumption in (LeBlanc et al. 2013 Sun-
daram & Gharesifard 2018; Su & Vaidya, 2016a). The robust network assumption requires there to be at least b paths between any two regular workers when there are b Byzantine workers in the network (LeBlanc et al., 2013 Sundaram & Gharesifard] 2018 Su & Vaidya 2016a). The topology in Figure only has I path between regular workers in two cliques while having 2 Byzantine workers the network. Therefore this topology does not satisfy the robust network assumption. But the graph cut is not adjacent to the Byzantine workers and, intuitively, it would be possible for an ideal robust aggregator to help reach consensus. The experimental results are given in Appendix [D.4
(Randomized) Small-world topology. The small-world topology is random graph generated with Watts-Strogan model (Watts & Strogatz, 1998). The topology is created using NetworkX package (Hagberg et al.) 2008) with 10 regular workers each connected to nearest neighbors and probability of rewiring each edge as 0.15. Two additional Byzantine workers are linked random regular workers. There are 12 workers in total.
17

---

Under review as a conference paper at ICLR 2023
A Cut B1
Clique A
Clique B
Figure 8: Example topology that does not satisfy the robust network assumptions in Sundaram Gharesifard 2018
Su & Vaidya 2016a).
Torus topology. The regular workers form torus grid T3,3 and two additional Byzantine workers are linked to 2 random regular workers. There are 11 workers in total.
The mixing matrix for these topologies constructed with Mctropolis- in the previous section. The spectral gap for small-world topology and torus topology are 0.084 and 0.131 respectively. In contrast, the dumbbell topology in Figure 1olis more challenging with spectral gap of 0.043. The data distribution is non-IID.
algorithm introduced
C.2 CONSTRUCTING MIXING MATRICES
In this section, we introduce few possible ways to construct the mixing weight vectors in the presence of Byzantine workers. The constructed weight vectors satisfy (A2) in Section 3
Metropolis- Hastings weight (Hastings, 1970). The Hetropolis-Hastting algorithm locally con- structs the mixing weights by exchanging degree information (d; and d,) between nodes and j. The mixing weight vector on regular worker i E VR is computed as follows
j jE
mAx dix 1
Wij
DIEN, Wa j=i,
Otherwise.
worker j E VB is Byzantine, then the only way for j to maximize its weight Wij to regular worker is to report smaller degree dy. However, such Byzantine behavior of node has limited influence worker i's weight Wij because it not be greater than -. weigh- Let dmaxx be the maximum degree of nodes in graph. Such upper bound dmaax be public information, for example, a bluetooth device can at most connect to dmax other devices due to physical constraints. The Byzantine worker cannot change the value of dmax. Then the following naive construction
jE No j=i, i,
A
W
=
AG
Otherwise.
Note that these construction schemes are not proved to be the optimal. In this work, we focus on the Byzantine attacks given topology and associated mixing weights. We leave it future work to explore the best strategy to construct mixing weights.
D EXPERIMENTS
We summarize the hardware and software for experiments in Table We list the setups and results of experiments for consensus in Appendix D.I and optimization in Appendix D.2
D.1 BYZANTINE- ROBUST CONSENSUS
18

---

Under review as a conference paper at ICLR 2023
Table Runtime hardwares and softwares.
CPU
Model
(R) (R)
# CPU(s)
56
NUMA nodo(s)
GPU
Product
Tesla 520-222232
CUDA Version
11.0
PyTorch
Version
1.7.1
Table 3: Default experimental settings for MNIST
Dataset
MNIST
Architecture
CON.COON.RROPOTHHRRRROOTTCC
Training objective
Negative log likelihood loss
Evaluation objective
Top-1 accuracy
Batch size per worker
32
Momentum
0.9
Learning rate
0.01
LR decay
No
LR warmup
No
Weight decay
No
Repetitions
Reported metric
Mean test accuracy over the last 150 iterations
In this section, we provide detailed setups for Figure 3 demonstrates the topology for the experiment. The regular workers are connected with two of them holding value O and the others holding 200. Then the average consensus is 100 with initial mean square equals 10000. Two Byzantine workers are connected two regular workers in the middle. We can tune the weights of each edge to change the mixing matrix and y. Then we decide the weight on the Byzantine edge. The y and 5 used in the experiments
The Figure 9
200
Figure 9: The topology for the attacks on consensus. The grey and red nodes denote reg- ular and Byzantine workers re- spectively.
P
(1
7)²
E
[0.06, 0.05 0.04, 0.03, 0.02, 0.01, 0.005, 0.0014,3.7e 4,
4. le
8 [0.05, 0.1, 0.4.0.0
where non-compatible combination of and 8 are ignored in the Figure 3 The dissensus attack is applied with 0.05. The hyperparameter 33 of trimmed mean (TM) of Byzantine workers around the regular worker. The clipping radius of CLIPPEDGOSSIP is chosen according to (27).
the actual number
In Figure 10 we show the ficration-to-eree curves for all possible combinations of y and 8. In addition, we provide version of TM and MEDIAN which takes the mixing weight into account. As we can see, the naive TM, MEDIAN, and MEDIAN cannot bring workers closer because of data distribution we constructed. The TM performing better than the other baselines but worse than CLIPPEDGOSSIP especially on the challenging cases where is small and is large. For CLIPPEDGOSSIP, it matches with our intuition that for a fixed y the convergences worse with increasing 8 while for a fixed the convergence is worse with decreasing
D.2 BYZANTINE- ROBUST DECENTRALIZED OPTIMIZATION
In this section, provide detailed hyperparameters and setups for experiments in the main text and then provide additional experiments. For all MNIST tasks, we use the default setup listed in Table unless specifically stated. The default hyperparameters of the robust aggregators: 1) For GM,
19

---

Under review as a conference paper at ICLR 2023
10000
611r
0.000
0.103
0.000
0,200
0.000000
00200
10030
EN01
0.040 Suas 3,000 p= 0.401 16
0,100
0.040 4yuu
0.200
000400
6..w
-0,300
0:00400) 4rua
0,403
0,040 4r 0.503
E71
0.030 P... 0.000
p 0.300
1. 0.103
0.030 S.. 0.200
p 0.030 Aew
0.300
p- 0.030
fru. 0,403
0.2001 Ana 0.500
p 0.020 Sree
0.000
pm 0.020 Srea 0.100
p 0.020 6rew 0.200
p 0.0020 &rew 0,500
p 0.020 6rue 0,400 n 0,0001 6rew 0,000
1003)
Eive
6000
po Modian
TM
Medban
TVP
p- 0.010 1uae
0.010 Seua 0.102
0.000 Srw
0.200
p- 0.0000 frew
p- 0.010 | fvua
p 0,010 6ra.
10033
Erdr
5000
1...
10000
5/v
10000
Enn
0.000
0,050
0.000
0.103
0.000] 0,200 0.000 00,000
0.000
0,403
0.000
0.500
10030
102
102
Figure 10: The iteration-to-ee -ooerrr curves for defenses under dissensus attack. The TM* and MEDIAN refer to the version of TM and MEDIAN which considers mixing weight.
choose number of iterations 7 = 8; 2) The TM drops top and bottom B = 6maxx percent of values in each coordinate; 3) The clipping radius of CLIPPEDGOSSIP is 4) The model averaging hyperparameter of MOZI is = 1.
D.2.1
SETUP FOR "DECENTRALIZER DEFENSES WITHOUT ATTACKERS"
The Fig. g uses the dumbbell topology in Fig. I with 10 regular workers in each clique. There is no Byzantine workers. The experiments run for 900 iterations. MozI uses 0.5 and p: 0.99 in
20

---

Under review as a conference paper at ICLR 2023
Agg ClippedGossip
GM TM
ATK ALIE
ATK Dissensus
100
W
Acouracy (%)
H.M.E.
40
False True
20
Clique A
Clique B
500
500 Iterations
Iterations
Figure II: Dumbbell variant where Byzantine workers maybe added to the central worker.
Figure 12: Accuracy of aggregators with or without the honest majority everywhere (H.M.E.) assumption. Regular workers are connected through ring and have IID data.
this setting. For bucketing experiment, we choose bucket size of 2. It means we randomly put at most two updates into one bucket and average within each bucket and then apply robust aggregators to the averaged updates.
D.2.2 SETUP FOR "EFFECTS OF THE NUMBER OF BYZANTINE WORKERS"
The Fig. 0 Juses dumbbell topology variant in Fig. I| The experiments run for 1500 iterations. In this experiment we choose n - 11 and 0, I, 3. 3. We choose the edge weight of Byzantine workers such that the W and remain the same for all these b. Then we can easily investigate the relation between 6max E [0, 5 and p by varying The hyperparameter of dissensus attack is set 8 1.5 for all workers and all experiments.
D.2.3 SETUP FOR "DEFENSE WITHOUT HONEST MAJORITY"
The Fig. 12 uses the ring topology of regular workers in Fig. B 11 Byzantine workers are added to the ring that regular worker do no have honest majority. The experiments for 900 iterations. We use 6; = 1.5 for dissensus attacks. We use clipping radius = 0.1 for CL.PPEDDGSSII..
In the decentralized environment, the common honest majority sumption in the federated learning setup can be strengthen to honest majority everywhere, meaning all regular workers have honest ma- jority of neighbors (Su & Vaidya 6b Yang & Bajwa 2019b a Considering ring of regular workers with IID data, adding 2 Byzantine workers to each node will still satisfy the honest majority assumption everywhere. Now adding one more Byzantine worker to a node will break the assumption.
Figure 13: Ring topology without honest majority.
Figure 12 shows that while TM and GM can sometimes counter the attack under the honest majority assumption, adding one more Byzantine worker always corrupts the entire training. The CLIPPED- GOSsIP defend attacks successfully even beyond the assumption, because they leverage the fact that local updates are trustworthy. This suggest that existing statistics based aggregators which take no advantage of local information vulnerable under this realistic decentralized threat model.
D.2.4 SETUP FOR "MORE TOPOLOGIES AND ATTACKS."
In Figure 5 we use the small-world and torus topologies described in Appendix C.I More specifically, created randomized small-world topology using NetworkX package (Hagberg et al.) 2008) with 10 regular workers each connected to 2 nearest neighbors and probability of rewiring each edge 051.. Two additional Byzantine workers are linked 2 random regular workers. There are 12
21

---

Under review as a conference paper at ICLR 2023
Table 4: Default experimental settings for CIFAR-10
Dataset
CIFAR-IP
Architecture
VGG-I I [Simonyan & Zisserman (2014
Training objective
Cross entropy loss
Evaluation objective
Top-1 accuracy
Batch size per worker
64
Momentum
0.9
Learning rate
0.1
LR decay
0.1 epoch 80 and 120 No
LR warmup
Weight decay
No
Repetitions
Reported metric
Mean test accuracy over the last 150 iterations
workers in total. For the torus topology, we let regular workers form a torus grid Ta.a where all regular workers are connected to 3 other workers. Two additional Byzantine workers are linked to random regular workers. There are workers total.
The mixing matrix for these topologies are constructed with Metropolis-Hasting algorithm in Appendix C.2 The spectral gap for small-world topology and torus topology are 0.084 and 0.131 respectively. In contrast, the dumbbell topology in Figure i6 more challenging with spectral gap of 0.043. The data distribution non-IID.
D.3 EXPERIMENT: CIFAR- 10 TASK
In this section, we conduct experiments on CIFAR-10 dataset Krizhevsky et al. (2009). The running environment of this experiment is the same as MNIST experiment Table 2 The default setup for CIFAR-10 experiment is summarized in Table
We compare performances of 5 aggregators on dumbbell topology with 10 nodes in each clique (no attackers). The results of experiments are shown in Figure 14 In order to investigate if consensus has reached among the workers, we average the worker nodes different categories ("Global", Clique A, and Clique B) and compare their performances on IID and NonlID datasets. The "IID-Global" result show that GM and TM is much worse than CLIPPEDDGSSIIP and Gossip, contrast to the MNIST experiment Figure 4 where they have matching result. This is because the workers with in each clique are converging to different stationary point - "IID-Clique A" and "IID-Clique B" show GM and TM in each clique can reach over 80% accuracy which is close Gossip. It demonstrates that GM and TM fail to reach consensus even this Byzantine- case and therefore vulnerable to attacks.
The NonlID experiment also support that CLIPPEDGOSSIP perform much better than all other robust aggregators. Notice that CLIPPEDGOSSIP' "NonIID-GGlobal" performance is better than "NonIIDD-Clique A" and "NoniIID-Clique B" while GM and TM's result are opposite. This because CLiPpEDGOSSIP allows effective communication in this topology and therefore clique models close to each other in the same local minima basin such that their average (global model) is better than both of them. The GM's and TM's clique models converge different local minima, making their averaged model underperform.
D.4 EXPERIMENT FOR "WEAKER TOPOLOGY ASSUMPTION"
As is mentioned in Remark and Appendix C.1 the topology assumption in this work is weaker than the robust network assumption in Su & Vaidya 20); Sundaram Gharesifard (2018). We use the topology in Figure which consists of 10 regular workers and 2 dissensus attack workers. While this topology does not satisfy the robust network assumption, intuitively should allow communication between two cliques will discard the graph cut due to data heterogeneity. This shows that GM and TM impede information diffusion. On the other hand, CLIPPEDGOSSII is the only robust aggregator which help two cliques
Byzantine workers are attached to the cut. However, both GM and TM
22

---

Under review as a conference paper at ICLR 2023
IID-Global
IID-Clique A
IID-Clique B
Cipped
Nos440 soy
Gossip
NoniID-Global
NonlID-Clique
NonlID-Clique
$880
Accyracy
Alb 40
1.25
0.50
1.25
Iterations
1e6
Iterations
1e6
Iterations
1e6
Train models dumbbell topology with IID and NonlID datasets. The three figures in each row correspond to the same experiment with "Global", "Clique A", "Clique B" denoting the performances of globally averaged model, within-Clique A averaged model, and within Cihiie-Clique B averaged model.
Figure 14:
IID
NonliD
NonilD
NonliD
NonilD + R.
100
80
Accuracy
70
GM
CipppeGGossip
MOZI
TM
50
Ideal Comm.
250
500
7500
250
500
7500
250
500
7500
250
500
7500
250
500
750
Iterations
Iterations
Iterations
Iterations
Iterations
Figure 15: Compare robust aggregators under dissensus attacks over dumbbell topology Figure
reaching consensus the NonlID case. The CLIPPEDGOSSIP theoretically applies to more topologies and empirically perform better.
D.5 EXPERIMENT: CHOOSING CLIPPING RADIUS
In Figure 16 we show the sensitive of tuning clipping radius. We dumbbell topology with regular workers each clique and add more Byzantine worker to each clique. The clipping radius searched over a grid of 10.1, 0.5, 10). The Byzantine workers chosen be Bit-Flipping, Label-Flipping. and ALIE.
We also give adaptive clipping strategy for different E VR and time f. After communication step ++1/
at time f, the value of x;
f+1/2 is available. Therefore we can sort the values of x
x;
++1//
for all j E Nr. We denote the set of indices set S as the indices of workers that have the smallest distances worker
S
arg min
Σ
x
14//2
141/2
S:M''s 5151--
jES
23

---

Under review as a conference paper at ICLR 2023
Bit-Flipping
Label-Flipping
ALIE
100
Accuracy (%)
90
80
T=0.1 T=
70
r= 1
r= 10
Adaptive
200
400
600
200
400
600
600
Iterations
Iterations
Iterations
Figure 16: Tuning clipping radius on the dumbbell topology against Byzantine attacks. The y-axis is averaged test accuracy over all of the regular workers.
Then the adaptive strategy picks clipping radius as follows
++1 - V Wij x
1+ 1+1/211
(10)
Note that this adaptive choice of clipping radius is generally a bit smaller than the theoretical value (27). guarantees that the Byzantine workers have limited influences cost of small slow down on the convergence.
As we can see from Figure 16 the performances of CLIPPEDGOSSIP are similar with different constant choices of which shows that the choice of T is not very sensitive. The adaptive algorithms perform well in all cases. Therefore, the adaptive choice of r will be recommended in general.
E ANALYSIS
We restate the core equations in Algorithm a time on worker follows
m ++1 (1 a)m; + (x)(
(11)
1///2 x¹ r/m
(12)
++1 J-i x 14//2 + CLIP(M, /4 x. 4///// 7/)
(13)
n
x W 241
(14)
In addition, we define the following virtual iterates on the set of good nodes VR
.z Eieva x! the average (over time) of good iterates.
Vil
m 1 Eiey, m. the average (over time) of momentum iterates.
[Val
In this proof, we define p (1 7) (0, 1] for convenience.
In this section, we show that the convergence behavior of the virtual iterates क'. The structure of this section is follows:
In Appendix E.I we give common quantities, simplified notations and list common equali- ties/inequalities used in the proof.
In Appendix E.2 provide all auxiliary lemmas necessary for the proof. Among these lemmas, Lemma is the key sufficient descent lemma.
In Appendix
E.3 we provide the proof of the main theorem.
E. DEFINITIONS, AND INEQUALITIES
Notations for the proof.
We use the following variables simplify the notation
24

---

Under review as a conference paper at ICLR 2023
Optimization sub-optimality:
re = f(='))
-
Consensus distance:
Σ VeVa
| x112
[Rl
The distance between the ideal gradient and actual averaged momentum
cft1 = V m ++1
Similarly, the distance between the ideal gradient and individual momentums
FIV - -
VEVA
Similar, distance between individual ideal gradients and individual momentums which is weighted by the mixing matrix
(v - >1
VR
JEV
Similar we have distance between individual ideal gradients and individual momentums
F Em ++
V f=
Let .+1 be the averaged squared error introduced by clipping and Byzantine workers
2
ΣE E
Σ
W Weglztt
2/ + Σ
Way 1+
x
VR
EV
JEVR
JEVe
Lemma (Common equalities and inequalities). We use the following equalities and inequalities
The cosine theorem: V xz E Rd
(x. y) - |1x0 2112 11=+2lan
(15)
Young's inequality: For > and x, y Rd
|| y 1 $ (1 + +) =0 (1 (1++ 18013
(16)
If f is convex, then for a [0, 1] and x, y E Rd
flax (1 a)y) S af( + (1)))f())
(17)
Cauchy-Schwarz inequality
(x. v) < 2اا2ا|1||
(18)
Let (æ, : i [m]] be independent random variables and Ex, and E El 2 o² then
Ell E.
(19)
E.2 LEMMAS
The following lemma establish the update rule for æ'.
Lemma 7. Assume Lemma
Let A t+1 be the error incurred by clipping and VB
1-1 1
Σ
Σ W Wir
x
W W1r - at v//1//)
(20)
VR
JEVR
JEVB
Then the virtual iterate updates
x/' -mm t+1
+ A 1+1
(21)
25

---

Under review as a conference paper at ICLR 2023
Proof. Expand xf+1
with the definition of [+1
in
14) yields
x++1_
Σ
Σ
Wij
+1 + Σ J-22
Wejz
VR
VR
iE
VE
JEVK
JEVn
Σ
Σ
Wis(s
Σ
Wajarj
14//2
VR
iEVR
JEVA
JEV
Σ
23 Wiy Wz
14//2/
Σ
W
Wijzety/ +
VRl
iEVR
JEVB
JEVB
Reorganize the terms to form A++1
x
1
Σ
W Wy 14/2
W Wijart1/3 14//2
Wayar
A+11
VR
VEVR
JEVR
JEVa
1
(1
1+//2
ó, 1+1/2
+ 1+
VR
[R
JEV
iEVA
1
T
++1/
+ A
1+1
Σ
(2)
rym + A 1+1
VR
[R
LEVR
EVVR
A H+1
m/m
Note that the A++1 can be written as the follows
A ++1
Σ JEVR
Wiya 141/2
x1+1
44//2
|R
[RR
LEVA
iEVR
where measures the error introduced to x'+1 considering the impact of Byzantine workers and clipping. Therefore when V/8 = @ and is sufficiently large, same rate as the centralized SGD with momentum.
= 0 and x++1 converge at the
Recall that ef+1 = f=)) - m²+ 12- The key descent lemma is stated as follow
Lemma 8 (Sufficient decrease). Assume A4 and S 2T. then
E [( </(#") - " 112 " "F
(+1
1 ne
1 1+1 +
-e2
7
17
Proof. Use smoothness (4 and expand it with 21
L
f( <ʃ ( (V f(''), 1m 1+1
A41) +
-
Ilim 1-1 A 1+1
2
Apply cosine theorem [5 to the inner product 17 V fz²")
m 1+1
A yields
[) Laj²
E [(
<s(=') " [| )13
El|
m
++1
A 17
+
11
2
+
f(*') - m 1+
1 -----+10
A
2
If step size 17 - 1. then Lo""
4. < - Applying inequality (66 to the last term
2T.
7 F m
1+1
A < m
ElA+t1 1/
2
17
Since ef ++1 = ElIVf((') m +1 and E|
1 ك et then we have
Ef(x+11 <f(x²)
7 El
++1
1 A + 1 nott!
+
1 ++1
17
26

---

Under review as a conference paper at ICLR 2023
In the next lemma, establish the recursion for the distance between momentums and gradients
Lemma 9. Assume A3
and (44 and Lemma
For any doubly stochastic mixing matrix A E R
H+1
Σ
-V
++1
VR
iE
JEVn
then we have the following recursion
a²0²
Al + +2LL3' 2z mm/
1 -1...
et S1 (1-aaeas +
(22)
[RR
a
11
where we define | = Eieva Σjer, A Therefore,
If A. = Dit for all i,j E VR. then et11 =est1 and ||A|| = 1.
A = W. then etAt1 = = x+1 and A A P.Ve = Eieve Eiera W3 s (Rl.
If - I, then |All [RRl. In addition,
at S $227tt 25²
where A I.
Proof. We can expand I+11 by expanding m.+
Σ
Aty ((1 - -o
VR
iEVR
JEVR
1
F
+ - V
VR
iEV
JEVv
Extract the stochastic term gy(x² V (x.)) inside the norm and use that E g = (z.))
Σ
Σ
A. (110))
(()
VR
iEVR
/EV
Σ EI
Σ
-
VR
JEVA
JEV
Σ (1,((11))
+ V
VR
iEVR
JEVA
Σ
-
(z)))
VR
JEV
Then we can use A3 for the last term to get
a²a²
++1
Σ A1,((1-a)
+
|
DR
[i
iEVi
JEV
Then we insert
+11 ax) (1,("' inside the first norm and expand using 17
a²0²
Σ
Σ
Am V
|
|
VR
DRR
SE JEVr
+ a Σ
Σ
+ -
Anj
- vf)(t')
a
-
(V
VR
iE VEVR
JEVR
27

---

Under review as a conference paper at ICLR 2023
Note that the first term is cs1 and by the convexity of ||-|| for the last term we have
a²o²
A
++1
<(1
a)) +
[RR
a
[V)())) - V1)(2') + 1-a a (VI}(z'11) - -
+
VR
JEVR
Then we can further expand the last term
o²0²
1+1 <(1 -
a1-'a +
All
[R
2a
2(1-a)
+
[V
V
Vf -
VR
a|VR
JEVE
JEVR
Then we can apply smoothness
A4
and use (1-a)><1 S
a²o²
<(1 -1-a)e
a)e
| A.
+2 +
m
A
A 12
11
Besides, consider
z(+1
1
et
E
m 1+1 ff((')) )12
E| m + Vfi(=') v
VR
[RR
iEVR
VV
<
m
c+1 V>( + +
[V - {(()")
VR
VR
iEVA
iEV
-6, 1+1
+ 2ç²
As we know that | 1+1 113 S 1-1 then we need to finally bound ct+1
Lemma 10 (Bound on e2 ,+1). ). For mmax = maXieva d,. if
+
W
E
a
1+1/
23
1+1/2
8
JEVR
then we have
++1 S c 8max (e) (ett1 + +2) + +
2
where constant eq 32.
Proof. Use Young's inequality 16 to bound et by two parts
2
Σ
E
Σ
W Wo
2
1222 +
W
W1
x. 211122
VR
iEVR
JEVR
JEVa
<
2
E
Σ
W Wo -
E
Σ
W
(2
x 22/1/)
VRl
VR
iEVR
EEVR
JEVB
Look at the first term use triangular inequality of ||.|] and the definition of 7
A 5
Σ
Σ
W
1
VR
iEVa
JEV
2
Σ
W W.J
1/2 x0
[R
JEV
The second inequality holds true because we can consider two cases of 2 for all j E VR
28

---

Under review as a conference paper at ICLR 2023
If |00
141/2
//////1
11 7i
then CLIP has no effect and therefore [+1
1/1/2
|| 2. 1/ 1|2
1+// 1/1//
5j 11
1/
. If [[
144/
144 my
11 /
7 ++ then ش sits between mj
1/4// and an ++
1/2
with
| 3y +
/ 1| + - ++ ||aett/
2 e-
112
Therefore, using the inequality
T S
a²
for 0 we have that
6+1 4+ jjj
4///2
++ 1 1|2
1+1 s
1
e+
1/2
z
74
Therefore we justify the second inequality. On the other hand,
2
2
2
A
Wi
x;
S
Σ SEVR
Σ
[R
VR
JEVB
jEVe
2
[RR
iEVR
Then minimizing the RHS of e2
1+1 by tuning radius for clipping
W
E
1/2/2
1/2
JEVR
Then come the following bound
[R
Σ
Σ
Wij
E
x
441/
j
141//11
2
VEVe
JEVR
Then we expand the norm as follows
E
1+1/2
+
1/2
E
x mm1
++1 2². + 1/m t-1
112
2
E x - x² x²j + nm 1+1 =1 7m1 +
-mm;+=)))+mm))0)) 1|
(23)
<41² 2 Ellm 1+1 v)(x')1 + F
1+1 -
+ 4|| x 112 + 4||=> 2
Use the fact that
Ejenh Wij = 1 - d; we have
ct v
16n
6,(1 8,) El m ++1 ff(E")1< +
1672
Σ
Σ
Wi5 Ellm -
VR
[R
VR
VR VVV
16
Σ 8,(1 o - x²112 +
16
Σ
8, W W - =
[VR
[RR|
iEV
JCV VEVA
Use the fact that 5; < 6max and 1- 8, < for all E VR.
++1 + + +2)) c < 325 (2n/ (e
Theorem with
Let x. = [Vo Eier, I; be the average iterate over the unknown set of regular nodes
1
E Wij
E [| - 22,12
(24)
If the initial consensus distance is bounded as output i; of CLIPPEDGOSSIP satisfies
1 Eiev, El|xx, 2 < pp then for all i e VR. the
Ve Eiev, El - 2112 < (1 (1-- + ev ) 2 22
where the expectation over the random variable (a: and <>> 0 is constant.
29

---

Under review as a conference paper at ICLR 2023
Proof. We can consider the 1-step consensus problem as 1-step of optimization problem with p² p²==" = and 1) = 0. Then we look for the upper bound of [V Eien, mmxx.
= +++1 =x'1 in terms of p², p. and
1
E||an c+1
2²12
1+1 W
-
[RR
VR
KEVA
iEV
Vi
1
Σ
EI(
W -
1+1 W Wyzj-
Σ JEVR
W W1
[R
EVVR
JEVR
Apply 16
with and use the expected improvement Lemma 4
Ella
VR
KEVR
1 1+6
1+
a W
Σ
Waja 12112 +
E
Σ
W
[Rl
[RR
joi
KEVA
JEVR
iEVR
j=1
JEVn
+ s) p)
||0|
11122
+
1+1
Σ
W
[Rl
VEVR
VEVR
j=1
JEVK
1+
S(1 (1++)) p)) +
Σ
E
W
|R
<VV
JEVR
Replace 2/ =zj
22/t1/3 + + ++1 using 12
then apply 18
and n 0
1 - v (1
1 1+
++1
Σ
Wija $1/
[RR
DRl
EEVR
j=1
jEV
Recall the definition of e+1
W Wijary 2
VR
iEVn
Then use Lemma 9 with the case A W and apply Lemma
10 with 17 =0
1 2'1 < (1 c) - p)= + (1+ 1e5t s +1 -0-pp)== + (1+ 3328 )328max=*
E E +
[VR
VEV
Let's minimize the right hand side of the above inequality by taking & such that s(1 -p) 328max which leads to
8
326 326mmax then the above inequality becomes I-p
x
++1
x 11 < (1
p 320 + 22/320max (1 p))= p+ )
[R
VE
The consensus distance to the average consensus is only guaranteed to reduce /1-pt 320mmax < 1 which is
8max
_ (1-1117
32
Finally, we complete the proof by simplifying the notation to spectral gap 7 :- 1 - vI- p.
Recall that
Σ
W
W1
B.
( +
Σ
W Wir(z a (412)
(25)
DR iEVn
JEV
JeVs
Next consider the bound on consensus distance E!.
30

---

Under review as a conference paper at ICLR 2023
Lemma 11 (Bound consensus distance E²). Assume Lemma 4 then E' has the following iteration
g < (1 (1)=) ez(1+ +22
(
62 ++1 + +/eet + c² + (V v/ Elm 1+1
1 - 3 1 11
77
where 0 is determined later such that (1 +1 p) < 1 and c2 5.
Proof. Expand the consensus distance at time t 2+1 1
1
E+H1
E
1
W ++1 プ-ナ - -
VR
VRR
VEVR
IE VR
j=1
1
(+1 - x² + -
[R
VEVR
EIC
W - +
W
Wif
Σ
W Woyzy)) + x' 1 112
[R
VEVI
JEV
JEVR
Apply Young's 's inequality improvement Lemma 4
16 with coefficient e, like the proof of Theorem
[ and use the expected
g++1 - 1+
Wy 21112
[RR
NEVR
JEVR
+
+ El
W
1+1 2-
Σ
W
Wijzj + x' -0'--+113
iEVR
j=1
JEVR
(1 (1+ p)
| 11
1 1+E
E
W 11
Σ
W
W
x -
[RR]
VR
j-si
VvV
VEVR
JEVn
1
5(1 + e) p))="=
Wizz
Wyyaz) x² 1 12
VRV
sEVR
JEVK
:
Replace 2² = ;z
1+//2
+ 1
1+1 using
then apply 18
1+8
Ti
E
W
W W1 + x² -
VR
LEVR
j=1
JEVR
JEV₂
<5
1 +
W ij 3-イ
W Wi Wiya 1/
E
iEVR
j=1
JEVR
(26)
El
W Wiy(m 11 - f
P
LEVR
JEV
Σ EVVR
Σ
+ +E 11-
P
-
JEVA
Recall the definition of ++1
++
Σ
E
Σ
Wir
1+1 - 22 2////) + Σ
W (2 ++1 2.t113)
VR
SEVR
JEV
JEV
Σ
El
Wo t+1
Σ
W W
++ 1/2
VR
EE
1=1
JEVR
31

---

Under review as a conference paper at ICLR 2023
Then use Lemma 9 with the case A W,
T <5(1 + )
6/2 e2 +1 [Val
W - + E| - x
JEVR
Use convexity of 11.113 and A3 we have
71 55 + ( (est) e7 + 2² + +// 113 + Ellaa' x.+1133)
Use 21 for the last term
Ti <5 2)
( 1+1 ( + + + + F
-
7
Finally, by the definition of ttt1, we have
Et! (1+ =) + +5(++ ) 2+ + + +²² + + =|mm
1 - ++1 113
+1
11
Lemma 12 (Tuning stepsize.). Suppose the following holds for any step size n S d:
To + bn + enj² + f
V S (T +1)
Then, there exists a step-size 1) S such that
M S 2(
brn
) + 2
ro
2f
ro
+
dro
T +
T+1
T +
T +1
Proof. Choosing n = min
To b(T+1]
To c(T+1)
To
we have four cases
((T+1)
:
. J/ and is smaller than
2
To e(T+1)
To
then
bT++)
[(T+1)
T S T +
dro
b
f
<
dro
+ ( bro
(+1)
te1/3
ro
$
+
ro +11/4
d
d3
T +1
T++1
T 1
== ((T+T]
minf
(77+TT)
then
e(T+1J
bro
ero
To
bro
1/2 te1/3
ro T+1
1 +/1
ro
VT 2
+ b(T 1)
+f
2
T+1
b(T
bT + 1
T + 1
1) =
E(7+1)
To
minf
6/++1
To
Eo [[T+T]
thehe
3
3
TT S 2/3
ra
+b
To
+
fro
bro
1/2
To T +
+/2/4
ro T 1
T T+1
c(T +1]
e(T + +1)
T+1
- ([T+TT)
min
b(T+1]
rn [(T+TT)
}. then
1/4
1/
38
VT S 2f11/4
T+1
ro
+b
((T+1))
f(T
+e
f(T +
To
T
bro
+e//3
To T+1
12f1/4
To T+1
Then, take the uniform upper bound of the upper bound gives the result.
32

---

Under review as a conference paper at ICLR 2023
E.3 PROOF OF THE MAIN THEOREM
Theorem
Suppose Assumptions 7 hold and 6max = -0 Define the clipping radius as
Jen, W
E 2;
1///22
1+ 1/21// 2
(27)
2
Then for a == 3nL, the iterates of Algorithm satissyy
1/2
200
7
max
+ +2(
[Vll
3"
+
320 mmax) )/2
7"
3Lo'r T+1
48c2
(2)
1/3
ra
9/3
1440z 0²)
1/4
ro
3/4
dora
T+1
T+1
T+1
where tu :7 f(x²) f and 0 = 32 and C2 = 5. Furthermore, the consensus distance has an upper bound
[4l Eienn | x =112= -1
Remark 13. The requirement Smax 0(72) suggest that 8max and x22 are of same order. The exact constant are determined in the proof and can be tighten simply through better constants in equalities like (23). (26). practice CLIPPEDGOSSIP allow high number of attackers. For example
in Figure 15 1/6 of workers are Byzantine and CLIPPEDGOSSIP still perform well in the non-lID setting.
Proof.
Denote the terms of average from 0 to T as follows
T
T
T
1
11
C2
m
++
++
D1
S
1+7
T
1
1
T
1=0
1=0
T
1
E
H+1
E
E7
H+
E2
H+1
1+7
1 1+
1+7
t=U
t=0
1=0
t=0
First we apply average to Lemma 10
Eg S C20 m2)) (2)) + (3) DD).
(28)
Then we rewrite key Lemma 8 as
2
2 41
\V + 2
El
A
1+1 112 < <-(r" p(1 22 +
62
"
and further average over time
2ro
C1 + C2 S C25
+ 2E + E2
2
[T 1)
172
where we use -f(x < - Combined with 28 gives
1 Ci + C2 <
2ro
2020max
+ + 4c28mnx Es + 402dmax +
D1
(29)
2
n( + 1)
n?
Now we also average Lemma
0 for ej over t gives
T
a²0²
2L'
T
Σ
a
of + 20L2D +
m
11
1+T
+ T
[R
1+7
1=0
1=0
1=0
1 - a
a²0²
2
1+1 + 2aL
+
C2
1+T 1=0
|R
where we use E el 0 and m
A 0. Then let B1
n
E < 2L2DD + a
+ B2.
(30)
[RR]
33

---

Under review as a conference paper at ICLR 2023
Similarly, Lemma 9 for e/ the only difference is that don't 't have for o²
Et 212 DI + oo² + BIC2.
(31)
Similarly, let's call 82 == [Vkl Lier, ΣjEn, W 1
E s 222 D1 + 3200² + +,102.
(32)
The consensus distance Lemmal
has
D1 11 (1+ p)
Ex + e2 + k) + 02 11) +
14T
t=
<(1 <(++))(1 - p) c2 ) c2 + ( + - Ci C2).
Replace Eg using (28 gives
D1 {1 + (1 + c2(1 +1+++1110010 (c1 (27 + 5²) + D1)) + 02(1 +2
<((1 (1(1+s) - + c12((1 ! maax Dj + 02 + _ )n² (2c) max E7 + Ef + (1 + 2c 2 + + C2).
Now replace E,, E, with 32
31 then
D1 <((1 + +) p) + c2(1 + (c + AL317² +2L227²)
+c2 ))) δmax + 82)a0² + (2c1 6max + +1)5² + ((2c) dmax + 1)31 + 1)C2 + C1).
By enforcing 7 s ol. and 6max
100102 have
20 57218 eje2dmax (1 44L))²² 572/8
we can achieve
v Vieezmmaxl (1 + 4121)2) + 222 - 2
Then
D1 p) (1+ DI
=T=
+c2(1 ((2) + 32)a0² + (20) 8max + 1)x² + ((2c)mmax + 1)31 1)C2 + C1).
Let us minimize the the coefficients of Dj on the right hand side of inequality by having
1 17
c(1 p)
4
33 that is E = V 1(1-p))
Then the coefficient becomes
T2 =11 + pp) + (1+ 1)
=(v1- p- 23
2
=(1 7)3.
Then we use
42-21 < and + 1 <
D (2cidmax
4 7
+ =22 + (2c) Smax + 1)(² + ((2c)mmax + 1)81 + 1)C2 + Ct).
This leads 20g 8max
and B2 < 1, then know
5cz
4c21² 22 (200² +22 + C + (1+ 23
D <
(33)
34

---

Under review as a conference paper at ICLR 2023
Finally, combine 29
(30
32
2rp
+ 2E + 1 E1 + 4e mmx ²² + 201 201Jm D1
C + / C2 < 7(T + 1)
2
112
2ro
+ALL
200" Mall
+23 6 max (4L2D1 + 2,2200222222 + C2)
7 + 1)
201dmax D1
+ 4c1 0cxxx
2ro + (AL2 + S0, mma 12 +
2e1 Imax
D1 + ( Val + 22222mma 2ac
71' + 1)
172
+431 + 40 5
Then we replace D1 with (33
1 C2 S Ci
2ng
2c, max )ao + C2 4c mmax
2
[T+]
MRi
(34)
(1 + 8c, 12 20, (11mmax 1 (2a0² + 25² + C1 (1 (1+ 23,)(2)
To have a valid bound on C₁ there are two constraints on the coefficient of the RHS C₁ and C2.
(4L217² + 8c1 L 122 + 20 (mxx) 2 <1
(4I.2-)² + 801 mm1x 1,² + 20, mmxx) ) + (1+ 2 28)) + 4 S
We can strength the first requirement to
40g 1
(4L2, 8c1 8max L22 + 2c1 2max)
(35)
7
4
Then, apply this inequality to the second inequality gives
1 4 + 2 < 2
1
which requires 7 $ 3L
Next (35) can be achieved by requiring 6max S
7² 0ic102
(4 + Sc; dmax L²²²² 2010ma
< <8L311² + 2c1 2max
1602
which requires 8,1212 < 32c²
and we can simplify it to 1) S
7
Now we can simplify 34 with
402
35
C S n.म
2re
[M + 2c, dmx 2a02 + 4e dmaxs
+ (4L21)²
8c, &max 122 + 2c, 2c18max) 4gg (200² 2 + 2(
Multiply both sides with $ and relax constant 3 2 2 3. Then by taking 17 2T, have that
1
C1 I 3r n(T+1) + ( [pal + 151 20, mmx 30o² 2 + 2000 ca m + 72
48ca
7² (ao² + (
72
By taking 3nL and relax the constants have
C1 < Minimize the the right hand side by tuning step size Lemma 12 have
3rg +
32 [pal +
7" 3 ) +
48cz (ao² + L2) + 200 c2 mmax 2
70
32 Vvl
320c1 72
mmax ) To
V
200c ez 72
8
2
+2
T+1
daro
+ 2
180 (
2
114cs z
+
7+1
7+1
T+1
where d/ = min 27, ST. 40T,
401. and
2ro
2ro
1/3
2roy
1/4
min
1
320c: 7
8 Lo (T'
L3o2TT
+
do
[M
35

---

Under review as a conference paper at ICLR 2023
2L²n" Bound on the consensus distance D1. Since 31 at = we can relax (33) to
D1 S dean' 70t (200 + 2 + + ( +22))
dean (200 2 + 2 + +3( + (.C))).
O ( and find the upper bound of 20x2 - 25² + Ci + JC2 with ((²)) where higher order terms of 1/T are dropped. Therefore, the upper
For significantly large T, we know that 1j
bound on the consensus distance D1 is O +((++))
F OTHER RELATED WORKS AND DISCUSSIONS
In this section, we add more related works and discussions.
Byzantine resilient learning with constraints Byzantine-rouustness is challenging when the train-
ing is combined with other constraints, such as asynchrony (Damaskinos et al., 2018 Xie al. 2020b Yang & Li )02T), data heterogeneity (Karimireddy et al.]| Peng & Ling 2020: Li
et al. 2019] Data & Diggavi 2021), privacy (He et al.) [020]] Burkhalter et al. 2021). These works all assume the existence of central server which communicate with all regular workers. In this
paper, we consider the decentralized setting and focus on the constraint that not all regular workers can communicate with each other.
More works on decentralized learning. Many works focus on compression-techhniuess (Koloskova al. 2019 2020a Vogels al., 2020), data heterogeneity (Tang et al.) 2018 Vo-
gels et al. 2021 Koloskova et al. 2021), and communication topology (Assran et al. 2019 Ying
al. 202 a).
Detailed comparison with one line of work. Among all the works on robust decentralized training, Sundaram et al. (Sundaram Gharesifard (2018) and Su al. [Su & Vaidya (2016a) and their followup works Yang & Bajwa (2019b]a) a) have the most similar setup with ours. They are all using the trimmed mean the aggregator assumptions on the graph. We illustrate our advantages over these methods as follows
1. Their methods (TM) make unrealistic assumptions about the graph while our method is much more relaxed. Their main assumption on the graph has 2 parts: 1) each good node should have at least 26 + neighbors where b is the maximum number of Byzantine workers in the whole network; 2) by removing any edges the good nodes should be connected. This assumption essentially requires the good workers have honest majority everywhere and additionally they have to be well connected. This can be hardly enforced in the decentralized environment. contrast, our method has weaker condition relating the spectral gap and Our method also works without a honest majority Figure The second part of their assumption exclude common topologies like Dumbbell.
2. TM fails to reach consensus even in some Byzantine-free graphs (e.g. Dumbbell) while SSClip converges as fast as gossip. For example, TM fails to reach consensus in NonlID setting for MNIST dataset (Figure and even fails in IID setting for CIFAR- 10 dataset (Figure 14
We have a clear convergence rate for SGD while they only show asymptotic convergence for GD. In fact, we even improve the state-of-art decentralized SGD analysis (Koloskova et al. 2020b).
Our work reveals how the quantitative relation between percentage of Byzantine workers (6) and information bottleneck (r) influence the consensus (see Figure and Theorem I].
We propose a novel dissensus attacks that utilize topology information.
6. Impossibility results. Sundaram et al. Sundaram & Gharesifard (2018) and Su et al. Su & Vaidya (2016a) give impossibility results in terms of number of nodes while we give a novel results in terms of spectral gap (7).
36

---

Under review as a conference paper at ICLR 2023
= 1/
cip
xf"1 Eily Wyyfft
zf Wor
(a) Before aggregation.
(b) Clipping updates.
(c) Gossip averaging.
Figure 17: Diagram of ClippedGossip at time t on worker i. Let purple node be the model worker i and green nodes be models of worker i's regular neighbors and red nodes be models of worker i's Byzantine neighbors. The figure (a), (b), and (c) demonstrate the stages of ClippedGossip. First, in the left figure (a) worker i collects models (ar) 4/1/2 j E Ni} from its neighbors. Then in the middle figure (b) worker clips neighbor models to ensure the clipped models are no farther than 7, (++1 from node i. Nodes outside the circle (e.g. z;
f+1/22 clipped to the circle (e.g. z}=,) while nodes inside the
remain the same after clipping (e.g. =/ the right figure (c) worker update its model to x.""
circle (e.g. a xf 1+1 using gossip averaging over clipped models.
Other related works and discussions. Zhao et al. Zhao et al. (0119) make assumption that some users are trusted and then adopt trimmed mean robust aggregator. But this assumption is incompat- ible with our setting where every node only trusts itself. Peng et al. Peng & Ling (2020) propose "zero-sum" attack which exploits the topology where Byzantine worker J construct
=
They aim manipulate the good worker i's model O, but also makes the constructed Byzantine model very far away from the good worker models, making it easy to detect. In contrast, our dissensus attack (6) simply amplifies the existing disagreement amongst the good workers, which keeps the attack much less undetectable. addition, we take mixing matrix into consideration and use & to parameterize the attack which makes more flexible.
Clarifications about our method. We make the following clarifications regarding our method:
Ideally we would like to replace the 6max = max, ōy with an average 8 1/2 Σ3 65. However, the requirement that & be small may be achieved by the good workers increasing its weight on itself. Note that Byzantine workers cannot alter good workers local behavior.
Theorem III does not tell us what happens if the percentage of Byzantine workers d is relatively larger than spectral gap (7), but it does not necessarily mean that CLIPPEDGOSSIP diverges. Instead, it means reaching global consensus is not possible as Byzantine workers effectively block the information bottleneck. We conjecture that within each connected good component not blocked by the byzantine workers, the good workers still reach component-leved consensus by applying the analysis of Theorem [I] to only this component. We leave such a component-win analysis for future work.
37


Reviews:
[{"review_id": "ttWOQhIuDd", "reviewer": "Reviewer_3Jpb", "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": "", "summary_of_the_paper": "This submission discusses using the technique ClippedGossip in the decentralized optimization setting to counter potential Byzantine agents in the network. \n\nThe authors provide convergence guarantee in terms of first-order condition to show the attainment of consensus in the network, and give numerical experiments to show the effectiveness of the ClippedGossip technique in providing robustness in several attack/data heterogeneity settings.", "summary_of_the_review": "There are several places where further clarification about theoretical proof and numerical experiments can be helpful for me to determine the correctness of the submission. It is not immediately clear to me that the selected numerical baseline is the most appropriate baseline, and I would like to examine the proof closer.", "strength_and_weaknesses": "Strength:\n\n-> The paper is well-structured and the narrative flows finely.\n\nWeakness:\n\n-> There can be further clarification about the experimental settings.\n\n-> Some proof steps do not naturally connect. Specific comments are in the following section.\n\n-> I suggest the authors submit core code for numerical experiments.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "icSL_R2fo4", "reviewer": "Reviewer_vfZ6", "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": "", "summary_of_the_paper": "The paper proposes a novel algorithm to deal with Byzantine resilient decentralized optimization for data training. ", "summary_of_the_review": "The paper proposes a novel algorithm to deal with Byzantine resilient decentralized optimization for data training, which has better performance compared with some existing works. However, the idea behind the algorithm is not clearly explained. In particular, the role of the \\tau parameter and the adaptive selection process for \\tau_i is unclear to me. ", "strength_and_weaknesses": "+ The algorithm dose not rely on additional graph connectivity\n+ The performance is better than some existing algorithms\n\n- The algorithm does not guarantee accuracy of the optimization process\n- The idea behind the algorithm is unclear. In particular, the Clipping idea involves a parameter \\tau but its role is not well explained and illustrated. \n- The paper has an adaptive selection process for \\tau_i, but it cannot be computed only rely on local information. In particular, it involves \\delta_max, which seems not an available information. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QeGQ-vnF5K", "reviewer": "Reviewer_wSS2", "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": "", "summary_of_the_paper": "This paper studies byzantine robust decentralized learning. In this setting, a fraction of workers is byzantine. First, the paper argues why the consensus is vulnerable to byzantine attacks, then they propose DISSENSUS, a decentralized attack to steer away from the true consensus. Finally, they come up with a robust called aggregation self-centered clipping which converges to a neighborhood of a stationary point. ", "summary_of_the_review": "The aggregation strategy proposed in the paper has been suggested before and is not a novelty of this paper. But, the authors provided a study of this method in a decentralized setting and did a good job comparing it with previous methods and providing experiments that support their idea. Compared to the previous versions of the paper, the authors add more comparisons with previous results in control/optimization literature. In summary, the strengths outweigh the weaknesses.", "strength_and_weaknesses": "-Weaknesses\n1)The aggregation strategy proposed in the paper has been proposed before and is not a novelty of this paper. Moreover, the idea of centralized clipping is not new, for example, paper [1] looked at this idea before in distributed setting, and this paper is an extension of that to the decentralized setting.\n[1]Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. \"Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing.\" arXiv preprint arXiv:2006.09365 (2020).\n-Strength\n1)The reviewer did a good job reviewing relevant papers.\n2)The paper does a good job of motivating the problem.\n3)The experimental results are sound.\n", "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": "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:

Decision: Reject