Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity
Authors: Youssef Allouah
Rachid Guerraoui
Nirupam Gupta
Rafael Pinot
Geovani Rizk
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Optimization
Byzantine resilience
Distributed machine learning
federated learning

Abstract: The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bounds on the learning error are essentially vacuous and greatly mismatch empirical observations. This is because the heterogeneity model considered is too restrictive and does not cover basic learning tasks such as least-squares regression. We consider in this paper a more realistic heterogeneity model, namely $(G,B)$-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. Notably, we show that the breakdown point under heterogeneity is lower than the classical fraction $\frac{1}{2}$. We also prove a new lower bound on the learning error of any distributed learning algorithm. We derive a matching upper bound for a robust variant of distributed gradient descent, and empirically show that our analysis reduces the gap between theory and practice.

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity
Youssef Allouah"
Rachid Guerraoui
Nirupam Gupta
Rafaël Pinot
Geovani Rizk
Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Abstract
The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, es- tablished lower bounds on the learning error are essentially vacuous and greatly mismatch empirical observations. This because the heterogeneity model consid- ered is too restrictive and does not cover basic learning tasks such least-squares regression. We consider this paper more realistic heterogeneity model, namely (G, B) -rradiett dissimilarity, and show that it covers larger class of learning problems than existing theory. Notably, we show that the breakdown point under heterogeneity is lower than the classical fraction 1/2. We also prove new lower bound on the learning error of any distributed learning algorithm. We derive a matching upper bound for robust variant of distributed gradient descent, and empirically show that our analysis reduces the gap between theory and practice.
Introduction
Distributed machine learning algorithms involve multiple machines (or workers) collaborating with the help of server to learn common model over their collective datasets. These algorithms enable training large and complex machine learning models, by distributing the computational burden among several workers. They are also appealing they allow workers retain control over their local training data. Conventional distributed machine learning algorithms are known to be vulnerable to adversarial workers, which may behave unpredictably. Such behavior may result from software and hardware bugs, data poisoning, or malicious players controlling part of the network. In the parlance of distributed computing, such adversarial workers referred Byzantine 24) Due the growing influence of distributed machine learning in public applications, a significant amount work has heen devoted addressing the problem of robustness Byzantine workers, e.g., see [34 2 I3 15).
vast majority of prior work on robustness however assumes data homogeneity, i.e., local datasets are generated from the same distribution. This questions their applicability in realistic distributed learning scenarios with heterogeneous data, where local datasets are generated from different distributions. Under data homogeneity, Byzantine workers only harm the system when the other workers compute stochastic gradient estimates, by exploiting the noise in gradient computations. This vulnerability can be circumvented using variance-reduuctoon schemes [19 13 14]. In contrast, under data heterogeneity, variance-reduction schemes are not very helpful, as suggested by preliminary work 12 20 3) In short, data heterogeneity is still poorly understood in robust distributed learning. In particular, existing robustness guarantees are extremely conservative, and often refuted by empirical observations. Indeed, the heterogeneity model generally assumed is typically violated in practice and does not even cover basic machine learning tasks such as least-squares regression.
"Correpondencee to: Youssef Allouah wywusseffllouaah@epl.ccco
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our work addresses the aforementioned shortcomings of existing theory, by considering a more realistic heterogeneity model, called (G, B -rr-giddnett dissimilarity [[8]. This criterion characterizes data heterogeneity for larger class of machine learning problems compared to prior works [12 20 3
and enables us to reduce the gap between theoretical guarantees and empirical observations. Before summarizing our contributions in Section 1.2 we briefly recall below the essentials of robust distributed learning and highlight the challenges of data heterogeneity.
1.1 Robust distributed learning under heterogeneity
Consider a system comprising n. workers Wi,..., W.n and a central server, where ʃ workers of a priori unknown identity may be Byzantine. Each worker w; holds dataset D; composed of m data points from an input space X, ie., D; = {al ,...,. I'm E Am. Given a model parameterized by E RR,, each data point x incurs a loss ((0;)) where l: Rd x + R. Thus, each worker wy has a local empirical loss function defined as (0) == J. EZED, {(0; æ)). Ideally, when all the workers assumed honest (i.c., non- non-Byzamtnn -e--Byyzattnn,, the server can compute a model minimizing the global average loss function given by >i (0). without requiring the workers share their raw data points. However, this goal is rendered vacuous in the presence of Byzantine workers. A more reasonable goal for the server is to compute model minimizing the global honest loss [16], i.e., the average loss of the honest workers. Specifically, denoting by H. S [nl] where [7(| = n - f. the indices of honest workers, the goal in robust distributed learning is solve the following optimization problem P
1
min (0) = OER
Σ NEW
C.(0).
H
Because Byzantine workers may send bogus information and are unknown to the server, solving (even approximately) the optimization problem (I is known be impossible in general 26 20). The key reason for this impossibility is precisely data heterogeneity. Indeed, we cannot obtain meaningful robustness guarantees unless data heterogeneity is bounded across honest workers.
Modeling heterogeneity. Prior work on robustness primarily focuses on a restrictive heterogeneity bound we call G-gradient dissimilarity [12 20 B.. Specifically, denoting || to be the Euclidean norm, the honest workers are said to satisfy G-gradient dissimilarity if for all 0 E Rd, we have
Σ
[V2(0)- GO. SP.
(2)
H
iN
However, the above uniform bound on the inter-worker variance of local gradients may not hold in common machine learning problems such as least-squares regression, as we discuss in Section 3 In our work, we consider the more general notion of (G, B) -rradiettt dissimilarity, which is a prominent data heterogeneity model in the classical (Byzantine-free distributed machine learning literature
(i.e., when f f= 0) [18, 23 27 29 Recent works have also adopted this definition in the context of Byzantine robust learning 22 [4], but did not provide tight analyses, as we discuss in Section Formally. (G, B)- -gradienn dissimilarity is defined as follows.
Assumption 1 (GG, -)ggrdiie dissimilarity). The local loss functions of honest workers (repre- sented by set H) said satisfy (G, B)-gradient dissimilarity if, for all E Rd, have
VV,(0)) -L [L)())] < G² +
H
EEH
Under (G, B.-BB)-grra -3)-gradient dissimilarity, the inter- worker variance of gradients need not be bounded, and can grow with the norm of the global loss function's 's gradient at a rate bounded by B. Furthermore, this notion also generalizes G G'gradient dissimilarity, which corresponds to the special case of B 0.
1.2 Our contributions
We provide the first tight analysis robustness Byzantine workers in distributed learning under realistic data heterogeneity model, specifically (G, B) -rgrdiient dissimilarity. Our key contributions are summarized as follows.
We denote by 'n] the set (1,..., n).
The dissimilarity inequality is equivalent to गी Eien [VC()) 5 G² ++((1+ B²) (0)1
2

---

Breakdown point. We establish novel breakdown point for distributed learning under heterogeneity. Prior to our work, the upper bound on the breakdown point was simply z more) of the workers are Byzantine, no algorithm can provide meaningful guarantees for solving ( We prove that, under (G, ---graiient dissimilarity, the breakdown point is actually 2+ That is, the breakdown point of distributed learning is lower than 1 growth rate B of gradient dissimilarity. We also confirm empirically that the breakdown point under heterogeneity can be much lower than 2. which could not be explained prior to our work.
Y 26], i... when half (or
2. under heterogeneity due to non-zero
Tight error bounds. We show that, under the necessary condition B+ any robust distributed learning algorithm must incur an optimization error in
Ω (2 B2) G²
on the class of smooth strongly convex loss functions. We also show that the above lower bound tight. Specifically, we prove a matching upper bound for the class of smooth non-convex loss functions, by analyzing a robust variant of distributed gradient descent.
Proof techniques. To prove new breakdown point and lower bound, construct instance of quadratic loss functions parameterized by their scaling coefficients and minima. While the existing lower bound under G-gradient dissimilarity can easily be obtained by considering quadratic functions with different minima and identical scaling coefficients (see proof of Theorem III in [20]), this simple proof technique fails to capture the impact of non-zero growth rate B in gradient dissimilarity. In fact, the main challenge we had to overcome is to devise coupling between the parameters of the considered quadratic losses (scaling coefficients and minima) under the B) -ggrddeie dissimilarity constraint. Using this coupling, we show that when 2 2+ the distance between the minima of the quadratic losses can be made arbitrarily large by carefully choosing the scaling coefficients, hence yielding an arbitrarily large error. We similarly prove the lower bound (3) when & << 2+B
1.3 Paper outline
The remainder of this paper is organized as follows. Section definition and recalls standard assumptions. Section discusses some key limitations of previous works on heterogeneity under G-gradient dissimilarity. Section 4 presents the impossibility and lower bound results under (G, -)-rrddient dissimilarity, along with a sketch of proof. Section presents tight upper bounds obtained by analyzing robust distributed gradient descent under (G, B)- gradient dissimilarity. Full proofs are deferred to appendices A and and
2 presents our formal robustness
Details on the setups of our
experimental results are deferred to Appendix D
2 Formal definitions
In this section, we state our formal definition of robustness and standard optimization assumptions. Recall that an algorithm is deemed robust to adversarial workers if it enables the server to approximate a minimum of the global honest loss, despite the presence f Byzantine workers whose identity is a priori unknown the server. In Definition I we state the formal definition of robustness.
Definition 1 e-resliicce))).).. A distributed algorithm is said to be (fesssresll if it can output parameter 0 such that
(x(0) L. Se,
where L.HH == mingerd (+)
Accordingly, (f, reeeslien distributed algorithm output an s-approximate minimizer of the global honest loss function, despite the presence of f adversarial workers. Throughout the paper, we assume that f < 2. as otherwise (f, (reslince is in general impossible 26). Note also that, for general smooth non-convex loss functions, aim find an approximate stationary point of the global honest loss instead of minimizer, which is standard in non-convex optimization [8].
Standard assumptions. To derive our lower bounds, we consider the class of smooth strongly convex loss functions. We derive our upper bounds for smooth non-convex functions, and for functions satisfying the Polyak- Lojaswwwwi (PL) incquality. This property relaxes strong convexity, i.c., strong
3

---

convexity implies PL. and covers learning problems which may be non stronnyyygly convex such as least-squares regression [7]. We recall these properties in definitions and beloo.
Definition 2 (Z-smoothness). A function L: Rd + R is L-smooth if, for all 8, 8, R we have
[V[(0) V - L 1|0 01I
This is equivalent 28 to, for all 0, 0", having |<()0) [()) (VC(0), -'- 0) - 4 110' 01 Definition 3 Polyyak-Lojasiwiice (PL), strong convexity). A function C: 12d + IR is μ-PL if, for all 0 E R2 we have
2p (C(() - C.) < [V(()))
where C. == millogRa ((0). Function & is ju-Strongly convex if, for all 0, 0' E R2, we have
- (V 8'
- 6 01
Note that function satisfies I-smoothhess and p-PI. inequality simultaneously only if p S L. Lastly, although not needed for our results to hold, when the global loss function Lu is fu-PI,, we will assume that it admits unique minimizer, denoted o., for clarity.
3 Brittleness of previous approaches on heterogeneity
Under the G-gradient dissimilarity condition, presented in 2). prior work has established lower bounds [20] and matching upper bounds [3 for robust distributed learning. However, G-gradient dissimilarity is arguably unrealistic, since it requires a uniform bound G² on the variance of workers' gradients over the parameter space. As matter of fact, G-gradient dissimilarity does not hold in general for simple learning tasks such as least-squares regression, as shown in Observation | [eloww general, G-gradient dissimilarity 2 does not hold in least-squares regression.
Observation
Proof. Consider the setting given by X' = IR2 n = 2, = 0, and d 1. For any data point (21, 2222 X, consider the squared error loss {(): (21, F22)
1 (0. .1 2 Let the local datasets be D2 = ((100), D2 = (0, 1)}. Note that for all 0 E R. we have (f) = 6, and V22 = 0. This implies that [ ΣiEn (0) (0)l = 0²/4, where H = (1, which is unbounded over R. Hence, the condition of G-gradient dissimilarity cannot be satisfied for any G E R.
In contrast, the (G, B) -gradient dissimilarity condition, presented in Assumption| 1 is more realistic, since it allows the variance across the local gradients to grow with the norm of the global gradient. This condition common in the (non-robust) distributed learning literature is also well-known in the monndisttribtted optimization community 8 g 32 While G-gradient
23
18 25 29], and
dissimilarity corresponds to the special case of (G. 0)- -rradient dissimilarity, we show in Proposition
below that non-zero growth rate B of gradient dissimilarity allows to characterize heterogeneity in much larger class of distributed learning problems.
Proposition 1. Assume that the global loss L* is J-PL and L-smooth, and that for each i E H local loss Li is convex and Li-smooth. Denote Linax == maxie H Li- Then, Assumption Dis sutisfied, i.e. the local loss functions satisfy (G, BB--BBrgddene gradient dissimilarity, with
G2
2 |H
Σ IEH
(V.1(11)1
and B = 2T 1.
(4)
P
We present the proof of Proposition 1 in Appendix A for completeness. However, note that it can also be proved following existing results [32 21 derived in other contexts. The (G, B)-gradient dissimilarity condition shown in Proposition] T is arguably tight (up to multiplicative factor 2), in the
sense that G cannot be improved in general. Indeed, as the (G, B) -raddiettt dissimilarity inequality should be satisfied for 0 = 0,, G2 should be at least the variance of honest gradients at the minimum, i... [ EieH [Q.)
Gap between existing theory and practice. The theoretical limitation of G-gradient dissimilarity is exacerbated by the following empirical observation. We train a linear least-squares regression

---

model on the LIBSVM dataset [10]. The system comprises honest and 3 Byzantine workers. We simulate extreme heterogeneity by having each honest worker hold one distinct point. We
implement four well-studied Byzantine attacks: sign flipping (SF) 22 fall of empires (FOE) [33
little enough (ALIE) [S] and mimic [20]. More details on the experimental setup can be found in Appendix D We consider the state-of-the-art robust variant of distributed gradient descent (detailed later in Section 5.1) that uses the NNM robustness scheme [3] composed with coordinate-wise trimmed mean. The empirical success on this learning task, which could not be explained by existing theory under G-gradient dissimilarity following Observation [ is covered under (G, -ggrddientt dissimilarity, per Proposition I We present formal robustness guarantees under (G, -gradient dissimilarity later in Section 5 Additionally, through experimental evaluations in Section 5 we observe that even if G-gradient dissimilarity were assumed to be true, the bound G² may be extremely large in practice, thereby inducing non-informative error bound Off/n G²) (20). On the other hand, under (G, B) B)-gradient dissimilarity, obtain tighter bounds matching empirical observations.
0.50
3;
3; FOE
0.150
0.40
3;
Mimic
0.125
Toining Lass
0.100
0.30
0.075
0.25
0.025
3. FOE
3
0.15
0.000
3. Mimic
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.2
0.4
0.6
0.8
Steps
164
Figure 1: Evolution of the training losses (left) and the trajectories (right) of robust D-GD algorithm with NNM and coordinate-vee wise trimmed mean (see Section on the mg LIBSVM least-squares regression task described in Section 0 corresponds to the case where the algorithm is run without Byzantine workers.
4 Fundamental limits robustness under (G, B)Gaddient Dissimilarity
Theorem below shows the fundamental limits on robustness in distributed learning under (G, B)- gradient dissimilarity. The result has twofold implications. On the one hand, we show that the breakdown point of any robust distributed learning algorithm reduces with the growth B of gradient dissimilarity. On the other hand, when the fraction f/n is smaller than the breakdown point, both G and B induce lower bound on the learning error.
Theorem 1. Let f < n/2. Assume that the global loss Cu is L-smooth and u-strongly convex with 0 < μ L. Assume also that the honest local losses satisfy (G, -.BBB-rrrdiin dissimilarity (Assumption) 7 with 0. Then, a distributed algorithm can be (f, -)rssiiinn only if
1
1 8p n (2 B G²
1
and
2+ B
Sketch of proof. The full proof is deferred Appendix In the proof, we construct hard instances for (f, eerreliie,, using a set of quadratic functions of the following form:
(0) 3/8 0
Vi E (1,..., We 1,............... 1...., f). ViE {n f 1,........ n...
(0)
(.) |0l
To prove the theorem, we consider two plausible scenarios corresponding to two different identities of honest workers, which are unknown to the algorithm. Specifically, in scenarios and II, we assume the indices of honest workers to be S = (I....,m f) and S2 {f I,..., n), respectively.
5

---

We show that for all 0 E R"
m n- K
a²
max {Ls; L1 Ls² (0) Sa)
|
(5)
8
n-2f
That is, every model in the parameter space incurs an error that grows with ||=|| in least one of the two scenarios. Hence, an (f. reesiiien algorithm, by Definition]
[ must guarantee optimization
error in both scenarios I and II, which together with ( implies that
2 a
|
(6)
8
K
n-
At this point, to obtain the largest lower bounds possible, our goal is maximize the right-hand side of under the constraint that the loss functions induced by the triplet (a, K,2) satisfy (G, B)- gradient dissimilarity, L-smoothness and ju-strong convexity (simultaneously in both scenarios). We separately analyze this error in two cases: (i) &
2+ In both cases, construct a coupling between the values of z and K by having the norm ||=|| proportional to K. Specifically, in case (i), we show that the condition ! 2 2+8z allows us to choose K arbitrarily large while satisfying (G, -idiiiiiiilll Thus, ||=||² being proportional to K means that is arbitrarily large as per (6) Similarly, in case (ii) where 2z K cannot be arbitrarily large and carefully choosing large possible value yields
a 2+B² and (ii)
1 81c n- (2 - B G
f
One of the crucial components the above deductions was finding the suitable triplets (a, K, =) while preserving the (G, B) -gradieett dissimilarity assumption (along with the smoothness and strong convexity assumptions) simultaneously in both the two scenarios, thereby establishing their validity. While the exact calculations are tedious, intuitively, B constrains the relative difference between the scale parameters and K and G constrains the separation between the minima, i.e. ||
L
Extension to non-convex problems. The lower bound from Theorem [asummss that the given distributed algorithm satisfies e -reeeileee, which means finding e-approximate minimizer of the global honest loss Cy. The latter may not be possible for the general case of smooth and non-convex functions. In that case cannot seek E-approximate minimizer, but rather approximate stationary point (20 3. i.e., 9 such that [[)(())] < e. Then the lower bound in Theorem in conjunction with the p-PL inequality, yields the following lower bound
1 4 (2 +B)
G²
Comparison with prior work. The result of Theorem generallizss the existing robustness limits derived under G-gradient dissimilarity (20). In particular, setting B 0 in Theorem I we recover the breakdown point? and the optimization lower bound Q2f/n G²). Perhaps, the most striking
contrast to prior work 212 20 13 is our breakdown point 3+B7 instead of simply J. We remark that a similar dependence on heterogeneity has been repeatedly assumed in the past, but without any formal justification. For instance, under (0, B) -)grrddient dissimilarity, (20] Theorem IV] assumes f/n = O(1/²²) to obtain a formal robustness guarantee. In the context of robust distributed convex optimization (and robust least-squares regression), the upper bound assumed the fraction f/n usually depends upon the condition number of the distributed optimization problem, e.g., see (6) Theorem 3] and [16] Theorem 2]. Our analysis in Theorem I justifies these assumptions on the breakdown point in prior work under heterogeneity.
Empirical breakdown point. Interestingly, breakdown point 2+ allows to better understand some empirical observations indicating that the breakdown point of robust distributed learning algorithms is smaller than 1/2. We illustrate this Figure with logistic regression model on the MNIST dataset under extreme heterogeneity, i.c. each worker dataset contains data points from

---

single class. We consider the state-of-the-ard robust variant of distributed gradient descent (detailed later in St.I that uses the NNM robustness scheme composed with robust aggregation rules, namely, coordinate-wise trimmed-mean (CW Trimmed Mean)
14 Krum 77 coordinate-wise
median (CW Median) 34 and geometric median [31 3D We observe that all these methods
I. which is well short of the previously known theoretical breakdown point 2. Theorem to the best of our knowledge, provides the first formal justification to this empirical observation.
consistently fail to converge as soon as the fraction of Byzantine workers exceeds 1
initial
2.5
90-
CW Trimmeed Mean
loss aalue
traiiiinnng lass over 500 steps
80-
CW Median Geametric Median
Accuncy
1.5
1-
CW Trimmee Moan
30-
Krum
20-
Median
0.5
Geometric Median
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Fraction of byzantine workers
Fraction byzantine workers
Figure 2: Best training loss (left) and accuracy (right) using robust D-GD (see Section 5.1 with NNM to train a logistic regression model on the MNIST dataset, in the presence of 10 honest workers and 1 to Byzantine workers. The Byzantine workers the sign flipping attack. More details on the experimental setup can be found in Appendix D
5 Tight upper bounds under (G, B)-Gradient Dissimilarity
We demonstrate in this section that the bounds presented in Theorem T arr tight. Specifically, we show that a robust variant of distributed gradient descent, referred to as robust D-GD, yields an asymptotic error that matches the lower bound under (G, B) gradient dissimilarity, while also proving the tightness of the breakdown point. Lastly, we present empirical evaluations showcasing significant improvement over existing robustness analyses that relied upon G-gradient dissimilarity.
5.1 Convergence analysis of robust D-GD
In robust D-GD, the server initially possesses a model fn- Then, at each step t E (O...., 1}. the server broadcasts model 0, to all workers. Each honest worker w; sends the gradient g. (0.) of its local loss function at 0t. However, a Byzantine worker wy might send an arbitrary value for its gradient. Upon receiving the gradients from all the workers, the server aggregates the local gradients using a robust aggregation rule F; Rddxn + Rd, Specifically, the server computes
R, F(g(") (1) ,....9t' (()). Ultimately, the server updates the current model 6g to 0 02 Re, where y > 0 is the learning rate. The full procedure is summarized in Algorithm
Algorithm 1: Robust D-GD
Input: Initial model Op robust aggregation F, learning rate y, and number of steps T.
for f 0... T do
Server broadcasts 6, to all the workers; for each honest worker w; in parallel do
Compute and send gradient of" VL,());
// A Byzantine worker Wy may send an arbitrary value for gf
Server computes the aggregate gradient: R₂ F(g (1) Server updates the model: 0z+1 = 0, RR;
,..... ()));
7

---

To analyze robust D-GD under BG. --gradien dissimilarity, we first recall the notion of (f, xc)- robustness in Definition below. First introduced in [3] (f. roobusttesssss is a general property of robust aggregation that covers several existing aggregation rules.
Definition 4 ((,, robbossste,ss) Let n. 2 1, 0 < f < n/2 and K. 2 0. An aggregation rule F: IRdxn + R2 said to be (f. ror-busst if for any vectors 21,...,, In E R and any set _ [n]
of size f. the output & == F(11,.... Fn) satisfies the following:
| - Fsll S K
Σ EES
||, 11:-Esh -
S
where Fs == [S] Eies We refer to as the robustness coefficient of F.
Closed-form robustness coefficients for multiple aggregation rules can be found in [3. For example, assuming 2 (2 +2+10 n),, for some 1) > 0, O 4 for coordinate-wise trimmed mean, K. (1)
for coordinate-wii wise median, and KFONNM = O (16 + 1)) when F is composed with NNM 3
Assuming F to be an (f, k)-rbusst aggregation rule, we show in Theorem 2 below the convergence of robust D-GD in the presence of up to Byzantine workers, under (G, BJ- R-yggrddeett dissimilarity.
Theorem 2. Let 0 S f < n/2. Assume that the global loss Ly is L-smooth and that the honest local losses satisfy (G, B)-gradient dissimilarity (Assumption) D. Consider Algorithm 7 with learning rate y L. the aggregation F is (S, ro)-robust with RB22 < 1, then the following holds for all T 1.
1. In the general case where LH may be non-convex, we have
T-1
RG2
2L (Oo) - L.,H)
[VC((0))1= < 1- 1- +
T
(1- -KKB2TT
20
2. In the case where LH is pLPL, we have
kG2
(x((T) La,H S 2p xB2) +e- ((1-BB") (Cn(Oo) L...))
Tightness of the result. We recall that the best possible robustmess coefficient for an aggregation F is k = f/n-2f (see (3). For such an aggregation rule, the sufficient condition kB² < 1 reduces to f/n-25- B 1 or equivalently s/n 1/2-B². Besides, robust D-GD guarantees (f. a) -reeiliie, for losses where we have (1/nn G2) asymptotically in T. Both these conditions on f/nn and E indeed match the limits shown earlier in Theorem [ Yet, we are unaware of an aggregation rule with an order-optimal robustness coefficient, i.e., usually A > 1/n-2s. However, as shown in [3. the composition of nearest neighbor mixing (NNM) with several aggregation rules. such as CW Trimmed Mean, Krum and Geometric Median, yields a robustness coefficient = (J/nn2r). Therefore, robust D-GD can indeed achieve (ʃ, e.e--sssileennc with an optimal error G?). but for suboptimal breakdown point. The same observation holds for the non-convex case, where the lower bound given by 77. Lastly, note that when B = O, our result recovers the bounds derived in prior work under G G-gradient dissimilarity (0 3].
We remark that while the convergence rate of robust D-GD shown in Theorem is linear (which is typical to convergence of gradient descent in strongly convex case), it features a slowdown factor of value =B².. Hence, suggesting that Byzantine workers might decelerate the training under heterogeneity. This slowdown is also empirically observed (e.g., see Figure D]. Whether this slowdown is fundamental to robust distributed learning is an interesting open question. Investigating such a slowdown in the stochastic case is also of interest, existing convergence bounds are under G- G-gradient dissimilarity only, for strongly convex 4 and non-convex cases.
Comparison with prior work. Few previous works have studied Byzantine robustness under (G. -rradient dissimilarity (20 [4]. While these works do not provide lower bounds, the upper bound they derive (see Appendix E in (20] and Appendix E.4 in [4] are similar to Theorem 2 with some notable differences. First, unlike the notion of robbsstts that we use, the so-called (c, d)-annoi robustness, used in 20 14 is a stochastic notion. Under the latter notion, good parameters (c, d) of robust aggregators were only shown when using a randomized method called Bucketing [20]. Consequently, instead of obtaining deterministic error bound as in Theorem 2
8

---

simply replacing cδ with A. in 20 14 gives an expected bound, which is strictly weaker than the result of Theorem Moreover, the corresponding non-vanishing upper bound term and breakdown point for robust D-GID obtained from the analysis in (20] for several robust aggregation rules (e.g.. coordinate-wee median) are worse than what we obtain using (f, ro)rrstsssssss.
5.2 Reducing the gap between theory and practice
In this section, we first argue that, even if we were to assume that the G-gradient dissimilarity condi- tion (2) holds true, the robustness bounds derived in Theorem 2 under (G, B--graiient dissimilarity improve upon the existing bounds [3] that rely G-gradient dissimilarity, Next, compare the empirical observations for robust D-GD with our theoretical upper bounds.
We consider a logistic regression model on MNIST dataset under extreme heterogeneity. While
Comparing upper bounds.
difficult to find tight values for parameters and satisfying (G, -)-rrddient dissimilarity, we can approximate these parameters through a heuristic method. A similar approach can be used to approximate G for which the loss functions satisfy the condition of G-gradient dissimilarity. We defer the details on these approximations to Appendix D In Figure 3 we compare the error bounds, i.e., 1/ G and f/n-2f G guaranteed for robust D-GD under (G, -gggrdiiett dissimilarity and G-gradient dissimilarity, respectively. We observe that the latter bound extremely large compared to the former, which confirms that the tightest bounds under G- G-gradient dissimilarity are vacuous for practical purposes.
Our bound
350
Upper Gidisimilarity
Our upper bound with dissimlairyyyyy
Best emol gap over 40000 stops
ALIE
mimic
250
10
150
10
100
10
01
0.05
0.20
0.15
0.20
0.25
0.30
0.35
0.40
0.45
Fraction Byzantine workers
0.20 0.30
0.45
byzartine
Figure 4: Comparison between our upper bound in Corollary [ and the training loss for the least-squares regression on the mg LIBSVM dataset [10]. The number of honest workers is 20 and the number of Byzantine workers varies from to 19.
Figure 3: Comparison our upper bound The- orem 2 with that of G-gradient dissimilarity MNIST with a logistic regression model. The number of honest workers is 10, and the number of Byzantine workers varies from to 9.
We further specialize the result of Theorem to the convex case for which the (G, -ragiiitt dissimilarity condition was characterized in Proposition [ We have the following corollary.
Corollary 1. Assume that the global loss Lu is μ-PL and L-smooth, and for each i E H. local loss Ea convex and smoohh.. Denote Lmax maxGEH Li and assume that x( 3Lmax 1) S
Consider Algorithm
with learning rale
Ff (ʃ -))rbuustt, then for all T 1, we have
3R
(x(OT) L.
[VC,0.)) + #. (CH(00)) Lo,7))
J
H
EEN
The non-vanishing term in the upper bound shown in Corollary corresponds to the heterogeneity at the minimum [ EiEw (V,,()))1 This quantity considered to natural measure of gradient
dissimilarity in classical (non- (oon-Byzantnne) distributed convex optimization believe that this bound cannot be improved upon in general.
23 As such, we
Matching empirical performances. Since the upper bound in Corollary | requires computing the constants μ. L, we choose conduct this experiment least-squares regression, where the exact

---

computation of μ. L is possible. We compare the empirical error gap (left-hand side of Corollary I with the upper bound (right-hand side of Corollary D.. Our findings, shown Figure 4 indicate that our theoretical analysis reliably predicts the empirical performances of robust D-GD, especially when the fraction of Byzantine workers is small. Note, however, that our upper bound non-informative when more than of the workers are Byzantine, as the predicted error exceeds the initial loss value. We believe this to be an artifact of the proof, i.c. the upper bound is meaningful only up to multiplicative constant. Indeed, when visualizing the results in logarithmic scale in Figure 4 the shape of empirical measurements and our upper bounds are quite similar.
6 Conclusion and future work
This paper revisits the theory of robust distributed learning by considering realistic data heterogeneity model, namely (G, -ggrddientt dissimilarity. Using this model, we show that the breakdown point depends upon heterogeneity (specifically, 1/2+B*) and smaller than the usual fraction 1/2. We prove new lower bound on the learning enror of any distributed learning algorithm, which is matched using robust D-GD. Moreover, we show that our theoretical guarantees align closely with empirical observations, contrary to prior works which rely upon the stringent model of G- G-gradient dissimilarity.
An interesting future research direction is investigate whether the 1 RB slowdown factor in the convergence rate of robust D-GD (Theorem 2 is unavoidable. Another interesting research problem is derive lower (and upper) bounds independent of the heterogeneity model, thereby elucidating the tightness of the convergence guarantee of robust D-GD in the strongly convex case (Corollary I
Acknowledgements
This work was supported in part by SNSF grant 200021 200021_200477 and an EPFL-INRIA postdoctoral grant. The authors are thankful to the anonymous reviewers for their constructive comments.
References
[1] Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S. Dhillon, and Ufuk Topcu. Robust training in high dimensions via block coordinate geometric median descent. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 1114-11168. PMLR, 28-30 Mar 2022. mlr URL htttpt:::ppocceedinnnne http:/eccggg.........reee////aaa http://///aaaaaaaa.a1aa html
Camps-Valls.
[2] Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex stochastic gradient descent. In International Conference on Learning Representa- lions, 2020.
[3] Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal Byzantine ML under heterogeneity, In International Conference on Artificial Intelligence and Statistics, pages 1232-1300 1300. PMLR, 2023.
[4] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. On the privacy-robustness-uiilgg trilemma in distributed learning. In International Conference on Machine Learning, number 202, 2023.
[5] Moran Baruch, Gilad Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 8-14 December 2019, Long Beach, CA, USA, 2019.
[6] Kush Bhatia, Prateek Jain, and Purushottam kar. Robust regression via hard thresholding. Advances in neural information processing systems, 28, 2015.
10

---

[7] Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In I. Guyon, U. V. Luxburg, S. Ben- gio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 119-129. Curran Associates, Inc., 2017.
[8] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31 2018.
[9] Volkan Cevher and Bäng Công Vü. On the linear convergence of the stochastic gradient method with constant step-size. Optimization Letters, 13()):1177-1887, 2019.
[10] Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines, ACM transactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
[11] EI Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in Byzantium. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3521-3530. PMLR, 10-15 Jul 2018. URL htt.httss://prreediing
mlr. artess/v800mmaaaae 18a html
[12] El Mahdi El Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Nguyên Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, Byzantine, heterogeneous, asynchronous and nonconvex learning). In Thirty- Conference on Neural Information Processing Systems, 2021.
[13] Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, edi- tors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 6246-6283. PMLR, 17-23 Jul 2022.
[14] Eduard Gorbunov, Samuel Horváth, Peter Richtárik, and Gauthier Gidel. Variance reduction is an antidote to byzantines: Better rates, weaker assumptions and communication compression as a cherry on the top. The Eleventh International Conference on Learning Representations, 2023. URL https: httttp::///peeeevvii http://pwwweeereeeeeeeeooooaaaap
[15] Rachid Guerraoui, Nirupam Gupta, and Rafael Pinot. Byzantine machine learning: A primer. ACM Computing Surveys, 2023.
[16) Nirupam Gupta and Nitin H Vaidya. Fault-tolerance in distributed optimization: The case of redundancy. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 365-374, 2020.
[17] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the -ojasak-tojssiwiizzz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 995-811. Springer, 2016.
[18] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5 5143. PMLR, 2020.
[19] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for Byzantine robust optimization. International Conference On Machine Learning, Vol 139, 139, 2021.
[20] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robuss learning on heteroge- neous datasets via bucketing. In International Conference on Learning Representations, 2022. URL httphst//pppeeeeiiiceoo net/teeetfee fest//formmidddjie utoe//Eoooum
[21] Ahmed Khaled and Peter Richtárik. Better theory for SGD the nonconvex world, Tronsactions on Machine Learning Research, 2022.

---

[22] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519 4529. PMLR, 2020.
[23] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Conference Machine Learning, pages 5381-5393, PMLR, 2020.
[24] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3):382-401, jul 1982. ISSN 0164-0925. doi: 10. 10.1145/35777. 357176. /tt.itttss//ii..rg//11....
[25] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429 450, 2020.
[26] Shuo Liu, Nirupam Gupta, and Nitin H. Vaidya. Approximate Byzantine fault-tolerance in distributed optimization. In Proceedings of the 2021 ACM Symposium Principles of Distributed Computing, PODC'21, page 379-389, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385480. doi: 10.11457346504444477990
[27] Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, $4:14606-14611 2021.
[28] Yurii Nesterov al. Lectures on convex optimization, volume 137. Springer, 2018.
[29] Maxence Noble, Aurélien Bellet, and Aymeric Dieuleveut. Differentially private federated learning on heterogeneous data. In International Conference Artificial Intelligence and Statistics, pages 10-10-55 PMLR, 2022.
[30] Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions Signal Processing. 70:1142-1154, 2022. doi: 10. 109/TSP. 2022.3153135.
[31] Christopher G Small. A survey of multidimensional medians. International Statistical Re- view/Revue Internationale de Statistique, pages 263-277, 1990.
[32] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over-parameterizee models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pages 1195-1204. PMLR, 2019.
[33] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking Byzantine- tolerant SGD by inner product manipulation. In Proceedings of the Thirty-Fifit Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviy, Israel, July 22-25, 2019, page 83,
2019.
[34] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robus. dis- tributed learning: Towards optimal statistical rates. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pages 5650-5659, PMLR, 10-15 Jul 2018. URL htttp::/pproeeedingg. mlr wwwppp/ssssppppee pre..eeee//////yiaaaattttt http://pooeciiigg.....ppsss////s
12

---

Organization of the Appendix
Appendix contains the proof of Proposition] | Appendix contains the impossibility result shown in Theorem Appendix C contains the convergence proofs concerning Robust D-GD (Theorem 2 Corollary and Proposition Appendix D presents our experimental setups.
A Proof of Proposition
Proposition 1, Assume that the global loss L* is J-Pl. and L-smooth, and that for each i E H local loss L is convex and smoshhhth. Denote Lmaax maxxeH Lg. Then, Assumption iis satisfied, i.e., the local loss functions satisfy (G, Ba-BBB--rraaa -rrrddient dissimilarity, with
2I
G²
Σ [VL,(0.)1 ECH
and
B²
1.
(4)
HH
P
Proof. Let 0 Rdd. By bias-variance decomposition, obtain that
Σ VV,(0) (L)(())1
1
Σ - EE
(8)
H.
H
iEH
Using triangle inequality, we have
[V)1 (0) VL.(0.) VL,(0.]1 S - + |VC (O.))))))) For any pair of real values (a, b). we have (a + 6)2 < 2a + 26a. Using this inequality with (0) (e.().) and b (o.)) in the above, we obtain that
(0)- < VL. (O. + 2
Using the above in { we obtain that
(O) (LH(0)) 7
2 22 +
H
iEH
- [0)12
(9)
For all E H. since L; is assumed convex and L--mootth we also have (see 28 Theorem 2.1)5 for all 0' Rd that
(,) 2 C,(0') + (V),(''), 0 0²) |VC V2)(1')12 2L, Substituting 8¹ 0g the above, we have (,) C,(),) - (V., 0 - 0.) 2 and (VV - (0.)ll < 2L, (C,(0) - C.(O.) - (O.), 0 - 0z)). Therefore, as Lmax = maxie L., we have
2L Σ (c,(0) (C,(0)-(,(0.) (V., -- 0-0.)) (10)
(0) VC.(0.)11
H
171
Recall that Lu [म|
Eien L. Thus, THT Eien (..))) (0,)),,, and 1 EIEN (C, Vz = 0. Using this in (10). and then recalling that Lize is assumed p--L., we have
Í.
[VC VC, & 2Lmax (Cn(0) - (0.) < Linax [V
Σ
H
KEH
Substituting the above in obtain that
1
Σ |VV,(00)
(L)(1))
Imax 1
|
+21H 17
1 Σ [ICC,(00)111 -VC,10.11--1VCxx000011
7
+ (2 - [V)2)
[V2((0)))1
HH|
EH
The above proves the proposition.
13

---

B Proof of Theorem !
Impossibility Result
For convenience, we recall below the theorem statement.
Theorem 1. Ler f n/2. Assume that the global loss Lu is L-smooth and u-strongly convex with 0 < μ L. Assume also that the honest local losses satisfy (G, B) -grrdiinn dissimilarity (Assumption)) 7 with 0. Then, a distributed algorithm can be e e-rrsiiiie only if
1 8p n2 B G
f
< 2+ 2+B² B
and E
B.1 Proof outline
We prove the theorem by contradiction. We start by assuming that there exists an algorithm. that (f, E) r-rsiiiie when the conditions stated in the theorem for the honest workers satisfied. We consider the following instance of the loss functions where parameters a and K are positive real values, and E Rd is vector.
(,) Li(0) = a 100 21?
Vi fI.
f},
(11)
2
(,(0) = (0) = 2K 101
Vi E [ + 1,..., - 1b.
(12)
(, = (i) = a
2 |1012
Vi (n f + m.....
(13)
We then consider two specific scenarios, each corresponding to different identities of honest workers: S {1...., n - f} and S2 = {f 1, 1....,n), n). That is, we let S1 and S2 represent the set of honest workers in the first and second scenarios, respectively. Upon specifying certain conditions on parameters a, K and we show that the corresponding honest workers' loss functions in either execution satisfy the assumptions stated in the theorem, i.e., the global loss functions are L-smooth ju-strongly convex and the honest local loss functions satisfy (G, -)-graiient dissimilarity. Since algorithm A is oblivious the honest identities, it must ensure (S,e) resiileeee in both these scenarios. Consequently, we show that cannot be lower that a value that grows with K and || Using this approach, we first show that the lower bound on can be arbitrarily large when 2 2+ Then, we obtain non-trivinn arivirivial lower bound on the case when < 2-B7 The two scenarios, and corresponding loss functions, used in our proof are illustrated Figure
K
K
2
Figure 5: Illustration of the proof of Theorem 1 It impossible distinguish between the scenarios depicted above, corresponding to local honest losses scenarios and S2. We set || to grow with K. and show that (G, B) -))grrdientt dissimilarity holds in both scenarios. A large means that the minimum in the first scenario (left) is close to 2, while it 0 the second scenario (right). Thus, any algorithm must make an error in the order of ||~||? which itself grows with K. When f/n 2 2+B7. show that K and thus can be made arbitrarily large.
make use of the following auxiliary results.
B.1.1 Unavoidable error due to anonymity of Byzantine workers
Lemma below establishes a lower bound on the optimization error that any algorithm must incur in at least one of the two scenarios described above. Recall that S ( -f] and
14

---

S2 = (f 1, l..................... n2. Recall that for any non-empty subset S S [rl] we denote
Cs( = |S|
E1(0 and L.S = min (+)
RER4
EE
Lemma 1. Consider the setting where the local loss functions are given by 11 this particular case, the following holds for all 0 E R
and
13
In
a
max (0s - S1, (s) - L,
|
n-25 R-/
n-jaa
The proof is deferred Appendix B.3
We next analyze the (G, B) -ggadientt dissimilarity condition for the considered distributed learning setting.
B.1.2 Validity of (G, -raddient dissimilarity
In Lemma 2 below we derive necessary and sufficient conditions on a, K and for (G, -gradientt dissimilarity when the loss functions are given by (1).. 12) and (33).
Lemma 2. Consider the setting where the local loss functions are given by Denote
and
13
A = f(n 2f)
((1 (1--1) B
n1 2f
B²) a + (1 (1- 11 2ʃ
f B²
2(1
2(1
a²
(n - f)2
K2
K
f2n=2
1
f(n 2f)
||
A2 (n - f-)(((n 22) + fa)
K
aa)a
K 2
and Aa
((n 2f) + fa)*
K2
(14)
Suppose that S1 = (I....nn- f} denotes the set of honest workers. Then, the honest workers satisfy (G. B)- -gggddientt dissimilarity if and only if
0,
A3 S G2, and || < A1s G2t)
(15)
The proof of Lemma deferred to Appendix B.4 Since Li corresponds to Lun with 0, the result the lemma above also holds true when the honest workers is represented by set S2 = 1,....,... n). Specifically, we have the following lemma.
Lemma 3. Consider specific distributed learning setting where the local loss functions defined in (1). 12) and 13). We denote
A = f(n 25)
(1--7T"
ni 1
2/
B2
B2)
-
2(1
B²)
a + K
(1--- B2 a²
a²)
(n f)²
K2
Suppose that S2 = {f f....,,,,n denotes the set of honest workers. Then, the honest workers satisfy (0, B) gradient dissimilarity if and only if A1 < O.
We do not provide a proof of Lemma 3 it follows the proof of Lemma verbatim upon simply substituting z = Oge and 0.
B.2 Proof of Theorem I
We prove the two assertions of Theorem | i.e., the necessity of 2+ and the lower bound separately in sections B.2.1 and B.2.2 respectively.
B.2.1
Necessity of L
2
In this section, we prove by contradiction the necessity of 1 " 24 by demonstrating that can be arbitrarily large if 24 Let 0 n/2, L, G > 0 and B 2 0.
15

---

Suppose that 2 B+ or equivalently B² > "
3ー" 2 Let be an arbitrary (f. rresilieet distributed
learning algorithm. We consider the setting where the local loss functions are given by and (3 and the corresponding parameters are given by
12
f p.
(16)
K' is an arbitrary positive real number such that
n1
2f
K 2 max
1
(17)
a
f
L
and 2 E R2 is such that
G T1 2 20
|||||
K
(18)
Proof outline. In the proof, we consider two scenarios, each corresponding to two different identities of honest workers: S = {1,..... .I,...,7. f) and Sg {f + n... For each of these, first show that the corresponding local and global honest loss functions satisfy the assumptions made in the theorem, invoking Lemma Then, by invoking Lemma[ we show that e is proportional to K which (as per (17) can be chosen to be arbitrarily large. This yields a contradiction to the assumption that A is (f, E rresilieen proving that e reesilineee is generally impossible when f 2 24
First scenario. Suppose that the set of honest workers is represented by S {I,..., - f}. From and we obtain that
1 S
(((0) = Ci(0) - + n n-2f nl n- (0)
Ls. (0)
iES
a 10 x|| + n2 - 2f 1
n1 f 2K 1101
Substituting, from 16
n- ls in the above we obtain that
Cs, (0) = 11 110 - 211
n 2
|10113
(19)
2
2K
Therefore,
vLs, (0)= (0 2) + n n- 2f 1
1u n n-
f K 0. and Ls (0)
la,
(20)
K
where La denotes the identity matrix of size d. From 20 we deduce that Ls, (0) is
n-2f + H
n-f
smooth and (n=2f + 11) -strongly convex. From 17 we have K 2 1 n-2f I-
n- 2f n-f
D-p
This implies that 2-2 1 p u 1 L. Clearly, (-2f n-f
n-f + 2 μ. Hence, the honest
global loss function Ls, is T.-smooth fu-strongly convex. Next, invoking Lemma 2 we show that the honest workers satisfy (G, B)-gradient dissimilarity. We analyze below the terms A1, Ag and A3 introduced in Lemma 2 in this particular scenario.
Term A,. Recall from Lemma 2 that
A = ((n - 2f) (n - f)²
25 25
n
B²
K2 - 2(1 2(1+BB) a K
B²) (1-
+ a²
n-
f
Since we assume B² > 7 we have
n-2f
- B²
< 0. Using this in the above obtain that
n-27
A < f'n - 2f)
f (1--122 B²
n- 2f
K2 2(1 + B²)
(n f)²
K
f(n - 2/) a ((1 ((1- n
25
B2
2(1 + B²)
(n f)2 K
aK
16

---

As K > O, and by 17
K 2
1 2
(1- 1-==21g B*)
Therefore, 1+ B² 1+ 2 ak (1- (1- B²).
1
1+B²
Using this in the above implies that
f(n - 2f) a
f(n f(n ( a (n f)z K
A -
(1+ B²) v
(21)
nn f)² K
Term A2. Recall from Lemma that
fn-22fje A2 (n- f)((1( -2f) + fa)
1 1 k=
K -a)
(22)
Therefore, as K > 0 and we assume n2 > 2f, we have
1(n - 2f)o
|| A2ll 2 (n [)((n 2 - + +fa)
K² ||=1|
K
f(n - 2f)a)
(1
n2 -2-25- j
)
(a
1 2
1
|E
|=
(n fi5a/
K
K2
K
K2
As K 2 1 > 0, we have (a- k) 1 a. Thus, from above we obtain that
à
2
1|
a K2
Substituting from (8) i.. ||=112
1
K, in the above implies that
n-2f 20
f(n 2f) G²
| <
(23)
(n f)2 K
Term Ag. Recall from Lemma 2 that
f(n - -2f)a
||
Aa =
((n - (n2-ff) + +fa)² K2
As K > 0 and n 2f, we have
Aa f(n a ||2|1
2
||2|1
f2a²
K2
f
K2
Substituting
||
=
f
K (see
, and then recalling that K 2 1 (see 17 ), yields
2-2f 2a
G2
G
Ag <
20K
2
Therefore,
G2
G A3 > 20.
(24)
Invoking Lemma] Using the results obtained above in 21 23 and 24h. we show below that
the conditions stated in (15) of Lemma ( are satisfied, i.e., A < 0, Ag S G2 and ||Aa]| <
Ai (A3 G Hence, we prove that the local loss functions for the honest workers in this particular scenario satisfy (G, -)-gradient dissimilarity.
First, from
21 we note that
A S f(n 2f) a
(n- 1n-ft f)² K 50.
(25)
Second, as a consequence of (24). As < G². Lastly, recall from (33 that
|| < f(n - 2f) a G2
(n - f)² K 2
17

---

As fin-2f) (n-1)² R < A (from 21 from above we obtain that ||A2|| S A Φ² G 2200 and G S 2( As) (from 24
T Therefore, as
|| < A1 G²).
This concludes the analysis for the first scenario. We have shown that the conditions on smoothness. strong convexity and (G, B) -gradient dissimilarity hold in this scenario.
Second scenario. Consider the set of honest workers be S2 {s ...., n). Identical to (9
with 2 = 0, from 12 and 13 we obtain that
(0) - 1
n2 n- 1 n1
11012
2K
Therefore, similar to the analysis of the first scenario, the global loss Ls, satisfies L-smoothness and ju-strong convexity. Moreover, Lemma 3 in conjunction with the deduction in (25) that A 2 0, implies that the loss functions the honest workers this particular scenario satisfy (0, -g-grddient dissimilarity, thereby also satisfying (G, B)-gradient dissimilarity.
This concludes the analysis for the second scenario. We have shown that the conditions on smoothness, strong convexity and (G, B) -gradient dissimilarity indeed hold true in this scenario.
Final step: lower bound on in terms of K. We have established in the above that the condi- tions of smoothness, strong convexity and (G, B) -grrddiettt dissimilarity are satisfied in both the scenarios. Therefore, by assumptions, algorithm A must guarantee (f, rressiliecee in either scenario. Specifically, the output of A, denoted by i must satisfy the following.
max { [ss (0) La,S1: (0) Lo,82 SE.
Due to Lemma the above holds true only if
a²
||:11
(26)
R1 2-2
f
n-7
Recall from (17 implies that
1
K
1
n-2f
Therefore, we have (n - 2f) I
L-a fa, which
2
a²
a²
P f
a
n-f
K
L-H
n-
L
n
Using the above in 26) and then substituting a " (from
16
implies that
12
||:1|--
8T.
Recall from 18) that ||21|² = f
C²
K where a 7 7-ps from above we obtain that
n-2f 2a
12
f
f
2 16L n - 2f
K
16L (n (n G²K. G.K.
-
That is, s grows with K. Note that the above holds for any arbitrarily large value of K satisfying (17) Therefore, e be made arbitrarily large. This contracts the assumption that A (J, e)-resilient with a finite e. Hence, we have shown that (f, E) -)-reiileence is impossible in general under (G, -gradieen
dissimilarity when 2 2+
Concluding remark. critical element to the above inference on the unboundedness of is the condition that A₁ < 0, shown in (2I) Recall that
A
f(n 2.f)
(( (11--
7 2f
B2
1 K2
1(22(1
f 1 n. 2f
B2
a + a²
B² )
(n 10-f) f)²
K
The right-hand side in the above is negative for any large enough value of K as soon as 1- カー B
0 or, equivalently, f. > 1
2+ However, the case when 1 < 24 K cannot be arbitrarily large we were to ensure A₁ S 0, i.e., K must be bounded from above. This constraint on K yields non-trivial lower bound on We formalize this intuition in the following.
18

---

B.2.2 Lower Bound on
In this section, we prove that E 2 the arguments presented in Section B.2.1 the assertion holds true when ! , 2 1 we assume that L 2+ or equivalently <² " "
Spt (2+ BA) G². Let < < n/2, and G, B 2 O. Owing to
1
12 In the following.
Let A be an (f. -rrssiieett algorithm. We consider a distributed learning setting where the workers' loss functions are given by (11 (12) and (13) with parameters a, K and set follows.
r (1 B²),
and
K
(27)
1 ( (1-
1 2- B3
We let z be an arbitrary point in I such that
(n 11-f9 f)²
G
||
K.
f(n ( 2f)
a(1 + B
Note that, as = (1 + B²). we have
+ B
K
(28)
11
2-
1 B2
2 1
a
Therefore,
(n- 15-fp f)²
1 n n- n2 B²
||=1|2
f(n 2f) (1 B2j2 K²
(29)
From 28 we also obtain that
(1
n- --17 B32
n 2f
f n n-
n 2f
at - a= n-2f 2 + +
fB²
0
a
n f K
f
1 B
(n- - f] B²)
(30)
B
Proof outline. We consider two scenarios, each corresponding two different identities of honest workers: S = (1, -1,...,,7 f and S2 = {f + 1,...,n). For each of these, we prove that the
corresponding local and global loss functions satisfy the assumptions of the theorem, mainly by invoking Lemma 2 Finally, by invoking Lemma D we show that ( ( -.r--sileeeeeee implies the stated
lower bound on
First scenario. Consider the set of honest workers to be S = {l..... f}. From and 12 we obtain that
f a
110 2|1² + n n 2f 1101
(0) = n f2
(31)
f 2K
Therefore,
2- n
2f Ia n n K
VLs, (0)= n - (0
2)
F and V (0)
- K
n -
where La denotes the identity matrix of size d. The above, in conjunction with 30 implies that Ls, is 14 -smooth
[- -strongly convex. As T+ μ (see 27 ). we deduce that Ls, j-smooth μ--strong convexity. Recall that μ L, therefore Ls, is also L-smooth. Next, by invoking Lemma [ we show that the local losses for the honest workers in this scenario also satisfy (G, diissimilal
We start by analyzing below the terms A1, As and Ag introduced in Lemma in this scenario.
Term Aj. Recall from 14) in Lemma that
A = [(n - 2f)
n1
2f
B²
K2 2(1 +
B²) K
+ a²
(n - f)²
f
2f
19

---

(2-13² A1. Substituting in the above, from Let A/ = /[-
28
K
1+
we obtain that
1- " 27 B
A1
(1-1-- 2f B²)
1 2- B
-2-2(14 + B²)
n- B
a
+
a²
)
1
f
20)
1+ 12
1 Ba
2
(1- B3)
(1- n- B²
2
1 n - 2f B²)
-1)
(1+ (1+
1 n 2f B²)
2
1 n n- 2f B²)
(1
n1 2f B²
- (11 + -(1+ B2)²)
(1 B2)²
f
1 - B²)
n-27
n 2
B
B² + B*)
- -1122B2
2B² + +B4))
(1+ B2)²
11 - 21
- B
(1 - nー B2) B² (n-
aa n 2-2
B² 2 n 2f
-
(1 )
f
11 - 2f
B2) f(n-2f) -
Recall that A/ [ff
(n- [n-f)²
A1. Therefore, from the above we obtain that
(1 11- 1 2 B²
A
B²a².
(32)
(1 + B²)²
Term A2. From 14 in Lemma and 330 we obtain that
f(n 2f)a
1
1
f(n 2fn (n- f)²
1 a
1
A2 (n M) 25) + fa)
K
a
K
(1 (1+ B²)
K
From 28 we obtain that a 1/ =a
1+
B²
a
n-2f 1 a. Using this above we obtain
n-f B²
that
||A2|| 2
[(n 2f) (((n-22)
(n- (n- f)2
(1+B²)²
( n n--fa f
(n-
)²
2
B
2 1=1
(
f
2
B²a
n n
(1+
B2)a
K2
12
K2
(33)
Term Ag. From
14 in Lemma
2 and (30,. we obtain that
f(n - 2f)aa
|
f(n 2f)
(1+ + B²)² |
Ag ((n -20) + sa)² K2 fn
(34)
K2
||=1|2 = (n- (1- -- B²2
Substituting in the above, from 29
K2 we obtain that
fn-211 (1+B4y
f B² G².
AA = 1 n 2f
(35)
Invoking Lemma? Using the results obtained above show below that the conditions stated in (5) of Lemma 2 are satisfied, i.e., A₁ < 0, A3 < G2 and || < A (A3- G²). Hence, proving that the local loss functions for the honest workers in this particular scenario satisfy (G, -rgaadiett dissimilarity.
Since we assumed that B²
< n 2-
32
implies that A, S 0 Similarly, 35 implies that
respectively, A = (1- n ay B²)
As < G2. Substituting, from
32 and
34
Baa² and Ag =
(1+
2 || f(n-2f) (1+ B2)² k² we obtain that (x-1)²
(1 (1- f B²)
A1 G²)=
2-
Bed C²
f(n 2f) (n- f)z
(1 + B²)² 2 |
(1 + B2)²
K2
20

---

i.e. ||= = (a-1)² (1-m-17 B²)
Substituting in the above, from 29
G2K2,
we obtain that
sin-2f)
(1-B4)²
(1 1 B²
-
n-2
B²
(22 (Ce-(1-n-
f
B² G²
(1 + B2)²
n1 2- 25
(1- B²)
(n - f)² (1 n-2
(1- 1 B²
f
f f
2
G²
G²
B'Q².
n 2f
f(n 2f)
n2
Recall that (n- f)a (1- (1- B²)
G2
|=|l K
Using this above, and then comparing the resulting
(f-2f) (1+Ba)²
equation with (33) we obtain that
A1 - (
2 B a
|=1l K²
||
This concludes the analysis for the first scenario. We have shown that the conditions on smoothness, strong convexity and (G, B) -gradient dissimilarity hold in this scenario.
Second scenario. Consider the set of honest workers to be S {f 1, n). Identical to (11
with 2 = 0, from 122 and 13 we obtain that
f n n 101 n - f 2K
2f 1
11012
Similar to the analysis in the first scenario, we deduce that Cs, is L-smooth and p-strongly convex. Moreover, Lemma 3 in conjunction with the deduction in (32) that A₁ 2 0 (recall that B² < 2=21), ) implies that the loss functions for the honest workers in this particular scenario satisfy (0, B) -ggaddient dissimilarity, thereby also satisfying (G, B)-gradient dissimilarity.
This concludes the analysis for the second scenario. We have shown that the conditions on smoothness, strong convexity and (G, B) -gradientt dissimilarity hold in this scenario.
Final step: lower bound on in terms of G and B. We have established in the above that the conditions of smoothness, strong convexity and (G, B) B)-gradient dissimilarity are satisfied in both the scenarios. Therefore, by assumptions, algorithm A must guarantee (f, -ressileeee in either scenario. Specifically, the output of A, denoted by i must satisfy the following:
max { (s. (0) Cr (s, Sr Se.
Due to Lemma the above holds only if
f
a²
n-プ
|
(36)
n- n-f
f
+
n-
a
Recall, from 30 that n-2f
n-f K
1
+
n-
a
I+B
Using this in 36). we obtain that
2
a
E 2
n-
f
|| =
a(1 + B²) ||
8
8
I+B²
Substituting, from 27 a = 1(1 + B²) in the above implies that
2
(1 (1+ B²)2 ||
n n-
Substituting, from
29 ||
(n-
(1- B²)
(1
6 K² in the above implies that
f(n-ff)
(1+84)2
2
(1 B²)² (n - f)² (1--~2)
B²)
G²
11 f
[(n - 2l) (1+B2)²
2f )
(1- / B² K²K².
8
8-221 2f
21

---

Substituting, from 27 i.e. K =
in the above implies that
111- -ll Be)
E 1 - 8 20-21 2f n2 2f 2f
(1- )
f B²
G
1
n n-2f
2
G²
1²2 (1
8p
B2
B²
n-
n n-
The above completes the proof.
B.3 Proof of Lemma
Let us recall the lemma below.
Lemma 1. Consider the setting where the local loss functions are given by (1). this parficular case, the following holds for all 0 E Rdd
12
and
13
In
a²
max {Ls, (0) Lr Ls (0) Sx
|
n-2f n-
a
K
Proof. We prove the lemma by contradiction. Suppose there exists parameter vector such that
a
max (s, (0) S. (o) Lr.So
|2/1 = 6.
(37)
n-2f n-f
K
+ n
n- a-
From
and
we obtain that
Ls, (0) n - f
1
f at 110 =1( (n - 2 1
[1013
and
2K
(s) (0) =t= n1 f
1
a |1012 + (n 2/) 2k
1
11013
Therefore, we have
/ n 2f
f
00
fa
2
Ls. (0) Lu.s)
a
2
and
n { K
n -
(n
2l) k
+
fa
n 1 2f 1
f
(0) - Lr,S²
2
n1 f K
Substituting from the above in (37. we obtain that
8 n 2 2f 1
f f K j
max {10- (n 2f) + fa
fa ]
As for any real values a, b, we have max(a, b} 2 (a + b). from above we obtain that
( n - 2f 1
f
) (10- (n 2f) 1 fa
fa
+ +1001()
8
(38)
1 n f K
By triangle and Jensen's inequalities, we have fa (n 20-2 fa = (n 2f) fa 2 0 0
fa
fa
-
2 (n 2f) R fo 2
+ +
*For arbitrary positive real values and b, and arbitrary z E Rd. consider loss function L(0)
||0 - =11² - |1011 The minimum point 0, of L(0) is given by 6_ = a+5 and for any 0, L(0) C(O.)
(a b) ||0 0.1
22

---

Substituting from the above in (38 we obtain that
n1 - 2f 1
f
fa
n1 - f K
n
(n - 2f) K
+
fa
2
f n-f a
n-3 a²
n - 25
S
|| 2 = 5
8 n f K
n
a
n-2
K 12
8
n-2f 1
n-} K
n
The contradiction above proves the lemma.
B.4 Proof of Lemma
Let us recall the lemma below.
Lemma 2. Consider the setting where the local loss functions are given by and 13 Denote
A f(n-ff)
((1 (11-" -
n 2f
1
+ (1 (1- n n B² a² )²)
f
B²
22(1111
B²) 2(1+BB)
(n fn- f)2
f
K2
K
f(n f(n-2f)a
1
K 2, and Ag = f(n - 2f)
|211
A₂ = (n --f)(nn (2(( fa)
K
a
((n 1 2F) + fa)
K2
(14)
Suppose that S1 = (1,...,, n- f} denotes the set of honest workers. Then, the honest workers satisfy (G. B) -ggrdeinntt dissimilarity if and only if
5
As S G2,
and || S AA1AAs G2).
(15)
Proof. Let A E Rd.
As
Σ Lies, [VC((0) [0),
[&T Eies. [VL(
1
S1
[[VCs, (0) we obtain that
VLs, - (0² + B² [VLs (0)1P) VO)
[
IES
1
[V,,00) (1+ + B²) VLs, (0) -
(39)
S
iES
We analyze the right-hand side of the above equality. As S (1,..., J/ from and 12 we obtain that
2ʃ n f
f
[Lnn(0)11
n n- [|V(((0))²
iES,
2ʃ 1
|1011
a² 110 211
(40)
n - f K2
n -
Similarly, we have
1
n - 2f 1
f
(6) J
(L.
0 +
(0- 2)
n f K
n
SES1
(n - 1n-2f) R
+ fa
f
(n- 2f) R + fa
fa
9
az
0
2f) + fa 2
n1 f
n1
n - f
(n
Ao
8.
Denoting in the above
(n - (n-ff) 1 + fa
Ag
(41)
n n-f f
23

---

and
fa
0, = (n (n-2f)x R + fa 2,
(42)
we have
(0) = Ao (0 0.). The above implies that 0, is the minimizer of the convex function Ls. and
|Vs, (0)1l = A ||0 - 0.112.
(43)
Substituting from (40)
and
43 in 39 implies that
VVC
())
VLs, (0)1l - G² - B2 || (0)1
S1
1E
2f 1
101 + f 2 10 - =||² - (1 + B | 110 - 0.11 G2.
n- ʃ K
f
Now, we operate the change of variables X = f - 0., and rewrite the above
1
(V), VLs, (0)11 G² - 2² VLs, (0)1
1
iESL
2f 1
f a² ||x + 0, - =112- (1 B²) ||X]] G2
|X + 0=
n n- f K2
11 -
n- n-2 1
(Ixx]] + 110.11 + + 0.)) + 1 -_ (IxII + +100 2 0, - -2)
n- f K2
-11 + 1B2 ) | G2
(n Rt + fa²
||X|| +2 X. n n-2f 2f 1
f a 20 2)
(1 + B²)
0. +
f
n f K2
2 1 n
f
|00_11
o² 110. -=1²-C0
(44)
K2
n1
Ag
Next, we show that A1, Ag and Ag defined in 14 can be equivalently written as follows.
A (n 2f) Rz
+ fa²
2f 1
(1 B²)
A n - f K2 12 - f
0_
+
a² a0= 2) and
n
Ag = n 1--2 2f 1
f a² 110 - 2|12
f K2 |10.11
+
n1
(n- 21- + ta カ-
Term A₁: Substituting from 41
i.e. Ao
we obtain that
(n - (n-2f) 1 K" + fa²
(n- K²
+
fa²
(n 2f) K + fa
2
(1+ (L+B))A33
B²)
n1 n-1
n1 S
n1 n- S
(n- 1-2 R2
+ +fa²
n-
1
f
2f(n 10d-2f1 2f) a (n - 5)² K
(1 (1+B) B²)
[ f
+
a +
n1 n- 1
K2
11
n 2
2
n1 f
s(n 2f) a
- (1+ + B²)
K² - 2(1 + B²)
n f
2
(n f] K
f
(1+ B²) (1+B²)
a
n f
f
n 2f
f
1
2(1 + B2) f(n f(n 2f) a
f
n1 - 2f
B²
+
a²
B²
n /
n-
n-
K2
(n- f| K"
n1
s
f(n -2-2ff 2f)
(n f/²
(1- 2
f
B2
K2
1
-
2(1 + B²)
)
K
a
+
1 -
n - 2
f
B²
a
24

---

Comparing the above with A1 defined in (14 implies that
(n 2f) 1 + fa² - (1+ B²) = A
(45)
Term A2: Substituting from (42
i.c. 0₂ 1n-2f)++fe 2, we obtain that
n -- 2f 1
f
+
(t2- 2)
f K2²
-22 1
fa
fa
2
a²1
(n - 21) + fa 2 2)
n n-f K²
K + (
fa
n - f
-2 1
fa
f a²
(n - 22)
n K2 (n - -2f) K + fa
11 - I
(n 2f) K + fa
- [(n-2f)e
(n [) 2f( k fa) K K 2
Comparing the above with A2 defined
(4) implies that
n 2f 0. +
2 (0. 2) = A
(46)
n f K2
11
Term A3: Similarly, substituting 0, (n-2f)
tfa 2, we obtain that
21)
n - 2f
f
||0-11 2 +
a² 110- 2|l
K2
2f 1
fa
2
f
fa
2
||211
a²
-11
||=11
n f K2
(n x + fa
n1 f
(n + + fa
n - 2f
(
fa
f a²
(n tे saa )
- (n2) 1/ 2
1|=11
||
11 f K2 (n 2 +fa)
f(n a ||=1|
(fn + fa)² K²
Comparing the above with A3 defined in 14 implies that
n n-2f
||0_11
n 110_ -=12
a
=112 As.
(47)
n f K2
Substituting from 45
46) and 47
in 44
we obtain that
VVC VLs, (0)]l2
G²
B VLs, (0)1 A, || +2 A2) + Ag - -2.
S
iES1
Therefore, by Assumption I the honest workers represented by set S1 satisfy (G, B) -)ggriiintt dissimilarity and only if the right-hand side of the above equations less than or equal to 0, i.e.,
A || + 2 A2) As G S 0, for all X = 0 0. Rd
(48)
To show the above, we consider an auxiliary second-order "polynomial" in E RRd, P(x) = ||==||² + 2 (ar, b) + where b Rd and a, E IR. We show below that P(x) for all Rd if and only a, c < and A = |bb|2 ac S O.
Case 1. Let # 0. In this particular case, we have P(x) = a (II= d b112 2) Therefore, P(x) < 0 for all æ if and only if a < 0 and A 50 0.
Case 2. Let a = 0. In this particular case, P(x) = 2 (x, b) + c. Therefore, P(x) $ 0 for all x and only if c < 0 and A = |[b|| = 0.
Hence, 48 is equivalent to Ai < 0, This completes the proof.
Ag - G² 20, and ||2]|² - AA(A33 G22) 00
25

---

C Proofs of Theorem and Corollary
1 Convergence Results
C.1 Proof of Theorem
Theorem 2. Let 0 < f < n/2. Assume that the global loss LH is L-smooth and that the honest local losses satisfy (G, B) gradientt dissimilarity (Assumption 7). Consider Algorithm Tith learning rate f. If the aggregation F is (f, r---busstt with xB² L, then the following holds for all T 2 1.
1. In the general case where Lu may be non-convex, we have
T-1 T
RG2
2L (Cx( L.,
[V &
+
KBB
1-kB22)T
2. In the case where Lu is p-PL, we have
2p (1 (132)BB) + - - (Cu(fu) - L.,H)
kG2
Cu((r) - L. S
C.1.1 Non-convex Case
Proof. As Lu is assumed L-smooth, for all 0, l' Rd we have (see Definition 2
L 110 011
Cx( - (0) s (V), 0) + 2
Let t E {O...., T 1}. From Algorithm] above 0 0, and 0' 8.+1, we have
recall that 0z+1 = 0s - Ro. Hence, substituting in the
(x(01+1) - Cx(())) - (VCx( R,) + 2 2
(49)
As (a, b) 2 [|a||2 + -1b1112 -Ila ||a=bl²² -11²)) for any b E Rd,, we also have
(O.), Ra) = 1 (IVI + [| [L.((.)) - -Rali))
Substituting the above in 49) we obtain that
+ [R IVV 11 - R.1l²) + 1 ""= ||,
(x(0x+1)- - ((,) < - 7 [Vxx(0)11 2 (1- -0 |R.
+ + [IV[x((0.) - Rell²
Substituting 7 = 3, the above we obtain that
Cx(0++1) (x.) 1 [0,)
1 |R, (LH
(50)
2L
2L
As assume the aggregation F to satisfy (J, (Jbbuuttssssssssss by Definition
we also have that
RR - VL)(1 rl r s6nh)
(
Σ
(
91
Dt
1H
H
H
IEH
EH
iEN
K 176
(V.) - (L)()))
(51)
IEM
Besides, Assumption implies that for all 0 E Rd we have
V 1
H
EE
Using the above in 51 yields
RR - 2 RG2 + RB [Vx (0,)11
26

---

Substituting the above in 50 yields
(o(0)+1) (0r) S
2L [VLx(00)1++ + 2I. (RG² + RB² xB22 IV (0.1)))))
(52)
Multiplying both sides in (52) by 2L and rearranging the terms, we get
[1-BB² (0))l S xG² +2 (Cx(0,) - Lx(00+1)).
(53)
Recall that t in the above was arbitrary in {O...., T 1}. Averaging over all {O.... 13 yields
T-1 (1 11= T
2L T-1
2L
Σ
[
2 xG +
Σ
(Cx(0,) (H(+))1)) = kG2 + T (Cn(00) Cre (0T))
T
1=0
2L
S xx + (Cz((06) Lx,
T
Finally, since we assume that 1 1-xB3 0, dividing both sides in the above by xB² yields
1 T Σ [VCu(0.))1
kG2
2L (B)) L..
+
xB²
xB=xBTyT
The above concludes the proof for the non-convex case.
C.1.2 Strongly Convex Case
Proof. Assume that Lu is p-PL. Following the proof of the non-convex case up until (33) yields
(1 xB²) (0,)l xG² + 2L (C.) (x((++1))
=G 21 (C,) L.. f.. (x(44+1))
Rearranging terms, we get
2L (CH(0i+1) x) S nG² (1- xB²) <B>>BBB)|LVHH [[.)l + 2L (CH(0)) Cr,z))
Since Lu is J-PL,, per Definition 3 we obtain
2L (0(4)))))))))))))))))))))))))))) L., S xG² 22 (1 <B²) (Ln(0.) C2,x) + 2L (Cx(()) L.,H)
G2 + (2L 24 (1 xB²)) (Cz((.) - L.,H).
Dividing both sides by 2L, we get
1G2
Cu(0++1) - Lu,H 5
+ (1
RB²) (Cx(0.)) L,,n))
(54)
2T,
Recall that is arbitrary in f0...., 13. Then, applying (54) recursively (on the right hand side) yields
(x(00+1) Lo.H 5
RG
1
1
# (1 - -B²)
2T
I
k=0
p1 (1 (1-xB3) kB2)) ++1
(Cn(Bu) - -L.,))
KG2
1
+ (1 4. (1 (1-kB²)) 1+1 (Cu(fo) L.,N)
11
2L 1 1- (1 - + (1 - xxx2)))
I (1 / (1 - xl- 1+1
KG2
(cx((0)-L..H))
24 (1 xB2)
L
Using the fact that (1+ 2)n R < nt for all x E R and substituting t = T - 11 yields
24 (1 - xB²) + =0 (Cn((b)) - C.,H)
kG2
Lu((r) - L, S
This concludes the proof.
27

---

C.2 Proof of Corollary
1
Corollary 1. Assume that the global loss Lu is p-PL and L-smooth, and that for each i H. local loss Li is convex and smooth. Denote Lmax = maX4ER Li and assume that k( SLymax - 1) S 1. Consider Algorithm with learning rate ? + F is (f, ro)rouus,,s,, then for all T 1, we have
(n( L. S
3x
[V,( +e # (Cu(0e) Lr,
176
KCH
Proof. Invoking Proposition with
1 we know that the loss functions satisfy (G, B)-gradient dissimilarity
2
B² 2 Lmax 1.
G²
[L)(0.))
176
EE
Moreover, since we assume that 6:3 Lmua - 1) $ 1, we have
xB² x22 Lmax 1)
Lmax nk(3 1
2
1)
+ 3
2
1
Therefore, since the global loss Lu is 4-PL and L-mmooth, we can apply Theorem
2 to obtain
2p (1 kB2) + ((I-BB)) (Cn(fo) L..H)
kG²
Cu(Or) L,,3 S
S 2p
GG te # - (Lz((0o) -c.)
3x 1
[V,( + T (Cu(0p) - -L,,H).
[
icH
This concludes the proof.
28

---

D Experimental Setups
In this section, we present the full experimental setups of the experiments in Figures 2 and All our experiments were conducted on the following hardware: Macbook Pro. Apple MI chip. 8-core CPU and NVIDIA A10-24GB GPUs. Our code is available online through this link
D.1 Figure
! brittleness of G-Gradient Dissimilarity
This first experiment aims to show the gap between existing theory and practice. While in theory G-gradient dissimilarity does cover the least square regression problem, we show that is indeed possible to converge using the Robust D-GD Algorithm with the presence of 3 Byzantine workers of 10 total workers, All the hyperparameters of this experiments are listed Table]
Number of Byzantine workers
f = 3
Number of honest workers
n - ʃ =
datapoints in mg LIBSVM [0] selected uniformly without replacement
Dataset
Data heterogeneity
Each honest worker holds one distinct point
Model
Linear regression
Algorithm
Robust D-GD
Number of steps
T 40000
Learning rate
0.001
Loss function
Regularized Mean Least Square error
lz-regularization term
A
= 1/v7
Aggregation rule
NNM coupled with CW Trimmed Mean 34
sign flipping fall of empires
33
Byzantine attacks
little is enough 5 and mimic 20
Table 1: Setup of Figure
experiment
29

---

D.2 Figure
2 empirical breakdown point
The second experiment we conduct tends to highlight the empirical breakdown point observed in practice when the fraction of Byzantines becomes too high. Indeed, while existing theory suggests that this breakdown point occurs for fraction of 1/2 Byzantine workers, show empirically that it occurs even before having 1/4 Byzantines. We present all the hyperparameters used for this experiment in Table
Number of Byzantine workers
from f to f =
Number of honest workers
72 f= 10
Dataset
10% of MNIST selected uniformly without replacement
Data heterogeneity
Each worker dataset holds data from distinct class
Model
Logistic regression
Algorithm
Robust D-GD
Number of steps
T 500
0.05
if
S
T
<
350
0.01
if
350
S
T
< 420
Learning rate
0.002
if
420
S
T
< 480
0.0004
if
480
T
500
Loss function
Negative Log Likelihood (NLL)
(z-regularization term
10-1
CW Trimmed Mean
34
Krum 77.
Aggregation rule
NNM
CW Median
33) geometric median [30]
Byzantine attacks
sign flipping
Table 2: Setup of Figure experiment
30

---

D.3 Figure 3 comparing theoretical upper bounds
In the third experiment, we compare two enrors bounds, i.e., 1/n- 1/x-12+ G and 1/n-25 G2, guaranteed for robust D-GD under (G, B) B-grrdiient dissimilarity and G-gradient dissimilarity, respec- tively, on the MNIST Dataset. We use a logistic regression model and the Negative Log Likelihood (NLL) loss function as the local loss function for each honest worker.
Before explaining how we compute G and (G, B), let us recall that the local loss functions of honest workers are said satisfy G-gradient dissimilarity for all Rd we have
Σ
&
H
IEH
Similarly, the local loss functions of honest workers are said to satisfy (G, B)-grudient dissimilarity if, for all E Ed we have
Σ V G + B VLx(0)]
H
iEN
Evidently, G and (G, B) difficult compute since has to explore the entire space to get tight values. In this paper, we present first heuristic compute approximate values of G and (G, B): We first compute A. by running D-GD without Byzantine workers, then we choose point Og. that arbitrarily far from 0.. Here we choose 0n = (1e4, .... le4) E Rd with d = 784 for the MNIST dataset. Given 0, and 0g we construct 101 points Oo 0100 between O, and Og such that
0- + (1 1
0.
1
x 0o WE ..., 100)
100
and then compute
1
ΣiEN (f:) (L)(111 and [V:ll for all t E
[H]
{0, 1.2, ..., 100}. We set
G
Σ VV. VLH(0,)11
max
1003
iE
Also, compute the couple (G, B), first consider 100 values of B 0, p-2
then compute
1
G
VL D [L)(
E 1E.0.1.2....100
[H|]
and finally
f (B) n (2 B
(G, B) arg min
G
we show the different values 1/n- (2+ n2)s G and f/n-2f 25 S for f 1 where there is always n - f = 10 honest workers.
In Figure 3
31

---

D.4 Figure 4 matching empirical performances
In the last experiments of the paper, we compare the empirical error gap (left-hand side of Corollary ! with the upper bound (right-hand side of Corollary T..
Let us first recall Corollary T
Corollary 1. Assume that the global loss LH is μ-PL and L-smooth, and that for each i E H. local loss L; convex and L--mootth. Denote Linax = maxieH Li and assume that k( 33omux 1) S
Consider Algorithm
7 with learning rate 7 F (i)rruuss then for all T 1, have
3x
Cx(OT) L..H
[VC, +e #1 (Lz((0)) L.,
H
iCH
We first give all the hyperparameters used for the learning in Table and then explain how computed J4, L., k and 0,.
Number of Byzantine workers Number of honest workers
from to 19
n f = 20
n f datapoints in mg LIBSVM [0 selected uniformly without replacement
Dataset
Data heterogeneity
Each honest worker holds m distinct point
Model
I Linear regression
Algorithm
Robust D-GD
Number of steps
40000
Learning rate
7 0.0001
Loss function
Regularized Mean Least Square error
E-regularization term
x= \/ 1/v7
Aggregation rule
NNM S coupled with CW Trimmed Mean 34
sign flipping fall empires 33
Byzantine attacks
a little is enough S and mimic 20
Table 3: Setup of Figure experiment
Computation of μ and Let be the matrix that contains the vector data points and the fzreegularization term, we have
1 11 1 (
1 x
eig eigmax
P eigmin
(55)
where for any matrix A E gaxd eigmax and eigmax (A) refer to the maximum and minimum eigenvalue of A respectively.
Computation of k. We recall that by definition, an aggregation rule F: Rddx Rd is said to be (f, k)-ruuustt if for any vectors æ1...., E Rdd and any set S C [n] of size n - f. the output F(x1,..., Fn) satisfies the following:
| Isll
1x E3
where vs == [3] Eies
32

---

Hence, as done in [3, we estimate empirically as follows: We first compute for every step t {O....,2 T 1 and every attack {SF, FOE, ALIE, Mimic) the value of Kr,a such that
R
It.a
Kt,a
[S]
Eies
91.0
Di,a
where It,a == 1
[7] EiEn Hi.a and Rea and Ii, refer respectively to Rg and Pi when the attack is used by the Byzantine workers. Then, we compute the empirical & following:
(8)
K
max (O.... T-.I] 1] oE ALLI,,
Kz,a-
Computation of 0.. We compute 0, using the closed form of the solution of Mean Least Square regression problem:
0, [ x + (n - AT) - y,
where X E (n- is the matrix that contains the data points and E Rn-f the associated vector that contains the labels.
33


Reviews:
[{"review_id": "qauzdml4wM", "reviewer": "Reviewer_GcGL", "summary": "In the present paper the authors study the problem of distributed learning in the presence of adversarial learners (aka Byzantine workers) and hetogeneous data. The paper aims to generalize and improve previous results on homogeneous data, an assumption that is claimed to be very restrictive in practice. For this they introduce a new concept of (G,B) gradient dissimilarity which has the same relation to the more standard G gradient dissimilarity as an affine variance assumptions has to a bounded variance assumption in stochastic optimization. \n\nUnder their assumption they first prove that the breakdown point, i.e., the share of Byzantine workers beyond which the optimization breaks down is upper bounded by $\\tfrac{1}{2+B^2}$, where previous results only yield the intuitive bound of $\\tfrac12$. They also confirm this theoretical observation numerically. Second, they also establish sharp error bounds in the regime below the breakdown point by proving a lower bound as well as an upper bound, attained by robust distributed gradient descent.\n\n", "questions": "p.2: Maybe you can make the connection between the G and (G,B) assumptions and bounded / affine variance assumptions in the analysis of SGD. \n\np.6, last paragraph: can one estimate B here to see whether it is close to $\\sqrt{2}$ which would fit to the $\\tfrac14$ you observe numerically?\n\np.7: Definition 4 should be followed by a few examples for $(f, \\kappa)$-robust aggregation rules. Please also mention that in the absence of adversaries, one can just average the gradients and gets a $(0,0)$-robust aggregation rule. \n\np.8: Here you start using nicefrac excessively which, at least for my brain, is very hard to read and process. Maybe you can use or stick to tfrac for inline fractions which you seemed to have used earlier.\n\np.30: Number of honest workers should just be $n-f$ not $n-f=10$. If I understand this correctly $n=10$ and $f$ ranges from $1$ to $9$.\n\n", "limitations": "The authors did make the point that probably not all of their results are sharp, e.g., in terms of constants or the slow down factor for linear convergence in the presence of adversaries.\nNegative societal impact is not to be expected in my opinion.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I find the paper very clear and well written. The theoretical contributions are very interesting and appear to be novel. Furthermore, the experiments illustrate the sharpness of the results. The proofs in the appendix seem to be sound although I have to say that I didn't check all the details in the proof of Theorem 1. I did check the convergence statement of Theorem 2 the proof of which is rather standard. ", "weaknesses": "I cannot list any significant weaknesses besides the few questions that I have in the next block.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging comments. We will implement your suggestions in the final version of the paper. Please find below answers to your questions.\n\n> p.2: Maybe you can make the connection between the G and (G,B) assumptions and bounded / affine variance assumptions in the analysis of SGD.\n\nThis is a good remark. We will make the connection between these in the final version of the paper.\n\n>p.6, last paragraph: Can one estimate B here to see whether it is close to $\\sqrt{2}$ which would fit to the $\\frac{1}{4}$ you observe numerically?\n\n This is an interesting question. We believe it is possible to get the result mentioned, similar to the way we measured $G$ and $B$ empirically in Figures 3 and 4. We will include this result in the final version.\n\n>p.30: Number of honest workers should just be $n-f$ and not $n-f = 10$. If I understand this correctly $n = 10$ and $f$ ranger from $1$ to $9$.\n\nIn experiments, we fix the number of honest workers and vary the number of Byzantine workers. In this particular case, the number of honest workers (i.e., $n-f$) is set to $10$, and the number of Byzantine workers $f$ varies from $1$ to $9$."}, {"review_id": "NJgaIFyaiN", "reviewer": "Reviewer_VidP", "summary": "The work focuses on the analysis of the limits of Byzantine-robust learning under so-called $(G,B)$-dissimilarity assumption -- a generalization of the standard bounded gradient dissimilarity assumption. The main result of the paper is in establishing the upper bound for the maximal admissible ratio of Byzantine workers: $\\delta < \\frac{1}{2+B^2}$ that is separated from $\\frac{1}{2}$ (and can be very small). The authors also derive the lower bound for the optimization error that matches the known upper bounds (up to numerical factors) and the derived upper bound for the robust version of the distributed gradient descent.", "questions": "1. In [17,18], another notion of robust aggregation was introduced. Are there any benefits of using a different notion of robustness?\n\n2. Theorem 2, \"let $f < n/2$\": this is a bit confusing, because $\\kappa$ implicitly depends on the ratio of Byzantines.\n\n3. Although the proofs are detailed and look correct to me, it is a bit inconvenient to read them. In particular, I suggest moving the proofs of Lemmas 1 and 2 to Appendix B.1.2.", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors derive the limits on robustness under $(G,B)$-gradient dissimilarity that are quite interesting. In particular, the ratio of Byzantine workers has to be smaller than $\\frac{1}{2+B^2}$ to guarantee the convergence to some neighborhood of the solution. Moreover, the lower bound for the optimization error $\\varepsilon$ is established. These bounds are quite pessimistic ($B^2$ is proportional to the condition number in the worst case) and emphasize the non-triviality of Byzantine-robustness in the heterogeneous case. The construction of the worst-case examples is quite simple.\n\n2. The paper is well-written in general, the idea is explained well in the main part of the paper.\n\n3. The proofs look correct to me.", "weaknesses": "The results of Theorem 2 are not completely novel. In particular, there exist results under $(G,B)$-dissimilarity assumption, see Theorem V from [18] and Theorems E.1, E.2 from [14]. These results are derived for the different notions of robust aggregator, but up to the replacement of $\\kappa$ with $c\\delta$ they recover Theorem 2 from this submission. Moreover, the method from [14] with $p=1$ and no compression coincides with Robust D-GD.\n\nThe paper should be modified accordingly. Nevertheless, I see Theorem 1 as the main contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging comments. We will implement your suggestions in the final version of the paper. Please find below answers to your questions.\n\n>The results of Theorem 2 are not completely novel. In particular, there exist results under $(G,B)$-dissimilarity assumption, see Theorem V from [18] and Theorems E.1, E.2 from [14]. These results are derived for the different notions of robust aggregator, but up to the replacement of $\\kappa$ with $c \\delta$ they recover Theorem 2 from this submission. Moreover, the method from [14] with $p=1$ and no compression coincides with Robust D-GD.\n\n We thank the reviewer for bringing up this point, as we were aware of these results. While we agree on the similarities between the results, there are subtle differences that are important to note. First, unlike the notion of $(f,\\kappa)$-robustness (that we use), the so-called $(c,\\delta)$-agnostic robustness (used in [14, 18]) is a stochastic notion. Under the latter notion, good parameters $(c,\\delta)$ of robust aggregators were only shown when using a randomized method called Bucketing [18]. Consequently, instead of obtaining a deterministic error bound as in Theorem 2, simply replacing $c\\delta$ with $\\kappa$ in [14, 18] gives a stochastic bound, which is strictly weaker than the result of Theorem 2. Moreover, the corresponding non-vanishing upper bound term for robust D-GD obtained from the analysis in [18] for several robust aggregation rules (e.g., coordinate-wise median) is worse than that we obtain using $(f,\\kappa)$-robustness (see also discussion below). We will include this discussion in the paper.\n\n>In [17,18], another notion of robust aggregation was introduced. Are there any benefits of using a different notion of robustness?\n\nThe main benefit of $(f,\\kappa)$-robustness (the notion of robust aggregation that we use) is that it was shown (originally in [3]) to hold for several existing aggregation rules (e.g. coordinate-wise median, trimmed mean) with tight rates of $\\kappa$, unlike $(c, \\delta)$-agnostic robustness introduced in [17, 18]. Also, as argued in [3], existing robustness criteria in the literature can be recovered from $(f,\\kappa)$-robustness. Importantly, as pointed out above, $(f,\\kappa)$-robustness is a deterministic condition, which allows us to obtain a deterministic bound for robust D-GD (unlike in [18]).\n\n>Theorem 2, ``let $f < n/2$\": this is a bit confusing, because $\\kappa$ implicitly depends on the ratio of Byzantines.\n\nThe reason we explicitly assume $f < n/2$ in the beginning of the theorem is that no upper bound can be achieved without this condition, as shown in [25]. We then let $F$ be a $(f,\\kappa)$-robust aggregation, which is implicit for ``let $F \\colon \\mathbb{R}^{d \\times n} \\to \\mathbb{R}$ and $\\kappa \\geq 0$ be such that $F$ is $(f,\\kappa)$-robust\". The theorem then holds for any $\\kappa$ verifying this condition (exact values for $\\kappa$ can be found in [3]). "}, {"review_id": "oD0588HBkf", "reviewer": "Reviewer_UheS", "summary": "This paper considers under the robust distributed learning settings, the conventional learning error bounds are vacuous as they rely on restrictive assumptions as $G$-gradient dissimilarity (equation 2). The paper relaxes the assumption to a more general $(G, B)$-dissimilarity model that relaxes the bounds on gradients norm of honest workers with a constant of $B$. A new breakdown ratio between Byzantine and honest workers $f / n$ that would yield theoretical robustness guarantees is established as $ 1 / (2 + B^2) $. The authors finally show the tightness of $f / n < 1 / (2 + B^2)$ bound via analyzing the state of the art robustness coefficient $ \\kappa = f / (n - 2f) $ on a robust D-GD that would also yield $ 1 / (2 + B^2) $ instead of $ 1 / 2 $ breakdown point. In this way, the gap between the previous theory and the empirical observation of the largest amount of Byzantine workers to have robustness guarantee on global honest loss (equation 1) is reduced. ", "questions": "I am confused on the heuristic method to compute $G$ and $B$ in Appendix D.3, line 743. Could you explain such formula?", "limitations": "I didn't find any other limitations of this paper. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper borrows the data heterogenity model ($(G, B)$-dissimilarity) from the classical distributed learning settings to the Byzantine distributed learning and build a nice and intuitive theory on the breakdown point on the fraction of Byzantine workers to melt down the robustness guarantee. The paper narratives are clear and easy to follow, and the experiments (Figure 2, 3, 4) are well conducted. ", "weaknesses": "The novel breakpoint essentially involves a dependency over the constant over honest workers' gradient norm. It would be better to have an ablation study on logistic regression that if such constant $B$ is changed, we would observe similar changes in the breakpoint point. Otherwise, it is a great paper!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging comments. Please find below answers to your questions. We hope that you would increase the score if you find our answers satisfactory.\n\n>I am confused on the heuristic method to compute and in Appendix D.3, line 743. Could you explain such formula?\n\nFirst, we recall that a fixed set of loss functions can satisfy the condition of $(G,B)$-gradient dissimilarity for multiple pairs $(G,B)$. For example, if the loss functions satisfy $(G,B)$-gradient dissimilarity, they also satisfy $(G,2B)$-gradient dissimilarity. Thus, our heuristic finds multiple couples $(G,B)$ and chooses that yielding the smallest upper bound (as per Theorem 2). To do so, we consider several possible values of $B$ (whose range is bounded as per the lower bound in Theorem 1). Then, for each possible value of $B$, we find the corresponding tightest $G$ satisfying Assumption 1 (as described in line 742). Finally, in line 743, we find the pair $(G, B)$ minimizing the theoretical upper bound.\n\n>The novel breakpoint essentially involves a dependency over the constant over honest workers' gradient norm. It would be better to have an ablation study on logistic regression that if such constant $B$ is changed, we would observe similar changes in the breakpoint point. Otherwise, it is a great paper!\n\nThis is an interesting remark. It is however quite challenging to conduct such an ablation study. This is mainly because we cannot directly control the constant $B$, subject to Assumption 1, even for simple learning problems like least-squares regression. Thus, in our experiments, we first partition data heterogeneously across workers, and then determine $B$ empirically. "}, {"review_id": "4CdvT4gp8J", "reviewer": "Reviewer_YywB", "summary": "The paper studies distributed learning in the presense of Byzantine workers (that is, nodes that output adversarial results) and data heterogeneity.\n\nA previous notion of robustness for distributed learning, namely G-gradient dissimilarity, is not sufficient to capture data heterogeneity. In fact, this holds even in fairly simple tasks such as least-squares regression (i.e., for any G>0).\n\nMotivated by this observation, the paper defines a new notion of robustness for distributed learning, (G,B)-Gradient Dissimilarity. This allows for some additional error term in the average gradient difference between workers, proportionally to B.\n\nThe proposed theory is used in a least squares regression task to justify observed robustness of stochastic gradient descent under small sets of dishonest workers.", "questions": "What is the (G, B)-gradient dissimilarity in the experiments?\n\nObservation 1 does not require any Byzantine workers, right? Perhaps this should be emphasized.\n\nIn Proposition 1, H is the set of honest workers. How do the honest workers know who is honest? Earlier in the paper it is mentioned that trying to compute any statistic over the whole set of workers is generally impossible in the presence of Byzantine workers. Does this mean that the task in Proposition 1 is impossible to perform in reality because H must be known to all honest workers? If so, this renders the whole model not very realistic.\n", "limitations": "The authors have adequately addressed the limitations of this work.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents an interesting notion of robustness in distributed learning. It is shown that this notion captures distributed gradient computation when a small number of workers can output arbitrary results. The theory is compelling and seems to justify observed behavior in a realistic setting.\n\nA theoretical criterion is given for algorithms to be robust against (G,B)-gradient dissimilarity. This is an interesting theoretical contribution.\n", "weaknesses": "The precise formula used in the definition of (G,B)-Gradient Dissimilarity makes sense because the analysis is done for a variant of stochastic gradient descent. However, it is unclear whether this notion is also relevant to other distributed learning tasks.\n\nThe precise setting regarding honest and Byzantine workers is confusing (see Questions section of this review).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging comments. Please find below answers to your questions.\n\n>What is the (G, B)-gradient dissimilarity in the experiments?\n\nIntuitively, $(G, B)$-gradient dissimilarity measures data heterogeneity using the gradient of the empirical loss function. For a given distributed learning problem, there may be multiple couples $(G,B)$ for which the gradient dissimilarity inequality holds (naive example: if it holds for $(G,B)$, then it also holds for $(G,2B)$). To show the tightest empirical upper bounds (Figures 3 and 4), based on our result in Theorem 2, we search through several possible values of $(G,B)$ using a heuristic method explained in Appendix D.\n\n>Observation 1 does not require any Byzantine workers, right? Perhaps this should be emphasized.\n\nYes, we agree. Thank you for pointing this out. We will emphasize it in the paper.\n\n>In Proposition 1, H is the set of honest workers. How do the honest workers know who is honest? Earlier in the paper it is mentioned that trying to compute any statistic over the whole set of workers is generally impossible in the presence of Byzantine workers. Does this mean that the task in Proposition 1 is impossible to perform in reality because H must be known to all honest workers? If so, this renders the whole model not very realistic.\n\nThank you for bringing up this point. Honest workers and the server do not know the set $\\mathcal{H}$. This is in fact one of the main theoretical arguments in the proof of the lower bound of Theorem 1. Of course, in Theorem 2, we analyze the convergence of Robust D-GD for the loss function over the set of honest workers $\\mathcal{H}$.\n\n>The precise formula used in the definition of (G,B)-Gradient Dissimilarity makes sense because the analysis is done for a variant of stochastic gradient descent. However, it is unclear whether this notion is also relevant to other distributed learning tasks.\n\nThis is a good remark, as one could think of the applicability of our findings to higher order optimization algorithms for example. In this sense, extending $(G,B)$-Gradient Dissimilarity to incorporate higher-order information is an interesting research direction. However, as long as the loss is differentiable we believe that $(G,B)$-Gradient Dissimilarity is the primary heterogeneity model to study, as was done before in the references in lines 143-144. Finally, we emphasize that, under $(G,B)$-Gradient Dissimilarity, the lower bound in Theorem 1 applies to any algorithm, and not just a specific variant of gradient descent. That is, we do not assume any structure of the algorithm for demonstrating Theorem 1."}]

Author rebuttal:

Meta-review: The paper advances our understanding of Byzantine resilient Distributed learning. Under a natural assumption of inhomogeneity that extends the standard one, it shows new breakdown point for Byzantine resilient learning, and establishes new lower and upper bounds for problems.

This is a clear accept paper.
Decision: Accept (spotlight)