Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates
Authors: Siqi Zhang
Sayantan Choudhury
Sebastian U Stich
Nicolas Loizou
Venue: ICLR 2024 poster (2024)
Keywords: Federated Learning
Variational Inequality
Minimax Optimization
Communication Complexity
Primary area: optimization
TL;DR: We present the first local gradient descent-accent algorithms with provable improved communication complexity for solving distributed variational inequalities on heterogeneous data.

Abstract: Distributed and federated learning algorithms and techniques associated primarily with minimization problems. However, with the increase of minimax optimization and variational inequality problems in machine learning, the necessity of designing efficient distributed/federated learning approaches for these problems is becoming more apparent. In this paper, we provide a unified convergence analysis of communication-efficient local training methods for distributed variational inequality problems (VIPs). Our approach is based on a general key assumption on the stochastic estimates that allows us to propose and analyze several novel local training algorithms under a single framework for solving a class of structured non-monotone VIPs. We present the first local gradient descent-accent algorithms with provable improved communication complexity for solving distributed variational inequalities on heterogeneous data. The general algorithmic framework recovers state-of-the-art algorithms and their sharp convergence guarantees when the setting is specialized to minimization or minimax optimization problems. Finally, we demonstrate the strong performance of the proposed algorithms compared to state-of-the-art methods when solving federated minimax optimization problems.

Published as a conference paper at ICLR 2024
COMMUNICATION-EEFRCENN GRADIENT DESCENT- ACCENT METHODS FOR DISTRIBUTED VARIATIONAL INEQUALITIES: UNIFIED ANALYSIS AND LOCAL UP-
DATES
Siqi Zhang* AMS MINDS
Sayantan Choudhury" AMS & MINDS
Johns Hopkins University szhan2077 76 jhu. edu
Johns Hopkins University schoudh8@ jhu. edu
Sebastian Stich
Nicolas Loizou
CISPA Helmholtz Center for Information Security st stichécispa.de
AMS & MINDS
Johns Hopkins University nloizou@ jhu. edu
ABSTRACT
Distributed and federated learning algorithms and techniques associated primarily with minimization problems. However, with the increase of minimax optimiza- tion and variational inequality problems in machine learning, the necessity designing efficient distributeddfedderatedd learning approaches for these problems is becoming more apparent. In this paper, we provide unified convergence analy- sis of communication--fficle
local training methods for distributed variational inequality problems (VIPs). Our approach is based on general key assumption on the stochastic estimates that allows to propose and analyze several novel local training algorithms under a single framework for solving a class of structured non- monotone VIPs. We present the first local gradient descent-accent algorithms with provable improved communication complexity for solving distributed variational inequalities on heterogeneous data. The general algorithmic framework recovers state-of-the-an -ott----tte--tttte algorithms and their sharp convergence guarantees when the set- ting is specialized to minimization or minimax optimization problems. Finally, demonstrate the strong performance of the proposed algorithms compared state-of- the-art methods when solving federated minimax optimization problems.
INTRODUCTION
Federated learning (FL) (Konečný al., 2016; McMahan al., 2017; Kairouz al., 2021) has become a fundamental distributed machine learning framework in which multiple clients collaborate train model while keeping their data decentralized. Communication overhead is one of the main bottlenecks in FL (Karimireddy et al., 2020), which motivates the use by the practitioners of advanced algorithmic strategies alleviate the communication burden. One of the most popular and well-studied strategies to reduce the communication cost is increasing the number of local steps between the communication rounds (McMahan et al., 2017; Stich, 2018; Assran al., 2019; Khaled et al., 2020a; Koloskova et al., 2020).
Towards a different objective, several recently proposed machine learning approaches have moved from the classical optimization formulation to multi-player game perspective, where good model framed as the equilibrium of a game, as opposed to the minimizer of an objective function. Such machine learning models are framed as games (or in their simplified form minimax optimization problems) and involve interactions between players, e.g., Generative Adversarial Networks (GANs)
"Equal contribution.

---

Published as a conference paper at ICLR 2024
(Goodfellow et al., 2014), adversarial training (Madry al., 2018), robust optimization (Namkoong & Duchi, 2016), and multi-agent reinforcement learning (Zhang et al., 2021a).
Currently, federated learning algorithms and techniques are associated primarily with minimization problems. However, with the increase of game- thee-theeoctical formulations in machine learning, the necessity of designing efficient federated learning approaches for these problems is apparent. In federated learning algorithms
this work, we are interested in the design of communication-efficin suitable for multi-player game formulations. In particular, we consider more abstract formulation and focus on solving the following distributed/feddrrtee variational inequality problem (VIP):
Find z" Rd, such that (F(=*), =²) 2 0, Vz E ERR.
where F Rdd + RR" is a structured non-monotone operator. We assume the operator F is distributed across different nodes/clients and written F(z) 1/2 -i= f((2). In this setting, the operator fi : IR' + IR' is owned by and stored on client i. Since we are in the unconstrained scenario, problem (1) can be equivalently written as finding z" E such that F(=*) = 0 (Loizou et al., 2021; Gorbunov al., 2022a).
Problem (1) can be seen as a more abstract formulation of several popular problems. In particular, the selection of the operator F captures classical minimization problems mingeR" f(z), minimax optimization problems with 2 = (21,42), min,, gR+4 max f(1 x2), and multi-player games as special cases. For example, in the minimization case, F() fz(z), and it is easy to see that 2" is the solution of (1) if and only if f=(=") = O, while in the minimax case F(z) F(x1,12)
(V 21 f x2)), -V = (x) x2)) and 2" is the solution if and only if 2* is a stationary point of f. More generally, an important special case of the formulation (1) is the problem of finding the equilibrium point in an N-players game. In this setting, each player j is simultaneously trying to find the action 2 which minimizes with respect to zj E Rd their own cost function (z while the other players are playing z-j. which represents In this scenario, operator F(r) is the concatenation over all possible j of V Vz x-z))
(Ii,..., xx) with the component removed.
Finally, in the distributtedffederated learning setting, formulation (1) captures both classical FL minimization (McMahan et al., 2017) and FL minimax optimization problems (Sharma et al., 2022; Deng & Mahdavi, 2021) as special cases.
1.1
MAIN CONTRIBUTIONS
Our key contributions are summarized as follows:
We present the first connection between regularized VIPs and federated learning setting by explaining how one can construct a consensus reformulation of problem(1) 1) by appropriately selecting the regularizer term R (r) (see discussion in Section 2.1).
VIPs and Federated Learning:
We provide a unified theoretical framework for the design of efficient local training methods for solving the distributed VIP (1). For our analysis, we a general key assumption on the stochastic estimates that allows us to study, under single framework, several stochastic local variants of the proximal gradient descent-ascent (GDA) method
Unified Framework:
Communication Acceleration: In practice, local algorithms are superior in communication complexity compared to their non-local counterparts. However, in the literature, the theoretical communication complexity of Local GDA does not improve upon the vanilla distributed GDA (i.e., communication in every iteration). Here we close the gap and provide the first communication- accelerated local GDA methods. For the deterministic strongly monotone and smooth setting, our method requires O (N: In 2) communication rounds over the O ( In 2) of vanilla GDA (and previous analysis of Local GDA), where is the condition number. See Table for further details.
OO
Heterogeneous Data: Designing algorithms for federated minimax optimization and distributed VIPs, is a relatively recent research topic, and existing works heavily rely on the bounded het- erogeneity assumption, which may be unrealistic in FL setting (Hou et al., 2021: Beznosikov et al.. 2020; Sharma et al., 2022). Thus, they can only solve problems with similar data between clients/nodes. In practical scenarios, the private data stored by a user on a mobile device and the
'Throughout this work we this suggestive name (GDA and Stochastic GDA/ SGDA) motivated by the minimax formulation, but we highlight that our results hold for the more general VIP (1)
2

---

Published as a conference paper at ICLR 2024
Table 1: Summary and comparison of algorithms for solving
federated minimax optimization problems (a special case of the distributed VIPs (1)).
Algorithm'
Acceleration?
Variance Red.?
Communication Complexity
GDA/SGDA
x
o maxx
Iu
(Fallah et al., 2020)
Local GDA/SGDA
x +
x
X
o
(Deng & Mahdavi, 2021)
ProxSkip-GDA/SGDAA.
X
o (V max {
of n²2
In
(This work)
ProxSkip-LSYRRGD--ELL
(1)
(This work)
"Accoleration" whether the algorithm enjoys acceleration in communication compared to its non-local counterpart, "Variance Red.?" whether the algorithm (in stochastic setting) applies variance reduction, "Communication Complexity" the communication complexity of the algorithm. Here k L/μ denotes the condition number where L is the Lipschitz parameter and şu is the modulus of strong convexity, of corresponds to the variance level at the optimum (o = 0 in deterministic setting), and A captures the bounded variance. For more detailed comparison of complexities, please also refer to Table 2.
data of different users can be arbitrarily heterogeneous. Our analysis does not assume bounded heterogeneity, and the proposed algorithms (ProxSkip-VIP-FF. and ProXSkip---VVRIDD--FL) guarantee convergence with an improved communication complexity.
Sharp rates for known special cases: For the known methods/settings fitting our framework, our general theorems recover the best rates known for these methods. For example, the convergence results of the Proximal (non-local) SGDA algorithm for regularized VIPs (Beznosikov et al., 2022h) and the ProxSkip algorithm for composite minimization problems (Mishchenko et al., 2022) can be obtained as special cases of our analysis, showing the tightness of our convergence guarantees.
Numerical Evaluation: In numerical experiments, we illustrate the most important properties of the proposed methods by comparing them with existing algorithms in federated minimax learning tasks. The numerical results corroborate our theoretical findings.
2 TECHNICAL PRELIMINARIES
2.1 REGULARIZED VIP AND CONSENSUS REFORMULATION
Following classical techniques from Parikh & Boyd (2014), the distributed VIP (1) can be recast into consensus form:
Find x² E RR such that (F(="), x²) + R(x) R(x*) 2 0, Vr E Rd.
(2)
where d = nd' and
F(T) & Σ F((a), R(x) & So in= Z.
+000
otherwise.
(3)
Here x (21, Ir E ER. RR, Rd F Rd + R. R (0, f((x,), 0) where (( dimension expansion on the variable enlarged from d' to d. It is well-known that the two problems (1) and (2) are equivalent in terms of the solution, which we detail in Appendix F.3.
Rd - Rd and (x(x,)
= (xx)). Note that the reformulation requires a
Having explained how the problem (1) can be converted into a regularized VIP (2), let us now present the Stochastic Proximal Method (Parikh & Boyd, 2014; Beznosikov et al., 2022b), one of the most popular algorithms for solving general regularized VIPs?. The update rule of the Stochastic Proximal Method defines follows:
+ 1 - 110 mr|
1 prox
79t) where prox., (rox,,R(x) R(x) A argmin
R(v))
(4)
wERd
27
We call general regularized VIPs, the problem (2) where F: Rd - Rd is operator and R Rd - R is regularization term proper lower semicontinuous convex function).
3

---

Published as a conference paper at ICLR 2024
Here It is unbiased estimator of F(zz) and y 0 is the step-size of the method. As explained in (Mishchenko et al., 2022), is typically assumed that the proximal computation (4) can be evaluated in closed form (has exact value), and its computation it is relatively cheap. That is, the bottleneck in the update rule of the Stochastic Proximal Method is the computation of gt- This is normally the case when the regularizer term R(x:) in general regularized VIP has simple expression, like -ormm expreeeieeeee (R(x)- = || and fz-norm (R(x) = | (2). For more details on closed-form expression (4) under simple choices of regularizers R(x), we refer readers to check Parikh & Boyd (2014).
However, in the consensus reformulation of the distributed VIP, the regularizer R(a)) has a specific expression (3) that makes the proximal computation (4) expensive compared to the evaluation of Gt- In particular, note that by following the defimition of R(x) in (3), we get that F = 2. Ei=1 T. and prox.,n(a)) = T., ..). So evaluating (r) is equivalent taking the average of the variables 25 (Parikh & Boyd, 2014), meaning that it involves a high communication cost in distribuueedffederaeed learning settings. This was exactly the motivation behind the proposal of the ProxSkip algorithm in Mishchenko et al. (2022), which reduced the communication cost by allowing the expensive proximal operator to be skipped in most iterations.
In this work, inspired by the ProxSkip approach of Mishchenko et al. (2022), we provide a unified framework for analyzing efficient algorithms for solving the distributed VIP (1) and its consensus reformulation problem (2). In particular in Section 3. we provide algorithms for solving general regularized VIPs (not necessarily a distributed setting). Later in Section 4 we explain how the proposed algorithms can be interpreted as distributeddfederraeed learning methods.
2.2 MAIN ASSUMPTIONS
Having presented the consensus reformulation of distributed VIPs, let now provide the main conditions of problem (2) assumed throughout the paper.
Assumption 2.1. We assume that Problem (2) has unique solution xt and
1. The operator F is j--quaii-strongly monotone and (-star-cocoercive with μ, f > i.e. Vn E Rd.
(F(x) - F(=*), x²) 2 u||x - 1I1 (F(x) - -===((x"xxx"")) - 21
2. The function R(-) is proper lower semicontinuous convex function.
and Lipschitz continuity assumptions commonly used in analyzing methods for solving problem (2) and captures monotone and non- Lipschitz problems as special cases (Loizou et al., 2021). In addition, given that the operator F is T--Lipschitz continuous and j-stroogly monotone, it can be shown that the operator F is (s: ()-tta- cocoercive where A L/p is the condition number of the operator (Loizou al., 2021).
Assumption 2.1
is weaker than the classical
Motivated by recent applications in machine learning, in our work, we mainly focus on the case where we have access unbiased estimators of the operator F. Regarding the inherent stochasticity, we further use the following key assumption, previously used in Beznosikov et al. (2022b) for the analysis of Proximal SGDA, to characterize the behavior of the operator estimation.
Assumption 2.2 (Estimator). For all f 2 0, we assume that the estimator is unbiased (E[g.
F(x:)). Next, we assume that there exist non-negative constants A, B, C, D1, D2 2 0, p E (0, 1] and a sequence of (possibly random) non-negative variables {or 1r20 such that for all 2 0:
EE gg - F(x*)11 < 2A(F(z) - f(x")x===>->)">))))))))))))))) x²) + Bo + D1:
S 2C(((z)) - F(=")) + (1 p) + D2.
Variants of Assumption 2.2 have first proposed in classical minimization setting for providing unified analysis for several stochastic optimization methods and, at the same time, avoid the more restrictive bounded gradients and bounded variance assumptions (Gorbunov et al., 2020; Khaled et al., 2020b). Recent versions of Assumption 2.2 have been used in the analysis of Stochastic Extragradient (Gorbunov et al., 2022a) and stochastic gradient-descen 2022b) for solving minimax optimization and VIP problems. To our knowledge, analysis of existing local training methods for distributed VIPs depends on bounded variance conditions. Thus, via Assumption 2.2, our convergence guarantees hold under more relaxed assumptions well. Note that
assent (Beznosikov et al.,
4

---

Published as a conference paper at ICLR 2024
Assumption 2.2 covers many well-known conditions: for example, when 02 and F(x*) 0. it will recover the recently introduced expected co-coercivity condition (Loizou et al., 2021) where A corresponds to the modulus of expected co-coercivity, and Dj corresponds to the scale of estimator variance at x². In Section 3.2, we explain how Assumption 2.2 is satisfied for many well-known estimators It. including the vanilla mini-batch estimator and variance reduced-type estimator. That is, for the different estimators (and, as result, different algorithms), we prove the closed-form expressions of the parameters A, B, C, D1, D2 2 0. (0, 1] for which Assumption 2.2 is satisfied.
GENERAL FRAMEWORK: PROXSKIP-VIP
Here we provide a unified algorithm framework (Algorithm 1) for solving regularized VIPs (2). Note that in this section, the guarantees hold under the general assumptions 2.1 and 2.2. In Section 4 we will further specify our results to the consensus reformulation setting where (3) also holds.
Algorithm is inspired by the ProxSkip proposed in Mishchenko et al. (2022) for solving composite minimization problems. The two key elements the algorithm are the randomized prox-skipping, and the control variate he. Via prox-skipping, the proximal oracle is rarely called if is small, which helps to reduce the computational cost when the proximal oracle expensive. Also, for general regularized VIPs we have F F(x*) # at the optimal point x" due to the composite structure. Thus skipping the proximal operator will not allow the method to converge. On this end, the introduction of he alleviates such drift and stabilizes the iterations toward the optimal point (h, F(x")) )).
We also highlight that Algorithm is a general update rule and can vary based on the selection of the unbiased estimator gi and the probability p. For example, if p 1, and h O, the algorithm is reduced to the Proximal SGDA algorithm proposed in Beznosikov et al. (2022b) (with the associated theory). We will focus on further important special cases of Algorithm I below.
Algorithm -roXSkip-VIP
Input: Initial point To. parameters >, initial control variate ho, number of iterations T
1: for all = 0, 1, T do
2: θ 2t 7---(0 (9t he)
3: Flip coin 0,, and 0g = 1 w.p. p, otherwise
4: if 0. then
5:
Ø1+1 prox n (8t+1 h
6: else
7:
U1+11 Te+1
8: end if
9: h4+1 he 12 [2141 Bz41)
10:
end for
3.1 CONVERGENCE OF PROXSKIP-VE VIP
Our main convergence quarantees are presented in the following Theorem and Corollary.
Theorem 3.1 (Convergence of ProxSkip-VIP), With Assumptions 2.1 and 2.2, let 7 S
B min #. MA+MC] ). A min {7/4 12 . XI ) for some M > Denote V, A || - 1/2
(7/1)?1h, 1( MrZa7. Then the iterates of ProxSkip- VIP (Algorithm 1), satisfy:
E[Vr] s (1-7) V. 2D
MD2)
Theorem 3.1 show that ProxSkip- VIP converges linearly to the neighborhood of the solution. The neighborhood is proportional the step-size y and the parameters D2 and D: of Assumption 2.2. In addition, we highlight that if we set p == 1, and h, = O, then Theorem 3.1 recovers the convergence guarantees of Proximal-SGDD, of (Beznosikov et al., 2022b, Theorem 2.2). As a corollary of Theorem 3.1, we can also obtain the following corresponding complexity results.
5

---

Published as a conference paper at ICLR 2024
Corollary 3.2. With the setting in Theorem 3.1, , if we set M
2B
yp and y
p
min j 2(A+MC)) 2p 2
we have B[V]] I with iteration complexity and the number of calls to the proximal oracle prox(.) as
e
Me
D2)
A
BC
D1 B
D2
Vo
A
BC
1
D1
+
D2
Vo In
In
and O
max
HLe
P
12t
c
3.2 SPECIAL CASES OF GENERAL ANALYSIS
Theorem 3.1 holds under the general key Assumption 2.2 on the stochastic estimates. In this subsection, via Theorem 3.1, we explain how different selections of the unbiased estimator gr in Algorithm lead to various convergence guarantees. In particular, here we cover (i) ProxSkip-SGDA (ii) ProxSkip-GDDi GDA, and (dilvariance--eduee method ProxSkip--SVRRGDA To the best of our knowledge, none of these algorithms have been proposed and analyzed before for solving VIPs.
(i) Algorithm: ProxSKip-SGDA. Let us have the following assumption:
Assumption 3.3 (Expected Cocoercivity). We assume that for all the stochastic operator gr g(ax),, which is unbiased estimator of F(2:), satisfies expected cocoercivity, i.e., for all Id there Lg > such that (Elg(=)) g(2" )|( Lg (F(x) F(x*), ) x*).
The expected cocoercivity condition was first proposed Loizou et al. (2021) to analyze SGDA and the stochastic consensus optimization algorithms efficiently. It is strietly weaker compared to the bounded variance assumption and "growth conditions," and it implies the star-cocoercivity of the operator F. Assuming expected co-coercivity allows characterize the estimator gr.
Lemma 3.4 (Beznosikov
(2022b)). Let Assumptions 2.1 and 3.3 hold and let o E [[lg(x') F(x") < +oo. Then di satisfies Assumption 2.2 with A Lg. Dj 20
p and B C' D2 of 0.
By combining Lemma 3.4 and Corollary 3.2, we obtain the following result.
Corollary 3.5 (Convergence of ProxSkip-SGDA), With Assumption 2.1 and 3.3, we further set 7 min 20g zn Bo?
1 de and VTI,, then for the iterates of ProxSkip-SGDA, have
E[Vr] S with iteration complexity and the number of calls of the proximal oracle prox(-) o max {
La e pre !n! and of (Mmaa La o² p²e ! respectively.
(ii) Deterministic Case: ProxSkip-GDA. In the deterministic case where g(xe) = F(xx), ), the algorithm ProxSkip-SGDA is reduced to ProxSkip-GDA Thus, Lemma 3.4 and Corollary 3.2 but with 0. In addition, the expected co-coercivity parameter becomes L, by Assum. 2.
Corollary 3.6 (Convergence of ProxSkip-GDA). With the same setting in Corollary 3.5, if we set the estimator = F(x+). and 7 = 22 the iterates of ProxSkip-GIDA satisfy: [[[T]] S
(1 - mii {Tp, p²1) Vo. and we get E[Vr] < e with iteration complexity and number of calls of the proximal oracle prox(-) O In and O ((V In ) respectively.
Note that if we further have F to be L-Lipschitz continuous and μ-sttooglyy monotone, then = kL where L/p is the condition number (Loizou et al., 2021). Thus the number of iteration and calls of the proximal oracles are O(k2 In !) and (O In 2) respectively. In the minimization setting, these two complexities are equal to O In 1) and ((VRln In !) since L, l = L. In this case, result recovers the result of the original ProxSkip method in Mishchenko et al. (2022).
(iii) Algorithm: ProxSkip-L-SvRGE
Here, we focus on a aariance-reduceed variant of the proposed ProxSkip framework (Algorithm 1). We further specify the operator F in (2) be in a finite-

---

Published as a conference paper at ICLR 2024
sum formulation: F(x) = Ein Fx)). We propose the ProxSkip-Looples--SVR (ProxSkip-L. SVRGDA) algorithm (Algorithm 3 in Appendix) which generalizes the L-SVRGDA proposed in Beznosikov al. (2022b). In this setting, need to introduce the following assumption:
Assumption 3.7. We assume that there exist a constant i such that for x E R&: 1 E [x)x) - 2 - ((F(x)
F(x"), ), ----- x*).
each F; is --cocoercive, then Assumption 3.7 holds with ? S max4e]]| L, Using Assumption 3.7 we obtain the following result (Beznosikov et al., 2022b).
Lemma 3.8 (Beznosikov et al. (2022b)). With Assumption 2.1 and 3.7, we have the estimator gr
in Algorithm satisfies Assumption 2.1 with A 2, B 2, D1 D2 0, C 2 p q and
oe
of = , E. 1 (x())) - (a
By combining Lemma 3.8 and Corollary 3.2, we obtain the following result for ProxSkip-L-VRRGDA Corollary 3.9 (Complexities of ProxSkip-L-SVRGIDA)
Let Assumption 2.1 and 3.7 hold. If we further set q = 27μ,, M _ p vTH and y = min
σz } then we obtain E[V]] S with
iteration complexity and the number of calls of the proximal oracle prox(.) (C//ulh b) and the number of calls of the proximal oracle prox(-) as O lm)
If we further consider Corollary 3.9 in the minimization setting and assume each F; is L-Lipschitz and ju-strongly convex, the number of iteration and calls of the proximal oracles will be O (<=li 4) and (VV w//li In 2), which recover the results of variance-reduced ProxSkip in Malinovsky et al. (2022).
APPLICATION OF PROXSKIP TO FEDERATED LEARNING
In this section, by specifying the general problem to the expression of (3) as special case of (2), we explain how the proposed algorithmic framework be interpreted federated learning algorithms. As discussed in Section 2.1, in the distributed/federrtte setting, evaluating the prox, x (x) equivalent
communication between the workers. the FL setting, Algorithm I can be expressed Algorithm 2. Note that skipping the proximal operator in Algorithm corresponds to local updates in Algorithm In Algorithm 2, It.t = (r(,,.)) the unbiased estimator of the (x.,.) of the original problem (1), while the client control vectors hir satisfy hi > fz()). The probability p in this setting shows how often a communication takes place (averaging of the workers' models).
Algorithm 2 ProxSkip- VIP-FL
i and / parameters T Input: Initial points { /
for all 0, 1,,1,... do
2: Server: Flip a coin dg, 0g = 1 w.p. p. otherwise 0. Send 6, to all workers
3: for each workers E [n] in parallel do
4: Fi,111 Ti,t 7 ha.))
I/ Local update with control variate
5: 0r = then
6: Worker: x|,4+1 = 31,41 I h4 sends 2',441 the server
7:
Server: computes F1,41 = Ei dhe41 and send to workers
// Communication
8:
else
9:
F4,4+1 = To,4+1
// Otherwise skip the communication step
end if
11: hi,441 = hit + E(ris41 - T(,41)
12: end for
end for
Algorithm: ProsSkip-GDDA-FL. The first implementation of the framework consider is SooSkip-SGDA-Ha Similar to MoxSkip-SGGD. in the centralized setting, here we set the esti- mator to be the vanilla estimator of F, i.e., Ji.t g=(#a,), where yi is an unbiased estimator of fi-
7

---

Published as a conference paper at ICLR 2024
We note that if we set ha.e = 0. then Algorithm 2 is reduced to the typical Local SGDA (Deng & Mahdavi, 2021). To proceed with the analysis in FL, we require the following assumption:
Assumption 4.1. The Problem (1) attains a unique solution 2" E R Each fi in (I), it is
s-quasi--trongly monotone around z", i.e., for any I; E IRd (fi((a)) - fi(="), 2²) z
nl|2, == Operator (r()),, is unbiased estimator of fi(x,), and for all v, R we have (z, 91(2*)]| S L,(f((z) (, 2*).
The assumption on the uniqueness of the solution is pretty common in the literature. For example, in the (unconstrained) minimization case, quasi-strong monotonicity implies uniqueness =" (Hinder et al., 2020). Assumption 4.1 is required as through it, we can prove that the operator F in (2) satisfies Assumption 2.1, and its corresponding estimator satisfies Assumption 2.2, which we detail in Appendix F.3. Let now present the convergence guarantees.
Theorem 4.2 (Convergence of ProXSkip-SGDA-FL), With Assumption 4.1, then ProxSkip- FL (Algorithm 2) achieves [[[V]] I (where V7 is defined in Theorem 3.1), with iteration
complexity O(max { Lim o2 ( In 2) and communication complexity Ol max
Lr ب. In ()
Comparison with Literature. Note that Theorem 4.2 is quite general, which holds under any reasonable, unbiased estimator. In the special case of federated minimax problems, one can use the same (mini- imini-batch) gradient estimator from Local SGDA (Deng & Mahdavi, 2021) in Algorithm 2 and our results still hold. The benefit of our approach compared Local SGDA is the communication acceleration, as pointed out in Table 1. In addition, in the deterministic setting (gi (gi,))))) f((z..)
have of 0 and Theorem 4.2 reveals Oll/p !) iteration complexity and O O(vE/ulm communication complexity for ProxSkip-GDA--F.. In Table 2 of the appendix, we provide a more detailed comparison of our Algorithm 2 (Theorem 4.2) with existing literature in FL. The proposed approach outperforms other algorithms (Local SGDA, Local SEG, FedAvg-S) in terms of iteration and communication complexities.
As the baseline, the distributed (centralized) gradient descent-ascent (GDA) and extragradient (EG) algorithms achieve Ors² In 2) and On communication complexities, respectively (Fallah et al., 2020; Mokhtari et al., 2020b). We highlight that our analysis does not require an assumption on bounded heterogeneity / dissimilarity, and as a result, we can solve problems with heterogeneous data. Finally, as reported by Beznosikov et al. (2020), the lower communication complexity bound for problem (1) given by 2(x In 4), which further highlights the optimality of our proposed ProxSkip-SGDA-FL algorithm.
Algorithm: ProsSkp-I-SVRRDDA-E.. Next, we focus on variance-reduced variants of ProxSkip-
SGDA-FL and we further specify the operator F in (2) as F(z) & Σ (z;) and F((x) & m; 2 1=1 (x:). The proposed algorithm, ProxSkip---SVRGDD -L,, presented in the Appendix as Algorithm 4. In this setting, we need the following assumption on F; to proceed with the analysis.
Assumption 4.3. The Problem (1) attains a unique solution =. Also for each fa in (1), it is j-quasi-strongly monotone around zt Moreover we assume for all I; E 12d we have 7. = (x.) - (=) < (()(()))) [(="), =*)-
m.
show that under Assumption (4.3), the operator and unbiased estimator fit into the setting of Assumptions 2.1 and 2.2 (see derivation in Appendix F.4). obtain the following complexity result.
Similar to the ProxSkip- -SDA--- case,
As result,
Theorem 4.4 (Convergence of Proxskip---VVRGDAA iterates of ProxSkip---VVRGDA--EE achieve E[Vr] (where Vr is defined in Theorem w.ih
Let Assumption 4.3 hold. Then the
itcration complexity ( μ In )) and communication complexity O( O(V ////unn// 2).
/
In the special case of minimization problems mingeRs f(z), i.e., F(z) = Vf(z), we have Theo- rem 4.4 recovers the theoretical result Malinovsky et al. (2022) which focuses on ProxSkip methods for minimization problems, showing the tightness of our approach. Similar to the ProxSkip- VIP-FL, the MoosSkip-L-VRGGAA
enjoys communication complexity improvement in terms of the condition number For more details, please refer Table 1 (and Table 2 in the appendix).
8

---

Published as a conference paper at ICLR 2024
5 NUMERICAL EXPERIMENTS
We corroborate our theory with the experiments, and test the performance of the proposed algorithms ProxSkip-(SyGDA--FL (Algorithm 2 with g: (x(x).) = (x .) or its unbiased estimator) and ProxSkip- L-SVRGIA-FL (Algorithm 4). We focus on two classes of problems: (i) strongly monotone quadratic games and (ii) robust least squares. See Appendix G and H for more details and extra experiments.
To evaluate the performance, we use the relative егтоr measure || - The horizontal axis corresponds to the number of communication rounds. For all experiments, we pick the step-size and probability p for different algorithms according to our theory. That is, ProxSkip-(S)GDA-T based on Corollary 3.5 and 3.6, ProxSkip--SVRRGA-
by Cororllary 3.9. See also Table 3 in the appendix for the settings of parameters. We compare our methods to Local SGDA (Deng & Mahdavi, 2021), Local SEG (Beznosikov al., 2020) (and their deterministic variants), and FedGIA- deterministic algorithm proposed in Sun & Wei (2022). For all methods, we use parameters based on their theoretical convergence guarantees. For more details on our implementations and additional experiments, see Appendix G and H.
Cowmusiaala lounce
KLrse Communtaaion
Rounds
(a) Deterministic Case
(b) Stochastic Case
(a) Deterministic Case
(b) Stochastic Case
Figure 1: Comparison of algorithms on the strongly- Figure 2: Comparison of algorithms the Robust
monotone quadratic game (5).
Least Square (6)
Strongly-monotone Quadratic Games.
In the first experiment, we consider a problem of the form
Σ 1 ma
Σ (1,
min max ERd m2ERd
(5)
J=1
Here we set the number of clients n = 20, m, = 100 for all i E [n] and = 20. We generate positive semidefinite matrices Aig, Bej, Cij E Raxd such that eigenvalues of Aej. Ct₃ lie in the interval [0.01, 1] while those of Bij lie in [0, 1]. The vectors dij: Cij E Rd are generated from (2 0. Ia) distribution. This data generation process ensures that the quadratic game satisfies the assumptions of our theory. To make the data heterogeneous, produce different Aij, Bij, Cij. aig. Gjj across the clients indexed by E (n].
where (1,,
A.] + 2. Biya2 - - -
We present the results in Figure for both deterministic and stochastic settings. As our theory predicted, proposed methods are always faster in terms of communication rounds than Local (S)GDA. The current analysis of Local EG requires the bounded heterogeneity assumption which leads convergence
neighborhood even in deterministic setting. As also expected by the theory, our proposed variance-reduced algorithm converges linearly to the exact solution.
Robust Least Square. In the second experiment. we consider the robust least square (RLS) problem (El Ghaoui & Lebret, 1997; Yang et al., 2020a) with the coefficient matrix A E grxs and noisy vector yo E R.." We assume Yo is corrupted by bounded perturbation (i.e..|oo) S 8g). RLS minimizes the worst case residual and can be formulated as follows:
min max ||A,
y|l² where
yo y.
3 6:1|o|
In our work, we consider the following penalized version of the RLS problem: | y/ Ally 2oll
min max BER- yER
(6)
This objective function is strongly- woonngly-oooee-ssttnnyy--------e -wtooogly-ooncawee when À > (Thekumparampii et al., 2022). We run experiment the "California Housing" dataset from scikit-learn package (Pe- dregosa et al., 2011), using À= = 50 in (6). Please see Appendix G for further detail on the setting.
In Figure 2, show the trajectories of our proposed algorithms compared to Local EG, Local GDA and their stochastic variants. In both scenarios (deterministic and stochastic), our ProxSkip- GDA/SGDA-FL. algorithms outperform the other methods in terms of communication rounds.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
The code for implementing all proposed algorithms and reproducing our experimental evaluation available within the supplementary materials, and https::///// /ttp:////ghthb//// com/ isayantan/ P ProxSkipVIP.
ACKNOWLEDGEMEET
Siqi Zhang gratefully acknowledges funding support from The Acheson J. Duncan Fund for the Advancement of Research in Statisties by Johns Hopkins University. Nicolas Loizou acknowledges support from CISCO Research.
REFERENCES
Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In COLT, 2022.
Sulaiman A Alghunaim and Kun Yuan. An enhanced gradient-tracking bound for distributed online stochastic convex optimization. arXiv preprint arXiv:2301 002855, 2023.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp. 344-353. PMLR, 2019.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, optimal and robust algorithms. arXiv preprint arXiv:2010.13/12 2020.
Aleksandr Beznosikov, Pavel Dvurechenskii, Anastasiia Koloskova, Valentin Samokhin, Sebastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. NewrlPS, 2022a.
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. arXiv preprint arXiv:2202.07262. 2022b.
Axel Böhm. Solving noncomvex-noncooeee. min-max problems exhibiting weak minty solutions. arXiv preprint arXiv:2201.122477 2022.
Xufeng Cai, Chaobing Song. Cristóbal Guzmán, and Jelena Diakonikolas. stochastic halpern iteration with variance reduction for stochastic monotone inclusion problems. arXiv preprint arXiv:2203.09436, 2022.
Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, pp. 217-234. SIAM, 2011.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Guanpu Chen, Gehui Xu, Fengxiang He, Yiguang Hong, Leszek Rutkowski, and Dacheng Tao. Global nash equilibrium non-convex multi-player game: Theory and algorithms. arXiv preprins arXiv:2301.08015, 2023.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In NewrIPS, 2014.
10

---

Published as a conference paper at ICLR 2024
Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. AISTATS, 2021.
Paolo Di Lorenzo and Gesualdo Scutari. Next:
In-network nonconvex optimization. IEEE Transac- fions on Signal and Information Processing over Networks, 2(2): 122):120-136, 2016.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan. Efficient methods for structured nonoonevveee min-max optimization. In AISTA7S, 2021.
Laurent El Ghaoui and Hervé Lebret. Robust solutions to least-squares problems with uncertain data. 1997.
SIAM Journal on matrix analysis and applications,
Francisco Facchinei and Jong-Shi Pang. Finite-dimension variational inequalities and complemen- tarity problems. Springer, 2003.
Alireza Fallah, Asuman Ozdaglar, and Sarath Pattathil. An optimal multistage stochastic gradient method for minimax problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 3573-3579. IEEE, 2020.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang. Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In AISTATS, 2019.
Ian Goodfellow, Jean Pouget-Abadie,, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NeurIPS, 2014.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent. In AISTATS, 2020.
Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pp. 7865-7901. PMLR, 2022a.
Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence proximal point and extragradient-bused methods beyond monotonicity: the case of negative comonotonicity. arXiv preprint arXiv:2210.1383/ 2022b.
Philip Hartman and Guido Stampacchia, On some non-linear elliptic differentiall-unccional equations. Acta mathematica, 115:271-310, 1966.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In COLT, 2020.
Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint arXi::2102.06333, 2021.
Yu-Guan Hsich, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. NeurIPS, 2020.
Feihu Huang. Adaptive federated minimax optimization with lower complexities. arXiv preprint arXiv:2211.07303. 2022.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. NeurIPS, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In ICML,, 2020.
11

---

Published as a conference paper at ICLR 2024
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. International Conference on Artificial Intelligence and Statistics, pp- 4519-4529. PMLR, 2020a.
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint 1xXi::200611173: 2020b.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. ICML,, 2020.
Anastasiaa Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for decentralized machine learning. NeurlPS, 2021.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.0253: 2016.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concav minimax problems, In ICML, 2020.
Yue Liu, Tao Lin, Anastasia Koloskova, and Sebastian Stich. Decentralized gradient tracking with local steps. arXiv preprint arXiv:2301.01313 2023.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochas- tic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In NeurIPS, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. ICLR, 2018.
Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced proxskip: Algorithm, theory and application to federated learning. NeurlPS, 2022.
Brendan Mc.Mahnn, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efficeenn learning deep networks from decentralized data. In AISTATS, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In ICML, 2018.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In /CML, 2022.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, pp. 1497-1507. PMLR, 2020a.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of ((1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-3251 2020b.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. NeurIPS, 2016.
Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2577-233, 2017.
Arkadi Nemirovski. Mini-course on convex programming algorithms. Lecture notes, 2013.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and trends@ in Optimization, (3):127-239, 2014.
12

---

Published as a conference paper at ICLR 2024
Francesca Parise and Asuman Ozdaglar. A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis. Games and Economic Behavior, 1 114: 47-82, 2019.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. Journal of machine learning research, 12(0ct):2825-288)) 2011.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained nonconvex-nooncoccve minimax problems. arXiv preprint 1.Xx:22302.08831 2023a.
Thomas Michaelsen Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, and Volkan Cevher. Solving stochastic weak minty variational inequalities without increasing batch size. In ICLR, 2023b.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica: Journal of the Econometric Society, pp. 220-534, 1965.
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney, Federated minimax optimization: Improved convergence analyses and algorithms. In /CML, 2022.
Sebastian Stich. Local SGD converges fast and communicates little. In ICLR, 2018.
Zhenyu Sun and Ermin Wei. A communicationn-eficieen algorithm with linear convergence for federated minimax learning. arXiv preprint wwx.iv2226601133 2022.
Davoud Ataee Tarzanagh, Mingehen Li, Christos Thrampoulidis, and Samet Oymak. FedNest: Federated bilevel, minimax, and compositional optimization. In ICML, 2022.
Kiran K Thekumparampil, Niao He, and Sewoong Oh. Lifted primal-dual method for bilinearly coupled smooth minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp. 4281 4400. PMLR, 2022.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior; 2nd rev. Princeton university press, 1947.
Jianyu Wang. Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, al. field guide federated optimization. arXiv preprint arXiv:2107.06917. 2021.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. local SGD better than minibatch sgd? ICML, 2020.
Haibo Yang, Zhuqing Liu, Xin Zhang, and Jia Liu. Sagda: Achieving O(e communication complexity in federated min-max learning. NeurIPS, 2022a.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of monconvex-nonconeee minimax problems. NeurIPS, 2020a.
Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. In NeurlPS, 2020b.
Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for mini- optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pp. 5485-5517. PMLR, 2022b.
Peng Yi and Lacra Pavel. A distributed primal- algorithm for computation of generalized nash equilibria with shared affine coupling constraints via operator splitting methods, arXiv preprint arXiv: 053888 2017.
13

---

Published as a conference paper at ICLR 2024
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021a.
Siqi Zhang, Junchi Yang. Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of boncconvex-ttrongly-coocee minimax optimization. In Uncertainty in Artificial Intelligence, pp. 482-492. PMLR, 2021b.
Xuan Zhang, Needet Serhat Aybat, and Mert Gürbüzbalaban. Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems. NeurIPS, 2022.
14

---

Published as a conference paper at ICLR 2024
Supplementary Material
The Supplementary Material is organized as follows:
Section A reviews the existing literature related work. Section B summarizes the notational conventions used in the main paper and appendix, while Section C includes the missing pseudocodes of the main paper (related variance reduced methods). Next, Sections D and present some basic lemmas to prove our main convergence results. We present the proofs of the main theorems and corollaries in Section Finally, in section we add further details related to our experiments the main paper, while in section H, we add more related experiments to verify our theory.
CONTENTS
1 Introduction
1.1 Main Contributions
Technical Preliminaries
2.1
Regularized VIP and Consensus Reformulation
2.2 Main Assumptions
3 General Framework: ProxSkip-VIP
3.1
Convergence of ProxSkip-VIP
3.2 Special Cases of General Analysis
Application of ProxSkip to Federated Learning
Numerical Experiments
Further Related Work
16
Notations
18
Further Pseudocodes
19
Useful Lemmas
20
Proofs Lemmas 3.4 and 3.8
Proofs of Main Convergence Results
22
F.I Proof of Theorem 3.1
22
F.2 Proof of Corollary 3.2
24
F3 Properties of Operators in VIPs
24
F.4 Properties of Operators in Finite-Sum VIPs
26
F5 Further Comparison of Communication Complexities
26
G Details Numerical Experiments
28
15

---

Published as a conference paper at ICLR 2024
G.1 Details on Robust least squares
28
H Additional Experiments
30
H.1 Fine-Tuned Stepsize
30
H.2 ProxSkip-VIP VIP-FL vs. ProxSkip-L-VRRGDAA
30
H.3 Low vs High Heterogeneity
H.4 Performance on Data with Varying Heterogeneity
32
H.5 Extra Experiment: Policemen Burglar Problem
32
A FURTHER RELATED WORK
The references necessary to motivate our work and connect it to the most relevant literature are included in the appropriate sections of the main body of the paper. In this section, we present broader view of the literature, including more details on closely related work and more references to papers that are not directly related our main results.
Federated Learning. One of the most popular characteristics of communication--fficiee FL. algorithms is local updates, where each client/node of the network takes multiple steps of the chosen optimization algorithm locally between the communication rounds. Many algorithms with local updates (e.g., FedAvg, Local GD, Local SGD, etc.) have been proposed and extensively analyzed FL literature under various settings, including convex and nonconvex problems (McMahan et al., 2017; Stich, 2018; Assran al., 2019; Kairouz et al., 2021; Wang et al., 2021; Karimireddy et al., 2020; Woodworth et al., 2020; Koloskova et al., 2020). local FL algorithms, a big source of variance in the convergence guarantees stems from infer-client differences (heterogeneous data). On that end, inspired by the popular variance reduction methods from optimization literature (e.g.. SVRG (Johnson & Zhang, 2013) or SAGA (Defazio et al., 2014)), researchers start investigating variance reduction mechanisms to handle the variance related to heterogencous env (c.g. FedSVRG (Konečný al., 2016)), resulting in the popular SCAFFOLD algrrihm(KKariiired) et al., 2020). Gradient tracking (Di Lorenzo & Scutari, 2016; Nedic et al., 2017) is another class of methods affected by bata-heterogeneity, but its provable communication complexity scales linearly in the condition number (Koloskova et al., 2021; Alghunaim & Yuan, 2023), even when combined with local steps (Liu et al., 2023). Finally, Mishchenko et al. (2022) proposed a new algorithm (ProxSkip) for federated minimization problems that guarantees acceleration of communication complexity under heterogeneous data. As we mentioned in Section 1.1, the framework of our paper includes the algorithm and convergence results of Mishchenko et al. (2022) as special case, and it could be seen as an extension of these ideas the distributed variational inequality setting.
Minimax Optimization and Variational Inequality Problems. Minimax optimization, and more
generally, variational inequality problems (VIPs) (Hartman & Stampacchia, 1966; Facchinei & Pang. 2003) appear in various research areas, including but not limited to online learning (Cesa-Bi Bianchi & Lugosi, 2006), game theory (Von Neumann & Morgenstern, 1947). machine learning (Goodfellow et al., 2014) and social and economic practices (Facchinei & Pang. 2003; Parise & Ozdaglar, 2019). The gradient descent-ascent (GDA) method is one of the most popular algorithms for solving minimax problems. However, GDA fails to converge for convex-concave minimax problems (Mescheder et al., 2018) or bilinear games (Gidel al., 2019). To avoid these issues, Korpelevich (1976) introduced the extragradient method (EG), while Popov (1980) proposed the optimistic gradient method (OG). Recently, there has been a surge developments for improving the extra gradient methods for better convergence guarantees. For example, Mokhtari et al. (2020b;a) studied optimistic and extragradient the proximal point method to solve bilinear games, while Hsich
methods as an approximation al. (2020) focused on the stochastic setting and proposed the use of larger extrapolation step size compared to update step size to prove convergence under error-bound conditions.
Beyond the convex-concave setting, most machine learning applications expressed as min-max optimization problems involve nonconvex nonconcave objective functions. Recently, Daskalakis al. (2021) showed that finding local solutions is intractable in the nonconvex-monconcave regime,
noncomvex-moccomcave
16

---

Published as a conference paper at ICLR 2024
which motivates researchers look for additional structures on problems that can be exploited to prove the convergence of the algorithms. For example, Loizou et al. (2021) provided convergence guarantees of stochastic GDA under expected co-coercivity, while Yang et al. (2020a) studied the convergence stochastic alternating GDA under the PL.PPI condition. Lin et al. (2020) showed that solving nonconvex-(strongly -concvvv minimax problems using GDA by appropriately maintaining the primal and dual stepsize ratio is possible, and several up works improved the computation complexities (Yang al., 2020b; Zhang et al., 2021b; Yang et al., 2022b: Zhang al., 2022). Later Diakonikolas et al. (2021) introduced the notion of the weak minty variational inequality (MVI), which captures a large class of sincoovve-noneonneee
minimax problems. Gorbunov al. (2022b)
provided tight convergence guarantees for solving weak MVI using deterministic extragradient and optimistic gradient methods. However, deterministic algorithms can be computationally expensive, encouraging researchers to look for stochastic algorithms. On this end, Diakonikolas et al. (2021); Pethick et al. (2023a); Böhm (2022) amalyze stochastic extragradient and optimistic gradient methods for solving weak MVI with increasing batch sizes. Recently, Pethick et al. (2023b) used a bias- corrected variant of the extragradient method to solve weak MVI without increasing batch sizes. Lately, variance reduction methods has also proposed for solving min-max optimization problems and VIPs Alacaoglu & Malitsky (2022); Cai et al. (2022). As we mentioned in the main paper, in our work, the proposed convergence guarantees hold for a class of non-monotone problems, i.e., the class of is u--quai--ttoonly monotone and é-star-cocoercive operators (see Assumption 2.1).
Minimax Federated Learning. Going beyond the more classical centralized setting, recent works study the two-player federated minimax problems (Deng & Mahdavi, 2021; Beznosikov et al., 2020; Sun Wei, 2022; Hou et al., 2021; Sharma et al., 2022; Tarzanagh et al., 2022; Huang, 2022; Yang et al., 2022a). For example. Deng & Mahdavi (2021) studied the convergence guarantees of Local SGDA, which is an extension of Local SGD in the minimax setting, under various assumptions; Sharma al. (2022) studied furthered and improved the complexity results of Local SGDA in the nonconvex case; Beznosikov et al. (2020) studied the convergence rate of Local SGD algorithm with extra step (we call it Local Stochastic Extragradient or Local SEG), under the (strongly)- (ttovex-sttooglyy-oonccc
setting. Multi-player games, which, as we mentioned in the main paper, can be formulated special case of the VIP, are well studied in the context of game theory (Rosen, 1965; Cai & Daskalakis, 201 I; Yi & Pavel, 2017; Chen et al., 2023). With our work, by studying the more general distributed VIPs, our proposed federated learning algorithms can also solve multi- palii-player games.
Finally, as we mentioned in the main paper, the algorithmic design of our methods is inspired by the proposed algorithm, ProxSkip of Mishchenko et al. (2022), for solving composite minimization problems. However, we should highlight that since Mishchenko et al. (2022) focuses on solving optimization problems, the function suboptimality [f(=*) [[x*)] is available (a concept that cannot be useful the VIP setting. Thus, the difference the analysis between the two papers begins at deeper conceptual level. In addition, work provides a unified algorithm framework under general estimator setting (Assumption 2.2) in the VIP regime that captures variance-reduced GDA and the convergence guarantees from Beznosikov et al. (2022b) as special case. Compared to existing works on federated minimax optimization (Beznosikov et al., 2020; Deng & Mahdavi, 2021), our analysis provides improved communication complexities and avoids the restrictive (uniform) bounded heterogeneityyvariance assumptions (see discussion in Section 4),
17

---

Published as a conference paper at ICLR 2024
B NOTATIONS
Here we present a summary of the most important notational conventions used throughout the paper.
FL: Federated Learning
VIP: Variational Incquality Problem
E Modulus of star-cocoercivity
E: Modulus of averaged star-cocoercivity
L: Modulus of Lipschitz continuity
Lg: Modulus of expected cocoercivity
μ.: Modulus of (quasi-Jstrong >strong monotonicity
A, B,C, D1, D2 2 0, (0, 1]: Parameters of Assumption 2.2 on the estimator g
K f.2 condition number
[zlest the i-th to j-th coordinates of vector x
[n]: the set (1. ,n}
Rd"; the variable in VIP (1), F(2) = + fi(z), fi Rd - Bdd
x E Rd: the variable in regularized VIP (2), = nd', F(x) & E F((x,).
(2, (nn) Rd, x4 Rd
Rd Rdd Fj Rdd + Rd and F((x,) = (f.:)).(())). ... .., where
[(x))((a++) (I,).
o² 2 ( < to0
A: (uniform) bounded variance of operator estimator
18

---

Published as a conference paper at ICLR 2024
C
FURTHER PSEUDOCODES
Here we present the pseudocodes the algorithms that due to space limitation did not fit into the main paper.
We present the ProxSKip-L-SVRGIA method in Algorithm 3, which can be seen as ProxSkip generalization of the L-SVRGDA algorithm proposed in Beznosikov al. (2022b). For more details, please refer to Section 3.2. Note that the unbiased estimator in this method has the form: gr (x,) F,, (w,) (w)).
Algorithm 3 ProxSkip-L-SVRGIAA
Input: Initial point zo, ha, parameters ", probabilities p, E [0, 1], number of iterations T 1: Set wi = 20. compute F(wo)
2: for all 0, 1.... T do
3: Construct Jr (x)( Fj. F(we), je E [n]
Dt w.p. q
4: Update w1+1
Wt
w.p. 1-q
5:
Te+1 2t - -9gtt l1t)
6:
Flip coin 01, 0, w.p. p. otherwise 0
7:
8, = then
8:
21+1 prox R B241 he)
9:
else
F1++ 3++1
11: end if
12:
h++1 14 2 [1141-111
end for
Output: 2T
Moreover, we present the ProxSkp-L-SVRRDAA-EL algorithm below Algorithm 4. Similar to the relationship between ProxSkip-SGDA and ProxSkip-SGDA-FL here this algorithm is the implementation of the Proxskip-L-VRRGDA method mentioned above FL regime, For more details, please check Section 4 of the main paper.
19

---

Published as a conference paper at ICLR 2024
Algorithm 4 ProxSkip-L-SVRRDAA-FL
Input: Initial points 21,0, ... In,o E TR!"" 7.P E R, initial control variates 11,0, ... An,o = E
Rd iteration number 7
1: Set w1,0 = 2,,0 for every worker i E [n]]
2: for all 0, ..., do
3: Server: Flip two coins 0g and G. where 0r = 1 w.p. and Çe = 1 w.p. q, otherwise O. Send 0,
and &e to all workers
4: for each workers E [n] in parallel do
5:
gi.c = Fije (xi,t)
Pi.. (w.,) + F(wre), where je Unif([m:))
Wi,t if G =1
6:
Update W1,++1 =
Wiit
otherwise
7:
Ti.+1 = Fi,t
7 hs.t)
8:
0; = then
9:
Worker: xf.e+11 = 3i,t+1 he,e. sends d',4 to the server
Server: computes T1,4+1 Di= 2h.41 sends Fi,4 to workers
|/ Communication
11: else
F4.++1 F,,,+1 13: end if
// Otherwise skip communication step
14: h4,+1 h4 + [ 2((+1)
15:
end for
end for
Output: 2T
D USEFUL LEMMAS Lemma D.1 (Young's Inequality).
||a + b12 < 2||a||2 + 2|1611
Lemma D.2. For any optimal solution x" of (2) and any > 0, we have
x² prox - (x))))).
(8)
Lemma D.3 (Firm Nonexpansivity of the Proximal Operator (Beck, 2017)). Let f be proper closed and convex function, then for any H, E Rd we have
xx y. (x) prox (v)) 2 prrxx(()) prox,
(9)
equivalently,
[I (x) - (y proxx(()))| (|ppr//X//////x////////
||prox - (1)) $ | -
(10)
20

---

Published as a conference paper at ICLR 2024
E PROOFS OF LEMMAS 3.4 AND 3.8
As we mentioned in the main paper, the Lemmas 3.4 and 3.8 have been proved Beznosikov et al. (2022b). We include the proofs of these results using our notation for completeness.
Proof of Lemma 3.4. Note that
E flge - F(x 21( 2 19: g(x")l1 + 2E
119(x=))) 2 F(x))]|
S (F(rt) - F(x"), - -x)) 20
where the second inequality uses Assumption 3.3. The statement of Lemma 3.4 is obtained by comparing the above inequality with the expression of Assumption 2.2.
Proof of Lemma 3.8. For the property of gr. it is easy to find that the unbiasedness holds. Then note that
El1g, F1 F) (xx) Fj, + - 21
=
1
[F()))) Fj.(wr) F(ws,) - F(x*)|1
n
2
[a())) F((=")11 + [1F((x)) - F((w)) - (F(x")- F(
2
[F((())) F1(=")|1 + [[(((*) - F(WW)1?
n
s 2x.)(1)) F(x*) (x(")xx+-00 +
2 n [1(((")) Fl(w)))1
2 - F(x"),"(-z") +
here the second inequality comes from the fact that Var(X) < E(X²), and the third inequality comes from Assumption 3.7. Then for the second term above, we have
I0
2
= -((=++1)-F((=")))
1+1
(l)lF((x.)) - F((x"))1² + (1- - (())) F(ax)))))
< <q((F(xt)) F(x*), ",a"),xe -x -x") )+ 1- q Σ (l...))) F((x))1
= - - F(x') (1)-))))))))))
here the second equality applies the definition of w1+1, and the first inequality is implied by As- sumption 3.3. The statement of Lemma 3.8 obtained by comparing the above inequalities with the expressions of Assumption 2.2.
21

---

Published as a conference paper at ICLR 2024
F PROOFS OF MAIN CONVERGENCE RESULTS
F. PROOF OF THEOREM 3.1
Here the proof originates from that of ProxSkip (Mishchenko et al., 2022), while extend it to the variational inequality setting, and combines it with the more general setting on the stochastic oracle.
Proof. Note that following Algorithm
have with probability p:
T++1 = prox R (fet1 - 2h1
h441 = h4 + ppoxx 2 0(t1 - 3/1)) T8(11)
and with probability 1 - pr:
x Tc+1
1/-1 ltt,
and set
V - |x, 2²1
2
11,, F(x*)12 My
p
For simplicity, we denote P(xr)= - prox R
Tz+1 - -1h1)) so we have
E[Vi+1l = {(1R(1)) - -x=12- + (2)
2
Nr + P y ((((x))- - -8+11) - F(07))1
+(1 p) |1se41 - x² x²1 + (2) 11ke - F(at))1) + 21720
= p (1P(a))) - 2²12+ P(ass) - (5e+1 -hn) (r(rr))
+(1 -p) p) (18771 x²112 (2) like - P((T)11) + -M7200+1
next note that x² prox (x p ff(x)) we have
P(x+) - (Be41 - h1) - ? F(x*)
p p
P(at) - -0e+1 Ihx) - prox x - p
(2(0)) - (x" - -F((x')))
p
so by Lemma D.3, we have
B[V++1]
(10) 5
p Tet1
2 hr - x² IF(a') 2
+ (1--)) (1EH1 + (2)
(p) 11,r - r(03))1))
+ +M7700+1
2
|| - 2²112
2
|// - - x²,he- - -FF("))) + 27700211
22p(āct1
p
p
let
W4 Ft 7g(x));
w³ 1 - F((())
so we have
|7+41 1/ 2 pl - th, - -F(x"))
||w, w² + 7(14 F(x² 2 22(wu= - w² + +r(h-- - F(x*)), F(x*)) -FF(")))
|lw-- w= 11 ?? 22²
= ||w, w/ 1|2 - p²
2 11/ - F(x*)11
p
22

---

Published as a conference paper at ICLR 2024
so we have
(2) 1) 11k -/h")( + My
2
B[ S || - w w=2 + (1 r²)
(II)
Then by the standard analysis on GDA, we have
|wu, - "= = || x² -((((=)) - F(
||aee 1="11=222 -2((((E))) F( + - F(x")|??
take the expectation, by Assumption 2.2, we have
E | - w [1] = |20 -
- F(x"((())))))))) ( - F F 112
|30 1=1 - 22 < [o, + Di),
substitute the above result into (11), we have
(
E l w² w²11+ - -1- (2) 114 F(x)))] + 0 3
B[V++1]
< B ||:0 x² 12 -1 - (x) ((x'),x=x")) + 72 (Bo + Di)
(1 - p²) ? 11 2( + M
|100 x² 27(1 - 7(A
-F("", + M1 - pp)o
+2²( + D1 +D2) + (11-p²) (2)
2
|1 -F(x))
<
E (1 27/411 - ((A+ MC))]][a- - 201 + (1- - p²)
2 like F(x")12
+M?² (
B M
0 + (D, (M.))
here the third inequality comes from Assumption 2.2 on - and the fourth inequality comes from quasi-strong monotonicity in Assumption 2.1. Recall that y S 2CA+ we have
E[V++1]
< E (1 --]ll( - x²1 -x* (1-1)) (3) 11, F(+*)1++ (1 (1-0+
B M
M7 + 7D) + MD2)
< E (1 min
B M } )))r}
TH,, pp P
v. + + + MD2).
by taking the full expectation and telescoping, have
B
E[Vr]
min
"
E
+ MD2)
M
B
T-1
B
min
?H,,p2
Vo
+7
+ MD2)
Σ
1 min
,0
M
M
1=0
B
})
T
72(1, + MMD2)
<
min pu, P-
Vo + min {nu,p2 M
M
the last inequality comes from the computation of a geometric series. which concludes the proof. Note that here implicitly require that < 1 and M
> B p
p
23

---

Published as a conference paper at ICLR 2024
F.2 PROOF OF COROLLARY 3.2
Proof. With the above setting, we know that
min >u. p- M
-/4,
and
Di D2
[| (1-714) Vo+ +
so it is easy that by setting
2V
μuE
T Z In
S
7/
2
D1 2B D2 p
we have
E[VT] S E,
which induces the iteration complexity be
2(A 2(A++BCCp)) 2 2 Di + 2B D2
21
2 max
"
In
1
p
12c
and the corresponding number of calls to the proximal oracle is
2(D: 2B D2)
2(A+ 2BC/p)
2
2Vo In
pT: 2
max 1,
p
12ee
e
which concludes the proof.
F.3 PROPERTIES OF OPERATORS IN VIPS
To make sure that the consensus form Problem (2) fits with Assumption 2.1, and the corresponding operator estimators satisfies Assumption 2.2, we provide the following results.
Proposition F.1. If Problem (1) attains an unique solution 2² E Rdd,, then Problem (2) attains unique solution x² A (2",2",... ........ 2²) E Rdd, and vice versa.
Proof. Note that each Ji is j-quasii-strongl monotone and xt is the unique solution to Problem (1). So for the operator F in the reformulation (2), first we check the point x" = (z 2 ",,,"" ,2"), note that for any 22, ,nn E Rdd we have
(F(x*), - x²) + R(x) R(x*)
Σ F(xz), ), x===)
x² + +R(x)
= Σ (F((x"), xxx="")=)=))) R(x)
Σ (((("),=;=-
R(x).
here the first equation incurs the definition of R, the third equation is due to the definition that F;-
Then for any x E Rdd if x; + x, for some i, E [n),, we have R(x) = +00, so the RHS above is always positive. Then if .1 D2
Fn = x' E Rdd" we have
Σ (f((*)) - 2²) R(x) = Σ (fi(z)), -2) = Σ f((z)) - - 20
24

---

Published as a conference paper at ICLR 2024
where the last inequality comes from the fact that 2" is the solution to Problem (1). So x² is the solution to Problem (2). It is easy to show its uniqueness by contradiction and the uniqueness of s*, which we do not detail here.
On the opposite side, first it is easy to see that the solution to (2) must come with the form x² (2" ,", ,2",, then we have for any (01, 02, 1.: ..n) E Rd
(F(x"), x x²) + R(z) R(x") = Σ (f(())) 2") + R(x),
then select (z', x², xx) for any I' E Rdd, have
(F(x"), x²) + R(x) R(x*)
- -2") 20) 0,
i=1
which corresponds the solution of (1), and concludes the proof.
Proposition F.2. With Assumption 4.1, the Problem (2) attains an unique solution (z", =²) E RRd, the operator F u-quasi-strongly monotone, and the operator g(x) (g)( 92 (2)), ... .9n (z,,) is an unbiased estimator of F, and it satisfies Lg -xxpectedd cocoer- civity defined in Assumption 2.2.
Proof. The uniqueness result comes from the above proposition. Then note that
(F(x) - F(x"), x²)
Σ (Fi(x) FF(x*)) )),²))) x¹'
Σ (B(x) - Fe(x"), ) x0 xxx)
Σ (f(()))) (2="),-=-1
Σ pl|2; 20
A|a 11
which verifies the second statement. For the last statement, following the definition of the estimator g.
[9 (91())) 92(=")
[1(2")
f2(2*)
a
Bg(x")=1 = TF.
Σ Fl(x*) F(x*),
9n (2*))
fn()*)
which implies that it an unbiased estimator of F. Then note that for any x E IRd,
El[g(=) 0(x")11
E
(a(()))) 9((")))1?
(x) 91(2")1
< (f((x.) ff(22), x2 - -²*)
Lg Σ (P((x)) F((x))) xxx==")''
(F(x)) F(x"), x²);
here the inequality comes from the expected cocoercivity of each 9; in Assumption 4.1, which concludes the proof.
25

---

Published as a conference paper at ICLR 2024
F,4 PROPERTIES OF OPERATORS IN FINITE- SUM VIPS Proposition F.3. With Assumption 4.3, the problem defined above attains an unique solution
x - (2', ,²²) E Rd, the operator F d-quasi-stronge monotone, and the operator 9t (91.1, 92,1, 92,0,' I9n.)) satisfies Assumption 2.2 with
a
A= B = 2, C= ol
2 p= q, D1 = D2 = 0, of
[aa((²) - (w,,W)
j=1
Proof. Here the proof is similar to that of Lemma 3.8. The conclusions on the solution x² and the quasi-strong monotonicity follow the same argument in the proof of Proposition F.2. For the property of gt, it is easy find that the unbiasedness holds. Then note that
E E F(x")1
Eligat F((x")1??
Fi., (x1,,) Fi.,(Wa,)) + F((wis.) F??
=
mi - - - F((us))) - F((
mi
10
2 m
(P.() - Fa,(=)) [P(g(2)) - F.s(wre)) (F((==)+=++ -((="")-F((ws.))f
mi
n
(F,)) Fas(2")) - Fus(W))))
M4 j=1
<
26
(fi(1e.)) -f((2), -1)))==)) +
[Fi((*)) - (war))
m
1=1
i=1
Σ (F.()).))) - F;(=), +
Fes(=")
(w,,
m
(("))))-(("), 20,,
the second inequality comes from the fact that Var(X) < E(x)), and the third inequality is implied
by Assumption 4.3. Then for the second term above, we have
E [o
Σ
2
1
Σ
m.
(F))("))1
=
m
i=1
j=1
(11))(()))) -i,(( (1)) (1 ())lFi - B=,(("))12)
Σ of f(((,)) f( ),
(2"), 24,1 - =²) + (1 - 9) Σ m
F. (wy())))) (2)(2")11
F(x) = - 2") -1-
here the second equality comes from the definition w1,+1 and the inequality comes from Assump- tion 4.3. So we conclude the proof.
F.5 FURTHER COMPARISON OF COMMUNICATION COMPLEXITIES
In Table 2, following the discussion ("Comparison with Literature") in Section 4, we compare our convergence results to closely related works stochastic local training methods. The Table shows the
26

---

Published as a conference paper at ICLR 2024
improvement in terms of communication and iteration complexities of our proposed ProxSkip-VIII VIP-FL algorithms over methods like Local SGDA (Deng & Mahdavi, 2021), Local SEG (Beznosikov et al., 2020) and FedAvg-S (Hou et al., 2021).
Table 2:
Comparison of federated learning algorithms for solving VIPs with strongly monotone and Lipschitz operator. Comparison is in terms of both iteration and communication complexities.
Algorithm
Setting'
Communication
Iteration
Local SGDA
n2o0 pe
k2o Jane
SM, LS
(Deng & Mahdavi, 2021)
Local SEG
SM, LS
o max
In 1. Pa?
.e pvee mive
o mmxx
= In 2
A2 p
NA p./Pe
(Beznosikov et al., 2020)
p
pave
FedAvg-S (Hou al., 2021)
SM, LS
pA Ô
vPKA pive
+ me
A² O
+
KE pANt
ProxSkip-VIP-FI
SM, LS*
o | |mxxx
o3 {N2, 1
In I
o |max
of {n²?
(This work)
ProSSiipL-SVRRA--FL
SM, LS
(x
O In
(This work)'
SM: strongly monotone, LS: (Lipschitz) smooth. - L/pa, and a are the modulus of LS. o < +oc is an upper bound of the variance of the stochastic operator at x². A is an (uniform) upper bound of the variance of the stochastic operator. ç² represents the bounded heterogeneity, i.c., ge(2; E.) is an unbiased estimator of fz) for any
i E (1,...,,7) n and 5 (ax) & supaeRd (lf((x) F(x)1 < g² S +00.
2 p the probability of synchronization,
take p O(Vi), which recovers O(1/V)) communication complexity dependence in our result. Ō(-) hides the logarithmic terms.
Our algorithm works for quasi-strongly monotone and star-cocoereive operators, which is more general than the SM and (Loizou et al., 2021).
LS setting, note that an L-LS and SM operator can be shown to be (#LL)-sta
4 When we further consider the finite-sum form problems, we turn this algorithm.
27

---

Published as a conference paper at ICLR 2024
G DETAILS ON NUMERICAL EXPERIMENTS
In experiments, we examine the performance of ProxSkip-VIP-PP and ProxSkipL-SVRRDDAFE We compare ProxSkip-VIPP VIP-FL and ProxSkip-L-SVRGDA-- algorithm with Local SGDA (Deng & Mahdavi, 2021) and Local SEG (Beznosikov et al., 2020), and the parameters are chosen according to corresponding theoretical convergence guarantees. Given any function f(11, the co-coercivity parameter of the operator
V sn (21, n2 (2))
is given by & minx)) R (+) (Loizou et al., 2021). Here, Sp denotes spectrum of the Jacobian matrix
V2 (
J
21.72
82.02
In our experiment, for the min-max problem of the form
min max
1
Σ
f(g(11,22,
(12)
==1
use stepsizes according to the following Table.
Algorithm
Stepsize 7
Value of
ProxSkip-VIP-FL
= VTH
(deterministic)
2 maxxee(H) &
ProxSkip-VIP-FL
(stochastic)
7 maxe, faj
p VTH
ProXSip-L-SVRRGDA-ELL
(finite-sum)
7 max4, Eag
p = vTu
Table 3: Parameter settings for each algorithm. Here & is the co-coercivity parameter corre- sponding m:
m. 121 x22) and lig the co-coercivity parameter corresponding fiy-
The parameters Table are selected based on our theoretical convergence guarantees, presented in the main paper. In particular, for Prox-Sip-VIP--L, VIP-FL, we use the stepsizes suggested in Theorem 4.2, which follows the setting of Corollary 3.5. Note that the full-batch estimator (deterministic setting) of (12) satisfies Assumption 4.1 when Lg maxie &, Similarly, the stochastic estimators of (12) satisfies Assumption 4.1 with Lg = max;,; Lij. For the variance reduced method, ProxSkip- the stepsizes
suggested in Theorem 4.4 (which follows the setting in Corollary 3.9) with è = max;,j lij for (12). For all methods, the probability of making the proximal update (communication in the FL regime) equals = v7H. For the ProxSkip---VVRGDA following Corollary 3.9 we set 2yp.
L-SVRGD--FL,
G.1 DETAILS ON ROBUST LEAST SQUARES
The objective function of Robust Least Square is given by
G(3,v) = ||3 vll - Ally - 12,
for A > O. Note that
V 3 AA =((
Therefore, for
1, the objective function G strongly monotone with parameter min AA), 2(A - 1)}. Moreover, G can be written as a finite sum problem, similar to (5), by decomposing the rows of matrix A i.e.
G(B,y) = > (A. y1)² A(y yos)
1=1
28

---

Published as a conference paper at ICLR 2024
Here AT denotes the ith row of the matrix A. Now divide the rows among nodes where each node will have m = =/nn rows. Then we use the canonical basis vectors e, (vector with i-th entry 1 and 0 for other coordinates) to rewrite the above problem as follow
A Al1-))4153 V(i U(i-1)m+s) 2 - A (1(i- Vo((i- 1)m++))
G( = ΣΣ
i=1
B A A(i-1)m+ (1-1)) - 2y 2y( 1) 1
3 + & Vii-l)m
X)((-1)m+t
ABo((i-1)mt)) + 2Ayoo(i-
BT
(A6-1))mt)44--11) 3 -- vn
(i)-)--))s))))))))))))))) B
V" (A-
y () y
W0(((s-1)m+)
B (A(- 3 --y² v² ( Afr 3
m
-y
(A - 1) y + ( (2 y
1)0(((-1)++)))"
2
Therefore G is equivalent (5) with nodes, my m 1/n, 21 =3, 22 and fiy(11 (111 x2) 21 [As--))++ A 12m+s) 81 1h (20 ((6-))A((11)))) xn
(1 us + (( (mmm))) D2 - (A-- -
-886((-11)m+)))
In Figure 2, we run our experiment on the "California Housing" dataset from scikit-learn package (Pedregosa et al., 2011). This data consists of 8 attributes of 200 houses in the California region where the target variable Yo is the price of the house. To implement the algorithms, we divide the data matrix A among 20 nodes, each node having an equal number of rows of A. Similar to the last example, here we also choose our ProxSkip-VIP-I VIP-FF. algorithm, Local SGDA, and Local SEG for comparison in the experiment, also we use = 50, and the thcoretical stepsize choice is similar to the previous experiment.
In Figure 3, we reevaluate the performance of ProxSkip on the Robust Least Square problem with synthetic data. For generating the synthetic dataset, we set 200 and 20. Then sample ~ (O, 1), 3u N00, 0.1), (0, 0.01) and set yo = A, + e. In both deterministic (Figure 3a) and stochastic (Figure 3b) setting, ProxSkip outperforms Local GDA and Local EG.
ProxSkkp GDA EG
SProxSkip
SEG
100
10
Relative Error
Relative Error
13-4
10-
Local EG
Local SGDA SProcškie Local SBG
Local CDA
13-4
ProaSkip
10-1
50
100
150
200
250
300
350
400
50
100 130
200
250
300
330
400
Number of Communication Rounds
Number of Communication Rounds
(a) Deterministic Algorithms
(b) Stochastic Algorithms
Figure 3: Comparison of algorithms the Robust Least Square (6) using synthetic dataset.
29

---

Published as a conference paper at ICLR 2024
H ADDITIONAL EXPERIMENTS
Following the experiments presented in the main paper, we further evaluate the performance of the proposed methods in different settings (problems and stepsize selections).
H.1 FINE-TUNED STEPSIZE
In Figure 4, we compare the performance of ProxSkip against that of Local GDA and Lo- cal EG on the strongly monotone quadratic game (5) with heterogeneous data using tuned stepsizes. For tuning the stepsizes, we did a grid search on the set FI where r (1,2, 8, 16, 64, 128, 256, 512, 1024, 2048] and L is the Lipschitz constant of F. ProxSkip outper- forms the other two methods in the deterministic setting while it has a comparable performance in the stochastic setting.
ProxSkip vs
SProxSkip Local SGDA Local SEG
10a
10-4
Preee
Relative Error
30.9
Relveive Error
20:91
00:97
10
10-11
10 29
100
200
300
402
100
130 200
Number of Communication Rounds
Number of Communication Rounds
(a) Deterministic Setting.
Stochastic Setting.
Figure 4: Comparison of ProxSkip-VIP-FL. vs Local SGDA vs Local SEG on Heterogeneous Data with tuned stepsizes.
H.2 PROXSKIP-VIP VL vs. PROXSKIP-L-VVRGDA.R
In Figure 5, we compare the stochastic version of ProxSkip- VIP-FL. with ProxSkip--SVRRGIAA FL. In Figure 5a, we implement the methods with tuned stepsizes while in Figure 5b we use the theoretical stepsizes. For the theoretical stepsizes ProxSkip-L-VVRGDAA from Corollary 3.9. We observe that PooxSkipL-SVRRDA-FL performs better than ProxSkip-VIP. with both tuned and theoretical stepsizes.
we use the stepsizes
Proxkkie L SVRGEA
10-2
SProodlap
Relative Error
Relative Error
20.
30-4
10.
30-11
10:44
10-1
10-17
ProsScip SVEGDA
ProkSilp
13
25
30
40
20
40
60
8u
100
Number of Communication Rounds
Number of Communication Rounds
(a) Tuned stepsize
(b) Theoretical stepsize
Figure 5: Comparison of ProxSkip-VIPP and ProxSkip-L-SVRGDAAFE using the tuned and theoretical stepsizes.
30

---

Published as a conference paper at ICLR 2024
H.3 Low vs HIGH HETEROGENEITY
We conduct numerical experiment toy example verify the efficiency of our proposed
algorithm. Following the setting in (Tarzanagh et al., 2022), we consider the minimax objective function
1
" Σ 22)
min max = ER R2CRd YL
where fi are given by
1 2
A
(2(11
|=2||
- -b,'x0 + +x1 A +
2 |=|||
Here we set the number of clients N(0 sf ( and A; I, xdy. For Figure 6a, we set 8; = 10 and 4 = for all i while in Figure 6b, we generate 8; Unif(0, 20) and f; ~ Unif(0, 1).
100, d1 = d2 = 20 and x = 0.1. We generate b ~
We implement Local GDA, Local EG, and ProxSkip- -L. with tuned stepsizes (we use grid search to tune stepsizes Appendix G). In Figure 6c, we observe that Local EG performs better than ProxSkip-VIP.. VIP-FL in homogeneous data. However, in Figure 6d, the performance of Local GDA (Deng & Mahdavi, 2021) and Local EG deteriorates for heterogeneous data, and ProxSkip- MAAASii--II--FEE VIP-FL outperforms both of them in this case. To get stochastic estimates, we add Gaussian noise (Beznosikov et al., 2022a) (details in Appendix G). We repeat this experiment in the stochastic settings in Figure 6c and 6d. We observe that ProxSkip- ProxSkip-VIP-FL. VIP-FL. has a comparable performance with Local SGDA (Deng & Mahdavi, 2021) and Local SEG in homogeneous data. However, ProxSkip-VIP-FF is faster on heterogeneous data.
ProxSkip vs
ProxSkip vs Local GDA vs Local
10-1
Local GDA
10a
Local tt:
10-1
ProxSkip
Relative Error
Relative Error
10-33
10:1
10:
10-11
10
10
ProxSopp
EG
Number Communication Rounds
Number Communication Rounds
(a) constant s;, 4
(b) uniformly generated 8i,
ProxSkip Loc al SCDA Local SEG
ProxSkip vs Local SGDA vs Local SEG
10a
10a
Local
Proo54to
Prooitipp
Relative Error
10-1
Relative Error
10-1
30-1
10-4
10-1
Number of Communication Rounds
Number of Communication Rounds
(c) constant s;, fx
(d) uniformly generated st,
Figure 6: Comparison of ProxSkip-VIP.. VIP-FL vs Local GDA vs Local EG on Homogeneous vy Heterogeneous Data. In (a) and (b), we run the deterministic algorithmss, while in (e) and (d), we run the stochustic versions. 10, f. = 1 for all [n) and for (b) and (d), generate 8,, uniformly from Unif(O, 20), Unif(0, 1).
For (a) and (c), we
31

---

Published as a conference paper at ICLR 2024
H.4 PERFORMANCE ON DATA WITH VARYING HETEROGENEITY
In this experiment, we consider the operator given by
F(x) = 21)))(() + + P2(x)
where
(1) M(x ri), F2(x) = M(x x
with M IR2x2 and 27. 22 R². For this experiment we choose
M = 12. xj (), 2 = 60,
Note that, in this case, x² 2 (Λf x5). Then the quantity max [I F(x")1?, which quantifies the amount of heterogeneity in the model, is equal to 8 Therefore, increasing the value of increases the amount of heterogeneity in the data across the elients.
We compare the performances of ProxSkip-VIPad VIP-FL, Local GDA, and Local EG when d = 0 and 5 10 in Figure In either case, ProxSkip-VIP-FL. outperforms the other two methods with the theoretical stepsizes.
ProxSkip vs Loral GDA vs Local EG
ProxSkip Local GDA vs Local EG
109
10-
10-4
Relative Error
Relative Error
10a2
10a4
10-4
10-1
1.
10-19
10a
Local EG
10:54
10:9
Communication Rounds
Number of Communication Rounds
(a) 8 = 0
(b) 10
Figure 7: Comparison of ProxSkip-VIP-PP Local GDA and Local EG with theoretical stepxizes for 6 = (left) and 5 10t (right).
H.S EXTRA EXPERIMENT: POLICEMEN BURGLAR PROBLEM
In this experiment, we compare the perforamnce of ProxSkip-GDA-EF Local GDA and Local EG on Policemen Burglar Problem (Nemirovski, 2013) (a particular example of matrix game) of the form:
min max ((11, = T2 Te agEd
Σ x A
where A fa Rd 1Tx 1, 2 0) is a (d 1) dimensional standard simplex. We generate the (r, s) element of the matrix A, as follow
A,(r, 8) = wy (1 exp { - s{})
Vi E [n]
where w, |w//| with w/ ~ N/ 1). This matrix game is constrained monotone problem and we use duality gap to measure the performance of the algorithms. Note that the duality gap for the problem mingeA maxyea f(x, y) (b. is defined max,ea f(ā y) min f(x,, 5)-
32

---

Published as a conference paper at ICLR 2024
Policemen Burglar Game
Local EG
16
Local GDA
Prox5kip-GDA-FL
Duality Gap
10-1
1000
2000
3000
4000
5000
Communication Rounds
Figure 8: Comparison of ProxSkip-GDA-HE Local EG and Local GDA Policemen Burglar Problem after
5000 communication rounds.
Figure 8, we plot the duality gap (on the y-axis) with respect to the moving average of the iterates, ie. RTT Ek=o Ty (here 2& the output after many communication rounds). As we can observe in Figure 8, our proposed algorithm ProxSkip-GDA-FL clearly outperforms Local EG and Local GDA in this experiment.
33


Reviews:
[{"review_id": "OljxGGs4W9", "reviewer": "Reviewer_5WaQ", "summary": "This paper provides a unified analysis of algorithms for general regularized VIPs and distributed VIPs. The proposed algorithms improve communication complexity and have strong performance compared to state-of-the-art algorithms. The paper's main contributions include the development of a new communication-efficient algorithm for solving VIPs, theoretical analysis of the algorithm's convergence properties, and experimental results demonstrating the algorithm's effectiveness on a range of problems.", "questions": "1. Theorem 3.1 shows that ProxSkip-VIP converges to the neighborhood of the solution, while the first experiment shows that the proposed variance-reduced method converges to the exact solution. Please add some words to explain it.\n\n2. Is the choice of the probability ($p=\\sqrt{\\gamma\\mu}$) because of the purpose of analysis? What impact will the change of $p$ have on the performance of the proposed algorithms.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The proposed algorithms are inspired by ProxSkip algorithm with a probability and a control variate. As far as I'm concerned, the originality of this paper is not strong, but the strength lies in the framework that recovers state-of-the-art algorithms and their sharp convergence guarantees. \n\nQuality: The paper's theoretical analysis of the proposed algorithm's convergence properties is rigorous and well-supported. The paper's experimental results demonstrate the algorithm's effectiveness on a range of problems.\n\nClarity: The paper is well-written and organized, with clear explanations of the key concepts and results. \n\nSignificance: This paper has the potential to advance the field of distributed/federated learning and have practical implications for solving variational inequality problems in machine learning.", "weaknesses": "1. $prox_{\\gamma R}(v)$ in Equation (4) should be $prox_{\\gamma R}(x)$.\n\n2. This paper does not mention the challenges or difficulties in algorithm design or theorem proofs. More explanations may help to clarify this paper’s originality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1GlXzLVtGz", "reviewer": "Reviewer_bdRp", "summary": "This paper suggests a family of algorithms for decentralized and federated learning settings of problems of solving variational inequalities. This algorithms share the same framework which is based on ProxSkip optimisation method. Concise convergence guarantees are obtained for these methods with general assumptions on problem, and obtained convergence rates expectably improve previously existed algorithms, because achieve acceleration and variance reduction.", "questions": "1) Is usage of colors in Appendix C motivated?\n2) Only strongly-monotone co-coercitive case is considered in the paper. Can authors report on the convergence guarantees in non-strongly-monotone case?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "All the proofs are concise and easy to follow, which is a metodical merit of the paper. Though the improvements achieved are not surprising, the way they were achieved is demonstrative enough.", "weaknesses": "Experiments seem not comprehensive. It would be interesting for authors to consider more complicated variational inequality problems than random quadratic and least squares, for example, particular test matrix games like policeman and burglar problem https://www2.isye.gatech.edu/~nemirovs/BrazilTransparenciesJuly4.pdf, and advanced practical problems like GAN training. Also, figures with comparison of the methods have onlu convergence curves without shadows showing standard deviation of function values from run to run, which is required due to stochasticity of the algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K84eJw0R2J", "reviewer": "Reviewer_5mwf", "summary": "This paper studies minimax optimization and variational inequality problems in a distributed setting. It proposes and analyzes several novel local training algorithms under a single framework for solving a class of structured non-monotone VIPs.", "questions": "1.  minimax optimization is important. But do GAN, adversarial training, robust optimization and multi-agent reinforcement learning tasks match the study in this paper?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The minimax problem covers a variety of crucial tasks within the field of machine learning, and it becomes imperative to investigate minimax problems in a distributed context.\n\n2. It proposes a single framework for solving a class of structured non-monotone VIPs", "weaknesses": "1. The main concern is the motivation behind this paper is not clear. Why do we need to design communication-efficient federated learning algorithms suitable for multi-player game formulations\n\n\n2. The experimental analysis is very limited.\n \n3. The main contributions of this paper are theoretical analysis. It would be better if this paper were submitted to other conferences such as COLT, and AISTAT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kBMPzaCdlK", "reviewer": "Reviewer_HQew", "summary": "This paper studies federated minimax optimization problems. \n\nThe authors proposed Proxskip-GDA and Proskip-L-SVRGDA which generalize the recent advance of Proxskip (Mishchenko et.al 2022) on the minimax (variational inequalities) problems and establish the new state-of-art in terms of communication complexity in both deterministic and stochastic setting.  \n\nHowever, the analysis and design of the proposed methods are very similar to the ones for minization problems, including the deterministic setting (Mishchenko et.al 2022) and the stochastic setting (Malinovsky et.al 2022). The author need to clarify the differences between their methods and the previous Proxskip framework (especially the hardness when generalize these methods from minimization to minimax).", "questions": "Please refer to the weakness part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The convergence rates in this paper are significant. They cover the settings of both stochastic and deterministic and establish the new SOTA.", "weaknesses": "My main concern about this paper is its novelty. The generalization of proxskip framwork (Mishchenko et.al 2022) into minimax optimization seems direct. The variance reduction variant is interesting, but the technique is also similar to the work for minimization problems (Malinovsky et.al 2022).\n\nFor the experimental part, the author should also compare their methods with Sun et.al 2022 which firstly establish the linear rate under similar settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)