Unified Breakdown Analysis for Byzantine Robust Gossip
Authors: Renaud Gaucher
Aymeric Dieuleveut
Hadrien Hendrikx
Venue: ICML 2025 poster (2025)
Keywords: Byzantine
robustness
decentralized
distributed
optimization
gossip
breakdown
Primary area: optimization->large_scale_parallel_and_distributed
TL;DR: A new analysis for Byzantine-robust gossip, with tight breakdown and convergence guarantees.

Abstract: In decentralized machine learning, different devices communicate in a peer-to-peer manner to collaboratively learn from each other's data. Such approaches are vulnerable to misbehaving (or Byzantine) devices. 
We introduce F-RG, a general framework for building robust decentralized algorithms with guarantees arising from robust-sum-like aggregation rules F. We then investigate the notion of *breakdown point*, and show an upper bound on the number of adversaries that decentralized algorithms can tolerate. We introduce a practical robust aggregation rule, coined CS+, such that CS+-RG has a near-optimal breakdown. Other choices of aggregation rules lead to existing algorithms such as ClippedGossip or NNA. We give experimental evidence to validate the effectiveness of CS+-RG and highlight the gap with NNA, in particular against a novel attack tailored to decentralized communications.

Distributing the training over a large number of devices introduces new security issues: software may be faulty, lo- cal data may be corrupted, and nodes can be hacked or Unified Breakdown Analysis for Byzantine Robust Gossip
Renaud Gaucher 12 Aymeric Dieuleveut
Hadrien Hendrikx
Abstract
even controlled by a hostile party. Such issues are modeled as Byzantine node failures (Lamport et al., 1982), defined as omniscient adversaries able to collude with each other. Standard distributed learning methods are known to be vul- nerable to these Byzantine attacks (Blanchard et al., 2017). This has led to significant efforts in the development of ro- bust distributed learning algorithms. From the first works on Byzantine-robur SGD (Blanchard al., 2017; Yin et al., 2018; 8; Alistarh al., 2018; El-Mhamdi al., 2020), meth- ods have been developed to tackle stochastic noise using Polyak momentum (Karimireddy et al., 2021; Farhadkhani et al., 2022) and mixing strategies to handle heterogeneous loss functions (Karimireddy et al., 2023; Allouah et al., 2023). In parallel to these robust algorithms, efficient at- tacks have been developed to challenge Byzantine-robust algorithms (Baruch et al., 2019; Xie et al., 2020). Recently, (Allouah et al., 2025) have used pre-aggregation adaptive clipping to improve the robustness. To bridge the gap be- tween algorithm performance and achievable accuracy in the Byzantine setting, tight lower bounds have been con- structed for the heterogeneous setting (Karimireddy et al., 2023; Allouah et al., 2024). Yet, all these works rely on a trusted central server to coordinate the training.
In decentralized machine learning, different de- vices communicate peer-to-peer manner to collaboratively learn from each other's data. Such approaches are vulnerable to misbehaving (or Byzantine) devices. We introduce F-RG, gen- eral framework for building robust decentralized algorithms with guarantees arising from robust- sum-like aggregation rules F. We then investigate the notion of breakdown point, and show an upper bound on the number of adversaries that decen- tralized algorithms can tolerate. We introduce practical robust aggregation rule, coined CS,, such that CS.-RC has near-optimal breakdown. Other choices of aggregation rules lead to existing algorithms such as ClispedGossip or NNA. We give experimental evidence to validate the effec- tiveness of CS,-RG and highlight the gap with NNA, in particular against novel attack tailored to decentralized communications.
1. Introduction
In contrast, the decentralized case has been less explored. Especially when the communication network, abstracted as a graph where vertices represent computing units that communicate through edges, is not fully connected (a.k.a. sparse). For instance, understanding how many Byzantine nodes can be tolerated over an arbitrary network before communication protocol fails is an open question (that we address in this paper). Indeed, the network is often assumed to be fully connected (EI-Mhamdi et al., 2021; Farhadkhani et al., 2023). If the work of (Fang et al., 2022) addresses the case of sparse networks, they only consider homogeneous losses. Closer to our setting, He et al. (2023); Wu al. (2023) tackle Byzantine optimization on sparse networks with heterogeneous losses, however, they only achieve suboptimal robustness, as their guarantees vanish with either the number of nodes or the connectivity of the network. Moreover, the communication scheme proposed in He et al. (2023) relies on inaccessible information. Similarly, there is lack of attacks designed to challenge decentralized optimization. Up to our knowledge, only He et al. (2023) propose one, named Dissensus. Still, few previous works
Distributed machine learning. in which the training pro- cess is performed on multiple computing units (or nodes), responds to the increasingly distributed nature of data, its sensitivity, and the rising computational cost of optimiz- ing models. We investigate the decentralized paradigm of distributed learning, in which nodes communicate in peer-to-peer manner within a communication network, in opposition distributed architectures relying central server that coordinates all units.
'Centre de mathématiques appliquées, École polytech- nique Institut Polytechnique de Paris, Palaiseau France "Centre Inria de l'Univ. Grenoble Alpes, CNRS, LJK, Greno- ble, France. Correspondence to: Renaud Gaucher <re- naud. gaucher@eeeepe hotpeaoo@oottccccuuuc......
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Unified Breakdown Analysis for Byzantine Robust Gossip
(Wu et al., 2023; Farhadkhani et al., 2023) have investigated generic criteria to go from communication schemes robust distributed SGD frameworks.
2. Background
2.1. Decentralized optimization.
We consider a system composed of m computing units that communicate synchronously through a communication net- work, which is represented an undirected graph G. We denote by H the set of honest nodes, and B the (unknown) set of Byzantine nodes. Each unit i holds local parame- ter æ; E R local loss function f: : R - I, and can communicate with its neighbors in the graph g. We denote the set of neighbors of node i by n(() and by nx(+) (resp. ng((i) the set of honest (resp. Byzantine) ones. We study decentralized algorithms for solving
Our work proposes a generic method to design algorithms that solve the aforementioned shortcomings. To do so, we carefully study the decentralized mean estimation problem. This seemingly simple problem retains most of the difficulty of handling Byzantine nodes while allowing us to derive strong convergence and robustness guarantees. Our solution relies on robust adaptations of the gossip communication, popular scheme for decentralized communication. We then tackle general (smooth non-convex) optimization problems through a reduction. Our contributions are the following:
{
1- Unifying algorithmic framework. We develop generic method (the RG method) to construct and analyze robust communication algorithms. It is based on the decentralized application of robust aggregation rules. This RG method re- covers NNA (Farhadkhani et al., 2022) and ClippedGossip (He et al., 2023) in specific cases. We use the RG method to build CS,-RG, a novel communication algorithm that both practical and adapted to sparse communication network.
arg min EER
(f((t)
1 17
Σ fi(z)) iE
(I)
Due to the averaging nature of Equation (1), centralized algorithms for solving this problem rely on global averaging of the gradients computed at each node. In the decentralized setting, we rely on performing local (node-wise) inexact averaging steps instead.
Gossip Communication. Standard decentralized opti- mization algorithms typically rely on the so-called gos- sip communication protocol (Boyd et al., 2006; Nedic & Ozdaglar, 2009; Scaman et al., 2017: Kovalev et al., 2020). The gossip protocol consists of updating the pa- rameter of a node i through linear combination of the parameters of its neighbors, with updates of the form 2t ++ = x - 17 Eن= Wey -x)), where wey is a weight associated with the edge (ij) of the graph and vj 2 will denote communication step-size. By denoting W the Laplacian matrix associated with the weighted graph G, i. W = Wwy if + j and Wt: = -Ejen() Wiy. and denot- ing the matrix of parameters as X = (x1....., the gossip update conveniently writes:
2 Tight theoretical guarantees. We show that RG pro- vides robust convergence guarantees as soon as the underly- ing aggregation rule verifies (b, p)-robustness, new robust- ness criterion that we introduce, and the weight of Byzantine nodes is not too large (with respect to the algebraic con- nectivity, a spectral property of the communication graph). We also show the converse result, that is, robustness guarantees can be obtained if the weight of Byzantine nodes exceeds this threshold. Our bounds match each other for specific aggregation rules. These results generalize the stan- dard fully-comnecee breakdown point of 1/3 of Byzantines nodes to arbitrary sparse networks.
then
Besides these core contributions, we introduce a theoreti- cally grounded attack, called Spectral Heterogeneity, specif- ically designed to challenge decentralized algorithms by leveraging spectral properties of the communication graph.
x++ = X' n/
(2)
The Laplacian matrix (a.k.a. gossip matrix), is symmet- ric non-negative. When the graph is connected, its kernel is restricted to the line of the constant vectors, i.e. span(1.... ..... 1)T. In the following, we will always con- sider that the graph G is weighted, so that a unique Lapla- cian matrix is associated with each graph G. Moreover, we denote by (9x) and p2(Gx) the largest and smallest non-zero eigenvalues of the Laplacian matrix WH of the honest subgraph Gn, and by y = p2 422())/ (mx) its spectral gap. Spectral properties of the Laplacian matrix are known to characterize the convergence of gossip opti- mization methods. For instance, in the absence of Byzantine nodes, Equation (2) with step-size 1j Pmax to a linear convergence of the nodes parameter values to- wards the average of the initial parameters: |X X 12
The remainder of the paper is organized as follows. Sec- tion 2 formalizes the problem of Byzantine-robur decen- tralized optimization. Section 3 presents the robust gossip framework as well as the main convergence guarantees. Then, Section 4 instanciates the general framework with several rules (and the associated robustness guarantees), and provides guarantees for a D-SGD algorithm based on F-RG. Finally, Section 5 presents the Spectral Heterogeneity at- tack, which is then used with other attacks to experimentally challenge several aggregation schemes in Section 6.
(g) (
leads
2

---

Unified Breakdown Analysis for Byzantine Robust Gossip
(1-n X - 12 for X the matrix with columns n -5 3.
properties of the honest subgraph, meaning that for a given communication network, these properties change depending the location of Byzantine failures, and the associated graph can either fall within I Hmmm. if Byzantines are "well spread", or not, e.g. if they are adversarially chosen.
Robustness Issue. Gossip communication relies on updat- ing the nodes' parameters by performing non-robust local averaging. As such, similarly to the centralized case, any Byzantine neighbor of node i can drive the update to any desired value (Blanchard et al., 2017). Then, the poisoned information spreads through gossip communications.
Approximate Average Consensus. The average consensus problem consists in finding the average of vectors locally held by honest nodes (æi))EH. It is specific case of Equa- tion (1) obtained by considering fi(x)) = | 1:1? Due to adversarial attacks only approximate estimate of the average of honest nodes vector In := [7|] |7||- Eiex can be reached (Karimireddy et al., 2023). We therefore intro- duce the following criterion to assess the robustness of a communication algorithm.
2.2. Byzantine-robust decentralized optimization.
In this section, we describe the threat model and the robust- ness criterion that we consider.
Threat model. We consider Byzantine nodes to be unknown omniscient adversaries, able to collude and send distinct val- ues to each of their neighbors. We measure their influence by considering the weight of Byzantine nodes in the neigh- borhood of each honest node, (b(i)= == Ejena() Way) iEN (as in LeBlanc et al. (2013); He et al. (2023)), instead of the total number of Byzantine nodes |B] as done for the centralized or fully- connecce setting. Similarly, we denote by h(i) Σjenz(() Wij the weights of the honest nodes adjacent to the node
Definition 2.2 (r-robustness on G.). Let < 1. A com- munication algorithm Alg is r-robust on a graph G if from any initial local parameters (æi) E (Rd)², allows any honest node to compute a vector x.." such that
1 174
|
T. 122 S r
x - -xx12
7H
E
IEW
Imposing r < 1 means the honest nodes' parameters have to be strictly closer (on average) to the initial mean after the communication than before. It thus requires that the reduction of the variance of nodes parameters Var (x)
In the case of an arbitrary communication network, the num- ber of honest nodes does not provide enough information by itself, as the results depend on how the nodes are linked, i.e., the topology of the honest subgraph. Therefore, in the case of sparse topologies, it necessary to consider a prop- erty of the graph related to its structure rather than relying solely on the number of honest nodes. We will show that spectral properties of the Laplacian of honest subgraph are relevant quantities for robustness analyses and introduce the following class of graphs.
Var (x is larger than the bias | xzZ 1l2 introduced by the Byzantines, with Varæ (x) xx 1|2 Remark that the r-robustness of an algorithm graph G states that single use of the algorithm strictly re- duces the average quadratic error. However, it does not mean that multiple uses would result in a geometric decrease; in- deed, we cannot simply use induction as 3 7 F.
== |7|] "EEN ||2;
Definition 2.1. For any Mmin 2 0 and b 2 0, we define the class of weighted graphs
3. The Robust Gossip Framework
We now introduce a generic framework, which relies two key building blocks: (i) generic update form, depending on an aggregation function F (I&+ x Rd)" + Rd, and (ii) a set of those aggregation functions F, referred to as robust summation functions. We then show that the combination of these two blocks, i.e., the generic update used with a robust summation function F, leads to a robust decentralized algorithm, hence the name: Robust Gossip.
"mmmmbb = =(o s.t. (2(9g) Mmin and max b(1) < b) NEH
In other words, we introduce subset of all possible graphs partitioning in terms of (i) the second smallest eigenvalue of the honest subgraph, (a.k.a. the algebraic connectivity), that is restricted to be larger than a minimal value Mmins and (ii) the maximal weight of Byzantines in the neighborhood of an honest node, which is restricted to be smaller than b.
We finally show that this framework leads to (near- Joptimal robustness guarantees for well-chosen F.
Note that if all edges are equally weighted (wiy = w),, then B(1) (i) -w,, and (ii) boils down to upper bounding the number of Byzantines in the neighborhood of honest nodes by f := -1 Hence, Definition 2.1 is an extension of the standard "there are at most f byzantine nodes among the [B| + | nodes" " to the setting of arbitrary connected graphs. We point out that this class of graphs depends on the spectral
3.1. The Robust Gossip Method: adding robust differences instead of averaging robustly.
We call aggregation rule function F; (RR x Rd) + gd meant to aggregate a set of vectors (#))ee()) E (IRd)" with weights (wx)ie(n) E Ry. For n) > 0 a communication step- size, the associated robust gossip algorithm (coined F-RG)
3

---

Unified Breakdown Analysis for Byzantine Robust Gossip
consists, for any honest node E H of the communication network G, in updating its parameter an; using:
3.3. Convergence of RG under (b, roobustnsssss.
As briefly discussed in the introduction, the goal of commu- nicating is to reduce the variance, which comes at the price of bias. This is unavoidable since communicating allows nodes to inject wrong information which biases the system.
2 = - -,F ((wi), L; - Zy))E(())
(F-RG)
Crucially, each node applies the (robust) aggregation rule F to (w), 2z)jen()) == (wij. F. Ty))en()) ie. to the dif- ferences of its parameter with those of its neighbors, and uses this estimate to update its parameter. Thus, Equa- tion (F-RG) recovers the standard gossip update from Equa- tion (2) if F' is the weighted sum operator (which is unfor- tunately not robust). Hence, we will look for aggregation functions that are robust versions of the weighted sum.
In the following core result, we show how (b, p)-bousssnesss enables us to tightly quantify how much a single step of F-RG reduces the variance, and how much bias is injected.
Recall that Varx(ar) - [ EiEn ||:; - Fzll is the vari- ance of honest nodes.
Theorem 3.3. Let F be a (b. p) summation, b and
Pmin be s. 2pb S Mmins and G E I Mmin. Then, assuming 1) S Munax (9x) -1, the outpui (ar DiEH of F-RG verifies:
In contrast, directly averaging the parameters of the neigh- bors, even with robust aggregation rule, would highly suffer from heterogeneity. Indeed, this leads to biased estimate of the mean of initial parameters for sparse commu- nication graphs. Extra assumptions, such as homogeneity of the local objectives, are thus needed to alleviate this prob- lem (Fang et al., 2022).
[M] Lien | - T S (1 (1-1) (Umin 2pb)) (arz(
| Fxll 1| S 2pb Varu(
Thus, F-RG is (1-1) (Pmin - rrobust for G E I Pimin
Meanwhile, the RG method uses intrinsically decentralized updates, allowing for tight convergence guarantees in sparse communication graphs with heterogeneous local objectives. The strength of the RG framework is to turn any robust summation into a robust gossip algorithm. As such, one can focus on the design of robust aggregation functions without worrying about the decentralized aspect.
While the bound on 1j depends on the honest subgraph, as (m S (m) 7 can be set conservatively by evaluating Mmax on the whole graph. Note that while r- robustness is guaranteed for the whole class I pomindd ds the value of will depend on the actual graph within the class.
Chaining aggregation steps. When low variance levels are required, it is necessary to perform several robust gossip steps one after the other. This contrasts with the centralized setting, in which the variance can be brought to zero in one step. While the variance reduces at a linear rate, the bias accumulates as multiple aggregation steps are performed. We provide bounds for t steps of F-RG in the following Corollary.
3.2. Robust Summation Functions.
Our analysis of F-RG relies on aggregation rules that meet the following robustness conditions.
Definition 3.1 ((b, pr-bbusst summation). Let b, 2 O.
An aggregation rule F (R+ x Rd)=" + Rd is a (b, p)-
Corollary 3.4. Let F be a (b, r)-bbust summation, let b and Muni be such that 2pb S Punim and let G e I V.maab. We denote 8 = 2pb and 7 = pminn/ Mwnin/Mmax Panaa (Gr). -pmin Then, for (x)))es 120 obtained from any (aq))ee through (xf (e(t))ees = F-RG(( =F-RG((x')Es)) ((es)))) with 1- Mmax ( (GH)
robust summation if, for any vectors (2)) E (R
any weights (Wi)ee(n] E Re and any S c [n] such that
Eie3 wi S b (where 5 = [m]]s)),
F [((, z))EEm)) - Σ wizz iES
S pb Σ
wi 12.1?
iES
{ Varh( S (1 (1-1111110 71 (1-1-)) 6))* Varx(a)), |latk axlll -15(1-11-712-0017 v (arr
In (F- (F-RG), S is the set of honest neighbors ni), while S is the set of Byzantine neighbors ni((). We will exhibit several (b, p)-robust summation rules, including a practical rule for p = 2, in Section 4.
1-V1-2(1-0)
Consensus is thus reached, Varz(x') 70 O, and
Remark 3.2. The latter definition differs from (f,x)- robustness (Allouah et al., 2023) we upper bound the error using the second moment of vectors within S instead of their variance. Note also that (f, robbuussssss is stated with con- stant weights only. Therefore, if F is (f, r)rbbus,,,, then F is a (b. robuutt summation with e.g. uniform weights wi= = 1n(nn - f) with b- = f/(n- - f) and p = n/b.
| - < 7(1 -8 Varx(
45
(3)
While the total L2 error (bias plus variance) is guaranteed to decrease after a single step by Theorem 3.3, it may in- crease if several F-RG steps are performed because of bias accumulation. This happens when the factor multiplying the

---

Unified Breakdown Analysis for Byzantine Robust Gossip
variance in Equation (3) is larger than I, which essentially means 7 S 8. Despite this bias, the output of the result- ing robust aggregation procedure is (arbitrarily) close to consensus, which can be desirable. Proofs of Theorem 3.3 and Corollary 3.4 are respectively given in Appendices D.1 and D.2.
graph's is spectral gap. This gap rapidly shrinks with the size and the lack of connectivity of the graph, making the condition orders of magnitude worse for large sparse graph. In Wu et al. (2023), the breakdown condition is 8b / /Hl = Pmin. which means that the robustness guarantee decreases when the number of honest nodes increases. For instance, only a // fraction of Byzantine nodes is tolerated for fully conne-co network, whereas we tolerate up to 1/s.
Dependence on the parameters. As expected, the bias increases with the amount of Byzantine corrptiio (through 5) and decreases the graph becomes more connected (i.e, 7 + 1). One can then use parameter yy (up to its maximum value) to control the bias-variance trade-off.
We conclude this section by two remarks on potential alter- native characterizations of the breakdown point.
Remark 3.6 (On algebraic connectivity). Theorem 3.5 does not imply that a given communication algorithm system- atically fails as soon as 26 2 p2((), but rather that since there exists a graph for which it is the case, one can not have an r-robust algorithm with an assumption based on (2( and b looser than (2( 2 2b. Yet, one can still prove breakdown points using other graph-related quanti- ties, which might lead to tolerating b >> Pumin/2 Byzantine nodes for specific graph architectures. This gap is standard in the decentralized optimization literature, where optimal algorithms depend on the (square root of the) spectral gap of the gossip matrix (Scaman et al., 2017; Kovalev et al., 2020), whereas iteration lower bounds proven in terms of diameter of the communication graph.
3.4. Spectral limit of r-robust decentralized algorithms.
We now provide an upper bound on the weight of Byzantine neighbors that can be tolerated by any algorithm running on a communication network in which the honest subgraph has a given algebraic connectivity.
Theorem 3.5. Let Pain 2 0, 62 0 be such that Pmin S 26. Then for any h 2 O and any algorithm Alg, there exists a graph G E T Paiuchh in which all honest nodes have a weight of honest neighbors hu(i) larger than h, and such that for any < 1, Alg is not r-robust on G.
We refer the reader to Appendix E for the proof details. It follows from Theorem 3.5 that when a theoretical guarantee quantifies the robustness of an algorithm on a graph through Mminn we must have 2b- < Mmin- Importantly, this upper bound on the breakdown point is independent of the total weight of honest neighbors.
Remark 3.7 ciimenionnddeendden breakdown points). The Approximate Average Consensus problem (Section 2.2) is related to the Approximate Consensus Problem (ACP) (Dolev et al., 1986), in which the nodes must converge to the same value while remaining within the convex hull of the initial parameters. This is harder problem, since the ACP cannot be solved using iterative communication system of m nodes with f Byzantine failures in dimension d if m S (d 2) + 1 (Vaidya, 2014). This dependence on the dimension d is prohibitive for ML applications. On the contrary, our definition of r-robustness only requires the algorithm to improve the average squared distance to the target value, which is enough for D-SGD to converge, and enables us prove Yet, it would be interesting to link their notion of r-robust networks (LeBlanc et al., 2013) with algebraic connectivity.
For a fully-connected graph with uniform weights w, we have (z(Sxx) w w|H and b(i) = w w.. Then, the previous condition boils down to |7|| > 2| i.e. there is less than 1/3 of Byzantine nodes, which recovers known necessary robustness conditions of distributed system (Lamport et al., 1982; Vaidya et al., 2012; El-Mhamdi et al., 2021).
Near-optimal breakdown point. Theorem 3.5 states that uniformly ensuring robussttssss on I Hm & is impossible as soon as 2b |'iin and we know that update (F-RG) is r-robust as soon as 2pb < Pmin- Therefore, no (p, b)- robust summand exists with p < 1, and (F-RG) achieves the optimal breakdown if a (b, 1)-ruuust aggregation rule is used. Such rules exist, as shown in Section 4, but are unfortunately not practical, as they require prior knowledge on the Byzantine nodes. It is an open question whether p 1 can be achieved using a practical rule.
wwwpsniiiiiiiiedeeeeeee breakdown.
4. From the general framework to practical decentralized algorithms
In this section, we first define robust summation rules and link our general framework with existing decentralized ro- bust algorithms in Scction 4.1. Then we prove convergence for Decentralized-SGi based on F-RG, in Section 4.2.
Nevertheless, we propose practical robust summation rule that achieves = 2, thus robust if 4b < /mmin- This is a significant improvement over existing works. For example, in He et al. (2023), the 4b < Hmin condition is essentially replaced by cb < Mumi (e.g., for regular graphs) where e > 0 is a large constant, and 7 = n2(Gx)) (Gxx) the
4.1. Examples of (b, p)-robust rules
Several methods have been proved to be (f, k)-robust, in- cluding the Coordinate- Wise Trimmed Mean (CWTM) (Yin
5

---

Unified Breakdown Analysis for Byzantine Robust Gossip
et al., 2018), the Coordinate-wise Median (CWM) (Yin
Remark 4.2 (Concurrent work). Allouah al. (2025) study the influence of an adaptive clipping scheme, named Adap- tive Robust Clipping (ARC), with the same adaptive clip- ping threshold as CS However, they use it before any aggregation function (J, k)-robust F, and only analyze the robustness of F o ARC, making their approach orthogonal to ours, Moreover, their focus is on the federated case.
al., 2018), the Geometric Median (GM) (Yin al., 2018; Pillutla et al., 2022) and Krum (Blanchard et al., 2017). It follows from Remark 3.2 that they are also (b. p)-robust summation.
However, since (b, p)-robust summation is weaker than (f, robbustssssss we can introduce robust aggregation methods using this new perspective with tighter robustness guarantees. The following introduced aggregator either recover existing algorithm, or are tighter than previous ap- proach. In their defimition, (w,, z.)ee(n) E (R+ x R" and S C [nx] such that 3z I b.
Next, we define oracle (or.) threshold functions. Those require the knowledge of the set S to be computed, which eventually corresponds to being able to identify which node is honest and which node is Byzantine. This is obviously not reasonable assumption in practice. Even though, it shows that the optimality gap is not inherent to clipping, since oracle choice of threshold is optimal. Furthermore, the guarantees from He et al. (2023) rely on such assumptions
Geometric Trimmed Sum (GTS), Assume w.l.o.g. that ([==)))xemii are sorted, i.c. || S ... S || ll. and we denote k" (b) :- max(k E [n]] Liza Wi 2 b) the index of the largest vector which has at least weight b of vectors larger than it!. (GTS) computes (b) = Ei> wi b, and outputs
Oracle Clipping. Let CS = CS( : where T.th (ww,, Zi)ie(n); S) = mmax ( ( 22: Eies wi | 2
Oracle clipping (He et al., 2023). CS = CS( :
(WI,(WN = (b)
+
wiz.
where oor ((ws, 2i)ee(n; S) = v Eies wi ||2:||
(b)
As shown below, CS leads to an optimal breakdown point. On the contrary, CSit only achieves = 4, despite its oracle aspect. Proofs of Theorems 4.1 and 4.3 are given in Appendix
In the simpler case where the weights are 1 and E [n]] GTS consists in discarding the b largest vectors within (21) and summing the rest.
Clipped Sum (CS). Given a threshold function T: (R, x yd)" + R,, output the mean of clipped vectors:
Theorem 4.3. Let 8 2 0, then CS is (b, (b,p)) with p p= 1, and CSH, is (b, pr-ruusst with p = 4.
CS((W,, 2))ie(1) = 1 wi Clippzz: T ((wi, z))ie()))
When instantiated in specific settings, our framework gives tight convergence guarantees (improving on the existing ones) for existing algorithms.
where Vz E RR, 7 e R,, Clip(z;;)
min(11=1] #).
Proposition 4.4. (F-RG) recovers existing algorithms.
|
1. GTS- RG, on a fully connected communication network G with constant weight, corresponds to Nearest Neigh- bors Averaging (Farhudkhani et al., 2022, NNA).
We propose the following threshold function?, which leads to practical and nearly optimal aggregator.
2. CS RRG recovers ClippedGossip (He et al., 2023).
Practical Clipping (CS.). Let CS. == CS((-i+)) where
4.2. Byzantine robust Distributed SGD on graphs
7+ (ww,, 2))se(n)) == max T 0: Σ W/ 1 1|x/1/27 2 2b
We now give convergence results for a D-SGD-type algo- rithm that uses (F-RG) for robust decentralized aggrega- tion. Several works on Byzantine-robust SGD abstract away the aggregation procedure by relying on contraction proper- ties (Karimireddy et al., 2021; Wu et al., 2023; Farhadkhani et al., 2023), so that global D-SGD convergence follows from the robustness of the averaging procedure. Our Corol- lary 4.8 builds on the (a, Ae-reduttinnn from Farhadkhani et al. (2023):
This rule corresponds, in the specific case of unitary weights wi = and E [n]], to defining the clipping threshold as the 21th largest value within || . || I || (i.e., ||=x-(20) l))- We now provide robustness guarantee for these two aggre- gation rules in the following theorem.
Theorem 4.1. Let b O, then GTS is 0= 4, and CS, is (b, proruusst with 2.
with 'hhen weights sum to 1, k- is quantile function.
Definition 4.5 ((a, redductio)..... A coordinating phase v verifies an (a. -)-reduction if, from any initial local param-
Note that Clipped Sum cannot he (b, prouutt summation when the threshold function is a fixed constant 0: the clipping threshold must be adaptive to the input vectors.
II their experiments, they propose practical (i.e. non-oracle) threshold function that is not supported by theory.
6

---

Unified Breakdown Analysis for Byzantine Robust Gossip
eters (æg)sen E (IR each honest nodes E H obtain parameter vector anj upon the completion of v such that
(Bounded noise) There exists 2 0 s.t. Vo E Rd.
[IIVV(( Et) ([(())]1 0² for all i [H].
3. (Heterogeneity) There exist <> 0 s.t. Vo Rd
1
|
x
मे DiEn [z) (x) <
[H]
H
KEH
K
We can now state the guarantees of Algorithm 1.
Ftl 11
TH 12
H
Corollary 4.8. Lel F a (b, p)- summation, let b and let G weighted graph such that 5 =2p/ u2 (9H))))))))))))))(() ) < 1 and of spectral gap ? p2 Pmax (9r). ( Under As- sumption 4.7, for all i E H. the iterutes produced by Al- gorithm / on 9 with = 1/Mmax(9) and learning rate Top (1/vT)) (depending also on problem parameters such as L, y or 6), verify as increases:
E
Remark 4.6. (a, A)-reduction and r-robustness are closely related quantities since (a, A) reductions implies r- robustness with r I a + X, and r-robustness implies o, À S r. Yet, r-robustness explicitly requires that < 1, unlike (a, A)rreduction. essence, r-robustness expresses more precisely that nodes benefit from the communication.
T
111 =0
C² 7(1 7(1-5)VT 72(1 - 8)2
Lo
The (a, A) requirements on the aggregation procedure ex- actly match the guarantees of Theorem 3.3: using one single step of F-RG as a coordination phase leads to y6, and using multiple communi-
+
1
( 1 -z
))
(
Varx( = =0
a = ===1-1d 1-1 cation steps leads to a and À 48/>(1-))* 61) We build on this abstraction to propose Byzantine robust decentralized stochastic gradient descent framework.
(1-1)))))) - 5) and
T
Performing (1- steps of F-RG between each gradient computation leads to:
We consider Problem 1, where we assume that each local function ft is a risk computed using a loss on data distribution D,, i.e fi(x)) = EE-D. [V((x. E)]. We solve Problem 1 using D-SGD over a communication network g. Robustness Byzantine nodes is obtained using (F-RG) as the aggregation rule, coupled with Polyak momentum used moving average reduce the stochastic noise.
T M T
Lo
8
852
E
VT
7(1 - 8)2
7(1 5)
It follows that those guarantees state that performing more aggregation steps between gradient computations improves the asymptotic error but under an additional communication cost.
Algorithm 1 Byzantine
D-SGD with F-RG
This corollary is the consequence of the combination of our Theorem 3.3 with Theorem 1 of Farhadkhani et al. (2023). The result is simplified using 5 2 [H/|_1 and y < 1. We refer the reader to Appendix for more precise result and detailed proof.
Input: Initial model x!! E Rd local loss functions fi, initial momentum m O. momentum coefficient 3 = O, learning rate Nop. communication step size 1), communi- cation graph G. upper bound on Byzantine weight b. for t = 0 to T do
for E H in parallel do
5. Attacking robust gossip algorithms
Sample noisy gradient: g (z()) + E
Update the momentum: m 3m 1-1 + +1-13)g
In this section, we design an attack that aims to disrupt robust gossip algorithms. To do this, we model communica- tions as perturbations of a gossip scheme, and analyze their impact the variance among nodes, which allows to deduce what perturbation Byzantines nodes should enforce for effective attacks. Recall that X (.f...., ff)))²
Optimization step: x, ++//2 x1 - m:
Send n; ++1/2 to the neighbors nii).
Update the model with F-RG 1+%/,
xt = F-RG
(x:
[a 1// m()))
end for end for
R [H| #d|xd denotes the matrix of honest parameters at commu- nication round t. Each step of F-RG can be decomposed as a perturbed gossip update (ef. Lemma D.
The convergence results of this algorithm rely on the follow- ing standard assumptions.
x H = (Ix - W), + E
(4)
Assumption 4.7. Objective functions regularity.
Where E' is the perturbation term due to Byzantine nodes. In the following. we assume that [E'}, = ç for any honest node where af is the direction of attack on node
1. (Smoothness) There exists L 2 0, s.t. Vx, y E Rd [V])(=) V)(()) s LlI - yll-
7

---

Unified Breakdown Analysis for Byzantine Robust Gossip
SpH
ALIE
Dissensus
FOE
10a
train loss
10a
109
10
2
4
6
10
4
10
2
6
10
4
6
10
b
RGG --- -----G
ClpppedGossip
......
IOS
Figure 1. Training loss achioved by GTS RG, CS.-RGG, RG. ClippedGossip and IOS on MNIST (a 1) after 300 optimization and communication steps. The honest subgraph graph is 9x 1mm defined in Appendix E. Thus, w2(GH) = 16.
i, and Ç is scaling factor, which is chosen to bypass the defenses. Typically, if Ç is small, Byzantine node j E uB (i) can declare to node i the parameter æ) = 2 + çaa).
(least-connected) components. Our Spectral Heterogene- ity attack consists in taking at = e fied leads Byzantine nodes to cut the graph into two by pushing honest nodes either plus or minus e'/ied
fied Kili which
Dissensus Attack. Byzantine nodes can disrupt decentral- ized communication by maximizing the variance of the honest parameters. A natural decentralized notion of vari- ance is the Laplacian heterogeneity Σijen Wiy ||æ; æyll? which corresponds to X W..- Finding at such that this heterogeneity is maximized at + writes
6. Experimental evaluation.
We follow Farhadkhani al. (2023) (on which the of our code is based), and present results for classification tasks on MNIST and CIFAR-10 datasets, well as plain averaging tasks. We refer to Appendix C for most of the experiments. Similarly to Farhadkhani et al. (2023), het- erogeneity is simulated by sampling data from each class using Dirichlet distribution of parameter a. We test the attacks Spectral Heterogeneity (SpH), Dissensus, A Little Is Enough (ALIE) (Baruch et al., 2019), and Fall of Em- pire (FOE) (Xie et al., 2020). The main differences with Farhadkhani et al. (2023) are the following
arg max (IH W) X 1 Wx [B))-=<aa
arggaa max 2n Wx X ; E²) o(1))) [
For small 77, this suggests to take of = W X Ejena(t) (2) x)). This choice of a corresponds to the Dissensus attack proposed in He et al. (2023). However, as gossip communication usually operated with multi- ple communication rounds, maximizing only the pairwise differences the next step is short-sighted approach.
ii) We consider sparse communication networks. (ii) We implement GTS-RG, instead of NNA, and ClippedGossip (aka (SHe-RG) is implemented the adaptive rule of clipping of (He et al., 2023) instead of a fixed threshold. We additionally implement IOS
Spectral Heterogeneity Attack. Byzantine nodes can take into account the fact that several rounds of communication will occur, and focus on increasing the heterogeneity over the long term. This leads, at any time t. to maximizing for any 2 the pairwise differences at time f 8, i.e, finding
(Wu et al.. 2023).
(iii) We add Dissensus and Spectral Heterogeneity attacks. (iv) We modify the generic design of attacks to adapt really to the decentralized setting.
arg max W WH [B)),={aa
2 X :
E + o(1)).
See Appendix B for detailed experimental setup and our implementation available https:
com/ Tenauugaucherr/yyaatii.io Robbussstteen-eooeeetteoeooooote Gossip.
Taking s + leads to approximating WH(IN 22 as a projection on its eigenspace associated with the largest eigenvalue W*(1x - )2, This eigenspace corresponds the space spanned by the eigen- vector of WH associated with the smallest non-zero eigen- value of WH, i.e (2(Gx) This eigenvector (denoted efed) is commonly referred to as the Fiedler vector of the graph. Its coordinates essentially sort the nodes of the graph with the two farthest nodes associated with the largest and small- est value. Hence, the signs the values in the Fiedler vector are typically used to partition the graph into two
In Figure 1, it appears that the SpH attack is more efficient in disrupting ClippedGossip. GTS- RG and IOS than Dis- sensus and ALIE, and that CS,-RG is highly resilient the setup considered. In this setting with a rather simple learn- ing task, the connectivity of the graphs appears as the major limiting factor to the robustness of distributed algorithms, hence why Spectral Heterogeneity is very efficient.
8

---

Unified Breakdown Analysis for Byzantine Robust Gossip
7. Conclusion
bust federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
This paper revisits robust averaging over sparse communi- cation graphs. We introduce a general framework for robust decentralized averaging, which allows us to derive tight con- vergence guarantees for many robust summation rules. In particular, we introduce one that nearly matches an upper bound on the breakdown point, i.e., the maximum number of Byzantine nodes an algorithm can tolerate. Our experi- ments confirm that our theory correctly sorts the breakdown points of the existing methods, and that some (such as NNA) fail before the optimal breakdown point. We introduce new Spectral Heterogeneity attack that exploits the graph topology for sparse graphs to obtain this result. An inter- esting future direction is the characterization of robustness when the constraint on the number of neighbors cannot be met globally. but convergence can be obtained within lo- cal neighborhoods. Conversely, this opens up questions on which nodes an attacker should corrupt to maximize their influence for specific graph, in light of our results.
Baruch, G., Baruch, M., and Goldberg, Y. A little is enough: Circumventing defenses for distributed learning. Ad- vances in Neural Information Processing Systems, 32, 2019.
Blanchard, P., EI Mhamdi, E. M., Guerraoui, R., and Stainer, J. Machine learning with adversaries: Byzantine toler- ant gradient descent. Advances in neural information processing systems, 30, 2017.
Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. Random- ized gossip algorithms. IEEE transactions on information theory, 52(6):2508-255 -530,, 2006.
Dolev, D., Lynch, N. A., Pinter, S. S., Stark, E. W., and Weihl, W. E. Reaching approximate agreement in the presence of faults. Journal of the ACM (JACM), 33(3): 499-516, 1986.
Impact Statement
El-Mhamdi, E.-M., Guerraoui, R., Guirguis, A., Hoang, L. N., and Rouault, S. Genuinely distributed byzantine machine learning. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 355-364, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
EI- BI-Mhamdi, E. M., Farhadkhani, S., Guerraoui, R., Guirguis, A., Hoang, L.-N,, and Rouault, S. Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). Advances in Neu- ral Information Processing Systems, 34:25044-25057, 2021.
Acknowledgments
The work of Aymeric Diculeveut and Renaud Gaucher was supported by French State aid managed by the Agence Na- tionale la Recherche (ANR) under France 2030 program with the reference ANR-23-PELA-000 (REDEEM project). The work of Aymeric Dieuleveut was also supported by
Fang. C., Yang, Z., and Bajwa, W. U. Bridge: Byzantine- resilient decentralized gradient descent. IEEE Transac- tions on Signal and Information Processing over Net- works, 8:610-626, 626, 2022.
Hi!Paris- FLAG chair.
References
Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, Byzantine machine learning made easy by resilient averaging of momentums. In International Con- ference on Machine Learning, pp. 6246-6283. PMLR, 2022.
Alistarh, D., Allen-Zhu, Z., and J. Byzantine stochas- tic gradient descent. Advances in neural information processing systems, 31, 2018.
Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, J. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1232-1300. PMLR, 2023.
Farhadkhani, S., Guerraoui, R., Gupta, N., Hoang, L.-N., Pinot, R., and Stephan, J. Robust collaborative learning with linear gradient overhead. In International Confer- ence Machine Learning, pp. 9761-9813. PMLR, 2023.
Allouah, Y., Guerraoui, R., Gupta, N., Pinot, R., and Rizk, G. Robust distributed learning: tight error bounds and breakdown point under data heterogeneity. Advances in Neural Information Processing Systems, 36. 2024.
Hastings, W. K. Monte carlo sampling methods using markov chains and their applications. 1970.
He, L., Karimireddy, S. P., and Jaggi, M. Byzantine-robust decentralized learning via clippedgossip, 2023. URL http:////axxiv..gaa////e/ss
Allouah, Y., Guerraoui, R., Gupta, N., Jellouli, A., Rizk,
G., and Stephan, J. Adaptive gradient clipping for ro-

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Karimireddy, S. P., He, L.,, and Jaggi, M. Learning from history for byzantine robust optimization. In Interna- tional Conference on Machine Learning, pp. 5311-5319. PMLR. 2021.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. Byzantine- robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5653 PMLR, 2018
Karimireddy, S. P... He, L., and Jaggi, M. Byzantine-robust learning on heterogeneous datasets via bucketing, 2023. URL httpp::://axxvvvvrrro..oo abs/ 6..0006000 09365.
Kovalev, D., Salim, A., and Richtárik, P. Optimal and practical algorithms for smooth and strongly convex de- centralized optimization. Advances in Neural Information Processing Systems, 13:18322-1835, 2020.
Lamport, L.,, Shostak, R., and Pease, M. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382 401, 1982.
LeBlanc, H. J., Zhang. H., Koutsoukos, X., and Sundaram, S. Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications, (4):766-781, 2013.
Nedic, A. and Ozdaglar, Distributed subgradient meth- ods for multi-agent optimization. IEEE Transactions Automatic Control, 54(1):48-61, 2009.
Pillutla, K., Kakade, S. M., and Harchaoui, Z. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70: 1111111214444 2022.
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference on machine learning, pp. 3027-3036. PMLR, 2017.
Vaidya, N. H. Iterative byzantine vector consensus in incom- plete graphs. Distributed Computing and Networking: 15th International Conference, ICDCN 2014, Coimbat- ore, India, January 4-7, 2014. Proceedings 15, pp. 14-28 28. Springer, 2014.
Vaidya, N. H., Tseng, I.., and Liang, G. Iterative approxi- mate byzantine consensus in arbitrary directed graphs. In Proceedings of the 2012 ACM symposium Principles of distributed computing, pp. 365-374, 2012.
Wu, Z., Chen, T., and Ling, Q. Byzantine-resilles decen- tralized stochastic optimization with robust aggregation rules. IEEE transactions on signal processing, 2023.
Xie, C., Koyejo, O., and Gupta, I. Fall of empires: Breaking byzantine-tolere sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270.
PMLR, 2020.
10

---

Unified Breakdown Analysis for Byzantine Robust Gossip
A. Additional Discussion
A.1. Asynchronous communications
In the core this paper, we assumed that all communications were synchronous. However, our F-RG framework can be readily adapted to operate in less synchronous settings.
Suppose that communication still occurs in rounds, but messages take variable amount of time be delivered. If each honest node waits receive messages from all its neighbors before performing aggregation step, then Byzantine nodes can prevent the honest nodes from updating simply by withholding their messages. To be robust against such behavior, the nodes should not wait for all messages before updating their parameters.
The F-RG framework adapts naturally to this setting. Specifically, consider a (p, b)-robust summand F, and assume that each honest node performs the F-RG update as soon as has received messages except those corresponding to a total weight of at most b. Then, this asynchronous version of F-RG remains (1 v7Pmin proposition demonstrates.
as the following
Proposition A.1. Let F (R+ x (R + Rd be a (b, ro-but summation. Let Fasma denote the rule that applies F to all imputs (w,, ()) excluding an arbitrary subset Stetaged C. [n)] of smaller than b, i.e. Eie Eitttayee W; b. Then Fasyn. a rrobust summation rule.
Proof. Using the triangle inequality, (a + b)2 < 2(a² 122) and Jensen inequality and the definition of robust summation yields
Fasum. ((Wi, Zi)iE(n)
Σ
Wizi EE
F( 21)e
Wiit
Wi
Selnl\,Sdetaged
iE SESSSael
2
[(wes Zi)eE
Σ
Wi
E
wizz
iE(n])
iESTSaddayed
2
Wi
2
wizi
+
21 VESNSdolayed
iE [[[m])(Sattayee
< 2 pb
Σ
wil|za|1 +
Σ
will willzi1??
iESNSactugeu
Now, since necessarily p 2 1, finally yields
Fasyn. ((Ws, zi)ie(m))
Σ w;
S 2pb
Σ
we w
Remark A.2. In the above result, used the fact that there exists (b, p) -robustt summand with p < as shown in
Theorem 3.5.
Remark A.3. The latter proof can be refined using (a (a² < (1+e)a² + - with an optimal choice of e, showing that Fasga. at least (b, p -robust
A.2. Choosing the graph's weights
Our analysis requires that each edge of the graph be associated with a nonnegative weight and that the communication step size satisfies S 1/Hmaxx (9x). Although unitary weights Wi = 1 are convenient for identifying b as an upper bound on the number of Byzantine neighbors, they require adjusting the step size 17 using global information from the graph, such as Umax(() (g)-1 practical way to circumvent this use bistochastic weights.

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Generic Bistochastic Matrix. Any bistochastic matrix B E [0, 1|mxm can be used to define the weights of the graph using wij Bij. In this case, the Laplacian matrix is defined as W = B. and its largest eigenvalue is upper-bounded by 2. The communication step size can thus be chosen as 1 1/2.. Note that, in such case, the condition A2l (2)))) 2 2p is implied by 7 2 2pb, where ý is generally named the spectral gap of the bistochastic matrix B, and is defined as 3 = pea ,1+11 |14,, where sp( B)) denotes the eigenvalues of the matrix B.
Metropolis-Hasting Weights (Hastings, 1970). The Metropolis- Hasting algorithm constructs bistochastic matrix by making each node declare to their neighbors their degree d, Then, any pair of neighbors (i, defines the weight on their edge Wij 1/max (d, nodes, since for i H. and B the influence of j on i is bounded by Wij S प. Interestingly, since the size of the communication step can be chosen as 1) 1/2 without further knowledge of the global network properties, this choice of weights requires only local information to carry out the communication.
++ d,)+1 As pointed out in He et al. (2023) this algorithm is robust to corrupted
B. Experiments
B.1. Detailed Experimental Setup
B.I.1. ATTACK DESIGN
Our experimental setting is built on top of the code provided by Farhadkhani et al. (2023), with the following differences:
1. Each honest node receives different messages from Byzantine nodes: for an honest node E H. the Byzantine node E (i)(i) declares to node at time t the vector æÿ = x + Çfa.. The reference point taken is the parameter of node i, instead of the average of all parameters z performed in (Farhadkhaní et al., 2022). Indeed, æi can be very far from the vectors in the honest neighborhood of node i since the network is not fully connected. Note that in opposition to (Farhadkhani et al., 2022), Byzantines declare different parameters to each of the honest nodes. Not only does it allow the use of attacks such as Dissensus and spectral heterogeneity (though the choice of a;), but it also allows to tune & differently for each node.
2. Each scaling parameter Ç is designed separately through a linear search, such to maximize for each honest node
F F( =z))En(())
Σ (Enx()
wiy(2; 2zy)
3. The vector at is defined differently depending on the attack implemented: Dissensus, Spectral Heterogeneity (SpH), Fall of Empire (FOE) from Xie et al. (2020) or little is enough (ALIE) from Baruch et al. (2019).
Dissensus. The Byzantines j E (i( take as attack vector a; = W = - Wij (x) -e/).
Spectral Heterogeneity. The Byzantines j E (i) take as attack vector at = [e T denotes an eigenvector of WN associated with (42 (W+).
fted Kl.. where e
ALIE. The Byzantine nodes compute the mean of the honest parameters उyz and the coordinate-wise standard deviation of. Then they use the attack vector a o².
FOF. The Byzantine nodes uses af = =- Z
Remark B.I. In the case trimming base rules, a badly designed attack leads Byzantine messages to be removed during aggregations, which induces the resulting algorithm behave plain non-corrupted D-SGD algorithm. Thus, proposing non-over-confident experimental proofs of trimming-basee aggregation requires fine design of the attacks.
1.1.2. ALGORITHMS TESTED
Networks. Two topologies of the honest subgraph are investigated: 1) A "Two Worlds" graph, i.e. GH == [9m= (0m=13,--8,.1)4 2) Randomly sampled Erdos-Renyi graphs, with varying probability of edge presence p. All graphs are equipped with unitary weights on the edges, for simplicity.
Communications, We compare
12

---

Unified Breakdown Analysis for Byzantine Robust Gossip
GTS-RG;
CS,-RG;
The version of ClippedGossip proposed in He et al. (2023) with an adaptive clipping rule which is not supported by any theory. Precisely, ClippedGossip is equivalent to CSH,-RG, with CSHe := CS THe), where, for || S S ||
THe (ww (m)) v Ex LisIn((t) wi +
Iterative Outlier scissors (IOS), from (Wu et al., 2023).
F-RG based methods uses
= Pmax (max(9x)
Optimization. All learning experiments implement Algorithm 1, and only the communication part changes among experiments. It follows that, even though IOS is not explicitly combined with momentum in (Wu al., 2023), still implement it with momentum. We do this to have fairer comparison between communication routines since (Farhadkhani et al., 2023) showed that momentum is key for robustness.
B.1.3. DATASET PROCESSOESSING
MNIST images receive an input image normalization of mean 0.1307 and standard deviation 0.3081. The images of CIFAR- 10 are horizontally flipped, and per-channel normalization is applied with means (0.4914, 0.4822, 0.4465), and standard deviation (0.2023, 0.1994, 0.2010).
B.1.4. DATA HETEROGENEITY
We simulate data heterogeneity in the correct nodes' datasets following the method of (Farhadkhani et al., 2023) by making nodes sample from each class of the considered dataset (MNIST or CIFAR-19) using Dirichlet distribution of parameter > 0: the smallest o, the more probable it is to sample from one class only.
1.5.5. MODEL ARCHITECTURE AND HYPER PARAMETERS
To present the detailed architecture of the models used, we adopt the following compact notation:
L(#outputs) represents fully-connected linear layer, C(output channels) represents 2D-convolutional layer of kernel size 3 and padding 1, R stands for ReLU activation, B stands for batch-normalization. and D represents dropout with probability 0.25, S stands for log-softmax and NLL for negative log-likelihood loss.
The architecture of the model used and the experimental setup are proposed in Table 1.
Table 1. Detailed experimental setting
Dataset
MNIST CNN
CIFAR-10
Model type Model architecture
CNN
C(10-R-M-L(10)S
((22)-B-R-M-CCG)BBBBRR
M-CC122)------111229)9
R-D-L(10)-S NLL
Loss
NLL 64
Batch size
64
Learning rate
Mopp 0.1
Mop 0.5
Momentum
3 0.9
3 0.99
Number of Iterations
T = 300
T = 5000
Number of honest nodes
|H| 26 Two Worlds k
|H| 20
| 16
Graph
Erdös Renyi E |0.26, 1]
Two Worlds
Graph parameter
k 6
Data Heterogeneity
1
= 5
Byzantine weight
b E (1...., 11}
b = 3
b = 3
Number of seeds
1
13

---

Unified Breakdown Analysis for Byzantine Robust Gossip
C. Experiments
In Appendix C.I we provide experiments with two world graphs taken as a communication network, both on learning tasks with MNIST and CIFAR-10 datasets, and on an averaging problem. Both on the MNIST and averaging task, we varying amount of Byzantine weight to investigate the empirical robustness of each algorithm.
In Appendix C.2 we provide experiments on Erdos Renyi networks MNIST and an averaging task. We study here the influence of the connectivity of the network on the robustness by varying the probability of each pair of honest nodes being connected.
C.1. Experiments with Two World graphs
For both the Averaging experiments and the MNIST experiments, we fixed the subgraph of honest nodes to be GH := (0m=13.==,.=1)), and the weight of Byzantine b varies. Note that Theorem 3.5 predict that, on this graph, no algorithm can be r-robust when >
Averaging experiments (Figure 2). Recall that Gz := 10m built on two fully connected cliques of 13 honest nodes, which are then connected. Here we initialize the parameters of honest nodes with a N (u, Ia/d) distribution (d 5), where u is equal +5, O......0 0)7 for one of the two clique, and equal (5, 0, ... 0) for the other one. For each setting (b, Communication Algorithm, Attack), correspond the mean square error Eien || æ*ll / Σien
perform experiments with 6 random seeds. The error plotted iEW || " achieved after 100 communication steps. The line corresponds to the average value among seeds, while the confidence interval corresponds to the maximum and minimal
values encountered.
FOE
SpHl
Dissensus
10
MSE /MSE"
109
10
10-2
10-3
10
5
10
-SG
CTS-RG
ClppeedGussip
IOS
Figure Relative MSE on an averaging task after 100 communication steps on a Two-Wold graph, with varying weight of Byzantines b, Here (2(HH) 16.
MNIST experiments (Figure 3). Experiments are conducted with a heterogeneity parameter a = 1. The error and accuracy displayed are after 300 iterations. Further experimental details are Table 1.
14

---

Unified Breakdown Analysis for Byzantine Robust Gossip
SpH
ALIE
Dissensus
FOE
0.75
accuracy
0.50
0.00
4
G
10
10
b
SpH
ALIE
Dissensus
FOE
102
train loss
10a
10a
10
2
6
10
8
10
2
6
10
4
8
10
b
CS,-RG
GTS-RG
ClippedGossip
JOS
Figure 3. Accuracy and training loss on MNIST 300 optimization and communication steps, Two Wold graphs, with varying weight of Byzantines neighhors. Here (9xx = 16, and a 1.
CIFAR-10 experiments (Figures 4 and 5). Experiments are conducted CIFAR-10 Dataset with heterogeneity parameters 5, Two Wold graph Gz == (5m=8.8x6,cce 1| with b 1. Further experimental details are in Table 1. We provide both test accuracy and train loss since the dynamic of the train loss does not always impact the test accuracy, specifically in the case of Spectral Heterogeneity and Dissensus attacks.
4
4
D-SGD
D-5GD
Train loss
3
-RG
Train loss
3
-RG
ClippedGossip
CippedGossip
105
2
105
1
1
0
0
0
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
Iteration
Iteration
4
4
CS* RG GTS-RG
CS CSG
Train loss
3
Train loss
3
GTS-RG
ClippedGossip Ios
OippedGossip
2
2
10S
1
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Iteration
Iteration
Figure Train loss on CIFAR-10 (a = 5) on Two Wold graph with (2(Sx) 12 ALIE (upper right), SpH (lower left), and Dissensus (lower right).
Attacks tested are FOE (upper left),
15

---

Unified Breakdown Analysis for Byzantine Robust Gossip
1.00
1.00
Test accuracy
Test accuracy
0.75
0.75
0.50
D-SGD
0.50
D-5GD
CR*
-RG
GTS-RG
GTS-RG
0.25
ClippedGossip
0.25
OippedGossip
10S
105
0.00
0.00
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Iteration
lteration
1.00
1.00
Test accuracy
Test accuracy
0.75
0.75
0.50
D.SGD
0.50
D.SGO
CS*
CS -RG
0.25
ClippedGessip
0.25
ClippedGossip
105
0.00
0.00
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Iteration
Iteration
Figure Accuracy on CIFAR-10 (a 5) Wold graph with p2(9x) 12 and b 1. Attacks tested FOE (upper left). ALIE (upper right), SpH (lower left), and Dissensus (lower right).
C.2. Experiments with Erdos-Renyi graphs
Experiments are conducted by using, as a subgraph of honest nodes, random Erdos Renyi graph with 20 honest nodes. Each honest node always adjacent Byzantine nodes. On each seed, test 12 different values of p [0.25, 1], where P denotes the probability of edge exist. We plot the links between the algebraic connectivity of the graph (denoted μ22. the second smallest eigenvalue of the unitary weighted Laplacian) and the losses.
Averaging task (Figure 6). Nodes' parameters are initialized using N(0, Is) distribution. Nodes perform 100 (robust) gossip communication iterations, and the gain in terms mean square error is plotted. Experiments are conducted on 6 different seeds, and curves are smoothed using a moving average of size
ALIE
FOE
SpH
Dissensus
MSE" /SSEE
0.01
3
7
15
17
11
13
15
19
13
17
11
15
122
f12
122
CS,
CTS-RG
ClippedGossip
Figure Averaging task. Relative MSF after 100 communication steps on randomly sampled Frdos-Renyl graphs with a fixed 4.
MNIST (Figure 7).
The heterogeneity among nodes set to a All experiments run on the same seed.
16

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Dissensus
SpH
ALIE
FOE
train loss
le1
leU
1o-1
10
15
20
0
10
15
20
0
10
20
10
15
20
SpH
ALIE
1.00
accuracy
0.75
0.50
0.25
0.00
15
10
20.
10
20
15
f4g
P2
CS.,RG
GTS-RG -TS--RG
ClippedGoesip
-..e.-OOS
Figure 7. Accuracy training on MN after 200 optimization communication steps on randomly sampled Erdos- Renyi graphs with a fixed = 4.
D. Analysis of RG
D.1. Proof of Theorem 3.3
We now prove Theorem 3.3, and then use to derive convergence for the Byzantine- decentralized stochastic gradient descent framework. Recall that nodes follow the update scheme below.
w ++ x² -nF ((wizi at - a)))En(()) i E
(5)
xf|1
if
We recall the following notations
Before proving Theorem 3.3, we recall the following notations:
Wij Wij 2 0 denote the weight associated with the edge ~ j on the graph.
(xc )
The matrix of honest parameters X
RIHixd
(T)
The error due to robust aggregation and Byzantine corruption:
Vi E H,
E
Σ
wiy (af a²)) F ((wijaa) af))En(()
(Enx())
Lemma D.1. Equation (5) writes
x = (Ix 17 W X E
Proof. Let E H. We decompose the update due to the gossip scheme and consider the error term coming from both robust aggregation and the influence of Byzantine nodes.
17

---

Unified Breakdown Analysis for Byzantine Robust Gossip
nxtt = a. - 11 ((wiy: - az))En())
o Σ
wis(ar 2t}) + 11
Σ
wislar - at)) - F ((wey - sddsents)
(Sn
)EnH(()
Finally, the proof is concluded by remarking that [W EjenZ()) Wiy(at (i We begin by controlling the norm of the error term | 12 in the case of CS.-RG.
- =z)).
Lemma D.2 (Control of the error). Assume F is (b, p) robust summation. Then the error is controlled by the heterogeneity as measured by the Laplacian matrix:
E S 2pb| X Iwn pb Σ
wijllæk - 20,11
(EH.JENN(1)
Proof. We recall that in this case,
Vi H, ET):
Σ
way(at - 2//) F ((wij x)))en(s))
jEnN(()
By assumption, for all honest node E H. the weight of Byzantine in his neighborhood is smaller than b, i.e Σ Thus, applying the (b, p) robustness of F yields
Ejeno(s) wis S
E
Σ
Σ
Wir x4)) - F ((wig) =)))En(i))
iCH
(E)
$ Σ pb Σ
Wiy ||a! 2/11
jERM(
ppb X W
Where the last equality follows by noting that 2/ X| = EEE W//|= - a311 Indeed, considering that Gx is an undirected graph, E nz(())
+ j E nz (i) and we have:
X k (XH, Hi
W 7 Xx)
Σ
Wiglat at))
(+)
Wis (x) x x3))
iEH jEnx(i)
Σ
Σ
Wij (o)) - xg -w/)
(E)
x =
Σ
Wij ||0 2 11.
ieH.
Now that we control the enror term, we can conclude the proof of Theorem 3.3 using standard optimization arguments. Before proving this theorem, we prove the following one, from which Corollary 3.4 is direct.
18

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Theorem D.3. Assume F is (b, p) robust summation, and RG is the associated robust gossip algorithm. Let b and Puin be such that 2pb S Panin and let 9 E T -mitub- Then, for any 1) S Mmmax (9x) 2, the output y RGG(a:) (obtained by one step RG on G from Φ) verifies:
11,
1
|
++1
H.H
1+1
12 (1 (Mmin 2pb))
Σ
|
(6)
176
KE
EEH
2pb H
-
Σ
||
- 1221?
iEH
Proof. Part I: Equation (7).
Equation (7) is a direct consequence of Lemma D.2. Indeed applying Pin == [H] 1x 111 the orthogonal projection on the kernel of WH on Lemma D.I results in
Pi X PIn (Ix - n + 1,,,, E' Pi X + n E'.
Taking the norm yields
P1 n X Pix x =,/ P1 E11 S 1/ /
(8)
We now apply Lemma D.2, and use that Mmax (97) is the largest eigenvalue of WH. It gives
Pin PI X PI x 2|? s 17 22bb X li,.,
S Pmax (G+) 2 2pbli([x - PI xx
Finally, Equation (7) derives from [Pi,, X HIKE
[EjeH FheeH//lee 2THEH TTHLE and mp (M S 1.
Part II: Equation (6).
We denote by W H the Moore-Penrose To prove Equation (6), we consider the objective function (1 - P1x)x pseudo inverse of WH. We begin by applying Lemma D.I.
[IIH PI ) X 2
||X| W
X + 1/ 11 Pax) 2n|
-|
x W X Ea)
+ X
E"
(IN (Ix P
(Ix P(x))
f P 2n X X W.'EE)
+n² V((''),... Wn
X W E²
Applying 2(a, b) = =2 + |b|l - ||a b12 leads to
W Fr 2
| [1 (xxx
X 2 [Ix Pan) - x W'
1) X W E²
+ 1
(9)
Wx
Wx
+ +1²
X
w 7 E²
w3
= =- X
2
E² 1|
W Ex 12
+ +1²
x - W Edd
Wx
+ 1/
W
?
Wx
W
We now apply that (4) (resp. (2(Gx)) is the largest (resp. smallest) non-zero eigenvalue of WH.
x lixx- X ( x -n X WM. + 1
E 2 111 Mrnax (Gx)
X
W W E 1
u2 ((x)
Wn
Eventually Lemma D.2 with the assumption 17 S 1/Pmex(Gxx yields the result
| 113 1i -p, - X 1| (1y P(n)) (1
2pb
||
mz(Gx)
19

---

Unified Breakdown Analysis for Byzantine Robust Gossip
1x-1111 H 11 x S (1 (1-))s111110 (1-))2(GH))
(1 (1- M2(HH) ())
2pb
))
X (IN PAN))
To obtain Theorem D.3, we note that we can actually control the one-step variation of the MSE using (1 - 77/min - -2pb)
only, thus strengthening the first inequality. We rewrite the first part of Theorem 3.3 below for completeness.
Corollary D.A. Assume is a (b, p) robust summation, and RG is the associated robust gossip algorithm. Let b and pman be such that 2pb S Pmin- and let G E I pemin Then, for any 1j S (max((r) the output y = RG(x)) (obtained by one step of RG on from x>) verifies:
|
xze 1 < (1 77 (Mmin -2pb))
Σ iE
|
xtel1
H
H
Proof. We consider Equation (8) and Equation (9), which write
11 X PIx
1112 = =1 1 E²1
-1 | 1-1-111 11 11 ,,
X 1 Pi 1 - X I + + E' W
follows from the bias- variance decomposition of the MSE
| PIn
11 x
PIx X X
P1x X Pix x
H
that
X PIx
X 2
| fe PIN) S -n - x
+ 1 lww + 1 E²I1
S S-n X I
+ " "#x)
|| || (Ix (IN-Pin) + 1
P1 E²1
As S (6x)
5 ] we eventually get
|| 1x H
PI X 12 S x (Tx Pax)) - ">1l + (2(H)) |
x lit -P1x) - 17 (1-- 2pb
He((r)) ) | l
$ (1 1 m)2(9H) (1- 11=
2pb )0bb))
x -Pa))'
Which concludes the proof.
D.2. Proof of Corollary 3.4
direct consequence of the above results is Corollary 3.4, as we show below.
Proof. Using the (a, A) reduction notations, we have:
a 1 (1- 5))
1 = 78.
We denote here the drift increment de+1
PL, X ++1
PA X and the variance at time t as of 1 '1
lli Pax)
Corollary D.4 ensures that
2 + de s ao?
20

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Hence,we have 0441 + 41 S aoz and of41 I aoz which implies that of S 004/200- This proves the first part of the result. Using this, we write that Theorem D.3 ensures that
de1 S Viols VāB'O0,
leading to:
T-1
T-1 VX
Vā(1 - aT
Σ de S Vx
Σ
2 0o
00,
1 1 122
which proves the second part. The last inequality is obtained by writing.
P1 X PIx x
S
00-
1=1
Then, we use that S I-VI-x S 2 for 0, with =7(1- 7(1-8)
E. Proof of Theorem 3.5 Upper bound on the breakdown point
We recall Theorem 3.5:
Theorem E.1. Let Punin 2 0, b 2 O be such that Pmin S 2b. Then for any h 2 and any algorithm Alg, there exists a graph G E I Manin in which all honest nodes have a weight of honest neighbors h(i) larger than h, and such that for any Alg not r-robust on
We recall that, since the Byzantine nodes are unknown, given a communication network and an algorithm Alg, the honest nodes follow Alg independently of the position of Byzantine nodes in the network. Thus, it is only when the position of the Byzantine nodes satisfies some hypothesis that Alg can be r-robust.
Here we consider the hypothesis H (u2(GN) = 2b} n {max:e b(1) S b}. We show that for any algorithm and any 0, there exists communication network A which any algorithm Alg is not r-robust for (at least) one configuration of the Byzantines that verifies the hypothesis H.
The structure of the proof is thus the following:
1. We introduce family of unweighted communication networks {Nm,k ) J me(]) such that Ni,,k admits three symmetric configurations of Byzantines nodes with 2m honest nodes and m Byzantines nodes, and each honest node is neighbor to k Byzantine nodes and m + & honest nodes. Then we show that an algorithm can not be r-robust in these three configurations with < 1.
2. Now, for 2 0, let's denote km, the weighted graph with uniform weight on the edges and such that Gm,k. is weighted version of one of the three above-mentioned configurations of Nm, We show that:
(a) The weight of Byzantines in the neighborhood of any honest node is equal to b ck.
(b) The algebraic connectivity of the honest subgraph [Gm,k,c]H verifies:
(z((Gm,,.el))) = 2ck = 2b.
(c) For any 2 b, there exists a graph within Men.kellmmMN.emm.....r such that all honest nodes have a weight associated to honest neighbors h(2) larger than h.
This concludes the proof.
21

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Figure 8. Topology of Nm=4,
E.1. Definition the family of graphs
Let m No and & E [m]]
We define the communication network Nm, as composed of three cliques of m nodes: C₁ C2 and Cz. Each node in C is additionally connected exactly l nodes in C++1 mod a and nodes in C--1 mod 3. Moreover, those connections are assumed to be in circular order, i.e., for any E [m]] node in C₁ is connected to nodes j, ......J + k mod m in C++1 mod
We assume that one of the eliques is composed of Byzantine nodes, each honest node having Byzantine neighbors, and there are m Byzantine nodes among the 3m nodes.
E.2. No algorithm can be a-robust on Nm.k-
We now show that no algorithm can be robust on the communication network Nm,k-
Lemma E.2. Let unknown clique within C2 C2 and C3 be composed of Byzantine nodes, then communication algorithm is a-robust on Nm.k-
Assume an r-robust algorithm exists on the communication network GH,k- Informally:
1. We first show that if all nodes within clique hold unique parameter æ, and receive this parameter from nodes of either of the two other cliques, then they cannot change their parameter.
2. We then consider a setting where the two honest cliques hold different parameters, and we conclude that Byzantine nodes can force all honest nodes to keep their initial parameter at all times. This shows that in the considered setting,
r is impossible.
Proof.
Part I. Let Alg be an algorithm r-robust on Nm.k with r < 1. We denote x the output from node after running Alg.
We know that one of the cliques say C1. is composed of honest nodes. Let the honest nodes within C₁ hold the parameter æ. Nodes in another clique, say C2, declare the parameter well, while nodes in C3 declare another parameter, say y A We show that all nodes E C₁ must output the parameter 2;
From the point of view of nodes in C₁ considering that the Byzantine clique is unknown, it is impossible to distinguish between these situations:
1. Situation I: C2 is honest, and C3 is Byzantine,
2. Situation H: C2 is Byzantine, and C3 honest.
22

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Thus the outputs of nodes in C1 after running Alg, denoted (ar )sec the same in both situations.
In Situation I, nodes of C2 are honest, and nodes in C1 and C2 have the same initial parameter; hence, the initial quadratic error is O. The criterion writes
Σl |
TH 11 S
TH = 0.
EEH
iEH
It follows that for any node in C1, of i.e., nodes in C₁ do not change their parameters (in both Situation I and Situation II).
Part II. Consider the setting where C and C2 are honest, while C3 Byzantine, and that nodes C hold the parameter æ, while nodes in C2 hold the parameter y + æ.
As Byzantine nodes declare different values their different neighbors, nodes in C3 declare to nodes in C1 that they hold the value æ. and to nodes in C2 that they hold the value y. Following Part I, nodes in Ci and in C2 cannot update their parameter, (i.e. Vi E H. x xz)) Applying the r-robustness property brings:
Σ
|
xx| =r Σ |
Enl
EH
ICH
iEH
which implies that 2 since
Eieh || IzHl" 12 > 0. follows that the Algorithm Alg is not r-robust on Nm, for an
r
<<
F.3. Spectral properties of the graph.
define as Gm, the graph associated with the network Nm, where all edges have weight and the nodes one the three cliques are Byzantine.
We show here that /2 (a((Gm,k,c) 2kc. This concludes the proof have:
1. The weight of Byzantines in the neighborhood of any honest node is equal to = ck;
2. Which is linked to the algebraic connectivity of the honest subgraph μz (2 = c2k;
3. While the weight of honest nodes the neighborhood of honest nodes equal to / c(m + k), thus growths to infinity with m.
Analysis. We denote Lu the Laplacian of [9m, (9m,, the honest subgraph of the network Nm, in which we provided unitary weights to edges. We show that μ2 (I0m, 2k, which brings that
= 2kc.
Lemma E.3. The second smallest eigenvalue of the (unitary weighted) Laplacian matrix Lx of kmm is equal to (2(xx) = 2k.
Proof. Recall that m A m. Let M E pmxm a circulant matrix defined as = E J9, where denotes permutation
1
0
0
0
1
0
J
1
0
0
The Laplacian matrix of the honest subgraph of GH.K can be written as:
(mim
1m
T
0
kImm
-M
L
0
mIm
1m
IT
+
-MM
kIm
23

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Hence
Im 1
0
-
(MT
0 M
Lx = (k mm)
(10)
0
1m 1
0
This matrix decomposition allows to have the eigenvalues of the the matrix Wg.
Lemma E.4. The eigenvalues of LH are {0, 2 U {K + m = E w i:p {l..... 1}} where exp( 2
To prove the Lemma E.4, we first need to following result.
Lemma E.5. If A a symmetric matrix in R2mx2m, which can be decomposed as - is matrix with complex eigenvalues .o...... 1mm11-
M
where M RRxmm
MT
Then the eigenvalues of A are (=ppp O, O,..., m 13
Proof of Lemma E.5. Let M = U DU be the diagonalization of M where D = matrix, i.c UU* I where we denote as U U² the conjugate transpose of U, where the (simple) conjugate matrix denoted U.
and U is unitary
Lemma E.5 follows from
(N=" M =
0 STTD -Ur
DDDU) 0
D.DU A=A
0
DU
DU
0
Hence
U 0
0
9)
A
U
D
0
D
simple calculus (using that D is diagonal) yields that all eigenvalues of
are { 0, ..... 1).
D
0
Proof of Lemma E.4. We start from the decomposition of Equation (10)
1n I 0
)
(10
0 M
Lu = (k + m2m
0
1m 12.
M
0
We first notice that the subspace spanned by +1,,+ and (1 - is an eigenspace of 1mm 17
0
0
1
1
associated the eigenvalue m, and the orthogonal subspace associated with 0. Furthermore these are eigenvectors of
( M 0 associated with i and kk It follows that they are eigenvectors of Lu with eigenvalues and 2k. We notice
M)
as well that the three matrices of Equation (10) can be diagonalized in the same orthogonal basis.
The matrix M is circulant matrix, it can be diagonalized in C. The eigenvalues {Mp Ed=o WP9: f0...., }}}, where ws = exp( 2im ). The eigenvector associated with is Tp (1,w², .up,.....lo (m- (m-1) As such, with U m
11) and Diag(Po.... (...p.........----.. M writes:
U-U-DU.
0 M
Mf are (+|upl:p = 0..... .mm1) considering that p = corresponds
Considering Lemma E.5, the eigenvalue of
MT
0
to the eigenvalues +k and -k: kt, hence the eigenvectors are (+1ppl:p = O...m .. 1}.
(1 1T) and (1 - 11T we deduce that the eigenvalues Lx
24

---

Unified Breakdown Analysis for Byzantine Robust Gossip
End of the proof of Lemma E.3.
To prove Lemma E.3, considering the decomposition of Equation (10), we only have to show that m A is always the second largest eigenvalue of the matrix
mm 1
+ (NTT m)
B:
1 I
First, considering Lemma E.4, the eigenvalues of are {m + m we-kk-kk-- ( E f1...., m-13] with Mp = Σg=0 wPO As such showing that 1ppl I k p E (1...., m - 1} yields the result.
As w = o = 1, we have that Σ wP wP) = 0. Hence, for E (1,...,,, m 1], as w 11,
k-1
WPO = 0 = 1D Σ
wh
Σ w
0=0
9=0 0
It follows from |س|| 1 that for p E m 13. 1pl S m - k.
F. (b, -robust summation rules
We recall the definition summation rules. Definition F.1 ((b, p)-robust summation). Let b. 0. An aggregation rule F (R+ x Fd R is a roobuut summation, when, for any vectors (zi)iE(M) E (R any weights (w;)iE(n) E R and any set S C [r]] such that Eies Wi < b, there is
F(wm, ((WHii))iEt)) zili(m) - -- wizt
S pb Σ wil1zi11?
iES
iES
where 3 = [n]
F.I. Clipping
We first prove the robustness of the clipping-based summation.
Proposition F.2. Let b 2 0, then
1. (Practical) CS is (b, (b.p)-robus) with p = 2.
2. (Oracle) CS is (b, probust with p 1.
3. (Oracle) CSor is (b, probust with p 4.
Proof. Let (wi, 2i)xe(1) E (R4, Rdy, and [m]] such that Eig wi b,
We consider for 2
F(we 2i) zi)i=l,...) Clip(#a7).
Then, by applying the triangle inequality we have
Σ Wi
Σ FES
Wi (Clip(zA:T) - -2;) + Σ
w. (1;T(
iEs
iE
2
Σ
wi wi|lz; Clip(zzT) + Σ
will Clip(z,;
iES
iES
2
Σ
Wi (|| - -T) + bt
(1))
163
Where we used EiE3 wi S b.
25

---

e elipped S 2b. Note that, if somehow is possible choose the clipping threshold such that the weight of clipped vectors within S is equal exactly to b then this factor 2 disappears. Which correspond to oracle clipping threshold Torr The same result can be achieved when it is possible to identify a subset of {1...., n of weight 2b which includes the set 5, and if the weight with 3 sums exactly to b. This is for instance the case of the communication Unified Breakdown Analysis for Byzantine Robust Gossip
1. Case of our clipping threshold.
We choose T as
max T 0:
Σ wi 1 121127 2 20 2 Tours ((wi, =))eE(
This corresponds to lowering the clipping threshold until the sum of the weights of clipped vectors is essentially equal to 26. This ensures that the total weight of the honest vectors that are clipped falls between b and 2b. If there ties at the clipping threshold, honest vectors can be arbitrarily denoted as clipped or non-clipped. Indeed, there is no clipping error incurred since the clipping threshold is the same as the actual value of the difference. Therefore, we do not have to accumulate error for the weight over 20, so the following equation always holds:
2h 2 Σ
wi 1 clipped 2 b.
iE
Which allows us to write:
Σ IS
wi (1Izil - -T) + b S
wi(l zil| - -T + bt
iES
<
wi |2 1 dipppod
iE
We conclude the proof using the Cauchy-Schwand inequality:
2
F F(Wws 2:)(=1,...))
Σ Witt
Σ
will zill
iES
iEE
Σ
wi w clipped
Eweel willlzlll?
LES
YES
< 26
wi |
iES
Where used Σ Ejenz(i) Wiy ر
graph used in Appendix E: nodes in (for instance) C1 know that Byzantines nodes are among the nodes within C2 and C3. thus selecting all their neighbors that belong to these two other cliques leads to a subset of neighbors of weight 26 with exactly a weight b corresponding to Byzantine neighbors.
2. Clipping threshold of He et al. (2023) We plug in Equation (11) the following upper bound:
[||= - -)+ = T
1
)
5
T
2 S
1
| 2
T
+
72
+
T
This yields
2
|z 2
(((rr)2)) =:):=I....))
Σ wi
Σ
Wi
+ bt
T
NES
Then taking as clipping threshold the minimizer of the RHS, T"
1/2 Σ
iies will
||
THE ((wi, 2()1E(m)) leads to:
F F(wus =1):=
Wi Zi
46
Wal 11
iES
iES
26

---

Unified Breakdown Analysis for Byzantine Robust Gossip
However, the clipping threshold here requires exact knowledge of the set S. Furthermore, it is unclear what extend making approximate estimate of this clipping threshold allows derive robustness guarantees.
Remark F.3. A key point here is that this oracle clipping threshold corresponds to the unique minimizer within each squared term of the sum. Hence, considering for instance the adaptive practical clipping rule of (He et al., 2023) leads to larger upper bound on the error.
F.2 Geometric trimming a.k.a. NNA
Let (w;, zi <i) E (R4 x Rd)", and S C [n] such that Eieswi S b.
We recall the definition of GTS: Assume w.l.o.g. that (||=:])<([n) are sorted, i.e. |2||| ... < || and denote
k" (b) = max(k [n]; Eiz4 wi 2 b} the index of the largest vector which has least a weight b of vector largest than him. (GTS) computes (k)( >i) Wi b, and outputs
(()((() = (0) + Σ wizi-
(k)
Lemma F.4. Geometric trimming (b. p) -robust with p =
Proof. Let (wi, zi)se(n) E (R.,, x Rdy", and S [n] such that Eies wi S b, Without loss of generality assume that (k)(b) 0
Thus the aggregation rules write
1
F( 2i)==
Σ
Wizg.
Σ
w3 z, 1, removed
(<)
Then, by applying the triangle inequality we have
F F(wir, zi)i=l,...))
Σ
wizi
Σ iES
Wi 1, removed +
Σ
wi 1
not removed
iES
icS
2
< Σ
||| removed +
Σ
Wi
|
1
removed
iSS
iES
As Em Wi removed b, holds that
Σ Wi Σ
wi l removed
Σ Wi removed
Σ
Wi I removed
x
Wi 1 not removed
Σ
wil 1 removed-
SES
Furthermore, if removed and j not, then | 2 || It follows that
Σ wil 1 removed
willzs| 1, not removed-
1ES
"Which can he ensured by adding artificially the entry (0)*()) (b)(
27

---

Unified Breakdown Analysis for Byzantine Robust Gossip
Consequently:
2
F P((Wis Zi zi)i=lm.m))
Σ Wizii
-
will
|
removed
EE
sES
2
Σ
/i 2/ V wi romoved
SES
- Σ
Wj
1 remaved
Ewillzil?
using Cauchy-Schward
iE8
iES
Thus:
2
F( zi):=1....)
Σ
S
4b Σ
wi | 2:11?
iES
EE
G. Proofs for D-SGD
Proof of Corollary 4.8. This proof hinges on the fact that the proof of Farhadkhani al. (2023, Theorem 1) does not actually require that communication is performed using NNA, but simply that the aggregation procedure respects (a,, ))-reduction, which they prove in their Lemma 2. Then, all subsequent results invoke this Lemma instead of the specific aggregation prove in Theorem 3.3. We can then use their bounds on the errors procedure. CS. also satisfies (a, A)rreduction, out of the box.
Then, as T grows, and ignoring constant factors, only the first and last terms in their Theorem 3 remain, leading to, for i E H:
T E [[[ T
Lov
f(x)) T
(1 + 111-++ +0)+
(12)
where c1 X but Farhadkhani et al. (2023, Theorem 1) allows to derive precise upper bounds for any T 2 1.
det, with C₁ a(1 + a1/(111a0) 1111--0 a)². Note that give O() versions of the Theorems for simplicity,
One-step derivation. The one-step result is obtained by taking the values of a = 1 - 111 6) and X = 76. On the one hand
c = (1 (1 - 62) - 7(1 8)) =0
(
1 1- 7 7( (11-8) 8)
70(1 8)2
72(1 8)2
On the other hand, x = 76 S 1 implies that C = Occ)). Both lead to
f(
f(x*)
1 1- -1 (P11-1
1- 71 (1- 6)
E | Fx (x))
Lo \
x
(13)
T
T
72 8)2
72 8)2
The result of Corollary 4.8 derives from the case 7 < (otherwise, the guarantees are essentially the same as in Farhadkhani et al. (2023)), and 5 2 1 (otherwise there essentially no Byzantine).
Multi-step derivation. In the previous case, we see that C' dominated by the e term since c >> A. In particular, the guarantees would increase if we were able to trade-off some a for some X, which is possible by using multiple communications steps. This is what we do, and take enough steps that C₁ = o()) (i.e., s 0), so that C' s X. Following Corollary 3.4, it can be achieved by performing '(y-1(1 - 5)-1) steps of F-RG, where logarithmic factors are hidden in the notation. We then plug the multi-step À value from Corollary 3.4 to obtain the result: as A = O ( (71ー3)) the multi-communication steps convergence bound writes
E [|V -o (Lo
Lov
f(
f(x²)
|
[H] -1
5
(14)
T
7(1 8)2
7(1 8)2
28

---

Unified Breakdown Analysis for Byzantine Robust Gossip
29


Reviews:
[{"review_id": "00tHmOKNaZ", "reviewer": "Reviewer_CF8P", "summary": "This paper studies Byzantine robust decentralized optimization with a focus on breakdown point. The authors propose a unified method  F-RG, and a new algorithm $CS_{ours}-RG$ adapted for sparse communication networks, both of which have near-optimal breakdown point. Under the proposed $(b, \\rho)$-robustness condition, and bounded weight on Byzantine nodes, $r$-robustness and convergence guarantees for decentralized gradient methods are provided for F-RG. Furthermore, the authors propose some new attacks that tested effective in MNIST and CIFAR10 classification tasks.\n\n# post rebuttal update\nI thank the authors for the rebuttal. The authors corrected their statement in corollary 4.7, and the updated claim on the spectral limit of $r$-robustness looks great to me. The added discussions on why the proposed sufficient condition is weaker and the final residual errors make the contributions more clear. Thus, I chose to raise my initial score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments, which we discuss below.\n# Theoretical Improvements\nWe respectfully but firmly disagree on the main weakness stated, i.e. our framework does not demonstrate theoretical improvement.\n\nThe major theoretical improvements of our framework rely on the tight analysis of the *breakdown point*, which are compared with previous papers in the paragraph *near optimal breakdown point* of Section 3.4.\n\nThe table below summarizes the main differences with previous works, with details afterwards.\n|Paper|Algorithm|Heterogeneous losses|Implementable|Generic Analysis|Breakdown assumption|\n|-|-|-|-|-|-|\n|[1]|ClippedGossip|Yes|**No**|No|$b/\\mu_{\\min}\\le \\gamma/8$|\n|[2]|NNA|Yes|Only on **fully-connected graphs**|None for $(\\alpha,\\lambda)$-reduction|$b/H\\le 10$|\n|[3]|IOS|Yes|Yes|Yes|$b/\\mu_{\\min}\\le O({1}/{\\sqrt{H}})$|\n|[4]|BRIDGE-T|**No**|Yes|No|NA|\n|Ours|CS$_{ours}$-RG (F-RG)|Yes|Yes|Yes|$b/\\mu_{\\min} \\le 1/4$|\n\nWe emphasize that:\n- [1] relies on a *non implementable clipping rule* that requires prior knowledge of the neighbors' identity (Byzantine or honest). Yet we have better guarantees: their breakdown point is suboptimal by a significant factor $\\gamma$ (the graph's spectral gap) shrinking with the lack of connectivity of the graph.\n- [3]'s breakdown point is highly suboptimal: the proportion of tolerated Byzantine nodes goes to 0 when the number of nodes increases.\n- [2] only considers fully connected networks, still we provide tighter breakdown guarantees: they show NNA tolerates up to 1/11 of Byzantines, while our method tolerates 1/5th. Moreover we show NNA tolerates up to 1/9th. Altough they show multiple steps of NNA satisfy $(\\alpha,\\lambda)$-reduction with 1/5 of Byzantine nodes, enforcing $\\lambda<1$ (required to be r-robust) in their guarantees leads to tolerate only $O(1/\\sqrt{H})$.\n# Corollary 4.7 Too Good to Be True\nWe clarify here the notation $Var_H(x^t)$, which converges in $O(1/T)$. \nRecall that $Var_{H}(x^t)=1/H\\sum_{i\\in H}|x_i^t-\\bar{x}_H^t|^2$.\n\nIt thus quantifies how far honest parameters are from each other, called 'variance among honest nodes'. This may converge to 0 quicker than $O(1/T)$: for an optimization step size $\\eta_{op}=0$, the algorithm boils down to (robust) gossip averaging, and the variance converges linearly to 0. Crucially, $Var_{H}(x)$ **does not** correspond to a stochastic variance due to SGD.\n\nPS: Cor. 4.7 statement had a typo: the expectation operator was missing, it might have driven the confusion. Exact result is $E[Var_{H}(x^T)]\\in O((1+\\zeta^2/\\sigma^2)/T)$, where the expectation is taken over SGD randomness.\n# Experiments\nWe provide additional experiments (  https://anonymous.4open.science/r/rebutal_files-342B/. ), which are described in Reviewer GrPa's answer.\n# Breakdown Point Limit is Not Fundamental\nWe highlight that Thm 3.5 only assumptions are:\n- Algorithm is decentralized, nodes communicate within a graph\n- Algorithm is $r$-robust on this graph\n- Byzantine nodes are unknown.\n\nThus we make very few assumptions on the nature of the algorithms involved. The r-robustness assumption is only used as a *definition* of a robust algorithm. Crucially, Thm 3.5 does not apply only to F-RG framework.\n\nHence we do not fully understand the remark on the lack of generality of our breakdown point limit. Would the reviewer know of a method not respecting this limit?\n\nTo clarify this section, we will highlight the assumptions of this breakdown point limit more precisely and change the section's title to *Fundamental Limits of r-Robust Algorithms*.\n# Linking $(\\alpha,\\lambda)$-reduction and $r$-robustness\nWe agree $(\\alpha,\\lambda)$-reduction and $r$-robustness are closely related quantities. While $(\\alpha,\\lambda)$-reduction measures with two different constants how the *bias* $|\\bar{x_i}^t-\\bar{x_H}^0|$ and the variance $H^{-1}\\sum_{i\\in H}\\|x_i^t-\\bar{x}_H^t\\|^2$ evolve during a step of communication, our definition of r-robustness criterion directly quantifies the  of the *mean square error*, i.e. the bias + the variance. Both are linked using:\n1. $(\\alpha,\\lambda)$-reduction implies r-robustness with $r=\\alpha+\\lambda$\n2. r-robustness implies $(\\alpha,\\lambda)$-reduction with $\\alpha=\\lambda=r$\n\nThe notion of r-robustness aims at defining what it means to be a \"robust decentralized communication algorithm\". Indeed, r-robustness with r<1 expresses that \"nodes benefit from communicating\" more directly than enforcing both $\\alpha<1$ and $\\lambda<1$. Moreover, the results provided are tighter with this notion of robustness.\n# Conclusion\nWe hope that we have adequately addressed all concerns and that these revisions will reflect positively in the reviewer’s final assessment. Otherwise, we would be delighted to engage in further discussion.\n[1] He et al. Arxiv 2023\n[2] Wu et al. IEEE 2023\n[3] Farhadkhani et al. ICML 2023\n[4] Fang et al. IEEE 2022", "claims_and_evidence": "The authors provided detailed analysis for the theoretical claims and clear experimental evaluations.", "methods_and_evaluation_criteria": "The proposed methods are well motivated, and are tested on realistic classification tasks.", "theoretical_claims": "I did not check the proofs of these theorems, but I have some concerns: \n1. The theoretical claim in Corollary 4.7 seems to be too good to be true, outperforming the best rate in non-adversarial centralized rate $O(1/\\sqrt{T})$.\n2. It lacks a detailed comparison with related works, like is this rate better than some previous rates, or this analysis works for a broader class of aggregators or graphs, or the assumptions are relaxed. A detailed comparison would help us to better understand the contributions of these theoretical results.", "experimental_designs_or_analyses": "More counterparts besides RG can be added for comparisons, such as the BRIDGE methods in this work: https://arxiv.org/abs/1908.08098", "relation_to_broader_scientific_literature": "N.A.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "Strengths: \n1. This paper presents a nice characterization of graph(weights) condition, and algorithm condition to ensure byzantine robustness (per my understanding and correct me if I were wrong, it seems that definition 2.1 and 2.2 constitute a sufficient condition for byzantine-robust averaging and gradient methods.  This is nice in the sense that the condition is imposed on the weight instead of the fraction of byzantine agents, which is more intrinsic per my understanding.\n2. The paper presents a breakdown analysis for this sufficient condition to hold. The writing is kind of misleading though, since not every byzantine robust decentralized method falls in to the pursuit of the proposed framework, and thus the breakdown point limit is not fundamental in general. \n3. Specific algorithms are designed that satisfies the sufficient condition and theoretical guarantees are presented. Attacks are developed, and the proposed algorithms are byzantine robust.\n\nWeakness:\n1. The proposed $r$-robustness is very similar to the reduction property used in Farhadkhani et al., 2023. It would be nice if the authors can differentiate from it. \n2. The proposed framework does not demonstrate improvement theoretically.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "N.A.", "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": "", "extra_scores": {}}, {"review_id": "mjXzT4jJW0", "reviewer": "Reviewer_UczM", "summary": "This paper presents a general framework for robust decentralized averaging over sparse communication graphs, providing tight convergence guarantees for various robust summation rules. The authors then investigate the so-called theoretical breakdown: the maximum number of Byzantine nodes an algorithm can tolerate, and demonstrate that some existing approaches like NNA fail earlier. Additionally, they introduce the Spectral Heterogeneity Attack, which leverages graph topology to compromise robustness in sparse networks", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, which we discuss below.\n\n# Experiments\n\nAs requested by Reviewers CF8P, UczM, and EynP, we performed additional experiments, which are available here https://anonymous.4open.science/r/rebutal_files-342B/.\n\nWe provide 2 additional experiments on Erdös Renyi graphs: one on an averaging task, and one on a CNN trained on MNIST. We additionally compare ourselves with IOS algorithm [3], thus we provide the previous experiments on MNIST as well.\n\n## Setting\n**Erdős-Rényi** The subgraph of honest nodes is sampled as a random Erdos Renyi graph with 20 honest nodes, each of them being always adjacent to 4 Byzantine nodes. For each seed, 12 different values of $p \\in [0.25,1]$ are tested, where p denotes the probability for each edge to exist. We plot the links between the algebraic connectivity of the graph ($\\mu_2$, the second smallest eigenvalue of the unitary weighted Laplacian) and the loss. The tasks tested on this graph are:\n   a. **Averaging task**: Nodes' parameters are initialized using a $N(0,I_5)$ distribution. Nodes perform (robust) gossip communication iterations. We conduct experiments on 6 different seeds, and curves are smoothed using a moving average of size 4. \n   b. **MNIST**: The model taken is the same CNN as in the previous experiments on MNIST in the paper. The heterogeneity among nodes has been increased to emphasize the importance of communication, from $\\alpha=5$ to $\\alpha=1$ (cf. Dirichlet sampling in [3]). Experiments are conducted on one seed.\n\nFor clarity, we changed the legend of CS$_{He}$-RG to *ClippedGossip*, even though they both correspond to the same implementable version of ClippedGossip from [1], unsupported by theory.\n\n## Analysis of the Experiments\n\n### Averaging Task on Erdős-Rényi\n\nWe provide, for each algorithm, the largest value of $\\mu_2$ for which it is non-robust and the attack that makes the algorithm break:\n1. CS$_{ours}$-RG breaks at $\\mu_2 \\approx 5.5$ with ALIE and FOE attacks.\n2. ClippedGossip breaks at $\\mu_2 \\approx 10$ with ALIE attack.\n3. IOS breaks at $\\mu_2 \\approx 16$ with FOE attack.\n4. GTS-RG breaks at $\\mu_2 \\approx 10$ with SpH attack.\n\nIn this setting, $CS_{ours}$-RG is the algorithm with the best breakdown point among the compared methods. Interestingly, $CS_{ours}$-RG is robust for a connectivity $2$ times smaller than GTS-RG, as our theory predict it. \n\n### MNIST Experiments on Erdős-Rényi\n\nWe notice that:\n1. CS$_{ours}$-RG keeps good performances in this setting while other methods break, showing a better performance than the (worst-case) one predicted in our theory.\n2. SpH makes IOS break with larger connectivity than other rules. SpH is just as efficient as Dissensus on ClippedGossip, while Dissensus makes GTS-RG break with a larger connectivity.\n### IOS on MNIST: Previous Experiment\n\nIOS performances are similar to that of GTS-RG: its breakdown point is slightly better than GTS-RG but still worse than CS$_{ours}$-RG. We notice that SpH is very effective against IOS as well in this setting, in the sense that it makes IOS break earlier than other attacks.\n\n# More Involved Datasets\n\nWe conducted our experiments on MNIST and CIFAR-10 datasets as those are standard benchmarks in the decentralized robustness literature (see e.g., [He et al., 2023] and [Farhadkani et al., 2022]). Furthermore, the initial experiments on MNIST require approximately 4 days to be performed: indeed, we train simultaneously 26 models for 10 different values of $b$, on 4 different attacks and 3 different algorithms, each experiment being initialized with 5 different seeds. This multiplication of configurations and models to train significantly increases the computational burden of experiments.\n\nAs our contributions focus on the averaging sub-problem (the rest is just a direct consequence of the better averaging properties), we provided learning experiments mostly to illustrate our theory, and show how better aggregations lead to better decentralized-SGD algorithms. Our goal was to provide clear theoretical foundations for decentralized optimization, not a large-scale benchmark of current solutions. \n\n# Generalization to Other Decentralized Protocols\n\nOur analysis focuses on the gossip protocol, but it may be of interest to other protocols. Any protocol that, at some point, performs node-level averages of other parameters in the network could apply some $(b,\\rho)$-robust summand instead of plain averaging and use our analysis to provide guarantees on the robustness of their algorithm. Note that averaging is particularly relevant, due to the average structure of the ERM problem. \n\n\n[1] Byzantine-robust decentralized learning via clippedgossip, He et al 2023\n[2] Byzantine-resilient decentralized stochastic optimization with robust aggregation\nrules, Wu et al 2023\n[3] Robust collaborative learning with linear gradient overhead, Farhadkhani et al 2023\n[4]  Bridge: Byzantine- resilient decentralized gradient descent. Fang et al 2022", "claims_and_evidence": "A bit lack of experimental evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I do not check all proofs. But the parts I have checked are right.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Pros:\n\n- Extending robust aggregation from fully connected graphs to sparse graphs is an interesting contribution.\n\n- The unified framework for analyzing theoretical breakdown points is important, especially since it can incorporate some existing well-known approaches as special cases for analysis.\n\n- Rigorous theoretical analysis is provided.\n\nCons:\n\n- The experiments are relatively simple, focusing only on MNIST and CIFAR-10.\n\n- The paper is somewhat difficult to follow.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Would the proposed approach generalize to other decentralized protocols beyond gossip-based ones?", "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": "", "extra_scores": {}}, {"review_id": "eMw1QAuAjU", "reviewer": "Reviewer_GrPa", "summary": "Decentralized training often encounter adversaries that may cause degraded model without proper defenses. This paper considers the problem of robust decentralized training against Byzantine adversaries. This paper revisits the previous robust gossip schemes and propose a generic framework which recovers these baselines as special cases. As a result, they propose the F-RG algorithm that outperforms previous works and reach near optimal breakdown point. Besides, they also propose a novel attack that based on spectral heterogeneity that pushes honest workers away from each other. The theoretical convergence rates are given under standard assumptions and impossibility results are also given. The empirical results show the effectiveness of their proposed algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, which we discuss below.\n\nThe reviewer is perfectly right to point out that the choice of edge weights influences the spectral properties of the graph, which impact the robustness criterion. It is thus an interesting research direction to develop a method that maximizes the spectral gap of the *honest subgraph* through a robust protocol, agnostic to the position of the Byzantine nodes.\n\nMeanwhile, it is still possible to build on existing methods, such as the Metropolis choice of weights:\n1. Given an upper bound on the number of Byzantine nodes $f$, one can have a *local upper bound* on the weight of Byzantine neighbors using $b_i = f \\max_{j \\in n(i)} w_{ij}$. This can be combined with Metropolis weights to have a robust initialization of the matrix weights. Indeed, as pointed out by [He et al., 2023], defining $w_{ij}$ as $\\frac{1}{max(d_i, d_j) + 1}$ is robust: if $i$ is honest and $j$ Byzantine, then $j$ cannot force $i$ to assign a weight greater than $1/(d_i+1)$ to the edge $(i,j)$. In this setting, a local bound of the Byzantine weight can be taken as $b_i=f/(d_i+1)$.\n2. Having a local upper bound on the number of Byzantine weights $b_i \\ge \\sum_{j \\in n_B(i)} w_{ij}$ is sufficient to implement the robust aggregation rules. For instance, each node $i \\in H$ chooses the local clipping threshold based on this local $b_i$. Using such a local upper bound of the weights of Byzantines leads to the same guarantees, with $b = \\max_{i \\in H} b_i.$\n\nDoes our response answer your question?\n\n[He et al., 2023] Byzantine-robust decentralized learning via clippedgossip, He et al. 2023", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The baselines are common in the literature and therefore make sense.", "theoretical_claims": "The theoretical claim are made under standard assumptions in the literature.", "experimental_designs_or_analyses": "Yes. The experiment settings looks good to me.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "### Strength\n\n- This paper approach the problem by considering a generic framework that includes previous works and propose better robust gossip algorithms. The rates and algorithms therefore makes sense.\n- Originality: the analysis framework, algorithm, and attack are all novel.\n- Clarity: Mostly clear and self-contained.\n- significance: the theoretical results of this paper is significant enough for a conference paper.", "other_comments_or_suggestions": "No.", "questions_for_authors": "This paper consider graphs from $\\Gamma_{\\mu,b}$. But in practice, there is an extra degree of freedom to choose the edge weights, e.g., using Metropolis weight. In this sense, both the spectral gap and the weights of Byzantine neighbors depend on such choice. It means we may not know a tight upper bound $b$ and if chosen graph belongs to $\\Gamma_{\\mu,b}$. Besides, the clipping strategy $CS_{ours}$ also depends on this information.  Could you leave some comments on how to handle this case?", "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": "", "extra_scores": {}}, {"review_id": "l6TXDixStL", "reviewer": "Reviewer_EynP", "summary": "This paper addresses the problem of designing robust decentralized algorithms in the face of so-called Byzantine adversaries, i.e. adversaries likely to send arbitrary (and potentially equivocal) information to other participants during protocol execution. It introduces a general framework, F-RG, for robust decentralized communication algorithms to compute weighted sum queries over sparse communication graphs. It provides a theoretical analysis of the breakdown point of this framework, presenting tight upper bounds on the number (maximal weight) of adversaries a system can tolerate with respect to the spectral properties of the communication graph. The algorithms matching this bound are, however, impractical. Accordingly, the paper presents an aggregation rule, $CS_{ours}$, that achieves near-optimal performance at the breakdown point. Combined with the existing mixing conditions of robust decentralized optimization, F-RG provides a fully robust pipeline to robustly implement decentralized SGD (with associated convergence analysis under standard assumptions). The paper also introduces a new adversarial strategy that exploits the spectral properties of the communication graph to disrupt decentralized learning. Empirical experiments are conducted to validate the theoretical results, comparing $CS_{ours}$ with other state-of-the-art aggregation schemes in various attack scenarios for summation and decentralized learning problems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and their precious suggestions. We examine the questions raised below.\n\n# Additional Experiments\n\nFollowing the reviewer's suggestion, we performed new experiments on Erdős-Rényi graphs and additionally compared ourselves with the IOS algorithm [Wu et al., 2022]. We refer the reviewer to the response to Reviewer UczM for further details.\n\n# Comment on Remark 3.2\n\nWe fully agree with the reviewer that there is no major technical difficulty in either:\ni) defining $(f,\\kappa)$-robustness with arbitrary weights, or\nii) going from $(f,\\kappa)$-robustness to $(b,\\rho)$-robustness with arbitrary weights.\n\nIn this remark, we mostly wanted to recall that $(f,\\kappa)$-robustness is originally defined with constant weights, so that the reader can easily compare both definitions. Still, we do not believe that generalizing it to arbitrary weights is a major contribution.\n\nFor now, if proofs on $(f,\\kappa)$-robust aggregators have been written with constant weights, arbitrary weights can be achieved, for instance by increasing artificially the number of input vectors so that the frequency of each input approaches the targeted weight.\n\n# Suggestions\n\nWe thank the reviewer for the meaningful and precious advice on the flow of the paper, which we will implement.\n\n1. **Introduction of Aggregation Rules**\nWe agree with the reviewer that this part takes space while not being clear enough. We will think about how to improve it. One solution we are investigating is to consider in the main part of the article definitions with unitary weights only and defer the generic definitions to the appendix. We agree that currently, the definition of $(b,\\rho)$-robustness is a bit too far away from the example of robust summands.\n\n2. **Asynchronous Part**\nWe fully agree that it is a bit rushed; we will move it to the appendix to clarify it.\n\n3. **Title of Section 3.4**\nThe reviewer is right to point out that our limits only apply when we consider $r$-robustness as the robustness definition of any decentralized algorithm. Thus, we will follow their suggestion.\n\n4. **Defining $(\\alpha,\\lambda)$-Reduction**\nWe agree as well that defining it properly will make the paper easier to read. Furthermore, it will allow us to better compare it with $r$-robustness.\n\n5. **Typos**\nWe agree that currently, the 'oracle' clipping thresholds are ill-defined; we will improve this point. Thank you as well for pointing out the missing sentence.", "claims_and_evidence": "The paper claims that F-RG provides a unified framework for Byzantine-robust decentralized summation and that $CS_{ours}$ achieves a near-optimal breakdown point. These claims are supported by:\n\n- The introduction of the $(b, \\rho)$-robustness criterion, which generalizes robustness guarantees for weighted summation queries to arbitrary sparse networks.\n- Theoretical upper and lower bounds demonstrating that, in the presented framework, the breakdown point is tightly characterized by the condition $\\mu_{\\text{min}} < 2 b $.\n- Theoretical results demonstrating that $CS_{ours}$ is robust as soon as $\\mu_{\\text{min}} \\geq 4b $, hence demonstrating the near-optimality of $CS_{ours}$ in regard to the breakdown point.\n- Extension of the robust summation guarantees to robust Decentralized SGD using the notion of $(\\alpha, \\lambda)$-reduction from (Farhadkhani 2022). \n- Empirical results showing that $CS_{ours}$ outperforms existing methods such as NNA and ClippedGossip under the new Spectral Heterogeneity attack.", "methods_and_evaluation_criteria": "The method and evaluation criteria are well suited to the claims of the paper and to the problem being tackled. The technical contribution is clear and well-explained, and the experimental setup is clearly described.", "theoretical_claims": "The analysis is rigorous, proofs are well-written appear correct upon review. However, in my opinion , some aspects of the theoretical presentation could be improved:\n\n- The introduction of new aggregation rules (starting on page 6) is somewhat rushed, with heavy notation and a list-based presentation that could benefit from more detailed explanations.\n- The discussion of asynchronous communication is brief and lacks clarity for me on its practical implications. It may be useful to remove it from the main body of the paper and have a dedicated section in the appendix. \n- Section 4.2 presents strong results on robust Distributed-SGD but does not clearly highlight the significance of using the reduction property from (Farhadkhani 2023) to ensure robust convergence guarantees. Reintroducing the definition of reduction could help make this clearer.", "experimental_designs_or_analyses": "Experiments, while rather limited in terms of scale are well-presented, effectively demonstrate the robustness of the proposed aggregation rule under Byzantine attacks in sparse networks. However, the study considers only one sparse graph. I think it would be valuable to test different levels of graph connectivity to see if all methods collapse to the same performance in fully connected settings or if certain approaches are more robust across different topologies.", "relation_to_broader_scientific_literature": "This article makes a significant contribution to robust decentralized learning. Theoretical results generalize known limitations, while experimental analysis introduces new adversarial strategies. The article presents all the background work necessary for the reader to understand the whole picture.", "essential_references_not_discussed": "The paper covers the relevant literature.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "- I believe that Section 3.4 should be titled \"Fundamental limits of $r$-robustness\" to better reflect the fact that the lower bound applies only to $r$-robust communication schemes, as noted in Remark 3.6.\n\nA minor technical clarification:\n- In Remark 3.2, the claim that $(f, \\kappa)$-robustness can only provide $(b, \\rho)$-robust summation with constant weights seem too restrictive to me. As I understand it, it seems possible to apply an $(f, \\kappa)$-robust function $F$ to a transformed set of vectors $ ( (n-f) w_i z_i )_{i \\in [n]}$, which would yield $(b, \\rho)$-robust summation with $\\rho = \\kappa$, $b = n-f$, for general weights $(w_i)_{i \\in [n]}$ (as long as they are upper-bounded by 1). Maybe I missed something though, could the authors comment on this point ? \n\n- Maybe the author could reduce a bit the space dedicated to listing the aggregations and instead present a bit more deeply the convergence framework (maybe re-presenting the definition of reduction being used). \n\nSmall typos: \n- I think the oracle clippings presented in page 6 should be defined by taking the set $S$ as an entry, otherwise the aggregation seem a bit ill-defined. \n- There is a sentence missing at the end of paragraph 1. In appendix A.", "questions_for_authors": "Can you please answer to my wondering on Remark 3.2 and to my suggestion for additional experiments with several levels of connectivity?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers agree that the work makes important theoretical contribution to decentralized robust optimization. Reviewers also find the unified framework useful, and strongly suggest authors to incorporate key points in rebuttal into the revision.
Decision: Accept (poster)