A Single-Loop Accelerated Extra-Gradient Difference Algorithm with Improved Complexity Bounds for Constrained Minimax Optimization
Authors: Yuanyuan Liu
Fanhua Shang
Weixin An
Junhao Liu
Hongying Liu
Zhouchen Lin
Venue: NeurIPS 2023 oral (2023)
Keywords: Constrained Minimax Optimization; nonconvex- nonconcave

Abstract: In this paper, we propose a novel extra-gradient difference acceleration algorithm for solving constrained nonconvex-nonconcave (NC-NC) minimax problems. In particular, we design a new extra-gradient difference step to obtain an important quasi-cocoercivity property, which plays a key role to significantly improve the convergence rate in the constrained NC-NC setting without additional structural assumption. Then momentum acceleration is also introduced into our dual accelerating update step. Moreover, we prove that, to find an $\epsilon$-stationary point of the function $f$, our algorithm attains the complexity $\mathcal{O}(\epsilon^{-2})$ in the constrained NC-NC setting, while the best-known complexity bound is $\widetilde{\mathcal{O}}(\epsilon^{-4})$, where $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic factors compared to $\mathcal{O}(\cdot)$. As the special cases of the constrained NC-NC setting, our algorithm can also obtain the same complexity $\mathcal{O}(\epsilon^{-2})$ for both the nonconvex-concave (NC-C) and convex-nonconcave (C-NC) cases, while the best-known complexity bounds are $\widetilde{\mathcal{O}}(\epsilon^{-2.5})$ for the NC-C case and $\widetilde{\mathcal{O}}(\epsilon^{-4})$ for the C-NC case. For fair comparison with existing algorithms, we also analyze the complexity bound to find $\epsilon$-stationary point of the primal function $\phi$ for the constrained NC-C problem, which shows that our algorithm can improve the complexity bound from $\widetilde{\mathcal{O}}(\epsilon^{-3})$ to $\mathcal{O}(\epsilon^{-2})$. To the best of our knowledge, this is the first time that the proposed algorithm improves the best-known complexity bounds from $\mathcal{O}(\epsilon^{-4})$ and $\widetilde{\mathcal{O}}(\epsilon^{-3})$ to $\mathcal{O}(\epsilon^{-2})$ in both the NC-NC and NC-C settings.

A Single-Loop Accelerated Extra-Gradient Difference Algorithm with Improved Complexity Bounds for Constrained Minimax Optimization
Yuanyuan Liu', Fanhua Shang?; Weixin Junhao Liu', Hongying L Zhouchen Lin
Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, School Artificial Intelligence, Xidian University, China School of Computer Science and Technology, College of Intelligence and Computing, Tianjin University Medical College, Tianjin University, China
National Key Lab of General AI, School of Intelligence Science and Technology, Peking University 'Institute for Artificial Intelligence, Peking University
Peng Cheng Laboratory
yyliu@xidian.edi edu. en, fhshang@tju. edu. cn, hyliu2009@t ju. edu. zlin@pku. edu. cn
Abstract
this paper, we propose a novel extra- graddett difference acceleration algorithm for solving constrained nonconvex-moncoocavee (NC-NC) minimax problems. In particular, we design a new extra extra-gradient difference step to obtain an important quasi-cocoercivity property, which plays key role significantly improve the convergence rate in the constrained NC-NC setting without additional structural assumption. Then momentum acceleration is also introduced into dual ac- celerating update step. Moreover, we prove that, to find an e-stationary point of the function f. the proposed algorithm attains the complexity O(e 2) in the constrained NC-NC setting, while the best-known complexity bound Ö(E 4),, where (-) hides logarithmic factors compared to O-)). As the special cases of the constrained NC-NC setting, the proposed algorithm can also obtain the same com- plexity ( ?) for both the nonconvex eineconnvx-concave (NC-C) and menvex-nonconcawe (C-NC) cases, while the best-known complexity bounds are ((55) for the NC-C case and ((e-4) for the C-NC case. For fair comparison with existing algorithms, we also analyze the complexity bound to find e-stationary point of the primal function é for the constrained NC-C problem, which shows that our algorithm can improve the complexity bound from Ö(E-") to O(e-2). To the best of our knowl- edge, this is the first time that the proposed algorithm improves the best-known complexity bounds from Ō(E-4) and ((e -3) O 2) in both the NC-NC and NC-C settings.
Introduction
This paper considers the following smooth minimax optimization problem,
min max f(x, v), z yey
(I)
"Corresponding authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where X' S Rn and Y S R" are nonempty closed and convex feasible sets, and f R" x E. + R is smooth function. In recent years, this problem has drawn considerable interest from machine learning and other engineering communities such as generative adversarial networks [14), adversarial machine learning [55] 28), game theory 3 reinforcement learning [2 empirical
risk minimization [54, 39. and robust optimization 36 13 [] While there is an extensive body
of literature on minimax optimization, most prior works such as [54] 39 42 33 50] focus on the
convex-concave setting, where f(z, y) is convex in and concave in y. However, in many nonconvex minimax machine learning problems as in [35] 61 ((z y) is nonconvex in x and (strongly) concave in y. or f(z, y) is (strongly) convex in and nonconcave in y. For
(NC-SC) minimax problems, a number of efficient algorithms such as [34 25 27
were proposed.
and their complexity can be O for achieving an e-stationary point & (e.g., V S e) of
the primal function Φ(-) := maxyey (,) where Ky is the condition number for f(x; -), and Ó hides logarithmic factors. More recently, 24 proposed an accelerated algorithm, which improves the gradient complexity to Ö(FRFE which exactly matches the lower complexity bound in [52 23]. Therefore, we mainly consider the problem TT in nonconvex-nonconeau (NC-NC), nonconvex-
concave (NC-C) and convex-nonconcave (C-NC) settings.
1.1 Algorithms in NC-C and C-NC Settings
For nonconvex-concav (NC-C, but not strongly concave) and convex-nonconcave (C-NC) problems. there are two types of algorithms (i.e., multi-loop (including double-loop and triple-loop) and single-loop algorithms), and most of them are multi-loop algorithms such as [8] 31 40 24,
BT
proposed a multi-step framework that finds an c-first order Nash equilibrium of f(x, y) with the
complexity ((c-3.5) 40 designed proximal dual implieit accelerated algorithm and proved that their algorithm finds an e-stationary point of ó with the complexity Ō(c-3) More recently, [24] proposed an accelerated algorithm, which achieves the complexity Ō(E-2.5) to find an e-stationary point of f. These multi-loop algorithms require at least O outer iterations, and thus their complexities are more than O 2). Even though single-loop methods are more popular in practice due to their simplicity, few single-loop algorithms have been proposed for NC-C setting. The most natural approach is the gradient descent-ascent (GDA) method, which performs a gradient descent step and a gradient ascent step on y each iteration. However, GDA fails to converge for simple bilinear zero-sum games [22]. Subsequently, several improved GDA algorithms such as [8] 2525 27 44 were proposed. For instance, 25 proved that the complexity of their two-time-scale
GDA to find an c-stationary point of ø is O(c ") for NC-C problems. Moreover, [27 presented an efficient algorithm, which obtains an e-stationary point of I with the complexity Ole In fact, the complexity only counts the number of times the maximization subproblem is solved, and does not consider the complexity of solving this subproblem. (44) proposed a unified algorithm, and proved that the complexity of their algorithm to find an e-stationary point of f is O O(e-a) for both NC-C and C-NC problems. More recently. [51] presented a smoothed -DA algorithm and proved that
the complexity can be improved to Olc 2 for optimizing a special case of NC-C problems (i.e., minimizing the pointwise maximum of a finite collection of nonconvex functions). However, its complexity is still O(c-A) for both NC-C and C-NC problems. One natural question is: can design single-loop accelerated algorithm with the optimal complexity bound O(e 2) for both NC-C and C-NC problems?
1.2 Algorithms in NC-NC Settings
This paper mainly considers constrained NC-NC minimax problems, i.c., f(z, v) is nonconvex in x and nonconcave in y in the constrained setting (called constrained NC-NC). In recent years, 38 20 focus on structured NC-NC problems. That is, the saddle gradient operator of such minimax problems or their objectives must satisfy one of the structured assumptions: the minty variational inequality (MVI) condition, the weak MVI condition, or negative comonotone condition and the Sojyak-Lojsieeiczz condition. However, structured NC-NC problems have limited practical applications because they are required to satisfy strong structural assumptions. For more practical constrained NC-NC problems or more general NC-NC problems, the convergence guarantec of the algorithms is still a challenge. In this paper, we also focus on convergence analysis
some works such as 7 31 46

---

Table Comparison of complexities of the minimax algorithms find an e-stationary point of f(::))
in the NC-C, C-NC and NC-NC settings. Note that Smoothed-GDA [5I] can find an e-stationary
point for special problem of (1) with (3)-)) and Ô hides logarithmic factors compared to ((-)
Optimality Criteria
References
NC-C
C-NC NC-NC
Simplicity
Lu et al. 27
O
Single-Loop
Stationarity of f with smoothness and compact sets assumptions
Nouiched al.
31
O 3.5)
Multi-Loop
Lin al. 24
((5))
Multi-Loop
Zhang et al.
5
O(c
Single-Loop
Xu et al.
(
O
Single-Loop
This work (Theorem
1b
(
(
O
Single-Loop
Table 2: Comparison of complexities of existing minimax algorithms and the proposed algorithm to find an of-) == maxzey f(,;8) () in the nonconvex-concave (NC-C) setting. This table only highlights the dependence of and compared with O(.). O()) hides logarithmic factors.
NC-C Settings
References
Compact set
Complexity
Simplicity
Rafique et al. 34 Jin et al.
17
X
Ō
Multi-LLoop
NC-C (Stationarity of ()
Lin et al. 25
N
Ō(c-)
Single-Loop
Thekumprampil et al.
40
X.y
Ö(e-3)
Multi-Loop
Zhao [55], Lin et
N.y
Ō(e-3)
Multi-Loop
This work (Theorem)
y
O
Single-Loop
for solving more practical constrained NC-NC problems. Another natural question is: design a single-loop accelerated algorithm to further improve the bound in the constrained NC-NC setting?
1.3 Motivations and Our Contributions
Motivations: For NC-C minimax problems, can we design single-loop directly accelerated algorith- m with the gradient complexity lower than the best-known result =2253? Though Smoothed -DAA [5T can obtain the complexity ((==2) for special case of Problem [ it only attains the complex- itt O(e-1) for NC-C minimax problems. For C-NC minimax problems, for any given æ, to solve the nonconcave maximization subproblem with respect to y is NP-hard. As result, all existing multi-loop algorithms will lose their theoretical guarantees as discussed in 444. Can we propose single-loop directly accelerated algorithm with the complexity lower than the best-known result O(e for C-NC and NC-NC minimax problems?
Our Contributions:
This paper proposes novel single-loop extra-gradient difference acceleration algorithm to push towards optimal gradient complexities for constrained NC-NC minimax problems ( and answer the
problems.
We summarize the major contributions this paper.
We design a new single-loop accelerating algorithm for solving constrained NC-NC problems. In the proposed algorithm, we design new extra-gradient difference scheme, and combine the gradient ascent and momentum acceleration steps for the dual variable update. In our algorithm, we present an important quasi-cocoereivity property. By leveraging the quasi-cocoercivityy property, we can improve the complexity bound in our theoretical analysis.
We analyze the convergence properties of the proposed algorithm for constrained NC-NC problems. Theorem shows that to find an e-stationary point of f. the proposed algorithm can obtain the gradient complexity OOe=?), which is the first time attains the complexity bound in constrained NC-NC setting. The constrained NC-C and C-NC problems can be viewed as two special cases of the constrained NC-NC problem, and the proposed algorithm is also applicable these two special problems. And its complexity is still O(c-2) for both NC-C and C-NC problems, which significantly improves the gradient complexity from O(e-1) of existing single-loop algorithms or Ö(e -2.5) of existing multi-lopp algorithms to ((e The complexities of some recently proposed algorithms are listed in [
3

---

In order to make a comprehensive comparison with existing algorithms, we also provide the theoretical analysis of our algorithm in terms of another convergence criteria (i.e., an e-stationary point of Φ) for constrained NC-C problems. The result shows that our algorithm improves the best-known result in 40 24
55
from (c (Ec shown in Table 2
2 Preliminaries and Related Works
Notation:
Throughout this paper, we use lower-case letters to denote vectors such as 2, y, and
calligraphic upper-case letters to denote sets such as X, y. For differentiable function f. Vf(x) is the gradient of f at æ. For function f(.--) :) of two variables, (a, y) (or (a, y)) the partial gradient of f with respect to the first variable (or the second variable) at (xr, y). For vector 2, ||=||| denotes its fo-norm. We use Px and Py to denote projections onto the sets and y
Assumption 1 (Smoothness). f(::)) is continuously differentiable, and there exists a positive constant such that
(e.((r V=f 32)ll S D||a1 -2ll, Wff( V. (12, S L 1l
-22l
holds for all 11, E R.",, V1, U2 E R
Definitions of the monotone operators: A operator F(.) R R is monotone, if (F(s) F(t)) -1 1) 2 0, Vs, RR.. If (F()) (s - 0, F is negative monotone. A mapping F()) is co-coercive if there is positive constant a, such that
[F(s) - F(t) t) al F(s) F(t)l,, t
Nonconvex-Concav Minimax Optimization: Due to the nonconvex nature of these minimax problems, finding the global solution is NP-hard in general. The recently proposed algorithms aim to find stationary solutions to such problems. For instance, the first-order Nash equilibrium condition optimality condition in [31]. Besides game stationary, there
(called game stationary) is used two main optimality criteria (i.c., an e-stationary point of f(..) or o(-) == maxzey f(:s y)) for the convergence analysis of the algorithms such [4 24
For solving NC-C minimax problems, there exist a number of efficient multi-loop and single-loop algorithms such as [31] 25 44 24]. Most of them are multi-loop algorithms, which either employ an accelerated update rule of by adding regularization terms to its subproblem, or use multiple gradient ascent steps for the update of solve the subproblem exactly or inexactly. Compared with multi-loop algorithms, single-loop algorithms are easier to implement. One of the most popular single-loop algorithms is GDA. However, GDA with constant stepsize can fail to converge even for a simple bilinear minimax problem [29].
To address this issue, only a few single-loop algorithms such as 25 27
were proposed, and most of them employed a smoothing or proximal point technique. For instance, Smoothed GDGA [51] introduces smooth function (æz, y, 2] = f(x, y) + [|===21l for the update of the primal variable x, where is an auxiliary variable and is a constant, and its main update steps are
Tz+1 = (xx -1 Vusp(z;, Zt: 1/)),, M = (y VyJ (x M))) F++1 = =1 3(x++1 - =2),
where 7/2 Fl > are two stepsizes, and 0 < 3 < 1. Smoothed-GHi can obtain the gradient complexity, OE -), for nonconvex concave minimax problems.
Extra-Gradient Methods: There are some extra-gradient methods such as (48 for solving minimax
problems. Let 7/u and u, be the i-th iterate, the extra-gradient method (53 has the following projection-type prediction-correctoon step:
Prediction "4+1/2 = Ps (wt T)s F(u)), Correction : :441 = Pa (u, - 7/ T (w(41/22)
In this paper, we call 42+1/2 as the prediction point the t-iteration.
3 Single-Loop Extra-Gradient Difference Acceleration Algorithm
In this section, we propose a single-loop Extra-Gradient Difference Acceleration algorithm (EGDA) for solving constrained NC-NC minimax problems.

---

Algorithm EEDAA for NC-NC minimax problems
Initialize: zo: Vo: uo: 1-1/2.7 0.5, ne my. B.
2: for = 0, .,,,,, T - 1 do
3: 1z++1 Px [r 1/s (1),
1 Dt+1 = Tye + (1 - - 114+1
(x+,
4: u++1 1 Ut th V V 1
5: end for
6: Output: (IT, yr).
3.1 Extra-Gradient Difference Acceleration
In recent years, many algorithms such as 27 31 NC-C minimax problems. In essence, most of them are "indirect" acceleration algorithms, which are used to optimize the surrogate functions with a smoothing or proximal point term instead of the original function. However, this may hurt the performance of these algorithms both in theory and in practice 12 J. To address this issue, we propose a single-loop directly accelerating algorithm to find an e-stationary points of [ and ø with a significantly improved complexity (E ((e-)). The main update steps of our EGDA algorithm are designed as follows.
32
24
51
have been proposed for solving
Gradient descent:
Tt-1 arg min (Vr, Be), x) + 1|0- xxl1? -xel= n/a zEX
(2)
Extra-gre gradient difference prediction:
4/+1/2 3/ (V - (x
(3)
Gradient ascent correction:
M++1 = arg max (Vyf 11-12); u² |/ Ve 11 /1///////-
(4)
wEY
Momentum acceleration:
V++ Tyr + (1 T)
(5)
Here, 0 8< 7., 7a, n > 0 are two stepsizes, Ut+1/2; 1 are auxiliary variables, 4/41/2 is prediction point, and 1/2 < r < 1 is momentum parameter. Our EGDA algorithm is formally presented in Algorithm Our EGDA algorithm first performs one proximal gradient descent step on the primal variable æ. and then we design new dual-accelerating scheme in 3 and (5) for the dual variable y.
3.2 Advantages of Our Algorithm and Comparison to Related Work
We first design
prediction point U4+1 /2 in Eq. 33). Compared with extra-gradient-te methods such as 7 16 20, one of the main differences is that the proposed prediction point "1+1/2 in (3)
is updated by the gradient difference (i.c.. (z 14-1/2 - (f 16-1)), while the prediction point in other extra-gradient aita-gradient-type algorithms is updated only by using the gradient information at
the correction point u, Then the gradient at the new prediction point 4/+1/2 is used in the gradient ascent step And the dual variable y is update by the momentum acceleration step in (5).
The monotonicity and co-coercivity properties of gradient operators play crucial role for convergence analysis. However, these important properties do not always hold for nonconvex problems. Some researchers have made great progress in some special nonconvex settings, such structured nonconvex and weakly convex settings, which require weaker condition such as weakly monotone (26), pseudo monotone [16), and MVI [7]. However, such conditions scriously limit the application scope of Problem (I)
Prediction Point:
To address this challenge, design a new prediction point scheme in which can help us obtain a useful cucoe-cocoerycvvity property. As result, it does not require any monotone or structural assumption. Specifically, we find that we only require weaker property in our theoretical analysis, that is, the co-coercivity is required at some special points {4.-1/2, Ve ((V,f(E,, 1/2)
V. (æ ye), uc+1/2 vd) 2 v 22+1/2) Vy (xze 11l with 3 > 0). Thus, we develop
5

---

decoupling idea to construct the prediction point 1/21/2- That is, we use the gradients with respect to y at 4 1,-1/2, 1 instead of those the points 1 yt. We can obtain a property (called the quasi-co-coercivtty) in Section 4.2, which plays key role in our theoretical analysis.
Gradient Difference: We also briefty discuss the underlying intuition of the proposed gradient difference in 33. We find that the proposed update in (3) is similar to the forms in 4 (see Eqs. (12) and (14) 43 [43 proposed a first-order procedure (i.e., difference of gradients) achieve the negative curvature of a Hessian matrix. Therefore, our algorithm has a similar procedure, which contains second-order information. Moreover, we use the difference of gradients in the gradient ascent procedure for the dual update. But our EGDA algorithm only requires the Lipschitz gradient assumption for minimax problems to find first-order stationary points, while [43] requires both the Lipschitz gradient and Lipschitz Hessian assumptions for solving second- codeer stationary points of nonconvex minimization problems.
We design a dual-accelerating update rule in (4) for the dual variable g/ in our EGDA algorithm, which is different from standard momentum acceleration schemes in 31 40 24). That is, the accelerated rules of existing algorithms are for the primal variable x, while our accelerated rule is designed for the dual variable y,
Momentum Acceleration:
Therefore, the proposed new acceleratnn step (including the gradient different prediction step in (3), the gradient ascent correction in 4 and momentum acceleration in (5)) is key accelerated technique for our EGDA algorithm, and can help to improve the complexity bound from O(
to 2)) In particular, our EGDA algorithm performs both gradient descent and ascent steps to the original function f. In contrast, many existing algorithms such as [51 their surrogate functions with smoothing terms instead of the original function. In particular, their smoothing parameters need to tune by repeatedly executing the algorithms,, which may make them impractical (T] As in our theoretical guarantees below, the proposed single-loop algorithm is able to significantly improve the best-known gradient complexity, O(E of existing single-loop algorithms O(
[8] optimize
such 27 5T
Convergence Guarantees
In this section, we provide the convergence guarantees of our EGDA algorithm (i.e., Algorithm I for solving constrained NC-NC and NC-C problems. We first present the definitions of the two optimality criteria (i.e., an e-stationary point of f or Φ). All the proofs of the lemmas, properties and theorems below are included in the Supplementary Material.
4.1 Optimality Criteria and Key Property
Since finding a global minimum of a nonconvex optimization problem is NP-hard, finding a global saddle point (or Nash equilibrium) of NC-NC function f intractable (30). As in the literature in the NC-NC setting, we introduce the local surrogates (i.e., the stationary point of f) and in the NC-C setting, we introduce the local surrogates (i.e., the stationary point of f or Φ), whose gradient mappings are equal to zero. Below we define the following two optimality measures (i.c., an e-stationary points of Φ) for our theoretical analysis.
Definition (An c-stationary point of f (27). A point (H., B) E X x y is an e-stationary point of f(6)) ( I| S e, where Ta and Fly are two constants, and
T (x, = (1/n=)(z (//na)(--P(EE--- n V=
(6)
(11/n) P
e = 0, then (7. v) is a stationary point J.
For the NC-C setting, we also present another convergence criterion used in 40 24 Let d(x) == max [x, y), f is called e-stationary point of a smooth primal function R IR, if |V < c. However, the function ø is not necessarily differentiable for minimax problems.
Following p 40 24 we introduce the Moreau envelope of for the optimality criterion, especially when @ is a weakly convex function, i.e., é is L-weakly convex if the function Φ(-) + 4 1|2 is convex. We refer readers
9 24 for the comparison of these two criteria.

---

Definition 2 (An e-stationary point of L- L-wekkly convex function 6). & is an e-stationary point of an L-weakly convex function o IR. R. if /(2/ (+)l Se. where (21)) is the Moreau envelope of 6 and is defined as: (-(x) :- o ( (1/2p) - Iff = then è is a stationary point.
Then we give the following important property for the analysis of the proposed algorithm. By leveraging the property, we can obtain the complexity bound of the proposed algorithm.
Property (Quasi-Cocoerciiitt)) Let u1+1/2 be updated in Eq. (3) then
(1112) Vy (2t, Vt-1), 44-1/2 - yt) = =3 (2t, U 112) (2)
4.2 Core Lemma
Our theoretical results mainly rely on Lemma 1 below, which plays key role in the proofs of Theorems and 2. Let ((1s, Vt. uz, (c-1/2)) be sequence generated by Algorithm and we define the potential function
G. = faz, ye) + 1 - +8.0 (1 4/222) V ( (21-1,
Next, we need to prove that our defined potential function can make sufficient decrease at each iteration, i.e. G2 Gi+1 0 as in Lemma below. To prove Lemma I we will provide and prove the following upper bounds. Proposition (Upper bound of primal- dual updates). Suppose Assumption holds. Let (Ir, yt, un) be a sequence generated by Algorithm with m @ 1/a)
2 ( 28L nzt.
f(1++1, 44+112) fx 3/.)
<
17x 2 2211+
vell? + Lilvi -1-111++ oof 11- 1/21/2 V1)
As Proposition 2 (Upper bound of dual updates). Suppose Assumption holds. Let {1res De, uz) be sequence generated by Algorithm / then
[01,, Me+1 (6-
< (V (2t Ut 1/21 u4 + (V
2ot1/2) tai.
A2
Aa
where at = - 96 (f u- V v (x,, V1 ))1 8I(11-111 111111111111
| ( 11-322 V 2) + 3T. Mr+ 1e
Using the optimal condition of Problem 4 and our quasi-cocoercivitg in Property 1, we further bound A₁ + A2 + Ag. The proof sketch of Lemma is listed as follows:
G++1- G. ==f (((e)))))))))))))))))))))) ("a + f( /411/2 - - ((., +other terms
Proposition
Proposition
A1 + A Ag
+
other terms.
Quase-Cocoercivity in Property
Combining the above results and the definition G., we can get the descent estimate of the potential function in Lemma 1, which is main lemma for Theorems 1 and 2 below.
Lemma (Descent estimate of G). Suppose Assumption holds. Let {(z,, Ve, un) be sequence generated by Algorithm then
Go GT
T-1
(G. - -G+11
t=0
T-1
12 8-
|1-11
1V fyf(ze, Ut - 1/2) Vyf Ur- 1
|ل 2z
Any
2
2n
1=0
7

---

4.3 Convergence Results
In this subsection, by using the optimality measure in Definitions 1 and 2 we present the following
theoretical results in Theorem ! and Theorem 2 for the constrained NC-NC setting and NC-C setting, respectively.
Assumption 2. y is closed, convex and compact set with a diameter Dy > O, and X is closed and convex set.
Furthermore, using Lemma 1 and the optimality measure in Definition 1 will study the relation between π ( u.) and the difference (i.e.. G2 GL+1) to obtain the gradient complexity in Theorem ! by computing the number of iterations to achieve an e-stationary point of f.
Theorem (Stationarity of f in constrained NC-NC settings), Suppose Assumptions I and 2 hold. 1 and 28L . nz), 3 I 6üz
Let the two stepsizes T/= S "L' niy = min 9ll (/a)
1
7 2 1/2, then the complexity of Algorithm to find an c-stationary point of f is bounded by
o( Go G 22DD3
where Go == G yo). and G == min 6(x).
Remark 1. For constrained NC-NC problems, the gradient complexity of our EGDA algorithm to find an e-stationary point of f is O(E That is, our EGDA algorithm is first to obtain the gradient complexity in constrained NC-NC setting. In addition, our method can achieve the same complexity, ( as the algorithm with an additional structured assumption for NC-NC problems. However, different from existing algorithms, our algorithm is more practical. That is, it only requires that y is a compact set, while existing algorithms need some stronger structured assumptions in the structured NC-NC setting. The detailed comparison is shown in Table [ As two special cases of the construined NC-NC problem, this theoretical result in Theorem I can be extended to the constrained NC-C andC C-NC settings. For NC-C problems, the gradient complexity of our EGDA algorithm find an 6-stationary point of J is O(r²)), while the best-known result of single-loop algorithms such as 127 51 444 is O(e-A), and the best-known result of multi-loop algorithms such 124) is Ö -2.5).
That is, our EGDA algorithm improves the best-known gradient complexity from Ö(E -2.5) to O 2). Smoothed-GDA [5lV can also obtain the complexity O(E-2)) for a special case of Problem ( and O(E for general NC-C minimax problems, while our algorithm attains the optimal result O for all NC-C minimax problems. Existing algorithms such as HiBSA (27] and AGP [441 require the compactness of the domain X in the NC-C setting, while our EGDA algorithm does not, which significantly extends its applicability. For C-NC minimax problems, the proposed algorithm can obtain the complexity, O(e ()) while the best-known complexity as in (44) is Oie -4). In other words, the proposed algorithm can improve the best-known result from O -) O(E
By using the criterion in Definition aa the optimality measure, we use the definition of Φ1/21. and introduce the property of V/1122 in (24). With a similar setting for varying stepsizes as in [24]. we study the relation between 1 and the basic descent estimation of the potential function in Lemma by using the property of V and compute the number of iterations to achieve an e-stationary point of Φ. We provide the following theoretical result and its detailed proof in the Supplementary Material.
Theorem (Stationarity of & for constrained NC-C settings). Using the same notation as in Theo- and f is concave with respect to y. Let (II Mr, u:)} be a sequence generated by Algorithm 1
rem 7
Baद Bet 2d, }. where ;=:= (z (I ff (1-1/2)ll.cc == || V yf f 1/21/))l :- V/V== (xz, u,) - V ( 44-1/2)ll Then the gra-
Ba²
with the stepsizes ni, min{ 25 28L
dient complexity of Algorithm tto find e-stationary point of & is bounded by
o Dy(Co - - G
2
Remark 2. From Theorem 2 it is clear that the gradient complexity of the proposed algorithm is
O That is, Algorithm 1 can improve the bnow- grudient complexity from ((e-3) in (24) to O() Therefore, Algorithm [ is the first algorithm, which attains the gradient complexity Oce-3 find an e- e-stationary point of o for NC-C minimax problems.
8

---

10a
10
10
10
10:20
10
-GDA
-GDA
EG
EGG
EGDA
EGDA
10:30
10
0
100
200
300
400
500
100
200
300
400
500
Number iterations
Number of iterattoon
Comparison of all the methods for solving the NC-NC problem, f(z y) x² 3 sin" sinnrssnn 4y² 10sin Left: Convergence in terms of I x= (x", yy) is the global saddle point; Right: Convergence in terms of f V
Figure 1:
12 + |Ive y 11, where
Numerical Results
We conduct many experiments to illustrate the performance of the proposed algorithm for solving NC-NC, NC-C and convex-concave problems.
NC-NC Problems. We conduct some experiments to illustrate the performance of the proposed algorithm, EGDA, for solving NC-NC problems. Moreover, we compare it against existing methods such as GDA 46 Material.
EG
[0], EAG
49 and FEG 20 Detailed setup is provided in the Supplementary
We compare EGDA with GDA, EG and FEG for solving simple NC-NC minimax problem (i.e., f(z, y) = x² +3 sin" sin2y-4y²~ 10 sin y). which satisfies the Polyak- Lojyak--ojaiiwwicz condition, as shown in Fig. [T] All the results show that EGDA indeed converges the global saddle point and is significantly faster than other methods including GDA and FEG in terms of both || x x²11 + ||
y" 11 and || f Although FEG has fast theoretical rate, (11(t²), with negative
monotone assumption, it converges much slower than EGDA in practice.
10
-2
GDA
EAG
EGDA
10
GDA .. EAG
-8
saddle point
- EGDA
Iniial point
-8
6
2
6
0
100
200
300
400
500
Number of iterations
Figure 2: Comparison of all the methods for solving the convex-concave problem, f(r
log(1 + e²) + 3wy log(1 e*). Left: Trajectories of the three algorithms; Right: Convergence in terms of |x, 11 112 lv y 1!?
Convex-Concave Problems. Fig. 2 shows the convergence results of the methods including GDA, EAG 49 and EGDA for solving the convex-concad problem, fax y) log(1 + c*)) 3ry log(1 e²). It is clear that EGDA converges much faster than other methods such EAG. We also observe empirically when the same step-size used, even if small, GDA may not converge to stationary points, and it proven always have bounded iterates.
NC-C Problems. We also apply our EGDA algorithm to train robust neural networks against adversarial attacks on Fashion MNIST and MNIST, and verify theoretical results. In [5] 28 31

---

10
GDA
10"
GDA
MSDA
MGDA
Smoothed-GDA
Smaothed-
EGDA
EGDA
10"
10"
Loss
10"
10
60
100
20
80
100
Epoch
Epoch
Figure 3: Convergence speed of all the algorithms on Fashion MNIST (left) and MNIST (right).
the robust training procedure be formulated into NC-C minimax optimization problem. It is clear that the minimax problem is nonconvex in æ, but concave in
FGSM [5] and PGD [9] are two popular methods for generating adversarial examples. To obtain the targeted attack Lig. we use the same procedure as in 51 as follows. The perturbation level is chosen from {0.0, 0.1, 0.2, 0.3, 0.4), and the stepsize is 0.01. Note that the number of iterations set to 40 for FGSM and for PGD, respectively. The details of the network are included in the Supplementary Material. We compare our EGDA method with GDA 255, MGDA [31 and Smoothed-GD4 [51] and illustrate the convergence of all the algorithms on the loss function in Fig. B The results show that Smoothed-GDD and EGDA converge significantly faster than other algorithms. This verifies that they have faster convergence rate, Ole ²). Moreover, EGDA converges much faster than Smoothed-GDA.
Conclusions and Future Work
In this paper, we proposed a new single-loop accelerated algorithm for solving various constrained NC-NC minimax problems. In the proposed algorithm, we designed a novel extra-gradient difference scheme for dual updates. Moreover, we provided the convergence guarantees for the proposed algorithm, and the theoretical results show that to find
e-stationary point of J, the proposed algorithm obtains the complexity bound (c= ) for constrained NC-NC problems. That is, this the first time that the proposed algorithm attains the complexity bound O(E in constrained NC-NC settings (including constrained NC-C and C-NC), For NC-C problems, we provided the theoretical guarantees of the proposed algorithm under the stationarity of Φ. which show that our algorithm improves the complexity bound from Ō to O) Experimental results also verified the theoretical results of the proposed algorithm, which have the factors of - and e faster than existing algorithms, respectively. For further work. we will extend our directly accelerating algorithm to stochastic, non-smooth, nonconvex-monconeee and federated learning settings in 37).
55 45
Acknowledgments
We want thank the anonymous reviewers for their valuable suggestions and comments. This work was supported by the National Key R&D Program of China (No. 20222D0160302,, the National Natural Science Foundation of China (Nos. 622707 1567, 61976164, 62276004 and 61836009), the National Science Basic Research Plan in Shaanxi Province of China (No. 2022GY-061), the major key project of PCL, China (No. PCL.2011A2)) and Qualcomm.
References
[1] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In STOC, 2017.
[2] Z. Allen-Zhu and Y. Yuan. Improved SVRG for non-strongly-come convex or oum-of-nnome non-convex objectives. In ICML, pages 1080-1089, 2016.
10

---

[3] J. P. Bailey, G. Gidel, and G. Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent, In The Annual Conference on Learning Theory (COLT), pages 391-407, 2020.
[4] R. Bot and A. Bohm. Alternating moximal-gradiens steps for (stochastic) nonconvex-concave minimax problems. SIAM Optim., 2023.
Y. Cai and W. Zheng. Accelerated single-call methods for constrained min-max optimization. Interna- tional Conference on Learning Representations (ICLR), 2023.
[6] Z. Chen, Z. Hu, Q. Li, Z. Wang, and Y. Zhou. A cubic regularization approach for finding local minimax points in nonconvex minimax optimization. Transactions on Machine Learning Research, pages 1-43, 2023.
[7] C. D. Dang and G. Lan. On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators. Comput. Optim. Appl., 6012):77--10,, 2015.
[8] C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min optimization. In The Annual Conference on Neural Information Processing Systems (NewrIPS), pages 9256 9266, 2018.
[9] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM J. Optim., (91(1)200-22)) 239. 2019.
[10] Diakonikolas, C. Daskalakis, and M. I. Jordan. Efficient methods for structured min-max optimization. In AISTATS, pages 2746-2754, 2021.
[11] J. Diakonikolas, C. Daskalakis, and M. I. Jordan. Efficient methods for structured nomconvex-nonnconcave min-max optimization. In The International Conference on Artificial Intelligence and Statistics (AISTA7S), pages 2746-2754, 2021.
[12] S. S. Du, Chen, L. Li, Xiao, and D. Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning (ICML). pages 1049-1058. 2017.
[13] C. Duchi and Namkoong. Variance-based regularization with convex objectives. Much. Learn. Res., 20:1-55, 2019.
[14] 1. Goodfellow, J. Pouget-Abadic M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In The Annual Conference on Neural Information Processing Systems (NIPS), pages 2672-2680, 2014.
[15] I. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations (ICLR), 2015.
[16] A. N. lusem, A. Jofré, I. Oliveira, and P. Thompson. Extragradient method with variance reduction for stochastic variational inequalities. SIAM Optim., 27(2))686 7244 2017.
[17] C. Jin, P. Netrapalli, and M. I. Jordan. What is local optimality in noncomvex-nonecoecaw minimax optimization? In International Conference on Machine Learning (ICML), pages 4880-4889, 2020.
[18] W. Kong and R. D. Monteiro. An accelerated inexact proximal point method for solving nonconvex-coneee min-max problems. In arXiv preprint 19t.::9905111333:3 2021.
[19] A. Kurakin, I. Goodfellow, and S. Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations (ICLR), 2017.
[20] S. Lee and D. Kim. Fast extra gradient methods for smooth structured noncomvex-nonconeane minimax problems. In NeurlPS, 2021.
[21] Y. Lei, Z. Yang, T. Yang, and Y. Ying. Stability and generalization of stochastic gradient methods for minimax problems. International Conference on Machine Learning (ICML), pages 6175-6186, 2021.
[22] A. Letcher, D. Balduzzi, S. Racaniere, Martens, J. N. Foerster, Tuyls, and Graepel. Differentiable game mechanics. J. Mach. Learn. Res., 20:1-40, 2019.
[23] H. Li, Y. Tian, J. Zhang, and A. Jadbabaie. Complexity lower bounds for nomcomvexx-stoonlly-oommaw min-max optimization. In arXiv preprint arXiv:2 104.22004.870v11 2021.
[24] T. Lin, C. Jin, and M. I. Jordan. Near-optimal algorithms for minimax optimization. In The Annual Conference on Learning Theory (COLT), pages 2020.

---

[25] T. Lin. C. Jin, and M. I. Jordan. On gradient descent ascent for nonconvex-coneayy minimax problems. In International Conference on Machine Learning (ICML), pages 6083-6093, 2020.
[26] M. Liu, H. Rafique, Q. Lin, and T. Yang. First-order convereencee theory for welkly.oomeerweekkkyyoonnee min-max problems. Mach. Learn. Rex., 12:169:1-169::: 2021.
[27] S. Lu, I. Tsaknakis, M. Hong, and Y. Chen, Hybrid block successive approximation for one-sided non- convex min-max problems: algorithms and applications. IEEE Trans. Signal Process., 68:3676-369,, 2020.
[28] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations (ICLR). 2018.
[29] A. Mokhtari, A. Ozdaglar, and S. Pattathil, unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In The International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1497-1507, 2020.
[30] K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming. 19(2)117-119, 1987.
[31] Nouiched, M. Sanjabi. T. Huang, Lee, and Razaviyayn. Solving a class non-convex min-man max games using iterative first order methods. In NeurlPS, pages 14905-1491,, 2019.
[32] D. M. Ostrovskii, A. Lowy, and M. Razaviyayn. Efficient search of first-order Nash equilibria in nonconvex- concave smooth min-max problems. SIAM J. Optim., 2021.
[33] Y. Ouyang and Y. Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programmingg 185:1-35, 2021.
[34] H. Rafique, M. Liu, Lin, and T. Yang. Weakly-convex concave min-max optimization: Provable algorithms and applications in machine learning. Optim. Method Sofnw,, 2022.
[35] M. Razaviyayn, T. Huang, S. Lu, M. Nouiched, M. Sanjabi, and M. Hong. Nonconvex min min-max optimiza- tion: Applications, challenges, and recent theoretical advances. IEEE Signal Process, Mag., 37(5):55 66, 2020.
[36] S. Shafierzadeh--Aaader M. Esfahani, and D. Kuhn. Distributionally robust logistic regression. In The Annual Conference on Neural Information Processing Systems (NIPS), pages 1576-1584, 2015.
[37] P. Sharma, R. Panda, G. Joshi, and P. K. Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning (ICML), pages 19683-19730, 2022.
[38] C. Song, 7., Zhou, Y. Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. In NeurlPS, 2020.
[39] C. Tan, T. Zhang, Ma, and Liu. Stochastic primal-dual method for empirical risk minimization with o(1) per-iteration complexity. In The Annual Conference on Neural Information Processing Systems (NeurIPS), pages 8376 7776-888,,77 2018.
[40] K. K. Thekumprampil. P. Jain, P. Netrapalli, and S. Oh. Efficient algorithms for smooth minimax optimization. In The Annual Conference Neural Information Processing Systems (NeurIPS), pages 8659-11270,, 2019.
[41] Н.-T. Wai, Z. Yang. Z. Wang, and M. Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In The Annual Conference on Neural Information Prucessing Systems (NeurIPS), pages 9672 9623,968,3222 2018
[42] G. Xie, I. Luo, Y. Lian, and 7. Zhang. Lower complexity bounds for finite-sum convex-concave minimax optimization problems. In International Conference Machine Learning (ICML), pages 2020.
[43] Y. Xu, R. Jin, and T. Yang. First-order stochastic algorithms for escaping from saddle points almost linear time. In NewrlPS, pages 5535-5545. 2018.
[44] Z. Xu, H. Zhang, Y. Xu, and G. Lan. A unified single-loop alternating gradient projection algorithm for Munconvex-concate and convex- nonconevee minimax problems. Mathematical Programming, 2023.
12

---

[45] J. Yang, N. Kiyavash, and N. He. Global convergence and variance-reduced optimization for a class of nonconvex-moncconcave minimax problems. In The Annual Conference Neural Information Processing Systems (NeurIPS), 2020.
[46] J. Yang, N. Kiyavash, and N. He. Global convergence and variance reduction for class of nonconvex- nonconcave minimax problems. In NeurlPS, 2020.
[47] J. Yang, Zhang, N. Kiyavash, and N. He. A catalyst framework for minimax optimization. In The Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[48] т. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with 011/k22) rate on squared gradient norm. M. Meila Zhang, editors, ICML, pages 12098-12109, 2021.
[49] T. Yoon
Ryu. Accelerated algorithms smooth convex-concane minimax problems with o(1 rate on squared gradient norm. In ICML, pages 12098-12100 2021.
[50] Zhang, M. Hong, and Zhang. On lower iteration complexity bounds saddle point problems. Mathematical Programming, 194:901-935, 2022.
[51] Zhang, Xiao, Sun, and Luo. single-lopp smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. In The Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7377-7389, 2020.
[52] S. Zhang, J. Yang, C. Guzman, N. Kiyavash, and N. He. The complexity of tonconver--tronngyyyommmaa minimax optimization. In The Conference on Uncertainty in Artificial Intelligence (UAI), 2021.
[53] W. Zhang and D. Han. A new alternating direction method for co-coercive variational inequality problems. Comput. Math. Appl., 57(7): 168-117777 1178, 2009.
[54] Y. Zhang and I. Xiao. Stochastic primal-dual coordinate method for regularized empirical risk minimization.
J. Mach. Learn. Res., 18:1-42, 2017.
[55] R. Zhao. A primal dual smoothing framework for max-structured nonconvex optimization. Mathematics of Operations Research, 2023.
13


Reviews:
[{"review_id": "YZ8vsVofxD", "reviewer": "Reviewer_VxsC", "summary": "This paper discusses a new extra-gradient difference acceleration algorithm for solving constrained nonconvex-nonconcave minimax problems. The algorithm introduces a \"quasi-cocoercivity property\" and momentum acceleration to significantly improve the convergence rate in the constrained NC-NC setting. The algorithm attains a complexity of $O(\\epsilon^{-2})$ for finding an $\\epsilon$-stationary point of the function $f$, which outperforms the best-known complexity bounds. The paper also provides theoretical analysis and comparisons with existing algorithms.", "questions": "---Can you explain more about the \"quasi-cocoercivity\" property and discuss how it improves the convergence rate in the constrained NC-NC setting? Is this an absolutely necessary property for the improved convergence rate to hold?\n\n---Can your algorithm or its variants be applied to other minimax optimization problems beyond the constrained NC-NC setting?\n\n---There do exist some typos. For example in Eq. (4) in Line 215, missing factor 2 in the denominator. Should be minor but the authors should check more and correct them.", "limitations": "This paper is purely theoretical and does not admit negative social impacts to my best knowledge.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "As a person who works in minimax optimization, I can make a fair judgment of this work. This paper presents a novel extra-gradient difference acceleration algorithm for solving constrained nonconvex-nonconcave minimax problems, which improves the existing convergence rate and outperforms the best-known complexity bounds to $O(\\epsilon^{-2})$. The paper also provides a comprehensive comparison with existing algorithms and a theoretical analysis of the algorithm's performance. I understand the \"extra-gradient difference prediction\" step as the key to the success of convergence rate improvements. In addition, I went through the proofs of Theorems 1 and 2 in detail. Overall, this paper provides valuable contributions to the field of minimax optimization and presents a promising algorithm for solving constrained NC-NC problems.", "weaknesses": "The paper assumes that the objective function satisfies certain structural assumptions, which may limit its practical applications. Also the writing style might not be as friendly for readers unfamiliar with the topic (I found it sufficiently clear though).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**： Can you explain more about the \"quasi-cocoercivity\" property and discuss how it improves the convergence rate in the constrained NC-NC setting? Is this an absolutely necessary property for the improved convergence rate to hold?\n\n**A**:  Thanks for your positive and valuable comments. To address your concern, we will add some explanations about the \"quasi-cocoercivity\" property, and discuss how it improves the convergence rate in the constrained NC-NC setting in our final paper. From the perspective of theoretical analysis, we use the \"quasi-cocoercivity\" property to offset some residual terms produced by Propositions 1 and 2. As a result, we can obtain a descent sequence of the potential function, i.e., G_t. From the perspective of algorithmic intuition, the \"quasi-cocoercivity\" property is related to the extra-gradient difference iteration, which can improve the convergence rate. Thus, we think that it is a necessary property to improve the convergence rate.\n\n**Q**：Can your algorithm or its variants be applied to other minimax optimization problems beyond the constrained NC-NC setting?\n\n**A**:   To address your concern, we will make some discussions in the revised manuscript. The proposed algorithm can be extended to some problems beyond the constrained NC-NC setting. For example, for the robust neural network training problem, which does not require the compactness of the domain X (x is the parameter of the neural network), it goes beyond the constrained condition in the domain X. Furthermore, we can also extend the proposed algorithm to the stochastic setting to effectively solve large-scale problems. In addition, we also provide more experimental results  in Figs.3 and 4 in the PDF file for more real-world applications (please see “global” response). \n\n**Q**：There do exist some typos. For example in Eq. (4) in Line 215, missing factor 2 in the denominator. Should be minor but the authors should check more and correct them.\n\n**A**:   To address your concern, we have corrected these typos in the revised manuscript.\n\n"}, {"review_id": "6mNWnxhvFP", "reviewer": "Reviewer_RSU3", "summary": "This work proposes a single-loop extra-gradient difference acceleration algorithm to find an \\epsilon-stationary point for constrained minimax optimization, which pushes forward the best complexity bounds of NC-NC, C-NC, NC-C problems to \\mathcal{O}(\\epsilon^{-2}). The proposed approach can deal with more general problems as it does not require monotone or structural assumption. Moreover, for the NC-C problem, the authors prove that the proposed method has better complexity bound under the stationarity of \\phi. Experiments are conducted to validate the method empirically. The results show that it can achieve better convergence rate when comparing with the related methods.", "questions": "please see above.", "limitations": "no negative societal impact", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe theoretical contributions are significant. The method employs a novel prediction point scheme to obtain the quasi-cocoercivity property, which relaxes the assumption requirements. Additionally, the paper provides a thorough analysis of the convergence complexity bound, demonstrating its superiority over the current state-of-the-art approaches.\n\n2.\tThe paper is well organized and easy to follow. The logical flow of ideas is well-structured, enhancing the overall readability and comprehension of the presented contents.\n\n3.\tEmpirical studies are conducted to validate the method in both synthetic and real tasks.\n", "weaknesses": "There are some possible limitations where the paper could be further improved.\n\n1.\tI suggest the authors to undertake additional analysis of the algorithm's time complexities, both theoretically and empirically. This deeper exploration would provide valuable insights, particularly for potential industrial applications.\n\n2.\tThe absence of experiments conducted on the C-NC problem should be explained within the paper.\n\n3.\tThere are some empirical evidences that seem to be inconsistent with the theoretical result, for example, FEG has a fast theoretical rate but is less effective in practice; GDA may not converge to stationary points. The authors may explain more about these in the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**:  I suggest the authors to undertake additional analysis of the algorithm's time complexities, both theoretically and empirically. This deeper exploration would provide valuable insights, particularly for potential industrial applications.\n\n**A**:   Thanks for your positive and valuable comments. To address your concern, we will add the time complexity of the proposed algorithm for solving  min-max problems in the final version. In our algorithm, three gradients need to be calculated for each iteration update, the time complexity for constrained NC-NC setting is O((m+n)\\epsilon^{-2}), where m and n denote the dimensions of x and y, respectively. Moreover, we have conducted more empirical experiments and compared the performance of all the algorithms over the running time, as shown in Fig. 1 in the PDF file (please see “global” response). All the results show that the proposed algorithm converges significantly faster than other algorithms, as verified by theoretical and empirical analysis. All the results will be included in our final paper. \n\n**Q**: The absence of experiments conducted on the C-NC problem should be explained within the paper.\n\n**A**: To address your concern, we will add some discussions about the C-NC problem in the revised manuscript. In fact, there are few C-NC minimax problems in real-word applications, such as the convex-nonconcave zero sum game in [R1]. If necessary, we will add some experiments for solving such problem in the revised manuscript. \n\n[R1] G. Su, et al. Secrecy-oriented user association in ultra dense heterogeneous networks against strategically colluding adversaries. IET Commun., 2022.\n\n**Q**: There are some empirical evidences that seem to be inconsistent with the theoretical result, for example, FEG has a fast theoretical rate but is less effective in practice; GDA may not converge to stationary points. The authors may explain more about these in the paper.\n\n**A**:  To address your concern, we will make the following clarifications. In fact, FEG has a fast theoretical rate for the problem with an additional structured assumption. However, the NC-NC function used in Figure 1 in this paper does not satisfy the structured assumption. As a result, FEG has a slow convergence rate. In addition, we have conducted more experiments of FEG for the function in Figure 2 (please see “global” response), and reported empirical results in Fig. 2 in the PDF file. The results show that FEG converges much faster than GDA and EAG.\n\n\n\n"}, {"review_id": "MHV7ABOHPz", "reviewer": "Reviewer_gZnc", "summary": "The authors have designed a single-loop accelerated algorithm for constrained min-max optimization problems of the form $\\min_{x\\in X}\\max_{y\\in Y} f(x,y)$. The algorithm provably converges in an approximate local stationary point in three particular setting: \n1. Non-convex non-concave min-max optimization, where the stationarity is measured for the function $f(x,y)$.\n2. Convex non-concave min-max optimization, and non-convex concave min-max optimization, where the stationarity is measured for function $\\phi(x)=\\max_{y'\\in Y} f(x,y')$. \n\nThe authors showed that their algorithm computes an $\\epsilon$-stationary point, in $O(1/\\epsilon^2)$ iterations. Finally, they experimentally verify their proposed algorithm.\n\n\n\nThe authors' rebuttal addressed my concerns, and their additional empirical evidence complemented their already compelling results. For these reasons, I decided to increase my score.", "questions": "The recent work in [1], shows that the computation of an approximate stationary point is PPAD-complete when the action space of the two players is a joint. Notably, the findings in your paper seem to suggest a different outlook when the strategy space of the two players is a product space, which negates the hardness results. A comment from the authors addressing this observation would be greatly appreciated.\n\nFurthermore, the proofs of the propositions and lemmas presented appear to be quite opaque, and verifying them poses a bit of a challenge. It would be truly beneficial if the authors could share some additional insights into the process behind the design and analysis of the algorithm. I think it would be good if the authors could provide a better commentary about the derivations of the proofs.\n\n[1] \"The Complexity of Constrained Min-Max Optimization\" by Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis", "limitations": "Any assumptions needed for the theorems to hold are listed. I do not believe this work can have negative societal impact.", "rating": 9, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The design and analysis of algorithms for non-convex non-concave minimax optimization is a fundamental problem, and the convergent results are indeed compelling. Moreover, the authors get the state-of-the-art for convex non-concave, and concave non-convex for the merit function they consider. Furthermore the main paper is well-written and easy to follow, and the algorithm seems to combine several interesting ideas.\n\nI verified the proofs of proposition 1 and 2, and the rest of the statement seems reasonable. I found the proofs of proposition 1 and 2 to be a bit dense, which made verifying them somewhat taxing.", "weaknesses": "Overall, I did not find some important weakness in the paper. As a suggestion, improving the readability and verifiability of the proofs could greatly benefit readers. Lastly, I came across a couple of typos:\n- In line 242, I think \"conference\" was meant to be \"convergence\".\n- When considering the proof of proposition 2 in the appendix, is $\\widehat{u}_{t+1/2}$ identical to the one referred to in line 706? If so, clarifying this might prevent confusion.\n- In line 3 in Algorithm 1, do you also need to initialize $y_{-1}$ for the first iteration of the algorithm?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: The recent work in [1], shows that the computation of an approximate stationary point is PPAD-complete when the action space of the two players is a joint. Notably, the findings in your paper seem to suggest a different outlook when the strategy space of the two players is a product space, which negates the hardness results. A comment from the authors addressing this observation would be greatly appreciated.\n[1] \"The Complexity of Constrained Min-Max Optimization\" by Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis.\n\n**A**:  Thanks for your positive and constructive comments. To address your concern, we will add this reference, and provide some discussions about [1] in our final paper. \n\n1.\tIn [1], the authors studied a constrained nonconvex-nonconcave problem, $\\min_x\\max_y f(x,y), s.t., g(x,y)<=0$, where the funciton $g$ is a linear funciton so that the constraint set is a polytope. While the constrained sets in our paper are closed, convex and compact sets in domains $X$ and $Y$. That is, the constrained set in our paper is only a special case of [1]. Therefore, the problem used in our work is much simpler than that in [1].\n\n2.\tWe design an extra-gradient difference iteration in our algorithm, which is similar to the forms in [43] (i.e., the difference of gradients) to achieve the approximation of negative curvature of a Hessian matrix. That is, it goes beyond a first-order method，while a first-order method is studied in [1]. The negative curvature method [43] can escape from saddle points for non-convex optimization problems. Thus, we think that our method may escape from the saddle point of lower level nonconcave problem w.r.t. $y$, which is very hard to first-order methods. That is, our method can find a \"better\" solution of lower level nonconcave problem w.r.t. $y$, which is an important reason to reduce the hardness.\n\nAll the discussions will be included in the revised manuscript.\n\n**Q**: Furthermore, the proofs of the propositions and lemmas presented appear to be quite opaque, and verifying them poses a bit of a challenge. It would be truly beneficial if the authors could share some additional insights into the process behind the design and analysis of the algorithm. I think it would be good if the authors could provide a better commentary about the derivations of the proofs.\n\n**A**: To address your concern, we will provide more details about the derivations of the proofs, and add more detailed explanations for the process behind the design and analysis of the proposed algorithm in our final paper.\n\n**Q**: In line 242, I think \"conference\" was meant to be \"convergence\".\n\n**A**: To address your concern, we have corrected in the revised manuscript.\n\n**Q**: When considering the proof of proposition 2 in the appendix, is $\\widehat{u}_{t+1/2}$ identical to the one referred to in line 706? If so, clarifying this might prevent confusion.\n\n**A**: Yes, $\\widehat{u}_{t+1/2}$ is identical to the one referred to in line 706, and we have clarified this in the revised manuscript. \n\n**Q**:  In line 3 in Algorithm 1, do you also need to initialize $y_{-1}$ for the first iteration of the algorithm?\n\n**A**: Yes, we need to initialize $y_{-1}$, and have added such initialization in the revised manuscript.\n\n\n\n\n"}, {"review_id": "Bk5LtAe2P8", "reviewer": "Reviewer_Lyoc", "summary": "Authors propose method of solving nonconvex-nonconcave saddle point problems with convergence rate O(eps^-2) by using gradient difference prediction and momentum acceleration to improve extragradient descent-ascent method. Proposed method is state-of-the-art in theory and leading in practice, including neural network learning with adversarial attacks task.", "questions": "Authors could provide more extensive empirical study, because algorithm seems to be candidate for being widely-accepted in practice and it would be good to have more justifications of its efficiency. ", "limitations": "Everything is okay", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Quite elegant construction of the algorithm, which also allows one to obtain best-known convergence rate guarantees. Algorithms allows practitioners to address the most practically important setting of nonconvex-nonconcave problems efficiently using easy to implement algorithm which will surely replace analogous methods, judging from empirical study.", "weaknesses": "No significant weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: Authors could provide more extensive empirical study, because algorithm seems to be candidate for being widely-accepted in practice and it would be good to have more justifications of its efficiency.\n\n**A**: Thanks for your positive and valuable comments. To address your concerns, we have provided more extensive empirical study, and reported more experimental results, as shown in Figs. 3 and 4 in the PDF file (please see “global” response). That is, we have applied the proposed algorithm to solve some real-world applications, such as robust neural network in Figure 3 and Wasserstein GAN training in Figure 4. All the results show that the proposed algorithm performs much better than other algorithms such as GDA, MGDA and Smoothed-GDA, which also verified our theoretical results. All the results will be included in our final paper. The details are as follows:\n\n1.\tMore Results for Robust Neural Network in Figure 3 in the PDF file (please see “global” response)\n\nUnder adversarial attacks including $\\ell_\\infty$ -norm FGSM and PGD attacks, the test accuracies of all the algorithms including GDA, MGDA, Smoothed-GDA and our EGDA are reported in Fig.3, where the $\\ell_\\infty$ -norm perturbation level $\\varepsilon$ varies from $0.0$ to $0.4$. Note that for EGDA, the parameter $\\tau$ is set to $3/4$, and the parameters $\\alpha$ and $\\beta$ in Smoothed-GDA are set to $0.2$ and $0.8$ as in [51], respectively. And the number of iterations is set to 100 for all the algorithms. All the results show that Smoothed-GDA and EGDA significantly outperform GDA and MGDA in terms of accuracy, and our EGDA also performs better than other algorithms including Smoothed-GDA.\n\n2.\tMore Results for Wasserstein GAN in Figure 4 in the PDF file (please see “global” response)\n\nFinally, we apply the stochastic version of the proposed EGDA algorithm to train Wasserstein GAN in [R3] on the MNIST dataset, and verify the effectiveness of our algorithm. Here the architectures of Wasserstein GAN (including its discriminator and generator) are set to be multi-layer perceptrons (MLP). The layer widths of the MLP in generator are 100, 128, 784, and the layer widths of the MLP in discriminator are 784, 128, 1. In addition, the batch size is set to 64, and the learning rate is 1e-4. Moreover, we compare our algorithm against one state-of-the-art method, Stochastic Gradient Descent Ascent (SGDA) by drawing their generated figures after 20k and 100k iterations, as shown in Fig.4. All the results show that our stochastic algorithm performs much better than SGDA and produces higher quality images, which shows the effectiveness of our algorithm.\n\n[R3] M. Arjovsky , et al., “Wasserstein generative adversarial networks,” ICML 2017.\n\n"}]

Author rebuttal:
Dear Reviewers and Area Chairs:

Thank you very much for the constructive comments. More experimental results in the PDF file, and the details are as follows: 

**1**. We have conducted more empirical experiments and compared the performance of all the algorithms over the running time, as shown in Fig. 1 in the PDF file.

**2**. We have conducted more experiments of FEG for the function in Figure 2, and reported empirical results in Fig. 2 in the PDF file.

**3**. More Results for Robust Neural Network in Figure 3: 

Under adversarial attacks including $\ell_\infty$-norm FGSM and PGD attacks, the test accuracies of all the algorithms including GDA, MGDA, Smoothed-GDA and our EGDA are reported in Fig.3, where the $\ell_\infty$-norm perturbation level $\varepsilon$ varies from $0.0$ to $0.4$. Note that for EGDA, the parameter $\tau$ is set to $3/4$, and the parameters $\alpha$ and $\beta$ in Smoothed-GDA are set to $0.2$ and $0.8$ as in [51], respectively. And the number of iterations is set to 100 for all the algorithms. All the results show that Smoothed-GDA and EGDA significantly outperform GDA and MGDA in terms of accuracy, and our EGDA also performs better than other algorithms including Smoothed-GDA.

**4**.	More Results for Wasserstein GAN in Figure 4

Finally, we apply the stochastic version of the proposed EGDA algorithm to train Wasserstein GAN in [R3] on the MNIST dataset, and verify the effectiveness of our algorithm. Here the architectures of Wasserstein GAN (including its discriminator and generator) are set to be multi-layer perceptrons (MLP). The layer widths of the MLP in generator are 100, 128, 784, and the layer widths of the MLP in discriminator are 784, 128, 1. In addition, the batch size is set to 64, and the learning rate is 1e-4. Moreover, we compare our algorithm against one state-of-the-art method, Stochastic Gradient Descent Ascent (SGDA) by drawing their generated figures after 20k and 100k iterations, as shown in Fig.4. All the results show that our stochastic algorithm performs much better than SGDA and produces higher quality images, which shows the effectiveness of our algorithm.

[R3] M. Arjovsky , et al., “Wasserstein generative adversarial networks,” ICML 2017.


Meta-review: This paper introduces an extra-gradient difference acceleration algorithm for constrained nonconvex-nonconcave minimax problems. The algorithm improves upon the existing best convergence rate. Additionally, the paper offers an extensive comparison with current algorithms and delivers a thorough theoretical analysis. The whole review team believes that the paper makes significant contributions to the field of minimax optimization.
Decision: Accept (oral)