Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences
Authors: Grigory Malinovsky
Peter Richtárik
Samuel Horváth
Eduard Gorbunov
Venue: NeurIPS 2024 poster (2024)
Keywords: Byzantine robustness
distributed optimization
communication compression
non-convex optimization
Primary area: optimization
TL;DR: In this work we introduce a novel approach how to handle byzantine workers in partial participation regime, when they can form majority.

Abstract: Distributed learning has emerged as a leading paradigm for training large machine learning models. However, in real-world scenarios, participants may be unreliable or malicious, posing a significant challenge to the integrity and accuracy of the trained models. Byzantine fault tolerance mechanisms have been proposed to address these issues, but they often assume full participation from all clients, which is not always practical due to the unavailability of some clients or communication constraints. In our work, we propose the first distributed method with client sampling and provable tolerance to Byzantine workers. The key idea behind the developed method is the use of gradient clipping to control stochastic gradient differences in recursive variance reduction. This allows us to bound the potential harm caused by Byzantine workers, even during iterations when all sampled clients are Byzantine. Furthermore, we incorporate communication compression into the method to enhance communication efficiency. Under general assumptions, we prove convergence rates for the proposed method that match the existing state-of-the-art (SOTA) theoretical results. We also propose a heuristic on how to adjust any Byzantine-robust method to a partial participation scenario via clipping.

Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences
Grigory Malinovsky" KAUST; MBZUAI
Peter Richtárik
Samuel Horváth MBZUAI
Eduard Gorbunov's
KAUST
MBZUAI
Abstract
Distributed learning has emerged leading paradigm for training large machine learning models. However, in real-world scenarios, participants may be unreliable or malicious, posing significant challenge to the integrity and accuracy of the trained models. Byzantine fault tolerance mechanisms have been proposed to address these issues, but they often assume full participation from all clients, which is not always practical due to the unavailability of some clients or communication constraints. In our work, we propose the first distributed method with client sampling and provable tolerance to Byzantine workers. The key idea behind the developed method is the use of gradient clipping to control stochastic gradient differences recursive variance reduction. This allows us to bound the potential harm caused by Byzantine workers, even during iterations when all sampled clients are Byzantine. Furthermore, incorporate communication compression into the method to enhance communication efficiency. Under general assumptions, we prove convergence rates for the proposed method that match the existing state-of- the-art (SOTA) theoretical results. We also propose a heuristic on adjusting any Byzantine-robus method partial participation scenario via clipping.
Introduction
Distributed optimization problems cornerstone of modern machine learning research. They naturally arise in scenarios where data is distributed across multiple clients; for instance, this is typical in Federated Learning (FL) (Konečný al., 2016; Kairouz et al., 2021). Such problems require specialized algorithms adapted to the distributed setup. Additionally, the adoption of distributed optimization methods motivated by the sheer computational complexity involved in training modern machine learning models. Many models deal with massive datasets and intricate architectures, rendering training infeasible on a single machine (Li, 2020). Distributed methods, by parallelizing computations across multiple machines, offer pragmatic solution to accelerate training and address these computational challenges, thus pushing the boundaries of machine learning capabilities.
To make distributed training accessible to the broader community, collaborative learning approaches have been actively studied in recent years (Kijsipongse al., 201 0018b; Ryabinin and Gusev, 2020; Atre et al., 2021; Diskin et al., 2021a). In such applications, there is high risk of the occurrence of so-called Byzantine workers (Lamport al., 1982; Su and Vaidya, 2arti-partic who can violate the prescribed distributed algorithm/protocol either intentionally or simply because they are faulty. In general, such workers may even have access some private data of certain participants and may collude to increase their impact on the training. Since the ultimate goal is to achieve robustness
Part of the work done when G. Malinovsky visiting MBZUAL. 1 Kiig Abdullah University of Science and Technology. Mohhamed bin Zayed University of Artificial Intelligence. Corresponding author: eduard. wor.bugoeebbbbuuaa...... ac. ac. ae.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

in the worst case, many papers in the field make no assumptions limiting the power of Byzantine workers. Clearly. in this scenario, standard distributed methods based on the averaging of received information (e.g., stochastic gradients) are not robust, even to single Byzantine worker. Such a worker can send an arbitrarily large vector that can shift the method arbitrarily far from the solution. This aspect makes it non-trivial to design methods with provable robustness to Byzantines (Baruch et al., 2019; Xie et al., 2020a). Despite all the challenges, multiple methods are developed/analyzed in the literature (Alistarh et al., 2018; Allen-Zhu et al., 2021; Wu et al., 2020; Zhu and Ling, 2021; Karimireddy et al., 2021, 2022; Gorbunov et al., 2022, 2023; Allouah et al., 2023).
However, literally, all existing methods with provable Byzantine robustness require the full (or close to full) participation of clients or rely on extra assumptions. The requirement of full participation is impractical for modern distributed learning problems since they can have millions of clients (Bonawitz et al., 2017; Niu et al., 2020). In such scenarios, it is more natural to use sampling of clients to speed up the training. Moreover, some clients can be unavailable at certain moments, e.g., due to a poor connection, low battery, or simply because of the need to use the computing power for some other tasks. Although partial participation of clients is a natural attribute of large- scale collaborative training, it is not studied under the presence of Byzantine workers. Moreover, this question is highly non-trivial: the existing methods can fail to converge if combined naïvely with partial participation since Byzantine can form a majority during particular rounds and, thus, destroy the whole training with just one round of communications. Therefore, the field requires the development of new distributed methods that are provably robust to Byzantine attacks and can work with partial participation even when Byzantine workers form majority during some rounds.
Our Contributions We develop Byzantine-toleran Redueeee-Redued MARINA with Partial Par- ticipation (ByZ-VR-MARINA-
Algorithm 1 the first distributed method having Byzantine robustness and allowing partial participation of clients without strong additional assumptions. Our method uses variance reduction to handle Byzantine workers and clipping of stochastic gradient differences bound the potential harm of Byzantine workers even when they form a majority during particular rounds of communication. To make the method even more communication efficient, we add communication compression. We prove the convergence of ByZ-VR-MARINA smooth non-convex functions and Dollykk-Eojasiewiic. functions. In the special case of full participa- tion, our complexity bounds recover the ones for ByZ-VR-MARINA (Gorbunov et al., 2023) that are the current SOTA convergence results. Moreover, we prove that in some cases, partial participation is theoretically beneficial for ByZ-VR-MARINA-PP We also propose simplified version of ByZ-VR- MARINA-PP with better neighborhood term in the convergence bounds SOY--RR-MARINA-PPA Algorithm 3) and a heuristic on how to use clipping to adapt any Byzantine-robust method to the partial participation setup and illustrate its performance in experiments.
for general
1.1 Related Work
Below, we overview closely related works. Additional discussion is deferred to Appendix A.
Byzantine robustness. The primary vulnerability of standard distributed methods to Byzantine attacks lies in the aggregation rule: even one worker can arbitrarily distort the average. Therefore, many papers on Byzantine robustness focus on the application of robust aggregation rules, such as the geometric median (Pillutla et al., 2022), coordinate- wise median, trimmed median (Yin et al., 2018), Krum (Blanchard et al., 2017), and Multi-Krum (Damaskinos et al., 2019). However, simply robustifying the aggregation rule is insufficient to achieve provable Byzantine robustness, as illustrated by Baruch et al. (2019) and Xie et al. (2020a), who design special Byzantine attacks that can bypass standard defenses. This implics that more significant algorithmic changes are required to achieve Byzantine robustness, point also formally proven by Karimireddy et al. (2021). who demonstrate that permutation-invante
algorithms- - i.c., algorithms independent of the order of stochastic gradients at each step- - cannot provably converge to any predefined accuracy in the presence of Byzantines.
Wu et al. (2020) are the first who exploit variance reduction to tolerate Byzantine attacks. They propose and analyze the method called Byrd-SAGA, which uses SAGA-type (Defazio et al., 2014) gradient estimators on the good workers and geometric median for the aggregation. Gorbunov et al. (2023) develop another variance-reduced method called Byz-VR-MARINA, which is based on (conditionally biased) GeomSARAH/PAGEyye (Horváth et al., 2023; Li et al., 2021) gradient estimator and any robust aggregation in the sense of the definition from (Karimireddy et al., 2021,

---

2022), and derive the improved convergence guarantees that are the current SOTA in the literature. There are also many other approaches and we discuss some of them in Appendix A.
Partial participation and client sampling. In the context of Byzantine-robust learning, there exists several works that develop and analyze methods with partial participation (Data and Diggavi, 2021; El-Mhamdi et al., 2021; Boubouh et al., 2022; Allouah et al., 2024a). However, these works rely on the restrictive assumption that the number of participating clients at each round is larger than the number of Byzantine workers. In this case, Byzantines cannot form a majority, and standard methods can be applied without any changes. In contrast, our method converges in more challenging scenarios, e.g., Byz-VR- FIZ-VR-MARINA-PP provably converges even when the server samples one client, which can be Byzantine. If the number of participating clients such that Byzantine clients can form majority, these methods have a certain probability of divergence and this probability grows with each communication round. We provide a more detailed discussion in Appendix
Preliminaries
In this section, we formally introduce the problem, main definition, and assumptions used in the analysis. That is, we consider finite-sum distributed optimization problem"
min (f(z) à Eieg f(()), f((x) in Eÿ= f1)(2) Vi
(I)
where G is a set of regular clients of size G [g]. In the context of distributed learning, fi R - R corresoonds to the loss function on the data of client i, and fi.j IRd - R is the loss computed on the j-th sample from the dataset of client i. Next, we assume that the set of all clients taking part in the training is [n] {1, ...,..... n and G C [nz]. The remaining clients B == [n] \ G are Byzantine ones. We assume that B := [B] ;= orealn S ōn, where &ecal is an exact ratio of Byzantine workers and is a known upper bound for dreat. We also assume that 0 < Greal 8 < 1/2 since otherwise Byzantine workers form a majority and problem (1) becomes impossible to solve in general.
Notation. We use a standard notation for the literature on distributed stochastic optimization. Everywhere in the text ||^||| denotes a standard l --norm of E R (a. b) refers to the standard inner product of vectors a, b E Rd. The clipping operator defined as follows: clipx(x) (z) := min(1, L, // Ja for x + 0 and clip, (0) == O. Finally, Prob(A] denotes the probability of event A. [g[] is the full expectation of random variable ç. [E[s A] is the expectation of & conditioned on the event A. We also sometimes use E& [c] to denote an expectation of w.r.t. the randomness coming from step k.
Robust aggregator. We follow the definition from (Gorbunov et al., 2023) of (6, co-busstt aggrega- tion, which is generalization of the definitions proposed by Karimireddy al. (2021, 2022).
Definition 2.1 ((6, c)-Rouust Aggregator). Assume that { : :nn is such that there exists a subset G C [n]] of size 9 = G 2 (1 - 8)n for 8 S 6max < 0.5 and there exists a 2 such that add-1) Enteg E ||x;; - 2/ < a² where the expectation is taken w.r.t. the randomness of faihieg: We say that the quantity T is (obbust Aggregator (ō, c) -RAgg) and write 3 RAgg (I)) for some > 0, if the following inequality holds:
E [||G =|| coo²,
where 7= = 1 Eieg x₁. If additionally 3 is computed without the knowledge of 0², we say that T 19] is (8, cA-Agnostic Robust Aggregator (8, (acc))AARAgA and write 2 ARAgg (I1,.... (Ii...., In).
One can interpret the definition as follows. Ideally, we would like to filter out all Byzantine workers and compute just an average over the set of good clients. However, this is impossible in general since we do not know apriori who are Byzantine workers. Instead of this, it is natural to expect that the aggregation rule approximates the ideal average up in certain sense, e.g., in terms of the expected squared distance to T. As Karimireddy et al. (2021) formally show, in terms of such criterion (E a {l²)), the definition of (6, c) -RAgg cannot be improved (up to the numerical constant). Moreover,
$ For simplicity, we assume that all regular workers have the same size of local datasets. Our analysis can be easily generalized to the case of different sizes of local datasets: this will affect only the value of C+ from Assumption D.3 for some sampling strategies.
3

---

The above assumption is quite standard for the literature on Byzantine robustness (Wu al., 2020; Karimireddy et al., 2022: Gorbunov et al., 2023; Allouah et al., 2023). Moreover. some kind of bound on the heterogeneity of good clients is necessary since otherwise Byzantine robustness cannot be achieved in general. In the appendix, all proofs are given under a more general version of standard aggregators such as Krum (Blanchard et al., 2017), geometric median, and coordinate-win median do not satisfy Definition 2.1 (Karimireddy et al., 2021). though another popular standard aggregation rule called coordinate- wwise trimmed mean (Yin et al., 2018) satisfies Definition 2. as shown by Allouah al. (2023) through the more general definition of robust aggregation. To address this issue, Karimireddy et al. (2021) develop the aggregator called CenteredClip and prove that it fits the definition of (ò, c) -RAgg. Karimireddy et al. (2022) propose a procedure called Bucketing that fixes Krum, geometric median, and coordinate-
median, i.e. with Bucketing Krum, geometric, and coordinate-wi wise median become (Ó, -ARAgg, which is important for our algorithm since the variance of the vectors received from regular workers changes over time in our method. We notice here that 5 is part of the input that should satisfy  I 8 S 6max-
Compression operators. In our work, we use standard unbiased compression operators with relatively bounded variance (Khirirat et al., 2018; Horváth et al., 2023). F E called unbiased compressorccompresion operator if there exists w 2 0 such that for any x E Ie E[[(x)) = 2, E [()) ==|²] I w||xi||. For the given unbiased compressor 2(x), one can define the expected density" as Ço == supzeRs B [[][([))))), where !/ylo is the number of non-zero components of E Rdd.
Definition 2.2 (Unbiased compression). Stochastic mapping
In this definition, parameter w reflects how lossy the compression operator is: the larger w the more lossy the compression. For example, this class of compression operators includes random sparsification (RandK) (Stich et al., 2018) and quantization (Goodall, 1951; Roberts, 1962; Alistarh
d et al., 2017). For RandK compression w =K Se = K and for fz-quantization ~ = v So =
Vd, see the proofs in (Beznosikov al., 2020).
Assumptions. Up to a couple of assumptions that are specific to our work, we use the same assumptions as in (Gorbunov et al., 2023). We start with two new assumptions.
Assumption 2.3 (Bounded ARAgg). We assume that the server applies aggregation rule A such that A is (6, c)-RAgg and there exists constant FA > such that for any inputs Ii,..., Fn Rd the norm of the aggregator is not greater than the maximal norm of the inputs: (I,,.....,22.) s FA max ||a]||--
The above assumption is satisfied for popular (6, c)-robust aggregation rules presented the literature (Karimireddy et al., 2021, 2022). Therefore, this assumption is more a formality than real limitation: it is needed to exclude some pathological examples of (6, c) co-buutst aggregation rules, e.g., for any A that is (d, c)-RAg one can construct unbounded (8, 2c)- as = A + X, where X is a random sample from the Gaussian distribution (0, =)
Next, for part of our results, we also make the following assumption.
Assumption 2.4 (Bounded compressor (optional)). We assume that workers use compression operator Q satisfying Definition 2.2 and bounded as follows: || [(x)] < DQllzy Vx E Rd
For example, RandK and é fg-quamtization meet this assumption with De = respectively. In general, constant Do can be large (proportional to d). However, in practice, one can use RandK with K = 100 and, thus, have moderate De = 100. We also have the results without Assumption 2.4, but with worse dependence on some other parameters, see Section 4.
R and De vd
NexI, we assume that good workers have (e-heterogeneous local loss functions.
Assumption 2.5 2 ('-heterogeneity). We assume that good clients have (e-heterogeneous local loss functions for some Ç 2 O, i.e. J Eieg [[)) - f=)) < 2
Vx E Rd.
'This quantity is well-suited for sparsification-tyy type compression operators like random sparsification (Stich et al., 2018) and 1-level Ez E--uantization (Alistarh et al., 2017). For other compressors, such as quantization with more than one level (Goodall, 1951; Roberts, 1962). Co not the main characteristic describing their properties.

---

Algorithm 1 Byz-VR-MARINA-PPE Byzantine- tolerant VR-MARINA with Partial Participation
Input: vectors 2", gg RR, stepsize 7, mini-batch size b, probability p (0, 1], number of iterations K, (6, ARAggg clients' sample size 1 I C v Č Σ n, clipping coefficients {ax hx21
2: for k = 0, o,...... K do
3: Get a sample from Bernoulli distribution with parameter p: ~ Be(p)
4: Sample the set of clients S₂ S [n], [Sp] = C. if cR 0; otherwise |Sp
5: Broadcast g². Cj to all workers
6: for E G &nS,, Sy: in parallel do
7:
k+ = xx - -ng* and Act1 = ax 10x1111x/tt - xx1|
Vf((ttt))
if =,
8: Set ++1 = (gt clip (o (A,(a*t1,, x(1)) otherwise,
where (, ,²t) is a mini-batched estimator of (ii - Vs((""), 2(-) for G Sn are computed independently
9: end for
ARAgg (19, *+1 hes.)
if c 1, otherwise
10:
(ECLiPAin (e((i(ottt) x(1))] SESa)
9e + ARAgE
end for
Assumption 2.5, see Assumption D.5. Finally, the case of homogencous data (C = 0) is also quite popular for collaborative learning (Diskin et al., 2021b; Kijsipongse et al., 201
The following assumption is classical for the literature on non-convex optimization.
Assumption 2.6 (Smoothness (simplified)). We assume that for all i E 9 and j E [m]] there exists 2 such that fig is C-smooth, i.e., for all x, Rdd
(v) ( S 5c1 - yll.
Moreover, we assume that f is uniformly lower bounded by f E R. i... f=
:= inf f(x).
For the sake of simplicity, do not differentiate between various notions of smoothness in the main text. However, our analysis takes into account the differences between smoothness constants, similarity of local functions, and sampling strategy (see Appendix D.
Finally, we also consider functions satisfying Polyak-E.ojasewwic. (PL) condition (Polyak, 1963; Lojasiewicz, 1963). This assumption belongs the class of assumptions on the structured non- convexity that allows achieving linear convergence (Necoara et al., 2019).
Assumption 2.7 (PL condition (optional)). We assume that function f satisfies Polyak-Lojasiewicc (PL) condition with parameter μ 0, i.c., for all æ e Edd there exists f* == infzers f(z) such that [|v 2 2u (f(x) f*).
3 New Method: Byz- ByZ-VR-MARINN--P
We propose a new method called Byzantine-tolerant Variance-Reducce MARINA with Partial Partici- pation (Byz-VR-MARINA-PP. Algorithm 1). Our method extends BYZ-VR-MARINA (Gorbunov et al., 2023) to the partial participation case via the proper usage of the clipping operator. To illustrate how Byz-VR-MMRRINA-P works, we first consider special case of full participation.
Special case: ByZ-VR-MARINA, turned off (A₃ = +oo), then Syz-VR-MMRIINAPP reduces to ByZ-VR-MARINA that works
all clients participate at each round (Ss. = [nl) and clipping
follows, Consider the case when no compression applied (Q(x) x) and (+ x²)) (2*++) fi.j(
fa,ia (æ*), where ja is sampled uniformly at random from [m], i E G. Then, regular workers compute GeomSARAHIPAGE gradient estimator at each step: for E g
V (z((+))),, with probability p, g + V. (11 - - (z*), otherwise
k+1
0
5

---

With small probability p. good workers compute full gradients, and with larger probability 1 1-3 they update their estimator via adding stochastic gradient difference. To balance the oracle cost of these two cases, one can choose p ~ 1/m (for b-size mini-batched estimator p ~ f/m). Such estimators are known to optimal for finding stationary points in the stochastic first-order optimization (Fang et al., 2018; Arjevani al., 2023). Next, good workers send ++1 or V. (1*=1) -
Vi.ia (a*) to the server who robustly aggregate the received vectors. Since estimators are conditionally biased, i..., E[g I²+1 2=1 * (x**t)) the additional bias coming from the aggregation does not cause significant issues in the analysis or practice. Moreover, the variance of {g} Jieg w.r.t. the sampling of the stochastic gradients is proportional to || - 1*1²² + 0 with probability 1 (due to Assumption D.3) that progressively limits the effect of Byzantine attacks. For a more detailed explanation of why recursive variance reduction works better than SAGA/SVRG-type variance reduction, we refer to (Gorbunov et al., 2023). Arbitrary sampling allows the improvement of the dependence on the smoothness constants. Unbiased communication compression also naturally fits the framework since it is applied to the stochastic gradient difference, meaning that the variance of {g. 8+11 heg w.r.t. the sampling of the stochastic gradients and compression remains proportional to ||z - 122 with probability - p.
client sampling and clipping, The algorithmic novelty of ByZ-VR-MARINA-PP in comparison to ByZ-VR-MARINA is twofold: with (typically large) probability 1 - P only C clients sampled uniformly at random from the set of all clients participate at each round, and clipping applied the compressed stochastic gradient differences. With a small probability p. a larger number" of clients C S n takes part in the communication. The main role of clipping is to ensure that the method can withstand the attacks of Byzantines when they form majority or, more precisely when there are more than 5C Byzantine workers among the sampled ones. Indeed, without clipping (or some other algorithmic changes) such situations critical for convergence: Byzantine workers can shift the method arbitrarily far from the solution, e.g., they can collectively send some vector with the arbitrarily large norm. In contrast, Byz- ByZ-VR-MARINA-PP tolerates any attacks even when all sampled clients are Byzantine workers since the update remains bounded due to the clipping. Via choosing Aa++1 ~ I| I1 ensure that the norm of transmitted vectors decreases with the same rate as it does in Byz-VR-MARINA with full client participation. Finally, with probability - P regular workers can transmit just compressed vectors and leave the clipping operation to the server since Byzantines can ignore clipping operation.
New ingredients:
4 Convergence Results
We define G = & n S and Gh = 1G and (+) also use the following probabilities:
x! kl(n-Rj]
represents the binomial coefficient. We
PG Prob G 2 8) = (9)())) (2)
C, mPG
(G)))
Pøg = Prob {i E G G 2 (1-
These probabilities naturally appear in the analysis and statements of the theorems. When C 0. then server samples C/ clients, and two situations can appear: either G.C, is at least (1 (1-8) 8) C' meaning that the aggregator can ensure robustness according to Definition 2.1 or Gt < <1 d) C. Probability Pa is the probability of the first event, and the second event implies that the aggregation can be spoiled by Byzantine workers (but clipping bounds the "harm"). Finally, we use Pgs. in the computation of some conditional expectations when the first event occurs. The mentioned probabilities can be easily computed for some special cases. For example, if C 1, then Pc G/n and Pos. 1/c: if C 2, then PG G(G-1)/n(n-D) 1) and Poy = 2/0; finally, if C n., then Pc: 1 and Psg
The next theorem is our main convergence result for general unbiased compression operators.
7 As one can see from our analysis, it is sufticient to take Ō 2 max(1, $uan/s) similarly to (Data and Diggavi, 2021). However, in contrast to the approach from Data and Diggavi (2021), Byz-VR-MARRINAPPP requires such communications only with small probability p.

---

Theorem 4.1. Let Assumptions 2.3, 2.5, 2.6 hold, Ak+1 = 2C - and C
2
max (1, 6/. Assume that 0 < S 1/((+//A),, where constant A is defined as
32pcGPob ob (30w + 11) (1 2c6) + 16(1 (1 + 442))
A
(4)
p2(1-5jC
p²
Then for all K 2 0 the iterates produced by ByZ-VR-MARINA-PP (Algorithm 1) satisfy
E [ 11
24
4Bc² P
(5)
+K+1]
28P dt
P G
where D
(5el + +P) + D. where D = 0 when Ö = n, D = (1-5)C when Ö = n, and xx
1-6
chosen uniformly at random from x², xx1 ,...,,,"""" K and Φ0 f (x=0) - f + 22 119 V (a (=0)|²
If. in addition, Assumption 2.7 holds and 0 < S 1/c(1+VAA) then for all K 2 0 the iterates
produced by ByZ-VR-MARINA-PP (Algorithm 1) with = min {TM, }} satisfy
E (1* f (x*) s (1-p)) p)* g0 + 1
(6)
pp
where の0 = (x.) 1* + 47 - V (1
The above theorem establishes similar guarantees to the current SOTA ones obtained for Byz-VR- MARINA. That is, in the general non-convex case, we prove (1/K) rate, which is optimal (Arjevani et al., 2023), and for Pt-functions we derive linear convergence result to the neighborhood depending on the heterogeneity. The size of this neighborhood matches the one derived for Byz- ByZ-VR-MARINA by Gorbunov et al. (2023). However, since our result is obtained considering the challenging scenario of partial participation of clients, the maximal theoretically allowed stepsize in our analysis of ByZ-VR-MARINN-PP is smaller than the one from (Gorbunov et al., 2023).
In particular, the second term in the constant A appears due to the partial participation, and the whole expression for A is proportional to 1/p². In contrast, a similar constant A from the result for ByZ-VR-MARINA is proportional to 1/p, which can be noticeably smaller than 1/p². Indeed, make the expected number of clients participating in the communication round equal to OCC), to make the expected number of stochastic oracle calls equal of transmitted components for each worker taking part in the communication round equal (SS)). parameter p should be chosen as p min (C/, f/m, Sa/d], where the latter term in the minimum often equals to (1)(w+11) (Gorbunov et al., 2021). Therefore, in some scenarios, p can be small.
(b)) and make the expected number
Next, in the special case of full participation, we have C = = n, PG = Pot = 1, meaning that A (((55)(())))) for ByZ-VR-MARINA-PE In contrast, the corresponding constant for ByZ-VR-MARINA is of the order (((++))/m + (1+w)c6/p²)) which is strictly better than our bound. In this special case, we do not recover the result for Byz- ByZ-VR-MARINA.
Such a complexity deterioration can be explained as follows: the presence of clipping introduces additional technical difficulties in the analysis, resulting in reduced step size compared to Byz-VR- MARINA, even when C Č n. To achieve more favorable convergence rate, particularly in scenarios of complete participation, we also establish the results under Assumption 2.4.
Theorem 4.2. Let Assumptions 2.3, 2.4, 2.5, 2.6 hold, AR+1 D&L
|| ||a
2*1| and Ō Z
max(1, 1, m/. Assume that 0 < $ 1/C0+VA), where constant A equals
4pcGPgg ct. 3w + 2 A = p(1 - 8)C (1-8)C
+ 8(5w + 4)c6
+ 8(1 P2) D8)
P
p2
Then for all K 2 0 the iterates produced by ByZ-VR-MARINN-PP (Algorithm 1) satisfy
B [
[17] S 7(K+1]
20
+
2îx² D
(8)
28P 1-8 66G
pgg G (1-8)č when Ö n, and x
where D D=
+ +D) D. where D 0 when Ō Ō n, D
is chosen uniformly at random from z" "..t,..,, KK and 00 = f (z²) f + 2 1و90 V (z 112
p
7

---

If, in addition, Assumption 2.7 holds and 0 <? S 1/(1++2A), then for all K 2 0 the iterates produced by ByZ-VR-MARINA-PPP (Algorithm 1) satisfy with min {114 5
EE [I*) f (x*)] (1- p) 40 +
_
(9)
pp
where Φ0 ff f 2% 1 - Vf (1'
legs can be upper bounded by D&C | x Using this fact, one can take the clipping level sufficiently large such that it is turned off for the regular workers. This allows us to simplify the proof and remove 1/p factor in front of the terms not proportional to 8 or to 1 PG in the expression for A that can make the stepsize larger. However, the second term in (7) can be larger than (4), since it depends on potentially large constant DQ- Therefore, the rates of convergence from Theorems 4.1 and 4.2 cannot be compared directly. We also highlight that the clipping level from Theorem 4.2 is in general larger than the clipping level from Theorem 4. I and, thus, it is expected that with full participation Theorem 4.2 gives better results than Theorem 4.1: the bias introduced due to the clipping becomes smaller with the increase of the clipping level. However, in the partial participation regime, the price for this is a decrease of the stepsize to compensate for the increased harm from Byzantine clients in situations when they form a majority. Further discussion of the technical challenges we overcame is deferred to Appendix E.3.
With Assumption 2.4, vectors { (2
I|-
Nevertheless, in the case of full participation, we have C- C n. PG P Poz
meaning that A = (((1=))ppn + (1 (1-2)=8/²²) in Theorem 4.2. That is, in this case, we recover the More generally, if pG = 1, which is equivalent to C' Σ max(1, 11 then Pst = Probçi E g = min(1, %/,), Psg = Prob(i E g = min 2/a} and we have = ((L + (1+=))=/pp²) Here, the first term in However, the second term in A matches the corresponding term for
result of B
"/c worse than the corresponding
term for ByZ-VR- ByZ-VR-MARINA. Moreover, this term is the main one if c5 2 p/c. which is typically the case since parameter p is often small (p- = min (0/0, b/m, (o/))) In such cases, ByZ-VR-MARINA-PP has the same rate of convergence as ByZ-VR-MARINE each step in contrast to ByZ-VR-MARINE that uses workers at each step. That is, in some cases, partial participation is provably beneficial for Byz-VR-MARINA-PP.
while utilizing, on average, just (CC) workers at
ByZ-VR-MARINA++ simplified version of Byz- ByZ-VR-MARINA. In Appendix F, we propose a simplified version of ByZ-VR-MARINA called ByZ-VR-MARINA+ (Algorithm 3). The only dif- ference is related to Line 10 of the method: when eą = O, ByZ-VR-MARINA+ computes just the
average of /clipees A (e (3 (a,(t x²)) .x+)))
instead of robust aggregation, while keeps using J.S,
ARAgg when C = 1. Of course, when Ca = O and at least one Byzantine worker is sampled, then the step can be useless, but the "harm" of this step is bounded due to the clipping. However, in certain regimes (c.g., when C' is small enough and the number of Byzantine workers is much smaller than the number of regular workers), the probability of sampling only regular workers is larger than sampling at least one Byzantine worker when = O, meaning that with high enough probability the resulting estimator has no additional bias coming from the robust aggregation. We formally analyze ByZ-VR-MARINAL and show that such a modification of the method leads to better theoretical results (especially when is small). In particular, in the settings of Theorem 4.2, we prove that ByZ-VR-MARINA+ exhibits the same Ol/K) rate but converges to Ot/r)) smaller neighborhood when Ò = n, i.e., the neighborhood term for ByZ-VR-MARINA+ is optimal (Karimireddy al., 2022; Allouah et al., 2024b). Moreover, our results for SYZ--VR-MARINA allow larger stepsizes when C small enough. For further details and complete proofs, we refer to Appendix F.
Extensions without full-batch gradient computations. The proposed methods Byz-VR- MARINA and ByZ-VR-MARINA+ have a common limitation related to the full-batch gradient computation with probability p. Although this probability is typically small, even one full-gradient computation can be very expensive for certain problems. To address this issue, we propose the modifi- cations of Byz-VR-MARING and Byz- Syy--VR-MARINA without full-batch gradient computations at all (see Algorithms 4 and 5 in Appendix G). That is, these modifications differ from BYZ-VA-MARINA and ByZ-VR-MARINA+ in Line 8 only: when C₁ 1, every good worker i from S₁ computes and sends to the server 6' b'-size mini- mini-batched stochastic gradient estimator V (z*+1) of V ff(x**+))
8

---

CH SHB
CM
SHB
CH SHB
Portal (20% clients)
10-
10-7
Full
10.7
Byr-R
By-Vi MAR
cip
clp
clp
0.0
0.5
1.0
1.5
2.0
10 0.0
0.5
1.5
epcens
000chs
00001s
Figure 1: The optimality gap -(=") for different scenarios. We use coordinate-wis mean with bucketing equal to as aggregation and shift-back as attack. We use the a9a dataset, where each worker accesses the full dataset with 15 good and 5 Byzantine workers. We do not use any compression. In each step, we sample 20% of clients uniformly at random to participate in the given round unless we specifically mention of SEN-VR--ARINN-PPP with clipping versus non-convergence without clipping. Middle: Full versus partial participation, showing faster convergence with clipping. Right: Clipping multiplier sensitivity, demonstrating consistent linear convergence across varying À values.
we use full participation. Left: Linear convergence
Under the additional assumption that the variance of V fa(++1)) is uniformly bounded by /b/,, which is standard assumption for aariance-reduced methods without full-batch gradient computations (Fang et al., 2018; Cutkosky and Orabona, 2019; Li et al., 2021; Gorbunov et al., 2021), we prove that both methods converge similarly as in the case of the (periodical) full-batch gradient computations but to the neighborhood having an additional term proportional to (c5 + Pag c/23) o²/b.. For further details and complete proofs, we refer to Appendix G.
Heuristic extension of Byz-VR-MARINN-PP. In this short remark, we illustrate how the proposed clipping technique can applied a general class of Byzantine-robust methods to adapt them to the case of partial participation. Consider the methods having the following update rule: x z - y Agg({g {g (i](n) where {9,t Fie(n) are the vectors received from workers at iteration & and Agg some aggregation rule. A vast majority of existing Byzantine-robust methods fit this scheme. In the case of partial participation of clients, we propose to modify the scheme as follows:
k+1 -- -g" where g² := + Agg ((clips, - - +)=))))
(10)
where S& S [n] a subset of clients participating in round & and {Aa Ja2o is sequence clipping parameters specified by the server. In particular, Byz- SyZ-VR-MARINA-PE can be seen an application of scheme (10) to ByZ-VR-MARINA (up to a minor modification when C₁ = 1 in -YZ-VR-MARINAA with AR+1 1|| I*1|. We suggest to use d4+1 A||z* x=1 with tunable parameter
for other methods as well.
5 Numerical Experiments
Firstly, we showcase the benefits of employing clipping remedy the presence of Byzantine workers and partial participation. For this task, we consider the standard logistic regression model with f2-reullarization, i.e., (x) -Vs log(h(z, ai.))) - (1 yk.) log(1 h(x,, ai,))) + n/|2/1 where Vi, {0, 1} is the label, aij E Rd represents the feature vector, 1) is the regularization parameter, and h(x,, convex, satisfying the PL-condition. We consider the a9a LIBSVM dataset (Chang and Lin, 2011) important feature of Byz- WyZ-VR-MARINN--PA
1/(1+e a =Tay. This objective is smooth, and for 7) >> 0, it is also strongly
and set 7 0.01. In the experiments, we focus has linear convergence for homogeneous datasets across clients even in the presence of Byzantine workers and partial participation, as shown in Theorems 4.1 and 4.2.
To demonstrate this experimentally, we consider the setup with 15 good workers and 5 Byzantines, each worker can access the entire dataset, and the server uses coordinate median with bucketing as the aggregator (see also Appendix C). For the attack, we propose a new attack that we refer as the shift-back attack, which acts in the following way. If Byzantine workers are in the majority in the current round k; then each Byzantine worker sends x _x Otherwise, they follow protocol and act as benign workers. Further experimental details are deferred to Appendix H.

---

MD
13-1
10.
Figure 2: Training loss of 2 aggregation rules (CM, RFA) under 2 attacks (BF, SHB) on the MNIST dataset under heterogeneous data split with 20 clients, 5 of which are malicious. Additional experi- ments on CIFAR 10 are provided in Appendix H.
We compare our ByZ-VR-MARINA-PP with its version without clipping. We note that the setup that we consider the most favorable in terms of minimized variance terms of data and gradient heterogeneity. We show that even in this simplest setup. the method without clipping does not converge since there is no method that can withstand the Byzantine majority. Therefore, any more complex scenario would also fall short using our simple attack. On the other hand, we show that once clipping is applied, SyZ-VR-MARINA-- is able to converge linearly to the exact solution, complementing our theoretical results.
Figure showcases these observations. On the left, we can see Byz-VR- ByZ-VR-MARINA-PA converges linearly to the optimal solution, while the version without clipping remains stuck at the starting point since Byzantines are always able to push the solution back to the origin since they can create the majority in some rounds. In the middle plot, we compare the full participation scenario in which all the clients participate in each round, which does not require clipping since, in each step, we are guaranteed that Byzantines are not in the majority, to partial participation with clipping. We can see, when we compare the total number of computations (measured in epochs), ByZ-VR-MARINA-PI leads to faster convergence even though we need to employ clipping. Finally, in the right plot, we measure the sensitivity of clipping multiplier X. We can see that ByZ-VR-MARINA-
is not very sensitive to À in terms of convergence, i.e., for all the values of X. still converge linearly. However, the suboptimal choice of À leads to slower convergence.
Furthermore, we also realize that other attacks and more complicated experiments could potentially damage clipping more than methods not using clipping. Therefore, we provide additional experiments with neural networks and different attacks in heterogeneous settings. For our experimental setup, we follow (Karimireddy et al.. 2021). However, when working with neural networks, the choice of standard variance reduction is not effective (Defazio and Bottou, 2019). Therefore, we use Byzantine Robust Momentum SGI) (Karimireddy et al., 2021) as an underlying optimization method; see (10).
We consider the MNIST dataset (LeCun and Cortes, 1998) with heterogeneous splits with 20 clients, 5 of which are malicious. For the attacks, we consider A Little is Enough (ALIE) (Baruch al., 2019), Bit Flipping (BF), and aforementioned Shift-Back (SHB). For the aggregations, we consider coordinate median (CM) (Chen et al., 2017) and robust federated averaging (RFA) (Pillutla et al., 2022) with bucketing.
From Figure 2, clipping performs on par or better than its variant without clipping. Furthermore, we can see that no robust aggregator is able to withstand the shift-back attack without clipping.
that clipping does not lead to performance degradation. On the contrary,
6 Conclusion and Future Work
This work makes an important step in the direction of achieving Byzantine robustness under the partial participation of clients. However, some important questions remain open. First of all, it will be interesting to understand whether the derived bounds can be further improved in terms of the dependence on w, m, and C. Next, it would be interesting to rigorously prove that our heuristic works for SGD with client momentum (Karimireddy et al., 2021, 2022) and other Byzantine-robust methods. Finally, studying other participation patterns (non-uniform sampling/arbirray client participation) also very prominent direction for future research.
10

---

Acknowledgements
The work of G. Malinovsky and P. Richtárik was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science.
References
Abadi, M.. Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318. (Cited page 20)
Agarwal, A. and Duchi, J. C. (2011). Distributed delayed stochastic optimization. Advances in neural information processing systems, 24. (Cited on page 20)
Ajalloeian, A. and Stich, S. U. (2020). On the convergence of SGD with biased gradients. arXiv preprint arXiv:2008. 00051. (Cited on page 20)
Alistarh, D.. Allen Zhu, Z., and Li, J. (2018). Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 4618-4623 (Cited on pages and 19)
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. (2017). QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Process- ing Systems, volume 30. (Cited pages 4 and 20)
Allen-Zhu, Z., Ebrahimian, F., Li, J., and Alistarh, D. (2021). Byzantine-resilient non-convex stochastic gradient descent. In International Conference on Learning Representations. (Cited on pages 2 and 19)
Allouah, Y., Farbadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., Rizk, G., and Voitovych, S. (2024a). Tackling byzantine clients federated learning. arXiv preprint arXiv:2402. /2780. (Cited on page 3)
Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, (2023). Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics, pages 1232-1300. (Cited on pages 2, 4, and 19)
Allouah, Y., Guerraoui, R., Gupta, N., Pinot, R., and Rizk, G. (2024b). Robust distributed learning: tight error bounds and breakdown point under data heterogeneity. Advances in Neural Information Processing Systems, 36. (Cited on pages and 63)
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, J., Srebro, N., and Woodworth, B. (2023). Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2):165-2111 (Cited on pages and 7)
Atre, M. Jha, B., and Rao, A. (2021). Distributed deep learning using volunteer computing-like paradigm. arXiv preprint arXiv:2103.cm 08894. (Cited on page I)
Baruch, G., Baruch, M., and Goldberg, Y. (2019). little is enough: Circumventing defenses for distributed learning. In Advances in Neural Information Processing Systems, volume 32. (Cited on
pages 2, 10, and 74)
Basu, D., Data, D., Karakus, C., and Diggavi, S. (2019). Oxparse-local-SGD. Distributed SGD with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, volume 32. (Cited on page 20)
Bernstein, J., Zhao, J., Azizzadenesheli, K., and Anandkumar, A. (2019). signSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learning Representations. (Cited on page 20)
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. (2020). On biased compression for distributed learning, arXiv preprint arXiv:2002. 22..200022/110 /2410. (Cited on pages 4 and 20)
Blanchard, P., El Mhamdi, E. M., Guerraoui, R., and Stainer, (2017). Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, volume 30. (Cited on pages and 4)
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, B., Patel, S., Ramage, D., Segal, machine learning. In
A., and Seth, K. (2017). Practical secure aggregation for
11

---

Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175-1191. (Cited on page 2)
Boubouh, K., Boussetta, A., Gupta, N., Maurer, A., and Pinot, R. (2022). Democratizing machine
learning: Resilient distributed learning with heterogeneous participants. In 2022 s International Symposium on Reliable Distributed Systems (SRDS), pages 94-120. IEEE. (Cited on page 3)
Chang. C.-C. and Lin, C.-J. (2011), Libsvm: a library for support vector machines. ACM transactions intelligent systems and technology (TTST), 2(3):1-27. (Cited on page 9)
Chen, L., Wang, H., Charles, Z., and Papailiopoulos, D. (2018). Draco: resslitte-resilient distributed training via redundant gradients. In International Conference on Machine Learning, pages 903-912. (Cited on page 19)
Chen, X., Wu, S. Z., and Hong. M. (2020). Understanding gradient clipping in private SGD: geometric perspective. In Advances in Neural Information Processing Systems, volume 33, pages 13773-13782. (Cited on page 20)
Chen, Y. Su, L.., and Xu, J. (2017). Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1-2):122.. (Cited on pages and 74)
Cutkosky, A. and Orabona, F. (2019). Momentum-baus based variance reduction in non-convex SGD, In Advances in Neural Information Processing Systems, volume 32. (Cited pages 9, 19, and 66)
Damaskinos, G., El-Mhamdi, E.-M., Guerraoui, R., Guirguis, A., and Rouault, S. (2019). Aggregathor: Byzantine machine learning via robust gradient aggregation. Proceedings of Machine Learning and Systems, 1:61-106. (Cited on page 2)
Damaskinos, G., Guerraoui, R., Patra, R., Taziki, M., al. (2018). Asynchronous byzantine machine learning (the case of sgd). In International Conference on Machine Learning, pages 1154.
PMLR. (Cited on page 20)
Data, D. and Diggavi, S. (2021). Byzantine-resilient high-dimensional SGD with local iterations on
heterogeneous data. In International Conference on Machine Learning, pages 2478-2488. PMLR. (Cited on pages 3, 6, 19, and 20)
Defazio, A., Bach, F., and Lacoste-Julient S. (2014). SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, volume 27. (Cited on pages and 19)
Defazio, A. and Bottou, L. (2019). On the ineffectiveness of variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, 32. (Cited on page 10)
Demidovich, Y., Malinovsky, G., Sokolov, and Richtárik, P. (2023). A guide through the Zoo of biased SGD. In Advances in Neural Information Processing Systems, volume 36. (Cited on page 20)
Diskin, M., Bukhtiyarov, A., Ryabinin, M., Saulnier, L., Lhoest, Q., Sinitsin, A., Popov. D.,, Pyrkin, D.. Kashirin, M., Borzunov, A., del Moral, A. V., Mazur, D.,, Kobelev, I., Jernite, Y., Wolf, T., and Pekhimenko, G. (2021a). Distributed deep learning in open collaborations. In Advances in Neural Information Processing Systems, volume 34, pages 7879-7897. (Cited on page 1)
Diskin, M., Bukhtiyarov, A., Ryabinin, M., Saulnier, L., Sinitsin, A., Popov, D.,, Pyrkin, D. V., Kashirin, M., Borzunov, A., Villanova del Moral, A., et al. (2021b). Distributed deep learning in open collaborations. In Advances in Neural Information Processing Systems, volume 34, pages 7879-7897. (Cited page 5)
El-Mhamdi, E. M., Farhadkhani, S., Guerraoui, R., Guirguis, A., Hoang, L.-N., and Rouault, S. (2021). Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). Advances neural information processing systems, 34:25044-25057. (Cited on page 3)
Fang. C., Li, J. Lin, Z., and Zhang, T. (2018). Spider: Near-optimal non-convex optimization via stochastic inth-integrated differential estimator. In Advances Neural Information Processing
Systems, volume 31. (Cited pages 6, 9, and 71)
Fang, M., Liu, J., Gong, N. Z., and Bentley, E. S. (2022). AFI.Guard: Byzantine-robust asynchronous federated learning. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 632-646. (Cited page 20)
12

---

Fatkhullin, I., Sokolov, I., Gorbunov, E., Li, Z.,, and Richtárik, P. (2021). EF21 with bells & whistles:
Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294.
(Cited on page 20)
Ghadimi, S. and Lan, G. (2013). Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-2365 (Cited on page 66)
Ghosh, A., Maity, R. K., Kadhe, S., Mazumdar, A., and Ramchandran, K. (2021). Communication- efficient and byzantine- robusst distributed learning with error feedback. IEEE Journal on Selected Areas in Information Theory, 233)9442-553 (Cited on page 20)
Ghosh, A.. Maity, R. K., and Mazumdar, A. (2020). Distributed newton can communicate less and resist Byzantine workers. In Advances Neural Information Processing Systems, volume 33, pages 18028-18038 (Cited on page 20)
Goodall, W. (1951). Television by pulse code modulation. Bell System Technical Journal, 30(1):33-49.
(Cited on page44 4)
Gorbunov, E., Borzumov, A., Diskin, M., and Ryabinin, M. (2022). Secure distributed training at scale. In International Conference on Machine Learning. (arXiv preprint arXiv:2106.1122 11257, 2021). (Cited on pages 2 and 19)
Gorbunov, E., Burlachenko, K. P. Li, Z., and Richtárik, P. (2021). MARINA: Faster non-convex distributed learning with compression. In International Conference on Machine Learning, pages 3788 -3988.79...0 (Cited pages 7, 7, 20, 66, and 71)
Gorbunov, E., Danilova, M., and Gasnikov, A. (2020). Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems, volume 33, pages 15042-15053, (Cited on pages 20, 26, and 57)
Gorbunov, E., Horváth, S., Richtárik, P., and Gidel, G. (2023). Variance reduction is an antidote to Byzantines: Better rates, weaker assumptions and communication compression a cherry on the top. International Conference on Learning Representations. (Cited on pages 2, 3, 4, 5, 6, 7, 19, 20, 25, 26, and 74)
Gower, R. M., Schmidt, M., Bach, F., and Richtárik, P. (2020). Variance-reduced methods for machine learning. Proceedings of the IEEE, 1968--139,. (Cited on page 19)
Haddadpour, F., Kamani, M. M., Mokhtari, A., and Mahdavi, M. (2021). Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pages 2350-2358. (Cited on page 20)
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778. (Cited on page 74)
He, L., Karimireddy, S. P., and Jaggi, M. (2022). Byzantine-robust decentralized learning via ClippedGossip. arXiv preprini 2tt.:222220154555 (Cited on page 19)
Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., and Richtárik, P. (2023). Stochastic distributed
learning with gradient quantization and variance reduction. Optimization Methods and Software 38(1). (arXiv preprint arXiv: 114.:01994.01115 2019). (Cited on pages 2, 4. 19, and 20)
Islamov, R., Qian, X., and Richtárik, P. (2021). Distributed second order methods with fast rates and compressed communication. In International Conference on Machine Learning, pages 4617-4623 (Cited on page 20)
Johnson, R. and Zhang, T. (2013). Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26. (Cited on page 19)
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. (2021). Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210. (Cited on page 1)
Karimireddy, S. P., He, L., and Jaggi. M. (2021). Learning from history for Byzantine robust optimization. In International Conference on Machine Learning, pages 5311-5319. (Cited on pages 2, 3, 4, 10, 19, 20, and 74)
Karimireddy, S. P., He, L.,, and Jaggi, M. (2022). Byzantine-robust learning on heterogeneous datasets via bucketing. International Conference on Learning Representations. (Cited on pages 2, 3, 4, 8, 10, 19, 23, and 26)
13

---

Khirirat. S., Feyzmahdavian, H. R., and Johansson, M. (2018). Distributed learning with compressed gradients. arXiv preprint vrXiv:1806.06573 (Cited on pages and 20)
Kijsipongse, E., Piyatumrong, A., al. (2018a). A hybrid gpu cluster and volunteer computing platform for scalable deep learning. The Journal of Supercomputing, 74(7):323633263. (Cited on
page 5)
Kijsipongse, E... Piyatumrong, A., and U-ruekolan, S. (2018b). A hybrid gpu cluster and volunteer computing platform for scalable deep learning. The Journal of Supercomputing. (Cited on page 1)
Konečný, J., McMahan, H. B., Yu, F., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop. (Cited on page 1)
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images. (Cited on page 74)
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401. (Cited on page 1)
LeCun, Y. and Cortes, C. (1998). The mnist database of handwritten digits. (Cited on pages 10 and 74)
Li, C. (2020). Demystifying gpt-3 language model: technical overview. "https://lambdaalabb" com/blog/ deddddifyiinng---e.//e gpt-3". (Cited page 1)
Li, Z., Bao. H., Zhang, X., and Richtárik, P. (2021). PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. International Conference on Machine Learning, pages 6286-6295. (Cited on pages 2, 9, 19, 26, 66, and 71)
Li, Z., Kovalev, D., Qian, X., and Richtárik, P. (2020). Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, pages 5895-5904. (Cited on page 20)
Eojasiewicz, S. (1963). A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117:87-90 89. (Cited page 5)
Lyu. L., Yu, H. Ma, X., Sun, L., Zhao, J., Yang. Q., and Yu, P. S. (2020). Privacy and robustness in federated learning: Attacks and defenses. arXiv preprint arXiv:2012.06337, (Cited on page 19)
Mai, V. V. and Johansson, M. (2021). Stability and convergence of stochastic gradient clipping: Beyond Lipschitz continuity and smoothness. In International Conference on Machine Learning. pages 7325-7335. (Cited on page 20)
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. (2019). Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1901.0929. (Cited on page 20)
Nazin, A. V., Nemirovsky, A. S., Tsybakov, A. B., and Juditsky, A. B. (2019). Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80:1607-1627. (Cited on page 20)
Necoara, I., Nesterov, Y., and Glineur, F. (2019). Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 1 175:69-107. (Cited on page
Nedić, A., Bertsekas, D. P., and Borkar, V. S. (2001). Distributed asynchronous incremental subgradi- ent methods. Studies Computational Mathematics, 8(C):381 1-407. (Cited on page 20)
Nemirovski, A. S., Juditsky, A. B., Lan, G., and Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-100) (Cited on page 66)
Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. (2017). Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621. (Cited on page 19)
Nguyen, D.D Ene, A., and Nguyen, H. L. (2023). Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv preprint arXiv:2304.0111 (Cited on page 20)
Niu, C., Wu, F., Tang, S., Hua, L., Jia, R., Lv, C., Wu, Z., and Chen, G. (2020). Billion-scale federated learning on mobile clients: A submodel design with tunable privacy. In Proceedings of the 26th Annual International Conference on Mobile Computing and Networking, pages 1-14. (Cited on page 2)
14

---

Pascanu, R., Mikolov, T., and Bengio, Y. (2013). On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, pages 1310-1318. (Cited on page 20) Pillutla, K., Kakade, S. M., and Harchaoui, Z. (2022). Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70:1 142-1154. (Cited on pages 2, 10, and 74)
Polyak, B. T. (1963). Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 1788644788... (Cited on page 5)
Qian, X., Richtárik, P., and Zhang. T. (2021). Error compensated distributed SGD can be accelerated.
In Advances in Neural Information Processing Systems, volume 34. (Cited on page 20)
Rajput, S., Wang, H., Charles, Z., and Papailiopoulos, D. (2019), Detox: A redundancy-base framework for faster and more robust gradient aggregation. In Advances in Neural Information
Processing Systems, volume 32. (Cited on page 19)
Regatti, J., Chen, H., and Gupta, A. (2020). ByGARS: Byzantine SGD with arbitrary number of attackers. arXiv preprint
13421. (Cited on page 19)
Richtárik, P., Sokolov, I., and Fatkhullin, I. (2021). EF21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, volume 34. (Cited on pages 20 and 22)
Roberts, L. (1962). Picture coding using pseudo-random noise. IRE Transactions on Information Theory, 8(2):145-155) 154. (Cited on page 4)
Rodríguez- Barroso, N., Martínez-Cámaen
E., Luzón, M., Seco, G. G., Veganzones, M. Á., and Herrera, F. (2020). Dynamic federated learning model for identifying adversarial clients. arXiv preprint arXiv:2007. 15030. (Cited on page 19)
Borriguez-Barross,
Ryabinin, M. and Gusev, A. (2020). Towards crowdsourced training of large neural networks using decentralized mixture-of-experts. In Larochelle, H., Ranzato, M., Hadsell, R.,, Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 3659-3672. Curran Associates, Inc. (Cited on page 1)
Sadiev, A., Danilova, M., Gorbunov, E., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. (2023). High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. arXiv preprint arXiv:23002.n 00999. (Cited on page 20)
Sadiev, A., Malinovsky, G., Gorbunov, E., Sokolov, I., Khaled, A., Burlachenko, K., and Richtárik, P. (2022). Federated optimization algorithms with random reshuffling and gradient compression. arXiv preprint 21t.i:::220000022111 (Cited on page 20)
Safaryan, M., Islamov, R., Qian, X., and Richtárik, P. (2022). FedNL: Making Newton-type methods applicable federated learning. In International Conference on Machine Learning. (arXiv preprint arXiv:2106.02969 2021). (Cited on page 20)
Schmidt, M., Le Roux, N., and Bach, F. (2017). Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1):83-112 (Cited on page 19)
Seide, F., Fu, H., Droppo. J., Li, G., and Yu, D. (2014). 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifieenth Annual Conference of the International Speech Communication Association. Citeseer. (Cited on page 20)
Stich, S. U., Cordonnier, J.-B., and Jaggi, M. (2018). Sparsified SGD with memory. Advances in Neural Information Processing Systems, volume 31. (Cited on pages 4 and 20)
Su, L. and Vaidya, N. H. (2016). Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 425-434. (Cited on page 1)
Szlendak, R., Tyurin, A., and Richtárik, P. (2022). Permutation compressors for provably faster distributed nonconvex optimization. In International Conference on Learning Representations. (Cited on page 25)
Vaswani, S., Bach, F., and Schmidt, M. (2019). Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In International Conference on Artificial Intelligence and Statistics, pages 1195-1204. (Cited page 26)
Vogels, T., Karimireddy, S. P., and Jaggi, M. (2019). Powersgd: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, volume 32, (Cited page 20)
15

---

Wen, W., Xu, C., Yan, F,, Wu, C., Wang, Y. Chen, Y., and Li, H. (2017). Temgrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, volume 30. (Cited page 20)
Wu, Z., Ling, Q. Chen, T., and Giannakis, G. B. (2020). Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583-4596. (Cited on pages 2 and 4)
Xie, C., Koyejo, O., and Gupta, I. (2020a). Fall of empires: Breaking byzantine-tolcrant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pages 261-2700 (Cited on page
Xie, C., Koyejo, S., and Gupta, I. (2020b). 7eno++: Robust fully asynchronous sgd. In International Conference on Machine Learning. pages 10495-10503, PMLR. (Cited on page 20)
Xu, X. and Lyu, L. (2020). Towards building robust and fair federated learning system. arXiv preprint arXiv:2011.10425 (Cited on page 19)
Yang. Y.-R. and Li. W.-J. (2023). Buffered asynchronous sgd for byzantine learning. Journal of Machine Learning Research, 24(204)11-62. (Cited page 20)
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. (2018). Byzantineroobust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650-5659.
(Cited on pages 2 and 4)
Zhang. J., He. T., Sra, S., and Jadbabaie, A. (2020a). Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations. (arXiv preprint 1905. 11881, 2019). (Cited on page 20)
Zhang. J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. (2020b). Why adaptive methods good for attention models? In Advances in Neural Information Processing Systems, volume 33, pages 15383-15393. (Cited on pages 20 and 57)
Zhu, H. and Ling, Q (2021). Broadcast: Reducing both stochastic and compression noise to robustify communication-efficceni federated learning. arXiv preprint wxXiv:2104006685 (Cited pages and 20)
16

---

Contents
Introduction
1.1 Related Work
Preliminaries
3 New Method: Byz-VR-MARINA-PP
4 Convergence Results
Numerical Experiments
6 Conclusion and Future Work
10
Extra Related Work
19
Useful Facts
22
C Justification of Assumption 2.3
23
General Analysis
25
D.1 Refined Assumptions
25
D.2 Technical Lemmas
26
D.3 Main Results
42
Analysis for Bounded Compressors
46
E.1 Technical Lemmas
46
E.2 Main Results
56
E.3 On the Technical -on-Tiivial of the Analysis
57
F ByZ-VR-MARIIN-PPP:: Simplified Version of Byz-VR- SYZ-VR-MARRIN-PP
58
F.1 Analysis for Bounded Compressors
58
F2 Discussion of the Results
G Analysis without Full-Batch Gradient Computations
65
New Lemma
66
G.2 Main Results for ByZ-VR-MARINA without Full-Batch Gradient Computations
70
G.2.1
General Results
70
G.2.2 Results for Bounded Compressors
G.3 Main Results for Byz-VR-MARINA+ without Full-Batch Gradient Computations
72
G.3.1 Results for Bounded Compressors.
72
H Experimental Details and Extra Experiments
74
H.I Experimental Details
74
17

---

H.2 Extra Experiments
74
18

---

A Extra Related Work
Further Comparison with Data and Diggavi (2021). As we mention in the main text, Data and Diggavi (2021) assume that 3B's is smaller than C. More precisely, Data and Diggavi (2021) assume that B S cC. where c S 1 c' for some parameter è' > that will be explained later. That is, the results from Data and Diggavi (2021) do not hold when C' is smaller than 3B, and, in particular, their algorithm cannot tolerate the situation when the server samples only Byzantine workers at some particular communication round. We also notice that when C' 2 4B, then existing methods such as ByZ-VR-MARINA (Gorbunov et al., 2023) or Client Momentum (Karimireddy et al., 2021, 2022) can be applied without any changes to get provable convergence.
3
Next, Data and Diggavi (2021) derive the upper bounds for the expected squared distance to the solution (in the strongly convex case) and the averaged expected squared norm of the gradient (in the non-convex case), where the expectation is taken w.r.t. the sampling of stochastic gradients
1 where H is the number of local steps. For simplicity consider the best-case scenario: H = 1 (local steps deteriorate the results from Data and Diggavi (2021)). Then, the lower bound for this probability becomes negative when either C' is not large enough or when K is large or when e is close to 3. e.g., for K = 10%, c = c'= 1 C = 5000 this lower bound is smaller than - 720, meaning that in this case, the result does not guarantee convergence. In contrast, our results have classical convergence criteria, where the expectations are taken w.r.t. the all randomness.
only and the bounds itself hold with probability at least 1 K H exp (1==)C)
6
Finally, the bounds from Data and Diggavi (2021) have nonrredueeable terms even for homogeneous data case; these terms are proportional to T. where o² is the upper bound for the variance of the stochastic estimator regular clients and b is the batchsize. In contrast, our results have only decreasing terms in the upper bounds when the data is homogeneous.
Byzantine robustness. There exist various approaches to achieving Byzantine robustness (Lyu et al., 2020). Alistarh et al. (2018); Allen-Zhu et al. (2021) rely on the concentration inequalities for the stochastic gradients with bounded noise to iteratively remove them from the training. Karimireddy et al. (2021) formalize the definition of robust aggregation and propose the first provably robust aggregation rule called CenteredClip and the first provably Byzantine robust method under bounded variance assumption for homogeneous problems, i.e., when all good workers share one dataset. In particular, the method from (Karimireddy et al., 2021) uses client momentum on the clients that helps to memorize previous steps for good workers and withstand time-coupled attacks. This approach is extended by He et al. (2022) to the setup of decentralized learning. Allouah al. (2023) develop an alternative definition for robust aggregation and propose a new aggregation rule satisfying their definition. Karimireddy et al. (2022) generalize these results to the heterogeneous data case and derive lower bounds for the optimization error that one can achieve in the heterogeneous case. Based on the formalism from Karimireddy et al. (2021), Gorbunov al. (2022) propose a server-free approach that uses random checks of computations and bans of peers. This trick allows the elimination of all Byzantine workers after a finite number of steps on average. There are also many other approaches, e.g., one can use redundant computations of the stochastic gradients (Chen et al., 2018; Rajput et al., 2019) or introduce reputation metries (Rodríguez- Barroso et al., 2020; Regatti et al., 2020; Xu and Lyu, 2020) to achieve some robustness, see also recent survey by Lyu et al. (2020).
Barrguu
Variance reduction. The first variance-reduced methods are designed to fix the convergence of standard Stochastic Gradient Descent (SGD) and make it convergent to any predefined accuracy even with constant stepsizes. Such methods as SAG (Schmidt et al., 2017), SVRG (Johnson and Zhang, 2013), SAGA (Defazio et al., 2014) are developed mainly for (strongly) convex smooth optimization problems, while methods like SARAH (Nguyen et al., 2017), STORM (Cutkosky and Orabona, 2019), GeomSARAH (Horváth et al., 2023), PAGE (Li et al., 2021) are designed for general smooth non-convex problems. In this paper, use GeomSARAH/PAGE-10 method that makes the method robust to Byzantine attacks.
The literature on seriance-reduced methods is very rich (Gower et al., 2020).
variance reduction as the main building block of the
Partial participation and client sampling. In the context of Byzantine-robust learning, there exists one work that develops and analyzes the method with partial participation (Data and Diggavi, 2021). However, this work relies on the restrictive assumption that the number of participating clients at each
19

---

round is at least three times larger than the number of Byzantine workers. In this case. Byzantines cannot form a majority, and standard methods can be applied without any changes. In contrast, our method converges in more challenging scenarios, e.g., Byz-VR-MARINN-PP provably converges even when the server samples one client, which can be Byzantine. The results from Data and Diggavi (2021) have some other noticeable limitations that we discuss in Appendix A.
Communication compression. The literature communication compression be roughly divided into two huge groups. The first group studies the methods with unbiased communication compression. Different compression operators in the application to Distributed SGD/GD studied in (Alistarh et al., 2017; Wen et al., 2017; Khirirat et al., 2018). To improve the convergence rate by fixing the error coming from the compression Mishchenko et al. (2019) propose to apply compression to the special gradient differences. Multiple extensions and generalizations of mentioned techniques are proposed and analyzed the literature, e.g.. see (Horváth et al., 2023; Gorbunov et al., 2021; Li et al., 2020; Qian et al., 2021; Basu et al., 2019; Haddadpour et al., 2021; Sadiev et al., 2022; Islamov et al., 2021; Safaryan et al., 2022).
Another large part of the literature on compressed communication is devoted to biased compression operators (Ajalloeian and Stich, 2020; Demidovich et al., 2023). Typically, such compression operators require more algorithmic changes than unbiased compressors since naïve combinations of biased compression with standard methods (e.g.. Distributed GD) can diverge (Beznosikov et al., 2020). Error feedback is one of the most popular ways of utilizing biased compression operators in practice (Seide et al., 2014; Stich et al., 2018; Vogels et al., 2019), see also (Richtárik al., 2021; Fatkhullin et al., 2021) for the modern version of error feedback with better theoretical guarantees for non-convex problems.
In the context of Byzantine robustness, methods with communication compression are also studied. The existing approaches are based aggregation rules based the norms of the updates (Ghosh et al., 2020, 2021), SignSGD and majority vote (Bernstein et al., 2019), SAGA-type variance reduction coupled with unbiased compression (Zhu and Ling, 2021), and GeomSARAH/PAGE-yyg variance reduction combined with unbiased compression (Gorbunov et al., 2023).
Gradient clipping. Gradient clipping has multiple useful properties and applications. Originally it was used by Pascanu et al. (2013) to reduce the effect of exploding gradients during the training of RNNs. Gradient clipping is also popular tool for achieving provable differential privacy (Abadi et al., 2016; Chen et al., 2020), convergence under generalized notions of smoothness (Zhang et al., 2020a; Mai and Johansson, 2021) and better (high-probabilit)) convergence under heavy-tailed noise assumption (Zhang et al.. 2020b; Nazin et al., 2019; Gorbunov et al., 2020; Sadiev et al., 2023; Nguyen et al., 2023). In the context of crrantine-robust learning, gradient clipping is also utilized to design provably robust aggregation (Karimireddy et al., 2021). Our work proposes a novel useful application of clipping, i.e., we utilize clipping achieve Byzantine robustness with partial participation of clients.
Byzantine-robust asynchronous methods. Byzantine-robust asynchronous methods are also very relevant to the problem of partial participation in the byzantine-robus learning. Indeed, the asynchronous methods like Asynchronous SGD (Agarwal and Duchi, 2011 1; Nedić et al., 2001) naturally have partial participation since whenever some worker finishes the computation (of the stochastic gradients), this worker immediately sends the update to the server and the server applies this update without waiting all other clients. However, without extra assumptions asynchronous methods cannot be tolerate Byzantine attacks: Byzantine clients could immediately send any vector to the server to guarantee that their update is received earlier than the updates from regular clients. Clearly, such behavior of Byzantine workers leads to the divergence of the method unless the server has additional information that can be used for acceptance/rejection of the update or some other alternation of the communication protocol preventing the situations when some client updates the model too many times in a row is applied.
Therefore, the existing approaches addressing this important problem rely on extra assumptions. Damaskinos et al. (2018) propose to use Lipschitz filter and frequency filters in order to filter out Byzantine workers. Next, Xie et al. (2020b); Fang et al. (2022) use additional validation data on the server to decide whether to accept the update from workers. This assumption restrictive for many FL applications when the data clients is private and is not available on the server. Yang and Li
20

---

(2023) propose so-called BASGD (and its momentum version) where the key idea is to split workers into the buffers and wait until each buffer gets at least one gradient update. the case when the number of buffers is sufficiently large (at least 273 where B is the number of Byzantine workers), the authors show that BASGD converges. However, this means that to make the step BASGD requires to collect sufficiently large number of gradients such that the good buffers form majority, which is closer to full participation than to the partial participation in the worst case.
We emphasize that in our work we consider different setup of synchronous communications with partial participation. The approaches discussed in the above paragraph cannot be directly applied to the problem considered in this paper without extra assumptions.
21

---

B Useful Facts
For all a, E Rd and 0,p (0, 1] the following relations hold:
2(a, b) = |||
||6|2
||a b1(
(11)
||a bll Σ (1 + a
|||||
2 + (1 + a a) |1b11
(12)
1
+ 1 |bb1
la bll2 v
||l|
(13)
1
(1 - p) (1+ P
p
2 -
p20
(14)
2'
(1 (1- (1 1+ 2) 11 P
P
p20.
(15)
4
4
Lemma B.1. (Lemma from (Richtárik et al., 2021)). Let a,
1f0 2 イ s
then
Votb
a²² by I 1. The bound is tight up the factor of 2 since 2 min 1 11 s Ja+b*
va bj
22

---

C
Justification of Assumption 2.3
Algorithm 2 Bucketing Algorithm (Karimireddy al., 2022)
1: Input: (II,..., F, E N - bucket size, Aggr aggregation rule
2: Sample random permutation
(I(1)..... ................................ (n)) of [m]
3: Compute y/, = 2k=s(t (1-1)+1 Tx(k) for = 1,.... [%/
4: Return: 3 = Aggr (yg ..-...)))
Krum and Krum Bucketing. Krum aggregation rule is defined as
Krum(z1..... Fn) = argmin
Σ 1 -8,-x1111 2;11?
z. =2........ jES;
where St C ( Inn is the subset of n - B 2 closest vectors to Ty. By definition, Krum(z1, Fn) E f.ı,..., .n) and, thus [[Krum(21.....
S maxie[]] || i.e., As-
sumption 2.3 holds with FA = 1. Since Krum o Bucketing applies Krum aggregation to av- erages Y/ over the buckets and || s 1 E L [I=)())]| S maXie(n] || we have that |[Krum o Bucketing(21...... F,)l I maX4e(1) ||
Geometric median (GM) and GM Bucketing. Geometric median defined as follows:
GM......... Fnn argmin ZER
| xill-
(16)
One can show that GM Fnl E Conv(TI,.... Fnn)
{s E Rd
Σ a;æ; for some ai,..... an 2 such that E a; a;= 1.. i... geometric median belongs the convex hull of the inputs. Indeed, let GM( In) on (II,..., and ã x a. Then, the optimality condition implies that I, y f) 2
= f + I. where f is the projection of x
for all y E Conv(r1, Ta). J.). In particular, for all E [n] we have (i 2, 24 +) 2 0. Since
( I, +) = (Ø, - x;)
1 + a - xull?
||
2 | x. 11?
2
2
2 |/ x:4
||:|| 2
2 | 2
| || 22113
we get that || - x 2 | - x for all i [n]] and the equality holds if and only if ē = Therefore, argmin from (16) is achieved for such that x 3, meaning that GM( I,) Conv(z1...., I.). Therefore, there exist some coefficients a1,...,a,, and GM (M..,.... = E OgT,, implying that
an 2
such that Σ 0 =
[GM( ka)ll S an aul|=all| max ||:|||- /E(n)
That is, GM satisfies Assumption 2.3 with FA 1. Similarly to the case of Krum o Bucketing, we also have ||GM Bucketing(E1, 2x)1l < max4e[n] [|
Coordinate-wise median (CM) and CM Bucketing. defined as
Coordinate- median (CM) is formally
CM(# x.) = argmin
Σ
x 1/1
(17)
zE2d
i=1
where || 1/1 denotes no-nrmm This equivalent geometric median/median applied to vectors I Zn component-wise. Therefore, from the above derivations for GM we have
[CMM(,,..., < max [u:]locs (E(m)
CM o Bucketing(z,...... In)le < max ||0:|o00
[E[n]
23

---

where || ac denotes &oc norm. Therefore, due to the standard relations between é2- and Eo nooms, L... ||a|boo I ||a|| - Vdllalloo for any IR we have
vd max ||
sE(n]
||CM o ( ,n).
dd | se(n]
i... Assumption 2.3 is satisfied with FA = vd.
24

---

D General Analysis
D.1 Refined Assumptions
For simplicity, in the main part of our paper, we present simplified versions of our main results. However, analysis works under more general assumptions presented in this section.
Assumption on Ć. In all the results of this paper, assume that 2 C max fwan/d). This condition ensures that the robust aggregation makes sense when C₁ = 1, i... at least 1 proportion of sampled workers not Byzantine ones when Cg = 1.
Refined smoothness. The following assumption is classical for the literature on non-convex optimization.
Assumption D.1 (I-smoothness). We assume that function f : Rd I is L-soohhh, i.e., for all Ir y/ Rdd we have
[)) Vf(illl s L||= yll-
(18)
Moreover, we assume that f is uniformly lower bounded by f E IR, i.e., f" = inf [(x). In addition, we assume that f; Lmmsohhth for all i E G. i... for all z; y IRd
[[Vf(()) - V((ii)l S L ||| vll-
(19)
We notice here that (19) implies L-smoothness of with L S. Eieg Li, ie.. smoothness constant of f can be better than the averaged smoothness constant of the local loss functions on the regular clients.
Following Gorbunov al. (2023), we consider refined assumptions on the smoothness.
Assumption D.2 (Global Hessian variance assumption (Szlendak et al., 2022)). We assume that there exists L 2 such that for all x, y E Rd
Σ [Vf(=) EEG
-V
vf(1) L3 yl1
(20)
T
We notice that (19) implies (20) with La < maxxee L. Szlendak al. (2022) prove that Ls satisfies
the following relation: L La < L3 S Livg. where L == _/4 Eieg L2 In particular, it is possible that 4 = 0 even if the data the good workers is heterogeneous.
Assumption D.3 (Local Hessian variance assumption (Gorbunov et al., 2023)), We assume that there
exists L+ 2 0 such that for all 2, y Rd
1
(1. v) AI S
w|ll
C
E
(21)
E
where (x, = Vf(()) fv and ( y) is an unbiased mini-batched estimator of (2, y) with batch size 6.
This assumption incorporates considerations for the smoothness characteristics inherent in all func- tions (ft,) j(]. the sampling policy, and the similarity among the functions hes.hee.eeem
Gorbunov et al. (2023) have demonstrated that, assuming smoothness of (fr,) ) ieG.) Assump- tion D.3 holds for various standard sampling strategies, including uniform and importance samplings.
For part of our results, we also need to assume smoothness of all Jegg jE[m] explicitly.
Assumption D.4 (Smoothness of ft, (optional)). We assume that for all G and [m] there exists L,,3 2 0 such that Si,j is -smoooh, i.e., for all xr, Rd f1,) - (z)l < Lr, yll.
(22)
Refined heterogeneity. Instead of Assumption 2.5, we consider a more generalized one. Assumption D.5 (2 >eeterogeneitty We assume that good clients have (B, (?) -heterogeneous local loss functions for some B 2 0, 2 0, i.e.
- BIV
Vr E dd
25

---

When B = O, the above assumption recovers Assumption 2.5. However, it also covers some situations when the model over-paranne wver-parameterieed (Vaswani et al.. 2019) and can hold with smaller values of ç². This assumption is also used in (Karimireddy et al., 2022; Gorbunov et al., 2023).
D.2 Technical Lemmas
Lemma D.6. Let X be random vector in Rd and X clip, Assume that [[X] RR
and ||||||| & X/2, then
E | x1|?] I 10E ||X - =012
Proof. The proof follows a similar procedure to that presented in Lemma F.5 from (Gorbunov et al., 2020). To commence the proof, we introduce two indicator random variables:
X = [X-IXI>> = { 1, if |X|| > X, otherwise
1, if x - x
. = [x-Ix-=1|>3 = (0
otherwise
|
Moreover, since | S |||||| + || - xI1
+ || - =z/1, we have x S Using that we get
_
A
x
x min
|
X
X
X
X (1 x)X.
By Markov's inequality,
A
X2
Binl = PP X - x|| >
= I |X x1|
S x2
E [|XX - -
(23)
2
Using || - x|| S || + ||^/|| S X + //2 2 we obtain
31
E |
=1
E
|
21
1113x +
1 - (1 x0]
A
+ || - =x1((11 x1
E
X
X
X
A
E
X
|
x
+ 1|x - x11 x))
|
31
+ 1|X - 21|2 -x11= =
E
where in the last inequality we applied
S 1.
Using (23) and x S 1) we get
-18- x1] <
9X²
2
E
[|X [ + []]X - x0|
4
10E
[||X-
x
x=|2]
Lemma D.7 (Lemma from Li et al. (2021)). Assume that function f is L-smooth (Assumption D.I) and x+1 = xx rggt. Then
f (a)tt) sf 2 (z
(1-11) 1- 112 + 110
Vf (z*))}
27 2--2)
Lemma D.8. Let Assumpiionsss D.I. D.2, D.3 hold and the Compression Operator satisfy Definition 2.2. Let us define "ideal" estimator:
Σ
(((x+t1),
On 1,
[]]
GK
g++1
g
+ vf (1)+1) (x*xx),
G, and GK (1 8)C,
g*
Σ clip, (o(A: (x/h1, (1)t),+))))
C. 0 and Gk > (1 8)C.
G
26

---

Then for all k 2 0 the iterates produced by ByZ-VR-MARINA-PP (Algorithm 1) satisfy
A1 E ||| v [1*
8. 8-Pog
(1 11pp p) (1 4 E |1oe [)(
+P (1 8)
E B B + +
+ (1 - p1pp (1+ 2 PO
"oww." + (10w + +1)4] + 10 + 1)c2
B |1
/
where PG Prob & 2 (1 8)C} and Pot Prob {i g G 2 (1-
Let examine the expected value of the squared difference between ideal estimator and full gradient:
Proof.
V. (2 11-]
A
E
Es
||ght|
Vf [x=+t)
(1 p) poL
EN
9* G
Σ
clips (o(2, (a (ootl,=4)) v. (ar4tt)
v.
[[3]
iESt
+ - (1-p)(1- - -
Eu |1oe vs(aa)) |1²] 1111 + pE
Σ
[/i(tht))- - V k11)
C
Using (12) and V (x*)
Vs (a+) we obtain
27
B
E
ER
g
+
clip, (0 (3. ( - Vf (o
113)
C
iEg
E
34
Σ
clips (2(3: (5+t1, ( ( v. (xt)
[3]
G
leog
(12)
1 +
p
E
v (1+))1
(1+
Th
Σ
clips (o(3. (a*)),)))) - (Vi(a+1), - -V
(3]
LE0g
(1+ 2) E ||s
)(( ||(]
+ (1+
E
Es
1
Σ
clips (e(A) (()))))))))))))))())))))))))(( A (2+ ,.a
[3]
G
Let us consider the last part of the inequality:
1
(e(3 (ott),at)) - (w 200))
B
E
Eg
clips
[3]
G
FEG
E
Es₁
Es
Σ
clipA
(e(A -A (2+411
[3]
C iEcg
27

---

Note that Ge 2 (1 - 5)C in this case:
B' < C(1 8)
1
E
Es
Σ
Bs
|| clips (0 ( 1 (24+1 ,2th)
-
x(t))) )1r] [3]
< C(1 - 8)
1
E
Σ
Esp.
[o8
Es |CLLps (o(3. (s (14111,z))) - (z ,2th) )19 [3]
LiEg
Ex ||cLipa (e (a (2)))))))))))) - - (2tt) xx4) y19] [33 (24)
Σ LiEC
Pog
C(1 6)
where Tøz is an indicator function for the event (i E g C 2 (1 8) c} and Pot
Prob EiE g | C. 2 (1 - C} is probability of such event. Note that Es₁ [ = Pog In
case of uniform sampling of clients we have
ViEg 9 Por = Prob {i E gE
| C (1-8))
C
((²)))
Σ
npG
(1-6)0SISC
(( ) ( (c-i) ) ((==1))")
Σ
PG
(1-6)0StSC
Now can continue with inequalities:
POr
clipA (0(2:(1t) e+l (z=t).=t)) - 1 (c (cat).zzt) ) [3]
B <
E
Ex
C(1 - 8)
LiEG
C(1 8) E
Pog
Σ Ex LEg
R2
clips (o(2: (3 (a x2+)) 1 ( , ||'] [3]
(12) Pag
Be /clpp (0 (0( ( ( x)) م (a ) [3]
TR.
2
C(1 6)
LIEg
Pgt
E
Σ 2E
|
(o*t1 ,at) - a (1tt1 , ا ||] [3]
C(1 -8)
Lieg
Using Lemma D.6 we have
Lemma D.6
Pot
||@0 (3. (a+t),=t) - A. (att1 ( )(') ||]] [3)
B
E
20E
EQ
C(1
8)
Lieg
Poz
Σ 2
|
(2r (at) - a (srtt1 = | [3]
C(1 8)
LiEg
20-P Pot E
| A (5 _.n)) ( - D. (2otit1) , set)) 1i] [3]
EP
EQ
C(1 8)
Lie
2. P.P E
Σ Lieg
Ex
|||
A
(a*+1 ( A ( 11 [3]
C(1 - 8)
C(1 - 8) E
20 Po
Σ EN Lieg
EQ
2 A (2ctt) ( )
Σ مهه (
(a - )2? [3]
150
2- Pog
Σ Ex ||||, (a*+1 , - A 1 ااه )1( 1 [3] Lieg
C(1 -8) 8)
28

---

Applying Definition 2.2 of Unbiased Compressor we have
20 Pot E Bi - C(1-6)
Σ (1 + WB
A (z 1 x²4) 112 - || (2nt), ,<+))
(2att,=*)) 1|? [3]
LiEG
.EG
2. Pop E
Σ ||ا, (x*) - A (zttt1 "==",,,,")" )²2
[3]
C(1 6)
LiEG
20 Pot EE
Σ (1 + BB) A (1o 24 - A (2 x²t) 12
C(1 8)
LiEG
20 Pote
Σ (1 W ||ا (2#t1 )
Σ EEG
Ex || (z )| [3]
C(1 6)
LiEg
2. Pat
+ C(1 5)
E
Σ (2 (x*t1 ,a²) - A (z )1² (a(t),=²))
[3]
LiEg
Now we combine terms and have
20 20-Pog Pot
E& || A (snt)1, srt) - As (a ,,,),,,,)) 11 [3]
B S C(1 () 8)
(1 + wF
LiEg
20 Pot
+ C(1 8) wI
Σ ||ا (,x4+,,,*)1
,1x))²² [3]
Lieg
2. Pgt
06 E
Σ 1| (on4t1 ,0,) - a (1att ,-,) [13]
C(1 - 8)
LiEg
20 Pog
Σ E& || | (a4+1 (,,tt1,aa) - A (1a+11 1 20t))) |1( [3]
(1 + +W)
8)
Lieg
20 PoB
+ C(1 5) Wi
Σ LiEg
| (a/t1, - A (1rt-1
- - ر| + ه|ا (ar , 11? (3]
2. P. E
Σ || (o* ,aa)) - A (z. , |1 [3]
+ C(1 5)
Lieg
Rearranging terms leads to
B < C(1 8)
20 O8
(1 + WW
Σ
En
A (2=+1, x - D (2rttl |لاي| |1] [3]
Lieg
2 2-Pg%
|| A (ar , - A (a+t1 || ? | [3]
(10w + 1)T3
C(1 (1-8) 8)
20 Pog WE
ΣlIa
(+1 xx || (3)
C(1 8)
Lieg
Now we apply Assumptions D.I, D.2, D.3:
20 Pog
Bi S C(1 8)
(1 (1+u0 WI G _ | b+1 x* 112
P.
(10w + I)E
[GL || k+1 - 112
C(1 8)
20 Pog
WB
[GL2 1|0
- =']
C(1 8)
29

---

Finally, we have
Po G Bi C(1-6)
(1OW1z + (10w 1)12
10( + 1)21
E || 2511
b
Let us plug obtained results:
B1 S
1 +
R 11oe - [](aa)]]]
4
4
2 Pat G
(10013 (10w + 1)73 +
10(w + 1)c3
+ 1
[|1 - -x1111
p
C(1 - 5)
b
27
Let us consider the term
Σ Vsi(z+t1) (((alttt
C
Vii(att))-
- V))
([ 2
G C iEg
G 160%
1
E
Σ
) -Vf
(1 (1-5)C
1
E
Σ Ioy [/i(ttt1)- (
(1-6)C²
(1 -1- 8)C
LiEg
Using definition of Pog we get
PØz
E
1
-
E
[li(x+t)) - (s(attt)11
Gh
8)C
C
iE
Lieg
G Pos
Vfi(at+1) { 1
8)CG
Lieg
Using Assumption D.5 we get
G.Poz
E
V
fi(++tl)- - (s(attl)
<
E [B f()] +
(1 8)6
iEGs
8 Po
E B [ +
(1 8) Beam
8 8.
E [B]])(<)]1
(25)
(1 (1-8)
30

---

Also, we have
A1 |1ght [
5. P.P
$ (1 BIPGBI + (1-11) (1-p)(1
P ||0* [
+P (1 5)
E |BI +
$ (1 p)pG (1+
p
E
4
+ 11pppp
pipc
(1 (1+
p)
4)
2. P. oh G
C(1 6)
(IWWL" + (10w 1)43
10( + 1)23
||1l=t+1 1²]
8 P.P
+ (1- - p) PP)
(v + (1 8)
[IV](()] + c7]
To simplify the bound we use
(1 + p 1) and obtain
8. S.Pox Pot
A1 S (1 pp)p
1
+
E
1100 - -V(=>>> + P E [B]V](+)]]2 + +c3
4
+ (1 - p)pa
(1
4)
2. Pog GG
1owl. + (10w + 1)62
10( + 1122
E -
p)
O(1 61
+ (1 p)
PG)]E
|190 -Vf(=*)1
$ (1 p)pG
(
p
E
119 [f(a>>11))
4
(1- p)P (1
p)
1)
2
Pag GG
1owi (100 + 1)42
10( + 1)23
E -11==tt-='11))
=011"]
C)
b
8. 8.P
+ - p)(1 - pGG (I + 2) E |||* - -vf(=>)]' |11]
+ (1 8)
[BI + +c?
8.P Ps
$ (1 - p) (1+
4
p
||0* - [f(+t)11 + (1 8)
E [[V]f + +c
+ +1-P))p p)pa (1+ 4) 2 2.Pag"
Pog"
(IOWL3 + (10w 1)23
10( 1)29
Lemma D.9. Let define "ideal" estimator:
G Σ
((((*++),,
Gn 1,
[1]
ghtl= = 9* + (z
Vf (x*),
Gn 0 and Gl < (1 8)C, [2]
g + CE
Σ clipy (1 21
Gn and G 2 (1 8)C.
[3]
LEGE
Also let us introduce the notation
..... clip Act1 (o (Do(att), att)) Then for all k 2 0 the iterates produced by BYZ-VR-MARINA-PP (Algorithm 1) satisfy
ARAgg k+1 ARAgg clápx--.
(e
A₂ E ||| - |2]
||ARAg9 (fo. " vf(x 11]] [m]]
< p'
Et
+ (1 p)PCEE
Ex
1
clips (0 (e (2 ,())))
ARAg9 k+1
I [3]
G iEgg
|| - -V(()) - ARAg9 k+1
+ - (1-p))11 IE
[|2]
31

---

where PG = Prob {Go 2 (1 - 8)C}.
Proof. Using conditional expectations we have
A2 E Ex
|1g 1
EE
||ARAEE (Lo JiESS) [[(a++))| [1]]]
+(1 plpoB
g + G
Σ clipx (0 (0(3, (2 (2 , ,²a))) -(0*
ARAgeQ k+1
LE98
g* Vf(x - - (gt ARAgEO R+11 11 [2]
+ - (1 PG)
Ex
V5(x
After simplification, we get the following bound:
A2 S pll
E&
||ARAgE
(1o,+t)
(s(x+t))]]] [n]
+ (1 P)PGE
Ex
clipy (o (2 x²a ,(1))
ARAgg k+1
[3]
G
iEgt
V/ -((()) - ARAgE&*11 [2]
+ - (11-p)(1 PG)
Es
Lemma D.10. Let Assumptions D.I and D.5 hold and Aggregation Operator (ARAgg) satisfy Def- inition 2.1. Then for all lo 2 0 the iterates produced by ByZ-VR-MARINA-PP (Algorithm 1) satisfy
Ti = E Ex ||Agg (19)
hies.) )| [1]]
8GP ot cBB
4GP 4GPgz cōς²
+2B
E | (z*) + L2 1112tt12 +=
- -|1p]
(1 5)² + +
(1 01c
Pgz GB
Pot G5²
where B = and ? = 0 when Ō = n, and B = (1 (1-6)0 and ?2 = (1-6)0 when Ô n.
Proof. Using the definition of aggregation operator, we have
|AAAg (1g, Jies.) v k || [n]]
T
E
Es
(12)
Ex
ARAgg (1g, k+ Jies.) Gk
Σ V
fa(aht1)
[
iEgs
+ E
Vfilah+l)- vl(+tt)
c C LEgt
32

---

Since 1 Σ
Vf((I*+1)= = V)(x*+1) with probability 1 when Ö = n, we can estimate the last
term as
E
Ex
vii(t=+1)- - )
G
i =n
E
Σ Ex [|//((=tt)) -
2 [4
i <n
LEgt 6
i
Σ E [[i( -
i <'"
(1 (1-8)C
icg
irŌ=
(As. D.5)
S
Pak [1-6)C
BE | |||} +
[E
+ (2))
irc <
where
0,
if Ō n,
0,
if Ō
B = Pot GB
and 2:= =
Pos Gx2
if Ō n,
if n
(1-8)0
(1-8)0
33

---

Using the above bound, we continue the estimation of T1 as follows:
Ti
(Det. 2.1)
S E
C
Σ
Ex
V/ (24t1) - v. (a*+1)) |1 [0
G G
0
0
L.ES% it
+ BE
|||]]
+ +?²
(12)
E
cō
Σ
2 (2 vs ( -
/| [4]]
G G 6
1.1E9 iff
+E
cō
Σ
E V -v [b= || [1]
Gk (G -1 1)
1.199% igft
+ BE
|| + ?²
-E
Σ 4E
(-
-f [m]
BE f k+1 || +22
Pazel co
4 ( - V (2++1) |1] BE ( |2 +
$
(1 5)C iEG
D.5)
[GGP %
coB
+ B
E
V f (2 |1
+
4GP o oōc²
+ +?
(1 8)C
(1 - 5)
(12)
8&GP oy cbB
+2B
E
2|
|| (1++1) - v. (1]
(1 (1-8)Ć
4GP o2 c8C²
+
(1 (1-8) -)
(GT-3 (1-
|SGPog oz cbB
4GP cōC² 6
+
2B
E
Vs 12 + L2 12llatt1 - 2010]]=
+22
(1 - ÓjC
which concludes the proof.
Lemma D.11. Let Assumptions 1.1, D.2, D.3 hold and the Compression Operator satisfy Defini- tion 2.2. Also let us introduce the notation
ARAgg k+1 k+1
ARAgg (clipr..
(a( (aat),,a))))
x(1)) ,...., clip A (o (Dolaht1, ,2))))
Then for all le 2 0 the iterates produced by BYZ-VR-MARINA-PP (Algorithm satisfy
2
T2 E
Ex
1
Σ
clips ((
k+1 -RAAg50
[13]
C iEct
8GP ot
(11 + w) C2
<
+ (10w + 1))2 + 10
cdT [1|a* 2x* 1111
(1 - 5)C
"bb
where Pog = Prob {i g
06 2 (1- 6) c}.
34

---

Proof. By the definition of robust aggregation, we have
2
1
Σ clipy (e(2, (a (11))) ARAgSQ k+1
T3 = E
Ex
[13]
G
LE
< E
c5
Σ
Fx
casps (0 (3: (oft),at))) clpp (0(3: (art),at))
18
L. 1i4
where D2 = (GG - 1). Next, we consider wair differences:
clipx (o ((.t),aa)) clipy (o Av (2 ,.a )) [3]
(11, = Ex
(12)
1 2F
euss (0 (3: (at111, (111,,,)))) a. (c+11, + ai (ch11, clipa (o (2 ))) [e]
| (x xx A (z , 11 [3]
+ 2B
(12)
cclip (0 (A, (a*t2 = A (a*t1 x 1| [3]
S 4
+ +4
A (xtt1 x**) clipA 00 A (Itt xx4) [3]
+ 2
|| (a+ _na م (1+ ,
xx )² 11² [3]
(12)
<Lip> (0) ( ( (I++1  A. ( x || [3]
< 4EE
+ 4E
A L ++1 xx - clips 0 A (I
/| [3]
+ +4E+
A a R+1 ) a (1اtt xτ 1|² [3]
(1 A+1 x A ( ) || [3]
+ 4E
35

---

Now we can combine all parts together:
f2 =E E
Σ 12(,1))
GC 1)
1.1E9 1311
||cips (e (2tt), Do (a#t1, u|² [3]
S E
Σ
4E
D2
1
||ا|| (1tt) - clipy (o(5i (1) x²4) ))) || 33]
+ +E
4E&
D2
1.EE
if
+ E
1
Σ
4E& |هاا (otttlaa)) - A (a )12 )|² [3]]
D2
V.Ee {
+ +E
1
Σ
4E,
|| (24t2, - A ( [3]
D2
V.lEgt if
Rearranging the terms, we obtain
|| clips (e( (att), - D. (24t11 (=,+),=*))] /|² [3]
E
Σ
SEx
D2
E
1
Σ
&E || (ant) - A ( 11 [3]
D2
Ef1
It leads to
||lip (2. (artt),z)) - A (oott,,0t) 1 [118]]
122 < E
SE
Gk
sege
E
8E
| (a*+1 , A (a*t11 "
, 1| [3]
ck
Lemma D.6
E
Σ SOE
(2(t1, - A. (2 ا ||² [3]
Gk
lEgE
8EL
|
(1 ,+) - A ,+,+,,,)))' ||² [3]
G iEG
36

---

Using variance decomposition we get
T. S
E
SOER
||o| (ā. (2ot1 - || [3]
GE 1ES
80EK || (a=+t1,=))) 112 [3]]
E
GC
SE9
|| (14t1 ,0t)) - A (aftt), 11 [3]]
+ E
SE
iEDE
Using properties of unbiased compressors (Definition 2.2) we have
80(1 + WEx || | (s .aat) 1 12 [3]
72 S
E
G
LES
80E | (3.tt1 ( 11 [3]]
E
G
SEgE
Σ SE ||اا (14+1 , A (2t ) [3]]
+ E
$590
Also we have
12 S E
1
80(1 + B) ||ام (akt1, (20) - Ds (a*t1 (a++),,+)) /|² [3]
Gl
E
1
80(1 + 1)
| (a* ( ||? [3]
iECk
80E2 | ( || [3]]
E
G
+ E
Σ
SE
|| (1+t1 , - A (artt || [3]
SECE
Let us simplify the inequality:
1/ S E
Σ
80(1 + 4
|| (1*+11, )²
,x*) - As (a*t1 ,,,),,,)))) ||² [3]
G
iEgt
1
| (a , || [3]]
+ E
SOWEE
G
SE ||
(aRt), - A (2ohit) , ||² [3]
+ E
G
37

---

Using a variance decomposition once again, we get
80(1 + Ex ||اا (z ,00) - A (2 || [3]
72 S
G
80w ||ا (1++t ,x,) - A (2/ttt ,et)) || [3]
+ E
iEC
SEE ||| (z ,xth) A (z. ,0*)) 1| [3]
+ E
G
1E99
E
80wlE
|| ( , 11 [3]
LEC
Using similar argument to the one used in the previous lemma, we obtain
T2 s
E
Pay
80(1 + WBB
||ا. (I*+1 x²t) A, (x x || [3]
8)C
iEg
Poz
Σ
S0WlE&
||اا , (2 > 11? [13]]
(1 6)C
P 0%
+ EE
Σ
SLE
||ا; (o _ - a (antt ااع 1| [3]
8)C
P
E
Σ
80WlE
||
(2+t1 x 11a [31
(1 8)C iEG
Using Assumptions 1.1, D.2, D.3:
[80[1 w))L G3 C3
8(10w + 1)GPPs 53 43
fg E E
| 211 E
|| 2+11
(1-8)Cb
(1 (1-
80GP 80GPgtwl'
+ E
|1 =2112
(1 (1-8)C
Finally, we obtain
Te = E
Ex
1 Σ
clipx (e(3, (att1,
ARAgg k+1
1 [13]
Gk SE9g
8GPg2 gb
(1001 + ww) b + +10w + +1T3 + 10 cδE [1Ia - 11
C1
<
(1-5)C
Lemma D.12. Let Assumptions 2.3 and D.1 hold. Also let us introduce the notation
ARAgg I+1 ARAgg ClippAm (o (Ai , x+))) ..... clip (o (Ao(attt) att) )))
Assume that AR+1 = ax4ts |1att1 2+1l. Then for all k 2 the iterates produced by Byz-VR- MARINA-PP (Algorithm 1) satisfy
(
-aaentt)VV(yAA VS(a"t) ARAgg k+1 2 [2]
T3 = E Ex
5 2(12 Faa )B [|latt1 - =01
38

---

Proof.
k+1 2
T3
E&
[ -. V5(aa)) ARAgEO
1 12]
(12)
x E
Ex 2 2l
- vf(at))] 12 1//+2 +
ARAgE
k+1
|| [2]
Using L-smoothness and Assumption 2.3 we have
(12)
T3
S
EB
E3 2L | 1 x111 + +2 [2]
$ E
22 12 -x 11 + aF22
|| h x 1 [2]
S 2 2
+ F2
1 )B
|| 2111
Lemma D.13. Let Assumptions 2.3. D.I, D.2. D.3, D.5 hold and Compression Operator satisfy
Definition 2.2. Also let us introduce the notation
ARAgg ++ ARAgg clippnn (o (3((0tt1,2t)) clipAen (o (Aolattt,,ao xtt))
Then for all k 2 0 the iterates produced by ByZ-VR-MARINA-PP (Algorithm 1) satisfy
E |1ght1
Vf (2*+1))
S 4) EE 110t Vf (=+))))
(x+) || + 52 + PA
+
BE
11 =
4
where
80 PGP
GP 06
160
GP ct
A
W + 24
B + 6B + (1 - -PG) +
PG
(1 8)C cdw
I
C
(1 (1- 8)C
p
P
4
D
C
(10w + +
16
p
PG (1
GP gh
8)C
c0(10w + +1))
37
4
160
GP
80
12
G
+
PG (1- (1-8)C
(1 (1+ + PcP o6
(1 ww)
P
p
b
4
4
(1 pG) F2
+
p
P
8P 5k
12cG +p) + +6B, ò= 2
8P gt
(6G
B = 2
@
+p tp)=
+ D,
1-8
1-6
oot GB
Pap G
and where B == 0 and D = 0 when Ō = and B = (1-510 and D = 1-876
when C <
pc Prob { & (1 -8)C), and Pog Prob (i E G Gk > (1 8) C)
39

---

Proof. Let us combine bounds for A1 and Ag together:
Ao
E |1ght1
Vf (1
<(1+ p
E |
Vf
(2(tt))11
+ (1+ 2 p
E 1gghz gut111]]
2)
<(1+ 2)
p)
A1 (1
2
A2
p
$(+ p)
(1 p)
(1+
p
||g* VS [1*
2
4
+(++5)
(1-1)
4
2. Pox" "
(IowL, (10w + 1723.
10(w + 1)02
B [lahta x911
plpo
p
b
8 Pos
-1+ 2
E [ ff()) +()))
(1-6) 6)
1 p
pe E&
|RAgg
V f2 ).... V(t(z(+t)) ((((a+t)))*
[111]
|+ p
2
(1 - --p)pBB
Es
Σ
clipy (e(
ARAgE
[3]
Ge
+ [+ p
(1 p1 - (P)]B ER
[ - vs(x*t ARAgeo
A
k+1
2 [
Finally, we obtain the following bound:
(12)
Ag 2 1 - 4
||0t
Vf [1²
8 gb n
10(w + 11
10wL + (10w 1)23 +
EE [[a - 101
-
P
C
PG
b
18.Po
+2p
E B [[ + +
8
(p
2) E
Es
|RAAE (2ft(t (fntt))))) vf(
2 E
Ex
Σ clipa (o (S. (2*t1, x =
ARAge
x+1
1 [[]]
GK icgt
2
(1 JE
E& [ - - ARAgg
vs(x+)
k+1
[12]
p
40

---

Now, we can apply Lemmas D.10, D.1I, D.12:
Ap
E2
|19 ++
Vf [2 | |1]
$ (1 2) E |10 vs (5 (a+) [²]
8 PO n
10( + +1
10Wl12 + (10w + +11
E [[ 2-1
p C Pa
b
8&PP d6
c5B
+ + 2)
+
E || (2**) 12 + 1,2 1
(1 - 8)C
GPgg
+ +4(++2)
2² + (p + +222
(1 8)C
GP c/ [
B
80(1 + w)
cō p - 2²11
(1- 8)C b
2
GP c/
B
8(10 +
1 cōllz
(1 8)C
2
GPØg
80
wL cL'ccol=**t - -
(1 8)C
(1 PT) + 2 )B 11
p
8P gt
+ 2p
E
B Vfxxl|| + 5
1 1
Finally, we have
E
[19 8+1
V
[1
27
- (1 - 4) E ||10~~ - Vs -1f (x+)) |1]]
|| (x*) |1] + DC² + PA
+
BE
[1 1=]]
4
where
32pa
Pggn
[1701] (10w + 1)23 10( 1)23
A
1d
C
b
+
8
(1 - S)C Poed
CP
(80(1 w) W)
fi b
+8(10w + +)12 + 80wL2
p²
24GG dr cbB
+ 4
+6B L2 16(1 (po) (L2 + F2aii
D
(1 (1-6)C
and
8P gh
8P ge
(12cG
6cG
B = 2
B
+p)
+ +6B, カ= 1-2 T
+
+ D,
1 -
C
P G (1-810
where
D = when Ô = n, and D =
when & < n. Once we simplify the equation, we
obtain
4
80
SOPPPog og
GP gb c8
4
160
GP
A
=
D
P
C
w + 24
+24
(1 (1- -)C
B + 6B + -(1 pc) +
p
p
PG
(1
8)C cdw
L2
+
4
8
PPPPgn n
(10w + +1)+ + PG (1 - 8)C
16
GP %%
co( co(10w + +11)
L3
P
D
C
p
160
GP P
(1 + w)od + PaP c6 (1 + (ww) n
80
22
+
P
P
PG
(1
8)C
()
b
4
4
+
(1 PG)
F2 F2
41

---

D.3 Main Results
Theorem D.14, Les Assumptions 2.3, D.1, D.2, D.3, D.5 hold.
Setting Ast1 =
2 maxieg T4 1111 x* ||- Assume that
0<9S
4B <p Lt VA'
where
80
Po
PCPGPa
GP cō
gh
4
160
GP ob
A
W 44
B + 6B + -(1 pc) +
PG
8) cdw
L
P
p
C
(1 8)C
p
p
4
PGPggn
16
Gp
+
(10w + +1) + PG (1 - 8)C o5(10w + +1)
1
p
C
+
160
GPgg
(1 + w00 + pa P 0
80
(1 + w)
n
f
P
P
(1 (1-8)C
C
b
+
-
(1 PG) 2
D
8P 5h
8P gz
12cG
6cG
B= 2 B
+D) +6B, H 2 2
+ p + D,
1-8 C
when Ö = and B = 11- and D = Poze G
Pot GB
and where B == 0 and D = 0
c
(1-833 when & <
and
C
((--1) ( (())))
Σ
Pot
npG
(1-8)Csisc
PG Prob (G) 2 (1-8)C}
( (0)))=))))))
n n- G (
Σ
C -t
siso
Then for all K the iterates produced by ByZ-VR-MARINA (Algorithm 1) satisfy
250
|1
E
1
(K 11)
4B
where FKK is chosen uniformly random from xº x1 x..., K.K and Φ0
((x0)
27
1 Vf (22
p
42

---

Proof of Theorem D.14. For all k 2 0 we introduce of = (x*) f + 2x Using the results of Lemmas D.13 and D.7, we derive
l1oe ff (a**) )|²
p
E [
(D.7) S
E
f (x*) ,
1
L
|1 -
7
111*= Vf -Vf 12)
27
2
2
F
V (1*) [1²]
27 IF
|1a
- Vs (x(tt1))1²
2
p
f (a*) - (
1
1.
10-1-=+11 + 2 l1 - Vs (2+))) (2+))))
E
27
E
VI (x*) 11]] + 27 (1 (1- p
||s* - Vf V (1+ [1a]
E
2
4
27
BE
|VVS (x*) |1² + -5
PA
1 1..tt_004p -
+
P
4
E [f (x*) - f++ + 27
((1-2) P)
+ P
||0** - Vf (z+ ||] 2
=
p
4
4
E
P
1
(1 Ly- - A E |||2//1 - -s<1??]
1 (1-
1
E V [1]
+ 2y
p
= E [0+] + 2D
+ 27
(1- - .,- - A72) HE [|lak+]] - , 111
P
7
4B
V (x 17]
E
2 p
Using choice of stepsize and second condition: 0 <<7S
1
.B < p and lemma B.1 we have
4B
T.
E [ S [a*]
2D
1
4B
E [())
p
2
p
Next, we have 3
(1- 18 0 and +++1 2 0. Therefore, summing up the above inequality for
k = 0, 1,
K and rearranging the terms, we get
Σ E
2
E [ - E 11)
K
k=0
7
18
(K + 1)
k=
48
2 (E [T0] - []
7 (1 48
(K + +1)
p 4-8 48
2E [$00]
4Dę²
7 11 48
(K+
p- 4B
Theorem D.15. Let Assumptions 2.3, D.I, D.2, D.3, D.5, 2.7 hold.
Set A441
maxieg Lu | 2* I|. Assume that
0 0475 L+ V2A'
8B <p
43

---

where
80
PCP
o
GP ob
160
GP o'
A
w
+ 24
B + 6B + (1 - -pc) +
PG
(1 8)c cdu) 1??
p
C
(1- 8)C
p
p
+
P
4
p
8
PPPPag
C
(10w + +1)+
16
p
PG
GP o
8)C co0 c100 + +11
3
4
160
GP s6
80
+
PG (1 (1-8)C
(1 +
w)
+ PcP c
(1 + w
0 b
p
p
4
4
(1 PG) PG)
+
p
P
8P&t
12cG
8P oz
GcG
B = 2
B
+P) + +6B, π =2 1- C +D) +D)+ + D,
1 1-8
C
Paz GB
Poze
and where B := 0 and D == 0 when Ö = n, and B = (1-5y: and D = (1-836 and
when Ö < n,
Pot
c
Σ
(1-1) ) ( c-1
G ) ((x))
npG
(1-6)ostsc
PG = Prob (Gt 2 (1-
n -- (()
G ( )²=1)²)
Σ
Then for all K 2 0 the iterates produced by ByZ-VR-MARINA (Algorithm 1) satisfy
- -Ix'')] (1 k)* Φ00 + 4Drc2
)
pp
where p min yy (1 - sB) p )) and To f (x0) - -0+ + to
[
1000 Vf (29)
p
Proof. For all l 2 0 we introduce th f (xt) - fr + t 111 - Vf vs(* |1² Using the results of Lemmas 1.13 and D.7, we derive
E i +1
(D.7) S
E
f (3 - 5 (
L
|| - 2 $11 + I1 - VS (2t))
27
2
|| (xt) 11]] + 47 E
- -Vf -
[||g+t]
(2*+1)))1 ||
2
p
(D.13)
E
(xa))
- (1 1
L)
|| - ~ 2 + 2/2 111*~v//
v.
27
+ 47 (1 - p)
4)
E [110* - vs (-a)) ||²]
47
DE
|
||]] + +Dς² + PA
1++ =t(pp)
+
4
E
[ (64)-(² [+]
47 (11-2) p)
+ 5)
E
||1** - (++) +
4D5²7
P
1 (1 (1-17-
. ----²²²) E [||a
- x+
1
8B
E
||
27
2
p
44

---

Using Assumption 2.7 we obtain
[s (x*)) - - + (1- () T - (z()) + 4
E
+1
11
S B
p
1
+ 2y
(1 -2A2)) EE - -
8B
rp
1
E If (x*) - f*]
Finally, we have
E [ <
1 min
7/4
1
B
p
E
4D<32
p
Unrolling the recurrence with p = min
[YM (1-
sB)
p
we obtain
18
25
K-1
E [
I (1 - p) x E [
+
(1 p)*
p
I (1 - p) E [ + 2
(1
p)*
p
k=0
4Dxc2
= -11- - p) k E [
+
pp
Taking into account o² 2 f (x*) - f (xx),, we get the result.
45

---

E
Analysis for Bounded Compressors
E.1 Technical Lemmas
Lemma E.1. Let Assumptions D. D.2, D.3 and 2.4 hold and the Compression Operator satisfy
Definition 2.2. We set Ak+1 = DQ maxi. Ti.j- Let us define "ideal" estimator:
Σ
V)ilah+1),
Gn =1
[1]
G
iEc
g
k++
9 + VJ (24+1) - -V (x*),
Gn and G (1 8)C,
9
Σ clip (o (2
Gn and G 2 (1 8)C.
[3]
E
Then for all k 2 0 the iterates produced by ByZ-VR-MARINA-PP (Algorithm 1) satisfy
A E ||ght1 v [1
5P 8o
$
- (1-pp)
||1 vf(x*)]'
+
E
[ [(x)) [3]
Poz G
(w (w+1)23
+ p)pG (² 8)2
wT. (w 1)
E [| 11]
where PG Prob ( 2 (1 - 8)C} and Pog Prob {i E g G 2 5)
Proof. Similarly to general analysis, we start from conditional expectations:
||ght| Vf (x*+t))² ||]]
A1 E
E Ex ||ght1
vs [1*
(1 P&
Et
g++ + G LE
Σ
clipx (0(A. (attt,att) Vf (axt2)
[3]
+ (1 p) PG)
Es 1110 - vf(x+))] |1²]
[22]
+ pE
V/i(attl)-
V)(catt)
(26)
Gk C
iEgt
Using (12) and V (x*) - v (x+) = 0 we obtain
clipy (e (att) (c)t)),0t)) - V. (cottt))
B = E
E
+
[3]
G C
clips (e(3. (2*t),=t)) v. (zttit + (zt) v. (2t) (+))
E
3x
* +
Σ
13]
Ge
scot
46

---

Using A6+1 = Do m (s.s1l=hh - 241| we can guarantee that clipping operator becomes identical since we have
|| ( (a ,2a4) )| - De
A (w ,ا7)
De
1
Σ
Viig(a (ar
b
jEm
D V V (2
Σ
JEm
S Do max T | - x²11
S Do max Tui || - x*11
Therefore, we can continue as follows
B = E
Ex
Σ 0
(rAt),2t)) -o0)-vv. V. (1ttt)
[13
G
=
BE
Σ
e
- vs ((())))))
[3]
G
kcog
Moreover, we can avoid application of Young's inequality and use variance decomposition instead:
B1
E
||g *
- V (a*)) [|]
Σ e (3: (ott),at)) (vs(attt)- - -r(tt)
+
E
Be
[3]
E
||g
*
V
E
Ex
1
o ( x()) A (xttt xtt)
[3]
(27)
G
iESt
Let us consider the last part of the inequality. Note that G6 2 (1 - -8)C in this case and
B
=
E
E2
Σ e A
(
(x*t1,²²))
- A (2ht1 )
1 [3]
G
kEg
ESP
E&
o
A ((att(=²))) A (attt1 ,20, )24)
1 [3]
Gle
1ED3
Σ Be |100 (A:
(1t (2(t),=²)) - a (stt1 = )13}
E Essk
1 13]
C2 - 5)2-
KEEE
[o0%] Ex 110 (1 (3 (x ,f))) 1 (aΛt1 , ||] [3]
C²(1 - 5)22 F.
TR
Lieg
(x+t...=))) A (+ , > |1-] [
F
Σ Pay T
(28)
C²(1 8)2
Lieg
where Igg. is an indicator function for the event (i g% Cg 2 (1 8) C) and Pog
Prob (i g | CtC 2 (1 - 6) C} is probability of such event. Note that Es, Loy = Pog In the
47

---

case of uniform sampling of clients, we have
Vi Vieg
Pøg = Prob fi gt
Ge 2 (1-
Σ ((-1) ) (c-1) ((==1))")
C
11 PG
(1-8)CSisc
Now, we can continue with inequalities:
B S C² - 8)2
E
Σ Ex
|
A
(a (eaaa))) - (2xttt (at4t1, x 112 [3]
LEG
Po8
2 3 ( ( x 1 ( |1
< C² - 8)22
E
Σ Bs
EQ
LIG
C² - 8)2 E
PoB
Σ Ex
EQ 0 aن (a _ م (alt)) ,2**
LiEG
PΦz
+ C² - 8)2 E
Σ E&
||| (z ,Iah) - A (I - ||] [3]
LiEg
Using variance decomposition, we have
B < C² - 8)2
POg
B
Ex
EQ
0 (.
( - د |ماا (a" , )1² [3]
LiEG
Pox
Σ Es [|A (24t1 x - a ( ) ||] [3]
+
E
C 8)2
LiEG
Applying the definition of unbiased compressor, we get
B C2 - 8)22"
Por
E
Σ (1 + E& ||ا. (s4t1 .a+) 11?
A (=(+),=()) [3]
LiEg
iEG
Pot.
+ C 6)2 E
Σ A| ++ xx - (1+tt1,++ ) )1² [3]
(
LiEg
Pog
Σ (1 + Ex | (1rt1 ,00) - Di (2 ..ot)) 11?
< C² 8)2
IF
LiEg
Pgt
Σ + (1 D (z+ x²)) Σ Ex A (a. ,2+) 11 [13]
+ C²(1 - 6)2
E
Lieg
iEG
PoB
Σ ||li (art1,2*)
(2 x )1² [3]
+ C - 6)2
E
Lieg
48

---

Next, we rearrange terms and derive
Pst
B| - C² 8)2 (1 W)E
Σ
| (ettt,,0 - Ds ( [3]
LEg
Pot
D + )1²) [3]
+ C² - 8)2 w.
LiEG
Pob E
- Σ | (a k+ ,2-)- - a (ztt11 "=""t,,=*11 ,12)1² [3]
+ C² 8)2"
LiEG
Pss
Σ Bk ||ا (1+t) 100)) - D (a+ x =b))|² ||] [3]
(1 W)E
C² 8)2
LiEg
Pab
C² 5)2 wIR
Σ
A (a xx+) - - (2 ",,,+,,,++] || + 1| (I xxt) 112 [3]
LiEG
Pot
Σ ||ا (skt1 ,x0) - (x. , )1² [3]
-
+ (² 5)2
.Eg
Rearranging terms leads to
Por
A (1 x - D. (1o .att) 119 [3]
B1 S C²(1 - 8)2 (1 + +w)
Σ
Ex
LiEg
Pog
C2 -8y2 (w + 1)B
م|ا; (athtl ,00)) A (ze 1 ,xah 1| [3]
15g
pgz
C² - 8)2 WE
Σ
|| (art11
" )1² [3]
Lieg
Now we apply Assumptions D.1, D.2, D.3:
Pgt
c || - 112
B < C²( - 8)2
(1 + W)
Poz
Poz
[GL k+1 111 + C² -jaaB CLL - =0]]]]]
(w + 1)B
C2 - 8)2
Finally, we have
B < C² - 8)2 (wT2 + (w 1)r2 + (w + +1)c2
pgz G
E [11 -
- 1-11137
b
Let us plug the obtained results in (27):
B1 < ||0* - {((+)))1
Pot- G
+ (w (w+1)
+ C2 (1 8)2
wI? + (w + 1)13
E [1 - 111
49

---

Also, we have
= E
lgght V \
(26)
(1- 11-))pBB + (1 - p) - 1 - {
8. P.p
+p (1 8)
E
B [z)] +
8 P.
5 (1 - PPPEE |10e - v + + 5)
B [B]V + [²]
Paz G
(w + 1)
+ (1 plpe C²( 8)2
wh.² + (w + +1113
+ (1- p) PG) |10 v /(aat)11
Rearranging the terms, get
So
A 51 (1-p)E |1gt - vf(E)))
(1 E [BIV +
Pay G
[WL + (w 1)L3 + (w (w1
1)23 E ||1 11.
+1 p)pG 0² - 8)2
Lemma E.2. Let Assumptions D. D.2, D.3, D.4, 2.4 hold and the compression operator satisfy
Definition 2.2. Also, let us introduce the notation
ARAgg k+1 ARAgg clips,
(2(2)(att)) ,24)) ....., clipxen x (e (e(o(aaht), ,x)))
Then for all k. 2 0 the iterates produced by ByZ-VR-MARINA-PP (Algorithm 1) satisfy
T2
E
Ex
Σ
clips
(e (att1 (ortt,,"1)) ARAgg
| [33
G iEgg
GP ot
C3 of (1
$ 4 C(1 - 8)
+ (w + +1) + wL? [11a - ==*117]
b
where Poz = Prob {i g Cg 2 (1 - c}
Proof. By definition of the robust aggregation, we have
2
T3 =
Ex
1
Σ
b+1 clipy (e(5, (c(t),=x1)) ,(1) ARAgg
[13]
Gk
< E
c
Σ
Ex
clipss (3 (2tt1, ())1),a+))) clpp (e(3: (, 18
k.eek eyl
where D2 (G - 1).
50

---

Using A6+1 = Do m 1i - xd1l we can guarantee that clipping operator becomes identical since we have Vi E G
||0 [ (a(tt1,zt) s DQ
A 1 ,20)
< DQ
b
1
Σ
Ving(a - (x*)
jem
DaT JEm
Σ
V[ (zs ||
< Do max Tui || - =t11-
(29)
Let us consider pair-wise differences: Vi, E g
clipy (o [ (2 (x=t),,²))) clips (e ( (o x²)) ))) [3]
(2(1,)) = Ex
E&
||| 0 A (a* - =+1)
2 ( (2t+1 xx+) [3]
||0 ( (#4t1, )² a. (+tt1, + a. (5 xt) - 0 (a. (#*t1, x )))) [a]
Eu
+ 16
||A,
(1 _.t) - A (- (z || [3]
(12) $ 2T,
o A (2++11 = ) A (2.tt1 x |
A b+1 x - 2 [Bi (a x* 11 (3]
+ 2E,
+ E3
| (2r ++ xx*) - A. (1a=11 )| [3]
(12)
Q A (2+++1_ (,*,,,,*)) - -i (2 x² | [3]
< 2
A ++1 x - 2 ( ( ( xz0) )>| |1" 2 [3]
+ 2
+ 2F,
||||
(2. ,²a - a (1ntt , 11 ||اا (W ( - A (a+t1 + [3]
51

---

Now we can combine all the parts together:
7.2 = EE
Σ 12(
CC - 1)
ie!
|10 ( [ (2ttt,, - D (ztttz x(t) /1 [3]
$
Σ
2E,
D2
1.EE0t iell
+ +E
Σ
2B
| ( - 2 (v (2 stt)) (x)+), )| [3]
D2
1,1E9
+ E
Σ
2E
(Iat), A (2btt), 1|² [3]
D2
+ E
2B | (10-1 ,aa)) A (a ( [3]
D2
lf!
Rearranging the terms, get
4
Σ E& ||o (A. (24+1 (24+1,.*t) Ds (1tt1 , , || [3]
f. S E
G
sEg
4
Ex ||A,| (aatt1=1) (an+1 " )| 2 [3|]
+
G
REGI
Using variance decomposition, we get
1/2 S
E
Σ 4
| D. (2++1 ,xt)) / [3]
(artt,,t)))
G
iES!
4Ex ||ا| ++ )1 [3]
+ E
Σ
ME
||ا| (1 (1 xxa) - A ,
11² [3]
GC
iEgE
52

---

Using the properties of unbiased compressors, we obtain
To
E
1
Σ
4(1 +
WBBK || (2 x /|= [3]
G
iEC3
4EA |داا (1 +
|| || [3]]
E
G
||ا| (I ,00)) A (z+ , 1| [3]
+ EE
4ER
GC
$ E
1
Σ
4(1 + W) ||اا (2 x - D (a (a ا || [3]
G
+ E
Σ
4(1 + w)
ب (2 ,
)1² || [3]
G
iECo
4E ||اا ( , ||² [3]
E
G
||اا (an+)) ,0*)) A ",,,,,,**11 112 [3]]
+ E
4
G#
iE
Let us simplify the inequality:
12 S
1
Σ
4(1 + w
||ام (a+t) - D (a+t1 ,++) /| [3]
G
iESt
+ E
|| | AwEi
) 11? [3]
G
+ E
Σ
4E
||As (a x² (=)),,,z))- A (2 ,a²² 2 [3]
Gk
iEg
Using variance decomposition once again, we get
i, < E
1
4(1
1 ||ا, (attt,, sat)) - A (a++t,2x+ ,++) ||? [3]
GE
|| (or , A (a*t1 ,,,++,+))))))))) ) || [3]
+ E
AwiB
Gk
iESt
+ E
Σ
4Ex
||ا|| (1*t), 200) (xx , )1 [3]
G
icg!
+ E
(
| [3]
G
53

---

Then, we apply similar arguments to the ones used in deriving (28):
T2 S E
Pot
4(1 W
| (2/ht1 xnth - Do (z ,et)) || [3]
C(1 C(1-5) 6)
iEG
Psb
| (a x a (a .2th) 11 [33]
+B EE
AwiBk
C(1 8)
iEG
+ E
4E
||ا| (5++1 , ) - a (z ( )1² [3]
C(1 8)
ieg
Por
+ E
AWEE
A (,=)
)1 1|2 13]
C(1 8)
iEG
Using Assumptions D.I, D.2, D.3:
4(1 + w) GP []
GPss 5t w || - 20/113)
T2 S E
|1 - ={1p]]
+ E
4(w + 1)
C(1 6)
C(1 8)
GP %% wL² 2 kt1 - =1(122
+ E
4 C(1 8)
Finally, we obtain
T2 = E
Et
Σ clipA
- A k+1
1 [33
G 1E98
GPog ot
co (1 (a++w)
+ (w + +)42 + wL?
E [lla4t1] - 1211
C(1 01
b
Lemma E.3. Let Assumptions 2.3, D.1, D.2, D.3, D.4, D.5, 2.4 hold and the compression operator
satisfy Desinition 2.2. We set AR+1 = D2 maxi. Lig [1a - x* Also, let us introduce the notation
ARAgg k+1 ++1 ARAgg clipp- (o (1 k+1 ,2)))
clipxem
Then for all k 2 0 the iterates produced by BYZ-VR-MARINA-PP (Algorithm 1) satisfy
E
I10
Vs
P E
||05 Vs (xx*)
2
[1 + Dx² + PA
+ BE
|V (x.
11/tt111 -
with
4
PaP 0g
G
8GP c5
4
+ 8
GP
A
D
C3( 8)20 w
(1 - O)
=B B - 6B +
p
- pc)
- -P0CCL
C(1 8)
cdw
L
4
PCPgg go. G
8
GP og
s( (w)+)
(13 + f
+
C²(1- - -6)2
(w+ 1)
-PG
p
PG
C(1 8)
b
+ 2
16
(1 F3
DQ Dqamaxia Lis i,j
8P gh
12cG
8P
6eG
B = 2
1 B
+D) + +6B, D=2
+ +p + D,
1
C
Pot GB
p P G
where B- = 0 and δ = 0 when C = and B = (1-51e and =
when Ô < n,
1 1-66
Pc Prob { GG& > (1 -8)) and Poy Prob {i e 9% G6 > (1 C).
54

---

Proof. Let us combine bounds for A1 and A2 together:
E. |1 V (a 1x* 1²]
Ao
$ s(1 + 10 2)
E ||1 - -V (2*tt))) + (1+
2 p
E 1 1g - 11+
$ <(1+ () A + (1+ 2
A2
p
8P oz
$ (1+ 2) - (1-p) 110 - -Vf(2*)11 + (1+ P) (2) P P( -1
E [B]Vf( + [2]
Pog G (1+ 2) (1 p)pe c² 8)
(w1. + (w+ 1)22 (w + 1)63 1 |||="+1-=11
+ 1+ p. Ex
ARAgg ( fi(( )..... V.n(((t1) - , [1] 1 [1]]
[+ p)
2)
(1 - p)
Et
Σ
clips (e(2) (1tt), (41))))))) ARAAE
[3]
Ge SE0E
1+ + 2 }) (1
E&
[[((tt)) vf(at) A
R+1 ||
[2]
Using Lemma E.2 and lemmas from General Analysis (Lemmas 1.10 and 2.12) we have
Ao E |||0 |11g++1 Vʃ
[1
8P
< <(1-33
E |11e Vf (x*))
+ 2p
E [ f(=)) +
2)
5)
+ -11-3 P)
Por G
wIL++(0 (w+ 1)12 (w + 1)c9
[|| - *
pa C2((1 - 8)2
88PP 0z cbB
VV (x 21 + I2 12 10|
+(++2)
+2B
(1-8)Ć
GP o8
+4 2)
2
+ 2)
(1- (1-8)²²
2
GP o/
+
P
4(1 + w)
cd
| - 112
p
C(1
2
GP c
+
AlW 11 C(1
cd
L || k+1 =0113/
8)
+ -PPGE
4w
GP
cō
12
t+1 - x² x²1
+ 2 p
(11-PG)2(E + F2 E ++ - x -0/
C(1 8)
Finally, we have
E
vs 11
||'] - (1 -1- 2
|100 - vs (1]
+ DE |V x 11 + Dy² + PA
||
1 - x12
4
where
1
p
4
C2 8)24
PGP o G
8GP c5
(1 11-00 0)
ok
B - 6B +
- Pc) +
8
C(1 ppp
PP
GP ot
8)
cow
I?2
+
4
C2(1 - 8)2
PGPg2 gg. G
(w (w+ 1)
+ -
p
8
PG
C(1 8)
GP oz
cd (w +1)
[1]
2
b
16
DQ (Damxxtns Lis
+ 22
(1 F3
55

---

and
sk B =
12cG
8P ot
6cG
θ +p) + +6B,
D 2
+p + D.
1-
1 1- c
E.2 Main Results
Theorem E.4. Let Assumptions 2.3, D.I, D.2, D.3, D.4, D.5, 2.4 hold.
Setting d6t1
maxi. Lig | | x²)
Assume that
0<75
<p
L+ VA'
where
PaPat 0 G
8GP
gt ob
4
GP 5t
A
B 6B + -(1 pGG + pp
C(1 - 8) now T,2
C² - 6)2
(1 -]
p
+ p C²( - -0)2
PCPog G
(w + 1) + p
8
GP o
cō(w +1)
[1 f
C(1 8)
b
+ pa
16
(1 pc) F3
Do maxma Tis) ii
2
8P
12cG +p)
8P
GcG
B = 2 8-8 B
+ +BB, 2 1-8
+p
+ D.
where B == 0 and D = 0 when Ô n, and B = Pos GB
Pog G
(1-8)ö and D (1-8)6 when C and
Por
C
Σ
(i-1)
( C -
c-
n-G G
)())(()))
n
TPG
(1-
PG Prob (G) 2 (1 (1-
n ()) 0
Σ
Then for all K 2 0 the iterates produced by ByZ-VR-MARINA (Algorithm 1) satisfy
25
2Bc²
E B[IVS(E*)
7 (1- 1B
(K (K+1)
p- 4B
where FK is chosen uniformly at random from x., x.l ,...,," R.K and Φo 5 lr 1 Vf (2
Proof.
The proof is analogous to the proof of Theorem D.14.
Theorem E,5. Let Assumptions 2.3, 2.4, D.I, D.2, D.3, D.4, D.5, 2.7 hold. Setting A max;, Lig || | x* Assume that
0<7Σ L+ 22A"
8B <pp
where
PGP ot G
8GP c5
gk
4
GP at.
1
B + 6B + -(1 Pc)) + -PG C(1 ppcC(
cow I
p
C2 8)2
(1 0
p
8)
4
PGPgg go. G
8
GP oh
f [1
+ P
C2(1 - 8)2
(W (w+ 1)
p
PG
C(1 8)
cd (w
+1)
b
+ 2
16
(1 F3
DQ Domaxtin Lis
56

---

8P 12cG +D) + 6B, D= 8P
c B
6cG 0
B- 1 8-8
+p) + D
Pok GB
P Por
where B == 0 and D = 0 when Ō = n, and B := (1 81-
and D = (1-8y0
when E < n, and
where PG = Prob { 2 (1 8)C} and Paz = Prob E g G 2 (1 6) C}. Then for all
K 2 0 the iterates produced by Byz-VR- (Algorithm 1) satisfy
E - - $ (1-pp pk) 1 + 2D
pp
where p = min (7 (1 / ? and Φo = (x0) - fr +
2x
p 66 Vf (29)1²
Proof.
The proof is analogous the proof of Theorem D.15.
E.3 On the Technical Non- Von-Triviality of the Analysis
As we explain in the main part of the paper, the main reason why we propose to use clipping is to handle the situations when Byzantine workers form a majority during some communication rounds since the existing approaches are vulnerable to such scenarios. However, the introduction of the clipping does not come for free: if the clipping level is too small, clipping can create noticeable bias to the updates. Because of this issue, existing works such as (Zhang et al., 2020b; Gorbunov et al., 2020) use non-trivial policies for the choice of the clipping level, and the analysis in these works differs significantly from the existing analysis for the methods without clipping. The analysis of ByZ-VR-MARINA is based on the unbiasedness of vectors Q(Ā,( xx x²))), i.e., on the following identity: EE E[Q( ( (a*+1 x
(1*h11 x**)
f( (f(")
Since E[clip (Q(á,(a**) x²))) 2.+11 .x*] + Vf( (x(*) in general, to analyze
ByZ-VR-MARINA-PP we also use special choice of the clipping level: Ap+1 = 0x+1 @x+1||=**1 - I/ To illustrate the main reasons for that, let us consider the case of uncompressed communication (Q(x) 2). In this setup, for large enough ag+1 we have clip (, .I*)) = (x**++ x²)) for all E G (due to Assumption 2.6), which allows us using a similar proof to the one for Byz-VR- MARINA when good workers form a majority in a round. Moreover, when Byzantine workers form a majority, our choice of the clipping level allows us to bound the second moment of the shift from the Byzantine workers as ~ ||-=-1 ~²11 (see Lemmas D.9 and D. 121 i.e., the second moment of the shift is of the same scale as the variance of {g: hieg. which goes to zero. Next, to properly analyze these two situations, we overcame another technical challenge related to the estimation of the conditional expectations and probabilities of corresponding events (see Lemmas D.9 and 1.10 and formulas for pa and Pog. at the beginning of Section 4). In particular, the derivation of formula (24) is quite non-standard for stochastic optimization literature: there are two sources of stochasticity one comes from the sampling of clients, and the other one comes from the sampling of stochastic gradients and compression. This leads to the estimation of variance of the average of the random number of random vectors, which is novel on its own. In addition, when the compression operator is used, the analysis becomes even more involved since cannot directly apply the main property of unbiased compression (Definition 2.2), and we use Lemma D.6 in the proof to address this issue. It is also worth mentioning that in contrast to ByZ-VR-MARINA, participation even with a small probability p. Instead, it is sufficient for ByZ-VR-MARINA-PP to sample a large enough cohort of Ć clients with probability p to ensure that Byzantine workers form minority in such rounds.
method does not require full
57

---

F ByZ-VR-MARINN-PPP-- Simplified Version of BYZ-VR-MARINN-PP
In this section, we present simplified version of ByZ-VR-MARINA-PP called Byz- ByZ-VR-MARINA- PP+ (see Algorithm 3). The only difference between the two methods is Line 10: Byz-VR- MARINA+ does not apply robust aggregation when e₁ = 0 and just averages the clipped vectors received from the set of clients Sy. Nevertheless, when Ck 1, i..., a large cohort of clients is sampled, the method still uses robust aggregation.
Algorithm 3 ByZ-VR-MARINA-PP Simplified ByZ-VR-MARINA-PP
1: Input: vectors g E TRd. stepsize 7, mini-batch size b, probability E (0, 1], number of iterations K, (6, ARAgg. clients' sample size 1 S C - Č s n, clipping coefficients {a*
2: for k == 0. 0,..... K
do
3: Get sample from Bernoulli distribution with parameter p: Ck Be(p)
4: Sample the set of clients S₃ S [n]. |S& = c₁ O; otherwise SSx Ò
5: Broadcast g* C* all workers
6: for i E 9 n Sk. in parallel do
7:
x x. -yg* and Ac+1 = ax-1l1= x*1|
Vf((tt+)).
cs 1,
8: Set g,
++1
9* + clip (e(
otherwise,
where Ai(ttt1 .xt) is mini-batched estimator of V (i( - V.i(x*), 2(-) for i e
gn Sa are computed independently
9: end for
ARAgg (1g, k+1 JeS,))
if c = otherwise
10:
9º + Σ clipxess (0 (e(S,Cott),at))
fESt
11: end for
The key idea behind this modification be explained as follows. For simplicity, let us assume that C' is small and dreal is also small. Then, for the communication rounds with Ck O, with a large probability, only good clients will be sampled. In this case, the method can just average of the received vectors and benefit from the lack of bias appearing due to the robust aggregation. Moreover, when C& 0 and at least one of the sampled clients is Byzantine, the method will tolerate due to the clipping. That is, when C' is small, the method can potentially benefit from the lack of robust aggregation when = O. However, for the rounds with 1, in the worst case, C = n, meaning that all Byzantines workers are guaranteed to be sampled. To tolerate such situations, we keep the robust aggregation in the method when C* 1.
F1 Analysis for Bounded Compressors
For simplicity, we analyze Byz-VR-MARINA-PPE for bounded compressors only. The analysis is very similar to the one we provide for ByZ-VR-MARINN-PPE but several steps are significantly simpler. In particular, the central part in the analysis of ByZ-VR-MARINA-PE is in deriving good recursive inequality for Elllg* V fz [=*)][3) [| which requires several quite technical steps. For
ByZ-VR-MARINA-PP.. one can obtain a similar inequality much easier as shown in the next lemma.
Lemma F.1. Let Assumptions D.I, D.2, D.3, D.4, D.5, 2.4 hold and the compression operator satisfy Definition 2.2. Assume that C' < G. We set A&+1 DQ maxi,j Lis [llla+++1 - x²Il Then for all k 2 0 the iterates produced by ByZ-VR-MARINN--PP. (Algorithm 3) satisfy
E 11 -1
V (
<
1
R
1|oe - Vs (5()))1
(30)
2
+ DE
V (z) [1
+ Ds² + PA
1|
1
k+1 x²11?
4
58

---

with
A 4
SpBGPos
6pB (1 - p)pgw + 6(1 - p)(1 o(1-p)(1 115) 12
P
(1 (1-6)C
C
p
4(1 p)p
4(1 4(1 p)pl
4(1-P)PG(1 (1 + w) 22
12 (1+²)
w
PC
24(1 - p) - pt))
2
DQ max Tis) i.j
pd
8GP 5 coBp
4GP
oj cóp
= (1- + 6pB,
D =
(1 (1-8) 8) +pD.
where B, D. plz. Poy are defined in Lemma D.13.
Proof.
From the update rule of gh+ we have
E |1g Vf(a + || = EE |AAgg (
(oes))) V[((a+t))| c x=
(31)
Ti
2
g" Σ clipAn (e(A((ott))tt)) v((xtt))
p)E
1c =0
Next, we bound Ti and T2 separately. From Lemma D.10, we have
8GP cōB
4GP 4GPozcdg cōç²
T (1 ()c + 2B E [ + 1.2
=|1]²]] -
12 -
2
(1 (1-
As for T2, consider possible situations: either n (no Byzantine workers are among sampled ones) or Sy n B # 2 (at least one Byzantine worker is sampled). Then, T2 equals
TB = E
Σ 1
clip (e(Ai(rtt),
( -v))))((((+tt)
c 0, n B = Ø
C
T2
2
+ +1 111-p3h p E
1 Σ
clip (o (e( aat))) Vs(attl)
C
iES.
T2
where
(
G
-G- C+ C+ (n C) (G (G+1) +2 .....
Pg = BB / c 0}
n
The choice of the clipping level A++1 = DQ max,, Ti x+1 and inequality (29) imply that
clip
A ka _x)) for all i E g. Therefore, for T2, we have
2
T3 = E
gh + C
Σ 2 (A((ttt),att) - vs(ahtl) ca = 0, B Ø
rES
E [llg*
+
Σ e
(V
-Vf(z))
0B
C
iESt
59

---

[ where we use that E 1 Diss 2 (Ai(a cs = 0, BB e]
vf(attl)
Vf(a"). Moreover, since E c Lies, 2 (A,(ott), xt)) cv - 0, Sx nB - S,
=
Ô Eiss, (Vf((ztt)) - Vf((2*)) =: e Eies, As(xltt), we can decompose the last term
in the upper-bound for T2 as follows:
T2 E [lle k
1 Σ (((S(ottt) - A, ax4)) )
/| |k === 00 Ø
+ +E
E
FESt
2
1
- vf((=*))
+ E
1 = 0, S₁ nB
C
&E
Since the compression operator computations are independent on each client, we have
T/2 E [Ilo*
V
(
+
E
Σ 0
(A,(artt),
(,tttt)
= /)/ Sh cx = BB
LiES
Σ Ai(ztt ,00)) 1
1o = 0, nB= Ø - E [[V -
E
S
E
[|Ig*
+
E
E
e
(A((ott) x01) - (z xtt)) lp?
- Sx cc = 00, nB
C2
S
j|? -2
cx 0, Sp 1 0
E
E
Sx
C
LiES
+E
Ai(zht| 220)
ca = 0, S4 nB = Ø - E [|Ts(ottt) -
S
(Def 22) 5
E [[lsst
A (attt =b> 1|
+
E
1 1 = 0, Ø
Sv
, ||
+
E
-
c = 0, Sx ==
= Ø
C
LiES
1
| k+1 x , c4 = 0. B Ø - B [I - -
+
R
LVES
||l0*
(f + CG i5g
ΣE, E | ا =1,
|| | x²) - Aaahttt x ||2)
+
Σ E
CG
Σ
E (z+++ R+1 |11 - E
|| {s(a")111]
+
G 1E0
60

---

Using || x
11'
(a - Do ((aaatt), 119 + +E (E(IA
we continue the derivation as follows:
[( (x2)) - (,ttttt _ 119
T2 S.B. E [lIs* - V
+
EE
CG
$E9
+ (1 + E | snh) 10))
E [ {f(xt)]1
121)
E [llg*
(1 + W
E - [1114t1=+111]]
bC
Σ |l
- ) -
E
G
LEG
||
- v [1
+
(20
v)( + (5 + (1+ () 12 + (1+ w
I E [llg*
E [llacht - 1n1
bC
Next, we estimate T2 using Young's 's inequality and the choice of the clipping level:
x (1+ B)B
|1o+
[/( + 2(1 + ) [| - -Vf(=t>1+
+ + + +
Σ
clip (0 (0(Ai(ett)
c+ 02 n * Ø
S
(18) S (1+ 3) ||10* - vf(a>>)] ||" + + + 3- (L'E ||a
|2] + 111
(1 + B)
max Li ||0 - [f(+>>]| ||² |||]] + 2(1 ( 3-1) ( D2g D&
E x
1.j
where B > 0 will be specified later in the proof. Combining the derived upper bounds for To and T2.
we get
Te S (rg + (1- (1-p)) + B)) E I|1a* )1²
+ p w 12=²+ + (1+
w ) 1 + (1+
E [[la+tt- x² [1]
6C
+ 2(1 - r1 + )
1.2 + Da max 12 1
RE [llakt1 - x0*1 1P]
i.j
Plugging the obtained bounds for Ti and T2 into (31), we obtain
E [11
vf(x+t))) )13] s (1 p) (PC + (1 (1 + B)) E [lle*t - [](
/8GP
c5B
4GP oz co62
+p
((1--))
+2B E
V (2 || + I || | | x+1| [1]
(1 500 + +72²
-1--8p 6)C
+ (1- (1-p)rt (W12+ + (1+ w) )
1 +
(1 + w
E 0[1a4411 - x [11
bC
+ 2(1 - -1 - (1) + +
1.2 + D3
max i
1.2,5
E2 [[laAt] [[aatt--~(17]] 101]
Taking
if iğ 2(1-p5)'
p
< 1,
3==(
1.
if if = 1,
we ensure that D3 (1- (1) + 9) < 11+ _ and (1 - p1) + 3-1) S (= م
p
3(1 pb) Using these inequalities and (1 p) (1 - !) < 1 - P. we simplify the upper bound for
P
61

---

E [ll ( ||] as follows:
E 1lg -S
= (1-2) 12) E Il1g* v)(xx'))
-
+D (1 | (8 0
coB
4GP 4GPoz od{2
0
+2B E v (x |1 + 1,2 || |
- -011 +
+ +
(1 8)
(1 8)C
(1 + W
+ (1 - p)r r + (1+
1 +
R -
bC
6(1 - p)(1 - pp))
1 D2
max Lit3 -
p
[.
Rearranging the terms, we get (35).
Then, similarly to the analysis of Byz- ByZ-VR-MARINA, get the following result.
Theorem F.2. Let Assumptions D.I. D.2, D.3, D.4, D.5, 2.4 hold.
Set AR+1
max,, Las || * x²1 Assume that
0<95
4B <p
L+ VA'
where
4
8pBGP cf
0g
(1 p)pp
+ 6(1 - ((1-p)(11 - -rt)
A =
+ +6pB +
I
p
(1 (1-8)6 -)c
C
p
4(1
pipt
(1+ c
12 4(1 - p)p (1 + w) 2
P
PC
24(1 p) - -pt)
2
+
DQ max Lis is
p²
8GP og
coBp
4GP 0j. côp
B
6pB,
D
(1 - (1- +DD,
(1 8)0
and
Pot
C
Σ
((-11 (
n n-G ())=)(())) (("))
TPG
(1-6)05ısc
---C+1(G-C+2 (n C)
p = Prob(S n B = Ø c = 0} =
(G (G+1)(G++2)
Then for all K 2 0 the iterates produced by ByZ-VR-MARINA+ (Algorithm 3) satisfy
2Φ
2D
E [ (T*)(**
(11- 18
7
(K +1+
D-4B 4B
where FKK is chosen uniformly at random from x², xl ,..., kk and Φo ((x")
9 Vf (.
Proof.
The proof is analogous to the proof of Theorem D.14.
Theorem E3. Let Assumptions 2.4, D.I, D.2, D.3, D.4, D.5, 2.7 hold. Set A
max,, Lis || x² Assume that
1
0 < 7 < min
8B <p.
I V2A
62

---

where
A 4 SpBGPog cō
+6p (1 - plnza
+ 6(1 - 6(1-p)(1 113)
P (1- - -)C
C
P
4(1 p)pp
4(1 - p)p' (1 + w) C3
(1+ T
1
PC
24(1 - p) - -p/)
2
DQ max Tiss 1.
p²
8GP $6
coBp
4GP cop
B=
6pB,
D =
+ DDD
(1 (1-8)0
(1 - (1-
and
Pot TPG
C
E
((-11 ) (
n a-G G
C-t ) (()))
(1-6)CSisC
Ck =0 (G- (G-C+1]G-C+2)
(n C) + .....
p Prob(S B
Then for all K 2 the iterates produced by ByZ-VR-MARINA, (Algorithm 3) satisfy
2DC²
E - f (1- p)) (K g
pp
where p = min 7/0 (1- ) and To = f (x²) - +*+ 2x
1000 - V (z9) p
Proof.
The proof is analogous the proof of Theorem D.15.
F22
Discussion of the Results
Improved neighborhood term and bound on 6. The key property of ByZ-VR-MARINA+ is its better neighborhood terms, and maximal allowed fraction of Byzantine workers 5 in comparison to Byz-VR-MARINA, To illustrate it, consider the non- non-Pi Pf.tetting (the discussion for the PI. case similar). For both algorithms, the neighborhood term in the convergence bounds equals ?
ie²
p- 4B
but corresponding constants ß and π are different:
8P P
5P + +6B and - 2
B 2 8-6
B
12cG
++D)+63
oz
6cG
+D)
+D for ByZ-VR-MARINA,
C
C
8GP ogPoy.O
coBp
4GP gb. côp
6pB and D
+ +p for BYZ-VR-MARINA+
(1 81C
(1-8)0
For the simplicity the comparison, consider the case of Ō = n. Then, Pøy = 1 and
B = θ (c5B) and Đ - (cc)) for ByZ-VR-MARINA,
B θ (c5Bp) and
δ = (cõp)) for ByZ-VR-MARINA+,
implying that the neighborhood term for ByZ-VR-MARINA+ is 1/2 times smaller than the neigh- borhood term for ByZ-VR-MARINA, Moreover, the restriction 4B < used in the analysis both methods implies
cb 0
for ByZ-VR-MARINA,
Bp
o8 O
B for ByZ-VR-MARRIN++.
i.e., the result for ByZ-VR-MARINA+ allows (1/p)-times more Byzantine workers when B > 0. We emphasize that the neighborhood term and the bound on the results for ByZ-VR-MARINA+ cannot be improved up to the numerical factors (Allouah et al., 2024b).
63

---

Comparison of stepsizes when Č = and C 1. For simplicity, to compare the stepsize consider the case when C = and
restrictions for ByZ-VR-MARINA and ByZ-VR-MARINA+, and let us ignore the differences between smoothness
C' = 1. Moreover, let us assume that constants and replace them with their upper bound L from Assumption 2.6. Then, for both methods, the results in the PLssetinng (the discussion for the PL case is similar) with 0 hold for 0 < 7 1/((+va), where
1 p
Sreat (1 + +F3D8) (1 w
A θ
++w+ +
for BYZ-VR-MARINA,
p
p²
1 1+
BralD' p²
= 0
for ByZ-VR-MARINAH,
p
8real- That is, the result for ByZ-VR-MARINA+ allows to use larger stepsizes than in ByZ-VR-MARINA (though the methods equivalent when C' 1). A similar comparison holds for small enough C' as well. Therefore, we recommend using ByZ-VR-MARINA+ instead of ByZ-VR-MARINA when C/ is small. We also highlight that the result for RRRARINA--AAAAAAA does not require Assumption 2.3.
where we use PG U/n 1 Sreal, P&s 1/0, P/ c
64

---

G Analysis without Full-Batch Gradient Computations
In this section, consider versions of Byz-VR-MARINA-PP and Byz-VR-MARINA-PP, that do not use full-batch gradient computations at all - see Algorithms 4 and 5. These variants of ByZ-VR-MARINN-PP and ByZ-VR-MARINA-PP- use b'-size mini-batcher estimator V (z when c for every E g in line and are identical to their original versions in all other steps/computations. This modification reduces the computation cost of iterations when making the methods more practical.
1,
Algorithm 4 Byz-VR-
without full-batch gradient computations
1: Input: vectors x0; g0 E IRd stepsize 7, mini-batch size b, mini-batch size V/, probability
E (0, 1]. number of iterations K, (5, AR-Agg, clients' sample size S C S C s n, clipping coefficients }
2: for = 0, 1,.,.... K 1
3: Get sample from Bernoulli distribution with parameter p: Ck Be(p)
4: Sample the set of clients Sk S [n]. |S& Cj O; otherwise |Sx|
ŌŌ
5: Broadcast g², C all workers
6: for i E 9 n S&S in parallel do
7:
x x. -yg* and A = ax-111= x*1| (ii(tt))).
ce 1,
8: Set 9.
g + clipAMi (o (A,(artt,,zt) ,2+))
otherwise,
where (f(*++)) is b'-size mini-batcher estimator of ff(***+)), (z xxh) is b-size mini-batcher estimator of [[((*++1) V((()), 2() for i G (g.S, Sy. are computed independently 9: end for
ARAgg (1g, R+1 (( (olt+Ieesi) Fiesw),
ck = 1,
g ++1
9º + ARAgg (foLipain) (e( SES2
otherwise
11: end for
Algorithm 5 Byz
without full-batch gradient computations
1: Input: vectors x0, x E IRd, stepsize 7, mini-batch size b, mini-batch size b', probability
p E (0, 1]. number of iterations K, (6, c)AAAgg clients' sample size S C' s Č S n, clipping coefficients )
2: for == 0, 1, 1 do
3: Get sample from Berouulii distribution with parameter p: O2 Be(p)
4: Sample the set of clients S₂ S [m]. [S& = cs 0: otherwise |Sa| =
5: Broadcast g*. ck all workers
6: for E 9 0 St in parallel do
7:
k+1 x. 7g and A = a -x-1/12bt -x ==
V (1
if 1,
8: Set g.
1+1
g + clip (o (A,(ztt), .2+)))
otherwise,
where (+++++)) is sisiize mini-batched estimator of ((((**+)), ( ,.*) is b-size mini-batched estimator of (f((t++1) vf((*',, Q(-) for i G n Ss are computed independently
9: end for
ARAgg (Lg) ((x k+1 Jiess),
if ca 1, otherwise
10:
n + J Σ clip (e (A,(oot1,
iESt
11: end for
However, our analysis EYV.V.--MMRRI--PP///AAAAAAAAA without full-batch gradient computations requires the following additional assumption.
65

---

Assumption G.1. We assume that there exist o 2 0 such that for all x E IR and i E [n]
E [VV((>)
v/(=))
(32)
V
where (x) an unbiased b'-size mini-batched estimator of (x))))
particular, when in L 25= - 2 o, which is a standard assumption for variance- reduced methods without full-batch gradient computations (Cutkosky and Orabona, 2019; Li et al.,
2021; Gorbunov et al., 2021), estimator fi())) = Σj= Vf..e (z) with { hie(m).ie(m) being i.i.d. samples from the uniform distribution over [m] satisfies (32). Assumption G. also standard for general stochastic optimization (Nemirovski et al., 2009; Ghadimi and Lan, 2013).
G.1 New Lemma
The main change in the analysis is related to Lemma D.10 since it is the only lemma that relies the full-batch gradient computation. Nevertheless, can be easily generalized to the case of Algorithms and 5, shown in the next result.
Lemma G.2. Let Assumptions D.I. D.5, G.I hold and Aggregation Operator (ARAg9) satisfy Definition 2.1. Then for all k 2 0 the iterates produced by By-.VR-MARRNAAPPPyxx----MMM PP+ (Algorithms and 5) satisfy
Ti
E2
ARAgg
Vf(x
[m]
8GP d5 CBB
+ 2B
E VI (12 L2²
12||
xth 11
(1 ()C
4GP ot cbB
( (1- 8)
Poy G
O²
5² 2²+
+ 408
(1 8)C
b
where = and ? = 0 when Ō = n, and = (1-0)6 and ?2 = Pog GC
P Pgg GB
(1-8)0 when I n
Proof. Using the definition of aggregation operator, we have
Ti = E
[ARgg
- V ( ||² 1141
(12)
Ex
ARAgg (1g, k+1] ((
Gh Σ ((((+tt)
[1]
iEgs
+
E
E
Σ
[[((att))
(1(+
[1]
(33)
G C
iegs
To proceed, we estimate the second term in the right-hand side of the above inequality first. From variance decomposition, we have
E
Ex
fi(*++1)
V vf(att1)
[1]
Gk C
iESt
E
-
[1
Gh
iEG'
E
E₁
Σ
Viilattl) -
(34)
G
iEg
66

---

The choice of Ö implies that Go 2 (1-8)C -)č. Moreover, due to the independence of stochastic gradient computations on different workers, we have
E k
1
( V(((ott)))
[0
E
E₁ Σ ( - ()i(ctt)))
[T]
(1 -1- 0)
iEDE
ff(ltttt) - - 12] [14
(1 - 8)²22 E
Σ Es
1
P
(2) Poz Go²
[ii - -
E
(1 (1- 0)
(1 8)2028'
iEg
Next, since 1 Σ Vf((=+t1)= (z(*+l)) with probability 1 when Ö n, we estimate the
G 1E99
last term in (34) as
E
Ex
vf((ttt)) - -ff(ztt1)
G
0,
if ifc =n
E
Σ
Es
-V
2 [1
ifc <n
G
0,
i
S
Pot
C
Σ
E [fi(ttt))-
-Vf(=t))11
i <n
(1-8JC
ieg
irŌ=
(As. D.5)
Pot [1-6)²
BE [V +
(BE [[ +
irc <n
where
0
if Ō n,
0,
i = n,
B
Pot
GB
and 2
Pot o (1-8)6
if Ō n,
i
(1-8)0
Plugging the derived bounds in (34), we get
2
Poz Go²
E E
(
[1]
vEge
BE [1 +
67

---

Using the above bound in (33), we continue the estimation of Ti as follows:
(Def. 2.1) 5
cô
- -. (
( (2tt)))) [n11
T
E
Σ
Es
Gk (h
Por Go² 6
BE | (1) ?
(1 C26
E
c6
Σ
Es
Vi (2++1) vi (1 [11]
Gk G
i.ec if
cd
Σ Ex ( -Vs(ott)) - ( + Vii (ai+z) | 1n
+E
Gh GG 6
1)
1.1gg igft
Poy 2
+ BE [[
++1 [11]] + +
(1- 22
68

---

where in the last inequality, we use the conditional independence of (ff((z())) Beed for fixed aktt Next, using Young's inequality, we derive
(12) T
cd
Σ
-
V. (1* (1 [0]
CC
1)
S ispt!
+E E
co
Σ
E
E (b+tt) - v. (a4+2) 1|
G K 0
1)
1.Ee if1
c8
2 Vf (2+t1) - iy (24+2) 1111
+E E
E
Gh GG C C
(
1 i4!
c8
2 75 - vs (24t1) || [1]
+
E
Gh (Gh
0 C
1,1E9 it!
P Go
BE [[ +22
+
(1 C)2
(32)
< E
Σ
4E
V (2*t2) - Vs (a4+2) 1| [1]]]
4cóo²
GE iEG
Pgy Go
6
+ BE |[ +2
(1- C)2C226'
Poy Poicó
4c0o²
ABx
(1 v. V (1
+
8)C iEg
Poy Go²
+ BE [
+1 ||| +2
(1 C)
(As. D5)
4GP oz cBB
4GP 4GPogedB cdB
B
E VJ (
c 22
(1-8)Ō
(1 - (1-
Pos G
o²
4ed
(1 6)-8)
(12)
(8GP og cóB
(1+) + || (1(V)(+*))*++111
Vs (-)))
+ 2B
E
(1-8)C
4GP oy cBB
( Pog G
(1- (1-8808 + 408 o²
( ?+?++
8GP cBB
E Vf (zt) )1 1|2 + #122 |2
+2B
(1 (1-8)Ò
4GPg cbB
Poz G
o²
(² + -
+ 4c8
(1 01-
(1 - 8
T.
69

---

which concludes the proof.
G.2
Main Results for ByZ-VR-MARINA without Full-Batch Gradient Computations
G.2.1
General Results
All the lemmas derived in Appendix D.2 hold for Algorithm 4 well except Lemma D.10, which can be replaced with Lemma G.2, and Lemma D.13 that has the following analog.
Lemma G.3. Let Assumptions 2.3, D. D.2, D.3, D.5, G.I hold and Compression Operator satisfy Definition 2.2. Also, let introduce the notation
ARAgg *+1 ARAgg clipp...
(2(2)( x*h) ....., clipxets (2 (Ac(ahtt. x²1) ))
Then for all k 2 O the iterates produced by ByZ-VR-MARINA-PP without full-batch gradient computations (Algorithm 4) satisfy
3Pgg G
a²
E |10 V (2
s 111-((
(1-4) ()
4) |10e V (x+) + (1 8)
+ 1208
D
|Vf (=+) D&² + PA p Allatt 2²12
BIE
where A, B, D. PG, D.P., Poy are defined in Lemma D.13.
Proof. Up to the replacement of the bound from Lemma D.10 with the bound from Lemma G.2, the proof of the result is identical to the proof of Lemma D.13.
Theorem G.4. Let Assumptions 2.3, D.I, D.2, D.3, D.5, G.1 hold. Set A8+1 2 maxxeg Li ||a - x*11. Assume that
0<75 L+VA
4B <PP
where A and B are defined Theorem D. 14. Then for all K 2 the iterates produced by Byz-VR MARINA without full full-batch gradient computations (Algorithm 4) satisfy
2Φ
4D<²
12P gg.
o² 6(p 4B)
| |1
+
+
+ 48c0
7
48
(K
(K+1)
p 4B
(1 - 8)222
where k is chosen uniformly random from ,0,x' ,..., xx and to f lr 11000 V [1
Proof. The proof is identical to the proof of Theorem D. 14 up to the replacement of Lemma D.13 with Lemma G.3.
Theorem G.S. Let Assumptions 2.3, D.I, D.2, D.3, D.5, 2.7 hold. maxieg Lj |ott11 2*11. Assume that
Set A
0 0< min
8B <p
L+ V2A
where A and B are defined in Theorem D.15. Then for all K > 0 the iterates produced by Byz-VR- MARINA without full-batch gradient computations (Algorithm 4) satisfy
p)* Φ + 4DMs²
12 G
702
E
(x [f(
(xx) 5 (1
+
(1 -1-68 -1-58202 48c8
pp
8'pp'
where p = min
7/1 (1-
sñ
p and Φ0 = f (xx) - 1 + 47 - (29))12
p
70

---

Proof. The proof is identical to the proof of Theorem D.15 up to the replacement of Lemma D.13 with Lemma G.3.
In contrast to their counterparts for ByZ-VR-MARINA-PP with (periodical) full-batch gradient computations (Theorems D. and D.15), the above results have additional terms proportional to o the upper bounds. These terms cannot be reduced with the decrease of the stepsize but can be made smaller via the increase of b' A similar phenomenon appears in the analysis of the methods with recursive variance reduction even in Byzantine-free case (Fang et al., 2018; Li et al., 2021; Gorbunov et al., 2021), and to address it, d' is typically chosen to be large.
&
G.2.2 Results for Bounded Compressors
Similarly to the previous section, we start with an adaptation of Lemma E.3 to the case without full-batch gradient computations.
Lemma G.6. Let Assumptions 2.3, D.I, D.2, D.3, D.4, D.5, G.I, 2.4 hold and the compression operator satisfy Definition 2.2. set λk+1 DQ maxi, Taglla 1²1 Also, let us introduce the notation
ARAgg ARAgg clipp...
,(t1)) ..... clipxe.. Act1 (o @e
Then for all 2 the iterates produced by ByZ-VR-MARINA-PP without full-batch gradient computations (Algorithm 4) satisfy
o² D
E ||g Vf (2*+1))]
< (1-2) () V (z+)) + (1 (1-882("
2
+ 12c6
.5² + PA 11 xx112
BE
where A, B. DG.
D.p.. Pos are defined in Lemma D.13.
Proof. Up to the replacement of the bound from Lemma D.10 with the bound from Lemma G.2, the proof the result identical to the proof Lemma E.3.
Theorem G.7. Let Assumptions 2.3, D.I. D.2, D.3, D.4, D.5, G.I, 2.4 hold. Setting Aet1 max,, Lig || | x* Assume that
0<7S L+ L+VA
4B <p.
where and B are defined in Theorem E.4. Then for all K 2 0 the iterates produced by Byz-VR- MARINA without full bathh computations (Algorithm 4) satisfy
V |11]
2Φ
+ p- p-4B 4B
2D
+
6P PPgt G
+ 24c5
o²
7
7
48 (K
(K+1)
6)2C2
b(p 4B)
where jK is chosen uniformly at random from x², xt xK x and to = f f(x)) - l +
1100 Vf (19)
Proof. The proof identical the proof of Theorem E.4 up the replacement of Lemma E.3 with Lemma G.6.
Theorem G.8. Let Assumptions 2.3, D.I, D.2, D.3, D.4, D.5, G.I, 2.4, 2.7 hold. Setting A maxi, Lij || ++1 x² Assume that
0 0<75 L+ 2A
8B <p.
71

---

where A and B are defined in Theorem E.S. Then for all K 2 0 the iterates produced by Byz-VR- MARINA without full aall-batch computations (Algorithm 4) satisfy
2 +
6P % G
70²
E [x((x)) - f (x*)] S (1 - p) Φ0 +
+ 24c0
pp
(1 - 8)2C2
Upp'
where p = min 774 (1- xB) ) and Φ = f (z0) f +
2%
l - Vf (29)1²
p
Proof. The proof identical the proof of Theorem E.5 up to the replacement of Lemma E.3 with Lemma G.6.
G.3 Main Results for Byz-VR-MARINA+ without Full-Batch Gradient Computations
G.3.1 Results for Bounded Compressors
Similarly to the analysis of ByZ-VR-MARINA without full-batch gradient computations, we start with the adaptation of Lemma F.1 to the no-full-batch gradient computations case.
Lemma G.9. Let Assumptions D.I, D.2, D.3, D.4, D.5, G.I, 2.4 hold and the compression operator satisfy Definition 2.2. Assume that C s G. We set Xk++1 Do max.,; Lig]l= x²1]. Then for all k 2 O the iterates produced by ByZ-VR-MARINA-PP2 without full-batch gradient computations (Algorithm 5) satisfy
E |10s k+ - Vf (2 (2
11]] S (1 (1-2) E ||o* Vf (1+)
(1
PogB
po² D'
+ 4c0
2
5)-
BE [+ + Dz² + P.A |latt1 20112
(35)
where A, B, D.PG. Poy are defined in Lemma E.I.
Proof. Up to the replacement of the bound from Lemma D.10 with the bound from Lemma G.2, the proof of the result is identical to the proof of Lemma F.1.
Theorem G.10. Let Assumptions D.I, D.2, D.3, D.4, D.5, G.I. 2.4 hold. Set A6+1 maxi. Lig || x²11 [....Asso Assume that
0<7S
4B <p
V+
where A and are defined in Theorem F.2. Then for all K 2 0 the iterates produced by Byz-VR- MARINA+ without full-batch gradient computations (Algorithm 5) satisfy
E V (5 [17
< 7 -
24
+ p p- 4B
2DŞ²
+
2P g G
+ 806
po²
(K(K1))
(1- (1-
b(p - (B)
where JkK is chosen uniformly at random from x², xt ok. and go =5(x9) 8
P 1000 v (1
Proof.
The proof is analogous to the proof of Theorem D.14.
Theorem G.11. Let Assumptions 2.4. D.I. D.2, D.3, D.4, D.5, G.1 2.7 hold. Set d
maxi, Lig ||o6+11 x*1 Assume that
1
0 0<Y min
8B <
I. 22A
where A and B are defined in Theorem F.3. Then for all K 2 0 the iterates produced by Byz-VR- MARINA+ without batl- gradient computations (Algorithm 5) satisfy
B () - (x*)) S (1 pk Φ0 2Nx² +
2P G
702
(1 (1-88²² 8)
+ 8c8
Up"
pp
where p = min 7/ (1 (1-
sA p
2 and Φ0 = (x00 - 1 + 23 6 v. (29)
72

---

Proof. The proof is analogous to the proof of Theorem D.15.
As in the case of ByZ-VR-MARINA, the above upper bounds for ByZ-VR-MARINA+ without full- batch gradient computations have additional terms proportional to e² In contrast to the results for ByZ-VR-MARIMA without full-batch gradient computations, these terms for Byz-VR-MARINA+ are 1/p times smaller.
73

---

H Experimental Details and Extra Experiments
H.1 Experimental Details
For each experiment, we tune the step size using the following set of candidates {0.1, 0.01, 0.001), 0.01,. }. The step size is fixed. We do not use learning rate warmup decay. We use batches of size 32 for all methods. For partial participation, in each round, we sample 20% of clients uniformly at random. For A AAIz* x-11|| || used for clipping, we select À from {0.1, 1., 10.}. Each experiment is run with three varying random seeds, and we report the mean optimality gap with one standard error. The optimal value is obtained by running gradient descent (GD) the complete dataset for 1000 epochs. Our implementation of attacks and robust aggregation schemes is based on the public implementation from (Gorbunov al., 2023).
H.2 Extra Experiments
Below we provide the missing neural network experiments from the main paper. We consider the MNIST dataset (LeCun and Cortes, 1998) and CIFARI 10 (Krizhevsky et al., 2009) (as in (Karimireddy et al., 2021)) with 20 clients, of which are malicious, and 4 clients are sampled in each step. For the attacks, we consider A Little is Enough (ALIE) (Baruch et al., 2019) and the aforementioned Shift-Back (SHB). For the aggregations, we consider coordinate median (CM) (Chen et al., 2017) and robust federated averaging (RFA) (Pillutla et al., 2022) with bucketing. For the MNIST dataset, we use a simple neural network with two convolution layers followed by two fully connected. For CIFAR 10, use ResNet18 (He et al., 2016) architecture with layer norm. One can note that the results are consistent with the ones provided in the main paper, i.c., clipping performs on par or better than its variant without clipping. and robust aggregator is able to withstand the shift-back attack without clipping. Our implementation available at https: : // //gi thub. Com/Samus Horeehhhor,ohhhoooaoo /RR_.. Byzantine/tan wteeeeeeteeeeeeeeeeeeeeeeeeeeeee tttp//eereeeaaaaeeeeeeeee seciiallpprrtiii palpppariippiii cipation..
OH ALL
EHD
014 AUE
MDC
WDOE
5
5
1011
10-1
2011
12-1
100
100
We
400chs
#20che
Figure 3: Training loss (top) and test accuracy (bottom) of 2 aggregation rules (CM, REA) under attacks (BF, LF, ALIE, SHB) the MNIST dataset under heterogeneous data split with 20 clients, 5 of which are malicious, 4 clients sampled per round.
@ Lon
g:
2
100
1001
4p001s
AUE
RSA
Wirhh
20
30
Figure 4: Training loss (top) and test accuracy (bottom) of 2 aggregation rules (CM, RFA) under attacks (BF, LF, ALIE, SHB) on the CIFARIO dataset under heterogeneous data split with 20 clients, 5 of which are malicious, 4 clients sampled per round.
74

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: see Sections 1, 3, 4,
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: see Sections 2, 3, 4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
75

---

Justification:
see Section 4 and the appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
76

---

Answer: [Yes]
Justification: see Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Policylly for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips wwtpccccpppppcpcccceceecccccclce stti:////ggiieeeeeeeuuubiiiiii //oo//eodeeesseeeeeeeeeee weriiisssinnniiieee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: see Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: see Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
77

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: We do not provide specific information about the computer resources used for our experiments. However, none of our experiments require significant computational power. Each experiment can be run in less than 5 minutes on Quadro RTX 6000 NVIDIA GPU.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp///eerrpp.cppppiiiiie cctpublicc/hhiccetuiiiiii
Answer: [Yes]
Justification: our work follows the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., . if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: theoretical paper
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
78

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
we do not train new models
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: provide citations when necessary
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
79

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
80


Reviews:
[{"review_id": "r9ixdONPy7", "reviewer": "Reviewer_RwBg", "summary": "This work considers the problem of Byzantine robustness in the framework of federated learning. The main contribution of this work is proposing and analyzing a novel federated algorithm, Byz-VR-MARINA-PP that utilizes gradient clipping. This algorithm is an extension of prior work, Byz-VR-MARINA, but importantly provides for the first time Byzantine robustness guarantees even in partial participation settings (even when Byzantine nodes could form a majority in some of the training rounds). The main idea of this method revolves around limiting the effects of Byzantine clients per round which is a consequence of the gradient clipping. As a result, Byz-VR-MARINA-PP is resilient to shift-back attacks. The authors further strengthen the proposed algorithm by incorporating communication compression. Theoretical results in terms of convergence guarantees are provided. The authors compare their results to SOTA works form the FL with Byzantine-workers literature and showcase the cost of obtaining Byzantine robustness in this more challenging regime. Additionally, numerical results showcase the merits of the proposed method.", "questions": "- In the main body of the paper the authors chose to use the more restrictive Assumption 2.5 whereas similar analysis has been performed in the Appendix with the less restrictive Assumption D.5.  Could the authors please elaborate on their decision and the differences between the two results?  \n- On line 304 the authors mention that in some cases partial participation is beneficial to their algorithm. Could they please provide some intuition behind this observation?\n- Although the theoretical results are convincing I believe that including more experimental results in broader regimes (of with a few more clients) would provide stronger evidence supporting the superiority of your method. This is not necessary but merely a suggestion.\n- In the Introduction/Contributions both \"Byz-VR-MARINA-PP\" and \"By-VR-MARINA-PP\" are met. Is this a typo?", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper addresses a very interesting and relevant problem in the area of Federated Learning. \n- The presentation of this work is very good and despite its theoretical depth it is easy to follow. \n- The theoretical results derived are comparable to the ones previously known for the full participation regime (despite being somewhat weaker) and the authors are comparing and contrasting their results with prior literature in a fair and clear manner. \n- Despite most of the tools used in this work are already known there has being a significant effort to combine them in an efficient manner and the derivation of the theoretical results is non-trivial.", "weaknesses": "- As I mentioned before most of the tools used in this work are not novel and as a result the novelty of this work is somewhat limited.\n- Although the main focus of this paper is theoretical it has to pointed out that the experimental results are derived in somewhat limited and less challenging settings i.e. a9a LIBSVM and MNIST datasets with 15 good and 5 Byzantine workers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback and time. We appreciate your positive evaluation of our work.\n\n>**As I mentioned before most of the tools used in this work are not novel and as a result the novelty of this work is somewhat limited.**\n\nWe kindly ask the reviewer to check our general response. \n\n>**Although the main focus of this paper is theoretical it has to pointed out that the experimental results are derived in somewhat limited and less challenging settings i.e. a9a LIBSVM and MNIST datasets with 15 good and 5 Byzantine workers.**\n>**Although the theoretical results are convincing I believe that including more experimental results in broader regimes (of with a few more clients) would provide stronger evidence supporting the superiority of your method. This is not necessary but merely a suggestion.**\n\nThank you for your comment! As requested, we have included an experiment with a larger model and dataset, namely a heterogeneous split of CIFAR10 with ResNet18 with GroupNorm. The setup for the MNIST dataset is described in the paper. \nAttached (see attached pdf in the main response), we provide a sample of these extra experiments, concretely [Shift Back + Coordinate-wise Mean] and [ALIE + Coordinate-wise Mean]. We note that the results are consistent with the ones provided in the paper, i.e., clipping performs on par or better than its variant without clipping, and no robust aggregator is able to withstand the shift-back attack without clipping. Finally, we are currently working on the experiments on even larger datasets and models, also with a larger number of clients.\n\n>**In the main body of the paper the authors chose to use the more restrictive Assumption 2.5 whereas similar analysis has been performed in the Appendix with the less restrictive Assumption D.5. Could the authors please elaborate on their decision and the differences between the two results?**\n\nAssumption D.5 is a direct generalization of Assumption 2.5 in the case of $B=0$. In the main part of the paper, we decided to consider a simplified version of the assumption to make it easier to read. The main message and the core ideas are still valid in the case of a simplified version of the assumption, but it allows us to present the result in a more compact and cleaner form. Also, we believe that obtaining convergence results for more complicated settings is important and we provide analysis for the more general case supplementary materials section. In contrast to Assumption 2.5, in Assumption D.5, instead of uniformly bounded heterogeneity, we have a bound that depends on the norm of the full gradient and constant, which makes this bound much more general. \n\n>**On line 304 the authors mention that in some cases partial participation is beneficial to their algorithm. Could they please provide some intuition behind this observation?**\n\nThe key reason for this phenomenon is that regardless of the real number of participating clients, the usage of $(\\delta,c)$-robust aggregator affects the final rate (i.e., stepsize) through the terms depending on parameter of the aggregator $\\delta$ (e.g., see formula (7)). Therefore, in the situation described in lines 296-301, the rate depends on two terms: one is decreasing in $C$ (roughly speaking, it corresponds to the decrease of the variance of the stochastic gradient $\\sim C$ times since the batchsize is increased $\\geq C/2$ times for each round in the worst case) and the second one is independent of $C$ and depends only on $\\delta$. Therefore, when the second term dominates the first one, it is optimal to decrease $C$ as long as the second term remains the main one and as long as $C \\geq \\max\\{1, \\delta_{\\text{real}}n / \\delta\\}$. Such a strategy allows to save on overall computations and at the same time keeps the number of communication rounds the same.\n\nMoreover, from the practical perspective, when the honest clients have similar data, it is natural that partial participation saves a lot of computation and this is exactly the setup of the experiment presented in Figure 1 (data was homogeneously split between workers). More precisely, the more honest workers participate, the less noisy the aggregated vector is (since the compute stochastic gradients independently; this can be seen from our bounds as well – the larger $C$ and $\\widehat{C}$ are, the fewer *communication rounds* the method requires). However, with the increase of participating clients, the total number of stochastic gradient calculations grows, i.e., the overall batch growth. From the standard practice of usage SGD, we know that for many ML problems the best (in terms of computation complexity) batch size is rarely a full batch and very often one can achieve reasonable results with relatively small batch size. This is exactly what our Figure 1 shows.\n\n>**In the Introduction/Contributions both \"Byz-VR-MARINA-PP\" and \"By-VR-MARINA-PP\" are met. Is this a typo?**\n\nThank you for noting this! It is indeed a typo, and \"Byz-VR-MARINA-PP\" is the correct option. We will fix this typo and also check for other typos in the text.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ub8mBIxs3W", "reviewer": "Reviewer_LGpc", "summary": "This paper proposes Byzantine robust approaches in the case of partial participation", "questions": "Did you compare to the literature on Asynchronous Byzantine ML?", "limitations": "Not applicable.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well written, but the claims of novelty are problematic, cf bellow.", "weaknesses": "The paper starts with a bold claim, \"literally, *all* existing methods with provable Byzantine robustness require the full participation of clients.\" Such a claim overlooks tens or at least a dozen papers on Asynchronous Byzantine machine learning that have been published in the past decade. All of these asynchronous solutions allow various forms of partial participation. Such a claim has no place in a properly researched paper on the topic.\n\nUpdate : While the analysis made in the paper is non-trivial, it relies on several confusions about what asynchrony means in distributed systems, in particular, any asynchronous systems allows Byzantine nodes not only to form a majority during some communication rounds, but to constitute 100% of the nodes during that round. For instance, in an asynchronous system, one update from one node can be enough to move on to the next iteration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**The paper starts with a bold claim, \"literally, all existing methods with provable Byzantine robustness require the full participation of clients.\" Such a claim overlooks tens, if not hundreds, of papers on Asynchronous Byzantine machine learning that have been published in the past decade. All of these asynchronous solutions allow various forms of partial participation. Such a claim has no place in a properly researched paper on the topic.**\n\nThe reviewer provides a very strong and vague claim that our work overlooks “tens, if not hundreds,” of papers that address the problem of partial participation in Byzantine-robust learning **without providing even a single reference** supporting this claim. **The review completely ignores the essence of our paper – new results and algorithms.** This is not a scientific approach to writing the review. \n\n- First of all, we never claimed that there exist no approaches considering Byzantine robustness in the context of partial participation. In contrast, we cite (Data & Diggavi, 2021), who also study this problem, and discuss the relation of our results to their ones in detail. \n\n- Next, in the phrase \"literally, all existing methods with provable Byzantine robustness require the full participation of clients\", a central part for us is **provable Byzantine robustness**. The existing work (Data & Diggavi, 2021) requires that at each round, the majority of participating clients are honest, which in terms of the theoretical analysis, is very similar to the case of full participation.\n\n- Moreover, we found **just five works** [1-5], not even ten and certainly not even close to hundreds, as the reviewer claims. However, none of these approaches are **provably** robust against Byzantine attacks when there are no additional assumptions (on some extra data or on the frequency filters). Indeed, in [1], the authors propose to use Lipschitz filter and frequency filters in order to filter out Byzantine workers. However, Theorem 4 from [1] establishes convergence only to some neighborhood that depends on the variance of the stochastic gradients and does not depend on the stepsize and number of Byzantine clients. This result is shown for homogeneous data regime, when the convergence to any optimization error can be achieved. Next, in [2, 4], the authors use additional validation data on the server to decide whether to accept the update from workers. This assumption is restrictive for many FL applications when the data on clients is private and is not available on the server. In [3], the authors propose so-called Buffered ASGD (and its momentum version) where the key idea is to split workers into the buffers and wait until each buffer gets at least one gradient update. In the case when the number of buffers is sufficiently large (should be at least $2B$, where $B$ is the number of Byzantine workers), the authors show that BASGD converges. However, this means that to make the step BASGD requires to collect sufficiently large number of gradients such that the good buffers form majority, which is closer to full participation than to the partial participation. We also found work [5], where the authors do not provide theoretical convergence analysis. We will add the discussion of work [1-5] to our paper: **this will be just a minor addition that will not change the main message of our work at all.**\n\n- Finally, the asynchronous communication protocol does not fit the setting of our paper, where we consider clients sampling. For example, one cannot model a synchronous communication with sampling of more than 1 client each round through the asynchronous one. **Therefore, the “criticism” provided by the reviewer is completely unrelated and it does not justify such a low score.** \n\n---\n\nReferences:\n\n[1] Damaskinos et al. Asynchronous Byzantine Machine Learning (the case of SGD). ICML 2018\n\n[2] Xie et al. Zeno++: Robust Fully Asynchronous SGD. ICML 2020\n\n[3] Yang & Li. Buffered Asynchronous SGD for Byzantine Learning. JMLR 2023\n\n[4] Fang et al. AFLGuard: Byzantine-robust Asynchronous Federated Learning. ACSAC 2022\n\n[5] Zhang et al. Anti-Byzantine Attacks Enabled Vehicle Selection for Asynchronous Federated Learning in Vehicular Edge Computing. arXiv:2404.08444", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qPlzvY8E6T", "reviewer": "Reviewer_oCpn", "summary": "The paper studied the federated learning problem with Byzatine clients and partial participation. The paper proposed a new algorithm called Byzantine-tolerant Variance-Reduced MARINA with Partial Participation or Byz-VR-MARINA-PP and proved its convergence upper bound when the aggregator is a $(\\delta, c)$-Robust Aggregator. The key idea of Byz-VR-MARINA-PP is to use clipping. In addition, the paper also proposed a heuristic algorithm in the general case. The performance of the proposed algorithm is verified via experiments as well.", "questions": "1. Can the results be extended when the number of local update is larger than 1?\n\n2. Is it possible to obtain any analysis of the heuristic algorithm under some assumptions?\n\n3. Could you please add more experiments using harder and more popular datasets in Federated Learning?", "limitations": "The proposed algorithm and its analysis focused on the case when the number of local update is 1.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper proposed a new federated learning coping with Byzatine clients and partial participation. The main focus is to consider the partial participation. The algorithm is called Byz-VR-MARINA-PP and the paper proved its convergence upper bound when the aggregator is a $(\\delta, c)$-Robust Aggregator. \n\n2. Using the idea of Byz-VR-MARINA-PP, the paper proposed a general algorithm. \n\n3. The paper is very well written. The explanation is very clear.", "weaknesses": "1. The proposed algorithm and its analysis focused on the case when the number of local update is 1. \n\n2. There is no any analysis of the heuristic algorithm. \n\n3. The experiments only use two simple datasets, LIBSVM and MNIST.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and time.\n\n>**The proposed algorithm and its analysis focused on the case when the number of local update is 1.**\n\n>**Can the results be extended when the number of local update is larger than 1?**\n\nThank you for raising this point! We understand that in a Federated Learning setting, several local steps are important. However, initially, we need to understand how to deal with partial participation for the provably Byzantine-robust training in case of 1 local update since partial participation is an interesting and complicated question on its own under the presence of Byzantine clients. Moreover, we have page limits for the paper, so we cannot cover all possible scenarios. Taking this into consideration, we leave the analysis of multiple local steps for future work since we believe a proper consideration of the effect of multiple local steps deserves a separate paper.\n\n>**There is no any analysis of the heuristic algorithm.**\n\nWe kindly disagree that this is a weakness of our paper. We provided an extensive analysis of the proposed method Byz-VR-MARINA. The heuristic framework is an additional idea that we provide to generalize the proposed algorithm. Note that before this paper, there was no other algorithm with partial participation and with provable Byzantine robust guarantees without additional assumptions on the number of participating clients. Moreover, we have a page limit for the paper, so we cannot cover all settings and analyze all methods.\n\n>**The experiments only use two simple datasets, LIBSVM and MNIST.**\n\n>**Could you please add more experiments using harder and more popular datasets in Federated Learning?**\n\nThank you for your comment. As requested, we have included an experiment with a larger model and dataset, namely a heterogeneous split of CIFAR10 with ResNet18 with GroupNorm. The setup for the MNIST dataset is described in the paper. \nAttached (see attached pdf in the main response), we provide a sample of these extra experiments, concretely [Shift Back + Coordinate-wise Mean] and [ALIE + Coordinate-wise Mean]. We note that the results are consistent with the ones provided in the paper, i.e., clipping performs on par or better than its variant without clipping, and no robust aggregator is able to withstand the shift-back attack without clipping. Finally, we are currently working on experiments on even larger datasets and models. If the reviewer has some concrete suggestions, we would like to hear them.\n\n> **Is it possible to obtain any analysis of the heuristic algorithm under some assumptions?**\n\nIf we assume a similar condition to the smoothness of communicated vectors $g^k_i$ for good workers, we can apply a similar analysis and obtain similar guarantees for the general method. We can add such an analysis in the appendix. However, we are not aware of any examples except for Byz-VR-MARINA, for which this smoothness property holds. We tried to analyze our heuristic extension of Byzantine Robust Momentum SGD (Karimireddy et al., 2021, 2022) but faced some technical difficulties that we have not overcome yet.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RcH5GYYzht", "reviewer": "Reviewer_mV5C", "summary": "This paper addresses an important problem: how to achieve Byzantine robustness when the clients partially participate in distributed learning and the Byzantine clients form a majority of sampled clients in some rounds. To solve this problem, the authors propose using the gradient clipping technique to control potential disturbances caused by Byzantine clients. The proposed method, which combines Byz-VR-MARINA and gradient clipping methods, has provable convergence for general smooth non-convex functions and PL functions.", "questions": "My detailed questions are listed in the above section; please refer to it.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow.\n\t\t\n2. The investigated problem, achieving Byzantine robustness with clients' partial participation, is important and not well understood in the field of  Byzantine-robust distributed learning.", "weaknesses": "1. The novelty is limited since the proposed method is a simple combination of the existing method Byz-VR-MARINA and gradient clipping. The idea of using gradient clipping to bound the potential harm caused by Byzantine clients in partial participation is straightforward and not surprising.\n\n2. In Line 225, the authors claim that ''In contrast, Byz-VR-MARINA-PP tolerates any attacks even when all sampled clients are Byzantine workers since the update remains bounded due to the clipping\". Why is this the case? Can Byz-VR-MARINA-PP still converge when Byzantine clients constitute a majority of the sampled clients in all rounds? This appears counter-intuitive. I believe there should be specific requirements on the client sample sizes $C$ and $\\hat{C}$ concerning the ratio of Byzantine clients $\\delta_{\\text{real}}$ or the upper bound ratio $\\delta$, but I did not find such conditions in Theorem 4.1 and Theorem 4.2. Have I overlooked something? If I have misunderstood any aspects of the paper, please correct me. \n\t\t\n3. Since the gradient clipping method is able to control the potential harm caused by Byzantine clients, is it necessary to use the robust aggregator $\\text{ARAgg}(\\cdot)$? Can the mean aggregator be used as a substitute for the robust aggregator $\\text{ARAgg}(\\cdot)$?\n\t\t\n4. The recent work [1] also considers  partial participation within Byzantine-robust distributed learning. The authors should discuss it in the related works part.\n\t\t\n\t[1] Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., Rizk, G., \\& Voitovych, S. (2024). Tackling Byzantine Clients in Federated Learning. arXiv preprint arXiv:2402.12780.\n\n5. Why does partial participation show faster convergence than full participation, as depicted in the middle of Figure 1? Could the authors provide insights or theoretical explanations for this phenomenon?\n\t\t\n6. I am curious about how the client's sample size affects the proposed method in practice. Could the authors vary the client's sample size in experiments?\n\t\t\n7. In Definition 2.1, '($\\delta, c$)-Robust Aggregator' should be '($\\delta_{\\max}, c$)-Robust Aggregator', as $\\delta_{\\max}$ represents the breakdown point of the robust aggregator, not $\\delta$; please refer to Karimireddy et al. (2021).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and time. Below, we address the concerns and comments raised by the reviewer.\n\n>**The novelty is limited since the proposed method is a simple combination of the existing method Byz-VR-MARINA and gradient clipping. The idea of using gradient clipping to bound the potential harm caused by Byzantine clients in partial participation is straightforward and not surprising.**\n\nWe kindly ask the reviewer to check our general response.\n\n>**In Line 225, the authors claim that ''In contrast, Byz-VR-MARINA-PP tolerates any attacks even when all sampled clients are Byzantine workers since the update remains bounded due to the clipping\". Why is this the case? Can Byz-VR-MARINA-PP still converge when Byzantine clients constitute a majority of the sampled clients in all rounds? This appears counter-intuitive. I believe there should be specific requirements on the client sample sizes $C$ and $\\widehat{C}$ concerning the ratio of Byzantine clients $\\delta_{\\text{real}}$ or the upper bound ratio $\\delta$, but I did not find such conditions in Theorem 4.1 and Theorem 4.2. Have I overlooked something? If I have misunderstood any aspects of the paper, please correct me.**\n\nAs we explain in Footnote 3 on page 6, for our results, we need $\\widehat{C} \\geq \\max\\{1, \\delta_{\\text{real}}n/\\delta\\}$. This condition ensures that with probability $p$, honest workers are guaranteed to be in the majority during the communication round, which allows the method to “adjust” the update direction $g^{k+1}$. Regarding line 225: we meant that even if for *some communication rounds* all sampled clients are Byzantines, our method provably tolerates this.\n\n>**Since the gradient clipping method is able to control the potential harm caused by Byzantine clients, is it necessary to use the robust aggregator $\\text{ARAgg}(\\cdot)$? Can the mean aggregator be used as a substitute for the robust aggregator $\\text{ARAgg}(\\cdot)$?**\n\nThis is an excellent question. We have an analysis showing that robust aggregation is needed only with probability $p$ (when a large number of workers participate in the communication round) for the case $C = 1$. The proof can be generalized to the case of any $C > 1$ as well, but this will decrease the probability of steps when the method actually does the progress, and as a result convergence rate will be slower.\n\n>**The recent work [1] also considers partial participation within Byzantine-robust distributed learning. The authors should discuss it in the related works part.\n[1] Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., Rizk, G., & Voitovych, S. (2024). Tackling Byzantine Clients in Federated Learning. arXiv preprint arXiv:2402.12780.**\n\nThank you for the reference; we will add it to the revised version. However, similarly to (Data & Diggavi, 2021), the method from the mentioned paper requires the number of sampled clients to be such that honest clients always form a majority (otherwise, there is a certain probability of divergence, and this probability is growing over time).\n\n>**Why does partial participation show faster convergence than full participation, as depicted in the middle of Figure 1? Could the authors provide insights or theoretical explanations for this phenomenon?**\n\nWhen the honest clients have similar data, it is natural that partial participation saves a lot of computation, and this is exactly the setup of the experiment presented in Figure 1 (data was homogeneously split between workers). More precisely, the more honest workers participate, the less noisy the aggregated vector is (since they compute stochastic gradients independently; this can be seen from our bounds as well – the larger $C$ and $\\widehat{C}$ are, the fewer *communication rounds* the method requires). However, with the increase of participating clients, the total number of stochastic gradient calculations grows, i.e., the overall batch growth. From the standard practice of usage SGD, we know that for many ML problems the best (in terms of computation complexity) batch size is rarely a full batch, and very often, one can achieve reasonable results with a relatively small batch size. This is exactly what our Figure 1 shows.\n\n>**I am curious about how the client's sample size affects the proposed method in practice. Could the authors vary the client's sample size in experiments?**\n\nThank you for the suggestion. We have added this case for the MNIST dataset, where we sample 1, 4, and 11 clients. We have attached (see attached pdf in the main response) several samples from these experiments on the heterogeneous split with the Shift Back attack and Coordinate-wise Mean as an aggregator. We first compare how clipping behaves across different sample sizes. We note that the smaller the sample size, the faster the convergence in terms of total computations; however, for sample size 1, the method does not converge to the same precision solution due to high noise. For the version without clipping ), we observe convergence only for sample size 11, as this is the only sample size where it is guaranteed that within each round, malicious clients cannot form a majority. Finally, we compare clipping vs. no clipping across these sample sizes. We note that the results are consistent with those provided in the paper, i.e., clipping performs on par or better than its variant without clipping, and no robust aggregator is able to withstand the shift-back attack without clipping unless malicious clients cannot form a majority. \n\n>**Definition 2.1**\n\nWe prefer to call it $(\\delta,c)$-robust aggregator to emphasize that it requires to know parameter $\\delta$. We will add this remark to the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8aQq41Qk5h", "reviewer": "Reviewer_xeac", "summary": "This paper presents a new distributed learning method called Byz-VR-MARINA-PP, which can achieve Byzantine robustness and partial participation at once. The authors theoretically analyze the convergence and Byzantine robustness of Byz-VR-MARINA-PP. Numerical results of Byz-VR-MARINA-PP are also provided in this paper.", "questions": "n/a", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is generally well-written. The problem of obtaining Byzantine robustness and partial participation is important in practical applications.", "weaknesses": "1. The proposed method is a combination of Byz-VR-MARINA and clipping, and the convergence analysis is similar to that of Byz-VR-MARINA. In light of these, the novelty of the paper is limited. \n2. The proposed method requires computing the full gradient with probability $p$ at each iteration, which is computationally expensive, especially when the number of training instances is large. \n3. The numerical experiment in this paper is conducted on a9a and MNIST datasets. The scale of these two datasets and the corresponding learning models is quite small given the computation power of today's devices. It would be interesting to see whether the proposed method works on larger datasets and models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and time. Below we address the concerns and comments raised by the reviewer.\n\n>**The proposed method is a combination of Byz-VR-MARINA and clipping, and the convergence analysis is similar to that of Byz-VR-MARINA. In light of these, the novelty of the paper is limited.**\n\nWe kindly ask the reviewer to check our general response. \n\n>**The proposed method requires computing the full gradient with probability $p$ at each iteration, which is computationally expensive, especially when the number of training instances is large.**\n\nIn practice, one can replace the full gradient computation with just a larger batch computation, i.e., with probability $p$ good workers can compute a mini-batched stochastic gradient with batch-size $b’ > b$ similarly to Geom-SARAH [1].  The usage of periodic full gradient computation is a common issue of many existing variance-reduced methods. Moreover, as the reviewer acknowledged, the considered problem is challenging. Therefore, we believe that despite the mentioned limitation, our work makes an important contribution to the field, and achieving similar results without full gradient/large batch computations at all is an interesting direction for future research. We would like to highlight that we have resolved this issue, at least in practical implementation, where we propose and experimentally analyze a version of our method that works with only a mini-batch gradient oracle (see lines 305-315, 350-363 and Figure 2).\n\n[1] Horváth, Samuel, Lihua Lei, Peter Richtárik, and Michael I. Jordan. \"Adaptivity of stochastic gradient methods for nonconvex optimization.\" SIAM Journal on Mathematics of Data Science 4, no. 2 (2022): 634-648.\n\n>**The numerical experiment in this paper is conducted on a9a and MNIST datasets. The scale of these two datasets and the corresponding learning models is quite small given the computation power of today's devices. It would be interesting to see whether the proposed method works on larger datasets and models.**\n\nThank you for your comment. As requested, we have included an experiment with a larger model and dataset, namely a heterogeneous split of CIFAR10 with ResNet18 with GroupNorm. The setup for the MNIST dataset is described in the paper. \nAttached (see attached pdf in the main response), we provide a sample of these extra experiments, concretely [Shift Back + Coordinate-wise Mean] and [ALIE + Coordinate-wise Mean]. We note that the results are consistent with the ones provided in the paper, i.e., clipping performs on par or better than its variant without clipping, and no robust aggregator is able to withstand the shift-back attack without clipping. Finally, we are currently working on experiments on even larger datasets and models. If the reviewer has some concrete suggestions, we would like to hear them.\n\nHowever, we also want to highlight that our work is primarily theoretical, and experiments are mostly needed to illustrate and support our theoretical findings. Moreover, closely related works also consider models and datasets of similar sizes, e.g., , e.g., (Karimireddy et al., 2021) also test their method (Byzantine-Robust Momentum SGD) at the training of MLP on MNIST and (Gorbunov et al., 2023) also test their Byz-VR-MARINA on the logistic regression for a9a dataset. Since in our work, we propose versions of these methods with clipping and partial participation, it was natural for us to consider the same tasks in the experiments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their feedback and time. Since several reviewers had concerns about the novelty, which we kindly but firmly disagree with, we prepared a general message addressing this.

As we mention in the introduction (page 2, left column, lines 49-54) and explain in Section 3 (paragraph “New ingredients: client sampling and clipping”), all existing methods (and Byz-VR-MARINA in particular) cannot be naively combined with client sampling/partial participation with an arbitrary small number of sampled clients: this can lead to communication rounds when Byzantine workers form a majority, which allows them to shift the updates arbitrary far from the solution. To handle such situations, we propose to use gradient clipping to the vectors that are communicated by the clients. As we explain in the same paragraph (page 6, lines 226-230), gradient clipping makes the updates bounded. Therefore, even if Byzantine workers accidentally form a majority during some rounds, the norm of the shift they can produce is bounded by a clipping level $\lambda_{k+1}$.

However, the introduction of the clipping does not come for free: if the clipping level is too small, clipping can create a noticeable bias to the updates. Because of this issue, existing works such as (Gorbunov et al., 2020; Zhang et al., 2020) use non-trivial policies for the choice of the clipping level, and the analysis in these works differs significantly from the existing analysis for the methods without clipping. The analysis of Byz-VR-MARINA is based on the unbiasedness of vectors $\mathcal{Q}(\hat \Delta_i(x^{k+1}, x^k))$, i.e., on the following identity: $\mathbb{E}[\mathcal{Q}(\hat \Delta_i(x^{k+1}, x^k)) \mid x^{k+1}, x^k] = \Delta_i(x^{k+1}, x^k) = \nabla f_i(x^{k+1}) - \nabla f_i(x^k)$. Since $\mathbb{E}[\text{clip}\_{\lambda\_{k+1}}(\mathcal{Q}(\hat \Delta_i(x^{k+1}, x^k))) \mid x^{k+1}, x^k] \neq \nabla f\_i(x^{k+1}) - \nabla f\_i(x^k)$ in general, to analyze Byz-VR-MARINA-PP we also use a special choice of the clipping level: $\lambda_{k+1} = \alpha_{k+1} \|\|x^{k+1} - x^k\|\|$. To illustrate the main reasons for that, let us consider the case of uncompressed communication ($\mathcal{Q}(x) \equiv x$). In this setup, for large enough $\alpha_{k+1}$ we have $\text{clip}\_{\lambda\_{k+1}}\hat \Delta\_i(x^{k+1}, x^k) = \hat \Delta\_i(x^{k+1}, x^k)$ for all $i\in \mathcal{G}$ (due to Assumption 2.6), which allows us using a similar proof to the one for Byz-VR-MARINA when good workers form a majority in a round. Moreover, when Byzantine workers form a majority, our choice of the clipping level allows us to bound the second moment of the shift from the Byzantine workers as $\sim \|\| x^{k+1} - x^k \|\|^2$ (see Lemmas D.9 and D.12), i.e., the second moment of the shift is of the same scale as the variance of $\lbrace g_i \rbrace_{i\in \mathcal{G}}$, which goes to zero (see page 5, lines 205-209). Next, to properly analyze these two situations, we overcame another technical challenge related to the estimation of the conditional expectations and probabilities of corresponding events (see Lemmas D.9 - D.10 and formulas for $p_G$ and $\mathcal{P}_{\mathcal{G}_C^k}$ at the beginning of Section 4). In particular, the derivation of formula (22) is quite non-standard for stochastic optimization literature: there are two sources of stochasticity – one comes from the sampling of clients and the other one comes from the sampling of stochastic gradients and compression. This leads to the estimation of variance of the average of the random number of random vectors, which is novel on its own. In addition, when the compression operator is used, the analysis becomes even more involved since one cannot directly apply the main property of unbiased compression (Definition 2.2), and we use Lemma D.6 in the proof to address this issue. It is also worth mentioning that in contrast to Byz-VR-MARINA, our method does not require full participation even with a small probability $p$. Instead, it is sufficient for Byz-VR-MARINA-PP to sample a large enough cohort of $\hat{C}$ clients with probability $p$ to ensure that Byzantine workers form a minority in such rounds. **Taking into account all of these multiple technical challenges that we circumvented, we believe that our choice of the clipping level is not obvious beforehand, and our analysis significantly differs from the analysis of Byz-VR-MARINA.**

Finally, we also want to emphasize that the idea of using gradient clipping to handle the Byzantine workers in the case of partial participation is novel on its own. Karimireddy et al. (2021) used clipping to construct robust aggregation, but it was never used in the way we apply it. We believe our work is an important step towards building more efficient Byzantine-robust methods supporting partial participation.

If our paper gets accepted, we will expand these clarifications in the main text (the accepted papers have one extra page).

Meta-review: This paper considers federated learning with Byzantine clients and partial participation. The problem is of practical importance, but lack of investigation. The reviewer raise several concerns, such as lack of new elements in the algorithm design (the proposed algorithm is the combination of several existing tools), lack of numerical experiments (the current numerical experiments are relatively simple), etc. However, the strengths of this paper outweigh its weaknesses. 

- Reviewer LGpc commented on the connection between partial participation and asynchronous participation. These two settings are tightly related but different. The investigated problem is originated from the recent federated learning applications, and has its own importance.

- Reviewer mV5C pointed that the main weakness of this paper is the combination of existing tools. Considering the importance and timeliness of the investigated problem, the proposed method would potentially motivate further research efforts. In addition, the analysis made in the paper is non-trivial.

Therefore, I recommend to accept.
Decision: Accept (poster)