Year: 2021

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 Newton-type GDA algorithm for escaping strict saddle points in nonconvexstrongly-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.

heading: 1 INTRODUCTION
text: Nonconvex minimax optimization is 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 et al., 2020; Ho and Ermon, 2016; Song et al., 2018), etc. A standard nonconvex minimax optimization problem is shown below, where f is a smooth nonconvex function in x.
min x∈Rm max y∈Rn f(x, y). (P)
In the existing literature, many optimization algorithms have been developed to solve different types of minimax problems. Among them, a 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-type geometry (f is convex in x and concave in y) (Nedić and Ozdaglar, 2009; Du and Hu, 2019; Mokhtari et al., 2020; Zhang and Wang, 2021), bi-linear geometry (Neumann, 1928; Robinson, 1951) and PolyakŁojasiewicz geometry (Nouiehed 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 nonconvex-concave problems (Lin et al., 2020; Nouiehed et al., 2019; Xu et al., 2020d) and nonconvex-strongly-concave 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 a certain envelope function of the minimax problem vanishes.
Although GDA can find first-order stationary points of nonconvex minimax problems, such a 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 a 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 nonconvex-strongly-concave minimax optimization. We also characterize the global and local convergence rates of this algorithm under various types of nonconvex geometry. We summarize our contributions as follows.

heading: 1.1 OUR CONTRIBUTIONS
text: We consider the minimax optimization problem (P), where f is a twice-differentiable and nonconvexstrongly-concave function, and its gradient and Jacobian matrices are Lipschitz continuous. Define an envelope function Φ(x) := maxy∈Rn f(x, y). The existing GDA algorithms can only find first-order stationary points that satisfy ∇Φ(x∗) = 0. In this paper, we develop a Newton-type GDA algorithm that converges to second-order stationary points of the nonconvex minimax problem (P).
Specifically, we propose Cubic-GDA – a Newton-type GDA algorithm that leverages the classical cubic regularization technique to escape saddle points. Different from the standard cubic regularization 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.
We study the global convergence property of Cubic-GDA in general nonconvex-strongly-concave optimization. Specifically, we show that Cubic-GDA admits an intrinsic potential functionH(x, 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 {xt}t 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 a broad spectrum of the local nonconvex Łojasiewicz gradient geometry. In this case, we show that Cubic-GDA converges to a unique limit point, which is a second-order stationary point. Moreover, as the geometry parameter increases (i.e., sharper local geometry), the convergence rate of Cubic-GDA accelerates from sublinear convergence up to super-linear convergence, as we summarize in Table 1 below. In particular, these convergence rates are orderwise faster than those of the standard GDA under the same type of nonconvex geometry (Chen et al., 2021) 1.
1Note that the geometry parameter θ in this paper corresponds to 1 1−θ in (Chen et al., 2021).

heading: 1.2 RELATED WORK
text: Deterministic GDA algorithms: 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 GDA in the nonconvex-concave setting whereas Lin et al. (2020); Xu et al. (2020d) focused on the nonconvex-strongly-concave setting. In these general nonconvex settings, it is shown that GDA converges to a certain stationary point at a sublinear rate. Recently, Chen et al. (2021) proved the parameter convergence of proximal-GDA in regularized nonconvex-stronglyconcave optimization under the Kurdyka-Łojasiewicz geometry. The convergence rates obtained 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 xt+1 instead of xt. Xu et al. (2020d) studied an alternating gradient projection algorithm which applies `2 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 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 momentum-accelerated 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 a 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 a comparison, this study focuses on analyzing the global and local convergence properties of Cubic-GDA.
Stochastic GDA algorithms: Lin et al. (2020); Yang et al. (2020) analyzed stochastic GDA and stochastic AGDA, which are direct extension of 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-based (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 to (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 a 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., 2011b). 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 et al. (2017) proposed an inexact CR for solving convex problem. Also, Cartis et al. (2011a) proposed
an adaptive inexact CR for nonconvex optimization, whereas Jiang et 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 et al., 2020a; Zhou and Liang, 2018; Wang et al., 2018).

heading: 2 PROBLEM FORMULATION AND PRELIMINARIES
text: 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∇1f,∇2f as the gradients with respect to the first and the second input arguments of f , respectively. We also denote ∇11f,∇22f as the Jacobian matrices where the second-order derivatives are taken over the first and second arguments of f , respectively. Moreover, we denote ∇12f as the Jacobian matrix where the second-order derivative is taken over the first argument of f and followed by the second argument, and∇21f 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:
1. Function f(·, ·) is L1-smooth and function f(x, ·) is µ-strongly concave for all fixed x;
2. The Jacobian matrices∇11f ,∇12f ,∇21f ,∇22f are L2-Lipschitz;
3. Function Φ is bounded below and has compact sub-level sets.
To elaborate, item 1 considers the class of nonconvex-strongly-concave functions f that has been 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 f are Lipschitz, which is a standard assumption for analyzing many second-order optimization algorithms (Nesterov and Polyak, 2006; Agarwal et al., 2017; Yue et al., 2019). Moreover, item 3 guarantees that the minimax problem has at least one solution. By strong concavity of f(x, ·), it is clear that the maximizer y∗(x) := arg maxy∈Rn f(x, y) is unique for every x ∈ Rm. In particular, if x∗ is a second-order stationary point of Φ(x), then (x∗, y∗(x∗)) is the desired solution of the minimax problem (P).
Define an envelope function Φ(x) := maxy∈Rn f(x, y). Then the minimax problem (P) is equivalent to the minimization problem. minx∈Rm Φ(x), where Φ(x) = maxy∈Rn f(x, y). As we show in item 2 of Proposition 1 later, this envelope function Φ(x) is smooth and nonconvex. The existing GDA algorithms can only find first-order stationary points of the minimax problem that satisfy∇Φ(x∗) = 0. In this paper, we aim to develop a provably convergent algorithm that can find second-order stationary points x∗ of the function Φ(x) that satisfy the following set of conditions.
(Second-order stationary): ∇Φ(x∗) = 0, ∇2Φ(x∗) 0.
In the existing literature, many optimization algorithms have been developed for finding secondorder 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 et al., 2017; Yue et al., 2019; Zhou et al., 2018). However, these algorithms are not directly applicable to solve the problem (P’), as the function Φ(x) involves a special maximization structure and hence its specific function form Φ as well as the gradient∇Φ and Hessian∇2Φ are not available in practice. Instead, our algorithm design can only leverage information of the bi-variate function f .
Next, we present some important properties regarding the gradient and Jacobian matrices of the functions f(x, y) and Φ(x). Throughout, we denote κ = L1/µ as the condition number. Proposition 1. Let Assumption 1 hold. Then, the following statements hold.
1. Mapping y∗(x) is κ-Lipschitz continuous;
2. Function Φ(x) is L1(1 + κ)-smooth and ∇Φ(x) = ∇1f(x, y∗(x));
3. Define G(x, y) = ∇11f(x, y) − ∇12f(x, y)[∇22f(x, y)]−1∇21f(x, y). Then, G is a Lipschitz mapping with constant LG = L2(1 + κ)2, i.e., ‖G(x′, y′)−G(x, y)‖ ≤ LG‖(x′, y′)− (x, y)‖;
4. The Hessian of Φ satisfies∇2Φ(x) = G(x, y∗(x)), which is Lipschitz continuous with constant LΦ = LG(1 + κ) = L2(1 + κ) 3.
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 ∇2Φ(x) allows us to develop a cubic-regularization-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 1 (see the first page of the appendix), which helps prove the Lipschitz continuity of the G mapping in item 3. Moreover, we leverage the optimality condition of f(x, ·) to derive an expression for the maximizer mapping y∗(x) (see (15) in the appendix), which is used to further prove item 4.

heading: 3 CUBIC-GDA: CUBIC-REGULARIZED GRADIENT DESCENT-ASCENT
text: In this section, we propose a 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, to find a second-order stationary point of the envelope function Φ(x), the conventional cubic regularization algorithm would perform the following iterative update.
xt+1 ∈ arg min x
∇Φ(xt)>(x− xt) + 1
2 (x− xt)>∇2Φ(xt)(x− xt) +
1
6ηx ‖x− xt‖3, (1)
where ηx > 0 is a proper learning rate. However, due to the special maximization structure of Φ, its gradient and Hessian have complex formulas (see Proposition 1) that involve the mapping y∗(x), which cannot be computed exactly in practice. Hence, we aim to 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∇Φ(xt) = ∇1f(xt, y∗(xt)) and ∇2Φ(xt) = G(xt, y∗(xt)) (by Proposition 1), both of which depend on the maximizer y∗(xt) of the function f(xt, ·). Since f(xt, ·) is strongly-concave, we can run Nt iterations of gradient ascent to obtain an approximated maximizer ỹNt ≈ y∗(xt), and then approximate∇Φ(xt),∇2Φ(xt) using∇1f(xt, ỹNt) and G(xt, ỹNt), respectively. Intuitively, these are good approximations due to two reasons: (i) ỹNt converges to y
∗(xt) at a fast linear convergence rate; and (ii) both ∇1f and G are shown in Proposition 1 to be Lipschitz continuous in their second argument. We refer to this algorithm as Cubic-Regularized Gradient Descent-Ascent (Cubic-GDA), and summarize its update rule in Algorithm 1 below.
Algorithm 1 Cubic-Regularized Gradient Descent-Ascent (Cubic-GDA) Input: Initialize x0, y0 and learning rates ηx, ηy . for t = 0, 1, 2, . . . , T − 1 do
Initialize ỹ0 = yt. for k = 0, 1, 2, . . . , Nt − 1 do
ỹk+1 = ỹk + ηy∇2f(xt, ỹk). end Set yt+1 = ỹNt and compute G(xt, yt+1) as follows:
G(xt, yt+1) = ∇11f(xt, yt+1)−∇12f(xt, yt+1)[∇22f(xt, yt+1)]−1∇21f(xt, yt+1).
xt+1 ∈ arg minx∇1f(xt, yt+1)>(x− xt) + 12 (x− xt) >G(xt, yt+1)(x− xt) + 16ηx ‖x− xt‖ 3. end Output: xT , yT .
We further comment on the implementation of Cubic-GDA. We note that the Cubic-GDA updates in Algorithm 1 can be implemented in a computation efficient way. First, note that Cubic-GDA involves
an inner loop that performs gradient ascent updates. To guarantee the convergence of the algorithm, we prove in the next section that the number of inner iterationsNt only needs to be kept at logarithm scale. Therefore, a few number of inner iterations suffice to 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 Hessian-vector product G(x, y)v for any vector v, one needs to compute the Jacobian-vector product∇11f(x, y)v and the matrix-vector product ∇12f(x, y)[∇22f(x, y)]−1∇21f(x, y)v. We note that this matrix-vector product term can be computed as follows: first compute the Jacobian-vector product b = ∇21f(x, y)v; Then, solve the invertible linear system ∇22f(x, y)u = b using any standard solver (e.g., conjugate gradient method), which involves iteratively computing Jacobian-vector products ∇22f(x, y)w for some vector w; Finally, compute the Jacobian-vector product ∇12f(x, y)u. Hence, one can call multiple Jacobian-vector product oracles to solve the cubic regularization sub-problem.

heading: 4 GLOBAL CONVERGENCE PROPERTIES OF CUBIC-GDA
text: In this section, we study the global convergence properties of Cubic-GDA. Importantly, our analysis is based on characterizing an intrinsic potential function of the Cubic-GDA algorithm in 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 1 hold. Define the following potential function
H(x, x′, y) := Φ(x) + L2κ 3‖x′ − x‖3 + 4L2‖y − y∗(x)‖3,
and denoteHt := H(xt, xt−1, yt+1). ChooseNt ≥ max(ln 2, ln[L1‖∇2f(xt,yt)‖/(L2µ)]−2 ln ‖xt−xt−1‖)ln[κ/(κ−1)] and learning rates ηx ≤ 128L2κ3 , ηy ≤ 2 L+µ . Then, the sequences {xt, yt}t generated by Cubic-GDA satisfy, for all t = 0, 1, 2, ...
Ht+1 ≤ Ht−L2κ3‖xt+1 − xt‖3−L2‖yt+1 − y∗(xt)‖3. (2) Consequently, it holds that
lim t→∞ ‖xt+1 − xt‖ = 0, lim t→∞ ‖yt+1 − yt‖ = 0, lim t→∞ ‖yt − y∗(xt)‖ = 0.
Remark 1. We note that the above key result can also be established for an inexact version of CubicGDA, which formulates the cubic subproblem with a general inexact gradient pt ≈ ∇1f(xt, yt+1) and inexact Jacobian Pt ≈ G(xt, yt+1) that satisfy the conditions
‖pt −∇1f(xt, yt+1)‖ ≤ O(‖xt+1 − xt‖2), ‖Pt −G(xt, yt+1)‖ ≤ O(‖xt+1 − xt‖). These inexactness conditions are widely studied in the existing literature Cartis et al. (2011b;a). Under these inexact conditions, our proof of the above proposition remains unchanged, except that the coefficients of the term ‖xt+1 − xt‖3 would be slightly different.
Proposition 2 reveals that Cubic-GDA admits an intrinsic potential function H , which is the objective function Φ(x) regularized by two cubic terms ‖x′ − x‖3, ‖y − y∗(x)‖3. Such a potential function is closely connected to the optimization goal. Specifically, consider a desired case where xt converges to a certain second-order stationary point x∗ and yt converges to y∗(x∗), it is clear that the potential function Ht would converge to the corresponding function value Φ(x∗). Hence, minimizing the function Φ is equivalent to minimizing the potential function H . More importantly, Proposition 2 shows that this potential function is monotonically decreasing along the optimization path of CubicGDA, 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 Cubic-GDA are asymptotically stable, i.e., xt+1 − xt → 0, yt → y∗(xt). Remark 2. In each outer iteration t, we set the total number of inner gradient ascent iterations Nt based on ‖∇2f(xt, yt)‖ and ‖xt − xt−1‖. Note that both of these two quantities can be easily computed right after iteration t− 1.
Based on Proposition 2, we are able to prove the convergence of {xt}t to a certain second-order stationary point, which we formally present in the next theorem. The proof is included in Appendix C. Theorem 1 (Global convergence). Under the same conditions as those of Proposition 2, the CubicGDA has the following global convergence properties.
1. The function value sequence {Φ(xt)}t converges to a finite limit H∗ > −∞;
2. The generated sequences {xt}t, {yt}t are bounded and have a compact sets of limit points.
3. Every limit point x∗ of {xt}t is a second-order stationary point of Φ, i.e., ∇Φ(x∗) = 0, ∇2Φ(x∗) 0, and satisfies Φ(x∗) = H∗.
The above theorem establishes the global convergence properties of Cubic-GDA. Specifically, item 1 shows that the function value sequence {Φ(xt)}t converges to a finite limit H∗, which is also the limit of the potential function sequence {Ht}t. Moreover, items 2 & 3 further show that all the limit points of {xt}t are second-order stationary points of the minimax problem, at which the function Φ achieves the constant value H∗. These results show that Cubic-GDA is guaranteed to find second-order stationary points in nonconvex minimax optimization.
By further leveraging the potential function characterized in Proposition 2, we obtain the following global convergence rate of Cubic-GDA to a second-order stationary point. The proof is included in Appendix D. Throughout, we adopt the following standard measure of second-order stationary introduced in (Nesterov and Polyak, 2006).
µ(x) = max
{√ ‖∇Φ(x)‖
1/(2ηx) + 5L2κ3 + 4L22κ 2/L1
, −λmin
( ∇2Φ(x) ) 1/(2ηx) + 4L22κ 2/L1 } .
Intuitively, a smaller µ(x) means that the point x is closer to being second-order stationary. Theorem 2 (Global convergence rate). Under the same conditions as those of Proposition 2, the Cubic-GDA converges at the following rate for all T ≥ H0−infx∈Rm Φ(x)L2κ3/3 .
min 0≤t≤T−1
µ(xt) ≤ (H0 − infx∈Rm Φ(x)
TL2κ3/3
)1/3 .
The above theorem shows that the first-order stationary measure ‖∇Φ(xt)‖ converges at a sublinear rate O(T− 23 ), and the second-order stationary measure −λmin ( ∇2Φ(x) ) converges at a sublinear rate O(T− 13 ). Both results match the convergence rates of the cubic regularization algorithm for nonconvex minimization (Nesterov and Polyak, 2006). Therefore, by leveraging the curvature of the approximated Hessian matrix G(xt, yt+1), Cubic-GDA is able to escape strict saddle points of Φ at a fast rate.
We note that the proof of the global convergence results in Theorems 1 and 2 are critically based on the intrinsic potential function H that we characterized in Proposition 2. We elaborate our technical contribution as follows.
• First, to identify the potential function, we need to characterize the per-iteration progress induced by the cubic regularization step. However, the cubic subproblem in Cubic-GDA is constructed by an inexact gradient∇1f(xt, yt+1) and Hessian matrix G(xt, yt+1). Therefore, we need to properly choose the number of inner gradient ascent iterations Nt to control the estimation error of both the gradient and Hessian approximations at a desired level.
• Due to the inexactness of the gradient and Hessian matrix, the cubic regularization update of Cubic-GDA does not lead to a monotonically decreasing function value Φ(xt), as opposed to the original cubic regularization algorithm in nonconvex minimization (which uses exact gradient and Hessian). Hence, we construct and identify a decreasing potential function H instead.

heading: 5 CONVERGENCE ANALYSIS UNDER LOCAL NONCONVEX GEOMETRY
text: The (2) of Proposition 2 shows that Cubic-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
optimization. In this section, we explore the convergence rates of Cubic-GDA under a broad spectrum of local nonconvex geometries characterized by the Łojasiewicz gradient inequality.
We first introduce the Łojasiewicz gradient geometry of a function h. Throughout, the point-to-set distance is denoted as distΩ(x) := infu∈Ω ‖x− u‖. Definition 1. A differentiable function h is said to satisfy the Łojasiewicz gradient geometry if for every compact set Ω of critical points on which h takes a constant value hΩ ∈ R, there exist ε, λ > 0 such that for all x ∈ {z ∈ Rm : distΩ(z) < ε, hΩ < h(z) < hΩ + λ}, the following condition holds.
h(x)− hΩ ≤ c‖∇h(x)‖θ, (3)
where c > 0 is a universal constant and θ ∈ (1,+∞) is the geometry parameter.
Intuitively, the Łojasiewicz gradient geometry is a gradient-dominant-type geometry that characterizes the local geometry of a nonconvex function around the set of critical points. In particular, it generalizes the Polyak-Łojasiewicz (PL) geometry that corresponds to the special case θ = 2 Łojasiewicz (1963); Karimi et al. (2016). In fact, a generalized version of the Łojasiewicz gradient geometry has been shown to hold for a large class of functions including sub-analytic functions, exponential functions and semi-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 minθ maxξi 1 n ∑n i=1 `(hθ(ξi), yi) 2 − λ2 ‖ξi − ai‖ 2. Here (xi, yi) is the i-th data sample that includes, e.g., an image xi and its label yi, ξi denotes the adversarial image, hθ is a classification model parameterized by θ, and ` denotes the loss function. Such a problem is nonconvex-stongly-concave when λ is large. In particular, as elaborated in the appendix of (Bolte et al., 2014), the envelop function Φ(x) := maxξi 1 n ∑n i=1 `(hθ(ξi), yi) 2 − λ2 ‖ξi − ai‖ 2 satisfies the local Lojasiewicz gradient geometry if it is semi-algebraic, which holds if every sample loss f(θ, ξi) := `(hθ(ξi), yi) 2 − λ2 ‖ξi − ai‖ 2 is semi-algebraic.
By (2) of Proposition 2 and (30) (proved in Appendix E), we show that the potential function H of Cubic-GDA satisfies the following special optimization dynamics.
Ht+1 −Ht ≤ −O ( ‖xt+1 − xt‖3 ) , (4)
‖∇Ht‖ ≤ O ( ‖xt − xt−1‖2 + ‖xt−1 − xt−2‖2 ) . (5)
The above dynamics of Cubic-GDA involves higher-order terms than the dynamics of GDA, which takes the form Ht+1−Ht ≤ −O(‖xt+1−xt‖2) and ‖∇Ht‖ ≤ O(‖xt+1−xt‖) (Chen et al., 2021). Thus, it is expected that Cubic-GDA achieves a faster convergence rate than GDA. On the other hand, compare with the dynamics of the cubic regularization algorithm (Zhou et al., 2018), the gradient dynamic of Cubic-GDA in (5) involves an additional term ‖xt−1−xt−2‖2 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 Łojasiewicz gradient geometry, we are able to prove the following strengthened convergence result of Cubic-GDA. Theorem 3. Let Assumption 1 hold and assume that the potential function H satisfies the local Łojasiewicz gradient geometry. Choose the hyperparameters Nt, ηx, ηy in the same way as Proposition 2. Then, the sequences {(xt, yt)}t generated by Cubic-GDA have a unique limit point, which is a second-order stationary point of Φ.
Recall that Theorem 1 only proves that every limit point of {xt}t 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 Łojasiewicz gradient geometry.
Next, we further study the asymptotic convergence rates of Cubic-GDA under different parameter ranges of the Łojasiewicz gradient geometry. We first obtain the following function value convergence rate result, which strengthens the convergence rate result established in Theorem 2. Throughout, t0 denotes a sufficiently large positive integer and C0 is a universal positive constant defined as
C0 = 3 √ 2c1/θL −2/3 2 ( 10L2κ+
24L32 L21κ + 4L22 L1 + 1 2ηxκ2 ) The proof is included in Appendix F.
Theorem 4 (Funtion value convergence rate). Under the same conditions as those of Theorem 3, the sequence of potential function {Ht}t converges to the limit H∗ at the following rates. 1. If the geometry parameter θ ∈ ( 32 ,∞), then Ht ↓ H ∗ super-linearly as
Ht −H∗ ≤ O ( exp ( − (2θ
3
) t−t0 2 )) , ∀t ≥ t0; (6)
2. If the geometry parameter θ = 32 , then Ht ↓ H ∗ linearly as
Ht −H∗ ≤ (1 + C3/20 )− t−t0 2 , ∀t ≥ t0; (7)
3. If the geometry parameter θ ∈ (1, 32 ), then Ht ↓ H ∗ sub-linearly as Ht −H∗ ≤ O ( (t− t0)− 2θ 3−2θ ) , ∀t ≥ t0. (8)
Remark 3. We note that if the Łojasiewicz gradient geometry holds globally, then the above asymptotic convergence rates become global convergence rates.
The above theorem characterizes the convergence rates of the potential function of Cubic-GDA in the full spectrum of θ of the local Łojasiewicz 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 in Table 1 in the introduction section, the convergence rate of Cubic-GDA is orderwise faster than that of the vanilla GDA for a wide range of the parameter of the Łojasiewicz gradient geometry. This demonstrates the advantage of leveraging higher-order information in nonconvex minimax-optimization.
As a byproduct, we also obtain the following asymptotic convergence rates of the parameter sequences generated by Cubic-GDA under the Łojasiewicz 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, yt}t generated by Cubic-GDA converge to their limits x∗, y∗(x∗) respectively at the following rates.
1. If the geometry parameter θ ∈ ( 32 ,∞), then (xt, yt)→ (x ∗, y∗(x∗)) super-linearly as
max { ‖xt − x∗‖, ‖yt − y∗(x∗)‖ } ≤ O ( exp ( − 1
3 (2θ 3 ) t−t0 2 −1)) , ∀t ≥ t0; (9)
2. If the geometry parameter θ = 32 , then (xt, yt)→ (x ∗, y∗(x∗)) linearly as max { ‖xt − x∗‖, ‖yt − y∗(x∗)‖ } ≤ O ( (1 + C 3/2 0 ) − t−t02 ) , ∀t ≥ t0; (10)
3. If the geometry parameter θ ∈ (1, 32 ), then (xt, yt)→ (x ∗, y∗(x∗)) sub-linearly as ‖xt − x∗‖ ≤ O ( (t− t0)− 2(θ−1) 3−2θ ) , ‖yt − y∗(xt)‖ ≤ O ( (t− t0)− 2θ 3(3−2θ) ) , ∀t ≥ t0. (11)
It 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.

heading: 6 CONCLUSION
text: In this paper, we take one step further toward improving the convergence guarantee of GDA-type algorithms in nonconvex minimax optimization. We develop a Cubic-GDA algorithm that leverages the second-order information and the cubic regularization technique to effectively escape strict saddle points in nonconvex minimax optimization. Our key observation is that Cubic-GDA has an intrinsic potential function that monotonically decreases in the optimization process, and this leads to a 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-type nonconvex geometries. In the future study, we will develop stochastic variants of Cubic-GDA to further improve its computation efficiency. Another interesting direction is to apply momentum techniques to further accelerate the convergence of this algorithm.

heading: A Proof of Proposition 1 13

heading: B Proof of Proposition 2 14

heading: C Proof of Theorem 1 16

heading: D Proof of Theorem 2 17

heading: E Proof of Theorem 3 18

heading: F Proof of Theorem 4 20

heading: G Proof of Theorem 5 22
text: In this supplementary material, we present the proof of all the results claimed in the paper. We first prove the following auxiliary lemma that bounds the spectral norm of the Jacobian matrices. Lemma 1. Let Assumption 1 hold. Then, for any x ∈ Rm and y ∈ Rn, the Jacobian matrices of f(x, y) satisfy the following bounds.
‖[∇22f(x, y)]−1‖ ≤ µ−1, (12) ‖∇12f(x, y)‖ = ‖∇21f(x, y)‖ ≤ L1. (13)
Proof. We first prove eq. (12). Consider any x ∈ Rm and y ∈ Rn. By Assumption 1 we know that f(x, ·) is µ-strongy concave, which implies that −∇22f(x, y) µI . Thus, we further conclude that
‖[∇22f(x, y)]−1‖ = λmax ( [−∇22f(x, y)]−1 ) = ( λmin ( −∇22f(x, y) ))−1 ≤ µ−1.
Next, we prove eq. (13). Consider any x, u ∈ Rm and y ∈ Rn, we have ‖∇21f(x, y)u‖ = ∥∥∥ ∂ ∂t ∇2f(x+ tu, y) ∣∣∣ t=0 ∥∥∥ = ∥∥∥ lim t→0 1 t [ ∇2f(x+ tu, y)−∇2f(x, y)
]∥∥∥ = lim t→0 1 |t| ∥∥∇2f(x+ tu, y)−∇2f(x, y)∥∥
≤ lim t→0 L1 |t| ∥∥tu∥∥ = L1‖u‖, (14)
which implies that ‖∇21f(x, y)‖ ≤ L1. Since f is twice differentiable and has continuous secondorder derivative, we have∇12f(x, y)> = ∇21f(x, y), and hence eq. (13) follows.

heading: A PROOF OF PROPOSITION 1
text: Proposition 1. Let Assumption 1 hold. Then, the following statements hold.
1. Mapping y∗(x) is κ-Lipschitz continuous;
2. Function Φ(x) is L1(1 + κ)-smooth and ∇Φ(x) = ∇1f(x, y∗(x));
3. Define G(x, y) = ∇11f(x, y) − ∇12f(x, y)[∇22f(x, y)]−1∇21f(x, y). Then, G is a Lipschitz mapping with constant LG = L2(1 + κ)2, i.e., ‖G(x′, y′)−G(x, y)‖ ≤ LG‖(x′, y′)− (x, y)‖;
4. The Hessian of Φ satisfies∇2Φ(x) = G(x, y∗(x)), which is Lipschitz continuous with constant LΦ = LG(1 + κ) = L2(1 + κ) 3.
Proof. The items 1 & 2 are proved in Chen et al. (2021); Lin et al. (2020).
We first prove the item 3. Consider any x, x′ ∈ Rm and y, y′ ∈ Rn. For convenience we denote z = (x, y) and z′ = (x′, y′). Then, by Assumption 1 and using the bounds of Lemma 1, we have that
‖G(x′, y′)−G(x, y)‖ ≤ ‖∇11f(x′, y′)−∇11f(x, y)‖+ ‖∇12f(x′, y′)−∇12f(x, y)‖‖[∇22f(x′, y′)]−1‖‖∇21f(x′, y′)‖
+ ‖∇12f(x, y)‖‖[∇22f(x′, y′)]−1 − [∇22f(x, y)]−1‖‖∇21f(x′, y′)‖ + ‖∇12f(x, y)‖‖[∇22f(x, y)−1]‖‖∇21f(x′, y′)−∇21f(x, y)‖ ≤ L2‖z′ − z‖+ (L2‖z′ − z‖)µ−1L1
+ L21‖[∇22f(x′, y′)]−1‖‖∇22f(x, y)−∇22f(x′, y′)‖‖[∇22f(x, y)]−1‖+ L1µ−1(L2‖z′ − z‖) ≤ L2(1 + 2κ)‖z′ − z‖+ L21µ−1(L2‖z′ − z‖)µ−1 ≤ L2(1 + κ)2‖z′ − z‖.
Next, we prove the item 4. Consider any fixed x ∈ Rm, we know that f(x, ·) achieves its maximum at y∗(x), where the gradient vanishes, i.e.,∇2f(x, y∗(x)) = 0. Thus, we further obtain that
0 = ∇x∇2f(x, y∗(x)) = ∇21f(x, y∗(x)) +∇22f(x, y∗(x))∇y∗(x),
which implies that
∇y∗(x) = −[∇22f(x, y∗(x))]−1∇21f(x, y∗(x)). (15)
With the above equation, we take derivative of∇Φ(x) = ∇1f(x, y∗(x)) and obtain that
∇2Φ(x) =∇11f(x, y∗(x)) +∇12f(x, y∗(x))∇y∗(x) =∇11f(x, y∗(x))−∇12f(x, y∗(x))[∇22f(x, y∗(x))]−1∇21f(x, y∗(x)) (16) =G(x, y∗(x)).
Moreover, we have that
‖∇2Φ(x′)−∇2Φ(x)‖ =‖G(x′, y∗(x′))−G(x, y∗(x))‖ ≤LG [ ‖x′ − x‖+ ‖y∗(x′)− y∗(x)‖ ] ≤LG(1 + κ)‖x′ − x‖, (17)
where the last step uses the item 1. This proves the item 4.

heading: B PROOF OF PROPOSITION 2
text: Proposition 2. Let Assumption 1 hold. Define the following potential function
H(x, x′, y) := Φ(x) + L2κ 3‖x′ − x‖3 + 4L2‖y − y∗(x)‖3,
and denoteHt := H(xt, xt−1, yt+1). ChooseNt ≥ max(ln 2, ln[L1‖∇2f(xt,yt)‖/(L2µ)]−2 ln ‖xt−xt−1‖)ln[κ/(κ−1)] and learning rates ηx ≤ 128L2κ3 , ηy ≤ 2 L+µ . Then, the sequences {xt, yt}t generated by Cubic-GDA satisfy, for all t = 0, 1, 2, ...
Ht+1 ≤ Ht−L2κ3‖xt+1 − xt‖3−L2‖yt+1 − y∗(xt)‖3. (2)
Consequently, it holds that
lim t→∞ ‖xt+1 − xt‖ = 0, lim t→∞ ‖yt+1 − yt‖ = 0, lim t→∞ ‖yt − y∗(xt)‖ = 0.
Proof. We first bound the term ‖yt+1 − y∗(xt)‖, which corresponds to the optimality gap of the maximization problem. Note that y∗(xt) ∈ Rn is the unique maximizer of the strongly concave function f(xt, y). Note that yt+1 is obtained by applying Nt gradient ascent steps starting from yt. Hence, By the convergence rate of gradient ascent algorithm under strong concavity, we conclude that with learning rate ηy = 2L+µ ,
‖yt+1 − y∗(xt)‖ ≤(1− κ−1)Nt‖yt − y∗(xt)‖ (18)
≤L2 L1 ‖xt − xt−1‖2, (19)
where the second inequality uses the hyperparameter choice
Nt ≥ ln[L1‖∇2f(xt, yt)‖/(L2µ)]− 2 ln ‖xt − xt−1‖ ln[κ/(κ− 1)] ≥ ln[L1‖yt − y ∗(xt)‖/L2]− 2 ln ‖xt − xt−1‖ ln[κ/(κ− 1)] ,
as ‖∇2f(xt, yt)‖ = ‖∇2f(xt, yt)−∇2f(xt, y∗(xt))‖ ≥ µ‖yt − y∗(xt)‖. Moreover, eq. (18) and the hyperparameter choice that Nt ≥ ln 2ln[κ/(κ−1)] imply that
‖yt+2 − y∗(xt+1)‖3 ≤(1− κ−1)3Nt‖yt+1 − y∗(xt+1)‖3
(i) ≤ ∥∥∥1
2 a+
1 2 b ∥∥∥3
(ii)
≤ 1 2 ‖yt+1 − y∗(xt)‖3 +
κ3
2 ‖xt+1 − xt‖3. (20)
where (i) denotes that a := yt+1 − y∗(xt), b := y∗(xt)− y∗(xt+1), (ii) applies Jensen’s inequality to the convex function ‖ · ‖3. Based on Theorem 10 and Proposition 1 of Nesterov and Polyak (2006), we know that
λmin [ G(xt, yt+1) ] ≥ − 1
2ηx ‖xt+1 − xt‖. (21)
Since xt+1 minimizes the following cubic sub-problem
gyt+1(x) := ∇1f(xt, yt+1)>(x− xt) + 1
2 (x− xt)>G(xt, yt+1)(x− xt) +
1
6ηx ‖x− xt‖3,
we obtain the following optimality condition
∇1f(xt, yt+1) +G(xt, yt+1)(xt+1 − xt) + 1
2ηx ‖xt+1 − xt‖(xt+1 − xt) = 0. (22)
Next, by the Lipschitz Hessian of Φ, we obtain that
Φ(xt+1)− Φ(xt) ≤ ( ∇Φ(xt)−∇1f(xt, yt+1) )> (xt+1 − xt) + 1
2 (xt+1 − xt)>
( ∇2Φ(xt)−G(xt, yt+1) ) (xt+1 − xt)
+∇1f(xt, yt+1)>(xt+1 − xt) + 1
2 (xt+1 − xt)>G(xt, yt+1)(xt+1 − xt) + LΦ 6 ‖xt+1 − xt‖3
(i) ≤ L1‖yt+1 − y∗(xt)‖‖xt+1 − xt‖+ LG 2 ‖xt+1 − xt‖2‖yt+1 − y∗(xt)‖
− 1 2
(xt+1 − xt)>G(xt, yt+1)(xt+1 − xt) + (LΦ
6 − 1
2ηx
) ‖xt+1 − xt‖3
(ii) ≤ 2L 3/2 1
3L 1/2 2 κ
3/2 ‖yt+1 − y∗(xt)‖3/2 +
L2κ 3
3 ‖xt+1 − xt‖3
+ LG 2 [2κ 3 ‖xt+1 − xt‖3 + 1 3κ2 ‖yt+1 − y∗(xt)‖3 ] + 1
4ηx ‖xt+1 − xt‖3 + (LΦ 6 − 1 2ηx ) ‖xt+1 − xt‖3 (23)
(iii)
≤ 2L2 3κ3/2 ‖xt − xt−1‖3 + 2L2 3 ‖yt+1 − y∗(xt)‖3 +
( 3L2κ
3 − 1 4ηx
) ‖xt+1 − xt‖3, (24)
where (i) uses Assumption 1, the item 4 of Proposition 1 and eq. (22), (ii) uses eq. (21) and the inequality that ab = ((Ca)3/2(Ca)3/2(b/C)3)1/3 ≤ 23 (Ca) 3/2 + b 3
3C3 for any a, b ≥ 0 and C > 0 (based on AM-GM inequality), (iii) uses eq. (19) and LG = L2(1 + κ)2 ≤ 4L2κ2, LΦ = L2(1 + κ)
3 ≤ 8L2κ3. Multiplying eq. (20) with 4L2 and adding it to eq. (24) yield that
Φ(xt+1)− Φ(xt) + 4L2‖yt+2 − y∗(xt+1)‖3
≤ 2L2 3κ3/2 ‖xt − xt−1‖3 + 8L2 3 ‖yt+1 − y∗(xt)‖3 +
( 5L2κ
3 − 1 4ηx
) ‖xt+1 − xt‖3,
(i) ≤ L2κ3‖xt − xt−1‖3 + 3L2‖yt+1 − y∗(xt)‖3−2L2κ3‖xt+1 − xt‖3,
where (i) uses the condition that ηx ≤ 128L2κ3 . The above inequality implies eq. (2) by defining Ht := Φ(xt) + L2κ
3‖xt − xt−1‖3 + 4L2‖yt+1 − y∗(xt)‖3. Next, summing eq. (2) over t = 0, 1, ..., T − 1, we obtain that for all T ≥ 1,
L2κ 3 T−1∑ t=0 ‖xt+1 − xt‖3 + L2 T−1∑ t=0 ‖yt+1 − y∗(xt)‖3
≤ H0 −HT ≤ H0 − Φ(xT ) ≤ H0 − inf x∈Rm Φ(x) < +∞. (25)
Letting T → ∞ yields that ∑∞ t=0 ‖xt+1 − xt‖3 < +∞ and ∑∞ t=0 ‖yt+1 − y∗(xt)‖3 < +∞, so limt→∞ ‖xt+1 − xt‖= limt→∞ ‖yt+1 − y∗(xt)‖ = 0. Hence, ‖yt − y∗(xt)‖ ≤ ‖yt − y∗(xt−1)‖+ ‖y∗(xt) − y∗(xt−1)‖
t→ 0 using continuity of y∗, and ‖yt+1 − yt‖ ≤ ‖yt+1 − y∗(xt)‖ + ‖yt − y∗(xt)‖ t→ 0.

heading: C PROOF OF THEOREM 1
text: Theorem 1 (Global convergence). Under the same conditions as those of Proposition 2, the CubicGDA has the following global convergence properties.
1. The function value sequence {Φ(xt)}t converges to a finite limit H∗ > −∞;
2. The generated sequences {xt}t, {yt}t are bounded and have a compact sets of limit points.
3. Every limit point x∗ of {xt}t is a second-order stationary point of Φ, i.e., ∇Φ(x∗) = 0, ∇2Φ(x∗) 0, and satisfies Φ(x∗) = H∗.
Proof. We first prove item 1. We have shown in Proposition 2 that {Ht}t is monotonically decreasing. Also, Assumption 1 says that Ht ≥ Φ(xt) ≥ infx∈Rm Φ(x) > −∞. Therefore, we conclude that {Ht}t converges to a finite limit H∗ > −∞. Since Proposition 2 proves that ‖xt − xt−1‖, ‖yt+1 − y∗(xt)‖ t→ 0, we further conclude that Φ(xt) t→ H∗, which proves item 1.
Next, we prove item 2. Note that Φ has compact sub-level sets. Moreover, for all t, we have
Φ(xt) ≤ Ht ≤ H0 < +∞. (26) Hence, the sequence {xt}t is bounded and thus has a compact set of limit points. Since y∗ is Lipschitz continuous by Proposition 1, {‖y∗(xt)‖}t is also bounded. Consequently, as ‖yt − y∗(xt)‖ → 0, we conclude that {yt}t is also bounded and hence has a compact set of limit points. This proves item 2.
Next, we will prove item 3. Suppose that xtk k→ x∗ along a certain sub-sequence {xtk}k. We have that ytk+1 t→ y∗(x∗) based on Proposition 2 and the continuity of y∗. In addition, Proposition 1 implies that Φ,∇Φ, ∇2Φ and G are continuous. Therefore, for every limit point x∗, Φ(x∗) = lim
tk→∞ Φ(xtk) = H
∗.
‖∇Φ(x∗)‖ = lim tk→∞ ‖∇Φ(xtk)‖ = limtk→∞ ‖∇f(xtk , y∗(xtk))‖ = limtk→∞ ‖∇f(xtk , ytk+1)‖
(i) = lim tk→∞ ∥∥∥G(xtk , ytk+1)(xtk+1 − xtk) + 12ηx ‖xtk+1 − xtk‖(xtk+1 − xtk) ∥∥∥ = 0
λmin [ ∇2Φ(x∗) ] = lim tk→∞ λmin [ ∇2Φ(xtk) ] = lim tk→∞ λmin [ G(xtk , y ∗(xtk)) ]
= lim tk→∞
λmin [ G(xtk , ytk+1) ] (ii) ≥ − 1
2ηx lim tk→∞ ‖xtk+1 − xtk‖ = 0
where (i) uses eq. (22), and (ii) uses eq. (21).

heading: D PROOF OF THEOREM 2
text: Theorem 2 (Global convergence rate). Under the same conditions as those of Proposition 2, the Cubic-GDA converges at the following rate for all T ≥ H0−infx∈Rm Φ(x)L2κ3/3 .
min 0≤t≤T−1
µ(xt) ≤ (H0 − infx∈Rm Φ(x)
TL2κ3/3
)1/3 .
Before proving Theorem 2, we first prove the following auxiliary lemma. Lemma 2. For any symmetric matrices A,B ∈ Rn×n, we have |λmin(A)− λmin(B)| ≤ ‖A−B‖.
Proof of Lemma 2. |λmin(A)− λmin(B)| ≤ ∣∣ min u:‖u‖=1 u>Au− min u:‖u‖=1 u>Bu ∣∣
≤ max u:‖u‖=1 ∣∣u>Au− u>Bu∣∣ ≤ max u:‖u‖=1 ( ‖u‖‖A−B‖‖u‖ ) = ‖A−B‖.
Proof of Theorem 2. Note that (25) implies that
min 2≤t≤T−1
( ‖xt+1 − xt‖3 + ‖xt − xt−1‖3‖+ ‖xt−1 − xt−2‖3 ) ≤ H0 − infx∈R m Φ(x)
TL2κ3/3 ,
which further implies that there exists 1 ≤ t′ ≤ T − 1 such that
max ( ‖xt′+1 − xt′‖, ‖xt′ − xt′−1‖, ‖xt′−1 − xt′−2‖ ) ≤ (H0 − infx∈Rm Φ(x)
TL2κ3/3
)1/3 . (27)
On the other hand, equation (2.2) of Nesterov and Polyak (2006) implies that,
‖∇Φ(xt′)−∇Φ(xt′−1)−∇2Φ(xt′−1)(xt′ − xt′−1)‖ ≤ LΦ 2 ‖xt′ − xt′−1‖2.
Since∇Φ(x) = ∇1f(x, y∗(x)),∇2Φ(x) = G(x, y∗(x)), the above inequality implies that
‖∇Φ(xt′)‖
≤ ‖∇1f(xt′−1, y∗(xt′−1)) +G(xt′−1, y∗(xt′−1))(xt′ − xt′−1)‖+ LΦ 2 ‖xt′ − xt′−1‖2 ≤ ‖∇1f(xt′−1, yt′) +G(xt′−1, yt′)(xt′ − xt′−1)‖+ ‖∇1f1(xt′−1, y∗(xt′−1))−∇1f(xt′−1, yt′)‖
+ ‖ ( G(xt′−1, y ∗(xt′−1))−G(xt′−1, yt′) ) (xt′ − xt′−1)‖+
LΦ 2 ‖xt′ − xt′−1‖2
(i) ≤ 1 2ηx ‖xt′ − xt′−1‖2 + L1‖yt′ − y∗(xt′−1)‖+ LG‖yt′ − y∗(xt′−1)‖‖xt′ − xt′−1‖
+ LΦ 2 ‖xt′ − xt′−1‖2
(ii) ≤ ( 1
2ηx + 4L2κ
3 ) ‖xt′ − xt′−1‖2 + L2‖xt′−1 − xt′−2‖2 + 4L22κ 2
L1 ‖xt′ − xt′−1‖2‖xt′+1 − xt′‖
(iii) ≤ ( 1
2ηx + 5L2κ
3 )(H0 − infx∈Rm Φ(x)
TL2κ3/3
)2/3 + 4L22κ 2
L1 (H0 − infx∈Rm Φ(x) TL2κ3/3 ) (iv)
≤ ( 1
2ηx + 5L2κ
3 + 4L22κ 2
L1 )(H0 − infx∈Rm Φ(x) TL2κ3/3 )2/3 , (28)
where (i) uses eq. (22), item 1 of Assumption 1 and item 3 of Proposition 1, (ii) uses eq. (19) and LG = L2(1 + κ)2 ≤ 4L2κ2, LΦ = L2(1 + κ)3 ≤ 8L2κ3, (iii) uses eq. (27), and (iv) uses T ≥ H0−infx∈Rm Φ(x)L2κ3/3 . Also, note that
− λmin ( ∇2Φ(xt′) ) (i)
≤ −λmin ( G(xt′ , yt′+1) ) + ‖G(xt′ , y∗(xt′))−G(xt′ , yt′+1)‖
(ii)
≤ 1 2ηx ‖xt′+1 − xt′‖+ LG‖yt′+1 − y∗(xt′)‖
(iii)
≤ 1 2ηx ‖xt′+1 − xt′‖+ LGL2 L1 ‖xt′ − xt′−1‖2
(iv)
≤ 1 2ηx (H0 − infx∈Rm Φ(x) TL2κ3/3 )1/3 + LGL2 L1 (H0 − infx∈Rm Φ(x) TL2κ3/3 )2/3 (v)
≤ ( 1
2ηx +
4L22κ 2
L1 )(H0 − infx∈Rm Φ(x) TL2κ3/3 )1/3 , (29)
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 ≥ H0−infx∈Rm Φ(x)L2κ3/3 and LG = L2(1 + κ)
2 ≤ 4L2κ2. Equations (28) & (29) imply Theorem 2.

heading: E PROOF OF THEOREM 3
text: Theorem 3. Let Assumption 1 hold and assume that the potential function H satisfies the local Łojasiewicz gradient geometry. Choose the hyperparameters Nt, ηx, ηy in the same way as Proposition 2. Then, the sequences {(xt, yt)}t generated by Cubic-GDA have a unique limit point, which is a second-order stationary point of Φ. Proof. We first derive a bound on ‖∇H(x, x′, y)‖ := √∑3
k=1 ‖∇kH(x, x′, y)‖2 as follows.
‖∇H(xt, xt−1, yt+1)‖ ≤ ‖∇1H(xt, xt−1, yt+1)‖+ ‖∇2H(xt, xt−1, yt+1)‖+ ‖∇3H(xt, xt−1, yt+1)‖
= ∥∥∥∇Φ(xt) + 3L2κ3‖xt − xt−1‖(xt − xt−1) + 12L2‖yt+1 − y∗(xt)‖∇y∗(xt)>[y∗(xt)− yt+1]∥∥∥ + ∥∥∥3L2κ3‖xt − xt−1‖(xt − xt−1)∥∥∥+ ∥∥∥12L2‖yt+1 − y∗(xt)‖[yt+1 − y∗(xt)]∥∥∥
(i) ≤ ‖∇Φ(xt−1) +∇2Φ(xt−1)(xt − xt−1)‖+ (LΦ
2 + 6L2κ
3 ) ‖xt − xt−1‖2
+ 12L2‖yt+1 − y∗(xt)‖2 ( 1 + ‖∇22f(x, y∗(x))−1‖‖∇21f(x, y∗(x))‖ )
(ii)
≤ ‖∇Φ(xt−1) +G(xt−1, yt)(xt − xt−1)‖+ ‖G(xt−1, y∗(xt−1))−G(xt−1, yt)‖‖xt − xt−1‖ + (LΦ
2 + 6L2κ
3 ) ‖xt − xt−1‖2 + 12L2(1 + µ−1L1)‖yt+1 − y∗(xt)‖2
(iii) ≤ ∥∥∥∇1f(xt−1, y∗(xt−1))−∇1f(xt−1, yt)− 1
2ηx ‖xt − xt−1‖(xt − xt−1)
∥∥∥
+ LG‖yt − y∗(xt−1)‖‖xt − xt−1‖+ (LΦ
2 + 6L2κ
3 ) ‖xt − xt−1‖2 + 24L2κ‖yt+1 − y∗(xt)‖2
(iv) ≤ L1‖yt − y∗(xt−1)‖+ (LΦ
2 + 6L2κ
3 + 1
2ηx
) ‖xt − xt−1‖2
+ LGL2 L1 ‖xt−1 − xt−2‖2‖xt − xt−1‖+
24L32κ
L21 ‖xt − xt−1‖4
(v) ≤ L2‖xt−1 − xt−2‖2 + ( 10L2κ 3 + 1
2ηx
) ‖xt − xt−1‖2
+ 4L22κ 2
L1 ‖xt−1 − xt−2‖2‖xt − xt−1‖+
24L32κ
L21 ‖xt − xt−1‖4 (30)
where (i) uses eq. (2.2) of Nesterov and Polyak (2006), the fact that ∇2Φ is LΦ-Lipschitz, and eq. (15), (ii) uses Lemma 1 and ∇2Φ(x) = G(x, y∗(x)) from item 4 of Proposition 1, (iii) uses eq. (22), ∇Φ(x) = ∇1f(x, y∗(x)) from item 2 of Proposition 1 and the inequality that 1 + κ ≤ 2κ, (iv) and (v) use eq. (19), and (v) uses LG = L2(1 + κ)2 ≤ 4L2κ2, LΦ = L2(1 + κ)3 ≤ 8L2κ3. Next, we prove the convergence of the sequence {xt}t under the assumption that H(x, x′, y) satisfies the Łojasiewicz gradient geometry. Recall that we have shown in the proof of Theorem 1 that: 1) {Ht}t decreases monotonically to the finite limit H∗; 2) for any limit point x∗, y∗ of {xt}t, {yt}t, Φ(x∗) = H∗. Hence, the Łojasiewicz gradient inequality (see Definition 1) holds after sufficiently large number of iterations, i.e., there exists t1 ∈ N+ such that for all t ≥ t1, H(xt, xt−1, yt+1) − H∗ ≤ c‖∇H(xt, xt−1, yt+1)‖θ. Equivalently,
ϕ′(Ht −H∗)‖∇H(xt, xt−1, yt+1)‖ ≥ 1.
where we define the concave function that ϕ(s) := c 1/θ 1−1/θ s 1−1/θ(θ > 1, s > 0).
In addition, since ‖xt − xt−1‖ t→ 0 (Proposition 2), there exists t2 ∈ N+ such that for all t ≥ t2, ‖xt − xt−1‖ ≤ 1. Hence, rearranging the above inequality and utilizing eq. (30), we obtain that for all t ≥ t0 := max(t1, t2),
ϕ′(Ht −H∗) ≥ ‖∇H(xt, xt−1, yt+1)‖−1
≥ [(4L22κ2
L1 + L2
) ‖xt−1 − xt−2‖2 + ( 10L2κ 3 + 24L32κ
L21 +
1
2ηx
) ‖xt − xt−1‖2 ]−1 (31)
By concavity of the function ϕ(s) := c 1/θ 1−1/θ s 1−1/θ(θ > 1, s > 0), we know that
ϕ(Ht −H∗)− ϕ(Ht+1 −H∗) ≥ ϕ′(Ht −H∗)(Ht −Ht+1) (i)
≥ L2κ 3‖xt+1 − xt‖3(
4L22κ 2
L1 + L2
) ‖xt−1 − xt−2‖2 + ( 10L2κ3 + 24L32κ
L21 + 12ηx
) ‖xt − xt−1‖2
(32)
(ii) ≥ L2κ 3‖xt+1 − xt‖3(√
4L22κ 2
L1 + L2‖xt−1 − xt−2‖+
√ 10L2κ3 + 24L32κ
L21 + 12ηx ‖xt − xt−1‖ )2 , where (i) uses Proposition 2 and eq. (31), (ii) uses the inequality that a2 + b2 ≤ (a + b)2 for any a, b ≥ 0. Rearranging the above inequality yields that
L2κ 3‖xt+1 − xt‖3
≤ [ϕ(Ht −H∗)− ϕ(Ht+1 −H∗)](√ 4L22κ 2
L1 + L2‖xt−1 − xt−2‖+
√ 10L2κ3 + 24L32κ
L21 +
1
2ηx ‖xt − xt−1‖
)2
≤ 1 27
( C2[ϕ(Ht −H∗)− ϕ(Ht+1 −H∗)] + 2
C
√ 4L22κ 2
L1 + L2‖xt−1 − xt−2‖
+ 2
C
√ 10L2κ3 + 24L32κ
L21 +
1
2ηx ‖xt − xt−1‖
)3 (33)
where the final step uses the AM-GM inequality that ab2 = [ 3 √ (C2a)(b/C)(b/C) ]3 ≤ 127 (C2a+ 2b C )
3 for any a, b ≥ 0 and C > 0 (the value of C will be assigned later). Taking cubic root of both sides of the above inequality and telescoping it over t = t0, . . . , T − 1, we obtain that
κ 3 √ L2 T−1∑ t=t0 ‖xt+1 − xt‖
≤ C 2
3 [ϕ(Ht0 −H∗)− ϕ(HT −H∗)] +
2
3C
√ 4L22κ 2
L1 + L2 T−1∑ t=t0 ‖xt−1 − xt−2‖
+ 2
3C
√ 10L2κ3 + 24L32κ
L21 +
1
2ηx T−1∑ t=t0 ‖xt − xt−1‖
≤ C 2
3 ϕ(Ht0 −H∗) +
2
3C
√ 4L22κ 2
L1 + L2 T−1∑ t=t0 ‖xt−1 − xt−2‖
+ 2
3C
√ 10L2κ3 + 24L32κ
L21 +
1
2ηx T−1∑ t=t0 ‖xt − xt−1‖
where the final step uses the facts that Ht − H∗ ≥ 0 and that ϕ(s) is monotonically increasing. Since the value of C > 0 is arbitrary, we can select large enough C such that 2 3C √ 4L22κ 2 L1 + L2, 2 3C √ 10L2κ3 + 24L32κ L21 + 12ηx < κ 3 √ L2
3 . Hence, the inequality above further implies that
κ 3 √ L2
3 T−1∑ t=t0 ‖xt+1 − xt‖ ≤ C2 3 ϕ(Ht0 −H∗)
+ κ 3 √ L2
3
[ ‖xt0−1 − xt0−2‖+ 2‖xt0 − xt0−1‖ ] < +∞. (34)
Letting T →∞ concludes that ∞∑ t=1 ‖xt+1 − xt‖<+∞.
Moreover, this implies that {xt}t is a Cauchy sequence and therefore converges to a certain limit, i.e., xt
t→ x∗. We have shown in Theorem 1 that any such limit point must be a second-order critical point of Φ. Hence, we conclude that {xt}t converges to a certain second-order critical point x∗ of Φ(x). Also, note that ‖y∗(xt)− yt‖ t→ 0, xt t→ x∗ and y∗ is a Lipschitz mapping, so we conclude that {yt}t converges to y∗(x∗). Finally, the item 3 of Theorem 1 implies that x∗ is a second-order critical point of Φ(x).

heading: F PROOF OF THEOREM 4
text: Theorem 4 (Funtion value convergence rate). Under the same conditions as those of Theorem 3, the sequence of potential function {Ht}t converges to the limit H∗ at the following rates. 1. If the geometry parameter θ ∈ ( 32 ,∞), then Ht ↓ H ∗ super-linearly as
Ht −H∗ ≤ O ( exp ( − (2θ
3
) t−t0 2 )) , ∀t ≥ t0; (6)
2. If the geometry parameter θ = 32 , then Ht ↓ H ∗ linearly as
Ht −H∗ ≤ (1 + C3/20 )− t−t0 2 , ∀t ≥ t0; (7)
3. If the geometry parameter θ ∈ (1, 32 ), then Ht ↓ H ∗ sub-linearly as Ht −H∗ ≤ O ( (t− t0)− 2θ 3−2θ ) , ∀t ≥ t0. (8)
Proof. Equation (31) implies that there exists t0 ∈ N+ such that for any t ≥ t0,
ϕ′(Ht −H∗)−1 = c−1/θ(Ht −H∗)1/θ ≤ (4L22κ2
L1 + L2
) ‖xt−1 − xt−2‖2 + ( 10L2κ 3 + 24L32κ
L21 +
1
2ηx
) ‖xt − xt−1‖2 (35)
(i) ≤ (4L22 L1 + L2κ −2 )(Ht−2 −Ht−1 L2 )2/3 + ( 10L2κ+ 24L32 L21κ + 1 2ηxκ2 )(Ht−1 −Ht L2 )2/3 where (i) uses proposition 2.
Defining dt := Ht − H∗, C1 := c1/θL−2/32 ( 4L22 L1 + L2κ −2 ) , C2 := c1/θL −2/3 2 ( 10L2κ+ 24L32 L21κ + 12ηxκ2 ) , and C0= 3 √ 2c1/θL −2/3 2 ( 10L2κ+ 24L32 L21κ + 4L22 L1 + 12ηxκ2 ) , the above inequality further becomes
d 1/θ t ≤C1 ( dt−2 − dt−1 )2/3 + C2 ( dt−1 − dt )2/3 (36)
≤2 max(C1, C2) [1
2
( dt−2 − dt−1 )2/3 + 1
2
( dt−1 − dt )2/3] (i)
≤2 max(C1, C2) [1
2 (dt−2 − dt)
]2/3 (ii) ≤ C0(dt−2 − dt)2/3 (37)
where (i) applies Jensen’s inequality to the concave function ξ(s) = s2/3, and (ii) uses the inequality that 21/3 max(C1, C2) ≤ C0. Next, we prove the convergence rates case by case.
(Case 1) If θ ∈ ( 32 ,+∞), since dt ≥ 0, eq. (36) implies that for t ≥ t0,
dt ≤Cθ0d 2θ/3 t−2 ,
which is equivalent to that
C 3θ
2θ−3 0 dt ≤
[ C 3θ 2θ−3 0 dt−2 ]2θ/3 (38)
Since dt ↓ 0, C 3θ 2θ−3 0 dt0 ≤ e−1 for sufficiently large t0 ∈ N+. Hence, eq. (38) implies that for any k ∈ N+
C 3θ
2θ−3 0 d2k+t0 ≤
[ C 3θ 2θ−3 0 dt0 ][(2θ/3)k] ≤ exp [− (2θ 3 )k] .
Hence,
d2k+t0+1 ≤ d2k+t0 ≤ C − 3θ2θ−3 0 exp [ − (2θ
3 )k] Note that θ ∈ ( 32 ,+∞) implies that 2θ 3 > 1, and thus the inequality above implies that Ht ↓ H
∗ at the super-linear rate given by eq. (6).
(Case 2) If θ = 32 , eq. (37) implies that for t ≥ t0,
dt ≤ (1 + C3/20 )−1dt−2. (39)
Note that dt0 ≤ 1 for sufficiently large t0. Therefore, dt ↓ 0 (i.e., H(zt) ↓ H∗) at the linear rate given by eq. (7).
(Case 3) If θ ∈ (1, 32 ), consider the following two subcases.
If dt−2 ≤ 2dt, denote ψ(s) = 2θ3−2θ s 1− 32θ , then for any t ≥ t0,
ψ(dt)− ψ(dt−2) = ∫ dt−2 dt −ψ′(s)ds = ∫ dt−2 dt s− 3 2θ ds (i) ≥ d− 3 2θ t−2 (dt−2 − dt)
(ii)
≥C− 3 2
0 ( dt dt−2 ) 3 2θ (iii) ≥ (2C0)− 3 2 (40)
where (i) uses dt ≤ dt−2, and − 32 (1− θ) < 0, (ii) uses the following inequality implied by eq. (37), and (iii) uses dtdt−2 ≥ 1 2 and 3 2θ ∈ ( 1, 32 ) .
If dt−2 > 2dt, then for any t ≥ t0,
ψ(dt)− ψ(dt−2) = 2θ
3− 2θ (d
1− 32θ t − d 1− 32θ t−2 ) ≥ 2θ 3− 2θ [ d 1− 32θ t − (2dt)1− 3 2θ ] ≥ 2θ ( 1− 21− 32θ ) 3− 2θ d 1− 32θ t ≥ (2C0)− 3 2 . (41)
where we use 1 − 32θ ∈ ( − 12 , 0 ) , 2θ3−2θ > 0 and dt ≤ dt0 ≤ (2C0) 3θ 3−2θ
[ 2θ ( 1−21− 3 2θ ) 3−2θ ] 2θ 3−2θ for
sufficiently large t0 ∈ N+.
Since at least one of eqs. (40) & (41) holds, we have ψ(dt)− ψ(dt−2) ≥ (2C0)− 3 2 . Hence,
ψ(d2k+t0+1) ≥ ψ(d2k+t0) ≥ ψ(dt0) + k(2C0)− 3 2 ≥ k(2C0)− 3 2 ; k ∈ N,
which implies that ψ(dt) ≥ t−t02 (2C0) − 32 By substituing the definition of ψ, the inequality above implies that H(zt) ↓ H∗ in a sub-linear rate given by eq. (8).

heading: G PROOF OF THEOREM 5
text: Theorem 5 (Parameter convergence rate). Under the same conditions as those of Theorem 3, the sequences {xt, yt}t generated by Cubic-GDA converge to their limits x∗, y∗(x∗) respectively at the following rates.
1. If the geometry parameter θ ∈ ( 32 ,∞), then (xt, yt)→ (x ∗, y∗(x∗)) super-linearly as
max { ‖xt − x∗‖, ‖yt − y∗(x∗)‖ } ≤ O ( exp ( − 1
3 (2θ 3 ) t−t0 2 −1)) , ∀t ≥ t0; (9)
2. If the geometry parameter θ = 32 , then (xt, yt)→ (x ∗, y∗(x∗)) linearly as
max { ‖xt − x∗‖, ‖yt − y∗(x∗)‖ } ≤ O ( (1 + C 3/2 0 ) − t−t02 ) , ∀t ≥ t0; (10)
3. If the geometry parameter θ ∈ (1, 32 ), then (xt, yt)→ (x ∗, y∗(x∗)) sub-linearly as ‖xt − x∗‖ ≤ O ( (t− t0)− 2(θ−1) 3−2θ ) , ‖yt − y∗(xt)‖ ≤ O ( (t− t0)− 2θ 3(3−2θ) ) , ∀t ≥ t0. (11)
Proof. Notice that eq. (34) still holds after increasing t0, i.e., for T ≥ t ≥ t0 and large enough C such that 23C
√ 4L22κ 2
L1 + L2, 2 3C
√ 10L2κ3 + 24L32κ
L21 + 12ηx <
κ 3 √ L2
3 , we have
κ 3 √ L2
3 T−1∑ s=t ‖xs+1 − xs‖ ≤ C2c1/θ 3(1− 1/θ) (Ht −H∗)1−1/θ
+ κ 3 √ L2
3
[ ‖xt−1 − xt−2‖+ 2‖xt − xt−1‖ ] < +∞. (42)
Proposition 2 implies that
‖xt − xt−1‖ ≤ L−1/32 κ−1(Ht−1 −Ht)1/3 (i) ≤ L−1/32 κ−1(Ht−1 −H∗)1/3, (43)
where (i) uses Ht−1 ≥ Ht ≥ H∗. Therefore, for t ≥ t0, eqs. (42) & (43) imply that
‖xt − x∗‖ ≤ lim sup T→∞ T−1∑ s=t ‖xs+1 − xs‖
≤ C 2c1/θ
κ 3 √ L2(1− 1/θ)
(Ht −H∗)1−1/θ + [ (Ht−2 −H∗)1/3 + 2(Ht−1 −H∗)1/3 ] (44)
Next, we discuss case by case. (Case 1) If θ ∈ (
3 2 ,+∞), then ‖xt − x∗‖ ≤O [ (Ht−2 −H∗)1/3 + (Ht−1 −H∗)1/3 + (Ht −H∗)1/3 ] (45)
≤O ( exp [ − 1
3 (2θ 3 )(t−t0)/2−1]) where the two ≤ use eqs. (44) & (6) respectively. Hence,
‖yt − y∗(xt)‖ ≤‖yt − y∗(xt−1)‖+ ‖y∗(xt−1)− y∗(xt)‖ (i)
≤L2 L1 ‖xt−1 − xt−2‖2 + κ‖xt − xt−1‖ (46)
(ii) ≤O [ (Ht−2 −H∗)2/3 + (Ht−1 −H∗)1/3 ] (47)
≤O ( exp [ − 1
3 (2θ 3 )(t−t0−2)] + exp [ − 1 3 (2θ 3 )(t−t0−1)/2]) ≤O ( exp [ − 1
3 (2θ 3 )(t−t0−1)/2]) ,
where (i) uses eq. (19) and item 1 of Proposition 1, (ii) uses eq. (43) and (iii) uses eq. (6).
(Case 2) If θ = 32 , then the proof is similar to that of Case 2, and eqs. (45) & (47) still hold. The only difference is to use the convergence rate of Ht −H∗ given by eq. (7) instead of eq. (6). (Case 3) If θ ∈ (1, 32 ), then similar to the proof of Case 2, we obtain from eq. (44) that
‖xt − x∗‖ ≤O [ (Ht−2 −H∗)1−1/θ + (Ht−1 −H∗)1−1/θ + (Ht −H∗)1−1/θ ] ≤O ( (t− t0)− 2(θ−1) 3−2θ ) ,
where the two ≤ use eqs. (43) & (6) respectively. Then, as eq. (47) still holds, we have ‖yt − y∗(xt)‖ ≤ O ( (t− t0)− 2θ 3(3−2θ) ) .

Review summaries:
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.   Under 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. 

 In 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. 

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. The 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.  The method is proved to converge to second-order stationary point, under standard assumptions.