Solving a Class of Non-Convex  Minimax Optimization in Federated Learning
Authors: Xidong Wu
Jianhui Sun
Zhengmian Hu
Aidong Zhang
Heng Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning
Non-Convex  Optimization
Minimax Optimization

Abstract: The minimax problems arise throughout machine learning applications, ranging from adversarial training and policy evaluation in reinforcement learning to AUROC maximization. To address the large-scale distributed data challenges across multiple clients with communication-efficient distributed training, federated learning (FL) is gaining popularity. Many optimization algorithms for minimax problems have been developed in the centralized setting (\emph{i.e.}, single-machine). Nonetheless, the algorithm for minimax problems under FL is still underexplored. In this paper, we study a class of federated nonconvex minimax optimization problems. We propose FL algorithms (FedSGDA+ and FedSGDA-M) and reduce existing complexity results for the most common minimax problems. For nonconvex-concave problems, we propose FedSGDA+ and reduce the communication complexity to $O(\varepsilon^{-6})$. Under nonconvex-strongly-concave and nonconvex-PL minimax settings, we prove that FedSGDA-M has the best-known sample complexity of $O(\kappa^{3} N^{-1}\varepsilon^{-3})$ and the best-known communication complexity of $O(\kappa^{2}\varepsilon^{-2})$. FedSGDA-M is the first algorithm to match the best sample complexity $O(\varepsilon^{-3})$ achieved by the single-machine method under the nonconvex-strongly-concave setting. Extensive experimental results on fair classification and AUROC maximization show the efficiency of our algorithms.

Solving a Class of Non-Convex Minimax Optimization in Federated Learning
Xidong Wu
Jianhui Sun Computer Science University of Virginia Charlottesville, VA 22903
Electrical and Computer Engineering
University of Pittsburgh Pittsburgh, PA 15213
sidong_ww@out.lne com
js@gu@virginia.c
Zhengmian Hu Computer Science University of Maryland
Aidong Zhang
Heng Huang"
Computer Science University of Virginia Charlottesville, VA 22903 aidong@virginia. edu
Computer Science
University of Maryland
College Park, MD 20742 huzhengmi angggail.. com
College Park, MD 20742
henghuanghh@@mail. com
Abstract
The minimax problems arise throughout machine learning applications, ranging from adversarial training and policy evaluation in reinforcement learning AU- ROC maximization. To address the large-scale distributed data challenges across multiple clients with communication-efficii ing (FL) is gaining popularity. Many optimization algorithms for minimax problems have been developed in the centralized setting (i.e., single-machine). Nonetheless, the algorithm for minimax problems under FI. is still underexplored. In this paper, we study a class of federated nonconvex minimax optimization problems. We pro- pose FL algorithms (FedSGDA+ and FedSGDA-M) and reduce existing complexity results for the most common minimax problems. For nonconvex-conent problems, we propose FedSGDA+ and reduce the communication complexity to ( "). Under nonconvex nonconvex-strongly stwoosly-ooooooono concave and nonconvex- minimax settings, we prove that FedSGDA-M has the best-known sample complexity of N-1e and the best-known communication complexity of = FedSGDA-M the first algorithm match the best sample complexity ( achieved by the single-machine method under the nonconvex-stronge saareee--troolly--ncaae setting. Extensive experimental results on fair classification and AUROC maximization show the efficiency of our algorithms.
distributed training, federated learn-
Introduction
The nonconvex minimax optimization has been actively applied to solve enormous machine learning problems, such as adversarial training [56] 61,, generative adversarial networks (GANs) [6 [8].
policy evaluation in reinforcement learning [5
22 25
robust optimization II] 60 AUROC
(area under the ROC curve) maximization [39], etc. Many single-machine minimax optimization
algorithms have been proposed to address these problems.
Equal contribution
9This work was partially supported by NSF CNS 2213700 and CCF 2217071 UVA. "This work was partially supported by NSF IIS 1838627, 1837956, 1956002, 221 1492, CNS 2213701, CCF 2217000 2217003, DBI 2225775 at Pitt and UMD.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Machine learning tasks with large-scale distributed datasets call for distributed training 3 because of its ability to shorten the calculation time and train models with data from various locations. At the same time, communication overhead has emerged as the most restrictive bottleneck of distributed training due to the increasing model and data size. To tackle these issues, federated learning (FL. 44 has emerged as a promising technique since it makes use of distributed data from different clients, avoids frequent transmission between clients and the central server, and preserves data privacy. In FL, clients train and update their models locally, and the server aggregates and averages the model parameters from all clients periodically. Only models are shared among clients and the training data stored locally, which provides certain level of data privacy. In addition, FL also enhances computation power since utilizes many clients to train models.
Although federated learning has gained popularity, most existing works focus on the standard stochastic minimization problem B3 minimization optimization in FI. are proposed [53
Recently, some algorithms for non- 59. However, existing FL minimax algorithms have not achieved the complexity level reached by single-machine algorithms. To bridge this gap, we consider the federated nonconvex minimax optimization problem as follows:
36
71
58
70
72
21
15,
50
{ F(z,z)
min max
Σ f(
(I)
#ER"1 WER
where the function f1 y) = BE [I( yi E:)] Rd Rd - IR. is the loss function of the 7th client. We restrict our focus to the non-convex minimax problem, where fi y) is nonconvex over E Rd and concave or nonconcave over y E Rdd N is the total number of clients. &, = (Ir, Bi) ~ Dj denotes data point & is sampled from the local data distribution D; on machine i. In this paper, heterogeneous datasets are considered, namely, D; and D, (i + j) ) are not identical.
Some recent works have attempted to solve federated minimax optimization for convex-concave setting 11 26 (2). Due to the popularity of deep neural networks, nonconvex minimax has wider extend single-machine algorithms, such as SGDA, to federated learning settings for nonconvex minimax optimization. However, theoretical understandings of federated minimax optimization remain limited in the literature. In the context of stochastic smooth nonconvex minimax problems, their analysis either relies on strict assumptions methods 44 28 [9 or achieves suboptimal convergence results [50]. For example, singl-mmchine
applications. More recently, some works [50 53 19 67
setting, which is much better than O( achieved by the best FL minimax algorithm [50] in existing literature. Therefore, natural question arises:
achieve O under wwwpuvee--stoogyyooooe
Can we design stochastic gradient decent ascent methods with better sample and com- munication complexities to match the convergence rate of single-machine counterparts for solving the problem !
In this paper, we provide an affirmative answer to the aforementioned question and propose class of algorithms to solve the problem (1) under different settings. In particular, we consider three most common classes of nonconvex minimax optimization problems: 1) NC-C: NonConvex in x, Concave in y: 2) NC-SC: NonConvex in x, Strongly- Concave in y, 3) NC- PL: NonConvex in PL-condition in y. For each of these problems, we propose new algorithm with provably better convergence rate (please see Table T) and provide theoretical analysis. Our main contributions are four-fold:
1) NC-C setting. We propose FedSGDA+, and prove it has sample complexity of O(N-1g-8) and communication complexity of O(E FedSGDA+ takes advantage of the structure of FL by adding the global learning rate at the server and reduces communication complexity to ( from O( in [50]. It also achieves a linear speedup to the number of clients.
2) NC-PL setting. We propose federated stochastic gradient ascent (FedSGDA-M) algorithm with the momentum-based variance reduction technique. It has the best sample complexity of O(x²N N and the best communication complexity of 0(k2==?) 2). Compared with existing momentum based variance reduction algorithms, our result employs a novel theo-
retical analysis framework that produces tighter convergence rate (i.c., our rate gets rid of a logarithmic term appearing in existing works).
3) NC-SC setting. FedSGDA-M can be directly applied to the NC-SC setting since the PI. condition is weaker than strong-coneavity. Our algorithm is the first work to reach sample

---

Table I: Complexity comparison of existing nonconvex federated minimax algorithms for finding an e-stationary point. Sample complexity is the total number of the First-order Oracle (IFO) to reach an e-stationary point. Communication complexity denotes the total number of back-and- forth communication times between clients and the server. Here, N is the number of clients, and L is the condition number.
Type
Algorithm
Reference
Sample
Communication
Nonconvex
Local SGDA+
[50]
0 ON
0
concave
FedSGDA+
Ours
0 ON
Local SGDA
[50
0 Ok2N
O
Nonconvex
Momentum Local SGDA
[50
N
O
Strongly
Concave
FEDNEST
[33
O
ONE
FedSGDA
Ours
N
0 O
Local SGDA
[50]
On-N-1
O 3)
Nonconvex
Momentum Local SGDA
[50]
NNNN
0
PL
SAGDA
663
1NN-88
01e
FedSGDA
Ours
[n'
0 O
Their theoretical analysis does not report the dependency on N.
Their theoretical analysis does not report the dependency on k.
complexity of 3 in federated learning. In addition, FedSGDA-M does not rely on large batch size to reach optimal sample complexity compared with single-mane machine minimax
algorithms 29 42
4) Extensive experimental results on fair classification and AUROC maximization confirm the effectiveness of our proposed algorithm.
2 Related Work
2.1 Single-Machine Minimax
proposed various deterministic and stochastic algorithms to solve the NC-C minimax problems. All of these algorithms,, however, have double-loop structure and are thus relatively complicated implement. They decouple the minimax problem into a minimization problem and a maximization problem and use a nested loop to update variable y while keeping variable constant. Subsequently, (38) studied the complexity result of the single-loop algorithm (SGDA) for the NC-C minimax problem and proves the stochastic algorithm achieves O( complexity. SGDA is direct extension of SGD from minimization optimization to minimax optimization problems. Recently, 433 providing a unified analysis for the convergence of OGDA and EG methods the minconvex-strongly-comm concave (NC-SC) and nonconvex concavee (NC-C) settings.
Nonconvex-Concave (NC-C) setting. 31 46
45
54
351
(NC-SC) setting. (88 analyzed the stochastic gradient descent ascent (SGDA) algorithm and proved that SGDA has 04) stochastic gradient complexity. To reduce the convergence rate, 42 proposed stochastic GDA algorithm (i.e. SREDA) with
double-loop structure based on the variance reduction technique of SPIDER [33 and reduce the
variance reduction technique of STORM 7 and proposed Acc-MDA. Acc-MDA is a single-loop algorithm, which gets the same convergence
complexity to e 3). (29 used momentum-biic
result as SREDA. Furthermore, adaptive minimax algorithms are introduced 28] 30 solve the nonsmooth nonconvex nonconve--strongly -troongyy-concvve minimax problems based on dynamic mirror functions. used a nested adaptive framework to design parameter- aggossic nonconvex minimax algorithm. proves that VR based SAPD+ has the complexity of O(k2E-3) However, whether the best convergence result of ( in single-machine methods can achieved the federated setting is an open question. In addition, [23] conducts an in-depth investigation of limitations of GDA algorithm (e-g., smaller learning rate, cycling/divergence issue) and gives a systematic analysis of how to improve GDA dynamics.
65
69
3

---

Nonconvex--oonconeave (NC-NC) setting, There is extensive research on NC-NC problems [2] and the Nonconvex-PL condition is a special class of functions that interests us the most. Polyak- łojasiewicz (PL) condition does not require the objective to be concave and recent works show that the PI. condition could hold in the training process of overparameterized neural networks with random initialization [ 5]. Recently, many deterministic methods [45] 64 [4] are proposed for NC-NC problems under the NC-PL setting. [20] proposed a PDAda method for Nonconvex-PL.
minimax optimization with the restriction of the concavity condition, and [6] focuses on the finite-sum Nonconvex-PP minimax optimization. Stochastic altermating GDA and stochastic smoothed GDA proposed in [66] achieve complexity of O(K"=- and O "e)e respectively.
2.2 Distributed/Federatee Minimax
Distributed training has rapid development in minimax optimization in recent years, driven by the need to train large-scale datasets [40]. Under the serverless decentralized setting, algorithms for nonconvex minimax have been studied extensively in nonconvex-strowe wsrreee-ssstooooooooe concave setting 62 nonconvex-Pl PL setting (27].
and
In the FL setting, some works analyzed algorithms for convex-concave problems
37 26 52)
However, as nonconvex models (e.g., deep neural networks) being more and more prevalent, there is growing need for federated nonconvex minimax optimization, such federated adversarial
training [49]. federated deep AUROC maximization [99] and federated GAN [47]. [99] and [67] focus on imbalanced data tasks. They reformulated the AUROC maximization problem as the min- max problem under the FL setting. But their analysis relies on strict assumptions that deep models minimax.
49] converted the robust federated learning into the minimax problem, where only model parameters, namely min variables, are exchanged among clients via the server. [10] proposed Local SGDA and Local SGDA+. Local SGDA is the local-update version of the SGDA algorithm in FL. Different from local SGDA, in local SGDA+, max variable y is updated with constant min variable T and the snapshot ã updates every S iteration. Afterward, (50) improves sample complexity and communication complexity of Local SGDA for NC-SC and NC-PL. settings, and Local SGDA+ for NC-C setting. (50) also proposes a Momentum Local SGDA, which achieves the same theoretical results as Local SGDA for NC-PL and NC-SC settings. In addition,
satisfy the PL condition and only focuses on PL-strong-coneas
(53) designs FEDNEST with two nested loops. Although FEDNEST composed of FEDINN (a federated stochastic variance reduction algorithm their convergence complexity is not improved over vanilla Local SGDA. Afterward, [63 proposes SAGDA under NC-PL setting, which yields better communication complexity (i.e., O 2). However, its analysis does not consider the effect condition number K. More recently, [51] considers federated minimax optimization with Client Heterogeneity in nonconvex concave and nonconvex strongly-concavs
settings.
Relation to Existing Works. We propose FedSGDA+ for NC-C setting and FedSGDA-M for NC-SC and NC-PI. settings. In NC-C setting, we discover that the addition of global step size leads to better communication complexity. Under this circumstance, theoretical analysis is more challenging not only need to consider the complicated structure of the minimax problem but also need to handle the local update and global update separately. For FedSGDA-M, we relax the requirement of step size (specifically designed unnatural step size is often required in STORM-like approaches 77 34] ) which requires novel proof techniques to obtain. Thus result does not contain logarithmic term and provides a tighter convergence rate (Seen in contributions 1 in (34).. In addition, with different theoretical frameworks, our better sample complexity doesn't 't rely on a big batch size, while the single-machine minimax algorithm with variance reduction (Acc-MDA) in 29) (Table 2) needs a large batch to achieve the same sample complexity.
3 Algorithms and Convergence Analysis
Notation: || denotes the &2 norm for vectors. a = Obb) denotes that a < Cb for some constant C> 0. Given the mini-batch samples B = {s, )3= 1 we let V ff( y: B) - ビ Vf Assumption 3.1. (i) Unbiased Gradient. The gradient of each component function fx computed at each client is unbiased for all (+) D., e [N]:
E [x ( = V fz(x
4

---

Algorithm FedSGDA+ Algorithm
1: Input: T, local step sizes é, c. global step sizes !/ 7y, h: numbers of inner updates and outer update S, and mini-batch size b, clients;
2: Initialize: 2/ To Tu. V0 yo.
3: for (/- 0, 0,.,...,
do
4: for 1, . do
5: Local Update:
6: for q = 0, 1, ..... Q do
7:
(4) "l,t11 = zt, eV aV Vi Bi.a)
Draw mini-batch samples - with B =b from D; locally
8:
9:
vig+1 = Vi, + cV yfii vi Bi.
end for
11:
end for
21+100 I++1 It 7}s
1= ( z1)
N
13:
V1+1.0 Di+1
41 My Σi= (vi.Q 9t)
14:
if mod 1, then
15:
k=
16:
17:
end if'
18:
end for
19:
Output: x and y chosen uniformly random from {(E,, 9c) Bt)
iii Variance Bound. The following inequalities hold for all g(+) Di,i, i [N]:
E Vf y: (0)) V.. y)| o²
N Σ [Vf((..)) (f(r,1))'' 5²
(2)
The Assumption 3.1 is standard assumption in stochastic optimization, which will be used through- out the rest of the paper. In FL. algorithms, the Assumption 3.1 (ii) is frequently used to bound the variance and data heterogeneity. The heterogeneity parameter, Ç, denotes the level of data heterogeneity. In the homogeneous data configuration, C 0.
3.1 Nonconvex Concave (NC-C) Problems
Assumption 3.2. (Concavity). The nonconvex function f(:.-) is concave in y if for fixed E Rd. Vy, y E Reda, we have
f(z, s f(x,8))++++))) (Vf(2./)),)1)))
To solve the problem ① under the NC-C setting and reduce the complexity, we propose FedSGDA+ (Seen in algorithm 1. Although local SGDA+ (50) achieves the same sample complexity the single- machine method (SGDA), its communication complexity is not optimal. This unsatisfactory result due the fact that local SGDA+ simply extends the single-machine method into the distributed setting, and does not consider the complicated local-server structure in FL.
In FedSGDA+, Line 5-10 are conducted in the local clients. The updates of variable to the standard stochastic algorithm for minimization problems, such as FedAvg. We sample data points and update the x locally with the current variable zi., and vi.g. However, for the y-updates, stochastic gradients are calculated with the latest snapshot of zii.e., 5x. and in each local iteration, updates with the constant Z as seen in Line 9 in Algorithm The Gg is updated every S rounds Line 14-16 in Algorithm [].
similar
In addition, we make use of the advantage of FL and introduce the global step size 7/ Ty which provides the flexibility of FL training (Seen in Line 12-13). Local SGDA+ could be regarded as special case of FedSGDA+. We now provide the convergence analysis of FedSGDA+ and introduce the necessary assumptions. The details of the proof's provided in the supplementary materials.
5

---

Assumption 3.3. (Smoothness). Each local function f((z,)) v) has a L Liipschitz continuous gradients, ie.. T2 and y1, y2. we have
f M1) V2(22, 32) - y (21, y1) (Z2, V2)1l
(4)
The Assumption 3.3 on the smoothness is a standard assumption stochastic optimization 2 17
Assumption 3.4. (Lipschitz continuity in x). For the function F, there exists constant G2. such that for each E R and Vx,I" x' E R we have
[F 9) - F(d', ((d',))ll & G. |2 - =''l
Under the NC-C setting, the function F(:.)) :) is concave in Following 99, we define Φ(x:)
max, F(x, y) and the Moreau envelope of (-) is defined below:
Definition 3.5. (Moreau Envelope) function x-) is the X-Moreau envelope of Φ(-), for À > Vr E ned,
$ < min ((2 + 2 x1/
1
2A
From 38 we know that when we have point that is an e-stationary point of + (z). then is close to a point z' which is stationary for (xr). Hence, we focus minimizing (x))l under the NC-C setting.
Theorem 3.6. Suppose Assumptions 3.1
3.2 3.3 3.4
hold and the sequences { ye are generated
by Algorithm max(cny, of
IQQL and let 1/
< D following [10 50)
1 T-1 T
0²
$ 1//22, (2o)
E $ 1 (iT) Qen.T
E
1/2r, (2.) S 8L &L,a +
)++8
+
N
t=0
+
e
(0² + 6QC
D
+ o
+
6L 10,/(22220 (0² 6(
N
o
1
16L, + 96T.3 +c()
G32T, G2
QS
N
Corollary 3.7. By setting c é
IT Q - E7 1o Cily To7,7Q
N
N 10L,
S=T1/3 FedSGDA+ has the following convergence rate:
1
T-1
E
1/21,, (3.))
80L
+(G)+
24(0² + 6(2)
72G
24(a²
6(2))
T
T1/3
572/3
2572/3
2/7
2572/3
1
D
0²
3(02 + 6
16G
0²
160L3D
S0²
2/72/3
T1/3
11/3
50L,
571/3 V
G2
+
N
T1/3
571/3
Remark 3.8. (Complexity) Based on Corollary 3.7
to make 1 ET E
| 1/21, (f.) e
communication complexity = 0 We choose b = O(), then we have sample complexity bQT = - It also denotes that FedSGDA+ has linear speedup with respect to the number of clients.
3.2 Nonconvex-PI. (NC-PL. Problems
Assumption 3.9. (Polyak Lojasiewiez (PL) Condition y). The function F(x, y) is p-PL condition in и(μ > 0), if Vr: 1) y (z) = arg max, F(x, y) has nonempty solution set; 2) || V FVr, (x 2p( (a. (x) (x. Vy-
To solve problem ① with better convergence complexity under nonconvex-Pl. we propose federated stochastic gradient ascent (FedSGDA-M) algorithm with the momentum based variance reduction technique (Seen in in algorithm

---

Algorithm 2 FedSGDA-M Algorithm
1: Input: T, step sizes é, CJ momentum coefficient a, 3, the number of local updates Q, and mini-batch size b and initial mini-batch size B;
2: Initialize: z/ = Zo = #े E zyg y0 = Yo = ; E vo- ui = Vaf(at: s6: BB) and
"i = -Vy (a): vó: Bb) where | = B are drawn from D, for E [N]-
3: for fort=10 1,2, ................................ do
4: for = 1,2,.. .. do
5:
if mod (1. Q) then
6:
Sever Update:
7:
" ūt N Σ j=1 u
8:
uf Et N
1 Σ ===l
9:
o = Ft
N Σ
(xk-1 - enpu)
10:
y = Jt
N E)= (96-1 + cnu!)
11:
else
12:
x = - End
13:
Vi Vi- cnpe
14:
end if
15:
Draw mini-batch samples B; [[/))_, with [B = b from D, locally
" V fx y/: Bi) + aa( V=fiari-1vv
17:
0 V (1) yi: Bi) + (1 - -B) Vyli(at-11-b-111
18:
end for
end for
20:
Output: and y chosen uniformly random from {ā,, (Zz,Dt)ees De
In FedSGDA-M, each client initializes the gradient estimators {ui vi} with stochastic gradient as seen in line 2 of Algorithm 2 Following that, each client updates the model variables {at vi locally as standard stochastic gradient descent ascent method (lines 12-13 of Algorithm Compared with local momentum SGDA [50), the key difference is that clients utilize variance reduction gradient estimators (u², r/ which are constructed
lines 15-17 of Algorithm 2 For the update step of {ur, vt). the coefficients should satisfy 0 < < 1 and 0 < B < 1. In every Q iteration, clients transmit model parameters and gradient estimators to the server, which computes {ã,, Ne, Te ) Then the server sends averaged model variables and gradient estimators to each client to update the local variables, as shown lines 5-10 Algorithm
Definition 3.10. According to Assumption 3.9 there exists at least one solution to the problem max, F(x, y) for any æ. Here we define (xx) F(x, y (x)) = max, F(x,1) We use g-stationary point of ((r), i.e. [[V(( < E as the convergence metric.
We know (xx) is differentiable and (L + k.L)-smooth and y²()) is k-Lipschitz from 50 Given
that V F (I,, y (x,)) O, we have V (z,) V.F (I,, (z,)) + V F (ā,, (xx)) Oy" (5x) =
V.F( (Ze, 3/" (z:)) which widely used in the analysis of nonconvex PL 10 and nonconvex -anconvex-stronglyy concave minimax optimization (62) 38). Then we discuss the convergence analysis of FedSGDA-M.
The proofs are provided in the supplementary materials.
Assumption 3.11. (Lipschitz Smoothness) Each component function fi v: has a Lipsschhttz gradient, i.e., Vx, 22 and 31 8/, we have
Vz g): ff E2 s L (x2, 82)ll
(5)
F(x, u) has LLpsschhitz gradient based on the convexity of norm and Assumption 3.11
We have
N
(2.1(11811) - V2F(12.
E ( v afll
E V (1:()
Azfi v2:
N
1=1
< L L vi) - (x2.
7

---

In optimization analysis. it is standard to use the Assumption 3.11 Several widely used single- machine stochastic algorithms, such as SPIDER [T3] and STORM 7 make use of this assumption. It is also used by numerous FI. algorithms, including MIME 32 Fed-GLOMO 8 STEM 34 and
FAFED [58]-
Theorem 3.12. Suppose that sequence Wel.o is generated from Algorithm
Under the above
Assumptions 3.1 3.11 given 1 Z0Q a = e/r 3 = 02n bNK
301,"
301.2
6NK--0
where [0, 1] we have
6xc
T
2(0(T0) ((TT)
302
361
1
E V (x:)1
+
+ (T))
F(To; Dt)
T t=
CnTT
aTBN
p. BNSTBN
cnp2T
6
2
72
[ cg)
(²(c2 + cg)
+
1211?
Nb
2
30b12
1212
Corollary 3.13. By setting b O(n²) for [0, 11.11 61
bNR 6N
3012 2
02 =
bNK
301
C
6x ok C
54x v. T = TT. Q N273. 1
1//33
N2/3
B
T /22"bx-->
we have C17²
2002
20LT.77
N273
1/3/3
B 221
3/1/3
401 'ixt-''
4015
2/
E V (3+))1 2160L
Φ*1
40
480o²
(NTT))2/3
k3
"NNT 22/3
R²
(NTT))
240Lg (NT))2/3
902
27a²
30
15ç21
(#o) F(Eo; [o)]
20bm
NT))
5(NT6)2/3
20h
40
(NTo)2/3
2/3
where क" is the optimal.
Remark 3.14. (Complexity) To make the 1 E S we get To = O(N--E-3 and T = 0 ".)) Considering the b = K², we have communication complexity _ k3 (NNT)) = x² x3= and sample complexity bT = O
When = b = K. communication Complexity T = 2² for finding an e-stationary point. Sample complexity BT LO(-NN-- matches the complexity result achieved by the single-machine algorithms, such as SREDA and Acc-MDA in [4]]29] but we do not require large batch size b compared with these algorithms. And O(x Nix ig 3) also exhibits a linear speed-up compared with the aforementioned single-machine algorithms,
3.3 Nonconvex-Stronge Sonconvee-Strongt-CCraeve (NC-SC) Problems
Assumption 3.15. Each local function function fa y) is p-strongly concave in y e V.i.., Vz e X and y1, V/2 E y, we have
I (I,,211) - V (x y2)l 2 plyy - y2ll
When the function F(x, 8) is strongly concave in y E y. there exists unique solution to the problem max f(x y) for any x. Since PL condition is weaker than strong concavity, the convergence result of FedSGDA-M in Algorithm Junder NC-PL also apply to NC-SC problem and FedSGDA-M has the sample complexity of O 33-3 and the communication complexity of O -2) under www.aneweesstoollyyoooeeeee setting.
2
4 Experiments
We conduct experiments AUROC maximization and fair classification tasks verify the efficiency of our algorithms under mmnconve--strongly-ccmmm and nonconvex-concave settings. Experiments completed on the computer cluster with AMD EPYC 7513 Processors and NVIDIA RTX A6000.
The code is available
8

---

Datasets and Models: We test the performance of algorithms on three typical datasets: Fashion- MNIST dataset, CIFAR-10 dataset and ImageNet. Mishion-MNIST dataset has 70, 000 28 28 gray images (10 categories, 60, 0000 training images and 10, 000 testing images). CIFAR-10 dataset consists of 50, 000 training images and 10, 000 testing images. Each image the 3 32 x 32 arrays of color image. Iiny-ImageNer dataset has 200 classes of (64 x 64) colored images and each class has 500 training images, 50 validation images, and 50 test images. For Fashion MNIST and Cifar data sets, choose convolutional neural network from [28 (The details are shown in the supplementray materials). For Tiny-Image ImageNet, we choose ResNet-18 24 as the model.
4.1 Fair Classification
First, we follow different categories.
50 28
and train fair classification networks by minimizing the maximum loss over
N
C
1 N
min max VEV
(x)
s.t.' = (v1 2 0. Σ =
where L denotes the cross-entropy loss functions corresponding to the class e in C different classes and r denotes the CNN model parameters. Clearly, the problem in 66 is nonConvex x (deep model parameters), and Concave in We compare our algorithm (FedSGDA+) and local SGDA+ with varying model, datasets, local update numbers, step size. Although the constraint not considered in the theoretical analysis of local SGDA+ and FedSGDA++ FedSGDA+ still shows better performance compared with local SGDA+.
The network has 20 clients. The datasets are partitioned into disjoint sets across all clients and each client holds part of the data from all the classes (34). We initialize the renset18 with pre- trained weights in PyTorch. In experiments, we run grid search for step size, and choose the step size for primal variable in the set {0.01, 0.03, 0.05, 0.1, 0.33 and that for dual variable in the {0.001, 0.01, 0.1}. We choose the global step size in the set (0.1, 0.5, 1, 1.5, 2}. The batch-size b is 50 and the inner loop number Q is seleted from {20, 50, 100). The outer loop number is selected from {1, 5, 10} for FedSGDA+ and {1, 5, 10, Q} for local SGDA+.
Figure shows that FedSGDA+ has better convergence our algorithm can effectively accelerate SGDA by using the structure of federated learning. Due to the page limititation, the ablation analysis of step size presented in the supplementary materials.
than local SGDAA+ This confirms that
Test Accuracy
Teot Rocouraat
Test Accuracy
ba-
Local SGDA+ 10 20
Local BODA+ (0 20)
Local SODA+ (Q 20)
FedEGDA: 10 20)
FedBGDA: (2 20)
FedSGDA: (Q 20)
Local SCDA+ (0 = 50)
Local SGDA+ (2 50)
t
Local SCDA+ (D 60)
FedSCDA 10 50)
FedSGDA (2 50)
FedSGDA: (D 60)
Local SODA+ 10 - 100)
Local SCDA+ (2 100)
Local SCDA+ (Q 100)
FedSCDDA+ - 100)
FedSGDA+ (0 = 109
FedSCDAA (0
Communication Round
Communication Round
Communication
(a) Fashion-MNIST
(b) CIFAR-10
(C) Tiny ImageNet
Figure 1: Test Accuracy vs the number of communication rounds during the training phase.
4.2 AUROC Maximization
showed the AUROC maximization problem could be reformulated as the non-convex-strongly concave minimax optimization, as below:
39
N Ee.~D. [fr (m, a, E)
min mer'
max WER
(6)
N
ER.

---

where
f (m, b, () (1 p) (h (m:x) aa²² 1rr=1] + (h (m: - b)2 I/u-
+ 2(1 whtp (m:x] 4 - (1 (1-p) -p (m, x) [p==1] p(1 p)w?
& (x.y) D; denotes a random data point and x represents the data features and E ) 1-1++1) is the label. h(m; x) denotes the prediction score of the data point x calculated by a model with parameter m. p Pr(y 1) = [y denotes the prior probability of the positive data.
600
AUROC
AUROC
Local SGDA
Local SGDA
Local SGDA
GODA+
GODA.
CODA.
Momentum SODA
Momentum SODA
Momentum BODA
CODASCA
64
CODASCA
CODASCA
SAGDA
SAGDA
640
SAGDA
FedSCDA-M
Fed5CDA-M
FadSCDA-M
Communication Round
Communication
Communication Round
(a) Fashion-MNIST
(b) CIFAR-10
(c) Tiny ImageNet
Figure 2: AUROC scores on the test datasets vs the number of communication rounds during the training phase.
Following 19 67 constructed the imbalanced binary-class versions of datasets follow: firstly, the first half of the classes (0 - 4) in the original Fashion-MNIST, CIFARIO and classes (0 99) in Tiny-ImageNet datasets are converted into the negative class, and the rest half of classes are considered to be a positive class. 80% of the negative data points are randomly dropped in each dataset. Then the datasets evenly divided into disjoint sets across 16 clients. In this case, each clients share completely different imbalanced datasets. In the experiment, we use xavier normal initialization deep models.
compare our algorithm (i.e.. FedSGDA-M) with local SGDA 10 50), CODA+ 19 67 Mo- mentum SGDA [50], CODASCA (67] and SAGDA [63] as baselines in AUROC maximization. In experiments, we carefully tune hyperparameters for all methods. We run a grid search for step size, and choose the step size for the primal variable in the set {0.001, 0.005, 0.01} } and that for dual variable in the set {0.0001, 0,001, 0.01}. We choose the global step size from {0.9, 1, 1.5, 2} for CODASCA and SAGDA. We choose the momentum parameter in Local Momentum SGDA in the set {0.1 1, 0.5, 0.9}. The a and / in FedSGDA-M are chosen from {0.1, 0.5, 0.9). The batch-size is 50 and the inner loop number E {10, 50).
As shown Figure 2 we compare the performance FedSGDA-M and other baseline methods against the number of communication rounds. Figure 2 shows that our algorithms consistently outperform the other baseline algorithms on testing datasets, which validates the efficacy of our algorithms. Due space limitation, other test results provided in the supplementary materials.
Limitation. Minimax optimization has many applications and more comprehensive discussion of our proposed algorithms on these tasks will be a futuree study because the theoretical analysis is the main contribution of this paper.
Conclusion
In this paper, we study a class of federated nonconvex minimax optimization problems ( We consider the three most common settings (NC-SC, NC-PL, NC-C). Under the NC-C setting, we propose FedSGDA+ and prove it has the best communication complexity of O(=-0). It also achieves a linear speedup to the number of clients. Under NC-PL and NC-PL settings, we propose FedSGDA- M with variance reduction technique and we prove that our algorithm (FedSGDA-M has the best sample complexity (O
and the best sample communication complexity (0)) We prove that FedSGDA also enjoys linear speedup with respect to the number of clients. Therefore, we reduce the existing complexity results for the most common nonconvex minimax optimization problems under the federated learning setting.
10

---

References
[1] Zeyuan Alien-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[2] Runxue Bao, Bin Gu, and Heng Huang, An accelerated doubly stochastic gradient method with fäster explicit model identification. In Proceedings of the 31st ACM International Conference Information & Knowledge Management, pages 57-66, 2022.
[3] Runxue Bao, Xidong Wu, Wenhan Xian, and Heng Huang. Doubly sparse asynchronous learning for stochastic composite optimization. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI, pages 1916-1922, 2022.
[4] Alcksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Scbastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. arXiv preprint wrw.::2106.0....mmmm 183 2021.
[5] Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge global optima. In International Conference on Machine Learning, pages 745-754. PMLR, 2018.
[6] Lesi Chen, Boyuan Yao, and Luo Luo. Faster stochastic algorithus for minimax optimization under polyak-('L) ojasiewicz condition. Advances Neural Information Processing Systems. 35:13921-13932. 2022.
[7] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. Advances neural information processing systems, 32, 2019.
[8] Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, and Inderjit S Dhillon. Improved convergence rates for non-convex federated learning with compression. arXiv e-prints, pages arXiv-2012, 2020.
[9] Damek Davis and Dmitriy Drusvyatskiy, Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-239) 2019.
[10] Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference Artificial Intelligence and Statistics, pages 1387-1395. PMLR, 2021.
[11] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. arXiv preprint arXiv: /2660, 2021.
[12] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured minconvex-nonconece min-max optimization. In International Conference on Artificial Intelligence and Statistics, pages 2746-2754, PMLR, 2021.
[13] Cong Fang. Chris Junchi Li. Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018
[14] Tanner Fiez, Lillian Ratliff, Eric Mazumdar, Evan Faulkner, and Adhyyan Narang. Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games. Advances in Neural Information Processing Systems, 0-220499-20663 2021.
[15] Hongchang Gao, Junyi Li, and Heng Huang. On the convergence of local stochastic compositional gradient descent with momentum. In International Conference Machine Learning, pages 7017-7035. PMI., 2022.
[16] lan Goodfellow, Jean Pouget-Abadis Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672 2680, 2014.
[17] Bin Gu, Runxue Bao, Chenkang Zhang, and Heng Huang, New scalable and efficient online pairwise learning algorithm. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[18] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
[19] Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Communication- efficient distributed stochastic auc maximization with deep neural networks. In International Conference Machine Learning, pages
PMLR, 2020.

---

[20] Zhishuai Guo. Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family and beyond. arXiv preprint arXiv:2104.14440 2021.
[21] Zhishuai Guo, Rong Jin, Jiebo Luo, and Tianhao Yang. Fedxl: Provable federated learning for deep x-risk optimization. 2023.
[22] Songyang Han, Sanbao Su, Sihong He, Shuo Han, Haizhao Yang, and Fei Miao. What is the solution for state adversarial multi-agent reinforcement learning? arXiv preprint ar arXiv:2212.02705, 2022.
[23] Huan He, Shifan Zhao, Yuanzhe Xi, Joyce Ho, and Yousef Saad. Gda-am: On the effectiveness of solving min-imax optimization via anderson mixing. In International Conference on Learning Representations, 2021.
[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pages 770-778, 2016.
[25] Sihong He, Songyang Han, Sanhao Su, Shuo Han, Shaofeng Zou, and Fei Miao. Robust multi-agent reinforcement learning with state uncertainty. Transactions on Machine Learning Research, 2023, ISSN 2835-8856. URL htthttps:
[26] Charlic Hou, Kiran K Thekumparampil. Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint /02.0033, 2021.
[27] Feihu Huang and Songean Chen. Near-optimal decentralized momentum method for nonconvex-pl minimax problems, arXiv preprint arXiv:2304. 10902, 2023.
[28] Feihu Huang. Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances Neural Information Processing Systems, 34: 10431-104443 2021.
[29] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization. J. Mach. Learn. Res., 23:36 2022.
[30] Feihu Huang, Xidong Wu, and Zhengmian Hu. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 2365-2389. PMLR, 2023.
[31] Chi Jin, Pranceth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv:1902.00618. 2019.
[32] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008. 000000 2020.
[33] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national conference on machine learning, pages 5132 5143, PMLR, 2020.
[34] Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and com- munication complexities for federated learning. Advances in Neural Information Processing Systems, 34, 2021.
[35] Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving conconvex-concave min-max problems. SIAM Journal on Optimization, 31(4):2558 2585, 2021.
[36] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Muchine learning and systems. 2:429-450. 2020.
[37] Luofeng Liao, Li Shen, Jia Duan, Mladen Kolar, and Dacheng Tao. Local adagrad typpe algorithm for stochastic convex-concave minimax problems. arXiv preprint arXiv:2 106. 10022, 2021.
[38] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-come wwn.cve minimax problems. In International Conference on Machine Learning, pages 6083-6093 PMLR, 2020.
[39] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianhao Yang. Stochastic auc maximization with deep neural networks. arXiv preprint erXiv: 10831, 2019.
[40] Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jarret Ross, Tianbao Yang, and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. Advances in Newral Information Processing Systems, 18:11056-1101 2020.
12

---

[41] Zhuging Liu, Xin Zhang, Songtao Lu, and Jia Liu. Precision: Decentralized constrained min-max learning with low communication and sample complexities. arXiv preprini arXiv:2303.02533 022332,... 2023.
[42] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-stronglle strongly-concave minimax problems. Advances in Neural Information Processing Systems, 33:20566 20577, 2020.
[43] Pouria Mahdavinia, Yuyang Deng, Haochuan Li, and Mehrdad Mahdavi. Tight analysis of extra gradient and optimistic gradient methods for nonconvex minimax problems. Advances in Neural Information Processing Systems, 35:31213 31225, 2022.
[44] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-ceffccnn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273 1282. PMLR, 2017.
[45] Maher Nouiched, Maziar Sanjahi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. Advances in Neurol Information Processing Systems, 32, 2019.
[46] H Rafique, M Liu, Q Lin, and T Yang. Non-convex min-max optimization: provable algorithms and applications in machine learning. arXiv preprint arXiv: 1810000000 2018.
[47] Mohammad Rasouli, Tao Sun, and Ram Rajagopal. Fedgan: Federated generative adversarial networks for distributed data, arXiv preprint arXiv:2006.07223 2020.
[48] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
[49] Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts, Advances in Neural Information Processing Systems, 33:21554-22155 2020.
[50] Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, pages 16683-19700 PMLR, 2022.
[51] Pranay Sharma, Rohan Panda, and Gauri Joshi. Federated minimax optimization with client heterogeneity. arXiv preprint 2:224:2.302.044499 2023.
[52] Zhenyu Sun and Ermin Wei. A communication -effffcciaatttneefcietttttt algorithm with linear convergence for federated minimax learning. arXiv preprint arXiv:2206.01 132, 2022.
[53] Davoud Atace Tarzanagh, Mingehen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. International Conference on Machine Learning, pages 21 146-21179. PMLR, 2022.
[54] Kiran Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
[55] Hoi-To Wai, Mingyi Hong, Zhuoran Yang. Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32: 5784-5795, 2019.
[56] Jingkang Wang, Tianyun Zhang, Sijia Liu, Pin- Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li. Adversarial attack generation empowered by min-max optimization. Advunces in Neural Information Processing Systems, 34:1 34:16020-166 16033, 2021.
[57] Xidong Wu, Zhengmian Hu, and Heng Huang. Decentralized riemannian algorithu for nonconvex minimax problems. arXiv preprint arXiv:2302.0388 2023.
[58] Xidong Wu, Feihu Huang, Zhengmian Hu, and Heng Huang. Faster adaptive federated learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 10379 10387, 2023.
[59] Xidong Wu, Jianhui Sun, Zhengmian Hu, Junyi Li. Aidong Zhang, and Heng Huang. Federated conditional stochastic optimization. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
[60] Yihan Wu, Hongyang Zhang, and Heng Huang. Retrievalguard: Provably robust 1 1-nearest neighbor image retrieval. In International Conference Machine Learning, pages 24266 222299. PMLR, 2022.
13

---

[61] Yihan Wu, Aleksandar Bojchevski, and Heng Huang. Adversarial weight perturbation improves generaliza- tion in graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 10417-10425, 2023.
[62] Wenhan Xian, Feihu Huang. Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. Advances Neural Information Processing Systems, 34:25865-25877. 2021.
[63] Haibo Yang. Zhuqing Liu, Xin Zhang, Jia Liu, Sagda: Achieving O(e ²) communication complexity in federated min-max max leamning. arXiv preprint arXiv:2210.0611,, 2022.
[64] Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance reduction for a class nonconvex-moncooaan minimax problems. Advances in Neural Information Processing Systemx, 33: 1153-1165, 2020.
[65] Junchi Yang, Xiang Li, and Niao He. Nest your adaptive algorithm for parameter-agnostie agnostic nonconvex minimax optimization. arXiv preprint arXiv:2206.00777 2022.
[66] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pages 5485 5517. PMLR, 2022.
[67] Zhuoning Yuan, Zhishuai Guo. Yi Xu. Yiming Ying, and Tianbao Yang. Federated deep auc maximization for hetergencous data with constant communication complexity. In International Conference Machine Learning, pages 12219- 12229. PMLR, 2021.
[68] Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communication and sam- ple complexities decentralized policy evaluation cooperative multi-agent reinforcement learning. Advances Neural Information Processing Systems, 34: 18:1888--11 18838, 2021.
14818885-18888
[69] Xuan Zhang, Needet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+; An accelerated stochastic method for nonconvex-conee concave minimax problems. arXiv preprint arXiv:2205. 2022.
[70] Zhengmian, Wu Xidong, Huang Heng. Beyond lipschitz smoothness: tighter analysis for nonconvex optimization. In International Conference on Machine Learning (ICML), 2023.
[71] Hanhan Zhou, Tian Lan, Guru Prasadh Venkataramani, Wenbo Ding. Federated learning with online adaptive heterogeneous local models. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurlPS 2022), 2022.
[72] Hanhan Zhou, Tian Lan, Guru Prasadh Venkataramani, and Wenbo Ding. Every parameter matters: Ensuring the convergence of federated learning with dynamic heterogeneous models reduction. In Advances in Neural Information Processing Systems, volume 36, 2023.
14


Reviews:
[{"review_id": "p5PCAQHEvg", "reviewer": "Reviewer_uFXg", "summary": "Authors propose federated stochastic gradient descent-ascent method for solving minimax problems in federated learning setting and demonstrate that oracle and communication complexity of their method is significantly better than that of analogues in nonconvex-(concave/non-concave/PL) cases with respect to dependence on desired accuracy.", "questions": "I suggest authors to reflect deviation of accuracy for runs with different realisations of randomness on their figures in addition to particular realisation of convergence curve — for example, with shadow. Its important for understanding stability of advantage of the proposed method. And maybe the title should be changed to correctly reflect the content of the paper: \"solving a class\" seems to have unclear meaning, etc.", "limitations": "Everything is okay.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Theoretical analysis of the proposed method shows that its complexity is the best among alternatives, construction of the algorithm is simple enough, important practical cases of nonconvex and PL functions are considered. ", "weaknesses": "I guess, within the goals of the paper there are no significant weaknesses: theoretical results are good and well-justified, minimal experiments confirm the advantages of the proposed method.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your appreciation. I will add extra deviation of accuracy in the final version and modify the paper according to your suggestion. Thanks!\n\n"}, {"review_id": "ypUaS5ZXXT", "reviewer": "Reviewer_7re5", "summary": "This paper studied a class of federated nonconvex minimax optimization problems. Authors proposed FL algorithms and provided sample complexity under three different settings including nonconvex-concave, nonconvex-strongly conconcave, and nonconvex-PL conditioned. Authors showed that derived rates has the best sample complexity. Experimental results demonstrated the superiority. ", "questions": "See above", "limitations": "Authors discussed limitations, although generic. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis is one main contribution of this paper. It's nontrivial to derive sample complexity for different settings. \n2. Experiments also validated the efficacy of proposed algorithms. \n3. Code is available and looks neat.  ", "weaknesses": "I have a major concern regarding the discussion and comparison of existing works in the paper. Specifically, when addressing local algorithms, the authors solely focus on SGDA (with and without momentum), which is considered a classical and relatively old algorithm. However, it is worth noting that several recent works have demonstrated improvements in convergence rates. For instance, in [1], Section 4.2 provides insights into enhanced rates, while [2] presents Theorems C.9 that showcase accelerated convergence rates for convex-nonconcave minimax problems. Additionally, [3] introduces Theorem 4.1, which is relevant to this discussion. Although these works may not directly address federated learning, their findings on accelerated convergence rates for general minimax problems should be brought into the discussion to avoid confusion among readers in the future.\n\n### reference:\n1. Mahdavinia et.al., Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems\n2. He et.al., GDA-AM: ON THE EFFECTIVENESS OF SOLVING MIN-IMAX OPTIMIZATION VIA ANDERSON MIXING, ICLR 2022\n3  Lee et.al., Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems, Neurips 2021\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your valuable and constructive comments!\n\n>Q1. \" ... existing works in the paper ... Although these works may not directly address federated learning, their findings on accelerated convergence rates for general minimax problems \"\n\nThanks a lot for your suggestions. Due to page limitations, we pay more attention to FL minimax works. I added these minimax works in Sec 2.1 Single-Machine Minimax. Given that we cannot resubmit the new version, we will present them in the final version.\n\n"}, {"review_id": "egWrKJG0qK", "reviewer": "Reviewer_sra2", "summary": "(1) This paper describes two algorithms, FedSGDA+ and FedSGDA-M, for solving non-convex minimax optimization problems. \n(2) Theoretical guarantees are establised for these two algorithms, under several assumptions.\n(3) Empirical tests are conducted.", "questions": "I have detailed the issues I identified as weaknesses in the previous message. Please address these questions I posed to them.", "limitations": "Yes, they have.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**Originality:**\n\nThe techniques used in this paper are not novel from an optimization perspective. However, they can indeed be applied to minimax problems and have a theoretical bound.\n \n**Quality:**\n\nThe notations, problem statements, and mathematical proofs appear rigorous, although I have not scrutinized them word by word.\n \n**Clarity:**\n\nThe readability of this article is good.\n \n**Significance:**\n\nThis paper provides agorithms with better convergence rates (although some extra assumptions were made in the paper, ). The techniques (and tricks) may inspire and guide future researchers.", "weaknesses": "1. The algorithms described in \"Federated minimax optimization: Improved convergence analyses and algorithms\" [36] and the ones in this paper are very similar. Specifically, FedSGDA-M and Local SGDA-M in [36] are basically the same, and the difference between FedSGDA+ and Local SGDA in [36] is very small, only in the step size, which may not be the most crucial part of the FedSGDA+ algorithm. Therefore, I believe that there is not much improvement in the algorithm aspect of the paper.\n \n2. On the other hand, the convergence rates established in this paper appear to be better than previous algorithms, but the assumptions used are different from those of the previous. Thus, this comparison seems somewhat unfair and does not necessarily indicate a substantial improvement in convergence rates.\n \n3. As for the experiments, firstly, this paper does not describe whether the experimental settings conform to the theoretical assumptions, so it is unclear whether the empirical studies can support the theoretical results. Secondly, the relationship between the complexity established in this paper and the number of worker nodes is not reflected in the experiments. Lastly, only Local SGDA was put into the experimental baseline set, and some algorithms that perform well in this field, such as FEDNEST and SAGDA, unfortunately did not become the experimental baselines.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition of the quality, clarity, and significance of our paper. \n\n>Q1. \"... FedSGDA-M and Local SGDA-M in [1] are basically the same, and the difference between FedSGDA+ and Local SGDA in [1] is very small, ...\"\n\nI respectively disagree with this statement. SGDA is a very classical algorithm in minimax optimization and many minimax algorithms are designed based on it. 1) Although both FedSGDA-M and Local SGDA-M are momentum-based algorithms, they are completely different since our FedSGDA-M introduces a momentum-based variance reduction technique, and reduces communication complexity and sample complexity. 2) FedSGDA+ and Local SGDA+ are both used for NC-C settings but the introduction of global learning in FedSGDA+  obviously improves the communication complexity. It should be mentioned that Local SGDA+  in [1] is from [2] but it provides a better theoretical analysis. Since [1] does not come up with a new algorithm for NC-C setting,  the convergence rate of Local SGDA+ cannot match our results.  \n\n>Q2. \"... the assumptions used are different from those of the previous. ...\"\n\nThe assumption for FedSGDA+ and Local SGDA+ are $\\textbf{completely same}$. Although Assumption Assumption 3.11. is different from the one used in [1], it is still a widely used assumption in optimization analysis. Many typical centralized stochastic algorithms use this assumption, such as SREDA [3], and VR-SMDA [4]. Similarly, it is also used in FL algorithms such as MIME [5] and Stem [6].\n\n>Q3. \"... experimental settings  ...\"\n\nWe consider two tasks. 1) Fair Classification is from [1] and since FedSGDA+ and Local SGDA+ use the same assumptions, we compare these two methods in NC-C settings. 2) AUPRC maximization is from [7]. Since [7] not only uses a similar assumption (Assumption 1 (iv)), but uses a stronger assumption (Assumption 1 (ii)), we use this task to evaluate our algorithms.\n\n> Q4. \"... the relationship between the complexity established in this paper and the number of worker nodes is not reflected in the experiments ...\"\n\nI provide the theoretical analysis in our works. Since we cannot upload the images in rebuttal, we will add it in final version.\n\n> Q5  \"... only Local SGDA was put into the experimental baseline set... \"\n\nI completely disagree with the statements. I politely remind you that Local SGDA and Local SGDA+ in [1] are two different algorithms and only Local SGDA+ is used for NC-C setting [1]. SAGDA [8] considers the NC-PL setting and cannot be used for NC-C setting. This is why we only use Local SGDA+ as a baseline in Fair Classification. In the AUROC Maximization tasks, we use local SGDA, CODA+, Momentum SGDA, CODASCA, and SAGDA as baselines, not only Local SGDA. \n\n[1] P. Sharma, R. Panda, G. Joshi, and P. Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, pages 19683–19730. PMLR,387 2022\n\n[2] Y. Deng and M. Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pages 1387–1395. PMLR, 2021.\n\n[3] Luo, L., Ye, H., Huang, Z. and Zhang, T., 2020. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems. Advances in Neural Information Processing Systems, 33.\n\n[4] Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances in Neural Information Processing Systems, 34, 2021.\n\n[5] Karimireddy, S.P., Jaggi, M., Kale, S., Mohri, M., Reddi, S.J., Stich, S.U. and Suresh, A.T., 2020. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03606.\n\n[6] Khanduri, P., Sharma, P., Yang, H., Hong, M., Liu, J., Rajawat, K. and Varshney, P., 2021. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning. Advances in Neural Information Processing Systems, 34, pp.6050-6061.\n\n[7] Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, Tianbao Yang. Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks. ICML 2020\n\n[8] Yang, Haibo, Zhuqing Liu, Xin Zhang, and Jia Liu. \"SAGDA: Achieving \n Communication Complexity in Federated Min-Max Learning.\" arXiv preprint arXiv:2210.00611 (2022). https://openreview.net/pdf?id=wTp4KgVIJ5\n\n"}, {"review_id": "Gj5kF92EUs", "reviewer": "Reviewer_Nj11", "summary": "this paper proposed new algorithms for solving federated minimax problems in both nonconvex concave and nonconvex PL (or strongly concave) settings under the assumption of data heterogeneity. the authors propose a novel way to incorporate the variance reduction technique into the federated setting and provide solid convergence analysis in both settings. numerical experiments on auc maximization and fairness problems are reported to show the advantage of the proposed algorithms.", "questions": "both algorithms in this paper use the same batch data to compute the x gradient and the y gradient. in that case, those gradients (\\nabla_x f and \\nabla_y f) are not independent of each other. will this cause problems in the proof? can the author double-check?", "limitations": "the algorithm names in the table are not consistent with the names in the algorithms.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. the proposed algorithms achieve the best convergence rate compared with existing works in the same setting. the final rate comes with linear speedup under the heterogeneous setting.\n2. the idea of updating y with a fixed x in the concave case helps to improve communication complexity.\n3. the numerical experiments are convincing. the authors compare with the majority of existing works.\n4. the paper is easy to follow.", "weaknesses": "the step size \\eta needs to be very small to guarantee the convergence since it's inverse propositional to q, the local updates. this requirement hurts the performance in practice", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your time and comments.\n\n> Q1. \"the step size \\eta needs to be very small to guarantee the convergence since it's inverse propositional to q, ....\"\n\nThanks for your mention. The relationship between learning rate $\\eta$ and local training iterations q is easy to understand because if we do not put a restriction on the learning rate, a large q will lead to divergence due to client drift in federated learning. In addition, this relationship is common in federated learning. Such as Corollary1 in [1] $\\eta_l = \\Theta (1/KL \\sqrt{T})$ where K is the local update and Theorem 1 in [2] shows that $\\eta_y \\leq \\frac{1}{8L_f \\tau}, \\frac{\\eta_x}{\\eta_y} \\leq \\frac{1}{8\\kappa^2} $ where $\\tau$ is the local training iterations. The relationship between the local step size and the local training iterations guarantees convergence.\n\n> Q2. \"... those gradients (\\nabla_x f and \\nabla_y f) are not independent of each other ...\"\n\nThis has brought significant challenges to the proof and thus some works use double-loop architecture, namely multiple samples and update for y but only one step for x.  We use simpler single-loop architecture. We use \\nabla_x f and \\nabla_y f to update x and y, separately. Lemma B.1, Lemma B.3 and Lemma C.2, Lemma C.3 show how to balance variable x and y.  This challenge also shows the value of our work. \n\n\n[1] Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S. and McMahan, H.B., 2020. Adaptive federated optimization. https://arxiv.org/pdf/2003.00295.pdf.\n\n[2] Sharma, P., Panda, R., Joshi, G. and Varshney, P., 2022, June. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning (pp. 19683-19730). PMLR. https://proceedings.mlr.press/v162/sharma22c/sharma22c.pdf\n\n"}, {"review_id": "nHyzK7F8YN", "reviewer": "Reviewer_dmWe", "summary": "The paper focuses on the minimax optimization problem within the context of the federated learning framework. In order to address this problem, the authors introduced two algorithms named as FedSGDA+ and FedSGDA-M, to handle distinct types of losses, specifically focusing on the concavity of the maximizer component. The study presented a comprehensive analysis encompassing both theoretical and numerical evaluations.", "questions": "see weakness", "limitations": "\nThe author acknowledged the need for further numerical studies and a more comprehensive analysis as a limitation of the paper. Since the research primarily focuses on theoretical algorithm development, there is no anticipated potential for negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper contributed two novel algorithms to solve various types of minimax optimization problems within the federated learning framework, which holds significant impact. As many machine learning problems are closely tied to minimax optimization, the developed algorithms offer valuable solutions for a wide range of applications. The solid theoretical analysis not only validates the effectiveness of their proposed algorithms but also lays a foundation for future investigations in the fields of minimax optimization and federated learning. ", "weaknesses": "The paper needs presentation improvement as well as more clarification in the motivation and algorithm development. \n\nCurrently, I am inclining towards border acceptance with my questions below. I encourage authors to provide responses for my better assessment.\n\n1. Line 27-29: The authors claim the federated learning is proposed to tackle the communication issue. But to my best knowledge, the federated learning has many advantages such as local data privacy preserving, utilizing more clients' data and enhancing computation power etc. Only highlighting communication advantages might be one-sided.\n\n2. Line 145: The second inequality in (2) seems to be a strong assumption. It requires the deviation of the local data from the global average  to be bounded. However, under severe data heterogeneity and large parameters magnitude ,  such bound might not hold. Many federated learning works have studied to avoid such assumption, e.g. [1]. Can we also relax this assumption here?\n\n3. Line 167: This assumption seems to be an addition assumption compared with the existing works in Table 1. Basically, it requires the gradient of $F$ w.r.t. $x$ to be bounded. It might not hold for many applications.\n\n4. Wonder whether linear speed up w.r.t. to clients' number hold for this study. Can the authors provide some numerical validation?\n\n5. For the algorithm presentation, can authors separate the server-side and client-side for better understanding?\n\n6. Is FedSGDA-M motivated by the STORM-type of variance reduction method? Why is the algorithm not applicable for NC-C case?\n\n7. Section 4.1: The loss looks be to a constrained one. How do the proposed algorithm hold the constraint?\n\n8. Figure 2: Is FedSGDA in the figure the proposed FedSGDA+ or FedSGDA-M? \n\n9. Can the authors provide numerical studies on the data heterogeneity, clients' number and computation cost?\n\n[1] Karimireddy, Sai Praneeth, et al. \"Scaffold: Stochastic controlled averaging for federated learning.\" International Conference on Machine Learning. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are deeply thankful for your time and comments.\n\n> Q1. \"The authors claim the federated learning is proposed to tackle the communication issue...\"\n\nThanks for your suggestion. Due to page limitation, I mention parts of advantages of FL, such as communication issue in Line 27 and privacy in Line 32. I will add more details about the advantages of FL. \n\n> Q2. \"Line 145: The second inequality in (2) seems to be a strong assumption ... \". Many federated learning works have studied to avoid such assumption, e.g. [1] ... \n\nVariance Bound assumption is a popular assumption in federated optimization. [1] use \n\n> Q3. Line 167: This assumption seems to be an addition assumption compared with the existing works in Table 1.\n\nThis assumption is used for the theoretical analysis in NC-C setting. We follow the only NC-C algorithm Local SGDA+ [2] in Table 1 and please see Assumption 6 in [2]. \n\n> Q4. Wonder whether linear speed up w.r.t. to clients' number hold for this study.\n\nRemark 3.8 and Remark 3.14 show our two algorithms have linear speedup with respect to the number of worker nodes. \n\n> Q5. For the algorithm presentation, can authors separate the server-side and client-side for better understanding?\n\nThanks for your suggestion. Because we only do average operation on the server, so we use denotes it as test mod (t, Q) = 0 in the Line 11 in algorithm 1 and Line 5 in the algorithm 2. \n\n> Q6. Is FedSGDA-M motivated by the STORM-type of variance reduction method? Why is the algorithm not applicable for NC-C case?\n\nFedSGDA-M uses a STORM-type variance reduction technique. The study of its application in NC-C case is in progress. \n\n> Q7. Section 4.1: The loss looks be to a constrained one. How do the proposed algorithm hold the constraint?\n\nWe follow the task in [2] and constrained is not considered in the algorithm. \n\n> Q8. Figure 2: Is FedSGDA in the figure the proposed FedSGDA+ or FedSGDA-M?\n\nThanks for the reminding. This is a typo. FedSGDA in the figure is FedSGDA-M. \n\n\n\n[1] Karimireddy, Sai Praneeth, et al. \"Scaffold: Stochastic controlled averaging for federated learning.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] P. Sharma, R. Panda, G. Joshi, and P. Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, pages 19683–19730. PMLR,387 2022. https://proceedings.mlr.press/v162/sharma22c/sharma22c.pdf"}]

Author rebuttal:

Meta-review: Dear Authors,

Thank you for submitting your paper on non-convex minimax optimization in federated learning. The paper received some positive feedback; the reviewers appreciated the simple construction of your algorithm, the theoretical analysis, and the experiments that confirm the efficiency of your method.

I would also like to point out that your paper contains many weaknesses. Luckily, during the rebuttal phase, you addressed most of the concerns from the reviewers, but please make sure to incorporate them into the final version.

Best, 

AC
Decision: Accept (poster)