Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization
Authors: Taoli Zheng
Linglingzhi Zhu
Anthony Man-Cho So
Jose Blanchet
Jiajin Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Nonconvex-Nonconcave Minimax Optimization
Limit Cycle

Abstract: Nonconvex-nonconcave minimax optimization has received intense attention over the last decade due to its broad applications in machine learning. Most existing algorithms rely on one-sided information, such as the convexity (resp. concavity) of the primal (resp. dual) functions, or other specific structures, such as the Polyak-Łojasiewicz (PŁ) and Kurdyka-Łojasiewicz (KŁ) conditions. However, verifying these regularity conditions is challenging in practice. To meet this challenge, we propose a novel universally applicable single-loop algorithm, the doubly smoothed gradient descent ascent method (DS-GDA), which naturally balances the primal and dual updates. That is, DS-GDA with the same hyperparameters is able to uniformly solve nonconvex-concave, convex-nonconcave, and nonconvex-nonconcave problems with one-sided KŁ properties, achieving convergence with $\mathcal{O}(\epsilon^{-4})$ complexity. Sharper (even optimal) iteration complexity can be obtained when the KŁ exponent is known. Specifically, under the one-sided KŁ condition with exponent $\theta\in(0,1)$, DS-GDA converges with an iteration complexity of $\mathcal{O}(\epsilon^{-2\max\\{2\theta,1\\}})$. They all match the corresponding best results in the literature. Moreover, we show that DS-GDA is practically applicable to general nonconvex-nonconcave problems even without any regularity conditions, such as the PŁ condition, KŁ condition, or weak Minty variational inequalities condition.  For various challenging nonconvex-nonconcave examples in the literature, including *Forsaken*, *Bilinearly-coupled minimax*, *Sixth-order polynomial*, and *PolarGame*, the proposed DS-GDA can all get rid of limit cycles. To the best of our knowledge, this is the first first-order algorithm to achieve convergence on all of these formidable problems.

Universal Gradient Descent Ascent Method for
Nonconvex-Nonconcavee Minimax Optimization
Taoli Zheng CUHK
Linglingzhi Zhu CUHK
Anthony Man-Cho So CUHK manchoso@se. cuhk. edu.
tizhengdse. cuhk. edu..edd..ae .k
11zzhu@se cuhk. edu.
José Blanchet
Jiajin Li Stanford University jiajinli@stanfor edu
Stanford University
jose. bl blanceet@ttaanoordd
Abstract
Nonconvex-noncooneaw nonconcave minimax optimization has received intense attention over the last decade due its broad applications in machine learning. Most existing algorithms rely on one-sided information, such as the convexity (resp. concav- ity) of the primal (resp. dual) functions, other specific structures, such the pllaak-Lojsseewizz (PL) and Hurdyka-Lojasiewiee (KL) conditions. How- ever, verifying these regularity conditions is challenging in practice. To meet this challenge, we propose novel universally applicable single-loop algorithm, the doubly smoothed gradient descent ascent method (DS-GDA), which naturally balances the primal and dual updates. That is, WD-GDA with the same hyper- parameters able uniformly solve nonconvex-coneet problems with one-sided Kt. properties, achieving
convex-noneoncave,
and nonconvex-nonconcaa convergence with ((-a)) complexity. Sharper (even optimal) iteration complexity can be obtained when the Kt. exponent is known. Specifically, under the one-sided KE. condition with exponent 6 (0, 1), DS-GDA converges with an iteration complexity of ( m2xx/2212))1)) They match the corresponding best results in the literature. Moreover, we show that DS-GDA is practically applicable to general -nnconvvx-nonconcavee problems even without any regularity conditions, such the PL condition, KL condition, weak Minty variational incqualities condition. For various challenging wonconvex-nonconee ture, including "Forsaken", "Bilinearly- coupled minimax". "Sixth-ore order polynomiall and "PolarGame", the proposed DS-Gr DS-GDA can all get rid limit cycles. To the best of our knowledge, this is the first first-order algorithm achieve convergence on all of these formidable problems.
examples in the litera-
Introduction
In this paper, we interested in studying
minimax problems of the form
min max fax ZE vEy
where RR x Rdd + nonconvex in x and nonconcave in y. and X' C R" C Rdd are convex compact sets. Such problems have found significant applications machine learning and operation research, including generative adversarial networks [27, 2), adversarial training [44, 53], multi-agent
'CCoresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

reinforcement learning [16, 48], and (distributionally) robust optimization [6. 19, 38, 25, 7], to name a few.
For smooth functions, one natural idea is to use gradient descent ascent (GDA) [41], which applies gradient descent on the primal function and gradient ascent on the dual function. However, GDA -orvee--ttooolly-----oo
is originally designed for the dual players can dominate the game. When applying it to the nonconvex-concave case, a so-called two-timescale method can make it converge. In this scenario, the primal player is the dominant player in the game, We can regard this one-step GDA scheme as an inexact subgradient descent on the inner max function m fzz y), thus it is necessary for the dual update to be relatively faster than the primal update at each iteration. However, this wo-timescale GDA yields a high iteration complexity of O "). To achieve lower iteration complexity, smoothed GDA (S-GDA) [62, 59] employs the Moreau-Yosida smoothing technique to stabilize the primal sequence. The resulting stabilized sequence can help S-GDA achieve a lower iteration complexity of O(c-)) Alternating Gradient Projection (AGP) [57] can also achieve this lower iteration complexity by adding regularizers to both primal and dual functions. It is worth noting that the convergence of all these algorithms is heavily contingent on the convexity/concavity of primal/dual functions, leading to asymmetric updates. In the convex-nonconcave scenario, the roles are reversed, and the dual player takes dominance in the game. To apply the aforementioned algorithms, their updates should be modified accordingly. Specifically, for SGDA and AGP, the smoothing and regularized sides also need to be changed to guarantce the optimal convergence rate. However, when dealing with problems, no player inherently dominates the other and all existing first-order algorithms cannot be guaranteed to converge to stationary points (see Definition 1), and they can even suffer from limit cycles. That is, the generated trajectories of all these algorithms will converge to cycling orbits that do not contain any stationary point of f. Such spurious convergence phenomena arise from the inherent minimax structure of (P) and have no counterpart in pure minimization problems. Conceptually, minimax optimization problems can be understood as a seesaw game, which means no player inherently dominates the other. More explicitly, the key difficulty lies in adjusting the primal and dual updates to achieve a good balance. Most existing works address this challenge by adding additional regularity conditions to ensure the automatic domination of one player over the other. Specifically, research works either impose the global Lojyyakwwoiiiiiizzzz (PL) condition on the dual function fxx.-) [59, 47, 22, 58] or assume the satisfaction of a-dominance condition [29, 30]. Both approaches fall into this line of research, enabling the adoption of algorithms and analysis for
problem, where either primal or
eesoonvex-nonconcee
conncve minimax problems. Although the recent work [40] extends the PL. (KE.) property, it is still hard to provide the explicit KE exponent, and prior knowledge regarding which side satisfies the KE condition is required to determine the appropriate side to employ extrapolation. If we choose the wrong side, it will result in a slow convergence or even divergence (see Figure 5). On another front, variational inequality (VT) provides unified framework for the study of equilibrium/minimx problems [46, 36, 26, 60, 45]. However, VI-related conditions are usually hard to check in practice. Hence, the convergence of the existing algorithms all highly rely on prior knowledge of the primal/dual function, which makes it paramount to design a universal algorithm for convex-nonconcave, nonconvex-concave and nonconvex- conconvex-nonconeeve nonconcave minimax problems.
condition to the one-sided
We propose a new algorithm called the Doubly Smoothed Gradient Descent Ascent (DS-GDA) algorithm. DS-GDA builds upon S-GDA by applying the Moreau-Yosida smoothing technique to both the primal and dual variables, which allows a better trade-off between primal and dual updates. All hyperparameters, including the stepsize for gradient descent and ascent steps, and extrapolation parameters are carefully and explicitly controlled to ensure the sufficient descent property of a novel Lyapunov function that we introduce in our paper. The carefully selected variables automatically decide the dominant player, thereby achieving the balance of primal and dual updates by the interaction of parameters. Furthermore, the doubly smoothing technique enables the use of set of symmetric parameters to achieve universality. This stands in sharp contrast to S-GDA, where only primal/dual function is smoothed. Specifically, the regularized function and the primal- updates in DS-GDA are inherently symmetric, which provides the possibility of applying the DS-GDA without prior information on the primal and dual functions.
To validate our idea and demonstrate the universality of DS-GDA, we provide a visual representation of the feasible symmetric parameter selections by relating the regularizer to Lipschitz constants and step sizes. This graphical illustration, depicted in Figure la, reveals that numerous parameter settings
2

---

can be chosen to guarantee convergence, which showcases the flexibility of DS-GDA. An experiment for noneoneex-nonconeeeee problem has also been done to test the efficiency of using symmetric parameters.
We also evaluate the performance of DS-GDA on range of representative and challenging nonconvex- nonconcave problems from the literature, which violate all known regularity conditions. These include the "Forsaken" example [32, Example 5.2], the "Bilinearly-couple" minimax" example [29], the "Sixth-order polynomial" example [18, 56, 13J, and the "PolarGame" example [50]. In all cases, DS-GDA successfully escapes limit cycles and converges to the desired stationary point, while other methods either suffer from the recurrence behavior or diverge. Moreover, our algorithm exhibits robustness to parameter selection (see Section 4.2), offering practical flexibility.
To corroborate its superior performance and have a better understanding of its convergence be- haviors, demonstrate that DS-GDA converges a stationary point for nonconvex-concave convex-nonconcave and nonconvex-nonconcave problems that satisfy a one-sided Kt. property. By employing a single set of parameters, DS-GDA converges with iteration complexity of O across all these scenarios. Remarkably, DS-GDA achieves this without prior verification of these conditions. However, if we have access a one-sided KE condition knowledge of the convexity (concavity) of the primal (dual) function, the range of allowable parameters can be expanded. What more, DS-GDA attains a lower or even optimal iteration complexity of ( max(26,1)) when the one-sided KE. property with exponent 0 E (0. 1) is satisfied. Notably, these convergence results match the best results for single-loop algorithms when the dual function is concave [62, 40] or satisfies Kt. condition [40]. To the best of our knowledge, our work demonstrates, for the first time, the possibility of having a simple and unified single-loop algorithm for solving nonconvex- wow.vvvee-oononnve...... nonconvex- concave, and coneex-nonconcave minimax problems. However, it remains an open question whether convergence results can be derived without any regularity conditions. This question is intriguing and nonconvex-noncoeeav nonconeave minimax problems in the future.
warrants further theoretical investigation of nonconvex
Our main contributions are summarized as follows:
(i) We present DS-GDA, the first universal algorithm for convex-nonconcan conconvex-concate and sancoonvexnonccoeene
problems with one-sided Kt. property. A single set of parameters can be applied across all these scenarios, guaranteeing an iteration complexity of O (((==).. With the KL exponent 0 E (0, 1) of the primal or dual function, we improve the complexity to O ((==2mxx(20.11) Our current convergence analysis achieves the best-known results in the literature.
(ii) We demonstrate that DS-GDA converges various challenging nonconvex nonconcave problems, even when no regularity conditions are satisfied. This makes DS-GDA the first algorithm capable of escaping limit cycles in all these hard examples.
2 Doubly Smoothed GDA
In this section, we propose algorithm (i.e.. DS-GDA) for solving (P). To start with, we introduce the blanket assumption, which is needed throughout the paper.
Assumption (Lipschitz gradient) The function f is continuously differentiable and there exist positive constant Lg, Ly > O such that for all x, x' E X and y. E E
| [ y) V. s/)lll S (II: - x'll + [yy 3/ b/1)), , (a, u) - (z' y S (, - x' yly s/ I1)-
For simplicity, we assume Ly = AL2 = XL with 0.
For general smooth nonconvex-concav problems, a simple and natural algorithm is GDA, which suffers from oscillation even for the bilinear problem millgel-1.1 1,1] max zy. To address this issue, a smoothed GDA algorithm that uses Moreau- Yosida smoothing techniques is proposed in [62]. Specifically. they introduced auxiliary variable z and defined a regularized function follows:
F(x. y, 2) = fx. v) +
2||2.
The additional quadratic term smooths the primal update. Consequently, the algorithm can achieve better trade-off between primal and dual updates. We adapt the smoothing technique to the nonconvex- nonconcave setting, where the balance of primal and dual updates is not trivial task. To tackle this
3

---

problem, we also smooth the dual update by subtracting a quadratic term of dual variable and propose a new regularized function F 12 F2
1
IR
1 || =11² 2
12 11y -112
F( (xx +
with different smoothed parameters Lz 12 > Ly for and y, respectively. Then, DS-GDA is formally presented in Algorithm 1.
Algorithm 1: Doubly Smoothed GDA (DS-GDA)
Data: Initial x0, y², 20, e., stepsizes a, c 0, and extrapolation parameters < B, <
for i 0, o...., do
x² +++ prroix('* cV FVxF(x', .y (,,,, v,,)) y't prroy(l'* + aa FV F(r*t) +1 ,3, ,²));
zt1 = x² + 3(x =z');
gt+1 = vt =-y - v²))
end
The choice rf and 72 crucial for the convergence the algorithm in both theoretical and practical senses, In particular, when rı 72, it reduces to the proximal-poing mapping proposed in [43] and inexact proximal point method (PPM) is only known to be convergent under certain VI conditions. Even with the exact computation of proximal mapping, PPM will diverge in the absence of regularity conditions [29]. By contrast, with an unbalanced 71 and r2, our algorithm can always converge. The key insight here is to carefully adjust 71 and 122 to balance the primal-dual updates, ensuring the sufficient descent property of a novel Lyapunov funetion introduced in our paper. In fact, as will show later in Section 3, and 72 typically not equal theoretically and practically. The two auxiliary variables and v. which are updated by averaging steps, are also indispensable in our convergence proof. Intuitively, the exponential averaging applied to proximal variables and ensures they do not deviate too much from æ and contributing to sequence stability.
We would like to highlight that the way use the Moreau- departure from the usual approach. Smoothing techniques are commonly invoked when solving
smoothing technique is notable
problems to achieve better iteration complexity [62, 40, 59]. However, target at smoothing both the primal and dual variables with different magnitudes to ensure global convergence.
3 Convergence Analysis
The convergence result of the proposed DS-GDA (i.e., Algorithm 1) will be discussed in this section. To illustrate the main result, we first provide the stationarity measure in Definition 1.
Definition (Stationarity measure) The point (2, X x ) is said to be an
(i) e-game stationary point (GS) if
dist fá ú) + x1x (+)) Se and dist - (t S
(ii) c-optimization stationary point (OS) if
prox f6-8+11 (0) - Se.
Remark The definition of game stationary point is natural extension of the first-order stationary point in minimization problems. It is necessary condition for local minimax point [34] and has been widely used in moncomeex-nonconcee optimization [21, 37]. We have investigated their relationships in Appendix K.

---

3.1 Complexity under Nonconvex-NNoncconcaeee Setting
Inspired by [62, 40], we consider a novel Lyapunov function R R R x IRd as follows:
R defined
(xx, yr 2, = F Flx, y, 2, d(y, 2, p(z, v) d(y, v) + ((2) p(z, v)
+
g
F
+F
Primal descent
Dual uscent
Proximal ascemt
Prosimal descent
= F ys 2, v) - 20l(y, 2, v) + 2q(z);
where d(y,z,0) == min F(x, 2, v), p(z, v) == maxyey 2,y,,,2), q(2) == max p(z, v). and F' == m g(z). Obviously, this Lyapunov function is lower bounded, that is, & 2 E. To gain better understanding of the rationale behind the construction of Φ, it is observed that the Lyapunov function has a strong connection to the updates of the iterations. The primal update corresoonds to "primal descent" and gradient ascent in dual variable corresponds to the "dual ascent". The averaging updates of proximal variables could be understood as an approximate gradient descent of p(z,v) and an approximate gradient ascent of g(v), resulting in the "proximal descent" and "proximal ascent" terms in the Lyapunov function. Compared with that in [62, 40), we have an additional "proximal ascent" term. It is introduced by the regularized term for dual variable in F and the update of proximal variable v. Essentially, the "nonconcavity" of f(x, .) brings the additional term. With this Lyapunov function, we can establish the following basic descent property as our first important result.
Proposition 1 (Basic descent estimate) Suppose that Assumption I holds and r1 2 2L, 12 2 2XL with the parameters
1
1 ,0 a S min
2
1
< e S min
3(L + ))) GAT.
3\oo2
6Ld 5 + 5T.
24ri
2
< 8 S min
360r, + 5r + (2AL + 5r,)²'
384r1 (A +A+ 5)
+ 1)3
2(A+ + 5)
a22
0 < min
12(x + 5) + X21 6drz X + 5)
Then for any t 120 0,
4'-4'+1
2
71
x
++
x² 112 12 Ilyl - v yx (')) + 5, - 2+1 12+
12
72
1|o0 (2(+1) - 0011
32
15
4t
4r
311311=(==* 1+ (0(2(t11) - x(= .u (2
(1)
where 0 = 21 and La= = 11 +2) AL + r2. Moreover, we have (2, = pr d)n-1)
AL
V F(,(,,(,, 2, v)) and 04 (2) = 0 v+u(y(az22 2)) with the following definitions: (i) ayy, = argmin, Ex F(z, y, 2, v), (ii) y(2. 2, r) = argmax, F(x. 2, v). (iii) x(2, v) =
argmin,exx max F(x, y. 2, v). (iv) v(2) = argmax P(2,0).
The lower bound of & by F is established by its construction, so the crux of proving subsequence convergence is to establish the decreasing property of the Lyapunov function. Although Proposition 1 quantifies the variation of the Lyapunov function values between two consecutive iterates, there is a negative error term ||a(="+],, =((++1)) ||a(="+),u(<=+11) x(2++1, of (2++1))] that makes the decreasing property of
unclear.
Next, we characterize the negative error term in terms of other positive terms and then exhibit the sufficient descent property by bounding the coefficients. Conceptually, the error term is related to (2 oz((t)]] by the Lipschitz property of the solution mapping 2(2,-). However, (2++1) += || may not be a suitable surrogate since includes the information about the optimal solution o(2+1) Fortunately, with the help of the global KE property or concavity for the dual function (see Assumption and 3), we can bound the negative error term by (=(+1)) ((2++)]] (called the proximal error bound). The explicit form of this bound is provided in the following Propositions 2.
Assumption (KE. property with exponent of the dual function) For any fixed point x E X, the problem maxyey f(r, y) has nonempty solution set and finite optimal value. Moreover, there
5

---

exist r > 0, 0 E (0, 1) such for any x E 2, E EV
max ((r (1,, (a: -(,,)))) S
+ 01y(v)).
8' y'Ey
Assumption (Concavity of the dual function) For any fixed point X, fxx is concave.
Proposition 2 (Proximal error bound) Under the setting of Proposition / with Assumption 2 or 3, for any E IR"" E Rd one has (i) KE exponent 0 E (0, 1):
||=(= (2( -x(='t1 v(2(t1))11 wollof
wollof (z(+1)
111 -
(ii) Concave:
||+( : (2((t)) - x(ztt|, ,(2 S wi willb (z(+1) -b'l,
where wo =
2
(all-n)
r2-AZ and W1
4ng diam(())
1- + -x ) Here,
LyT
d)am()) denotes the diameter of the set V
Armed with Proposition 1 and Proposition 2, we establish the main theorem concerning the iteration complexity of DS-GDA with respect to the above-mentione standard stationarity measure for (P).
Theorem (Iteration complexity for nonconvex-(nonjeoncaee problems) Under the setting of
Theorem I and Proposition 2, for any T > O, there exists a E (1,2.... T3 such that
() Kt. exponent
E (2, 1): (xt+1, .111) is an OTT J-GS and 2 is O(T t --O if
3 S OTT 20
(ii) KE exponent 0 (0, }): (1'+1, ( is O(T and 1t+ is O if
32r1 jowa (2 diam()"))
(iii) Concave: (x , is an O(T-1) and 24+1 is an if O(T-
Moreover, when the problem (P) equipped with the widely fulfilled semi-algebraic structure [9, 4, 15] and the dual function satisfies the Kt. property with 0 E (0, z we additionally have the following sequential convergence result of the DS-GDA.
Theorem 2 (Last-iterate convergence of DS-GDA) Consider the setting of Theorem and suppose that Assumption 2 holds with 0 E (0, 1 Suppose that f(:,y) y) is semi-alge semi-algebraic and X, y are semi- algebraic sets. Then, the sequence {(x", y', 2², ,²)) converges to (x", yy z= v²) where (x", ,y²) is GS and z" is OS.
3.2 Universal Results
For connee-nonconccvc or nonconvex-nonconeaav minimax problems in which the primal function satisfies the Kł property, analogous results to Theorem can be established. This can be accomplished by introducing an alternative Lyapunov function RR" x Rdd R x Rdd - R as follows:
Vi (,,,,, h(,, z, v) F(x, y, 2, + h(, 2, v) p(z, + pl v) g(v) F (v)
Dual
Primal descent
Proximal
Proximal
where Mx,, 2, = max F(x, v, 2, g(v) = min p(z, v), and = max g(v). ZER"
yEy
vERd
is worth noting that our Lyapumov function exhibits symmetry with respect to nonconvex- (non)concave problems, since the adjustment only entails interchanging the position between (d(y, 2, v). q(2)) and (h(x, 2, u). g())). Therefore, similar convergence results as Theorem could be derived without any effort. A more detailed proof can be found in Appendix H.
Based on these results, we are ready to show that our DS-GDA a universal algorithm. By incorporating the choices of parameters, we can identify a consistent set of parameters that ensures the convergence of DS-GDA conconvex-nonconcave nonconvex-coneave and convex-nonconcave problems. The universal convergence rate is stated follows:

---

Theorem (Universal convergence of DS-GDA) Without loss of generality, we consider the case where X = L, implying L3 Ly L. For nonve-noncoocava. nonconvex-concen and nonconvex- nonconcave minimax problems that satisfy the one-sided Kt. property, if we further set rı = r 2 20T, DS-GDA converges provided certain parameter conditions are met:
(r L.VT2 141r + 1
8Lr + +
sc=
12L
6Ld
0 << 3 p S min 360r + +5r + (2L + 5r)22 9216r'
24r
cT2
12
O((T)))
12 + L3
When Kt exponent 0 E (0, 1. we further require
8 - 3
Av 2 max (wo (2 diam w2 diam (axammm()) (X))
where wy and W2 are the coefficients in Propositions 2 and 6. Then, (x'+1, y is an O(T
Remark It worth noting that our results are more general compared to AGP [57], where unified analysis for nonexx-onconccve and nonconvex-concan problems is provided. Here, our algorithm can also be applied to the conconvex-nonconcan problem with one-sided Kt. property. Moreover, our algorithm is universal, meaning that one single set of parameters can ensure con- vergence across all these scenarios. By contrast, different choices of parameters are required to guarantee optimal convergence in AGP.
Empirical Validation of DS-GDA
4.1 Universality of DS-GDA
To validate the universality of DS-GDA, we commence by providing a graphical description of feasible regions for the choice of parameters. Subsequently, employing set of symmetric parameters, we will show that the KŁ-nonconvex problems can converge to the desired stationary point, which supports universality results.
Without loss of generality, we consider the case where 1. In the pursuit of symmetric parameter selection, we initially fix B = = 1/5000, thus reducing the problem to determining only two remaining parameters: e and r. We then explore their relationships by setting ri = -22 127. and 1/(4r)). Restricting 0 S 41, 12 < 100, the feasible choices of l and l2 are selected to guarantee the first four coefficients in basic descent estimate (1) are positive. As visually depicted in Figure la, it becomes apparent that a large number of choices for r and are available to ensure convergence.
Next, we test our algorithm on a nonconvex -ow.onnceven problem that satisfies the one-sided KE property. With a set of symmetric parameters, we find that DS-GDA can easily converge to the desired stationary point. We first introduce the KE-nonconcave problems as follows:
KE-Noneoneave Example 2. which is studied in [58]:
The following example satisfies two-sided KE property with exponent
min max x² + +3sin(x)) sin(y)² - 4y² 10sin(y)
re yEy
where X' (2: 13. The only saddle point is =² [-";""] [0: 0].
From Figure 1b, we can observe that symmetric parameter selection is effective for addressing KE-nonconcave problems. To be specific, by setting Fı r2 = 0.125, = 0.04, 8 = = 0.8, DS-GDA directly converges to the saddle point, which validates the universal results in Theorem 3.
4.2 Robustness of DS-GDA
In this section, we compare the convergence performance of DS-GDA with the closely related algorithm S-GDA on some illustrative examples. Additionally, we report the range of parameters for these two algorithms to demonstrate the robustness of DS-GDA. To begin, we present some simple polynomial examples.
7

---

100
Initialization Trajetoriis
70 Feasible
-21
infeasible
40
-0.5
21
-0.5
0
0.5
(a) Feasible region of different t and
(b) Convergence of no-noncocevee problem
Figure 1: In Figure (a), the blue region indicates where convergence cannot be guaranteed. The green region indicates a series of parameters that be chosen to guarantee convergence. Figure (b) demonstrates the effectiveness of symmetric parameter selection for (non)convex-(non))onee))) problems.
Convex-Nonconeee Example
The following example convex-nonconeuse which is studied in
[13, 1}:
min max 2x²² 1222-22220 - + 4y /3 /4. =e yEy
where X' = -1 < and u" :=":y" "*] [0: 0] is the only stationary point.
KF Nf-NNoncoeevve Example The Kt.-nonconcave example considered here is mentioned in Section
4.1 (see equation (2)). The u" = [=":"""] = [0; 0] is a saddle point and the only stationary point.
Nomconvex--oncconean Example "Bilinearly-couuleed Minimax" example (3) discussed in [29]:
The nonconvex nowceoncoonccce example considered here is the
min max f(x) Azy f(y), =eX yEY
where f(=) = (2+
18-+1) 1)(2 1)(2 3) - 3), A == 11, and X = y fz: < 4). It does not satisfy any existing regularity condition, and the point = [ :''' = [0; is the only stationary point.
The extrapolation parameters z and v are initialized as æ and y, respectively. According Lemma 8, our algorithm terminates when ||z ell and |yy u|l are less than 10 or when the number of iterations exceeds 10". To ensure a fair comparison, we use the same initializations for DS-GDA and S-GDA in each test. The algorithm parameters are tuned so that both DS-GDA and S-GDA are optimal. other words, they can converge to stationary point in a minimum number of iterations. We compare the convergence of two algorithms by plotting the iteration gap ||u* u against the number of iterations for each example, where u* denotes the stationary point. Our results show that DS-GDA and S-GDA have similar convergence performance when the primal function is convex or satisfies KE property, as depicted in Figure 2a and 2b. However, for the nonconvex-nonconcan example where no regularity condition is satisfied, DS-GDA achieves much faster convergence than S-GDA, as shown Figure 2c.
To demonstrate the robustness of the proposed DS-GDA, we present feasible regions of all common hyperparameterss in Figure We tune the lower and upper bounds of each parameter while keeping other parameters fixed at their optimal values. As illustrated in Figures 3a and 3b, for examples that satisfy the one-sided KE property or with a convex primal function, the implementable ranges of DS-GDA and S-GDA for common parameters are roughly similar. In addition, the two auxiliary parameters for DS-GDA, i.e., 122 and μ. have relatively wide ranges of values, indicating that they allow for flexibility in their selection. However, for imconvex-nonconeee exhibits a wider range viable parameter values compared S-GDA. This observation highlights the robustness of DS-GDA when comes parameter selection (refer to Figure 3c).
problems, DS-GDA

---

50DA
1uA or
16
10
(a)
(b) KE -onconnavee
(c) Nonconvex Nonconvex-Noncooeawy Nonconccav
Figure 2: Convergence performance of different problems.
10
Rurge gunuidtos
Rurge garunctes
Range of permmeee
10
of 02
Parameters
12
Parumeters
Pizameters
Parameters
(a) Sunvex-Noneeonacee
(b) -Nonconcave
(c) Nonconvex-Noncooeen
Figure 3: Range of parameters for different problems.
4.3 Effectiveness of Getting Rid of Limit Cycle
In this section, we demonstrate the effectiveness of the proposed DS-GDA some illustrative examples that are widely used in literature. Notably, they not satisfy any of the regularity conditions in previous literature (i.e., Kt. condition, weak MVI, and a-dominant condition). We refer the readers to Appendix L for details on how to check the failure of these conditions for these examples. In addition to the violation of regularity conditions, it has been verified that none of the existing first-order algorithms can achieve convergence for all four examples. The detailed description of the four examples can be found in Appendix B.
To showcase the convergence behavior and effectiveness of the proposed DS-GDA, we compare with three other state-of-the the-hrterrtt art methods, that is, damped extragradient method (Damped EGM) [30], S-GDA [40, 62], and generalized curvature extragradient method (CurvatureEG+)) [50]. Damped EGM is guaranteed to converge under a-dominant condition, and S-GDA converges when the dual function is concave. CurvatureEG++ could converge under weak MVI condition, which the weakest. variational incquality- -based condition far as we know in the literature.
For the experiments, we use the same initializations of primal and dual variables for all four methods to ensure fair comparison. For DS-GDA, the exponentially weighted variables are initialized as the same values of the primal and dual variables, respectively. We stop DS-GDA when the differences between primal-dua variables and the corresponding exponentially weighted variables are all less than 10 b or when the number of iterations exceeds 10 For other baseline methods, we terminate them when either the number of iterates reaches 10a or the difference between two consecutive iterates less than 10-6
Figure 4 shows the trajectories of different methods with various initializations for the aforementioned four examples. We observe from the first column that our DS-GDA successfully gets rid of limit cycles in all examples. While S-GDA exhibits similar performance as DS-GDA, it is still not as potent in terms of its overall effectivvnnsss. Specifically, in the case of the "Bilinearly-coupled minimax" example, S-GDA gets trapped in a limit cycle, while our DS- DDDGA successfully avoids it and achieves convergence. The figure in the second column provides more details on this comparison. With the violation of the of o-interaction dominance condition, damped EGM either suffers from the spurious cycling convergence phenomenon or diverges to point on the boundary (see the third row in fourth column). It converges only when the initialization is very close to the stationary point (see the fourth row the last column). Similar results are observed for CurvatureEG++ (see Figures in the third column for details). Thus, the proposed DS-GDA outperforms other methods. It is the only

---

DS-GDA
S-GDA
CurvatureEG
Damped EGM
Bilineat- coupled
Forsaken
655
6-order poly
1.28
PolarGame
05
35
35
Figure 4: Trajectories of different methods with various initialization for the aforementioned four examples. The initialization of every trajectory is marked black star, the blue (resp. red) line represents the path (resp. limit cycle) the methods, and the red rhombus is the stationary point.
algorithm that can get rid of the limit cycle and enjoy global convergence for all these challenging examples.
Conclusion
In this paper, propose single-loop algorithm called the doubly smoothed gradient descent ascent (DS-GIAA) algorithm, which offers a natural balance between primal-dual updates for constrained nonconvex-nnoccocaan minimax problems. This is the first simple and universal algorithm for nonconvex-concave, nonvex-nonconcvve and manconvex-nonconcee property. By employing single of parameters, DS-GDA achieves convergence with iteration complexity of (4)-A) across all these scenarios. Sharper iteration complexity can be obtained when the one-sided KE property is satisfied with an exponent (0. 1), matching the state-of the-art results. We further conduct experiments to validate the universality and efficiency of DS-GDA for avoiding the limit cycle phenomenon, which commonly occurs challenging nonconvex-noncom examples. There is still a gap between theory and practice, and it would be intriguing to explore the possibility achieving global convergence for DS-GDA without any regularity conditions, This opens up avenues for research nonconvex-nonconee minimax problems.
problems with one-sided KE
10

---

Acknowledgments and Disclosure of Funding
Anthony Man-Cho So is supported in part by the Hong Kong Research Grants Council (RGC) General Research Fund (GRF) projects CUHK 14203920 and 14216122. Jose Blanchet and Jiajin Li are supported by the Air Force Office of Scientific Research under award number FA9550-20- 20500200---097 and NSF 1915967, 21 111999 2229012, 2312204.
References
[1] Leonard Adolphs. Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: curvature exploitation approach. The 22nd International Conference on Artificial Intelligence and Statisties, pages 486 186-495. PMLR, 2019.
[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. International Conference on Machine Learning, pages 214-223. PMLR, 2017.
[3] Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based the kurdyka-Eoojsseewicz inequality. Mathematics of Operations Research, 35(2):438-457, 2010.
[4] Hedy Attouch, Jéróme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, neward-backwerr splitting, and 2013.
regularized Gauss-Seide methods. Mathematical Programming,
[5] Hédy Attouch and Roger J-B Wets. A convergence theory for saddle functions. Transactions of the American Mathematical Society, 280(1): 1983.
[6] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust oplimization, volume 28. Princeton University Press, 2009.
[7] Dimitris Bertsimas, David Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464 501, 2011.
[8] Axel Böhm. Solving noncomvex--nonconcan min-max problems exhibiting weak minty solu- tions. arXiv preprint arXiv:2201 2022.
[9] Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, (((4):1205-120) 2007.
[10] Jérôme Bolte, Shoham Sabach, and Mare Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1-2):459 494,, 2014.
[11] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclusions and constrained nonconvex-noncee nonconcave min-max optimization. arXiv preprint arXiv:2206.05228, 2022.
[12] Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization. arXiv preprini arXiv:2210.03096 2022.
[13] Raphael Chinchilla, Guosong Yang, and Joao Hespanha. Newton and interior- -oont methods for (constrained) nonconvex-nonccocavee minmax optimization with stability guarantees. arXiv preprint arXiv:2205.08033 08038, 2022.
[14] Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.07280 2015.
[15] Michel Coste. An introduction o-minimal geometry. Istituti editoriali poligrafici internazion- ali Pisa, 2000.
[16] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sheed: Convergent reinforcement learning with nonlinear function approximation. In Interna- tional Conference Machine Learning, pages 1125-1134, PMLR, 2018.

---

[17] Cong D Dang and Guanghui Lan. On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators. Computational Optimization and Applications, 60(2):77-3300 2015.
[18] Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis, and Manolis Zampetakis. Stay- on-the-ridge: Guaranteed convergence to local minimax equilibrium in nonconvex-nonconcave games. arXiv preprint arXiv:22 10.09769, 2022.
[19] Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595 2010.
[20] Vladimir Fedorovich Dem't yanov and Aleksandr Borisovich Pevnyi. Numerical methods for finding saddle points. USSR Computational Mathematics and Mathematical Physics, 12(5):11- 52, 1972.
[21] Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan.
Efficient methods for structured nonconvex-noncconaay min-max optimization. In International Conference Artificial Intelligence and Statistics, pages 2746-2754. PMLR, 2021.
[22] Thinh Doan. Convergence rates of two-time-scale gradient descent-ascent dynamics for solving nonconvex min-max problems. In Learning for Dynamics and Control Conference, pages 192-206. PMLR, 2022.
[23] Zehao Dou and Yuanzhi Li. On the one-sided convergence of adam-type algorithms in non- convex non-concave min-max optimization. arXiv preprint 12X1::2109.1211,, 2021.
[24] Francisco Facchinei and Christian Kanzow. Generalized nash equilibrium problems. 4or, 5(3):173-210, 2007.
[25] Rui Gao, Xi Chen, and Anton Kleywegt. Wasserstein distributionally robust optimization and variation regularization. Operations Research, 2022.
[26] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.
A variational inequality perspective on generative adversarial networks. arXiv preprint 1802 2018.
[27] Ian Goodfellow, Jean Pouget- Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 1344144199414, 2020.
[28] Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragradient-basee methods beyond monotonicity: the case of negative comonotonicity. arXiv preprint arXiv:2210. 13831, 2022.
[29] Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for amncovve--nonconcat minimax optimization. arXiv preprint N0K.:20006.0666. 2020.
[30] Saeed Hajizadeh, Haihao Lu, and Benjamin Grimmer. On the linear convergence of extra-gradient methods for noncomvex-nonconcave minimax problems. arXiv preprint arXiv:2201.06167, 2022.
[31] Philip Hartman and Guido Stampacchia. On some non-linear elliptic instrrential-functioonn equations. Acta mathematica, 115:271-310, 1966.
[32] Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-mo max optimiza- tion algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning, pages 4337-4348. PMLR, 2021.
[33] Alfredo N lusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extragra- dient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2):686-724, 2017.
12

---

[34] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex nonconcave minimax optimization? In International conference on machine learning, pages 4880-4889. PMLR, 2020.
[35] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-Lojasiewiez condition. In Joint European conference on machine learning and knowledge discovery in databases, pages 795-811. Springer, 2016.
[36] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[37] Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. Advances in Neural Information Processing Systems, 34:22588- 22600, 2021.
[38] Daniel Levy. Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances Neural Information Processing Systems, 33:8847-8860, 2020.
[39] Guoyin Li and Ting Kei Pong. Calculus of the exponent of Kurdyka-LLojssiwwicz incquality and its applications to linear convergence of first-order methods. Foundations of Computational Mathematics, 18(5): 199-1232, 2018.
[40] Jiajin Li, Linglingzhi Zhu, and Anthony Man-Cho So. Nonsmooth nonconvex-noncen nonconcave minimax optimization: Primal-dual balancing and iteration complexity analysis. arXiv preprint arXiv:2209. 10825, 2022.
[41] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference Machine Learning, pages 6083-6093. PMLR, 2020.
[42] Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv: 1940, 2019.
[43] Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence theory for weakly-conven wowallyyyoooeewwwlllloooooomm weakly- min-max problems. Journal of Machine Learning Research, 12:169-1, 2021.
[44] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: (tVv:/70660088.. 2017.
[45] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.026223 2018.
[46] Arkadi Nemirovski. Prox-method with rate of convergence o(1 /t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251 2004.
[47] Maher Nouiched, Maziar Sanjabi. Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
[48] Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P How, and John Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, pages 2681-2690. PMLR, 2017.
[49] Jong-Shi Pang. A posteriori error bounds for the lincarly-constrained variational inequality problem. Mathematics of Operations Research, 12(3):474 484, 1987.
[50] Thomas Pethick, Panagiotis Patrinos, Olivier Fercoq, Volkan Cevherå, et al. Escaping limit cycles: Global convergence for constrained nonconvex-nonconeeee minimax problems. In International Conference on Learning Representations, 2022.
13

---

[51] Boris T Polyak. Gradient methods for solving equations and inequalities. USSR Computational Mathematics and Mathematical Physies, 4(6):17-32, 1964.
[52] Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
[53] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some dis- tributional robustness with principled adversarial training. arXiv preprint 1rXiv11710.10571, 2017.
[54] Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176. 1958.
[55] Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual ex- trapolation for coherent non-monotone variational inequalities. Advances in Neural Information Processing Systems, 33: 13303-1444,,, 2020.
[56] Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A tollow-the-ridge approach. arXiv preprint arXiv:1910.07512. 2019.
[57] Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for conconvex-concave and convex-nonconcave minimax problems. arXiv preprini arXiv:2006.02032. 2020.
[58] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimiza- tion for class of minconvex-noncoeeww minimax problems. arXiv preprint arXiv:2002.0962. 09621, 2020.
[59] 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.
[60] TacHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth problems with o(1 (1/ rate on squared gradient norm. In International Conference on Machine Learning, pages 12109. PMLR, 2021.
minimax
[61] Peiran Yu, Guoyin Li, and Ting Kei Pong. Kurdyka hooisskaatt.jjssiiiiieeeeeeeee Foundations of Computational Mathematics, 22( 2214:1177 2022.
via inf-projection.
[62] Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. A single-loop smoothed gradient descent-ascen algorithm for nonconvex-conent min-max problems. Advances in Neural Information Processing Systems, 33:7377-7389, 2020.
14

---

A
Organization of the Appendix
We organize the appendix as follows:
The related work and the four challenging nonconvex-nonconcei examples are listed in
Section B;
Notations and some useful lemmas such as Lipschitz error bounds are provided in Section
C;
The characterization of changes in the Lyapunov function between successive iterations is established in Section D;
The proof of Proposition is given in Section E;
The proof of proximal and dual error bounds are given in Section F;
The proof of Theorem is given in Section G;
The convergence proof for roncomve((covexx))oocccooe problem provided in Section H.
The proof of Theorem 2 is provided in Section I;
The proof of Theorem is provided Section J;
The quantitative relationship between different notions of the stationary point is provided in Section K;
The properties of examples mentioned in Section 4.3 are checked in Section L. We also show that the wrong selection of smoothing sides will result in slow convergence for S-GDA.
B
Related Works
There are three representative types of regularity conditions in the literature to restrict the problem class that algorithms are developed get rid of the limit cycle.
(PL) condition The PL condition (4) was originally proposed by [51] and crucial tool for establishing linear convergence of first-order algorithms for pure minimization problems [35]. Suppose that the problem max h(x) has a nonempty solution set and a finite optimal value. The Pł. condition states that there exist constant >> 0 such that for any x E Rdd
|Vh(x))1 2 [((x)
min M(x)
(4)
agRd
There a host of works trying to invoke the Pt. condition on the dual function far, [59, 47, 22, 58). Unfortunately, would like point that this condition is too restrictive and inherently avoid the main difficulty in addressing general nonconvex-nonconcan minimax problems. With Pł condition imposed on the dual function, the inner maximization value function ø(-) maxzey f(-2) is L- smooth [47, Lemma A.5J. Thus, the dual update can naturally be controlled by the primal since we can regard minimax problems pure smooth (weakly convex) minimization problems
x. However,
for general cases, the inner value function Φ may not even be Lipschitz. Recently, [47] proposed
so-called multi-step GDA method with an iteration complexity of (log )e 2). [22] further developed the singlc-loop wwo-timescale GDA method to better take the computational tractability into account and the complexity improved O( Following the smoothing (extrapolation) technique developed in [62], [59] extended the proposed smoothed GDA to the stochastic setting and
obtained an iteration complexity of O(c-a).
Varitional Inequality (VI) Variational inequalities can be regarded as generalizations of minimax
optimization problems [20]. convex-concave minimax optimization, finding a saddle point is equivalent to solving the Stampacchia Variational Inequality (SVI):
(G(n"), u u²) 2 O, Vu E.
(5)
Here u = [r: the optimal solution, and the operator G a gradient operator: G(u)) =
[V Vzf(z.v): f v)] with U X' The solution of (5) is referred to strong solution of
15

---

Another line of work is to impose the a-interaction dominant the VI corresponding to G and 44 [31]. For the nonconnccve minimax problem, without the monotonicity of G, the solution of SVI may not even exist. One alternative condition is to assume the existence of solutions u² for the Minty Variational Inequality (MVI):
(G(u), u - u²) 2 0, Vu E.U
The solution of (6) is called a weak solution of the VI [24]. In the setting where G is continuous and monotone, the solution sets of (5) and (6) are equivalent. However, these two solution sets are different in general and a weak solution may not exist when strong solution exists. Many works have established the convergence results under the MVI condition or its variants [21, 28, 45, 43, 42, 17, 55, 8, 23]. Although MVI leads to convergence, it is hard to check in practice and is inapplicable to many functions (see examples in Section 4.3 A natural question is: Can we further relax the MVI condition to ensure convergence? One possible way is to relax the nonnegative lower bound to negative one [33, 37, 11, 12, 21], i.e., the so-called weak MVI condition:
(G(u), u n²) P [G(n))?, Vu E.
2
Here, we restricted p E [0, 4 and [21] proposed Generalized extragradient method (Generalized EGM) with O)- iteration complexity. To include wider function class, [50] enlarged the range of p to [0, +) and p can be larger more curvature information of f is involved. However, for general smooth
problems, various VI conditions are hard check and p would easily violate the constraints. In this case, the proposed CurvatureEG+ still suffers from the limit cycle issue.
a-interaction dominant condition conditions (7a), (7b) on f, i.e.
ya (x. V f + V fxr ( + 2 (z, v)) V xy (x. = aI.
2 (x, + V (1, yy ()) '
= aI,
(7a)
(7b)
Intuitively, this condition is to characterize how the interaction part of f affects the landscape of saddle envelope (z, y) = minzex max.ey f(2, v) + - Ilv -il [5]. We say a is in the interaction dominant regime a in (7a), (7b) a sufficiently large positive number and in the interaction weak regime when is small but nonzero positive number. Convergence results for the damped proximal point method (Damped PPM) can only obtained for these two regimes [29]. Otherwise, the method may fall into the limit cycle or even diverge. Unfortunately, conditions (7a) and (7b) only hold with a = -L < 0 for general L-smooth nonconvex -onooeeccconnnccveeeee function, which will dramatically restrict the problem class. Moreover, second-order information of f is required. For instance, if we choose Exponential Linear Units (ELU) with a = 1 [14] as the activation function in neural networks, f is L-smooth but not twice differentiable. [29] studied the convergence of Damped PPM and showed that in the interaction dominant regime, their method converges with only one-sided dominance. In the interaction weak regime, their method also enjoys local convergence rate of (log((-1)) Taking computational efficiency into consideration, [30] developed the Damped EGM, which has iteration complexity of (log(E under two-sided dominance conditions.
par
There are four representative challenging have been mentioned in Section 4.3.
examples in the literature, which
"Bilincarly- minimax" example The first one is the "Bilinearly-coupled Minimax" ex- ample (3) with A = 10. It is a representative example to showcase the limit cycle phenomenon as breaks the a-dominant condition. When the bilinear intersection term between primal and dual variables, i.e., x and y, is moderate, it becomes uncertain which variable, either the primal or dual, holds dominance over the other. As a result, this particular example poses a great challenge in terms of ensuring convergence.
"Forsaken" example The second one the "Forsaken" example considered in [32, Example 5.2], i.e.,
min max (y - 0.45) + ((x) d(y), ZEX yey
where :====10 222 1-- - 6 and X' representative case, highlighting the limitations of min-max optimization algorithms. It demonstrates
< 1 This example serves as
16

---

Optimization problems
| 2/112. Function values
Optimal solutions
min Fz, 2,
d(y. 2, v)
a(y, 2(2,2,0)
rE
max F y/ 2, v)
2(2,2,0)
yEyy
min max Fzz, V, 2,
p(2,u)
aeX yEy
min 2,
p(z,u)
s(2, v) z(y(2, 2,
#eX
max d(y, 2,
p(2,0)
v(2, y(>(2, 2,
vEY
min p(z, v)
g(v)
z(v)
2E8
max max v)
g(2)
v(2)
veRd
Table I: Notation
situations where standard algorithms fail to converge the desired critical points but instead converge to spurious, non-critical points. Specifically, for problem (8), two spurious limit cycles exist across the entire domain. Worse. the one closer to the optimal solution y=";y"] ~ [0.08; 0.4] is unstable, which potentially pushes the trajectories to fall into the recurrent orbit.
"Sixth-order polynomial" example The third one is a sixth-order polynomial scaled by an expo- nential function. studied [18, 56, 13), i.e.,
min max max(4x² (y - 3x + 0.05x - -x.1--000(((((_--- exp(=)==000000( +)))) zEX yEy
where X' X'= f2: < 23. 23. It is shown in [56] that existing first-order methods will suffer ] = [0; 0J. As far as we know, all existing convergence results rely
from limit cycles around [x";y"]= on seden information. Therefore, it is intriguing to investigate the potential for ensuring convergence using first-order methods.
"PolarGame" example
The last example is constructed in [50, Example 3]:
1 where u y satisfy u E X' y with = - : -1 S 2 S 1} and & (2 y) = d(-1+2² +)) 1 + 16y²). It has been verified that there exist limit cycles at ||u|| = and ||||| f. which definitely make the iterates hard to converge to [=": = [0; 0j. To further demonstrate the effectiveness of our DS-GDA, we intentionally initialize the algorithm on the limit cycle ||u|| =
G(u) V fxx v = v) (y, 2²) + +
C Notation and Useful Lemmas
We first list some useful notations in Table 1. In the following parts, some technical lemmas are presented. Recall that rı > Lg and r2 > by.
Lemma For any x, x' E X. y.y E V. z R" and Rd. it follows that
F1- by | x' 121 < F(x', ( y, 2, u) F(x, (..,, (V, F(r, x' - x) S
Lu + 11
2
Ly T2 ly 2112 < F(x.8/ 2, Fl,,g, WV,Ffa,y,2.0
Ly 12 11y 3/ y/113
v) 5
2
Proof Since f is L-smooth (from the Assumption 1), we have
L | - r'112 < [ v) - [(x, v) - V=I(x,,)) -x) <
L
x - x 11,
2
2
(9)
Ly ll - = - f(x, v) (V.f(z, v). v/ - y) -
I
b1y - 3/ 11.
2
2
2|| represents the fn-nomm.
17

---

On the other hand, we know that
F(x's y, 2, 0) F( M, (V -x)
=f(d', v) [(x,9) (=](2, (1
11 || =112
x
=|?
(10)
2
=f(x'. 10--faa (zx 9) f))
1 1| x
and similarly
F(x, v/, u) P(x, y. (V, - 19)
= =s(, v/) -s(, u) - vv, r- u), y) r2
111 - 1 01
+
12
11y - -ol?
(11)
2
2
= =f(x, (/( - f(x, v) - (V y). - 11 ull?
Combing (9), (10) and (11), we directly obtain the desired results.
Lemma (Lipschitz type error bound conditions) Suppose that v2 > L,, + 2) Log. then for
any x E v. E e z' E _2n and v, v' E RR. Then the following inequalities hold:
①) |,<g/ xly, 2, w) s 01 oılly' vll.
(ii (=((,²''v) x(y. 2, w) S 0211= 2'11.
(iii) [[<(2',)) x(2,0)l $ x2||= - 2/|1.
(iv) [lv(2, v) v(z',0)) s os||= 2 - 2/1b.
(v) [1,(,, 2, - v(l',2, s a4||ar x'1l.
(vi) [1v(,, 2,0) - y(2, 2, o']l s 055|u v'Il.
(vii) [1((,,)) y22 r')l s 55.le v'1l.
where Lutri-Le 11-1,
-. 03 =
rids
+ 01 04
Letre-Ly and -12
p2
12-1u
Proof (i) From Lemma we know that
11 To
F(r(),2.0).v' F(x(y' 22 u).
|z(y, x1y' 2,, u)13
2
Ly 1 12
2( 20.. (V v, v,,
y)
|1 1/11?
2
Lg +
F(x(y', 22 2, V 2,0),,,,,)) 8/)
11 1/11
2
2(=(,,,,0). - F(x(v' v), L r1
-
Combining above inequalities, one has that (ri - x(1',,,,
< < Ly |2(2' x(y.,,,))l) - vll + L, - 1/1
(,) 5) + Lylly - y/11
where the second inequality is from Cauchy-Schin Schwarz inequality and L-smooth property. Let & = lo(y',2,0) 2(y, r)ll/ly 1/1 Then it follows that
Ly
Ly
e²
T
Consequently, utilizing AM-GM inequality we derive & < (iiiii) Again from Lemma we know that
Lytribee --
01.
m--be
71 Lr
F(a(y, (.cyy,,,).,,ddd F(r(y, 2/ y,
|a(y, 2, -xy,, 2,,22,,1]13 u)]1
2
(12)
L -r r|
2(z(y,2.0), F(x(g, // 2,
u)),,,,)
| 2, v) =(y, 2'),22,v)113
18

---

From the definition of F, we know that
F(z(y,2, 2), 2(x.2.2,))) = [ (2' + 2x(y, 2, v), 2), F(x(y,=' v,,,,, F(z(v,2',
(13)
2 (=+ 2x(y. u), x²)-
Incorporating (12), (13) and using the Cauchy- inequality, we have
(ri - (,),,, - z(y, =', u)1 - ri (1(2, v) z, u) z) Σ n [ - =(y, 2, e) = =||,
which completes the proof of (ii). Moreover, since maxyey F(, U.::) is (r L )stronggy convex in x, the similar argument leads to (iii).
(iv) We will now proceed to prove inequality (iv). From Lemma 1, we know that
r2 Ly (1v(2, u(2', u)]l?
d(u(2, d(v(2',)),,, 2
2,
2
d(y(z, u), _()(=..)).2/.))))
L, -22
r2
(1 u(2'. v)1.
2
On the other hand, we have
2, -(y(,,)),
2(0+ x²)
and
d(y(=', -(y)) [)
< Fla(u((,,)),,,0),,
2/ (2' (2' 2)) z).
Armed with these inequalities, we conclude that
(r2 L,))l,l(((z))) - 2(2', s (1(()((') ") =2)
<r 2' (0.ll((,,)))))))o w v) + 02|1z 2'1l)
$ <mall 2' (llbb() u( b)ll + 0100|1= - 2/113
where the last inequality is from error bounds (i) and (ii). Let & = (((,,)))((E',))) rige_ Using AM-GM inequality, we obtain < b { 12
we have
2--2||
1, v) y(21,0)) 2|2- z'1l
11 L,
03.
Next, we consider (v). Still from Lemma 1, we have the following inequalities:
r2 - Ly
- F(z, V(z,v(z', 22),
(1v(z,2,)) 2,
2
Ly -2 2))(,
- F(d', 2.0),
2
Ier + ri ||-- - x'122
F(z,y(z,2, - u(x,", u), W.
2
L 11 || x'112
P(dl,((d' 2,00,,,,, F(x, 2,0,, S W. x)
Summing them up, we derive that
(r2 - (,)1l(( v) v(σ' 2, v)l < Lz|1x æ'112 + L 2'1llv(z,,,,)) v(26, 22
19

---

Let E = I x--5'|
Then, have g² S
Le_ + r2-by & and consequently & r2
bettr-ly 19- ry-by d-
(vi-viti) From the definition of F, we get
F(2, - F(z, 22), = 12 (r' + -リー 1---2y0 2,
22,(2,,,0), u),
2
F(z, - ((,, u(z, 1'), 2,0) Moreover, by the strong concavity of F F(x, ' 2, U), we have
2 (v + v' 2, 1¹).
F(z,y(2,2,,)) 2) - F(x, u( v'), 2, 2 - F(z, 2, e') F(x, (z,, v'), S
b 2, - 2/?
2
Ly 12 l,, 2, v(2, 2, v' Il?
2
Armed with these inequalities and Cauchy-Schwarz Schwarz inequality, we conclude that
(r2 - Lg),lu(z, - u(x, 2, 12 - (2 2, v)' 21 v), u) - r2ll,(2,,2 2, 20) - y(2,2, u r'1l.
which gives the inequality (vi). Since d(,, v) min ,, v) is (r2 - -strnnlyy concave, similarly we can derive the Lipschitz property of y(z, v), as shown in (vii).
Lemma 3 (L-smooth property of dual function) For any fixed a E R", V RC, the dual function d(,,2, 2,0) v) continuously differentiable with the gradient V v,, 2,2) = F(r(( 2, v). y, 2, v) and
y 2, v) - vydly's 2, w)ll S Lally - y Il.
where La ==:=11 11 + Ly + r--
Proof Using Danskin's theorem, we know that d(., 2, v) is differentiable with Vyd(y,,, = 2)) v). Also, we know from the L-smooth property of ʃ that
(Vd((,,2,0) Vyd(v's 2, w))l = (1 - V, z, v) y' ,2, u)ll S , ((,,, v, 2, v), V, 2, b]
[V,, - V,F(((('',,,))) 2/ < 4,)1=((0'.2,0))- v)ll + (Ly + r2) s'll
$ (L + +r) - s/1 L.aly y 1/ll.
where the last inequality is due to the error bound in Lemma 2 (i).
Recall that (2, v) projy + a FF 2, v), 2, v)). Incorporating the iterates of DS-GDA, we have the following error bounds:
Lemma 4 For any 2 O, the following inequalities hold:
(i) | x(y², 2", I| S aallx=-1 1/11.
(ii llg*+1 y(0 2n, wt || S 0r1ly't1 1/1l.
(iii) ||y[(* u²) w'll asslis Ily'' v (2 v')l
(iv) |lg - y (2",2") & Ly ||* x't1l
where og =
+1 cri-ch,' 07
20rz+1 and og = a(r2-2,))
ltala
arz-aL,,"
Proof (i-iii) First, we consider (i), which is also called "primal error bound". From Lemma 1, we know that the mapping VzF(. y. 2, u) is (r1 --t-oolyy monotone and Lipschitz continuous with constant (r, + T.z) on set X' for all y E V R², dRd. Adopting the proof in [49, Theorem
3. I]. we can easily derive that
cla + er + 1
||x: =01'
|| - a'11,
cri cLu
20

---

which implies that
2cr +
||x 1a"t1-x(1") x0'' 2')l - || 2'1l || xly,, x. w')l
| +
x'1l-
en
ch
Similarly, since - F 2) is (r2 Ly) stronnyy monotone and Lipschitz continuous with constant (r2 + Iyy) J/ for all E X,= E Rd, E Red we can derive the "primal error bound" for V1 in the inequality (ii). As for (iii), notice that y(2, v) argmax yEy d(y, 2, v), the "primal error bound" is defined with operator v,d(,, v). Since d(-, 2, v) min F(x,,, 2, v) is (r2 Ly)- strongly concave, the operator - -Vyd(- 2, v) is (r2 Ly) -strongly monotone. Moreover, from the Lemma 3, we find V vyd(, 2, u) is La-Liscchitz continuous on y for all 2 E IR", u E R Thus, (iii) can be derived correspondingly.
(iv) Utilizing the inequality (i), we can further bound the desired term
1 - y4(=', (=',
= -/rpooy + av ((* ,8 20,2%,00)) proiy( 2" S sallV,F(t ,'',=",00 v²) 20 - Fay''' ,²',')) ,',,""","","")
solyll x2y',2',00 20), L ||," 2't
where the first inequality follows from the non-expansivity of the projection operator.
D Basic Descent Lemmas
Lemma (Primal descent) For any O, the following inequality holds:
1 L + r1
F( ut) 2 F(xtt1 ttth 2t11 rlt
|xrt1-
1111-x" ==111
2
F(rt1 .0' 20) - ) + - Ly
11 +
2 - 9
23 Ti 11112+11 - 2²122 + / 4 2
r2 72 - v2112.
2μ
Proof We firstly split the target into four parts follows:
F(x', y', 20, v²) F(x - 1 ,
F(x', 2t ,0) (( .1y" v') F(a'-1 , n² 2/ 20,2""")) F(x -y ,,,00)) )
F(o't1, 14 x², w0 F(alt1 yut , 1lt1 rt) + Flalt1 tltl 2411 tll v0) Flalt1 yet 1 2441 ((t1)
((t)
As for Q) have
ri Lg
F(x", 2., - F(x't1 ,2,2", vt) 2 (V,((zt (('.2"" 22"22)) -
a 1+1
x'11
2
1 L + rı
|| 1
2
where the first inequality is from Lemma and the second is due to the projection update of x++1, i.c..
(o eV, F(x', y², 2", v²) - (+1 x² x x++)) s O. Next, from Lemma one has for the inequality
① that
F(r4+1
. v 2 20 F f . 25, w0) 2 F 22,2",,,, 2", 2",)) + 12
Ly
1
++1 -y 11.
2
For@. top of the update of 1+1 ie, 2t| 2t + 3(x++1 - =²"), we obtain
F F( ++1 20, 20) - F(alt1, n , 12²) 2
2,3 r || - 20112
21

---

Similarly, as for @ following the update of vf+1, i.,, v r² + ply v²), we can verify that
F(x vtt 22,1,,,0 - F(x ytt t v 11 -
110tt - -011p.
2p
Combining all the above bounds leads to the conclusion.
Lemma 6 (Dual ascent) For any 2 0, the following inequality holds:
dly +1 , d(y': , + (2 1)r2
vt
1 | 1/112 +
2p
rı 12 (2 + - 22(y 2+ ,
xt1 -²)) 20),22+11 2²) +
2
( F(x("" , v²), s 2., ,'), y - -yy) - Ld bl - 1/1? 2
Proof The difference of the update for the dual function is controlled by the following three parts: dlyft1, , , . - d(y'; v²) d(y't1 1+ ,t1 -1t1)- d(y't +1 21t ,²) + dly't1 2tt1 v²) dly'tt ,²", 2²,0²)
dly'+1 x² 22,20) d(y', 2',
For the first part, following from the update of u1+1, we have
12 (1ly
11122 10--1 01-1113) (2 (2-1))2 |u't1 111/
①
2
2/1
For the second part,
,2 ,2,00²) v²) 2 F(x(y" 1+1 211 22,,,,0), v'), ++ 2011 0t) F(x(y" 41 211 3 1+1 22, 2t)
F'xly'+ ++1 ,2 +11 (ott,,'),, t , 0t) F(a(y ,²)=²²) 2²), ), +2
71 (2 +2' 2 +1 x²),2t+1 - =²)-.
2
Finally, consider the third part, from the Lemma we get
Le
( F(x(s', x², v²),") v", x², v²), w - w²)
1
3 111
2
Combining the above inequalities finishes the proof.
Lemma (Proximal descent) For all 2 O, the following inequality holds: <(>') 2 g(= (1)
+ Ti (a +
_t1 +
2x(2", ((2 - 2111
Proof From Sion's minimax theorem [54], we have ((=) = max p(2, v) max min max F(I,8,,,,) #Et wEY
= max ((x(,, v), ())
max =( v),
Thus, it follows that
((=²) ((x M(x(=' v(20))))))))))))))))))))))))vv (zz")),²",,(())) - Ma((2*+1 v(2 ((2++1)), s141 (6(2
2 h(o(2* 002 (2, u(, - h(x(2 1+1 u ((2 2tt1, ((2(11))
h(z(et u(" 1), 2(2 - n(x(2 u(2 2 ,
F(x(=", (22tt)))) ((2 244 u( +( )), 2 ((2)
F(x(e", (oo(""u(2tt))) o(s )), (12 () (((
2 (2" + +2411 2x u(2 - 2(1)).
The proof is complete.
22

---

E Proof of Proposition 1
From the results in Lemmas 5, 6, and 7, we know that
(1
L +
(a' y. 2", ,0) 2 ((x ,//t1, =t11, r +
1 | - -1011 +
c 2
r2 Lu Ltd
1115 r/122 + (2-
|| - -2/112- +
23
(2 p2r2
11 -00122 + (V 2 10)))))0 getl yr
2p
2(V y F(x("", 22,,00)) V. 2², v²) Vy F(x
tt 18) +
2r (=(2" v( )) xly 1+ 1t1 ee t+1 x²)
xly't1
For the part ① using the projection update of y'+ we have
(V,F(ett) -v', 2", 2²), y y²) 11y 11g"tt+11 112
The part @ is due to the Lipschitz gradient property (see Assumption 1) and error bound (i) in Lemma
4:
2(V Ffr(' v', y² 2¹, 2²) - (x y2, 24, v²), y- y²)
2 20,1|I11² / 2t, v0) - + I11 8/1l
2 Loo +1 - 1/22 Ly00 | - 112
2 4.08ll1 1+ - 1/112 2 - -, + - x21
As for the part @ for any n > 0 it follows that
2r (x(=", (c(="(u(zz+1)) - xxy +1 ,141, ,2),, x1+1 =²²
2 1 - 2²) + 2r, (x((= (2 - x(y 1,,,,,2t1 , v.) 2022 - -2-) = (2r1( (o(( - x(2 (()
2 - -2r1o2ll2 - 111 = || - 211 - - +1 u v((x+t))) - x(y't1
+1 _ )²
where the inequality is from the Cauchy-Schward inequality, AM-GM inequality, and error bound (iii) in Lemma 2. Hence,
$ (xx' v² e²)
(xx .3 141
211 (11)
Lx +r1 by
T2 Ly
|| 1441-x11 =211
Los -,,00 11 11122+
6
α
2 3
1
|| =12 (2 p)rz
Ti
20²
|1 00113-
23
13
2/1
Fi [111 2(22 (2(+11)
x(y" +1 2111 w1)11
Next, we focus the negative term. From the fact x(2,0) u(v(2,0), and a(y,2,0)
xyy, 2, v²), the inequality @ is bounded as follows:
||x(2t+), v(2+t))) - x(y'+1 ++1 2211,, 2f)22
$ 211x(2*t1 tirtt,, -(((+())) a(='t), , (2 + 21|x(==*1, .o4 (2
- x(y +1 ,, (o4t,,') (2)l
< t41 21 =(= (2 ))1² + 20
++1 y(alt1, of (2 (1)
(14)
Here, the second inequality is due to the error bound (i) in Lemma 2. We can further simplify the second error term by (ii))-iv) in Lemma 4 and (iv), (vii) in Lemma 2:
Ily² y( +ff(=**** 1212
< <3|lg/+1 - 2(22, N² + 3l)u(2', u²) v(2 , + (1 ,00) v(2 24 24((2+2)))
61.30² "001''' - 1|2 6(as + 1)?1lv' v ( 011 + 30311=" - 112 + 30 100 of (1?
(15)
23

---

Plugging (15) into (14), we have
|k(xtt), ((z(tt)) - x(y ,,,
S 21|x(2/ 22) - z(s wt 1)| + +
1
1207(08 + 1)911y/ - 14 of)l + 60 - -/1 + - -f
Summing the above inequalities and letting $1 = Lutt Ly 82 + 1-4 L = - L.
and 83 == =1 29 - 202- - a,) we have
((x', 3², 2¹,, 0²) (1 y +1 2041 (1
- =29/2 (2 -iy2 1 - -012--
2 81 111/ - 1113= + +211y - 112 + s3 -
2μ
12rnnL - 0,00 o - x 1| 12r noT (os + +1)?11/ - 3 (2+, ,²))) 1|1 6r, 6rrno000311 -
Gr 6rikajo3llu* -
1 v(2(+1)) 21 1+
xx2tt1,,,000100 ef (2(+1)1)
= (s1 - 12r, kT o - 1| + 22 1 - y/11 + (83 6r ) || - =2112+
(2- 12 (2-1)12 |1u v 111 - oranoio3 11' (1 12 1)?|ly' - 32 =1)
2p
2r trin|a(==*11 v)( (|ll==l
=x2 vt (2(+1)))
(16)
Moreover, to make the terms in the upper bound consistent, by error bound (iv) in Lemma 4, we have
1ly 1/1 ス lly - sa,, 2²) 1lg y (2', o')11
(17)
1 lIv' - (=',", - Laa2oolle* x²+111 112
Similarly, we provide lower bound for || - 1²112 as follows:
1 1100 - of (2 |12 || 10:41-1:1 (2((1)1)
||0541 - 1/ 2
1 - r4 (2) - n²2 (4L3a'o21 - 111 1(08 +) 3 (2', +0)
20ā 111)
(18)
Recalling that vf 1) = ot + u(y(ztt), : o²) - v²), the last incquality can be obtained by using error bounds (iv) in Lemma 2 and (ii). (iv) in Lemma 4, ie..
|100t1 - (2 = 1² 11 v(x(t1,10))
S n² (211
+ 211x(2z', 0²) (((=++1,0001? sx² (41.a 2 x' 1 + 4(0s + 1) =f + -033 11)1)
u( )²)11
Substituting (17) and (18) to (16) yields
((x', y² 2 v²) (1 +1 20+1 101)
z (s1 - (12r 82 + (2 - 1)) Lg a² a²00) || -x011
(²2
882 - (12m) + (2 - n2)22) (1 + os)2) 110 -
2
(8s - (w(2 - m)) + 6r, ko) )33) ||ا² - 2 1 + (2 12)r)22 Gr orfoof 1|0 uu- (2 x(2 (2
4p
2r 2rin|la(z*t1 111 (2(2(1+1 (((
Recalling that Ly = ALz, we have the following results:
* As ri 2 2L,, we have 01 = l.g 2Ly similarly, we find 03 = r2-by
+ 1 I Ly Ix +1 = X and 02 --n < 2. As 2
.rdi + < Ly
r((A+1) + 2 and 05 = b b
$ 2. With these
24

---

bounds and set v: : 2,3 with 0 < 8 I min 360r, +50r (22, +5r, 384r1 B1(1+1)3 and
2
a12
0 < < min
2(A+55)
(4+5 } we derive that
abi
(2 - p1y22
6r k
r2
48(A
1)
2p
4
12
1
12aa
Y2
>
2
2
8(1 + +5)
41
and
aI.yb
1(2 - p)r2 + Grikot S 2r2 12r, B(A + +1)2 <
(19)
16(A + 5)
With the upper bound (19), further bound the coefficient of || - 2" ||? by
83 - (1(2 - 12) + Gr(no]) d3
1
rI(A
+ 1)²
4r 4ri 1
27
- 4
+4+
B
2
28
16(2
+ 5)
12
Ly
1
9
11
+ 1)
L3
Ly
+
B
3
2
16
20r
53
Let L.t
2
and 3c
Ly 2
Then, we have 1
c 2 max (T + r1), 6T.p).
2
3c
6c"
2r 11-112 22 1 4
which implies that 51 2 dc
and
0g
Let _ - Lyo
and
La 2 6a
Then, we have 1 2 max Ly 6La} and
a
3a
3a
$2 2 6a + r2-by
2 0g
r2 by
+a
S
ora
2
x x 4. With these bounds, if we further assume
that 1 2 5/2- >
5yy we obtain
a
82
(12M2 + 22 - 12)2)) (1+ oz)²
2
1
122
Ly
aL?
4
4(A+5)
+
+
+
12x
8(1+ 5)
0212
ar2
1
Ly
(A + 5)al
L
+
y
12a
4
8(1 + 55a
8
4
1
(A
+
5)
1
72
60a
8
90a
15
and
1
a aTT,00g
2
81
(12r1Kof + 82 2pp(2 - 1) 11
2
6c
8(1 +5)
3
2 1
13L,
2Ly
6c
2500
3
7Ly
1
T1
2 6c
2
2
10
24c
32'
where the first inequality is due 3a
2 Lyog and
1
T2 Ly
1
12 Ly
$2
L,0g La
L L - (01
+
1)L,
-
a 2
a
2
a
Putting together all the pieces, we get
(xx' v² (2"00) 0²) (x 2+1
, _t41 , 11 F1 || 111 + 12 11'"" 24 (2 (12%,0')1 01) 32
2
112
+ 12 4
|| 110 (z 2/122
15
53
4r 011811((=+)1 ++ 112 =(= ( (2
The proof is complete.
25

---

F Proof of Proximal Error Bounds and Dual Error Bounds
F.1 Proof of Proposition 2 under Assumption? 2
Note that 2(,,2,)) 2, = ma F(; F. is (ri L sttrongly convex. Hence, we have max h(x(==*) off (2*+1)), tt v) h(*(=*t) (), x ((=+t)))
h(x(2*+1, 2 (z*+1)), 2t 2tt1,,02'" ,0(2t()) h(a(2tt1,, / uuz 2),
2t1 r(2
(20)
L |x(2*t|, of (z(+1)) z(2"t1, ((eet,,(=((+))]
On the other side, by leveraging the Kt. Assumption 2, h1, 2, satisfies the Kt. property with same exponent [61, Theorem 5.2]. Thus, we get
max M(*(=*)), 14 (z*+))), )), , -((((tt),,, ,=(=*+1)), )), x( ,((
S max (axxh((tt!!,_. w4 (), v) M(x(2tt), (2(+1)))), 2 ,0 (z
(21)
1 <V of (z/+1)) 1+1 w (=(+t))))1 S T
where the first inequality is because
1), a v(2*+1)) = maxh(x(2*t)) 2 .)) h(x(2*+1, u(2 ((2**()),++))))
2 h(x(2 uf (z)+1)), 2t41 of (2(+))).
Next, we further bound the right-hand part. Recalling the definition of ut (2++1) and with the bound (vii) in Lemma 2, we obtain
[Voh(a(z , un 1), (x+++())
rellut (14+1) - u(x(==+t) 41 of (z (2(+))) 2441 (2
= -r21((1 uiy + uy(z"* (+1 ,u') - y(2 (
(22)
S r2(1 - =1]llu² - u1= 1-1 ,,0)] + rallu( e+1 (t) y( uf (2
(1 (1-11 11)
S
+ os ||l| (2 - =²1l
Combining (20) (21), and (22), we have
2 || ()(( x= o(2(+1)112 S (ri LT)T
(r2(1- p)) + r200) ) (2(t1))
1
The proof is complete.
F.2 Proof of Proposition 2 under Assumption 3
By the strong convexity of h(. 2, v) = maxyey F(; V. 2, v), we have
h(a(z*t1, vf (2(+1)) }), 2t11 , ((((+1)) - h(a(2t11, of (x(+)))) st v4 (2(+1) 2 h(((2+11 H1 wf (ct+1)) )), 2t11 1 ((=(t))) - M(((ott1 ((o(ttt,,(2ttt))) 244,
(((e)t ((2 2 71 Lx l0t of (2++)) 2((tt1,0(2(tt) ,022+1))112.
2
On the other side,
Ma(2zt2 ut (2( 1t1 x1)) - M(x(2
of (2(+1)), 2411, 2(t1,, 2 (2(()) +t!1 .of (2*+1)), 2(2 - of (2
$ (V.h(z(z*t)) (2 2t
1 p + tos) ||l| (3 - 11
< 2idim()))
26

---

Here, the first inequality is because h(2,2,-) = maXgEy f(r, y) - 2 lly - -12 is concave [52. Theorem 2.26]. The last inequality is from (22) and the fact that || S diam(Y), which could be derived from mathematical induction. Moreover, v(z) = argmax, maxxey / (x 2, v),
2 || 2, 2) =|I² - 2 lly - } should satisfy e(z) = prox ((36,2.)))) (ot -. - + (z(e)) [52, Theorem 2.26], which indicates that ||u(=)]| < diam())). Thus,
||x( e4, (2 ===tt,,,110/0000000,1_1 v(2 = 4r2 diam(J)
(1 12 + 0s) l10| (z(+t) 1'1l
r1 Lo
11
F3 Dual Error Bounds
Before presenting the results, we first introduce some useful notation:
(y, =) :- argmin (xx v) + 2 || =11².
x x=))) = argmingex maxyey (zx y) + -1 21|2.
(2) == projy(v + a f (y. 2),
Proposition 3 Suppose that Assumption 2 holds. Then, we have u)1 S wellv 8]2,0)1 (x) =22,,)11
where W2 T(m T.
2r
Proof By the strong convexity of o(. 2) = maxxey [(: y) + 7 -2112 we have
max f(z(2,)), v) + 2 |,((, 2112 max f(z" f(='(2), y) マタ | [z - 2|1
yE)
11 17
Lz
2
1 - x2,, e11
2
On the other hand, we have
max
f(x(2((()))) v), + |,((, u) =11² max (x*(z),))
ri //1 (100(2)) =112
vEy
2
wey
I wey /(x(1,((())0) v). v) + |=(2,)) - =212 (f(x(2,)), x)) + 212 || v) - =1(2)
2
= max f(x(2,0),)) 3) - f(x(2, v), y(2,
vey
Recall that x(2, v) = argmin maxzey F(x, 2, v). Then, the first inequality is from the fact that
max f(x (zx -1 [x) =1|² max min [(x, + vEY
æ =||
Ney sE
2 min f(z, ((,,,((2)))) + fi | =12 sex
+
||,(2, v) - =112.
2
Under Assumption 2, we find that
max f(x(z,)), v), u) - f(x(,(( v), u(, v)) < - dist(O, - (, u)) + (1)) yEy
||2( v(2 x))1
where the last inequality is due to the first optimality condition of v(2,0) argmaxyey f( z, v), z lly 21l2.
Proposition 4 Suppose that Assumption 3 holds. Then, we have IIx=()) x(2, 2) < walle 2(2, v)1l,
where Wg == 4ry diam())
T1
27

---

Proof We first define 2)
f(z,y) + 2 || =||2 and (()) =
argmaxyey yey min,ex (1 v, = yrgmaxyey o(zn, (2, Let y²()) be an arbitrary
solution in (x). By the strong convexity of (6. = f(:3) + 1 we have
(x((2, u). v (2) -000,, v), 2 ((z(2, (z), - 20 (x), v (2),
2 11 L. | [x) - =(2
2
Here, the first inequality is beacuse (2x= (2), = m (ar, (v. v. (an (y(2, 2), (2. ((z(2, ((2, On the other hand, by the concavity of (x),;)),
-0((, u(, 0), - ((2)
- -((2
S r (2))((,,)) - (1))) - y(2,0i]]
- 2r diam()))lo(zz,)) - -Vl-
The second inequality is due to (V,f(x(z,, w), y(2, v)) (v((,,)) v), (z) the last inequality is because both y" (2) and y(2, v) lie in set S.
u(2, v)) < 0 and
G Proof of Theorem
Before presenting the proof of Theorem 1, we first introduce the following lemma.
Lemma 8 Let 0. Suppose that
max || 11+1|| 11yl (4 ||2² -
1110 - wtt111 (oot-1 {
u s Sc.
c
a
B
Then, there exists p > O such that (1++1, )(+ is PE-GS.
Proof In accordance with definition 1, we just need to evaluate the two terms d0s V f 1)+1 + 01 x1x(x(+))) and dist(0, Vyf(z++1 y + )l We first
note that
x = projx - cV F(x 3 22 = argmin xEX
- 24 2',
Its optimality condition yields
0 0E 1 - x² + cV of (") + +
which implies that
(o'- - V v=f(z't) - E Vaf(a'tl, (((aatl."'t/) ,/ + +1xx(1+t))
V V=f(a',') ('))
Then, we are ready to simplify the stationarity measure as follows:
di, Vaf(a't1, , + (2x+)))))
+ Lo ||02 - x' _11ll || + r rall - 201 + L Lally' - y
c
- + Toe + rı + T topoos ) 1|,0" - x4
+ 12 2| - -1t11| + Tea 11 v/ w())
3
P1 Le + r2 - L3 + (2r1 + 1)bedby
10"0" x1+1 || + /z || - اا + L ll v vi(=", [-
c(ri l.n)
11 1 (=':00)) ||اا || } S c. Similarly, we have lo'-otti||
|
The last inequality is because max
c
3
1 a
-y+) -r2(2-22=---0 - 0²) vf
- 1 E -Vyf(att1, 1.ff((tttttt1111 + (y (1),
28

---

which can be directly derived from the update of y Then, we can simplify the expression
dist(O. -..vo -ooo . + )1v(v(t))
+ Ly) l1y' - -1 + r21lol - -1
+ (2= + Try + m2) Inovoallal - x2 + 22 1106 o 11
+ Tny +12) 110e
aa
1 + by + 12 11 - v (z', e0)|
+ [n(1 + by + +r2)(2n + 1)
1| 1lt1|| + 2 l|oe - rl+1|l
dr1 Luz)
|| | S e. The proof is complete. In' | I1o* - a
The last inequality is due to max
Proof of Theorem 1 Firstly, it is easy to check that (2x, Mr z, v) is lower bounded by F. Let
Ç =
max
T1 32
|a +1 - =²11?, 15 llv' v4 (z", e0)1
5B
Ti
1| - -x 112
4y
T2
ll lof (zf+1)
111 }.
Then, we consider the following two cases separately:
There exists t (O. T 13 such that
2 s 4r 4r101la(2 +
- =02tt1,, 24,(22 (212.)
For any E {0, ,,.1,...777 T 1}. we have
1 z z 4r, Ar1Blla(=*** ,((att1)))))) ==(*+1,, (ost),,400 (=(=*t)))))
We first consider the first case. If the KE exponent A E (2. 1). then from Proposition 2,
3//
(1 - u²12 s
||a( ,((t)t))))))))))))))))))))))), - x(2 of ())1
r2
32r1
| (2 - -
r2
Then, we have |ll (z(+1) 1²ll S p1 where P1 = /32m 28 bound other terms as follows:
Armed with this, we can
|| - 101
2563
||
, _1(2++1)) - -x(2't1, , (2(+)))))
c²
2563ws
lo
(2 (1) 0/1 = 12
c²
l1o - (2 0112
12
||a
(2t1 ,u((++2)) - x<2tt1 (2
a
r
120r,3wp
(2 - - = p3 -
< r2a2
||
2012
W 40/l (+1 .0(2(+11)
- -(2 . (2(+)))1 S (u(t1) -2 = pe
8²
|
v² 12
21lu4 (2++1) 1/112
+ 24TT3 l11aa 12 + 4(0s + 1)9111" 1/" )11
112
112
200 1p2)
< 2p²
g gztn + 883 a 20000000'000 0
p2 - + 8(os + 1)322p233t50
p3. 32 + 3
112
< 20
29

---

where P2 == 25
12 Pi Pi-P3= P=:= r2a Pf 04 == 40wopf and ps == 2pi # + &T p2 + 8(as 1)8a²ps p3 + 40zp3. According to Lemma 8, there exists p > 0 such that (xl+1, , is a pe-Gi, where c maxf /P2 /P vpis /P }. For the general concave case, the
3/2
c²
above analysis holds with 0 = 1 and (x' is a p max VprB, vPs,S, vpy J-GS by replacing wh with w1.
One remaining thing is to prove that 2 is an 0(3 O-OS. By the dual error bounds in Proposition
3 and error bounds in Lemmas 2 and 4, we have
|| - x² (xl+
$ $112411 - 2-11 + 11 - x1+1|| || + || - xxy' ,0,, e')) +
- x(s",,")) +
||=(2" rt) =x(=+t,,,000 .'']l + |||[[=/||, ,0') x (z (2]
$ (1 + 02) 11 - -11|| + ||' | + t0ol|=² 11 + +100sl1 (2'2,"))) +
w2llet - y0 : , 2
s / #/ー + v vp pi + (06V (108/)+ - + wap ح
= -(
(23)
Now, we consider the second case. Since
( y', 2", e²) ((x y²+h 2 , 21
T1 |z - 2²112 + 12 lyy nタ (z', )²2
+ T1
| - 11
+
12 8p
|u (2 - =2211
64
30
10,3
holds for t E 10 T - }} and (x. 2, 2 F. we know that
11 ,0 ,000,000 -F F
T-1
Σ
141 -x x2112 12++ +
T2 30
Iyy y4 (2", o0) 10)11
1|= 1/
+
T2
10 (2 - 1011
10,3
8y
T=0
ric?
r
1i
|| 2912
11y
2 Tmmin
+
64
30
10'
8
c²
a²
ric²
r2a²
7i
T2
||
2/1
(z - 2²
Tmin
64
30
10"
8
3
122
Since ( U, 2, v)
F, there exists a t {0, I.....,T T 1) such that
| - 11 || - v (2', )1
1|2 - 2 - 12
11
vf (11
max
a²
3
n22
$ (xx0) yo 20 20,000 - F
11
T min
ric²
raa?
11 ran
64 1
30
10
Note that
| ot 12
21104 (2 - 11
- 2/212 + + 1)2||ba 14 ( 1²
1²
72 02+ 8l300000 oze² + 8(as + 1))02 + 403
20 2¹ - 2 111)
< T
ps
where Ps = (7 =2 3LZa200ee + 8(008 + 1)²a² + +40)). Thus, we know there exists > 0
such that (x.+1,10 ) is a PC-GS, where c = V 0g- Similar argument as (23) shows that 211
is an O 1 O-S. Moreover, if we choose 3 < O "/-1, when the KE exponent 0 E (g) 1) VTB
(T))))
and 8 O(-
1) for general concave case, the two cases coincide. We conclude that under KE
30

---

assumption, (x'+1 ") is an O(T de )-GS and 2 is an O(T do J-OS. When the dual function is concave, (x'+1, , is an A-GS and 2 is O(T - --OS..
Next, suppose that the Kt exponent E (0. 21. From Proposition 2, we obtain
| (((2+t,,((((tt)) x02 (2 < wolluf (21+1) - e²1l
(24)
S wi (2 diam -2 || ( v112.
The last inequality is from (2 - w01l = y ( wt)
rl1l f 2 diam()) since || s
ttiam()), Armed with the homogeneous proximal error bound (24), we have
((x v', (xz00") - D(att1 -u*!! , ,
2
ri || - 111 +
r2 lly v (2", 01)11 +
ri
11
11
+ 12 1104 (2/+1)
1-:4+1--00 - ut212
32
15
5/
Ap
Bwo (2diam (2)) - 1o (2* - r'11
4r
11 g+ - 211 +
12
Ily (2", w²)1
2/1 || - 112+
32
15
5,
4r, BBo (2 diam (2)) 3 -2 || (z(+1) - -
4y
2
11
|| - 22112 + r2 lly v' (2" 11 + ii
||
1|2 + + 12
|1 (2 - r²1??
32
15
53
8p
where the last inequality is because B S 32r diam())) The rest of the proof is similar to
that in the second case when 0 E (g. 1), and we conclude that (1+)) is O(T --GS and ++1 is an b-r-S
H Convergence Anaylsis for (Non)oonvex-Noooonccee Problems
problems can be established with the symmetric property of our Lyapunov function. Specifically, we can derive the following Proposition by doing an easy transformation of (z, z, r1, r,, B, Izz) to (y. v, r2, O. Ht Lyy):
Similar convergence results for (non)convex-noncon)
Proposition 5 (Basic descent estimate) Suppose that Assumption I holds and r 2 2L, 12 2 2AL with the parameters
4
1
2
< S min
, <<c min
3(AL + r2)) 6L S
3Lo 22 6Ln 55/++5L)
24r2
cI?
< μ min
360r2 + 5r32 + (2L + 5r2)²
384r2(A + +1
2(A + +5)
cL2
<< B S min
1((A+ + 5) + 1 64r1 + 5)
Then, for any t 2 0,
T 11(11 >
r2
x²
2 10,, + T1 I1y' +1 112 + T2 1
11 +
T1
|| (1-11)- 211
32
15
5fp
43
Araully 2+1) x21 - 812 (1 (11 ,
where d' 1 and Ln ( +2) L rı. Moreover, we set (2, = projx a(13 -1
cV FvF 2, (x), v)) and 24 (V) := + [(>(((22 ()) 2,), - with the following definitions: (i) 108(2,0) v) = argmin yey m F(x,y, 2, v), (ii) 2(b) == argmin.eR= P(2, v).
To handle the negative term the basic decrease estimate (Proposition 5), we would impose the following assumptions on primal function:
31

---

Assumption 4 (KL property for primal function) For any fixed point E V.2 2 E RR, and E R the problem min F(x,y, y, 2, v) has a nonempty solution set and a finite optimal value. Moreover, there exist > 0, 01 E (0, such that
91 S _disst( dist((,, V=I(z,u)+ + +xxx(x))
[(0z y)
min s(x'. x'Ex
)
holds for any y E y and X.
Assumption (Convexity of the primal function) For any fixed point y V. f(-y) is convex.
Proposition 6 (Proximal error bound) Under the setting of Proposition 5 with Assumption 4 or 5, for any 2 E RR, v E Rd, we have
(i) KL exponent 01 E (0, 1):
llv(=1 (o(+1), vlt1) v(z(1)t1), 2/111112 ) S w2ll2 ( - =1:
(ii) Convex:
11u(24 (utt1), (,ttt)))))))))) y(=((ot)), 111 w3||=4 (1²t1) - =
B + i d and W3 == 4rg dinm(x))
where W2 == (y 11 denotes the diameter of the set X.
6 + 02). Here, diam(X)
r-- by
Equipped with these results, we could also derive similar complexity results for (non)convex- nonconcave minimax problems as Theorem 1.
I Proof of Theorem 2
In general, analyzing the local convergence rate of sequences could be challenging. Fortunately, when 0 E (0, 2) the homogeneous sufficient descent property holds as follows:
(a' u/,,,, =z..e" ,²) (xx'11, -,/+1 2 x(+1)
ri 1+ 1²1 + r2 lly - 3 (24, 00)2 + ri 1| - 2122 +
6r2
10f (2(11)
( - v2122.
40
20
48
25μ
Consequently, we can the unified analysis framework in [3]. Next, we prove the "Safeguard" property as required there.
Proposition 7 ("Safeguard" property) There exists series of parameters vi, 12, U3, V4 0 such that for all E (0, 1,.... T - 11, the following holds:
dist 2
@ (x t 1
< 11 - xltil| + velly' - v4 (z',,")) + vzlle' - ot (2(+1)) + -ull=" - 2111l1. -
Proof We observe from the update of ++1 argmin - 11-x-(2x--0 (x--oV cV F( Fzzt,"". 2f,,2t,e))) and
g'+1 = argminyey llly (v' + a (x 1ft 2", v²) ))12 that
E t1 - x² + cV F v. ,0 20,0²) + 01x(x*+1)
(25)
E y +1 - y¹ - a F F( 1+ 1 2', 0²) + 01 y1 +1).
Moreover, we have
04(x* 41 ,141, 1241
(v. 141 gt1 x1+1) (1x(x()))
(V,4(att)) +1 2411,
x(11) ,0t1,
2V 2V 2t11, 0(41) + 01y()
(V.F(a +1 241,, ,t ,(1)) 2V 241 (1 + 2V 2v=((<+1])
(V.F(x 2t1 001) 2V. 2+1 , |
32

---

This, together with (25), gives
dist(0, a0 y g 24t1, ()-1))
x² xtt1
+ wytt) , ,2 (ott)
y' n
+ FV +1 .
F /+1 20 ,ett) - 2V yd(c , 200-1 (11)
a
|n( - ) - 2r1 (= ++] s(y t1 اtب )) + 2rl (2 - xxzlt2 v0= ++ I)][+
1r2(y(11- -
(26)
Under Assumption I and utilizing the error bounds in Lemmas 2 and 4, we can simplify (26). When et reaches the local region that satisfies B||xr(z', + - = S 1, we can show that the right-hand side is actually upper bounded by the linear combination of the desired four terms:
dist (0, (1 y/tt 2011 o 1)
[ + Lu + +n) 1|0 11 + I flyy' - y +1 + r 1| 21+ + a
_ +
S
T.p +
12)
1102 y1
c
24 1//111/t1 11 - xly r1 , ,,t + r2llo - / 11 1|///11111111/ -
2r ||((1] 111 ; , , (2) - x(x -(= |||ا| + +2 41 11
Sn 1/1 - x1111 11 + v2ll8' - v4(2 (2", e')ll + 2| - (4 )| + valle' - -
Here, 1/2 = 1 Lg + rı + o6 + 2r 2r10 L + (Lg + 1 + Ly + 2r + 2L Ly U/2 = L + 1. + Tyy +r + 2 + rı (20) + () + 1), 1/3 = 3 + +2 + -2210100 + 1203, and + 22101105 + 2r / Moreover, since ((: and -) is semi-algebraic [10, Theorem 33, using results in [10, Example 2], we find that (zz, y, 2,
14 1r
Fzx, v. v) -2(ly, 2, 2g)x) is also semi-algebraic in I, y, v. Based on Assumption 1, (xx y, 2, U) is continuous in I. 2, v. Building on the unified convergence analysis framework in [4], we can conclude that {(x', y² 2t )²)
converges to one stationary point (x", "." 2², v²). On top of Lemma 8 and lim I| - x t
0, lim 1yy +1 0, we have {0 y²)} actually converges to GS. For 2 we have
|| x² '=''il
< 11 2²11|
+ || - 2(0', 2 D-)l + | 24, =(=", et)l + ||<((",, - -0)=",)))=='(" (='))l
2 21|
+ x alo v o')ll + walle - =y(=" r')ll
B
21 - -11
+ +oolla" - - 010001110 11' v (z w')ll + w2 | -
B
11
-011 || + 20, | - x² 11 + 2(00 + 1)lb (2", u²) -
Since lim ||2 +1 || 0, lim ||0² - +| || 0. lim I1y vi (zt, 10000 (2(+
0.
lim I|0
to
+xx
t00
O, we conclude {2") convergs to an OS.
J Proof of Theorem 3
Here, without the generality, we assume Lzg = Tyy = T. and r = 12 = r. Then from the Proposition
1 and Proposition 5, we can easily derive the bounds for all the parameters as follows:
3L(2or + 1)2
r 2L, 0 <c= min
< <1,0>
(27a)
3(L
6Ld 5V66
2(r - L)2
0< 3 = p < min
24r
cL2
12
S OT
(27b)
360r + 5r + (2L + 5r
9216r'
12 + L2
33

---

There are numerous feasible choices for 3 and that satisfy equation (27b). Next, we will demonstrate the existence of viable solution for and a by establishing the intersection of the last two constraints in equation (27a). Solving these constraints under the condition r 27. yields
(r- L)V 14Lr + r2 L 8Lr + <c=as (r LVv22 14Lr + + L2 8Lr r
12L,
12Lr²
where should further satisfy > 14T. Combing these with the penultimate constraint in equation (27a), we can provide a set of feasible parameters as follows:
20L, - - L 14Lr + + L 8Lr +r
1
sc=
(28)
12Lr
6Ld
Armed with equation (27b) and equation (28), we finish the proof of Theorem 3.
K
Relationship Between Different Notions of Stationary Points
In this section, we illustrate the quantitative relationship among several notions of stationary measure.
Definition The point (z. E X x y said to an
e-optimization game stationary point (OS) if
prox max flom)
(2) - 20| S
C-game stationary point (GS) if
dist(0, vzf(z,v) + (1x(z)) s e, dist -0,00,,,.. vf
01y(1)) Sc.
Recalling that x² (=) = argmin,ex maxzey f(I, v) + 7| -
2| we have
prox masucy f6-a0) +1x (x) -I (x* x||. With Proposition 3, we are ready prove
the relationship between OS and GS.
Proposition 8 Suppose that Assumption holds. If (x. X X is e-GS, then it is (1.
Building on the proposition 3, we have
||~ (x) æ1 I || (x)) - x(x, v)1l + ||,[ v) - x|l
w2 |yy y( y ||,[,, y) x:ll
(29)
we [yy v( r)|| || (I, æ|| + 01 lly - y(2, 8)ll-
By the nonexpansiveness of projection operator and error bounds in Lemmas and 4, we can further bound [yy 7(2, v)]l as follows:
- -
S 10lllpppppiy(tttoo/fff..xx.)11
< <asll hugp:-/hhhhhuuaoo///u..////----d
< 5slly |ctp::/:....eh....k.....///1/110
z(y, v)
< <ssly <ell0-~~jhhccco|--Hoooo444444110
4,00s| 20y 2,)
< (2 a + (2, - x)
Plugging this bound into (29), we get
||0" (x) - x1 v σ + aL., + ar2) |ly - y w)1l + (Ly + 1) || a(y,r,))1 We (4,0as|| - x x, v) + (2 + ab, + ar²) aslly - ,(2, v) +
34

---

Next, we will explore the relationship between || - 2(y, u)|l and dist(0, V fxx d1x (x)) Let x. (y, 0) projx ,V,P(z y, x, 1)). Then, from the primal error bound (see [49]),
know that
| - z(y. x. u)|l v cho - cTi + ||
x+ (v, w)]l.
CT chب
Moreover, since V V,F(x.y,,,.)) Vz x: y), it follows from [39. Lemma 4.1] that
cم + c +
| - z(y, 2.
|| x (v,
1 ch2
c12 + cri +
|| proix cV cV..(
er claz
cL2 + dist V.f(z.)) -00x)))))xxx)))))
r1 - Lo
similar analysis can be applied derive the bounds for |yy y(, 2, y) Thus, (2, c-GS, then it is an O(emin(1.2) J-OS.
L Details about Examples in Section 4.3 and Behaviors of Wrong Selection of Smoothing Sides in S-GDA
This section will check all the regularity conditions for the examples mentioned in Section 4.3. The violation of the global KE condition can be easily vertified by plotting the figures for these exam- ples. Therefore, conditions, which are two representative classes of conditions in the nonconvex-nonconcal setting. Moreover, we will also give example showing the slow convergence caused by the wrong selection of S-GDA.
mainly discuss whether they satisfy "weak MVT" and "a-interaction dominant"
L.1 Proof of Proposition for "Forsaken" Example
This subsection considers the "Forsaken" example in [32, Example 5.2] on the constraint sets 1.5 S = S 1.5). In [50], it vertified that the "Forsaken" example violates "weak 1 21. Therefore, we only consider the a-interaction dominant condition
= (2 =
MVI" condition with
here. By simple calculation, we get [I,, v) = 1 62 5x.2, V V (1r, y) = f y) = 1,
and V ( - + 6y² 5 Armed with these, can be found globally by minimizing the
following:
V2 fxx v) + V2y (z,,)((11 fx p.. fxr
-1
6x 5x +
6y² + 5
less than zero when [z: v] = 11:0]. That is, a < in the constraint set X, which means the a-interaction dominant condition is violated for the primal variable æ. Similar proof could be adapted for the dual variable. This rules out the convergence guarantees of damped PPM, which is validated
in Figure 4.
L.2 Proof of Proposition for "Bilinearly-coupled Minimax" Example
This "Bilinearll- Minimax" example is mentioned as a representative example where is in the interaction moderate regime [29]. Experiments also validate that the solution path will be globally trapped into limit cycle (see Figure 4). For this reason. we only check the "weak MVT" condition. In this example, X' = y = {2 -4 < 2 < 4}. G(u) = v (I, y); y v)l = [Ar 20r + 10y; 4y² - 20y 10x], and u² = [0: 0j. Then, p can be found by globally minimizing
p(u) = (G(w),u=")) for all E X x V. Notice that [[(0)) (G(u), u u-=" u²)
x² 1²a 5x² 53y2
[[(
(2x3 10r + 5 + (2n3² 10y 5
We have p(u) = (G(w).u-n**
89 when u [x; y] = [0; 1]. which implies that p < 8g
[[]]]
Moreover, we find T. 172, so < 89
1 = 1. We conclude that this example does not 344
satisfy the "weak MVI" condition and the limit cycle phenomenon is actually observed in Figure 4.
35

---

15
20
25
50
Itenations
Figure 5: Converegnce behavior of DS-GDA and different smoothing sides for S-GDA.
L.3 Proof of Proposition for "Sixth-order polynomial" Example
We demonstrate that this example violates both the 'weak MVI' and "a-interaction" conditions. To provide evidence of this violation, we follow the same approach used to prove violations Sections I..1 and I.2 and present counter-examples On the one hand, we found that p S p ()) -0.0795 <
-0.0368 = z with = [x; vl = [=1; 0.5], which implies the violation of "weak MVT" condition. On the other hand, we have
V (x, + V [ (2. (21609 exp(- (0G60)eep(--/5)))(((51())) + (77061 (aspp-1/1000)////11
V (x; y)) V2 yz (x, y)
[=:0]=(0:1]
(4989 exp exp((=11000))
It is less than zero when 1) 2 L. which indicates the violation of the a-interaction condition.
L.4 Proof of Proposition for "PolarGame" Example
In this subsection, we check the conditions for the "PolarGame" example. Firstly, have S p(ū) 00.722 < -0.0039 = 27, with à = [0.8; 0J. Thus, it does not satisfy the "weak
MVT" condition. Next, consider the following [ [0.8;
V fz v) + (2. V (z)((z,))) 'V? of (z.
[a:y]=[0.8;0]
= =1/(n- - 2799/256)) 779/125.
is less than zero when 1) 2 L. Thus, the "PolarGame" violates the a-interaction condition.
L.5 Wrong Smoothing Side S-GDA
For S-GDA, show that if we choose the wrong side. it will result in slow convergence. To validate this, we conduct a new experiment for the KL-NC problem
4y
min max f(x, y) = 2x y2 4xy zEX yEy
3
4
where X' y
(2: 1}. With wrong smoothing side, S-GDA (with primal smoothing) leads to slower convergence compared with dual smoothing (see Figure 5).
36


Reviews:
[{"review_id": "1ayX7yhlDI", "reviewer": "Reviewer_pZz2", "summary": "Constructing a method that finds an optimal point of nonconvex-nonconcave problems is of interest. Built upon the \"one-sided\" smoothed GDA (SGDA) that exploits the Moreau-Yosida smoothing technique, this paper studies the \"doubly\" smoothed GDA (DSGDA), applying the smoothing to both the primal and dual variables. As an illustration, this paper considers four challenging nonconvex-nonconcave minimax problems that do not satisfy any of the regularity conditions considered in the literatures and that none of existing methods work. It turns out that the DSGDA is the first known method that works for all four difficult problems. To complement this empirical success, the authors theoretically show that the DSGDA converges to a stationary point under an one-sided KL condition. (The aforementioned four problems do not satisfy the one-sided KL condition.) The authors also present that the DSGDA works for a wider range of hyperparameters than the SGDA for nonconvex-nonconcave problems.", "questions": "* Line 33: Why does no player inherently dominate the other in nonconvex-nonconcave problems? Later in line 50, the authors claim that the primal player becomes dominant for the nonconvex-concave problem. Then, consider a nonconvex-nonconcave problem that is locally nonconvex-concave at some stationary points. Then will the primal player suddenly become dominant locally?\n\n* Line 34: How do you achieve a good balance between primal and dual updates in this paper? Of course, applying smoothing to both variables improve the balance, as claimed by the authors. However, the choice of regularization parameters $r_1$ and $r_2$ and step sizes $\\alpha$, $c$, $\\beta$, $\\mu$ are not the same for both variables. At this point, I am not following what it really means by the good balance.\n\n* line 83: In what sense, is this work the best known convergence analysis?\n\n* Are there practical examples that satisfy the one-sided KL property but not the one-sided PL property?", "limitations": "This work has potential but the gap between the practical claim and the theoretical claim seems not negligible, and I think that the paper could have been better if such gap was further reduced. For example, an experiment with one-sided KL where DSGDA outperforms SGDA could have better supported the paper's claim.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The proposed DSGDA methods empirically converges to stationary points of four notoriously difficult minimax problems, while other existing methods do not, which is impressive.\n- The authors shows that the DSGDA converges to a stationary point of nonconvex-nonconcave problems with one-sided KL property. The method achieves the best known rate for a more restrictive setting that the dual function satisfies either the concavity or the PL condition.\n\n", "weaknesses": "* The DSGDA does not outperform SGDA under the one-sided KL setting, where the proposed DSGDA is theoretically shown to work well. Would it be possible to show that the SGDA also converges under the one-sided KL setting? Or instead, would it be possible to show that it does not converge? Are there other methods that work under the one-sided KL setting?\n* As mentioned by the authors, there remains a gap between the theoretical claim and practical claim.\n* The robustness claim is only based on one nonconvex-nonconcave experiment. In addition, the region of convergence of DSGDA for the nonconvex-nonconcave case is relatively small, so it does not seem to be sufficient to claim that DSGDA is robust (even though it is relatively robust than the SGDA).\n* The choice of hyperparameters that guarantees convergence in Theorem 1 is complicated, so it is not easy to find an optimal choice in terms of the rate, making it difficult for the users to choose.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments. We hope the clarification that we emphasize may help for a better understanding of our contributions.\n\n**Q1: Does SGDA converge under the one-sided KL setting?  As there other methods that work under the one-sided KL setting?**\n\nRecent work [1] has demonstrated the convergence of the SGDA under the one-sided KL condition, and it is currently the sole method to have a global convergence guarantee under this setting. Despite this, DSGDA still outperforms SGDA due to its universality. Please refer to the global response to Q1.\n\n**Q2: Gap between theory and practice.**\n\nPlease refer to the global response to Q3.\n\n**Q3: The region of convergence of DSGDA for the nonconvex-nonconcave case is small, so it is not sufficient to claim that DSGDA is robust.**\n\nThe NC-NC example ($a=11$) we evaluate in the paper (Figure 3(c)) is already an extremely challenging case as SGDA fails to converge at $a=10$. The challenge stems from the difficulty in identifying the dominant side. Thus, the problem becomes easier and the range of parameters becomes wider when $a$ becomes larger (see Figure (e)-(f) in the **PDF**). To further corroborate the robustness of DSGDA, we provide the parameter ranges for several less challenging problems when $a=11.6$ and $a=13$. It's evident that both robustness (see Figures (c)-(d) in the **PDF**) and fast convergence (see Figures (a)-(b) in the **PDF**) of DSGDA persist across these NC-NC problems.\n\n**Q4: It is not easy to find an optimal choice in terms of the rate.**\n\nThe choice of parameters will not affect the convergence rate. Actually, all parameters only relate to the Lipschitz constants of the gradients $L_x, L_y$. Please refer to the global response to Q2.\n\n**Q5: Will the primal player suddenly become dominant locally for local NC-C problem?**\n\nThanks for pointing out it. We would like to clarify that dominance is a global concept. One player is said to dominate the other if its decisions determine the convergence no matter how good action the other player has done.  For NC-NC problems, there is no player inherently dominates the other and the local structure plays no effect on global convergence.\n\n**Q6: How do you achieve a good balance between primal and dual updates in this paper? The choice of parameters is not same**\n\nThe unbalance between primal and dual updates in minimax raises from the different optimal directions and these related changing quantities of two players. That is, one aims to minimize the function value, while the other aims to maximize it, making it hard to guarantee the sufficient decrease property of a function. Thus, achieving a good balance means that we can construct a novel Lyapunov function that possesses the \"sufficient decrease\" property (see Theorem 1). Here, the parameters are not the same in general. They are precisely controlled to ensure the 'sufficient decrease' property, achieving a good balance between primal-dual updates. \n\n**Q7: In what sense, is this work the best-known convergence analysis?**\n\nThanks for your questions. We will clarify this point in our updated version. \n\n* **NC-C:** DSGDA attains both the $\\epsilon$-GS (game-stationary point) and $\\epsilon$-OS (optimization-stationary point) with a complexity of $\\mathcal{O}(\\epsilon^{-4})$, matching the sharpest rate among single-loop algorithms for NC-C minimax problems. \n\n* **NC-PL/NC-SC:** DSGDA attains both the $\\epsilon$-GS and $\\epsilon$-OS with a complexity of $\\mathcal{O}(\\epsilon^{-2})$, which is already optimal.\n\n**Q8: Are there practical examples that satisfy the one-sided KL property but not the one-sided PL property?**\n\nPL property is only defined for unconstrained problems, while KL property is more general and can be applied to constrained (nonsmooth) problems. Additionally, even in unconstrained cases, PL condition is a special case of KL with exponent $\\theta=\\frac{1}{2}$. Hence, KL functions are considerably broader than PL functions. Many constrained minimax problem examples will be that case. More specifically,  we may consider the widely considered max-structured problem $\\min_{x\\in\\mathcal{X}} \\max_{y\\in\\Delta} y^\\top G(x)$,\nwhere $\\Delta =\\\\{y \\in \\mathbb{R}^d:\\sum_{i=1}^d y_i = 1, \\ y \\ge 0\\\\}$ is the standard simplex. Such a problem arises frequently in machine learning applications, including distributionally robust optimization, adversarial training and fairness training. It can be shown that this problem possesses the KL property with exponent $\\theta=0$ for the dual problem under the mild condition that there exists $\\delta>0$ such that $\\max_{i\\in [d]} G_i(x^*)\\ge G_j(x^*)+\\delta$ for $j\\in[d]$ satisfying $y_j^*=0$, see [1] for details. Moreover, the constrained NC-SC and NC-PL problems all satisfy the one-sided KL property. For example, the nonconvex-regularized variant of DRO problem and multi-class classification problems mentioned in [2] possesses KL property with $\\theta=\\frac{1}{2}$ for dual problem. \n\n**Q9: An experiment with one-sided KL where DSGDA outperforms SGDA could have better supported the paper's claim.**\n\nThank you for your suggestions. To further demonstrate the superiority of DSGDA over SGDA for the NC-KL case, we have included an additional experiment, see Figure (g) in the **PDF** (the example we test in the global response to Q1). As we have mentioned, the universal applicability of DSGDA has been clarified in the global response to Q1. We further support it with the new experiment illustrated in Figure (g). Notably, DSGDA, even without prior knowledge, demonstrates faster convergence upon entering the local region of the stationary point. This efficiency contrasts with SGDA, even when equipped with the correct smoothing side.\n\n[1] Li J, Zhu L, So A M C. Nonsmooth nonconvex-nonconcave minimax optimization: primal-dual balancing and iteration complexity analysis.\n\n[2] Zhang X, Aybat N S, Gurbuzbalaban M. Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems."}, {"review_id": "O2q16fhWfI", "reviewer": "Reviewer_gc6W", "summary": "This paper introduces a novel single-loop algorithm called the doubly smoothed gradient descent ascent method (DSGDA). DSGDA effectively balances the primal and dual updates, eliminating limit cycles in various challenging nonconvex-nonconcave scenarios in the literature. The paper establishes that under a one-sided Kurdyka-Łojasiewicz condition, with an exponent $\\theta\\in (0,1)$ (or for convex primal/concave dual functions), DSGDA can discover a game-stationary point with an iteration complexity of $O(\\epsilon^{-2\\max\\{(2\\theta, 1)\\}})$ (or $O(\\epsilon^{-4})$), respectively. These complexity results match the best outcomes achieved by single-loop algorithms for solving nonconvex-concave or convex-nonconcave minimax problems, as well as problems satisfying the restrictive one-sided Polyak-Łojasiewicz condition. \n", "questions": "**Main Questions**\n\n1. Relation between OS and GS: I would suggest including further discussions in the paper regarding the relationship between OS and GS notations. It appears that there exists a translation method between these two notations, as mentioned in [1]. Elaborating on this relationship can greatly enhance the paper's quality and comprehensibility.\n\n2. Odd constants in Theorem 1:The extrapolation step in the algorithm introduces exceedingly large constants, which might seem counter-intuitive. Although the calculations on Page 23 provide some insight into their derivation, further explanation is required to clarify the reasoning behind these values and make them more understandable to readers.\n\n3. Connection between theory and practice: Considering the paper's objective of addressing limit cycles, it would be beneficial to establish a clearer connection between the existing theory and the role of DSGDA in avoiding such cycles. Elaborating on this relationship would significantly enhance the paper's overall strength and clarity.\n\n4. Unconstrained setting: While the paper focuses on the two-sided constrained setting, it is worth noting that some existing papers tackle the scenario where only the domain of the max variable is bounded, as demonstrated in [1]. To enhance the paper, it could be valuable to discuss the disparities and challenges encountered in the unconstrained setting, providing a comparative analysis between the two scenarios.\n\n5. Stochastic setting: It would be interesting to see if similar theoretical results can be obtained in the stochastic setting as provided in [2]\n\n**Minor issues**\n\n6. I would recommend not directly using “nonconvex-nonconcave” in the title as the paper does not consider the general nonconvex-nonconcave setting.\n\n7. I recommend not using “SGDA” to represent the smoothed GDA as SGDA is well-known for stochastic gradient descent ascent algorithms. Using “S-GDA” and “DS-GDA” instead would avoid confusion.\n\n8. Line 77: The size of the right parenthesis\n\n**Reference**\n\n[1]  Lin, Tianyi, Chi Jin, and Michael Jordan. \"On gradient descent ascent for nonconvex-concave minimax problems.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Yang, Junchi, et al. \"Faster single-loop algorithms for minimax optimization without strong concavity.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n", "limitations": "The paper is theoretical and does not have any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: The paper provides a comprehensive discussion of existing algorithms for mini-max optimization problems and introduces a novel algorithm aimed at avoiding limit cycles. The proposed algorithm is supported by both theoretical results and empirical validation, strengthening its efficacy.\n\n**Quality and Clarity**: The paper exhibits a high level of writing quality, featuring a well-structured presentation that is easy to follow. It effectively employs examples and explanations to enhance comprehension of both the algorithm and the underlying theory.\n", "weaknesses": "**Significance**: While I acknowledge the valuable contributions made by this paper in terms of algorithmic and theoretical aspects, it is important to note that the current theory relies on one-sided KL or one-sided convex/concave conditions. Considering the paper's objective of addressing limit cycles, it would be beneficial to establish a clearer connection between the existing theory and the role of DSGDA in avoiding such cycles. Elaborating on this relationship would significantly enhance the paper's overall strength and clarity.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy that the reviewer enjoys our paper and would like to thank you for your insightful comments. Below we provide a point-by-point response to your comments and questions.\n\n**Q1: Connection between theory and practice: It would be beneficial to establish a clearer connection between the existing theory and the role of DSGDA in avoiding such cycles.**\n\nThanks for your advice. We will add additional discussions in our updated version. \n* All existing work for NC-NC problems relies on restricting the function classes to achieve convergence. There are mainly three types of regularity conditions in the literature, PL condition, VI-related condition, and $\\alpha$-interaction dominance (see Appendix B). With PL condition imposed on the dual function, the inner max function $\\phi(\\cdot)=\\max_{y\\in \\mathcal{Y}} f(\\cdot,y)$ is smooth and we can regard minimax problem as a pure smooth minimization problem. VI conditions regard the primal and dual variables as integral and update them together, which does not follow the nature of sequential games. The one-sided $\\alpha$-dominance condition imposes the dominant player before the game. Instead, we address the NC-NC minimax problem by achieving primal-dual balance through algorithmic developments. We believe the double smoothing technique is an efficient manner to get rid of the limit cycle. \n * Extensive experiment results also validate the power of DSGDA (see Section 2). To the best of our knowledge, DSGDA is the first algorithm, which can converge on all four difficult examples in literature. We admit the theoretical result of DSGDA is restricted to one-sided KL (convex/concave) cases.  Although there is a gap between practice and theory, we hope it opens a new path for studying and developing new theoretical frameworks.\n\n**Q2: Relation between OS and GS**\n\nThanks for the good question. We also have such GS and OS translation results: **If $(x,y)\\in \\mathcal{X}\\times \\mathcal{Y}$ is an $\\epsilon$-GS, then it is an $\\mathcal{O}(\\epsilon^{\\min\\\\{1,1/2\\theta\\\\}})$-OS.** One should be noted that our algorithm-dependent result (Theorem 2 for the proposed DSGDA) will achieve the GS and OS at the same rate, which is stronger than directly applying the translation result when $\\theta\\in(\\frac{1}{2},1)$. We will add the proof in our updated version and here is a proof sketch.\n\n**Proof Sketch** Building on the Proposition 2 in Appendix, we have the following bound of the measurement of OS:\n         $$\\\\|x^*(x)-x\\\\|\\leq \\\\|x^*(x)-x(x,y)\\\\|+\\\\|x(x,y)-x\\\\|\\leq \\omega_2\\\\|y-y(x,y)\\\\|^{\\frac{1}{2\\theta}}+\\\\|x(y,x,v)-x\\\\|+\\sigma_1\\\\|y-y(x,y)\\\\|.$$\n\nBy the nonexpansiveness of the projection operator and error bounds in Lemma 2 and 3, we can further bound $\\\\|y-y(z,v)\\\\|$ as follows:\n$$\\\\|y-y(z,v)\\\\|\\leq \\sigma_8 \\\\|y-y_{+}(z,v)\\\\|\\leq  L_y\\alpha\\sigma_8\\\\|x-x(y,z,v)\\\\|+\\left(2+\\alpha L_y+\\alpha r_2\\right)\\sigma_8\\\\|y-y(x,z,v)\\\\|.$$\n\nNext, we will explore the relationship between $\\\\|x-x(y,x,v)\\\\|$ and $dist(z, \\nabla_{x}f(x,y)+\\partial1_{\\mathcal{X}}(x))$. Let $x_{+}(y,x,v):=proj_{\\mathcal{X}}(x-c\\nabla_{x}F(x,y,x,v))$, then from the primal error bound (see [3]), we know that \n$$\\\\|x-x(y,x,v)\\\\| \\leq \\frac{cL_x+cr_1+1}{cr_1-cL_x}\\\\|x-x_{+}(y,x,v)\\\\|.$$\n\nMoreover, since $\\nabla_{x}F(x,y,x,v)=\\nabla_{x}f(x,y)$, then following from Lemma 4.1 of [4], we get\n\t\t\t$$\\\\|x-x(y,x,v)\\\\| \\leq  \\frac{cL_x+cr_1+1}{cr_1-cL_x}\\\\|x-proj_{\\mathcal{X}}(x-c\\nabla_{x} f(x,y))\\\\|\\leq  \\frac{cL_x+cr_1+1}{r_1-L_x} dist(z, \\nabla_{x}f(x,y)+\\partial1_{\\mathcal{X}}(x)).$$\n\t\tThe similar analysis can be applied to derive the bounds for $\\\\|y-y(x,z,y)\\\\|$. Thus, if $(x,y)$ is an $\\epsilon$-GS point, then it is also an $\\mathcal{O}(\\epsilon^{\\min\\\\{1,1/2\\theta\\\\}})$-OS.\n\n**Q3: Odd constants in Theorem 1**\n\nWe kindly request the reviewer to confirm whether we misunderstand your question. From our side, the extrapolation step $\\beta$ should decrease to zero w.r.t. iteration $T$ when $\\theta\\in (\\frac{1}{2},1)$ (see Theorem 2). This implies that the sequence ${z_t}$ will undergo a decreasing rate of change, gradually approaching convergence. Conceptually, you can regard $z$ as an approximated proximal mapping of the max function $\\max_{y\\in\\mathcal{Y}} f(\\cdot,y)$. For further insights into parameter selection, please refer to the global response to Q2.\n\n**Q4: Unconstrained setting**\n\nFor the NC-C problem, the primal boundedness requirement can be removed and only the lower boundedness of the max function is enough, which allows the unbounded case and match those results in [1]. Otherwise, for the NC-NC case, the boundedness requirement is needed to ensure the lower boundedness of the Lyapunov function.  \n\n**Q5: Stochastic setting**\n\nYes, it can be done. There are no intrinsic difficulties. However, since the paper is already 32 pages, it may disperse the current focus of the paper if the proof of stochastic setting is included.\n\n**Q6: Minor issues**\n\nThanks for your advice. We will modify our title to \"Doubly Smoothed GDA for a class of Constrained Nonconvex-Nonconcave Minimax Optimization\". For the other suggestions on abbreviation and right parenthesis, we will revise it afterward.\n\n[3]. Pang J S. A posteriori error bounds for the linearly-constrained variational inequality problem.\n\n[4]. Li G, Pong T K. Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods."}, {"review_id": "aC7wadQYSE", "reviewer": "Reviewer_71Wf", "summary": "This paper addresses the nontrivial general minimax problem by proposing a novel algorithm called Doubly Smoothed Gradient Descent Ascent (DSGDA). The authors provide both experimental and theoretical evidence to support their claims.", "questions": "### Explainantion on Theorem 1\nCould authors make additional comments are conditions of theorem 1. \n\n", "limitations": "Authors discussed limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Overview I enjoyed reading this work. It's well written and organized, although some refernece and comparison is missing (see below). \n\n2. The proposed algorithm is not complicated and the intuition is sound. \n\n3.  Convergence results are sound. \n", "weaknesses": "\nWhile I acknowledge the soundness of the algorithm and the obtained results, I do have several concerns about this paper.\n\n### W1: \nThe theoretical convergence results demonstrating that the proposed method converges to a stationary point do not necessarily showcase its effectiveness in addressing the issue of **general** minimax problems. Although it is generally difficult for first-order methods to derive other convergence properties, such as local minimax points, for nonconvex-nonconcave problems, could the authors show the superiority of the algorithm under other settings?\n\n### W2: \nThe authors claim that their work demonstrates, for the first time, the possibility of having a simple and unified single-loop algorithm for solving nonconvex-nonconcave, nonconvex-concave, and convex-nonconcave minimax problems. However, to my knowledge, GDA-AM (ICLR 2022) also demonstrated such theoretical results (Thm C.4 and C.9) and showed convergent experiments. Additionally, the fast extragradient (NeurIPS 2021) made similar claims, as mentioned in Remark 1. Could the authors discuss the differences in contributions between their work and these existing papers?\n\n### W3: \nExperiments\nThe authors only compared their algorithm with SGDA. However, what about other methods? For example, how does it compare to fast extragradient or GDA-AM on these problems?\n\n1. He et.al. GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration, ICLR 2022\n2. Lee et.al. Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems, Neurips 2021\n\n\nExcept several concerns unaddressed, I tend to accept. I look forward to the authors' response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. We are happy that the reviewer enjoys our paper and would like to thank you for your insightful comments. Here are some illustrations based on your questions/suggestions. \n\n**Q1: Superiority of the algorithm under other settings.**\n\nWe kindly request the reviewer to confirm whether we misunderstand your question. We answer it in the following two possible directions. We'd be happy to clarify and answer your follow-up questions during the discussion period. \n* For general C-NC and NC-C problems, we have shown our algorithm can achieve both $\\epsilon$-game stationary (GS) and $\\epsilon$-optimization stationary (OS) points. They are the best points we can get in these settings and similar results can be obtained by SGDA. For C-C problems, we believe DSGDA can achieve Nash equilibrium point and we intend to explore it in future research.\n* For the superiority of DSGDA on C-NC and NC-C problems, our convergence rate matches the results of SGDA, which is the SOTA. For the superiority compared with SGDA, please refer to the global response to Q1.\n\n**Q2: Differences with GDA-AM (ICLR 2022) and fast extragradient (NeurIPS 2021).**\n\nThanks for pointing out two useful references. We believe our proposed DSGDA is fundamentally different from GDA-AM and fast extra-gradient. Here are detailed comparisons:\n\n**For GDA-AM:** GDA-AM only enjoys the global convergence guarantee for **unconstrained** C-C and C-NC problems. We have gone through the proof details, to the best of our knowledge, GDA-AM cannot handle the constrained case and its extension to the constrained scenario is highly non-trivial. Even under the unconstrained setting, the convergence of NC-NC problems is unsolved. As far as we know, no first-order method can converge for unconstrained NC-NC problems. We conduct a new experiment for the ``sixth-order polynomial'' example with initialization $(x,y)=(15,15)$, none of the first-order methods (SimGDA, AltGDA, OMD, EG, DSGDA, AltGDA-RAM, SimGDA-RAM) converge (refer to Figure (h) in **PDF**). For constrained NC-NC problems that we studied in the paper, the applicability of GDA-AM remains uncertain. In contrast, we have demonstrated that our algorithm effectively eliminates limit cycles in challenging constrained NC-NC scenarios, accompanied by theoretical guarantees for KL-NC and NC-KL settings.\n\n**For fast extra-gradient:** Firstly, it is only shown to converge under the negative comonotone condition, which is a stronger assumption than weak MVI. Such an assumption is restrictive and general C-NC/NC-C problems are easy to violate it. For example, the violations of this condition for C-NC problem $\\min_{x\\in \\mathcal{X}}\\max_{y\\in \\mathcal{Y}}f(x,y)=2x-y^2+4xy^6$ with $\\mathcal{X}=\\mathcal{Y}=\\\\{z:-1\\leq z\\leq 1\\\\}$ can be checked. Secondly, the convergence for C-NC/NC-C problem is unaddressed in this paper (i.e., NC-C/C-NC problems are not necessary to satisfy the negative comonotone condition), while DSGDA enjoys the global convergence with an iteration complexity of $\\mathcal{O}(\\epsilon^{-4})$. Finally, CurvatureEG+, an algorithm that converges under the weak MVI condition, is compared with DSGDA in Section 2. We can observe that CurvatureEG+ diverges or falls into a limit cycle for many examples. Given that weak MVI represents the weakest VI condition, we can reasonably anticipate similar outcomes for the fast extra-gradient method.\n\n**Q3: Experiments for GDA-AM and fast extragradient.**\n\nGDA-AM cannot directly apply to constrained problems and the fast extra gradient will have similar performance with CurvatureEG+. Please refer to the response to Q2 for details.\n\n**Q4: Explanation on Theorem 1: Could authors make additional comments are conditions of theorem 1.**\n\nPlease refer to the global response to Q2.\n\n**Missing reference**\n\nThanks for your advice. We would add the missing reference in the updated version.\n"}, {"review_id": "q3YhEryHyX", "reviewer": "Reviewer_KYPK", "summary": "The paper proposes the doubly smoothed gradient descent ascent method and studies its convergence under nonconvex-KL and nonconvex-concave minimax problems.", "questions": "Are there any differences between the convergence of Doubly Smoothed GDA and Smoothed GDA (Zhang et.al 2020) / Smoothed PLDA (Li et. al 2022) in theory? From the theoretical viewpoint, why is  Doubly Smoothed GDA better than Smoothed GDA? Can we show that the Doubly Smoothed GDA provably gets rid of limiting cycles?\n\nThe authors claimed that \"our work demonstrates, for the first time, the possibility of having a\nsimple and unified single-loop algorithm for solving nonconvex-nonconcave, nonconvex-concave,\nand convex-nonconcave minimax problems.\"  Can the authors explain that why the Smoothed GDA cannot have such a \"unified analysis\"?\nBy the way, I think it is better to use \"nonconvex-KL\" instead of \"nonconvex-nonconcave\" since the difficulties of these two problems seem to be very different from my point of view.\n", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper proposes a novel model to address the limiting cycle phenomena in nonconvex-nonconcave minimax optimization. The theoretal analysis match the best-known results for other methods.", "weaknesses": "The algorithm proposed in this paper comes naturally. From my experience, I can expect that DSGDA performs well in practice. My main concern is the theoretical guarantee of DSGDA. However, it seems that the results given by this paper do not show any superiority of DSGDA compared with other methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. We hope the clarification can clear your concerns and may reevaluate our contribution.\n\n**Q1: Superiority of DSGDA compared with other methods.**\n\nDSGDA can directly achieve both $\\epsilon$-GS and $\\epsilon$-OS points at the same rate.  Furthermore, its convergence rate stands out as the fastest among the current body of literature, aligning with the results of SGDA. For the superiority of DSGDA compared with SGDA, please refer to the global response to Q2.\n\n**Q2: Differences between the convergence of DSGDA and SGDA (Zhang et al. 2020)/Smoothed PLDA (Li et al. 2022) in theory. Why is DSGDA better than SGDA? Can we show that the DSGDA provably gets rid of limiting cycles?**\n\n- The introduction of double extrapolation in DSGDA fundamentally differentiates it from SGDA. Several key aspects highlight these differences. 1. The previously used Lyapunov function in SGDA is no longer applicable and a novel Lyapunov function tailored for DSGDA is constructed (see line 198). 2. To establish the sufficient decrease property of this newly proposed Lyapunov function, the derivation of a new proximal error bound is required (refer to Proposition 1). 3. Conceptually, due to the two extrapolation steps, extending the proof technique from SGDA to DSGDA presents significant challenges in primal-dual balancing. To be specific, our theoretical analysis, as shown in Theorem 1, two additional parameters, $r_2$ and $\\mu$, make it difficult to provide explicit bounds for all hyperparameters. In SGDA, since there is only one-sided extrapolation, the relationship between different parameters is rather simple. The step-sizes can be sufficiently small.  While in DSGDA, due to the double extrapolation, their relationship is complicated and the step-sizes will have non-trivial lower bounds. Although the algorithmic extension of DSGDA may seem intuitive and straightforward, we firmly believe that substantial effort and theoretical development are required to establish the global convergence of our proposed DSGDA method. The complexities introduced by double extrapolation demand rigorous investigation and are the focus of our research efforts.\n\n- From the theoretical viewpoint, DSGDA is the first simple and universal single-loop algorithm for solving NC-NC, NC-C, and C-NC minimax problems. SGDA does not have such \"unified analysis\". Please refer to the global response to Q1.\n\n- Yes, we believe DSGDA can be proven for getting rid of the limit cycles. Regarding the gap between the practical claim and the theoretical claim, please refer to the global response to Q3.\n\n**Q3: Can the authors explain why the SGDA cannot have such a \"unified analysis\"? It is better to use \"NC-KL\" instead of \"NC-NC\" since the difficulties of these two problems seem to be very different.**\n\n- For the SGDA proposed in [1] and [2], it can only solve concave (or NC-KL) problems. Further changes in algorithms are needed for solving KL-NC problems. Please refer to the global response to Q1 for details.\n\n- Intuitively, DSGDA is designed to address general NC-NC problems. Although our theoretical analysis currently focuses on cases that satisfy one-sided KL (or convex/concave) problems, we observe that DSGDA effectively escapes the limit cycle in numerous challenging NC-NC examples without any regularity condition (see Section 2). Moreover, our algorithm can also be applied to NC-C problems, which may not satisfy the KL property (see counterexamples in Corollary 4 of [3]). It may be better to use \"a class of Constrained Nonconvex-Nonconcave Minimax Optimization\" instead.\n\n[1]. Zhang J, Xiao P, Sun R, et al. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems.\n\n[2]. Li J, Zhu L, So A M C. Nonsmooth Composite Nonconvex-Concave Minimax Optimization.\n\n[3]. Bolte J, Pauwels E. Curiosities and counterexamples in smooth convex optimization.\n"}]

Author rebuttal:
We appreciate and thank the reviewers for their instructive comments. Below we provide our response to some common comments and questions. We believe that our responses will effectively address your major concerns, leading to a re-evaluation of our paper's contribution and quality.

**Q1: Is there any superiority compared with SGDA?**

Yes. One of the key advantages, the universality of DSGDA across NC-NC, NC-C, and C-NC problems, might have been overlooked by the reviewers. In practice, justifying the convexity/KL property of the primal or the concavity/KL property of the dual is a considerably challenging task. Our proposed DSGDA can be applied without knowing this prior information, owing to its inherent symmetry. However, prior to implementing SGDA, we have to choose which side we would like to employ the extrapolation. If we choose the wrong side, it will result in a slow convergence or even diverge. To validate this, we conduct a new experiment for a KL-NC problem $\min_{x\in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x,y)=2x^2 - y^2 + 4xy^6 + 4y^3/3-y^4/4$ with $\mathcal{X}=\mathcal{Y}=\\{z:-1\leq z\leq 1\\}$. With a wrong smoothing side, SGDA (with primal smoothing) leads to a slower convergence compared with dual smoothing, see Figure (g) in the **PDF**. We kindly request all reviewers to reevaluate the universal applicability of DSGDA. We will provide more details on this universality in our updated version.  

On the theoretical side, the convergence rate matches the results of SGDA under the same condition. On the practical side, DSGDA has better empirical performance than SGDA, which stands out as the only algorithm capable of overcoming the limit cycle phenomenon in all four challenging NC-NC examples (see Section 2). Moreover, DSGDA is more robust in parameter selection (see Section 5).

**Q2: Explanation on Theorem 1: Could authors make additional comments on conditions of theorem 1?**

Thank you for bringing up this matter. We would like to emphasize that we only offer a single set of workable upper and lower bounds for all hyperparameters. However, there are numerous alternative selections, which is essentially not a big deal. The principle behind selecting those hyperparameters is to ensure the sufficient decrease property of the novel Lyapunov function, see Theorem 1. In practice, as we have shown, the range of viable parameter values can be quite large.

**Q3: There remains a gap between theory and practice.**

Regarding the gap between the practical claim and the theoretical claim, it's important to emphasize that achieving a game stationary point through first-order oracles for smooth constrained separable NC-NC optimization problems (where constraint sets of primal and dual variables are independent) within polynomial time remains an open question over an extended period. Recently, the pioneering work by [1] has demonstrated that finding a game stationary point in smooth constrained **non-separable** NC-NC optimization problems is already a PPAD-complete problem. We believe our paper marks the initial stride towards bridging this gap and aims to encourage further engagement from researchers in tackling this issue.

[1] Daskalakis C, Skoulakis S, Zampetakis M. The complexity of constrained min-max optimization.




Meta-review: This paper proposes a doubly smoothed GDA for nonconvex-nonconcave minimax problem. It can escape the limit cycle of several well-known examples. Convergence to a stationary point and the iteration complexity under one-sided KL assumption are established. The results are important complement to the literature of minimax problem.
Decision: Accept (poster)