Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences

Authors: grigory  malinovsky
‡  peter
richtárik  kaust
eduard  gorbunov
  mbzuai
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 23:44:30

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.

Main paper: 
 introduction: 
 Distributed optimization problems are a 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ý et al., 2016; Kairouz et al., 2021) . Such problems require specialized algorithms adapted to the distributed setup. Additionally, the adoption of distributed optimization methods is 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 a 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 et al., 2018b; Ryabinin and Gusev, 2020; Atre et al., 2021; Diskin et al., 2021a) . In such applications, there is a high risk of the occurrence of so-called Byzantine workers (Lamport et al., 1982; Su and Vaidya, 2016) -participants who can violate the prescribed distributed algorithm/protocol either intentionally or simply because they are faulty. In general, such workers may even have access to some private data of certain participants and may collude to increase their impact on the training. Since the ultimate goal is to achieve robustness 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 a 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 Karimireddy et al., , 2022;; Gorbunov et al., 2022 Gorbunov et al., , 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 largescale 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 a majority during some rounds.Our Contributions We develop Byzantine-tolerant Variance-Reduced MARINA with Partial Participation (Byz-VR-MARINA-PP, 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 to 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-PP for general smooth non-convex functions and Polyak-Łojasiewicz functions. In the special case of full participation, 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 a simplified version of Byz-VR-MARINA-PP with better neighborhood term in the convergence bounds (Byz-VR-MARINA-PP+, 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.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 implies that more significant algorithmic changes are required to achieve Byzantine robustness, a point also formally proven by Karimireddy et al. (2021) , who demonstrate that permutation-invariant algorithms -i.e., 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/PAGE-type (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 (Karimireddy et al., , 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-MARINA-PP provably converges even when the server samples one client, which can be Byzantine. If the number of participating clients is 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 A. 
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 problem5 EQUATION)where G is a set of regular clients of size G := |G|. In the context of distributed learning, f i : R d → R corresponds to the loss function on the data of client i, and f i,j : R d → 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 We assume that B := |B| := δ real n ≤ δn, where δ real is an exact ratio of Byzantine workers and δ is a known upper bound for δ real . We also assume that 0 ≤ δ real ≤ δ < 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 ∥x∥ denotes a standard ℓ 2 -norm of x ∈ R d , ⟨a, b⟩ refers to the standard inner product of vectors a, b ∈ R d . The clipping operator is defined as follows: clip λ (x) := min{1, λ /∥x∥}x for x ̸ = 0 and clip λ (0) := 0. Finally, Prob{A} denotes the probability of event A, E[ξ] is the full expectation of random variable ξ, E[ξ | A] is the expectation of ξ conditioned on the event A. We also sometimes use E k [ξ] 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 (δ, c)-robust aggregation, which is a generalization of the definitions proposed by Karimireddy et al. (2021 Karimireddy et al. ( , 2022)) . Definition 2.1 ((δ, c)-Robust Aggregator). Assume that {x 1 , x 2 , . . . , x n } is such that there exists a subset G ⊆ [n] of size |G| = G ≥ (1 -δ)n for δ ≤ δ max < 0.5 and there exists σ ≥ 0 such that 1 G(G-1) i,l∈G E ∥x i -x l ∥ 2 ≤ σ 2 where the expectation is taken w.r.t. the randomness of {x i } i∈G . We say that the quantity x is (δ, c)-Robust Aggregator (δ, c) -RAgg) and write x = RAgg (x 1 , . . . , x n ) for some c > 0, if the following inequality holds:EQUATIONwhere x := 1 |G| i∈G x i . If additionally x is computed without the knowledge of σ 2 , we say that x is (δ, c)-Agnostic Robust Aggregator (δ, c) -ARAgg and write x = ARAgg (x 1 , . . . , x n ).One can interpret the definition as follows. Ideally, we would like to filter out all Byzantine workers and compute just an average x 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 a certain sense, e.g., in terms of the expected squared distance to x. As Karimireddy et al. (2021) formally show, in terms of such criterion (E[∥ x -x∥ 2 ]), the definition of (δ, c) -RAgg cannot be improved (up to the numerical constant). Moreover, standard aggregators such as Krum (Blanchard et al., 2017) , geometric median, and coordinate-wise median do not satisfy Definition 2.1 (Karimireddy et al., 2021) , though another popular standard aggregation rule called coordinate-wise trimmed mean (Yin et al., 2018) satisfies Definition 2.1 as shown by Allouah et 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-wise median, i.e., with Bucketing Krum, geometric, and coordinate-wise median become (δ, c) -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 δ is a part of the input that should satisfy δ real ≤ δ ≤ δ max .Compression operators. In our work, we use standard unbiased compression operators with relatively bounded variance (Khirirat et al., 2018; Horváth et al., 2023) . Definition 2.2 (Unbiased compression). Stochastic mapping Q : R d → R d is called unbiased compressor/compression operator if there exists ω ≥ 0 such that for any x ∈ R d E[Q(x)] = x, E ∥Q(x) -x∥ 2 ≤ ω∥x∥ 2 . For the given unbiased compressor Q(x), one can define the expected density6 as ζ Q := sup x∈R d E [∥Q(x)∥ 0 ], where ∥y∥ 0 is the number of non-zero components of y ∈ R d .In this definition, parameter ω reflects how lossy the compression operator is: the larger ω 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 et al., 2017) . For RandK compression ω= d K -1, ζ Q = K and for ℓ 2 -quantization ω = √ d-1, ζ Q = √d, see the proofs in (Beznosikov et 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 (δ, c)-ARAgg and there exists constant F A > 0 such that for any inputs x 1 , . . . , x n ∈ R d the norm of the aggregator is not greater than the maximal norm of the inputs:∥A (x 1 , . . . , x n )∥ ≤ F A max i∈[n] ∥x i ∥.The above assumption is satisfied for popular (δ, c)-robust aggregation rules presented in the literature (Karimireddy et al., 2021 (Karimireddy et al., , 2022)) . Therefore, this assumption is more a formality than a real limitation: it is needed to exclude some pathological examples of (δ, c)-robust aggregation rules, e.g., for any A that is (δ, c)-RAgg one can construct unbounded (δ, 2c)-RAgg as A = A + X, where X is a random sample from the Gaussian distribution N (0, cδσ 2 ).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:∥Q(x)∥ ≤ D Q ∥x∥ ∀x ∈ R d .For example, RandK and ℓ 2 -quantization meet this assumption withD Q = d K and D Q = √ d respectively.In general, constant D Q can be large (proportional to d). However, in practice, one can use RandK with K = d 100 and, thus, have moderate D Q = 100. We also have the results without Assumption 2.4, but with worse dependence on some other parameters, see Section 4.Next, we assume that good workers have ζ 2 -heterogeneous local loss functions. Assumption 2.5 (ζ 2 -heterogeneity). We assume that good clients have ζ 2 -heterogeneous local loss functions for some ζ ≥ 0, i.e., 1G i∈G ∥∇f i (x) -∇f (x)∥ 2 ≤ ζ 2 ∀x ∈ R d .The above assumption is quite standard for the literature on Byzantine robustness (Wu et al., 2020; Karimireddy et al., 2022; Gorbunov et al., 2023; Allouah et al., 2023) . Moreover, some kind of a 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 for i ∈ G ∩ S k in parallel do 7:x k+1 = x k -γg k and λ k+1 = α k+1 ∥x k+1 -x k ∥ 8: Set g k+1 i = ∇f i (x k+1 ), if c k = 1, g k + clip λ k+1 Q ∆ i (x k+1 , x k ) , otherwise,where∆ i (x k+1 , x k ) is a mini-batched estimator of ∇f i (x k+1 ) -∇f i (x k ), Q(•) for i ∈ G ∩ S k are computed independently 9:end for 10:g k+1 =    ARAgg {g k+1 i } i∈S k , if c k = 1, g k + ARAgg clip λ k+1 Q ∆ i (x k+1 , x k ) i∈S k, otherwise 11: end for Assumption 2.5, see Assumption D.5. Finally, the case of homogeneous data (ζ = 0) is also quite popular for collaborative learning (Diskin et al., 2021b; Kijsipongse et al., 2018a) .The following assumption is classical for the literature on non-convex optimization. Assumption 2.6 (Smoothness (simplified)). We assume that for all i ∈ G and j ∈ [m] there existsEQUATIONMoreover, we assume that f is uniformly lower bounded by f * ∈ R, i.e., f * := inf x∈R d f (x).For the sake of simplicity, we 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.1).Finally, we also consider functions satisfying Polyak-Łojasiewicz (PŁ) condition (Polyak, 1963; Łojasiewicz, 1963) . This assumption belongs to the class of assumptions on the structured nonconvexity that allows achieving linear convergence (Necoara et al., 2019) . Assumption 2.7 (PŁ condition (optional)). We assume that function f satisfies Polyak-Łojasiewicz (PŁ) condition with parameter µ > 0, i.e., for all x ∈ R d there existsf * := inf x∈R d f (x) such that ∥∇f (x)∥ 2 ≥ 2µ (f (x) -f * ) .3 New Method: Byz-VR-MARINA-PPWe propose a new method called Byzantine-tolerant Variance-Reduced MARINA with Partial Participation (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-MARINA-PP works, we first consider a special case of full participation.Special case: Byz-VR-MARINA. If all clients participate at each round (S k ≡ [n]) and clipping is turned off (λ k ≡ +∞), then Byz-VR-MARINA-PP reduces to Byz-VR-MARINA that works as follows. Consider the case when no compression is applied (Q(x) = x) and ∆ i (x k+1 , x k ) = ∇f i,j k (x k+1 ) -∇f i,j k (x k ), where j k is sampled uniformly at random from [m], i ∈ G. Then, regular workers compute GeomSARAH/PAGE gradient estimator at each step: for i ∈ Gg k+1 i = ∇f i (x k+1 ), with probability p, g k + ∇f i,j k (x k+1 ) -∇f i,j k (x k ), otherwiseWith small probability p, good workers compute full gradients, and with larger probability 1 -p 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 ∼ b /m). Such estimators are known to be optimal for finding stationary points in the stochastic first-order optimization (Fang et al., 2018; Arjevani et al., 2023) . Next, good workers send g k+1 i or ∇f i,j k (x k+1 ) -∇f i,j k (x k ) to the server who robustly aggregate the received vectors. Since estimators are conditionally biased, i.e., E[gk+1 i | x k+1 , x k ] ̸ = ∇f i (x k+1), the additional bias coming from the aggregation does not cause significant issues in the analysis or practice. Moreover, the variance of {g k+1 i } i∈G w.r.t. the sampling of the stochastic gradients is proportional to ∥x k+1 -x k ∥ 2 → 0 with probability 1 -p (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 k+1 i } i∈G w.r.t. the sampling of the stochastic gradients and compression remains proportional to ∥x k+1 -x k ∥ 2 with probability 1 -p.New ingredients: 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 is applied to the compressed stochastic gradient differences. With a small probability p, a larger number7 of clients C ≤ 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 a majority or, more precisely when there are more than δC Byzantine workers among the sampled ones. Indeed, without clipping (or some other algorithmic changes) such situations are 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-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 λ k+1 ∼ ∥x k+1 -x k ∥ we 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 1 -p regular workers can transmit just compressed vectors and leave the clipping operation to the server since Byzantines can ignore clipping operation. 
convergence results: 
 We defineG k C = G ∩ S k and G k C = |G k C | and n k = n! k!(n-k)!represents the binomial coefficient. We also use the following probabilities:p G := Prob G k C ≥ (1 -δ) C = ⌈(1-δ)C⌉≤t≤C ( G t )( n-G C-t ) ( n C ) , P G k C := Prob i ∈ G k C | G k C ≥ (1 -δ) C = C np G • ⌈(1-δ)C⌉≤t≤C ( G-1 t-1 )( n-G C-t ) ( n-1 C-1 ). These probabilities naturally appear in the analysis and statements of the theorems. When c k = 0, then server samples C clients, and two situations can appear: either G k C is at least (1 -δ) C meaning that the aggregator can ensure robustness according to Definition 2.1 orG k C < (1 -δ) C. Probability p G 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 P G k C 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, ifC = 1, then p G = G /n and P G k C = 1 /G; if C = 2, then p G = G(G-1) /n(n-1) and P G k C = 2 /G; finally, if C = n, then p G = 1 and P G k C = 1.The next theorem is our main convergence result for general unbiased compression operators.Theorem 4.1. Let Assumptions 2.3, 2.5, 2.6 hold, λ k+1 = 2L x k+1 -x k , and C ≥ max{1, δ real n /δ}. Assume that 0 < γ ≤ 1 /L(1+ √ A), where constant A is defined asEQUATION)Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyEQUATIONwhereD = 2δP G k C 1-δ 6cG C + p + D, where D = 0 when C = n, D = P G k C G(1-δ) C when C = n, and x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .If, in addition, Assumption 2.7 holds and 0 < γ ≤ 1 /L(1+ √ 2A), then for all K ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) with ρ = min γµ, p 8 satisfyEQUATIONwhereΦ 0 = f x 0 -f * + 4γ p g 0 -∇f x 0 2 .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 O( 1 /K) rate, which is optimal (Arjevani et al., 2023) , and for PŁ-functions we derive linear convergence result to the neighborhood depending on the heterogeneity. The size of this neighborhood matches the one derived for 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-MARINA-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 2 . 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 2 . Indeed, to make the expected number of clients participating in the communication round equal to O(C), to make the expected number of stochastic oracle calls equal to O(b), and to make the expected number of transmitted components for each worker taking part in the communication round equal O(ζ Q ), parameter p should be chosen as p = min{ C /n, b /m, ζ Q /d}, where the latter term in the minimum often equals to Θ( 1 /(ω+1)) (Gorbunov et al., 2021) . Therefore, in some scenarios, p can be small.Next, in the special case of full participation, we have C = C = n, p G = P G k C = 1, meaning that A = Θ( (1+ω)(1+cδ) /p 2 ) for Byz-VR-MARINA-PP. In contrast, the corresponding constant for Byz-VR-MARINA is of the order Θ( (1+ω) /pn + (1+ω)cδ /p 2 ), which is strictly better than our bound. In this special case, we do not recover the result for 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 a reduced step size compared to Byz-VR-MARINA, even when C = C = n. To achieve a more favorable convergence rate, particularly in scenarios of complete participation, we also establish the results under Assumption 2.4.EQUATION)Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyEQUATIONwhereD = 2δP G k C 1-δ 6cG C + p + D, where D = 0 when C = n, D = P G k C G(1-δ) C when C = n, and x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + γ p g 0 -∇f x 0 2 .If, in addition, Assumption 2.7 holds and 0 < γ ≤ 1 /L(1+ √ 2A), then for all K ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfy with ρ = min γµ, pEQUATIONwhereΦ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 . With Assumption 2.4, vectors {Q( ∆ i (x k+1 , x k ))} i∈G k C can be upper bounded by D Q L x k+1 -x k .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 δ or to 1 -p G 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 D Q . 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.1 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.Nevertheless, in the case of full participation, we have C = C = n, p G = P G k C = P G k C = 1, meaning that A = Θ( (1+ω) /pn + (1+ω)cδ /p 2 )G k C = Prob{i ∈ G k C } = min{1, C /G}, P G k C = Prob{i ∈ G k C } = min{1, C/G} and we have A = Θ( (1+ω) /pC + (1+ω)cδ /p 2 ). Here, the first term in A is n /C worse than the corresponding term for Byz-VR-MARINA. However, the second term in A matches the corresponding term for Byz-VR-MARINA. Moreover, this term is the main one if cδ ≥ p /C, which is typically the case since parameter p is often small (p = min{ C / C, b /m, ζ Q /d}). In such cases, Byz-VR-MARINA-PP has the same rate of convergence as Byz-VR-MARINA while utilizing, on average, just O(C) workers at each step in contrast to Byz-VR-MARINA that uses n workers at each step. That is, in some cases, partial participation is provably beneficial for Byz-VR-MARINA-PP.Byz-VR-MARINA+: simplified version of Byz-VR-MARINA. In Appendix F, we propose a simplified version of Byz-VR-MARINA called Byz-VR-MARINA+ (Algorithm 3). The only difference is related to Line 10 of the method: when c k = 0, Byz-VR-MARINA+ computes just the average of clip λ k+1 Q ∆ i (x k+1 , x k ) i∈S k instead of robust aggregation, while keeps using ARAgg when c k = 1. Of course, when c k = 0 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 (e.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 c k = 0, meaning that with high enough probability the resulting estimator has no additional bias coming from the robust aggregation. We formally analyze Byz-VR-MARINA+ and show that such a modification of the method leads to better theoretical results (especially when C is small). In particular, in the settings of Theorem 4.2, we prove that Byz-VR-MARINA+ exhibits the same O( 1 /K) rate but converges to O( 1 /p) smaller neighborhood when C = n, i.e., the neighborhood term for Byz-VR-MARINA+ is optimal (Karimireddy et al., 2022; Allouah et al., 2024b) . Moreover, our results for Byz-VR-MARINA+ allow larger stepsizes when C is 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 modifications of Byz-VR-MARINA and Byz-VR-MARINA+ without full-batch gradient computations at all (see Algorithms 4 and 5 in Appendix G). That is, these modifications differ from Byz-VR-MARINA and Byz-VR-MARINA+ in Line 8 only: when c k = 1, every good worker i from S k computes and sends to the server b ′ -size mini-batched stochastic gradient estimator ∇f i (x k+1 ) of ∇f i (x k+1 ). Under the additional assumption that the variance of ∇f i (x k+1 ) is uniformly bounded by σ 2 /b ′ , which is a standard assumption for variance-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 cδ+ P G k C G / C 2 σ 2 /b ′ .For further details and complete proofs, we refer to Appendix G.Heuristic extension of Byz-VR-MARINA-PP. In this short remark, we illustrate how the proposed clipping technique can be applied to 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 k+1 = x k -γ • Agg({g k i } i∈[n] ), where {g k i } i∈ [n] are the vectors received from workers at iteration k and Agg is 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:EQUATIONwhere S k ⊆ [n] is a subset of clients participating in round k and {λ k } k≥0 is sequence of clipping parameters specified by the server. In particular, Byz-VR-MARINA-PP can be seen as an application of scheme (10) to Byz-VR-MARINA (up to a minor modification when c k = 1 in Byz-VR-MARINA) with λ k+1 = λ∥x k+1 -x k ∥. We suggest to use λ k+1 = λ∥x k+1 -x k ∥ with tunable parameter λ > 0 for other methods as well. 
numerical experiments: 
 Firstly, we showcase the benefits of employing clipping to remedy the presence of Byzantine workers and partial participation. For this task, we consider the standard logistic regression model with ℓ 2 -regularization, i.e., f i,j (x) = -y i,j log(h(x, a i,j )) -(1 -y i,j ) log(1 -h(x, a i,j )) + η∥x∥ 2 , where y i,j ∈ {0, 1} is the label, a i,j ∈ R d represents the feature vector, η is the regularization parameter, and h(x, a) = 1 /(1+e -a ⊤ x ). This objective is smooth, and for η > 0, it is also strongly convex, satisfying the PŁ-condition. We consider the a9a LIBSVM dataset (Chang and Lin, 2011) and set η = 0.01. In the experiments, we focus on an important feature of Byz-VR-MARINA-PP: it 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-wise median with bucketing as the aggregator (see also Appendix C). For the attack, we propose a new attack that we refer to 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 0 -x k . Otherwise, they follow protocol and act as benign workers. Further experimental details are deferred to Appendix H. We compare our Byz-VR-MARINA-PP with its version without clipping. We note that the setup that we consider is the most favorable in terms of minimized variance in 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, Byz-VR-MARINA-PP is able to converge linearly to the exact solution, complementing our theoretical results.Figure 1 showcases these observations. On the left, we can see Byz-VR-MARINA-PP 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-PP leads to faster convergence even though we need to employ clipping. Finally, in the right plot, we measure the sensitivity of clipping multiplier λ. We can see that Byz-VR-MARINA-PP is not very sensitive to λ in terms of convergence, i.e., for all the values of λ, we 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 SGD (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 et 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 , we can see that clipping does not lead to performance degradation. On the contrary, 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. 
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 ω, m, and C. Next, it would be interesting to rigorously prove that our heuristic works for SGD with client momentum (Karimireddy et al., 2021 (Karimireddy et al., , 2022) ) and other Byzantine-robust methods.Finally, studying other participation patterns (non-uniform sampling/arbitrary client participation) is also a very prominent direction for future research.Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. (2017) . (arXiv preprint arXiv:1905 .11881, 2019) . (Cited on page 20) Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. (2020b)  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 a Quadro RTX 6000 NVIDIA GPU.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: we do not train new models Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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: we provide citations when necessary Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Further Comparison with Data and Diggavi (2021) . As we mention in the main text, Data and Diggavi (2021) assume that 3B is smaller than C. More precisely, Data and Diggavi (2021) assume that B ≤ ϵC, where ϵ ≤ 1 3 -ϵ ′ for some parameter ϵ ′ > 0 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 ≥ 4B, then existing methods such as Byz-VR-MARINA (Gorbunov et al., 2023) or Client Momentum (Karimireddy et al., 2021 (Karimireddy et al., , 2022) ) can be applied without any changes to get a provable convergence.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 only and the bounds itself hold with probability at least 1-K H exp -ϵ ′2 (1-ϵ)C 16, 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 ϵ is close to 1 3 , e.g., for K = 10 6 , ϵ = ϵ ′ = 1 6 , 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.Finally, the bounds from Data and Diggavi (2021) have non-reduceable terms even for homogeneous data case: these terms are proportional to σ 2 b , where σ 2 is the upper bound for the variance of the stochastic estimator on 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 et 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 et 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 metrics (Rodríguez-Barroso et al., 2020; Regatti et al., 2020; Xu and Lyu, 2020) to achieve some robustness, see also a recent survey by Lyu et al. (2020) .Variance reduction. The literature on variance-reduced methods is very rich (Gower et al., 2020) . 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, we use GeomSARAH/PAGE-type variance reduction as the main building block of the method that makes the method robust to Byzantine attacks.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 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-MARINA-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 on communication compression can 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 are 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 in 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 et 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 on aggregation rules based on the norms of the updates (Ghosh et al., 2020 (Ghosh et al., , 2021)) , SignSGD and majority vote (Bernstein et al., 2019) , SAGA-type variance reduction coupled with unbiased compression (Zhu and Ling, 2021), and GeomSARAH/PAGE-type 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 a 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-probability) 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 Byzantine-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 to 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-robust learning. Indeed, the asynchronous methods like Asynchronous SGD (Agarwal and Duchi, 2011; 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 a 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 is restrictive for many FL applications when the data on clients is private and is not available on the server. Yang and LiFor all a, b ∈ R d and α > 0, p ∈ (0, 1] the following relations hold:EQUATIONEQUATION) Lemma B.1. (Lemma 5 from (Richtárik et al., 2021)). Let a, b > 0. If 0 ≤ γ ≤ 1 √ a+b , then aγ 2 + bγ ≤ 1. The bound is tight up to the factor of 2 since 1 √ a+b ≤ min 1 √ a , 1 b ≤ 2 √ a+b .Algorithm 2 Bucketing Algorithm (Karimireddy et al., 2022) 1: Input: {x 1 , . . . , x n }, s ∈ N -bucket size, Aggr -aggregation rule 2: Sample random permutation π = (π(1), . . . , π(n)) of [n] 3: Compute y i = 1 s min{si,n} k=s(i-1)+1 x π(k) for i = 1, . . . , ⌈ n /s⌉ 4: Return: x = Aggr(y 1 , . . . , y ⌈ n /s⌉ ) Krum and Krum • Bucketing. Krum aggregation rule is defined as Krum(x 1 , . . . , x n ) = argmin xi∈{x1,...,xn} j∈Si ∥x j -x i ∥ 2 , where S i ⊂ {x 1 , . . . , x n } is the subset of n -B -2 closest vectors to x i . By definition, Krum(x 1 , . . . , x n ) ∈ {x 1 , . . . , x n } and, thus ∥Krum(x 1 , . . . , x n )∥ ≤ max i∈[n] ∥x i ∥, i.e.,i ∥ ≤ 1 s min{si,n} k=s(i-1)+1 ∥x π(k) ∥ ≤ max i∈[n] ∥x i ∥, we have that ∥Krum • Bucketing(x 1 , . . . , x n )∥ ≤ max i∈[n] ∥x i ∥.Geometric median (GM) and GM • Bucketing. Geometric median is defined as follows:EQUATION) One can show that GM(x 1 , . . . , x n ) ∈ Conv(x 1 , . . . , x n ) := {x ∈ R d | x = n i=1 α i x i for some α 1 , . . . , α n ≥ 1 such that n i=1 α i = 1}, i.e., geometric median belongs to the convex hull of the inputs. Indeed, let GM(x 1 , . . . , x n ) = x = x + x, where x is the projection of x on Conv(x 1 , . . . , x n ) and x = x -x. Then, the optimality condition implies that ⟨x -x, y -x⟩ ≥ 0 for all y ∈ Conv(x 1 , . . . , x n ). In particular, for all i ∈[n] we have ⟨x -x, x i -x⟩ ≥ 0. Since ⟨x -x, x i -x⟩ = ⟨x, x -x i ⟩ = 1 2 ∥x + x -x i ∥ 2 - 1 2 ∥x∥ 2 - 1 2 ∥x -x i ∥ 2 = 1 2 ∥x -x i ∥ 2 - 1 2 ∥x∥ 2 - 1 2 ∥x -x i ∥ 2 ≤ 1 2 ∥x -x i ∥ 2 - 1 2 ∥x -x i ∥ 2 ,we get that ∥x -x i ∥ ≥ ∥x -x i ∥ for all i ∈ [n] and the equality holds if and only if x = 0. Therefore, argmin from ( 16) is achieved for x such that x = x, meaning that GM(x 1 , . . . , x n ) ∈ Conv(x 1 , . . . , x n ). Therefore, there exist some coefficients α 1 , . . . , α n ≥ 0 such thatn i=1 α i = 1 and GM(x 1 , . . . , x n ) = n i=1 α i x i , implying that ∥GM(x 1 , . . . , x n )∥ ≤ n i=1 α i ∥x i ∥ ≤ max i∈[n] ∥x i ∥.That is, GM satisfies Assumption 2.3 with F A = 1. Similarly to the case of Krum • Bucketing, we also have ∥GM• Bucketing(x 1 , . . . , x n )∥ ≤ max i∈[n] ∥x i ∥.Coordinate-wise median (CM) and CM • Bucketing. Coordinate-wise median (CM) is formally defined asEQUATIONwhere ∥ • ∥ 1 denotes ℓ 1 -norm. This is equivalent to geometric median/median applied to vectors x 1 , . . . , x n component-wise. Therefore, from the above derivations for GM we have∥CM(x 1 , . . . , x n )∥ ∞ ≤ max i∈[n] ∥x i ∥ ∞ , ∥CM • Bucketing(x 1 , . . . , x n )∥ ∞ ≤ max i∈[n] ∥x i ∥ ∞ ,where ∥ • ∥ ∞ denotes ℓ ∞ -norm. Therefore, due to the standard relations between ℓ 2 -and ℓ ∞ -norms, i.e., ∥a∥ ∞ ≤ ∥a∥ ≤ √ d∥a∥ ∞ for any a ∈ R d , we have∥CM(x 1 , . . . , x n )∥ ≤ √ d max i∈[n] ∥x i ∥, ∥CM • Bucketing(x 1 , . . . , x n )∥ ≤ √ d max i∈[n] ∥x i ∥,i.e., Assumption 2.3 is satisfied withF A = √ d.For simplicity, in the main part of our paper, we present simplified versions of our main results. However, our analysis works under more general assumptions presented in this section.Assumption on C. In all the results of this paper, we assume that n ≥ C ≥ max{1, δrealn /δ}. This condition ensures that the robust aggregation makes sense when c k = 1, i.e., at least 1 -δ proportion of sampled workers are not Byzantine ones when c k = 1.Refined smoothness. The following assumption is classical for the literature on non-convex optimization.Assumption D.1 (L-smoothness). We assume that function f : R d → R is L-smooth, i.e., for all x, y ∈ R d we have ∥∇f (x) -∇f (y)∥ ≤ L∥x -y∥.(18) Moreover, we assume that f is uniformly lower bounded by f * ∈ R, i.e., f * := inf x∈R d f (x). In addition, we assume thatEQUATION)We notice here that (19) implies L-smoothness of f with L ≤ 1 G i∈G L i , i.e., smoothness constant of f can be better than the averaged smoothness constant of the local loss functions on the regular clients.Following Gorbunov et al. (2023) , we consider refined assumptions on the smoothness. Assumption D.2 (Global Hessian variance assumption (Szlendak et al., 2022) ). We assume that there existsEQUATION)We notice that ( 19) implies (20) with L ± ≤ max i∈G L i . Szlendak et al. (2022) prove that L ± satisfies the following relation:L 2 avg -L 2 ≤ L 2 ± ≤ L 2 avg , where L 2 avg := 1 G i∈G L 2 i .In particular, it is possible that L ± = 0 even if the data on the good workers is heterogeneous. Assumption D.3 (Local Hessian variance assumption (Gorbunov et al., 2023) ). We assume that there existsEQUATIONwhere ∆ i (x, y) := ∇f i (x) -∇f i (y) and ∆ i (x, y) is an unbiased mini-batched estimator of ∆ i (x, y) with batch size b.This assumption incorporates considerations for the smoothness characteristics inherent in all functions {f i,j } i∈G,j∈[m] , the sampling policy, and the similarity among the functions {f i,j } i∈G,j∈[m] . Gorbunov et al. (2023) have demonstrated that, assuming smoothness of {f i,j } i∈G,j∈[m] , Assumption 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 {f i,j } i∈G,j∈[m] explicitly. Assumption D.4 (Smoothness of f i,j (optional)). We assume that for all i ∈ G and j ∈ [m] there exists L i,j ≥ 0 such that f i,j is L i,j -smooth, i.e., for all x, y ∈ REQUATION)Refined heterogeneity. Instead of Assumption 2.5, we consider a more generalized one. Assumption D.5 ((B, ζ 2 )-heterogeneity). We assume that good clients have B, ζ 2 -heterogeneous local loss functions for someB ≥ 0, ζ ≥ 0, i.e., 1 G i∈G ∥∇f i (x) -∇f (x)∥ 2 ≤ B∥∇f (x)∥ 2 + ζ 2 ∀x ∈ R dWhen B = 0, the above assumption recovers Assumption 2.5. However, it also covers some situations when the model is over-parameterized (Vaswani et al., 2019) and can hold with smaller values of ζ 2 . This assumption is also used in (Karimireddy et al., 2022; Gorbunov et al., 2023) .Lemma D.6. Let X be a random vector in R d and X= clip λ (X). Assume that E[X] = x ∈ R d and ∥x∥ ≤ λ/2, then E ∥ X -x∥ 2 ≤ 10E ∥X -x∥ 2 .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:χ = I {X:∥X∥>λ} = 1, if ∥X∥ > λ, 0, otherwise , η = I {X:∥X-x∥> λ 2 } = 1, if ∥X -x∥ > λ 2 0, otherwise . Moreover, since ∥X∥ ≤ ∥x∥ + ∥X -x∥ ∥x∥≤λ/2 ≤ λ 2 + ∥X -x∥, we have χ ≤ η.Using that we getX = min 1, λ ∥X∥ X = χ λ ∥X∥ X + (1 -χ)X.By Markov's inequality,E[η] = P ∥X -x∥ > λ 2 = P ∥X -x∥ 2 > λ 2 4 ≤ 4 λ 2 E ∥X -x∥ 2 . (23) Using ∥ X -x∥ ≤ ∥ X∥ + ∥x∥ ≤ λ + λ 2 = 3λ 2 , we obtain E ∥ X -x∥ 2 = E ∥ X -x∥ 2 χ + ∥ X -x∥ 2 (1 -χ) = E χ λ ∥X∥ X -x 2 + ∥X -x∥ 2 (1 -χ) ≤ E χ λ ∥X∥ X + ∥x∥ 2 + ∥X -x∥ 2 (1 -χ) ∥x∥≤ λ 2 ≤ E χ 3λ 2 2 + ∥X -x∥ 2 ,where in the last inequality we applied 1 -χ ≤ 1. Using ( 23) and χ ≤ η we getE ∥ X -x∥ 2 ≤ 9λ 2 4 2 λ 2 E ∥X -x∥ 2 + E ∥X -x∥ 2 ≤ 10E ∥X -x∥ 2 .Lemma D.7 (Lemma 2 from Li et al. ( 2021)). Assume that function f is L-smooth (Assumption D.1) andx k+1 = x k -γg k . Then f x k+1 ≤ f x k - γ 2 ∇f x k 2 - 1 2γ - L 2 x k+1 -x k 2 + γ 2 g k -∇f x k 2 .Lemma D.8. Let Assumptions D.1, D.2, D.3 hold and the Compression Operator satisfy Definition 2.2. Let us define "ideal" estimator:g k+1 =            1 G k C i∈G k C ∇f i (x k+1 ), c n = 1, [1] g k + ∇f x k+1 -∇f x k , c n = 0 and G k C < (1 -δ)C, [2] g k + 1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k , c n = 0 and G k C ≥ (1 -δ)C. [3]Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyA 1 = E g k+1 -∇f x k+1 2 ≤ (1 -p) 1 + p 4 E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + (1 -p)p G 1 + 4 p 2 • P G k C n C 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 ,wherep G = Prob G k C ≥ (1 -δ)C and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C .Proof. Let us examine the expected value of the squared difference between ideal estimator and full gradient:A 1 = E g k+1 -∇f x k+1 2 = E E k g k+1 -∇f x k+1 2 = (1 -p) p G E   Ek    g k + 1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -∇f x k+1 2    | [3]    + (1 -p)(1 -p G )E E k g k -∇f (x k ) 2 | [2] + pE    1 G k C i∈G k C ∇f i (x k+1 ) -∇f (x k+1 ) 2    .Using ( 12) and ∇f x k -∇f x k = 0 we obtainB 1 = E   Ek    g k + 1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -∇f x k+1 2    | [3]    = E   Ek    g k + 1 G k C i∈G k C clip λ Q ∆i x k+1 , x k -∇f x k+1 + ∇f x k -∇f x k 2    | [3]    (12) ≤ 1 + p 4 E g k -∇f x k 2 + 1 + 4 p E   Ek    1 G k C i∈G k C clip λ Q ∆i x k+1 , x k -∇f (x k+1 ) -∇f (x k ) 2    | [3]    = 1 + p 4 E g k -∇f (x k ) 2 + 1 + 4 p E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -∆ x k+1 , x k 2    | [3]    .Let us consider the last part of the inequality:EQUATIONwhereI G k C is an indicator function for the event i ∈ G k C | G k C ≥ (1 -δ) C and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C is probability of such event. Note that E S k I G k C = P G k C . In case of uniform sampling of clients we have ∀i ∈ G P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C = C np G • (1-δ)C≤t≤C G t n -G C -t n C -1 , p G = (1-δ)C≤t≤C G -1 t -1 n -G C -t n -1 C -1 -1Now we can continue with inequalities:EQUATION≤P G k C C(1 -δ) E i∈G 2E k EQ clip λ Q ∆i x k+1 , x k -∆i x k+1 , x k 2 | [3] + P G k C C(1 -δ) E i∈G 2E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Using Lemma D.6 we haveB ′ 1 Lemma D.6 ≤ P G k C C(1 -δ) E i∈G 20E k EQ Q ∆i x k+1 , x k -∆i x k+1 , x k 2 | [3] + P G k C C(1 -δ) E i∈G 2E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] ≤ 20 • P G k C C(1 -δ) E i∈G E k E Q Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 2 • P G k C C(1 -δ) E i∈G E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] ≤ 20 • P G k C C(1 -δ) E i∈G E k EQ Q ∆i x k+1 , x k 2 - i∈G ∆i x k+1 , x k 2 | [3] + 2 • P G k C C(1 -δ) E i∈G E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Applying Definition 2.2 of Unbiased Compressor we haveB ′ 1 ≤ 20 • P G k C C(1 -δ) E i∈G (1 + ω)E k ∆ i x k+1 , x k 2 - i∈G ∆ i x k+1 , x k 2 | [3] + 2 • P G k C C(1 -δ) E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] ≤ 20 • P G k C C(1 -δ) E i∈G (1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 + 20 • P G k C C(1 -δ) E i∈G (1 + ω)E k ∆ i x k+1 , x k 2 - i∈G E k ∆ i x k+1 , x k 2 | [3] + 2 • P G k C C(1 -δ) E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .B ′ 1 ≤ 20 • P G k C C(1 -δ) (1 + ω)E i∈G E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 20 • P G k C C(1 -δ) ωE i∈G ∆ i x k+1 , x k 2 | [3] + 2 • P G k C C(1 -δ) E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] = 20 • P G k C C(1 -δ) (1 + ω)E i∈G E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 20 • P G k C C(1 -δ) ωE i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 + ∥∆ x k+1 , x k ∥ 2 | [3] + 2 • P G k C C(1 -δ) E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Rearranging terms leads toB ′ 1 ≤ 20 • P G k C C(1 -δ) (1 + ω)E i∈G E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 2 • P G k C C(1 -δ) (10ω + 1)E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] + 20 • P G k C C(1 -δ) ωE i∈G ∆ x k+1 , x k 2 | [3] .Now we apply Assumptions D.1, D.2, D.3:B ′ 1 ≤ 20 • P G k C C(1 -δ) (1 + ω)E G L 2 ± b ∥x k+1 -x k ∥ 2 + 2 • P G k C C(1 -δ) (10ω + 1)E GL 2 ± ∥x k+1 -x k ∥ 2 + 20 • P G k C C(1 -δ) ωE GL 2 x k+1 -x k 2 .Finally, we haveB ′ 1 ≤ 2 • P G k C • G C(1 -δ) 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 .Let us plug obtained results:B 1 ≤ 1 + p 4 E g k -∇f (x k ) 2 + 1 + 4 p 2 • P G k C • G C(1 -δ) 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 .Let us consider the termEQUATIONAlso, we haveA 1 = E g k+1 -∇f (x k+1 ) 2 ≤ (1 -p)p G B 1 + (1 -p)(1 -p G )E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 ≤ (1 -p)p G 1 + p 4 E g k -∇f (x k ) 2 + (1 -p)p G 1 + 4 p 2 • P G k C • G C(1 -δ) 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + (1 -p)(1 -p G )E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 .To simplify the bound we use 1 + p 4 > 1 and obtainA 1 ≤ (1 -p)p G 1 + p 4 E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + (1 -p)p G 1 + 4 p 2 • P G k C • G C(1 -δ) 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + (1 -p)(1 -p G )E g k -∇f (x k ) 2 ≤ (1 -p)p G 1 + p 4 E g k -∇f (x k ) 2 + (1 -p)p G 1 + 4 p 2 • P G k C • G C(1 -δ) 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + (1 -p)(1 -p G ) 1 + p 4 E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 ≤ (1 -p) 1 + p 4 E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + (1 -p)p G 1 + 4 p 2 • P G k C n C 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 .Lemma D.9. Let us define "ideal" estimator:g k+1 =            1 G k C i∈G k C ∇f i (x k+1 ), c n = 1, [1] g k + ∇f x k+1 -∇f x k , c n = 0 and G k C < (1 -δ)C, [2] g k + 1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k , c n = 0 and G k C ≥ (1 -δ)C. [3]Also let us introduce the notationARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyA 2 = E g k+1 -g k+1 2 ≤ pE E k ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | [1] + (1 -p)p G E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       + (1 -p)(1 -p G )E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2] ,wherep G = Prob G k C ≥ (1 -δ)C .Proof. Using conditional expectations we haveA 2 = E E k g k+1 -g k+1 2 = pE E k ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | [1] +(1 -p)pGE   E k   g k + 1 G k C i∈G k C clip λ Q ∆i x k+1 , x k -g k + ARAgg k+1 Q 2   | [3]   + (1 -p)(1 -p G )E E k g k + ∇f (x k+1 ) -∇f (x k ) -g k + ARAgg k+1 Q 2 | [2] .After simplification, we get the following bound:A 2 ≤ pE E k ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | [1] + (1 -p)p G E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       + (1 -p)(1 -p G )E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2] .Lemma D.10. Let Assumptions D.1 and D.5 hold and Aggregation Operator (ARAgg) satisfy Definition 2.1. Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyT 1 = E E k ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | [1] ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδζ 2 (1 -δ) C + ζ 2 ,where B := 0 and ζ 2 := 0 when C = n, and B :=P G k C GB (1-δ) C and ζ 2 := P G k C Gζ 2 (1-δ) C when C < n.Proof. Using the definition of aggregation operator, we haveT 1 = E E k ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | [1] (12) ≤ E   Ek    ARAgg {g k+1 i } i∈S k - 1 G k C i∈G k C ∇f i (x k+1 ) 2    | [1]    + E   Ek    1 G k C i∈G k C ∇f i (x k+1 ) -∇f (x k+1 ) 2    | [1]    . Since 1 G k C i∈G k C ∇f i (x k+1 ) = ∇f (x k+1) with probability 1 when C = n, we can estimate the last term asE   Ek    1 G k C i∈G k C ∇f i (x k+1 ) -∇f (x k+1 ) 2    | [1]    ≤        0, if C = n E   1 G k C i∈G k C E k ∇f i (x k+1 ) -∇f (x k+1 ) 2 | [1]   , if C < n ≤    0, if C = n P G k C (1-δ) C i∈G E ∇f i (x k+1 ) -∇f (x k+1 ) 2 , if C < n (As. D.5) ≤    0, if C = n P G k C G (1-δ) C BE ∥∇f (x k+1 )∥ 2 + ζ 2 , if C < n = BE ∥∇f (x k+1 )∥ 2 + ζ 2 ,whereB :=    0, if C = n, P G k C GB (1-δ) C , if C < n,andζ 2 :=    0, if C = n, P G k C Gζ 2 (1-δ) C , if C < n.Using the above bound, we continue the estimation of T 1 as follows:T 1 (Def. 2.1) ≤ E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E k ∇f i x k+1 -∇f l x k+1 2 | [1]      + BE ∥∇f (x k+1 )∥ 2 + ζ 2 (12) ≤ E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E 2 ∇f i x k+1 -∇f x k+1 2 | [1]      + E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E 2 ∇f l x k+1 -∇f x k+1 2 | [1]      + BE ∥∇f (x k+1 )∥ 2 + ζ 2 = E    cδ G k C i∈G k C 4E k ∇f i x k+1 -∇f x k+1 2 | [1]    + BE ∥∇f (x k+1 )∥ + ζ 2 ≤ P G k C cδ (1 -δ) C i∈G 4E k ∇f i x k+1 -∇f x k+1 2 + BE ∥∇f (x k+1 )∥ 2 + ζ (As. D.5) ≤ 4GP G k C cδB (1 -δ) C + B E ∇f x k+1 2 + 4GP G k C cδζ 2 (1 -δ) C + ζ 2 (12) ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + ∇f x k+1 -∇f x k 2 + 4GP G k C cδζ 2 (1 -δ) C + ζ 2 ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδζ (1 -δ) C + ζ 2 ,which concludes the proof.Lemma D.11. Let Assumptions D.1, D.2, D.3 hold and the Compression Operator satisfy Definition 2.2. Also let us introduce the notationARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyT 2 = E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       ≤ 8GP G k C (1 -δ)C 10(1 + ω) L 2 ± b + (10ω + 1)L 2 ± + 10ωL 2 cδE ∥x k+1 -x k ∥ ,whereP G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C .Proof. By the definition of robust aggregation, we haveT 2 = E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       ≤ E      cδ D2 i,l∈G k C i̸ =l E k clip λ Q ∆i x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3]     ,where D 2 = G k C (G k C -1). Next, we consider pair-wise differences:T ′ 2 (i, l) = E k clip λ Q ∆ i x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3] (12) ≤ 2E k clip λ Q ∆ i x k+1 , x k -∆ i x k+1 , x k + ∆ l x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3] + 2E k ∆ i x k+1 , x k -∆ l x k+1 , x k 2 | [3] (12) ≤ 4E k clip λ Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 4E k ∆ l x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3] + 2E k ∆ l x k+1 , x k -∆ i x k+1 , x k 2 | [3] ] (12) ≤ 4E k clip λ Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 4E k ∆ l x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3] + 4E k ∆ l x k+1 , x k -∆ x k+1 , x k 2 | [3] + 4E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Now we can combine all parts together:T 2 = E     1 G k C (G k C -1) i,l∈G k C i̸ =l T ′ 2 (i, l)     ≤ E     1 D 2 i,l∈G k C i̸ =l 4E k clip λ Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 4E k ∆ l x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 4E k ∆ l x k+1 , x k -∆ x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 4E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]     .Rearranging the terms, we obtainT 2 ≤ E     1 D 2 i,l∈G k C i̸ =l 8E k clip λ Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]     .It leads toT 2 ≤ E   1 G k C i∈G k C 8E k clip λ Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   Lemma D.6 ≤ E   1 G k C i∈G k C 80E k Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Using variance decomposition we getT 2 ≤ E   1 G k C i∈G k C 80E k Q ∆ i x k+1 , x k 2 | [3]   -E   1 G k C i∈G k C 80E k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Using properties of unbiased compressors (Definition 2.2) we haveT 2 ≤ E   1 G k C i∈G k C 80(1 + ω)E k ∆ i x k+1 , x k 2 | [3]   -E   1 G k C i∈G k C 80E k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Also we haveT 2 ≤ E   1 G k C i∈G k C 80(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 80(1 + ω)E k ∆ i x k+1 , x k 2 | [3]   -E   1 G k C i∈G k C 80E k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Let us simplify the inequality:T 2 ≤ E   1 G k C i∈G k C 80(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 80ωE k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Using a variance decomposition once again, we getT 2 ≤ E   1 G k C i∈G k C 80(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 80ωE k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 80ωE k ∆ x k+1 , x k 2 | [3]   .Using a similar argument to the one used in the previous lemma, we obtainT 2 ≤ E P G k C (1 -δ)C i∈G 80(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + E P G k C (1 -δ)C i∈G 80ωE k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] + E P G k C (1 -δ)C i∈G 8E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] + E P G k C (1 -δ)C i∈G 80ωE k ∆ x k+1 , x k 2 | [3] .Using Assumptions D.1, D.2, D.3:T 2 ≤ E 80(1 + ω)GP G k C L 2 ± (1 -δ)Cb ∥x k+1 -x k ∥ 2 + E 8(10ω + 1)GP G k C L 2 ± (1 -δ)C ∥x k+1 -x k ∥ 2 + E 80GP G k C ωL 2 (1 -δ)C ∥x k+1 -x k ∥ 2 .Finally, we obtainT 2 = E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       ≤ 8GP G k C (1 -δ)C 10(1 + ω) L 2 ± b + (10ω + 1)L 2 ± + 10ωL 2 cδE ∥x k+1 -x k ∥ 2 .Lemma D.12. Let Assumptions 2.3 and D.1 hold. Also let us introduce the notationARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Assume that λ k+1 = α λ k+1 ∥x k+1 -x k ∥. Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyT 3 = E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2] ≤ 2(L 2 + F 2 A α 2 λ k+1 )E x k+1 -x k 2Proof.T 3 = E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2] (12) ≤ E E k 2 ∇f (x k+1 ) -∇f (x k ) 2 + 2 ARAgg k+1 Q 2 | [2]Using L-smoothness and Assumption 2.3 we have T 3 (12) ≤ E E k 2L 2 x k+1 -x k 2 + 2F 2 A λ 2 k+1 | [2] ≤ E E k 2L 2 x k+1 -x k 2 + 2F 2 A α 2 λ k+1 ∥x k+1 -x k ∥ 2 | [2] ≤ 2(L 2 + F 2 A α 2 λ k+1 )E x k+1 -x k 2 . Lemma D.ARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyE g k+1 -∇f x k+1 2 ≤ 1 - p 4 E g k -∇f x k 2 + BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 ,whereA = 4 p 80 p p G P G k C n C ω + 24 GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 160 p p G GP G k C (1 -δ)C cδω L 2 + 4 p 8 p p G P G k C n C (10ω + 1) + 16 p p G GP G k C (1 -δ)C cδ(10ω + 1) L 2 ± + 4 p 160 p p G GP G k C (1 -δ)C (1 + ω)cδ + 80 p p G P G k C (1 + ω) n C L 2 ± b + 4 p 4 p (1 -p G )F 2 A α 2 λ k+1 , B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,and where B := 0 and D := 0 when C = n, and B :=P G k C GB (1-δ) C and D := P G k C G (1-δ) C when C < n, p G = Prob G k C ≥ (1 -δ)C , and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C .Proof. Let us combine bounds for A 1 and A 2 together:A 0 = E g k+1 -∇f x k+1 2 ≤ 1 + p 2 E g k+1 -∇f x k+1 2 + 1 + 2 p E g k+1 -g k+1 2 ≤ 1 + p 2 A 1 + 1 + 2 p A 2 ≤ 1 + p 2 (1 -p) 1 + p 4 E g k -∇f x k 2 + 1 + p 2 (1 -p)p G 1 + 4 p 2 • P G k C n C 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + 1 + p 2 p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + 1 + 2 p pE E k ARAgg ∇f 1 (x k+1 ), . . . , ∇f C (x k+1 ) -∇f (x k+1 ) 2 | [1] + 1 + 2 p (1 -p)pGE   E k   1 G k C i∈G k C clip λ Q ∆i x k+1 , x k -ARAgg k+1 Q 2 | [3]     + 1 + 2 p (1 -p)(1 -p G )E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2] .Finally, we obtain the following bound:A 0 (12) ≤ 1 - p 4 E g k -∇f x k 2 + 8 p P G k C n C p G 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + 2p δ • P G k C 1 -δ E B∥∇f (x)∥ 2 + ζ 2 + (p + 2) E E k ARAgg ∇f 1 (x k+1 ), . . . , ∇f n (x k+1 ) -∇f (x k+1 ) 2 | [1] + 2 p p G E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       + 2 p (1 -p G )E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2]Now, we can apply Lemmas D.10, D.11, D.12:A 0 = E g k+1 -∇f x k+1 2 ≤ 1 - p 4 E g k -∇f x k 2 + 8 p P G k C n C p G 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + (p + 2) 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4 (p + 2) GP G k C cδ (1 -δ) C ζ 2 + (p + 2) ζ 2 + 2 p p G E 80(1 + ω) GP G k C (1 -δ)C L 2 ± b cδ∥x k+1 -x k ∥ 2 + 2 p p G E 8(10ω + 1) GP G k C (1 -δ)C L 2 ± cδ∥x k+1 -x k ∥ 2 + 2 p p G E 80 GP G k C (1 -δ)C ωL 2 cδ∥x k+1 -x k ∥ 2 + 2 p (1 -p G )2(L 2 + F 2 A α 2 λ k+1 )E x k+1 -x k 2 + 2p δP G k C 1 -δ E B∥∇f (x)∥ 2 + ζ 2 .Finally, we haveE g k+1 -∇f x k+1 2 ≤ 1 - p 4 E g k -∇f x k 2 + BE ∇f x k 2 + Dζ 2 + pA 4 E ∥x k+1 -x k ∥ 2 ,whereA = 32pG p 2 P G k C n C 10ωL 2 + (10ω + 1)L 2 ± + 10(ω + 1)L 2 ± b + 8 p 2 GP G k C (1 -δ)C pGcδ 80(1 + ω) L 2 ± b + 8(10ω + 1)L 2 ± + 80ωL 2 + 4 p 24GP G k C cδB (1 -δ) C + 6 B L 2 + 16(1 -pG) p 2 (L 2 + F 2 A α 2 λ k+1 ),andB = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,where D := 0 when C = n, and D :=P G k C G (1-δ) C when C < n.Once we simplify the equation, we obtainA = 4 p 80 p p G P G k C n C ω + 24 GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 160 p p G GP G k C (1 -δ)C cδω L 2 + 4 p 8 p p G P G k C n C (10ω + 1) + 16 p p G GP G k C (1 -δ)C cδ(10ω + 1) L 2 ± + 4 p 160 p p G GP G k C (1 -δ)C (1 + ω)cδ + 80 p p G P G k C (1 + ω) n C L 2 ± b + 4 p 4 p (1 -p G )F 2 A α 2 λ k+1 .Theorem D.14. Let Assumptions 2.3, D.1, D.2, D.3, D.5 hold.Settingλ k+1 = 2 max i∈G L i x k+1 -x k . Assume that 0 < γ ≤ 1 L + √ A , 4 B < p,whereA = 4 p 80 p p G P G k C n C ω + 24 GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 160 p p G GP G k C (1 -δ)C cδω L 2 + 4 p 8 p p G P G k C n C (10ω + 1) + 16 p p G GP G k C (1 -δ)C cδ(10ω + 1) L 2 ± + 4 p 160 p p G GP G k C (1 -δ)C (1 + ω)cδ + 80 p p G P G k C (1 + ω) n C L 2 ± b + 4 p 4 p (1 -p G )F 2 A α 2 λ k+1 , B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,and where B := 0 and D := 0 when C = n, and B :=P G k C GB(1-δ) C and D :=P G k C G(1-δ) C when C < n, andP G k C = C np G • (1-δ)C≤t≤C G -1 t -1 n -G C -t n C -1 , p G = Prob G k C ≥ (1 -δ) C = ⌈(1-δ)C⌉≤t≤C G t n -G C -t n -1 C -1 -1.Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA (Algorithm 1) satisfyE ∇f x K 2 ≤ 2Φ 0 γ 1 -4 B p (K + 1) + 4 Dζ 2 p -4 B ,where x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .Proof of Theorem D.14. For all k ≥ 0 we introduceΦ k = f x k -f * + 2γ p g k -∇f x k 2 .Using the results of Lemmas D.13 and D.7, we deriveE Φ k+1 (D.7) ≤ E f x k -f * - 1 2γ - L 2 x k+1 -x k 2 + γ 2 g k -∇f x k 2 - γ 2 E ∇f x k 2 + 2γ p E g k+1 -∇f x k+1 2 (D.13) ≤ E f x k -f * - 1 2γ - L 2 x k+1 -x k 2 + γ 2 g k -∇f x k 2 - γ 2 E ∇f x k 2 + 2γ p 1 - p 4 E g k -∇f x k 2 + 2γ p BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 = E f x k -f * + 2γ p 1 - p 4 + p 4 E g k -∇f x k 2 + 2 Dζ 2 γ p + 1 2γ 1 -Lγ -Aγ 2 E ∥x k+1 -x k ∥ 2 - γ 2 1 - 4 B p E ∇f x k 2 = E Φ k + 2 Dζ 2 γ p + 1 2γ 1 -Lγ -Aγ 2 E ∥x k+1 -x k ∥ 2 - γ 2 1 - 4 B p E ∇f x k 2 .Using choice of stepsize and second condition:0 < γ ≤ 1 L+ √A , 4 B < p and lemma B.1 we haveE Φ k+1 ≤ E Φ k + 2 Dζ 2 γ p - γ 2 1 - 4 B p E ∇f x k 2Next, we have γ 2 1 -4 B p > 0 and Φ k+1 ≥ 0. Therefore, summing up the above inequality for k = 0, 1, . . . , K and rearranging the terms, we get1 K + 1 K k=0 E ∇f x k 2 ≤ 2 γ 1 -4 B p (K + 1) K k=0 E Φ k -E Φ k+1 + 4 Dζ 2 p -4 B = 2 E Φ 0 -E Φ k+1 γ 1 -4 B p (K + 1) + 4 Dζ 2 p -4 B ≤ 2E Φ 0 γ 1 -4 B p (K + 1) + 4 Dζ 2 p -4 B .Theorem D.15. Let Assumptions 2.3, D.1, D.2, D.3, D.5, 2.7 hold.Setλ k+1 = max i∈G L i x k+1 -x k . Assume that 0 < γ ≤ 1 L + √ 2A , 8 B < p where A = 4 p 80 p p G P G k C n C ω + 24 GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 160 p p G GP G k C (1 -δ)C cδω L 2 + 4 p 8 p p G P G k C n C (10ω + 1) + 16 p p G GP G k C (1 -δ)C cδ(10ω + 1) L 2 ± + 4 p 160 p p G GP G k C (1 -δ)C (1 + ω)cδ + 80 p p G P G k C (1 + ω) n C L 2 ± b + 4 p 4 p (1 -p G )F 2 A α 2 λ k+1 , B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,and where B := 0 and D := 0 when C = n, and B :=EQUATIONP G k C = C np G • (1-δ)C≤t≤C G -1 t -1 n -G C -t n C -1 , p G = Prob G k C ≥ (1 -δ) C = ⌈(1-δ)C⌉≤t≤C G t n -G C -t n -1 C -1 -1.Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA (Algorithm 1) satisfyE f x K -f (x * ) ≤ (1 -ρ) K Φ 0 + 4 Dγζ 2 pρ ,where ρ = min γµ 1 -8 B p , p 8 andΦ 0 = f x 0 -f * + 4γ p g 0 -∇f x 0 2 . Proof. For all k ≥ 0 we introduce Φ k = f x k -f * + 4γ p g k -∇f x k 2 .Using the results of Lemmas D.13 and D.7, we deriveE Φ k+1 (D.7) ≤ E f x k -f * - 1 2γ - L 2 x k+1 -x k 2 + γ 2 g k -∇f x k 2 - γ 2 E ∇f x k 2 + 4γ p E g k+1 -∇f x k+1 2 (D.13) ≤ E f x k -f * - 1 2γ - L 2 x k+1 -x k 2 + γ 2 g k -∇f x k 2 - γ 2 E ∇f x k 2 + 4γ p 1 - p 4 E g k -∇f x k 2 + 4γ p BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 = E f x k -f * + 4γ p 1 - p 4 + p 8 E g k -∇f x k 2 + 4 Dζ 2 γ p + 1 2γ 1 -Lγ -2Aγ 2 E ∥x k+1 -x k ∥ 2 - γ 2 1 - 8 B p E ∇f x k 2 .Using Assumption 2.7 we obtainE Φ k+1 ≤ E f x k -f * + 1 - p 8 4γ p E g k -∇f x k 2 + 4 Dζ 2 γ p + 1 2γ 1 -Lγ -2Aγ 2 E ∥x k+1 -x k ∥ 2 -γµ 1 - 8 B p E f x k -f * .Finally, we haveE Φ k+1 ≤ 1 -min γµ 1 - B p , p 8 E Φ k + 4 Dζ 2 γ p .Unrolling the recurrence with ρ = min γµ 1 -8 B p , p 8 , we obtain E Φ k ≤ (1 -ρ) K E Φ 0 + 4 Dζ 2 γ p K-1 k=0 (1 -ρ) k ≤ (1 -ρ) K E Φ 0 + 4 Dζ 2 γ p ∞ k=0 (1 -ρ) k = (1 -ρ) K E Φ 0 + 4 Dγζ 2 pρ Taking into account Φ k ≥ f x k -f (x * ),g k+1 =            1 G k C i∈G k C ∇f i (x k+1 ), c n = 1, [1] g k + ∇f x k+1 -∇f x k , c n = 0 and G k C < (1 -δ)C, [2] g k + 1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k , c n = 0 and G k C ≥ (1 -δ)C. [3]Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyA 1 = E g k+1 -∇f x k+1 2 ≤ (1 -p)E g k -∇f (x k ) 2 + p δP G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + (1 -p)p G P G k C G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 .wherep G = Prob G k C ≥ (1 -δ)C and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C .Proof. Similarly to general analysis, we start from conditional expectations:EQUATION)Using ( 12) and ∇f x k -∇f x k = 0 we obtainB 1 = E   Ek    g k + 1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -∇f x k+1 2    | [3]    = E   Ek    g k + 1 G k C i∈G k C clip λ Q ∆i x k+1 , x k -∇f x k+1 + ∇f x k -∇f x k 2    | [3]   Using λ k+1 = D Q max i,j L i,j ∥x k+1 -x k ∥ we can guarantee that clipping operator becomes identical since we haveQ ∆ i x k+1 , x k ≤ D Q ∆ i x k+1 , x k ≤ D Q 1 b j∈m ∇f i,j (x k+1 ) -∇f i,j (x k ) ≤ D Q 1 b j∈m ∇f i,j (x k+1 ) -∇f i,j (x k ) ≤ D Q max j L i,j x k+1 -x k ≤ D Q max i,j L i,j x k+1 -x k .Therefore, we can continue as followsB 1 = E   Ek    g k + 1 G k C i∈G k C Q ∆ i x k+1 , x k -∇f x k+1 2    | [3]    = E   Ek    g k + 1 G k C i∈G k C Q ∆i x k+1 , x k -∇f x k+1 + ∇f x k -∇f x k 2    | [3]   .Moreover, we can avoid application of Young's inequality and use variance decomposition instead:EQUATION)Let us consider the last part of the inequality. Note that G k C ≥ (1 -δ)C in this case andEQUATIONwhereI G k C is an indicator function for the event i ∈ G k C | G k C ≥ (1 -δ) C and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C is probability of such event. Note that E S k I G k C = P G k C .In the case of uniform sampling of clients, we have∀i ∈ G P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C = C n 1 p G • (1-δ)C≤t≤C G -1 t -1 n -G C -t n -1 C -1 -1. Now, we can continue with inequalities:B ′ 1 ≤ P G k C C 2 (1 -δ) 2 E i∈G E k Q ∆i x k+1 , x k -∆ x k+1 , x k 2 | [3] ≤ P G k C C 2 (1 -δ) 2 E i∈G E k EQ Q ∆i x k+1 , x k -∆ x k+1 , x k 2 | [3] ≤ P G k C C 2 (1 -δ) 2 E i∈G E k EQ Q ∆i x k+1 , x k -∆i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 E i∈G E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Using variance decomposition, we haveB ′ 1 ≤ P G k C C 2 (1 -δ) 2 E i∈G E k EQ Q ∆i x k+1 , x k 2 - i∈G ∆i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 E i∈G E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Applying the definition of unbiased compressor, we getB ′ 1 ≤ P G k C C 2 (1 -δ) 2 E i∈G (1 + ω)E k ∆ i x k+1 , x k 2 - i∈G ∆ i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] ≤ P G k C C 2 (1 -δ) 2 E i∈G (1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 + P G k C C 2 (1 -δ) 2 E i∈G (1 + ω)E k ∆ i x k+1 , x k 2 - i∈G E k ∆ i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Next, we rearrange terms and deriveB ′ 1 ≤ P G k C C 2 (1 -δ) 2 (1 + ω)E i∈G E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 ωE i∈G ∆ i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] = P G k C C 2 (1 -δ) 2 (1 + ω)E i∈G E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 ωE i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 + ∥∆ x k+1 , x k ∥ 2 | [3] + P G k C C 2 (1 -δ) 2 E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Rearranging terms leads toB ′ 1 ≤ P G k C C 2 (1 -δ) 2 (1 + ω)E i∈G E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 (ω + 1)E i∈G ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] + P G k C C 2 (1 -δ) 2 ωE i∈G ∆ x k+1 , x k 2 | [3] .Now we apply Assumptions D.1, D.2, D.3:B ′ 1 ≤ P G k C C 2 (1 -δ) 2 (1 + ω)E G L 2 ± b ∥x k+1 -x k ∥ 2 + P G k C C 2 (1 -δ) 2 (ω + 1)E GL 2 ± ∥x k+1 -x k ∥ 2 + P G k C C 2 (1 -δ) 2 ωE GL 2 x k+1 -x k 2 .Finally, we haveB ′ 1 ≤ P G k C • G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 .Let us plug the obtained results in ( 27): 25)B 1 ≤ E g k -∇f (x k ) 2 + P G k C • G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 . A 1 = E g k+1 -∇f (x k+1 ) 2 (26),(≤ (1 -p)p G B 1 + (1 -p)(1 -p G )E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 ≤ (1 -p)p G E g k -∇f (x k ) 2 + p δ • P G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + (1 -p)pG P G k C • G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + (1 -p)(1 -p G )E g k -∇f (x k ) 2 .Rearranging the terms, we getA 1 ≤ (1 -p)E g k -∇f (x k ) 2 + δP G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + (1 -p)p G P G k C G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 .Lemma E.2. Let Assumptions D.1, D.2, D.3, D.4, 2.4 hold and the compression operator satisfy Definition 2.2. Also, let us introduce the notationARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyT 2 = E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       ≤ 4 GP G k C C(1 -δ) cδ (1 + ω) L 2 ± b + (ω + 1)L 2 ± + ωL 2 E ∥x k+1 -x k ∥ 2 ,whereP G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C .Proof. By definition of the robust aggregation, we haveT 2 = E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       ≤ E      cδ D2 i,l∈G k C i̸ =l E k clip λ Q ∆i x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3]      , where D 2 = G k C (G k C -1).Using λ k+1 = D Q max i,j L i,j ∥x k+1 -x k ∥ we can guarantee that clipping operator becomes identical since we have ∀i ∈ GEQUATION)Let us consider pair-wise differences: ∀i, l ∈ GT ′ 2 (i, l) = E k clip λ Q ∆ i x k+1 , x k -clip λ Q ∆ l x k+1 , x k 2 | [3] = E k Q ∆ i x k+1 , x k -Q ∆ l x k+1 , x k 2 | [3] = E k Q ∆ i x k+1 , x k -∆ i x k+1 , x k + ∆ l x k+1 , x k -Q ∆ l x k+1 , x k 2 | [3] + E k ∆ i x k+1 , x k -∆ l x k+1 , x k 2 | [3] (12) ≤ 2E k Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 2E k ∆ l x k+1 , x k -Q ∆ l x k+1 , x k 2 | [3] + E k ∆ l x k+1 , x k -∆ i x k+1 , x k 2 | [3] ] (12) ≤ 2E k Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + 2E k ∆ l x k+1 , x k -Q ∆ l x k+1 , x k 2 | [3] + 2E k ∆ l x k+1 , x k -∆ x k+1 , x k 2 + ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] .Now we can combine all the parts together:T 2 = E     1 G k C (G k C -1) i,l∈G k C i̸ =l T ′ 2 (i, l)     ≤ E     1 D 2 i,l∈G k C i̸ =l 2E k Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 2E k ∆ l x k+1 , x k -Q ∆ l x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 2E k ∆ l x k+1 , x k -∆ x k+1 , x k 2 | [3]     + E     1 D 2 i,l∈G k C i̸ =l 2E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]     .Rearranging the terms, we getT 2 ≤ E   4 G k C i∈G k C E k Q ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   4 G k C i∈G k C E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Using variance decomposition, we getT 2 ≤ E   1 G k C i∈G k C 4E k Q ∆ i x k+1 , x k 2 | [3]   -E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   .Using the properties of unbiased compressors, we obtainT 2 ≤ E   1 G k C i∈G k C 4(1 + ω)E k ∆ i x k+1 , x k 2 | [3]   -E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k -∆ x k+1 , x k | [3]   ≤ E   1 G k C i∈G k C 4(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4(1 + ω)E k ∆ i x k+1 , x k 2 | [3]   -E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k -∆ x k+1 , x k | [3]   .Let us simplify the inequality:T 2 ≤ E   1 G k C i∈G k C 4(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4ωE k ∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k -∆ x k+1 , x k | [3]   .Using variance decomposition once again, we getT 2 ≤ E   1 G k C i∈G k C 4(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4ωE k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3]   + E   1 G k C i∈G k C 4E k ∆ i x k+1 , x k -∆ x k+1 , x k | [3]   + E   1 G k C i∈G k C 4ωE k ∆ x k+1 , x k 2 | [3]   .Then, we apply similar arguments to the ones used in deriving (28):T 2 ≤ E P G k C C(1 -δ) i∈G 4(1 + ω)E k ∆ i x k+1 , x k -∆ i x k+1 , x k 2 | [3] + E P G k C C(1 -δ) i∈G 4ωE k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] + E P G k C C(1 -δ) i∈G 4E k ∆ i x k+1 , x k -∆ x k+1 , x k 2 | [3] + E P G k C C(1 -δ) i∈G 4ωE k ∆ x k+1 , x k 2 | [3] .Using Assumptions D.1, D.2, D.3:T 2 ≤ E 4(1 + ω) GP G k C C(1 -δ) L 2 ± b ∥x k+1 -x k ∥ 2 + E 4(ω + 1) GP G k C C(1 -δ) ωL 2 ± ∥x k+1 -x k ∥ 2 + E 4 GP G k C C(1 -δ) ωL 2 ∥x k+1 -x k ∥ 2 .Finally, we obtainT 2 = E   Ek    1 G k C i∈G k C clip λ Q ∆ i x k+1 , x k -ARAgg k+1 Q 2 | [3]       ≤ 4 GP G k C C(1 -δ) cδ (1 + ω) L 2 ± b + (ω + 1)L 2 ± + ωL 2 E ∥x k+1 -x k ∥ 2 .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 Definition 2.2. We set λ k+1 = D Q max i,j L i,j ∥x k+1 -x k ∥. Also, let us introduce the notationARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP (Algorithm 1) satisfyE g k+1 -∇f x k+1 2 ≤ 1 - p 2 E g k -∇f x k 2 + BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 , with A = 4 p p G P G k C G C 2 (1 -δ) 2 ω + 8GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 8 p p G GP G k C C(1 -δ) cδω L 2 + 4 p p G P G k C G C 2 (1 -δ) 2 (ω + 1) + 8 p p G GP G k C C(1 -δ) cδ(ω + 1) L 2 ± + L 2 ± b + 16 p 2 (1 -p G )F 2 A D Q max i,j L i,j 2 B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,where B := 0 and D := 0 when C = n, and B :=P G k C GB (1-δ) C and D := P G k C G (1-δ) C when C < n, p G = Prob G k C ≥ (1 -δ)C and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C .Proof. Let us combine bounds for A 1 and A 2 together:A 0 = E g k+1 -∇f x k+1 2 ≤ 1 + p 2 E g k+1 -∇f x k+1 2 + 1 + 2 p E g k+1 -g k+1 2 ≤ 1 + p 2 A 1 + 1 + 2 p A 2 ≤ 1 + p 2 (1 -p)E g k -∇f (x k ) 2 + 1 + p 2 p δP G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + 1 + p 2 (1 -p)p G P G k C G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + 1 + 2 p pE E k ARAgg ∇f 1 (x k+1 ), . . . , ∇f n (x k+1 ) -∇f (x k+1 ) 2 | [1] + 1 + 2 p (1 -p)pGE   E k   1 G k C i∈G k C clip λ Q ∆i x k+1 , x k -ARAgg k+1 Q 2 | [3]     + 1 + 2 p (1 -p)(1 -p G )E E k ∇f (x k+1 ) -∇f (x k ) -ARAgg k+1 Q 2 | [2] .Using Lemma E.2 and lemmas from General Analysis (Lemmas D.10 and D.12) we haveA 0 = E g k+1 -∇f x k+1 2 ≤ 1 - p 2 E g k -∇f x k 2 + 2p δP G k C (1 -δ) E B∥∇f (x)∥ 2 + ζ 2 + 1 - p 2 p G P G k C G C 2 (1 -δ) 2 ωL 2 + (ω + 1)L 2 ± + (ω + 1)L 2 ± b E ∥x k+1 -x k ∥ 2 + (p + 2) 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4 (p + 2) GP G k C cδ (1 -δ) C ζ 2 + (p + 2) ζ 2 + 2 p p G E 4(1 + ω) GP G k C C(1 -δ) cδ L 2 ± b ∥x k+1 -x k ∥ 2 + 2 p p G E 4(ω + 1) GP G k C C(1 -δ) cδL 2 ± ∥x k+1 -x k ∥ 2 + 2 p p G E 4ω GP G k C C(1 -δ) cδL 2 ∥x k+1 -x k ∥ 2 + 2 p (1 -p G )2(L 2 + F 2 A α 2 λ k+1 )E x k+1 -x k 2 .Finally, we haveE g k+1 -∇f x k+1 2 ≤ 1 - p 2 E g k -∇f x k 2 + BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 ,whereA = 4 p p G P G k C G C 2 (1 -δ) 2 ω + 8GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 8 p p G GP G k C C(1 -δ) cδω L 2 + 4 p p G P G k C G C 2 (1 -δ) 2 (ω + 1) + 8 p p G GP G k C C(1 -δ) cδ(ω + 1) L 2 ± + L 2 ± b + 16 p 2 (1 -p G )F 2 A D Q max i,j L i,j 2 and B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D.Theorem E.4. Let Assumptions 2.3, D.1, D.2, D.3, D.4, D.5, 2.4 hold. Setting λ k+1 = max i,j L i,j x k+1 -x k . Assume that0 < γ ≤ 1 L + √ A , 4 B < p,whereA = 4 p p G P G k C G C 2 (1 -δ) 2 ω + 8GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 8 p p G GP G k C C(1 -δ) cδω L 2 + 4 p p G P G k C G C 2 (1 -δ) 2 (ω + 1) + 8 p p G GP G k C C(1 -δ) cδ(ω + 1) L 2 ± + L 2 ± b + 16 p 2 (1 -p G )F 2 A D Q max i,j L i,j 2 B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,where B := 0 and D := 0 when C = n, and B :=EQUATIONP G k C = C np G • (1-δ)C≤t≤C G -1 t -1 n -G C -t n C -1 , p G = Prob G k C ≥ (1 -δ) C = ⌈(1-δ)C⌉≤t≤C G t n -G C -t n C -1.Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA (Algorithm 1) satisfyE ∇f x K 2 ≤ 2Φ 0 γ 1 -4 B p (K + 1) + 2 Dζ 2 p -4 B ,where x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + γ p g 0 -∇f x 0 2 .Proof. The proof is analogous to the proof of Theorem D.14.Theorem E.5. Let Assumptions 2.3, 2.4, D.1, D.2, D.3, D.4, D.5, 2.7 hold. Setting λ k+1 = max i,j L i,j x k+1 -x k . Assume that 0 < γ ≤ 1 L + √ 2A , 8 B < p,whereA = 4 p p G P G k C G C 2 (1 -δ) 2 ω + 8GP G k C cδ (1 -δ) C B + 6 B + 4 p (1 -p G ) + 8 p p G GP G k C C(1 -δ) cδω L 2 + 4 p p G P G k C G C 2 (1 -δ) 2 (ω + 1) + 8 p p G GP G k C C(1 -δ) cδ(ω + 1) L 2 ± + L 2 ± b + 16 p 2 (1 -p G )F 2 A D Q max i,j L i,j 2 B = 2 δP G k C 1 -δ B 12cG C + p + 6 B, D = 2 δP G k C 1 -δ 6cG C + p + D,where B := 0 and D := 0 when C = n, and B :=P G k C GB (1-δ) C and D := P G k C G (1-δ) C when C < n, and where p G = Prob G k C ≥ (1 -δ)C and P G k C = Prob i ∈ G k C | G k C ≥ (1 -δ) C. Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA (Algorithm 1) satisfyE f x K -f (x * ) ≤ (1 -ρ) K Φ 0 + 2 Dζ 2 pρ , where ρ = min γµ 1 -8 B p , p 4 and Φ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .Proof. The proof is analogous to the proof of Theorem D.15.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 a 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( ∆i (x k+1 , x k )), i.e., on the following identity:E[Q( ∆i (x k+1 , x k )) | x k+1 , x k ] = ∆ i (x k+1 , x k ) = ∇f i (x k+1 ) -∇f i (x k ). Since E[clip λ k+1 (Q( ∆i (x k+1 , x k ))) | x k+1 , x k ] ̸ = ∇f i (x k+1 ) -∇f i (x k) in general, to analyze Byz-VR-MARINA-PP we also use a special choice of the clipping level:λ k+1 = α k+1 ∥x k+1 -x k ∥.To illustrate the main reasons for that, let us consider the case of uncompressed communication (Q(x) ≡ x). In this setup, for large enough α k+1 we have clip λ k+1 ∆i (x k+1 , x k ) = ∆i (x k+1 , x k ) for all i ∈ 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 ∼ ∥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 {g i } i∈G , 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 D.10 and formulas for p G and P G k C 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 stochasticityone 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 C clients with probability p to ensure that Byzantine workers form a minority in such rounds.F Byz-VR-MARINA-PP+: Simplified Version of Byz-VR-MARINA-PPIn this section, we present a simplified version of Byz-VR-MARINA-PP called Byz-VR-MARINA-PP+ (see Algorithm 3). The only difference between the two methods is in Line 10: Byz-VR-MARINA+ does not apply robust aggregation when c k = 0 and just averages the clipped vectors received from the set of clients S k . Nevertheless, when c k = 1, i.e., a large cohort of clients is sampled, the method still uses robust aggregation.Algorithm 3 Byz-VR-MARINA-PP+: Simplified Byz-VR-MARINA-PP1: Input: vectors x 0 , g 0 ∈ R d , stepsize γ, mini-batch size b, probability p ∈ (0, 1], number of iterations K, (δ, c)-ARAgg, clients' sample size 1 ≤ C ≤ C ≤ n, clipping coefficients {α k } k≥1 2: for k = 0, 1, . . . , K -1 do 3: Get a sample from Bernoulli distribution with parameter p: c k ∼ Be(p) 4: Sample the set of clients S k ⊆ [n], |S k | = C if c k = 0; otherwise |S k | = C 5: Broadcast g k , c k to all workers 6: for i ∈ G ∩ S k in parallel do 7: x k+1 = x k -γg k and λ k+1 = α k+1 ∥x k+1 -x k ∥ 8: Set g k+1 i = ∇f i (x k+1 ), if c k = 1, g k + clip λ k+1 Q ∆ i (x k+1 , x k ) , otherwise,where∆ i (x k+1 , x k ) is a mini-batched estimator of ∇f i (x k+1 ) -∇f i (x k ), Q(•) for i ∈ G ∩ S k are computed independently 9:end for 10:g k+1 =    ARAgg {g k+1 i } i∈S k , if c k = 1, g k + 1 C i∈S k clip λ k+1 Q ∆ i (x k+1 , x k ) , otherwise 11: end forThe key idea behind this modification can be explained as follows. For simplicity, let us assume that C is small and δ real is also small. Then, for the communication rounds with c k = 0, with a large probability, only good clients will be sampled. In this case, the method can use just an average of the received vectors and benefit from the lack of bias appearing due to the robust aggregation. Moreover, when c k = 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 c k = 0. However, for the rounds with c k = 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 k = 1.For simplicity, we analyze Byz-VR-MARINA-PP+ for bounded compressors only. The analysis is very similar to the one we provide for Byz-VR-MARINA-PP, but several steps are significantly simpler. In particular, the central part in the analysis of Byz-VR-MARINA-PP is in deriving a good recursive inequality for E[∥g k -∇f (x k )∥ 2 ], 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.1, 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 λ k+1 = D Q max i,j L i,j ∥x k+1 -x k ∥. Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP+ (Algorithm 3) satisfyE g k+1 -∇f x k+1 2 ≤ 1 - p 2 E g k -∇f x k 2 (30) + BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 , with A = 4 p 8pBGP G k C cδ (1 -δ) C + 6p B + (1 -p)p k G ω C + 6(1 -p)(1 -p k G ) p L 2 + 4(1 -p)p k G p 1 + ω C L 2 ± + 4(1 -p)p k G (1 + ω) pC L 2 ± b + 24(1 -p)(1 -p k G ) p 2 D Q max i,j L i,j 2 , B = 8GP G k C cδBp (1 -δ) C + 6p B, D = 4GP G k C cδp (1 -δ) C + p D, where B, D, p k G , P G k Care defined in Lemma D.13.Proof. From the update rule of g k+1 , we haveE g k+1 -∇f (x k+1 ) 2 = p E ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | c k = 1 T1 (31) + (1 -p) E   g k + 1 C i∈S k clip λ k+1 Q ∆ i (x k+1 , x k ) -∇f (x k+1 ) 2 | c k = 0   T2 .Next, we bound T 1 and T 2 separately. From Lemma D.10, we haveT 1 ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδζ 2 (1 -δ) C + ζ 2 .As for T 2 , we consider two possible situations: either S k ∩ B = ∅ (no Byzantine workers are among sampled ones) or S k ∩ B ̸ = ∅ (at least one Byzantine worker is sampled). Then, T 2 equalsT 2 = p k G E   g k + 1 C i∈S k clip λ k+1 Q ∆ i (x k+1 , x k ) -∇f (x k+1 ) 2 | c k = 0, S k ∩ B = ∅   T2 + (1 -p k G ) E   g k + 1 C i∈S k clip λ k+1 Q ∆ i (x k+1 , x k ) -∇f (x k+1 ) 2 | c k = 0, S k ∩ B ̸ = ∅   T2 ,wherep k G := Prob{S k ∩ B = ∅ | c k = 0} = G C n C = (G -C + 1)(G -C + 2) • . . . • (n -C) (G + 1)(G + 2) • . . . • n .The choice of the clipping level λ k+1 = D Q max i,j L i,j ∥x k+1 -x k ∥ and inequality (29) imply that clip λ k+1 Q ∆ i (x k+1 , x k ) for all i ∈ G. Therefore, for T 2 , we haveT 2 = E   g k + 1 C i∈S k Q ∆ i (x k+1 , x k ) -∇f (x k+1 ) 2 | c k = 0, S k ∩ B = ∅   = E ∥g k -∇f (x k )∥ 2 + E   1 C i∈S k Q ∆ i (x k+1 , x k ) -(∇f (x k+1 ) -∇f (x k )) 2 | c k = 0, S k ∩ B = ∅   ,where we use thatE 1 C i∈S k Q ∆ i (x k+1 , x k ) | c k = 0, S k ∩ B = ∅ = ∇f (x k+1 ) - ∇f (x k ). Moreover, since E 1 C i∈S k Q ∆ i (x k+1 , x k ) | c k = 0, S k ∩ B = ∅, S k = 1 C i∈S k (∇f i (x k+1 ) -∇f i (x k )) =: 1 C i∈S k ∆ i (x k+1 , x k ),we can decompose the last term in the upper-bound for T 2 as follows:T 2 = E ∥g k -∇f (x k )∥ 2 + E   E   1 C i∈S k Q ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 | S k   | c k = 0, S k ∩ B = ∅   + E   1 C i∈S k ∆ i (x k+1 , x k ) -(∇f (x k+1 ) -∇f (x k )) 2 | c k = 0, S k ∩ B = ∅   .Since the compression operator computations are independent on each client, we haveT 2 = E ∥g k -∇f (x k )∥ 2 + 1 C 2 E E i∈S k Q ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 | S k | c k = 0, S k ∩ B = ∅ + E   1 C i∈S k ∆ i (x k+1 , x k ) 2 | c k = 0, S k ∩ B = ∅   -E ∇f (x k+1 ) -∇f (x k ) 2 ≤ E ∥g k -∇f (x k )∥ 2 + 1 C 2 E E i∈S k Q ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 | S k | c k = 0, S k ∩ B = ∅ + 1 C 2 E E i∈S k ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 | S k | c k = 0, S k ∩ B = ∅ + E   1 C i∈S k ∆ i (x k+1 , x k ) 2 | c k = 0, S k ∩ B = ∅   -E ∇f (x k+1 ) -∇f (x k ) 2 (Def. 2.2) ≤ E ∥g k -∇f (x k )∥ 2 + ω C 2 E i∈S k ∆ i (x k+1 , x k ) 2 | c k = 0, S k ∩ B = ∅ + 1 C 2 E i∈S k ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 | c k = 0, S k ∩ B = ∅ + 1 C E i∈S k ∆ i (x k+1 , x k ) 2 | c k = 0, S k ∩ B = ∅ -E ∇f (x k+1 ) -∇f (x k ) 2 = E ∥g k -∇f (x k )∥ 2 + ω CG i∈G E ∆ i (x k+1 , x k ) 2 + 1 CG i∈G E ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 + 1 G i∈G E ∆ i (x k+1 , x k ) 2 -E ∇f (x k+1 ) -∇f (x k ) 2 . Using E ∆ i (x k+1 , x k ) 2 = E ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 + E ∆ i (x k+1 , x k ) 2 ,we continue the derivation as follows: 18)T 2 ≤ E ∥g k -∇f (x k )∥ 2 + 1 + ω CG i∈G E ∆ i (x k+1 , x k ) -∆ i (x k+1 , x k ) 2 + 1 + ω C 1 G i∈G E ∆ i (x k+1 , x k ) 2 -E ∇f (x k+1 ) -∇f (x k ) 2 (21) ≤ E ∥g k -∇f (x k )∥ 2 + (1 + ω)L 2 ± bC E ∥x k+1 -x k ∥ 2 + 1 + ω C E 1 G i∈G ∆ i (x k+1 , x k ) 2 -∇f (x k+1 ) -∇f (x k ) 2 + ω C E ∇f (x k+1 ) -∇f (x k ) 2 (20),(≤ E ∥g k -∇f (x k )∥ 2 + ω C L 2 + 1 + ω C L 2 ± + (1 + ω)L 2 ± bC E ∥x k+1 -x k ∥ 2 .Next, we estimate T 2 using Young's inequality and the choice of the clipping level:T 2 ≤ (1 + β)E g k -∇f (x k ) 2 + 2(1 + β -1 )E ∇f (x k+1 ) -∇f (x k ) 2 + 2(1 + β -1 )E   1 C i∈S k clip λ k+1 Q ∆ i (x k+1 , x k ) 2 | c k = 0, S k ∩ B ̸ = ∅   (18) ≤ (1 + β)E g k -∇f (x k ) 2 + 2(1 + β -1 ) L 2 E ∥x k+1 -x k ∥ 2 + E[λ 2 k+1 ] = (1 + β)E g k -∇f (x k ) 2 + 2(1 + β -1 ) L 2 + D 2 Q max i,j L 2 i,j E ∥x k+1 -x k ∥ 2 ,where β > 0 will be specified later in the proof. Combining the derived upper bounds for T 2 and T 2 , we getT 2 ≤ p k G + (1 -p k G )(1 + β) E ∥g k -∇f (x k )∥ 2 + p k G ω C L 2 + 1 + ω C L 2 ± + (1 + ω)L 2 ± bC E ∥x k+1 -x k ∥ 2 + 2(1 -p k G )(1 + β -1 ) L 2 + D 2 Q max i,j L 2 i,j E ∥x k+1 -x k ∥ 2 .Plugging the obtained bounds for T 1 and T 2 into (31), we obtainE ∥g k+1 -∇f (x k+1 )∥ 2 ≤ (1 -p) p k G + (1 -p k G )(1 + β) E ∥g k -∇f (x k )∥ 2 + p 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδζ 2 (1 -δ) C + ζ 2 + (1 -p)p k G ω C L 2 + 1 + ω C L 2 ± + (1 + ω)L 2 ± bC E ∥x k+1 -x k ∥ 2 + 2(1 -p)(1 -p k G )(1 + β -1 ) L 2 + D 2 Q max i,j L 2 i,j E ∥x k+1 -x k ∥ 2 .Takingβ := p 2(1-p k G ) , if p k G < 1, 1, if p k G = 1, we ensure that p k G + (1 -p k G )(1 + β) ≤ 1 + p 2 and (1 -p k G )(1 + β -1 ) ≤ (1-p k G )(p+2(1-p k G )) p ≤ 3(1-p k G ) p. Using these inequalities and (1 -p) 1 -p 2 ≤ 1 -p 2 , we simplify the upper bound for E ∥g k+1 -∇f (x k+1 )∥ 2 as follows:E ∥g k+1 -∇f (x k+1 )∥ 2 ≤ 1 - p 2 E ∥g k -∇f (x k )∥ 2 + p 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδζ 2 (1 -δ) C + ζ 2 + (1 -p)p k G ω C L 2 + 1 + ω C L 2 ± + (1 + ω)L 2 ± bC E ∥x k+1 -x k ∥ 2 + 6(1 -p)(1 -p k G ) p L 2 + D 2 Q max i,j L 2 i,j E ∥x k+1 -x k ∥ 2 .Rearranging the terms, we get (35).Then, similarly to the analysis of Byz-VR-MARINA, we get the following result. Theorem F.2. Let Assumptions D.1, D.2, D.3, D.4, D.5, 2.4 hold. Set λ k+1 = max i,j L i,j x k+1 -x k . Assume that0 < γ ≤ 1 L + √ A , 4 B < p,whereEQUATIONP G k C = C np G • (1-δ)C≤t≤C G -1 t -1 n -G C -t n C -1 , p k G = Prob{S k ∩ B = ∅ | c k = 0} = (G -C + 1)(G -C + 2) • . . . • (n -C) (G + 1)(G + 2) • . . . • n .Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA+ (Algorithm 3) satisfyE ∇f x K 2 ≤ 2Φ 0 γ 1 -4 B p (K + 1) + 2 Dζ 2 p -4 B ,where x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + γ p g 0 -∇f x 0 2 .Proof. The proof is analogous to the proof of Theorem D.14.Theorem F.3. Let Assumptions 2.4, D.1, D.2, D.3, D.4, D.5, 2.7 hold. Set λ k+1 = max i,j L i,j x k+1 -x k . Assume thatEQUATIONP G k C = C np G • (1-δ)C≤t≤C G -1 t -1 n -G C -t n C -1 , p k G = Prob{S k ∩ B = ∅ | c k = 0} = (G -C + 1)(G -C + 2) • . . . • (n -C) (G + 1)(G + 2) • . . . • n .Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA+ (Algorithm 3) satisfyE f x K -f (x * ) ≤ (1 -ρ) K Φ 0 + 2 Dζ 2 pρ , where ρ = min γµ 1 -8 B p , p 4 and Φ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .Proof. The proof is analogous to the proof of Theorem D.15.Improved neighborhood term and bound on δ. The key property of Byz-VR-MARINA+ is its better neighborhood terms, and maximal allowed fraction of Byzantine workers δ in comparison to Byz-VR-MARINA. To illustrate it, consider the non-PŁsetting (the discussion for the PŁ case is similar). For both algorithms, the neighborhood term in the convergence bounds equals O Dζ 2 p-4 B , but corresponding constants B and D are different: 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 δ in the results for Byz-VR-MARINA+ cannot be improved up to the numerical factors (Allouah et al., 2024b) .B = 2 δP G k C 1 -δ B 12cG C + p + 6 B and D = 2 δP G k C 1 -δ 6cG C + p + D for Byz-VR-MARINA, B = 8GP G k C cδBp (1 -δ) C + 6p B and D = 4GP G k C cδp (1 -δ) C + p D for Byz-VR-MARINA+.In this section, we 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-MARINA-PP and Byz-VR-MARINA-PP+ use b ′ -size mini-batched estimator ∇f i (x k+1 ) when c k = 1 for every i ∈ G ∩ S k in line 8 and are identical to their original versions in all other steps/computations. This modification reduces the computation cost of iterations when c k = 1, making the methods more practical. for i ∈ G ∩ S k in parallel do 7:x k+1 = x k -γg k and λ k+1 = α k+1 ∥x k+1 -x k ∥ 8: Set g k+1 i = ∇f i (x k+1 ), if c k = 1, g k + clip λ k+1 Q ∆ i (x k+1 , x k ) , otherwise,where∇f i (x k+1 ) is a b ′ -size mini-batched estimator of ∇f i (x k+1 ), ∆ i (x k+1 , x k ) is a b-size mini-batched estimator of ∇f i (x k+1 ) -∇f i (x k ), Q(•) for i ∈ G ∩ S k are computed independently 9:end for 10: g k+1 =    ARAgg {g k+1 i } i∈S k , if c k = 1, g k + ARAgg clip λ k+1 Q ∆ i (x k+1 , x k )k ⊆ [n], |S k | = C if c k = 0; otherwise |S k | = C 5: Broadcast g k , c k to all workers 6: for i ∈ G ∩ S k in parallel do 7: x k+1 = x k -γg k and λ k+1 = α k+1 ∥x k+1 -x k ∥ 8: Set g k+1 i = ∇f i (x k+1 ), if c k = 1, g k + clip λ k+1 Q ∆ i (x k+1 , x k ) , otherwise, where ∇f i (x k+1 ) is a b ′ -size mini-batched estimator of ∇f i (x k+1 ), ∆ i (x k+1 , x k ) is a b-size mini-batched estimator of ∇f i (x k+1 ) -∇f i (x k ), Q(•) for i ∈ G ∩ S k are computed independently 9:end for 10:g k+1 =    ARAgg {g k+1 i } i∈S k , if c k = 1, g k + 1 C i∈S k clip λ k+1 Q ∆ i (x k+1 , x k ) , otherwise11: end for However, our analysis of Byz-VR-MARINA-PP/Byz-VR-MARINA-PP+ without full-batch gradient computations requires the following additional assumption.Assumption G.1. We assume that there exist σ ≥ 0 such that for all x ∈ R d and i ∈EQUATIONwhere ∇f i (x) is an unbiased b ′ -size mini-batched estimator of ∇f i (x).In particular, when 1 m m j=1 ∥∇f i,j (x)-∇f i (x)∥ 2 ≤ σ, which is a standard assumption for variancereduced methods without full-batch gradient computations (Cutkosky and Orabona, 2019; Li et al., 2021; Gorbunov et al., 2021) , estimator ∇f i (x) = 1 b ′ b ′ j=1 ∇f i,ξ j i (x) with {ξ j i } i∈[n],j∈[m] being i.i.d. samples from the uniform distribution over [m] satisfies (32). Assumption G.1 is also standard for general stochastic optimization (Nemirovski et al., 2009; Ghadimi and Lan, 2013) .The main change in the analysis is related to Lemma D.10 since it is the only lemma that relies on the full-batch gradient computation. Nevertheless, it can be easily generalized to the case of Algorithms 4 and 5, as shown in the next result. Lemma G.2. Let Assumptions D.1, D.5, G.1 hold and Aggregation Operator (ARAgg) satisfy Definition 2.1. Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP/Byz-VR-MARINA-PP+ (Algorithms 4 and 5) satisfyT 1 = E E k ARAgg {g k+1 i } i∈S k -∇f (x k+1 ) 2 | [1] ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδB (1 -δ) C ζ 2 + ζ 2 + P G k C G (1 -δ) 2 C 2 + 4cδ σ 2 b ′ ,where B := 0 and ζ 2 := 0 when C = n, and B :=P G k C GB (1-δ) C and ζ 2 := P G k C Gζ 2(1-δ) C when C < n.Proof. Using the definition of aggregation operator, we haveEQUATIONTo proceed, we estimate the second term in the right-hand side of the above inequality first. From variance decomposition, we haveEQUATIONThe choice of C implies that G k C ≥ (1 -δ) C. Moreover, due to the independence of stochastic gradient computations on different workers, we haveE   Ek    1 G k C i∈G k C ( ∇f i (x k+1 ) -∇f i (x k+1 )) 2    | [1]    ≤ 1 (1 -δ) 2 C 2 E   Ek    i∈G k C ( ∇f i (x k+1 ) -∇f i (x k+1 )) 2    | [1]    = 1 (1 -δ) 2 C 2 E    i∈G k C E k ∇f i (x k+1 ) -∇f i (x k+1 ) 2 | [1]    = P G k C (1 -δ) 2 C 2 i∈G E ∇f i (x k+1 ) -∇f i (x k+1 ) 2 (32) ≤ P G k C Gσ 2 (1 -δ) 2 C 2 b ′ . Next, since 1 G k C i∈G k C ∇f i (x k+1 ) = ∇f (x k+1) with probability 1 when C = n, we can estimate the last term in (34) asE   Ek    1 G k C i∈G k C ∇f i (x k+1 ) -∇f (x k+1 ) 2    | [1]    ≤        0, if C = n E   1 G k C i∈G k C E k ∇f i (x k+1 ) -∇f (x k+1 ) 2 | [1]   , if C < n ≤    0, if C = n P G k C (1-δ) C i∈G E ∇f i (x k+1 ) -∇f (x k+1 ) 2 , if C < n (As. D.5) ≤    0, if C = n P G k C G (1-δ) C BE ∥∇f (x k+1 )∥ 2 + ζ 2 , if C < n = BE ∥∇f (x k+1 )∥ 2 + ζ 2 ,whereEQUATIONζ 2 :=    0, if C = n, P G k C Gζ 2 (1-δ) C , if C < n.Plugging the derived bounds in (34), we getE   Ek    1 G k C i∈G k C ∇f i (x k+1 ) -∇f (x k+1 ) 2    | [1]    ≤ P G k C Gσ 2 (1 -δ) 2 C 2 b ′ + BE ∥∇f (x k+1 )∥ 2 + ζ 2 .Using the above bound in (33), we continue the estimation of T 1 as follows:T1 (Def. 2.1) ≤ E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E k ∇f i x k+1 -∇f l x k+1 2 | [1]      + P G k C Gσ 2 (1 -δ) 2 C 2 b ′ + BE ∥∇f (x k+1 )∥ 2 + ζ 2 = E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E k ∇f i x k+1 -∇f l x k+1 2 | [1]      + E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E k ∇f i x k+1 -∇f i (x k+1 ) -∇f l x k+1 + ∇f l x k+1 2 | [1]      + P G k C Gσ 2 (1 -δ) 2 C 2 b ′ + BE ∥∇f (x k+1 )∥ 2 + ζ 2 ,where in the last inequality, we use the conditional independence of { ∇f i (x k+1 )} i ∈G k C for fixedx k+1 . Next, using Young's inequality, we deriveT 1 (12) ≤ E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E 2 ∇f i x k+1 -∇f x k+1 2 | [1]      + E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E 2 ∇f l x k+1 -∇f x k+1 2 | [1]      + E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E 2 ∇f i x k+1 -∇f i x k+1 2 | [1]      + E      cδ G k C (G k C -1) i,l∈G k C i̸ =l E 2 ∇f l x k+1 -∇f l x k+1 2 | [1]      + P G k C Gσ 2 (1 -δ) 2 C 2 b ′ + BE ∥∇f (x k+1 )∥ 2 + ζ 2 (32) ≤ E    cδ G k C i∈G k C 4E k ∇f i x k+1 -∇f x k+1 2 | [1]    + 4cδσ 2 b ′ + P G k C Gσ 2 (1 -δ) 2 C 2 b ′ + BE ∥∇f (x k+1 )∥ 2 + ζ 2 ≤ P G k C cδ (1 -δ) C i∈G 4E k ∇f i x k+1 -∇f x k+1 2 + 4cδσ 2 b ′ + P G k C Gσ 2 (1 -δ) 2 C 2 b ′ + BE ∥∇f (x k+1 )∥ 2 + ζ 2 (As. D.5) ≤ 4GP G k C cδB (1 -δ) C + B E ∇f x k+1 2 + 4GP G k C cδB (1 -δ) C ζ 2 + ζ 2 + P G k C G (1 -δ) 2 C 2 + 4cδ σ 2 b ′ (12) ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + ∇f x k+1 -∇f x k 2 + 4GP G k C cδB (1 -δ) C ζ 2 + ζ 2 + P G k C G (1 -δ) 2 C 2 + 4cδ σ 2 b ′ ≤ 8GP G k C cδB (1 -δ) C + 2 B E ∇f x k 2 + L 2 x k+1 -x k 2 + 4GP G k C cδB (1 -δ) C ζ 2 + ζ 2 + P G k C G (1 -δ) 2 C 2 + 4cδ σ 2 b ′ ,which concludes the proof. = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP without full-batch gradient computations (Algorithm 4) satisfyE g k+1 -∇f x k+1 2 ≤ 1 - p 4 E g k -∇f x k 2 + 3P G k C G (1 -δ) 2 C 2 + 12cδ σ 2 b ′ + BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 ,where A, B, D, p G , P G k C 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.1, D.2, D.3, D.5, G.1 hold. Set λ k+1 = 2 max i∈G L i x k+1 -x k . Assume that 0 < γ ≤ 1 L + √ A , 4 B < p,where A and B are defined in Theorem D.14. Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA without full-batch gradient computations (Algorithm 4) satisfyE ∇f x K 2 ≤ 2Φ 0 γ 1 -4 B p (K + 1) + 4 Dζ 2 p -4 B + 12P G k C G (1 -δ) 2 C 2 + 48cδ σ 2 b ′ (p -4 B) ,where x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .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.5. Let Assumptions 2.3, D.1, D.2, D.3, D.5, 2.7 hold. Set λ k+1 = max i∈G L i x k+1 -x k . Assume that 0 < γ ≤ min 1 L + √ 2A , 8 B < pwhere 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) satisfyE f x K -f (x * ) ≤ (1 -ρ) K Φ 0 + 4 Dγζ 2 pρ + 12P G k C G (1 -δ) 2 C 2 + 48cδ γσ 2 b ′ pρ , where ρ = min γµ 1 -8 B p , p 8 and Φ 0 = f x 0 -f * + 4γ p g 0 -∇f x 0 2 .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.14 and D.15), the above results have additional terms proportional to σ 2 b ′ in 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, b ′ is typically chosen to be large.Similarly to the previous section, we start with an adaptation of Lemma E. = D Q max i,j L i,j ∥x k+1 -x k ∥. Also, let us introduce the notation ARAgg k+1 Q = ARAgg clip λ k+1 Q ∆ 1 (x k+1 , x k ) , . . . , clip λ k+1 Q ∆ C (x k+1 , x k ) .Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP without full-batch gradient computations (Algorithm 4) satisfy E g k+1 -∇f x k+1 2 ≤ 1 - p 2 E g k -∇f x k 2 + 3P G k C G (1 -δ) 2 C 2 + 12cδ σ 2 b ′ + BE ∇f x k 2 + Dζ 2 + pA 4 ∥x k+1 -x k ∥ 2 ,= max i,j L i,j x k+1 -x k . Assume that 0 < γ ≤ 1 L + √ A , 4 B < p,where A and B are defined in Theorem E.4. Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA without full-batch computations (Algorithm 4) satisfyE ∇f x K 2 ≤ 2Φ 0 γ 1 -4 B p (K + 1) + 2 Dζ 2 p -4 B + 6P G k C G (1 -δ) 2 C 2 + 24cδ σ 2 b ′ (p -4 B) ,where x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , andΦ 0 = f x 0 -f * + γ p g 0 -∇f x 0 2 .Proof. The proof is identical to the proof of Theorem E.4 up to the replacement of Lemma E.3 with Lemma G.6.Theorem G.8. Let Assumptions 2.3, D.1, D.2, D.3, D.4, D.5, G.1, 2.4, 2.7 hold. Setting λ k+1 = max i,j L i,j x k+1 -x k . Assume that0 < γ ≤ 1 L + √ 2A , 8 B < p,where A and B are defined in Theorem E.5. Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA without full-batch computations (Algorithm 4) satisfyE f x K -f (x * ) ≤ (1 -ρ) K Φ 0 + 2 Dζ 2 pρ + 6P G k C G (1 -δ) 2 C 2 + 24cδ γσ 2 b ′ pρ , where ρ = min γµ 1 -8 B p , p 4 and Φ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .Proof. The proof is identical to 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 ComputationsSimilarly 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.1, D.2, D.3, D.4, D.5, G.1, 2.4 hold and the compression operator satisfy Definition 2.2. Assume that C ≤ G. We set λ k+1 = D Q max i,j L i,j ∥x k+1 -x k ∥. Then for all k ≥ 0 the iterates produced by Byz-VR-MARINA-PP+ without full-batch gradient computations (Algorithm 5) satisfyEQUATIONwhere A, B, D, p G , P G k C are defined in Lemma F.1.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.1, D.2, D.3, D.4, D.5, G.1, 2.4 hold. Set λ k+1 = max i,j L i,j x k+1 -x k . Assume that0 < γ ≤ 1 L + √ A , 4 B < p,where A and B are defined in Theorem F.2. Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA+ without full-batch gradient computations (Algorithm 5) satisfyE ∇f x K 2 ≤ 2Φ 0 γ 1 -4 B p (K + 1) + 2 Dζ 2 p -4 B + 2P G k C G (1 -δ) 2 C 2 + 8cδ pσ 2 b ′ (p -4 B) ,where x K is chosen uniformly at random from x 0 , x 1 , . . . , x K , and Φ 0 = f x 0 -f * + γ p g 0 -∇f x 0 2 .Proof. The proof is analogous to the proof of Theorem D.14.Theorem G.11. Let Assumptions 2.4, D.1, D.2, D.3, D.4, D.5, G.1 2.7 hold. Set λ k+1 = max i,j L i,j x k+1 -x k . Assume that0 < γ ≤ min 1 L + √ 2A , 8 B < p,where A and B are defined in Theorem F.3. Then for all K ≥ 0 the iterates produced by Byz-VR-MARINA+ without full-batch gradient computations (Algorithm 5) satisfyE f x K -f (x * ) ≤ (1 -ρ) K Φ 0 + 2 Dζ 2 pρ + 2P G k C G (1 -δ) 2 C 2 + 8cδ γσ 2 b ′ ρ ,where ρ = min γµ 1 -8 B p , p 4 and Φ 0 = f x 0 -f * + 2γ p g 0 -∇f x 0 2 .For each experiment, we tune the step size using the following set of candidates {0.1, 0.01, 0.001}. The step size is fixed. We do not use learning rate warmup or 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 λ k = λ∥x k -x k-1 ∥ 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) on the complete dataset for 1000 epochs.Our implementation of attacks and robust aggregation schemes is based on the public implementation from (Gorbunov et al., 2023) .Below we provide the missing neural network experiments from the main paper. We consider the MNIST dataset (LeCun and Cortes, 1998) and CIFAR10 (Krizhevsky et al., 2009) (as in (Karimireddy et al., 2021) ) with 20 clients, 5 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, we 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.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. Our implementation is available at https://github.com/SamuelHorvath/VR_ Byzantine/tree/partial_participation. • 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.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 L± from Assumption D.3 for some sampling strategies.This quantity is well-suited for sparsification-type compression operators like random sparsification(Stich et al., 2018) and 1-level ℓ2-quantization(Alistarh et al., 2017). For other compressors, such as quantization with more than one level(Goodall, 1951;Roberts, 1962), ζQ is not the main characteristic describing their properties.As one can see from our analysis, it is sufficient to take C ≥ max{1, δ real n /δ} similarly to(Data and Diggavi, 2021). However, in contrast to the approach fromData and Diggavi (2021), Byz-VR-MARINA-PP requires such communications only with small probability p. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: 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?  
- 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?
- 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.
- In the Introduction/Contributions both "Byz-VR-MARINA-PP" and "By-VR-MARINA-PP" are met. Is this a typo?
limitations: limitations: The authors adequately addressed the limitations of their work.
paper_summary: paper_summary: This paper proposes Byzantine robust approaches in the case of partial participation
strength_weakness: strength_weakness: 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.

Update : 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.
questions: questions: Did you compare to the literature on Asynchronous Byzantine ML?
limitations: limitations: Not applicable.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The proposed algorithm and its analysis focused on the case when the number of local update is 1. 

2. There is no any analysis of the heuristic algorithm. 

3. The experiments only use two simple datasets, LIBSVM and MNIST.
questions: questions: 1. Can the results be extended when the number of local update is larger than 1?

2. Is it possible to obtain any analysis of the heuristic algorithm under some assumptions?

3. Could you please add more experiments using harder and more popular datasets in Federated Learning?
limitations: limitations: The proposed algorithm and its analysis focused on the case when the number of local update is 1.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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. 
		
3. 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)$?
		
4. The recent work [1] also considers  partial participation within Byzantine-robust distributed learning. The authors should discuss it in the related works part.
		
	[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.

5. 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?
		
6. 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?
		
7. 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).
questions: questions: My detailed questions are listed in the above section; please refer to it.
limitations: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. 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. 
3. 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.
questions: questions: n/a
limitations: limitations: n/a

Comments: title: Further clarifications
Response to Reviewer mV5C
Response to Reviewer xeac
Additional clarification
Extra clarification
Thank you
Post Rebuttal
Response to reviewer
Response to authors
comment: I thank the authors for the clarification. As I promised, I increased my rating.
We thank the reviewer for contacting us. Below, we address further comments provided by the reviewer.

>*For the claim "literally, all existing methods etc." to be correct, there needs to be no single other work with provable Byzantine robustness allowing partial participation. If there exists just one, then the statement is an exaggeration, and the type that demotivates further reading, and I apologies if my review felt harsh in that sense.*

As we explained in our rebuttal, there is no work that addresses the same problem as we do in the same or comparable generality (without extra assumptions on some extra data or on the frequency filters). We will adjust the writing and add the discussion of extra related work -- it can be done easily and does not change the scientific essence of the paper. **Therefore, the mentioned writing issue is minor -- this should not be the reason for rejection (see NeurIPS 2024 Reviewers Guidelines https://neurips.cc/Conferences/2024/ReviewerGuidelines).**

>*Regarding existing works, you could add several other contributions on asynchrony in Byzantine robust ML such as (at least):*

We thank the reviewer for providing additional references. 

- [1] does not consider partial participation.

- [2] requires all-to-all communication, i.e., it is not applicable to partial participation.

- [3] requires that the number of sampled clients is such that robust aggregation is possible, i.e., it is necessary for their theoretical results to have majority of honest workers at each communication round, while our work does not have such a requirement.

- [4] considers the setup when the number of participating clients has to be at least $C \cdot B$, where $C \geq 2$ and $B$ is the overall number of Byzantine workers, i.e., the majority of participating clients need to be honest.

- [5] proposes a library for Byzantine-Robust Machine Learning and does not provide theoretical results (in particular, it does not provide a theory for partial participation).

- [6] does not consider partial participation.

Overall, we would like to highlight that all of the mentioned works focus **on a different problem setup**, and the methods from the mentioned papers **are not guaranteed to converge in the setup we consider**. **Therefore, the mentioned works do not undermine the contribution, novelty, and significance of our paper.** 

>*Most importantly, there seems to be a confusion in the paper and the rest of this discussion about what asynchrony means : unbounded communication delays, please refer to, e.g. Section 5 of the last reference (Fault-Tolerance in Distributed Optimization: The Case of Redundancy) about partial asynchrony.*

We understand this aspect, but as we already explained, asynchronous settings are quite different from synchronous settings with partial participation. Without additional assumptions on the extra data on the server or frequency filters, in the asynchronous regime, it is impossible to guarantee anything: even $1$ fast Byzantine clients can sequentially send multiple small updates that can shift the model arbitrarily far before good workers send their updates.

>*Another aspect of this confusion appears in statements such as "allowing Byzantines to form a majority during certain rounds of communication" (cf comments on openreview). But in an asynchronous setting, adversaries can not only form a majority during a communication round, but the round could also consists only of adversaries (i.e. the Byzantine nodes constitute 100% of the updates in such a round). See e.g. "Distributed Algorithms" Lynch 1996.*

As we explained above, without additional assumptions, asynchronous algorithms may fail in the presence of Byzantine nodes and **they cannot be directly applied to the problem we solve**. Moreover, we are not aware of any other paper (with asynchronous or synchronous communications) that shows **theoretical convergence guarantees in the setup we consider**.

**If the reviewer agrees with us, we kindly ask the reviewer to further improve the score.**

---

References:

[1] "Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers" (ICML 2024)

[2] "Robust collaborative learning with linear gradient overhead" (ICML 2023)

[3] "Democratizing Machine Learning: Resilient Distributed Learning with Heterogeneous Participants" (IEEE SRDS 2022)

[4] "Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning)" (NeurIPS 2021)

[5] "GARFIELD: System Support for Byzantine Machine Learning" (IEEE DSN 2021)

[6] "Fault-Tolerance in Distributed Optimization: The Case of Redundancy" (ACM PODC 2020).
We thank the reviewer for actively engaging in the discussion with us and for their willingness to reconsider the score. We address the remaining concerns and new questions below.

>*The authors claim that "If this probability were not greater than zero, it would indicate that the Byzantine clients form a majority not just in a subset of clients but across the entire client participation." I disagree with this statement for the following reasons. Since the number of iterations $K$ is finite, it is possible, though with a small probability, that Byzantine clients could form a majority in all communication rounds. For example, consider the case where $K=10$ and $n=3$, with $1$ Byzantine client. If we only sample $1$ client in each iteration, the Byzantine client would form a majority in all communication rounds with a probability of $\left(\frac{1}{10}\right)^{10}$. In this scenario, it would be impossible to derive any meaningful results from the proposed method.*

We believe there is a slight misunderstanding: in the response, we meant that the probability that good clients form a majority **during a particular round** has to be greater than zero. If this is not the case, then it means that a number of good clients is smaller than $C/2$ (otherwise, the probability is strictly larger than zero), which is smaller than $n/2$. However, when the number of good clients is smaller than half of the overall number of clients, it is provably impossible to solve the problem (this is a well-known result, e.g., see [1]).

Next, the provided example fits our setting, and our Theorems 4.1 and 4.2 are valid as well because they provide **in-expectation guarantees** for the squared norm of the gradient/function suboptimality. In-expectation convergence does not imply convergence with probability $1$ (and we never claimed that our method converges with probability $1$).

>*Therefore, I still believe the condition $\widehat{C} \geq \max\lbrace 1, \delta_{\text{real}}n / \delta\rbrace$ is critical...*

We agree that this condition is important for our theoretical results and we will add it to the formulations of Theorems 4.1 and 4.2. However, we would like to emphasize that this condition is needed only for $\widehat{C}$, i.e., for the number of clients that are sampled with a small probability $p$. In contrast, we have no restrictions on $C$, e.g., our theory works even for $C = 1$.

>*According to Karimireddy et al. (2021) and [1]... I think the method from Karimireddy et al. (2021) could be directly applied to the partial participation scenario.*

We want to clarify that Karimireddy et al. (2021) do not use **gradient** clipping, they apply CenteredClipping aggregation, which is an iterative procedure ensuring $(\delta,c)$-robustness of the aggregation. Although CenteredClipping uses a clipping operator inside, it is applied differently from what we do and for a different purpose. As explained in [2], CenteredClipping is a fixed-point iteration for solving a special equation (corresponding to the minimization of Huber-type loss function, see formula (1) in [2]). In contrast, we propose to clip gradient differences without any iterative procedure.

Regarding the direct application of the method from Karimireddy et al. (2021) to the problem of partial participation, we believe that it is quite challenging to show theoretically. In fact, we are currently working on this problem, but the theoretical analysis of Clipped Client Momentum SGD with partial participation becomes quite challenging since the key recurrences (e.g., the ones used in Lemma 9 from [1]) do not hold in this case. Nevertheless, this is a very important direction for future work, and we hope to resolve the mentioned challenges in the near future.

>*...the learning error seems large...*

We agree that the mentioned term is worse than the corresponding term in [3] and we will clarify it in the final version explicitly. However,

- In [3], the authors do not consider a partial participation setup, which is more challenging. Moreover, our method converges as $1/K$, while the method from [3] has $1/\sqrt{K}$ convergence.

- Our term is comparable to the one for Byz-VR-MARINA.

- When the problem is homogeneous ($\zeta = 0$), this term vanishes. We note that a homogeneous setup is also important.

- We have a simplified proof for the case of $C = 1$, where we achieve $O(\widehat{D}\zeta^2)$ error term instead. The key idea is that one can use robust aggregation only with probability $p$ in our method while clipping robustifies the remaining rounds. We will include it in the final version.

**If the reviewer agrees with our clarifications, then we kindly ask to increase the score.**

---

References

[1] Karimireddy et al. “Learning from history for Byzantine robust optimization”, ICML 2021

[2] Gorbunov et al. "Secure Distributed Training at Scale", ICML 2022

[3] Karimireddy et al. "Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing", ICLR 2022
We thank the reviewer for actively engaging in the discussion with us and for their willingness to further increase the score. We address the follow-up questions below.

>*If I did not get it wrong, a similar theoretical guarantee can also be achieved without full gradients or large-batch stochastic gradients. So I am curious why the full gradient is introduced in the initial version of the proposed method.*

Since the proposed modification has an additional term $\frac{\sigma^2}{nb'}$ in the convergence bound and the original version with a full batch computation (with small probability $p$) does not have such terms, we focused on the original version. That is, our paper is mainly theory-focused (though motivated by existing practical challenges), and that is why we considered only the version with better guarantees in the original submission. Nevertheless, the extra term in the convergence bound for the non-full batch version can be negligible in certain situations (as explained in previous responses) and we promise to include the proposed modification in the final version of our work.

>*In other words, could the authors briefly summarize the advantages and disadvantages of using full gradient periodically (instead of always using small-batch stochastic gradients)?*

- The main advantage of using full gradient periodically is described above -- it leads to better convergence bounds than for the version that always uses small-batch. 
- On the other hand, full-batch computation might be computationally expensive (though this computation happens only with a small probability in our method), implying that the method that always uses small-batch has cheaper iterations and is better suited to the case when devices have low computation resources. This can be seen as the main advantage of always using small-batch (and main disadvantage of the original version respectively).
- In terms of the other aspects, the methods are similar.

>*Furthermore, to quantitatively study the effect of $b$ or $b'$, it may be helpful to fix the gradient computation number and rewrite the convergence rate in the form of $b$ or $b'$, like those in [Yang et al., 2024]. I understand that the problem setting considered in this paper is much complex and there is only a little time left. This is just a suggestion for future work, and please focus on my question above in bold.*

We thank the reviewer for the great suggestion! Indeed, we can explicitly write how the convergence bounds depend on $b$ and $b'$ and then optimize them under the constraint that the computation budget is limited. This can be deduced from our current analysis relatively easily, and we promise to do it in the final version.

>*If full gradients are not necessary to obtain the theoretical result, can Byzantine robustness and partial participation be achieved at once if we just use the proposed clipping strategy with some simpler training methods, such as momentum SGD with robust aggregators? Similarly, given the limited time, a brief discussion is okay.*

This is a great question! In fact, we are currently working on this problem, but the theoretical analysis of Clipped Client Momentum SGD with partial participation becomes quite challenging since the key recurrences (e.g., the ones used in Lemma 9 from [1]) do not hold in this case. Nevertheless, this is a very important direction for future work, and we hope to resolve the mentioned challenges in the near future.

---

References

[1] Karimireddy et al. “Learning from history for Byzantine robust optimization”, ICML 2021
Thank you to the authors for their detailed responses. After carefully reading their replies and theoretical analysis, I am inclined to agree that the analysis may be more challenging than I initially thought, and I will reconsider the paper's contribution. However, some of my other concerns remain unresolved, and I would like to discuss these further.

A2. The authors claim that "If this probability were not greater than zero, it would indicate that the Byzantine clients form a majority not just in a subset of clients but across the entire client participation." I disagree with this statement for the following reasons. Since the number of iterations $K$ is finite, it is possible, though with a small probability, that Byzantine clients could form a majority in all communication rounds. For example, consider the case where $K = 10$ and $n = 3$, with $B = 1$ Byzantine client. If we only sample $C = 1$ client in each iteration, the Byzantine client would form a majority in all communication rounds with a probability of $(\frac{1}{3})^{10}$. In this scenario, it would be impossible to derive any meaningful results from the proposed method.

Therefore, I still believe the condition $\hat{C} \geq \max{1, \delta_{\text{real}} n / \delta}$ is critical, as it ensures that Byzantine clients form a majority only in some communication rounds, rather than in all rounds. This condition should be included in Theorem 4.1 or Theorem 4.2, rather than relegated to the footnote.

A3. According to Karimireddy et al. (2021) and [1], the gradient clipping method can defend against Byzantine attacks when Byzantine clients do not form a majority. Therefore, I think the use of the robust aggregator in the proposed method is unnecessary. I believe that gradient clipping alone is sufficient to handle Byzantine attacks whether the Byzantine clients form a majority or not. Related to this, I think the method from Karimireddy et al. (2021) could be directly applied to the partial participation scenario.

Beyond the concerns mentioned above, after revisiting the paper, I have a new concern:

B1. Although the authors prove the convergence of the proposed method in Theorem 4.1 and Theorem 4.2, the learning error seems large. The learning error in Theorems 4.1 and 4.2 is $O(\frac{\hat{D} \xi^2}{p})$ in the non-convex case, which is far from the optimal learning error $O(\delta \xi^2)$ proved by [2] when the probability $p$ is small. I suggest the authors clarify this point further in the paper.

[1] He, L., Karimireddy, S. P., \& Jaggi, M. (2022). Byzantine-robust decentralized learning via clipped gossip. arXiv preprint arXiv:2202.01545.

[2] Karimireddy, S. P., He, L., \& Jaggi, M. (2022). Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing. In International Conference on Learning Representations.
Thanks to the authors for taking the time to reply. 

For the claim "literally, all existing methods etc." to be correct, there needs to be no single other work with provable Byzantine robustness allowing partial participation. If there exists just one, then the statement is an exaggeration, and the type that demotivates further reading, and I apologies if my review felt harsh in that sense. 

Regarding existing works, you could add several other contributions on asynchrony in Byzantine robust ML such as (at least) :

"Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers" (ICML 2024)
"Robust collaborative learning with linear gradient overhead" (ICML 2023)
"Democratizing Machine Learning: Resilient Distributed Learning with Heterogeneous Participants" (IEEE SRDS 2022)
"Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning)" (NeurIPS 2021)
"GARFIELD: System Support for Byzantine Machine Learning" (IEEE DSN 2021)
"Fault-Tolerance in Distributed Optimization: The Case of Redundancy" (ACM PODC 2020).

So yes probably not a hundred but at least a dozen, but again, one is enough not to make the bold and non-nuanced statement the paper have.

Most importantly, there seems to be a confusion in the paper and the rest of this discussion about what asynchrony means : unbounded communication delays, please refer to, e.g. Section 5 of the last reference (Fault-Tolerance in Distributed Optimization: The Case of Redundancy) about partial asynchrony.

Another aspect of this confusion appears in statements such as "allowing Byzantines to form a majority during certain rounds of communication" (cf comments on openreview). But in an asynchronous setting, adversaries can not only form a majority during a communication round, but the round could also consists *only* of adversaries (i.e. the Byzantine nodes constitute 100% of the updates in such a round). See e.g. "Distributed Algorithms" Lynch 1996.

I recognise that my score was biased by the repeated unpleasant experience of reading statements such as "there exists no other method" in modern ML papers, and will update it. I hope you now understand the serious problem in having such a statement, but also address the issues about what partial participation and asynchrony means in a distributed setting. For now, this confusion prevents me from assessing the real contribution of this paper.
I thank the authors for the further explanation. I agree that the problem considered in this paper is challenging, as presented in the initial review, and I am inclined to further increase my rating. Meanwhile, I have two follow-up questions after reading the explanation, as listed below. 

1. If I did not get it wrong, a similar theoretical guarantee can also be achieved without full gradients or large-batch stochastic gradients. So I am curious why the full gradient is introduced in the initial version of the proposed method. In other words, **could the authors briefly summarize the advantages and disadvantages of using full gradient periodically (instead of always using small-batch stochastic gradients)?**  
Furthermore, to quantitatively study the effect of $b$ or $b'$, it may be helpful to fix the gradient computation number and rewrite the convergence rate in the form of $b$ or $b'$, like those in [Yang et al., 2024]. I understand that the problem setting considered in this paper is much complex and there is only a little time left. This is just a suggestion for future work, and please focus on my question above in bold.

2. If full gradients are not necessary to obtain the theoretical result, can Byzantine robustness and partial participation be achieved at once if we just use the proposed clipping strategy with some simpler training methods, such as momentum SGD with robust aggregators? Similarly, given the limited time, a brief discussion is okay.

Yi-Rui Yang, Chang-Wei Shi, and Wu-Jun Li. "On the Effect of Batch Size in Byzantine-Robust Distributed Learning." ICLR 2024.
We thank the reviewer for increasing the score and participating in the discussion with us. However, we want to provide additional clarifications that are important for making a final decision.

>*My major concern is about the full gradient (or the stochastic gradient with a large batch size). The full gradients are computationally expensive and empirically has little positive effect on the training of large-scale models in the experiments of existing works.*

As we explained in our previous response, the additional term in the convergence bound for the proposed modification without full batch computation is proportional to $\frac{\sigma^2}{nb'}$. For situations when $n$ is large enough, one can use small $b'$ (same as during other rounds), but the term $\frac{\sigma^2}{nb'}$ will remain small as well. Therefore, this limitation of our method is easily addressable.

>*Meanwhile, I would like to clarify that the score is not based only on the parts of the experiments.*

If our explanation above addresses the concern about full/large batch computation, then we believe we addressed all the concerns related to the theory and the method. Therefore, from the reviewer's responses, we conclude that the only factor preventing the reviewer from increasing the score further is experiments.

>*Given the reasons above, it would be interesting to see the performance of Byz-VR-MARINA-PP on the model with a larger scale. Unfortunately, the additional experimental results do not address the concern.*

>*In summary, the theoretical results in this paper are generally solid, but the practical performance of the proposed method is not that satisfactory.*

The remaining concerns are related to the experiments, and we are committed to addressing them in the final version of our paper, as we explained in our previous responses.

To sum up, **if the reviewer agrees with our responses above, then we kindly ask the reviewer to reconsider their score towards further improvement.** If this is not the case, we kindly ask the reviewer to let us know what are the remaining concerns and why they prevent the reviewer from increasing the score. **Finally, we also emphasize the difficulty of the resolved open question**: partial participation for Byzantine-robust learning was never considered in such generality as we do, e.g., there were no methods allowing Byzantines to form a majority during certain rounds of communication without extra assumptions (such as additional dataset on the server). **We believe it is another aspect justifying a higher score.**
I thank the authors for the timely and detailed explanation, which has addressed my concern about the effect of the extension on the theoretical results. 

Meanwhile, I would like to clarify that the score is not based only on the parts of the experiments. My major concern is about the full gradient (or the stochastic gradient with a large batch size). The full gradients are computationally expensive and empirically has little positive effect on the training of large-scale models in the experiments of existing works. Given the reasons above, it would be interesting to see the performance of Byz-VR-MARINA-PP on the model with a larger scale. Unfortunately, the additional experimental results do not address the concern.

Since my concerns about the theory are almost addressed, the submission looks borderline to me now. I am willing to raise my rating accordingly. In summary, the theoretical results in this paper are generally solid, but the practical performance of the proposed method is not that satisfactory.
We thank the reviewer for contacting us and would like to elaborate further on the concerns mentioned.

>*The authors propose to use a larger batch size $b'$ to avoid the heavy computation of full gradients. However, it is uncertain how this heuristic extension affects the theoretical results. A main contribution of this work is the convergence guarantee of achieving Byzantine robustness when allowing partial participation. Will this heuristic extension damage the theoretical results?*

Such an extension can also be analyzed if we additionally assume that stochastic gradients have uniformly bounded variance $\sigma^2$ (a classical assumption in this case for recursive variance reduction). Then, our analysis will remain almost unchanged: in Lemma D.8, $\zeta^2$ will be replaced by $\zeta^2 + \frac{\sigma^2}{\widehat{C}b'}$ (up to a constant factor). This is well-aligned with a similar term appearing in the analysis of VR-MARINA (see Theorem D.3 from [1]; in particular, for $\widehat{C} = n$ we also have $\frac{\sigma^2}{nb'}$ term). **That is, the modification of Byz-VR-MARINA-PP proposed in our response is guaranteed to converge** to some neighborhood that depends on the variance of stochastic gradients, the number of clients, and the batch size $b'$. **If the number of clients is sufficiently large, which is the case for many FL applications where client sampling is used, then this neighborhood term becomes negligible.**

>*I appreciate the authors providing additional experimental results on the CIFAR dataset. However, the results are far from satisfactory. The test accuracy of the ResNet-18 model on the CIFAR-10 dataset can be up to 94% when trained with momentum SGD. In the additional experiment, the test accuracy is only about 50%.*

This experiment's purpose was to show that our approach works for various models. We emphasize that without clipping, the method does not converge under SHB attack, not even to 50%. Recovering the best-known accuracy is not the goal of our experiments. Given the severe time limitations, we ran the methods only for $5$ epochs and did not tune the parameters extensively. Our current experiment corresponds to 200 communication rounds, and our obtained accuracy is consistent or better than other works that also use heterogeneous data split, e.g., see Figure 1 in [3], while we note that in our case, malicious workers are present. For camera-ready, we will provide experiments with 4000 communications rounds (similarly to [3]). Finally, please note that for the heterogeneous split in FL, we would generally expect much smaller final accuracy, e.g., 78% in [3].

>*Meanwhile, periodically computing full gradients or stochastic gradients with a large batch size is computationally expensive. Therefore, I am not optimistic about the proposed method's scope of practical application.*

For the experiments with neural networks, we used a heuristic extension of our method described in lines 305-315 of our paper. In particular, we used Byzantine-Robust SGD with momentum from [2] as the base method and applied our heuristic to it. This method does not require full/large batch computations at all.

**We also note that our work is primarily theoretical, and we find it unfair to give our paper a “reject” score based on the criticism of the experiments.**

---

References:

[1] Gorbunov et al. "MARINA: Faster Non-Convex Distributed Learning with Compression", ICML 2021

[2] Karimireddy et al. “Learning from history for Byzantine robust optimization”, ICML 2021

[3] Reddy et al. “Adaptive Federated Optimization”, ICLR 2021
I thank the authors for the explanation. However, there are some remaining concerns.

1. The authors propose to use a larger batch size $b'$ to avoid the heavy computation of full gradients. However, it is uncertain how this heuristic extension affects the theoretical results. A main contribution of this work is the convergence guarantee of achieving Byzantine robustness when allowing partial participation. Will this heuristic extension damage the theoretical results?

2. I appreciate the authors providing additional experimental results on the CIFAR dataset. However, the results are far from satisfactory. The test accuracy of the ResNet-18 model on the CIFAR-10 dataset can be up to 94% when trained with momentum SGD. In the additional experiment, the test accuracy is only about 50%. Meanwhile, periodically computing full gradients or stochastic gradients with a large batch size is computationally expensive. Therefore, I am not optimistic about the proposed methods scope of practical application.

Due to the reasons above, my rating remains unchanged.
Dear Reviewer,

Thank you for checking our responses and other reviews. We are glad to hear that we addressed all your concerns. We would also appreciate it if you could champion our paper in discussion with other reviewers: as the reviewer acknowledged and as we explain in the paper, **the problem we addressed is very important and non-trivial, and we managed to circumvent multiple technical challenges to achieve our results (as explained in the general rebuttal message)**.

Thank you once again for your feedback and time. If the paper gets accepted, we promise to incorporate all the requested changes and add extra experiments attached to the general rebuttal message, in particular, to the camera-ready version.

Best regards,

Authors
I appreciate the authors efforts to address my question and include more experiments. 

After carefully reading the comments from the other reviewers and the responses of the authors I find that all my concerns are addressed. I am inclined to keep my score and I look forward to the reviewers discussion.
Thank you for your comment!

Let us address each issue one by one.

A1. We are having difficulty understanding the reviewer's perspective. In our response, we have thoroughly outlined the challenges faced during the analysis and provided **detailed explanations** as to why this work is not merely a "simple combination" of existing techniques. The **reviewer acknowledges** that we have done this. Despite this, the reviewer has not offered any **specific reasoning** to support the belief that the analysis is not particularly challenging. If the analysis were indeed as straightforward as suggested, it raises the question of why this is the **first result** to achieve Byzantine robustness in the context of partial participation without relying on strong assumptions, such as additional data on the server, etc. 

We believe that a scientific discussion should be based on **well-reasoned** arguments and evidence, rather than subjective feelings or impressions. We would greatly appreciate a more detailed explanation or critique so that we can engage in a meaningful and **constructive** dialogue.

A2. Please note that the condition on $\hat{C}$ is only required once every several communication rounds, and this happens with a small probability $p$. We will certainly add a footnote to clarify this point, as suggested. 

Additionally, it is important to understand that we do not need a situation where the good clients form a majority in every round with absolute certainty. What is necessary is that the probability of good clients forming a majority is greater than zero. If this probability were not greater than zero, it would indicate that the Byzantine clients form a majority not just in a subset of clients (cohort) but across the entire client population. In such a case, it would be impossible to develop any effective method, as the system would be fundamentally compromised. 

We addressed this crucial point at the beginning of the paper (lines 104-105), but we will ensure that it is emphasized appropriately in the camera-ready version. 

A3.Let us provide a more detailed clarification on this point. Robust aggregators are designed to function effectively as long as the Byzantine clients do not form a majority, meaning that the proportion of Byzantine clients $\delta$ is within the acceptable range $\delta \leq \delta_{\max} < 0.5$. For a more precise definition, please refer to Definition 2.1 in the paper.

However, when the Byzantine clients do form a majority, robust aggregators are no longer effective, as they fail to maintain their robustness under such conditions. To mitigate this issue and handle scenarios where the Byzantine clients might dominate, we incorporate a clipping technique. This approach helps to manage the influence of outliers and reduces the potential impact of malicious clients on the overall aggregation process.

We hope this expanded explanation clarifies how our method addresses situations where the number of Byzantine clients might form a majority.

A4. Please note that our method employs variance reduction techniques for both data and client sampling. Because the method is designed to reduce variance, increasing the cohort size or batch size does not further reduce variance (as this is already achieved through the variance reduction technique). Consequently, increasing the cohort size or batch size does not lead to substantial gains in convergence. In other words, the benefits of using a larger cohort or batch are limited when variance reduction is already in place.

In this context, the situation is similar to what is observed with other variance-reduced methods. Therefore, utilizing a smaller cohort (i.e., a subset of clients) is more advantageous for minimizing communication load. By doing so, we can maintain efficiency and effectiveness while managing the overall communication overhead, which is a key consideration in practical implementations.

We hope that we have addressed all the raised issues. If all concerns have been resolved, we would appreciate it if the score could be increased. If there are still any outstanding issues, we remain open to providing further clarification.
I thank the authors for their careful responses to each of my comments. The authors have addressed some of my concerns. I will respond to the authors' responses which I think should be further clarified. 

A1. Although the authors highlight several technical challenges in their responses, I'm still not convinced by the novelty of the paper. Since the proposed method is a simple combination of two existing methods, I believe the analysis may not be very challenging.

A2.  I believe the condition $\hat{C} \geq \max{1, \delta_{\text{real}} n / \delta}$ is critical and should not be placed in the footnote. In the current presentation of Theorem 4.1 and Theorem 4.2, there seems no guarantee that the Byzantine clients form a majority only in some communication rounds rather than in all rounds.

A3.  If I understand the authors' response correctly, they confirm the need for a robust aggregator to handle Byzantine attacks, even when the gradient clipping method is used. However, I still don’t fully understand why the robust aggregator is necessary. Could the authors please clarify this further?

A5.  I agree that for many machine learning problems, the optimal batch size is not a full batch but rather a smaller one. This is especially true in neural network training, where stochastic noise can help achieve better solutions with smaller generalization errors. Since the objective function in the experiments is strongly convex, does this conclusion still apply? Could the authors provide more insights into this phenomenon?

Given the comments mentioned above, I am keeping my rating unchanged.