Escaping Saddle Points in Nonconvex Minimax Optimization via Cubic-Regularized Gradient Descent-Ascent
Authors: Ziyi Chen
Qunwei Li
Yi Zhou
Venue: ICLR 2022 Submitted (2022)
Keywords: Minimax optimization
Gradient descent-ascent
saddle point
cubic regularization
Lojasiewicz gradient geometry

Abstract: The gradient descent-ascent (GDA) algorithm has been widely applied to solve nonconvex minimax optimization problems. However, the existing GDA-type algorithms can only find first-order stationary points of the envelope function of nonconvex minimax optimization problems, which does not rule out the possibility to get stuck at suboptimal saddle points. In this paper, we develop Cubic-GDA -- the first GDA-type algorithm for escaping strict saddle points in nonconvex-strongly-concave minimax optimization. Specifically, the algorithm uses gradient ascent to estimate the second-order information of the minimax objective function, and it leverages the cubic regularization technique to efficiently escape the strict saddle points. Under standard smoothness assumptions on the objective function, we show that Cubic-GDA admits an intrinsic potential function whose value monotonically decreases in the minimax optimization process. Such a property leads to a desired global convergence of Cubic-GDA to a second-order stationary point at a sublinear rate. Moreover, we analyze the convergence rate of Cubic-GDA in the full spectrum of a gradient dominant-type nonconvex geometry. Our result shows that Cubic-GDA achieves an orderwise faster convergence rate than the standard GDA for a wide spectrum of gradient dominant geometry. Our study bridges minimax optimization with second-order optimization and may inspire new developments along this direction.

Under review as a conference paper at ICLR 2022
ESCAPING SADDLE POINTS IN NONCONVEX MINIMAX OPTIMIZATION VIA CUBIC-REGULARIZED GRADIENT DESCENT-ASCENT
Anonymous authors Paper under double-bling review
ABSTRACT
The gradient descent-ascent (GDA) algorithm has been widely applied to solve nonconvex minimax optimization problems. However, the existing GDA-type algorithms can only find first-order stationary points of the envelope function of nonconvex minimax optimization problems, which does not rule out the possibility to get stuck at suboptimal saddle points. In this paper, we develop Cubic-Gii GDA the first Newton-type GDA algorithm for escaping strict saddle points in nonconvex- strongly-concave minimax optimization. Specifically, the algorithm uses gradient ascent to estimate second-order information of the minimax objective function, and it leverages the cubic regularization technique to efficiently escape the strict saddle points. Under standard smoothness assumptions on the objective function, show that Cubic-GDA admits an intrinsic potential function whose value mono- tonically decreases in the minimax optimization process. Such property leads desired global convergence of Cubic-GDA at a sublinear rate. Moreover, we analyze the convergence rate of Cubic-GDA in the full spectrum of gradient dominant-type nonconvex geometry. Our result shows that Cubic-GDA achieves an orderwise faster convergence rate than the standard GDA for wide spectrum of gradient dominant geometry. Our study bridges minimax optimization with second-order optimization and may inspire new developments along this direction.
second-order stationary point
INTRODUCTION
Nonconvex minimax optimization a popular optimization framework that has broad applications in modern machine learning, including game theory (Ferreira et al., 2012), generative adversarial networks (Goodfellow et al., 2014), adversarial training (Sinha et al., 2017), reinforcement learning (Qiu al., 2020; Ho and Ermon, 2016; Song et al., 2018), etc. A standard nonconvex minimax optimization problem is shown below, where f is smooth nonconvex function in r.
min max f(z RER YER"
In the existing literature, many optimization algorithms have been developed to solve different types of minimax problems. Among them, simple and popular algorithm is the gradient descent-ascent (GDA), which alternates between a gradient descent update on x and a gradient ascent update on y in each iteration. Specifically,, the global convergence of GDA has been established for minimax problems under various types of global geometries, such as convex-concave-tee convex in and concave in y) (Nedić and Ozdaglar, 2009; Du and Hu, 2019; Mokhtari al., 2020; Zhang and Wang, 2021), bi-linear geometry (Neumann, 1928; Robinson, 1951) and Polyak- Lojasiewiez geometry (Nouiched et al., 2019; Yang et al., 2020), yet these geometries are not satisfied by general nonconvex minimax problems. Recently, many studies proved the convergence of GDA in nonconvex minimax optimization for both noncomvex-comcat problems (Lin et al., 2020; Nouiched al., 2019; Xu et al., 2020d) and nonconvex- sitronly strongly-cooncceee problems (Lin et al., 2020; Xu et al., 2020d; Chen et al., 2021). In these studies, it has been shown that GDA converges sublinearly to a stationary point where the gradient of certain envelope function of the minimax problem vanishes.
geometry (f is

---

Under review as a conference paper at ICLR 2022
Although GDA find first-order stationary points of nonconvex minimax problems, such type of convergence guarantee does not rule out the possibility that GDA may get stuck at suboptimal saddle points of the envelope function, which are well known to be the major challenge for training high-dimensional machine learning models (Dauphin et al., 2014; Jin et al., 2017; Zhou and Liang, 2018). On the other hand, while numerous algorithms have been developed for escaping saddle points in conventional nonconvex optimization, e.g., first-order algorithms (Ge et al., 2015; Jin et al., 2017; Carmon and Duchi, 2016; Liu and Yang. 2017) and second-order algorithms (Nesterov and Polyak, 2006; Agarwal et al., 2017; Yue et al., 2019; Zhou et al., 2018), such type of algorithm has not been developed for escaping saddle points in nonconvex minimax optimization. Therefore, we want to ask the following fundamental questions.
Q: How to develop a provably convergent Newton-type GDA algorithm that can effectively escape saddle points in nonconvex minimax optimization? How fast it converges?
Developing and analyzing such an algorithm is nontrivial due to the following reasons: 1) we need to have a good understanding and characterization of both the first-order and second-order information of nonconvex minimax problems: 2) we need to develop a computationally feasible and efficient GDA algorithm that can leverage the local curvature of the function to escape saddle points; 3) we aim to develop a unified analysis framework that can characterize the convergence rate of this algorithm under different types of nonconvex geometry of the minimax problem.
In this paper, we provide comprehensive answers to these questions. We develop the first Newton-type GDA algorithm that escapes strict saddle points and converges to second-order stationary points in wwweeee--sstooooooooo convergence rates of this algorithm under various types of nonconvex geometry. We summarize our contributions as follows.
minimax optimization. We also characterize the global and local
1.1 OUR CONTRIBUTIONS
We consider the minimax optimization problem (P), where f is twice-differentibble and nonconvex- dtronglyconcave function, and its gradient and Jacobian matrices are Lipschitz continuous. Define an envelope function (xx) := maXgeR= fx. y). The existing GDA algorithms can only find first-order stationary points that satisfy V = 0. In this paper, we develop Newton-type GDA algorithm that converges to second-order stationary points of the nonconvex minimax problem (P).
Newton-type GDA algorithm that leverages the classical cubic regularization technique to escape saddle points. Different from the standard cubic regulariza- tion algorithm that uses the Hessian information of the function, the Hessian of Φ(x) is not directly available in nonconvex minimax optimization, and hence we develop a rigorous and computationally feasible scheme in Cubic-GDA to estimate the Hessian.
Specifically, we propose Cubic-GDD
We study the global convergence property of Cubic-GDA in general wewcoonvee-sttonnyyoooooo optimization. Specifically, we show that Cubic-GDA admits an intrinsic potential function H (xx x', y) (see Proposition 2), which monotonically decreases along the trajectory of Cubic-GDA. Based on the monotonicity of this potential function, we show that every limit point of the parameter sequence { generated by Cubic-GDA is a second-order stationary point of the minimax problem.
We further analyze the aymptotic convergence rates of Cubic-GDA under broad spectrum of the local nonconvex E.ojasiewicz gradient geometry. In this case, we show that Cubic-GDA converges to unique limit point, which is second-order stationary point. Moreover, as the geometry parameter increases (i.c., sharper local geometry), the convergence rate of Cubic-GDA accelerates from sub- linear convergence up to super-linear convergence, as we summarize in Table below. particular, these convergence rates are orderwise faster than those of the standard GDA under the same type of nonconvex geometry (Chen et al., 2021) !.
Note that the geometry parameter 0 in this paper corresponds 1 in (Chen al., 2021).
2

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison of potential function value gap (2) H* convergence rates of Cubic-GDA
and GDA under different parameterizations of Lojasiewiez gradient geometry.
Geometry parameter
GDA (Chen et al., 2021)
Cubic-GDA (This paper)
0 E (2, +00)
Super-linear convergence
Super-linear convergence
0 = 2
Linear convergence
Super-linear convergence
0 E (2,2)
Sub-linear convergence
Super-lina linear convergence
0
Sub- convergence
Linear convergence
0 E (1, 3) 2
Sub-linear convergence
Sub-linear convergence
1.2
RELATED WORK
Many studies characterized the convergence of GDA in nonconvex minimax optimization. Specifically, Lin et al. (2020); Nouiehed et al. (2019); Xu et al. (2020d) studied the convergence of GIAA in the nonconvex-concave setting whereas Lin et al. (2020); Xu et al. (2020d) focused on the nonconvex-siie wer---sttoooooncceee is shown that GDA converges et al. (2021) proved the parameter convergence of proximal- -DAA in regularized nonconvex-stronge concave optimization under the there are orderwise slower than that of Cubic-GDA. Yang et al. (2020) studied an alternating gradient descent-ascent (AGDA) algorithm in which the gradient ascent step uses the current variable x++1 instead of 2,. Xu et al. (2020d) studied an alternating gradient projection algorithm which applies le 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 (2021) analyzed optimistic gradient descent-ascent (OGDA) which applies negative momentum to accelerate GDA. Mokhtari et al. (2020) also studied an straaggrddiet algorithm which applies two-step GDA in each iteration. Nouiched et al. (2019) studied multi-step GDA where multiple gradient ascent steps are performed, and they also studied the coomentum-accelerateed version. Cherukuri et al. (2017); Daskalakis and Panageas (2018); Jin et al. (2020) studied GDA in continuous time dynamics using differential equations. Adolphs et al. (2019) analyzed a second-order variant of the GDA algorithm. In concurrent work (Luo and Chen, 2021), the authors proposed and studied the same Cubic-GDA algorithm. They characterize the computation complexity under a special type of inexactness that approximates the inverse Jacobian using matrix Chebyshev polynomials. As comparison, this study focuses on analyzing the global and local convergence properties of Cubic-GDA.
Deterministic GDA algorithms:
setting. In these general nonconvex settings, certain stationary point at a sublinear rate. Recently, Chen
geometry. The convergence rates obtained
Stochastic GDA algorithms: Lin et al. (2020); Yang et al. (2020) analyzed stochastic GDA and stochastic AGDA, which are direct extension GDA and AGDA to the stochastic setting. Variance reduction techniques have been applied to stochastic minimax optimization, including SVRG-based (Du and Hu, 2019; Yang et al., 2020), SPIDER- (Xu et al., 2020c), SREDA (Xu et al., 2020b), STORM (Qiu et al., 2020) and its gradient free version (Huang et al., 2020). Xie et al. (2020) studied the complexity lower bound of first-order stochastic algorithms for finite-sum minimax problem.
Cubic regularization (CR): CR algorithm dates back (Griewank, 1981), where global convergence of the algorithm is established. In Nesterov and Polyak (2006), the authors analyzed the convergence rate of CR to second-order stationary points for nonconvex optimization. In (Nesterov, 2008), the authors established the sub-linear convergence of CR for solving convex smooth problems, and they further proposed an accelerated version of CR with improved sub-linear convergence. Recently, Yue et al. (2019) studied the asymptotic convergence properties of CR under the error bound condition, and established the quadratic convergence of the iterates. Recently, Hallak and Teboulle (2020) proposed framework of two directional method for finding second-order stationary points in general smooth nonconvex optimization. This main idea of the algorithm is to search for a feasible direction toward the solution and is not based on cubic regularization. Several other works proposed different methods to solve the cubic subproblem of CR, e.g., (Agarwal et al., 2017; Carmon and Duchi, 2016; Cartis et al., 201 lb). Another line of work aimed at improving the computation efficiency of CR by solving the cubic subproblem with inexact gradient and Hessian information. In particular, Ghadimi al. (2017) proposed an inexact CR for solving convex problem. Also, Cartis al. (201 la) proposed
3

---

Under review as a conference paper at ICLR 2022
adaptive inexact CR for nonconvex optimization, whereas Jiang al. (2017) further studied the accelerated version for convex optimization. Several studies explored subsampling schemes to implement inexact CR algorithms, e.g., (Kohler and Lucchi, 2017; Xu al., 2020a; Zhou and Liang, 2018; Wang et al., 2018).
2 PROBLEM FORMULATION AND PRELIMINARIES
In this section, we introduce the problem formulation and present some preliminary results that will be used in the analysis.
Notation:
For notation simplicity. we denote Vif, V2f as the gradients with respect to the first and the second input arguments of f, respectively. We also denote VII,, 222 the Jacobian matrices where the second-order derivatives are taken over the first and second arguments of f, respectively. Moreover, denote V V12 the Jacobian matrix where the second-order derivative is taken over the first argument of f and followed by the second argument, and 22 f is defined in a similar way.
We consider the minimax optimization problem (P) that satisfies the following standard assumptions. Assumption 1. The minimax optimization problem (P) satisfies:
Function f(.))) ) is L -mmoohh and function f(x,-) :) is u-strongly concave for all fixed æ;
2. The Jacobian matrices Vnf, V12f, 2 222 are Ln-Lipschitz;
Function & is bounded below and has compact sub-level sets.
To elaborate, item 1 considers the class of sancconve-sstrongyy-coom widely studied in the minimax optimization literature (Lin et al., 2020; Jin et al., 2020; Xu et al., 2020d; Lu et al., 2020). Items 2 assumes that the block Jacobian matrices of are Lipschitz, which a standard assumption for analyzing many second-oree -ooeed-order optimization algorithms (Nesterov and Polyak, 2006; Agarwal et al., 2017; Yue al., 2019). Moreover, item guarantees that the minimax problem has at least one solution. By strong concavity of f(x,, ), it is clear that the maximizer (z) == arg maxyeR" fax y) is unique for every E R In particular, if x² is second-order stationary point of (xx), then (x",y" (z*)))
functions f that has been
)) is the desired solution of the minimax problem (P).
Define an envelope function (z)) := maXyER" f(z, 3). Then the minimax problem (P) equivalent to the minimization problem. min ((z), where ((x) = maxyek" fax, v). As we show in item 2 of Proposition later, this envelope function & (xx) smooth and nonconvex. The existing GDA algorithms can only find first-order stationary points of the minimax problem that satisfy V 0.
In this paper, we aim to develop a provably convergent algorithm that can find second-order stationary points x² of the function (xx) that satisfy the following set of conditions.
(Second-order stationary):
V$(x") 0, VO
In the existing literature, many optimization algorithms have been developed for finding second- order stationary points in conventional nonconvex minimization problems. This includes first-order algorithms (Ge et al., 2015; Jin et al., 2017: Carmon and Duchi, 2016; Liu and Yang, 2017) and second-order algorithms (Nesterov and Polyak, 2006; Agarwal al., 2017; Yue al., 2019; Zhou et al., 2018). However, these algorithms are not directly applicable to solve the problem (P"), as the function (xx) involves a special maximization structure and hence its specific function form as well as the gradient v and Hessian 4 are not available in practice. Instead, our algorithm design can only leverage information of the bi bi-variate function f.
Next, present some important properties regarding the gradient and Jacobian matrices of the functions f(x y) and (x). Throughout, we denote k = L1/ μ as the condition number. Proposition Let Assumption hold. Then, the following statements hold.
1. Mapping y" (xx) is k-Lipschitz continuous;
2. Function & (x) L1 + re)-smotth and ( Vif(z.
Define G(z,y) = (nff(z 3) V12f(x, voe V2if(z Then, G is a Lipschitz mapping with constant T.g (1 x)) Le., [G(z G(x, w)ll S Tall(x' "ell(d'.')) yy) (5r v)
4

---

Under review as a conference paper at ICLR 2022
4. The Hessian of 4 satisfies (2) = G(z, y (z)), which is Lipschitz continuous with constant L = LG + k))
The first two items characterize the gradient of the envelope function & in terms of the partial gradient of the bi-variate objective function f. They are proved in the previous work (Lin et al., 2020) and we include them for completeness. On the other hand, the last two items further characterize the Hessian of + in terms of the block Jacobian matrices of f. As we present in the next section, the Lipschitz continuous Hessian 42 (z) allows us to develop cubie-regularizzaton- based algorithm for finding second-order stationary points. We also note that the proof of items 3 & 4 are not trivial. Specifically, we need to first develop bounds for the spectrum norm of the block Jacobian matrices in Lemma (see the first page of the appendix), which helps prove the Lipschitz continuity of the G mapping in item Moreover, we leverage the optimality condition of fa. to derive an expression for the maximizer mapping y (x: (see (15) in the appendix), which is used to further prove item 4.
CUBIC-GDA: CUBIC-REGULAN
GRADIENT DESCENT-ASCENT
In this section, we propose new Gradient Descent-Ascent (GDA) algorithm that leverages the cubic regularization technique (Nesterov and Polyak, 2006) to escape strict saddle points and find second-order stationary points of the nonconvex minimax problem (P).
Our algorithm design is inspired by the conventional cubic regularization algorithm (Nesterov and Polyak, 2006). Specifically, find second-order stationary point of the envelope function ((z), the conventional cubic regularization algorithm would perform the following iterative update.
T++1 E arggmin min V ((x 2.)) [ xx)
1
Nt 11
(1)
61
where The is proper learning rate. However, due the special maximization structure of Q. its gradient and Hessian have complex formulas (see Proposition 1) that involve the mapping y" (z), which cannot be computed exactly in practice. Hence, we aim develop a new algorithm to efficiently compute approximations of the gradient and Hessian of & and use them to perform the cubic regularization update.
To perform the cubic regularization update in eq. (1), we need to compute ( = (if of (xx))
and (x,) = G( y (xx)) (by Proposition 1), both of which depend on the maximizer y (xt) of the function f ( -). Since f(x,,) is strongly-concave we can run N, iterations of gradient ascent to obtain an approximated maximizer UN, Re y² (xz), and then approximate ( (*)( using (If (N,) and G(z,, VN.), ), respectively. Intuitively, these good approximations due to two reasons: (i) UN. converges to y (xx)) at a fast linear convergence rate; and (ii) both V1 and G are shown in Proposition
be Lipschitz continuous in their second argument, We refer to this algorithm as Regularied Gradient Descent-Ascent (Cubic-GDa) and summarize its update rule in Algorithm below.
Algorithm 1 Cubic-Regularizz Gradient Descent- Slubic-GDA
Input: Initialize Ho. yo and learning rates 722 Tly- for t == 0, 1, 1,2.....
do
Initialize f/ Vt-
for 1 =
N₂ - do
Mk+11 V/ My 22 Vk).
end
Set M1+1 UN, and compute G( yt+1)))+))))))))) ) as follows:
((z1)) VuI( M141) V12f (tte)
M141).
Lt+1 E arg min, V Vif(a,, M1+1) (x xx) ) + {x G( - Ix) +
L bmy.
|| 1|3.
end Output: Fr.
We further comment on the implementation of Cubic-GDA. We note that the Cubic- updates in Algorithm 1 can be implemented in computation efficient way. First, note that Cubic-GDA involves
5

---

Under review as a conference paper at ICLR 2022
an inner loop that performs gradient ascent updates. To guarantee the convergence of the algorithm, prove in the next section that the number of inner iterations N, only needs to be kept at logarithm scale. Therefore, a few number of inner iterations suffice guarantee convergence in practice. Second, the cubic regularization sub-problem can be efficiently solved by the gradient descent algorithm (Carmon and Duchi, 2016), and it involves computation of only Jacobian-vector product that can be efficiently computed by the existing machine learning platforms such as TensorFlow (Abadi et al., 2015) and PyTorch (Paszke et al., 2019). In particular, to compute the feesiinnvvector product (zz, y)v for any vector v, one needs to compute the Iacobian-vector product In (z. y)u and the matrix-vector 221ff( VV (ar y)e. We note that this meatrix-vector product term can be computed as follows: first compute the lacobian-vector product b 22 (at, y)æ; Then, solve the invertible linear system /22 y)u b using any standard solver (e.g., conjugate gradient method), which involves iteratively computing Jacobian-vector products 2 y) for some vector w; Finally, compute the Jacobian- vector product V (z, y)u. Hence, one can call multiple Jacobian-vecte product oracles to solve the cubic regularization sub-problem.
product V12f (z. 22 y)
4 GLOBAL CONVERGENCE PROPERTIES OF CUBIC-GDA
In this section, we study the global convergence properties of Cubic-GDA Importantly, our analysis based on characterizing an intrinsic potential function of the Cubie-GDA algorithm nonconvex minimax optimization.
Recall that our goal is to find a second-order stationary point of the function ((x). Our next result shows that Cubic-GDA admits an intrinsic potential function that monotonically decreases in the optimization process. The proof of is included in Appendix B. Proposition 2. Let Assumption I hold. Define the following (iteittil
H(x, a(xr, y) := (xx) + Lz2n || - x=|1 + +T22lly y (x:)]]
and denote He == HI1,, It- Vl+1). Choose N₂ 2 max(In 2. In(L, lI Vaf (e) (L/())) 21 ||ا,- II)
In[ee/( (n(x:((==1)
and learning rates 7h S 28 Fl S ity. Then, the sequences (x1, yehe generated by Cubic-GDa satisfy. for all 0, 1,2...
He-1 S H₂ I22n21 11041 xells- L22 12111e111 -y (2:))1
(2)
Consequently, it holds that
lim |1e+1 10:1--00 ==ll=00.
0, lim || - 1oll = 0,
lim 11ye (xx)) 0. 80000
Remark 1. We note that the above key result can also be established for an inexact version of Cubic- GDA, which formulates the cubic subproblem with a general inexact gradient pt (1 and inexact Jacobian P. se G( Mt41) that satisfy the conditions
llp, - Vif(E,, Be+1)ll S O(| -
IP, - G(I,, 1)ll S O(1 - xell)-
These inexactness conditions are widely studied in the existing literature Cartis et al. (201 (b;a)) Under these inexact conditions, our proof of the above proposition remains unchanged, except that the coefficients of the term || - =xll would be slightly different.
Proposition reveals that Cubic-GDA admits an intrinsic potential function H, which is the objective function (x:) regularized by two cubic terms ||a² - 2=133 lly y" (a)) | Such potential function is closely connected to the optimization goal. Specifically, consider a desired case where 2, converges certain second-order stationary point x² and yo converges y (x=), it is clear that the potential function He would converge to the corresponding function value 4(x*). Hence, minimizing the function equivalent to minimizing the potential function H. More importantly, Proposition shows that this potential function is monotonically decreasing along the optimization path of Cubic- GDA, implying that the algorithm continuously makes optimization progress. By leveraging this property of the potential function, we are able to show that the parameter sequences generated by Cubie-GDA are asymptotically stable, i.e., I++1 It + 0, yt + y" (x+).
Remark 2. In each outer iteration t. set the total number of inner gradient ascent iterations N₂ based on ff yi)ll and 1|, 2z 0.1 Note that both of these two quantities can be easily computed right after iteration

---

Under review as a conference paper at ICLR 2022
Based on Proposition 2, are able to prove the convergence of {2:}e to certain second- stationary point, which we formally present in the next theorem. The proof is included in Appendix C.
Theorem (Global convergence). Under the same conditions as those of Proposition 2, the Cubic-
GDA has the following global convergence properties.
The function value sequence {d(Iz)} converges a finite limit H* -0;;
2. The generated sequences {aetee te are bounded and have compact sets limil points.
3. Every limit point x² of {oitt is second-order stationary point of t. i.e. VD(x*) 0, V²Φ(x") = O, and satisfies ((x") = H"
The above theorem establishes the global convergence properties of Cubic-GDA. Specifically, item 1 shows that the function value sequence { (2;x))) converges to finite limit H', which is also the limit of the potential function sequence {He)e. Moreover, items 2 & further show that all the limit points of {#+); are second-order stationary points of the minimax problem, at which the function & achieves the constant value H² These results show that Cubic-GDA guaranteed find second-order stationary points in nonconvex minimax optimization.
By further leveraging the potential function characterized Proposition 2, we obtain the following global convergence rate of Cubic-GDA to second-order stationary point. The proof is included in Appendix D. Throughout, we adopt the following standard measure second-order stationary introduced in (Nesterov and Polyak, 2006).
u(x) max {
(+)
-Amin (22
(V 1/(2n)) + 5L 4L3x2/L 1/(21t) + 4L3x2 L/1
Intuitively, a smaller p(z) means that the point x is closer to being second-order stationary.
Theorem (Global convergence rate). Under the same conditions as those of Proposition 2, the Cubic-GDA converges at the following rate for all T 2 Ho-inf ((z)
L2x
Hu inf uRR F(x) 1/3
min OSIST-1
TL2
The above theorem shows that the first-order stationary measure V ( converges at a sublinear rate O(T ). and the second-order stationary measure -Amin
<<)(r) converges at sublinear
rate OT ). Both results match the convergence rates the cubic regularization algorithm for nonconvex minimization (Nesterov and Polyak, 2006). Therefore, by leveraging the curvature of the approximated Hessian matrix G( 3t+1), Cubic-GDA able to escape strict saddle points of d at a fast rate.
We note that the proof of the global convergence results in Theorems and are critically based on the intrinsic potential function H that characterized in Proposition 2. We elaborate our technical contribution as follows.
First, to identify the potential function, we need characterize the per-iteration progress induced by the cubic regularization step. However, the cubic subproblem in Cubic-GDA is constructed by inexact gradient V Vif(zz, Bt+1) and Hessian matrix G( M++1). Therefore, need to properly choose the number of inner gradient ascent iterations N; to control the estimation error of both the gradient and Hessian approximations at desired level.
Due to the inexactness of the gradient and Hessian matrix, the cubic regularization update of Cubic-GDA does not lead to monotonically decreasing function value ((xx), as opposed to the original cubic regularization algorithm nonconvex minimization (which exact gradient and Hessian). Hence, we construct and identify a decreasing potential function H instead.
5 CONVERGENCE ANALYSIS UNDER LOCAL NONCONVEX GEOMETRY
The (2) of Proposition 2 shows that Cubic-GDD GDA has a special optimization dynamics and therefore its convergence rate is expected to be different from that of the vanilla GDA in nonconvex minimax

---

Under review as a conference paper at ICLR 2022
optimization. In this section, we explore the convergence rates of Cubic-GDA under broad spectrum of local nonconvex geometries characterized by the Lojasiewicz gradient inequality.
We first introduce the Lojasiewicz gradient geometry of function h. Throughout, the point-to-set distance is denoted as dista (2) == inf -
Definition 1. A differentiable function is said to satisfy the Lojasiewicz gradient geometry if for every compact set St of critical points on which h takes constant value ha E R. there exist e, X > O such that for all x E {= E R. distn(=) < E, ha < h(z)) < ha + }}. the following condition holds.
M(x) hn S VV(()))"
where e is a universal constant and E (1, +00) is the geometry parameter.
Intuitively, the Lojasiewiez gradient geometry is praddent-dominant--ie
geometry that characterizes
the local geometry of a nonconvex function around the set of critical points. In particular, it generalizes the Dolyak-t.ojsseeiiz (PL) geometry that corresponds to the special case 0 = 2 Lojasiewicz (1963); Karimi et al. (2016). In fact, a generalized version of the Lojasiewicz gradient geometry has been shown to hold for a large class of functions including aub-analytic functions, exponential functions and almi-algebraic functions, which cover most of the nonconvex functions encountered in machine learning applications (Zhou et al., 2016; Yue et al., 2019; Zhou and Liang, 2017: Zhou et al., 2018). For example, consider the class of robust machine learning problems that involve the minimax problem ming max;, ( y:)² - 3 Ilk: - a.ll?. Here (zi, y:) is the i-th data sample that includes, e.g., an image I; and its label Vı. & denotes the adversarial image, he a classification model parameterized by 8, and l denotes the loss function. Such a problem is when À is large. In particular, as elaborated in the appendix of (Bolte et al., 2014), the envelop function ((x) == maxg, - ((,o yz)2 L|E - aill? satisfies the local Lojasiewicz gradient geometry if it is semi-algebraic, which holds if every sample loss f(0, == (E)) y:)² I|l. a.l 12 is semi-algebraic.
nonconvex- nonconvex-stongly-eee stongly-concan
By (2) of Proposition 2 and (30) (proved in Appendix E), show that the potential function H of Cubic-GDA satisfies the following special optimization dynamics.
H++1 H; S -[ - -xell3 =)2
(4)
| S ( - x1-1 + 11 - It 211)
(5)
The above dynamics of Cubic-GDA involves higher-orde terms than the dynamics of GDA, which takes the form H++1 - H, < -0[]2+++ - 12 12) and |/ S 0[1 zxll) (Chen et al., 2021). Thus, it is expected that Cubic-GDA achieves faster convergence rate than GDA. On the other hand, compare with the dynamics of the cubic regularization algorithm (Zhou et al., 201 8), the gradient
dynamic of Cubic-Gii -DDi in (5) involves an additional term | - -1-21l Il2 that depends on the history, which is due to the inexact gradient and Hessian used in the cubic regularization step.
With the optimization dynamics in (4) and (5) and by leveraging the Lojasiewicz gradient geometry, are able to prove the following strengthened convergence result of Cubic-GDA.
Theorem 3. Let Assumption hold and assume that the potential function H satisfies the local Lojasiewiez gradient geometry. Choose the hyperparameters N2, The Ny in the same way as Proposi- tion 2. Then, the sequences {(T,, Wt) generated by Cubic-GDA have a unique limit point, which is a second-order stationary point of Q.
Recall that Theorem only proves that every limit point of {axa] is a second-order stationary point of the minimax problem. Theorem 3 further strengthens Theorem 1 by showing that Cubic-GDA converges to a unique second-order stationary limit point under the Lojasiewiez gradient geometry.
Next, we further study the asymptotic convergence rates of Cubic-GDA under different parameter ranges of the Lojasiewicz gradient geometry. We first obtain the following function value convergence rate result, which strengthens the convergence rate result established in Theorem 2. Throughout, to denotes a sufficiently large positive integer and Co is a universal positive constant defined as
2413
4T2
Co = 1/0 L. 2/3 (1012*+
2/3
L +
2m
The proof is included in Appendix F.
8

---

Under review as a conference paper at ICLR 2022
Theorem 4 (Funtion value convergence rate). Under the same conditions those of Theorem 3, the sequence of potential function {Hi) converges to the limit H at the following rates.
1. If the geometry parameter 0 (2,00) 20), then H, 4 HH super-linearly
H, H' S 0 exp (-
20
1010
vA to:
(6)
2. If the geomelry parameter 0 then He 4 H" linearly as
H. H* S (1 + )
11 loi
3. If the geometry parameter 0 (1, 2). then He HH sub- sub-linearly as
- S <0((t to) 3-20
Vt to-
(8)
Remark 3. We note that if the Lojasiewicz gradient geometry holds globally, then the above asymp- totic convergence rates become global convergence rates.
The above theorem characterizes the convergence rates of the potential function of Cubic-GID in the full spectrum of f of the local Lojasiewicz gradient geometry. Specifically, it shows that a larger implies that the local geometry is sharper and hence leads to a faster convergence rate. In particular, as we summarize Table in the introduction section, the convergence rate of Cubic-GDA is orderwise faster than that of the vanilla GDA for wide range of the parameter of the Eojasiewicz gradient geometry. This demonstrates the advantage of leveraging higher-order information in nonconvex minimax-optimizzate
As a byproduct, we also obtain the following asymptotic convergence rates the parameter se- quences generated by Cubic-GDA under the Lojasiewicz gradient geometry. The proof is included in Appendix G.
Theorem 5 (Parameter convergence rate). Under the same conditions as those of Theorem 3, the sequences {xt, Ve generated by Cubic-GDA converge to their limits x² -y (x") respectively at the following rates.
1. If the geometry parameter 0 E ( oo). then (It, H+) + (x" "," (x*)) super-linearly as
max (1|=) - =²Il. ll, 11
v" (x")11 s 0 exp 3 3
20
A4 2 to:
(9)
If the geometry parameter 2 then (It, y1) + (x", yy (x*) linearly as
3
max {11 x" 11, llve 1 (x" |lI} - o (11 + 0 1
Vt 2 to:
(10)
If the geometry parameter (1, 3) then (Ir, v/) + (z" ,y"v"" (xx)) sub-linearly as
- --1-x*11= ((t 4-=+ 11 (I:)) - o ( 31--20
Vt 2 to (11)
can be seen that, similar to the convergence rate results of the function value sequence, the convergence rate of the parameter sequence is also affected by the parameterization of the local geometry.
CONCLUSION
In this paper, we take one step further toward improving the convergence guarantee GDA-type algorithms in nonconvex minimax optimization. We develop Cubic-GDA algorithm that leverages the second-order information and the cubic regularization technique to effectively escape striet saddle points in nonconvex minimax optimization. Our key observation is that Cubic-GDA has intrinsic potential function that monotonically decreases in the optimization process, and this leads to guaranteed global convergence of the algorithm. Moreover, our convergence analysis shows that Cubic-GDA achieves a faster convergence rate than the standard GDA for a wide spectrum of gradient dominant-tyy type nonconvex geometries. In the future study, will develop stochastic variants of Cubie-GDa to further improve its computation efficiency. Another interesting direction is to apply momentum techniques to further accelerate the convergence of this algorithm.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving. G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, Vanhoucke, V., Vasudevan, V., Viégas, F,, Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng. X. (2015). TensorFlow: Large-scale machine learning on heterogeneous systems. Software available from tensorflow.org.
Adolphs, L.,, Daneshmand, H., Lucchi, A., and Hofmann, T. (2019). Local saddle point optimization: A curvature exploitation approach. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 486-495.
Agarwal, N., Allen- Z., Bullins, B., Hazan, E., and Ma, T. (2017). Finding approximate local minima faster than gradient descent. In Proc. Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1195-1199.
Bolte, J., Sabach, S., and Teboulle, M. (2014). Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, (46(1-2):459-444
Carmon, Y. and Duchi, J. C. (2016), Gradient descent efficiently finds the cubic-regularized non- convex Newton step. ArXiv: /6/2.00547.
Cartis, C., Gould, N. I. M., and Toint, (2011a). Adaptive cubic regularization methods for unconstrained optimization. part ii: worst-case function- and derivative-evaluation complexity. Mathematical Programming. 130(2):295-319,
Cartis, C., Gould, N. I. M., and Toint, P. L. (201 (2011b). Adaptive cubic regularization methods for unconstrained optimization, part i: motivation, convergence and numerical results. Mathematical Programming.
Chen, Z., Zhou, Y., Xu, T., and Liang, Y. (2021). Proximal gradient descent-ascent: Variable convergence under kl geometry. Proc. International Conference on Learning Representations (ICLR).
Cherukuri, A., Gharesifard, B., and Cortes, J. (2017). Saddle-point dynamics: conditions for asymptotic stability of saddle points. SIAM Journal on Control and Optimization, 55(1):486-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.
Dauphin, Y. N., Pascanu, R., Gulcehre, C.,, Cho, K., Ganguli, S., and Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Proc. Advances in Neural Information Processing Systems (NeurIPS), page 2933-2941.
Du, S. 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, J. A., and Coelho, M. P. (2012). Minimax theorem and nash equilibrium. International Journal of Latest Trends in Finance & Economic Sciences.
Ge, R., Huang, F., Jin, C., and Yuan, Y. (2015). Escaping from saddle points online stochastic gra- dient for tensor decomposition. Proc. 28th Conference on Learning Theory (COLT), volume 40, pages 797-842.
Ghadimi, S., Liu, H., and Zhang, Т. (2017). Second-order methods with cubic regularization under inexact information. ArXiv: 1710.05782.
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 Neural Information Processing Systems (NeurIPS), pages 2672-2680.
10

---

Under review as a conference paper at ICLR 2022
Griewank, A. (1981). The modification of newton's method for unconstrained optimization by bounding cubic terms. Technical Report.
Hallak, N. and Teboulle, M. (2020). Finding second-order stationary points in constrained min- imization: A feasible direction approach. Journal of Optimization Theory and Applications. 186(2):480-505
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 minimax optimization. ArXi::2008.08170
Jiang, B., Lin, T., and Zhang, (2017). A unified scheme to accelerate adaptive cubic regularization and gradient methods for convex optimization. ArXIv:1710.04788.
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. (2017). How escape saddle points efficiently, In Proc. International Conference on Machine Learning (ICML), volume 70, pages 1724-1732.
Jin, C., Netrapalli, P., and Jordan, I. (2020). What local optimality in nonconvex-nonconcea minimax optimization? In Proc. International Conference on Machine Learning (ICML).
Karimi, H., Nutini, J., and Schmidt, M. (2016). Linear convergence of gradient and proximal-gradien methods under the bolyak-lojasiewicz condition. Machine Learning and Knowledge Discovery in Databases: European Conference, pages 795-811.
Kohler, M. and Lucchi, A. (2017). Sub-sampled cubic regularization for non-convex optimization. In Proc. International Conference Machine Learning (ICML), volume 70, pages 1895-1904.
Lin, T., Jin, C., and Jordan, M. (2020). On gradient descent ascent for nonconvex-concave minimax problems, In Proc. International Conference on Machine Learning (ICML).
Liu, M. and Yang, T. (2017). On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization. ArXiv:1709.08571v2.
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 Signal Processing.
Luo, L. and Chen, C. (2021). Finding second-order stationary point for noncomver-strongyy-cooaae minimax problem. 10.444441.
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 Statistics (AISTATS), pages 1497-1507.
Nedić, A. and Ozdaglar, A. (2009). Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142(())205-228.
Nesterov, Y. (2008). Accelerating the cubic regularization of newton's method on convex problems. Mathematical Programming, 112(1):159-18)
Nesterov, Y. and Polyak, B. (2006). Cubic regularization of newton's method and its global perfor- mance. Mathematical Programming.
Neumann, J. (1928). Zur theorie der gesellschaftsspele. Mathematische annalen, 100(1):295-320.
Nouiehed, M., Sanjabi, M., Huang, T... Lee, J. D., and Razaviyayn, M. (2019). Solving class of non-convex min-max games using iterative first order methods. Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 14934-14942.
11

---

Under review as a conference paper at ICLR 2022
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang. E., Vitoo, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. (2019). Pytorch: An imperative style, high- performance deep learning library. In Proc. Advances in Neural Information Processing Systems (Neurips), pages
Qiu, S., Yang, Z., Wei, X., Ye, J., and Wang, Z. (2020). Simgle-timescale stochastic nonconvex- concave optimization for smooth nonlinear td learning. ArXiv:2008.1010
Robinson, J. (1951). An iterative method of solving game. Annals of mathematics, 54(2):29-331.
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 in Neural Information Processing Systems (NeurIPS), pages 7461- 7472.
Wang. 7.,, Zhou, Y., Liang. Y., and Lan, G. (2018). Sample Complexity of Stochastic Variance- Reduced Cubic Regularization for Nonconvex Optimization. ArXtv:1802.00372211
Xie, G., Luo, L., Lian, Y., and Zhang, Z. (2020). Lower complexity bounds for finite-sum convex- concave minimax optimization problems. In Proc. International Conference on Machine Learning (ICML).
Xu, P., Roosta, F., and Mahoney, M. W. (2020a). Newton type methods for non-convex optimization under inexact hessian information. Mathematical Programming, 184(1):35-70. 30.
Xu, T., Wang, Z., Liang, Y., and Poor, H. V. (2020b). Enhanced first and zeroth order variance reduced algorithms for min-max optimization. A7X:v.2000..9361.
Xu, T., Wang, Z., Liang, Y., and Poor, H. V. (2020c). Gradient free minimax optimization: Variance reduction and faster convergence. ArXiv:2006.09361.
Xu, Z., Zhang, H., Xu, Y. and Lan, G. (2020d). A unified single-loop alternating gradient projection algorithm for nonconvex-concat and nononxce minimax problems. 02200:2000.02032.
Yang. J., Kiyavash, N., and He, N. (2020). Global convergence and variance reduction for a class of nonconvex-nonconean minimax problems. In Proc. Advances in Neural Information Processing Systems (NeurIPS).
Yue, M.-C., Zhou, Z., and Man-Cho So, A. (2019). On the quadratic convergence of the cubic regularization method under a local error bound condition. SIAM Journal on Optimization, 29(1)990-9332.
Zhang, and Wang, Y. (2021). On the suboptimality of negative momentum for minimax optimiza- tion. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2098-2106.
Zhou, Y. and Liang, Y. (2017). Characterization Gradient Dominance and Regularity Conditions for Neural Networks. In Neurips Optimization for Machine Learning Workshop.
Zhou, Y. and Liang, Y. (2018). Critical points of linear neural networks: Analytical forms and landscape properties. In Proc. International Conference on Learning Representations (ICLR).
Zhou, Y., Wang, Z., and Liang, Y. (2018). Convergence of cubic regularization for nonconvex optimization under kl property. In Proc. Advances Neural Information Processing Systems (NeurIPS), pages 3769.
Zhou, Y., Zhang. H., and Liang, Y. (2016). Geometrical properties and accelerated gradient solvers of non-convex phase retrieval. Proc. Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 331-335.
12

---

Under review as a conference paper at ICLR 2022
Appendix
Table of Contents
A Proof of Proposition 1
13
B Proof of Proposition 2
14
C Proof of Theorem 1
16
Proof Theorem
E Proof of Theorem 3
18
F Proof of Theorem 4
20
Proof Theorem
In this supplementary material, present the proof of all the results claimed in the paper. We first prove the following auxiliary lemma that bounds the spectral norm the Jacobian matrices.
Lemma 1.
Let Assumption hold. Then, for any R and y E R", the Jacobian matrices of f(z v) satisfy the following bounds.
(x,
(12)
12 = 22, v) SL
(13)
Proof. We first prove eq. (12). Consider any x E Ih and y R2.. By Assumption we know that fxx is j-strongy concave, which implies that - 22 (x. 2 ul. Thus, we further conclude that
[Z 1| Xmax (1-V22/ (x,
[Aiin (2,l(z, S =t
Next, we prove eq. (13). Consider any x, R and y E R", we have
221 y)
V 2 (r tu, v) |-al
0t
lim
V2f(x (u,y) 225 v)]
lim
V2f(xx + tu, 22f v)
L1
lim
|u|l||
= L1 |//1|
(14)
80
[6|
which implies that f v)1l < L, Since f is twice differentiable and has continuous second- order derivative, we have V12/(r, (22
= 221 fa.f(e (ar, y), and hence eq. (13) follows.
A PROOF OF PROPOSITION
Proposition Let Assumption hold. Then, the following statements hold.
1. Mapping y" (x)) is k-Lipschitz continuous;
Function & (xx L1 + km)-mmothh and V Vif(z.v"<z)
Define G(z,y) = Vnf((z 3) V12f(x, (22 v). Then, G is a Lipschitz
mapping with constant T.g [1 x))2 ie, [ 1/) G(z, v)ll Tol((x', y') (x.y))l:
13

---

Under review as a conference paper at ICLR 2022
4. The Hessian of 2 satisfies (x) G(z, y" (x)), which is Lipschitz continuous with constant L = LG + +) L2(1 x)).
Proof. The items & 2 are proved in Chen et al. (2021); Lin et al. (2020).
We first prove the item 3. Consider any v, Rd and y, y' R For convenience denote
2 = (z, v) and z' = (x', 3²). Then, by Assumption and using the bounds of Lemma 1, we have that
|[G(', 3/) - G(,,
- 1 Va
+1V2://e///lll22///0001111111111 - 221f(z
+L ( v'dl''l y)1 11f "L2ll =|l)
2|| - < L2(1 + 26]]|2/
L1# (L2112'- - =11)a=
& [2 + =)]||='- =
Next, we prove the item 4. Consider any fixed x E I we know that f(x, .) achieves its maximum y" (I), where the gradient vanishes, i.c., (2f (x)) = 0. Thus, further obtain that
0 V2 V + 22f((, (z))
which implies that
Vy (x)
-VV V2,
(15)
With the above equation, we take derivative of v -
Vif(z, (x)) and obtain that
(²)(2) =v Vuff(z, (inff///(())++=
hall::ahhhh-oooooo/o//////aaaoaa -G(zzy'()),
(16)
Moreover, we have that
||'2 - ( (()] =| ((x)))((r
G(x,)"(=))
LG |||e - I|| + 11=((x²)~
LLa(1 + x))l - ==1,
(17)
where the last step uses the item 1. This proves the item 4.
B PROOF OF PROPOSITION 2
Proposition 2. Let Assumption / hold. Define the following potential function
H(z, a''''' y) (xx) L |12 z11 4L y" (x)
and denote H. = H( I1 1.411..... Choose N, > max(In 2, In[4, (a.lL///VV/aa.g.gl////...l (/tll//...))l/(()/))) 2lu ||ا ||)
In(x/((-1)
2 and learning rates 77 Σ 28L2E3 Fl I L+m Then, the sequences (r,. Vele generated by Cubic- GDA satisfy, for all = 0, 0,1,
H S H L2n xel|s-La Lz 11tt1 -3- (3
(2)
Consequently, it holds that
lim || - xell = 0, 1000
lim || - will O, lim |1 3 (xx)) = 0. 1-000
10000
14

---

Under review as a conference paper at ICLR 2022
Proof. We first bound the term l1 - (2x))l which corresponds the optimality gap of the maximization problem. Note that (xx) E R" is the unique maximizer of the strongly concave function f y). Note that +++1 is obtained by applying N₂ gradient ascent steps starting from yr- Hence, By the convergence rate of gradient ascent algorithm under strong concavity, we conclude that with learning rate fly LtF'
l1 - (x=e)l S(1 -1
1 11ye
(xxe)l
(18)
La | x112
(19)
where the second inequality uses the hyperparameter choice
N₂ 2 Dt) (T)21/ In l x1-1ll In[Lillv: - (0()))))/ - 21n ||,, - x2-1ll
In(n/(n= (0)x--11) 1)]
In In/n/(n= 1)]
(2 u+)l = [2 vt) (2f 1/ (1+)))l 2 mllye v" (xx))l Moreover, eq. (18) and
the hyperparameter choice that No 2 In(e/((<-1) 1)] imply that
lu2
Ilue+2 y" (12+1))l
<(1 k 1- Ilye+1 1/ (12+1))1
a + b
33 | y² (xxx))
|
(20)
2
where (i) denotes that := M6+1 y" (x.), b: (xx) y (I++1). 1, (ii) applies Jensen's 's inequality to the convex function || ||
Based Theorem 10 and Proposition of Nesterov and Polyak (2006), know that
Amin [G( U6+1]] 2 2n
|| - xzll-
(21)
Since 1e+1 minimizes the following cubic sub-problem
1 o (x G. M41) xz) + ||x - xell
Ircss (I) == V (f 11+1) T (x - xx) +
61/z
we obtain the following optimality condition
Vif(Ee Me+1) + G(z,, (1+1) - -xa) + | xx1((x141 xx) =0 (22)
211x
Next, by the Lipschitz Hessian of 4, we obtain that ((F+41) ((x))
$ (v)(x,)- Vi ve+1)) (Ir+1 - xx) +
1 [B(t1) - xx,) TV'((((( - G( Vo+ v1+1)) - xx)
1
Lo
Vif( M++1) (1e+1 - xx) + 2 [+++1 - 21) xz)) GG(e, (11 - xz) +
||++11 - xeel
6
(
2 Li |lvet1 y y"(xx)lll=e++ 21|1+ LG || - 1ell 3² (xxx)l
(11+1 TG(z,, (1) -xt) + (L1
La 1
2
|1 - =x
2n
(10
2/
L
11 - y" (x:) +
| - x3 1|a
3L2
1/2 ka/2
k2/2
3
LG
2k
1
|2141
xzll3 3 +
11
(zx (x:)))13
2
3x²
1
L$
1
||
sell3
+
| - 22
(23)
4m
6
2n
15

---

Under review as a conference paper at ICLR 2022
(18)
2L2 3x3/22
2L2 22-111 10-1-1111 3
1 y (xx))l + (3L2x² | - zrl1
22
(24)
4n
where (i) uses Assumption 1, the item 4 of Proposition and eq. (22), (ii) uses eq. (21) and
the inequality that ab (CC)))*(
I (Ca) + 30 for any a, b 2 0 and
C' > 0 (based on AM-GM inequality), (ii) uses eq. (19) and LG L2(1 x)² 4L2x2
Le = L2 + x) & 8L2x².
Multiplying eq. (20) with 4Lg and adding it to eq. (24) yield that
$ (xx++1) @ (x²) + 4L 11 - y" (1=+1))l
$ 2L2
|108 xt-1ll 1|3 8L2
|1+41 y" (2+)]l + (5L2 1 | x,11
3/3/2
4m/0
(0)
$ L2k 21 - x 13 + 3L2 M1+1 y (at)) -2 1 - zel1"
where (i) uses the condition that 1/2 I 23 The above inequality implies eq. (2) by defining
H₃ == (xx)) + 1 z1-1| 31 + 4 002l/1++111 Yt+1 y l
Next, summing eq. (2) over 0, 1..,, ..., T 1, we obtain that for all T 2
T-1
L2n
|1++] 11113 L2
11 - (2xx))
0=
1=0
$ Ho
HT < Ho - ((TT) s Ho
inf (xx) < toc. FE
(25)
Letting T > yields that Ee |,++1 || +o0 and Et= |t++ y² (xx))l < +00, so
lom || xea == lim | - y (.x) = 0. Hence, 1 - y (xt)] S 11 -y"
llv (1re - (0(x+11)l - 0 using continuity of y", and ||M+1 - yell I || - (xx)) 11
y² (z:)]l 4 0.
C PROOF OF THEOREM
Theorem (Global convergence). Under the same conditions as those of Proposition 2, the Cubic-
GDA has the following global convergence properties.
1. The function value sequence {D(xz)} converges to finite limit H* > -00;
2. The generated sequences {weete { are bounded and have compact sets of limit points.
Every limit point x² of {aett is a second-order stationary point of L i.e. Vx(x") = O. Vxx(x") 0, and satisfies 4(x*) = H*
Proof. We first prove item 1. We have shown in Proposition 2 that {H+) is monotonically decreasing.
Also, Assumption 1 says that H, 2 (xx)) 2 in.. (xx) > -cc Therefore, we conclude that {H,}. converges to a finite limit H* > 00. Since Proposition 2 proves that || Zz- ll. I1
y (xx) 4 0, we further conclude that (xx) 4 H which proves item 1.
Next, we prove item 2. Note that & has compact sub-level sets. Moreover, for all t, we have
(xxx) S H, < Ho < +00.
(26)
Hence, the sequence {æ, h is bounded and thus has a compact set of limit points. Since y is Lipschitz continuous by Proposition conclude that (ye J is also bounded and hence has compact set of limit points. This proves item 2.
(xx))) ) also bounded. Consequently, as 11yt-9' (x+)l + we
Next, we will prove item 3. Suppose that It, 4 x= along a certain sub-sequence { Ja- We have that Mtg+1 4 y (a*) based on Proposition 2 and the continuity of y². In addition, Proposition I implies that 4. V4, 2 and G are continuous. Therefore, for every limit point x",
((x") lim ((F+.) H
to 000
16

---

Under review as a conference paper at ICLR 2022
V+(=")|l
lim [D(Iza)) lim V V (I22)) lim VVf Ml++1)l )
lim 400
G( yoa 11,+1 Iet) +
| - Ue ( vea) =0
217ss
Amin
V2b((")]
lim Amia V (=D(1))))
lim Amin 1x-000
G (I(e))
lim Amin [G(Ttt M1y+
2
lim |1 Fzy 11 = 0
212
where uses eq. (22), and (ii) uses eq. (21).
D PROOF OF THEOREM
Theorem 2 (Global convergence rate). Under the same conditions as those of Proposition 2, the
Cubic-GDA converges at the the following rate for all T 2 Ho Ho-inf (xx)
L2k²73
Hu - inf ((x)
1/3
min 0StST
T /3
Before proving Theorem 2, we first prove the following auxiliary lemma.
Lemma 2. For any symmetric matrices A, B E Rexx, we have Dmiin (miin() Amin (B) S 1|A BI|
Proof of Lemma 2.
Amiia (A) - Amin (- (B)1
min v Au min u Bu |u|l==1
w:||a||=1
s max [u Au u Bul
u: =
max
([]u|II|A B|||u[]) I|AA BlI.
mi x||=1
Proof of Theorem 2. Note that (25) implies that
Ho -in F(x) TL2x3/3 /3
min 251ST-1
(1 xx/1 + ||ara 11-1|13|| || x1-2113)
which further implies that there exists
< 1' < such that
xe. x21 - Ho inf ERRm ((x) max (f|x0411 - Ir || - -zy-1ll [xp-1
( TL2x3 /3
1/3
(27)
On the other hand, equation (2.2) of Nesterov and Polyak (2006) implies that,
L | Ie- 11
[d(xx)= - v -a - zr -r-1))l -
Since V4(x) (z)( v<0(=) = G(z, y² (x)), the above inequality implies that [v
La
< |V (rr - xel1
| 11-111 1|?
2
|if((r-11 + G( Me (av - mr -1 + V (2 (xv-1)) - V.
zr 1Il + L
+ +I[(G(v-113' (Ie G( 1.
|| - 1112
2
( 1
5 27
|0e -e-1ll 11 L Liller - y (IV-1))l Lollue v (xv - - ze-1ll
Lo
+ 2
ai - IV-
17

---

Under review as a conference paper at ICLR 2022
(10
4L2n²
+ +422k
1101 z0-1112 +
+
120 -20-11?(|=0+
211
L1
(361)
Ho infrERm ((x))
2/3
4I3m²
Hn in $(x))
+ 5l2m2
+
27,
TL2k3 /3
L1
T L
1 /3
(10)
1
4L2x2 ( Ho - EnR ((x))
2/3
+ 5L2n3
(28)
2//
T1
TL2k3 /3
where (i) uses eq. (22), item of Assumption and item 3 of Proposition (ii) uses eq. (19)
and LG = [2
(1(1 + x)² I 4Lgk², La = L2(1 + x)) I 8L2x", ? (iii) uses (27), and (iv) uses
(x)) Also, note that T Ho inf, 13
Ami (V(((x))
Amin (G(zr, v1))) + (G(
(0)
| - ze Lal V² (xv))
2m,
(166)
| - -xvll LGh2
1, -vv-1ll
2//
I
(iv)
1
Ho innfeERm
((x))
1/3
Lat2 ( Ho inf RR {(x)) 2/3
+
27
TL2k3 /3
L1
TL2x3 /3
WV3
1
AL3x²
Hn
inf $(x)) 1/3
+
(29)
2T
L1
TL2x3/3
where (i) uses Lemma 2, (ii) uses eq. (21) and item 3 of Proposition 1, (iii) uses eq. (19), (iv) uses
eq. (27), and (v) uses T Ho ing-inf.rgm s.am ((x)) and Le L2(1 + x)² < 4Lgx2, Equations (28) & (29)
L2
imply Theorem
E PROOF OF THEOREM 3
Theorem 3. Let Assumption hold and assume that the potential function H satisfies the local Lojasiewicz gradient geometry. Choose the hyperparameters N,, Qas Ty in the same way as Proposi- tion 2. Then, the sequences {(I th generated by Cubic-GDa have unique limit point, which is a second-order stationary point of t.
Proof. We first derive bound on VV x1)1 := VE V v)l as follows.
V H (It, Tz- V1+1)
S V 11.
+ 3L2 Hz-
+ ||2 -
3 (2: - v
(
(Lr + +6 |1:0 xI--
Li
+
12T Me+ (1x))
122 (n)) -1ll) (x))
(1)
- ( GG xz-1) || + [G (x+ - 2z-1ll
La
+622
||:: x-11 12L (1 + μ L1) - (x:))1
2
v. V - - v.f(x-11.1))
| - Ft-111 - m-
2n
18

---

Under review as a conference paper at ICLR 2022
Lallye - (+ا-1)| je -z-1ll 11 + (Lr + 6L2x*) |1:0 1111-11-11f 24L2x - - (xx))l
Li
(10)
Lي S Lillye V (x(==11) + ( + 612r1 +
1
||0 - 121-112
21/21
Lah2 1 - -1--21 x2-1l1 +
24I22
+
1|0q - x1-111 1022-11111
L1
Li
(0)
Lz 11-1 - 22-2111 2 (10I2 +
1
|1:0 1212
2/70
4L3n²
24L3
-
-4-1
21-1 +
||
2112
(30)
L1
Li
where (i) uses eq. (2.2) of Nesterov and Polyak (2006), the fact that V is L Lo-Lipschitz, and eq.
(15), (ii) uses Lemma and (x) G(x,, y (x)) from item of Proposition 1, (iii) uses eq. (22), ( = (a, y (z)) from item 2 of Proposition I and the inequality that + K S 2k, (iv) and
(v) use eq. (19), and (v) uses LG = L2(1 + x)² < 4L2k², L. = L2 + x)² I 8L2
Next, we prove the convergence of the sequence { h under the assumption that (x, satisfies the Lojasiewicz gradient geometry. Recall that we have shown in the proof of Theorem that: I) {He) decreases monotonically to the finite limit 2) for any limit point x², yy of (1a) {ye)e.
((x") H" Hence, the Lojasiewicz gradient inequality (see Definition 1) holds after sufficiently large number of iterations, i.e., there exists t N+ such that for all t 2 ti, H H Fz-1, Bc+1) H* S
It-1 11)1) Equivalently,
(H HIIII (2 It- 11-1,,,01111 2c- 1)l1 2 1.
where we define the concave function that (p()) == 1-170 1/0 (0> 1,8 0)-
210
In addition, since ||,;, - - || 4 0 (Proposition 2), there exists t, E N+ such that for all t 2 fz. ||, zt-1 < Hence, rearranging the above inequality and utilizing eq. (30), obtain that for all / 2 40- = max((1, (2),
x (14 11")
2 VH It-1, 1t-1
21-211 + 21--11 + (10L2h²
24433R
1 1 |1 - 21 =111
+
+
(31)
L1
2n
By concavity of the function cp()) = 2/10
1-170 11/6 1,8 > 0), we know that
((H, - H²) (HH - H*)
('HH, -HH - -H*) - H++1)
L2x
Ie+1 1
11
(32)
413K"
h + +L2) [ | - 12-2 + 1102 + 241.3 + 2n
1.
||xe x1-1
(4)
L 11gh2111444 |5441 - 2/113
4L2x2 L.
- x1- - + -
+ 10L22 +
24 4
+ 2 ||,, xz-
where (i) uses Proposition 2 and eq. (31), (ii) uses the inequality that a² + - (a + b)² for any a, b 2 O.
Rearranging the above inequality yields that
L2 1 - 12
(H, (H) -H(+)11--1T) Hz)
4L3n2
24L3x 10L +
b1 + - - Iz-2/ +
+
1 111
1
2115
19

---

Under review as a conference paper at ICLR 2022
2
4T2gk2
1 - -H) - H
+ -2 22-2
27
C/
L1
24L3x 1062K' + CV
2
1
It xz- 11l
(33)
21/=
where the final step uses the AM-GM inequality that ab [VCC0///000/0]]] < 27 (C
2b/3 for any a, 2 0 and C > 0 (the value of C' will be assigned later). Taking cubic root of both obtain that
Ç
sides of the above inequality and telescoping it over to....; T
BV
L
a1+1 xell
too
C
2
4T2n2
5
(p(ll - 11) p(1T H]]]+
+
L2
x
xt-2
3
30
L1
t=to
24L3x
T-1
+
10L2x3 +
It Tt-1ll
30
Li
21/ t=to
0
2
AL3K²
<
- -H*) +
+ L2
|8--1 1 xz-21
3
3C
b
t=
24Lăx
T-1
+ 3C 10L2x3 +
I - zz-1ll
L
27
t=to
where the final step uses the facts that He H 2 0 and that pps) is monotonically in- creasing. Since the value of C 0 is arbitrary, can select large enough C such that
1LEx² L1
L2 2 V 100223 + 21L
Va Hence, the incquality above further im-
14 27
plies that
K
/2
T
- xzll S
C
(H - H²)
3
3
1=
K TT
[|
21o-2
21|T1, Sto-1ll to0.
(34)
3
Letting T + concludes that
Σ
|0 xz |||<
Moreover, this implies that (2r)) is Cauchy sequence and therefore converges certain limit, i.., 4 x²" We have shown in Theorem 1 that any such limit point must be second-order critical point of &. Hence, we conclude that {a+}: converges to a certain second-order critical point x of (xx). Also, note that I|v* (xxe) yell S 0, xr 4 x² and y² is Lipschitz mapping, we conclude that {ye J. converges to y" (z*). Finnlly, the item 3 of Theorem implies that x is a second-order critical point of (xx).
F PROOF OF THEOREM 4
Theorem 4 (Funtion value convergence rate). Under the same conditions those of Theorem 3, the sequence of potential function {Hi)) converges to the limit H" at the following rates.
1. If the geometry parameter 0 (3) 20). then He 1 H² super-linearly
H H" 20 exp - 20 )-(20)=0)
Vt 2 to:
(6)
20

---

Under review as a conference paper at ICLR 2022
2. If the geometry parameter 0 = then He 4 H" linearly
- S (1 _ Vt to:
3. If the geomelry parameter 0 E (1, then H, + H* sub-linearly as
H: - <(((ttt)) (t)
3-30 --)0
Vt 2 to.
(8)
Proof. Equation (31) implies that there exists lo N+ such that for any 1 2 lo.
4'( - 1-------- c10 11/////0
=
4L3n²
24L3N
+ L2)) - +
1102 +
+
| - xc-1/1
(35)
L1
L2
27
AL3
+ L2nx 7) (
- Hc-1 (Hi- 2/3
+ (10I2x +
24L
1
H1-1 - He
+
L1
L2
LG
21
L2
where (i) uses proposition 2.
Defining dt
H.
H
C1 =
c//0 1/2
2/3
(41.
+ T22x
C2
[I
L 2/3 (10L2x + the above inequality further becomes
2412 I.K. 2
and Co= 2/22/10 Lig 2/3
110 +
2413
422
I2
27
d/
(d dr-1) 2/3
+ (2 - 2/3
(36)
$2 ma C2)
2 (di-2- - -1-1)
+ )
2/3
(d.-1 - de) 2/37
2
2/3 (16)
< max C2)
1 (di2 di)
I Colde-2 de)2/3
(37)
where (i) applies Jensen's inequality to the concave function {(s) = 52/3, and (ii) uses the inequality that 2//3 max(C: (C1, C2) I Co.
Next, we prove the convergence rates case by case.
(Case 1) If E (g. +00), since d, 2 0, eq. (36) implies that for 2 la.
de d
which is equivalent to that
C 20-3 de < [C, 10-3 dr-2)
20/3
(38)
38 d, Se -1 for sufficiently large to E N Hence, eq. (38) implies that for any Since de + 0, C
k E N
38 C dok+to S(C00 deg
1120/3)41
20
S exp
Hence,
38
[-(20)
20
d2x++o+1 S d2x+to < Co
20-3
exp
Note that 0 E (2, +00) implies that 2/ > 1, and thus the inequality above implies that H, 4 H² at the super-linear linear rate given by eq. (6).
(Case 2) If 0 3. eq. (37) implies that for t 2 to.
de S (1 Go ) -
(39)
21

---

Under review as a conference paper at ICLR 2022
Note that dis I 1 for sufficiently large to Therefore, de 0 (i.e., ((x)) H²) at the linear rate given by eq. (7). (Case 3) 1 ),, consider the following two subcases.
If d2-2 S 2dh, denote (s)))
20
81
20, then for any 1 2 l0.
3-26
di-2
da- s 20 ds 2 2
(1) 2
(dde) 2))
- (s)dss
(de-2 de)
de
(1)
dj
20 (68)
2 Co
z (2Co)
(40)
dj
where (i) uses d, 1 d 2. and
- 2
0)
< 0, (ii) uses the following inequality implied by eq. (37),
and (iii) uses
de de-2 2
2 1 and
3
E (1. 2)
28
If di-2 2d,, then for any t 2 to.
v(d)) - 2)
20
(1g
(1--3) 20
dg
1-
2
20
[d--2 20
(2d,)²
20
2
3 28
20 (1 2
3
2
26
2 (2Co) -
(41)
3 20
20 1-22 1
20
where we use 1-3 3 E ( (- 1, 0),
29
and de S di s (200) 3-29
for
20
3-28
3-20
sufficiently large to N+
Since least one of eqs. (40)& & (41) holds, we have (dd) (dd 2 (2Co) -. Hence, ((22++o+11 2 (122 to) 2 (dh,)) + b(CCo) : z k2(C)) k E which implies that (ddb) 2 مهه (2Co)- By substituing the definition of eb, the inequality above implies that H(2) 1 H in a sub-linear rate given by eq. (8).
G PROOF OF THEOREM
Theorem 5 (Parameter convergence rate). Under the same conditions as those of Theorem 3, the ht
sequences { generated by Cubic-GDA converge to their limits x", yy (x*) respectively at the following rates.
1. If the geometry parameter 0 E (3, oo). then (xt, - (a", ,0" (x*)) super-linearly as
max (112,- x²1l llve y (x*)l) S 0 exp 3 3
1 1/20 20
))
Wt 2 to:
(9)
If the geometry parameter A == 3. 2. then (It, y10 + (x", yy" (x(x)) (x*)) linearly as
max f1 - x llve y (x" ||| s o ( (1 + 2/22 )
Vt V2 to:
(10)
3. If the geometry parameter O (1. 2) then (It, y1) + (z" y (x²)) sub- lub-linearly as
|1t- 00 to) 20-112 l1 (x:))l s 00 ((t-to) to) 3:3
Vt Vt to.
(11)
Proof. Notice that eq. (34) still holds after increasing to, i.e., for T 2 t 2 to and large enough C 2
such that
V
ALLxx²
+
Lz,
so / /102233 + 24
+ 2n
T 3
we have
3C
T.1
L
K T
2
T-1
Σ
||
2zll S
C2o1/0
(He H
3
3(1 - 1/0)
x Ln
+
||
x2-2|l + 2| - r--1l| < +00.
(42)
3
22

---

Under review as a conference paper at ICLR 2022
Proposition 2 implies that
(8)
|2 -t- 11 S L2
1/3 R
(H1-1 - 1/3
I L2
1 K- -Hi 1²11/3
(43)
where (i) uses H Hi H Therefore, for 2 to. eqs. (42) & (43) imply that
T-1
|| - x²1l 1 lim sup T-0
|10+1 - x.sll
s C²
(H. 11)1-10000 + [HH-2 H 2(H111 HM)2/8]
(44)
K L - 1/0)
Next, we discuss case by case.
(Case 1) lf ( +00), then
| x=1 (H1 - (H1-1 H3)1/3 (H, HT)1/31
(45)
50( cxp [ 1 (22)) (1-ta)/2-17)
3
where the two use eqs. (44) & (6) respectively. Hence,
1/ve y² (*+))
< 1/ y" (xx-1) + I1y" (2t-1) - (x+)l
(i) Le
| 22-2 xl| x1-1|
(46)
(HH-2
H' H²12/3 (Hz-1 H+)3//3]
(47)
20 (c-to-2)
1 20
(1-1o-1)/2))
50
exp
+ exp
3 3
<o exp
20
((-(--1)/21)
where uses eq. (19) and item 1 of Proposition 1, (ii) uses eq. (43) and (iii) uses eq. (6).
(Case 2) If 0 2. then the proof is similar to that of Case 2, and eqs. (45) & (47) still hold. The only difference is use the convergence of HI, Hl* given by eq. (7) instead of eq. (6).
(Case 3) If E (1, ). then similar to the proof of Case 2, we obtain from eq. (44) that
||,; x1I| 50 (H, 22 H*)1-1/0 (Hr-1 H/))-1/09 (He HT))-1/00
<0 -to 3-28
where the two use eqs. (43) & (6) respectively. Then, eq. (47) still holds, we have
Iive (x+)) <0 = 28
297
23


Reviews:
[{"review_id": "ukjcID0QU8D", "reviewer": "Reviewer_Xmar", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This work develops a non-trivial extension of first-order GDA algorithm to second-order algorithms for escaping saddle points in nonconvex minimax optimization. Specifically, the Cubic-GDA algorithm uses gradient ascent to estimate the second-order information of the minimax objective function, and leverages the cubic regularization technique to efficiently escape the strict saddle points.\n\nThe paper provides a comprehensive convergence analysis of this algorithm. Including its global convergence properties and convergence rates in general nonconvex minimax optimization, as well as its convergence rates under a broad class of gradient dominant conditions. The analysis is based on a careful characterization of the Jacobian matrix of the minimax objective function and its Lipschitz continuity property (Prop. 1). The key to the analysis is characterization of a special potential function that is proven to be monotonically decreasing (Prop. 2). This is an elegant result that justifies the numerical stability and correctness of the algorithm. \n\nUnder a wide spectrum of gradient dominant conditions, it is proved that Cubic-GDA achieves an orderwise faster convergence rate than the standard GDA. This demonstrates the effectiveness of introducing cubic regularization into nonconvex minimax optimization. This may inspire future developments of second-order minimax optimization algorithms.\n\n\nThe proposed Cubic-GDA algorithm can be viewed as an inexact cubic-regularization algorithm. Can the existing analysis of inexact Cubic regularization be applied here? \n\nThe learning rate $\\eta_x$ has a bad dependence of the problem condition number. This seems to be caused by the bounding techniques used in the proof. Is there a way to further reduce the dependence? Note that the GDA studied in (Lin 2020) only has a dependence of $\\kappa^2$.\n\nIf we apply accelerated gradient descent to solve the strongly concave sub problem, then it may lead to a faster global convergence rate of the algorithm. I suggest the authors add more discussions on this point.\n\n\n\n", "summary_of_the_paper": "This paper develops Cubic-GDA—the first GDA-type algorithm that can find second-order stationary points in nonconvex minimax optimization, whereas the existing GDA algorithms can only converge to first-order stationary points. The developed algorithm leverages the popular Cubic regularization technique to escape saddle points in nonconvex minimax optimization. \n\nUnder standard assumptions, the authors identify a monotonically decreasing potential function of the proposed Cubic-GDA algorithm, and leverage it to establish global convergence of Cubic-GDA to a second-order stationary point. Moreover, they analyze the convergence rate of Cubic-GDA in the full spectrum of gradient dominant-type geometries, and show that Cubic-GDA achieves an orderwise faster convergence rate than the standard GDA.\n", "summary_of_the_review": "Overall, this paper is nicely written and contains solid theoretical contributions to nonconvex minimax optimization. Given the emerging and growing interests in minimax optimization in the general machine learning community, I recommend accepting this work.\n\n-----------------------------\nAfter reading the other reviews, it seems that the present version indeed consists of a number of issues and is not yet ready for publication. But overall, I feel the paper contributes to analysis and algorithm design for minimax optimization. I have updated my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Y1evK2NF0hU", "reviewer": "Reviewer_N6EU", "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": "To the best of my knowledge, this is one of the very first second-order convergence rate results for nonconvex-strongly concave min-max problems (see another similar paper [1]). Both the results and analysis seem to be good to me. The theoretical contribution is also significant for this area. \n\nI have the following concerns:\n\nIn my understanding, ICLR is a conference that emphasizes relevance to practice. The optimization focus in the machine learning community is developing algorithms that are scalable for large-scale problems. This work seems to only focus on giving the convergence rates but not care about per-iteration cost. In fact, both forming the Jacobian matrix in the algorithm and solving the cubic subproblems exactly are very expensive in the machine learning context. So, I am not sure of the practical relevance of this paper. I hope that the authors can provide approximate optimization steps for the primal variable vector and provide the iteration complexity in terms of first-order oracle (i.e., gradient evaluation and Jacobian-vector product). \n\nFor the results under Łojasiewicz gradient geometry, I hope that the authors can provide some practical cases that satisfy this assumption in the paper, not only just citing some relevant papers. \n\n\n\n[1] Luo, Luo, and Cheng Chen. \"Finding Second-Order Stationary Point for Nonconvex-Strongly-Concave Minimax Problem.\" arXiv preprint arXiv:2110.04814 (2021).\n\n\n\n\n\n", "summary_of_the_paper": "This paper introduced new algorithms for second-order guarantees of nonconvex-strongly concave problems. First, the paper first gave convergence rate guarantees for the general setting; then it gave linear or superlinear convergence rate results under different orders of  Łojasiewicz gradient geometry. ", "summary_of_the_review": "The authors provide the very first second-order convergence rate results for nonconvex-strongly-concave minimax problems. But I believe that the style of the current version is not very suitable for the machine learning community and the ICLR conference as it does not focus on the large scale setting and does not care about practical performance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Prf97yMIFLn", "reviewer": "Reviewer_c2gL", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper combines gradient ascent-descent techniques with the second-order optimization approach of cubic regularization, leveraging on the preservation of Lipschitz properties of the solution of the max problem, while using only an approximated solution for the strongly concave max problem.\nI found the approach interesting and sufficiently innovative. \nThe paper is well-written, the mathematical  writing and analysis are nice and straightforward, and their combination of techniques is interesting.\nI read most of the proofs in the appendix, and to the best of my knowledge, are correct, although I did not read too carefully; nonetheless, the results are sensible and coherent compared to standard analysis and known results.\n\nA few issues:\n\n1. The structure of the paper, or more precisely the locations of the problem formulation and baseline assumption, is confusing for the expert reader. The problem is declared in 3 locations, together with the definition of second-order stationarity, but the first two statements are lacking in terms of mathematical formulation. This can be solved easily by moving Assumption 1 to the beginning of the paper, so all the statements made up until page 4 will make sense...\nAdditionally, in the same context, pages 1-4 indeed feel a bit repetitive, consider maybe revising, and then you will have some spaces for additional things, such as proofs sketch, etc.\n2. The cubic regularization approach was first taken by: Griewank, A.: The Modification of Newton’s Method for Unconstrained Optimization by Bounding Cubic Terms. Technical Report NA/12 (1981). \nUnfortunately, this is quite an unknown manuscript in the community that deserves the credit for being the first (to the best of my knowledge).\n3. Another recent paper for second-order optimization that might be relevant and was not mentioned is: Hallak, N., and Teboulle, M., \"Finding second-order stationary points in constrained minimization: A feasible direction approach.\" Journal of Optimization Theory and Applications 186.2 (2020): 480-503. \nI think this paper also has a version for unconstrained problems.\n4. There is a typo in the declaration of Theorem 4. \n", "summary_of_the_paper": "The paper proposes a second-order cubic regularization type method for an unconstrained min-max problem in which the function is twice continuously differential, strongly concave w.r.t the max decision variable, with Lipschitz continuous first and second derivatives.\nThe proposed method comprises a nested gradient ascent process of the max variable, with a dynamic number of iterations that guarantee the desired properties to support the convergence resutls, and a cubic proximal update on the min variable. \nThe method is proved to converge to second-order stationary point, under standard assumptions.", "summary_of_the_review": "Pros:\n- New method combining elements from first and second order methods\n- The method only approximates the solution of the max problem\n- New convergence guarantees for the min-max problem\n- Well-written mathematically and in general\n\nCons:\n- Results are not surprising, and somewhat a direct implication, considering the techniques used and the current literature.\n\nOverall: I recommend to accept the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Nx3Vt41qlnX", "reviewer": "Reviewer_ENLL", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Finding second-order stationary points of a nonconvex minimax problem is an interesting and important problem in the optimization area. The proposed algorithm seems intuitive and reasonable with clear motivation. However, the theoretical contributions of the paper are not strong and the empirical study is missing.\n\nMy first concern is about the global convergence rate. According to Proposition 2, $\\eta_x$ should be $O(\\kappa^9)$. Then, the global convergence rate in Theorem 2 shows that cubic-GDA seems to require $O(\\kappa^{13.5}\\epsilon^{-1.5})$ total iterations to achieve an $\\epsilon$-first-order stationary point which satisfies $||\\nabla\\Phi(x_t)||\\leq \\epsilon$. Notice that the convergence rate of GDA is only $O(\\kappa^2\\epsilon^{-2})$ (Lin et. al., 2020). The order of $\\kappa$ in the results of Cubic-GDA  is much worse than that of GDA.\nSuch result is unbearable for ill-conditioned problems (which is very common in real applications).\n\nMy second concern is about the way of solving the cubic regularization sub-problem. The paper claims that the cubic regularized sub-problem can be efficiently solved by gradient descent methods (Carmon and Duchi, 2016). However, gradient descent can only achieve a sublinear convergence rate.\nHence, I think it is important to discuss how the inexact minimizer affects the convergence behavior of Cubic-GDA. \nThe theoretical analysis of this paper is based on assuming the sub-problem can be solved exactly, which is not reasonable.\n\nMy last concern is this paper does not provide any empirical results. The previous two concerns show that the proposed algorithm may converge very slowly. Thus I doubt whether the proposed method can outperform GDA algorithms in real applications. I hope the authors perform some empirical studies to verify the effectiveness of the proposed algorithm. Additionally, it is preferred to conduct experiments to show Cubic-GDA can escape some unexpected suboptimal saddle points that GDA stuck.\n\nMinors:\n\nDo you have any ideas to generalize current results to nonconvex-concave (not strongly-concave) setting?", "summary_of_the_paper": "This paper studies nonconvex minimax optimization problems and proposes a novel algorithm, called Cubic-GDA, which can escape the strict saddle points and find the second-order stationary points of the nonconvex minimax problem. The paper also provides the global convergence rate of the proposed algorithm and analyzes the convergence property under local nonconvex geometry.  ", "summary_of_the_review": "Pros:\n1. The studied problem is interesting and the proposed method is novel.\n\nCons:\n1. Theoretical analysis is on the weak side.\n2. No empirical results.\n\nOverall, I recommend to reject this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GxCqN20Z-G7", "reviewer": "Reviewer_W1TD", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Major issues:\n\n1. The key takeaway is that Cubic-GDA converges to a “second-order stationary point” of the envelope function. While it is well-received in nonconvex optimization literature, the authors could explain why such a point is of interest in the context of minimax optimization, i.e., how it is related to the solution of (P). For instance, it appears to have connection with the second-order necessary condition for a local minimax point introduced in (Jin et al. 2020, “What is local optimality in nonconvex-nonconcave minimax optimization?”).  \n\n2. The paper is not very novel in terms of algorithms development cause it basically runs the update of CRN method on the envelope function and reaches its second-order stationary point, which is known for CRN. The only technical challenge is addressing the accuracy required for solving the inner maximization problem. Indeed, this is not very challenging as in the strongly concave case the inner problems can be solved exponentially fast. \n\n3. The comparisons with related work seem insufficient. I expect the authors to discuss more on current first-order methods for the nonconvex-strongly-concave minimax problems. Also, given that the proposed method is in essence an inexact version of CR on the envelope function, the authors may need to justify why existing results on inexact CR method are not directly applicable.   \n\n4. In Proposition 2, the choice of $\\eta_x$ has a very bad dependence on the conditional number (on the order of \\kappa^{-7}). This in turn leads to huge constants in most of the convergence results, which could potentially undo the benefit of using second-order methods if the required accuracy is moderate. \n\n5. The original CR method in (Nesterov and Polyak, 2006) is also shown to behave very well in the local neighborhood of a strict saddle point or a strict local minimum. So I am wondering whether cubic-GDA can retain these desired features or not. \n\n6. It will be helpful if the authors can include numerical experiments to support the theoretical findings. For instance, it will make a very good point if the authors can come up with a specific example where GDA converges to an undesired stationary point while cubic-GDA succeeds in finding a local minimax solution. \n\nMinor issues:\n\n1. At the bottom of page 1: “envelop” -> “envelope”.\n2. The paper refers to y^*(x) as the minimizer, but it is in fact the maximizer.\n3. The authors describe their method as a “GDA-type algorithm”, which is a bit misleading. First of all, there is no gradient descent step. Also, since the update of x requires second-order information, it seems more appropriate to address it as a Newton-type method.\n4. Both “Jin et al. 2017a” and “Jin et al. 2017b” point to the same reference. Also, “Jin et al. 2017b” mentioned in the related work on CR seems to be the wrong reference.", "summary_of_the_paper": "\nIn this paper, the authors develop a second-order method based on the cubic regularization technique for solving nonconvex-strongly-concave minimax problems. They analyze its convergence rate under the standard smoothness assumptions as well as under the local Lojasiewicz gradient geometry. Notably, this is the first algorithm that provably converges to a second-order stationary point and hence escapes strict saddle points. ", "summary_of_the_review": "I think the paper addresses an interesting problem, but its algorithm development is not very novel. Moreover, the authors need to better explain why achieving such second-order stationary point should be of interest in the context of minimax optimization. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide a cubic regularization approach to non-convex concave minimax problems. The reviewers highlight that the paper in its current form is not ready for publication due to issues such as the gap between the theory and the implementable algorithm.
Decision: Reject