A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning
Authors: Zhenyu Sun
Ermin Wei
Venue: NeurIPS 2022 Accept (2022)
Keywords: federated learning
minimax optimization
generalization bound

Abstract: In this paper, we study a large-scale multi-agent minimax optimization problem, which models many interesting applications in statistical learning and game theory, including Generative Adversarial Networks (GANs). The overall objective is a sum of agents' private local objective functions. We focus on the federated setting, where agents can perform local computation and communicate with a central server. Most existing federated minimax algorithms either require communication per iteration or lack performance guarantees with the exception of Local Stochastic Gradient Descent Ascent (SGDA), a multiple-local-update descent ascent algorithm which guarantees convergence under a diminishing stepsize. By analyzing Local SGDA under the ideal condition of no gradient noise, we show that generally it cannot guarantee exact convergence with constant stepsizes and thus suffers from slow rates of convergence. To tackle this issue, we propose FedGDA-GT, an improved Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT). When local objectives are Lipschitz smooth and strongly-convex-strongly-concave, we prove that FedGDA-GT converges linearly with a constant stepsize to global $\epsilon$-approximation solution with $\mathcal{O}(\log (1/\epsilon))$ rounds of communication, which matches the time complexity of centralized GDA method. Then, we analyze the general distributed minimax problem from a statistical aspect, where the overall objective approximates a true population minimax risk by empirical samples. We provide generalization bounds for learning with this objective through Rademacher complexity analysis. Finally, we numerically show that FedGDA-GT outperforms Local SGDA. 

A Communication-effiieenl Algorithm with Linear Convergence for Federated Minimax Learning
Zhenyu Sun
Department of Electrical and Computer Engineering Northwestern University Evanston, IL 60208
zhenyusun20266u. www.:e/ottttwwwwt.c...o
Ermin Wei
Department of Electrical and Computer Engineering
Northwestern University
Evanston, IL 60208
ermin. www..eiwtttrtttteten...mmm edu
Abstract
In this paper, we study a large-scale multi-agent minimax optimization problem, which models many interesting applications statistical learning and game theory, including Generative Adversarial Networks (GANs). The overall objective is a sum agents' private local objective functions. We focus on the federated setting, where agents can perform local computation and communicate with central server. Most existing federated minimax algorithms either require communication per iteration lack performance guarantees with the exception of Local Stochastic Gradient Descent Ascent (SGDA), multiple-local-udaal descent ascent algorithm which guarantees convergence under diminishing stepsize. By analyzing Local SGDA under the ideal condition of no gradient noise, we show that generally it cannot guarantee exact convergence with constant stepsizes and thus suffers from slow rates of convergence. To tackle this issue, we propose FedGDA-GT. improved Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT). When local objectives are Lipschitz smooth and strongly- munee--strongly-coneaa
prove that FedGDA-GT converges linearly with constant stepsize to global e-approximation solution with O (log(1 communication. which matches the time complexity of centralized GDA method. Then, we analyze the general distributed minimax problem from a statistical aspect, where the overall objective approximates true population minimax risk by empirical samples. We provide generalization bounds for learning with this objective through Rademacher complexity analysis. Finally, we numerically show that FedGDA-GT outperforms Local SGDA.
(n/e())))))) /c)) rounds
1 Introduction
In recent years, minimax learning theory has achieved significant success in attaching relevance to many modern machine learning and statistical learning frameworks, including Generative Adversarial Networks (GANs) [TH3], reinforcement learning [4], adversarial training (56)). robust estimation
and optimization [7111] and domain adaptation [3]. Generally, a minimax learning problem is
modeled game between two players with opposite goal, i.e., minimizes the objective while
the other maximizes it.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Most current studies in the field of machine learning are targeted at understanding the minimax problem from the view of the speed of convergence and the accuracy of fixed points. In the centralized setting, gradient descent ascent (GDA), which is an extension of gradient descent (GD), stands out for its simple implementation. Specifically, at each iteration, the "min" player conducts gradient descent over its decision variable while the "max" player performs gradient ascent in contrast. Due to the huge volumn of data, stochastic gradient descent ascent (SGDA) is preferred in machine learning settings. Theoretical guarantees are well-established for GDA and SGDA in [14 [5]. However, in practical scenarios, concerns on computation efficiency and data privacy trigger the development
of federated learning over server-client topology and distributed learning over general graph.
These often require communication with the server or neighbors at each iteration [13 16 17 and
inapplicable to scenarios where communication is expensive.
In this work, we focus on solving a minimax problem in Federated Learning (FI.) setting with one server and multiple client/agents. In FI., the server hands over computation burden to agents, which perform training algorithms on their local data. The local trained models are then reported to the server for aggregation. This process is repeated with periodic communication. Much existing literature in FL, however, focuses on minimization optimization [1-222. The limited literature on federated minimax problems either lacks theoretical guarantees or requires frequent communication
13 23 24), with the exception of Local Stochastic Gradient Descent Ascent (SGDA) (25). In Local SGDA, each agent (or client) performs multiple steps of stochastic gradient descent ascent before communication to the server, which then aggregates local models by averaging. Under careful selection of diminishing learning rates, [25 26 show that Local SGDA converges to the global optimal solution sub-linearly. However, as we show here, when we try to improve the speed of convergence and reduce communication overhead by introducing constant stepsize Local SGDA, it fails to converge to the exact optimal solution, even when full gradients are used. Thus Local SGDA can either be fast(with little cattuuuiiiaiiioobu-ttaaaaaaaaaot communication). To address this tradeoff' between model accuracy and communication efficiency, we develop FedGDA-GT, Federated Gradient Descent Ascent based Gradient Tracking (FedGDA-GT), and show that it can achieve fast linear convergence while preserving accuracy.
or sccurate-but-slowwwee
much
In addition to solving the minimax problem, also study the generalization performance of distributed minimax problems in statistical learning, which measures the influence of sampling on the trained model. In most existing works, generalization analysis is established in the context of empirical risk minimization (ERM) (2). It is well-known that for generic loss functions, the learning error for centralized ERM is on the order of O(1/V with N denoting the total number of training samples. Recently, several works derive generalization bounds on centralized minimax learning problems with the same order [30 For generalization analysis in distributed minimax learning, learning bounds are only provided for specifie scenarios, e.g., agnostic federated learning [13 and multiple-source domain adaptation [12). In this paper, we provide generalization bounds for distributed empirical minimax learning with the same order as results of centralized cases, generalizing the results in [3]
1.1 Related work
Centralized minimax learning Historically, minimax problems have gained attraction of re- searchers since several decades ago. An early instantiation is bilinear minimax problem, which becomes a milestone in game theory together with von Neumann's 's theorem [33]. A simple algorithm is then proposed to solve this bilinear problem efficiently 34
33 generalizes von Neumann's 's
theorem to convex-concave games, which triggers an explosion in algorithmic research [36-38] 38) GDA,
widely used algorithm, is notable for its simple implementation. It is well-known that GDA can achieve an e-approximation solution with (log(1/ee) iterations for atrongly-conved strongly-concave games and with O(e iterations for convex-concave games under diminishing stepsizes 14]. Very recently, nonconvex-noncomee minimax problems appear to be a main focus in optimization and machine learning, due the emergence of GANs. Several related works are listed therein 45
Distributed and federated minimax learning few recent studies are devoted to distributed minimax problems due to the increasing volume of data and concerns on privacy and security. Algorithm design and convergence behaviors are extensively studied for minimax problems in the context of distributed optimization, where communication is required at each iteration 47
2

---

In the federated setting, 48
proposes coultipee-ocal-uppee algorithm to deal with distribution shift issue. [49] studies federated adversarial training under nonconvex-PL objectives. FedGAN is proposed in (50) to train GANs in communication-efficcne way. However, these works are targeted at some specific scenarios. Very recently, aiming to solve the general federated minimax problems, (25) proposes Local SGDA by allowing each agent performing multiple steps of GDA before communication. The authors also prove sub-linear convergence for Local SGDA under diminishing stepsizes. Their convergence guarantees is then improved by (26) to match the results of centralized SGDA (T5). However, we note that all these algorithms require diminishing learning rates to obtain exact solutions, which suffer from relatively slow convergence speed, but algorithm allows constant stepsizes and hence linear convergence can be achieved.
Generalization of minimax learning Recently, generalization properties of minimax learning problems have been widely studied in different scenarios. including GANs and adversarial training. For GANs, [5T] analyzes the generalization performance of GANs when discriminators have restricted approximability. [52] evaluates generalization bounds under different metries. In contrast, (53) suggests a dilemma about GANs' generalization properties. In the context of adversarial training, generalization performances are studied through Rademacher complexity analysis [54[57), function transformation [55], margin- based [56] approaches. (58) studies the generalization bounds of convex- concave objective functions with Lipschitz continuity. However, all these works are under centralized setting. Recently. [13] provides generalization analysis under agnostic federated learning, where the objective is optimized for any target distribution formed by a mixture of agents' distributions. Our work extends their generalization analysis to general distributed minimax learning problems.
1.2 Our Contributions.
We summarize our main contributions follows: (1) In federated setting, characterizing the behavior of fixed points of Local SGDA, which reveals the impact of objective heterogeneity and multiple local updates the model accuracy [see Section 3.1]; (2) Resolving the tradeoff between model accuracy and communication efficiency by developing a linear-rate federated minimax algorithm that guarantees exact convergence [see Section 3.2 (3) Analyzing the generalization properties of
empirical minimax learning in distributed settings through Rademacher complexity analysis [see Section (4) Providing numerical results which suggest communication efficiency of our algorithm compared to Local SGDA and centralized GDA [see Section
Notations. In this paper, we let || denote (z-norm and denote the cardinality of set or a collection, or absolute value of a scalar. Vectors are column vectors by default and = (æ, y) forms the concatenated vector with [x:", ".".v""T. Vectors and scalars for agent are denoted using subscript i, e.g., fa y). Superscripts, e.g., f. denote the indices of iterations. We let the gradient of f(x, y) by Vf(z, y) (V.f(x,)) v). V (x, v)), where fzf y) and V (yf(zz)) z) denote the gradients with respect to x and y, respectively.
2 Problem Setup
In this paper, we consider the general constrained minimax distributed optimization problem collec- tively solved by m agents:
((o.v) v)
1 m - f((z,)) m i=1
min max x DEy'
(I)
where X are some compact feasible sets contained in R2 and R", E X' is p-dimension vector, y E y is a q-dimension vector and fi(,,) -) is the local objective function of agent i, Vi 1. 1.... m.
Solving 1 is equivalent to finding a minimax point of f(,,, v). defined as follows:
Definition 1. The point (x*,y" y²) is said to be minimax point of f(z, y) if [(" ,w) S f("", "u"""")) S max
(xx, Vx E X, e y'Ey"
The first-order necessary condition for minimax points is given by the following lemma. Lemma 1. (59) Assume f is continuously differentiable. Then, any minimax point (x", (1)) in the interior of X x satisfies
Vaf(2" v4)) = vyf(=",v") =0
3

---

3 FedGDA-GT: A linear-rate algorithm for federated minimax learning
In this section, focus on solving ① in the federated setting, where the m agents are connected to a central server. In general, the agents' communication with the server is more expensive than local computation. We show that the existing methods either require lots of communication (i.e. the convergence rate is sublinear) or could only converge to an inexact solution with linear rates. This suggests tradeoff between model accuracy and communication efficiency. Motivated by this phenomenon, we aim at developing a communication-effiene efficient minimax algorithm with linear convergence that preserves model accuracy and low communication overhead simultaneously.
We adopt the following standard assumptions on the problem.
Assumption 1 (j--ttronglyconnvex wttp:/eweetttoolyyooccceeeee For any i 1,..., m1, Se(x, y) is twice- comere/oooooeeeeeooonoooooooo www.r:sssoonoooooororeeeeee with some >> 0 for any (x, y) E RD x R9,
differentiable and is p-strongly conver
i.e.
11 "111= =11² V2, x.
for any given y.
fi(2,9) 2 f((2. (V..i v).
yll? Vz, y- Assumption 2 (L-smoothness). There exists some L > 0 such that for any 1,.... m, [V, Vii('', ,/)|I S L][(x,)) 3) (x',"')l ((, ( y), (r', 5/) E Rp R2.
for any given x,
fi(x, 2) S f(x v) + (V, v). y)
We note that although each [1 y) may have different μ4 and Li we can set = minl;= P4g and L max,=11...m L; to ensure Assumptions and hold.
3.1 Analysis on Local SGDA
We first study Local Stochastic Gradient Descent Ascent (SGDA) proposed in [25). which is the only known method with convergence guarantees and can utilize multiple local computation steps before communicating with the central server for solving general federated minimax problems. In particular, in each iteration of Local SGDA, each agent updates its local model (æ;, y/) for K times by using local stochastic gradients before communication, and then sends its local model to the server, which then computes the average of local models and sends it back.
In [25], the authors prove that under Assumptions T 2 with bounded variance assumption on all local gradients and vanishing learning rate, after T rounds of communication, the convergence result of Local SGDA is
(1~(T) 211 + (ly y" |P] S (TTTT
This shows the slow sublinear convergence rate of this method, which translates to large amount of communication. We next consider an ideal deterministic version of Local SGDA (Algorithm [ where local stochastic gradients are replaced with full gradients.
Algorithm Local SGDA
Input: (z., . as initialization of the server
1: for 1,...... T do
2:
1.0
1+1 = x² Vi,0
[+1
y², Vi = =1 1,...,
3: for k = 0,1,..., K... - do (in parallel for all agents)
4:
141 = =rttl
i
.11
i.k na V + 11
5:
Vi
(+1 Vi.k
++1
+ ny V ( -1(kk)
6: end for
7: g+++1
1 m (+1
- d +
8:
end for
Output: (xT () given by the server
In order to rewrite Local SGDA in concise form, we define the operator for gradient descent evaluated (x. y) for agent as
(=,))) r V Vof((z,)), vi= L,..,,

---

Given some k 2 1, let D define the composition of l. Dj operators, Moreover, (z, v) = x: is the identity operator on the first argument. Let A, (z. 1) = y + 7y V gf y) be the gradient ascent operator with A (z. y) and AQ y) = y defined similarly. Then, given some initial point (a² y/), Algorithm is rewritten as the recursion of the following for t = 0, 1,..,, T:
. D (x' .y) De
A (a' -y
Vi
(3)
==
The following result shows that Local SGDA generally cannot guarantee the convergence to the optimal solution of ① with fixed stepsizes even with full gradients.
.......0 ........" m. For any K2 1, let {(at, yy'} be the sequence generated by (3) (or equivalently by Algorithm D. If (("),"") converges to a fixed point (x" yy), then
Proposition 1. Suppose Ja is difserentiable, Vi 1i=1,....
K-1
(D
= 0.
Note that when = 1, Local SGDA reduces to GDA and the fixed point (x",y") satisfies
m
m
VaJi(t' ,")
Vyfi(o' "1ll"""'''
771
which meets the optimality condition (by Lemma 1 of the minimax point of f(x,, y). For any other K, the fixed point characterization is different from the minimax point. An illustrative example is provided in Appendix C
We mention that while having multiple local gradient steps in the inner loop allows the agents to reduce the frequency of communication, it also pulls the agents towards their local minimax points as opposed to the global one. Motivated by this observation, next propose modification involving gradient correction term, also known as gradient tracking (GT), to make sure the agents are moving towards the global minimax point.
3.2 FedGDA-GT and convergence guarantees
As indicated Section 3.1 Local SGDA cannot guarantee exact convergence under fixed stepsizes, which implies tradeoff between communication efficiency and model accuracy. Aiming at resolving this issue, in this section, we introduce our algorithm FedGDA-GT, formally described in Algorithm 2. that can reach the optimal solution of (1) with fixed stepsizes, full gradients and the following assumption.
Assumption 3. The feasible sets X and y are compact and corvex. Moreover, there is at least one minimax point of f(x, y) lying in X V
(rojx()) and Projy(-) denote the projection operators, i.e.,
Projx = arg min 2EX
||2 æ|| and Projy(u) = arg min ||2 yll-
which well defined by the previous assumption and used to guarantee the output of Algorithm Zis feasible. The main differences between FedGDA-GT GT and Local-SGDA are the correction terms of V='f(x', ; v²) Vaf(x', y²) and -Vyfe(at, ,²)) + Vyf(x', y²), which track the differences between local and global gradients. By including the gradient correction terms, when (Ni, M is not too far from (x*, yy), we can expect (x.f(x v(++) ~ Vafi(z', y²) and similarly for gradients. Hence the updates reduce to simply taking global gradient descent and ascent steps, which coincide with centralized GDA updates and thus would have the correct fixed points. We next show the convergence guarantee of FedGDA-GT.
We first establish the uniqueness of minimax point of f(z, y) by the following lemma.
5

---

Algorithm 2 FedGDA-GT
Input: (x", yy) as initialization of the global model
1: for 0,,1,.... 1,..., do
2: Server broadcasts (x* y²)
3: Agents compute (V (V
V Vufi(r' ,3 3²)) and send it to the server
4: Server computes aVaf ,8 V of(2" y²)) and broadcasts
5:
Each agent for i 1, ...,,., m sets 2,0 = x², vi.0" = =y"
6:
for 0, 1,..., K
(in parallel for all agents)
7:
iik
1+1 17( VV 3 Vafi(z', ,y) + (zf(a',
i,4+1
i.k
8:
Vr,++1
++1
Wi,k
1+1
+ n yi
4+1 wirk) Vyli(u', ,y²) VyJ (x+, (z))
9:
end for
All agents send (ii Ki the server to compute (x'+1, , , by
11:
g++ = Projx
+/ Ei 2 ++1
y
Proiy ( Ei= vi,
end for Output: (x (x²,v²) given by the server
Lemma 2. Under Assumptions
andd (x" -v") is the unique minimax point of f(r,, v) if and only if
vuf(x" y²) V vyf(w* (="xxx"")) v²) = O.
Next, we state the main convergence result of our algorithm.
Theorem 1. Suppose Assumptions
3 are satisfied. Let {(x', .u )i= be a sequence generated by Algorithum 2 Then there exists a scalar Nu > O. such that for any stepsize nj E (0,
| ==2 + lly y' p(n)² (11= 2²11 212 + 11 v" 1²) Vt 0,1.....
where (x" (x") the unique minimax point of [xx, y) and p(n) is some scalar in (0, 1).
Theorem I guarantees linear convergence of FedGDA-GT (Algorithm 2 to the correct optimal solution of ① under suitable choices of stepsize 1/. We note that linear convergence here with respect to the outer-loop (indexed by 1), as the inner-loop (indexed by k) can be implemented cheaply without any communication. The fast convergence speed and exact convergence of this result eliminate the tradeoff between model accuracy and communication efficiency. Furthermore, no restriction on heterogeneity level of local objectives placed. For the homogeneous setting, we show in Appendix (.4 that the convergence rate of FedGDA-GT can be improved at least K times, compared to heterogeneous setting.
4 Generalization bounds on minimax learning problems
In this section, we consider minimax statistical learning, an important application of the minimax framework. We view the problem (I) in Section ass the empirical version of a population minimax optimization problem. We evaluate the generalization performance of the empirical problem using Rademacher complexity.
To more specific, in a minimax statistical learning task, each agent is allocated with some local dataset S {E,;) 1i where & denotes the jth sample of agent and n, denotes the number of local samples. S U St is the dataset with all samples. Moreover, we assume n, vi = 1,... and N = mn is the total number of samples. Then, each local objective function (z, y) is defined by using local data, i.c.
f(x, 1 Σ v:
(4)
where 1(2, y: Ex,)) is the loss function measured at point E.jj and 4 is called local empirical minimax risk. Suppose that for agent i each data sample Či, is independently drawn from some underlying distribution P,, denoted by & P:. We can further define the local population minimax risk as follows:
R2 v) = Ee~P; [1 E)
(5)

---

and similarly, the global population minimax risk is defined by
R(z, y) = B [1 y; E)
(6)
where P is the underlying distribution of the whole dataset S. Then, the minimax problem based on the population minimax risk is given by
min max R(x,2) 3). #EX yey
Sample applications of our formulation
can be found in Appendix A
While we are interested in calculating the population minimax risk, in practice we can only solve (.. which is a sampled version of 7 since the true distribution P is unknown. In this sense, how could expect the optimal solution of (T) performs successfully (6) To answer this question, we provide the generalization bound which measures the performance of the model trained on the empirical minimax risk fx, (). Our generalization bound based on the notion of Rademacher complexity [29] defined by
0 (X v) Eg
sup NEX mn
oL yi End)
where o (oig). Vi l..., m, Vj I,...,, n, is a collection of Rademacher variables taking values from } uniformly. Basically, the Rademacher complexity (8) captures the capability of X' to fit random sign noise, i.e., a. Note that , y: Et.j) measures how well the loss correlates with noise a on sample space S. By taking the supremum, it means what the best extent the feasible average can correlate with random noise a. Thus, if X' is richer, then the Rademacher complexity is bigger. Moreover, the minimax Rademacher complexity is defined on y by
((,,)) = max 3 v).
yEy
Given c > 0, we further define the c-minimum cover of y in la distance by
y = arg min c(),))
(C)))))
where c(),e)= = (B. y E such that for any y E y there exists some By/r/) E C(Y, c) with E (y').. Note that [ < co, since y is compact and thus every open cover of y has finite subcover.
is a collection of open balls (v) centered at with radius
Then, we have the following generalization bound for the distributed minimax learning problem:
Theorem 2. Suppose [1x y: {) - 1(x, E) < T.ylly 55'll and MMx, v) I M(()), Ya E X, Vy. y' Ve and AA P., ...., m. with some positive scalar T.y and real-valued function (1) > 0. Then, given any >> 0 and >> O, with probability at least 1 - for any (x,z) X x X),
Mf(w) 2m2
D 8
R(x, & f(z v) (38
log
+ +LLye.
(10)
Theorem 2 generally states that given any x, y feasible, it is highly possible that the distance between the global population minimax risk R(2, y) and the global empirical minimax risk [(x, y) can be bounded by Rademacher complexity and a term related to the number of agents and local sample size. Moreover, we allow the upper bound of I(:, y) can depend different choices of y and agents since different local distributions always have different effects on the value of ((-, y).
Based on Theorem 2 we further derive the high-probability bound maxyey R(x, v)-
Corollary Under the same conditions of Theorem with probability at least 1 5 for any x E X.
2
the following inequality holds for any >> 0, 8 > 0:
Mf(y) 2m2n
Vel 5
Q(x) S +2 +
max DEy
log
+ 2L
(11)
where Q(x) = max R(x,)) g(x) max (1, v) are the worst-case population and empiri- cal risks, respectively.
7

---

We can further bound (") when the loss function ((2, yi takes finite number of values for any (z. y) X x y and any data samples.
Lemma 3. Suppose for any y E y and i (l,...,my) ... MM yi ) bounded by Mily) and takes finite number of values. Further, assume that the VC-dimension of X is d. Then, the following inequality holds:
Mf(() m2n (1+ log min
2d max yEy
(12)
Corollary measures the error between the worst-case population and empirical risks, that is max R(z,y) y) maXyey f(z, y). A smaller error indicates a better performance of the model, which is trained empirically, generalized know that this worst-case error can be bounded by some decreasing function with respect to sample size. Thus, in order get better generalization performance, one effective way is to draw more local samples for each agent.
the underlying distribution P. Combining Lemma we
It it worth noting that the generalization bound is related to the term Σ i=1 Mf) as shown in (1)--1). which essentially measures the effect of feasible set y by means of different local data distributions on each agent. This also captures the heterogeneity of agents.
In fact, the bounds 10 12
proposed generalized versions of those in [13] which essentially include them as special cases by selecting suitable (y). Specifically, noting that in [3], the global population risk takes the form of R(x, 3) -i=1 R; with yi Z 0 and Σ V/ then by choosing M2(3) my;M with some M > 0 we recover the same result. Moreover, compared (1), where only centralized minimax learning problems are considered, our bounds have the
same order of complexity (I/vVN) with N denoting the total sample size by taking the uniform
bound on ((-) for all agents.
5 Experiments
In this section, we numerically measure the performance of FedGDA-GT compared to Local SGDA with full gradients on personal laptop by solving (T). We consider first perform experiments quadratic objective functions with æ and uncoupled. Then, we test our algorithm on the robust linear regression problem. In both cases, FedGDA-GT performs much better than Local SGDA with heterogeneous local objectives.
5.1 Uncoupled quadratic objective fuunctions
We first consider the following local objective functions:
[i v)
2 = A A 3"" Af Aay + b.) (2r n). Vi= 1f=1..... ,....,,,.
(13)
where x, E Rd and A, E Rd with n; representing the number of samples of agent i. We generate A,, b, as follows:
For each agent, every entry of A,, denoted by [AmRas is generated by Gaussian distribution N/O,, (0.5i)-2). To construct by, we generate random reference point 0 Rd where 0, N(j,, lxxa). Each element of is drawn from from.((a, 1) with a ~ AO,, 100). Then b, = A,0; + with E; [O, 0.254,, xn.). We set the dimension of model as d 50 and number of samples as n, = 500 and train the models with m = 20 agents by Algorithm [ aand Algorithm 2 respectively. In order to compare them, the learning rate 10 for both algorithms and we choose Local SGDA with K = 1, which is equivalent to centralized GDA, as the baseline. Figure [ shows the trajectories of Algorithms
D and under objective functions constructed by [3),, respectively. Different numbers of local updates are selected (with K = 20 and K 50). In this heterogeneous setting, we can see that FedGDA-GT achieves linear convergence, converging to more accurate solution with significantly fewer rounds of communication, compared with Local SGDA and centralized GDA. Moreover, our numerical results suggest that Local SGDA may converge to a non-optimal point (optimality gap over 10'), which conforms with our Theorem
8

---

104
304
100
10"
10P
100
Local SG3A, K
SCDA. K
10
Local 5039, K
FedGB/-S77 20
1019
FeddEX-GT K 50
S0DA. 50
10
102
200
350
403
530
10
100
205
400
502
Communicatio round.c
Communication round
(a) K 20
(b) K 50
Figure 1: Local SGDA and FedGDA-GT with constant stepsizes under different numbers of local
updates
5.2 Robust linear regression
Next, we consider the problem of robust linear regression, which is widely studied in estimation with
gross error 28 57.. As the same formulation in [25]. each agent's loss function is defined by
[(
1 Ths
Iall Vi = 11= 1...., m, (ai. + v) be, 2
(14)
where (ai,) b(.) is the jth data sample of agent i, n, is local sample size. Specifically, in (14). IRd represents the model of linear regression and [d represents the gross noise aimed at contaminating each sample. We assume that there is an upper bound on the noise, i.e., llvll I 1.
By solving min | 1 fe(x, v), obtain global robust model of the linear regression problem even under the worst contamination of gross noise. To measure the convergence of algorithms, we use the robust loss, i.e., given model J. the corresponding robust loss 25 26 is defined by f(t |ax C.
We generate local models and data as follows: the local model x; is generated by a multivariate normal distribution. The output for agent i given by be, = (xf)" a.,, + Ej with ej _N(0, 1). Each input point at,j is with dimension d and drawn from a Gaussian distribution aij ~ "Nu,, K2) where 14 ~ (C;, Taxa) and K; = i-1.3 Taxd- Each element of e is drawn from (N o²). By choosing different a, we control the heterogeneity of local data and hence ft(x, y).
In this experiment, we compare Algorithms and 2 Jnder different heterogeneity levels, i.e., a = 1, 5 and 20. For each case, we choose the same constant 1) for both Local SGDA and FedGDA- GT. As shown in Figure 2] when local agents are more heterogeneous, FedGDA-GT performs better than Local SGDA, which lies not only in faster convergence but also smaller robust loss. Specifically, when & = 1, two algorithms almost have the same performance. To explain this phenomenon, let us recall FedGDA-GT again. Smaller essentially means more similar local objectives. In particular, a = 0 corresponds to i...d. cases. In this sense, the local updates of FedGDA-GT become the same that in Local SGDA, which indicates similar performance shown in Figure 2 a).
Locll SCANA E
Local SUDA K
Local SGUAA
TeOGOA CT. 20
TeoGBA-CT K=
Ted 2T 22
502
12
502
402
60
100
100
(a) a
(b) & =
(C) C 20
Figure 2: Local SGDA and FedGDA-GT under different heterogeneity levels

---

6 Conclusion
In this paper, we investigate the federated minimax learning problem. We first characterize the fixed-point behavior of a recent algorithm Local SGDA to show that it presents a tradeoff between communication efficiency and model accuracy and cannot achieve linear convergence under constant learning rates. To resolve this issue, we propose FedGDA-GT that guarantees exact linear convergence and reaches c-optimality with (loo((//e) time, which is the same as centralized GDA method. Then, study the generalization properties of distributed minimax learning problems. We establish generalization error bounds without strong assumptions on local distributions and loss functions based on Rademacher complexity. The bounds match existing results of centralized minimax learning problems. Finally, we compare FedGDA-Gi with two state-of-the-ar algorithms, Local SGDA and GDA, through numerical experiments and show that FedGDA-GT outperforms in efficiency and/or accuracy.
Acknowledgments and Disclosure of Funding
This work was supported by the NSF NRI 2024774.
References
[1] Ian Goodfellow, Jean Pouget-Abadic Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
[2] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C. Courville. Improved training of Wasserstein GANs. Advances in Neural Information Processing Systems, 30, 2017.
[3] Xudong Mao, Qing Li, Haoran Xie, Raymond Y.K. Lau, Zhen Wang, and Stephen Paul Smolley. Least squares generative adversarial networks. Proceedings of the IEEE International Conference on Computer Vision, pp. 2794-2802, 2017.
[4] Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P How, and John Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. arXiv preprint arXiv:1703 7033 06182, 2017.
[5] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. International Conference on Learning Representations, 2017.
[6] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018
[7] Nam H. Nguyen and Trac D. Tran. Robust lasso with missing and grossly corrupted observations.
IEEE Transactions on Information Theory, 59(4): 2036-2058, 2013.
[8] Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances Neural Information Processing Systems, 29, 2016.
[9] Hongseok Namkoong and John Duchi. Variance-based regularization with convex objectives. Advances in Neural Information Processing Systems, 30, 2017.
[10] Hongseok Namkoong and John C. Duchi. Learning models with uni- form performance via distributionally robust optimization. arXiv preprint arXiv:1810.08750 2018.
[11] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. International Conference on Learning Representations, 2020.
[12] Han Zhao, Shanghang Zhang, Guanhang Wu, José M. F. Moura, Joao P. Costeira, and Geoffrey
J. Gordon. Adversarial multiple source domain adaptation. Advances in Neural Information Processing Systems, 31, 2018.
[13] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. Inter- national Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
10

---

[14] Angelia Nedic and Asuman Ozdaglar. Subgradient methods for saddle-point problems. Journal of Optimization Theory and Applications, pp. 205-228, 2009.
[15] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concaae minimax problems. International Conference on Machine Learning, 119:6083-6033. PMLR, 2020.
[16] Ohad Shamir, Nathan Srebro, and Tong Zhang. Communication efficient distributed optimization using an approximate Newton-type method. International Conference on Machine Learning, 1202):1000-1008 PMLR, 2014.
[17] Jialei Wang, Mladen Kolar, Nathan Srebro, and Tong Zhang. Efficient distributed learning with sparsity. International Conference on Machine Learning. 70:3636-3645. PMLR, 2017.
[18] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, Blaise Aguera y Arcas. craamunncation-ffficienee learning of deep networks from decentralized data. International Conference on Artificial Intelligence and Statistics, 54:1273- PMLR, 2017.
[19] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. International Conference on Machine Learning, 11::5132-5143, PMLR, 2020.
[20] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
[21] Reese Pathak and Martin J. Wainwright. FedSplit: an algorithmic framework for fast federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
[22] Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani. Linear convergence in federated learning: tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34, 2021.
[23] Zilong Zhao, Robert Birke, Aditya Kunar, and Lydia Y. Chen. Fed- TGAN: Federated learning framework for synthesizing tabular data, arXiv preprint arXiv:2108.07922 2021.
[24] Vaikkunth Mugunthan, Vignesh Gokul, Lalana Kagal, and Shlomo Dubnov. Bras-free FedGAN:
A federated approach to generate bias-free datasets. arXiv preprint arXiv:2108 0099777 2021.
[25] Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: convergence analysis and communication efficiency. International Conference on Artificial Intelligence and Statistics, 130:1387-1395. PMLR, 2021.
[26] Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod K. Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. arXiv preprint arXiv:2203.044 04850, 2022.
[27] Po-Ling Loh and Martin J. Wainwright. High ligh-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in Neural Information Processing Systems, 24, 2011.
[28] Nasser Nasrabadi, Trac Tran, and Nam Nguyen. Robust Lasso with missing and grossly corrupted observations, Advances in Neural Information Processing Systems, 24, 2011.
[29] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, second edition, 2018
[30] Farzan Farnia and David Tse. A minimax approach to supervised learning. Advances in Neural Information Processing Systems, 29, 2016.
[31] Jacho Lee and Maxim Raginsky. Minimax statistical learning with Wasserstein distances. Advances in Neural Information Processing Systems, 31, 2018.
[32] Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. International Conference on Machine Learning, 139:3174- 3155. PMLR, 2021.
[33] John Neumann. Zur theorie der gesellschaftsspicle. Mathematische Annalen, 100(1): 295-320, 1928.
[34] Julia Robinson. An iterative method of solving a game. Annals of Mathematics, pp. 296-301, 1951.
11

---

[35] Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176 1958.
[36] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[37] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programmingg 109(2-3):319-444 2007.
[38] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach. International Conference Artificial Intelligence and Statistics, 108: 1497-1777. PMLR, 2020.
[39] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.
A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv: 10555 2018.
[40] Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv: 2019.
[41] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
[42] Mingrui Liu, Youssef Mroueh, Wei Zhang, Xiaodong Cui, Tianbao Yang, and Payel Das. Decentralized parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 33, 2020.
[43] Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan, Efficient methods for structured nonconvex-noncoocauy min-max optimization. International Conference on Artificial Intelligence and Statistics, 13::2746-7754. PMLR, 2021.
[44] David Mateos-Núnez and Jorge Cortés. Distributed subgradient methods for saddle-point problems. IEEE Conference on Decision and Control, pp. 5462-5467, 2015.
[45] Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle poiitt problems: Lower bounds, near-optimal and robust algorithms. arXiv preprint arXiv:2010. 13/ 2020.
[46] Wenhan Xian, Feihu Huang, Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. Advances in Neural Information Processing Systems, 34, 2021.
[47] Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2 02200778, 2021.
[48] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. Advances in Neural Information Processing Systems, 33, 2020.
[49] Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaic. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Systems, 33, 2020.
[50] Mohammad Rasouli, Tao Sun, and Ram Rajagopal. Fedgan: Federated generative adversarial networks for distributed data. arXiv preprint arXiiv2000.077228 2020.
[51] Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implies diversity in GANs. arXiv preprint arXiv:1806. 178806008866 10586, 2018
[52] Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the enteriminationneeneraiiieee
tradeoff in GANs. arXiv preprint 1rXiv:1711.02271, 2017.
[53] Sanjeev Arora, Rong Ge. Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilib- rium in generative adversarial nets (GANs), International Conference on Machine Learning, 70:224-232. PMLR, 2017.
[54] Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. International Conference on Machine Learning, 97:7085-7094, PMLR, 2019.
12

---

[55] Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv:1810.09519 2018.
[56] Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-Layer margin. arXiv preprini arXiv: 1rXiv:1910.04284, 2019.
[57] Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for robust learning. International Conference Algorithmic Learning Theory, 98:162-183. PMLR, 2019.
[58] Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. International Conference on Artificial Intelligence and Statistics, 130:568-576. PMLR, 2021.
[59] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? arXiv preprint arXiv:1902.00611 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "Z1hp_Jnxtpb", "reviewer": "Reviewer_LKhi", "summary": "The paper characterizes the fixed-point properties of local SGDA with no gradient noise with multiple local steps and constant stepsize. Then FedGDA-GT, an improved Federated Gradient Descent Ascent method based on Gradient Tracking, is proposed. It is shown that FedGDA-GT converges linearly with O(\\log\\frac 1\\epsilon) rounds of communication under smmoth strongly-convex-strongly-concave setting. Besides, the paper also analyzes the generalization of empirical minimax learning under distributed setting.", "questions": "1.\tIs it possible to prove the convegence guarantee of FedGDA-GT with graident noise? Does linear convergence with constant stepsize still hold?\n2.\tWhat is the connection between section 3 and other sections despite the distributed minimax setting?\n", "limitations": "NA.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: This paper characterizes the fixed-point condition for local SGDA with multiple local steps with constant stepsize. The condition is not necessarily equivalent to the optimality condition, demonstrating local SGDA under this configuration is not necessarilty convergent to saddle point. The authors also provide an example to illustrate this fact.\n\tUnder the same setting, FedGDA-GT can be shown to exhibit linear rate, which is faster than the sublinear rate of local SGDA. The gradient tracking is used to eliminate the client drift. The numerical experiment also provides evidence on the empirical benefit of FedGDA-GT. \n\nCons: The linear convergence rate of FedGDA-GT is derived under the setting without gradient noise. However, this is a distinct (and easier) scenario than the typical one in the federated learning framework where we only have access to the estimator of the gradient f_i. Whether the properties derived in this paper, i.e., linear rate with constant stepsize, still holds is unknown. Diminishing stepsize could be necessary to guarantee covergence and only sublinear rate is expected.\nThe paper also studies the generalization bounds on minimaxx learning problems in the distributed setting using Rademacher complexity. But its connection with other parts of the paper is unclear.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WZaaS85rZ_p", "reviewer": "Reviewer_oPra", "summary": "This paper studies the problem of min-max optimization in federated settings. The paper derives a Rademacher complexity bound for this setting, and then proceeds to analyze the local SGDA method in federated contexts. The paper shows that when using fixed learning rates and multiple local optimization steps, local SGDA does not converge to minimax optimal points (and give explicit examples of this in the quadratic setting in the appendix). The paper then proposes a method, FedGDA-GT, and shows that in certain settings, FedGDA-GT converges linearly to a minimax optimal point. Finally, the paper concludes with experiments comparing local SGDA and FedGDA-GT on synthetic data that show that FedGDA-GT can converge faster and to a point with lower loss.", "questions": "Some of these are distillations of questions from the section above.\n\n*   Can Assumption 1 be relaxed at all?\n*   Is there any benefit theoretically to setting $K > 1$ in Theorem 2?\n*   Can you shed light on the form of $\\rho(\\eta)$ in Theorem 2?\n*   In Proposition 1, can you concretize the trade-off between model accuracy and communication-efficiency you mention at the beginning of Section 4? For example, [1, 2] show that increasing $K$ for FedAvg does exactly this in quadratic settings.\n\nMinor comments and questions:\n\n*   The discussion before Figure 2(a) seems to suggest that the left plot is $\\alpha = 0$, but the caption says $\\alpha = 1$.\n*   The bound quoted in (11) is incomplete. The dominant part of the convergence rate seems to be $O(c/\\mu n T)$ for some $c$.\n*   In Section 5.1, you seem to use the same learning rate for different methods and different values of $K$. Why is this valid?\n*   In the empirical evaluations of Section 5.2, you use the same learning rate $\\eta$ for different methods \"for the sake of fair comparisons.\" Given that the methods are different, why is this fair?\n\n\n#### References\n\n[1] Malinovskiy et al, \"From local SGD to local fixed-point methods for federated learning.\" ICML 2020.\n\n[2] Charles & Konecny, \" Convergence and accuracy trade-offs in federated learning and meta-learning.\" AISTATS 2021", "limitations": "There are no potential negative societal impacts that I can discern.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I will preface this section with a note that I am not an expert in minimax optimization. Thus, I have taken the paper at face value in some of its discussion of related works on distributed minimax optimization.\n\nThat being said, I think this is a generally well-written paper that occupies an important point in a vein of works on federated optimization that the authors may not be aware of (as I will discuss below). The paper has 3 primary components (generalization bounds, convergence bounds, and empirical evaluation), and I have separated this discussion accordingly.\n\n### Section 3 - Generalization bounds\n\nThe section gives a digestible introduction to Rademacher complexity, and gives corresponding generalization bounds for distributed minimax optimization that extend those of [Mohri et al., 2019]. The proofs seem sound and are interpretable.\n\nThat being said, this section is (in my opinion) one of the weaker portions of the paper. It feels disjointed from the rest of the work, especially as I found no observations that come out of the Rademacher complexity that influence any of the subsequent sections. For example, there is no facet of Corollary 1 that seems to influence the design of FedGDA-GT. Rather, the rest of the work is quite focused on the question of whether you converge to minimax optimal points of the training loss, so I'm not certain what the reader should take away from this section.\n\n### Section 4 - Convergence bounds\n\nIn contrast to the above, this is the strongest part of the work. The observation that Local SGDA may not converge to minimax optimal points is a valuable one, and fits in nicely with a line of prior work in federated optimization (more on that below). Similarly, the FedGDA-GT method is an intuitively useful method that has nice convergence guarantees in certain settings. The proofs all seem sound, and the entire section gives a nice picture of federated minimax optimization.\n\nThe primary weakness of this section is something that is easily remedied, which will in turn make the paper stronger. This paper gives a minimax mirror to an important line of work in risk-minimization federated optimization that should be emphasized. Prior works, including [1, 2, 3] have all explored variations on a central theme: That Federated Averaging (FedAvg) does not converge to critical points of the empirical loss when using $K > 1$ local optimization steps. In that sense, Proposition 1 of this work is effectively a minimax version of this result, and I believe should be discussed as such.\n\nAnalogously, the solution to use gradient tracking kinds of techniques to remedy this issue is one that has appeared in multiple parts of the literature. Perhaps most fittingly, I would urge the authors to consider [4]. This work proposes a kind of gradient tracking version of FedAvg that has linear convergence in deterministic settings. In fact, the method FedGDA-GT is intuitively a minimax version of FedLin from [4]. The two methods share a very common framework, and have similar convergence results. Basically, I believe this work has done a good job of translating relevant work on objective inconsistency in federated learning to minimax settings, and I would like to see more of a discussion of this.\n\nOne other weakness of this section that is worth noting: It is unclear from Theorem 2 whether setting $K > 1$ in Algorithm 2 is useful.  In [4], the authors actually construct settings where $K = 1$ is optimal (by way of a lower bound). This is potentially a useful thing to add to this work if possible. Finally, I will note that while I would also love to see extensions to non-strongly-convex-strongly-concave settings, I do not think this is strictly necessary for acceptance.\n\n### Section 5 - Empirical results\n\nAs mentioned above, these results are all on synthetic data. As such they succeed in illustrating the relevant properties of FedGDA-GT and Local SGDA that the authors want to illustrate. Moreover, I appreciated the authors' attempts to explore how heterogeneity affects the methods (and in particular, the observation that the methods are comparable in some settings).\n\nWhile explorations on less synthetic data would improve the work, I do not think this is strictly necessary given the theoretical focus of the work.\n\n### Review Summary\n\nAll in all, I think this is a good work that opens the way for many other analyses of federated minimax optimization. The strongest parts of this work are in Section 4. I would personally recommend the authors open this section up a bit more and include more about details about how it relates to federated risk-minimization works (eg. [1, 2, 3, 4]). In particular how this work presents an extension of these works to minimax settings. This related work also gives various avenues that could improve this work, including extensions to more general loss functions and possible lower bounds. While the generalization bounds and empirical evaluation are nice, they are not the primary draw of the work.\n\n#### References\n\n[1] Malinovskiy et al, \"From local SGD to local fixed-point methods for federated learning.\" ICML 2020.\n\n[2] Pathak & Wainwright, \"FedSplit: An algorithmic framework for fast federated optimization.\" NeurIPS 2020.\n\n[3] Charles & Konecny, \" Convergence and accuracy trade-offs in federated learning and meta-learning.\" AISTATS 2021\n\n[4] Mitra et al., \"Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients.\" NeurIPS 2021.\n\n# Post author-feedback comments\n\nI have read the other reviews of this work, and all the author comments. I still believe this paper should be accepted. While there are some discussions about the assumptions made regarding the minimax setting (eg. whether the strongly-convex-strongly-concave is too strong), I think that this misses the core contributions of the work:\n\n1) A proof that Local SGDA with fixed learning rates will not converge to minimax-optimal points in federated settings when $K > 1$. Note that in particular, the linear convergence of Local SGDA only holds in non-federated settings: This work demonstrates that in federated settings it may not converge at all.\n\n2) A new method that does converge linearly to minimax-optimal points in federated settings when $K > 1$ even with fixed learning rates.\n\nAs I mention in my review above, this mirrors a lot of theoretically interesting and provocative work on FL minimization over the last few years, but brings it to the realm of minimax optimization. I believe that this warrants publication (especially as the proofs are intuitive, easy to read, and correct). While the current organization of the work (with Rademacher complexity bounds coming first) may obscure these contributions slightly, this is eminently fixable.\n\nFinally, I wish to note my strong belief that this is primarily a theoretical work, and should be reviewed accordingly. I think the experiments help validate the theory, and do not need to go beyond that. Similarly, I think that questions of the actual utility of this method in practical settings miss the point: This serves as a theoretical jumping off point for understanding why minimax optimization methods fail in FL settings, and how we can possibly remedy that. There is plenty of precedent in the literature for works of exactly that nature (including [1, 2, 3, 4] above).\n\nI have increased my score to a 7 accordingly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BVWbMVa0j-r", "reviewer": "Reviewer_urch", "summary": "This paper considers a federated minimax optimization problem with compact constraints. The contents of this paper are threefold. First, under assumptions with respect to the maximization variable, the authors upper bound the stochastic minimax objective with the empirical minimax objective. They also provide an upper bound of Rademacher complexity of the stochastic minimax model. Second, a Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT) (FedGDA-GT) is proposed. Under the assumption that the minimax problem is strongly convex and strongly concave, and other assumptions, the linear convergence of the generated sequence is proved. In the last part, experiments on quadratic minimax problems and robust linear regression problems are conducted.", "questions": "1.\tIn the experimental part, are the models satisfy the assumptions in section 4? Do they have the unique interior optimal solutions? If yes, does it mean the considered quadratic problems have closed forms?\n2.\tWhat’s the complexity that counts the inner iterations for the proposed method?\n3.\tWhat is the exact form of M(y) that is used as a key element in the upper bound of the Rademacher complexity? Can it be infinity when taking the maximum over y? If yes, does the upper bound in Corollary 2 and Lemma 2 become infinity?\n", "limitations": "1.\tThe proposed algorithm needs to communicate with the server twice in each iteration, which can be inefficient. \n2.\tIn applications of federated learning, the data size is huge and the proposed method requires computing the full gradient in each step. Thus, this method is expensive to apply. A stochastic variant of this method and its convergence analysis are not considered. \n3.\tThe assumptions for the linear convergence of the proposed method are too strong to satisfy or check for the learning model. See more explanation in \"strength and weakness\" part 2.\n", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. The upper bound of Rademacher complexity for the general federated minimax model is new. \n2. A gradient tracking skill is applied in the local updates of the proposed method. Thanks to this, in the deterministic case, the proposed method has sequential linear convergence under some assumptions.\n\nWeakness: \n1.\tFrom my understanding, the upper bound of the Rademacher complexity can be obtained following similar assumptions and proofs in Section 4 [13] of this paper.  \n2.\tIn Section 4, the assumptions that the objective is strongly convex strongly concave, that the objective is twice continuously differentiable, and that the problem has at least an interior stationary point, are too strong. In centralized minimax problems, twice continuously differentiability is not usually assumed, but there are still methods that achieve linear convergence. Thus, the twice differentiability is not necessary and limits the scope of the applications of the convergence results. In addition, the assumption that there exists an interior stationary point is hard to check for many minimax models. Thanks to these ideal assumptions, the proofs for the linear convergence of the proposed method are classical and simple. In my opinion, these assumptions lack convincing application examples.\n3.\tThe models in the experiments part are relatively simple, compared to those in [13]. No experiments are conducted on widely tested datasets such as Adult dataset, Fashion MNIST, and Language models. Since this paper claims to generalize the results in [13], I think experiments that apply the proposed method to the models in [13] should be conducted and compared.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "2vv2OhEVR_b", "reviewer": "Reviewer_gBj4", "summary": "The paper is focused on minimax problems. First some generalization bounds are proposed via Rademacher complexity for the empirical minimax problem. Then, the paper focuses on federated learning for strongly-convex-strongly-concave minimax problems. A new algorithm  is proposed for which the convergence rate is provided.", "questions": "Qu1: How many communication rounds and what is the convergence rate of the proposed method compared with the results in [25] ? Using the same notations for clarity. Are the additional broadcasts from the server in FedGDA-GT accounted for ? \n\nQu2: What is the link between Section 3 presenting the Rademacher complexity and Section 4 presenting the proposed federated learning algorithm?\n", "limitations": "The limitatios of the propsoed method do not seem to be addressed in this paper. \n\nRegarding negative societal impact, this work is fairly theoretical and there are no straightforward negative impact to be reported. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThis paper investigates a federated learning approach for minimax problems. An interesting new algorithm is introduced, but which lacks a clear presentation. \n\nWeaknesses\n\nOverall, the paper lacks a clear focus and clear interpretations of the proposed algoritm and its main results in comparison with the state of the art. \n\n1. The motivation behind the mathematical derivations in Section 3 are not clear. Some examples of its application could be provided. \n\n2. The equation (11) does not seem to be accurate as 1/T^3 would mean a very fast convergence much better than 1/T. From [25], it seems that a rate convergence of O(1/(nT)) is achieved by local SGDA, but that the number of communications is either O(n) in the homogeneous setting or sqrt(nT) communication rounds in the heterogeneous setting. \n\n3. Some further interpretation could be provided behind the result in Proposition 1. Especially, why this result implies that SGDA with a fixed point step-size cannot converge. \n\n4. The discussion regarding local vs global minimax points right before section 4.2 is not clear especially since the objective is assumed to be strongly-convex-strongly-concave as per Assumption 1. This should be clarified. \n\n5. The description of the novel proposed approach lacks in clarity. Some details behind the major differences between the SGDA and the proposed method FedGDA-GT should be provided after introducing the algorithm. It seems that some additional global information that is broadcasted by the server is used. \n\n6. A more detailed discussion about the precise convergence rate and communication rounds behind the main result in Theorem 2 and in comparison to those of [25] should be provided before the Experimental section. \n\nThe main convergence result is not interpreted well enough and it is not clear why the proposed algorithm is superior than SGDA. Indeed, the convergence rate seems to be linear which is also the case for SGDA. \n\nRegarding the communication rounds required by the proposed method, there is no clear discussion in the main body of the paper. \n\nIn the abstract the authors mention log(1/epsilon) communication rounds to reach an epsilon precision but this is nowhere to be found in the main body of the paper. In the conclusion it is mentioned log(1/epsilon) time, but this is very vague and unclear. \n\nComments post-rebuttal:\n\nThe authors have answered in a satisfactory manner to most raised comments. However, the paper still requires major changes to be accepted. Thus, the initial score is raised to 5. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept