Byzantine-Robust Gossip: Insights from a Dual Approach
Authors: Renaud Gaucher
Hadrien Hendrikx
Aymeric Dieuleveut
Venue: Accepted by TMLR ()

Abstract: Distributed learning has many computational benefits but is vulnerable to attacks from a subset of devices transmitting incorrect information. This paper investigates Byzantine-resilient algorithms in a decentralized setting, where devices communicate directly in a peer-to-peer manner within a communication network. We leverage the so-called dual approach for decentralized optimization and propose a Byzantine-robust algorithm. We provide convergence guarantees in the average consensus subcase, discuss the potential of the dual approach beyond this subcase, and re-interpret existing algorithms using the dual framework. Lastly, we experimentally show the soundness of our method.

Published in Transactions on Machine Learning Research (02/2025)
Byzantine-Robust Gossip: Insights from Dual Approach
Renaud Gaucher
Center for Applied Mathematics
École polytechnique
TP Paris
Palaiseou
Aymeric Dieuleveut
Center for Applied Mathemafics
Ecole polytechnnqqee
IP Paris
Palaiseoa
Hadrien Hendrikx
ludriien.hendrkkz@ianiii.
huiia Center of Grenoble Alpes Universily
CNRS, LJK
Grenoble, France
Reviewed on OpenReview: https: openreview. net/ forum?? urruLUpUpk
Abstract
Distributed learning has many computational benefits but is vulnerable to attacks from subset of devices transmitting incorrect information. This paper investigates Byzantine- resilient algorithms in decentralized setting, where devices communicate directly in a peer-to-peer manner within a communication network. We leverage the so-called dual approach for decentralized optimization and propose Byzantine-robust algorithm. We provide convergence guaranlees in the average consensus subcase, discuss the potential of the dual approach beyond this subcase, and re-interpret existing algorithms using the dual framcwork. Lastly, we experimentally show the soundness of our method.
1 Introduction
Distributed optimization algorithms allow to harnessing the multiplication of devices to tackle the increasing computational complexity of machine learning models. Yet, the involvement of many parties in the learning process opens up the threat of misbehaving devices, that purposely inadvertently send arbitrarily harmful messages. Such device failures commonly termed Byzantine (Lamport et al., 1982). This paper studies Byzantine robustness in the decentralized communication paradign, which alleviates the risk of a single point of failure due to a central server by making devices directly communicate with each other in a pecr-to-pecr manner.
We consider devices (a.k.a nodes) that communicate synchronously within a communication network, ab- stracted as graph G (V,E), where each vertex is a node that communicates with its neighbors in the graph through the odges. We denote V, the Byzantine nodes, and V/, V(V, the remaining nodes, called honest. Similarly, we split the edges in & E,, U U&,, where &, are the edges linking honest nodes, while edges in & link honest. to Byzantine nodes. The subgraph of honest nodes Gr == (Vn, Ex) is always assumed to connected. For any i E Vn, we denote fi RRd + R the local objective function on node i, and we study the optimization problem:
minzer Eiev, f((x))
(1)
We study decentralized algorithms to solve this problem, which rely on the gossip commmication protocol (Boyd al., 2006; Nedic & Ozdaglar, 2009; Duchi et al., 2011; Scaman al., 2017), in which cach node E V maintains local parameter I; E Rd, and updates this parameter by performing approximate average of this parameter with those of its neighbors in the graph.

---

Published in Transactions on Machine Learning Research (02/2025)
Such gossip algorithms naturally arise when solving well-chosen dual formulation of Equation (1) with standard first-order methods. This dual approach gives principled framework to design and analyze efficient decentralized algorithms, leading for instance to acceleration (Scaman et al., 2017; Kovalev et al., 2020), variance reduction (Hendrikx ct al., 2019) and has strong links with gradient tracking (Jakovetić, 2018). This paper investigales the benefits of this approach in the Byzantine robust setting.
Related works. Since its introduction by Blanchard et al. (2017); the setting of Byzantine-robust learning has been extensively studied. The large majority of works focus on the federated case, in which central server organizes the training and communicates directly with each node (Yin et al., 2018; Chen et al., 2017; Alistarh et al., 2018; Li et al., 2019; El-Mhamdi et al., 2020; Karimireddy et al., 2023; 2021; Farhadkhani et al., 2022; Allouah et al., 2023). Some work investigated the robust decentralized optimization setting, either with fully connected networks (El-Mhamdi et al., 2021; Farhadkhani et al., 2023) or with more generic networks (He et al., 2023; Wu al., 2023; Gaucher et al., 2025). However, those works only skimmed over the challenges of decentralizod optimization in the Byzantine setting, and many key optimization techniques such gradient tracking or acceleration are still unexplored in the presence of adversaries. Developing the dual framework in the presence of adversaries would thus open the way to tackle these challenges.
Contributions. In this paper, we (i) leverage the dual approach to derive EdgeClippedGossip. decentralized robust algorithm based on clipped dual gradient descent, (ii) derive clipping rules and their associated convergence guarantees in the average consensus subproblem, in which EdgeClippedGossipp recovers existing algorithms. Finally, (iii) we highlight the dynamics of the developed method compared to previous approaches and discuss its generalization beyond the average consensus case.
1)", || |l2 or simply || (resp. (::)) the Euclidean norm (resp. inner product) on R4; || || the Frobenius norm of any matrix in Rdxn and (M, N)r Tr(M²N) the corresponding inner product. We denote X1. the i-th row of a matrix X. For a matrix M in RRd we denote M := n-' 1, M, and for E {1,2, (0),,00,, we denote ||Mlp.., the p-norm of the vector of 2-norms of the rows of M, i.e., (..l22)))
Notations. We denote 1,
Moreover, C2 is the Moore Penrose inverse of and Id is the identity matrix. We identify Re to RiEll and R to Ra. We denote a A = min(a, b).
2 Deriving EdgeClippedoosip
This section describes dual approach to Byzantine robustness. We first introduce dual gossip algorithm, then show how it can be made robust using EdgeCliippedCossip.
Setting: We denote ny = -Va and ny = |V/] the total number of honest and Byzantine nodes, and (1) and (1)1) the number of honest and Byzantine neighbors of node i. Each agent owns and iteratively updates a local parameter z/. At time f, we denote x= :4, E Rxd the parameter matrix, which we split
into honest and Byzantine as X (X) (x,) where X = [<*))e,,,'" (resp. X!) is the sub-matrix containing
the models held by the honest workers (resp. Byzantine). Note that Byzantine nodes can declare different values to each of their neighbors. As such, only the number and positions of edges with Byzantine nodes matter, and we can w.l.o.g identify the number of edges linking Byzantine and honest nodes |Ep] to the number of Byzantine workers Té.
2.1 Gossip - average consensus case
Gossip communications (Boyd et al., 2006) consist in sharing information between neighbors through local averaging steps. The standard gossip protocol writes X = WX'', where W E [0, 1|mXx is a gossip matriz. Definition (Gossip matrix). A matrix W E R a gossip matris for a graph g = (V,8) if: (i) W is symmetric and doubly-stochastic: W1, = 1n, and 1"W = 1 (ii) W is supported on the edges of the network: Wy # 0 if and only if j or (i ~ j)
Such a matrix W has cigenvalues 1 14 (W) > (W> > ... > In,, (W)). The propagation of information in the graph is characterized by the spectral gap of W, which is defined as Yw == 1 1- -lp) Note that, if the graph G is connected, then 7 > 0.
2

---

Published in Transactions on Machine Learning Research (02/2025)
Example (Gossip from Graph Laplacian). Consider the Laplacian matrix of the graph L = D A where D is the diagonal matrix of degrees and A is the adjacency matrix (i.e., Aij = ((0)))E)) Then, W.. = Id -1y L is gossip matrix for 7 < 1/M,,W); with spectral gap YW, = =m (L), where Muin (L) is the second smallest eigenvalue of L.
The average consenius problem is an important special case of Equation (1).
Definition 2. The approximate average consensus problem (ACP) consists in computing x === 1. Eien, 2 where each node i E V4 holds a value 27, which is equivalent to Problem (1) with [1x) = 1 x 11. In the presence of Byzantines, only approximate estimation of xF can be found.
When there are Byzantine nodes, standard gossip-averaging results ensure linear convergence of the parameters to the average (Boyd et al., 2006): Σiev | - 2- < (1 Eevvlaaf - Yet, this result is not robust to adversarial nodes: the standard gossip communication uses averaging steps, it is vudnerable to single Byzantine node, which can drive all honest nodes to any position (Blanchard et al., 2017).
2.2 Dual approach in decentralized optimization
The use of a dual formulation to solve decentralized optimization is very popular (Jakovetić et al., 2020; Uribe et al., 2020). Not only has it been at the heart of key advances such as acceleration (Scaman al., 2017; Hendrikx et al., 2019; Kovalev et al., 2020) and variance reduction (Hendrikx et al., 2021), but it also allows us to understand methods such as gradient tracking (Jakovetić, 2018). It is thus natural to investigate whether the dual approach can be used for Byzantine robustness.
We first introduce the dual approach in a Byzantine- free setting. Then, we interpret dual variables and explain their use in the Byzantino-robust sctting. Eventually, we instantiate the algorithm the ACP setting and show that it recovers existing algorithms.
2.2.1 Byzantine-free free dual approach.
We first show how the dual approach unrolls on Problem (1), in setting without Byzantine agents. Let us write Problem (1) as constrained optimization problem on F(X) = Evev fa(X,), where the constraints write X1, constraint into a matrix C RÉXY, such that [CT (((n))); = =x; - Xx, for any edge (i ~ j) in E, we obtain a primal version Problem (1), which is, under convexity of functions Si, equivalent to a dual problem:
Xn, or equivalently v(i j) E E X₁ = =x for a connected graph. By encoding this
min XeR CO X=0
F(X)= = min max (F(X)- - (A, (A,C*X)}
(Primal)
Xxd AERexa
min (CAC)). AgRexd
(Dual)
where FY)): == supxexvxa (X,Y) is the Fenchel conjugate of F. Note that as F is separable, F* can be decomposed as F*(Y) Evey The dual approach leverages Equation (Dual) to design decentralized optimization algorithms, for instance by solving the dual problem using gradient descent (GD). If we denote Y = CA E Vxd the dual variable deriving from the Lagrangian multipliers A E Rexd GD with step-size 7) writes:
A+ = A' 1F = y = = = -F
(2)
Dual gossip update. The incidence matrix C is root of the Laplacian matrix L, as CCT L. It follows that in the case of the average consensus problem where (v) = + xt. Equation (2) consists in doing an update on the dual variable Y, which for the associated primal variable X = (Y) Y + X recovers the standard gossip protocol X = - X
Convergence. Using standard GD results, A in Equation (2) converges lincarly to A", the solution of (Dual), under strong convexity and smoothness assumptions on the f.. It follows that X == (F*(CA) converges to the solution of (Primal). Indeed:
3

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm Byzantine- Byzantine-Resllenn Resilient Decentralized Optimization with EdgeClippedGossip (r')
Input: { [v]), 77 {T*)
for / = 0 to T do
for jo 1.....,.. in parallel do
Compute o (V,( j E Vn else Share parameter z with neighbors
f) [+1 = 0/3 Eing Clip a2) x ((11))
Invariant. As y a CN, ker CT = span 1, and VF(X)) = Yt, the sum of (primal) gradients null by design:
Eien,
1²
(Invariant)
Asynptotic consensus. Reaching stationary point of Equation (2) means that VY* E ker CT, thus X, Xy; for all (i 5) E &, i.c. consensus is reached among nodes.
Note that although dual gradients are arguably hard to compute in the general case, several approaches allow to leverage the (primal-)dus approach while either bypassing the problem or alleviating this cost (Hendrikx et al., 2020; Kovalev et al., 2020).
2.2.2 Duality in the Byzantine setting.
In (Dual), the Lagrangian multipliers A' E gxd correspond to the influence between nodes the graph. Precisely, each row of A, indexed by edges as A(sa), corresponds to the accumulated influence between nodes and j through edge (i~j) j). Indeed, the (primal) gradient is equal to the aggregation of neighboring Lagrangian multipliers, fi(xt) $ of = E(en)) Mingy: while the update of cach Ming)) multiplier involves only the two nodes of the edge: A/t1 = A M/m,)) (V) (v(). This latter update thus corresponds to the update of the inffuence between node i and node during time step.
It follows that applying an operator on the update on the row (i ( f) of A corresponds to altering the influence between nodes i and j. For instance, setting the row A(t=)) to 0 corresponds to removing edge
(i ~~م j) from the graph.
To address the vulnerability of plain gossip averaging to Byzantine parties, we regulate the influence update between nodes by clipping the update on the edges. Formally, for and Rd, the projection of x onto the L2 ball of radius writes:
Clip(æ;T) = x
r).
(3)
|
We thus consider for a general vector T E R the regulation of the influence update on (i ~ j), by setting A 1+1 (bwz) A/pw5) - 1 fl (vf), 7 (ewn))) which writes under matrix form as
1+1 A² -1 (C"FF((CN)++)
This gives Algorithm 1, called EdgeClippedGoosip. which translates the update described above in terms of primal and dual iterates.
Oracle strategy. the set Byzantine edges E, is known, then Equation (4) with T(mws) = 00 ((ww)) exactly recovers the generalized gossip algorithm on the subgraph of honest nodes.
The previous derivations summarized into the following result.
Proposition 1. Consider a threshold т > 0 and = r1g. Then, Algorithm corresponds to clipped gradient descent on the dual problem (Dual): A+11 A² -II,, ball of radius for the infinile-2 norm [M] sup( || |I ((aa)))
where II, the projection
4

---

Published in Transactions on Machine Learning Research (02/2025)
Next, we instantiate the algorithm in the ACP case, in which the V have special form, and which is the sptup under which theoretical guarantees are given in Sections 3 and 4.
2.2.3
EdgeClippedGossip for the ACP.
From now on, we focus on Algorithm 1 for the Average Consensus Problem (Definition 2).
We denote X [ 2,,", the matrix of node-wise optimal parameters. In the ACP setting, X (CF( ACP CA + X", thus Equation (4) writes
A+ = A - Clip (C"VF(CN));) + x x - - x')-
(5)
In order to distinguish the impact of honest and Byzantine nodes, we decompose Matrix C into blocks Xn
Ch C
C
and X as
The update on (A') in Proposition thus writes as Xx
Ide.
x
X (Cn, Cb) Clip(C X'ir'); x =
(6)
We analyze this sub-prot tob-problem in the following section.
3
Global Clipping
We now investigate average consensus EdgeClippedGossip under a global clipping threshold, and highlight a choice of thresholds (r*) ))zo for which derive convergence guarantoes. All proofs for this section can be found in Appendix B.2.
3.1 The Global Clipping Rule
To analyze Equation (6), we decompose the influence update between honest and Byzantine edges (CT X C X Re and x'); C. X7, X3 R&xdd For given threshold 7 define s² the number of honest edges that are modified by Clip( (ipp(,r')) r²), ie.,
n² = ((i ~ 1) En, [I(Ck XDien) > +'}.
We then denote |[C X 1ll and the 1, 2-norm of the sub-matrix of clipped messages, i.e.:
I0 2,
Σ
[KCT (x)(s))))
(i-t)EEE. of largest
These quantities thus represent the fractions of weights of messages in (C* = ((1; x))(s))EE))) that are affected by clipping. We now introduce
A =
sup C,
Uxd 201
which quantifies how much the Byzantine nodes can increase the variance of the honest nodes. We will need Aso < 1 to obtain non-vacuous rosults, as otherwisc, it mcans that Byzantine nodes introduce more variance than what reduced by the contraction oblained through gossip averaging. Age decreases when removing Byzantine edges from the graph, and can be bounded for some graphs.
Lemma 1. For Gn fully connected where each honest node has exactly No(1) = -N. Byzantine neighbors, 2N /d N,
To satisfy A 1, two regimes appear: is sufficient that n, 2N, for small dimension d, but n, > 4N3 for large d, which quickly untractable. Therefore, the limit fraction Byzantine neighbors is significantly impacted by the dimension. We define the following clipping threshold rule.

---

Published in Transactions on Machine Learning Research (02/2025)
Definition 3 (Global Clipping Rule (GCR)). Given step size n, sequence of clipping thresholds (r")s20.
satisfies the Global Clipping Rule if for all > 0, either rf = 0, or
18 2
IIc% X A IC Xi 11,2 + +
Σ T
nn 05
This clipping rule enforces that the clipping threshold is below certain value, since docreasing r² increases xt, which in lurn increases the left term. In particular, 7¹ is reduced until the sum of the norms of clipped honest edges is greater than the sum of the norms of all honest edges, shrunk by the contraction Axs plus term proportional to the sum of previous thresholds (which is known by all nodes). This latter term, n E6 E.sr" T /nn, can be understood as a bound on the maximum bias induced by Byzantine nodes after steps, i.c. (x(X
Over-clipping. The GCR defines an upper bound on T', but any value below this threshold works. By denoting *²* the smallest w² such that the GCR holds, we must ensure that at least x** honest edges are clipped. A solution to this end consists in clipping x²* + [&g] edges overall, by removing first the [&o] largest odges, and computing 6²* on the remaining edges afterwards. Note that the GCR still holds if the number of Byzantine edges is over-estimated. We provide in Appendix B.3 simplified (yet looser) version of the GCR.
Global coordination. Implementing global clipping threshold that satisfies Definition 3 requires some global coordination, which is hard in general in this decentralized setting. As such, we propose a proof of concept on what can be achieved by this approach under a favorable assumption of their communications, more than & practical decentralized algorithm.
3.2 Convergence result
Recall that Umax(Lx) (L)) the maximal eigenvalue of the honest subgraph Laplacian, and Ao depends only on the topology of the full graph G. We note X7, 1, 1,, /
Theorem 1. Assuming Ax < 1, let v be a conslant step size: n & 1/(141//((11))) Mane
(a (La). If the clipping
thresholds (7')s20 satisfy Definition 3 (GCR), then:
|x - X & XX - XT - T
|| - x511 10: injeEn
Theorem 1 ensures that the squared distance of honest models X to the global optimum X decreases at each step, although not necessarily all the way to O. In essence, what happens is the following: cach step of EdgeellippedGossip pulls nodes closer logether but at the cost of allowing Byzantine nodes to introduce some bias so that X -X # O. This trade-off appears in the GCR: at some point, further reducing the variance not beneficial because it introduces too much bias, and so the GCR enforces that r R O, which essentially stops the algorithm. Yet, regardless of the initial heterogeneily, nodes benefit from running FdgeeClipeedGosspp.
Asymptotic error. This theorem ensures that finding small 7² that satisfy the GCR reduces the distance to the optimum, yet it does not characterize the asymptotic error. Furthermore, the smallest rf satisfying the GCR is an oracle quantity, in the sense that it requires computing sum of node-wise differences on honest neighbors only.
4 Beyond global coordination and averaging
In this section, we investigate how to extend the dual approach beyond the average consensus case, We discuss de discropancics between the developed dual framework and local clipping mothods such as (He et al., 2023; Gaucher et al., 2025). Then we discuss on the difficulties to extend the dual framework beyond the average consensus setting.

---

Published in Transactions on Machine Learning Research (02/2025)
4.1 Dual interpretation of existing algorithms
Several works investigated the problem of robust average consensus. Among those, He et al. (2023); Farhadkhani et al. (2023); Gaucher et al. (2025) propose robust communication algorithms that rely, under the hood, on performing gossip communication while altering the update on the Lagrangian multipliers at each step. All those algorithms can be written as:
2 = at - -nF =3))smm) o++1==
if Vn if e V--
(F-RG)
where F is an aggregation function that verifies a (b, p)-robust summand properties. The SOTA (b, p)-rouust summand, Clipped Sum, relies on clipping strategy: CS(21...., .x) := Σi=1 Clip(za;7). Interestingly, the success of those methods relies partially on the control of the quantitics (I; - Ty)ing In other words, they consist. altering the Lagrangian multipliers update (IC" (*))>) based on the norm of each entry.
Proposition 2. When T is a fixed constand, (6) is equivalent to Equation (F-RG) with Clipped Sum aggregation.
Local Clipping thresholds. An other key element of the robustness of CS,, is that the clipping threshold is tailored locally, in a node-wise manner. Typically, the clipping threshold т; on node is defined as the largest value within (I|æ; - 2y [))=~.. It follows that the influence update of two neighbors may not symmetric when Clip(æ; Zy; 7,) & Clip(z; Tz) This asymmetry between clipping thresholds in CS-RG may bias the average of honest parameters independently of the allack of Byzantine nodes.
Brror
Variance
Bias
10a
10-2
0.010
10
10
10
0.005
10-8
10-2
10-10
0.000
50
100
50 Iteration
100
1 LocalTrimming
LocalCCiinnii
GlobalClipping
Figure 1: Bias Variance decomposition of the parameters of honest nodes. GTS-RG (LocalTrimming)) CS-RG (LocalClipping) and the GCR are tested under ALIE attack, in Two Worlds graph (ef. Section 5) with 64 honest nodes in two cliques, each being neighbor to 16 nodes in the other clique, and to 3 Byzantine nodes.
Trading bias and consensus. This bias induced by the communication scheme is fundamental difference with the dual approach such as exposed in Algorithm 1, where the bias is only induced by the Byzantines nodes. This discrepancy is reflected in the analysis: in the bias of Algorithm is controlled directly in the GCR, while for instance (Gancher et al., 2025) controls the additional bias at cach step, and sum them up by using that honest nodes converges quickly enough to the same value. Overall, Algorithm with the GCR does not alter the average of honest parameters and thus can induce less bias in the communication process than local clipping methods. Yet, there is no free lunch: the variance of the honest parameters does not converge to 0 using the GCR, while CS-RG for instance ensures asymptotic consensus. We illustrate this point in Figure 1.
4.2 Dual formalism for asymmetric clipping
Considering the weak convergence guarantee of the GCR, we modify slightly the dual formalism to allow local clipping thresholds. Then we discuss the major difficulties encountered when extending the dual approach beyond the case of average consensus.

---

Published in Transactions on Machine Learning Research (02/2025)
From symmetric to asymmetric clipping. In Byzantine-free settings (see Section 2.2.1), dual gradient descent leads to gossip algorithms for which the influence of node i on node is the opposite of the one of node j on node i, both are stored in Agwg. The matrix of influence updates C"VF''(CA for cach edge, the update can be written as (2), and the (Invariant) property is kept. This symmetry between the influence of two honest nodes (i,j) E Vn remains when the influence update is clipped, as long as both honest neighbors clip the influence update on edge (i j) with the same threshold. Allowing local clipping thresholds requires storing in two different variables the influence from node on node j and from node i to j.
thus has one row
To do so, consider 9 = (V.E) the directed version of the undirected graph G, enumerate its set of odges as & {i 1} and consider the directed incidence matrix ČT E BÆÊY, such that for X Rvxd and i j.j (i-)) = x;;- - x Furthermore, we define B E RVXE as the positive coordinates of the incidence matrix Ö such that for Á E Rexd and j E V, we have [BÅi, = (i-o)ee Ae-3- Under these
notations, Equation (2) can be written with directed edge-wise clipping thresholds T E R as:
X+ = A - Clip(( VF (BA))
g = 8 - nB Clip(C"TF
(8)
And, in the average consensus sub-case, Equation (5) generalizes as
g = XX - B Clip(C X.)
(9)
Node-wiss clipping thresholds. This formalism allows node-wise clipping thresholds as a sub-case of directed edge-wise wise clipping thresholds. Thus, communication algorithms with node-wise clipping thresholds ClippedGossip in (He et al., 2023) or CS-RG in Gaucher et al. (2025) exactly correspond to Equation (9)
for appropriate T'.
Proposition 3. Denoting M := BlĆ, Equation (8) can be seen a clipped pre-conditioned gradient descent on the dual objective A + (CA)::
A++1_ = - Blip(M"
(10)
In particular, we expect fized points of this iteration to be minimizers of Á (BA) in the absence of Byzanlines.
Loss of the invariant. As denoted before, even in the absence of Byzantines, the (Invariant) property, i.e.
1 = 0, does not hold by design anymorc, since [ + O.
Error metric. The main difficulty in extending the dual approach to more generic loss functions, even with a global clipping threshold, lies in this loss of invariant. The Fenchel transform F F*(Y)) is no longer informative of the distance between VF (X,) and the solution of the problem (Primal) when 1' o O. Local clipping analyses such as F-RG bypass this difficulty by directly proving linear decrease for the variance of honest nodes.
Lack of Lyapunov function Seeing Equation (8) as noisy variation of Equation (2) leads to writing
ft+ = Y - FLVF"((") + nE",, where E is the error induced by both Byzantine corruption and clipping of honest edges. Note that E' may lie in the kernel of L. If is possible to use F-RG analysis to upper-bound the error as || < pbllv/VFF* (Y,))1,, it is much more involved to find a proper Lyapunov function to leverage this bound. One can consider (PYY)), with P being the projection on span 1 However, some point it is necessary to control P (VF* (Y VF (PY))), which leads to vacuous results beyond the average consensus case.
In summary, the strength of the dual approach generally lies in its structure, which usually allows for building Lyapunov functions in a principled manner. The Byzantine case breaks this structure, which significantly hardens the analysis.
Conclusion.
5 Experiments
We perform all experiments on a 'Two Worlds' graph with 64 nodes, made of two cliques of 32 honest nodes. Each node is connected to 16 nodes in the other clique. On such graph, the theoretical maximal number
8

---

Published in Transactions on Machine Learning Research (02/2025)
of tolerated Byzantine numbers per honest node is 16. The actual mumber of Byzantine neighbors per honest node depends on the experiment. We initialize the parameter of each honest node using a N(0, Ts) distribution, each experimental configuration is run with 5 different seeds, and results are averaged. We implement ALIE (Baruch et al., 2019), FOE (Xic et al., 2020), Dissensus (He ct al., 2023) and Spectral Helerogeneity (Gaucher et al., 2025), more details are available in Appendix A.1. We compare 1) the Global Clipping rule, the threshold the largest clipping threshold verifying the GCR, 2) Local Clipping denotes the algorithm CS-RG (Gaucher al., 2025), 3) Local Trimming denotes GTS-RG, i.e. the inplementation of NNA (Farhadkhani et al., 2022) in the case of sparse communication networks (Gaucher et al, 2025).
FOE
ALIE
Dissensus
SpH
10
MSE /MSE
10
10
2
3
4
5
4
5
2
4
5
3
b
b
LocalTrimming
LLocaCCiippng
-GlobalClipping
Figure 2: Relative mean square error after T = 100 commuication steps, with varying number of Byzantine neighbors to each honest node.
Analysis. We note on Figure 2 that the GCR has similar worst-case! performances on the investigated task than methods with local aggregation rules (i.e. GTS-RG and CS-RG). However, soon as Ax 1, the GCR does not allow communication between nodes anymore, and have MSE" /MSF 1. This follows from the definition of the GCR itself: by design, the GCR is built such to ensure that nodes benefit from the communication. As such, when there is no guarantee that this is the case anymore, the algorithms prevent communication between nodes. On the contrary, node-wise aggregation methods are provably robust up to a certain amount of Byzantines but do not have any guarantees beyond this breakdown point, and they do increase the mean square error by communicating see e.g. Gaucher et al. (2025).
6 Conclusion
In this paper, we leverage the dual approach to design a byzantine-robust algorithm, which we then analyze in the average consensus case. We leverage the dual approach to re-interpret existing efficient: robust communication algorithms, and we experimentally compare our algorithms with them. Finally, we highlight that the usual strength of the dual approach to decentralized learning - its structure introduction of Byzantine nodes, which brings significant challenges to the analysis. Yet, interesting algorithms arisc, which do not ensure consensus among nodes (as standard algorithms do, the price of some bias). Finding new ways of better characterizing the convergence properties of such algorithms is an interest open problem.
broken by the
7 Statement of Broader Impact
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Note that the empirical worst-case performance among all attacks is the meaningful evaluation of the resilience of algorithm, and thus the superior performance LocalClipping against Dissensus and SpH only denotes that these attacks not optimal against LocalClipping, and not that LocalClipping has superior robustness.

---

Published in Transactions on Machine Learning Research (02/2025)
Acknowledgments
The work of Aymeric Dieuleveut and Renaud Gaucher supported by French State aid managed by the Agence Nationale de la Recherche (ANR) under France 2030 program with the reference ANR-23-PEIA-QU (REDEEM project). The work of Aymeric Dieuleveut was also supported by HilParis FLAG chair.
References
Dan Alistarh, Zeyuan All, and Jerry Li. Byzantine stochastic gradient descent. Advances in newral information processing systems, 31, 2018.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 1232 1300. PMLR, 2023.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, (2(6))2508-22) 2530, 2006.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-25, 12:: 2017.
John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3))592-600) 2011.
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lé Nguyên Hoang, and Sébastien Rouault. Genuinely distributed byzantine machine learning. In Proceedings of the 39th Symposium Principles of Distributed Computing, pp. 355-364, 2020.
Mahdi El-Mhandi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyèn Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asyn- chronous and nonconvex learning). Advances in Neural Information Processing Systems, 34:25044 25057, 2021.
Sadegh Parhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging momentums. In International Conference on Machine Learning, pp. 12-6-6283. PMLR, 2022.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Lê-Nguyên Hoang, Rafael Pinot, and John Stephan. Robust collaborative learning with linear gradient overhead. In International Conference on Machine Learning, pp. 9761-9813. PMLR, 2023.
Renaud Gaucher, Aymeric Dieuleveut, and Hadrien Hendrikx. Unified breakdown analysis for byzantine robust gossip, 2025. URL https://aaxi:: orggabss/410..04// 10418.
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine-robust decentralized learning via clippedgossip, 2023. URL http:://aaaxivvo./aaaa/////sss/
01545.
Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Accelorated decentralized optimization with local updates for smooth and strongly convex objectives. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 897- 997-906. PMI.R, 2019.
10

---

Published in Transactions on Machine Learning Research (02/2025)
Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Dual-free stochastic decentralized optimization with variance reduction. Advances in neural information processing systems, 33:19455- 199456199666, 2020.
Hadrien Hendrikx, Francis Bach, and Laurent Massoulie. An optimal algorithm for decentralized finite-sum optimization. SIAM Journal Optimization, 31(4):2753 2783, 2021.
Dušan Jakovetié. A unification and generalization of exact distributed first-order methods. IEEE Transactions Signal and Information Processing over Networks, 5(1):31 46, 2018
Dušan Jakovetić, Dragana Bajović, João Xavier, and José MF Moura. Primal dual methods for largo-scale and distributed convex optimization and data analytics. Proceedings of the IEEE, 108(11):1923 19111-9998,,, 2020.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. PMLR, 2021.
In International Conference on Machine Learning, pp.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. ryzant learning on helerogeneous dalasets via bucketing, 2023. URL https://arxvv.org/ wwt. 09365.
Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 18:18342-183577 2020.
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 433):382-401, 1982.
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. Rsa: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544 1551,155, 2019.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE
Transactions on Aulomatic Control, 54(1):48 61, 2009.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference on machine learning, pp. 3027-3036. PMLR, 2017.
César A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedié. dual approach for optimal algorithms in distributed optimization over networks. In 2020 Information Theory and Applications Workshop (ITA), pp. 1-37. IEEE, 2020.
Zhaoxian Wu, Tianyi Chen, and Qing Ling. Byzantine-resilien docentralized stochastic optimization with robust aggregation rules. IEEE transactions on signal processing, 2023.
Cong Xie, Oluwasammi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270. PMLR, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5630-5659. PMLR, 2018.
A Experimental design
A.1 Byzantine attacks in the federated case
In our experiments, we implement SOTA atlacks developed for the federated SGD setting: Fall of empire (FOE) from Xie et al. (2020) and A little is enough (ALIE) from Baruch et al. (2019), Dissensus from He et al. (2023) and Spectral Heterogeneity for Gaucher et al. (2025). We implement all these methods by making Byzantine node j E Vo declare to an honest neighbor i V/, a vector 2ÿ x + Efa, where of Rd is the attack direction node i and of the scale of the attack.
11

---

Published in Transactions on Machine Learning Research (02/2025)
ALIE.
The Byzantine nodes compute the coordinatewwiee standard deviation o². Then they use
a ===+ o².
FOE. The Byzantine nodes compute the mean of the honest parameters z', and declare of = z².
Dissensus. The Byzantines take df En-j kev, 2 -
x
Spectral Heterogeneity. The Byzantines compute the Fiedler vector of the honest subgraph fieds i.e. the eigenvector associated with the second smallest eigenvalue of the Laplacian of the honest subgraph. Then, they take af = [efied]i Σkev, (efeed)=2..
In all attacks chose of to maximize the error induced by Byzantines: for trimming take it such that all Byzantine allacks are just below the trimming threshold, while for clipping strategies chose ef >> 1.
B Proofs
B.1 Notations
In this subsection we resume the different notations of the proofs. Table summarizes notations used for primal and dual parameters, as well as Lagrange multipliers.
Table 1: Summary of notations
Variable
Name
Size
Rows
primal parameter
x
(xi)kev
dual parameter
V x
(Yi)iev
Lagrange multipliers
CCA)
Influence update the edges
(#; (iso))E
We recall the algorithm in the global clipping setting:
X X/1 (TCh Cb) Clip(C"xx;r))
x
In the global clipping setting, we consider that, as 7' = r',g, we can overload the clipping operators writing for A E ipeadd xd and Ag E Rexxd
Clip(An;7") +Clip(A(ssss)> 7 Dlsssee
(11)
Clip(As;7') =[Clip(A(aw)) (oWSEE
(12)
We use the following notations:
For any matrix M E Raxd, we denote
M
1m
17 M. na
Th
We note the primal parameter re-centered the solution
Z = X
The unitary matrix of attack on edges linking to Byzantine nodes
U = 1p2
(Ap+1 - -A3).
Thus || & and Ag+1 A₁ Clip((CT x9)1;7() A₁ Ur.
12

---

Published in Transactions on Machine Learning Research (02/2025)
The error term induced by clipping and Byzantine nodes
E = Cn. (C², z Clip(C Z);7)) +.U.U
We denote for e 21 and n¹ E fo..... [
10 Xillppee
Σ
IKC (me))
(in))EEa, x² largest
10 x pp == ==10 x
We recall that by default ||-|| and ||- ll2 is the usual Euclidean norm (or the Frobenius norm in case of matrix).
And we recall some previous facts:
Ln C,TT 1 the Lagrangian matrix on the honest subgraph Gh.
Ia, =0 - X -0 = C = 0₁ z
C the Moore-Penroese pseudo inverse of Ch.
B.2 Analysis of Global Clipping Rule (GCR) Theorem
Lemma 2. (Gossip Error decomposition) The iterate update can be decomposed as
zz = (In nLa) + nE
Proof. The actualization of X writes
x x - Cn Xhip((X)i:7) nOs Clip([CT Clip((CTT')=77)
Using X2 CT % get
2 2%, Cn Clip(C] x(;7) + Cr'
(In - -,CC 2 + tn (C) zj - ((ip(C//Z::7)) + +r'CUU))
(In - mL)) +
Lemma 3. (Sufficient decrease on the variance) We have the decomposition of the variance as biased grudient descent:
- 2 1
12 - 2 + 17 Ln E²11 - 2f 2n 27, E²).
Proof. start from Lemma 2
1 17 || 7 nTLn - 1
+2 + - E - +2m - E*)
=
=1Z 2 7² [ - 2nl 2nl C/ + ET,
where we used that Z and Cr. Li. Lemma 4. (complete sufficient decrease)
12 1 Tu 23 E.112 2n/1C 2012 2n -
13

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. We leverage that
| = / +
1//t11 2 12
| 2
| 2 2 Z
Then we use Lemma 3.
Assumption 1. Definition Tradc-off between clipping error and Byzantine influence. By denoting
Do == sup U.
We assume that 7 0,
110% x > Ax 1o, +
Σ T"
Thh
0
Lemma 5. (Join control of the first order error and second order bias) Under Definition we have that
1 F T 2
Z + 1
7/ CI 2
7' = =.
Proof- We begin by upper bounding precisely both error terms:
1. Varianco-induced error.
Ez) - - 2% Ch (C - Clip( - + - -Z,,,
-C,, %h, C% 7i Clip(C% 21:'') + (C Z, ,C,,C,U)
Using that 7 = 0. On one side we have that,
(C), 2i, C 2 Clip(C 23:19))
Σ
(2f 261-2/10 2/, - 21 -Clp(z} - 7'))
(in))EEn
Σ
2/1la (11= 21112 -²) l
(iN))E
One the other side, by using that, for M, N E Bnxd (M,N) & |1 as:
(M,N)
Σ (inj)EEE
(M(-s)) N(w-))
Σ
|| N
(inj)EE,
< ||,,,,
Σ ||Meo))
(i~j))E,,
we can upper bound the second term
<
14

---

Published in Transactions on Machine Learning Research (02/2025)
Then by defining Ax Su 1, using |1 2/ Eitn)EEn 11 - 251l2. we have that
(2h T/ E") <
Σ
| zilla (112f zill2 - +') Do0
E
1 zzll2 ll2
(
(imj)EER
Σ
1| - 2)11 1|1 -
=
(imj)EEE
Σ
11 - 25ll2 1 12, -
Σ
1 - 2/11
(trr)EEn
(bnr))EEn
Let's consider any xf E N such that
ntt
Σ
Σ
(i~S)EER
(b-j)EEn
Then, using
2
Σ
1 2
(inj)EEn xe largest
the previous inequality writes
(Z) - E")
< |1 2.12, - (ICT - Ax010%%
From this upper bound we could derive a clipping rule taking only into account the error induced by clipping and Byzantine nodes on the variance. In this analysis, we will include the second error term induced by the bias.
2. Bias-induced error. We consider the term (2), x,
Z We remark that, using that 2,,1 = (Lr - C2 + nE", and considcring that 1", Ch = 0, using the definition of E we get:
1 1 IT, Zí + T7T I C.U = Σ " C.U..
8=0
Using this, we remark that
2' = 21+T - - = 7²1 1112 + (2) Z
Z2 = =Zttt 7 z
1tttt -2%).
Thus we get
(2
7141
Σ
qT 11
1nx 1 n. Thp
CoUS, "TT 1 -nn, 1 CoUb
-1,,,
(1T ng.
C.US 1 (L.C,U)
r'm 2
No(i)uff Σ [Nalout)
VEVA
SEV
Where of is the mean vector of Byzantine neighbors of node E Vn, so that ||uffl2 & 1, thus we get
2
Σ No(i)
Σ 7
Thh
Th
V.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Now that we controlled both terms, we mix both error terms:
- - 1/ 13) + (Z Z
< || 1 +' (1C2 2i Do 102%%,11 + 7 +
AAA
||C% 11 7' 110% x
7/
n4h
Hence, as long as
n766/1
[0 Aill,a > IR +
Σ T
(13)
T/b
==0
we have that
(2 (",
2 <
1 2/ 12.
When Equation (13) cannot be enforced using x² < |1 1, then we take 7 0 (thus x² [Exl), everything is clipped and nodes parameters don't 't move anymore.
Lemma 6. (Control of first and 2nd order ervor lerms logether) Assume Definition 3 and that
Piax (Lh)²
then by denoting the first and 2nd order error term, dévided by 1 as
nl E. +
(7, zh)
We have the control:
5² E MPmmx (Ln) (11C) 7 - + (7')3 -1-112222) 24xx) +
A31 + +2 2 11
Proof. This part of the proof allows to compute the maximum stepsize usable. We want to control the discretization term Th, E' l1.. II E' 0 it would have been done using step-size small enough. In this case we will do the same, but we will monitor the interactions between the discretization and the control of the error. Note that
F L, = Cr Clip(C) Z/:²') + +
(14)
and that the first order (C, Clip(C, Z): 7,; -',U)) & 0 if Byzantine aims preventing the convergence. Thus, we will include this second-order term in the proof of the Lemma 3.
We denote by Pmax (Ln) the largest cigenvalue of Li.
We denote the first and 2nd order error term, divided by 17 as
st = nl Zh. E² 12 + 2( Ey, 22 ZT)
Hence 1 < | + 5 - 2nl C 11112
Using
|| | T. = |CCpp - -C,CC,) 1
= || (Clip( CT 2/; +C
have:
16

---

Published in Transactions on Machine Learning Research (02/2025)
5² =
E
+ + - 20, z
< 1//maxx (n.) (11 (1Ciic((((////))))+++1CC00000
2mp
+ 7
+2 Z 7' C,CCUU + 2, C Clip(C Zhi+')) + 2n 2n (2,
-1/ (Ln) (1I Clip(O 21) 1
+2(C% 7 C 7 Clip(Ck %/: +')) + 27 ( 7/2
+ +1111 - max )
Ch Un - C,U,)
<|[C), 2 A
2mx (T.) (C %
Clip(Ch 7'), c.CC,,))
- 27:-()] A
Then we use that
110% 23 (1 - 21 || Clip(CT 7))r))
to get, for r & Mmax (Ln),
5¹ < M1max (Ln) (1CIbbCG/44:///1=++HHCC
+ +2CC) Z% C Zi - Clip(C2 21: 21:1((
+ +n 2onn((z7) 1Z Z Z
+ 2(1 m//m (L,) (L,)) Z |l A + 2 (Lx) C Aoo
ma// [ Clip(C) z/; A0
< m1/mmax (L,) (11 Clip(C), 7%; -') )| + || C 2/l Clip(C Z/i (')l] A00
+ 2 2 C Zi - Clip C 1 7²)) + C| 2011 + 2n (Z,,t) ( -//²1 Z,,
Then, the second term is controlled using the proof of Lemma By denoting
A = sup 13
IC
we have that, under Definition
5¹ < MP (Ln) (11C% z l mn + (T'n' + - 2''N'' 2 (1,))=)))) + 211C 2.112
< m/mmax ( (L) ((1 A00) | 2 -x (7')² [x*(1 24xx) 4 211C% 2j 122...
Eventually, leveraging that 43 & 42 |1 have
5² < MPmmaxx (La) (1 z 22 - (+*)) (x -A.) + 1 +210 12,,,
Theorem 2. Hence, under Desinition 3, for
Mmnax (oaxxe(Lr)) (Lh)
1 <
-Do0)
we have
12
11 mlI.% 2
17

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. We start from Lemma 4 and use the majoration of the error from Lemma 6:
1| = - 2n 2 - =²11 2m1(Zh En, + 2, 3
< || | 21 + + 7 11
+ r Pmax (L)) (110% 2,112, + ++')² (1'(1- - 2D + +
|| | 2nl Ch Zh, 12 -x
+ r² Mmaxx (Ln) (1 Z 1,, 2 + (T')² [x'(( 2A
(0 + 2 [x]]
< | 17 [2 max (L.) (1+ x'((1 2 + - & |] 10 / 11112.-2
Where we used that, as n¹ & (Ems)Es -//-=//1 -1, the largest term in 1 Z 12 -x is (T))
Hence, for
Mmax (Lh) 1 xot
20 A E
or, using a simpler (and stricter) condition
Mmax Mma (Lp) 11 Doo)
have
11 < 12 oII.T 2
B.2.1 On the computation of Aco
We recall that
Doo = sup fxd
ICA.C,Ulloo.. 11
Proposition 4. (Computing A Consider fully connected graph G, we have that
2nd V [8).
Ax E sup (Knj))E
where un is the number of Byzontines nodes and ny the number of honest nodes.
Proof. In fully connected graph L., = n4Th Jn - 1, thus = = na -...T. Using this, we compute:
Ax
sup
ICC.C.Ulll...
Fue 10
1
[|C CaUblimn)
sup fod (i-))EE,
sup
Th
[|Us|bo.2E1
18

---

Published in Transactions on Machine Learning Research (02/2025)
For (i ~ E En.
sup Une |0,
[[ C,Ubl(--)):1B
sup U 20
[C% Collessn
[[Cbbe. - [Co]::1 (Ub)a:)"Ub)).e))
sup FoERooxd 21
[[[Ck], [Cbb,,11i
sup U [
(No(1) + No())
Σ ||Ubb,,
sup
U
Amm
< (N&(1) + (dA)) (&)))
Hence, we get:
No(1) No()) Van [8
E sup (t-j))En,
nh
Thus, assumiin that, as we are in a fully-connected graph, every honest node is connected to na Byzantine node, we get the result.
B.3 simplified global clipping rule
The following proposition provides a sufficient condition for being a GCR that only requires He to be large enough, without any dependence on X
Proposition (Simplified GCR). If (7') is such that: for all 0, either 7 or
E
x¹ >
A En +
(15)
1hh
3E
then (r") satisfies the GCR.
This result reads as a lower bound on the fraction x²/(Eal edges that are clipped.
Proof. (GCR), i.c Equation (13) writes
1/E6,2 2
[C Zilli 2
Axo ZiIl +
0=
19

---

Published in Transactions on Machine Learning Research (02/2025)
We leverage that 10, 11, > r'x' and that [|C Z -x & T'(n - x²) to write
[10% Zill,,x 20 + n 2
7"
nbb
7/86 2 !
= (1- 11 1, > |1%h Z% 1 +
Σ 7
77
= (1 Doo) Ao 7 n.t) +
n
7/66/ 2
= R'T' T' EEal +
T
Th ==0
n² > 00 E + n/Eo?
7
Tt
20


Reviews:
[{"review_id": "1XXVOYp6Ms", "reviewer": "Reviewer_GPXg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has several strengths.\n\nFirstly, the application of the dual formulation to Byzantine robustness is a significant and novel conceptual contribution. It provides a principled and unifying framework for understanding and designing robust decentralized algorithms, moving beyond ad-hoc aggregation rules.\n\nThe second factor is theoretical analysis. The convergence analysis for the ACP case is thorough. The derivation of the GCR is a key strength, as it formally justifies when and why communication should be attenuated to prevent Byzantine nodes from causing harm, a concept often implicit but not formally captured in prior work.\n\nIn general, I would like to recommend this paper for acceptance. However, there are also several weaknesses.\n\n(1) Limited Practicality of the GCR. The primary weakness of the proposed GCR is its reliance on global coordination and knowledge (e.g., of $\\Delta_{\\infty}$, $|C_h^T X_h^t|_{1,2;\\kappa^t}$). The authors correctly note this is a \"proof of concept,\" which limits the immediate applicability of the main theoretical result in truly decentralized systems. A discussion on how to approximate these global quantities in a decentralized manner would significantly strengthen the paper's impact.\n\n(2) Narrow Problem Scope. The strong theoretical guarantees are currently confined to the Average Consensus Problem. While Section 4 provides an excellent discussion of the difficulties in generalizing the approach, the paper would be significantly more impactful if it included even a preliminary extension or empirical validation on a more general distributed optimization problem (e.g., distributed logistic regression).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a study on Byzantine-robust decentralized optimization, specifically within the gossip communication framework. Its primary contributions includes:\n\n(1)The paper leverages the dual approach to decentralized optimization to derive EdgeClippedGossip, a new algorithm that achieves robustness by applying a clipping operator directly to the updates of the Lagrange multipliers (the \"influence\" between nodes) on the edges of the communication graph.\n\n(2)The authors provide a rigorous theoretical analysis of EdgeClippedGossip in the Average Consensus Problem (ACP). They introduce a Global Clipping Rule (GCR) and, under this rule, prove convergence guarantees (Theorem 1). This analysis formally characterizes the trade-off between reducing variance among honest nodes and controlling the bias introduced by Byzantine nodes.\n\n(3) The paper demonstrates that several existing state-of-the-art robust gossip algorithms (e.g., He et al., 2023; Gaucher et al., 2025) can be recovered as specific instances of their proposed dual framework with asymmetric clipping. Furthermore, it offers a insightful discussion on the fundamental challenges—such as the loss of the invariant property and the lack of a Lyapunov function—that arise when extending the dual approach to Byzantine settings beyond simple averaging.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The related work section and the broader discussion could be improved by a more direct comparison with other robust aggregation strategies. For instance, while the clipping operation is central to this work, it would be insightful to relate it to other robust loss functions or gradient manipulations.\n\nFor example, the work of Zhao, Puning, Fei Yu, and Zhiguo Wan (2024) on Huber loss minimization for Byzantine-robust federated learning offers an alternative, well-motivated statistical approach to outlier rejection. A comparison of the underlying philosophy (loss geometry vs. dual influence control) would be valuable.\n\nSimilarly, the gradient normalization technique proposed by Zuo, Shiyuan, et al. (2024) for handling non-IID data in federated learning addresses the challenge of biased updates, which is related to the \"bias\" discussed in this paper. Drawing connections to such methods could broaden the paper's relevance.\n\nThe very recent work by Fang, Minghong, et al. (2024) on \"Byzantine-robust decentralized federated learning\" is a direct contemporary; a more detailed comparison to their approach and findings would better situate this paper within the current literature.\n\n[1]Zhao, Puning, Fei Yu, and Zhiguo Wan. \"A huber loss minimization approach to byzantine robust federated learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 19. 2024.\n\n[2]Zuo, Shiyuan, et al. \"Byzantine-resilient federated learning employing normalized gradients on non-iid datasets.\" arXiv preprint arXiv:2408.09539 (2024).\n\n[3]Fang, Minghong, et al. \"Byzantine-robust decentralized federated learning.\" Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jxLDULr0cd", "reviewer": "Reviewer_unrv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper uses the dual optimization framework to develop a principled method for Byzantine-robust decentralized optimization. The proposed method is theoretically grounded.\n- The paper also uses the dual framework to re-interpret and discuss existing local clipping algorithms. Based on this, the paper reveals an interesting trade-off: the local clipping-based methods introduce additional biases but enjoys guaranteed asymptotic consensus; on the other hand, the global clipping-based method is free from such biases yet does not guarantee consensus.\n- The authors are transparent about the limitations of the paper, for example, the theoretical result for the global clipping method does not provide convergence rates.\n\nWeaknesses:\n- If I understand correctly, the proposed global clipping strategy is in fact an oracle strategy, in that it requires knowledge of the \"sum of node-wise differences on honest neighbors only\". This makes this strategy impractical in practice, and hence may limit the practical contribution of the paper.\n- As the authors have acknowledged, an important limitation of the theoretical results in this paper is that it does not offer a concrete convergence rate. This is likely to limit the theoretical contributions of the paper.\n- It is unclear to me how the empirical results in Fig. 2 demonstrate the empirical advantage of the proposed methods. The results suggest that previous methods based on local clipping consistently achieve smaller final errors, and the proposed global clipping method is likely overly conservative in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper conducts a theoretical study of Byzantine-robust distributed learning in the decentralized setting. The authors propose EdgeClippedGossip which is robust against Byzantine nodes that is designed based on clipped dual gradient descent. Convergence guarantee is provided for the proposed algorithm for global clipping. The paper also uses the proposed framework to re-interpret previous methods based on local clipping.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the Weaknesses above. I think both the theoretical and empirical aspects of the paper could benefit from additional contributions.", "broader_impact_concerns": "The Broader Impact section is left empty. I think the paper is indeed more theoretical in nature and hence may not have immediate negative impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KodHby5kF8", "reviewer": "Reviewer_YXxX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**  \n1. The paper introduces a novel perspective by leveraging the dual approach for Byzantine robustness in decentralized optimization. It connects with existing robust communication algorithms, providing a unifying view.\n2. The paper provides theoretical convergence guarantees for the proposed EdgeClippedGossip in the average consensus subcase under the Global Clipping Rule (GCR).\n3. The paper demonstrates the trade-off between bias and variance, and shows empirical results supporting this claim.\n\n\n**Weaknesses**\n1. The paper is limited in proof of concept for the Global Clipping Rule, but doesn't provide a practical decentralized algorithm.\n2. The experimental setup is unclear. The whole paper is based on decentralized settings, but it compares with FOE and ALIE which are federated settings with a central server. Why is it necessary to compare with these two baselines rather than other decentralized methods?\n3. Empirical results are insufficient. Could you provide empirical results on MNIST and CIFAR-10? Although implementing GlobalClipping may be challenging, comparing it with LocalClipping and LocalTrimming on more realistic datasets is essential.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces EdgeClippedGossip, a new Byzantine-robust algorithm for decentralized learning that uses a dual optimization framework to clip influence updates on graph edges. It provides convergence guarantees for this method in the average consensus setting, where it recovers existing algorithms. It also proposes a Global Clipping Rule (GCR) as a theoretical proof-of-concept, demonstrating a trade-off where GCR reduces bias but doesn't guarantee full consensus. While GCR has practical limitations due to its global coordination requirement, the paper re-interprets other robust algorithms within its dual framework and highlights the challenges of extending this approach to more general decentralized optimization problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In the 2nd paragraph of Introduction, there is a typo: \"We denote $V_b$ as Byzantine nodes...\".\n- Section 7, Statement of Broader Impact, is empty.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)