Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
Authors: Ziyi Chen
Yi Zhou
Tengyu Xu
Yingbin Liang
Venue: ICLR 2021 Poster (2021)
Keywords: Kurdyka-Łojasiewicz geometry
minimax
nonconvex
proximal gradient descent-ascent
variable convergence

Abstract: The gradient descent-ascent (GDA) algorithm has been widely applied to solve minimax optimization problems. In order to achieve convergent policy parameters for minimax optimization, it is important that GDA generates convergent variable sequences rather than convergent sequences of function value or gradient norm. However, the variable convergence of GDA has been proved only under convexity geometries, and it is lack of understanding in general nonconvex minimax optimization. This paper fills such a gap by studying the convergence of a more general proximal-GDA for regularized nonconvex-strongly-concave minimax optimization. Specifically, we show that proximal-GDA admits a novel Lyapunov function, which monotonically decreases in the minimax optimization process and drives the variable sequences to a critical point. By leveraging this Lyapunov function and the KL geometry that parameterizes the local geometries of general nonconvex functions, we formally establish the variable convergence of proximal-GDA to a certain critical point $x^*$, i.e., $x_t\to x^*, y_t\to y^*(x^*)$. Furthermore, over the full spectrum of the KL-parameterized geometry, we show that proximal-GDA achieves different types of convergence rates ranging from sublinear convergence up to finite-step convergence, depending on the geometry associated with the KL parameter. This is the first theoretical result on the variable convergence for nonconvex minimax optimization. 

Published as a conference paper at ICLR 2021
PROXIMAL GRADIENT DESCENT-ASCENT: VARIABLE CONVERGENCE UNDER KL GEOMETRY
Ziyi Chen, Yi Zhou
Tengyu Xu, Yingbin Liang Department of ECE The Ohio State University
Department of ECE University of Utah Salt Lake City, UT 84112, USA (u1276972, y1. y @utah. edu
Columbus, OH 43210, USA {xu. 3260, 1 liang. 889) @osu. edu
ABSTRACT
The gradient descent-ascent (GDA) algorithm has been widely applied to solve minimax optimization problems. In order to achieve convergent policy parameters for minimax optimization, it is important that GDA generates convergent variable sequences rather than convergent sequences of function values or gradient norms. However, the variable convergence of GDA has been proved only under convexity geometries, and there lacks understanding for general nonconvex minimax opti- mization. This paper fills such gap by studying the convergence of more general proximal-Gii GeDAAaa--GAAA.. for regularized nonconvex wwwpinew---toogyyooooo tion. Specifically, we show that proximal- -DAA admits a novel Lyapunov function, which monotonically decreases in the minimax optimization process and drives the variable sequence critical point. By leveraging this Lyapunov function and the Kt. geometry that parameterizes the local geometries of general nonconvex functions, we formally establish the variable convergence of proximal- critical point x², i.e., 2t - x² 3/t y" (x*). Furthermore, over the full spectrum of the KE--parameterized geometry, we show that proximal-GDA achieves different types of convergence rates ranging from sublinear convergence up finite-step convergence, depending on the geometry associated with the KE. parameter. This is the first theoretical result on the variable convergence for nonconvex minimax optimization.
minimax optimiza-
to a
INTRODUCTION
Minimax optimization is classical optimization framework that has been widely applied in various modern machine learning applications, including game theory Ferreira al. (2012), generative adversarial networks (GANs) Goodfellow et al. (2014), adversarial training Sinha et al. (001 7). reinforcement learning Qiu et al. (2020), imitation learning Ho and Ermon (2016); [Song et al. 2018
etc. A typical minimax optimization problem is shown below, where is differentiable function.
min max f(x, v)-
#eX yEy
A popular algorithm for solving the above minimax problem is gradient descent-ascent (GDA), which performs a gradient descent update on the variable æ and a gradient ascent update on the variable y alternatively in each iteration. Under the alternation between descent and ascent updates, it is much desired that GDA generates sequences of variables that converge to a certain optimal point, i..., the minimax players obtain convergent optimal policies. the existing literature, many studies have established the convergence of GDA-type algorithms under various global geometries of the objective function, e.g., convex-concave geometry (f convex in x and concave in y) Nedić and Ozdaglar (2009), bi-linear geometry Neumann (1928); Robinson (1951) and Polyak-L.ojssiewicz (PE. geometry Nouiched et al.) (2019): Yang et al. (2020). Some other work studied GDA under stronger global geometric conditions of such convex-strooggyy-omee
geometry Du and Hu (2019) and brongly-convex-steeee sttooglyyconncay geometry Mokhtari et al. (2020); Zhang and Wang (2020), under which GDA is shown to generate convergent variable sequences. However, these special global function geometries do not hold for modern machine learning problems that usually have complex models and nonconvex geometry.

---

Published as a conference paper at ICLR 2021
Recently, many studies characterized the convergence of GDA in nonconvex minimax optimization, where the objective function is nonconvex in x. Specifically, [in et al. (2020); Nouiched et al. (2019); Xu et al. ( Bot and Böhm (2020) studied the convergence of GDA in the nonconvex-conent setting Lin in et al. 2020); Xu et al. (020b) studied the seroovvee-strongly-concaa
setting. In these general nonconvex settings, it has been shown that GDA converges to certain stationary point at sublinear rate, i.e., [=+())]] < t-a for some > O, where ((z+) corresponds to certain notion of gradient. Although such a gradient convergence result implies the stability of the algorithm, namely, lime-+oo || Zz| = 0, it does not guarantee the convergence of the variable sequences {2r ht fye generated by GDA. So far, the variable convergence of GDA has not been established for nonconvex problems, but only under (strongly) convex function geometries that are mentioned previously Du and Hul (2019); Mokhtari et al. (2020); Zhang and Wang (222)). Therefore, we want to ask the following fundamental question:
QI: Does GDA have guaranteed variable convergence nonconvex minimax optimization? If so. where do they converge to?
In fact, proving the variable convergence of GDA in the nonconvex setting is highly nontrivial due to the following reasons: 1) the algorithm alternates between minimization step and a maximization step: 2) It is well understood that strong global function geometry leads to the convergence of GDA. However, in general nonconvex setting, the objective functions typically do not have amenable global geometry. Instead, they may satisfy different types of local geometries around the critical points. Hence, it is natural and much desired to exploit the local geometries of functions in analyzing the convergence of GDA. The Kurdyka--Lojaseeiizz (KL) geometry provides a broad characterization of such local geometries for nonconvex functions.
The Kurdykka-oojssewiicz (Kt) geometry (see Section 2 for details) Bolte et al. (007 2014
parameterizes broad spectrum of the local nonconvex geometries and has been shown to hold for broad class of practical functions. Moreover, it also generalizes other global geometries such as strong convexity and PL geometry. In the existing literature, the KL geometry has been exploited extensively to analyze the convergence rate of various gradient-bee -ased algorithms in nonconvex optimization, e.g.. gradient descent /Attouch and Bolte (2009) Li et al. (2017) and its accelerated version Zhhou et al.) (2020) as well the distributed version Zhou et al. (201 Hence, we are highly motivated to study the convergence rate variable convergence of GDA in nonconvex minimax optimization under the KL geometry. In particular, we want to address the following question:
Q2: How does the local function geometry captured by the KL parameter affects the variable convergence rate of GDA?
In this paper, we provide comprehensive answers to these questions. We develop a new analysis framework to study the variable convergence of GDA in nonconvex-strongly -tonesssooollyycoccveeeeee minimax optimization under the Kt geometry. We also characterize the convergence rates of GDA in the full spectrum of the parameterization of the KL geometry.
1.1 OUR CONTRIBUTIONS
We consider the following regularized noncomvex--tronlly-coocaee minimax optimization problem min max f(z + +(xx) - h(y), #ER" yEy
(P)
where of a differentiable and sonconvex-ttrongly-comeee regularizer and h is a convex regularizer. Both and h can be possibly nonsmooth. To solve the above regularized minimax problem, we study a proximal-GDA algorithm that leverages the forvard-backward splitting update Lions and Mercier (179);; Attouch et al. (2013).
function, g is general nonconvex
We study the variable convergence property of proXimal-GDA in solving the minimax problem (P). Specifically, show that proximal-GDA admits novel Lyapunov function H H(, y) (see Proposition 2}. which is monotonically decreasing along the trajectory of proximal GDA, i.c., H H( )++1) < H vt). Based the monotonicity of this Lyapunov function, we show that every limit point of the variable sequences generated by proximal-GDa is a critical point of the objective function.
Moreover, by exploiting the ubiquitous KL geometry of the Lyapunov function, we prove that the entire variable sequence of proximal-GDA has unique limit point, equivalently speaking, it
2

---

Published as a conference paper at ICLR 2021
converges to certain critical point x=", i.e., zt + x² Ut - -y="(""* (x*) (see the definition of y" in Section 2). To the best of our knowledge, this is the first variable convergence result of GDA-type algorithms nonconvex minimax optimization.
Furthermore, we characterize the asymptotic convergence rates of both the variable sequences and the function values of proximal- -DDA in different parameterization regimes of the Kt. geometry. Depending on the value of the Kt. parameter 8, we show that proximal-GDA achieves different types of convergence rates ranging from sublinear convergence up finite-step convergence, we summarize in Table below.
Table I: Convergence rates of proximal-GDA under different parameterizations of Kt. geometry.
Note that to denotes a sufficiently large positive integer.
KL parameter
Function value convergence rate
Variable convergence rate
Finite-step convergence
Finite-step convergence
( - [2(1 ))))
O ((exp [2(1 ())==))) Super-lineat convergence
0 E 12
Super-linest convergence
((11 -) Linear convergence
O( (2, 1 + p}) (lo (k000/2)
0 ==
Linear convergence
(11- - (o) --)-)
O - 4)) Sub-linear convergence
0 (0,
Sub-linear convergence
1.2 RELATED WORK
Deterministic GDA algorithms: Yang (2020) studied an alternating gradient descent-ascent (AGDA) algorithm in which the gradient ascent step uses the current variable 2141 instead of zt.
Bot and Böhm (2020) extended the AGDA algorithm to an alternating proximal-GDA (APGDA) algorithm for regularized minimax optimization. Xu et al. (2020b) studied an alternating gradient projection algorithm which applies f2 regularizer to the local objective function of GDA followed by projection onto the constraint sets. Daskalakis and Panageas (2018); Mokhtari et al. (2020);
Zhang and Wang (020)) analyzed optimistic gradient descent-ascent (OGDA) which applies negative momentum to accelerate GDA. Mokhtari et al. (2020) also studied extra-gradient algorithm which applies two-step GDA in each iteration. Nouiehed et al. (2019) studied multi-step GDA where multiple gradient ascent steps are performed, and they also studied the nomentum-acceleree version. Cherukuri et al. (2017); Daskalakis and Panageas (2018); 10: Jin et al. (2020) studied GDA in continuous time dynamics using differential equations. Adolphs et al. (019) analyzed second-order variant of the GDA algorithm.
Stochastic GDA algorithms: Lin al. (2020); Yang et 2020 Bot and Böhm (2200) analyzed stochastic GDA, stochastic AGDA and stochastic APGDA, which are direct extensions of GDA, AGDA and APGDA to the stochastic setting respectively. Variance reduction techniques have been applied to stochastic minimax optimization, including SVRG-based Du and Hu 2019); Yang et al. (2020). PIIER--base Xu et (2020a), STORM Qiu al. (2020) and gradient free version Huang et al. (020). Xie et al. (2020) studied the complexity lower bound of first-order stochastic algorithms for finite-sum minimax problem.
KE geometry: The Kt. geometry was defined in Bolte et al. (2007). The Kł. geometry has been exploited to study the convergence various first-order algorithms for solving minimization problems, including gradient descent Attouch and Bolte (2009), alternating gradient descent Bolte et al. (2014) distributed gradient descent Zhou et al. (2016a (0188),, accelerated gradient descent Li et al. (0017) It has also been exploited to study the convergence of second-order algorithms such Newton's method Noll and Rondepierre (2013); Frankel et al. (2015) and cubic regularization method Zhou
al. 2018b).
3

---

Published as a conference paper at ICLR 2021
2 PROBLEM FORMULATION AND KE GEOMETRY
In this section, we introduce the problem formulation, technical assumptions and the Kurdyka- Lojasiewicz (KL) geometry. We consider the following regularized minimax optimization problem.
min max f(z, v) + g(x) - h(y),
EERm yEy
where f 1.Th x R + R is a differentiable and nonconvex wwwpaweee--toooy-ooooee concavv loss function, y C R a compact and convex set, and g, h are the regularizers that are possibly non-smooth. In particular, define ((x) == maxyey fxx y) - h(y), and then the problem (P) is equivalent to the minimization problem mingeR ((x) ((z).
Throughout the paper, we adopt the following standard assumptions on the problem (P).
Assumption 1. The objective function of the problem (P) satisfies:
1. Function [(,: .) is L-smooth and function f(x,,) -) is j--strongyy concave;
2. Function ( (x)) is bounded below, i.e., inf (T + +z)(z) > -oc;
For any a E R. the sub-level set {x ( + (z) I a is compact:
4. Function h is proper and convex, and function g proper and lower semi-continuous.
To elaborate, item 1 considers the class of nonconvex
nonconvex-stroogly -tronstl--ooccaanee functions f tthat has been widely studied in the existing literature Lin et al. (2020); Jin al. (2020); y [u et al. (2020b a): Lu ctt al. (202)). Items and guarantee that the minimax problem (P) has at least one solution, and the variable sequences generated by the proximal- Item 4 requires the regularizer h to be convex (possibly non-smooth), which includes many norm- based popular regularizers such as lp (p 2 1), elastic net, nuclear norm, spectral norm, etc. On the other hand, the other regularizer can be nonconvex but lower semi-continuous, which includes all the aforementioned convex regularizers, l, (0 S p 1), Schatten-p norm, rank, etc. Hence, our formulation of the problem (P) covers rich class of nonconvex objective functions and regularizers and is more general than the existing nonconvex minimax formulation in Lin et al. (2020), which does not consider any regularizer.
algorithm (See Algorithm I are bounded.
Remark 1. We note that the strong concavity of f (z. in item can be relaxed to concavity, provided that the regularizer h(y) is p-strongly convex. In this case, we can add - llvl? 2 to both f(z, v) and hyy) such that Assumption still holds. For simplicity, we will omit the discussion on this case.
By strong concavity of [(x, .) it is clear that the mapping y (x) = arg max (x. y) h(y) uniquely defined for every z R In particular, if x= is the desired minimizer of ((z). then (a", y" (x")) is the desired solution of the minimax problem (P).
Next, we present some important properties regarding the function (xz) and the mapping y (z). The following proposition from Boj and Böhm (2020) generalizes the Lemma 4.3 of et al. (2020) to the regularized setting. The proof can be found in Appendix A Throughout, we denote k L/j fz as the condition number and denote fx, v), 2 y) as the gradients with respect to the first and the second input argument, respectively. For example, with this notation, ViJ(z, y² (x)) denotes the gradient of f(x y (xx) with respect to only the first input argument x, and the in the second input argument y" (x) is treated as a constant.
Proposition 1 (Lipschitz continuity of y" (x) and Vz(())) Let Assumption C Toold. Then, the mapping y (z) and the function (xx) satisfy
1. Mapping y" (x) is k-Lipschitz continuous; Function (x) is L(1 + -mmoth with V = Vzf(z,
As an intuitive explanation of Proposition since the function f(x v) 11(y) is L-smooth with respect x, both the maximizer y" (xx) and the corresponding maximum function value (xx) should not change substantially with regard to a small change of æ.
Recall that the minimax problem (P) equivalent to the standard minimization problem minZERR ((z) + 9(x), which, according to item 2 of Proposition]] [ includes smooth nonconvex function (x) and a lower semi-continuous regularizer g(z). Hence, we can define the optimiza- tion goal of the minimax problem (P) as finding critical point x² of the nonconvex function @ (z) + g(x) that satisfies the necessary optimality condition 0 E a( + g)(x)) for minimizing nonconvex functions. Here, & denotes the notion of subdifferential
elaborate below.
4

---

Published as a conference paper at ICLR 2021
Definition 1. (Subdiffrrenial and critical point, Rockafellar and Wers 2009 ential oh of function h at dom h is the set of u E Rdd defined as
The Frechét subdiffer-
Ōh(z) = {u: lim inf 27/0,3-2
h(2)= h(x) - u (z x2) 20].
and the limiting subdifferential 0h at x E dom h is the graphical closure of Oh defined as:
ah(x) == {u: loz - I, h(xa)) + h(x),, un E @ō((kx), un + u].
The set of critical points of h defined as crith == (a: Oh(x)).
Throughout, refer to the limiting subdifferential subdifferential. We note that subdifferential a generalization of gradient (when h is differentiable) and subgradient (when h is convex) to the nonconvex setting. In particular, any local minimizer of h must be critical point.
Next, we introduce the point-to-set distance denoted as (isto(x)) = infuug -
(KL) geometry of a function h. Throughout, the
Definition 2 (Kt. geometry, [oolte et al. (2014). A proper and lower semi-continuoss function h is said to have the KL geometry if for every compact set Q C domh on which takes a constant value lig E IR, there exist x > such that for all æ E Ω and all E {= E IR dista(z) < 6, ha < h(2)- < ha + N}. the following condition holds:
4 (h(x)) ha) diston(z) (0) 1,
where xp' is the derivative of function up: [0, A) - R4, which takes the form sp(() = 11 for certain universal constant 0 and KL parameter E (0,
The KE geometry characterizes the local geometry of a nonconvex function around the set of critical points. To explain, consider the case where is a differentiable function that 0h(x:) Vh(x))
Then, the Kt. inequality in eq. (1) becomes h (x) - ha < (( - which generalizes the Polvak-E.ojasiewwicz (PI.) condition /xx))= ha ((IVV Lojasiewicz (963) Karimi et al. (016)) (i.e., KE parameter 0 }). Morcover, the KE geometry has been shown to hold for large class of functions including sub-analytic functions, logarithm and exponential functions and semi-algebraic functions. These function classes cover most of the nonconvex objective functions encountered in practical machine learning applications Zhou Zhou al. (2016b); Yue al. (2018): Zhou and Liang 2017); Zhou et al. (2018b).
The Kt. geometry has been exploited extensively to analyze the convergence of various first-order algorithms, e.g., gradient descent Attouch and Bolte (2009): Li et al. (2017), alternating minimization Bolte et al. (2014) and distributed gradient methods Zhou et al. (2016g 6a). It has also been exploited to study the convergence of second-orde -oddrr algorithms such cubic regularization Zhou et al. (2018b). In these works, it has been shown that the variable sequences generated by these algorithms converge to desired critical point in nonconvex optimization, and the convergence rates critically depend on the parameterization 8 of the KL geometry. In the subsequent sections, we provide a comprehensive understanding of the convergence and convergence rate of proximal-GDA under the KE geometry.
PROXIMAL-GDA AND GLOBAL CONVERGENCE ANALYSIS
In this section, study the following proximal-GDi algorithm that leverages the forward-backwer splitting updates| Lions and Mercier 1979): Attouch et al. (2013) to solve the regularized minimax problem (P) and analyze its global convergence properties. In particular, the proximal-GDA algorithm is a generalization of the GDA Du and Hu (2019) and projected GDA Nedić and Ozdaglar (2009)
algorithms. The algorithm update rule specified in Algorithm [ steps are formally defined as
where the two proximal gradient
prox (st The V Wil( W:)) argmin {g(u) "ERm
1 I|u It + The V Vil(aar V
(2)
2np
prox,, (ve + no V2l (z), v:))
argmin KEY
h(v)) + 27y
||u Vt - ml V2. V2l (2 v1)) (3)
5

---

Published as a conference paper at ICLR 2021
Algorithm 1 Proximal-GDA
Input: Initialization Fo, yo. learning rates m/ fly for t = 0,1, . - do
3++1 E prox Dag (It - 7/ V (Te, Wt)),
Ve+1 = prox, (ve + my V2f(21
end
Output: 2T, V/r
Recall that our goal is to obtain critical point of the minimization problem min (xx) + g(x). Unlike the gradient descent algorithm which generates a sequence of monotonically decreasing function values, the function value (Φ + (xxx) along the variable sequence generated by proximal- GDA is generally oscillating due to the alternation between the gradient descent and gradient ascent steps. Hence, it seems that proXimal-GDA is less stable than gradient descent. However, our next result shows that, for the problem (P), the proximal-GDA admits a special Lyapunov function that monotonically decreases in the optimization process. The proof of Proposition in Appendix B
Proposition 2. Let Assumption 4 Thold and define the Lyapunov function H ((x)) g(a))
(1 T, -llylyly" -y" (1) with z == (0, y)- Choose the learning rates such that Th S x3( fl S Z
Then, the variables 21 (It, v1) generated by proximal-GDD GDD satisfy, for all 0, 1,,,
1 4x
H(2+1) S (z,) 21|2241 - xell?
(1186+1 - y v"(++11)11 - (x))).))
-
(4)
We first explain how this Lyapunov function is introduced in the proof. By eq. 19 in the supplemen- tary material, we established a recursive inequality on the objective function ( + (2(+1)) One can see that the right hand side of eq. (19) contains negative term - -||x 2z 1l? and an undesired positive term Ily" (a+t) yel Hence, the objective function ($ + (dx-1) may be oscillating and cannot serve as proper I Lyapuovv function. In the subsequent analysis, we break this positive term into a difference of two terms I1y (zt)- y/ 1|2 11 (Z++1) - W 1| by leveraging the update of yt+1 for solving the strongly concave maximization problem. After proper rearranging, this difference term contributes to the quadratic term in the Lyapunov function.
We note that the Lyapunov function (=) is the objective function (xx) + g(x) regularized by the 1
additional quadratic term (1 - 4.z Ily - y (z)]l?, and such a Lyapunov function clearly characterizes optimization goal. To elaborate, consider desired case where the sequence 2, converges to a certain critical point xx and the sequence Y/t converges to the corresponding point y (xx)). In this case, it can be seen that the Lyapunov function H (2+) converges the desired function value (.)))) Hence, solving the minimax problem (P) is equivalent to minimizing the Lyapunov function. More importantly, Proposition 2 shows that the Lyapunov function value sequence { (2+)) is monotonically decreasing in the optimization process of proximal-GDD GDA, implying that the algorithm continuously makes optimization progress. We also note that the coefficient (1 ax² in the Lyapunov function is chosen in a way so that eq. (4) can be proven to be strictly decreasing. This monotonic property is the core of our analysis of prDX
Based on Proposition 2 we obtain the following asymptotic properties of the variable sequences generated by proximal GDAA The proof can be found in Appendix
Corollary 1. Based on Proposition
the sequences {2t, ye generated by proximal-GDA satisfy 2
lim |111| 2x O, lim || 3/ O, lim 11ye y² (xx))l = 0.
The above result shows that the variable sequences generated by proximal-GIAA in solving the problem (P) are asymptotically stable. In particular, the last two equations show that yı asymptotically approaches the corresponding maximizer y" (zx) of the objective function f(r,, v) + g(xx) h(y). Hence, if z3 converges to certain critical point, y/ will converge to the corresponding maximizer.
Discussion: We note that the monotonicity property in Proposition 2 further implies the convergence xx < (1-1/22 (by telescoping over f). When there is no regularizer,
rate result minngkge [

---

Published as a conference paper at ICLR 2021
this convergence rate result can be shown to further imply that minoskse [ 2 1(t-1/2) which reduces to the Theorem 4.4 of [in et al. (2020). However, such a convergence rate result does not imply the convergence of the variable sequences {ar)e, {yr To explain, we can apply the convergence rate result || 2; S O(t-1/3) to bound the trajectory norm as |ær|| S || + Σi= || - xel R VT, which diverges to +00 as - oo. Therefore, such type of convergence rate does not even imply the boundedness of the trajectory. In this paper, our focus is to establish the convergence of the variable sequences generated by proximal-GIDA.
All the results in Corollary imply that the alternating proximal gradient descent & ascent updates of proximal-GDA can achieve stationary points, which we show below to be critical points.
Theorem 1 (Global convergence). Let Assumption 7 hold and choose the learning rates Te S
(14337 Fl S t. Then, proximal-GDA satisfies the following properties.
1. The finction value sequence {( + (2x)) converges to a finite limit > -0;;
2. The sequences {21}s, {yr]s are bounded and have compact sets limit points. Moreover, ($
(x²) = H² for any limit point x² of {
3. Every limit point of {21he a critical point of ( + (z).
The proof of Theorem D is presented in Appendix D The above theorem establishes the global convergence property of proximal-GDA. Specifically, item I shows that the function value sequence {(o + g) (x+)]: } converges to a finite limit H' which is also the limit of the Lyapunov function sequence {2))) Moreover, items 2 & 3 further show that all the converging subsequences of } converge to critical points of the problem, at which the function & + g achieves the constant value H These results show that proximal-GDA can properly find critical points of the minimax problem (P). Furthermore, based on these results, the variable sequences generated by proximal-GDA geometry holds,
are guaranteed to enter local parameter region where the which we exploit in the next section to establish stronger convergence results of the algorithm.
4 VARIABLE CONVERGENCE OF PROXIMAL-GDA UNDER KE GEOMETRY
We note that Theorem only shows that every limit point of {at) he is a critical point, and the sequences {xt, )e may not necessarily be convergent. In this section, we exploit the local Kt. geometry of the I Lyapunov function to formally prove the convergence of these sequences. Throughout this section, we adopt the following assumption.
Assumption 2. Regarding the mapping y" (1:), the function (1y) - y/l² has a non-empty subdiffer- ential, ie., dz (Ilvs" (x) 2)l²) + 0.
Note that in many practical scenarios "² (xx) is sub-differentiable. In addition, Assumption
2 ensures
the sub-differee differentiaaiilit of the Lyapunov function H (2) := + g(x) + (1 1 11))ly y" (x) P.
We obtain the following variable convergence result of proximal-GDA under the KE geometry. The proof is presented in Appendix F
Theorem 2 (Variable convergence). Let Assumption 1 & 2 hold and assume that H has the K& ge- ometry. Choose the learning rates 7) S m[L+3yz and Thy S +. Then, the sequence {(Ie, We be generated by proximal-GID -DDA converges to certain critical point (x","" (x*)) of (ΦD + +z))), ie..
St 4 x²
M/. 4 y (xx).
Theorem 2 formally shows that proximal-GDA is guaranteed to converge to certain critical point (x*, yy (a*) the minimax problem (P), provided that the Lyapunov function belongs to the large class of KE functions. To the best of our knowledge, this is the first variable convergence result of GDA-type algorithms in nonconvex minimax optimization. The proof logic of Theorem 2 can be summarized as the following two key steps.
Step 1: By leveraging the monotonicity property of the Lyapunov function in Proposition 2 we first show that the variable sequences of proximal-GDA eventually enter local region where the KL geometry holds;
Step 2: Then, combining the KL inequality in eq. [ and the monotonicity property of the Lyapunov function in eq. 4 we show that the variable sequences of proximal mrxiimal-GDA are Cauchy sequences and hence converge certain critical point.
7

---

Published as a conference paper at ICLR 2021
5 CONVERGENCE RATE OF PROXIMAL-GDA UNDER KL GEOMETRY
In this section, we exploit the parameterization of the Kt. geometry to establish various types of asymptotic convergence rates of proximal-GDA.
We obtain the following asymptotic convergence rates of proximal-GiD under different parameter regimes of the Kt. geometry. The proof is presented in Appendix F In the sequel, we denote lo as sufficiently large positive integer, denote e > 0 as the constant in Definition 2 and also define
C 1/
M = max
(x.+4x2)11
4x (T + (I+ 4m))
(5)
Theorem (Funtion value convergence rate). Under the same conditions as those of Theorem
2 the
Lyapunov function value sequence {H(z)) converges to the limit H at the following rates.
1. If KL geometry holds with 0 1, then (=)) 4 H within finite number of iterations:
2. If KE geometry holds with 0 E ($) 1), then (2x) & HH super-lineariy as
H(z)) H" S (2 wo.1 exp ( (-(2 2(1 0)
v4 to:
(6)
3. If KL geometry holds with 0 1/2 then H(z)) H linearly
H(z)) H' - (1 1 to-t (H(2))) - H*), At 2 to:
(7)
2Mc²)
4. If KL geometry holds with 0 E (0, }) then H (2t) & H² sub-linearly as
(22) H - CC(t to) - AA 2 to.
(8)
where C = min
1-20 (1 (1-20) 2- > O. 8Me di
can be seen from the above theorem that the convergence rate of the Lyapunov function of proximal-GDA is determined by the KE parameter 6. A larger implies that the local geometry of is 'sharper', and hence the corresponding convergence rate is orderwise faster. In particular, the algorithm converges at linear rate when the Kt. geometry holds with 0 2 (see the item 3), which is a generalization of the Siyyak-Lojssiwiizz (PL) geometry. As a comparison, in the existing analysis of GDA, such a linear convergence result is established under stronger geometries, e.g., convex-strongly wtoee-sttoooyyycoccveeeeee concave Du and Hu (009)), waanglyccovve--srronn coorooe Mokhtari et al. (2020); ZZang and Wang (2020) and two-sided PL condition Yang et al. (2020). In summary, the above theorem provides a full characterization of the fast convergence rates of proximal-Gii in the
full spectrum of the Kt geometry.
Moreover, we also obtain the following asymptotic convergence rates of the variable sequences that generated by proximal-GDA under different parameterization of the Kt. geometry. The proof is presented in Appendix G
Theorem (Variable convergence rate). Under the same conditions as those of Theorem the
sequences {at, ht converge to their limits x" yy" (²(x") respectively at the following rates.
1. If KL. geometry holds with 0 then (rt, Mc) - (x*, """ (x*)) within finite number of itera- tions;
If KL geometry holds with (t) 1), then (It, W:) + (x", "o" "''"""""""" (x*)) super-linearly as
max {1|=, x'1l 11. ll 4" (x") 00 ( 1
2(1 1
)
Vt 2 to:
(9)
3. If KL geometry holds with o = }. then (Ie, - (x", "0',""""))) linearly as
max {1 - 2²11. I1.111 l1,. y" [1) < =0(( min {2, +
2Mc })
1
(1o 1)/2))/2
Vt 2 to: (10)
4. If KL geometry holds with 0 E (0, }) then (It, y/) + (x*, "."""" (x*)) sub-linearly as
max {1lxr - x x11,, I1, 1y: - 3 (x*)1I} < o (0) -
11 2 4o
(11)
8

---

Published as a conference paper at ICLR 2021
To the best of our knowledge, this is the first characterization of the variable convergence rates of proximal-GDA the full spectrum of the Kł geometry. can be seen that, similar to the convergence rate results of the function value sequence, the convergence rate of the variable sequences is also affected by the parameterization of the Kt. geometry.
CONCLUSION
In this paper, we develop a new analysis framework for the proximal-GDA algorithm in nonconvex- cronngly-ooncave optimization. Our key observation is that proximal-GDA has intrinsic Lyapunov function that monotonically decreases in the minimax optimization process. Such a property demon- strates the stability of the algorithm. Moreover, we establish the formal variable convergence of proximal-GDA to a critical point of the objective function under the ubiquitous KL geometry. Our results fully characterize the impact of the parameterization of the KL geometry on the convergence rate of the algorithm. In the future study, we will leverage such an analysis framework to explore the convergence of stochastic GDA algorithms and their variance-reduced variants.
ACKNOWLEDGEMENT
The work of T. Xu and Liang was supported partially by the U.S. National Science Foundation under the grants CCF-1900145 and CCF-1909291.
REFERENCES
Adolphs, L., Daneshmand, H., Lucchi, A., and Hofmann, T. (2019). Local saddle point optimization: curvature exploitation approach. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 486-495
Attouch, H. and Bolte, J. (2009). On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1-2):5-16.
Attouch, H., Bolte, J., and Svaiter, B. F. (2013). Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, nawardd-bckwaad splitting, and regularized gauss-seidel methods. Mathematical Programming, 137(1-2):91-129,
Bernhard, P. and Rapaport, A. (1995). On theorem of danskin with application to theorem of von neumann-sion. Nonlinear Analysis: Theory, Methods & Applications, 2468):1133-1181.
Bolte, J., Danilidis, A., and Lewis, A. (2007). The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17:1205-1223.
Bolte, J., Sabach, S., and Teboulle, M. (2014). Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1-2):459-499
Bot, R. I. and Böhm, A. (2020). Alternating proximal-gradient steps for (stochastic) nonconvex- concave minimax problems. 1xXi:22007.3665.
Cherukuri, A., Gharesifard, B., and Cortes, J. (2017). Saddle-point dynamics: conditions for
asymptotic stability of saddle points. SIAM Journal on Control and Optimization, 5561)188--511
Daskalakis, C. and Panageas, (2018). The limit points of (optimistic) gradient descent in min-max optimization. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 9236-9246.
Du, S. and Hu, W. (2019). Linear convergence of the primal-dual gradient method for convex- concave saddle point problems without strong convexity. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 196-205.
Ferreira, M. A. M., Andrade, M., Matos, M. C. P., Filipe, A., and Coelho, M. P. (2012). Minimax theorem and nash equilibrium.

---

Published as a conference paper at ICLR 2021
Frankel. P., Garrigos, G., and Peypouquet, J. (2015). Splitting methods with variable metric for Kurdyka Kurdyka-Lojasiewinn Lojasiewicz functions and general convergence rates. Journal of Optimization Theory and Applications, 165(3):874-900
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014). Generative adversarial nets. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 2672-2680.
Ho, J. and Ermon, S. (2016). Generative adversarial imitation learning. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 4565-4573
Huang, F,, Gao, S., Pei, J., and Huang, H. (2020). Accelerated zeroth- order momentum methods from mini to minimax optimization. ArXiv:2008.08/1
Jin, C., Netrapalli, P., and Jordan, M. I. (2020). What is local optimality in nonconvex- www.ovvve---oncccveee minimax optimization?
Karimi, H., Nutini, J., and Schmidt, M. (2016). Linear Convergence of Gradient and Proximal- Gradient Methods Under the Polyak-Lojasiewicz Condition, pages 795-811.
Kruger, A. Y. (2003). On fréchet subdifferentials. Journal of Mathematical Sciences, 116(3):3325- 3358.
Li, Q.. Zhou, Y., Liang, Y., and Varshney, P. K. (2017). Convergence analysis of proximal gradient with momentum for nonconvex optimization. In Proc. International Conference Machine Learning (ICML), volume 70, pages 2111-2119.
Lin, T., Jin, C., and Jordan, M. I. (2020). On gradient descent ascent for nonconvex-concave minimax problems.
Lions, P.-L. and Mercier, B. (1979). Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):964-979.
Eojasiewicz, S. (1963). A topological property of real analytic subsets. Coll. du CNRS, Les equations aux derivees partielles, page 87-89.
Lu, S., Tsaknakis, I., Hong, M., and Chen, Y. (2020). Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing.
Mokhtari, A., Ozdaglar, A., and Pattathil, S. (2020). A unified analysis extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In Proc. International Conference on Artificial Intelligence and Statisties (AISTATS), pages 1497-1507.
Nedić, A. and Ozdaglar, A. (2009). Subgradient methods for saddle-poing problems. Journal of optimization theory and applications, 142(1):205-228.
Neumann, J. (1928). Zur theorie der gesellschaftsspeeee. Mathematische annalen, 100(1):295-320.
Noll, D. and Rondepierre, A. (2013). Convergence of linesearch and trust-region methods using the Sondyya--ojasiewicc inequality. In Proc. Computational and Analytical Mathematics, pages 593-611.
Nouiehed, M., Sanjabi, M., Huang, T., Lee, D., and Razaviyayn, M. (2019). Solving a class of non-convex min-max games using iterative first order methods. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 14934-14942.
Qiu, S., Yang, Z., Wei, X., Ye, J., and Wang, Z. (2020). Single-timescale stochastic nonconvex- concave optimization for smooth nonlinear td learning. ArXiv:2008.101
Robinson, J. (1951). An iterative method of solving a game. Annals of mathematics, 54(2):296-301.
Rockafellar, R. T. (1970). Convex analysis. Number 28. Princeton university press.
10

---

Published as a conference paper at ICLR 2021
Rockafellar, R. T. and Wets, R. J.-B. (2009). Variational analysis, volume 317. Springer Science & Business Media.
Sinha, A., Namkoong, H., and Duchi, J. C. (2017). Certifying some distributional robustness with principled adversarial training. In Proc. International Conference on Learning Representations (ICLR).
Song, J., Ren, H., Sadigh, D., and Ermon, S. (2018). Multi-agent generative adversarial imitation learning. In Proc. Advances Neural Information Processing Systems (NeurIPS), pages 7461- 7472.
Xie, G., Luo, L., Lian, Y., and Zhang, Z. (2020). Lower complexity bounds for finite-sum convex- concave minimax optimization problems.
Xu, T., Wang. Z., Liang, Y., and Poor, H. V. (2020a). Enhanced first and zeroth order variance reduced algorithms for min-mat max optimization. ArXiv:2006.099::
Xu, Z., Zhang. H., Xu, Y., and Lan, G. (2020b). unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. (xXiv:2006.02033 02032.
Yang, J., Kiyavash, N., and He, N. (2020). Global convergence and variance reduction for class of nonconvex nonconcave minimax problems.
Yue, M., Zhou, Z., and So, M. (2018). On the Quadratic Convergence of the Cubic Regularization Method under Local Error Bound Condition. ArXiv: 181.08810......71.
Zhang, and Wang, Y. (2020). On the suboptimality of negative momentum for minimax optimiza- tion. ArXiv:2008.07455
Zhou, Y. and Liang, Y. (2017). Characterization of Gradient Dominance and Regularity Conditions for Neural Networks. ArXiv:1710.069100
Zhou, Y., Liang, Y., Yu, Y., Dai, W., and Xing, E. P. (2018)).. Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters. Journal of Machine Learning Research (JMLR), 19:1
Zhou, Y., Wang, Z., Ji, K., Liang, Y., and Tarokh, V. (2020). Proximal gradient algorithm with momentum and flexible parameter restart for nonconvex optimization. In Pruc. International Joint Conference Artificial Intelligence, ISCAI-20, pages 1445-1451.
Zhou, Y., Wang, Z., and Liang, Y. (2018b). Convergence of cubic regularization for nonconvex optimization under kl property. In Proc. Advances Neural Information Processing Systems (NeurIPS), pages 77693769.
Zhou, Y., Yu, Y., Dai, W., Liang, Y., and Xing, (2016a). On convergence of model parallel proximal gradient algorithm for stale synchronous parallel system. In Proc. International Conference on Artificial Intelligence and Statisties (AISTATS, volume 51, pages 713-722.
Zhou, Y., Zhang. H., and Liang, Y. (2016b). Geometrical properties and accelerated gradient solvers of non-convex phase retrieval. In Proc. 54th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 331-335.

---

Published as a conference paper at ICLR 2021
SUPPLEMENTARY MATERIAL
A PROOF OF PROPOSITION
Proposition 1 (Lipschitz iy of y" (x) and (T())), Let Assumption hoold. Then, the mapping y (a) and the function ((x) satisfy
1. Mapping y" (x) is k-Lipschitz continuous;
Function (x) is L(1 + k) with ( Vis(a,
Proof. We first prove item 1. Since f(z; y) is strongly concave in y for every x and h(y) is convex, the mapping y (Ø) = arg y f(x,)) y) - hly) is uniquely defined. We first show that y (xx is a
Lipschitz mapping. Consider two arbitrary points 2 22. The optimality conditions of y (xx and y" (22) imply that
(v - 1--y (x1). V2l(21,
u1) 2 0,
Vy E V.u u1 E (x1l)
(12)
(y (y- y² (22). V2f ( (x2) u2) I 0,
Vy E V.uz u2 E (0h()((22)
(13)
Setting = y² (x2) in eq. 12 = (x1) in eq. 13 and summing up the two inequalities, we obtain that
w (22) - v (21). V2f(=1, (21)) 2 y (x2)) u1 + u2) < 0.
(14)
Since 0h is a monotone operator (by convexity), we know that (u2 u1,y y² (z1)) 2 0. Hence, the above inequality further implies that
(y" (x2) y² (x1), V2f 22, (x1)) V2f(22, ( (x2))) 0.
(15)
Next, by strong concavity of f(z1, -), we have that (y' (xz2) v² (z1), V2](z1, v/ (22)) V2s(21, "eri,,"(aaa (xi))) + (x1) v' (x2))1 so. (16)
Adding up the above two inequalities yields that
ully" (x1) - (x2))1 < (y" (x2) - (x1), V2f (x2)) V $ Ily" (x2) - 5² (<1) V2/ (x2)) V2f( y (x2))
s Lly" - y" (x1) x1ll-
The above inequality shows that 11 (x1) - (x2)) S <=||== - 2 ||. and item I is proved.
Next, we will prove item 2. Consider A, (x(())
Rm |||||| n) C y. Since h is proper and convex, h(yn) +o0 for some yo E y. Since f is L-smooth, its value is finite everywhere. Hence, for any x E Rm, (xx max f (I, y) h(y) 2 f(z, 30) h(y0)) > -00, so hx))
(2x) <
+00. Therefore, based on Corollary 10.1.1 of Rockafellar (970). h(()) is continuous on A, and
thus f(z, y) h(y) is continuous in (ar y) E RTT An- Also, Vif y) continuous in (z. y) E Rm x An, since f is L-smooth. For any sequence {rL} such that || S n and y (xx) - y ) y = y="(x") for any limit point x' of (rx) ) (there at least one such limit point since || < n) since we have proved that y² is continuous. As || S n. y E An Hence, An is closed. As Ag is included in bounded y. An is compact. Therefore, based on the Danskin theorem Bernhard and Rapaport 1995). the function (x) ;= arg max f(x, 3) h(y) is differntialable with (L,(I) = V y (x)). On one hand, 2,(x)) < 4(x) since A, Y. On the other hand, when ||||| S n, y² (z) E An, so ((x)
h(y"(z)) < (x).).. Hence, when ||>||| < n, ((x) = (x) and thus (T(()) = V. = Vi (x)). Since n can be arbitrarily large,
f(I,y(xz)
( = Vil(a, (x)) for any x E R..
Next, consider any 21,72 E Thm we obtain that
[ - v )|| [ v/ (42)) - (a (x1))
<L||1> xill + Llly" (x²) (x1))
<T| - .1 L xn
=L(1 + x) x1l1.
which implies that (xx is L(1 + k)-smooth.
12

---

Published as a conference paper at ICLR 2021
B PROOF OF PROPOSITION 2
Proposition 2. Let Assumption D hold and define the Lyapunov function H()) : 4(x)) + g(x)
(1 The lll (x)]l with z == (x, y). Choose the learning rates such that The S 5.(,+37 f2 S Z
Then, the variables 2t (It, generated by proximal-Gii -DGA satisfy, for all t =
1 4x²
((2+11) S (z)) 21|2+11 - xell
(119++1 y (=(+11)) live y (2))
(4)
Proof. Consider the 1-th iteration of proximal-GIA. By smoothness of t we obtain that
(F(+1) ((xx) (#l+1 21, v + L(1 k(1+k) |0++1 2,1.3.
(17)
On the other hand, by the definition of the proximal gradient step of 2t, we have
1
g( + | 21 + 1/ V Wif 30)1 g(x))
11 Vif(2,,
2n
2T
which further simplifies to
g(+++1) g(x))
|| - - (1141
zell?
T2, Vif(Is,
(18)
27
Adding up eq.
and eq.
18 yields that
((1241) g(32+1)
1
L(1 (1)+K)
(xra) g((ra)
|00++1 -x,12 +1++1 3z, (.(.) V Vis 1 91))
212
1
11 + x)
((x)) + g(xx))
| xz
| x. ( - V firt,,, vt)l
2M
T.(1 + 1s)
= +((x)) + g(xx))
|,0+1 23, 12 + |0411 - 22ll 1if (xx)) - V (x),
2/
2
1
I(11 + k))
((x))) + +g(x)))
||4411 2y 1
L||
xelllly" (allllyy()))) (xx.) well-
211
L(1 + k)
L22x²
1 2n I1l/ (xx) 11
< (())))) + +
|30211 12
(19)
27,
Next, consider the term (x," yell in the above inequality. Note that y (xxe) is the unique minimizer of the strongly concave function f(z, y) hly). and 3t+1 is obtained by applying one proximal gradient step on it starting from ye- Hence, by the convergence rate of proximal gradient ascent algorithm under strong concavity, we conclude that with B7 S L
|| - 1² (xx))1 < (1-x- - 1² (2.)
(20)
Hence, we further obtain that
|ly (I141) l1+1ll 2 < [ +=) -1x=))1=+11~~>)))) + x1
v² (xx))l
< - - (1 + + -
(21)
Adding eqs.
19 21 we obtain
$ (Ir+1) + g(fz+1)
< ((x)) + gz(z))= - ( 2010
L(1 k))
I?x²
k2 xx2 + x) | - xel1?
2
2
+(1 2x² |11x*(xr (sre) - -11122 (x((x++)) 1) - y 1|
1
13

---

Published as a conference paper at ICLR 2021
Rearranging the equation above and recalling the definition of the Lyapunov function (=) :- =x) + ((x) + (1 + Ilu - - (x))) we have
H(z++) <H())) - 1 L(1+ + x)
I22R² - x²211 + x)) | - xell?
2//
2
1 (z)) - yell + (z(+1) 3(+1113)
(22)
4x
When T/e < (L+ 2, using x 2 yields that
L(1 (1+00) k)
L²k²
2 x² 1 +K)
2//a
L22x²
( [L + +3)² - (2k)
R
-22(2kk
2
2
2
1
[< + 3)2 21 -2-
2
2
5AT
(23)
As result, eq. can be concluded by substituting eq.
23 into eq.
22
C PROOF OF COROLLARY
Corollary 1. Based on Proposition
2 the sequences {21,3e generated by proximal-GDA satisfy
lim 10000
|a+11 zell O, lim [| - y/el O, lim
|1yr - (x+)) =0
+
t-000
Proof. To prove the first and third items of Corollary I summing the inequality of Proposition 2 over t= 0, 1,..,, T 1, we obtain that for all T 2 1,
2|| xell +
4x² (1lve1 y² (0++1)) + 11 v (xx) (11)
1
< H(z)) H(Tr)
< H(2)) [T(TT) g(Tr)]
< (20) inf ($(x) + s(x)) 400
=ERm
Letting T + 00, we conclude that
Σ 2| - xell2 + 4x² (11v4+1 y² (x++1))12 +1111 - 1¹' (x+))13) to0.
Therefore, we must have li || 21ll lim I1 (xx)l =0. To prove the second item, note that
| - vell S || - y (He)l + 1lve 3" (xx) 0q. (V1 - x + +1)llv 8 (xx))) o.
D PROOF OF THEOREM
Theorem 1 (Global convergence). Let Assumption hold and choose the learning rates Yu (L433 Fl < 1. Then, proximal-GDD satisfies the following properties.
14

---

Published as a conference paper at ICLR 2021
1. The function value sequence {(O + (24) converges finite limit H -00; The sequences [zr]t, }yt): are bounded and have compact sets of limit points. Moreover, (Ø + (x*) = H* for any limit point x² of {zebe
3. Every limit point of Jt is a critical point of ( (++ + gx)).
Proof. We first prove some useful results on the Lyapunov function (z). By Assumption I we know that g is bounded below and have compact sub-level sets, and we first show that (z) also satisfies
these conditions. First, note that (2) = ((x) + g(x) + (1- 1x2 lly - v-(=(( 2 ((x) + g(x). Taking infimum over x, on both sides we obtain that inf (z) 2 inf, D(x) + ((x)(())))))))))))) > -c. This
shows that H (z) is bounded below. Second, consider the sub-level set Zn (z,) S
a} for any a E R. This set is equivalent to {(r, + + g(z) + (1- 462 5 a).
1
For any point (x, y) E Za. the x part is included in the compact set fa : + g(x)+ I a). Therefore, the in this set must be compact, Also, the y in this set should also be compact as it is inside the co-coercive function | - y (I) Hence, we have shown that (z) is bounded below and have compact sub-level set.
We first show that { + (x1) has a finite limit. We have shown in Proposition 2 that (H monotonically decreasing. Since H (z) is bounded below, we conclude that {H (2)) has finite limit H -0, i.e., lim ( (xx) + -े Ilue 5" (x+))1 H Moreover, since llye y" (2+)) - 0, we further conclude that lim ( (z)) = H²
Next, we prove the second item. Since (z))e is monotonically decreasing and (2) has compact sub-level set, conclude that {zehe. (ye h are bounded and hence have compact sets of limit points. Next, we derive a bound on the subdifferential. By the optimality condition of the proximal gradient update of 24 and the summation rule of subdifferential in Corollary 1.12.2 of Kruger (2003). we have
E 0g(2++1) + (I++1 2e + 7/e V V (2((
Then, obtain that
1
(Ir r(t1) V (2 ( E 0(Φ
(2+11,,
(24)
which further implies that
(0)
| xell + [V -
7
|| x + [i 91) V
1
||
x + 0(| zell + (2x+())))))) vell)
//
$
+ 1111 x4|1 + [Il (x(41) - 3² (xx) + (xx)) vell)
1/
[ - L(1 + mi) | - x + L| (Ix) - well-
Since we have shown that || - xell 4 0, (x:)):) vell 4 0, we conclude from the above inequality that dista((+))).=)) (0) - 0. Therefore, have shown that
1 (I 21) v Vif(zr v4 v 0( + (xx))
7
1 - - xx) nh
and
( 4 0.
(25)
Now consider any limit point x" of x, so that Zz(7) 2 x along a subsequence. By the proximal update of Z2G), we have
1
((xa)))=
(100)) =10))-11++ (2i6) -10)-11 V V
2n
15

---

Published as a conference paper at ICLR 2021
1 --11x" =10)-112 + (x" z(1))1 V1)( 21/3
S (g(x") +
Taking limsup on both sides of the above inequality and noting that { fue are bounded, Vf is Lipschitz, || - well i and T(()) + x", we conclude that lim sup, I ((Fa))) S g(x"). Since lower-semicontinuuus, we know that lim inf, g(*)()) 2 g(x"). Combining these two inequalities yields that limy g(Xx())) = g(x²). By continuity of o, we further conclude that lim, ( + ()((()) = ($ + (xx). Since we have shown that the entire sequence {( + g) (xt)): converges to a certain finite limit H", we conclude that (+ + g)()) H" for all the limit points x² of (ma)t-
Next, we prove the third item. To this end, we have shown that for every subsequence T(() 4 x²,
have that (Φ + (x((G) 2 (Th (x²) and there exists us a (x:) such that 4n - (by eq. (25)). Recall the definition of limiting sub-differential, we conclude that every limit point x
of {2,): le is critical point of (Φ g)(),, i.e., 0 a( + (x*).
E PROOF OF THEOREM 2
Theorem 2 (Variable convergence). Let Assumption 7
& 2 hold and assume that H has the Kt.ge- ge- ometry. Choose the learning rates The S mIL+3yz and By S +. Then, the sequence {(I,, bt) generated by proximal-GDA converges certain critical point (x", (x")) of ( + g)(x), ie.
St S x.
V1 1 (x²).
Proof. We first derive bound on (z). Recall that H(2) = ((x)+ 1 and that Ilo (x) y/12 has non-empty subdifferential (1yl (z) - yll²). We therefore have
H₂H(2) > a( +)(x)) + (1
1
Oz (1lv) (z) -,1
4x²
1 (y (x) -y), {(=) = -(2 2x
where the first inclusion follows from the scalar multiplication rule and sum rule of sub-differential, see Proposition 1.11 & 1.12 of Kruger (2003). Next, we derive upper bounds on these sub-differentials.
Based on Definition 1 we can take any 0z (llv (x:) 3)l²) and obtain that
(z) v1 (x)( - y/1² u (2
0 < lim inf 2,1,2-
1|z- - æ||
[y' - n" (x)) (/"n0"(()))))))'' (z) + (xx) (()=- 2y) uu (z x))
lif 202,2--
|| 15-20 x||
(z) (x) (z) y v²(x)= 2y uT (2 x))
inf 2/3,2-
||2- - x||
ut (z x²)
lim inf 29t.
(x) + (x) - 2yl1
|| x
uT(2 -23- x)
2x 2x (x) yll lim
sup sup 222
|| x:
(101) 2x (x) - vll
||u||
(26)
where and (ii) use the fact that y* is k-Lipschitz based on Proposition I and the limsup (iii) is
achieved by letting = x + ou with - 0f in (ii). Hence, we conclude that ||w]]| S 2<|[ (x) - vll.
Since (,ll'v"(>> - y/l²) is the graphical closure of a, (Ilv" (Ir) =11²), we have that
dista, (Ilv* (1) s 2x|ly" (x) -vll-
16

---

Published as a conference paper at ICLR 2021
Then, utilizing the characterization of a( + (z) in eq. (2 we obtain that
distam(=:)))
H(s (0) [V,H(=,)))
< (ista(0+ (0) + (1- 4x² dista, (x (P) + (2 2x²²
1 10 (1=+1)) we+1ll
|x+41 xzll + V Me) (=(+++))] + (2 2k²
(1 + k) Ily (Ie+1) Betill
1/a
(9)
- + 1) || - xell + (x(+1) - well + 2 + Ri) "l (I++1) - yo+1ll
1
7/2
(1 + L(1 + 15) x1)) 1122111111 - mell + Elly* (are) vall
1
1/2
+ +2(1 + k) V1- 2 (sx)) 3el + x + 1)) [0 22.1
(01)
1 (L + 4x )1 +x) (1+ 11) -z zz (L + 4x) (xz) yell.
(27)
where (i) uses Proposition D that V2(=++1) = V 12 (Ie-1)) and that y" is x-Lipschitz, (ii)
uses eq. 21 and the inequality that va +a+bs Vā vb (a, 2 0) and (iii) uses x: 2 1.
Next, we prove the convergence of the sequence under the assumption that (2) is KE. function. Recall that we have shown in the proof of Theorem I that: 1) (2:))) decreases monotonically to the finite limit H 2) for any limit point x", ,y² of T tveh.. (x"", .y²) has the constant value H Hence, the KE inequality (see Definition ( holds after sufficiently large number of iterations, i... there exists E N+ such that for all to.
(H((2) H" )disttrr()))))) (0) 2
Rearranging the above inequality and utilizing eq. (27). we obtain that for all t 2 to. o (z)) - H))
1
(is) (0)
[ 7/
+L 4x3) (1 13) 1|:2)1120000000
- -I-- + (L + (x)))))(()11)) V V2-
(28)
By concavity of the function yp (see Definition D. we know that
(H((z) - H²) - (H(((=)+1) - HH)
2 (H(()= - (H()) - H(z++1))
(
|| =zel12 + - 11:: y² (2t))12
(29)
(1. + (I. + 4x²) ni) ||,, - --- + (L + 41)))1l ---ll
|| xell 2/4 l1ye y² (sre))
(8)
IV
+ (L + 4x (1 + x)) || - - + (L + 4m:) 11 (2,-1) V1--111
where (i) uses Proposition
2 and eq. 28 (ii) uses the inequality that a² + 2 [a + +
Rearranging the above inequality that
|| - xzll + Ilve - y² (x+)]]
1 2x
< (2)p(H(x)) - H²) (2(-1) H*)]
[[ + +L 4x3 (1 + x3) ||:te - 2z-1ll + (L + 4n) 34- 21-11]
< [[e((H(z))) - H²) - ((H())))) H*)
17

---

Published as a conference paper at ICLR 2021
+ 1 c f/2
+ +L 4k²) (I++4x)((1 +1)+ 1a x1-1l++ C CL 4k)lly" (ax-1) yr- v-- =1]
where the final step uses the inequality that 2ab v (Ca + 2)² for any a, 2 and C > 0 (the value of C will be assigned later). Taking square root of both sides of the above inequality and telescoping over = to..... T 1, we obtain that
T-1
|0+11 xell +
Σ
1lve y (sxa)l
2k
to
t=
T-1 Σ 1=
1 C + (I+
C2(HH(2))) -H* C - H
(x)(4
3t 8--1
C 77
T-1
1
+
(1.+ 4k)
Σ (x -1--lll
t=
Ce
Ce (H(z)))
( (L An
1
T-2 Σ tmfo-1
H111
+
4x²)
|0++1 - xx
0
C 1/x
T-2
7 (L+ 4k)
Σ (=t-11
Ily" (x1) vell
- where the final steps uses (ps) = s and the fact that H H" 2 0. Since the value of
select large enough C such that 2 ( 1 (L + 4x) m)) and
C' > is arbitrary,
1/x
(L++ + Hence, the inequality above further implies that
T
1 -11210 - -1l + Ce (2n))) 1 +
1
11++1 xill s 0
11 (210-1) - yto yto-111 < to0.
2 t=to
2x
Letting T oo, conclude that
F141 2z 2:/1< + co.
Moreover, this implies that (12), is Cauchy sequence and therefore converges certain limit, i.e., It 4 x². We have shown in Theorem that any such limit point must be critical point of Φ Hence, we conclude that {ath converges to a certain critical point xx of (& + (z). Also, note that lly" (Ix) vell S 0. Ct 4 x² and y² is Lipschitz mapping, conclude that {y: J converges to yn (x*).
F PROOF OF THEOREM
Theorem (Funtion value convergence rate). Under the same conditions as those of Theorem Lyapunov function value sequence (H)z) converges to the limit H² at the following rates.
2 the
KL geometry holds with 1, then H(2)) + H* within finite number of iterations:
2. If KL geometry holds with 0 E ( 1). then H (2t) &. HH super-linearly as
Lo10
(2Me) d exp
14 2 loi
(6)
2(1 0)
If KE geometry holds with 1, then H(x) H* linearly as
H(z)) - H² < (1+ 2Mc²
1 ro-t (H()))) H²),
Vt 2 to:
18

---

Published as a conference paper at ICLR 2021
4. KL geometry holds with 0 (0. 2)) then (2x) 4 H sub-linearly
(zt)) H < [C(t to)] AA 2 lo-
(8)
where C min
1-29 88M dw
(1-20)
(1 (1-2-
Proof.
Note that eq.
27
implies that
distam(())))) ()) (0)² =2
(L (1 x)) || zell + 2(L + 4x)) (1)l)))))))))))))))))))))))))(
vell.
7/e
(30)
Recall that we have shown that for all 2 to. the Kł property holds and we have
(H)()) H]] dist ? (0) 2
Throughout the rest the proof, we assume 2 to- Substituting eq. that
(30 into the above bound yields
=22 - ( + (L 4x2) k)) || x1-1l1
1/2
+(L + 4k)² 2 11 (01-1) 1122112
S2M [2 )² 21|0g - F2 22-1ll 11 + 4x² (x2-1) - ye- 1111
(31)
where the second inequality uses the definition of M in eq.
Substituting eq. and (s((s 0- 0) iNto eq.
(31 and rearranging, we further obtain that
[c(H((=)) -ー < 2M H(x)]]
Defining d, (2,) H", the above inequality further becomes
d-1 - 2MC d 2(1-9)
(32)
Next, prove the convergence rates case by case.
(Case 1) / = 1, then eq. 32 implies that d d, 2 MM > 0 whenever de > 0. Hence, de
achieves 0 (i.e., H (2x) achieves H²) within finite number of iterations.
(Case 2) If E (2. 1), since d, 2 0, eq.
32 implies that
d
de
2(1-0)
(33)
2Mc²
which is equivalent to that
(2Mc 20 de
(2 dz-1
2(-0)
(34)
Since de 0. (2Mc² 20 de, Se- for sufficiently large t N+ and t to. Hence, eq. implies that for 2 f
34
(2Mc)) _ de S (2Mc²) x de,
1-
cxxp
22 - 8)_
Note that 0 E (t, implies that 2(1 the super-linear rate given by eq.
1, and thus the inequality above implies that H (xx) $ H
19

---

Published as a conference paper at ICLR 2021
(Case 3) If 2.2
1
d-11 de
2M des
(35)
which implies that de v (1+ 2M given by eq. (7) (Case 4) If (0, })) consider the following two subcases. If d S 2d,, denote (b)))
d- Therefore, de + 0 (i.e., H(z)) H) at the linear rate
I-26 8
-(1-9)
then
(dd)) - (d(-1)) fam.
de-1
(1) 2(100)
-s'(s)
s s-2(1-0) ds 2 d-
(d--
de)
de
(18)
dt
2(1-0)
(36)
2
c2
dl-1
23 M 2
8M
where (i) uses de s d and -2(1 0) 1, and (ii) uses eq. 32
dd-1 2dc
(d+e) 1/(d(-1)
28 (dle
(1-(11-0))
d,-1 (1-1)-)))
1 - 28 (d," (1 (1-20)
(2d.) (11-29)
1 - (1-28)
1 1-2 (1-22) (1-20)
dr
(11220)
>
dio
(37)
20
29
where we use -(1 - 20) < 0. d > 2dl and de S dio Hence,
2 (1 (1-20) (1-20)
(dd) - (dd,1)) 2 min 18M
> 0,
(38)
1 20
1 20
which implies that
C
C (t to)
((d)) 2 (dd,))
(t-
(t to)
20
28
By substituing the definition of sb the inequality above implies that H (2x) ) H in sub-linear rate given by eq. 8
G PROOF OF THEOREM 4
Theorem 4 (Variable convergence rate). Under the same conditions as those of Theorem 2 the
sequences {zt, V. converge to their limits x", "",y" (x*) respectively at the following rates.
1. If Kt. geometry holds with 0 = 1, then (It, vc) - (x", (x*)) within finite number of itera- tions:
2. If Kt. geometry holds with 0 E ($) 1), then (Ie, Vs) + (x", ,y" (x*)) super-linearly as
max {11ara x lbut v² (x*)))) 0
(expp exp (
Vt 2 to:
(9)
3. If KL geometry holds with 0 = 11 then (Ies vr) + (x", "0,,y((x"" (x*))) linearly as
max {1 - 2"11 11. l1,. (x*) I| < x0((
c0(mmmi (mmi {2,1+ 1+ 2M 1)
1 (fo 11/2 (0000/2)
AA > to: (10)
4. If KL geometry holds with 0 (0, }) then (Ie, vi) + (z" y² (x*)) sub-linearly
max {1lxr - x=11 Iy: - 3 (x*)1I} < o ( (0) -m)) 1i 4a
(11)
20

---

Published as a conference paper at ICLR 2021
Proof. (Case 1) 0 = L, then based on the first case of Appendix F (()) H after finite number of iterations. Hence, for large enough t, Proposition yields that
2112111 xxll2
4x² (1lv+1 (x++1)) llu. y (ax)13) & H(2)) (2++1) 0, (39)
which implies that + Iy and y/ - y (xx) for large enougth I. Hence, 4 - x² and y/: - y (x*)
within finite number of iterations.
(Case 2) If ($. 1), denote A, = || 2rll + zze live - y (2+)). Then, based on the definition
of M in eq. (5) we have
+ (L (L+4))) + x)) ||, x--1ll + (L + (x) V4- S V2MA,
(40)
Hence, eqs.
28 & 40 and (l(s) csa imply that
c(H(z - ( ( ((2MAL-))
which along with 0 < implies
- 11 (cv ((
(41)
Then, eqs. 29 & (40
imply that
| x2ll2 + 1 11 y (xx))l
(H()) H*) (H(((21+)) H²)
1x2
2/2M A,-1
Using the inequality that a² + 62 > {a + 6)2 and recalling the definition of Ae and (p(s) "o, the above inequality further implies that
(H(z))
c ((( - 2 H 0
(42)
0
4 4
Substituting eq.
41
into eq.
42 and using H(2+11) H' 2 0 yield that
AZ < 0 (cV2MAr-1))
which is equivalent to that
C1A: S (C1A(-1) ,i-0;
(43)
where
G (4/0) - (cv2M I..
Note that eq. (43 holds for 2 to Since A + 0, there exists t 2 to such that CiA,, Se1
Hence, by iterating eq. 43) from 1 1, we obtain
2(1 0) )
1. 1A 2 41
C1A, S exp
Hence, for any t 2 t 1
Σ
A
8
exp
8-11
2(1 0)
smt
6-41
1-4
1 9-417
C2 exp
exp
2(1 8)
2(1 8)
2(1 8)
1-4
exp
2(1
0)
Σ exp
2(1 0)
1
2(1
0)
a=1
21

---

Published as a conference paper at ICLR 2021
6-61
exp
exp
2(1
8)
2(1 8)
==
6-11
2(1 0) )
Ci exp
exp
2(1 0)
8=0
of exp
2-4
(44)
2(1 0)
where (i) the inequalities that 2(1-0) and that 2 2 t + 1, and (ii) uses the fact that == exp
() too is positive constant independent from Therefore, the convergence rate (9) can be directly derived as follows
T-1
| x² = limm -limsup ||x - xTl S lim sup T-+00
Σ
|x - xell
T+000 e=
< simmsu sup
Σ T T-000 8=t
T-1
A. S of exp [- [(22
2(1 - 0) )
1-61 "
(45)
and
(6) yy (x*))1
Ilue y¹ v0xx")| Sllee - yf (ft) + (,,)()))
S 2n.A, + k$| - x=1l
22
Σ
00
Ag xa| x'1l of exp 2(1 - 8)
((i)
t-
where (i) uses the Lipschitz property of y² in Proposition D and (ii) uses eqs. 44 & 455)
(Case & 4) Notice that eq. implies that
(42) still holds if (0. 2 Hence, A, 2 2 Ar-1. then eq. 422
8c 2M
A
[(H(2)) H*) 1 (H(24)) J')
Otherwise, A, S 1 A1-1. Combining these two inequalities yields that
Gev2M, [(H( - H² (H(#++1) (H(#)))- Hm) + - A.-1.
4, < 0
Notice that the inequality above holds whenever / 2 ln- Hence, telescoping the inequality above yields
1 T-1 Vt
A
[(H(z)) H - (H(2T41)
Σ
Ag,
2 to
(46)
s=t-1
which along with Ar 2 0, H (2T+1) H 2 0 implies that
8cV2M
Σ A.
(H(z)-
11 +
A
Letting = to and T' co in the above inequality yields that Va As t00. Hence, by letting
+ oc and denoting S, Exe A, in eq. (46), we obtain that
8c
1 St-1,
S <
(H())) - Hr) +
VI 2 lo
0
2
which further implies that
8cv2M
S, S 2
Sio +
Σ
(H H
(47)
2
s1
22

---

Published as a conference paper at ICLR 2021
(Case 3) If
1/2, eq. 7 holds. Substituting eq. 7 and 9 1/2 into eq.
47 yields that
1
(fo s)/2
St _ 2
Sto +
(2)
H*]
1 +
2
2M
Sto +
C2
Σ
(1
1
-6/2
(48)
2
2
8M22
smto++
where
C = (M( (1 (1+
1
te/2
(49)
2M
a positive constant independent of l.
Notice that when 1
8Mc 1,
-8/2
+ 8M2
11-16 t0
and when 1 + sM62 < 1I
(t-10)/2
Σ s
x/2
-1/21 1
-11
SMC2
-1/2
4
8Mc22
8.M22
+
8Mc²
8Mc2
Since either of the two above inequalities holds, combining them yields that
-//2
S 0 max [ 1o (1 8M
1/2
8M2
Substituing the above inequality into eq.
448 yields that
S, < 21- S.. + of max 22- - -o): (1+ 2M
11/2
50 min (2 + 2Mc2
Hence,
(1) S Σ
A, S, s o0 min 2, + 2Mc² )
| x²1l
s=t
where comes from eq. (45 Then,
ll y² (z")) <11y: y (at) + 11 (xx) 3" (x*) < 2kA, + K x||2, xx
x²
<2kS; + x ,| x' s of min 22,1 2M 2
1//2
The two above inequalities yield the linear convergence rate (10 (Case 4) If 0 E (0, 2), then eq. constant C33 > 0,
g holds.
Substituting eq. into eq.
47 yields that for some
8cV2M St0 +
C3 2
S, < to
(8
10) 1-20
0
8=1++1
8cCav
2M
t-to
St0
288 1-20
20-
26-
(
S
MM
2
8cCaV2M
L-
Σ
-
1-
2
20-
20
23

---

Published as a conference paper at ICLR 2021
S 20-
Sto
+
8cC3V2M
2
80C3V2M
Σ
Lo
2
11- 40
-m
20-
2
2
$=
(0)
Sto
8cC3v2M 2M
2
8cC3v2M 2M
1 to
1-28
2
2
20-
20
=0
(t -
(o) - 10 =0
(t 10)-1110
1-20
(50)
2
2(1-ta1/2
where (i) denotes 1 [(t /2), (ii) uses the incquality that Ex
2 Ei=0 2 < 22'
++1 _
Therefore, the sub-linear convergence rate eq. (IT) follows from the following inequalities.
|| - x=1 S S. so to) 1-m
and
1/ 1" (x*))l Slyye- y (x++)) + (xx) -yy "**")) S 2mA, + Kilas x²1
22x:S + x||0, =0' o (t: to) 1 1
24


Reviews:
[{"review_id": "wCRYHCRpEkE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors analyze the convergence of a proximal gradient descent ascent (GDA) method when applied to non-convex strongly concave functions. To establish convergence results, the authors show that proximal-GDA admits a novel Lyapunov function that monotonically decreases at every iteration. Along with KL-parametrized local geometry, the Lyapunov function was used to establish the convergence of decision variables to a critical point. Moreover, the rate of convergence of the algorithm was computed for various ranges of KL-parameter. \n\nPros:\nThe paper studies an interesting and relevant problem in a vibrant field of research. \n\n\nThe convergence analysis of proximal-GDA are detailed and well presented (covering function value convergence, variable convergence, function value convergence rates, and variable value convergence rates). To show the results, the authors provided a novel Lyapunov function and analyzed the convergence using KL local geometry.\n\nThe paper is very clear, concise and neatly written (almost free of typos).\n\nThe related material are referenced and well-discussed in the paper. The authors clearly positioned their work in the related field and discussed their contributions in comparison to other similar works.\n\n\nCons:\nThe paper lacks any experimental results. Demonstrating the different convergence rates on critical points with various KL-parameter can be good experiment.\n\nMinor Comments:\n1.\tDefinition 2: Should it be $h(z)$ instead of $f(z)$?\n2.\tEquation (19) in the Appendix, and P Third Inequality should be =.\n3.\tPage 14: upper bound on distance of subgradient set to 0, second inequality should be =.\n4.\tAppendix F: Theorem 3, Function missing a ``'c'\n5.\tEquation (36): $d_{t-1}$ instead of $t_{t-1}$.\n6.\tLast expression of Page 19: I think 1/2 is missing in the left hand-side. \n\n---------------------------------------------------------------------------------------------------\nSatisfied with the response, will keep my score the same.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QrXC-IJ8Mvs", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied the convergence properties of the proximal-GDA algorithm for solving nonconvex-strongly-concave optimization problems. It develops a novel and comprehensive theoretical understanding of the variable convergence and rates of the algorithm under the KL geometry by identifying an important and intrinsic Lyapunov function. \n\nSpecifically, the paper considers a regularized nonconvex-strongly-concave optimization problem, with one convex regularizer and another possibly nonconvex and lower-semicontinuous regularizer. This problem formulation generalizes many existing differentiable minimax problems. Then, under standard conditions in Assumption 1, the authors identified a novel and important Lyapunov function H(z) and showed that this function monotonically decreases throughout the optimization process, although the minmax objective function value may oscillate. Based on this new characterization of Lyapunov function, the authors proved that every limit point of the algorithm is a critical point of the minmax problem. Moreover, under the general KL geometry of the Lyapunov function, they formally proved that proximal-GDA converges to a single critical point. This is the first variable convergence result in nonconvex minmax optimization. Besides, they also characterized the dependence of the variable and function value convergence rates on the parameterization of the KL geometry.\n\nOverall I believe this is a novel and important work in minimax optimization. In particular, the Lyapunov function is a very powerful tool for studying the convergence properties of the two variable sequences of proximal-GDA. It conveniently simplifies the analysis of minmax optimization into the analysis of min optimization via Proposition 2. Also, the monotonic decreasing property of the Lyapunov function further enables analyzing this algorithm under the general KL geometry, and obtain a fundamental variable convergence (rates) result(s). These technical tools develop a new framework for analyzing minmax optimization algorithms and can potentially used to study other minmax algorithms. \n\nBelow are some of my minor comments:\nIn Def.2, the {h_\\Omega < f(z) < h_\\Omega + \\lambda}, should be h(z).The proof of Theorem 2 assumes that H is a KL function. As H is essentially the objective function regularized by some quadratic terms, is it sufficient to assume \\Phi+g is KL?If possible, I suggest do a simple experiment to verify the monotonic decreasing property of the Lyapunov function.", "extra_scores": {}, "extra_text": {}}, {"review_id": "IB3g5HFmEuE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis paper discusses the convergence of the proximal gradient algorithm in the case of KL geometry. It does not propose a new algorithm but rather focuses on understanding the simplest (although not the best) algorithm that can be applied to the saddle point objective.\n\nI enjoyed reading this paper, I find the theory to be quite interesting and well-grounded. The minmax problem has gained considerable attention recently but is not yet fully developed, and this work has a valid contribution. I think its main strength is the simplicity of the discussed algorithm and I hope that it will lead to further extension. The work is purely theoretical, but I still think it could benefit from some numerical experiments, especially if the authors identified a practical setting that can be described by the paper's assumptions.  The other weakness is the lack of clear motivation: the authors consider a very specific setup, with two proximable functions and one non-bilinear joint term, certain assumptions about each of the functions, and I don't feel that the choices were sufficiently motivated. Still, I vote for acceptance because, in my opinion, the topic is underexplored.\n\n## Additional comments\n\n1. The authors wrote in Section 1.1 that they \"propose a proximal-GDA algorithm\", and I find this choice of words to be confusing: this algorithm is by far not new as it is a well-known special case of the Forward-Backward iteration, which dates back to (1979, \"Splitting algorithms for the sum of two nonlinear operators\"). I expect the authors to properly cite the related literature on Forward-Backaward and mention the guarantees that follow from the existing bounds on Forward-Backward algorithm (which has been quite extensively studied).\n\n2. The Lyapunov function in Proposition 2 is quite interesting, but the quadratic term is not really explained. I think the paper would benefit from explaining why this term shows up in the proofs.\n\n3. The bounds in Theorem 1 and other results seem to have a terrible dependency on the conditioning. In the strongly monotone case, the stepsize in GDA has to be of order O(1/(kappa*L)), but here it is O(1/(kappa^3*L)). This is not completely unexpected due to the nonconvexity, but I'm wondering if the authors think that the bounds are tight or they can be improved.\n\n4. The bad conditioning in the bounds seems to be coming from the update of GDA, and a better update should lead to faster rates. I think that the extragradient algorithm should have the right conditioning with stepsize O(1/L), and several methods have been proposed recently that achieve O(kappa) bounds: 1) \"Reducing noise in GAN training with variance reduced extragradient\", 2) \"Revisiting stochastic extragradient\", 3) \"On the convergence of single-call stochastic extra-gradient methods\". I'd appreciate if the authors could comment on that.\n\n5. The authors wrote \"The Kurdyka-Łojasiewicz (KŁ) geometry <...> has been shown to hold ubiquitously for most practical functions\" -- I think this is a big overstatement,  I haven't seen any example that would be relevant to the minmax optimization.\n\n6. The authors assume that y*(x) is differentiable in Section 4. First of all, please make this assumption more explicit as it's very easy to miss, particularly so because the other assumptions are presented in Assumption 1. Secondly, I'm wondering if the assumption that y*(x) is differentiable is really necessary. The authors prove that y* is Lipschitz, so assuming differentiability makes the class of relevant objectives small. Secondly, as far as I can see, differentiability is only used in the proof of theorem 2, and the authors only need f1(x)=||y-y*(x)||^2 to be differentiable and to satisfy ||nabla f1(x)|| <= const * f1(x). It might be possible to relax the assumption a little bit (for example ||x||^2 is differentiable everywhere but ||x|| isn't).\n\n7. Remark 1 is not precisely correct: to relax the assumption, function h would have to be strongly concave with constant mu>L as otherwise adding gamma*h to f with gamma<1 will not make f strongly concave.\n\n### Minor issues\nAbstract: \"it is lack of understanding\" -> \"it lacks understanding\"\np.2, \"the entire variable sequences of proximal-GDA have a unique limit point\" -> \"sequence ... has\"\np.6, \"proximal-GDA admits a very important Lyapunov function\" -- it's a bit strange to call the Lyapunov function \"very important\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "AabcP1xC0Ky", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors analyze a proximal gradient descent-ascent method for nonconvex minimax problem under specific assumptions (another name would be a forward-backward algorithm). The authors prove subsequence convergence of iterates to critical points and furthermore,  additionally under the Kurdyka-Łojasiewicz condition, prove iterate convergence with some  rates.\n\nI have two main concerns.\n1) The first one is that required assumptions are quite restrictive. Basically, whatever analysis needs the authors included into assumptions. There is no much discussion about Assumption 1. I understand that it is just a concatenation of different and popular assumptions in the literature, but together they look stringent. What are the real interesting examples that satisfy all of them?\n\n2) The second concern is that a big part of obtained results is very natural if not known already. The authors cite Lin et al. (2020), where the problem $\\min_x \\max_y f(x, y)$ was studied. Adding regularizers $g$ and $h$ do not complicate things much. Even though we allow $g$ to be nonconvex, we use a proximal step for it, which preserves monotonicity of the Lyapunov energy.  To explain better what I mean, see Attouch,  et. al. \"Convergence of descent methods for semi-algebraic and tame problems\": once we establish convergence for a forward method (gradient of $f$), adding a backward step (prox of $g$) is easy.\nFinally, adding Kurdyka-Łojasiewicz assumption does not change situation much. Its application is standard, once we have some decrease in the objective or energy.\n\n\nTo conclude, I don't see much value in the proposed analysis, since its strength lies in the required assumptions and not in the novel technique.\n\n\nBelow I collect a more detailed list of issues I found.\n\n\n1. page 1: What is the definition of \"function geometry\"? Why is it strong convexity/concavity?\n\n2. page 2, \"converges to a certain stationary point at a sublinear rate, i.e., $|G(x_t)|\\to 0$\": I didn't understand such explanation of the sublinear rate.\n\n3. page 2. What is \"variable convergence\"? Probably the authors mean \"iterates convergence\".\n\n4. page 2, \"The Kurdyka-Łojasiewicz (KŁ) geometry provides a universal characterization...\": I am afraid, this is not true, it does not provide a universal characterization.\n\n5. page 2, \"a very novel Lyapunov function\": Adding more adjectives would only help of course.\n\n6. page 5, \"we propose the following proximal-GDA algorithm...\": It is a well known method. Another name for it is \"forward-backward method\".\n\n7. page 5: If $g$ is not convex, how is $x_{t+1}$ uniquely defined?\n\n8. Proposition 1, proof. $\\Phi + g$ is lower bounded, but $g$ can be $+\\infty$ on the set $A_n$, thus we cannot conclude that $\\Phi$ is lower bounded on $A_n$\n\nProposition 2, proof.\n1. page 12: $y^*(x_t)$ is the unique minimizer of the strongly concave function $f(x_t, y) - h(y)$, not of $f(x_t, y)$.\n2. page 14: In Eq. 24 it is worth to add a reference for the sum rule of a subdifferential.\n3. page 14, Eq. 25: the notation in the end is incorrect (as well as in page 4). Subdifferential is a set.\n\nTheorem 2, proof.\n1. page 15. Why is $y^*(x)$ differentiable? We proved that it is only Lipschitz. Note that the sum rule applied to the subdifferential of $H(z)$ won't be valid.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies nonconvex-strongly concave min-max optimization using  proximal gradient descent-ascent (GDA), assuming Kurdyka-Łojasiewicz (KŁ) condition holds. The main contribution is a novel Lyapunov function, which leads to a clean analysis. The main downsides of the paper as discussed by the reviewers are the lack of experiments and somewhat stringent assumptions needed in the analysis. Nevertheless, the paper was overall viewed favorably by the reviewers, who considered it a worthwhile contribution to the area min-max optimization.  
Decision: Accept (Poster)