On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Authors: Yi-Rui Yang
Chang-Wei Shi
Wu-Jun Li
Venue: ICML 2025 spotlightposter (2025)
Keywords: distributed machine learning
Byzantine robustness
robust aggregation
Primary area: optimization->large_scale_parallel_and_distributed

Abstract: Byzantine-robust distributed learning (BRDL), which refers to distributed learning that can work with potential faulty or malicious workers (also known as Byzantine workers), has recently attracted much research attention. Robust aggregators are widely used in existing BRDL methods to obtain robustness against Byzantine workers. However, Byzantine workers do not always exist in applications. As far as we know, there is almost no existing work theoretically investigating the effect of using robust aggregators when there are no Byzantine workers. To bridge this knowledge gap, we theoretically analyze the aggregation error for robust aggregators when there are no Byzantine workers. Specifically, we show that the worst-case aggregation error without Byzantine workers increases with the increase of the number of Byzantine workers that a robust aggregator can tolerate. The theoretical result reveals the tension between Byzantine robustness and no-attack accuracy, which refers to accuracy without faulty workers and malicious workers in this paper. Furthermore, we provide lower bounds for the convergence rate of gradient descent with robust aggregators for non-convex objective functions and objective functions that satisfy the Polyak-Lojasiewicz (PL) condition, respectively. We also prove the tightness of the lower bounds. The lower bounds for convergence rate reveal similar tension between Byzantine robustness and no-attack accuracy. Empirical results further support our theoretical findings.

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Yi-Rui Yang
Chang-Was Wei Shi
Wu-Jun Li
Abstract
1. Introduction
Distributed learning has been a hot research topic for years (Haddadpour et al., 2019; Jaggi et al., 2014; Lee et al., 2017: Lian et al., 2017; Ma et al., 2015; Shamir et al., 2014; Sun et al., 2018; Yang. 2013: Yu et al., 2019a;b; Zhao et al., 2017; 2018; Zhou et al., 2018; Zinkevich et al., 2010). Tra- ditional distributed learning typically assumes no attack or failure. However, some real-world scenarios such as federated learning (McMahan Ramage, 2017), the probability of attacks or failure greatly increases due to the server's weak control on workers (Baruch et al., 2019; Kairouz et al., 2021; Xie et al., 2020a). The workers under attack or failure are also called Byzantine workers (Lamport et al., 1982). Byzantine- robuust distributed learning (BRDL), which refers to distributed learning that can work with poten- tial Byzantine workers, has recently attracted much research attention (Bernstein al., 2019; Bulusu al., 2021; Chen et al., 2018; Damaskinos et al., 2018: Diakonikolas et al., 2017; Diakonikolas & Kane, 2019; Konstantinidis & Ra- mamoorthy, 2021; Rajput et al., 2019; Sohn et al., 2020; Wu et al., 2020; Yang & Li, 2021; Yang et al., 2024; 2020; Yin ct al., 2019).
Byzantine-robust distributed learning (BRDL), which refers to distributed learning that can work with potential faulty or malicious workers (also known as Byzantine workers), has recently at- tracted much research attention. Robust aggrega- tors are widely used in existing BRDL methods to obtain robustness against Byzantine workers. However, Byzantine workers do not always exist in applications. As far as we know, there is al- most no existing work theoretically investigating the effect of using robust aggregators when there are no Byzantine workers. To bridge this knowl- edge gap, we theoretically analyze the aggrega- tion errrr for robust aggregators when there are no Byzantine workers. Specifically, we show that the worst-case aggregation error without Byzan- tine workers increases with the increase of the number of Byzantine workers that a robust aggre- gator can tolerate. The theoretical result reveals the tension between Byzantine robustness and no- attack accuracy, which refers to accuracy without faulty workers and malicious workers in this paper. Furthermore, we provide lower bounds for the convergence rate of gradient descent with robust aggregators for non-convex objective functions and objective functions that satisfy the Polyak- Lojasiewiez (PL. condition, respectively. We also prove the tightness of the lower bounds. The lower bounds for convergence rate reveal simi- lar tension between Byzantine robustness and no- attack accuracy. Empirical results further support our theoretical findings.
Robust aggregation is a widely used technique to obtain Byzantine robustness in distributed learning. By replacing the vanilla mean aggregator the server with some robust aggregators, the distributed learning method can be robust against a certain number of Byzantine workers. There are many robust aggregators proposed in existing works (Blan- chard et al., 2017; Chen et al., 2017; Guerraoui et al., 2018; Karimireddy et al., 2021; Yin et al., 2018). Meanwhile, using robust aggregation will also inevitably introduce an aggregation error, which is the square distance between the aggregation result and the true mean value. Large aggrega- tion error will lead to a decrease of model accuracy.
Existing analyses (Allouah et al., 2023; Karimireddy et al., 2021; 2022) for the aggregation error of robust aggregators typically assume that the number (or fraction) Byzantine workers is known in advance, while in real-world applica- tions, the number of Byzantine workers is usually unavail- able. It is advised in existing works (Karimireddy et al., 2022; Yang & Li, 2023) to determine the maximum number of Byzantine workers that the BRDL method can tolerate
'National Key Laboratory for Novel Software Technology, School Computer Science, Nanjing University, Nanjing, China. Correspondence to: Wu-Jun Li <liwujun @ weroienjnu....oo.. eju.edu.ens.
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
in advance and then set the robust aggregator accordingly. However, Byzantine workers do not always exist in appli- cations. When there are actually no Byzantine workers, the aggregation error introduced by robust aggregators could have negative effect on the convergence of distributed learning methods and degrade the model accuracy. As far as we know, there almost no existing work theoretically investigating the performance of robust aggregators when there are Byzantine workers. To bridge this knowledge gap, we mainly focus on the following question:
Algorithm Byzantine- Gradient Descent (ByzGD)
Input: iteration number T, learning rates {1e TT ro- bust aggregator Agg(-);
Initialization: model parameter wo: for t 0 to T - do
Broadcast w, to all workers;
on worker i E {1...., n in parallel do
Compute local gradient g, = VF((w:);
Send g: to the server;
end on worker
How large could the aggregation error be when there are actually no Byzantine workers?
Compute: Wx+1 Wt T/ Agg(gi...... end for
Output: model parameter WT.
The main contributions of our work are listed as follows:
to solve the problem (1) is gradient descent presented below:
To the best of our knowledge, this is the first work that theoretically investigates the tension between Byzan- tine robustness and no-attack accuracy in distributed learning.
We+1 W. 7t 1
g
Specifically, at the t-th iteration, all the workers compute local gradients g...... gn in parallel and send them to the server. Then, the server aggregates the gradients with vanilla averaging and updates the model parameter with the aggre- gated gradient. However, the averaging value is sensitive to the outliers and not robust against Byzantine workers. Therefore, robust aggregators such as Krum (Blanchard et al., 2017), geometric median (Chen et al., 2017) and coordinate- wise trimmed mean (Yin et al., 2018) pro- posed replace vanilla averaging in BRDL. By replacing the vanilla averaging with some robust aggregators, we can obtain Byzantine-robust gradient descent (ByzGD). In ByzGD, the model parameters are updated by:
We theoretically prove that the worst-case aggregation error without Byzantine workers increases with the in- crease of f. which is the number of Byzantine workers that a robust aggregator can tolerate. The theoretical re- sult reveals the tension between Byzantine robustness and no-attack accuracy.
Moreover, we provide lower bounds for the conver- gence rate of gradient descent with robust aggrega- tors for non-convex objective functions and objective functions that satisfy the Dolyak-E.jjsiewwic (PL.) con- dition, respectively. We further show that the lower bounds are tight and increase with the increase of f.
We also provide empirical results, which further sup- port our theoretical findings.
W++1 W. 10--10 T)
Agg(gi. . Bn).
where Agg(.) denotes a general robust aggregator. More details about ByzGD are presented in Algorithm 1.
In addition, would like to point that existing works on robust aggregators mainly explore the performance when there exist Byzantine workers while we focus on the case without Byzantine workers in this work.
In existing works, there are several definitions of robust ag- gregators that are used to analyze the aggregation error. The definition of (Smax, c)-ARAgg (Karimireddy al., 2022) is proposed based on the expectation of the distances among the vectors while the definition of (f. A)-resilient averag- ing (Farhadkhani et al., 2022) is proposed based on the maximum distances among the vectors. In (Allouah et al., 2023), the definition of (f, k))robustt aggregator is further proposed, which can unify many existing definitions of robust aggregators including (6max. c)-ARAgg and (f, A)- resilient averaging. Due to this reason, we mainly follow the definition of (f, -oobbusstt aggregator in this work. For to represent the L2-norm simplicity, we use the notation || in this paper.
2. Preliminary
Many distributed learning problems can be formulated as:
min F(w)= WERd
R(().
where w is the model parameter, n is the number of workers and (w) is the loss function associated with the training data on the i-th worker. Moreover, we mainly focus on the Parameter Server (PS) framework, where there is an extra server responsible for coordination, A widely used method
Definition 2.1 ((f, robouuseesssss (Allouah et al., 2023)).
Let < 3 and x: 2 An aggregator Agg : Rd + Rd
2

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
said be (J, -robuust if for any n vectors x1:...;; ;,....;,,, Xn Rd and for any set S S (1,.... satisfying |S| = n f. we have
3.1. General Lower Bound
Firstly, we provide a lower bound of e for (f, k))-ubustt aggregators.
1 SS| SES
Theorem 3.1 (Lower Bound), If If (f,,))-rouust aggrega- tor e-accurate, we have n-7
Axg.(........... Xn) x S K
xx xs112
where Xs- = 1. [5] Eies x,
The lower bound --y in Theorem 3.1 is between 0 and 1 since 3. Moreover, when the total number of workers is fixed, the lower bound increases as f increases. In other words, making the aggregator robust to more Byzan- tine workers will inevitably introduce a larger worst-case aggregation error. We will discuss more about this after proving the tightness of the lower bound in Theorem 3.1.
For an (f, (foxs) aggregator, the square distance be- tween the aggregated result Agg(x)...., xn) and the mean value of non- non-Byzanting workers Xs is bounded. [ggg(x)...,,,,, x,)) xs|² is also known as the aggrega- tion error. Since the server cannot identify Byzantine work- ers, the inequality should be satisfied for any set S with [S] = - f. where f is the number of Byzantine workers that the aggregator can tolerate. Specifically, when there are actually no Byzantine workers, the aggregation error is |Agg(x)..... x.,) 1. Ei= 121 Thus, we propose the definition of c-accuracy in Definition 2.2, which measures the aggregation error when there are no Byzantine workers.
3.2. General Upper Bound
Then we provide a general upper bound of e for all (f, K)- robust aggregators in Theorem 3.2.
Theorem 3.2. Any (f, ko)-ruusst aggregator is k-accurate.
The constant is dependent f and differs for different robust aggregators (Allouah et al., 2023). We present the values of k for three common (ʃ, k)-robust aggregators, which are known as coordinate-wist trimmed mean (TM), coordinate-win wise median (CM) and geometric median (GM), respectively, and the lower bound of in Table
Definition 2.2 (e-accuracy). Let e 2 0. An aggregator Agg: Rd + IRd is said to be e-accurate if for any n. vectors XI,..., Xn E Rd, we have
n n
Aggg(x),........ x,) x|| c.
| - x12
As can see, the values of much larger than the lower bound , of Specifically, for GM and CM, the value of x is larger than 4 while the lower bound is always smaller than when ʃ < 3.- Moreover, even the lower bound n- of will be much larger than I when n-f I is close to 2 since the denominator is close to 0. To obtain tighter results, then we separately analyze the aggregation error of each aggregator.
where x 1 11
E X
f n-f of c
Comparing Definition 2.1 and 2.2, we can find that 6- accuracy equivalent (J, k))rrouuttness when f and k e. However, it is meaningless to say the robust- ness of an aggregator that can tolerate most 0 Byzantine worker (f = 0). Thus, for better readability, we present the definition of e-accuracy alone, which is about the per- formance of an aggregator in the case without Byzantine workers.
3.3. Analysis for Specific Aggregators
In this section, we analyze the value of e for TM, CM, and GM. Firstly, we present the definitions of these three common (f, ro)rrbustt aggregators.
3. Analysis of Aggregation Error
In this section, we theoretically analyze the aggregation error of (f. ko-rousst aggregators in the case without Byzan- tine workers. We only present the main results and proof sketches in this section. Proof details are deferred to Ap- pendix A the supplementary material due to the limited space.
Definition 3.3 (coordinate-we wise trimmed mean (Yin et al., 2018)). Let vectors X XI...., Xn. E Rd, The coordinate-wise trimmed mean TM Rdxn" + RRd is defined as:
[TM5 (X.,...... x.....,,,,,, x,, = 2f
Σ x, mEX,
To avoid confusion, would like clarify that f is the number of Byzantine workers that the aggregator can toler- ate and there are actually no Byzantine workers in the case that we consider. Specifically, we will focus on how large (please refer to Definition 2.2) could be in the case without Byzantine workers.
where [-ly denotes the j-th coordinate of a vector and the set X, is obtained by removing the f largest and the f smallest values of { {[x1]]...., (x,))--
Definition 3.4 (coordinate-ve median (Yin et al., 2018)). Let X,....,X, Xn E Rdd. The coordinate wise median CM
3

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Table
Values of for different robust aggregators (Allouah al., 2023)
Aggregator
TM
CM
GM
Lower bound
R
6f n-
n-
4(1 + n-23
4(1+ + n-27
2
Table 2. Values of for different robust aggregators
Aggregator
TM f/n
CM
GM
Lower bound
1
Bdx= Rd is defined as:
3.4.1. PROOF SKETCH OF THEOREM 3.6
We first consider the case where the dimension d 1. Let ;I,...,ān be any real numbers. Without loss of generality, we assume that I1 S 22 S S 2n since the order does not affect the trimmed mean of the n values. Furthermore, we let sets I_ = {1, ........................... f). Io = {f +
(CM(xI,....... Xn)l; (xi]; [xmli),
where Median(-) is the scalar median operator.
Definition 3.5 (geometric median). Let x1...., Xn E R. The geometric median GM: Rgdxn_ >> IRd is defined as:
1, 1y..., ʃ] and I = {n - f + ...... n., and define
GM( xn) arg min xERd
Σ
x x:Il-
F1_ =
(3)
iEL_
1=1
In other words, the geometric median is the vector that minimizes the sum of Læ-distances. When the vectors X,...., X2 not collinear, the optimization problem in the right-hand side of (2) has unique solution (Vardit & Zhang, 2000).
1
1
n
31 =
34
T/
(4)
Hol
11 2f
iElo
i=f+1
1
314
x
Z4.
(5)
[4
iEf
i=n-
f+1
The values of e for the three (f, R)) -robust aggregators are summarized in Table Due to the limited space, the analysis details for TM, CM and GM are deferred Ap- pendix A.3, Appendix A.4 and Appendix A.5, respectively. Moreover, please note that the value of for the coordinate- wise trimmed mean 7', exactly meets the general lower bound in Theorem 3.1. It indicates that the value of e for /M/ and the general lower bound are both tight.
According the definition,
25
5 F1
$10
I14
n
n1
n
TM (0.....,In)) = Z10-
Thus, we have
TM TM //a (r,,,..,,I, -
3.4. Conditions of the Worst Case
f (3 - _z_
f A
f A+., (6)
f We have obtained that the value of e can be up to n-f in the worst case. Then we would like to focus on the following question:
(T1o
31..)
n
n
where
= 31 - 5イ_ 2 0,
and
A = 51,
F1 2 0.
Under what conditions is the aggregation error largest?
Moreover, we define the within-group variances
To answer the question above, we would like to first present the theoretical result and a proof sketch for the aggregation error of TM Theorem 3.6 below. The conditions of the worst case can be derived based on the proof of Theorem 3.6.
07
= + Σ (x. - F1 11
$/. -
1 Σ
(x. - -
VEL_
velo
Theorem 3.6. When f < 3. the coordinate-wise trimmed mean TM s/n n-3 aacurrate.
1 Σ
$]
(x; - 31,

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
and we have the following equation
3.5. More Discussion
3.5.1. ABOUT THE TIGHTNESS OF THE BOUNDS
T1 S
( x)²=
As we can see, the value of for TM5/n exactly meets the lower bound ب-y. Thus, both the upper bound for JM/ and the lower bound are tight. Moreover, since coordinate- wise median (CM) is robust against f = - Byzantine workers, the value of for CM also meets the lower bound.
1=1
2 (A +
f [.
2
n
n-2f
2f
f 2
+
s7_
+ $1+
n
n
For space saving, the proof details of (7) are deferred to
Then we show the tightness of the value of for GM. Con- sider the case where dimension d = 1. Moreover, X1 X2
Appendix A.3. Noticing that s7_ 2 0, o. 2 0, s7, 2 0,
2n' is an even number and the
A_ and A 2 O, we have that E (x; x)²
X,,' 0 X2n' = 1. In this case, x = and 1 E | x n (Et= 1) = 4- The geomet-
and Xn'+1 = Xx +2
TM f/n (x1:...,
x)? or, equivalently,
ric median XGM can be any value in [0, 1J. When XGM =
TM / En) x f n f
or we have that ||XGM - x|| 4' Therefore, in this case.
x)² (2t
|XGM- x|2== 1
n || x:I1?
(8)
1.
For general d-dimension cases, |/M xn) x
n
and ||x; - x22 can be written as summations of square errors on each dimension. Recursively using inequality (8) for 1-
Therefore, the value c = for GM in Table 2 is tight. More- over, the value of for GM asymptotically meets the lower bound since GM is robust against f n-1 Byzantine
dimension case above, we finally obtain that
workers and lim //11/(1 |
(X).) x..) x||2
|x
x
n
3.5.2. A AOOU DATA HETEROGENEITY
Due to the tightness of the lower bound, the aggregation error in the worst case is proportional to 1 Σ ||x; x 12. which could be large when the probability distributions of x;'s are heterogeneous. Therefore, the aggregation error could be larger when data distribution are more heteroge- neous. There are some existing techniques reduce the gradient (or momentum) heterogeneity in BRDL such as bucketing (Karimireddy et al., 2022) and nearest neighbour mixing (NNM) (Allouah et al., 2023). However, both of the two techniques requires the prior knowledge of the maxi- mum number of Byzantine workers to mix the input vectors. Less Byzantine workers can tolerated we want to make the vectors more homogeneous after mixing.
implies that f/ is f- accurrtee.
3.4.2. DISCUSSION ON THE WORST CASE
By comparing Equation (7) and Inequality (8), we can find that the equation in (8) holds if and only if
2 (A A4
11
25
91
0,
n
n
1
which is equivalent to that s7_ 27, 27_ and
A A 0. Without loss of generality, we assume that A 0. Recall that ,7__ sî, and s7, are the within-group variances of {zi)er. farheto and (zi)er, respectively. Therefore, we have
From another perspective, aggregator combined with NNM (or bucketing) can be considered as new aggregator that can resist fewer Byzantine workers but have less aggre- gation error. Therefore, when using NNM or bucketing, we actually use the prior knowledge of the Byzantine worker number to make better trade-off between robustness and accuracy. Please see Section 5 for the empirical results, which will further support the theoretical findings in this section.
11 22 ... = xy and 2f+1 = = Fn- (10)
In summary, for 1-dimension case, in the case described by Equation (10), the aggregation error is the largest. For the general d-dimension case, the aggregation error is the largest when Equation (10) holds for each dimension.
Moreover, please note that the condition described by Equa- tion (10) indicates a large skewness among {=1,..., )... Thus, our theoretical results show that a large data skewness will lead to a large error of robust aggregation even if there actually no Byzantine workers.
3.5.3. SUMMARY OF THEORETICAL RESULTS
In this section, we theoretically show that for any (f. it)- robust aggregator, when there are no Byzantine workers, it is inevitably have an aggregation error in the order of
5

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
)(~اg) in the worst case. Moreover, the value of n-f increases as increases. It shows that obtain robust- ness against more Byzantine workers, the worst-case per- formance in no-attack cases is inevitably degraded, which we deem as the tension between Byzantine robustness and no-attack accuracy.
and
nG
Ff+1(w)= = _... =F((w)= = 2 2v (1n-1) (u² -2w).
It can be verified that F(w) = - Fi(w)) has the unique global mimimum point w" = n-f and satisfies Assumptions 4.1, 4.2, 4.3 and 4.4. Moreover, the updating rule of ByzGD for this case can be written as:
n
4. Convergence
In this section, we theoretically analyze the convergence of ByzGD with (S, k)-rbbust aggregators when there are actu- ally no Byzantine workers. Firstly, we list the assumptions below.
nn vf(n -
W6+1
1
(w) -)).
Assumption 4.1 (Bounded loss). 3F E IR such that V'w E
By separately analyzing the three cases where (i) 0 nn n
R4, (e.) 2 Ft.
2 2/ (ii) 1) na nG
2/1(x=12 and (iii) vj > 2/1(11
ng we can finally obtain the desired results. Please refer to Appendix A for more proof details.
Assumption 4.2 (L-smoothness). Vw, w/ E Rd [VF(w)- Fw(w')l S L|lw -wll.
Assumption 4.3 (Bounded heterogeneity). There exists
Theorem 4.5 indicates that whatever the initial point Wo, the learning rate and the iteration number T are, ByzGD with a (f, rs)-robust aggregator cannot guarantee + E [VF(w.)]l to be smaller than G for gen- eral non-convex loss functions that satisfy Assumptions 4.1, 4.2 and 4.3, Similarly, [F(WT) -1m))=F* [*] cannot be guaranteed to be smaller than : G
G 2 0 such that Vw& Rd
[VP((w)- VF(W)]& s
Assumption 4.4 F' denote the lower bound of F(w). 3p 0 such that Vw E Rd, F(w) - F < 2u VF 11..
(PL) condition). Let
n- 2 for loss functions that satisfy Assumptions 4.1, 4.2, 4.3 and 4.4.
In general cases where V (w()ss are not all the same, we have G > 0. Theorem 4.5 indicates that ByzGD with a (f, r)r-bbust aggregator cannot guarantee the convergence to O. Moreover, the term n-f S, where f is the number of Byzantine workers that be tolerated. Therefore, the convergence lower bound will be larger if more Byzantine workers can be tolerated, which we consider as the tension between Byzantine robustness and no-attack accuracy. Then we show that the constant terms , G2 and ب G² are optimal and cannot be improved. 24
The four assumptions above are common in distributed learn ing (Allouah et al., 2023; Blanchard et al., 2017; Farhad- khani et al., 2022; Karimireddy et al., 2021; 2022; Xie et al., 2019; 2020b). Specificallyy the value of measures the heterogeneity of local gradients on workers. A larger typ- ically makes the distributed learning task more challenging. Under the assumptions, we have the following convergence result for ByzGD.
_ increases with the increase of
Theorem 4.5 (Lower bound). For ByzGD (Algo- rithm 1) with any (f, -)rbbust aggregator, there exist satisfying Assump- tions 4.1, 4.2, 4.3 and 4.4, and satisfying the following condition: For any initial point Wa, any positive constant learning rate ne = 11 > 0, any constant C1 G and any positive integer K > 0, there exists an integer T > K such that
Theorem 4.6 (Upper bound). For ByzGD (Algorithu 1), under Assumption 1.1, Assumption 4.2 and Assumption 4.3, when Te r.
n loss functions
1 and Agg(.) is e-accurate, we have that
IVF((,)) 2L(F" - F(WT)) cG2.
Σ t=
VF(w:))1 Ci,
Furthermore, when F(w) also satisfies the PL condition (Assumption 4.4), we have that
T
and
eG2
Ci 2μ
F(WT) - F= S (1- [F(wo) FF1+ -F
F(WT) F*
2p
Due to the limited space, we only provide proof sketch of Theorem 4.5 here. Consider the 1 1-dimension case where
The terms 2L[P-=F(wr)) and (1 ()= Theorem 4.6 approach 0 when T - xo, while the constant terms cG² and <G² remain. Please note that c 2 L (Theo- rem 3.1) and that 7M s/n both (f, kt) re)-uttust and accurrate
F+] in
nG
(w) =.. =...::F(uuu =F((w)=
2 ff) 2
2μ
6

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
- It indicates that the lower bound ر G2 for C1 in Theorem 4.5 cannot be improved. Therefore, the constant terms in Theorem 4.5 and those in Theorem 4.6 are both tight.
with e
BN layers have poor performance with heterogeneous data across workers (Wu & He, 2018). All algorithms implemented with PyTorch 1.3.
We use cross-entropy as the loss function, set the batch size on each worker to 16, and use the cosine annealing learning rates (Loshchilov & Hutter, 2017). Specifically, the learning rate at the p-th epoch is 7/p = (tcoo(pp//1l 0. 0....... 159. The initial learning rate no is selected from {0.1, 0.2, 0.5, 1.0), and the best final top-1 test accuracy is used as the final metrics. Local momentum is used with momentum
In this section, we mainly analyze the convergence of ByzGD. In some large-scale problems, the computation of local gradients is time-consuming. Some variants such as Byzantine-robust stochastic gradient descent (ByzSGD) has much lower computation cost of each iteration and is more widely used. We would like to point out that the lower bound in Theorem 4.5 can be directly applied to ByzSGD since ByzGD can be considered as a special case of ByzSGD with a zero variance. Local momentum (Allouah et al., 2023; Farhadkhani et al., 2022; Karimireddy et al., 2021) is also proposed to reduce the variance of stochastic gradients in ByzSGD. However, the constant terms eG2 and eG' related to the aggregation accuracy c and the heterogeneity degree G while using stochastic gradients or local momen- tums does not help reduce e or G. Stochastic gradients can reduce the computation cost of each iteration, but do not have a better worst-case convergence guarantee. There- fore, for these variants, there are similar tensions between Byzantine robustness and no-attack accuracy, which we will verify by empirical results.
1Jo for =
set to 0.9. We first test the performance of using Krum (Blanchard et al., 2017) and coordinate-wis trimmed mean (Yin et al., 2018) when pyper-parameter f. which is the number of the Byzantine workers that can be tolerated, ranges from 0 to 7. It takes about 1.5 hours to run each method for 160 epochs.
2n are
As the results in Table 3 and Table 4 show, for both multi- Krum and coordinate-wise trimmed mean, the final top-1 test accuracy decreases as f increases. In other words, to make the BRDL method robust to more Byzantine workers, the model accuracy under no attack will decrease. Further- more, the final top-1 test accuracy decreases more rapidly with a smaller a. Please note that a is the prper-parameter related to the data distribution. A smaller a indicates a more heterogeneous data distribution and larger G (please refer to Assumption 4.3). Thus, the final top-1 test accuracy de- creases more rapidly when G is larger, which is consistent with the theoretical results in Theorem 4.5 and Theorem 4.6.
In real-world applications, the number of Byzantine workers is usually unknown, and it is typically required determine in advance the number f of Byzantine workers that the dis- tributed learning system can tolerate. A too small f will make the BRDL method easy to be foiled by Byzantine workers. However, a too large f may also lead to a large ag- gregation error, and thus degrade the model accuracy, even if there are actually no Byzantine workers. Thus. f should be carefully estimated before designing the distributed learning system in real-world applications.
We also test the performance of multi-Krum and coordinate-wise trimmed mean with nearest neighbour mix- ing (NNM) (Allouah et al., 2023). The NNM technique can reduce the heterogeneity of vectors. Specifically, we fix f = 7 (the maximum number of Byzantine workers that can be tolerated) for both of the two robust aggregators and let the
fNNM range from 1 to 7 for NNM. A smaller fNNM makes the vectors after mixing more ho- mogeneous but will also decrease the number of Byzantine workers that the whole BRDL method can tolerate. Specifi- cally, the whole BRDL method robust to min (f. JNNM] Byzantine workers. When fNNM O, the output vectors of NNM will be all the same and equal the mean of the input vectors. Thus, when fNNM = 0, robust aggregator combined with NNM is equivalent to vanilla mean aggregator.
5. Experiment
In this section, we will empirically test the effect of using robust aggregator when there are no Byzantine workers. Specifically, we use ByzSGD with various robust aggrega- tors to train a ResNet-20 (He et al., 2016) deep learning model on the 10 dataset (Krizhevsky et al., 2009) for 160 epochs without attacks. All the experiments are conducted on a distributed platform with 16 Docker con- tainers serving as workers and an extra Docker container as the server. Each Docker container bound to an NVIDIA TITAN Xp GPU. We test the performance of each method when the training instances are randomly distributed to the workers according to the Dirichlet distribution with hyper- parameters a = 0.1, 1.0 and 10.0, respectively. A smaller a will lead to a more heterogeneous data distribution. More- over, the batch normalization (BN) layers in the 2esNet-20 model are replaced with group normalization layers since
As the results in Table 5 and Table 6 show, using NNM alleviates the degrade of final top-1 test accuracy for both multi-Krum and coordinate-wise trimmed mean. Moreover, using smaller fNNM can lead to higher final top-1 1 test accuracy, but will also make the distributed learning method robust to less Byzantine workers. Therefore, there is also a tension between Byzantine robustness and no-attack accu- racy when using the NNM technique.
7

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Table 3. The final top-1 1 test accuracy of using mullii-Krum with various rrper-parameter f to train the model for 160 epochs under different data distributions when there are no Byzantine workers. Both of the two aggregators are equivalent to vanilla mean when f = 0. The values in the parentheses are the differences compared the case of 0.
Multi- (Blanchard et al., 2017)
a: 0.1
= 1.0
10.0
0 (=mean)
89.42%
89.36%
89.55%
88.05% (-1.37%)
87.50% (-1.86%)
88.36% (-1.19 %)
3
83.50% (-5.92%)
84.49% (-4.87%)
87.02% (-2.53%)
5
69.86% (-19.56%)
80.40% (-8.96%)
84.64% (-4.91%)
7
40.31% (-49.11%)
68.54% (-20.82%)
73.69% (-15.86%)
Table 4. The final top-1 test accuracy of using coordinate-wist trimmed mean with various hyper-paramette f to train the model for 160 epochs under different data distributions when there are no Byzantine workers. Both the two aggregators are equivalent to vanilla mean when f = 0. The values in the parentheses are the differences compared to the case of f = 0.
Coordinate-win trimmed mean (Yin al., 2018)
a: = 0.1
a = 1.0
a = 10.0
(=mean)
89.42%
89.36%
89.55%
I
50.13% (-39.29%)
66.18% (-23.18%
88.71% % (-0.84%)
3
24.95% (-64.47%)
48.32% (-41.04%)
87.51 % (-2.04%)
5
10.00% (-79.42%)
42.86%
(-46.50%)
86.68% (-2.77%)
7
10.00% (-79.42%)
40.54% (-48.82%)
83.15% (-6.40%)
Table The final top-1 1 test accuracy of using multi- with NNM to train the model for 160 epochs under different data distributions when there Byzantine workers. Both of the two robust aggregators combined with NNM equivalent to vanilla mean when fNNM = 0. The values in the parentheses are the differences compared to the case of fNNM = O.
Multi-Krum (Blanchard et al., 2017) with f 7
fNNM
0.1
a 1.0
a 10.0
0 (=mean)
89.42%
89.36%
89.55%
88.81 % (...1%)))
88.39% (-0.97%)
89.49 (-0.06%)
3
87.61 % (-1.81%)
86.56% (-2.80%)
88.93% (-0.62%)
83.16% (-6.26%)
84.63% (-4.73%)
87.99% (-1.56%)
75.03% (-14.39%)
83.88% (-5.48%)
86.94% (-2.61%)
without NNM
40.31% (-49.11%)
68.54% (-20.82%)
73.69% (-15.86%)
Table The final top-1 test accuracy of using coordinate-wise trimmed mean with NNM to train the model for 160 epochs under different data distributions when there are no Byzantine workers. Both the two robust aggregators combined with NNM are equivalent to vanilla mean when fNNM 0. The values in the parentheses are the differences compared to the case of fNNM = 0.
Coordinate- wise trimmed mean (Yin al., 2018) with f = a = 0.1
fNNM
a = 1.0
a 10.0
O (=mean)
89.42%
89.36%
89.55%
86.61% (-2.81%)
88.59% (-0.77%)
88.57% (-0.98%)
3
83.83% (-5.59%)
87.57% (-1.79%)
88.53% (-1.02%)
5
81.50% (-7.92%)
86.03% (-3.33%)
88.06% (-1.49%)
61.09% (-28.33%)
82.77% (-6.59%)
87.79% (-1.76%)
without NNM
10.00% (-79.42%)
40.54% (-48. 82%
83.15% (-6.40%)
8

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
6. Conclusion
Chen, L., Wang, H., Charles, Z., and Papailiopoulos, D. Draco: Byzantine-resilient distributed training via redun- dant gradients. In Proceedings of the International Con- ference on Machine Learning, pp. 902-912, 2018.
To the best of our knowledge, this the first work that theoretically investigates the tension between Byzantine ro- bustness and no-attack accuracy in distributed learning. We theoretically analyze the aggregation error of robust aggrega- tors and the convergence rate of using gradient descent with robust aggregators. The theoretical results show that making the distributed learning method robust to more Byzantine workers will degrade the worst-case performance under no attack. Our theoretical findings are further supported by the empirical results.
Chen, Y., Su, I.., and Xu, J. Distributed statistical machine learning in adversarial settings: Byzantine gradient de- scent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1255, 2017.
Damaskinos, G., Guerraoui, R., Patra, R., Taziki, M., et al. Asynchronous Byzantine machine learning (the case of SGD). In Proceedings of the International Conference Machine Learning, pp. 1155-1154, 2018.
Acknowledgements
This work is supported by National Key R&D Pro- gram of China (220000F00133000) NSFC Project (No. 123266155,,, the Key Major Project of the Pengcheng Laboratory (No.CCL002406).
Diakonikolas, and Kane, D. M. Recent advances in algo- rithmic high-dimensional robust statisties. arXiv preprin! arXiv:191 1.05911, 2019.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the International Conference on Machine Learning, pp. 999-1008, 2017.
Impact Statement
This paper mainly theoretically explores the tension be- tween Byzantine robustmess and no-attack accuracy in dis- tributed learning. There may be some potential societal consequences of our work, none of which we feel must specifically highlighted here.
Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, J. Byzantine machine learning made easy by resilient averaging of momentums. In Proceedings of the International Conference on Machine Learning, pp. 6246-6283, 2022.
References
Guerraoui, R., Rouault, S., et al. The hidden vulnerability of distributed learning in byzantium. In Proceedings of the International Conference Machine Learning, pp. 3521 3521-3530, 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 Proceedings of the International Conference Artificial Intelligence and Statistics, pp. 1232-1300. PMLR, 2023.
Haddadpour, F., Kamani, M. M.. Mahdavi, M., and Cadambe, V. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimiza- tion. Proceedings of the International Conference on Machine Learning, pp. 2545-2554, 2019.
Baruch, G., Baruch, M., and Goldberg, A little enough: Circumventing defenses for distributed learning. In Ad- vances in Neural Information Processing Systems, pp. 2019.
Bernstein, J., Zhao, J., Azizzadenesheli, K., and Anandku- mar, A. signSGD with majority vote is communication efficient and fault tolerant. In Proceedings of the Interna- tional Conference on Learning Representations, 2019.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leam- ing for image recognition. Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 770-777 2016.
Blanchard, P., Guerraoui, R., Stainer, J., et al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances Neural Information Processing Systems, pp. 119-129, 109-129,201111 2017.
Jaggi, M., Smith, V., Takác, M., Terhorst, J., Krishnan, S., Hofmann, T., and Jordan, M. I. Communication--ffficenn distributed dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 3068-3076 2014.
Bulusu, S., Khanduri, P., Kafle, S., Sharma, P., and Varsh- ney, P. K. Byzantine resilient non-convex scsg with dis- tributed batch gradient computations. IEEE Transactions on Signal and Information Processing over Networks, 7: 764-766, 2021.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji. A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and Trends@ Machine Learning, 14(1-2): 2021.

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Karimireddy, S. P., He, L.,, and Jaggi, M. Learning from history for Byzantine robust optimization. In Proceedings of the International Conference Machine Learning, pp. 5311-5319, 2021.
Byzantine attacks. In Advances in Neural Information Processing Systems, pp. 14615-14625, 2020.
Sun, S., Chen, W., Bian, J., Liu, X., and Liu, T.-Y. Slim- dp: multi-agent system for communication-effiiii distributed deep learning. In Proceedings of the 17th In- ternational Conference on Autonomous Agents and Mul- tiAgent Systems, pp. 721 2018.
Karimireddy, P., He, L., and Jaggi, M. Byzantine-robust learning on heterogeneous datasets via bucketing. In
Proceedings of the International Conference on Learning Representations, 2022.
Vardit, Y. and Zhang, C. H. The multivariate 11 11-median and associated data depth. Proceedings of the National Academy of Sciences of the United States of America, 97 (4): (4):1423-1426, 2000.
Konstantinidis, K. and Ramamoorthy, A. Byzshield: An efficient and robust system for distributed training. Pro- ceedings of Machine Learning and Systems, 3:812-828, 2021.
Wu, Y. and He, K. Group normalization. In Proceedings of the European Conference on Computer Vision, pp. 3-19, 2018.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Lamport, L., Shostak, R., and Pease, M. The byzantine generals problem. ACM Transactions Programming Languages and Systems, 4(3):382-401, 1982.
Wu, Z., Ling, Q.. Chen, T., and Giannakis, G. B. Federated variance-reducee stochastic gradient descent with robust- ness to Byzantine attacks. IEEE Transactions on Signal Processing, 68:4583-4535 4596, 2020.
Lee, D., Lin, Q., Ma, T., and Yang. T. Distributed stochas- tic variance reduced gradient methods by sampling extra data with replacement. Journal of Machine Learning Research, 18(1):4404 4446, 2017.
Xie, C., Koyejo, S., and Gupta. Zeno: Distributed stochas- tic gradient descent with suspicion based fault-tolerance. In Proceedings of the International Conference on Mu- chine Learning, pp. 6893-6901, 2019.
Lian, X., Zhang, C., Zhang. H., Hsich, C.-J., Zhang, W., and Liu, Can decentralized algorithms outperform central- ized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Infor- mation Processing Systems, pp. 5330-5340, 2017.
Xie, C., Koyejo, O., and Gupta, I. Fall of empires: Breaking crrantine-tolerann sgd by inner product manipulation. In Proceedings of the Conference on Uncertainty in Artifi- cial Intelligence, pp. 261-270, 2020a.
Loshchilov, I. and Hutter, F. Sgdr: Stochastic gradient descent with warm restarts. In Proceedings of the Inter- national Conference on Learning Representations, 2017.
Xie, C., Koyejo, S., and Gupta, I. Zeno++: Robust fully asynchronous SGD. In Proceedings of the International Conference on Machine Learning, pp. 10495-10503, 2020b.
Ma, C., Smith, V., Jaggi, M., Jordan, M., Richtárik, P., and Takác, M. Adding vs. averaging in distributed primal- dual optimization. In Proceedings of the International Conference on Machine Learning, pp. 1973-1982, 2015.
Yang, T. Trading computation for communication: Dis- tributed stochastic dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 629-637, 2013.
McMahan, B. and Ramage, D. Federated learning: Collabo- rative machine learning without centralized training data. Google Research Blog, 3, 2017.
Yang, Y.-R and Li, W.-J BASGD: Buffered asynchronous SGD for Byzantine learning. In Proceedings of the In- ternational Conference on Muchine Learning, pp. 11751- 11761, 2021.
Rajput, S., Wang, H., Charles, Z., and Papailiopoulos, D. Detox: A redundancy-basse based framework for faster and more robust gradient aggregation. In Advances in Neural Information Processing Systems, pp. 10320-10330, 2019.
Yang, Y.R. and Li, W.-J Buffered asynchronous SGD for Byzantine learning. Journal of Machine Learning Research, 24(204): 162 2023.
Shamir, O., Srebro, N., and Zhang, T. Communication- efficient distributed optimization using an approximate newton-type method. In Proceedings of the International Conference on Machine Leurning, pp. 1000-1008, 2014.
Yang, Y.R.,, Shi, C.-W., and Li, W.J. On the effect of batch size in byzantine- distributed learning. In Proceedings of the International Conference on Learning Representations, 2024.
Sohn, J.-y., Han, D.-J., Choi, B., and Moon, Election cod- ing for distributed learning: Protecting signsgd against
10

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Yang, Z.,, Gang, A., and Bajwa, W. U. Adversary-resilient distributed and decentralized statistical inference and ma- chine learning: An overview of recent advances under the Byzantine threat model. JEEE Signal Processing Magazine, 37(3):146-15 2020.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. Byzantine- robust distributed learning: Towards optimal statistical rates. In Proceedings of the International Conference on Machine Learning, pp. 5650-5659, 2018.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. Defending against saddle point attack in Byzantine robbut distributed learning. In Proceedings of the International Conference on Machine Learning, pp. 7074-7084, 2019.
Yu, H., Jin, R., and Yang, S. On the linear speedup analy- sis of communication efficient momentum SGD for dis- tributed non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 7184- 7193, 2019a.
Yu, H., Yang. S., and Zhu, S. Parallel restarted SGD with faster convergence and less communication: Demystify- ing why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelli- gence, pp. 6693-5700, 2019b.
Zhao, S.-Y., Xiang, R., Shi, Y.-H., Gao, P., and Li, W.-J. SCOPE: scalable composite optimization for learning on spark. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 2928-4934, 2017.
Zhao, S.-Y., Zhang, G.-D., Li, M.-W., and Li, W.-J Proxi- mal SCOPE for distributed sparse learning. In Advances in Neural Information Processing Systems, pp. 6551- 6560, 2018
Zhou, Y., Liang. Y., Yu, Y., Dai, W. and Xing, E. P. Dis- tributed proximal gradient algorithm for partially asyn- chronous computer clusters. Journal of Machine Learn- ing Research, 19(1)::33-766 764, 2018
Zinkevich, M., Weimer. M., Li, L., and Smola, A. J. Paral- lelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 2595-2603, 2010.

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
A. Proof Details
A.I. Proof of Theorem 3.1
Proof. Let (- be a (frobustb aggregator. Assume that Agg(.) is e-accurate, We consider the case where X1
X = and Xx-f+1 = ... X A >
We have
/
x
Σ
X
A,
(11)
1=1
and
1
( ( A
2
S A 1)
27
f(n f) n A2.
x;
x
(n f)
+ f
(12)
m
n
n
i=1
Let set S" (1,...,
72
f). We have
Σ x 0,
X5
S
İES!
and
Σ
x; - x3 2= 0.
S
EE
According to the definition of (J: robboussssssss, we have
Agg((...................... ... xn) xs.
||x x..11 =0,
|S
iES"
which implies that
Agg(X),...,,X,, Xx) ) = 8g = 0.
(13)
According to equations (11), (12) and (13),
f2
Agg X X ..,) x
0
A
A2
x - x||
n2
In addition, according to the definition of e-accuracy,
Agg(x....., x112 Se.
Σ
xx x1
1=1
Therefore,
1
x x|1
xx)
x
xx
x||2
1=1
i=1
Consequently, is obtained that
A.2. Proof of Theorem 3.2
Proof. Suppose that Agg(.) is an (J, -ooobust aggregator. Let set
4 = (1.. n), f].
Therefore, we have
n! 14| = ( 7 ) f!(n f)!
n 2-ff.
12

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
For any S E U and any n vectors x E Rd, have
X,,
Σ
|
x3|1²
Σ (1xx| 11
2x; X5 + ||x)|1))
IES
iES
Σ
|x: |1 2 -2|5| xS + |||||s|||
iE8
|x x
E
Σ
|x|||
1
Σ X
S
iES
iE8
1
2
Σ
|x
||
2
Σ (ES.JESKK)
X;
1.51
S
IES
iE9
Notice that |S| = n f for all S E U. Therefore,
2
Σ
||x xs|1
|xx||
Σ iJESsiij
x, .j..
(14)
n2
ES
ES
Take summation over all S E 24 for both sides of (14), it is obtained that
xx - xs|13
n
Σ |x
2
Σ
x4 x,
n f SEMl (JESiij)
SEM
NES
SEMl
EE
For any element E {l...., n. there are totally (1 (-- sets S in 22 that contain i. Moreover, for any two different elements i,j (1.-.., n), there totally (,n-2, sets S in 2/ that contain both and j. Therefore,
xx x3|12
SEu
NES
n
1
11 - 1
|x1 11
2
n1 - 2 n-1
X
n f
12 f
11 f 11 f - 2
1=1
1=1 j=+t
(n- f 1) - 1)!
2(n 2)
n-1
1x112
Σ X4 XX
(n f) - 1)!
(n f)fl(n - f 2)
i=1 1=/11
(n 1 - -1)(n -1)!
2(n - 2) - 1)
| 2
X
(n- f)if!
1=1
n2 f
n
|x 2
Σ
n-1 Σ x X.
= fl(n f)!
1
n
1=1
i=1
j=it1
In (14), S= (1,...,.) .............. and we have
22
n-1
Σ |x x1|2 =
n
X
2
Σ
Σ X
(15)
i=1 j=i+1
where x = - x,. Therefore,
Σ Seu
Σ
||x: x3112 = fl(n f)!
n- -
Σ
|x; - 2
- 1 1=1
13

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Since [2]
and |S| n for all E U, it is obtained that
71n-1) f7
1
(n - f - 1)m
x xs|2
- x112
4
(n f) 1)
SEM
iES
n² nf
1
Σ
n
x2 1xx11p))
n² nf + f
n
Therefore,
x xs|1?
1
Σ
x x||
(16)
U
S
72
Meanwhile, by using Cauchy's inequality and the fact that & = [t]
11
E EsEu Xs, we have
A Agg(x),..... xn) 1
x||==
(eggxx)...,x,).. ,.,,,,,,,,,,
Xn.) -Xs]
[21]
SEU
$
Agg(x)..... .,)) xxsl2
4
SEu
According to the definition of (J: k:)rruusssssss
Agg(x....... ..)) -n)) - xs S n.
Σ
||, xs|12
S
iES
Therefore,
,,., x112 S x [u
Σ iEs
|x; xs11²)
|S|
Sell
Using inequality (16), we finally obtained that
n
Aggg(x1...... x,) - x12 S K
Σ
||x; x|{
(17)
i=1
which implies that Agg(.) is k-accurate.
A.3. Analysis for Coordinate-wise Trimmed Mean
Proof. We first proof the theorem for the case where the dimension Let Fi...., F. be any n real numbers. Without loss of generality, we assume that xj I æ2 S ... S In since the order does not affect the trimmed mean of the a values, and the trimmed mean can be written
TM [M/ [n.) [m)== = n1 2f
i=f+1
Therefore,
TM IM// (T1..... Rn) -
n-f f
1
32
n 2f
11.
i=f+1
i=1
1
Σ
11
2f
#=/+1
i= f+1
14

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
2
1
n-
F
Fi
11
11
2
π
/=/+1
ビ=
f+1
n-/
1
nー/
Σ
Σ
Y1
11 2
34
24
11
11 2/
J i= s+1
i=f+1
i=f+1
Let sets I_ = 11.2...,,,,.--- (f
n ,,...,n-- A and I = {n- - f + 1,1, +,....,,7 n3. We define
31
Fit
SEl_
1
Σ
1
F1.
24
Fi+
[ol
2
iEIn
i=f+1
and
n
Σ
31+ = [1
I2 =
SEL
i=n- 1+1
Therefore, we have
I (31, 111)+ + f (ilo- - -814).
{
TM//n(F1......
(18)
n
n1
Meanwhile,
1
(z) .)² + 1 Σ (ar 8)2
+ 1 Σ
[24-
3)
(z; - =)
1
n
1=1
EE7_
iElo
iE1+
1
(1x; T1_ ) (01 - =]
17
leT
+
[(x - E1,) + (3r - =
71
:EL.
+
Σ
[( - 3τ ) + (or, - 8)}?
(19)
71
:E/+
Notice that
1
[1x; 31 ) (ūs -))²
11
VEI_
(s=; )2 + (i1 - 3)2 + 2(x 51 (or - -]]]
n
VEl_
(xt )1 + Σ
2²
(01_ - =))² +
1
Σ
12(x; F1 (5 - =]]
n2 iE!_
vel_
IE1
f
1 Σ
2( 7)
(x; - )2
+ - [ - -))2 +
Σ
(x; - FT
f
n
n
n
ier
8E1
Since Σier (x; - )1_) = 0, we have
1
Σ
[(
(51_ + - =))² f
-31)
_ + (31 -3)7
(20)
71
1
1E
15

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
where o7. = -iEr (c, 31 ) Similarly,
[x:; T1o) + (3r - -]]]² n n-2f
18% + (31 =)²},
(21)
1
[0 - =1_ ) (31, - -3)? f
1s + (31, - 3)²1.
(22)
71 iE1+
n
where 5%/ = 2- Ever, (2g -11o)² 2 and 67, = Eiel (ot
31 )a Substituting (20), (21) and (22) into (19), we have
n
[
n 2ʃ
Σ
(1 - x)²²
=
$1_
+
810 + 71
814
12
n
n
f
2f
+ f (31, - 3)3.
+
(31
2)²
(310
=)2
n
n
Notice that 3 f-,1- + 2-2L21 21o
L and we have
f
2f
f
(2) x)²
3T_
+
810
2
2 $1
n
7
n
2f
f
+
(ir_ 11,) + (5r_ 31,) )
n
2ʃ
[
S (F1o B14)
2
+
(511 11_)
n
n
n
f.
f
n - 2f
+
[81, -i_)) +
[1,+ 11m))
71
n
For simplicity, we let
f
2
f
52
In
- 2
n
n
n1
A
31g
2
0,
and
A
31,
31 0.
Therefore, we have
1
2
f (-A A - A.)
[
8) 2
52
(-A-)
71
n
n
n
n 2ʃ
[ [[(A _ (-1+) 2
f f (A_ +
n 2f (A+) 2
+ +++++
n
n
By expanding the square terms, it obtained that
11 f
+ n n-2f 2f (
S A
f A
+ n- f 1
A+
A.
+
+ 32
n1
n
n
n
n
f(n f
f2 2f)
2f)
f3
f(n
2f)
f(n - f)2
+
+ 3
(A_)² +
(A+)²
3
3
13
n2
3
2f
f) 2 (n 2f)
2f²(n f) n
+
(A. (A- ++)
3
3
16

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
f(n - f) (A_)²
f(n f)
(A,))+ 2 n²
(A-+))+
122
n²
n ---/ 1 [ A
2
( -) + 82
+
Meanwhile, according to (18) and the definition of A_ and A+, we have
f A TM [M//
A
n
n
Therefore,
( x)² n
25 (A A +
(MM.)(..............
f
Notice that 52 P A_ 2 0 and
A 2 0, and we finally obtain that
(xs x)² 2 [TM (21, (.1,....,, .n) =//
or, cquivalently,
f
1 n
[M f/n /// (.1, -.0,,,.......................... Fnn) 57]
ax 5)
(23)
n f
i=1
Moreover, the equality in (23) holds if and only if 5² 0 and A A+ O, which is equivalent to that s7_ =s and A 4 0.
5/-
We have finished the proof for the 1-dimension case. For the general d-dimension case,
..)) - -x12 = [TM (X1,, xn)
(T.,,.))).....xx) x},} ?
(TMM) -xx);) 2
2
[x:]n((
n2 > [xils
1
j=1
Oby (23)
d
n
(xxi) -(x1,)²
11 f n
1
x4 x13
11
i=1
1
||2 x
n1
Namely,
[M/ xn)
x||
x x
n f
n7
A.4, Analysis for Coordinate-wise Median
Theorem A.1. Coordinate-wise median is acccurae where C, R-
Proof. Notice that coordinate- wise median can be deemed as applying Theorem 3.6.
TMM. The desired result can be directly obtained by
17

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
A.5. Analysis for Geometric Median
Theorem A.2. The geometric median is 1-accurate.
Proof. We use XaM denote the geometric median of X1...., According the definition, we have the following inequality:
a
XGM
X
x x.|l-
(24)
According to the Triangle Inequality,
2
1
XGM x|/= =
XGM
XGM
Xi)
XGM
x:I
(25)
i=1
i=
1=1
Combining (24) and (25), we have
2
2
1
n
1
n
|GGM
x12²5
x:1l
x
x;||
(26)
n
n2a
According to Cauchy- Schhar- inequality, we have
2
Σ
12 i=
Σ X
-
x;l2
>
Σ
1 ||x xi1l
Namely,
Σ
xill
S n Σ
x x; 1.
(27)
Combining (26) and (27), we finally obtain that
n
XxGM
x||
S n
n
x x; 1
=1.
X
It implies that geometric median is 1-accurate.
A.6. Proof of Theorem 4.5
Proof. We first consider the 1-dimension case where
nG
Fi(w)= =...
= =F((w)
2
2 f(n ff)
and
nG
nG
Fs+1(w) = =... = Fn(w)= =
u
w
2/T(m f)
vf(n -
Therefore,
F((w)= = f nG
w + n - f
nG
nG
F(w)= = Σ
w²
w
2 f(n - f)
f(n
vf(n 1
1=1
nG
Vn J V]
3
Gw
ff)
nG
11 n
(n A)
2 2vI(n- -f)
n
2n
18

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
which indicates that F(w) satisfies Assumptions 4.1 and 4.2 and has the unique global mimimum point
10"
Moreover,
Σ (w(w)) ('w]]
f x
Vn in-fe
-
2
n R-f x
nG
vn - vf
Vf
n
(Vf(n-
G + f 0²
71
= G²
Therefore, F(w) satisfies Assumptions 4.3. Furthermore, F(w) also satisfies Assumption 4.4 with μ (s(n-f) since F(w) is quadratic function. Let the set S ( + ......n and
nG
(w) = |S|
(w)
VI( (w (W 1).
SES
Since Agg(.) is (f, robustt and (w)) = ... F/ (w), we have
Aggg(F (F,(F())...," (w)) Fs(ww]
(F) F3((w)) 0.
|S|
ES
Therefore, have
nG
Agg(F((w))...., = Vs(n- (w-1).
Let (w, be the sequence obtained by ByzGD (Algorithm with initial point wy E F and learning rate ne = > 0. We have
nGn Wr+1 W. - 77. Agg (w.)) (wx)) We vs(n (w. 1).
Therefore,
nGn
Wh+1
(w: 1).
Vf(n f)
Then we consider the following three cases.
f(n- FV
Case (i). When 0 <ク< <
we have
nGn Vi(=1)
E (-1,1).
Thus, We
nGn Vs(n-i)
(wo 11) converges Consequently, wi converges Since F(w) is L-smooth.
[w:)] converges to [F((1)2=
nG
- 1
1 n- G2. Thus, for any Ci < aLy G2 and any positive
Vi(n-T)
K, there exists Ti > K such that
T (w:)) Ci.
Σ
T
Similarly, we have that [F(w)) ) F(w")] converges to
nG
(1- n 1-2 1-m-1)-
(1---1)²
FaG
1 G
((1-=F(w)) 2/J(n-1 -
n
2n [n-
n - 2p
19

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
by noticing that μ V)(n-f)
nG Thus, for any C1 < , G2 and any positive K, there exists T2 K such that
F(WT,)= - F(w") > Ci
24
Let T = max (T1, T2] and we obtain the desired result.
Case (ii). When 17 ((-f) have 1 nGy 1. Thus, wt+1 =(w, 1). For any positive K,
Vf(n-f)
have that w|]++ - (WIx]+2- - 1). which is equivalent to that w w|]++ + W [ = 2. Let
arg max Wt:
EE [E[
We have that un max w[K +2) 2 1. Since F(w) is monotonically increasing when w 2 1, we have that
F(WT,) F(w") > F()) - F(w")(w)))))))))))> f
G²
C1
2p
2p
Let H 1 Ti 21=0 (w:))
If (F C1, we directly obtain the desired result by letting T = Ti If C1 let
+2 (n ()(TC H)
T= +2
+1
2fG
where [.] is the floor function. Therefore,
wT 1 = (wT, 1) x (-1)²(
2/a²
WT, 1.
Namely, wr = wr, Therefore,
F(WT) - F(w") F(WT,) F(w") > C1
24
Moreover, using the equation that w/ + Wr+1 = 2 and the inequality that x² + y² 2 (x+x)²
F (www)) + [F (F((++1))
n1 f 1
nG
n n f
nG
+
Wi+1
Vi(n= (1n--f f)
v
[[ -J
n²G²
n1
2
n f-
27
T(n -)
11
+
Wr+1
n
n²G²
2(n
2
W. W1+1
2f(n - f)
n
11 f
1
f(n f)
n
2f G².
Thus,
T-1 1
1 T
T-1
Σ
F (wx))²
Σ
F
(w(ww))²
+
Σ
F (w,))²
T
T
1=0
t=
Ti
1
T-
2
H
G2
T
n
20

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
Til
(n f)(C) f- -TiH)
2
+1
G
T
T
2JG²
11
T.H T
(n- [) [)(CC--THH) -HTH)
25
+ T
G²
2fG²
TH TC1 TiH
T
T
C1.
Therefore, the positive integer T 2 Ti > K satisfies the two desired conditions.
Case (iii). When v) > both [F]] and F(w) diverge to +o0 when
2VI(=-f) nG
we have
nGn 1, 1. In this case, wy - oo. Since F(w) I-smooth, and Vi(n-f)
We can directly obtain the desired result.
In summary, the desired result be obtained in all of the three cases, and the proof for the 1-dimension case is finished.
For general d-dimension cases where E Rdd we can simply choose Fi(w): = (wpr) for all i {1, .,..,, n. where Wiy is the first coordinate of vector w. Thus, we have that [[](( (F[(w))) Therefore, we can use the result for the 1-dimension case above, and obtain the desired result for general d-dimension cases.
A.7. Proof of Theorem 4.6
Proof. Let G. Agg (W:((.)) (w.)).)). Since F(w) smoohhhh
F(W++1) = =F(w; G.)
<F(w:) Th VF (w.) G L(m))
-|,
The N IVF w:) || + Th || VF(w.)) 1h(1 Lmx)
=F(w.)
[.
(28)
2
2
where the last equation can be quickly checked by expanding the squares. Moreover, using Assumption 4.3 and that Agg(.) e-accurate, we have that
n [V](w)- VF(W))| < EGG
|G. VF(w)) se.
(29)
n
Since 1 T. we have that 1 - Lip: = 0. Substituting (29) into (28), we have that
F(W++1) F(w,) S T/t
VF((:))
2hd cC 1
VF(w))12
21 c
(30)
2L
Taking summation over it is obtained that
T-1 Σ IVF(W))) (L F(wT)]
+ +eG².
T
According to Assumption 4.1, we have that F(WT) > F and obtain the first desired result. Furthermore, when F(w) satisfies the PL condition, we have that
[F(())) ( - FF].
(31)
Substituting (31) into (30), have that
M1 (00+1)-F(ww)) S - (((:)) F*] + cG²
2L
which is equivalent to that
EG21
F(w:) - Ft cG²
F(We-1) - F
<
2p
L
241
21

---

On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning Recursively using the inequality, we have that
cG2 21
(1 4) T
cG2
F(WT)- F.
P(wo)- 24
Therefore, finally obtain that
F F(WT)
F $ =31- =11=1 (F(wo) - -F +
cG2 2f
22


Reviews:
[{"review_id": "vKwmliIICV", "reviewer": "Reviewer_k8Cc", "summary": "This work studies robust aggregation methods in the Byzantine setting. Specifically, let $x_i \\in \\mathbb{R}^d$ be information held by worker $i$, and suppose that the goal is to compute the mean $\\frac{1}{n}\\sum_{i=1}^n x_i$. In the Byzantine setting, an unknown subset of $f$ workers are adversarially corrupted, and thus a robust aggregator $Agg(x_1, \\dots, x_n)$ is used to approximate the mean of the uncorrupted workers' vectors, i.e., $\\frac{1}{n-f}\\sum_{i \\in S} x_i$, where $S$ denotes the unknown set of uncorrupted workers. Such aggregators aim to approximate this quantity reasonably accurately without knowing $S$ in advance.\n\nWhile prior work has developed methods for robust aggregation, this work considers the scenario where previously proposed methods are applied even though there are actually no Byzantine workers present. This serves as a sanity check measuring the \"price of robustness.\" To quantify robustness, they define an aggregator to be $(f,\\kappa)$-robust if it approximates the desired output within a factor of $\\kappa$ times the variance of the inputs, for every subset of uncorrupted workers of size at least $n-f$. To measure accuracy, they say an aggregator is $\\epsilon$-accurate if its estimate is within $\\epsilon$ times the variance of the inputs from the true mean of all $n$ workers.\n\nIn their first set of results, they derive upper and lower bounds relating the accuracy $\\epsilon$ of an estimator to its robustness parameter $\\kappa$. They show general bounds satisfying $\\frac{f}{n - f} \\leq \\epsilon \\leq \\kappa$, along with tighter, method-specific bounds for particular estimators (namely the geometric median, coordinate-wise trimmed mean, and coordinate-wise median). In all cases, they demonstrate that their bounds are relatively tight by explicitly constructing examples where these bounds are attained.\n\nThen, they turn their attention to one of the most common use cases of Byzantine aggregation, namely the aggregation of gradients. In this setting, each worker has its own local dataset and computes a gradient $\\nabla F_i(w)$, where $w$ denotes the current shared model parameters and $F_i$ represents the local loss function evaluated on worker $i$'s dataset.\n\nIn this setting, under several (relatively standard) assumptions on the loss functions, they provide lower and upper bounds for how closely $T$ steps of Byzantine gradient descent (where each step updates $w$ based on a robust aggregation of gradients computed by the workers) approximate the optimal loss. Specifically, their lower bounds hold under the assumption that the Polyak–Łojasiewicz condition is satisfied, indicating that achieving near-optimal loss through standard gradient descent would, in principle, be feasible. In their upper bound, they explicitly show that the accuracy term $\\frac{f}{n - f}$, previously derived for general Byzantine aggregators, directly affects how closely one can approach the optimal loss.\n\nEmpirically, the authors validate their theoretical results by training a ResNet-20 model on CIFAR-10 using Byzantine gradient descent with robust aggregators, specifically multi-Krum and coordinate-wise trimmed mean. They vary the maximum number of Byzantine workers ($f$) the aggregators can tolerate and the degree of heterogeneity in data distributions across workers (controlled by the Dirichlet parameter $\\alpha$). Their results demonstrate that even in the absence of actual Byzantine attacks, increasing the robustness parameter $f$ significantly reduces accuracy on the clean test set, with this effect being particularly pronounced when data distributions across workers are highly heterogeneous (small $\\alpha$). These empirical findings confirm their theoretical claim of an inherent tradeoff between robustness to Byzantine workers and accuracy under no attack.", "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 sincerely thank the reviewer for the insightful comments, the constructive suggestions, and the support of our work. We would like to respond to the raised questions point by point below.\n\n**Comment 1. Some of the results on specific aggregation methods could be deferred to the appendix.**  \nIn the current version, we present the definitions and results of several common robust aggregation methods (GM, TM, and CM) in order to be more friendly to the readers who are not very familiar with Byzantine-robust distributed learning. Meanwhile, we agree with the reviewer that part of these texts could be deferred to the appendix for better readability. We will revise it in the final version and thank the reviewer for the constructive suggestion. \n\n**Comment 2. I find the general bounds more interesting and would be interested in further theoretical analysis of these bounds in contexts of explicit heterogeneity (i.e. assume $x_i$ are sampled from some distribution, etc. etc.).**  \nFor the case where $x_i$ are independently sampled from the same distribution with a variance of $\\sigma^2$, we can take expectation on the inequality in Definition 2.2 (line 126). According to (15) on page 13 in the Appendix and using the fact that $x_i$ and $x_j$ are independent $(i\\neq j)$, we can obtain that \n$$\\mathbb{E}||Agg(x_1,\\ldots,x_n)-\\bar{x}||^2\\leq \\epsilon \\cdot \\mathbb{E}[\\frac{1}{n}\\sum_{i=1}^n ||x_i-\\bar{x}||^2]=\\epsilon\\cdot \\frac{n-1}{n}\\sigma^2. $$\nMeanwhile, we will also investigate more cases in future work and sincerely thank the reviewer for the suggestion.\n\n**Comment 3. What are some future directions for investigating this problem under more concrete assumptions on the hetrogeneity of the data?**  \nSome potential future directions are presented below:\n+ As pointed out by reviewer RMMi, investigating the tension between Byzantine robustness and no-attack accuracy under the more general $(G, B)$-dissimilarity assumption is a direction of future extension.\n+ Additionally, reviewer RMMi also provides a potential future direction of studying the tension when the actual number of Byzantine workers is larger than $0$ but smaller than $f$.\n+ The analysis of this work is for general cases, and the bounds are related to the case with an extreme large skeness. In some real-world applications, the distribution of training instances and gradients is usually not that extreme. Thus, we find it will be a potential future direction to investigate the data distribution in real-world applications and analyze the tension for some specific distributions.\n\n**Comment 4. It feels like in those situations, one might hope for a \"best of both worlds\" by coming up with some sort of scheme to detect if one is in the byzantine setting or not. It also feels like there might be some more interesting theoretical bounds one could come up with under more structural assumptions on the data.**  \nWe agree with the reviewer's insightful comments, which inspire us to think more about future directions. In this paper, we mainly investigate the tension and prove the tightness of our results for general cases. In real-world applications, as the reviewer pointed out, we could utilize the observation of some true data. Under the assumption that the non-Byzantine data is close to the observed data, we may obtain a better result about the tension between Byzantine robustness and no-attack accuracy. Since we mainly focus on the general cases, it is beyond the scope of this paper. We will explore this in future work and sincerely thank the reviewer for the constructive comments.", "claims_and_evidence": "Yes. They prove their claims and their experiments make sense.", "methods_and_evaluation_criteria": "Yes, especially given that their contributions are primarily theoretical. I view the experiments a basic sanity check to illustrate the effect of their theorems in practice.", "theoretical_claims": "I scanned through the proofs and they appear correct. They also all make very intuitive sense and so i do not doubt their validity.", "experimental_designs_or_analyses": "The experiment design made complete sense to me. It didn't require significant checking due to its very simple design (i.e. simply measuring the effectiveness of byazantine algorithms with varying levels of tolerance and heterogeneity).", "relation_to_broader_scientific_literature": "They seem well related. This does appear to be the first work that sanity checks existing methods on uncorrupted data, and this paper does well in positioning itself as such.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths: i think the theory is simple, easy to follow, and also quite illustrative. I generally like the theme of understanding tension between accuracy and robustness (which appears in many different fields of machine learning!) \n\nWeaknesses: Some of the results on specific aggregation methods seem like they could be differed to the appendix (given that they are quite simple). I find the general bounds more interesting and would be interested in further theoretical analysis of these bounds in contexts of explicit heterogeneity (i.e. assume $x_i$ are sampled from some distirbution, etc. etc.).", "other_comments_or_suggestions": "None.", "questions_for_authors": "What are some future directions for investigating this problem under more concrete assumptions on the hetrogeneity of the data? It feels like in those situations, one might hope for a \"best of both worlds\" by coming up with some sort of scheme to detect if one is in the byzantine setting or not. It also feels like there might be some more interesting theoretical bounds one could come up with under more structural assumptions on the data.", "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": "TxiIwgCMU1", "reviewer": "Reviewer_rsEj", "summary": "This paper examines distributed learning in a setting where the server implements a robust aggregation rule. Motivated by the Byzantine-robust learning framework, it evaluates the performance of distributed gradient descent (GD) methods designed to cope with Byzantine workers, even when none are present. The authors extend the definition of $(\\delta,\\kappa)$-robustness to scenarios without Byzantine workers by introducing the notion of $\\epsilon$-accuracy, derive accuracy coefficients for several robust aggregation rules, establish a convergence result and a lower bound, and support their findings with numerical experiments on CIFAR-10 that illustrate the impact of varying the \"assumed\" number of Byzantine workers.", "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 sincerely thank the reviewer for the valuable time and the detailed review. We will respond to the raised concerns point by point as follows:\n\n**Concern 1. The proof of Theorem 4.6 is of limited novelty as it can be directly deduced from [1].**  \nWe thank the reviewer for letting us know their concern and would like to clarify the meaning of Theorem 4.6 below.\n\n+ We would like to first politely point out that the notation $f$ in [1] is the **known** Byzantine worker number, while $f$ in this work is the **assumed** Byzantine worker number. To the best of our knowledge, this is the first convergence result for ByzGD with any $(f,\\kappa)$-robust aggregator when there are actually no Byzantine workers. \n+ Meanwhile, since this work mainly focuses on the tension between Byzantine robustness and no-attack accuracy, the main contribution of Section 4 lies in the lower bound (i.e., Theorem 4.5). The main purpose of presenting Theorem 4.6 here is to show the tightness of Theorem 4.5.  \n\n**Concern 2. The analysis is done for ByzGD and mentions ByzSGD as a variant. However, considering just SGD without momentum won't work in my opinion.**  \nWe thank the reviewer for the insightful comment. As discussed in Section 4 (please refer to the right column of line 326), using momentum can reduce the variance (which the aggregation error is proportional to) in ByzSGD. Thus, ByzSGD with momentum has a better convergence rate and more Byzantine robustness than ByzSGD. However, compared to ByzGD, ByzSGD with momentum does not improve the theoretical learning rate w.r.t. the iteration number $T$.\n\nFor example, we consider ByzGD with momentum as a special case of ByzSGD with momentum (with variance $\\sigma^2=0$). For the same case as in line 314 to line 320 where $$F_1(w)=\\ldots=F_f(w)=\\frac{nG}{2\\sqrt{f(n-f)}}w^2$$ and $$F_{f+1}(w)=\\ldots=F_n(w)=\\frac{nG}{2\\sqrt{f(n-f)}}(w^2-2w),$$ the aggregated result will be totally controlled by worker $\\{f+1,\\ldots,n\\}$, and from the server's perspective, it is equivalent to optimize the objective $\\tilde{F}(w)=\\frac{nG}{2\\sqrt{f(n-f)}}(w^2-2w)$, whatever the optimizer (e.g. ByzGD with momentum) is used. Thus, ByzSGD with momentum cannot theoretically improve over ByzGD in this case.\n\nAdditionally, we failed to find reference [2] in the review although the reviewer mentioned it. We politely guess that the reference might be [B], which is presented below. Please correct us if the guess is wrong.\n\n[B] Karimireddy, S. P., He, L., and Jaggi, M. Learning from history for Byzantine robust optimization. In Proceedings of the International Conference on Machine Learning, pp. 5311–5319, 2021.\n\n\n**Concern 3. In the proof of Theorem 4.6, the term in the upper bound related to heterogeneity (for both non-convex and PL functions) is proportional to $\\frac{f}{n-f}$, whereas according to the proof (in Appendix A.6) it should be instead proportional to $\\epsilon$ (or $\\kappa$) -- the accuracy of the actual aggregator used and not the optimal accuracy.**  \n\nWe sincerely thank the reviewer for pointing out the typo, and we will fix this typo in the final version. \n\nMeanwhile, we would clarify that the novelty and the contribution of this paper are almost not affected by the revision. Specifically, as mentioned in our response to Concern 1, the main contributions of this paper are the lower bounds. Please note that $\\epsilon\\geq\\frac{f}{n-f}$ (Theorem 3.1) and that $TM_{f/n}$ is both $(f,\\kappa)$-robust and $\\epsilon$-accurate with $\\epsilon=\\frac{f}{n-f}$. It shows the tightness of the lower bound in Theorem 4.5. \n\n**Additional Clarification**  \nFinally, we would like to restate the main theoretical contributions of this work briefly. In this paper, we provide lower bounds for the aggregation error (Section 3) and convergence rate of ByzGD (Section 4) for $(f,\\kappa)$-robust aggregators. Moreover, we show the tightness of the lower bounds. \n\nWe sincerely thank the reviewer again for the insightful review and hope that our response can address the reviewer's concerns. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work in light of our response.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the correctness of the proofs for the upper and lower bounds (Theorems 4.5 and 4.6) .", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The proof of Theorem 4.6 closely follows the proof of Theorem 1 in [1], with Definition 2.2 replacing Definition 2.1 (which is expected, given that the definitions coincide when $f=0$, as the authors mention). Therefore, the analysis is of limited novelty as it can be directly deduced from [1].\n\n\n[1] Allouah, Farhadkhani, Guerraoui, Gupta, Pinot, Stephan. \"Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity\", AISTATS, 2023.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- The experimental setup is sound and detailed.\n- The analysis is done for ByzGD, where local gradients are computed exactly. While the authors mention ByzSGD as a variant, it is in fact much more common and brings up additional challenges: even in homogeneous scenarios (when $G=0$), simply applying a robust aggregation rule isn’t sufficient—even when Byzantine workers are absent—as seen in cases with skewed noise distributions (e.g., Counterexample 3 and others in [2]). They suggest that incorporating momentum or a similar strategy that leverages historical gradient data is necessary for true Byzantine-robustness, yet no analysis for momentum is provided (considering just SGD without momentum won't work in my opinion).", "other_comments_or_suggestions": "In the proof of Theorem 4.6, the term in the upper bound related to heterogeneity (for both non-convex and PL functions) is proportional to $\\frac{f}{n-f}$, whereas according to the proof (in Appendix A.6) it should be instead proportional to $\\epsilon$ (or $\\kappa$) -- the accuracy of the actual aggregator used and not the optimal accuracy.", "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": "zzijPzXsOE", "reviewer": "Reviewer_RMMi", "summary": "The paper analysis the learning error in distributed learning induced by robust aggregation schemes in the case when the actual number of Byzantine workers is 0, while the system is designed to handle a non-zero number of Byzantine workers $f$. The paper makes important contributions to the field of robustness in distributed learning by re-analyzing the errors of SOTA robust aggregation in the above-mentioned setting (i.e., no actual Bzyantine workers but non-zero $f$). The obtained bounds are better than those that assume presence of Byzantine workers, especially when $f$ approaches the limit $\\frac{n}{2}$. The presented analysis is useful for studying the impact of Byzantine-robustness in ideal scenarios when the actual number of Byzantine workers (in most learning rounds) are much smaller than the maximum possible number of Byzantine workers (in any given learning round). The paper can have long lasting implications.", "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 sincerely thank the reviewer for their valuable time, constructive suggestions, and support of our work. We would like to respond point by point below.\n\n**Comment 1. Impact on learning error under the more general heterogeneous setting of (G, B)-dissimilarity is missing.**\n\nWe agree with the reviewer that analyzing the tension under the more general setting of $(G, B)$-dissimilarity can help improve the theoretical contribution. Meanwhile, we politely think that adding the theory under $(G, B)$-dissimilarity requires substantial improvement, and the current version already makes an important contribution, as the reviewer mentioned. We will study the learning error under more general settings in future work and sincerely thank the reviewer again for the constructive suggestion.\n\n**Comment 2. Suggestions: (a) Utility of the obtained results for studying the algorithmic stability (thereby, generalization power) of ByzGD; (b) Interpolation between the two extreme cases: i) actual number of Byzantine worker is 0 and ii) actual number of Byzantine workers is $f$.**\n\nWe greatly thank the reviewer for the constructive suggestions and will study the two problems in future work. \n\n**Comment 3. Did you mean to present Theorem 4.6 for $\\epsilon$-accurate aggregation rule?**\n\nWe sincerely thank the reviewer for pointing out the typo. Theorem 4.6 for $\\epsilon$-accurate (instead of $(f,\\kappa)$-robust) aggregation rule. Please refer to Appendix A.6 for the correct result. We will fix this typo in the maintext in the final version. \n\nMeanwhile, we would clarify that the novelty and the contribution of this paper will be almost not affected by the revision. Specifically, as mentioned in our response to Concern 1, the main contributions of this paper are the lower bounds. Please note that $\\epsilon\\geq\\frac{f}{n-f}$ (Theorem 3.1) and that $TM_{f/n}$ is both $(f,\\kappa)$-robust and $\\epsilon$-accurate with $\\epsilon=\\frac{f}{n-f}$. It shows the tightness of the lower bound in Theorem 4.5. \n\n**Comment 4. A few typos ...**  \nWe greatly thank the reviewer for pointing out the typos. We promise to proofread the script carefully and fix the typos in the final version.\n\nWe sincerely thank the reviewer again for the great support of our work, and we are always willing to answer any further questions.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I (quickly) checked the proofs of Theorems 3.1, 3.2 and 3.6. I did not find any issues.", "experimental_designs_or_analyses": "While I did not reproduce the experimental results, they appear sound/valid.", "relation_to_broader_scientific_literature": "The paper makes important contributions to an important field of Byzantine-robustness in distributed learning.", "essential_references_not_discussed": "Not that I could think of.", "other_strengths_and_weaknesses": "Strengths:\n1. Good comprehensible proofs with proper explanation and motivation between steps.\n2. The proof techniques can be applied to future research in this field.\n\nWeaknesses:\n1. Impact on learning error under the more general heterogeneous setting of (G, B)-dissimilarity is missing.", "other_comments_or_suggestions": "Some suggestions for future extensions:\n1. Utility of the obtained results for studying the algorithmic stability (thereby, generalization power) of ByzGD.\n2. Interpolation between the two extreme cases: i) actual number of Byzantine worker is 0 and ii) actual number of Byzantine workers is $f$.\n3. Did you mean to present Theorem 4.6 for $\\epsilon-$accurate aggregation rule? Lines 328 - 329 after the theorem mentions $\\epsilon G^2$ and $\\frac{\\epsilon G^2}{2 \\mu}$ terms.\n\nA few typos:\n1. Line 110: For 'an' $(f, \\kappa)-$robust ...", "questions_for_authors": "See my suggestions and weaknesses above.", "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": "VPSnHKMlwg", "reviewer": "Reviewer_x4mZ", "summary": "This paper explores the trade-off between Byzantine robustness and standard accuracy in distributed learning. It provides a theoretical analysis of the error of robust aggregation methods when there are no Byzantine workers.  In doing so, it establishes lower bounds on the deviation from the average of the datapoints as well as on the convergence rate of Byzantine robust gradient descent (ByzGD) in the absence of Byzantine workers. The authors present theoretical results demonstrating that the worst-case aggregation error (with respect to the average) increases as the number of expected Byzantine workers increases, leading to a potential degradation in accuracy. Empirical experiments are provided to support the theoretical findings.", "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 sincerely thank the reviewer for their valuable time, insightful comments, and support of our work. We would like to answer the raised questions point by point as follows:\n\n**Q1.  I am unsure that the worst-case analysis is the best way to capture the accuracy vs robustness trade-off of Byzantine-robust methods. A more informative approach would be to analyze statistical bounds under assumed data distributions.**  \n\nWe agree with the reviewer that a statistical bound would be informative and provide a simple way to obtain a statistical bound based on the definition of $\\epsilon$-accuracy below.\n\nWhen $x_1,\\ldots,x_n$ are sampled from a probability distribution, we can take expectation on both sides of the inequality in Definition 2.2 ($\\epsilon$-accuracy) and obtain that \n$$\\mathbb{E}||Agg(x_1,\\ldots,x_n)-\\bar{x}||^2\n\\leq \\epsilon \\cdot \\mathbb{E}[\\frac{1}{n}\\sum_{i=1}^n ||x_i-\\bar{x}||^2], $$\nwhere $\\mathbb{E}[\\frac{1}{n}\\sum_{i=1}^n ||x_i-\\bar{x}||^2]$ can be viewed as a measurement of the diversity. Specifically, when $x_1,\\ldots,x_n$ are independently sampled from the same probability distribution with variance $\\sigma^2$, we have \n$$\\mathbb{E}||Agg(x_1,\\ldots,x_n)-\\bar{x}||^2\n\\leq \\epsilon\\cdot \\frac{n-1}{n}\\sigma^2. $$\n\nMeanwhile, we would like to point out that there are some other measurements of diversity such as $\\max_{i\\neq j}\\mathbb{E}||x_i-x_j||^2$ in existing works [2].  It still requires much more effort to study what statistics can be used to better analyze the Byzantine robustness, which we will leave for future work.\n\n**Q2. Clarify the novelty of the proof techniques and how they differ from prior work.**  \n**Q2.(a). the derivation of the lower and upper bounds on aggregation error appears to closely follow existing proofs in the literature, especially Section 8 in [1].**  \nWe would like to point out politely that we only follow the notations (e.g., the notations of $f$ and $n$) in [1]. Although the format of our results may be similar to those in [1], the proof of bounds for aggregation error in this work is substantially different since we consider a different scenario without Byzantine workers.\n\n**Q2.(b).Could the author explain what key insight we can get from the Theorem besides that we have a lower bound in ($\\frac{f}{n} G^2$), which is already what one has when considering the presence of Byzantine workers?**  \nWe would like to politely point out that when there are $f$ Byzantine workers, the lower bound should be $\\frac{f}{n-2f}G^2$ (please refer to Table 1 in [1]), which can be infinitely large when $f\\rightarrow(\\frac{n}{2})_{-}$. \n\nPrevious work [2] considers a special case where $\\delta=\\frac{f}{n}\\leq\\delta_{\\max}<\\frac{1}{2}$ and obtains a lower bound of the order $O(\\delta)=O(\\frac{f}{n})$. However, it cannot be extended to general cases of $\\delta<\\frac{1}{2}$ because $$\\frac{f}{n-2f}=\\frac{f}{n}\\times\\frac{n}{n-2f}=\\frac{f}{n}\\times\\frac{1}{1-2\\delta}\\leq\\frac{1}{1-2\\delta_{\\max}}\\frac{f}{n}.$$ When $\\delta_{\\max}\\rightarrow\\frac{1}{2}$, the term $\\frac{1}{1-2\\delta_{\\max}}$ will diverge to $+\\infty$ and cannot be viewed as a constant any more.\n\nIn summary, the lower bound $\\frac{f}{n}G^2$ in this work will approach $\\frac{1}{2}G^2$ when $f\\rightarrow\\frac{n}{2}$ (or equivalently, $\\delta\\rightarrow\\frac{1}{2}$). On the contrary, the lower bounds in existing works considering the presence of Byzantine workers diverge to $+\\infty$ when $f\\rightarrow\\frac{n}{2}$. \n\n**Q3. I would suggest including loss curves in the empirical evaluation.**  \nWe sincerely thank the reviewer for the constructive suggestion and will add the loss curves in the final version. Since we are not allowed to attach figures here, we present the test accuracy during the training process of using Multi-Krum when the hyper-parameter of Dirichlet distribution $\\alpha=0.1$ in the following table. The added empirical results further support the conclusion of our work. \n\n|Epoch|19|39|59|79|99|119|139|159(final)|\n|-|-|-|-|-|-|-|-|-|\n|$f=0$|77.27%|84.70%|84.46%|86.90%|87.81%|88.82%|89.17%|89.42%|\n|$f=1$|55.04%|78.78%|83.64%|84.55%|86.36%|87.27%|87.77%|88.05%|\n|$f=3$|45.24%|72.90%|78.00%|81.11%|82.60%|82.19%|82.98%|83.50%|\n|$f=5$|30.41%|37.60%|52.83%|63.48%|69.01%|69.55%|69.68%|69.86%|\n|$f=7$|18.68%|25.55%|27.64%|30.88%|33.98%|38.72%|40.05%|40.31%|\n\n**Q4. They do not seem to explain very clearly the behavior of state-of-the-art methods like NNM or Bucketing.**  \nTo answer the question, we provide another perspective of viewing NNM and bucketing below. An aggregator combined with NNM (or bucketing) can be considered as a new aggregator that can resist fewer Byzantine workers but have less aggregation error. Therefore, when using NNM or bucketing, we actually use the prior knowledge of the Byzantine worker number to make a better trade-off between robustness and accuracy.\n\n----\nWe hope that our response can address the reviewer's concerns, and we greatly thank the reviewer again for the support of our work.", "claims_and_evidence": "The paper claims that making an aggregator more robust to Byzantine workers leads to an inevitable degradation in standard accuracy when there are no Byzantine failures. To support this claim, the paper studies the notion of **worst-case accuracy** of a robust aggregator $\\textbf{Agg}$, defined as \n\n$$ \\epsilon := \\sup_{x_1, \\dots, x_n \\in \\mathbb{R}^d}   \\frac{\\Vert\\textbf{Agg}(x_1, \\dots, x_n) - \\bar{x}_n  \\Vert^2}{\\frac{1}{n}  \\Sigma \\Vert x_i - \\bar{x}_n \\Vert^2} . $$ \n\n$\\textbf{Note:}$ I am rewriting the definition here (off course excluding the trivial case of zero empirical variance). \n\nTheoretical results support the claim by proving lower bounds on a well-known class of robust aggregation methods known as $(f,\\kappa)$-robust averaging introduced in [1]. This bound writes $\\epsilon \\in \\Omega(\\frac{f}{n-f})$, hence it linearly depends on the ratio $\\frac{f}{n-f}$ where $n$ is the total number workers in the system and $f$ is the maximal amount of Byzantine workers the aggregation can theoretically tolerate. Based on this idea, the paper also provides a lower bound on the wort-case training error of ByzGD. These lower bounds are tight as proven by the matching upper bounds the paper presents. \n\nEmpirical experiments show accuracy degradation for ByzGD in the absence of Byzantine workers in several context to further support the point made by the theoretical claims (this point will be mitigated below).", "methods_and_evaluation_criteria": "The authors define worst-case accuracy using the norm difference from the true average of the datapoints (see above). The worst-case scenario (i.e., the lower bound) is constructed by assuming datasets with extreme skewness, which significantly affects the distance between the computed aggregation and the true average of the distribution. However, in such cases, targeting the average as the aggregation goal may not be statistically meaningful anymore (as the average is not a meaningful summary of the dataset anymore). Accordingly, I am not certain to understand the semantic of being distant from the average in such a scenario. In essence, I am unsure that the worst-case analysis is the best way to capture the accuracy vs robustness trade-off of Byzantine robust methods. A more informative approach would be to analyze statistical bounds under assumed data distributions to better model realistic data heterogeneity among honest workers.\n\nI also feel like there is a lack of deep analysis on state-of-the-art robust aggregation techniques. In fact, the paper does not truly discusses the impact of state-of-the-art pre-aggregation methods like NNM or Bucketing on the trade-off being studied. These methods have been shown to improve Byzantine robustness while mitigating accuracy degradation, making their omission a significant gap in my opinion. I also feel similar concerns on the experimental part. While the experiments confirm theoretical findings on simple aggregation rules like trimmed mean or median, they do not seem to explain very clearly the behavior of state-of-the-art methods like NNM or Bucketing. \n\n**Side note:** I would suggest including loss curves in the empirical evaluation to study whether the theoretical findings hold throughout the training process (as the theory in on training not testing).", "theoretical_claims": "I checked the correctness of some of the proofs (proof of Theorems 3.1, 3.2, and 3.4) and only had a quick look over the rest of the proofs. Overall the proofs seem correct to me even-though they also seemed quite limited in terms of technical novelty. \n\nIn fact, the derivation of the lower and upper bounds on aggregation error appears to closely follow existing proofs in the literature see especially Section 8 in [1]. The Byzantine convergence analysis also resembles prior work (see e.g. [2] for lower bound and [1] for upper bound), and the paper does not sufficiently explain what modifications or adaptations were required. The connection of the convergence result with prior work is also not well explained in my opinion. Could the author explain what key insight we can get from Theorem besides that we have a lower bound in ($\\frac{f}{n} G^2$), which is already what one has when considering the presence of Byzantine workers. \n\n[1] Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity, Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, John Stephan (AISTATS 2023)\n[2] Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing, Sai Praneeth Karimireddy, Lie He, Martin Jaggi (ICLR 2022)", "experimental_designs_or_analyses": "The experimental setup seemed sound to me.", "relation_to_broader_scientific_literature": "As I was mentioning above, the paper technical content seem to be quite derivative compared to [1,2]. Nevertheless, the idea of investigating the tension between accuracy and robustness theoretically seem like a novel and interesting idea to investigate.", "essential_references_not_discussed": "There are some recent works that are very related to the Byzantine literature like [3,4] that could be cited but are not essential to the understanding of the paper. \n\n[3] Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity, Youssef Allouah Rachid Guerraoui Nirupam Gupta Rafaël Pinot Geovani Rizk, (Neurips 2023)\n[4] Variance reduction is an antidote to Byzantoine workers, Eduard Gorbunov, Samuel Horvath, Peter Richtarik, Gauthier Gidel (ICLR 2023)", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "This paper raises an interesting and important question about the trade-off between Byzantine robustness and accuracy in non-attack scenarios. However, I am unsure if it currently provides a deep enough analysis of this trade-off (I will wait for discussion with the authors and the other reviewers to make my final decision I guess). Here are some suggestions, that might help Improve the paper.\n\n- Consider statistical bounds under realistic data distributions rather than focusing solely on worst-case skewed data.\n- Expand the analysis of state-of-the-art robust aggregation techniques like NNM and Bucketing.\n- Clarify the novelty of the proof techniques and how they differ from prior work.\n- Strengthen the empirical evaluation by including loss curves and more in-depth analysis of heterogeneity effects.", "questions_for_authors": "Please answer my above concerns, especially regarding proof novelty and the limitations of using a worst-case analysis.", "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: This paper investigates the trade-off between Byzantine robustness and attack-free learning error in distributed learning. To be specific, it analyzes the aggregation errors of robust aggregation rules, as well as the learning error of Byzantine-robust gradient decent equipped with these robust aggregation rules, both in the absence of Byzantine workers. The theoretical results show that making Byzantine-robust gradient decent robust to more Byzantine workers will increase the worst-case attack-free learning error. Although the theoretical analysis resembles those from the existing works and limited to gradient descent (not stochastic gradient descent), this paper provides novel insights into the tension between Byzantine robustness and attack-free learning error. All reviewers unanimously recommend acceptance.
Decision: Accept (spotlight poster)