Byzantine-Tolerant Methods for Distributed Variational Inequalities
Authors: Nazarii Tupitsa
Abdulla Jasem Almansoori
Yanlin Wu
Martin Takáč
Karthik Nandakumar
Samuel Horváth
Eduard Gorbunov
Venue: NeurIPS 2023 poster (2023)
Keywords: byzantine robustness
variational inequalities
min-max problems

Abstract: Robustness to Byzantine attacks is a necessity for various distributed training scenarios. When the training reduces to the process of solving a minimization problem, Byzantine robustness is relatively well-understood. However, other problem formulations, such as min-max problems or, more generally, variational inequalities, arise in many modern machine learning and, in particular, distributed learning tasks. These problems significantly differ from the standard minimization ones and, therefore, require separate consideration. Nevertheless, only one work [Abidi et al., 2022] addresses this important question in the context of Byzantine robustness. Our work makes a further step in this direction by providing several (provably) Byzantine-robust methods for distributed variational inequality, thoroughly studying their theoretical convergence, removing the limitations of the previous work, and providing numerical comparisons supporting the theoretical findings.

Byzantine- Tolerant Methods for Distributed Variational Inequalities
Nazarii Tupitsa MBZUAI, MIPT
Abdulla Jasem Almansoori MBZUAI
Yanlin Wu MBZUAI
Martin Takáč MBZUAI
Karthik Nandakumar
Samuel Horváth
Eduard Gorbunov'
MBZUAI
MBZUAI
MBZUAI
Abstract
Robustness to Byzantine attacks is necessity for various distributed training narios. When the training reduces to the process of solving a minimization problem, Byzantine robustness is relatively well-understood. However, other problem for- mulations, such as min-max problems or, more generally, variational inequalities, arise many modern machine learning and, in particular, distributed learning tasks. These problems significantly differ from the standard minimization ones and, therefore, require separate consideration. Nevertheless, only one work [Adibi al., 2022] addresses this important question in the context of Byzantine robustness. Our work makes further step in this direction by providing several (provably) Byzantine-robust methods for distributed variational inequality, thoroughly study- ing their theoretical convergence, removing the limitations of the previous work, and providing numerical comparisons supporting the theoretical findings.
Introduction
Modern machine learning tasks require to train large models with billions of parameters on huge datasets achieve reasonable quality. Training of such models is usually done in distributed manner since otherwise it can take a prohibitively long time [Li, 2020]. Despite the attractiveness of distributed training, is associated with multiple difficulties not existing in standard training.
In this work, we focus on one particular aspect of distributed learning Byzantine tolerance/robustmess the robustness of distributed methods to the presence of Byzantine workers² i.e., such workers that can send incorrect information (maliciously or due to some computation errors/faults) and are assumed to be omniscient. For example, this situation can appear in collaborative training, when several participants (companies, universities, individuals) that do not necessarily know each other train some model together [Kijsipongse et al., 2018, Diskin et al., 2021] when the devices used in training are faulty [Ryabinin et al., 2021]. When the training reduces to the distributed minimization problem, the question of Byzantine robustness is studied relatively well both theory and practice [Karimireddy et al., 2022, Lyu et al., 2020].
However, there lot of problems that cannot be reduced minimization, e.g., adversarial training [Goodfellow et al., 2015, Madry et al., 2018), generative adversarial networks (GANs) [Goodfellow al., 2014], hierarchical reinforcement learning [Wayne and Abbott, 2014, Vezhnevets et al., 2017], adversarial examples games [Bose et al., 2020], and other problems arising in game theory, control theory, and differential equations [Facchinei and Pang, 2003]. Such problems lead to min-max
"Corresponding author: eduard. eduard.gorbunooe. gorbunov@mbzuai. awt.uaii.c....... ac.
"The term "Byzantine workers" is standard term for the field [Lamport al., 1982, Lyu et al., 2020], We do not aim to offend any group of people but rather use common terminology.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

or, more generally, variational inequality (VI) problems [Gidel et al., 2018] that have significant differences from minimization ones and require special consideration [Harker and Pang, 1990, Ryu and Yin, 2022]. Such problems can also be huge scale, meaning that, in some cases, one has to solve them distributedly. Therefore, similarly to the case of minimization, the necessity in Byzantine-robust methods for distributed VIs arises.
The only existing work addressing this problem is [Adibi et al., 2022], where the authors propose the first Byzantine-folerant distributed method for min-max and VI problems called Robust Distributed Extragradient (RDEG). However, several interesting directions such as application of (6, c)-robust ag- gregation rules, client momentum [Karimireddy et al., 2021], I, and checks of computations [Gorbunov al., 2022b] studied for minimization problems are left unexplored in the case of VIs. Moreover, [Adibi et al., 2022] prove the convergence to the solution's 's neighborhood that can be reduced only via increasing the batchsize and rely on the assumption that the number of workers is sufficiently large and the fraction of Byzantine workers is smaller than 1/16, which is much smaller than for SOTA results in minimization case. Our work closes these gaps the literature and resolves the limitations of the results from [Adibi et al., 2022].
1.1 Setting
To make the further presentation precise, we need to introduce the problem and assumptions we make, We consider the distributed unconstrained variational inequality (non-linear equation) problem':
find x=" E IR such that F(x") O, where F(z) = G
1
Σ F((x), SEG
(1)
where G denotes the set of regular/good workers and operators F; have an expectation form (xx == Eg, (2: E.)]. We assume that n workers connected with a server take part in the leariingoppimization process and [n] = G B, where B is the set of Byzantine workers the subset H of workers [n]] that can deviate from the prescribed protocol (send incorrect information, e.g., arbitrary vectors instead stochastic estimators) either intentionally or not and are onniscient* i.e., Byzantine workers can know the results of computations on regular workers and the aggregation rule used by the server. The number of Byzantine workers B = [B] assumed to satisfy B S ôn, where 5 < 1/2 (otherwise Byzantines form majority and the problem becomes impossible to solve). The number regular workers denoted as -G]-
Assumptions. Here, we formulate the assumptions related to the stochasticity and properties of operators (Fi).eg-
Assumption 1. For all E G the stochastic estimator g (ar, Ei) is an unbiased estimator of Fi())) with bounded variance, iee., Eg (x, E:)] = (x())) and for some a 2 0
Egg |1. Es) F((=))1]] 0²
(2)
The above assumption is known as the bounded variance assumption. It is classical for the analysis of stochastic optimization methods [Nemirovski et al., 2009, Juditsky et al., 2011] and is used in the majority of existing works on Byzantine robustness with theoretical convergence guarantees.
Further, we assume that the data heterogeneity across the workers is bounded.
Assumption 2. There exists such that for all Rd
1
[(((()) iEG
(3)
G
Condition (3) a standard notion of data heterogeneity in Byzantinerrobust distributed optimization [Wu et al., 2020, Zhu and Ling, 2021, Karimireddy et al., 2022, Gorbunov et al., 2023a]. It is worth
'We assume that the problem (1) has unique solution x.. This assumption can be relaxed, but for simplicity of exposition, enforce it.
"This assumption gives Byzantine workers a lot of power and rarely holds in practice. Nevertheless, if the algorithm is robust to such workers, then it is provably robust to literally any type of workers deviating from the protocol.

---

mentioning that without any kind of bound on the heterogeneity of {Filieg it is impossible to tolerate Byzantine workers. In addition, homogeneous case (Ç 0) is also very important and arises in collaborative learning, see [Kijsipongse et al., 2018, Diskin et al., 2021].
Finally, formulate here several assumptions on operator F. Each particular result in this work relies only on subset of listed assumptions.
Assumption 3. Operator F
R2 + R is L-Liscchitz i.e,
[F(x) - F(y)ll - -|| yll, Va.yER.
(Lip)
Assumption 4. Operator F R + Rdd is u-quasi strongly monotone, i.e., for μ
(F(x), x x') u|| x²1?? V e R².
(QSM)
Assumption 5. Operator F [R + R is monotone, i.e.,
(F(x) - F(y), y) 2 0, A Vz,yER
(Mon)
Assumption 6. Operator F Rd + Rd is E-star-cocoercive, i.e., for 220 20
1 1 [(x))) VæERd.
(F(x), x - x²) z
(SC)
Assumptions 3 and 5 are quite standard for the literature on VIs. Assumptions and can be seen as structured non-monotonicity assumptions. Indeed, there exist examples of non-monotone (and even non-Lipschitz) operators such that Assumptions 4 and holds [Loizou et al., 2021]. However, Assumptions 3 and 5 imply neither (QSM) nor (SC). It is worth mentioning that Assumption 4 is also known under different names, i.e., strong stability [Mertikopoulos and Zhou, 2019] and strong coherent [Song et al., 2020] conditions.
Robust aggregation. We use the formalism proposed by Karimireddy et al. [2021, 2022].
Definition 1.1 ((ō, RAGG [Karimireddy et al., 2021, 2022]). Let there exist a subset G of random vectors (y1,..., yn such that G 2 (1 - d) for some < 1/2 and Elly; - y S p² for any fixed pair i, E & and some p 0. Then, ÿ RAGG(By....... yn.) called (6, cr.buut aggregator if for some constant e 2 0
E 1 u|8] S c5p²,
where y to Eieg Vs- Further, if the value of p is not used compute y. then ÿ is called agnostic (8, c)-rubust aggregator and denoted as ÿ ARAGG y.
The above definition is tight in the sense that for any estimate ÿ the best bound one guarantee is E
| || ((6pp) [Karimireddy et al., 2021]. Moreover, there are several examples of (6, c) robusttt aggregation rules that work well in practice; see Appendix B.
Another important concept for Dyzantine-robus learning is the notion of permutation inveriance.
Definition 1.2 (Permutation invariant algorithm). Define the set of stochastic gradients computed by each of the n workers some round to be .p.t....,,9n... For a good worker G. these represent the true stochastic gradients whereas for a bad worker E B. these represent arbitrary vectors. The output of any optimization algorithm ALG is a function of these gradients. A permutation-invan invariant algorithm is one which for any set of permutations over t rounds [Ti...., ) its output remains unchanged if we permute the gradients.
In.1h:
[g. (m).))
ALG
ALG
( gant
As Karimireddy et al. [2021] prove, any permutation-invarian algorithm fails to converge any predefined accuracy the solution (under Assumption 1) even all regular workers have the same operators/fumctions, i.., even when Ç 0.
3

---

Table I: Summary of known and new complexity results for Byzantine-robuut methods for distributed variational inequalities. Column "Setup" indicates the varying assumptions. By the complexity, we mean the number of stochastic oracle calls needed for a method to guarantee that Metrie v & (for RDEG P (Metric I }} 2 ÔRDEG. ÅRDEG E (0. 11 and "Metric" is taken from the corresponding column. For simplicity, we omit numerical and logarithmic factors in the complexity bounds. Column "BS" indicates the minimal batch-size used for achieving the corresponding complexity. Notation: c, ò are robust aggregator parameters; a = momentum parameter; 3 = ratio of inner and outer stepsize in SEG-like methods; total numbers of peers;
number of checking peers; G = number of peers following the protocol; R = any upper bound on || x ||: quasi-strong monotonicity parameter; star-cocoercivity parameter; L Lipschitzness parameter; o² bound the variance. The definition x" can vary; see corresponding theorems for the exact formulas.
Sctup
Method
Citation
Metric
Complexity
BS
SGDA-RA
Cor.
ola"
M-SGDA-RA
Cor,
ole" aPptc
SC,
uaa odan me
QSM
SGDA-CC
Cor,
E||Ø" x11
ne
p n'o m
R-SGDA-CC
Cor,
+
SEG-RA
Cor. 3
Ag
Ap-
Lip.
SEG-CC
Cor. 9
B|[a=" - 1/9
1.
QSM
By-me n my/ie
R-SEG-CO
Cor. 11
mae
Lip.
RDEG
Adihi et al. [2022]()
||a"" - x: 112
QSM
consider only homogeneous case (Ç = 0).
1.2 Our Contributions
Now we are ready to describe the main contributions of this work.
Methods with provably robust aggregation. We propose new methods called Stochastic Gradient Descent-Ascent and Stochastic Extragradient with Robust Aggregation (SGDA-RA and SEG-RA) variants of popular SGDA [Dem' yanov and Pevnyi, 1972, Nemirovski et al., 2009] and SEG IKorpelevich, 1976, Juditsky et al., 2011]. We prove that SGDA-RA and SEG-RA work with any (6, c)-robust aggregation rule and converge to the desired accuracy if the butchsize is large enough. In experiments, we observe that SGDA-RA and SEG-RA outperform RDEG in several cases.
Client momentum. As the next step, we add client momentum to SGDA-RA and propose Momentum SGDA-RA (M-SGDA-RA), As is shown by [Karimireddy et al., 2021, 2022], client momentum helps to break the permutation invariance of the method and ensures convergence to any predefined accuracy with any batchsize for non-convex minimization problems. In the case of star-cocoercive quasi-strongly monotone VIs, we prove the convergence to the neighborhood of the solution; the size of the neighborhood can be reduced via increasing batchsize only similarly to the results for RDEG, SGDA-RA, and SEG-RA. We discuss this limitation in detail and point out the non-triviality of this issue. Nevertheless, we show the experiments that client momentum does help to achieve better accuracy of the solution.
Methods with random checks of computations. Finally, for homogeneous data case (C 0), we propose a version of SGDA and SEG with random checks of computations (SGDA-CC. SEG-CC and their restarted versions R- SGDA-CC and --SG--CC). We prove that the proposed methods converge to any accuracy of the solution without any assumptions on the batchsize. This is the first result of this type on Byzantine robustness for distributed VIs. Moreover, when the target accuracy of the solution is small enough, the obtained convergence rates for R-SGDA-CG and R-SEG-CC are not worse than the ones for distributed SGDA and SEG derived in the case of 8 (no Byzantine workers); see the comparison of the convergence rates in Table 1. In the numerical experiments, we consistently observe the superiority of the methods with checks of computations to the previously proposed methods.

---

1.3 Related Work
Byzantine-robust methods for minimization problems. Classical distributed methods like Par- allel SGD [Zinkevich et al., 2010] cannot tolerate even one Byzantine worker. The most evident vulnerability of such methods is an aggregation rule (averaging). Therefore, many works focus on designing and application of different aggregation rules to Parallel SGD-like methods [Blanchard et al., 2017, Yin et al., 2018, Damaskinos et al., 2019, Guerraoui et al., 2018, Pillutla et al., 2022]. However, this is not sufficient for Byzantine robustness: there exist particular attacks [Baruch et al., 2019, Xie et al., 2019] that can bypass popular defenses. [Karimireddy et al., 2021] formalize the definition of robust aggregation (see Definition 1.1), show that many standard aggregation rules are non-robust according to that definition, and prove that any permutation-invent fixed batchsize can converge only to the ball around the solution with algorithn-independenn radius. Therefore, more in-depth algorithmic changes are required that also explain why RDEG, SGDA-RA and SEG-RA are not converging to any accuracy without increasing batchsize.
algorithm with a
One possible way to resolve this issue is to use client momentum [Karimireddy et al., 2021, 2022] that breaks permutation- invariance and allows for convergence any accuracy. It is also worth mentioning a recent approach by [Allouah et al., 2023], who propose an alternative definition of robust aggregation the one considered in this paper, though to achieve the convergence any accuracy in the homogeneous case [Allouah et al., 2023] apply client momentum like in [Karimireddy el al., 2021, 2022]. Another line of work achieves Byzantine robustness through the variance reduction mechanism [Wu et al., 2020, Zhu and Ling, 2021, Gorbunov et al., 2023a]. Finally, for the homogeneous data case, one can apply validation test [Alistarh al., 2018, Allen Zhu al., 2021] or checks of computations [Gorbunov et al., 2022b]. For the summary of other advances, we refer to [Lyu et al., 2020].
Methods for min-max and variational inequalities problems. As mentioned before, min- max/variational inequalities (VIs) problems have noticeable differences with standard minimization. In partieular, it becomes evident from the differences in the algorithms' behavior. For example, di- rect analog of Gradient Descent for min-max/Vis maas/VIs---.. Gradient Descent-Ascent (GDA) [Krasnosel skii, 1955, Mann, 1953, Dem' yanov and Pevnyi, 1972, Browder, 1966] fails to converge for simple bilinear game. Although GDA converges for a different class of problems (cocoercivee/tar-cccoerre) ones) and its version with alternating steps works well in practice and even provably converges locally [Zhang et al., 2022], many works focus on Extragradient (EG) type methods [Korpelevich, 1976, Popov, 1980] due to their provable convergence for monotone Lipschitz problems and beyond [Tran-Dinh) 2023]. Stochastic versions of GDA and EG (SGDA and SEG) are studied relatively well, e.g., see [Hsich et al., 2020, Loizou et al., 2021, Mishchenko et al., 2020, Pethick et al., 2023] for the recent advances.
On the results from [Adibi et al., 2022]. In the context of Byzantine robustness for distributed min- max/VIs, the only existing work is [Adibi et al., 2022]. The authors propose a method called Robust Distributed Extragradient (RDEG)
distributed version of EG that uses a univariate trimmed-men mean estimator from [Lugosi and Mendelson, 2021] for aggregation. This estimator satisfies a similar property to (4) that is shown for 5 < 1/16 and large enough n (see the discussion in Appendix B). In contrast, the known (ō, c)-rouust aggregation rules allow larger 8, and do not require large n. Despite these evident theoretical benefits, such aggregation rules were not considered in prior works on Byzantine robustness for distributed variational inequalities//innnaax problems.
Main Results
In this section, we describe three approaches proposed in this work and formulate our main results.
2.1 Methods with Robust Aggregation
We start with the Stochastic Gradient Descent-Accent with (8, co-buustt aggregation (SGDA-RA):
++1 = x" - -RRAAo(gi....... gi), where of = -g( Vieg G and gi = ViEB,
where hoT sampled independently. The main result for SGDA-RA is given below.
5

---

Theorem 1. Let Assumptions 1, 2, 4 and 6 hold. Then after ' iterations SGDA-RA (Algorithm 1)
with (6, c)-GGG and 7 S 22 outputs x" such that
B8| 10" - x= x01 =
7/4 T 2
270 2ye0 + 12(²) + n²2
có + 12(²)
x
x
G
/
The first two terms in the derived upper bound are standard for the results on SGDA under Assump- tions I, 4, and 6, e.g., see [Beznosikov et al., 2023]. The third and the fourth terms come from the presence of Byzantine workers and robust aggregation since the existing (6, c)-bbustt aggregation rules explicitly depend on ó. The fourth term cannot be reduced without increasing batchsize even when Ç = 0 (homogeneous data case). This is expected since SGDA-RA is permutation invariant. When Ø = 0 (regular workers compute full operators), then SGDA-RA converges linearly to the ball centered at the solution with radius ( vo8(/u) that matches the lower bound from [Karimireddy et al., 2022]. In contrast, the known results for RDEG are derived for homogeneous data case (ç = 0). The proof of Theorem I deferred Appendix D.I.
Using a similar approach we also propose a version of Stochastic Extragradient method with (6, robust aggregation called SEG-RA:
n' = x 7 R.RGAGG (g)
ge where gē. = =g((=', ,.), V G and g = A E B, Inn.) where on. ( m.). Vi E G and g Vie B,
att = x.' 72 (GGG
where fgh, hec and {9 hee are sampled independently. Our main convergence result for SEG-RA is presented in the following theorem; see Appendix D.2 for the proof.
Theorem 2. Let Assumptions 1, 2, 3 and 4 hold. Then after T iterations SEG-RA (Algorithm 2) with (6, c)AGG, 7/ S 2u+22 and B =4/m S 1/4 outputs x² such that
---1==111
x01 S (1- 1 (-44
|| 11²
8/10² M3G Sco(240² + 12(3)
71 3p
2 μ22
Similar to the case of SGDA-RA RA, the bound for SEG-RA has the term that cannot be reduced without increasing batchsize even in the homogencous data case. RDEG, which also modification of SEG, has the same linearly convergent term, but SEG-RA has a better dependence on the batchsize, needed to obtain the convergence any predefined accuracy, that is O(E-1) versus (E 2) for RDEG; see Cor. 3.
In heterogeneous case when 0, SEG-RA also converges linearly the ball centered at the solution with radius @(VBC//)) that matches the lower bound.
2.2 Client Momentum
Next, we focus on the version of SGDA-RA that utilizes worker momentum m/. i.e..
x x RRAGG ..... m,), with m (1 ai a)m f- aag
where gf = (x(. Vi E G and gi = * V i E and {g' lreg are sampled independently. Our main convergence result for this version called M-SGDA- is summarized in the following theorem.
Theorem 3. Let Assumptions 1, 2, 4, and 6 hold. Then after T iterations M-SGDA-RA (Algorithm 3)
with (6, C)-RAGG outputs a² such that
E ||Ia""
- x+ 111
21120 11 WnaWT
87c0 + 12(2)
6y0²
4c5(240² 12ç²)
na2
G
11aa2
where ह.. I WT Σ w.
Σ/=0 (1-1-)=--0 ~')
Wi (1
and WT -T- Wt-
'SGDA-basse based and SEG- based methods are typically analyzed under different assumptions. Although (SC) follows from (Lip) and (QSM) with f= L²/u. some operators may satisfy (SC) with significantly smaller é. Next, when μ 0, SGDA is not guaranteed to converge [Gidel et al., 2018J, while SEG does

---

Despite the fact that M-SGDA-RA is the first algorithm (for VIs) non con-invariant to permutations, also requires large batches to achieve convergence any accuracy. Even in the context of minimization, which is much easier than VI, the known SOTA analysis of Momentum-SGo relies in the convex case on the unbiasedness of the estimator that not available due to a robust aggregation. Nevertheless, we prove" the convergence to the ball centered at the solution with radius O /ove see Appendix D.3. Moreover, we show that M-SGDA-RA outperforms in the experiments other methods that require large batches.
2.3 Random Checks of Computations
We start with the Stochastic Gradient Descent- Accent with Checks of Computations (SGDA-CC). At each iteration of SGDA-CC, the server selects m workers (uniformly at random) and requests them to check the computations of other m workers from the previous iteration. Let V2 be the set of workers that verify/check computations, A, are active workers at iteration t, and V2 n A = Ø. Then, the update of SGDA-CC can be written as
xr x." 79' if g
1 [4
Eg
Σ
. 9
is accepted,
SEA.
where (g,(2', heg are sampled independently.
The acceptance (of the update) event occurs when the condition [ g: < S Co holds for the majority of workers. If g' rejected, then all workers re-sample g: (x' 4 until acceptance is achieved. The rejection probability is bounded, per [Gorbunov et al.. 2022b], and can be adjusted by choosing a constant C = (()). We assume that the server knows the seeds for generating randomness on workers, and thus, verification of computations is possible. Following each aggregation of go g;(x', E the server selects uniformly at random 2m workers: m workers check
the computations at the previous step of the other m workers. For instance, at the (t + 1)-th iteration, the server asks checking peer i to compute 9, (z', E)), where j a peer being checked. This is possible if all seeds are broadcasted at the start of the training. Workers assigned to checking do not participate in the training while they check and do not contribute to g'. Therefore, each Byzantine peer is checked at each iteration with probability of ~ m/n. by some good worker (see the proof of Theorem 4). If the results are mismatched, then both the checking and checked peers are removed from training.
This design ensures that every such mismatch, whether it is caused by honest or Byzantine peers, eliminates at least one Byzantine peer and at most one honest peer (see details in Appendix E) It's worth noting that we assume any information is accessible to Byzantines except when each of them will be checked. As such, Byzantine peers can only reduce their relative numbers, which leads us to the main result for SGDA-CC, which is presented below.
Theorem Let Assumptions I, 4 and 6 hold. Then after T iterations SGDA-CC (Algorithm 5) with S z outpuls x. such that
E 1 T+I
xx" 112 S (1
7/4
T+1
1000
x=1'
4y0²
2q02nB (1 +2))
2
11(n - 2B m)
m 11
where q = 2022 + 12 + n-28-m²
12
(1) since = O(1.
The above theorem (see Appendix E. for the proof) provides the first result that does not require large batchsizes converge to any predefined accuracy. The first and the second terms in the convergence bound correspond to the SOTA results for SGDA [Loizou et al., 2021]. Similarly to the vanilla be obtained by decreasing stepsize, however, such an approach does not
SGDA, the convergence benefit from collaboration, since the dominating term yo02n (coming from the presence of Byzantine workers) is not inversely dependent on n. Moreover, the result is even worse than for single node SGDA in terms of dependence on n.
'In contrast to Theorems 1-2, result from Theorem is given for the averaged iterate. consider the averaged iterate to make the analysis simpler. We believe that one can extend the analysis to the last iterate as well, but we do not do it since we expect that the same problem (the need for large batches) will remain in the iss-iiteate analysis.
7

---

To overcome this issue we consider the restart technique for SGDA-CC and propose the next algorithm called R-SGDA-CC. This method consists of stages. On the t-th stage R-SGDA-CC runs SGDA-CC with N for K2 iterations from the starting point क', which is the output from the previous stage, and defines the obtained point as a++1 (see details in Appendix E.2). The main result for R-SGDA-CC is given below.
Theorem 5. Let Assumptions
and 6 hold. Then, after
log Rta
restarts
R-SGDA-CC (Algorithm 6) with 7
min
2B R
and
22
6a 20"22' Ke
72ga "2" 13"
K₁ = max
2
34n B V 92"
where R 2 ||000
x
outputs H" such that
p
2
m) R.
mycR
E||3"
x= 112 E. Moreover, the total number of executed iterations of SGDA-CC is
Σk.=C - log
RRg
0² +
nBo
(5)
(n - 2B -0--11 -m)E myHE
The above result implies that R-SGDA-CC also converges to any accuracy without large batch- sizes (see Appendix E.2 for details). However, as the accuracy tends zero, the dominant term (a-2B-m)pu inversely depends on the number of workers. This makes R-SGDA-CG benefit from collaboration, as the algorithm becomes more efficient with an increasing number of workers. More- over, when B and m are small the derived complexity result for R- R-SGDA-CC matches the one for parallel SGDA [Loizou et al., 2021], which is obtained for the case of no Byzantine workers.
Next, we present modificaaion of Stochastic Extragradient with Checks of Computations (SEG-CC): a' = x 71
if g' [.. EiE g $ is accepted,
a= = x² 720
TA. if 9 1 Eiea,gi n/) accepted,
where (x", hee and {g.("', nn) are sampled independently. The events of acceptance G', (or ge) happens if
- . S Co (or - .n)l Co)
holds for the majority of workers. An iteration of SEG-CC actually represents two subsequent iteration of SGDA-CC,
refer to the beginning of the section for more details. Our main convergence results for SEG-CC are summarized in the following theorem; see Appendix E.3 for the proof.
Theorem 6. Let Assumptions 1, 3 and hold. Then after T iterations SEG-CC (Algorithm 7) with 71 S 20+21 and B = 72/71 S 1/4 outputs xx such that
E B - x²1|² xx'12 1 n0n
1|00 |
x11 --'1''1'-
20 202
4y1
ngnB m
ppp2n
2B m)
: where q 2C2 12 2 9 (1) since C = O(1).
Similarly to SGDA-CC, SEG-CC does not require large batchsizes to converge to any predefined accuracy and does not benefit of collaboration, though the first two terms correspond the SOTA convergence results for SEG under bounded variance assumption [Juditsky et al., 2011]. The last term appears due to the presence of the Byzantine workers. The restart technique can also be applied; see Appendix E.4 for the proof.
Theorem 7. Let Assumptions 3, 4 hold. Then, after
log Ra
restarts
R-SEG-CC (Algotithm 8) with n. min 21. V
GG-B-a R2
mnH 8g Br
16
min
R2 m²
G B B-m) R and K₁
max 8L 16na B B 92
256 P'2 (G
41. 24 m
640=K,
mpR
m
where R 2 1000 xt1 outputs 3' such that E|@"" - x1 < E. Moreover, the total number of
executed iterations of SEG-CC is
( log RR
o²
nBa my/re
Σ Ki
+
(6)
(n 2B m)
8

---

The above result states that R-SEG-CC also converges to any accuracy without large batchsizes; see Appendix E.4. But with accuracy tending zero (e 0) the dominating term (n-2B-m))p inversely depends on the number of workers, hence R-SEG-CC benefits from collaboration. Moreover, when B and m are small the derived complexity result for R-SEG-CC matches the one for parallel/mini- batched SEG [Juditsky et al., 2011], which is obtained for the case of no Byzantine workers.
o²
Numerical Experiments
Quadratic game. quadratic game
To illustrate our theoretical results, we conduct numerical experiments on
1 2 AI.i + A2,2 - A3.1 + bI b2
1
mim maxx
The above problem can be formuuaulte as a special case of (1) with defined as follows:
F(x)
A by, where x = (2 TT b, (b 62,)
(7)
with symmetric matrices A s.t. l x J A, A E Rdd and by E IR:; see Appendix F for the detailed description.
We set 100, μ = 0.1, s 1000 and d = 50. Only one peer checked the computations on each iteration (m 1). We used RFA (geometric median) with bucketing as aggregator since it showed the best performance. For approximating the median we used Weiszfeld's 's method with 10 iterations and parameter
0.1 [Pillutla al., 2022]. RDEG [Adibi al., 2022] provably works only if n 2 100, so here we provide experiments with n = 150, B 20, y = 2e We set the parameter 0.1 for M-SGDA-RA, and the following parameters for RDEG: ORDEG 0.06, ŌADEG 0.9 and theoretical value of e; see Appendix for more experiments. We tested the algorithms under the following attacks: bit flipping (BF), random noise (RN), inner product manipulation (IPM) Xie et al. [2019] and "a little is enough" (ALIE) Baruch et al. [2019].
Robust Neural Networks training. Let f(u x, v) be the loss function of neural network with parameters I2 given input E Rh and label y. For example, in our experiments, we let be the cross entropy loss, and {1i, y:)} is the MNIST dataset. Now consider the following objective:
N
A2 1012 2
min max oE VER T
Σ s(u; + u. mR)
N
This min-ma max objective adds an extra adversarial noise variable to the input data such that it maximizes the loss, the neural network should become robust to such noise it minimizes the loss. We can reformulate this objective as a variational inequality with
1 N F(x) = N 1=1
Fx(x:) =
V V. (u; - v. v.) + A1
Σ F(z)..
(9)
(u; x4 + v, Mi) + A22
We let n 20, B = 4, \ = O, and A2 = 100. We fix the learning rate to 0.01 and use batch size of 32. We run the algorithm for 50 epochs and average our results across 3 runs. We test the algorithms under the following attacks: i) bit flipping (BF), ii) label flipping (LF), iii) inner product manipulation (IPM) Xie al. [2019], and iv) little is enough (ALIE) Baruch et al. [2019]. We compare our algorithm SGDA-CC against the following algorithms: i) SGDA-RA, ii) M-SGDA-RA, and iii) RDEG Adibi al. [2022]. We use RFA with bucket size 2 the robust aggregator. The results are shown Figure 2. Specifically, we show the validation error on MNIST after each epoch. We that SGDA-CC performs the best, followed closely by M-SGDA-RA.
4 Conclusion
This paper proposes several new algorithms for Byzantine- distributed variational inequalities and provides rigorous theoretical convergence analysis for the developed methods. In particular,

---

ALIE (7e=03)) 2012
IF. 26-3
20-1
PMllee 1601
10-1
AN (law-1) Mao1
Beota De Py
S00TA (D-30
S0OM De-32
COSRA De440
50
1E-4
Humber prrdeert
Sunder alypedeee
ALIE (36-01) 2002
BF: 2am3
22 taw3
AN: 12e--33 bomd
10-1
12-1
wineee fay
NOCEMAA 2e:0
52840C Decd)
506ACC Gedd!
10
Mander craderts
Munber of Coreebrrt
Sumder Fopaddrrs
Sunder www.dealeeett.....oo..
Figure 1: Error plots for quadratic games experiments under different Byzantine attacks. The first row shows the outperformance of M-SGDA-RA over methods without checks of computations. The second row illustrates advantages of SGDA-CC and SEG-CC.
Adversariel MNIST Error, sttack -
Adversarial MNIST Error, attack
T6
stratogy
strategy
SGDA-CC
SADA-CC
SGDA-RA
Eroor
M-SGDA-RA
M-SCDA-RA
10
10
20
30
40
50
10
30
40
60
Epochs
Epochs
Adversarial
stralegy
stretegy
SGDA-CC
SEDA-CC
SGDA-RA
Erter
M- M-SGGIA.RA RA
Error
M-SGDA
10
1
10
20
30
40
50
10
30
50
Epochs
Epochs
Figure 2: Error plots for the robust neural network experiment on MNIST under different byzantine attacks (BF, LF, IPM, and ALIE). Each algorithm shown with a consistent choice of color and style across plots, indicated in the legends.
propose the first methods in this setting that provably converge to any predefined accuracy in the case of homogencous data. We believe this is an important step towards building a strong theory of Byzantine robustness in the case of distributed VIs.
However, our work has several limitations. First of all, one can consider different/more general assumptions about operators [Beznosikov et al., 2023, Gorbunov et al., 2022a, 2023b] in the analysis of the proposed methods. Next, as we mention the discussion after Theorem 3, our result for M-SGDA-RA requires large batchsizes, and it remains unclear to whether this requirement can be removed. Finally, the only results that do not require large batchsizes are derived using the checks of computations that create (although small) computation overhead. Obtaining similar results without checks of computations remains an open problem. Addressing these limitations is a prominent direction for future research.
10

---

Acknowledgments and Disclosure of Funding
This work of N. Tupitsa was supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000773331PSQ0000 agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138.
and the
References
A. Adibi, A. Mitra, G. J. Pappas, and H. Hassani. Distributed statistical min-max learning in the presence of byzantine agents. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 4179-4184. IEEE, 2022.
D. Alistarh, Z. Allen-Zhu, and J. Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018.
Z. Allen-Zlne Zhu, F. Ebrahimianghazami, J. Li, and D. Alistarh. Byzantine-resilien non-convex stochastic gradient descent. In International Conference on Learning Representations, 2021.
Y. Allouah, S. Farhadkhani. R. Guerraoui, N. Gupta, R. Pinot, and Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference Artificial Intelligence and Statisties, pages 1232-1300. PMLR, 2023.
M. Baruch, G. Baruch, and Y. Goldberg. A little is enough: Circumventing defenses for distributed learning, 2019.
A. Beznosikov, E. Gorbunov, H. Berard, and Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 172-235. PMLR, 2023.
Blanchard, E. M. Mhamdi, R. Guerraoui, and J. Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
J. Bose, G. Gidel, H. Berard, A. Cianflone, P. Vincent, S. Lacoste-Julien, and W. Hamilton. Ad- versarial example games. Advances in neural information processing systems, 33:8921-8934, 2020.
E. Browder. Existence and approximation solutions of nonlinear variational inequalities. Proceedings of the National Academy of Sciences, 1680):6000- 1966.
Y. Chen, Su, and J. Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1 (2):1-25, 2017.
G. Damaskinos, E.-M. El-Mhamdi, R. Guerraoui, A. Guirguis, and S. Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. Proceedings of Machine Learning and Systems, 1:81 181-106, 2019.
V. F. Dem' yanov and A. B. Pevnyi. Numerical methods for finding saddle points. USSR Computa- tional Mathematics and Mathematical Physics, 12(5):11-52, 1972.
M. Diskin, A. Bukhtiyarov, M. Ryabinin, L. Saulnier, A. Sinitsin, D. Popov, D. V. Pyrkin, M. Kashirin,
A. Borzunov, A. Villanova del Moral, et al. Distributed deep learning in open collaborations. Advances in Neural Information Processing Systems, 34:7879-7897, 2021.
Facchinei and J.-S. Pang. Finite-dimensionl variational inequalities and complementarity prob- lems. Springer, 2003.
G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequality perspec- tive on generative adversarial networks. International Conference on Learning Representations, 2018. URL https:

---

I. Goodfellow, J. Pougee-Abaadin M. Mirza, B. Xu, D. Warde-Farley. S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
1. Goodfellow, Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations, 2015.
E. Gorbunov, D. Kovalev, D. Makarenko, and P. Richtárik. Linearly converging error compensated sgd. Advances in Neural Information Processing Systems, 33:20889-20900, 2020.
E. Gorbunov, H. Berard, G. Gidel, and N. Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 7865-7901. PMLR, 2022a.
E. Gorbunov, A. Borzunov, M. Diskin, and M. Ryabinin. Secure distributed training at scale. In International Conference on Machine Learning, pages 7679-7739. PMLR, 2022b. URL sttaps://proceedingg mlr. wal...pees//v66 prtp.rrre////////oooooooaaa hatpaaooo//gggobbboorroeo
E. Gorbunov, S. Horváth, P. Richtárik, and G. Gidel. Variance reduction is an antidote to byzan- tines: Better rates, weaker assumptions and communication compression as cherry on the top. International Conference Learning Representutions, 2023a.
E. Gorbunov, Taylor, S. Horváth, and G. Gidel. Convergence of proximal point and extragradient- based methods beyond monotonicity: the case of negative comonotonicity. In International Conference on Machine Learning, pages 11614-11641. PMLR, 2023b.
R. Guerraoui, S. Rouault, et al. The hidden vulnerability of distributed learning in byzantium. In International Conference Machine Learning, pages 3521 PMLR, 2018
I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: survey of theory, algorithms and applications. Mathematical programming, 48(1-3); 161-220, 1990.
Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 13:16223-16234, 2020.
A. Juditsky, A. Nemirovski, and Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
S. P. Karimireddy, L. He, and M. Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pages 5311-5315 PMLR, 2021.
S. P. Karimireddy, L. He, and M. Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In International Conference on Learning Representations, 2022. URL https: // //arxiv..t org/pdft http/dff20000 /200 09365. pdf.
E. Kijsipongse, A. Piyatumrong, et hybrid gpu cluster and volunteer computing platform for scalable deep learning. The Journal of Supercomputing, 74(7):323-3363,, 2018.
D. P. Kingma and J. Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6900 2014.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
M. A. Krasnosel'ski: Two remarks the method of successive approximations. Uspekhi matem- aticheskikh nauk, 10(1):123-127, 1955.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
12

---

L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982.
C. Li. Demystifying gpt-3 language model: A technical overview, 2020. "https://lambdall gpt-3".
N. Loizou, H. Berard, G. Gidel, I. Mitliagkas, and Lacoste-Julien. Stochastic gradient descent- ascent and consensus optimization for smooth games: Convergence analysis under expected co-coereivity. Advances in Neural Information Processing Systems, 34:19095-19108, 2021.
G. Lugosi and S. Mendelson. Robust multivariate mean estimation: the optimality of trimmed mean. 2021.
L. Lyu, H. Yu, X. Ma, L. Sun, J. Zhao, Q. Yang, and P. S. Yu. Privacy and robustness in federated learning: Attacks and defenses. arXiv preprint arXiv:2012.0633/) 2020.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
W. R. Mann. Mean value methods in iteration. Proceedings of the American Mathematical Society, (3):006-510, 1953.
Mertikopoulos and Z. Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173(1):465-500) 2019.
K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik, and Y. Malitsky. Revisiting stochastic extra- gradient. In International Conference on Artificial Intelligence and Statistics, pages 4573-4582. PMLR, 2020.
T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httpp://openreeviv. net/ f BatimmdddBBQRgaaa
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-166) 2009.
Pethick, O. Fercoq, P. Latafat, P. Patrinos, and V. Cevher. Solving stochastic weak minty variational inequalities without increasing batch size. In The Eleventh International Conference on Learning Representations, 2023.
K. Pillutla, S. M. Kakade, and Z. Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70:1 142-1154, 2022.
L. D. Popov. A modification of the arrow-huricz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
M. Ryabinin, E. Gorbunov, V. Plokhotnyuk, and G. Pekhimenko. Moshpit sgd: Communication- efficient decentralized training on heterogeneous unreliable devices. Advances in Neural Informa- tion Processing Systems, 34:18195-18211, 2021.
E. K. Ryu and W. Yin. Large-Scale Convex Optimization: Algorithms &nnalyess via Monotone Operators. Cambridge University Press, 2022.
C. Song, 7. Zhou, Y. Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non- monotone variational inequalities. Advances in Neural Information Processing Systems, 33: 14303-14314, 2020.
S. U. Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint
197.:v/907.04232 2019.
Q. Tran-Dinh. Sublinear convergence rates of extragradient-rype methods: A survey on classical and recent developments. arXiv preprint arXi::2303.17192. 2023.
13

---

A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference on Machine Learning, pages 3540-3549. PMIR, 2017.
G. Wayne and L. Abbott. Hierarchical control using networks trained with higher-level forward models. Neural computation, 26(10):21632211 2014.
Z. Wu, Q. Ling, T. Chen, and G. B. Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 08:4583-4555 2020.
C. Xie, S. Koyejo, and I. Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation, 2019.
Y.-R. Yang and W.-J Li. Basgd: Buffered asynchronous sgd for byzantine learning. International Conference on Machine Learning, pages 11751-11761. PMLR, 2021.
D. Yin. Y. Chen, R. Kannan, and P. Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650-5659, PMLR, 2018.
G. Zhang, Y. Wang, L. Lessard, and R. B. Grosse. Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 7659-7679. PMLR, 2022.
H. Zhu and Q. Ling. Broadcast: Reducing both stochastic and compression noise to robustify communication-effiene federated learning. arXiv preprint
2021.
M. Zinkevich, M. Weimer, L. Li, and A. Smola. Parallelized stochastic gradient descent. Advances in neural information processing systems, 23, 2010.
14

---

Contents
Introduction
1.1
Setting
1.2
Our Contributions
1.3
Related Work
2
Main Results
2.1
Methods with Robust Aggregation
2.2 Client Momentum
2.3
Random Checks of Computations
3
Numerical Experiments
Conclusion
Examples of cobbust Aggregation Rules
17
A.1 Aggregators
17
A.2 Bucketing algorithm
17
A.3 Robust Aggregation examples
17
B Further Details on RDEG
19
Auxilary results
21
C.1 Basic Inequalities
21
C.2 Usefull Lemmas
21
D Methods that use robust aggregators
24
D.1 Proofs for SGDA-RA
24
D.1.1
Quasi-Strongly Monotone Case
24
D.2 Proofs for SEG-RA.......
25
D.2.1 Auxilary results
................................
26
D.2.2
Quasi-Strongly Monotone Case
28
D.3 Proofs for M-SGDA-RA
30
D.3.1
Quasi-Strongly Monotone Case
30
E Methods with random check of computations
35
E.1
Proofs for SGDA-CC.
36
E.1.1
Star Co-coercieve Case
36
E.1.2
Quasi-Strongly Monotone Case
39
E.1.3
Monotone Case
E.2
Proofs for R-SGDA-CC
44
E.2.1
Quasi-Strongly Monotone Case
44
15

---

E,3
Proofs for SEG-CC
46
E.3.1
Auxilary results
46
E.3.2
Lipschitz Case
48
E.3.3
Quasi-Strongly Monotone Case
51
E.3.4
Lipschitz Monotone Case
56
E.4
Proofs for R-SEG-CC
59
E.4.1
Quasi Strongly Monotone Case
59
F
Extra Experiments and Experimental details
61
F.1
Quadratic games
F2
Generative Adversarial Networks
68
16

---

A Examples of (ò, c)-cbuusstt Aggregation Rules
This section is about how construct an aggregator satisfying 1.1.
A.1
Aggregators
This subsection examines various aggregators that lack robustness. It means that new attacks can be easily designed exploit the aggregation scheme, causing its failure. We analyze three commonly employed defenses that are representative.
Krum. For i + j. let i + j denote that æj belongs to the
closest vectors to a;. Then,
KRUM(ZI,..... T.) == argmin Σ 2 2.l1?
Krum is computationally expensive, requiring (n²) work by the server Blanchard et al. [2017]. CM. Coordinate-wis median computes for the k-th coordinate:
(C. xn)] == medi (xn]))) = argmin j=1
[..] jk - [æy]k|]
Coordinate-wee wise median is fast to implement requiring only (n) time Chen et al. [2017]. RFA. Robust federated averaging (RFA) computes the geometric median
REA ...,, a..) == argmin
10 2:1122
Although there is no closed form solution for the geometric median, an approximation technique presented by Pillutla et al. [2022] involves performing several iterations of the smoothed Weiszfeld algorithm, with each iteration requiring computation complexity (()).
A.2 Bucketing algorithm
We use the process of s-bucketing, propose by [Yang and Li, 2021, Karimireddy et al., 2022] to randomly divide n inputs, 31 to En. into [n/s] buckets, each containing no more than s elements. After averaging the contents of each bucket to create y1..... n/sss] we input them into the aggregator AGGR. The Bucketing Algorithm outlines the procedure. Our approach's main feature that the resulting set of averaged Y1, "/.....: U[nns] original inputs.
are more homogeneous (with lower variance) than the
Algorithm Bucketing Algorithm
1: input ( }, s E N, aggregation rule AGGR
2: pick random permutation of [n]
3: compute y; + 1 _k=(i-1)a4) (*()) for = {1,..., [n/s]}
4: output ã (..R(y)....,,//....
|| aggregate after bucketing
A.3 Robust Aggregation examples
Next recall the result from (Karimireddy et al., 2022], that shows that aggregators which saw, can be made to satisfy 1.1 by combining with bucketing.
Theorem 8. Suppose pair i,j & G and some p 2 foror some 8 < 6maxs with 8max to be defined. Then, running Bucketing Algorithm with s Smass
given inputs {Z1,..., xn) such that E x = < p² for any fixed
yields the following:
Krum: KRUM BUCKETING(Z).....
=112 < (8p²²) with 6max <
Geometric median: E RFA BUCKETING(E)...... x < O()p²) with 8max 1
17

---

woss median: E|CM o BUCKETING(21..... R.. - -n)- S (ddpp² with
max
Note that all these methods satisfy the notion of an agnostic Byzantine robust aggregator (Definition 1.1).
18

---

B Further Details on RDEG
Originally RDEG was proposed for min-max problems and represents variation of SEG with Univariate Trimmed-Mean Estimator aggregation rule. For convenience we give here RDEG pseudo- code we used in experiments.
In this section we use the notation ग E (0, 1) for a confidence level.
Robust Distributed Extra-Gradient (RDEG)
Input: TRIM Y
I: for = 1,... do
2:
for worker [n] in parallel
3:
9g. + (x E()
4:
send gg. if i G. else send if Byzantine
5:
(x= TRIM,, (g.......
6:
x² x² -i (x²).
7:
for worker i [m] in parallel
8:
9n, 9:''',, mi)
9:
send g if E G. else send if Byzantine
10: 9t (x²) TTIM c.0.5 (0m..--,,000 - In
*+1 x 92 (x").
Performance of Univariate Trimmed-Mean Estimator. The TRIM operator takes as input n vectors, and applies coordinatewisely the univariate trimmed mean estimator from Lugosi and Mendelson [2021], described bellow here as Univariate Trimmed-Mean Estimator Algorithm.
Univariate Trimmed-Mest Estimator Algorithm Lugosi and Mendelson [2021]
Input: Corrupted data set Zi.... Zn/2, Zz.... Zn/2 corruption fraction 5, and confidence level
1: Set 86 24 log(1/n)
2: Let Zi S Z S Tn/2 represent non-decreasing arrangement of {2,) (E(/22()))) Compute
quantiles: Z/m and Z(1-e)n/2
3: Compute robust mean estimate ÿız as follows:
2 n/2
B I > B
Pz
Σ i=1
Φ Z.): (xx())
[7, 3]
? < 7
The following result on the performance of Univariate Trimmed-Meat Estimator plays a key role in the analysis of RDEG.
Theorem. (Adibi et al., 2022, Theorem 1] Consider the trimmed mean estimator. Suppose 8 E [0, 1/16), and let E 10 be such that 4e 4/2 Then, there exists universal constant such that with probability at least
n.
log(1 (TT)
jzz - uzl S coz
Vo +
Using the latter componentwise result the authors states that
@g (x*) - F(x S co Vv
log 11m)
In fact this result is very similar to the Definition 1.1. The main difference is that for Univariate Trimmed-Men Meea Estimator we have bound with some probability. The other difference that using
19

---

the following representation of the result with p² c²o²
I (a') F(x")| 8p² p² loggLL/T)
w.p. 1 -
Univariate Trimmed- Meaa Estimator has the additional term inversely depending on the number of workers.
Moreover, the result requires 5 E [0. 1/16/ in contrast to the aggregators we used, that work for wider range of corruption level å [0, 1/5].
Performance guarantees for RDEG. case.
The authors of [Adibi et al., 2022] consider only homoge-
Theorem. [Adibi et al., 2022, Theorem 3] Suppose Assumptions 3 and 4 hold in conjunction with the assumptions on 5 and n: the fraction of corrupted devices satisfies E 1/.1/, and the number of agents is sufficiently large: 48 log(16dT Then, with 1/(4TT and step-size S 1/L).. RDEG guarantees the following with probability at least 1/T:
8ca Rs
(V++ 1og(4d)2)
- T+111 2e
-
In R2 +
(10)
L
where &. = L.L.
The result implies that RDEG benefits of collaboration only when the corruption level is small. In ldd(A
fact, the term log[AdTT)
48 log 164 1/48, so the corruption level should be less than 1/48 to SEG-CC that requires corruption level only less than 1/5. Moreover, case of larger corruption level, RDEG converges to a ball
make RDEG significantly benefit of collaboration in contrast
centered at the solution with radius T
contrast to our methods SGDA-RA, SEG-RA Ro
and M-SGDA-RA converge to a ball centered at the solution with radius (V chrz
that has
better dependence on It is crucial with increasing batchsize (b = batchsize), since O² depends on batchsize J
20

---

C
Auxilary results
C.1 Basic Inequalities
For all a, b E R and À > 0, E (0, 1]
|aa|
[[a b)l S 2A
(11)
2
||a + b112 S 2|1a| + 2111112
(12)
(1 + 1 |b112
a|a + b11 < (1 + 1a||a|1 2
(13)
(a. b) (Ila + bll2
-11a [001))
(14)
1
(a, b)
(-
||a
bll2
+ ||a|2 + 11b12)
(15)
2
2
Σ
a
S n
||a11?
(16)
1=1
l|a + b112
Σー 2
|1a|1 1611
(17)
(1 2) 11 4
-1
(18)
(1 + - (1- - 1) < 1 0 2
(19)
C.2 Usefull Lemmas
We write of or simply gi instead of (x { when there is no anbiguity.
Lemma C.I. Suppose that the operator F is given in the form (1) and Assumptions I and 6 hold. Then
Eg g(x x 3)1 & (F(()) x x²) + o² G
where Rg = TT, and g(, {) t/ Eieg 9: Ei).
Proof of Lemma C.I. First of one can decomposeda squared norm of a difference and obtain Eelgg(0 {) F(x))l (x e)_l 2(EET(( E), F(x)) + [[(())]
Since g(x = 2/ Eiec gi (x; Ei), by the definition (1) of F and by Assumption one has
Eeg(æ, E) G
Σ
Ee, (x Ec) G
Σ
Fi(x)) F(x),
iEc
and consequently
Bellg(x, E)1 = Belgg(x,E) + - -1
(20)
One can bound Belgg(n, {) ((x))|l² as
1
Eg ()
Eg
(x: Ei) F((x)) -())))())))))
G
iEG
independence of &;
E ll, (x: {.) F(2) <
0²
C
REC
where the last inequality of the above chain follows from (SC). The above chain together with (20)
and (SC) implics the statement of the theorem.
21

---

Lemma C.2. Let K > 0 be a positive integer and m. 12.
MK be random vectors such that
Es [mt] def Elyn !/),.... [[--1] for k 2.... K. Then
K
K
E
Σ
Tk
Elll
(21)
Proof. We start with the following derivation:
K
K-1
K
E
E[[nxx| 1 2
1 Σ
+ E
Σ
R=
K-1
>
= E[|mm|| 11 21
TKK
+ E
k=1
K
K
= E[|lx] | + 2EE
EK [m
m
+
Σ k=1
7k
1=1
K
E|llxx| ||] + E
Applying similar steps to E result.
K-1 k=
7h
E
>>> k=
7h
27
E
Σ k=
Th
we get the
Lemma C.3. Suppose
TK S ro - ar)
C17
+
90
(22)
holds for y S To- Then the choise of
3c0
2
and
Co
7 S min
70:
implies that TK S e for
3ra
K > max
In
Co
To
Proof. Since b then
5 and
212
d125
The choise S min 70: cs
implies that
30g
The choice of K max
In 3ra
implies that ro ay)* < & and finishes the proof.
To
Lemma C.4 (see also Lemma 2 from Stich [2019] and Lemma D.2 from Gorbunov et al. [2020]).
Let (rklazo satisfy
Tk < ro a7) +ar+or
(23)
for all K. 2 with some constants a, 02 0. Ci N 0, 7
Then for
In (max/2, min minfarm Kork a To R2 /e2)))
7 min
%
(24)
a(K 1
have that
ã @x0eep (-axp(aann 1))
Ci ak
C2
TK
+
k²k²
22

---

Moreover тK S E after
K ②
c
c2
+
+
a7o ae
d=
iterations.
Proof. We have
rk ro(1 a7)*k1 + + c272 S ro (xeep(-ann 1)) +17+
(25)
Next we consider two possible situations.
mo /22))) x22//))))) a(K+1)
1. If 70
then we
choose
In max f (2.ii fora //ra//// /c,, 2 /c211) and get that
a(k+
225
To exp (-ay(K + 1)) c.7 + o2?
TK
In (maxf2, minfarok//a d2ro k2 /cat)) a(K + +1))
=
ro
exp
a(K + 1)
+0
C1
02
ak
k²k²
-Im
arak arrok?
exp
In
max
2, min
C1
02
+0
C1
62
ak
a²
4
C2
ak
K²
In 1n(max(2.min( 2 (rok2/o2))) /o2)))
2. If <
then choose y %o which implies that
a(K+1)
PK
ro exp (-aroo + 1)) + c170 + c2
= o (0 + 1)) + G + ak
K2
Combining the obtained bounds we get the result.
23

---

D Methods that use robust aggregators
First of we provide the result of Karimireddy et al. [2022] that describes error of RAGG, where m = ag' (1-a)m²²
Lemma D.1 (Aggregation enror Karimireddy al. [2022]). Given that R AGG satisfies 1.1 holds, the error between the ideal average momentum m' and the output of the robust aggregation rule m for any 2 can be bounded as
m' m 1| S co(p")²
where we define for t Z
( == 4(600² +3(2) + 4(60² -3(-) 3(2) o)
For t 0 we can simplify the bound (p¹)² 24o² + 12ç3.
Moreover, one can state a uniform bound for (p²)²
(0')² s = 240 + 1252.
(26)
D.1 Proofs for SGDA-RA
Algorithm 1 SGDA-RA
Input: RAGG, 7
I: for = ... do
2:
for worker i [n] in parallel
3:
g + g.(2 (x) send g if E G. else send * if Byzantine
Et)
4:
5:
g' == =RAG .gg......hh 9 and x++1 +- x² -9".. // update params using robust aggregate
D.1.1
Quasi-Strongly Monotone Case
Theorem (Theorem 1 duplicate). Let Assumptions 1, 2, 4 and 6 hold. Then after iterations 1
SGDA-RA (Algorithm 1) with (ō, c)-AGG and
27 outputs x² such that
E E|
x'1 (1
7/ T
||0e0
2y0²
2yc8p²
cop²
2
GG
11
+
12
where p² = 240² + 1 by Lemma D.I with a = 1.
Proof of Theorem 1. We start the proof with
| - x x=1 || x= -1''1'' = xx' - x=11²- 2-/g"" -220"-""'""
x² - -x") + +
Since g' =g- pt + Fr one has
||_ 1²11 =||0- =1122-2000 2"''g' -g', x² x²) ('' x² - xx") >
1' 1|?
Applying (11) for (g' - ggg, x² - x²) with \ = and (12) for || -g'-- - gg' + g²1l we derive
2
| t1 - 1²1 -x11
5 (1 + 2/4 xe' x: 2- x. x²)
7/11
2% g'' g" 1|
2n² g' g' 1| 2 g'|
Next by taking an expectation Eg of both sides of the above inequality and rearranging terms obtain
Bellæ* - 11
<
1 11 7/
x0 x=112 - (x(F(x²), x² xx²)
2
+ Ee g'' 5 1| $ +n |g' - -'12 + 2 We 11
27
24

---

Next we use Lemmas C.1 and D.1 to derive
Be|lØ - =011" S
1 + 7/11
|| - + 1778-2111 2 x²)
2
2720²
+ +20pp² (Z+
that together with the choice of
28 and Assumption (QSM) allows to obtain
Be 1
x=1
(1
7/0
x² xx"
||
27
+ 2c0p²
2 +72)
14
Next we take full expectation of both sides and obtain
27
E Ella'
x= 112 =
7/4
E x
=01
+ 200p
+72)
2
14
The latter implies
B x (1
Y/4
| -x"1'
x=1²=
4y0
+
4yc0p²
4cop² 112
2
MG
1
where P bounded by Lemma D.I with a =.
Corollary 1. Let assumptions of Theorem hold. Then E
E1xxT
x
x=
S holds after
4
1
3R²
T
4
+
In
3cdG
iterations of SGDA-RA with
min
and b 2
72chn² N²c
2t
2ut
easa
Proof. If -f 24o² the result of Theorem can be simplified as
B a||"" x (1
7/44 T
| x11
270²
48yy000
24c50²
uG +
2
P
42
Applying Lemma C.3 to the last bound get the result of the corollary.
D.2 Proofs for SEG-RA
Algorithm 2 SEG-RA
Input: RAGG, Y
1: for 1= 1,... do
2:
for worker i [n] in parallel 9g. +- g: (z Ex)
3:
4:
send g3. if G. else send if Byzantine
5:
(x'') RAGG (g) .......))))))
6:
3² x² (x' (x').
// update params using robust aggregate
7:
for worker i [n] in parallel
8:
9 9: (*' n:)
9:
send g if i E G. else send if Byzantine
Iep (x') RAGG (g ............ "h...
x² y (x*).
|/ update params using robust aggregate
To analyze the convergence of SEG introduce the following notation
ge (x*) Ie* (2x
Σ (x .eh)
G
EEG
25

---

(e*(2x) = RAGG (1 .t......ee 9a(",,, , -%)),,
x² = x² - ~
9,, (T²) g (x*)
1
Σ
(a m))
G iEG
where E i E G and n². j G are iid. samples satisfying Assumption 1, ie., due to the
independence we have
Corollary 2. Suppose that the operator F is given in the form (1) and Assumption holds. Then
Eeg [llgen (x**) F(ax")11
S
(27)
G
o²
E [1g (x*) )1
S G
(28)
D.2.1
Auxilary results
Lemma D.2. Let Assumptions 2, 3, 4 and Corollary hold. If
1
m1 S 2L
(29)
for SEG-RA (Algorithm 2), then Tep (x*) = In (x*
-Gāet (x**) satisfies the following inequal-
ity
87200²
B @ (x*) (z=))]2 x0%) I 2Pr +
G + 477c5p²
(30)
where Px = YE m ( (ot - and p² = 240² + 12 by Lemma D.I with a = 1.
Proof.
Using the auxiliary iterate 2x+1 = x² 71 (x**), we get
h+ x=
| x² x01 - 2n (a* - x Irpt (ā*)) + 7 g (1*)]?
(31)
| x² 112 - 27 (x -- (xt) xx xx" (āx))
(32)
27 get (xt) I.,," (τ²)) + 7ी I
g.," (²²)
(33)
Taking the expectation Rg n² [] = E [- m=*] conditioned on x from the above identity, using tower property Ee = 1E 1,,, [:]] and y-quasi strong monotonicity of Fz),, we derive
[| xx1 [1]
1|at x011² + x Be [| ( [1]
2n Eee
[(a* - m (xx*) )- - x I (a*)
- 2TT m² (xx)) 9, (5t1)]
| - xx x='11
2n Eegr [/a0 Tiges (a²*) xx", F (ar 7 (ar+))
- 2g [(get (2*)) ).pp) (3+))] + Br n²
||0,, (5 |1²
(144).14) $
1| x²11 - |10e (xx*) )
+ + B
[|[ee- (a²*) - I, (=*)
26

---

To upper bound the last term we use simple inequality (16), and apply L-Lipschitzness of F(z):
,n || - x11
(16)
I
| x
x11
1|2
ri A
| (zz*) (1²)
+ Be
IE* (ax*) Ien (a**) >11 }1{
Be
F((*)) F (12)
+ 44 Eey
IEn ggn (zx*) - =(x="))
+ Bg
||18,pe (x²) F (x*) [|]
(27)).22)).28)) 1
| x x=1
- 71 (1 -44229) Eeeh || (ze*) |1
+ 44 B
[ - get (z+)))
47902
4ni0²
+ G
+
G
(16, Lemma 13.1
| - x²1
- -11(11472L)
Ee" [| (x* 11(
S
8720²
+ 177c8p2
G
(29)
|0 - x a²1
81202
47pcop²
G
Finally, the above inequality together with (31):
8710²
||a - x²11" 2Pr + マラ In (z )|²
xx
I|a
x²1l +
+ 44/08p2
where Pr = m/ (ggpt (#t (
x²)]. Rearranging the terms, we obtain (30).
Lemma D.3. Consider SEG-RA (Algorithm 2). Let Assumptions 2, 3, 4 and Corollary hold. If
71 2/ + 2L
(34)
then 9 (x.² = Ixp (x** 7g (x**)) satisfies the following inequality
Pk 2 11/1 ar xx 111
12 Fgg Reg gee (ax ||²]
87102
9yfe8p²
(35)
2
or simply
4n
-rx 5
1471
42200p
2
where Pr. 11 mr (g ( x²)] and p² 240 12 by Lemma D.I with 1.
27

---

Proof. Since Be .² = E[[ xx) and Rept (x*) = 9n (x* - -nge+ (x*))= we have
-P
-e nn (ept (t") x x011|
-m Bgt [(E Iept (x [2=))] 11 (x= -xx))==)))
- [(r,t (Øt) ge* (x"))) []]
(14)
Bgt [(F(** - nget (x )), x -10g xx)
2
2 et
Egtnn m²
I1,t (o+)
(1@ex(2=))1
2
2
Egtin
9 (ā*)) ge" (ze (x*)
2
(16)).16)
11 - xx - -ggeu (ze )12]
[liēe- (ze ) [1]
1m ge .m
Eee
2
412
Rey
[gcx(1*)) Fec (2r*) >13
2
412
Ben
|F(x0*) F -(**)) [1*)
2
4v
Ees
gea (x=)) F(x")) )1²
2
||0 (I²) - F (a*)) [|]]
Ees .1
2
(l)) D.1.Cor.
PM
x12
71 (1
2n14 12 [|[ğe (z+))
2
2
0n
4120²
+
2G
2G
(34)
P771
11
2 Ee
||0e= (ar
(aa)
4720²
2
2
G
So one have
PR
14/1
x0 x=11
7
Egg
Egg
||
47200
+
97fc8p²
2
G
2
or simply
4n/02
P
<
1171
x x² 11
+47e05p²
2
that concludes the proof.
D.2.2 Quasi-Strongly Monotone Case
Combining Lemmas D.2 and D.3, we get the following result.
Theorem (Theorem 2 duplicate). Let Assumptions 1, 2, 3 and 4 hold. Then after T. iterations
SEG-RA (Algorithm 2) with (6, cRAGG,, m S 22422 and 9 1//71 S 1/4 outputs xT such that
E 2T
T 1| 201 + 2 (1-M8M))
8no2
43G + 8cop2
11
2
3p
422
where 0² =40² + 1 by Lemma D.I with 1.
28

---

Proof of Theorem? 2. Since x++1 = x² - -2 (z*). we have
||x x²1|
1| 12 (3t) x²1 11?
|| ||=2* x² 211 22 ' (3²)) x - x²) + + (0*) 1|
||at xx 212 22 1r2( In (x*)) x x²) + 27 9,y² (x' ||
+ 21² gyp (0") - DTp (a') 11
+ 2y Inn (x") 9, (x*)) x x²)
s (1 + 2) x0 x=1 2y,2 (x
- x²) + 2 Iyy (a*)]²
1 2) || (0*) Ir (x*) ||
+72 2
Taking the expectation, conditioned on x²
1e 1-:+t1===111 =212 < (1 1)||2* 20 -- ge np D,, (xt), ,0 x²)
2 snp |1 (**)) 1| + 2200 pp
2 + 1
x
using the definition of Ps. Bet [( (5**,, x* * x²)] we continue our derivation:
Eea .n |1000t111 - x =01
(36)
= (1 + 2)1|z0* - -x01|" 2211|2-2,77 -23Pp + B Inpt )1²
+3305p² 2+ 1
x)
(30 I
(1 + 211| - x01| 21 -23P + 238
8yR0² 2Pp +
G + +290000²
+2206p² (2+ 1
058C1/2
167302
(1 + A)||0* x²11 111--200 -2Pp (
232)+ +
+ 8y2cbpp
G
+2300p² (2+ x
(35)
(1+ + 2)1lz0* - =x¹1?
+23(1 - 233 (- (-121
47702
11 - 101
42/cbpp
+
+
2
G
16720² G 8ygc8pp
2 1
+72c8p²
<
(1 (1+1- 1-31- 228)
471
1100
x1
2
1202
167202
8/2e6p² + 2500p² 112060((2+1)
+ G
+ 706pp +
(37)
G
05351/4 5
(1 (1+ X - M72)
2 1|00*
x11
+ 0
(72 + 1613)
7
+cdp²
912 1013
+
A
(1- 1172)
11a0 x= x=1²t
0²
(1i + 1677)
G
472
+odp²
1 + 10n2
+
p
29

---

Next, we take the full expectation from the both sides
|| x= x=11"] -
3 ||
o² (1 167 1i 1072 + x" -'11"+
4/2
p
(38)
Unrolling the recurrence, together with the bound on P given by Lemma D.1 we derive the result of the theorem:
E || 10 - 21
442 K
x - x²1
40 40 1672)
4c5pp + 1012
402
2
142
142
Corollary 3. Let assumptions of Theorem hold. Then E
x
x²12 S holds after
2
2
1
3R²
T
In
B
3,cdG
E
iterations of SEG-RA with 71 min
and b
288c5o 3pde
2p+2L
2p+
Proof. Next, we plug 72 = B31 S 51/4 into the result Theorem and obtain
E n ++
x= x²11²] S
1 |=" x=1
87i0² PBG
871c0p2
16c0p²
(39)
3p
Bp2
If Ç p² -2402 the last receurence can be unrolled as
E nr - a²1?² (1- 11 T |r x=1
8r102
8 24-4
16 24c50²
+
+
P3G
3p
3p2
Applying Lemma C.3 the last bound we get the result of the corollary.
D.3 Proofs for M-SGDA-RA
Algorithm 3 M-SGDA-RA
Input: RAGG, a [0,
1: for ( -, 0, do
2: for worker i [n] in parallel 9 < (x.",, E.) and m (1 a)m; + agi 4: send m. i E G, else send if Byzantine
3:
|/ worker momentum
5: m' = RAAG (m) .... m and x'+1 mm'-mmm
// update params using robust
aggregate
D.3.1 Quasi-Strongly Monotone Case
Theorem (Theorem 3 duplicate). Let Assumptions 1, 2, 4, and 6 hold. Then after iterations M-SGDA-RA (Algorithm 3) with (6, -AGG outputs /" such that
2 20
4c8p² u²a² +
8y0882
+ 6y02
E
|
x
17]
<
phawr
ua²
Ha?G
where ह" 1
Wr ΣT w. $' = I-(1-ajTT E/ -)-a(1a---a -s)
Wi (1- 170
-1-1
and WT === and p² 24g 12 by Lemma D.I.
30

---

Proof of Theorem 3. Since m² mm² ''''' + m and m = =ag' + (1 - a m'm -1 one has
x ++ - -x01" = xe - x²" -7m² 11 = || - =011² - 22 x - x²) + 7 -
= |x' - x² x²11 - 27(mm² m x' - x²) + + |
- -- (m x² - xx").
Next, unrolling the following recursion
(m', x' x²)
agg' x' x²> + (1 (m
(m x² x²)
al'', x' x²) + (1 a) (m" x x²) + (1 am x x
alg', x') + (1 a) (m x² x²) + (1 a)> (772" ,
one obtains
(m', -x'''"x'
Σ a)) ( x ~x)) (1 a)7 Σ (1 - a)- (0m::-mmm-11 ,m²)
5=1
Applying the latter and (11) for (m² n x² x²) with X = paa
we obtain
2
2a7
(1 (1-a) aa-
x x")
1=0
$ (1 + 17a0)
||a2" x>'1
1x -xx1'' xx1|²² +
27
m m²
ua
2
+7 m
+ +2 2-2(1 - a)
Σ
(1 a)*² 1-1 ( .m²)
j=1
(1+
|0e (14))0)
- =011² - ||00 x x²1|2
+
2%
m
m 1
2
+ m'
2
+ 2
(1 a)--1 |
j=1
+
a)²
Σ (1 a/- |m 1
/=1
(2)
(1
u7a
xe - x ||
1 ++ x01'
+
2%
m
m
2
b
+47 2
(1 a)² | m |
j=1
+3y² 2 Σ (1 a) |11 11
j=1
Since m7' a E5=o(1 (1 - a''- and hence M
s a E5 - ||""1|100| one has
200
- -a)=aa) x x²)
)=0
(1 + 1000)
|x"" x²1
x 1+1
201
27
m
ml
2
aa
+42² Σ (1 a)) ->
m² m
j=1
+
a) 1-j Σ
(1 a)
1=0
31

---

Next by taking an expectation Eg of both sides of the above inequality and rearranging terms obtain
2a7
(1 -1- (a))
x x²)
i=0
11
pga)
x²' x²1 E
EE||=/t1 x - =x111
2
2
m
m
2 +47 Σ (1 "B==
m E g'1l
m
140k
j=1
j
+ 2a a
-
a) 1-j
Σ
(1 a)
j=1
1=0
Next we use Lemma C.1 to bound R |
2 and Assumption (QSM) to obtain the following bound
(1
a x x²)
S
(1 a)* x² xx x=1 S -aulla= - x²11?
1=
j=0
Gathering the above results we have
α7
a)
( xx")
==
(1
ama
x²' x²1 -El fe|lz/11 - x²11
2
2y
Eg
m'
m²
2 + 442 2 Σ (1 "Exl m m
pa
+372 al > (1-a)²
(1 (F((((()),, -x")
j=1
2=0
t
Σ
(1-a)
Σ (1 - -3--
G
j=1
1=0
Next we take full expectation of both sides and obtain
(1-a))--B8 BB x x²)
0
(1 pna EE| Bllxe' x01 -12 -Bll00 x²1
+
27 F2 m'm
m'|
+ 472 2
(1 a)' " -RR/mmm
m m² 1
==1
j
a3 al Σ
a)-
(1 a) 1 '(F((z) x² x²))
j=1
1=
37
aG
Introducing the following notation
Z = Σ (1 -
-
x -x")
0=
32

---

and using that E8 m
m'
=1 v cōpp²
where p is given by (26) we have
a (1
1/a
BB x²
x
| E
x
x²
r2+12+ +
2ycop²
2
ua
cōp2
3720²
+ 37 al
(1 a3)-322' 2' +
aG
Next we sum the above inequality I "times with weights Wi = (1
430
-t-1
where WT
2
T
T
T
W4
Zt
(1-
110
E
x²
x²"
1
Wy
x
++1
x² x²1
2
1=0
+3y2 al
(1 a)'
Wi
1=0
j=0
2rc0p²
+ epp
3720²
+WT
ua
aG
Since (1
1100 2
Wt = Wi-1
T
a7
W. Z'
S ||00 - 1011 -x"1' +
+3y at
Σ
Wi
Σ (11-a)-iz2
t=0
t=0
1=0
(2)00p²
4700dp²
37-0²²
+Wr
1100
aG
If S 1 we have
We = (1
17/0)
-t+-
[+ + w; S
170
b-
S
1 +
a) 1
W/.
2
2
2
So have
ar
W Z
<
||000 x x11
1 2) [-j (1 aaa)a=3w32 23
+3y² ol
ao
ΣV Σ
==0
12c0pp
4 e5p 37202
+Wr
pa
a
aG
S
||000
x
2 + +372 2 al
t-j wy Z
==0
2g00pp
4 22205p2
37202
+Wr
Na
aG
< 11 xx" ?
+
Σ
Wi Z'
Σ
2
1=0
1=0
2xc0pp
c726pp2
3720² 02
+Wr
1a
a
aG
T Σ w.
$ $11000
x= 121 + 2
Z'
1=
2yc5p2
3-202
+Wr
40
a
aG
33

---

y S
a 12
then the following is true
T
22c0pp
27p
3//02
a7
Wy Z' S 1 -x"1'' x²11²
WT
+
(40)
pa
a
aG
Using the notations for Ze and (QSM) we have
Z a)* (F x x²) 2 1 Σ
)z-
E x²1l
1=0
1=0
and consequently by Jensen's 's inequality
Σ a(1 a0)
z P Σ -3' x 2 p
E
x
(1 a 2
a
With the definition "²
(1-aj1 E (1 - -
then the above implies that
Z 2 nl / x=1
that together with (40) gives
anp
T
x=
S 1200
x²1 x²112+10 + Wr
22y08p²
+
cr2ppp
+
37202)
(41)
aG
Applying the Jensen inequality again with x.'
2tmo wa we derive the final result
Wr
| x= x01
x x²1
4cop² 12a2
8yy68p²
6r0²
E
+
ua² +
(42)
Py
ua²Gi
together with the bound on given by Lemma D.1.
Corollary 4. Let assumptions of Theorem hold. Then E ..
x=1 S holds after
24 ua
3R²
T
4 +
+
In
Sc0G
iterations of M-SGDA-RA with 7 min
126 2 mहre
Proof. { 0, p² 24 the result of Theorem can be simplified as
E ||="
11] <
2|
101
4. 24c502
8.
24yc502
6
+
pya
2
2
1 (1 - p7a T+1
Since py
can apply Lemma C.3 and get the result of the corollary.
34

---

E Methods with random check of computations
We replace (amax c) -GG with the simple mean, but introduce additional verification that have to be passed to accept the mean. The advantage of such aggregation that it coincides with "good" mean there are no peers violating the protocol But if there is at least one peer violating the protocol iteration we can bound the variance similar to Lemma D.I.
Algorithm 4 CheckComputations
Input: t. Gt Ut, Ct. Banned, 2
1: C++1 = {cf
++1 ..... 1. C++1 C. (Gr U Bx) C and U441 {ut ..... 1 U4+1 C
(Gr U Bc) \ C.. where 2m workers cf 10 2+1 ++1
u1 ....e u are choisen uniformly at
random without replacement.
2: for i I,... m in parallel c++1 checks computations u, ut during the next iteration receives query to recalculate g(x ())))
3:
4:
d sends the recalculated g E (,,1)
5: for i 1= m
6: if g(' Exy) # g'z then
7: Banned, = Banned, U [ut, c).
8: end if
Output: C(+1, Gi U., \ Banned,
Lemma E.1. Let Assumption 2 is satisfied with Ç Then the error between the ideal average g' and the average with the recomputation rule g' can be bounded as
Ee g g" 1|
p²11,,
12 where p² qa² with 2C + 12 + n-28-m and C (1).
Proof of Lemma E.I. Denote the set & in the following way G = fi \ C. 1l gill s Co).
Σー
Th ge
if number of workers 3 otherwise.
g
recompute,
So that we have
1 - 7
g
g
iEg
iEG
<
2
g
g
+ 2
g
g'
G
9
iEC
iec
$ 20202 +2
Σ
9
g'
If 8 < 1/4 then acceptance of g' implies that [
n/a and [ 16/01/3.
Σ g'
of
g'1l2
9 g'12
G
G REC, (C
GEG
iEG
Σ
lg g' 1
G.
C2
35

---

Bringing the above results together gives that
E g" r''l
< 20"022
+
6
Σ sEG
Ellgi - g'll
C
Since checks of computations are only possible in homogeneous case (C 0) then Elg - Ful and
o²
20
E lgi -9' ø'12² 2B .f F212
+
2R
g 1| S
20² +
(43)
Since |9c \ Cdl > n 2B m
Eellg' - 3²11² 200 + 120² +
12o²
< 20
+ 12o2 +
12o²
C1 C2
2B 11b
E.1
Proots for SGDA-CC
Algorithm 5 SGDA-CC
Input:
Co = Ø
2: for t = 1,... do
3:
for worker i
(Gr U B.) \ C, in parallel
send g = g1(2", Ei), i e G \ Ca,
4:
i B, \ C,,"
5:
g' = w.
1
Eien, L: Wh = (Gi UB) \ C2
6:
7:
if i E W
g
g
& Co 2 11///2 then
8:
411 x²' 7g'
9:
else
10:
recompute
11:
end
C.+1, G.+1 U B CheckComputations(CC,, Gt B,)
E.1.1
Star Co-coercieve Case
Next we provide convergence guarantees for SGDA-CC (Algorithm 5) under Assumption Theorem 9, Let Assumptions and 6 hold. Next, assume that
2B R)
m m²R² R2
7 min
(44)
28
6
72p² B2n²
where 1² = q0² with q 20 12 +
n-2B and C (1) by Lemma E.I and R. 2 1| - x=1
12
Then after K iterations of SGDA-CC (Algorithm 5) outputs x" such that
K-1 Σ
K-1 B((F((*)) k=
x²))= 2PR
E
F(*
s
7
k=
Proof. Since 19, \ Col 2 - 2B - m one can derive using the results of Lemmas C.1 and E.1 that
E. [[|a x:" 1|2 #
= [||a** xx" 7 2 x
= 1 - xx 2012 2y [xx k - x;, ,²" | x + 7 [|l0*1] a=
xx" F(x*)) l x²12 2x( x², F(*)(()))) + +26 (x*
2-20²
2yE [fat - xx
g - - | x + 2-²2²= 2 11 +
n 2B
36

---

where 1 is an indicator function of the event that at least 1 Byzantine peer violates the protocol at iteration k.
To estimate the inner product in the right-hand side we apply Cauchy-Schwarz inequality and then Lemma E.1
2y1B (xx
x=, x² -0-"" 9²) xx s 27|1 x= |E | g"ll xx*
s 2y|1 x= |1
E [ll g-112 |x*]
- 2ypl|=* - x L'k
Since 7 28
1. the above results imlies
100 - x, F(x*))
s 1|00 x=12- - E || R+ - x011 x=*)
|
27²0²
2 ((at - -x', g" -g") ax.h + 2222221, +
2B m
||0 x²112- EE || x x²11 x**]
27202
+2?2 p² 1s + 11 2B
x 21pllx>* 2-pp|==*=x*111 L
Taking the full expectation from the both sides of the above inequality and summing up the results for k = 0, ,.....,y K 1 we derive
K
(F
* x x1}]
K
k=0
27202
[ || -x"1|" x011 E /1 ==1)
n1
2BB
m
K-1
K-1
2710
+
[||a xx 11
+
E(UR]
K
K
k=0
k=0
|
xx' ||
Bi] [K|| - x01
272202
<
K
11.
2B
K 1
27²p'² K-1
27p
+
E [1|a* - x:" 11113]](111)
+
E(1a].
K
K
k=0
K-1
Since F satisfies Assumption
6,
Σ
(F(F(=)) ) xt - -x0" 2 0. Using this and new notation
k=0
Rs = 1æ - x=1|,
11, 1 > 0, Ro
2 ||x
x²1 we get
R3
E[R
27202
0
2B m
K
27 p² K
27p
+ K
E R E[1s]
[[LA]]
(45)
K
k=0
k=0
implying (after changing the indices) that
27²0²k
E R
R
+ 2%p
Σ
[ +
E
2
E(1
(46)
n
2B m
I=0
holds for all k: 2 0. In the remaining part of the proof we derive by induction that
27
A-1
R +
2YP
E E
2 p
B[1a] S 2R
(47)
n 2B m
1=0
1=0
37

---

for all k = O....,K. K. For k 0 this inequality trivially holds. Next, assume that it holds for all
k= -,-,,T K 1. Let us show that holds for k = T as well. From (46) and (47)
we have that [R[R)]] < 2R for all k 1........ T 1. Therefore,
27²0²T
T-1
T-1
EIRE <
RB
+ 27p
Σ
E [RR
27'p2²
11 2B m
1=0
2T - 2B m
T-1
T-1
$ RØ
+ 22222ypp
E + 27
E[1.]
a Byzantine peer deviates from the protocol at iteration k it will be detected with some probability Pk: during the next iteration. One lower bound this probability
Ge
1
m(1 - 6x
Pk
7kg
7kk
7k
Therefore, each individual Byzantine worker can violate the protocol no more than l/2 times on average implying that
2-20OT 2B m
272yyRooBB
272
E[RN]
<
Rg +
+
m
m
Taking
(n 2B m)
2 R2
7 min
28
6
72p B²n²
we ensure that
2- 2T
2v 2yppaBBBB
p2pp2nB
R2
R2
R2
+
R
n 2B- m
m
m
3
3
3
and, as result, we get
E[R I 2R 2R
(48)
Therefore, (47) holds for all k 0, K. Together with (45) implies
K
[F(((=*), xx - x111 2R
Σ
7
K=
The last inequality together with Assumption 6 implies
K-1
2
Σ
B|F(">>||
K
Corollary 5. Let assumptions of Theorem 9 hold. Then
((x*))))) S e holds after
k=0
(22R2
o²
R
K =
ng
me
iterations of SGDA-CC.
Proof.
2ER²
2
662K
72p² B2n?
K E F(* 5
28 +
7K
K
(n 2B - m)
m²
4E R2
24
17pBnRR
K
(n 2B 1BBm)K m)
mK
38

---

Let us chose K such that each of the last three terms less or equal 6/s, then
6 R2
2160 R2
51pBneR
K max
(n - 2B mm)²
me
where p² qo with 0 20 + 12 + that
12
and C (1) by Lemma E.1. The latter implies
n 28
E Fall)|| Ss.
Using the definition of p from Lemma E.I and B S 2. m << n the bound for K can be easily derived.
E.1.2 Quasi-Strongly Monotone Case
Theorem (Theorem 4 duplicate). Let Assumptions 1, 4 and 6 hold. Then after T iterations SGDA-CC (Algorithm 5) with 7 S 28 outputs x² such that
E x T+1 - x x11 - (1 - 2 /
1
x
pln 2B m) +
4y0²
2p2nB (?
+22)
where 8² = qo² with q 2C + + n-26-m and C (1)) by Lemma F.
12
Proof of Theorem 4. The proof similar to the proof of Theorem
K
|?
K
b
xx x011²]
= μE
x
x²
S
μE
x x²1
K
k=0
K
K
(0SM)
E
w
x
E
[(F(x*)) - xx"1]
k=
Since g'
Fp =F' Fr one has
|| xx 11= = =11=" x²11
27/(g' -g'- x' - xx") ( x² -x*) 1
Applying (11) for (g', x² x²)) with x 7 and (12) for 1|@'|12 = 1| g g'll we derive
x - x²1 I 1 + 7H4
x - -2r'-"'''' x' x²)
2
2"
g' g' 1| +
2 g7|l2
+
Next by taking an expectation Eg of both sides of the above inequality and rearranging terms obtain
Be|l=* 10
1 + 2 xz x'1 (2)(F(x") x² - xx")
7
27 Ee g' g 1| 2e /"' -112 + 27 EE 1
The difference with the proof of Theorem is that we suppose that the number of peer violating the protocol at iteration t is known to any "good" peer. So the result of Lemma E.1 writes follows
Eglg' g'll sp,,
where 1, is indicator function of the event that at least Byzantine peer violates the protocol at iteration t.
Together with Lemma C.I we can proceed as follows m
Sella't1 101 <
(1+ 7/4
||00
27) x' xx") -'x")
2020²
+ +2 (1 (2
+ G
39

---

Since $ 28
and Assumption (QSM) holds we derive
2720²
Eg
x=1 s
x
x0+
Next we take full expectation of both sides and obtain
2-202
B a ++1
x011
= (1
7/44
Bl|xs a2' -x"1|=="""
E
x²11²
+ 22p 11
+2² EL.
2B
The latter implies
7/4 T+1
470²
= - x011²
5 -x=12
| =x²12 +
2
1a(n - 2B - -m)
+ 2p" ( + +1²
Σ E1,
T
(1- 7H
T-t
2
If Byzantine peer deviates from the protocol at iteration I, it will be detected with some probability during the next iteration. One can lower bound this probability as
G.
m 5,)
m
Pt m
74g
Therefore, each individual Byzantine worker can violate the protocol no more than 1/2 times on average implying that
DC
nB
1
m
t=
that implies
7/11
T-1
nB
E
1,
E
1
(49)
m
The latter together with the above bound on E
x T+
x=
implies the result of the theorem.
B x T+1 x. x=112= $ (1
7/4 2
T+1
1::00 - x=1 -000xx111
4-
2p²nB +x2))
(2
p(n - 2B - m)
m
1
Corollary 6. Let assumptions of Theorem hold. Then E
~T" E|(0T"
x² < holds after
(
0²
+ go²Bn qo²
T= 3 1 1º(n - mle
2mme 1Rnve
iterations of SGDA-CC (Alg. 5) with
2n
max
2,
min
min-2B 2
mu 123 K Sqn Bor
Smo"t 1 4q An B3 27 27-m)
= min
2
(K +
Proof.
Using the definition of (p² qo² = ( from Lemma E.1 and if B < 7. << the
result of Theorem 4 can be simplified as
E r T+1
<
7/4
T+1
x
11
4
2g
(1 /
+
2
p(n 2B m)
m
Applying Lemma C.4 to the last bound get the result of the corollary.
40

---

E.1.3
Monotone Case
Theorem 10. Suppose the assumptions of Theorem and Assumption 5 hold. Next, assume that
(n 2B R)
m2 R²
7 min
(50)
2
6
72p² B²n² B2p2B²n22
where 0² = qo² with q 20 12
n-2B m and C (1) by Lemma E.I and R z ||000
x=I1
Then after K iterations of SGDA-CC (Algorithm 5)
3R²
(appR((a))))))))))))))(()))))( (I*) 1 7K*
(51)
1 K-1
where Cap CapBa(z*) (T*)= max (F(u), wEBn(e*)
-w), x
Σ
k and R 2 ||20 x=')
K
h=0
Proof. Combining (16), (14) one can derive
27(F((*),, u)
|| u 2u|2² - | k+1 u1
(g ge xx n 2 (g
Fb: ,x 4)
+ +2 1²1 2 + 27² g
Assumption 5 implies that
(F(u), -) S (F(x*)) x - u.)
(52)
and consequently by Jensen inequality
K-1
27y 2y - uu) s 1 u u11² 27
g g x un)
k=
K
K-1
[g
pk
xx
1)) + 27 2
(1g0* 1 +
11)²11²)
Then maximization in gives
2 K Kapp Br(x*) (x*)
||200
u112 + 222 Σ ||g* 8²1 + |
max "EBn(#")
K
+2 max We (x(e)
9 g x 4
+2 max
gh x² 4
uEBa((
Taking the full expectation from the both sides of the previous inequality gives
KE
Gap
GaPBn(e")
(zK)
max WE Bn(x*)
|20
K-
+2y
max Bxx
x
41
K-1
+2yE
max B )
Fb
g"
21
k=
+2
k
g²1
+ lg 12)
k=U
41

---

Firstly obtain the bound for the terms that do not depend on u using Assumption 1, Lemma E. and Theorem
K
30 | |1011")
2
EE
| g"
k=
KK-1
TK-1
2T
Σ K==
11 k 3²1|3
2
Σ 1==0
g"
KK-1
2 2 Ko²
K-1
27 PT
1
+2y
E ph: xx
x²))
G2 Cel
k=0
k=0
27 BBpp
Ko²
+ Rl
G. Ctl
(48)
Since B [[||=* t
uI]
s
=[[[=*
x² |] + ||0= 2ell s
<E[[<=*
x=
max
||
ul
I 3R
one can derive that
K-1
2yE
max de Bx(x))
Σ 0=
g
g xx* -u)
K-1 ( gth x -u) ui)
K-1
2y
max nEBR(æ*)
+
g
g x
xx¹)
k=
27
E
max [uEBn(.*)
g x 4)
2y
x
xz))
K-1
K 1
<
27
maax (x(
9
|110" w|l
+ 2+E
g
x
K=U
R=U
K-1
K-1
2
E
R gg
g01l| + 2y
Σ
pl
x01|
k=0
R=0
KK -
K-1
K-1
6n BnByRa Rp
<
RTE
Σ 0=
1
+
4ypRE
Σ
1
S
RyRpE
1
m
k=
Following Beznosikov et al. [2023] one can derive he bound for the next term:
K
K
E
F
g",
x²
E
[E[F
g" x 1,1, 0,
A
k=
K
E
(Fk
gt 20
[E g ") =0,
k=
42

---

we have
K-
2y
max
(F* g¹, x 2)
uE (x
K Σ k=0
K-1
2
(F*
g"h x²
+ 2
max
(F
9 4
"E
k=U
K-1
2-
(1k
g"
(E
k=
K Σ
2y
(Fk
2000
K-1
+2yLE
max uEBn((²)
(Fth g _
K-1
2yKE
max mE MEBR(z*)
(F
gd), x0
21
K
k=0
9*)) 12
(
2yKE
max uEBR(x")
22
Fk
1
uel2
27
B
Σ F
g*))
max "EBn(=*)
| - -2112.
We notice that E[FK Lemma C.2 are satisfied. Therefore, applying Lemma C.2, we get
g F g" p
g² for all l: 2 i.c. conditions of
K (F g" x un
2y
max ME (x(2*)
<
E|| F -
k=0
k=0
max
||x ull²
(53)
" Bu(a))
2 Ko
max
|| - -ull
u//
(54)
G. Cel
WE mEBa(z
Assembling the above results together gives
2- K E Gap
(
(x=1
2r²nBp²
3o²
GnByRR
< 2 max uc Bn(**)
|/000 u
+ 4 +
G. \ C.l.
m
nr2BBp
3r²
< 2
max
1|200 ul|
We "EBg(2'
m
n1 2B m7
BnByRp
(44)
+4
m <
6R
Corollary 7. Let assumptions of Theorem hold. Then Gap B (x (x*)
S holds after
(RR
a R2
on R
K 4
+
ng2
ms
iterations of SGDA-CC.
43

---

Proof.
3R²
3R
2
72p² B m R
I
Gap Gap Ba(2))
(xx
26 +
+
7K
K
(n 2B R)
6
R2
26pBnR
K
(n 2B m)k
mK
Let us chose K such that each the last three terms less or equal f/3, then
18
9-54a²
78pBnR
K = max
(n 2B m)s?
me
guarantees that
13
Gap ) (xx S
Using the definition of p from Lemma E. and B - 4. m << n the bound for K can be easily derived.
E.2
Proofs for R-SGDA-CC
E.2.1
Quasi-Strongly Monotone Case
Algorithm 6 R-SGDA-CC
Input: x² starting point, r number of restarts, {イ+)== stepsizes for SGDA-CC (Alg. 5), ( [Kerr number of iterations for SGDA-CC (Alg. 5)
[= xr
2: for t = 1.2....,7 do
3: Run SGDA-CC (Alg. 5) for K, iterations with stepsize Tt, starting point a'-1 K.
4: Define क6 as S
1 Kz
Σ k.e, where æh, ,..,,,.., Ke.t are the iterates produced
by SGDA-CC (Alg. 5).
5: end for
Output:
Theorem (Theorem 5 duplicate). Let Assumptions 4 and 6 hold. Then, after logz Rt²
1
restarts R-SGDA-CC (Algorithm 6) with Tt. mmnn
nn-BB (n-2B-m)) H1
vn R?
and
T2ga B"
K,
max
81 (n 2B
p
2
R
34n0B /
where R
|| x
outputs T such that
E| E xx" 1| S c. Moreover, the total number of executed iterations of SGDA-CC is
Σ K. - @ 1=1
( log
o²
+ nBa
(55)
(n 2B m)
m my/ue)
With q 202 12 n-2B-an m and C (1) by Lemma E.I.
Proof of Theorem 5. x.
Ek= x.
1 K
uE
μE
c x²)
μE
x
K
Σ E
x
x
|||
(USM)
K
[[
x x -x)]
A=0
44

---

Theorem implies that SGDA-CC with
(n
2B -m)
m R2
min
28"
6 K
72p² B2n
guarantees
1 k
10113]
-
2 Rlg
7k
after K iterations.
After the first restart we have
R 2
|| x² x²11²)
E
S
147
K
Next, assume that we have Bllla' x= x=11 S
Ro
for some S 1. Then, Theorem implies that
2 x011
EE || xr" ||²
Taking the full expectation from the both sides of previous inequality we get
E
11]
x-
28[ xx x=1131
2n
R2 2
myeK,
K2
Therefore, by mathematical induction we have that for all 1. l....,r
R2
E
2
Then, after log2 nr
restarts of SGDA-CC we have E ||
x²1 S E. The total
number of iterations executed by SGDA-CC is
22
n BBp2
Σ max
K2 = 1
11' (n - 2B
m) Rg
muRo
1
222
n nBp22
1
r
+
+
(n
2B
m1
Rd
muRu
RRg
a²
RR
BBp
R
1
log
+
+
(n 2B
m) R
E
mulo
L
RR
σ²
nBp
1
log
+
+
(n 2B
m)
m mw/ue
Corollary 8. Let assumptions of hold. Then EE [| - x ||
S E holds after
Σ K2 9 (
RR²
+ σ²
n²o
log
+
(56)
11 E
npe
m m
iterations of SGDA-CC.
Proof. Using the definition of p from Lemma E.1 and B < 4. m << the bound for
K₁ can
be easily derived.
45

---

E.3 Proofs for SEG-CC
Algorithm 7 SEG-CC
Input: 7
1: for = I,... do
2:
for worker i [n] in parallel
3: 9g. + gi (x', E:)
4:
send gg. if E Gt. else send * if Byzantine
5:
(x')) = "
1 Eiew, gé. 1/ = (G+ U., !e
if { E 1 (0:(2²)) - ge - Co } 2 / then
6:
7:
n² t x. 99 (x²")
8:
else
9:
recompute end if
11:
C+4.-C44 U U - CheckComputaiions((.. Ge B,) for worker i [n] in parallel
12:
13:
Iin + g:(2", mi)
14:
send g if E G. else send if Byzantine
15:
Iop (*') = Wr. Liew, Dy.
W. = (G- UB+4g)
\ CC++
16:
if LiEE 10: 9 (x')
9 Co } 2 |0l/2 then
92 (3')
18:
else
recompute
20:
end
if
C4+1. G141 U BB+1 CheckComputations((., Ge+b UB444)
E.3.1 Auxilary results
Similarly to Section E.1 we state the following. If a Byzantine peer deviates from the protocol at iteration k, it will be detected with some probability Pk during the next iteration. One can lower bound this probability as
G+
m(1
5k)
Ph
7kg
71k
71k
Therefore, each individual Byzantine worker can violate the protocol no more than 1/p times on average implying that
EELL+>E
nB
(57)
Lemma E.2. Let Assumption 3 holds. Let Algorithm run with 7 1/22 and -0/71 S $122. Then its iterations satisfy
272 (g (3*),, = u2)
S 11 ull² -1| -ll - (o, (क*) - I (क** ) .xt u))
+2 I (ath)
-,, (1* + 4 g (5**) F(xt)) !|2
+ +4 F(xz Fe (x 11 / (x*) -e )1² 1
Proof. Since t +1++11100 t '29 2 (. we have
| uul2
|| '2 (xt²) u1l
||00* - -ull² 27 g., (,²),
u)) + + 9r (3²)
46

---

Rearranging the terms gives that
(g (I"), xt u) = || | 2el - -1|a 21 1
27 (rrt (#*) - Irtt (xx ) x² -2) u) + +3,, (1=)
Next use (14)
2g (5*), xx u)
g( (ā'), ) 1 x - =²a) + 2g (00):=(x))) (3*), xt - u)
27 (g, ( (a*)) + 2g (at)) a* - u)
(14)
-m1 0 (5*) - (at))")) (a*))) -10e=<(+))) (==))12-100 - -11g,,
11²
2(g (,*), - -u)
and obtain the following
27y2 Dept (x*), xh - un
1|0* - ull² - |la - u²|² - 22 - Ir, (at)), x* - u)
+73 "l@ (²²)
+7172 (1 (5x") - ge= (2=²)]² 1/= (xxx )|² - | (ar*) /1²)
1
1|00* - ull || / - uel2 - -2y2(0n (σ²)) - -Tnpt (āth), ) x*t ne)
+27/ Mg (5th) - D (Tth )1 + 27/ | (a-))² ||?
271rt (19 (x+*) (x*))))) (x+²) )|² @0e. (ax )1² gnp" (3tt) )1²)
3 = =n//m S 1/2
272 ">2(g," (3h), x u) S ||a** ual² - -1|= || - uel2 - -2 (Qn) (ā²) - Iep (20 ) xx 2))
+ +272 T.p. (ath) I,, (12
72 [1 (***) ge (ze (aa))|² [g (1o*) 11)
Combining the latter with the result of the following chain
I.,e (0*) -e= (x*) |
(16)
( - F(ā*)]] 11² + F((*) - 112
+4 +4|| - De (x+)) 112 + 4 gea (x* - Den (12
1
,1 (5²) - F( /1²
+ 4L - - -x-1(² x01
F(** - De (a+) )|(
+ 4 g 41 ggn((t)) (1²
(3t) F(**))l )1² + +4(1 -ee (c+t) 11?
+4| (a*) ge (e (zr5)]
40 L @g (zz
we obtain if 712 1 1/27.
( (āt), x* - u)
< 1| ull - _a|2-11p -1|0 ual2 - -272 (g, (ā+)) D, (āt*) xt u)
+ +272l My (Ith g,, (12 + 42 g. (x+)) F(**) ||²
+4117e (eeel(((a*)))))) - ge (x*)))
2| ||
+ + (x*)) -e (a+) 2 (58))
47

---

E.3.2
Lipschitz Case
Theorem 11. Let Assumptions 1, 5 hold. And let
(n 2B R2
m.
"1
min
(59)
2L
16o2
8p3 Bn
m² Re
(n 2B mm
72
min
4L
64p² n²n
64a²
(60)
where p² go²² with 9 20 + 12 +
and C (1)) by Lemma E. Then iterations of
n n- m
SEG-CC (Algorithm 7) satisfy for
E| E[R S 2R.
(61)
and
K
E [F ). x²) R²
where Rg 1| - x²1l and R 2> ||0 - x
Proof. Substituting u = x into the result Lemma E.2 and taking expectation over r7 one obtains
/ (g 222lEnp
(it*), xx')|
(16)
5 || 1 2²1 Eyp |1 x 11]]]] - 2y [( (xx) Irpt (x ) xx x²)1
t |1 (6*) F( 11 + 71724 F F(x*)
- gea )1²
+n (x*) ge- (2+))) + Ex || (ā*) - Irt (#*) [1"]
To estimate the inner product in the right-hand side we apply Cauchy-Sehware inequality:
- F (gnt (x*) - In (#*),, ) x²)}
2y ||| x'll
@) I (3*)|]
Lemma F.1
272p|1 x0 22||
Then Assumption 6 implies
272 (F(TF) x -ax x²) 5 10 -x0 x=11 -=-12-- Eyy k+2 x=1 12]
47
+ +2%20|1 - x x1111x 2 +
19x C+1
+4 (oapaaF((***) ge ge- (z+1)1 4nrrellge (2 gea (z (x²
48

---

Taking expectation over ę one obtains that
By nr ((F(E*). ). - -x>)]
1 1 x
- .pt [11eAt1 -x01' 0011 + 2 10 x x0111x 27200 222021 1x
402
+ +ABer [11((at)) ge- (2())11 + 4B |||ge (a#*) get (2t))))
+
19 1 Cxxl
S
|xt x² 1| - Beet,
|||0At1- -x-11" 2=11"] + //20|| a
x 101111 272 121
202
402
+
+ 4pp2 x-
19k
Ckl
Ck++3 \ /C++2)
x²'
1|
Bet.nn |||0/0t1 - x 11²
+ 272p|1 be" x x0'11x 2'
402
402
+7172
+
+ 4p² k-
2B
m1
71
2B
Finally taking the full expectation gives that
272 x
I E B|1a** x x011²]
18
||
-x*|1"] 2 212
x0||La| + 2722'² B[1a]
80²
+772
+ 44p²1 k-
n2 2B m
Summing up the results for k ===0, 1....... K- - 1 we derive
272
E
(F
I² xx)]]
K
K
8717202
[E || - x x11 - -E [[1aa k+1 - x11 [||0=
K
71 2B m
k=
2/22/
K-1
27
K-1
471 K-1
+
K
E 1 x [1] +
K
B[1g] +
K
k
k=0
k=0
R=0
|
x= 112
E
20 11
8717202
<
K
nt
2B m
K
2720² K-1
K-1
2x2
E 1|| x [[
B[1a] +
421
Σ E
K
K
K
Assumption 5 implies that S (F(x*)) k xx)
< (F (F(**), . x²))
Using this and the
notation R₂= = =|
x=
||.
k > 0, Ro 2 ||000 xx" ||
we get
n2
E[R
871 7202
0
<
K
n1 2B
K
2r2p² K
K
42 K
E
|||a - 12]
+
E +
622)
K
K
k
0=
k=0
implying (after changing the indices) that
8117202
E
E
<
R2 +
2720
E
E[RR)EELL
(63)
2B
1
k-1
k-1
+2
E[1 +
E 1
(64)
1=0
1=0
49

---

holds for all & 2 0. In the remaining part of the proof we derive by induction that
820 k
E[R]] Σ
R +
+ +22
E[R
(65)
n 11-24 2B m
1=0
k-1
+2 2
E[Li] + 72
B
S 2
(66)
1=0
for all = ,,..., K. For 1: = this incquality trivially holds. Next, assume that it holds for all k = 0, 1,..,.... - < K - 1. Let us show that it holds for k = T as well. From (64) and (66)
we have that [ I 2R for all = 1......,, 1. Therefore,
871 1217 k
B E[
Rg +
+ 2722
/ERR + 2720²
B[Li
n1 2B m
k-1 1 74
1
1=0
8/11 8/1"200* k
k 2720² 0²
Rg +
po
[[11]
Σ B[4i]
n1 2B m
k-1 1
+47
1=0
The latter together with the expected number of at least one peer violations (57) implies
2 2
nB
nB
nB
E[R
RØ +
n 2B m +
Ro
m +
27
+
422
m
m
Taking
2B m) Rg
RRR
h1 min
21.
1602K K
8p2 Br
m² R
1
(n 2B - -m) R3
m R3
min
V
64p² n
4L"
64o2K
32p² Bn
1
m² R
(n 2B m)
min
4L
64p B2n 2
64g²K K
we satisfy conditions of Lemma E.2 and ensure that
2 +
nB
2-220² nB
nB
R2
R2
R2
R2
4
<
+
R2
2B m
m
m
4
4
4
and, as result, we get
E[R2] S 2R 2R.
(67)
Therefore, (66) holds for all k = 0,1, K. Together with (62) it implies
K
R
B ((((Tt)) - -x')] <
72
50

---

E.3.3
Quasi-Strongly Monotone Case
Lemma E.3. Let Assumptions 3, 4 and Corollary 2 hold. If
1
71 S 2L
(68)
then T,p:(3* Inph (ar* (10ee((a²)) satisfies the following inequality
87900
AiB || (3 (3*))12 x 1 2P +
+ +4nip²1
(69)
G
where Pk: Bgg Ee m ( (ot*) a a²)] and 0² =go² with q 20 + 12 +
12
and
C= -1) by Lemma E.I.
Proof. Using the auxiliary iterate x*+1
"1 (x**, get
1 x: 2=²
1|a:* xx" 271 (xx* x² Dt (at))) + 7 Typ (1+)
(70)
1|at x²
271 ( (x 7タE (xx xx , (a*))
(71)
2 (get (x*) ). (āx)) + I (
(72)
Taking the expectation Eg m² [] = E [=1=] conditioned x from the above identity, using tower property Be [.] = Egg [E,, [.]] and uı-qaasi strong monotonicity of F F(x), we derive
Ee . [| - x²11²]
x x² 271 1(2" -11 (x**) x I.," (x
2 Ben.n
(Gee (a*)), (x+))\ + 7 "e ||g (
1100* x12
2 Bgg [(x* - -19e (a+*) xx"; F (zt T (ax* 1)}]
2 Ext [( (2*) I. (z=))] + Bt m²
| (a**
(14) $
x x=1 Bi . [|00e (ax )|
+ "R m [| (2**)
Iz (at*) "1* ||
51

---

To upper bound the last term we use simple inequality (16), and apply L-Lipschitzness of F(z):
gt .²
||
- x²11²]
(16)
1| x
x
11 1e [I (a*)
Bgy
| (x*)) 3 (== |1
Be
|| - F (x**) 11²
B
| (z**) F(
+4yfBee Be .² ||0 (5**) F (x**) [1=]
(22)).27).228)
| x= 11²
79 (1 4T.2>;) Eeex || (az*) ]
S
+47
-e (3+"))
47/0²
4770²
+ G
G
Lem,. D.1 I
|| b x²1
112-
4,2 Eea² ||0e (z*h))
87802
-42
--
G
(68)
|x x012
87i0²
1-
G
Finally, we use the above inequality together with (70):
87f0²
|| -x'1= -2P% + 7E |1gmp (x*) [1² xxk
s |1 x
+
+411p21
G
where Pr = = BB mr Kg )x - x²)] Rearranging the terms, we obtain (69).
Lemma E.4. Let Assumptions 3, 4 and Corollary 2 hold. If
n 2p 21
(73)
then 97pz(0") In (a** (000)=(a+")) satisfies the following inequality
Pk
4m x x2112+
22 Ee
[ggg
8yf02
92pp21
(74)
2
2
or simply
4ni0²
-Py
pm71
x²112=
+ + 1 -
<
x
2
G
where Ps. = 7E (0,," (hh)
) t x²)}.
where p² = q02 with 9 = 2C + 12 +
12
and
n-28-1
C' = (1) by Lemma E.I.
52

---

Proof. Since Bgt .² = E[[ x=1 and Eept (x*) = 9n (x* - -nget (x*)), we have
Pk
->n Begn mn 1g (#r ) x+ xx11]
Be [(Dn)) 1 (3 x -10E (2*)) - x²"]
- [(r (3t ). (xg"(xx")) (zx))]
(14)
Me [1F(x* - m9g (xx)) 1),
-1g (2x x0)]
2 Eet.."
Iyp (a*) - 2
[l [1*))((**)) (a*
2
2
2
Ee mn
[ (x* He (z=)))
2
(QSMO.(16)
|| -x" nge (2x*))
7p Ee
ge (a (x=)
ee mp
2
41
|1ge - get (x*)))
Ee
2
Eee
|| F (**1)]
2
41
Eee
[1gex F(xx")] |1]
2
4n
+
Be
|1
(x*) - F (1
2
(Lip), Cor.
I
1411
||
1*
x²11
2 (1 - 2n1 P
2
[| (x**) 1
2
2
47/02
47j0²
+
17p0"
2g
2g
11l1
1
x²1
2
Ee
[1ee(()*))
2
2
42102
1
G
So one have
4n/02
9ypp²1
1
Pk
<
1171
x
x=
11
7 Ee
ge (xx)) [13
+
2
G
2
simply
4ni02
Ps
<
1071
x
x²1
+
+
+4/pp²1s
2
G
that concludes the proof.
Combining Lemmas F.3 and E.4, we get the following result.
Theorem (Theorem duplicate). Let Assumptions and hold. Then after T iterations SEG-CC (Algorithm 7) with S 24422. and = =72/71 < 1/4 outputs x T such that
E x
x²11
1
1B311
1000
x1112 + 20²
471 3p2(n
2B m)
where q 20 12
n-28 m q= (1) since C = (().
12
53

---

Proof of Theorem 6. Since x++1 = x² - ~220n" (z*). we have
||aht| 2=
a| 729rp (x x=
|| x² || -21/ In, (x*)) x - -x)) + + 977 (x*) )|
||a x²1) $1 22 In (3*) xx x²) + 9,," (x*)) |
+ + g (a+*) 9n (xx*) ||² + 27 Sr (x*) In' (x** ax x²)
(1 + 2)ه|z0* - x01 || Oy (x*) x x²) 27 Iy (ā*) 11?
+72 2 2)) 11 (07t) In (x*) ||
Taking the expectation, conditioned on x²,
Ee || - =211
< (1 1)|l - -x'1² -28 Ee m G,, (0"), x x")
+2 2 Te .n |1 (***) 1| + 220 2 +
using the definition of Pr. Bet (gn) xz - x²)). we continue our derivation:
[|a44t] -=-1-=111 x=11
Egg* m²
=1+
+ ^) 2)1|z0* -x01=11"" 1x"1|== 228P% + Be nn JTnt )1
-23PP
=
1
+720² 2
2 T
1x
(09) 3
(1 + 11/|a2* x=112-2,8p + 2333
2 +
8770²
+ + k-
G
1
+020² 2 )
1
05351/2
167302
(1 + A)||a.* 201/² - -2 2282) -B
+
+ 87207² F
G
1
+720² 2 7
1x
(4)
(1+ 2)I|z* x²1?
(2 - 23)
(1192
119
|| - x2'1² + G
42/0²
+
+1
2
167202
+ 8'222
k + 720"
2 5
1)
1
11:
G
(1+ 1 - 23(1 - 299)
M/ |0 x2'1?
0/02
16
8 002p211-3 + +220 2+ (200(2+ 22 Ax
+ +rpp11 !
G
G
05331/1 I
1+
142
|| xx'1
2
02
k- + "000 2 1) 2 M
- (7i + 1672)
+ 7 1100211
kー + +8
1
(2+x²)
A=Hry/4
(1- (22) 1,ot x11?
x²
+ C
(n7 + +17/) + - + 8720 1 + 7302
k-
2+ 1r22
In
54

---

Next, taking the full expectation from the both sides and obtain
E || x= 111
s (1 (1-4))
4 ) 11
x01
0²
20/2
+ t (n (nf + 1673) + 02 + 812)E1,
+22 1/
Unrolling the recurrence, derive the rest of the result:
13 x K+1
x²'1² - (1 (1-14) 1472
K+1
1
2
x: x²112
+
40 ( 16
4
12 - 2B - m)
+p²(71 + 872))
Σ(
K
112
K-i
E
4
+2p²
12
2
+
272 1
Σ6
1
112
E1,
Since 7/2 S and that implies
Σ
T
1,
7/4
T-i
E
T
1,
nB
(75)
2
m
using the expected number of at least one peer violations (57) we derive
E x K+1
x0 x²1
s
102
K+1
x01
40 (v) + +1622)
1212 (n 2B m))
TB
272 nB
+p² (77 + +87))
2p
72 1 m
m
< (1 1472
K+1
40² (7ī + 1672)
x
4
12 n - 2B m)
nB
4p² nB
+p² (72 + 1072)
+
1
m
that together with p² - with q 2C + 12 result of the theorem.
12
and
C ((1) by Lemma E.1 give
Corollary 9. Let assumptions of Theorem hold. Then E
x
x²
2 S s holds after
-= T. 1
a²
2 Bn
qo² Bn
5² - 2B ml) B
8p2me
32,2mm/e
iterations of SEG-CC with
m(n 02 R²
32 n2 R²
4ln max 2, min
1
32mo' 4qo 3 Bin 2B -m)
32mBar
7 min
2L 2p
m3(K + +1)
Proof. Next, we plug 72 = By S n//4 into the result of Theorem 6 and obtain
E |||a =[|a0ht1- x0 0001"]] (1- (1-13m) 11000 x0 12112+ Bpln 2B -m)
80²n1
+2p² nB +
4p² By2 nB
m
(76)
Using the definition of (p² = =ao²= = ((o2)) from Lemma E. and if B < 2. m << the result of Theorem 6 can be simplified as
Bl|a" 10
(1
13311
||000
x=11 11
80
2 nB
71
+
4go By nB
By(n 2B m)
m
/
m
Applying Lemma C.4 to the last bound we get the result of the corollary.
55

---

E.3.4 Lipschitz Monotone Case
Theorem 12. Suppose the assumptions of Theorem 11 and Assumption 5 hold. Then after K iterations of SEG-CC (Algorithm 7)
3RF
IE CapBule (x+*)) - 272 K*
(77)
K-1 Σ
where Gap Bn(z=)(**))
max wEBR(ar)
(F(u), u)), 2zKk
K
ã* and R S ||xe0 x=11
k=
Proof. We start the proof with the result of Lemma E.2
272 gg (3"), -)
|| ull - || -ull 20|? - -272 (ā (3²) 9r (x"), xt 24)
+212 Irpt (āt)) I., (x,(1))) (0-))² + 4 Fnp (ō**) -F(#*) 11?
+ F(a")) gx || + 4 471 ge (xtt) -e (a )1²
that leads to the following inequality
22 ( (F(#"). x² --1 u)
$ || - ull - a1|2~110a* - uul + 2 (3x) - g,t (a*))
+2 ( F F(x*t) gtpt (3*)) ,t"h - u) 272 (3²) - Inn (*t x² -u)
74 (I (x0)(()))))))))))) F( ||² F(x=*) Tec (xx >> 1|² + (xx De 00=(">>)1 11).
Assumption 5 implies that
(F(u), u) S (F(**), x+ u)
(78)
and consequently by Jensen inequality 2/ K (F(u), T u)
$ 1000 u|| + +27/
Σ
Myy² (x*) -,,t (321)12
k=0
K-1
+2 Σ
(FF(T") 9np ). x - -u) - (gn - g (2*), x u))
k=
K-1
(3t =1 + ||F((t*) - Dea -e (z+t)) + Ie (2*) - ge- (x²)))
+44172
k=
K-1
where Hxa
Σ
x
K
km
0
Then maximization u gives
272 (a)
K-1
<
max (x
||000
-ull² + +27/ Σ
9rp² (ā*) F,,- (1*)
K-1
Ignt (x*) - F( )|( + || F(a*) get (2² + gl (20²) De- (x**) (1)
+4m 72
k=
K-1
+2% max vEBR(=")
(( I,," (5t) ui)
+2% max Wc (x(
Inp (i*)= -,,² (5²)) x u).
56

---

By Lemma E.1
B
K Σ
(xp - grp (x*h (2²)
272
R-1
Σ
B[
2 272
nn (60)
R
(79)
m 32
k=
k=0
and
12
K-
gg
ge (x*))]² s 4
K 1
E
1 k-
S
44
nB (39)600)
R²
5
k=
(80)
By Corollary 2
B
K-1
Σ 1=0
(1
(
)1 |F(x*t) - ge- (axt) (a2))(1)
8/172K
(59) R²
n 2B m
4
(81)
K
272 max "
Inp (i*) - Dept (a*) x -u) u)
K
212 max uEBr(x²)
Inp (x")
-gnn (2=)
x x²)
k=
+2 max =EBn(
Σ I,, (x*) Irpt (3² xx 21)
K
2
|1| (2*h) - It (i*))l
k=0
K-1
+2% max BEBR(z*
|x= u/ll
u|||[ (3²*) - (#*))
k=0
Lemma E.1
Taking the full expectation of both sides of the result of the previous chain we derive
K
nB (60) 3
E max
g (t -,," (5*), x* u) S 6y2pRoE14 S Ry
S R2.
4
k=
Now the last term
K-
272 max uE Ba(a")
Σ A=0
(F(**)
9 (a ( xx 21)
(82)
Following Beznosikov al. [2023] one can derive the bound for the next term:
K
E
F( Ir -0 (,
E
FF 9,,' (5*) 1*) 0,
E
Σ (F(**) T, (2t"),
(E(F(a") -r (-*)) x -.
57

---

we have
K --1
2
max (z
(F(x") 9n7" (I
x 4)
K
1
(F(**)
Trj² (x²)
k=
K-1
2
max ME BR(z*)
(F(*") - Inp (5²) - -u)
k=0
K-1 Σ (F(**) In (3t"), -u)
E
max ME (2*)
k=0
K-1
B
(F 91p" (2* ),
km0
K-1
+
max ME (z(2²)
Σ (F(T*) - In (T²) -2)
k=0
K-1
2B
max ué B (x=*
(F(**)) - I, (ot))) x 2
K
k=0
K
max KE
72
(F(**)
I,Pt (x**)
+ 2
|| u2l2
2
K
k=D
K
27
=
12
(F
+ Mc Bx(
max
||000 - -u11
We notice that (
Inp k
F (r
9r (#......, F (a*k-1)
91pti1(22 1 (x*-1)] 0 for
all 2 1, i.e. conditions of Lemma C.2 are satisfied. Therefore, applying Lemma C.2, we get
K-1
272
max We BR(x')
(F((t) In (x x** 22)
(83)
K-1
12 k=0
[* 9 (1²)
(84)
max
||20 ul
(85)
(x*x(2*)
12 Ko²
<
max
||00" -u12
(86)
2B
Wc BR(=*)
(69)
9
R²
(87)
Assembling the above results together gives
R2
R2
R2
9
2/ K TEGaPaaaaaaa Bu(z') (x*)
+
R²
R2
< 3R²
(88)
32
4
8
Corollary 10. Let assumptions of Theorem 12 hold. Then E GaPBnie' (I*)
S holds after
K 0
LR2
o²
R2
on
me
iterations of SEG-CC.
58

---

Proof.
3R²
3R²
64 K
64p²
E Gap Bx(2))
4L +
27zK
2K
(n 2B - -m)
m²
6R²
14
12pBnR
K
V
(n 12-22 2B -mm mk
Let us chose K such that each the last three terms less or equal f/3, then
K = max 18LR
144 900
36pBnR
(n (n-2B m))²
where p² = qo² with 0 202 12 a-2B-m and C (1) by Lemma E.1. The latter implies that
I GaPBn(z')
(x*)
S S.
Using the definition of p from Lemma E.1 and B S 4. m << n the bound for K can be easily derived.
E,4
Proofs for R-SEG-CC
E.4.1
Quasi Strongly Monotone Case
Algorithm 8 R-SEG-CC
Input: x starting point, number of restarts, {n))== stepsizes for SEG-CC (Alg. 7),
( Kg 1r number of iterations for SEG-CC (Alg. 7),
ft 1: "n
2: for wott-1 11:1=12, -,2,...,, do
3:
Run SEG-CC (Alg. 7) for K, iterations with stepsize Yr starting point a'-1,
4: Define a _t R. Σ at where 0tt, x.. x Ke,t are the iterates produced by
SEG-CC.
5: end for
Output: 27
Theorem (Theorem 7 duplicate). Let Assumptions 1, 3, 4 hold. Then, after r
log, R²
restarts R-SEG-CC (Algotithm 8) with n, = min
2I:
16a 22
m)
Sqa 22 Br.
m2
72,
min
4L
64ge
22 22 B
R2 m
B-m) and K. = Ke
max
81. 16na /22""
mppt
(G-B
256
R
where R >
|x
xt outputs "" such that E| 30" x
112
<
Moreover, the total number of
executed iterations of SEG-CC is
FRg log
a²
+ nBo m mv/e/
Σ K. =
(89)
E
(n - 2B m)
K-1 Σ
Proof of Theorem 7. K.K
K
k=0
nE
||
11]
μE
)
+ x
11
1
Σ
B
x
(USM)
S
1
(((F(**),
2h -²1)]
K
K
A=0
k=0
59

---

Theorem 11 implies that SEG-CC with
nn
2B mm
mR²
71
min
2L
16
V
8p2 Bn
1
m²R²
(n 2B m m2 12
min
4L
64p2BBn22
B2n
64o²
guarantees
RS
1B
k
x²11²]
S
7/2 K
after K iterations.
After the first restart we have
R
RS
E
||
$12²)
HLY22 K
since (1)2, K1 2.
Next, assume that we have E[[| xx
x0113]
Rá for some t S 1. Then, Theorem 11 implies that
| -=-1'"
E
x 201
1172, Ke
Taking the full expectation from the both sides of previous inequality we get
Blll x= 112]
R R
E
|||
x=
122. K₁
2' K2
21+1
Therefore, by mathematical induction we have that for all
1, I....,r
RS S 2
[[|
Then, after loga of iterations executed by SEG-CC is
R
restarts of SEG-CC we have E [|
10] S
The total number
L
22
BB22 2
})
K2
1
max
11 (n ( 112BB- - m) m)p RR
muRo
222r
nBp2
=
1
(n
2B mmm RB +
mpRo
L
RR
d²
RR
n nBp
RR
1
log
+
E
(n (n- 2B - m) 2 R
myRo
nBp
1
log
(n 2B m)lu
/us
that together with p² = qa² with 2C + 12 + n
12
and C = (1) given by Lemma
2B2B
implies the result of the theorem.
Corollary 11. Let assumptions of 7 hold. Then [|āT x
holds after
(
L
RR²
+ σ² +
n²o
K₁ = 0
log
(90)
E
nue
m mype
iterations of SEG-CC.
Proof. Using the definition of p from Lemma E.1 and if B < q. << the bound for be easily derived.
K, can
60

---

Extra Experiments and Experimental details
F.1
Quadratic games
Firstly, let us clarify notations made in (7):
A A
A2,1
(b,s
A,
b,
- A2,
A3,i)
b2,5
with symmetric matrices A₁ s.t. μI & Aja < AI E Rddd and 6, e Rd.
Data generation. For each we sample real random matrix B, with elements sampled from normal distribution. Then we compute the eigendecomposition and obtain the following B; U,D,U, with diagonal D.. Next, we scale D; and obtain D; with elements lying in [n, E.. Finally we compose Aja as Aja U,U, This process ensures that eigenvalues of A all lie between and L, and thus F(x)) is strongly monotone and cocoercive. Vectors by IRd are sampled from normal distribution with variance 10/2.
Experimental setup. For all the experiments we choose l 100, p= 0.1, 1 1000 and 50.
For the experiments presented in the Appendix we simulate 20 nodes on single machine and B For methods with checks of computations the only one peer attacks per iteration.
We used RFA with buckets bucketing as an aggregator since showed the best performance. For approximating the median we used Weiszfeld's 's method with 10 iterations and parameter 0.1 Pillutla et al. [2022].
RDEG [Adibi al., 2022] provably works only if n > 100 manually selected parameter 0.5 using a grid-search and picking the best performing value.
We present experiments with different attack (bit flipping (BF), random noise (RN), inner product manipulation (IPM) Xie et al. [2019] and "a little enough" (ALIE) Baruch et al. [2019]) and different batchsizes (bs) 1, 10 and 100. If an attack has parameter it is specified in the brackets on each plot.
No checks. Firstly we provide a detailed comparison between methods that do not check com- putation with fixed learning rate value ? 3.3e 5. Code for quadratic games is available https://g/
www..thc..ooooa.eeeeeeoo www.mazya/sgaaaa....aaaoa ra?.
"Code is based on htw.ettubb..oo/uuubbb//e/ge
61

---

10"1
RDBG
10.4
RDES
10.4
RDEG SEGIA
Ditanre vdtutton
SEGRA
SEGIAA
Ditwaze to sotee soteeton
MSDDANA
MACDANA
M5ODARA
SCDARR
10"2
SCDARA
SGDARA
10-1
10-3
20
10"
0.2
1.2
gradienss
gradients
Number gradients
(0++00), b5-1
[1e. 00), bs-10
(To+ 00),
10
RDDS
10.1
RDDS
10:
RDEG
Distence the solution
SEGRA
SEGRA
Destnce the solldion
SEGRA
MSGIDANA
M510XA
M5DIAAAA
10-2
10-2
10
0.0
0.2
0.4
06
0.8
1.0
0.0
0.2
0.4
0.6
1.0
1.2
0.0
0.4
0.6
0.8
1.0
1.2
Number gradlents
Number of gradients
Number of gradients
ALIE (1e+01), bsm1
ALIE (1e+01), bs=10
ALIE (1e+01), bs=100
10-1
RDE6
RDES
10-4
RDES
Didherce selonkn
SEGRA
SEGIA
Disterce to the colirion
SEGRA
M5GDARA
MSG0ARA
10-2
10:
10-1
0.0
0.2
0.4
0.8
0.8
1.0
1:2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.01
3.0
1.2
Number gradients
Number of gradients
Number of gradierts
ALIE (1e+02), b
ALIE (1e++02) bs=10
ALIE (1e+02), bs=100
10-4
RDES
RDEG
Datence to the volatton
Datance to the vnbiioon
10-2
10-2
10
10-1
10a2
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.6
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.0
3.0
1.2
Kumber gradients
165
Number of gradients
106
Number of gradierts
107
Figure 3: Distance to the solution ALIE attack with various of parameter values and batchsizes.
BF, b5=1
bs=10
BF, bs=100
10-1
HDEG SEGRA MSGDARA
HDED
10-1
ROEG SEGRA
Dinerca solurknn
SEGRA
Disteree to cotrrin
MSSDARA
20-2
20-2
10-2
1p-2
10-4
0.0
02
0.4
0.5
0.5
2.0
0.0
0.2
0.4
1.0
1.2
0.0
0.4
0.5
0.8
1.0
1.2
Number gradients
Number of gradients
Number of gradientss
Figure 4: Distance to solution attack with various batchsizes.
62

---

10"1
RDBG
10.4
RDES SEGIAA
10.4
RDEG
Ditanee edtiiton
SEGIA
Detwore to the sotee sateeton
SEGIAA
MSDDANA SCDAAR
MA
M50DARA
SCDARA
SGDARA
10"2
10->
20-1
10-1
1.2
gradienss
gradients
gradients
IPM (1 DO), bS-1
(1e+ bo-
(1e bs=100
10
RD3S
10.1 3.
RDDS
10:
RDEG
Dssentee the solutoo
SEGRA
SEGRA
Destance to the sot Lttn
SEGRA
MSGIDA
MO
MSLDAAAA
10-2
10-2
10:4
10-4
0.0
0.2
0.4
066
0.8
1.0
0.0
0.2
0.4
1.0
1.2
0.4
0.6
0.8
1.0
1.2
Number gradlents
Number of gradients
Number of gradients
IPM 01)+ bs:
IPM (1e+01), b5=10
IPM (1e+01), bs=100
10r1
RDE6
RDE3
10-4
RDES
Ditherce selonkn
SEGRA
SEGRA
Disherce to the velirtoo
SEGRA
M5GDARA
MS304RA
10-1
10
10"2
10-3
10-1
0.0
0.2
0.4
0.5
0.8
3.0
1:2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
1.0
1.2
Number gradients
Number of gradients
Number of gradierts
IPM [1ee 02), bs
IPM (1e+02), bp
IPM (1e+02), 1s=100
RDES
RDEG
Datence to the vnlatton
Datance to the subitoon
20-2
0.0
0.2
0.4
0.5
0.8
3.0
0.0
0.2
0.4
0.6
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
Kumber of gradients
165
Jumber of gradients
106
Number of gradients
107
Figure 5: Distance to the solution under IPM attack with various parameter values and batchsizes.
63

---

(1e+01),
(1e+01). bs=100
10"1
RDBG
10.4
RDES
10"4
RDEG SEGIA
Ditanee votutton
SEGRA
SEGIIA
Detwaze the saleeton
MSSDANA
MACDANA
M50DARA
SCDAARA
10
SADARA
20:2
SCDA
200
SEGRA
10
10-1
10:1
0.0
0.2
0.4
0.0
1.2
gradinns
Number gradients
Number gradients
(1e+077), bS-1
(Te+ 02), bo
[36 02)). bc-100
10
RD3S
10: 0.
RD1S
RDEG
Disence the solution
SEGRA
SEGRA
Destence to the Lffn
SEGRA
MSDIDANA
M5
M5DIDAAA
20-2
20-2
10
20-3
10.4
0.0
0.2
0.4
06
0.8
1.0
0.0
0.2
0.4
0.6
1.0
1.2
0.0
0.4
0.6
0.8
1.0
1.2
Number gradlents
Number of gradients
Number of gradients
RN (1e+03)) bs#1
RN (1e+03), bs=
(1e+03), bs=100
10a1
RDE6
10a4
RDE3
10-4
RDEG
Cleerre velnnkn
SEGIA
SEGIA
Ditheree to the colition
SEGRA
M5GDARA
MSG0ARA
10-2-
10
10-2
10-1
10-1
0.0
0.2
0.4
0.5
0.8
1.0
1:2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
1.0
1.2
Number gradients
Number of gradients
Number of gradierts
RN (1c+044) bs
RN (1c+04), bp=
RN (1e+04), bo-
10-4
RDES
RDEG
Datance the sobitton
Dalance to the snkitoo
10-2
20-
SCDARA
10"2
10-)
10-1
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.6
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
Kumber of gradients
105
Number of gradients
106
Number of gradierts
107
Figure Distance to the solution under RN attack with various parameter values and batchsizes.
Checks of Computations. Next, using the same setup, we compare M-SGDA-RA, which showed best performance the above experiments, with methods that check computations. With checks of computation the best strategy for attackers is that at each iteration only one peer attacks, since maximizes the expected number of rounds with the presence of actively malicious peers. So the comparison in this paragraph is performed in this setup.
64

---

(le-01),
10"1
1014
SEGCC
10-4
SESCC
10"2
1012
SCIAACC
Diteare the solee sotriio
SCIMACC MIDDARA SGDA
MODDARA 5CDA
20-1
10"1
10:1
10-3
10-1
SQUACC MSGDARA
20
10
SCDA
2.0
1.2
gradinnss
gradienss
Number gradients
(1.+00), 1
01). bo-10
(To+ 00),
10
10:
Destnce the wot.eootddn Mhon
10-1
10
20-1
Diannre the
10
10.
10"
SEGOC
SEGOC
10
10T1
MSQDARA
SGDACC
EGDA
10--
SODA
SGDACC
MSGDARA
20-
S0DA
MBGLANA
SGDACC
0.0
0.2
0.4
06
0.5
3.0
0.0
0.2
0.4
0.6
1.0
1.2
0.4
0.6
0.8
1.0
1.2
Number gradients
Number Of gradients
Number of gradients
ALIE (1e+01), 1sm1
ALIE (le+01), bs=10
ALIE (1e+01), bs=100
10a1
10-
Dishence the colerio
10
10
10-1
10-1
20
SEGOC
SEGOC
20
SEGCE SGDACC MEGDARA
10-4
SCDACE
MEGDARA
10-7
SCIACE
MEGDARA
SCDA
SCDA
0.0
0.2
0.4
O5
D.E
3.0
1.2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
Number gradintts
Number of gradirts
Number of gradierts
ALIE (1e+02), 1
ALIE (1e+02), bs=10
ALIE (1c+ bs=100
10-4
SEGCC
10-2
Datance tn the unkitoon
10-1
10*2
10-3
Dalence
10-1
to
20-4
SESCC SGOACE
MSGDARA
10
0.0
0.2
0.4
0E
0.8
3.0
1.2
0.0
0.2
0.4
0.6
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
Kumber gradients
165
Number of gradients
106
Number of gradients
107
Figure 7: Distance to the solution under ALIE attack with various parameter values and batchsizes.
BF, b
bs=10
BF, bs=100
10-1
SEGCE
10-1
SEGEEL
10-1
SEGCE
10
MSGDARA
SCEAADC
1002
SCDAACC MSEDARA
Dietenre to the eotrrim
20-3
SCEACC
10-3
2014
10-1
10-4
10-4
10-5
10
20-9
10-4
10-7
0.0
0.2
0.4
0.5
0.5
1.0
0.0
0.2
0.4
0.5
0.3
1.0
1.2
0.0
0.4
0.5
0.8
1.0
1.2
Number of gradients
165
Number of gradients
Number of gradientss
167
Figure 8: Distance to the solution under BF attack with various batchsizes.
65

---

10"1
1011
SEGCC
10-4
SESCC
SCIDACC
Ditenze the sotre sotreton
SCIEACC
MODDARA 5CDA
22--
MIDDARA
SGIDA
10-1
10:1
20-3
SQUACC
10-1
10
SCDA
MSGDARA
20-
2.0
1.2
gradinns
gradients
gradients
IPM (1 DO), BS-1
(1e+ 00), bs-10
(1e bs-100
10
10:
SEGCE
SEGEE
SEDAOCC
Dastence to the sot Jinn
SEDACC
10"3
MO
20--
MSSADAAA
10-1
10.3
10
SEGCE
10
SGDACC
10
MSQDARA
EGDA
10-7
0.0
0.2
0.4
06
0.5
1.0
0.0
0.2
0.4
0.6
1.0
1.2
0.4
0.6
0.8
3.0
1.2
Number gradeenss
Number of gradients
Number of gradients
IPM (1e+01), 1s=1
IPM (1e+01), b5
IPM (1e+01), bs=100
10a1
SEGCE
10-4
SEGIE
SCDADDC
Ditherce the colemin
SCBACC
10
10
MSCDARA
10-3
MSGDARA
10-4
20
SEGCE SGDACC MEGDARA
10-7
0.0
0.2
0.4
O5
D.E
3.0
1.2
0.0
0.2
0.44
0.5
0.8
3.0
1.2
0.0
0.2
0.48
0.5
0.8
3.0
1.2
Number gradients
Number of gradients
Number of gradierts
IPM 02), b
IPM (1e+02), bp
IPM (1e+ 02)), bs=1000 1.00
10-4
SEGCC
10-2
Dalance tn the unbitoo
10-1
10*2
10-3
Dalence
10-1
to
20-4
SESCC SGOACE
MSGDARA
10
0.0
0.2
0.4
0.
0.8
3.0
1.2
0.0
0.2
0.4
0.6
0.8
3.0
1.2
0.0
0.2
0.48
0.5
0.8
3.0
1.2
Kumber gradients
165
Number of gradients
106
Number of gradients
107
Figure 9: Distance to the solution under IPM attack with various parameter values and batchsizes.
66

---

(1e+01), bsm1
19.4
SEGCC
19"1
SEGCC
1prl
Ditange the sole
10th
MEGDARA SCDA
SERAACE
Distance to the SOlUEION
SCABACE
MSSDDRA
Distanna to salutin
20-1
SCEIA
10"h
10ah
10
SQUALC MEGDARA
19"9
1brf
SCDA
1.2
0.8
0.4
grudients
gradients
le6
gradennss
(1e+077),
(1e+07) 02), bo-10
[N bc-100
10
10:
SEGEE
10'2
10-2
MOLIDA
SEDACC
Destence to the atld
Disantt the
10
10-1
20-1
SEGEE
SEGOC
20-3
SGDACE
10-1
SGDACC
10
MSGDARA
SGDA
10-4
10-7
S0DA
MBGEANA
0.0
0.2
0.4
06
0.8
1.0
0.0
0.2
0.4
0.6
1.0
1.2
0.4
0.6
0.8
3.0
1.2
Number gradlents
Number of gradients
Number of gradients
RN (1c+03), 1om1
RN (1e+03), bs=
RN (1e+03), 1s=0
10-4
SEOCE
10-1
SCDADD
Diherre to colerton
10
MSCDARA
10-1
10-1
10-2
10-1
10-4
SEGCC ScoAct
SEGOC
SCIAACE
MSGDARA
MEGDARA
SCDA
10-1
SCDA
0.0
0.2
0.4
0.5
0.8
3.0
1.2
0.0
0.2
0.44
0.55
0.80
3.0
1.2
0.0
0.2
0.4
0.5
0.0
3.0
1.2
Number gradients
145
Numbbrr of gradients
Number of gradierts
RN (1c+04), bs
RN (1c+04), b0=
RN (1c+04), bo 100
SESCC
10a
SBOCC
10-1
SCDAOC
Dalance tn the unbiion
20
10-2
10+2
SEDA
SGDA
Dalence the
20"3
10
10
10-4
20
Lo-3
10-4
10-
0.0
0.2
0.4
0.5
0.8
7.0
0.0
0.2
0.4
0.6
0.8
3.0
1.2
0.0
0.2
0.4
0.5
0.8
3.0
1.2
Kumber gradients
105
Number of gradients
l06
Number of gradients
107
Figure 10: Distance to the solution under RN attack with various parameter values and batchsizes.
Learning rates. We conducted extra experiments to show the dependence on different learning rate values le 5, 2c
5c
6.
Laid
Figure 11: Distance to the solution under various attacks, batchsizes (bs) and learning rates (Ir).
67

---

F.2 Generative Adversarial Networks
One of the most well-known frameworks which the objective function a variational inequality is generative adversarial networks (GAN) Goodfellow et al. [2014]. In the simplest case of this setting, we have generator G R + Rd and discriminator D R R. where denotes the dimension of the latent space. The objective function can be written as
min max (log(D())) + E log(11 D(G(=))). G D
(91)
Here, it is understood that D and G are modeled as neural nets and can be optimized in the distributed setting with gradient descent ascent algorithms. However, due the complexity of the GANs frame- work, tricks and adjustments are being employed to ensure good results, such as the Wasserstein GAN formulation [Gulrajani et al., 2017] with Lipschitz constraint on D and the spectral normalization [Miyato et al., 2018] trick to ensure the Lipschitzness of D. The discriminator can thus benefit in practice from multiple gradient ascent steps per gradient descent step on the generator. In addition, Adam [Kingma and Ba, 2014] is often used for GANs as they can be very slow to converge and not perform as well with vanilla SGD.
Therefore, in our implementation of GANs in the distributed setting, we employ all of these techniques and show improvements when we add checks of gradient computations the server. As for the gradients in our implementation, we can think of the accumulated Adam steps within the clients as "generalized gradients" and aggregate them in the server with checks of computations (by rewinding model and optimizer state). We tried aggregation after each descent or ascent step, after full descent- ascent step, and after multiple descent-ascent steps. For the first case, we found that GANs converge much more slowly. For the third case, the performance is better but checks of computations take more time. Thus, we choose to report the performance for the second case: aggregations full descent-ascent step. Though, we note that experiments for the other cases suggest similar improvements.
The dataset we chose for this experiment is CIFAR-10 [Krizhevsky et al., 2009] because it is more realistic than MNIST yet is still tractable to simulate in the distributed setting. We let 10, B = 2, and choose learning rate of 0.001, 31 = 0.5, and 32 0.9 with batch size of 64. We run the algorithms for 4600 epochs. We could not average across runs as the simulation very compute intensive and the benefits are obvious. We compare SGDA-RA (RFA with bucket size 2) and SGDA-CC under the following byzantine attacks: i) no attack (NA), ii) label flipping (LF), iil) inner product manipulation (IPM) [Xie et al., 2019], and iv) a little is enough (ALIE) [Baruch et al., 2019]. The architecture of the GAN follows Miyato et al. [2018].
We show the results in Figure 12. The improvements are most significant for the ALIE attack. Even when no attacks are present, checks of computations only slightly affects convergence speed. This experiment should further justify our proposed algorithm and its real-world benefits even for setting as complex as distributed GANs. Code for GANs available https: : // //gi//gtttt github. com/ com/zeligism.
vi-robust-aa
68

---

FID of CIFAR-10, attack NA
FID of CIFAR-10, attack LF
SGDA-CC SGDA-RA
SGDA-CC
SGDA-RA
40
35
35
30
30
FID of CIFAR-10, IPM
CIFAR-10,
SGDA-CC SGDA-RA
SGDA-CC
SGDA-RA
50
45
40
30
30
1000
2000
3000
4000
1000
2000
3000
4000
Figure 12: Comparison of FID to CIFAR- 10 per epoch between SGDA-CC and SGDA-RA. The FID is calculated on 50,000 samples. (lower = better).
69


Reviews:
[{"review_id": "hzBFs1Q1wf", "reviewer": "Reviewer_zd6L", "summary": "In this paper, the authors provide robust variants of some popular optimization algorithms in the presence of Byzantine workers. They also use client momentum and random checks of computations to enhance the performance further. They provide theoretical guarantees of converges and empirically test their methods against Robust Distributed Extragradient (RDEG) by [Adibi et al., 2022].", "questions": "It would strengthen the paper if authors could list down novel ideas/challenges of their paper which are unique to this problem - either in the problem formulation or in proof techniques. ", "limitations": "Limitations are adequately addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and ideas are presented clearly. The problem description is interesting and the proposed approach combines existing methods with theoretical guarantees. At first glance, proofs of convergence rates seem correct. As their main contribution, the dependency on large batch size is reduced to a lesser extent.   ", "weaknesses": "The novelty of this paper lies in combining existing ideas from the field of distributed optimization and applying them to the problem at hand. In my opinion, these are not original ideas but rather an extension of ideas to a different setting. This is definitely not a trivial task but I believe it's not entirely original either.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. Below we address the reviewer’s questions and concerns.\n\n>**Concerns about the novelty.**\n\nOur paper indeed relies on the existing methods like SGDA and SEG for variational inequalities and existing techniques for achieving Byzantine robustness studied for minimization problems. However, despite the popularity and importance of variational inequality problems and the significant differences with minimization problems in terms of various aspects [1], such combinations were not studied in the literature. In lines 36-45, we explain what gaps remained in the field before our work. The results obtained in our paper are not known before and, thus, are novel.\n\nNext, we believe that it is not obvious beforehand what combination should be considered and what convergence guarantees one can achieve for the new methods. For example, one could expect that client momentum resolves the issue of SGDA-RA and allows convergence without large batchsize. However, this turned out to be a highly non-trivial task. As we explain in lines 200-204, it is unclear whether one can prove the convergence without large batches even in the special case of convex minimization problems (note that monotonicity can be seen as a generalization of convexity to the case of operators). We are not aware of papers that discuss this issue of Momentum-SGD in the convex case. So, our work brings this problem to the attention of the community. However, this issue was not that evident beforehand since nobody reported it, and the existing analysis from [2] bypasses this issue by considering non-convex problems where the analysis is not that sensitive to the bias in the stochastic gradient.\n\nTherefore, we believe that our paper makes an important step towards a better understanding of Byzantine robustness in the context of variational inequalities.\n\n---\nReferences:\n\n[1] Gidel et al. A Variational Inequality Perspective on Generative Adversarial Networks. ICLR 2019.\n\n[2] Karimireddy et al. Learning from history for byzantine robust optimization. ICML 2021.\n"}, {"review_id": "fbtpobHDMy", "reviewer": "Reviewer_RWvG", "summary": "This paper studies the problem of Byzantine-robust distributed learning with variation inequalities, e.g., max-min form. Three different robust methods for this problem are developed from the concepts of robust aggregation, client momentum, and checks of computations, respectively. For each of the proposed methods, this paper proves its convergence via strict theoretical analysis. Simulation experiments on quadratic game as well as robust NN training further demonstrate the superiority of the proposed methods on the predictive performance over the previous method. ", "questions": "Minor issue:\n\nThe font size in Figure 1 is too small, which makes the legends almost unreadable.", "limitations": "Limitations have been properly discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem of Byzantine-robust distributed learning with variational inequalities is important. I think this paper do a good job clarifying different scenarios (or conditions) of this problem and develop an effective method for each of the scenario. The proposed various methods and the corresponding analysis improve the frontier of the relevant research areas. \n\n2. This paper is technically sound with solid theoretical results. Comparison with other relevant work is clear.\n\n3. This paper is well written and easy to follow.", "weaknesses": "1. The motivation of tackling variation inequalities problems is not so sufficient. Provide more examples on VIs besides the max-min form may help better understand the significance of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and a positive evaluation of our work. Below we address the reviewer’s questions and concerns.\n\n>**Motivation of tackling variational inequalities.**\n\nIn our work, we are mostly motivated by min-max problem formulations that form a quite broad class of problems, as we illustrate in lines 27-33. Variational inequality problem is a convenient generalization of min-max problem. Therefore, we consider everything in the generality of variational inequalities. Regarding the additional motivating examples: variational inequalities arise in game theory, control theory, and differential equations [1].\n\n[1] Facchinei, F., & Pang, J. S. (2007). Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Science & Business Media.\n\n>**Font size in Figure 1.**\n\nWe thank the reviewer for the comment. We will increase the fonts in Figures for the final version of the paper.\n"}, {"review_id": "hfYGsotDfF", "reviewer": "Reviewer_vExH", "summary": "This paper studies convergence guarantees of Byzantine tolerant methods in the context of distributed variational inequalities.", "questions": "- Assumption 1/2 are for uniformly bounded variance/heterogeneity. But this can be unrealistic in the following case: looking at the bound in Theorem 1, with $\\mu$ in the denominator in the last two terms, we can potentially kill these terms by scaling the loss function be a large constant, consequently increasing $\\mu$. So, can the current results be modified to adapt to the case when the variance/heterogeneity is affine increasing with gradient norm squared?\n- Aren't you also using assumption 2 in Theorem 1-3?\n- Why are SGDA-RA and SEG-RA analyzed for separate assumptions? Doesn't SGDA-RA hold under assumptions of Theorem 2?\n- Why are SEG-CC and R-SEG-CC stated under different assumptions?\n\nMajor confusion about random checks of computation:\n- if the server knows random seeds, why does it need the additional $m$ clients to verify computations? Why can't it do that itself? This would be more privacy friendly also, since the clients can still trust the server, but not other clients. \n- And how can a client check other clients, without having access to their datasets?\n- Won't clients need to communicate their datasets for this to happen? Isn't that a major privacy violation?", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper seems to contain a lot of work.", "weaknesses": "In my opinion, the main weakness of the paper is its writing. I acknowledge that I have not read the papers most related to this one, [Karimireddy et al., 2021], [Gorbunov et al., 2022], and [Adibi et al., 2022]. Therefore, even though I work on related problems, I struggled to understand the theoretical results. For example,\n- Permutation invariance seems like a crucial concept but is not explained anywhere in the main paper.\n- Theorem 1: all I could infer from the bound is that if $\\delta=0$, the last two terms disappear, and the bound makes sense (since it generalizes smooth, strongly convex minimization). But, intuitively, why does the non-vanishing last term appear? \n- Similar comments about Theorem 2 and 3. Adding momentum seems to require using an averaged iterate rather than using the last iterate. Can you comment on if (and why) is this necessary?\n- Theorems 4-7 have little to no accompanying discussion or intuition for the stated bounds.\n- More questions below.\n\nI do not mean to belittle the authors' contribution. Given my judgment from reading the draft of the main paper, and apart from some questions I have below, I think this is a reasonable contribution. And I admit that many ML conference papers follow this style. But, I think this is not very helpful for the majority of the readers, except for the ones who are already too familiar with the field. Given the page limit in conference papers, maybe a journal would be a better venue for this paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback. Below we address the reviewer’s questions and concerns.\n\n>**The main weakness of the paper is its writing.**\n\nThank you for your multiple suggestions and comments. We will apply all necessary changes to the final version of the paper to make it easier to read for a broader audience. In the case of acceptance, we will be allowed to have one more page in the main part that we will use to provide these remarks. Alternatively, to get more space, we can move some of the theorems to the appendix and shorten the part on the numerical experiments.\n\n>**Permutation invariance.**\n\nThe definition is given in [1] (Definition B). We will add it to the final version.\n\n>**On Theorems 1-3.**\n\nThese results recover SOTA results for SGDA and SEG when $\\delta = 0$. When $\\delta > 0$, there are non-reducible terms proportional to $\\delta$. In Theorems 1 and 2, the terms proportional to $\\delta \\sigma^2$ appear because of the permutation invariance of SGDA-RA and SEG-RA. Intuitively speaking, permutation invariant algorithms do not track the information from the previous rounds. Therefore, Byzantine workers can hide small perturbations in the noise of the correct stochastic gradients in any single round that can accumulate over time, e.g., this happens with attacks from [2,3]. Next, the term proportional to $\\delta\\zeta^2$ is unavoidable in general for any algorithm [4]: when the problem is heterogeneous, Byzantines can jointly pretend to be good clients with non-representative data and shift the solution proportionally to the gradient dissimilarity of the good workers.\n\nTheorem 3: although M-SGDA-RA is non-permutation invariant, similar terms appear. As we explain in lines 201-204, this is related to the difficulties of the analysis of Momentum-SGD with biased stochastic gradient for **convex problems**. We bring the attention of the community to this non-trivial question via our results.\n\n>**Averaged-iterate analysis for the momentum-version.**\n\nWe analyze the momentum version in terms of the averaged iterate to make the analysis simpler. We believe that one can extend the analysis to the last iterate as well, but we do not do it since we expect that the same problem (the need for large batches) will remain in the last-iterate analysis.\n\n>**Discussion of Theorem 4-7.**\n\nThe main property of Theorems 4-7 is that they do not require large batches to converge to any predefined optimization error in the homogeneous case ($\\zeta = 0$). They are the first results of their type for Byzantine-robust variational inequalities. Let us discuss here some noticeable details. In each of these theorems, the first two terms recover (up to numerical factors) the SOTA results (in the case of no Byzantines) for distributed SGDA or SEG, respectively. The last terms appear because of the presence of Byzantines. In Theorems 4 and 6, the last terms do not have a linear speed-up in $n$ and are proportional to $\\gamma_1$ as well as the second term (there is a typo in Theorem 6: we should have $\\gamma_1$ in the last term instead of $\\gamma_1^2$). In Theorems 5 and 7, the last terms have better dependence on $\\varepsilon$ than the second terms and, therefore, for small $\\varepsilon$ the complexities coincide with the SOTA ones for SGDA and SEG (that are obtained for the case of no Byzantines).\n\n>**Assumptions 1 and 2.**\n\nWe use bounded variance and heterogeneity assumptions for the sake of simplicity and to make the comparison with the related work easier (these assumptions were used in this area before). Our analysis can be extended to the case of affine increasing variance/heterogeneity, i.e., when $\\sigma^2$ is replaced with $A\\|\\| F_i(x) \\|\\|^2 + \\sigma^2$ in (2) and $\\zeta^2$ is replaced with $B\\|\\|F(x)\\|\\|^2 + \\zeta^2$ in (3), similarly to [4].\n\n>**Assumption 2 in Theorems 1-3.**\n\nYes, we use it. Thank you for spotting the typo.\n\n>**Different assumptions for SGDA-RA and SEG-RA.**\n\nThank you for the good question. In fact, (SC) follows from (Lip) and (QSM) with constant $\\frac{L^2}{\\mu}$: $\\|\\|F(x)\\|\\|^2 \\leq L^2\\|\\|x-x^\\ast\\|\\|^2 \\leq \\frac{L^2}{\\mu}\\langle F(x), x-x^\\ast\\rangle$. However, the star-cocoercivity $\\ell$ can be significantly smaller than $\\frac{L^2}{\\mu}$. Next, when $\\mu = 0$, SGDA is not guaranteed to converge without cocoercivity [5], while SEG converges. We have the results for SEG-type methods when $\\mu = 0$.\n\n>**Different assumptions for SEG-CC and R-SEG-CC.**\n\nThis is a typo: in Theorem 7 we should have Assumption 4 instead of 5. Thank you for spotting this.\n\n>**Checks of computations.**\n\nThank you for the questions. As we mention in “Our Contributions” section, methods with the checks of computations are designed for the homogeneous case only ($\\zeta = 0$). This case is also very important for Byzantine-robust applications, as we explain in lines 70-71. The key idea is to use the computing power of workers and not overload the server with extra computations of the mini-batches (though it is possible for a powerful server). Since the data is homogeneous, i.e., the whole data is available to everybody, there are no privacy issues.\n\nAchieving convergence to any predefined in the general heterogeneous setup is impossible under Assumption 2 [4]. However, this is an interesting direction for future research requiring rethinking the whole concept of Byzantine workers for the applications like federated learning. This goes far beyond the scope of this work.\n\n[1] Karimireddy et al. Learning from history for byzantine robust optimization. ICML 2021.\n\n[2] Baruch et al. A little is enough: Circumventing defenses for distributed learning. NeurIPS 2019.\n\n[3] Xie et al.  Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation. UAI 2020.\n\n[4] Karimireddy et al. Byzantine-robust learning on heterogeneous datasets via bucketing. ICLR 2022.\n\n[5] Gidel et al. A Variational Inequality Perspective on Generative Adversarial Networks. ICLR 2019."}, {"review_id": "g6sy7pbWyI", "reviewer": "Reviewer_AxmQ", "summary": "**Summary:** The authors propose robust optimization methods for solving distributed variational inequalities (VI). The authors provide theoretical guarantees for numerous popular algorithms for solving min-max (more generally VI) problems. The authors corroborate their theoretical findings with experiments on quadratic games and robust neural network training. ", "questions": "Please see weaknesses section above. ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Strengths:**\n\n-\tThe authors provide guarantees for a set of algorithms for solving VIs with application to min-max optimization. Specifically, the authors propose a robust version of SGDA and SEG and provide theoretical convergence guarantees for the proposed algorithms. The authors show that if the batch size at each client is large enough the algorithms can converge to desired accuracy. \n-\tThe authors propose momentum versions of the vanilla algorithms and establish improved convergence performance. The authors establish convergence to a neighborhood whose size can be reduced with increasing batch sizes. \n-\tThe authors also propose random checks of computations versions of the methods for the homogeneous setting and provide a theoretical analysis of the proposed methods. \n-\tThe authors evaluate the convergence performance of the proposed algorithms on a quadratic game and for robust neural network training. \n\n", "weaknesses": "**Weaknesses:**\n\n-\tA major weakness of the proposed results is the requirement of large batch sizes to ensure convergence to the desired accuracy. Is it feasible to circumvent this requirement?\n-\tAnother drawback of the paper is that it is written in a very dense manner. The authors have attempted to include a host of results in the main paper which has left no space for stating the algorithms along with their discussions in the main paper. It is advisable to make the paper more accessible to the readers by including detailed algorithms in the main paper. \n-\tThe results are presented in terms of iterate convergence but in the contribution section, the authors have mentioned that their result implies exact convergence for the non-convex case which requires convergence in terms of gradient norm. Please clarify why iterate convergence implies convergence for the non-convex case.\n-\tSome of the discussion from the contribution section is missing in the respective sections. For example, the discussion on the convergence of non-convex functions is not included in the section where momentum versions of the algorithms are presented. \n\n---\n\nUpdated the score. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback and a positive evaluation of our work. Below we address the reviewer’s questions and concerns.\n\n>**Large batch sizes requirement.**\n\nPart of our results (Theorems 1-3) indeed require large batches: for SGDA-RA and SEG-RA this limitation cannot be bypassed (see lines 172-173), and M-SGDA-RA it is unclear whether one can circumvent this issue since it is unknown even in the case of minimization problems (see lines 200-204). However, the proposed methods with random checks of computation **do not require large batches**: Theorems 4-7 are valid even if the batchsize equals $1$. Moreover, these results establish the convergence to any predefined optimization error.\n\n>**Paper is written in a dense manner.**\n\nWe thank the reviewer for the suggestion. Indeed, we can move some of the results to the appendix as well as some details on the numerical experiments and use this space for providing more details about the algorithms and giving more discussion of the derived results. In the case of acceptance, there will also be an extra page for addressing the reviewers’ comments. We promise to add all necessary details requested by the reviewers in this case.\n\n>**Convergence in the non-convex case.**\n\nWe do not claim that we have the results for non-convex problems: in lines 103-105, we emphasize that **the existing results** about the Byzantine robustness of the methods with client momentum are derived for non-convex minimization problems. In our work, we found out that for quasi-strongly monotone variational inequalities, it is not an easy task: according to our analysis, the method with momentum still requires large batches. Since monotonicity can be seen as a generalization of convexity to the case of operators, it is natural to ask a simpler question: can we circumvent this issue in the case of convex minimization problems? This remains an open question as we explain in lines 201-203: the current analysis of Momentum-SGD in the convex case relies on the unbiasedness of the stochastic gradient. Since robust aggregation breaks the unbiasedness, it is unclear for now how to fix this issue.\n\nWe will make our statements clearer to avoid the readers’ confusion."}]

Author rebuttal:
We thank the reviewers for their feedback, time, and positive evaluation of our work. We appreciate that the reviewers acknowledged several strengths of our work:

- The paper is well-written (Reviewers zd6L and RWvG)

- The ideas are presented clearly (Reviewer zd6L)

- The problem is interesting (Reviewer zd6L)

- Dependency on the large batch size is reduced (Reviewer zd6L)

- The problem is important (Reviewer RWvG)

- The proposed various methods and the corresponding analysis improve the frontier of the relevant research areas (Reviewer RWvG)

- This paper is technically sound with solid theoretical results (Reviewer RWvG)

- Comparison with other relevant work is clear (Reviewer RWvG)

- The paper contains a lot of work (Reviewer vExH)

- The paper gives guarantees in different setups and evaluates the convergence performance of the proposed methods in the numerical experiments (Reviewer AxmQ)

The reviewers also raised several questions and concerns that we addressed in detail in our responses to each reviewer.

We also will be happy to participate in the discussion in the case if reviewers will still have questions/comments/concerns after reading our responses.


Meta-review: This paper studies the problem of Byzantine-robust distributed learning with variational inequalities. The authors provide theoretical guarantees for numerous popular algorithms for solving min-max (more generally VI) problems. The authors corroborate their theoretical findings with experiments on quadratic games and robust neural network training. The overall feedback is positive, the AC agrees and recommends acceptance.
Decision: Accept (poster)