Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top
Authors: Eduard Gorbunov
Samuel Horváth
Peter Richtárik
Gauthier Gidel
Venue: ICLR 2023 poster (2023)
Keywords: byzantine robustness
variance reduction
communication compression

Abstract: Byzantine-robustness has been gaining a lot of attention due to the growth of the interest in collaborative and federated learning. However, many fruitful directions, such as the usage of variance reduction for achieving robustness and communication compression for reducing communication costs, remain weakly explored in the field. This work addresses this gap and proposes Byz-VR-MARINA -- a new Byzantine-tolerant method with variance reduction and compression. A key message of our paper is that variance reduction is key to fighting Byzantine workers more effectively. At the same time, communication compression is a bonus that makes the process more communication efficient. We derive theoretical convergence guarantees for Byz-VR-MARINA outperforming previous state-of-the-art for general non-convex and Polyak-Lojasiewicz loss functions. Unlike the concurrent Byzantine-robust methods with variance reduction and/or compression, our complexity results are tight and do not rely on restrictive assumptions such as boundedness of the gradients or limited compression. Moreover, we provide the first analysis of a Byzantine-tolerant method supporting non-uniform sampling of stochastic gradients. Numerical experiments corroborate our theoretical findings.

Published as a conference paper at ICLR 2023
VARIANCE REDUCTION IS AN ANTIDOTE TO BYZANTINE WORKERS: BETTER RATES, WEAKER ASSUMPTIONS AND COMMUNICATION COMPRESSION AS A CHERRY ON THE TOP
Eduard Gorbunov* MBZUAL, MIPT Mila & UdeM, KAUST
Samuel Horváth MBZUAI, KAUST
Peter Richtárik KAUST
Gauthier Gidel
Mila & UdeM
Canada CIFAR AI Chair
ABSTRACT
Byzantine-robusten has been gaining a of attention due the growth of the interest in collaborative and federated learning. However, many fruitful directions, such as the usage variance reduction for achieving robustness and communica- tion compression for reducing communication costs, remain weakly explored in the field. This work addresses this gap and proposes Byz- SyZ-VR-MARINA- new Byzantine-tolerant method with variance reduction and compression. A key mes- sage of our paper is that variance reduction is key to fighting Byzantine workers more effectively. At the same time, communication compression is bonus that makes the process more communication efficient. We derive theoretical conver- gence guarantees for Byz-VR SEE-VR-MARINA outperforming previous state-of-the-art for general non-convex and Dollykk-Eojaseewice loss functions. Unlike the con- current Byzantine-robil
methods with variance reduction and/or compression, our complexity results are tight and do not rely on restrictive assumptions such boundedness of the gradients or limited compression. Moreover, we provide the first analysis of ryzantine-toleran method supporting non-uniform sampling of stochastic gradients. Numerical experiments corroborate our theoretical findings.
INTRODUCTION
Distributed optimization algorithms play a vital role in the training of the modern machine learning models. In particular, some tasks require training of deep neural networks having billions of parameters on large datasets (Brown et al., 2020; Kolesnikov et al., 2020). Such problems may take years of computations to be solved if executed circumvent this issue, is natural to use distributed optimization algorithms allowing to tremendously reduce the training time (Goyal al., 2017; You al., 2020). In the context of speeding up the training, distributed methods are usually applied in data centers (Mikami et al., 2018). More recently, similar ideas have been applied to train models using open collaborations (Kijsipongse al., 2018; or an individual) has problems.
single yet powerful machine (Li, 2020). To
Diskin et al., 2021), where each participant (e.g., small company/univern very limited computing power but can donate jointly solve computationally-ie
Moreover, in Federated Learning (FL.) applications (McMahan et al., 2017; Konečný et al., 2016 6;; Kairouz et al., 2021), ), distributed algorithms are natural and the only possible choice since in such problems, the data is privately distributed across multiple devices.
In the optimization problems arising in collaborative and federated learning, there is a high risk that some participants deviate from the prescribed protocol either on purpose or not. In this paper, we
"Corresponding author: eduard.gorbune @mmzuai.aaa ac..ac. Part of the work was done when Gorbunov was a rescarcher at MIPT and Mila & UdeM and also a visiting researcher KAUST, in the Optimization and Machine Learning Lab of P. Richtárik.
t Part of the work done when S. Horváth was Ph.D. student KAUST.

---

Published as a conference paper at ICLR 2023
call such participants Byzantine workers' For example, such peers can maliciousll send incorrect gradients to slow down or even destroy the training. Indeed, these attacks can break the convergence of naive methods such as Parallel-SGD (Zinkevich et al., 2010). Therefore, it is crucial to secure (a.k.a. Syyantin-rous//yyaaiiinttttoottn
distributed methods for solving such problems.
However, designing distributed methods with provable Byzantine-robusttees is not an easy task. The non-triviality of this problem comes from the fact that the stochastic gradients of good/honest/regllar workers are naturally different due to their stochasticity and possible data heterogeneity. At the same time, malicious workers can send the vectors looking like the stochastic gradients of good peers or create small but couele shifts. Therefore, as it is shown in (Baruch et al.. 2019; Xie et al., 2020; Karimireddy et al., 2021), Byzantine workers can circumvent popular defences based on applying robust aggregation rules (Blanchard et al., 2017; Yin et al., 2018; Damaskinos et al., 2019; Guerraoui et al., 2018; Pillutla et al., 2022) with Parallel-SGD. Moreover, in a broad class of problems with heterogeneous data, it is provably impossible to achieve any predefind accuracy of the solution (Karimireddy et al., 2022; El-Mhamdi et al., 2021).
Nevertheless, as it becomes evident from the further discussion, several works have provable Byzan- tine tolerance and rigorous theoretical analysis. In particular, Wu et al. (2020) propose natural based on the usage of variance-reduced
yet elegant solution to the problem of Byzantine-robustee methods (Gower et al., 2020) and design the first vuriance-reduced Byzantine-robuss method called Byrd-SAGA, which combines the celebrated SAGA method (Defazio et al., 2014) with geometric median aggregation rule. As result, reducing the stochastic noise of estimators used by good workers makes it easier to filter out Byzantine workers (especially in the case of homogeneous data). However, Wu et al. (2020) derive their results only for the strongly convex objectives, and the obtained convergence guarantees are significantly worse than the best-known convergence rates for SAGA, i.e., their results are not tight, even when there are no Byzantine workers and all peers have homogeneous data. It is crucial to bypass these limitations since the majority of the modern, practically interesting problems are non-convex. Furthermore, it is hard to develop the field without tight convergence guarantees. All in all, the above leads to the following question:
Q1: Is it possible to design variance-reduced methods with provable secantine-robusteess and tight theoretical guarantees for general non-convex optimization problems?
In addition to Byzantine-robustned one has to take into account that naive distributed algorithms suffer from the so-called communication bottleneck situation when communication is much more expensive than local computations on the devices. This issue is especially evident in the training of models with a vast number of parameters (e-g., millions or trillions) or when the number of workers is large (which is often the case in FL.). One of the most popular approaches to reducing the commu- nication bottleneck is to use communication compression (Seide et al., 2014; Konečný et al., 2016; Suresh et al., 2017), i.e., instead of transmitting dense vectors (stochastic operator to these vectors and send the
order tensors) workers apply some compression/sparsifeeee compressed results to the server. Distributed learning with compression is a relatively well- well-developed field, e.g., see ( (Vogels et al., 2019; Gorbunov et al., 2020b; Richtárik et al., 2021; Philippenko & Dieuleveut, 2021) and references therein for the recent advances.
Perhaps surprisingly, there are not many methods with compressed communication in the context of Byzantine-robust learning. In particular, we are only aware of the following works (Bernstein et al., 2018; Ghosh et al., 2020; 2021; Zhu & Ling, 2021),. Bernstein et al. (2018) propose signSGD to reduce communication cost and and study the majority vote to cope with the Byzantine workers under some additional assumptions about adversaries. However, it is known that signSGD is not guaranteed to converge (Karimireddy al., 2019). Next, Ghosh et al. (2020; 2021) apply aggregation based on the selection of the norms of the update vectors. In this case, Byzantine workers can successfully hide in the noise applying SOTA attacks (Baruch et al., 2019). 7hu & Ling (2021) study Byzantine-robur versions of compressed SGD (BR-CSGD) and SAGA (BR-CSAGA) and also propose a combination of DIANA (Mishchenko et al., 2019; Horváth et al., 2019b) with BR- CSAGA called BROADCAST. However, the derived convergence results for these methods have several limitations. First of all, the analysis is given only for strongly convex problems. In addition,
'This term is standard for distributed learning literature (Lamport et al., 1982; Su & Vaidya, 2016; Lyu et al., 2020). Using this term, we follow standard terminology and do not want to offend any group. It would be great if the community found and agreed more neutral term denote such workers.
2

---

Published as a conference paper at ICLR 2023
Table Comparison the state-of-the art (in theory) tyzleatine-oolrran distributed methods. Columns: "NC" does the theory works for general smooth non-convex functions?: "PL" = does the theory works for functions satysfying PE-condition (As. 2.5y?; "Tight"" = does the theory recover tight best-known results for the version of the method with ó (no Ryzantines) "Compr. ?" does the method use communication compression?; "VR?" is the method varuenc:-reducedd?: "No UBV?" does the theory work without assuming uniformly bounded variance of the stochastic gradients, i.c., without the assumption that for
E RR the good workers have an access to the unbiased estimators (:: of V (++()) such that IB [B]lg(()) - V f((2))]l I o for all E g and a 2 0?; "No BG?" does the theory work without assuming uniformly bounded second moment of the stochastic gradients, ie., without the assumption that for all æ E IR the good workers have access to the unbiased estimators (x) fi (x) such that (z)]l < D2 for all E and > 07; "Non-US?" does the theory support non- non-uniform sampling of the stochastic gradients; "Het.?" = does the theory work under <² -eeteroggnnity assumption (As. 2.2)?
Method
NC
PL
Tight?
Compr.?
VR?
No UBV?
No BU?
Non-US?
Het.
BR-SGDm
/
x
K
(Katminedyy 2022)
BTARD-SGD
x/
X
X
X
X
X
(Gorbanov 2021a)
Byrd-SAGA
X
X/D
X
4
X
(Wa et 2020)
BR-MVR
V
X
X
(Karmireddy et al., 2021)
(Tho & ing. 2021)
BR-CSGD
X/D
X
X
BR BR-CSAGA
X
X
X
X
(Th & Ling 2021)
BROADCAST (Zha Ling, 2021)
X
X/tb
d
X
Byz MA-VRAAAAAIN
/
/
V
Strong convexity of f is assumed.
relies on restrictive assumptions. Namely, Zhu & Ling (2021) assume uniform boundedness of the second moment of the stochastic gradient in the analysis of BR-CSGD and BR-CSAGA. This assumption rarely holds in practice, and it also implies the boundedness of the gradients, which contradicts the strong convexity assumption. Next, although the bounded second-moment moment assumption not used in the analysis of BROADCAST, Zhu & Ling (2021) derive the rates of BROADCAST under the assumption that the compression operator is very accurate, which implics that in theory workers apply almost no compression the communicated messages (see remark (5) under Table 2). Finally, even if there are no Byzantine workers and no compression, similar to the guarantees for SAGA the rates obtained for BR-CSGD, BR-CSAGA, and BROADCAST are outperformed with a large margin by the known rates for SGD and SAGA. All of these limitations lead to the following question:
Q2: Is it possible to design distributed methods with compression, provable Byzantine-robustee and tight theoretical guarantees without making strong assumptions?
In this paper, we give confirmatory answers to Q1 and Q2 by proposing and rigorously analyzing new Byzantine-toleran tollerant variance-reduced method with compression called ByZ-VR-MARING Detailed related work overview is deferred to Appendix A.
Our Contributions. Before we proceed, we need to specify the targetted problem. We consider a centralized distributed learning in the possible presence of malicious so-called Byzantine peers. We assume that there are n clients consisting of the two groups: [n] = 9 L1 B, where G denotes the set of good clients and B is the set of bad/mmliicios/Byzznmii workers. The goal is solve the following optimization problem
f(x) - 1 I
1 Σ (z) ViEG,
min ZERd
f((z) =
(1)
sEg
where G = | and functions (x) are assumed to be smooth, but not necessarily convex. Here each good client has its dataset of the size m, ft,((z) (r) is the loss of the model, parameterized by vector Rdd the j-th sample from the dataset the i-th client. Following the classical convention
3

---

Published as a conference paper at ICLR 2023
Table 2: Comparison the state-of-the-att complexity results for Byzantinetoolrrat distribused methods. Columns: "Assumptions" additioonal usumptions smoothness of all (xx 1 (allhough resulls require refined As. 2.3y; "Complexity (NC)" and "Complexity (Pt.) number of communication rounds required to find such a that EJ V fxx]]l S = in the general non convex case and case respectively. Dependencies numerical constanis (and logaritims
setting, smoothness constunts, and initial suboplimality are omitted in the complexity bounds. Although BR-SGDm, BR-MVR, BTARD-SGD, Byrd-SAGA, BR-CSGD, BR-CSAGA, BROADGAST are analyzed for unit batchsize only
such x that [x) f(=") S
of desired accuracy; 6 ratio of Byzantine workers; parameter of the robust
one can easily generalize them
and we show these generalizatiios in the table. Notation: aggrogator; n = total number of werkers; b= batchsize; o² uniform bound on the variance of stochastic gradients: D = uniform bound on the secund moment of stochasic gradients; C= tbe number of workers used by BTARD-SGD for the checks of computations after each step; " parameter from As. 2.5 (strong convexity parameter in the case of BTARD-SGD, Byrd-SAGA, BR-CSGD, BR-CSAGA, BROADCAST); size the local dalasel on workers; p min {a/m, 1/(+w)) probubility of communication in Byz- MR-MMINAA
Setup
Method
Assumptions
Complexity (NC)
Complexity (PL)
BR-SGDm
UBV
22 (cd+1//n)
(Karimiredy at. 2021; 2022)
be
(Kariminally et all. 2021)
BR-MVR
UBV
22
/V6543/n
Hom, data,
(Gerbunov et al., 202
BTARD-SGG
UB
2 +
2aa Che
nbe4
2 nape
2 be 9) C-bbu
compr.
Byrd- Sard (7)
Smooth fig
m 62
m
(Wu al., 2020)
26
Byz-VR-MARINA Cor, E.1 & Cor. E.5
As. 2.4
BR-SGDm
UBV
+ +
(Karinieddy et all, 2022)
be
data,
Byrd-SAGA SAGA (213)
Smooth fi.j
x
D4 m2
compr.
(Wu al., 2020)
25
Byz-VR-MARINA C1/4 Cor, F.2 & Car. E.6
14y
abm'n (1+ 1 F
(1+
As. 2.4
BR-CSGD 1515
UBV. BG
(Zhu & ing, 2001)
n2
BR-CSAGA (2:23)
Smooth fuj UBV, BG
Ling, 2021)
X
(1-
data, compr.
BROADCAST (2MBU5)
(1-2288/2
Smooth figj
(Zhu Ling. 2021)
21 26)
1- +w
11
ByZ-VR-MARINA C1165) Cor. F.3 & Cor. E.7
As. 2,4
(++))++
(1++0++++)
/PP + (
ID Gorbanov et (2021a) assume additionally that Although the analyses by Wa at. (2020); Zhu Ling (2021) support inexact geometric median computation, for simplicity of presentation, we assume that goometric median is computed exactly.
noise distribution stochastic gradients suh-quudratic.
(9) BR-SGDm: e² Mosc"); y; Byrd- e = ((("/(uP( ()) ByZ-VR-MARINA:
= 9mmax (m/6, + w)oo(() for
general non-convex case and e = Qimax (m/6, + jedc" /vx) for the case of Pt functions (with w = 0, where there no compression);
BR CSGD: = A](e² c D Pa 28)2)) (positive even when ç² = Oy; BR CSAGA: = a((c? W// 26)
(positive even when ç = 0): BROADCAST: e = -0(0=w>>//e> /t=( 2:)
The term midex is proportional to much smaller Lipschitz constant than the term 69/22 does. A similar statement holds in PL case as be
well.
(5) For this result 7hu & I ing (2021) assume that 28: which is very restrictive assumption when A 0. For example, 322-12-28-T
for well conditioned problems with e/t. 1003 and 8 0 (no Byzantine workers), this bound implies that should larger than 10-7, Such value of corresoonds to almost noa-compressed commumication..
The term /o(((()
.T+u is proportional to much smaller Lipschitz constant than the term 1+ (e(
does. A
Vpnc?
similar statement holds Pt. case as well.
( The rate is derived under the strong convexity assumption. Strong convexity impliss PL-condition but not vice versa: there exist non-convex Pulunccions (Karimi el al., 2016).
(Lyu et al., 2020), we make no assumptions on the malicious workers B, i.e., Byzantine workers are allowed to be omniscient. Our main contributions are summarized below.
New method: BYZ-VR-MARINA. We propose a new Byzantine-robust variance-reduced method with compression called ByZ-VR-MARINA (Alg. 1). In particular, make VR-MARINA (Gorbunov et al., 2021b), which is a auriance-reduce method with compression, applicable to the context of Byzantine-tolerant distributed learning via using the recent tool of robust agnostic aggregation of Karimireddy et al. (2022). As Tbl. I shows, BYZ-VR-MARINA and our analysis of the method leads to several important improvements upon the previously best-known methods.
New SOTA results. Under quite general assumptions listed in Section 2, we prove theoretical convergence results for ByZ-VR-MARINA in the cases of smooth non-convex (Thm. 2.1) and Polyak-
4

---

Published as a conference paper at ICLR 2023
Lojasiewicz (Thm. 2.2) functions. As Tbl. 2 shows, complexity bounds in the non-convex are always better than previously known ones when the target accuracy e is small enough. In the PE. results improve upon previously known guarantees when the problem has bad conditioning or when & is small enough. Moreover, we provide the first theoretical convergence guarantees for Byzantine-tolerant methods with compression in the non-convex case for arbitrary adversaries.
Byzantine-tolerant variance-reduced method with tight rates. Our results are tight, i.e., when there are Byzantine workers, our rates recover the rates of VR-MARINA, and when addition- ally no compression is applied, we recover the optimal rates of Seeom-SARAH (Horváth et al., 2022WPAGE (Li al., 2021). In contrast, this is not the case for previously known variance- reduced Byzantine-roben robust methods such as Byrd-SAGA, BR-CSAGA, and BROADCAST that in the homogeneous data scenario have worse rates than single-mache machine SAGA.
Support of the compression without strong assumptions. As we point out in Tbl. 2, the analysis of BR-CSGD and BR-CSAGA relies on the bounded second- moment assumption, which contradicts strong convexity, and the rates for BROADCAST are derived under the assumption that the compres- sion operator almost coincides with the identity operator, meaning that practice workers essentially do not use any compression. In contrast, our analysis does not have such substantial limitations.
Enabling non-uniform sampling. In contrast to the existing works on Byzantine-robusttess our analysis supports non-uniform sampling of stochastic gradients. Considering the dependencies smoothness constants, one can quickly notice our rates' even more significant superiority compared to the previous SOTA results.
2 BYZ-VR-MARINA: BYZANTINE-TOLERANT VARIANCE REDUCTION WITH COMMUNICATION COMPRESSION
We start by introducing necessary definitions and assumptions.
Robust aggregation. One of the main building blocks of our method relies on the notion of (6, c)- Robust A Aggregator introduced in (Karimireddy et al., 2021; 2022).
Definition 2.1 ((6, c)-Robust Aggregator). Assume that { "r1,,, En. is such that there exists a subset G C []] of size G = G Z (1 - 6)n for 5 < 0.5 and there exists 2 O such that GIG-T) Enee [[[|=; - xı 21 o² where the expectation is taken w.r.t the randomness of {æelieg- We say that the quantity & is (5, c)-Robust Aggregator ((5, c)-RAgg) and write T = RAgg(a,, x.)
for some e > 0, if the following inequality holds:
E [I| - [ S cōo²,
(2)
where == 1 Eieg Ts. If additionally T is computed without the knowledge of o², we say that is To (6, -)-nostii Robust Aggregator ((ō, c)g) and write 3 ARAgg(an........)
In fact, Karimireddy et al. (2021; 2022) propose slightly different definition, where they as- sume that E| x2|12 < o² for all fixed good workers i, G, which is marginally stronger than what we assume. Karimireddy et al. (2021) prove tightness of their definition, i.e., up to the constant one cannot improve bound (2), and prove that popular "middle-seekers" such as Krum (Blanchard et al., 2017), Robust Federated Averaging (RFA) (Pillutla et al., 2022), and Coordi naaee--ttee-e wise Median (CM) (Chen et al., 2017) do not satisfy their definition. However, there is trick called bucketing (Karimireddy al., 2022) that provably robustifies Kr Krum/RFA/CM Nevertheless, the difference between our definition and the original one from (Karimireddy et al., 2021; 2022) is very subtle and it turns out that Krum/RFA/CC with bucketing fit Definition 2.1 as well (see Appendix D).
Compression. We consider unbiased compression operators, i.e., quantizations.
Definition 2.2 (Unbiased compression (Horváth et al., 2019b)), Stochastic mapping Q : Rdd - Rd
called unbiased compressor/coopression operator if there exists w Z 0 such that for any x. E R
E [[(x)) x. E [1[((x) x S =
(3)
For the given unbiased compressor Q(x). one can define the expected density as So supzerd E. [l)) where l!vllo is the number of non-zero components y E IRd.
=
5

---

Published as a conference paper at ICLR 2023
The above definition covers many popular compression operators such RandK sparsification (Stich et al., 2018), random dithering (Goodall, 1951; Roberts, 1962), and natural compression (Horváth et al., 2019a) (see also the summary of various compression operators in (Beznosikov et al., 2020)). There exist also other classes of compression operators such as 8-contractive compressors (Stich al., 2018) and absolute compressors (Tang al., 2019; Sahu et al., 2021). However, these types of compressors are out of the scope of this work.
Assumptions. The first assumption is quite standard in the literature on non-convex optimization. Assumption 2.1.
We assume that function f Bd - R is L-smooth, i.e., for all x, E RR we have -Vf(z)-Vf(y) f & -||x- yll. Moreover, we assume that f is uniformly lower bounded by f. E R. i.., f. = inf f(x).
Next, we need to restrict the data heterogeneity of regular workers. Indeed, arbitrarily heteroge- neous scenario, it is impossible to distinguish regular workers and Byzantine workers. Therefore, use a quite standard assumption about the heterogeneity the local loss functions.
Assumption 2.2 (52 -eterrogeeeitt). We assume that good clients have Çe-heterogeneous local loss functions for some Ç 2 0, i.e.,
(V)()))
V((r) Vo E
(4)
G 3E9
We emphasize here that the homogeneous data case (C = 0) is realistic in collaborative learning. This typically means that the workers have an access the entire data. For example, this can be implemented using so-called dataset streaming when the data is received just in time in chunks (Diskin et al., 2021: Kijsipongse et al., 2018) (this can also be implemented without using the server via special protocols similar to BitTorrent).
The following assumption a refinement of a standard assumption that fi is L.-smooth for all e G. Assumption 2.3 (Global Hessian variance assumption (Szlendak al., 2021)). We assume that there exists L 2 0 such that for all æ, E Rdd
V-WW v(()
L2 yll
(5)
G
iEG
Ji is L4-smooth for all E G. then the above assumption always valid for some L+ 2 such that 1 - 1,2 < 12 < ag. where L.2g è E.eo L (Szlendak et al., 2021). Moreover, Szlendak et al. (2021) show that there exist problems with heterogeneous functions on workers such that (5)
holds with L+ 0. while Lavg 0.
We propose a generalization of the above assumption for samplings stochastic gradients.
Assumption 2.4 (Local Hessian variance assumption). We assume that there exists L. such that for all y E gd
C
Σ E| (2, v) Ai(a, w)
y11
(6)
b
EEG
where Ae(x,) v) (f)()) and Âi(2, v) an unbiased mini-batched estimator of De(x, y) with batch size b.
We notice that the above assumption covers wide range of samplings of gradient differences, e.g., standard uniform sampling or importance sampling. We provide the examples Appendix E. We notice that all previous works on Byzantine focus on the standard uniform sampling only. However, uniform sampling can give times worse constant L3 than importance sampling. This difference significantly affect the complexity bounds.
stochastic
New Method: Byz-VR-MAPER Variance-Redunn MARINA (Byz-VR-MARINN)
Now we ready to present new m Byzantine-tolerant
Our algorithm based on the recently proposed varicede-reduced method with compression (VR- (VR-MARINA) from (Gorbumov et al., 2021b). At each iteration of SyZ-VR-MARINA good workers update their parameters &++1 = =² - 7g using esti- mator g² received from the parameter-server (line 7). Next (line 8), with (typically small) probability

---

Published as a conference paper at ICLR 2023
p each good worker i G computes its full gradient, and with (typically large) probability - p this worker computes compressed mini-batched stochastic gradient difference 2 (a 1 x²)), where
(x ,²)) satisfies Assumption 2.4, After that, the server gathers the results computations from the workers and applies (6, c)-ARggg to compute the next estimator gx+l (line 10).
Let us elaborate on several important parts of the proposed algorithm. First, we point out that with large probability 1 - good workers need to send just compressed vectors 2(A, ,x"),, i G. Indeed, since the server knows when workers compute full gradients and when they compute compressed stochastic gradients, it needs just to add g to all received vectors to perform robust aggregation from line 10. Moreover, since the server knows the type of compression operator that good workers apply, it can typically easily filter out those Byzantine workers who try to slow down the training via sending dense vectors instead of compressed ones (e.g., if the compression operator is RandK sparsification, then Byzantine workers cannot send more than K components; otherwise they will be easily detected and can be banned). Next, the right choice of probability p allows equalizing the communication cost of all steps when good workers send dense gradients and compressed gradient differences. The same true for oracle complexity: if S h/m, then the computational cost of full-batch computations is not bigger than that of stochastic gradients.
Algorithm Byz-VR-MARINA Byzantine-tolerant VR-MARINA
I: Input: starting point z0, stepsize 7, minibatch size b, probability E (0, 1], number of iterations K. (6, c)-AAgg
2: Initialize g
fxx
3: for = 0, 1, K do
4: Get sample from Bernoulli distribution with parameter pt Be(p)
5: Broadcast g², c to all workers
6: for E G in parallel do
7:
xk+1_ x 7
V (z( n Q (Ai(oht1, (a)) otherwise," where minibatched estimator
cf =
8: Set 9r k+1
(att1 )x) of ff(*++1)) vff((*);; Q(-) for i G are computed independently
9: end for
10: gh+l ARAgg(o) k+1 ..... 1
11: end for
12: Return: ik chosen uniformly random from {>*)K=) K-1 Tk=0
Challenges in designing variance-reduced algorithm with tight rates and provable Byzantine- robustness. In the introduction, we explain why variance reduction is natural way to handle Byzantine attacks (see the discussion before Q1). At first glance, it seems that one can take any variance-reduced method and combine with some robust aggregation rule to get the result. However, this is not straightforward it may appear. As can see from Table 2, combination of SAGA m²
with geometric median estimator (Byrd-SAGA) gives the rate Ö (1F (smoothness constant
and logarithmic factors are omitted) in the smooth strongly convex case - this rate is in fact O 62 times worse than the rate of SAGA even when Å 0. Therefore, it becomes clear that the full potential of variance reduction in Byzantine-robus learning is not revealed via BArd-SAGA.
The key reason for that is the sensitivity of SAGA (and SAGA-based methods) to the unbiasedness of the stochastic estimator the analysis. Since Byrd-SAGA uses the geometric median for the aggregation, which is necessarily biased, it is natural that it has much worse convergence rate than SAGA even the = 0 case. Moreover, one can't an't solve such an issue by simply changing one robust estimator for another since all known robust estimators generally biased.
To circumvent this issue, we consider 2019; Li et al., 2021) and study how it interacts with the robust aggregation. In particular, we observe that the averaged pair-wise variance for the stochastic gradients of good workers could be upper bounded by constant multiplied by B||a*+1 I x²1 plus some additional terms appearing due to heterogeneity (see Lemma E.2). Then, we notice that the robust aggregation only leads to the additional term proportional to [ x (plus additional terms due to heterogeneity). We
SAiiI--AAAAAAAA----aan estimator (Horváth & Richtárik,
7

---

Published as a conference paper at ICLR 2023
show that this term can be directly controlled using another term proportional - -B|x 1 1=1 which appears in the original analysis of PAGE/VR-MARINA.
These facts imply that although the difference between DAZ-VR-MARRING and VR-MARINA is only in the choice the aggregation rule, is not straightforward beforehand that such a combination show next, obtain vast improvements upon the previously best-known theoretical results for Byzantine-toles
should be considered and that it will lead to better rates. Moreover, torantine-tolerant learning.
General Non-Convex Functions. Our main convergence result for general non-convex functions follows. All proofs are deferred to Appendix E.
Theorem 2.1. Let Assumptions 2.1, 2.2, 2.3, 2.4 hold. Assume that <> S [10(1++]]
L+VA' where
A =
6(1-p)
A0B pp++
[wL²+
6(1-p)
+ w L Then for all Z 26
2G
h
the point EKK choosen uniformly at random from the iterates x., x0,x,, ,..,...,e K produced by Byz-VR- MARINA satisfies
,...,
24.
24c65²
[IV](E 11
7(K
p
where Do - f( -11 f= and E[|] denotes the full expectation."
We highlight here several important properties of the derived result. First of all, this is the first theoretical result for the convergence of byzzaninnetolerant methods with compression in the non- convex case with arbitrary adversaries. Next, when Ç > 0 the theorem above does not guarantee that [[IV/((*)) )|]] can be made arbitrarily small. However, this is not drawback of our analysis but rather an inevitable limitation all algorithms in heterogeneous case. This is due to Karimireddy et al. (2022) who proved lower bound showing that in the presence of Byzantine workers, all algorithms satisfy EIll ( ] = )(o(²), i.e., the constant term from (7) is tight up to the factor of 1/p. However, when Ç 0, BYZ-VR-MARINA can achieve any predefined accuracy of the solution, if 8 is such that ARAgq is (6, co-rouust (see Theorem D.1). Finally, as Table shows?, ByZ-VR-MARINA achieves / )|²] < e² faster than all previously known Byzantine-toleran methods for small enough e. Moreover, unlike virtually all other results in the non-convex case, Theorem 2.1 does not rely on the uniformly bounded variance assumption, which known to be very restrictive (Nguyen et al., 2018). For further discussion refer to Appendix E.5.
Functions Satisfying Polyak-Lon Lojysa--oojsiewizz (PL) Condition. We extend our theory to the functions satisfying
condition (Polyak, 1963; Eojasiewicz, 1963). This assumption gen- eralizes regular strong convexity and holds for several non-convex problems (Karimi et al., 2016). Moreover, very similar assumption appears in over over- parameterizee deep learning (Liu et al., 2022).
Assumption 2.5 (PL condition). We assume that function f satisfies tion with parameter μs ie., for all a E Bdd there exists x² argmin a f(x) such that
(PL) condi-
|V 2 2μ (f(x) - f(x)).
(8)
Under this and previously introduced assumptions, we derive the following result.
Theorem 2.2. Let Assumptions 2. 1, 2.2, 2.3, 2.4, 2.5 hold. Assume that 0 < S min L /2A
Tu
where A 6(1-p)
408
wL² + (++))c3
6(1-))
[408(1+w) +
w 26
L3 Then for all
2G
K 2 the iterates produced by Byz-VR- satisfy
E [f(x*) f(x*)] & < - yu) 2 24c8
where Po = - 27 11 -1
In all the results and the proofs. El-] denotes the full expectation if the opposite is not specified.
"To have a fair comparison, we take p min("/m, 1/(L+w)) since in this case, each iteration each worker sends ((Ca) components, when w + ((/cc) (which is the case for RandK sparsification and f2 f2-quantization, see (Beznosikov et al., 2020)), and makes O(b) oracle calls in expectation (computations of (z)) With such choice of p. the total expected (communication and oracle) cost of steps with full gradients compurations/uncomprssce communications coincides with the total cost of the rest of iterations.
8

---

Published as a conference paper at ICLR 2023
g
120
101
130
Figure I: The optimality gap f(x²) of 3 aggregation rules (AVG, CM, RFA) under 5 attacks (NA, LF, BF, ALIE, IPM) on a9a dataset, where each worker has access full dataset with 4 good and 1 Byzantine worker. In the first row, we do not use any compression, in the second row each method uses RandK sparsification with K 0.1d.
Similarly to the general non-convex case, in the PE.-setting ByZ-VR-MARINA able to achieve = O (cac")n /n) accuracy, which matches (up to the factor of 1/p) the lower bound from Karimireddy et al. (2022) derived for j--ttrongly conver objectives. Next, when Ç = 0, Byz-VR- MARINA converges linearly asymptotically to the exact solution. Moreover, as Table 2 shows, our convergence result in the Pt.setting outperforms the known rates in more restrictive strongly-conver setting. In partieular, when E is small enough, ByZ-VR-MARINA has better complexity than BTARD- SGD. When the conditioning of the problem is bad (i.e., L/p= > 1) our rate dominates results of BR-CSGD, BR-CSAGA, and BROADCAST. Furthermore, both BR-CSGD and BR-CSAGA rely on the uniformly bounded second moment assumption (contradicting the strong convexity), and the rate of the BROADCAST algorithm based on the assumption that w O(H /L²) implying that (xx) 2 x (no compression) even for well-conditioned problems.
- (x=x)] B[f(=*)=
NUMERICAL EXPERIMENTS
In this section, we demonstrate the practical performance of the proposed method. The main goal of our experimental evaluation is to showcase the benefits of employing SOTA variance reduction to remedy the presence of Byzantine workers. For the task, we consider the standard logistic regression
model with Ez-reullarization fig (z)) = - Vi.j log(h(z, ((.)) - (1 yK.s) log(1 - ((r, as.s) ) + | where Vi.j E {0. 1} is the label. 0t.j E IR represents the features vector, À is the regularization parameter and h(x, a) = 1/(1+e-=Ta *)). One can show that this objective is smooth, and for À > 0, it also strongly convex, therefore, it satisties Plcondition. We consider a9a LIBSVM dataset (Chang & Lin, 2011) and set À= = 0.01. In the experiments, we focus on an important feature of Byz-VR- MARINA: it guarantees linear convergence for homogeneous datasets across clients even in the presence of Byzantine workers, as shown in Theorem 2.2. To demonstrate this experimentally, we consider the setup with four good workers and one Byzantine worker, each worker can access the entire dataset, and the server uses coordinate-wis median with bucketing as the aggregator (see the details in Appendix D). We consider five different attacks: + No Attack (NA): clean training; o Label Flipping (LF): labels are flipped, i.c., V/., - Yi.z Bit Flipping (BF): Byzantine worker sends an update with flipped sign; A Little is enough (ALIE) (Baruch et al., 2019): the Byzantine workers estimate the mean Ag and standard deviation dg of the good updates, and send jg 20g to the server where 2 is small constant controlling the strength of the attack; Inner Product Manipulation (IPM) (Xie et al., 2020): the attackers send - - V (((()) where controls the strength of the attack. For bucketing, we use = 2, i.e., partitioning the updates into the groups of two, as recommended by Karimireddy et al. (2022). We compare our ByZ-VR-MARINA with the baselines without compression (SGD, BR-SGDm (Karimireddy et al.. 2021)) and the basclines with random sparsification (compressed SGD and DIANA (BR-DIANA). We do not compare against Byrd-SAGA (and BR-CSAGA, BROADCAST from Zhu & Ling (2021)), which consumes large memory that scales linearly with the number of local data points and is not well suited for memory- efficient batched gradient computation (e.g., used in PyTorch). Our implementation is based on PyTorch (Paszke et al., 2019). Figure showcases that, indeed, we observe linear convergence of our method while no baseline achieves this fast rate. In the first row, display methods with no compression, and in the second row, each algorithm uses random sparsification. We defer further details and additional experiments with heterogeneous data Appendix B.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank anonymous reviewers for useful suggestions regarding additional experiments and dis- cussion of the derived results. The work of E. Gorbunov was partially supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Gov- ernment of the Russian Federation in accordance with the subsidy agreement (agreement identifier (00000D33332 (P5Q00022) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00133 The work of P. Richtárik was partially supported by the KAUST Baseline Research Fund Scheme and by the -AAST Center of Excellence in Data Science and Artificial Intelligence.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017.
Dan Alistarh, Zeyuan Allen-Zhi and Jerry Li. Byzantine stochastic gradient descent. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 44188446222 2018.
Zeyuan Allen-Zin -hu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):819-882) 2017.
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex
stochastic gradient descent. In International Conference on Learning Representations, 2021. URL
https:// //tppr/eeeeeeeeeeeeeeeeee net doorum?iddPbBiqrree..
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Osparse-local-sgde Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint arX1v.1810.05291, 2018.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 124.0 2020.
Aleksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, and Alexander Gasnikov. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. arXiv preprint arXiv:2110.03311 2021.
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. arXiv preprint arXiv:2202.07262. 2022.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM
transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. In International Conference on Machine Learning, pp. 903-912. PMLR, 2018.
10

---

Published as a conference paper at ICLR 2023
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 122):1225,22 2017.
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Georgios Damaskinos, El-Mahdi El-Mhamdi, Rachid Guerraoui, Ausany Guirguis, and Sébastien Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. Proceedings of Machine Learning and Systems, 1:8 1:81- 2019.
Marina Danilova and Eduard Gorbunov. Distributed methods with absolute compression and error compensation. arXiv preprint arXiv:2203. 02388, 2022.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
Michael Diskin, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, Anton Sinitsin, Dmitry Popov, Dmitry V Pyrkin, Maxim Kashirin, Alexander Borzunov, Albert Villanova del Moral, et al. Distributed deep learning in open collaborations. Advances in Neural Information Processing Systems, 34:7879-7899 2021.
El Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyên Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, hetero- geneous, asynchronous and nonconvex learning). Advances in Neural Information Processing Systems, 34:25044-25000 2021.
Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M Roy, and Ali Ramezani-Kebrya. Adaptive gradient quantization for data- mata-parallel sgd. Advances in neural information processing systems, 13:3174-3183 2020.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic inttgrateeet differential estimator. Advances Neural Information Processing Systems, 31, 2018.
Avishek Ghosh, Raj Kumar Maity, and Arya Mazumdar. Distributed newton communicate less and resist byzantine workers. Advances in Neural Information Processing Systems, 33: 18038- 2020.
Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ranchandran. Conmunication-efficienn and byzantine-robust distributed learning with error feedback. IEEE Journal on Selected Areas in Information Theory, 2(3):942-955 953, 2021.
WM Goodall. Television by pulse code modulation. Bell System Technical Journal, 30(1):33 1951.
Eduard Gorbunov, Adel Bibi, Ozan Sener, El Houcine Bergou, and Peter Richtárik. A stochastic derivative free optimization method with momentum. International Conference on Learning Representations, 2020a.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging етror compensated sgd. Advances in Neural Information Processing Systems, 33:20889-20990 2020b.
Eduard Gorbunov, Alexander Borzunov, Michael Diskin, and Max Ryabinin. Secure distributed training at scale. arXiv preprint arXiv:2106.11257 2021a.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- сonvex distributed learning with compression. In International Conference on Machine Learning, pp. 3788-3798. PMLR, 2021b.
Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance- methods for machine learning. Proceedings of the IEFF, 108(1 1911111):96899999 1983, 2020.
11

---

Published as a conference paper at ICLR 2023
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pp. 5209. PMLR, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: /rXivv:706..0B 706.02677, 2017.
Rachid Guerraoui, Sébastien Rouault, al. The hidden vulnerability of distributed learning in byzantium. In International Conference on Machine Learning, pp. 3521-3530. PMLR, 2018.
Nirupam Gupta and Nitin H Vaidya. Byzantine fault-tolerance in peer-to-peer distributed gradient- descent. arXiv preprint arXiv:2101. 12316, 2021.
Nirupam Gupta, Thinh T Doan, and Nitin H Vaidya. Byzantine fault-tolerance in decentralized optimization under 2f-redundancy. 202/ American Control Conference (ACC), pp. 3632-3637. IEEE, 2021.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2350-2358. PMLR, 2021.
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine-robust decentralized learning via self-centered clipping. arXiv preprint arXiv:2202.01545, 2022.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In International Conference on Machine Learning, pp. 2781-2789. PMLR, 2019.
Samuel Horváth, Chen-Yu Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint 1XXX:v1905..0090 2019a.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:/904.05//5 2019b.
Samuel Horváth, Lihua Lei, Peter Richtárik, and Michael I. Jordan. Adaptivity of stochastic gradient methods for nonconvex optimization. SIAM Journal on Mathematics of Data Science, 4(2): 634 648, 2022. doi: 10. 00.1137/11M1994308.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. In International Conference on Machine Learning, pp. 4617-4628. PMLR, 2021.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-21 1100 2021.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
gradient methods under the
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3262-3261. PMLR, 2019.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference Machine Learning, pp. 5311 5311-5319. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2023
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robuss learning on heterogeneous datasets via bucketing. International Conference on Learning Representations, 2022.
Ekasit Kijsipongse, Apivadee Piyatumrong, et al. A hybrid gpu cluster and volunteer computing platform for scalable deep learning. The Journal of Supercomputing. 74(7):32363326,, 2018.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European conference on computer vision, pp. 491-507. Springer, 2020.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp.
PMLR, 2019.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-PPrty Machine Learning Workshop, 2016.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, and Sebastian Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference Artificial Intelligence and Statistics, pp. 4087-4092 PMLR, 2021.
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trunsactions Programming Lunguages and Systems, 4(3):382-401, 1982.
Guanghui Lan and Yi Zhou. An optimal randomized incremental gradient method. Mathematical programming, 171(1):167-2) 165-11,, 2018.
Guanghui Lan, Zhize Li, and Yi Zhou. A unified variance-reduced accelerated gradient method for convex optimization. Advances in Neural Information Processing Systems, 32, 2019.
Chuan Li. Demystifying gpt-3 language model: A technical overview, 2020. "https://
lambdalabs wwwcccomooooooo ctt//bllo///eyyaa........n.
Zhize Li and Peter Richtárik. Canita: Faster rates for distributed convex optimization with communi-
cation compression. Advances in Neural Information Processing Systems, 34, 2021.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, pp. 5895-5900 PMLR, 2020.
Zhize Li. Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp. 6286 6295. PMLR, 2021.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
Stanislaw Eojasiewicz. A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117:87-89, 1963.
Lingjuan Lyu, Han Yu, Xingjun Ma, Lichao Sun, Jun Zhao, Qiang Yang, and Philip S Yu. Privacy and robustness in federated learning: Attacks and defenses. arXiv preprint arXiv:2012.06337, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Aguera y Arcas. Communication-efficinn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Hiroaki Mikami, Hisahiro Suganuma, Yoshiki Tanaka, Yuichi Kageyama, et al. Massively distributed sgd: Imagenet/resnet-50 training flash. arXiv preprint 1rXiv:1871.05233 2018.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 0ete:-901909999 2019.
13

---

Published as a conference paper at ICLR 2023
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341 2012.
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. Sgd and hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pp. 3750-3758. PMLR, 2018.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, pp. 2613-2621. PMLR, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing. 69(2):117-124, 2009.
Jie Peng, Weiyu Li, and Qing Ling. Byzantine-robust decentralized stochastic optimization over static and time-van coae-varying networks. Signal Processing, 183:108020, 2021.
Constantin Philippenko and Aymeric Dieuleveut. Preserved central model for faster bidirectional compression in distributed settings. Advances in Neural Information Processing Systems, 34, 2021.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70:1 10:1142-1154, 2022.
Boris T Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 878, 1963.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa-
tional mathematics and mathematical physics, 4(5): 1964.
Xun Qian, Zheng Qu, and Peter Richtárik. SAGA with arbitrary sampling. In International Conference on Machine Learning. pp. 5190-5199, PMLR, 2019.
Xun Qian, Zheng Qu, and Peter Richtárik. L-SVRG and L-Katyusha with arbitrary sampling. Journal of Machine Learning Research, 22:1-49, 2021a.
Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accelerated. Advances in Neural Information Processing Systems, 34, 2021b.
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling I: Algorithms and complexity. Optimization Methods and Software, (1(5):829-883 000--877222 2016.
Shashank Rajput, Hongyi Wang. Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy-
based framework for faster and more robust gradient aggregation. Advances in Neural Information Processing Systems, 32, 2019.
Jayanth Regatti, Hao Chen, and Abhishek Gupta. ByGARS: Byzantine SGD with arbitrary number of attackers. arXiv preprint arXiv:2006. 13421, 2020.
Peter Richtárik and Martin Takáč. On optimal probabilities in stochastic coordinate descent methods. Optimization Letters, 10(6): 123-1 2016.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster emor feedback. Advances in Neural Information Processing Systems, 34, 2021.
Lawrence Roberts. Picture coding using pseudo-random noise. IRE Transactions on Information Theory, 1455544 1962.
Nuria Rodríguez-Barroso, Eugenio Martinez-Cámara, M Luzón, Gerardo González Seco, Miguel Ángel Veganzones, and Francisco Herrera. Dynamic federated learning model for identify- ing adyersarial clients. arXiv preprint arXiv:2007. 15030, 2020.
14

---

Published as a conference paper at ICLR 2023
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. Fednl: Making newton- typt methods applicable to federated learning. arXiv preprint arXiv:2106.02969 2021.
Atal Sahu, Aritra Dutta, Ahmed M Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification total error minimization. Advances in Neural Information Processing Systems, 34, 2021.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(():83-11) 1128 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association. Citeseer, 2014.
Sebastian U Stich, Lean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems, 31, 2018.
Lili Su and Nitin H Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In Proceedings of the 2016 ACM symposium on principles of distributed computing. pp. 425-434, 2016.
Ananda Theertha Suresh, Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International Conference Machine Learning, pp. 3329-3337. PMLR, 2017.
Rafal Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:21 2021.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning, pp. 6155-6165, 2019.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.
Endre Weiszfeld. Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Mathematical Journal, First Series, 43:355-386, 1937.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583 2020.
Cong Xie, Oluwasammi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270. PMLR, 2020.
Xinyi Xu and Lingjuan Lyu. Towards building a robust and fair federated learning system. arXiv preprint arXiv:2011. 2020.
Zhixiong Yang and Waheed U Bajwa. Bridge: Byzantine-resilicn decentralized gradient descent. arXiv preprint arXiv: 08098, 2019a.
Zhixiong Yang and Waheed U Bajwa. Byrdie: Byzantine-resilien distributed coordinate descent for decentralized learning. IEEE Transactions on Signal and Information Processing over Networks, (4):611-627, 2019b.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robuse distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
15

---

Published as a conference paper at ICLR 2023
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsich. Large batch optimization for deep learning: Training bert in 76 minutes. International Conference Learning Representations. 2020.
Heng Zhu and Qing Ling. Broadcast: Reducing both stochastic and compression noise to robustify coamuunication-fficieet federated learning. arXiv preprint arXiv:2104.06685, 2021.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. Advances in neural information processing systems, 23, 2010.
16

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
ByZ-VR-MARINA: Teyanninn-Toleraan Variance Reduction with Communication Com- pression
3 Numerical Experiments
Detailed Related Work
18
B Extra Experiments and Experimental details
19
B.1
General setup
19
B.2
Experimental setup
21
B.3 Extra Experiments
B.3.1
Heterogeneous Data
21
B.3.2
Compression
B.3.3
Extra dataset: w8a
22
B.4
Comparison with Byrd-SVRG
22
B.5 Effect of compression
22
Useful Facts
24
D Further Details on Robust Aggregation
25
E Missing Proofs and Details From Section 2
28
E.1 Examples of Samplings
................................
28
E.2 Key Lemmas
29
E.3 General Non-Convex Functions
33
E,4 Functions Satisfying Polyak-Lojasiewicz Condition
37
E.5 Further Details the Obtained Results and the Comparison from Table 2
41
17

---

Published as a conference paper at ICLR 2023
A DETAILED RELATED WORK
Byzantinerrobustess.. Classical approaches to Byzantine-tolerant optimization are based on ap- plying special aggregation rules Parallel-SCa (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Damaskinos et al., 2019; Guerraoui et al., 2018; Pillutla et al., 2022). It turns out that such defences are vulnerable to the special type of attacks (Baruch et al., 2019; Xie et al., 2020). Moreover, Karimireddy et al. (2021) propose a reasonable formalism for describing robust aggregation rules (see Def. 2.1) and show that almost all previously known defences are not robust according to this formalism. In addition, they propose and analyze new Ryzantinettolerant methods based on the usage of Polyak's momentum (Polyak, 1964) (BR-SDG) (DDG) and momentum variance reduction (Cutkosky & Orabona, 2019) (BR-MVR). This approach is extended to the case of heterogencous data and aggregators agnostic to the noise level by Karimireddy et al. (2022), and He et al. (2022) propose an extension to the decentralized optimization over fixed networks. Gorbunov et al. (2021a) propose an alternative approach based on the usage of AllReduce (Patarasuk & Yuan, 2009) with additional verifications of correctness and show that their algorithm has complexity not worse than Parallel- SGD when the target accuracy is small enough. Wu et al. (2020) are the first who applied variance reduction mechanism to tolerate Byzantine attacks (see the discussion above Q1). We also refer reader to (Chen et al., 2018; Rajput et al.. 2019; Setriguuz--Baroose et al., 2020; Xu & Lyu, 2020; Alistarh et al., 2018; Allen-Zhu et al., 2021; Regatti et al., 2020; Yang & Bajwa, 2019a;;; Gupta et al., 2021; Gupta & Vaidya, 2021; Peng et al., 2021) 1) for other advances in Byzantine- (see the detailed summaries in (Lyu et al., 2020; Gorbunov et al., 2021a)). We further progress the field by obtaining new theoretical SOTA convergence results in our work.
Compressed communications. Methods with compression are relatively well studied in the lit- erature. The first theoretical results were derived in (Alistarh et al., 2017; Wen al., 2017; Stich et al., 2018; Mishchenko et al., 2019). During the last several years the field has been significantly developed. In particular, compressed methods are analyzed in the conjuction with variance reduc- tion (Horváth et al., 2019b; Gorbunov et al., 2020b; Danilova & Gorbunov, 2022), acceleration (Li al., 2020; Li & Richtárik, 2021; Qian et al., 2021b), decentralized communications (Koloskova et al., 2019; Kovalev et al., 2021), local steps (Basu et al.. 2019; Haddadpour et al., 2021). adaptive compression (Faghri al., 2020), second-order methods (Islamov et al., 2021: Safaryan et al., 2021), and min-max optimization (Beznosikov et al., 2021; 2022). However, to our knowledge, only one work studies communication compression the context of Byzantine- robustness (Zhu & Ling, 2021) (see the discussion above Q2). Our work makes further step towards closing this significant gap in the literature.
Variance reduction is powerful tool allowing to speed up the convergence of stochastic methods (especially when one needs to achieve a good approximation of the solution). The first variance- reduced methods were proposed by Schmidt al. (2017); Johnson & Zhang (2013); Defazio et al. (2014). Optimal variance-reduced methods for (strongly) convex problems are proposed in (Lan & Zhou, 2018: Alle 2017: Lan et al., 2019) and for non-convex optimization in (Nguyen et al., 2017; Fang et al., 2018; Li et al., 2021). Despite the noticeable attention to these kinds of methods (Gower et al., 2020), only a few papers study Byzantine-robustten
in conjunction with variance reduction (Wu et al., 2020; Zhu & Ling, 2021; Karimireddy et al., 2021). Moreover, we mentioned before, the results from Wu et al. (2020); Zhu & Ling (2021) are not better than the known ones for non non-parallel pariance-reduced methods, and Karimireddy et al. (2021) rely on the uniformly bounded variance assumption, which is hard to achieve in practice. In our work, we circumvent these limitations.
Non-uniform sampling. Originally proposed for randomized coordinate methods (Nesterov, 2012;
Richtárik & Takáč, 2016; Qu & Richtárík, 2016). non-uniform sampling is extended in multiple ways to stochastic optimization, e.g., see (Horváth & Richtárik, 2019; Gower et al., 2019; Qian et al., 2019; Gorbunov et al., 2020b;a; Qian et al., 2021a). Typically, non-uniform sampling of stochastic gradients allows better dependence on smoothness constants in the theoretical results. Inspired by these advances, we propose the first Byzantine-robust optimization method supporting non-uniform sampling of stochastic gradients.
18

---

Published as a conference paper at ICLR 2023
13
307
12
107
10-1
120
10-
00-
Figure 2: The optimality gap f(x*) fx=) of 3 aggregation rules (AVG, CM, REA) under 5 attacks (NA, LF, BF, ALIE, IPM) on a9a dataset with uniform split over 15 workers with 5 Byzantine workers. The top row displays the best performance in hindsight for a given attack.
101
101
320
spods
AKC
Age
120
10.1
13-
15-
220
g1
107
Figure 3: The optimality gap f(x)) f(x)) of aggregation rules (AVG, CM, RFA) under 5 attacks (NA, LF, BF, ALIE, IPM) on a9a dataset with uniform split over 15 workers with 5 Byzantine workers. The top row displays the best performance in hindsight for given attack. Each method uses Rand sparsification with K- = 0.1d.
B
EXTRA EXPERIMENTS AND EXPERIMENTAL DETAILS
B. GENERAL SETUP
Our running environment has the following setup:
19

---

Published as a conference paper at ICLR 2023
107
Figure 4: The optimality gap f(x²) fxx) of 3 aggregation rules (AVG, CM, RFA) under 5 attacks (NA, LF, BF, ALIE, IPM) on w8a dataset with uniform split over 15 workers with 5 Byzantine workers. The top row displays the best performance in hindsight for a given attack. No compression is applied.
1011
157
20-
13.
210
15"
134
15
331
210
Figure 5: The optimality gap f(**) f(=') of 3 aggregation rules (AVG, CM, RFA) under 5 attacks (NA, LF, BF, ALIE, IPM) on w8a dataset with uniform split over 15 workers with 5 Byzantine workers. The top row displays the best performance in hindsight for a given attack. Each method uses RandK sparsification with K = 0.1d.
24 CPUs: Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHZ,
GPU: NVIDIA TITAN Xp with CUDA version 11.3,
PoTorc version: 1.1....
20

---

Published as a conference paper at ICLR 2023
177
210
Figure 6: The optimality gap ffx-) of aggregation rules (AVG, CM, RFA) under 5 attacks (NA, LF, BF, ALIE, IPM) w8a dataset, where each worker has access full dataset with 4 good and I Byzantine worker. In the first row, we do not use any compression, in the second row each method uses RandK sparsification with K 0.1d.
B.2 EXPERIMENTAL SETUP
For each experiment, we tune the step size using the following set of candidates {0.5, 0.05, 0.005). The step size is fixed. We do not use learning rate warmup decay. We use batches of size 32 for all methods. 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 (Karimireddy et al., 2022) available at https: : // g thub. eep /byzant via anonymized repository https: : / / ////ttttttt thub. com
iwwoooiiddppppooo iei. zer. Our codes are available wt__y/aatttiiiiieeaeeeeae We select the same set of hyperparameters as (Karimireddy et al., 2022), i.e.,
RFA: the number of steps of smoothed Weisfield algorithm T 8; see Section D for details,
ALIE: small constant that controls the strength of the attack is chosen according to (Baruch et al., 2019).
IPM: small constant that controls the strength of the attack 0.1.
B.3 EXTRA EXPERIMENTS
B.3.1
HETEROGENEOUS DATA
In this case, we randomly shuffle dataset and we sequentially distribute it among 15 good workers, where each worker has approximately the same amount data and there no overlap. We include five Byzantine workers who have access to entire dataset and the exact updates computed each client. For the aggregation, we consider three rules: standard averaging (AVG), coordinate- wise median (CM) with bucketing, and robust federated averaging (RFA) with bucketing (see the details in Appendix D).
that momentum (BR-SGDm) the variance reduction (Byz-VR- MARINA) techniques consistently outperform the SGD baseline while none of them dominates for all the attacks. BYZ-VR-MARINA is particularly useful in the clean data regime and against the ALIE and IPM attacks, and the BR-SGDm algorithm provides the best performance for label and bit flipping attacks. would be interesting to automatically select the best technique, e.g., momentum or VR-MARINA, that provides the best defense against any given attack. We leave this for future work.
Discussion. In Figure 2,
B.3.2 COMPRESSION
In this section, we consider the same setup as for the previous experiment with a difference that we employ communication compression. We choose random unbiased sparsification for with sparsity level 10%. We compare our BYZ-VR-MARINA algorithm to compressed SGD and DIANA (BR- DIANA).
Discussion. In Figure 3, we can see that ByZ-VR-MARINA consistently outperforms both baselines except for the bit flipping attack. However, even in this case, it seems that ByZ-VR-MARINA only
21

---

Published as a conference paper at ICLR 2023
CM NA
ALE
10:2
10
SGD
SGD
BR-SGDm
BR-SGDm
Byz-VR MARINA
Byz-VR MARINA
Byrd-SVRG
Byrd-SVRG
10
15 epochs
20
25
30
10
20
25
30
epochs
Figure 7: The optimality gap f(**) f(x*) under 2 attacks (NA, ALIE) a9a dataset, where each worker has access full dataset with good and Byzantine worker. No compression is applied.
needs more epochs to provide the better solution while SGD cannot further improve regardless the number of epochs.
B.3.3 EXTRA DATASET: W8A
In Figures 4-6, we perform the same experiments, but for the different LIBSVM dataset:w8a, We note that the obtained results are consistent with our observations for the a9a dataset.
B.4 COMPARISON WITH Byrd-SVRG
As note in the main part of the paper, Byrd-SAGA is not well suited for PyTorch due to the large memory consumption of SAGA-based methods. Nevertheless, one can use SVRG-estimator (Johnson & Zhang, 2013) proxy of SAGA-estimator due to similarities between SAGA and SVRG. We call the resulting method as Byrd-SVRG and compare its performance with Byz- VR-MARINA the logistic regression task with non-convex regularization:
instance of (1) 14=? The results
with fz)(z) Vi. log(h(z, (:.))) (1 yı.j) log(1 h(,, a.,)) + + x?
are presented Figure 7. One can see that ByZ-VR-MARINA converges to the exact solution
asymptotically, while other methods are able converge only some neighborhood of the solution.
B.5 EFFECT OF COMPRESSION
In this experiment, we illustrate the effect of compression ByZ-VR-MARINA on its communication efficiency. We compare the performance of Byz-VR-MARiNA with and without compression in terms of the number of communicated bits between workers and server. The results are shown in Figure 8. One can see that communication compression does speed up the training (in terms of the number of transmitted bits).
22

---

Published as a conference paper at ICLR 2023
CM ALIE
10
ByZ-VR-MARINA
DI--VR-MARINAL - Rand10%
10-2
10-3
f(x)
10
10-5
0
15 Relative Comm. Complexity
5
10
20
Figure 8: The optimality gap f(**) f(x²) under ALIE attacks on a9a dataset, where each worker has access full dataset with 4 good and Byzantine worker. The figure illustrates the effect of compression in Byz-VR-MARINE operator. "Relative comm. compression" = number of transmitted bits divided by the number of transmitted bits per iteration for full-precision algorithm and then divided by the size of the dataset (when no compression is applied this quantity equals the number of epochs).
Rand sparsification with K = 0. 1d is used as compression
23

---

Published as a conference paper at ICLR 2023
C USEFUL FACTS
For all a, E Rd and a > 0,p E (0, 1] the following relations hold:
2(a, b)
||a|| + ||6|| - 1aaaa-a0 b11?
(10)
|| + b1(
(1 + a)) |a]l + (1 + a 0]]
(11)
|all + 1
|| bl|2
|bb
(12)
1+a
(1 - p) (1+2) & 1 1-
p
(13)
2
Lemma C.1 (Lemma 5 from Richtárik al. (2021)). Let a, b 0. 1f0 S s
then
Va40
ar² + by & 1. The bound is tight up to the factor of 2 since
Jato I min
{ 1
2
Va b
va+b"
24

---

Published as a conference paper at ICLR 2023
D FURTHER DETAILS ON ROBUST AGGREGATION
In Section 2, consider robust aggregation rules satisfying Definition 2.1. As notice, this definition slightly differs from original one introduced by Karimireddy al. (2022). In particular, we assume
Σ IJE
E
x1|l? s
(14)
G 1)
while Karimireddy et al. (2022) uses E1| - xı [|3] - a² for any fixed i, I E G. As we show next, this difference is very subtle and condtion (14) also allows to achieve robustness.
We consider robust aggregation via bucketing proposed by Karimireddy et al. (2022) (see Algo- rithm 2). This algorithm can robustify some non-robust aggregation rules Aggr. In particular,
Algorithm 2 BBcketiingg Robust Aggregation using bucketing (Karimireddy al., 2022)
1: Input: ( J. J. E N bucket size, Aggr- aggregation rule
2: Sample random permutation π (TT().... x (n)) of [n]
Compute y/ 1 (si,n)
-k-((i-))) (1-1) Tm(k) for i 1, ..... [//=]
4: Return: 3 = Aggr(y)........ ./.,))
Karimireddy al. (2022) show that Algorithm 2 makes Krum (Blanchard al., 2017), Robust Federated Averaging (RFA) (Pillutla et al., 2022) (also known as geometric median), and Coordinate- se Median (CM) (Chen al., 2017) robust, view of definition from Karim- ireddy et al. (2022).
Our main goal in this section is to show that Krum Bucketing, RFA Bucketing, and Bucket ing satisfy Definition 2.1. Before prove this fact, we need to introduce Krum, RFA, CM.
Krum. Let S, S f=1....,.. Fn be the subset of n [ 2 closest vectors to T;. Then, Krum-
estimator is defined as
Krum(z1,... Fnd def argmin
Σ
||,r xzi1?
(15)
z (f) jES.
Krum requires computing all pair-wise distances of vectors from {zI,.... In resulting in O computation cost for the server. Therefore, Krum is computationally expensive, when number of workers is large.
Robust Federated Averaging. RFA-estimator finds a geometric median:
RFA Inn del argmin ZERd
Σ
(16)
The above problem has no closed form solution. However, one can compute approximate RFA using several steps of smoothed Weiszfeld algorithm having (nn) computation cost of each iteration (Weiszfeld, 1937; Pillutla et al., 2022).
Coordinate-wise Median. CM-estimator computes a median each component separately. That is, for t-th coordinate it is defined as
CC 1, def
Kedian( [x,]c) (1))=>>)))))) argmin uER
Iu
[r.]el
(17)
where [z),, is t-th coordinate of vector I E Rd. CM has (n)) computation cost (Chen et al., 2017; Yin et al., 2018).
25

---

Published as a conference paper at ICLR 2023
Robustness via bucketing. The following lemma is the key to show robustness of Krum bucketings RFA o Bucketing, and CM o Bucketing in terms of Definition 2.1.
Lemma D.1 (Modification of Lemma from (Karimireddy et al., 2022)). Assume that is such that there exists subset G S [nl], [9] = = (1 5'n and a 2 0 such that (14) holds. Let vectors fyh....,
{21, D2,...,Zay Fn
= n/s* be generated by Algorithm and = E [N] B, S g) where Yi [B,] ΣJEB, Tj and B; denotes the i-th bucket, i.e.
B. ( - 1). + 1), ................................ (minfi 8, Then, | G z (1 5s)N for any fixed
i, E 9 we have
and E [lly - wlll]] S 0²
y = ]
(18)
where J = Eieg Zz..
Proof. The proof is almost identical to the proof of Lemma from (Karimireddy et al., 2022). Nevertheless, for the sake of mathematical rigor, we provide complete proof. Since each Byzantine peer is contained in no more than 1 bucket and [8] S ôn (here B = [m] \ 9), we have that number of "bad" buckets is not greater than ōn S 6sN, i.e. G (1 5s) Next, for any fixed E & we have
[M i G]
Σ JEB;
Bx [
Σ === G
1
B:
where [-[[-] denotes the expectation w.r.t. the randomness comming from the permutation. Taking the full expectation, we obtain the first part of (18). To derive the second part we introduce the notation for workers from B, and By: B, = (ki, .a...... ki,s} and B; = (kr, 2,, at,,). Then, for any fixed i, 9 the (ordered) pairs {(Tk,,> Fk2,)) are identically distributed random variables as well as for any fixed f = 1.....& vectors Tk.,,; Pki, are identically distributed. Therefore, we have
E [lu 3011 = E
Tkke - IRi,))
2
E [| - 2kg, 112] +
E [ Dki. Tkiic - Ika. >
15t <las
E
[|| Ikk 112] + 8
E
Iki, Ikis - Ikiill
Σ E
||,, -iz
sG(G - 1)
11.259 i1
8-1
Σ
E [[(a - Fig Rig - -xia)
5G - -) -) 3)
(14) o²
Σ
E [
11 +
+
sGiG - 1)
Eg
Finally, we notice that S = 0: for any fixed in, 82, 83, i4 the sum contains one term proportional
to E [(x, - Tig Fig x;a)) and one term proportional to (<rig - Tiy Tig - xia) that cancel out. This concludes the proof.
O
Using the above lemma, we get the following result.
Foor simplicity, we assume that is divisible by
26

---

Published as a conference paper at ICLR 2023
Theorem D.1 (Modification of Theorem I from (Karimireddy al., 2022)). Let {Ii, P2, Fnd satisfy the conditions of Lemma D.I for some å S 6max. If Algorithm 2 is run with 8 = [8ma//6], then
Krum
Bucketing satisfies Definition 2.1 with c ( and 8max 1/4.
RFA
Bucketing satisfies Definittinn 2.1 with с ( and δmax < 1/2,
CM
Bucketing satisfies Definition 2.1 with c = O(d) and 6max < 1/2.
Proof. The proof identical the proof of Theorem I from (Karimireddy al., 2022), since Karimireddy et al. (2022) rely only on the general properties of Krum/RE A/CM and (18) to get the result.
27

---

Published as a conference paper at ICLR 2023
E MISSING PROOFS AND DETAILS FROM SECTION 2
E. EXAMPLES OF SAMPLINGS
Below provide two examples of situations when Assumption 2.4 holds. In both cases, assume that Júg is ssmoohh for all E G.j E [m].
Example E.1 (Uniform sampling with replacement). Consider A,(x.)) = EjEt, Aig(z, v), where (1, v) V(s(()) Viy((y) and I is the set of i.i.d. samples from the uniform
distribution [m]] Then, Assumption 2.4 holds with L3 12 where I3,us S G Eieg 12 12S and tus such that
m (x,
Σ m j=1
A,(z,))1'
S L ,,s y11
Lemma 2 from Szlendak et al. (2021) implies that Lž, L S 12,2.us S L where L2 is such that 1 m -== (1, v)12 < L2,uslI= yll2. We point out that in the worst case L2
1 m
j=1 Li.
It,; Aas V). where Asj(z, y) fz)((z) V (v) I, EØ=1 Li.j, and Is is the set of i..d samples
Example E.2 (Importance sampling with replacement). Consider D = = Is
from the distribution D.,s on [mm] such that for Di.ss we have PÍj = 1) = Les Then,
mu.
Assumption 2.4 holds with C L3,,1s such that
1
m
L
1
(2,
[IA((E)))1 S L3 1s,1sl1 y112.
mG
1=G Lu
m& iEG
Lemma 2 from Szlendak et al. (2021) implies that & Eieo (L, - -
(2) S 12,1 S à Eieg L. We point out that I S Li,s and in the worst case mL, = Lu Therefore, typically Li,ss < 1
Next, we show that Assumption 2.4 holds whenever fúj is -moothh for all E G.j E [m] and A, y) can be written as
m Σ
Á
Eas (Viis()) (v))
= m j=1
for some random variables ε such that B|Ei,] = i E G.j [m] and maxieg.j(mm) B[E,,) E² 30.. Indeed, in this case, we have
Σ E A v) - Ar(,,))| S
A w)
E
G
G
iEg
1EG
m
Σ E
EN (V)r - -V(((())))
G
M 1=1
EGG
m
[z) (
Gm
IEg j=l
E
m
1711 y/2
GM
IEG f=1
E
T2 vll
max iEG.Eimm
meaning that Assumption 2.4 holds with C. S VbE max;eg Li,- However, as we show in Examples E. and E.2 constant L1 can be much smaller than the derived upper bound.
Wee note that this assumption on the form of (r y) is very mild and holds for standard sampling strategies including uniform and importance samplings. We refer to (Gower al., 2019) for more examples.
28

---

Published as a conference paper at ICLR 2023
E.2 KEY LEMMAS
Our theory works for slightly more general setting than the one we discussed the main part of the paper. In particular, instead of Assumption 2.2 we consider more general assumption on the heterogeneity.
Assumption E.1 (B, <2 -heterogeenttyy) We assume that good clients have ( hheerroeeess local loss functions for some B 2 0, 2 0, i.e.,
VV((x)
v=)2) < BIV + Vo E IR..
(19)
G REG
When B = 0 the above assumption recovers Assumption 2.2. Since we allow B to be positive, it may reduce the value
in some applications (for example, for over-parameterized models). As we show further, the best possible optimization error that ByZ-VR-MARINA can achieve in this case is proportional to ç². We refer to Karimireddy al. (2022) for the study of typical values of parameter
B for some over-parameterizee models.
In proofs, we need the following lemma, wich often used for analyzing SGD-like methods the non-convex case.
Lemma E.1 (Lemma from Li et al. (2021)). Assume that function f is L-smooth and 2k+ x² rghh Then
1 1.) 11) 27
f(r s
- [
| 2
+ -11-= -f((=)) (20)
To estimate the "quality" of robust aggregation iteration ls + we derive an upper bound for the averaged pairwise variance of estimators obtained by good peers (see also Definition 2.1).
Lemma E.2 (Bound on the variance), Let Assumptions 2.1, E.I, 2.3, 2.4 hold. Then all k 2 0 the
iterates produced by Byz- ByZ-VR-MARINA satisfy
E I1gg,
8+1
91 ++1 11 < A'E [|x x* 11 8BpE [Bp=) + 4pc (21)
G(G 1)
i.eg
where A' (8BpI. + 4(1 - p) (wT2 (1 (1+w)13 (+w)<
Proof. For the compactness, we introduce notation: A Vs(at+l) v.((.t). Let Beggy denote the expectation w.r.t. Cg. Then, by definition of g k+1 for E & have
Σ
Eer [lla k+1 ot 1111 = G(G - 1)
Σ
-
G(G - 1) 1,159
1.eg
Ti
1-p
+
G(G -
-
7B
Taking the full expectation and using the tower property E[E,, [:]] = E[.]. we derive
E
[|l ++1
1
E[Ti] TT
(22)
G(G 1) ileg
29

---

Published as a conference paper at ICLR 2023
Term E[Ti] can be bounded via Assumption 19:
p
B[T]]
E
G(G
1)
(
p
E (2 v + 21(Vf((a*tt) -Vf(c+t2)](
G(G
- 1)
ideg 19f1
4p Σ
E fi [f(2
=
G
E
(19)
S
4BpE
f +1 )| + 4pp²
(1)
8BpE
[IV
> ||9]] SBpE [I (1+)) ()xx>>)>) 4pc²
As. 2.1
8BpE [<V 8BpL +
[|a -
[|| 11
+ 4p5².
To estimate B[Ty] we first derive an upper bound for E, [T2], where E+1-] denotes expectation w.r.t. the all randomness (compression and stochasticity of the the gradients) coming from the step l + 1 of the algorithm:
1
E& (10r00))-((11)
E& [T2]
G(G 1)
Lleg ief
1 1-p Σ
E& [10
A (2(5)) 4+))
G(G 1)
P
Σ |4 A/1
+ G 1)
i.eg igst
1-P Σ
E& (2100(5)) + [719]
G(G - 1)
1- P
Σ
(2 +21 AT1??)
G(G 1)
1- Σ E& Eo, (2)0(00)) + AMP]]]
G(G - 1)
1IEG igfl
1 1-P P
Σ (2114) - 1- +211 - 2²17
G 1)
wee 1+l1
4(1 p)
Eo, [10 - 114 + 4(1 - p)
E&
(11//122 - -14
G
G
kEg
iEG
4(1 p)
4(1 - p)
(1+ -1A!11]
Σ
(1AI| (|4111
G
G
VEg
4(1 (1 w)
Ex
[|
APP]]
+
4(1
p) w
-
G
G
+4(1 - ||
where [. denotes the expectation w.r.t the randomness coming from the compression at step
+ Applying Assumptions 2.4, 2.3, and 2.1 and taking the full expectation, we get
L2 )) b
TT <
4(1 p) wT? + (1 w)) 1
[1 - -x x01
30

---

Published as a conference paper at ICLR 2023
Plugging the upper bounds for B[T1] and B[Ty] in (22), we obtain the result.
Using the above lemma, derive the following technical result, which we rely on in the proofs of the main results.
Lemma F.3 (Bound on the distortion). Lei Assumptions 2.1, E.I, 2.3, 2.4 hold. Then for all k 2 0 the iterates produced by ByZ-VR-MARINA satisfy
E |llg ++1
V fl ||
(1-3
P
E Ill -Vf(-f((")) || 24Bc5E + 12c8ç²
2
Ap
+
E |||abt1 x* |17]
(23)
where A c8
F
6(1-p)
4cb p p
+
26
1
(wI22 + (1tw)e2 6(1-p) p
[ed(]+ww)
P
+
2G
w
I
Proof. For convenience, we intoduce the following notation:
V ge + T Eieg 2(A,),
if c 1, otherwise.
g ++1
(24)
C7
iEg
Using the introduced notation, derive
E [1lg V (2a
(1
P E - [[
2
2
+ 1 + p
E
- 113].
(25)
Next, we need to upper-bound the terms from the right-hand side of (25). Let E.,, [ denote the expectation w.r.t. Ck. Then, in view of (24), we have
Eeg [l (f(att))111
(1-p)
g
1 G
Σ 2(4+) - Vi(att)) iEg
Taking expectation E+I-] w.r.t. the all randomness (compression and stochasticity of the the gradi- ents) coming from the step & + 1 of the algorithm and applying the variance decomposition and independence of mini-bated and compression computations different workers, get
27
Eg [|lg+t1_ (f( = (1- E
ge + &
- (f(tt1)
IEG
- 1l
+(1 pD)R
[
E A/)
iEg
| 1:17
p)
||(x))]1
Σ
E
G
ieg
31

---

Published as a conference paper at ICLR 2023
Let Eq, [:] denote the expectation w.r.t. the randomness coming from the compression at step ko 1. The definition of the unbiased compression operator (Definition 2.2) implies
Ex |1g ++ V Vf(x*t1))1 = (1 - p}llg*
V ff(=")
||
1-P
Es
[1005111
G
iEG
1-p p
Σ
1
G 1E9
= (1 p)llg *
vs(x ||+
1- p
Eq, |
G
159
1 1-P P
Σ
11
G
LEG
(1 p)1l {|(
(1 - p1 + w)
EE
[12
G
KEg
1 p
Σ 11
G
EEG
(1 p)1lg* v)(x*)
(1 p) + w)
ER
|1
-M11
G²
VeG
+ (1 p)w Σ
||
iEg
= (1 p) vx((x*) 11
+ (1 p1 + w)
Σ Ex | 1
G
iEg
(1 p)w
(1 - p)w
111
|
G2
G
SEG
Using Assumptions 2.4, 2.3, and 2.1 and taking the full expectation, we arrive at
E |1ght1
v
(1
p)l Illa* \1(
(26)
1 P
wL
+L
(1+w) b
E [1a - 1 1
G
That is, we obtained an upper bound for the first term in the right-hand side of (25). To bound the second term, we use the definition of (6, c)-ARAgg (Definition 2.1) and Lemma E.2:
E [[lg -
E Ex
[1g
9 [[1]
co
E
E& [llg,t1]
[1]
G(G 1)
i,EGG
c5
=
G(G - 1)
E
|19
gi
k+1
iJEG
(n
8Bpc + 2
A'COTE [1]1]]
(27)
32

---

Published as a conference paper at ICLR 2023
where A' = (BBp2 + + -l p) (WL (wL2 + (1+ (1) + ( ))
Plugging (26) and (27) in (25)
and using p S L, we obtain
[1g -Vf=- 1 (1- p) [1 p
[llg* [[(())
2)
+ 3(1 p))
wI? + wI + (1 (1+
E [1100 - [2]
26
3
+- (8Bpc) + 4px + A'eOB || - 121)
(13)
(1
E ||l9* vf(z*) |1 + 24Bc6 12Ç²c8
2
Ap
E [| - x 113]
2
where
A
2
3(1 -p) p)
wL + wL1 + (1+W)C
+ AA'o
p
2G
P
400 1
(1 (1+ C2
24 + 3(1 p)
WL2
p
P
2G
b
3(1 p) .
2
4cc0(1 + ww)
L3
p
p
2G
48BT2e6
6(1 -pp) p)
(4cō
1
(1 (1+
wT.2
+
p
p
2G
b
6(1 p)
(4c8(1
+ W)
+ 2G
p
This concludes the proof.
E.3 GENERAL NON-CONVEX FUNCTIONS
Theorem E.1 (Generalized version of Theorem 2.1). Let Assumptions 2.1, E.1, 2.3, 2.4 hold. Assume
that
8< P
0C7S L+VA
(28)
48cB'
where A = 48B1 6(1-p)
4ch +
1 WI. + (Itw)a2) 6(1-p) (166(1tw)
L2 Then
2G
2G
for all K 2 0 the iterates produced by BR-MVRAA satisfy
20
24c8ç²
E
VlV 119
<
(29)
48Bch (K (K+1)
48Bc8
where 5K is choosen uniformly at random from ,0,xt .......,_ r and Do f(x0) f. p
"llg"
{I(2")| The result of Theorem 2.1 is special
case of the statement above with B O, since for B 6(1-p) [4c(1++w) P
we have A
48B12 + 6(1-p) P
(II?
(1+w)
L2
p
P
2G
P
2G
6(1-p)
Acō +
WL?
+
(+w))+
6(1 6(1-p)
4n8(1+
L2
18Bo5
2G
b
2G
p
48Bc p. and the second condition from (28) always holds.
33

---

Published as a conference paper at ICLR 2023
Proof. For all & 2 0 we introduce t f(x*) - fx + B119** V1( Using the results of
Lemmas E.1 and E.3, we derive
E k+1
(3)
E f(x")) - fx
1
L
|| 1--11-210 111 + 2110* [(("a)11)
27
2
E fII (- 11
2 (1
p.
E [119*t 11ll9~-Vi0 vf(('))
2
24Bod
1
+ 7 IE [|l 11
E
[IV] ||
p
P
E x
7
(1 48Bch
E
[ f )|
+ 12c05²7
2
p
p
(1 - b1 - An²) IE ||
R++
1|3]
27
7 (1 48
[[V][(>>)) + 12c6c²7
[
2
P
where in the last step we use Lemma C.I and our choice of from (28). Next, in view of (28), we
have (1- 48Bcó) > O. Therefore, summing up the above inequality for l = 0, 1...., K and
rearranging the terms, we get
K
K (K
Σ
E
| [?]
[0| 1(
K + k=0
48Bcb 7
1) k=0
P
+ 24c8ç²
B80
2 [EE 20)
[[2
24c0ç²
? 1 48Bc6
(K 11)
p p- 48Bed
K++ 20
2 [0)
24c5c
+ p 48Bc8
? (1
48Bcb
(K+ 1)
P
It remains to notice, that the lef-hand side equals V[ )19) where T.K is choosen uniformly at random from x0, x! ,..., x
On the differences between ByZ-VR-MARINA and momentum- -based methods. Karimireddy al. (2021) use momentum and momentum- variance reduction in order to prevent the algorithm from being germutationiinvarian permuation-invariant algorithms cannot converge to any predefined accuracy even in the homogeneous case. In our paper, we provide different perspective on this problem: it turns out that the method can be variance-reduced, byzanttne-robust, and commutation-invariin at the same time.
since in the setup considered by Karimireddy el al. (2021) all
Let us first refine what we mean by permutation-invarianee since our definition slightly differs from the one used by Karimireddy et al. (2021). That is, consider the homogeneous setup and assume that there are no Byzantine workers. We say that the algorithm is coamutatioo-invariann if one can arbitrarily permute the results of stochastic gradients computations (not necessarily one stochastic gradient computation) between workers at any aggregation step without changing the output of the method. Then, BYZ-VR-MARINA permutation-invarian since the output in line 10 depends only on gf and the set ) hee(n] (note that Q(x) z, since we assume
O), not on their order. Our results do not contradict the ones from Karimireddy et al. (2021), since Karimireddy et al. (2021) assume that the variance of the stochastic gradient is bounded, while we apply variance reduction implying that the variance goes to zero and Byzantine workers cannot successfuly "hide in the noise" via couple attacks anymore.
Before we move on to the corollaries, we ellaborate on the derived upper bound. In particular, is important to estimate [. By definition, to f(x=) fa Ellg V((x") i.e., to depends
34

---

Published as a conference paper at ICLR 2023
on the choice of gº. For example, send it to the server. Then, the server can set g" as g" = AR ,n). This gives us
ask good workers compute h; V. i 9 and
E B[Po
f(x)) f.
7 E [llg
p
2 s(x²) - f. PG
7cò
[Vf(2²))
Vf((=')11
(D)
27c8
S f(x²) - ft PG(G- -
Σ (IV
vacg if!
f(x²) - So 4705
PG
(9) S -(=
4ycB B
4y05ç²
||
P
Function / is L-smooth that implies and y S 1/2, derive
[/(2))11 s 2L (5(x9) -.).
Using this and d P/(48)B)
S 1 8yc8BL)
(5(x9)-1)) -.)) 4yy0ç²
E P
P
P
2 1 24 (1(=9- --) 47c8c²
P
< 2 (J(x)) s.) 4yc86²
(30)
p
Plugging this upper bound (29), we get
(f(xx) - fa)
32c8C²
[IVS(**)
7
18Bo6
(K +
p- 48Bc5
Based on this inequality we derive following corollaries.
Corollary E.1 (Homogeneous data, no compression (w = 0)). Let the assumptions of Theorem E.1 and
hold, ((x) x for all Rdd (no compression, = 0), p b/m, B
L f V 6 4
FG
Then for all K 2 0 we have E [|| f* ||2]
of the order
L C=
chm 6
2
Au
O
(31)
where J.lk is choosen uniformly at random from the iterates d0 xt vK produced by Byz- VR-MARINA and An = [xx") Sa. That is, to guarantee E ||v ByZ-VR-MARINA requires
(T
||
s s² for 8² > 0
L [ Lu
chm²
An
FC
o
(32)
62
communication rounds and
bb + C=
V
b
m
Ao
o
(33)
22
oracle calls per worker.
35

---

Published as a conference paper at ICLR 2023
Corollary E.2 (No compression (w 0)). Let the assumptions of Theorem E.1 hold, Q(x) x for all x E Ie (no compression, w = 0). = f//m and
I 48L Beem
24chm² 82
[2 + 6 4oomm²
+
BC
ma
b
Then for all K 2 O we have E f(*k [[3] of the order
L +
Bobm
+
cóm²
+
cóm2 62
Do
62
cOç²
(34)
(1
Beóm
K
48Bc8
where HK is choosen uniformly at random from the iterates x0 x² MARINA and Ag [(x") f.. That is, to guarantee E. [ ( {|l]
xx produced by Byz-VR-
S 8² for 8² 2 12c5ç²
48Bco
ByZ-VR-MARINA requires
[+
Beom
cóm² +
+
cóm2 1
m bG
4
Do
b
82
O
(35)
(1
e2
communication rounds and
bL Bedmb + côm² + (côm² +
mb
L2
Do
G
O
(36)
(1 48 Behm
g2
oracle calls per worker.
Corollary E.3. Let the assumptions of Theorem E.1 hold, p min(b/m, 1/1+w) and
1
?
where
L+
V
A
48L²
B max
Bcd
b 1 1.1+
+6
4cd max
m²
82 :1+ w)2
max
m
b
1 + [w]
wI.2+ + (1+ W]
2G
+6 4cō(1 + w) max
m
.1, (1+ w)2
w max
m 17.1+
L3
62
2G
Then for all K 2 we have [||V] [[|V/(*>)] ||2] of the order
o o 48Bed max ( (8,1+w))
[L+ VA Ao
cOC²
(37)
K min
48 Bcó
m 14
where &K is choosen uniformly at random from the iterates x xx MARINA and Ag f(x") fa. That is, to guarantee E 112] S e² for e² 2 32c5c
KKK produced by Byz-VR-
p- 485c6
Byz- BYZ-VR-MARINA requires
L+ V Do
o
(38)
(1
48Bcd max
+ w E2
b
communication rounds and
6L + bVA Au
(39)
48 max
m b
+
2
oracle calls per worker.
36

---

Published as a conference paper at ICLR 2023
Corollary E.4 (Homogeneous data). Let the assumptions Theorem E. hold, p min(f/m, 1/2tw).
B Ç = 0, and
7 L VA
where
(300 (c30mm max
{
m²
(1 (1+w))
m max
b 1 ww)
(I12 + (1 (1+ w
A
b2
2G
Then for all K 2 0 we have E [[ of the order
Do
(40)
K
where &K is choosen uniformly at random from the iterates x. xx ..... x produced by Byz- VR-MARINA and Dn = [(x)) - Sa. That is, to guarantee E [IV }| z 8² for 8² > 0
ByZ-VR-MARINA requires
L+ A Do 5²
(41)
communication rounds and
bL. (
DVA
Ao
o
(42)
E²
oracle calls per worker.
E.4 FUNCTIONS SATISFYING POLYAK-EOIASIEWICZ CONDITION
Theorem E.2 (Generalized version of Theorem 2.2). Let Assumptions 2.1, E.1, 2.3, 2.4, 2.5 hold. Assume that
P
P
0 < 7 < min
(43)
4p (1- 96Hoc L V2A
96cB'
where A 48B1 + 6(1-p)
4cb + 20: (WI+++ + (1+w) 6(1-p)
(106(1tw)
12 Then
20
for all K 2 0 the iterates produced by ByZ-VR-MARINA satisfy
(015((11))) (1-7H (1- 96Bcd )) K
24c0
E ( s
@ + plp - 96
(44)
where tn ((09) f(x²) + 22 221100
Vf(29)12
The result of Theorem 2.1 is
special case of the statement above with B
0. since for
O we have
A 48BL' 6(1-p)
And
2G wI? + (1+W)2)
6(1-p) 4ch(1+te)
I2
P
P
2G
6(1-p) Aed + 2G
(WL +
(+
+ 6(1-p) (eo((++w)
w
L2
(1
96Bo
1, p
2G
BcB p. and the second condition from (43) always holds.
37

---

Published as a conference paper at ICLR 2023
Proof. For all k 2 0 we introduce 42 = f(x²) - -+++ + p blla - vf(x=))1
Using the results of
Lemmas E.1 and E.3, we derive
(20),23) R
[(xt)) - -(xx)) - (
27 - 4) | - -2/1/ + 221ot= VS(a+)]13
[
E
2
EE [IV (())))))]]] + 2% (1 2)) E 01ll9~-viil ( |1a]
p
48Body
P E V (x* ||²] + 2
+ +yBB -1 [c]
- x
p
E
[s(( - -sxx'] + 2
(1 - 6)
4
E Illg* - ((()))111
=
7
(1 96
ʃ k ||2] + 24c55²7
2
p
P
1
(1
- Ly -
E [11 - 2-1
2y
(1 96Bcd
1 7/
E [f(a*) - [(x))]
p
+ p
2Y
(1
p)
E
[lle*
V\((*)) +
24c00²7
4
p
1 m/ (1 96Bcd
24c0ç²7
E [
+
p
P
where in the last step we use Lemma C. and our choice of y from (43). Unrolling the recurrence, we obtain
96L10)) 1
)) K
2
K-1
1 96
)) k
B
x
$
1 1-711
7p
E [ +
Σ
1 7p
p
p
P
k=
96Bcd) )) K p
E [ + 2
8
7M (1 (1- 96Bc8
k
1-71
1
7p
p
p
96130) ))
24coç²
( 1-710 7p
1
E [Po]
P
p(p 996Bed)
Taking into account $ 2 s(xa)) - f(x"), we get the result.
As in the case of general non-convex smooth functions, we need to estimate Da to derive complexity results. Following exactly the same reasoning as in the derivation of (30), we get
B[oo| S 2 (J(x") - f(x')) + 8yc6(²
p
Plugging this upper bound in (44), we get
96Bcd) )) K
E [f((**) - -[(x"]] S
1 1-7
7/4
1
(f(09- - f(x²))
p
(1-
96Bed)
8yc86?
24c0(2
+ 1
1-114
7/4
+ M(p 968
P
P.
96
<
2
1 - 1-7
1
(f(29)
-f(x*)
p
(1- 1 )
* 8y0062
+ 240852
+
1 - 7/14
p
P
1(p - 96B
0=0
(1- 96Bcd
))²
K (f(29) - f((=))
32c8ç²
<
2
11
1
7/4
p(p -96Bed)
Based on this inequality we derive following corollaries.
38

---

Published as a conference paper at ICLR 2023
Corollary E.5 (Homogeneous data, no compression (w 0)). Let the assumptions of Theorem E.2 hold, Q(z) = x for all E Rd (no compression, w = 0), p = m, B = 0, Ç = 0, and
1
b
7 min
L (++2Ct/ v
12cdm +
3mm 25
4mp
Then for all K 2 O we have E [f(x - f(x²)] of the order
b
O
exp
min
A0).
do
(45)
+ 26+
1268m
2
where Ag = f(z0)
f(x)).
That is, to guarantee [f(xk) f(x(((()))))) S Efo 0 Byz-VR-
MARINA requires
O max
L L
cōmn 6
m BAG
m
log
Ao
(46)
communication rounds and
bL + L+
c6m²
m
A
max
17
log
(47)
oracle calls per worker.
Corollary E.6 (No compression (w 0)). the assumptions of Theorem E.2 hold, 2(x) = x for
all Rd (no compression, w 0), b// and
min
m
96L 36L2Bee5m Beöm
18c5m² 62
L3 + 12
1c5m2
+
C7
4p
Bc8
62
26G
Then for all K we have E [f(*k) - fxx*) of the order
(1 - 91B66" 5
b
o
exp
min
K
An
Bebm
48c5m² L 12
4c5m²
m
C
m
26(3
(48)
"
96BB6)
where Ao = f(x0) f(x"). ByZ-VR-MARINA requires
That is, to guarantee [f(x*) - [(x))] S E for &
32ch<2
96BB3
Beam + o6m2
+
cdm2 1
m
Ao
O max
log
(49)
96
mm
b
,
communication rounds and
6L
Lcdmb + côm2 L3 (côm² +
mb
4
Au
max
m
log
(50)
1 96 168
oracle calls per worker.
39

---

Published as a conference paper at ICLR 2023
Corollary E.7. Let the assumptions of Theorem E.2 hold, p (f/m 1/2tw] and
min
b 1t
7 min
where
L V2A
4u (1 9c max m
b + w)) {
A
48L² Bcd BcL max
{
b. 1 111+
m²
max
b 1 + W
WL? (1+w)
+6
4ed max
(1 (1++))
1
2G
+6 4e0(1 + w) max
m²
12 (1 + w)
w maxx
1 b + w/
12
2G
Then for all K we have E. [f(ak)
[(x²)] of the order
(1 B6 max (T. + w
O
exp
min
K
Do
I. VA
m
w
c
(51)
M(min
( T0 Ii 26BB1)
where Do [(x0) [(x').
That is, to guarantee E [(x")] -
-
S S for
32r
ulp
96B0
ByZ-VR-MARINA requires
m 11 96 max (b: w)) b
L+ VA
Ao log
max
+ w fog
(52)
communication rounds and
bL + bvA
Ao m, b(1 + w) log E
O max (1 Bcd max
(53)
ma b 1 + w]]
oracle calls per worker.
Corollary E.8 (Homogeneous data). Let the assumptions of Theorem E.2 hold, p min(b/m, 1/1+w].
B = 0, < 0, and
min
T4w
7 = min
where
L + 22A"
4fc
m2
max (Th 1 w
(WI + (1+
A = 6 4c5 4ax max
62 (1 + w)2
2G
b
Then for all K 2 0 we have E [ - f(x")] of the order
exp
min { ( m 1+
b
K (K)A
(54)
where Dg f(x²) fxx)).
That is, to guarantee E [f(*K)
f(x))] S for
0 Byz-VR-
MARINA requires
L A
Ag
max
1
log
(55)
#
communication rounds and
bL bb+ bv
Ao
O
max
m, b( + u))
log
(56)
oracle calls per worker.
40

---

Published as a conference paper at ICLR 2023
E.5 FURTHER DETAILS ON THE OBTAINED RESULTS AND THE COMPARISON FROM TABLE 2
In this part, we discuss additional details about the obtained results and on the comparison of methods complexities given in Table 2. We mostly focus on the results for general smooth non-convex functions. Similar observations are valid for smooth Pl.functions as well.
Comparison of the assumptions on the stochastic gradient noise. Many existing works rely on the uniformly bounded variance assumption (UBV): is assumed that for all x E IR the good workers have an access to the unbiased estimators (x()) of f((x)) such that [g]g V {((r)]] s o² for all i E G and 2 O. This assumption does not hold in many practical situations and even for simple convex finite-sum problems like sums of quadratic functions with non-identical Hessians. Moreover, in the situations when this assumption holds, the value of x² can be huge. However, UBV assumption does not require individual stochastic realizations, i.c., summands fi.z to be smooth.
In contrast, we use Assumption 2.4 that holds for many situations when UBV assumption does not. For example, Assumption 2.4 holds whenever all functions fi.. E G. j E m are -mmoooh (see Appendix E.1). These facts allow to cover a large class of problems that does not fit the setup considered in (Karimireddy et al., 2021; 2022; Gorbunov et al., 2021a). Moreover, since Assumption 2.4 4 is more general than smoothness of all st.j. our analysis covers the setup considered in (Wu et al., 2020; Zhu & Ling, 2021). However, it is worth mentioning that there exist problems such that UBV assumption holds and Assumption 2.4 does not, e.g., when the gradient noise is additive: ( v) = (=(()) - fi(v)) + E,, where E,;- = and B||&|||== =
On the choice of p. Our analysis is valid for any choice of p E (0, 1]. As we explain in footnote 2, the choice of p = min(m/m 1/(++)) leads to the fair comparison with other results, since this choice implies that the total expected (communication and oracle) cost of steps with full gradients communications coincides with the total cost of the rest of iterations. Indeed, to measure the communication efficiency one can use expected density Ço (see Definition 2.2). Then, the expected number of components that each worker sends to the server at each step is upper- bounded by Se(1 - p) + pd meaning that p = Sa/a makes the expected number of components that each worker sends to the server at each step equal to ((Se). In the case when + w = O(d/so) (which is the case for RandK sparsification and fz-quantization, see (Beznosikov et al., 2020)), one can choose p 1/(+=w).
conpurations/umconpress
On the other hand, the expected number of oracle calls per iteration 2b(1 p) + mp meaning that p f/m makes the expected oracle cost of each iteration equal to O(b) like in the case of SGD. This means that the best p for oracle complexity and the best p for communication efficiency are different in general. When f/m < 1/(1+w), the choice = min(t/m, 1/(1+) implies that the algorithm could use uncompressed vectors more often without sacrificing the communication cost, and when h// > 1/(++w,, the choice p min(b/m /m, 11 + w)} implies that the algorithm could use full gradients more often without sacrificing the oracle cost. That is, the choice of p zs 1/m implies better oracle complexity and the choice p R 1/(1+w) leads to better communication efficiency. Depending on how much these two aspects are important for the particular application, one can choose p in between these two values.
The effect of compression. For simplicity, consider a homogeneous case (B = 0, (= 0) and let b = 1; similar arguments are valid for the general case. As Corollary E.4 states, the communication complexity of Byz-VR-MARINA in this case equals
A
Ao
where
22
A = 3cd max ( (m², 2 w)] max {m, 1 + w (WL2 + (1+
2G
The above result shows that the communication complexity becomes worse with the growth of w. Larger means that the compression Q is more loose, i.e., less information is communicated. This is
WW remind here that by communication complexity mean the total number of communication rounds needed for the algorithm to find point such that EE (VVff())) < ?
41

---

Published as a conference paper at ICLR 2023
common phenomenon for the methods with communication compression (Horváth et al., 2019b; Gorbunov et al., 2021b). However, when the compression is not severe, e.g., 1 + w S m, then the complexity bound becomes
[+ E²
L
(L+VA)
Ao
where A= 3cdm² + 2G (wT? + (1+ +))
which is worse only ((Vw) times than the complexity Byz- SR--VRAAAAINN without compression, while the number of communicated bits/components becomes O (2/co) times smaller. For example, in the case of RandK sparsification we have + w = 4/K = 4/<o, and + w S m allows to have quite strong compression, e.g., for Z 1000, meaning that the dataset has at least 1000 samples, inequality 1 ++ S m implies that workers can send just 0.1% of information. In this case, the communication cost of each iteration becomes 1000 times cheaper, while the number of communication rounds increases only v1+ + w ~ 30 times. If the communication is the bottleneck, then the algorithm will converge much faster with compression than without it in this setup.
On the batchsizes. First, we note that our analysis is valid for any choice of b > 1. For simplicity of the further discussion of the batchsizes role in the complexities, consider the homogeneous case (B 0, < = 0) without compression (w 0). As Corollary E. states, the communication complexity of ByZ-VR-MARINA this case equals
L
L=
cóm2 6
m baG
Au
O
E2
Note that the term depending on the ratio of Byzantine workers ô scales b- with the batchsize and the term depending on 1/G scales as b b-1 Table 2 illustrates that previous SOTA results in this case scale as 6-1 or 6 6-1/2, so, the complexity bound for ByZ-VR-MARINA scales with b no worse than the concurrent bounds.
Next, typically, there is no need to take b larger than V for SARAH-based variance reduced methods (Horváth al., 2022; Li et al., 2021): oracle complexity is always the same (neglecting the differences in the smoothness constants), while the iteration complexity stops improving once becomes larger than vm. However, the complexity bound for ByZ-VR-MARINA contains non-standard term O (Eam)) appearing due the presence of Byzantine workers. For simplicity, we assume that L = O(L+) (though L+ can be both smaller and larger than L). Then, when we increase batchisze b, the communication complexity stops improving once b becomes larger than max Vcôm², m). Interestingly, céôm² can be larger than the standard value /m: this the case when m 1/c252. In this case, the communication complexity of ByZ-VR-MARINA benefits from the slightly larger batchsizes than in the classical case. This phenomenon has a natural explanation: when we increase the batchsize, the variance of the gradient noise decreases and becomes even harder for Byzantine workers to shift the updates of the method significantly.
42


Reviews:
[{"review_id": "ZsviceBERLY", "reviewer": "Reviewer_QBBT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The focus of this paper is on communication-efficient and Byzantine-robust distributed optimization. To this end, the authors propose an algorithm Byz-VR-MARINA that combines ideas from the Byzantine-robust distributed optimization work of Karimireddy et al., 2021 and communication-efficient distributed optimization work of Gorbunov et al., 2021b. The main contributions of the work include both theoretical guarantees for the proposed algorithm as well as numerical experiments that highlight the effectiveness of the proposed algorithm.", "summary_of_the_review": "Overall, it is a solid piece of work that primarily suffers from somewhat limited novelty and also lack of appropriate experimental results.", "strength_and_weaknesses": "**Strengths**\n\n- This appears to be first work in the literature that focuses on communications efficiency in Byzantine-robust distributed optimization.\n- The paper includes a rigorous set of theoretical guarantees for both the general nonconvex functions as well as functions that satisfy the PL condition. In addition, the analysis in the paper includes the case of heterogeneous data.\n\n**Weaknesses** \n\n- In most works, the theory is presented for functions that are either strongly strongly convex or that satisfy the PL condition, but the experiments are then presented for nonconvex functions. It is strange that the experiments in this paper are only for strongly convex functions. Experiments with a total of five workers and just one of them being Byzantine are also not convincing.\n- At some level, the paper appears to be a mash-up of ideas from two existing works. The authors could have done a better job of clarifying the challenges they have to face in terms of this.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XS3fTFbUX8", "reviewer": "Reviewer_9mHu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a new Byzantine-tolerant distributed learning method called Byz-VR-MARINA, which adopts variance reduction to obtain a better convergence rate than existing methods. Meanwhile, communication compression is a bonus of the proposed method. The authors provide theoretical analysis of Byz-VR-MARINA for non-convex objective functions and the functions satisfying Polyak-Lojasiewicz inequality. Besides, empirical results of Byz-VR-MARINA and the baselines on binary classification tasks are provided.", "summary_of_the_review": "Given the concerns above, this paper seems currently below the acceptance threshold to me. Meanwhile, I am willing to raise my rating if the authors could properly address the concerns.", "strength_and_weaknesses": "The main idea of variance reduction is well presented. I appreciate that theoretical analysis is provided for both non-convex objective functions and functions satisfying PL inequality. Meanwhile, there are also some concerns.\n\n1. My major concern is about the proof details. The expectation notation $\\mathbb{E}$ is used ambiguously in the proof details in the Appendix. Specifically, the randomness comes from both the stochastic mapping $\\mathcal{Q}$ and the mini-batched estimator $\\hat{\\Delta}_i$. However, it is ambiguous which stochastic operator each expectation is with respect to. It increases the difficulty of checking the correctness of the proof details and would make readers confused.\n\n2. It is claimed that communication compression is a bonus of the proposed method. However, there seems no theoretical analysis or empirical results about the communication efficiency in the paper.\n\n3. The proposed method is very similar to VR-MARINA [1], which limits the novelty of this paper.\n\n4. The experiments are conducted with the logistic regression model on a9a and w8a datasets. The scale of the problem is small given the current computing power and the background of distributed learning. Adding experiments on larger-scale problems would make this work more solid and convincing.\n\n5. (minor) It seems that only the proofs for the generalized version of Theorem 2.1 and 2.2 are provided in the Appendix. It is suggested to add some details in the Appendix about how to obtain the final results when $B=0$ in Assumption E.1.\n\n6. (minor) I am wondering why the hyperparameter setting for bucketing is presented in the paragraph that introduces the attack method IPM (page 9).\n\n[1] Gorbunov, Eduard, et al. \"MARINA: Faster non-convex distributed learning with compression.\" International Conference on Machine Learning. PMLR, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QJsLuOO8yd", "reviewer": "Reviewer_GiVQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies Byzantine-robust variance reduced methods, and further combines them with gradient compression for communication efficiency. The paper takes a theoretical point of view, and numerical results on simple tasks such as logistic regression are provided.", "summary_of_the_review": "This paper tackles Byzantine-robust distributed optimization mostly from a theoretical perspective. However, the comparison with related works seems difficult to carry out due to the different assumptions in analysis seems, hence its difficult to evaluate the theoretical contribution. In addition, the numerical results are relatively thin and cannot fully support the claimed merits. ", "strength_and_weaknesses": " **Strength:**\n\n- S1. The theoretical perspective of proposed algorithms is studied thoroughly. \n- S2. The presentation is clear.\n\n\n**Weakness:**\n- W1. (Theory.) The proof of Byz-VR-MARINA seems to rely on different assumptions (see assumptions 2.3, 2.4) with other works in Table 2. Can the authors compare these assumptions, and is it possible to conclude which one is stronger? Another question is that for those convergence rates marked with x in Table 2, is it impossible to establish? Or the original paper did not report? For example, in the nonconvex setting, if combining the analysis to nonconvex SAGA and Byrd-SAGA, is it possible to get a rate? \n\n- W2. (Methodology.) This paper combines several techniques from existing works, such as VR-MARINA and robust aggregator. This makes the novelty boils down to applying existing works to the byzantine setting, which seems not sufficient for conferences like ICLR. \n\n- W3. (Experiments.) The numerical results can be improved in multiple aspects. **i)** No variance reduced method is compared. It is helpful to include the performance of e.g., VR-MARINA to verify how much the proposed algorithm is affected by byzantine workers. In addition, no alternatives from byzantine-tolerant VR methods are compared. Although Bryd-SAGA uses additional memory, but the datasets e.g., a9a, is small and such memory consumption is affordable. Even if Bryd-SAGA is not a good choice to compare with, the authors can compare to heuristics such as Bryd-SARAH / Bryd – SVRG.  **ii)** The numerical experiments do not reflect the influences of gradient compression. No runtime is compared. **iii)** Although claimed for nonconvex problems, most of tests are on logistic regression, which is convex. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KQtm3mpa53", "reviewer": "Reviewer_kABX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the Byzantine resilient optimization problem and proposes to use variance reduction and compression for improved convergence rates. More concretely, they propose a novel method, Byz-VR-MARINA, which integrates VR-MARINA and an unbiased gradient compressor together for Byzantine robustness. They show that Byz-VR-MARINA enjoys a better convergence rate under weaker assumptions when compared to previous works. The empirical evaluations also show that Byz-VR-MARINA has outstanding performances.", "summary_of_the_review": "I recommend accepting this paper as it gives good theoretical analysis and good empirical performance. ", "strength_and_weaknesses": "Strength:\n- The paper is well-written and covers a sufficient amount of related works.\n- The idea of using variance reduction for Byzantine robustness is natural but it is straightforward to make the rate tight. This paper did a very good job of proving the rates under standard or weak assumptions.\n- The gradient compression improves the communication efficiency but has little influence on the convergence rate.\n- This paper additionally allows non-uniform sampling of stochastic gradient which is not seen in previous works.\n\nWeakness / Possible improvement:\n- What's the relation between b and m? For variance reduction techniques like SPIDER, the optimal choice of b is $b=\\sqrt{m}$. If $m$ is significantly large than b, then in Table 1 (homogeneous + no compression + NC), Byz-VR-MARINA has a scaling of $c\\delta\\frac{m}{b} + 1/n$ which seems to be worse than BR-SGDm $c\\delta + 1/n$.\n- The probability p looks very interesting and can be further discussed. For example，\n    - The p serves two goals in variance reduction and compression. If $b=\\sqrt{m}$ for SPIDER, does it mean we may not simultaneously choose the best p for variance reduction and compression?\n    - The lower bound term in (7) has a coefficient 1/p. Is it optimal?\n    - Eq. (7) suggests that while variance reduction improves the convergence rate but at the same time makes the lower bound worse. Is there any way we can circumvent this? The overparameterization trick in (Karimireddy et al., 2021) seems not working as it increases the gradient size.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Byblj8d4gQ", "reviewer": "Reviewer_xAhq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method for training a deep neural network in a federated fashion in the presence of malicious or misled workers who misreport their gradient contributions, aiming to reduce variance of the stochastic gradients during learning and compress. It illustrates that the reduction of variance, is, unsurprisingly, key to withstanding the activities of such workers and achieve robust learning. The paper contributes tighter guarantees than previous work in the area with fewer assumptions, as well as a method that can work under nonuniform gradient sampling.", "summary_of_the_review": "The authors made some effort to improve the scientific clarity of the terms employed in the paper to properly identify the kind of workers envisaged in this context, however they fell short of providing clear technically worded definitions that would not rely on a prejudice dating back to the 15th century to convey the required scientific meaning. In fact, they even insisted that alluding to such a prejudice is necessary to convey the intended technical neaning\n\nTherefore, unfortunately, the core definitions and terms employed remain wanting clarity and scientific precision, and there have not been solid rectification steps; the authors also bluntly refused using any of the alternative terms suggested and to provide the definitions requested by this reviewer.\n\nIn particular, the authors disputed that the use of language in their original submission, which violates ACM guidelines on the matter, was ambiguous and potentially offensive. They argued that using an ethnoreligous term with a derogatory meaning as scientific terminology is fine as long as it is abbreviated to its first three letters. They used as their main piece of evidence the fact that this term was not offensive to themselves. They declined to engage in further discussion and to respond to either the scientific or the ethical concerns raised. They expressed open disagreement regarding the ambiguity and lack of scientific clarity in the definitions employed and decided to do nothing more about it, contrary to ACM guidelines.\n\nNevertheless, I appreciate the dedicated scientific effort made by the authors to provide additional results comparing with alternative variance-reducing methods as they could. I also appreciate their willingness to rectify the terminological ambiguity and omit allusions to an enduring cultural prejudice of medieval origin that have no place in a peer-reviewed academic article, albeit only superficially. Therefore, I recommend acceptance.", "strength_and_weaknesses": "Strength\n- Novel theoretical results, though mostly based on previous work on VR-Marina, a variance-reducing method.\n- Interesting combination of robust aggregation and VR-Marina in a deviance setting.\n\nWeakness\n- Ambiguous and undefined terminology using a lexicographically documented ethnoreligious prejudice as a technical term.\n- Use of language violating ACM guidelines on inclusiveness and non-discrimination.\n- Confusing use of terminology, mixing a subset with a set.\n- Lack of experimental comparison to alternative deviance-tolerant variance-reducing methods.\n- Refusal to use the objective term \"Deviant\" instead of perpetuating an unscientific derogatory stereotype.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster