Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
Authors: Luo Luo
Yujun Li
Cheng Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Minimax optimization
Second-order optimization
Cubic regularization

Abstract: We study the smooth minimax optimization problem $\min_{\bf x}\max_{\bf y} f({\bf x},{\bf y})$, where $f$ is $\ell$-smooth, strongly-concave in ${\bf y}$ but possibly nonconvex in ${\bf x}$. Most of existing works focus on finding the first-order stationary point of the function $f({\bf x},{\bf y})$ or its primal function $P({\bf x})\triangleq \max_{\bf y} f({\bf x},{\bf y})$, but few of them focus on achieving the second-order stationary point, which is essential to nonconvex problems. In this paper, we propose a novel approach for minimax optimization, called Minimax Cubic Newton (MCN), which could find an ${\mathcal O}\left(\varepsilon,\kappa^{1.5}\sqrt{\rho\varepsilon}\right)$-second-order stationary point of $P({\bf x})$ with calling ${\mathcal O}\left(\kappa^{1.5}\sqrt{\rho}\varepsilon^{-1.5}\right)$ times of second-order oracles and $\tilde{\mathcal O}\left(\kappa^{2}\sqrt{\rho}\varepsilon^{-1.5}\right)$ times of first-order oracles, where $\kappa$ is the condition number and $\rho$ is the Lipschitz continuous constant for the Hessian of $f({\bf x},{\bf y})$. In addition, we propose an inexact variant of MCN for high-dimensional problems to avoid calling the expensive second-order oracles. Instead, our method solves the cubic sub-problem inexactly via gradient descent and matrix Chebyshev expansion. This strategy still obtains the desired approximate second-order stationary point with high probability but only requires $\tilde{\mathcal O}\left(\kappa^{1.5}\ell\varepsilon^{-2}\right)$ Hessian-vector oracle calls and $\tilde{\mathcal O}\left(\kappa^{2}\sqrt{\rho}\varepsilon^{-1.5}\right)$ first-order oracle calls. To the best of our knowledge, this is the first work that considers the non-asymptotic convergence behavior of finding second-order stationary points for minimax problems without the convex-concave assumptions.

Finding Second-Order Stationary Points in Nonconvex-Stronly--oncvee Minimax Optimization
Luo Luo
Yujun Li Noah's 's Ark Lab Huawei Technologies Co., Ltd.
School of Data Science
Fudan University
luoluo&fudan .du..
Jjynjunn@huaweiiccom com
Cheng Chen'
School of Physical and Mathematical Sciences Nanyang Technological University cheng. chen@ntu. edu. sg
Abstract
We study the smooth minimax optimization problem minx maxy [xx, y), where I is E-smooth, strongly-concave in but possibly nonconvex in x. Most existing works focus on finding the first-order stationary points of the function f(x, its primal function P(x) A maxy f(x, y), but few of them focus on achieving second-order stationary points. In this paper, we propose a novel approach for minimax optimization, called Minimax Cubic Newton (MCN), which could find an (s, k2.5 V J-second-order stationary point of P(x) with calling Ok... Vp= times of second-order oracles and Ó( vPe-1.5) times of first- order oracles, where & is the condition number and p is the Lipschitz continuous constant for the Hessian of [(x. y). In addition, we propose inexact variant of MCN for high-dimensional problems to avoid calling expensive second-order oracles. Instead, our method solves the cubic sub- broblerolem inexactly via gradient descent and matrix Chebyshev expansion. This strategy still obtains the desired approximate second-order stationary point with high probability but only requires 1.5) first-order oracle
(x Hessian-vector oracle calls and Ó(s² Vpe 1.5) calls. To the best of our knowledge, this is the first work that considers the non- asymptotic convergence behavior of finding second-orde stationary points for minimax problems without the convex-concanl assumptions.
Introduction
We consider minimax optimization of the form
min max f(x,)) y); xERda yERdv
(1)
where f(x,y y) is E-smooth, j-strrongyy-coomave y, but possibly nonconvex in Problem also be written as
1 can
& max f(x,)) yER"s
min X
P(x)
(2)
This framework covers wide range of applications machine learning such as regularized GAN reinforcement learning (3I], domain adaptation
32
[ and adversarial training [35]
'The corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Most recent works focus on finding an E o-first-order stationary point (FSP) of P(x). Lin et al. 20 showed that the vanilla gradient descent ascent (GDA) method could obtain an E-FSP with O( + x) first-order oracle calls. This complexity can be reduced to Ô (Vile-2 by proximal iteration algorithms [2I]. which matches the gradient oracle lower bound for finding E-FSP of P(x)
44 The theory of first-order optimization for problem (T) has also been studied in
stochastic settings [15 20 24! All !o and the block-wise setting 2 However, the approximate
FSP obtained by these algorithms cannot guarantee the local optimality since the primal function P(x) could be nonconvex.
In this paper. we focus on finding a second-order stationary point (SSP) of P(x) to capture the 26]. Inspired by the success of second-order optimization in nonconvex B8 E5]. we propose novel method, called Minimax Cubic Newton (MCN), which runs cubic Newton update on x and maximizes the objective on y alternatively. This iteration scheme avoids getting stuck at an unexpected FSP. Specifically, we show MCN will converge to an (E, vpe --SSP of P(x) with OR vpe- L.5) number of iterations, where is the condition number and p is the Lipschitz continuous constant of 22 fxx, For high- dimensional problems, we also propose an efficient algorithm, called Inexact Minimax Cubic Newton (IMCN), which avoids the expensive second-order oracle calls. IMCN approximates the sccond-order information by matrix Chebyshev polynomial and solves the cubic regularized sub-problem inexactly. only requires (1s1.5
local optimal properties [S
minimization M 14
18 [2
28
Hessian- vector oracle calls and Ô Ó yps 1.5) first-order oracle calls
to find an (s, 1c 1.5 /pE -SSP. Under mild strict saddle condition 6 10
)
K6
37
the approximate
SSP of P(x) implies an approximate local minimax point of f(xx y) defined by Jin et al. [17], which successfully characterizes the local optimality for problem ( To the best of our knowledge, this is the first work that considers non-asymptotic convergence behavior of finding SSP for minimax problems without
coneevee assumptions. We also conduct experiments on both synthetic function and the real application to validate our theoretical analysis. The empirical results show that the proposed algorithms significantly outperform the GDA method.
In a concurrent work, Chen et al. 7 also studied Problem I and proposed Cubic-GDA which is similar to our MCN algorithm. MCN has advantage on complexity of first-order oracles by factor of VK since Cubic-GDA adopts GD to update y while MCN uses AGD instead. Chen et al. ? mentioned that the cubic sab-problem can be efficiently solved by gradient-basee they did not provide theoretical analysis for this inexact variant, which is more practical in high dimensional case. As comparison, we provide the complexity of both Hessian- -eector oracles and first-order oracles of our inexact algorithm IMCN.
algorithms, but
2
Preliminaries
This section first presents the notations and assumptions for our settings. Then we introduce the background of local optimality for minimax optimization and some basic algorithms.
2.1 Notations and Assumptions
For twice differentiable function f(x, y), its partial gradients with respect to x and y are denoted
as V. v.f(x,)) y) and V fx, y) respectively. Its Hessian matrix at point (x,y) can be partitioned as v²f(x,y) = IV2 znn (x. y). y); V2 fxx y), v2 fx, y)l, where V2. fx, E Rd xds, 2 fx,,) E Rdd V2 (x,
Rd, and V2 I y) E Rdyxdd, We also denote (x,,)) - fx. y) if V fxx,())) y) is invertible.
H(x,y) (x
Given symmetric matrix A. denote Amin (A) the smallest eigenvalue of A. We use ||-11p to denote the spectral norm of matrices and Euclidean norm of vectors. We also denote the closed Euclidean ball with radius and center x" B(x*,7) r) = {x ||x x1112 I r]. Additionally, we use notation (-) to hide logarithmic terms in the complexity.
We suppose the objective function y(x.y) of Problem 1 satisfies the following assumptions. Assumption 1. The function f(x, y) has l- L-ipscchizz gradients, i.e., there exists a constant 0 such that fxx, - y.y' Rdv
< e ||x x²1 + Ily y'1l)) for any x,x x' IRda and

---

Assumption 2. The function f(x,y) y) has p-Lipschitz Hessian, i.e., there exists constant > 0 such that f(x,(x V2 f2' y')l2 S p² (|xx x112 lly y'122 for any x, x' E R and y.y's E Rdy.
Assumption 3. The function y(x, ) is p-strongly-concave in y, i.e., there exists a constant >> 0 such that (x, S Vx,,))) (')- lyy f0 anyoorayy2 E Rd and y.d. E Rdy,
Assumption 4. The function P(x) maxyeR f yxx satisfies P - infxer== P(x) -00.
Definition 1. Under Assumption and we define the condition number of yxx K 2 e/p.
The assumptions of Lipschitz continuous gradient and grongly-concavinn on f indicate that the primal function P(x) maxyER* f(x.y) is well-defined and has Lipschitz continuous gradients as shown in Lemma
Lemma 1 20 Lemma 4.31). Suppose the objective function f satisfies Assumptions and
then the primal function P(x) & maXyeR*v y) has (K 1)e-Lipschitz continuous gradients.
Additionally, the function y (x) arg yany, fxx,y defined and r-Lipschitz. We also
have P(xx = Vx)x)
Now give the definitions of s-FSP and (s, -SSPP follows.
Definition 2. Suppose the function yx satisfies Assumption Mand then call E-FSP of P(x) if P 2 S E.
Definition Suppose the function f(x. y) satisfies Assumption and then we call x is an (5,6 P(x) if (()) S and P2 -51.
The following two lemmas provide the closed form of 2 (x)) and its Lipschitz continuity.
Lemma 2 ((44). Suppose the function f(x, satisfies Assumption and We use the definition of (x) in Lemmal then it holds that P²P( = H(x,y"(x))
Lemma 3. Under assumptions of Lerma we have /²)((x) V*P(x)]1 < <4V2x'p x'l22 for any x and x' in RRd,
2.2 Local Optimality of Minimax Optimization
The Nash equilibrium is widely used the study of convex-concave minimax optimization 40 33
but it is intractable in general when the objective function f(xx y) is nonconvex in nonconcave in y. For the general minimax problem, we introduce the local minimax point [17], which characterizes the optimality in two-player sequential games where players can only change their strategies locally.
R that is strongly- concave in y. point (x", yy) E Rd x Rd, is called a local minimax point of f. if there exists 5u > and a function satisfying h(5) > 0 as + O, such that for any ō E (0, 56), x E B(x", ((()) and y E RRdy we have
Definition 4 (177) Given a differentiable function f(x,y) Rd x Rdd
1(x",) S f(x",y)) max f(x,y'). y'ERdy
(3)
Remark 1. The definition of local minimax point for general nonconvex-noncomm !TZ) only requires 3 holds for any y and y' in neighbour of y", while the constraint on y and y' is unnecessary in our setting since we assume that f fxx,y) is strongly-concave in y.
The local minimax point enjoys the following property.
Lemma 4 (17 Proposition 19]). Suppose f(x, is twice differentiable, then any point (x", y")
satisfying Vf(x","" O, v2 fx",, y²) 2 and H(x" ,²)) > O is local minimax point
of yx.

---

Based on Lemma we introduce the strict-minimax condition on f which is an extension of strict-saddle condition for nonconvex minimization E 10 I6 36 371.
say y(x,y) is (a, (,,) (.)n))-strict--mmnmma for some E R R satisfies at least one of the following three conditions: (a) V fx, ll2 > a; (b) min (H(x,)) y)) < -3; (c) There exists a local minimax point
Definition 5. Under Assumption
! and > 0. 3 0 and 0 if every (x.
(x",y) such that |X x" + 11 y" S2
Note that f is (a, 8, ---ssrict-miniman and there exists a point which is an (e, 6)-SPP of P(x) with sufficient small and 6, then we can find ý R arg maxy f(x. y) via running first-order algorithm to minimize -X and obtain (&. y) which is in neighborhood of yx). In other words, under the strict-minimax condition, we can reduce the task of finding approximate local minimax point of f(x,y y) to finding an approximate SSP of P(x). We will provide the formal statement in Section
2.3 Accelerated Gradient Descent
Nesterov's accelerated gradient descent (AGD) the optimal first-order algorithm for convex optimization [27] (29], which is widely used
Algorithm (h, K, 0)
1: Yo Yo
2: for k 0..... K do
in minimax optimization algorithms [21 39
We describe the details of AGD for smooth and strongly-convex functions in Algorithm
3: ya+1 = ÿK- - (5(k
I
4: Y&+1 = Y++1 0(yk+1 - Ykk
which has the following convergence rate.
5: end for
Lemma (139) Lemma 2)). Running Algo-
6: Output: YK
rithm 7 on a Cn-smooth and un-strongly-coover
objective function h(-)) with parameters 1j = 1/En and
VRR v
produces the output YK satisfying
y²112 S (KR + 1)(1 Jan K Ilyo 1- where y arg min,, h(y) and fig. En/ 4n/Pn- Ph-
2.4 Cubic Regularized Newton
Cubic regularized Newton (CRN) is a classic algorithm for nonconvex minimization 5 It solves the nonconvex minimization problem minx g(x) via the following update rules
360
27 2
38
= arg min Vg(x,) T 2 SCRd
T (xx(x=
Pg ||s| 6
Xx+1 = X, + St.
The CRN method could find an (s, vpg ) JSSP of g(x) with (VP 1.5) number of iterations, where Py is the Lipschitz continuous constant of the Hessian of gxx).
3 Minimax Cubic Newton Algorithm
In this section, we propose our minimax cubic Newton algorithm and give its convergence results.
3.1 Minimax Cubic Newton Method
We present the details of Minimax Cubic Newton (MCN) method in Algorithm 2 In each round, the MCN algorithm performs following steps:
Run AGD as presented in Algorithm D to estimate y: RJ yx,) = arg max, (x),
Compute the inexact first-order and second-order information of P at x, as
P(xx) g: V.J(x,, y+) and 22P(x,) ~ H. H().,
Solve the following cubie regularized problem
M |s1 g, s+ H
1
S arg min Rdz
(4)
6

---

The expressions of and H in the algorithm
Algorithm 2 Minimax Cubic-Newton (MCN)
are inspired from Lemma D and B The smooth-
ness of P()) and 42 P(x) allow the total complexity of AGD iteration of the algorithm has the desired upper bound. Our theoreti-
1: Input: Xg E R Y-1 0, T, {Kil
1t= E.
2: for = =0,.. T do
3: Yr = AGD - -x(xxx y,,,,,,, Kr Z:
vK-1
cal analysis show the termination condition in Line 7 of Algorithm more than O(x pe 1.5) number of itera- tions. We also show that small || will lead to a desired approximate second-order sta- tionary point of P(x). Hence. using AGD to optimize f(x + y) with respect to gen- erates approximate local minimax point of y).
VR+1
2 can be attained in
4: ge = vaf(Xr, Vr), H = Hxx;, Y:)
5: of arg min gi + 1 H 6 || sE
H,S
6: if || ll S 2 V Ve/M then break
7: X++1 X + ss
8: end for
9: Output: & Xx 8
3.2 Complexity Analysis for MCN
In this section, we let M 2/2x² p for MCN. Our analysis for MCN algorithm contains three parts:
1. We follow Tripuraneni et al. 38 's idea to show that our algorithm with sufficient accurate gradient and Hessian estimator of P requires more than T = O (1.1.5 Vps -15) rounds of iterations achieve an (c, x1.5 Vpe -SSP of P(x).
2. We prove the AGD step in line 3 requires at most Ô (R² VP= gradient calls in total.
3. The last part shows we can achieve an approximate local minimax point of f(x, from an (e,5 Vp -second-order stationary point of P(x) under strict-saddle condition.
Cubic Newton Iteration on P(x) The procedure of our Algorithm 2 can be regarded as applying cubic Newton method to minimize nonconvex function P(x), but using inexact first-order and second- order information. We consider the following conditions on the inexact gradient and Hessian, which will hold if we run AGD with enough number of iterations.
Assumption 5. Suppose the estimators gi E Rdd and H. E Rd xd, satisfy conditions [[v)(xx) - g: l2 I CyE and P(x)) - Hell2 s CHVMe for some C. > and Cи > O.
The following lemma implies the analysis of MCN algorithm only needs to focus on the case of each || is large, otherwise we have already find x which desired approximate SSP of P(x). Lemma 6. Under Assumption 5 with Cg = 1/192 and Cи 1/48, if x from Algorithm is not an (e, v M -SSP of P(x), we have |s ll 1 /
By Lemma 6 we can show that MCN with sufficient accurate gradient and Hessian estimators can find an (e, V ME) -SSP of Pxx) with T O Vpe-1.3) number of iterations follows.
Theorem 1. Under Assumption
we run Algorithu 2 with T = (192(P(x)) ((xx))>*)>>a V -151 +1: and further suppose K, is suffictent large that results ge and H. satisfy Assumption 5 with
C2 1/192 and Cи = 1/48. Then the output & is (c, ) -SSP of P(x).
Total Complexity of AGD using yr initialization the t-th round. With such initaaizaaiinn, the following theorem provides the upper bound of total number of gradient calls required by AGD and guarantees that g, and H, in the MCN algorithm satisfy Assumption 5
Note that MCN (Algorithm 2 applies AGD to maximize f by
Theorem 2. Under Assumption and K. 2 log Vu+II (ē
we run Algorithm 2 with Ko = [2 ( (VEE Ily (xm))l2))
K ( for 2 1, where min [Cge/e, CHn.Ce/MNn
and So Then all g, and H, satisfy the condition of Assumption We also have
Σ K. < T+1
2/
3 3log
VK + ē
lly (xo))l log 1) 8x (x5 1)
|| 11 112]
Tga
t=0
1m
5

---

Algorithm 3 Inexact Minimax Cubic-Newton
Algorithm 4 Cubic-Solver
1: Input: Xo E RR y-1
0, T. {Ki)
1: Input: g, H, K((,
1//FE11
2: if [glll 2 1, /2/M then
2: ck VIy Va/ct1
3: for 0,... do
Hg
g H'g
2 2|/l|
3: R M llgl
4: Y: AGD( f(xe, ), ve-1, Ke, vE-1)
M ligll
M
VR+I
5: g: y1)(
Rog/ ||g||2
6: Ze - (V (Xe, yt) + 2 1
else
7: Compute H, as equation 5
Su = 0, 01 = 1/(2LL)
(st, Cubj=Cubi-Solvvrr g. H o, (e,
7: g g oc for Uniform(s*1)
9:
X141 X. +
10:
if A.
128 V / then
1
8:
for k 0.... Ke,,, 8') do
11:
$ = Sinal-Cubic- Sabbe-Solverrgg. E),E)
9: Sk+1 Sx n (8 + Hss + T [1
M
12:
X++1 =x S
10: end for
13:
break
14:
end if
11: $ == BK(c.5))
15:
end for
12: end if
16:
Output: x X1+1
13: Output: 8 and =g 2 H&
||
Combining Theorem | and Theorem 2 we can obtain the total number of gradient oracle calls, Hessian (inverse) oracle calls and exact cubic sub-problem solver calls follows.
Corollary 1. Under Assumption
4 running Algorithm with T (12)) -P) Me'-13 +1, 1o-12v log ( wi+i [|y*(x)) and K,= // log
/K+1 (5' + [|st-111))) for t 2 I, where e'= min (C,e' /e,CHv CHCCCMMM Me'MMee = and 2.55, then the output & is k1.5 VpE -SSPP
of P(x) and the number of gradiens oracle calls is at most (I² vpe Vpe-1.3). The total number of Hessian (inverse) oracle calls and exact cubic sub-problen solver calls is at most O (vpxl.5--1) -15).
Note that MCN method needs to construct the Hessian estimator H, H(x,, yr) and solves the cubic regularized sub-problem in each round. Constructing H. requires calling the second-order oracle at (x, and taking O [d + dz + dy flops for matrix multiplication and inversion. Solving sub-problem 4 requires O (d)) flops for matrix factorization inversion [5] Hence, besides the gradient calls from AGD step, MCN requires O (d + de) time complexity each round and its space complexity is O (de + d)).
Approximate Local Minimax Point Under the strict-minimax condition, can find an approxi- mate local minimax point by performing an additional AGD procedure on the output of MCN.
Corollary 2. Suppose fxx y) is (a, (r))sstrct-mininne and satisfies Assumption 4 Let & be
the output of running Algorithm 2 with the setting of Corollary Aand min (a/3, 8
//K833 p)
Let ý = AGGD - (xx, Yt, K, SK-1) where t. corresponds to the last iteration of Algorithm
such that x = X; + st and K- = v log ( mmn a 26 exists a local minimax point (x",y) of yxx, such that ||x* x112 + Ily - -112 < 72.
+ 2:T / 37 ))) Then there
4 Inexact Minimax Cubic Newton Algorithm
In this section, we proposed an efficient algorithm called inexact minimax cubic Newton (IMCN), which avoids any operation related to the second-order oracle and only requires Ô 1.2.3 2)
Hessian-vector product calls and Ô (x2 ppe-1.55 gradient calls in total to find (e. k1.55 pps) -SSP of Pxx). Since the Hessian-vector products can be computed as fast as gradients much more efficient than MCN in high- high-dimensional cases.
30 33 IMCN is

---

We present the details of IMCN in Algorithm Un- like MCN which solves problem
Algorithm 5
4 exactly. IMCN
Input: g. H.
uses gradient-based cubic sub-problem solver (Algo-
rithm A
to compute
2: = 0, =1 1/(00)
for 0,. ..... do
M ||
St arg min (s) A gi SER4
2 H.S HH
4: if ||g: 2|l| S < then break
S1+1 St 1/g:
If the condition in line 10 of Algorithm holds, the point x +5द should be desired approximate second-
6: ---1 g + Hs + M
|| 1l2 Sc+1
end for
order stationary point. Due to St is hard to obtain, we introduce additional gradient descent steps (Algo- rithm 5 to approximate it by å and use x $ as the final output.
8: Output:
The design and the convergence analysis of IMCN is more challenging than existing inexact cubic
Newton algorithms for minimization problems 18 3 since the Hessian estimator in IMCN has more complicated structure. To address this issue, we approximate the Hessian V2 V²P(xx) by He as
H = V2zJ(x,. + my Nt) fx..
(5)
where C, 32 I+ 1 ΣK=
C2 E (Z.) and Z. 14
V fo
1 Here Tx(-) is
the matrix Chebyshev polynomials (shown in Section 4.1 leading to C, ~ - (V
uy (x. yz) Note
that we never construct matrix H, explicitly in implementation because all operations related to H, can be reduced to compute Hessian-vector products, which avoid any second-order oracle calls or matrix factorizatton/inversio..
Then we provide the convergence analysis for the IMCN algorithm. Throughout this section, we let 2né and M = 4v/xxpp p be the Lipschitz continuous constants of Px)) and P()(z). We suppose S I.2 / /M, otherwise, the second-order condition V2 ł - - always holds and we only need use gradient methods 200 21 to find first-order stationary point.
4.1 Approximating Hessian by Matrix Chebyshev Polynomials
We first show the error bound of matrix inverse approximation via matrix Chebyshev polynomials. Lemma Suppose symmetric matrix X E IRdxd satisfies μ 3 X 3 I'I with < p S 1,
|X- - - ERE CP (Z))))) S /e
2/(VeTpl + 1)) K' where
then we have
VeE
Z' F-a X
E' 1). Ck VEE +1 2
and T-(-) are matrix Chebyshev polynomials 2 [W/EE-
with To(Z') = I, (Z')) Z' and Tx ) = 2 (Z') for k 2 2.
Based on Lemma we can bound the approximation error of the Hessian estimator H, as follows. Lemma 8. Using the notation of Algorithm we have
2 (22P(x))) -Hell S 3px2 VN 1(1
K:/2
-y--1-y"(x:)l + xe
2 K"
VK
Lemma 8 means using AGD with K, = O /K
(V = = and the number of terms for Chebyshev polynomials with K' = O (VRlog(nd/HH)) = (vK) could achieve He with P[x))(x)> Hall2 & εн for any ен > 0.
In the implementation of IMCN, all operations related to H. can be viewed computing Hessian- vector products. Actually, we can obtain H,u' with O(K') Ō(vk) Hessian-vector calls for any u' E 1dd= which avoids O (d2 + dt) space to keep Hessian matrices. The detailed implementa- tion presented in Appendix
Rigorously speaking, the term log(Ily:-1 - (xx))la) also should be considered into the total complexity, which will be discussed in later sections.
7

---

4.2 Complexity Analysis for IMCN
The IMCN method calls gradient- based sub-problem solver (Algorithm 4 in each iteration
to optimize the following
cubic regularized problem 4 [8
1 8 H +
M
min ms(s) - ge s SER**
||
(6)
2
6
It requires at most K({E, 8)) - Ae (log (v ) + +lo
(
))) number of iterations to achieve
an approximate solution with enough accuracy. The detailed analysis for the complexity of Algo- rithm 4 is deferred to appendix [
Then we bound the total number of iterations for Algorithm 5
Theorem 3. Running Algorithm 3 with C. = 1/4, 8' = 8/T, T= [626(P(xx) P*) (rMMMM> 1.5
and sufficient large Ke and K' such that Assumption 5 holds with C. = 1/240 and CH = 1/200. 1 Then the condition D, 2 128
V M in line 11 must hold in no more than T = O (1:1.5 Vpe 1.5) iterations; and the output & is an (e, 2x2.5 VpE )-SPP with probability 1 1
We also bound the number of gradient calls from AGD procedure in Algorithm B as follows. Theorem 4. Under the setting of Theorem we run Algorithm
with
VR+1 log K'=
kl 2min (CHVMM,eeL)
) and K,=
2 log
V++I
lly (xw)lla]
t= 0
2
2 log
|x=I + [|st (| 11)] t t2
where E min {Cge/e, min {CHv Mε, en I. ((pp))))) and
o, then it holds that [(x) ggll2 S CCe, P(x,) - Hellz I min (C,VME,EHL) and
so
T
by (xx)))ll) log (8(x+1)) + 1)1.5 155 8 (n + 1)..5 T || 11
Σ K. ST 1=
log
T
E
TEa
Note that the value of K" Ö(vk) corresponds to the number of Hessian vector calls for each iteration of cubic sub-problem solver (Algorithm and 5). Combining Theorem 3 Theorem and the value of (((,,''). we obtain the main result for Algorithm as follows.
Corollary 3. Under Assumption
if we run Algorithm with C. 1/4, 8' = 5/T. 1
VK+1 2
2min {CHV ME, 36 )
Kf
2 Fog VA+T lly (x0))l2)
t= 0
K'= =
log
and Kr
2
(E + n: 1|
t2
where T
- MMe--1111. Cg 1/240, Cn 1/200. So = 0, E'
e/4 and
غ = min [Cg=/(4L), min (CHN(CeM Me, 3L } then the output & is an (E, Vpp) second-
order stationary point of P(x) with probability 8 and the number of gradient calls is at most Ö (x2 (ps The number of Hessian-vectorr product calls is at most O (x238E-2).
we can also achieve an approximate local minimax point by running AGD based on the & obtained from Algorithm
Following the analysis of Corollary 2
5
Experiments
In this section, we conduct empirical studies for our methods against the classical GDA algorithm 20 on both synthetic problem and real-world application.
5.1
Synthetic Minimax Problem
We construct the following noncomees--tronlyy-oocaee minimax problem:
v2
5z/2
min max f(x, = wx(aa)
+ 31l11
+ x2222
(7)
x yER?
40
2
8

---

where x [21, P2, Fzl form is shown A Appendix (Xo: Yo) = [0. 0,0, 0] [0, 0]
V1. Me]" and w(-) is the W-shaped scalar function
B8 whose exact easy verify that the problem has an striet saddle point at
10-3
GDA
MCN
||PPO>]|>>
10-2
Amin(V'P(x))
GDA
MCN
10-5
P(x)
00.1
GDA
10-7
10-3
MCN
-0.2
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
Time(s)
le-3
Time(s)
1e-3
Time(s)
1c-3
(a) Initial point (1)
(b) Initial point (x)
(c) Initial point (xI,
10
10
GDA
à 10-4
||9Pb>)
10-3
Amin(V?P(x))
MCN
10-10
10-
0,050
GDA
GDA
10-14
10-13
MCN
MCN
0.048
0.5
1.0
0.0
0.5
1.0
1.5
0.5
1.0
1.5
Time(s)
le-3
Time(s)
Time(s)
(d) Initial point (2)
(e) Initial point (x)
(l) Initial point (x),
Figure I: We present comparisons of error, gradient norms and Hessian minimum eigenvalues on the synthetic problem. Figure (a), (b) and (c) shows the results with initial point (1). Figure (d), (e) and (f) shows the results with initial point (2).
We conduct experiments on problem with two different initial points
(x1, (110-,110* 10-3, (0,00] and (x2, Y2) = (10, 10,00117 (10,0,1),[(000]]
Notice that problem 7 has an strict saddle point at (Xo. Yo) = ((0, 0. (0,00]]) The initial point (x) is close No) and (x2, far from (Xo, No). We compare the proposed algorithm MCN with GDA. The learning rate of GDA and AGD step in MCN is selected from (c-10-< e (1,5), 21,2,3) }. For MCN method, we choose M 10. We compare the running time against P(x) - P", [|VP(x)]l2 and Amin A (V²)(x)) for two algorithms and plot the results in Figure 0 From the curves corresponding to initial point (2), we observe that both MCN and GDA converge to the minimum when the initial point far from the strict saddle point, but MCN converges much faster than GDA. When the initial point is close the strict saddle point, Figure 4(b) shows that the GDA algorithm gets stuck at the strict saddle point since its Hessian minimum eigenvalue are always negative. However, our MCN algorithm reach the points which have positive Hcssian minimum cigenvalues.
5.2 Domain Adaptation
The Commain-Advesartin Neural Network (DANN) S is classic method to domain adaptation. Suppose the source domain dataset is S = {(a b sample and b, is the corresponding label. The target domain dataset T {aT) /=1 only contains features. Then DANN aims to solve the following nonconvex-stronnly-conee. minimax problem
where a. is the feature vector of the i-th
min max (x1,,, x2) - a L2(x1,)),
[xxx]]ERds yeRdy
Ne (xx;; (x(;a))) ), b$) is the loss of supervised learning and where Lx(X1xx)) Ns
No L2(X1,y)= = No Σ
1 Nr
Ds(h(y; o ((x;aa)))
Dr Dr (hly: (0::::(xx::0 ((x: \|ly|
NT
the domain classification loss. Here + is single-layer neural network of size (28 28) 200 with parameter and / is a two-layer neural network of size 200 x 20 x 10 with parameter x2, followed

---

IMCN
IMCN
IMCN
IMCN
P000
-1
Oracle 1e5
Time(s)
Oracle
1e5
Time(s)
1e3
(a) MNIST to MNIST-m
(b) MNIST to MNIST-m
(c) MNIST-m to MNIST
(d) MNIST-m to MNIST
Figure 2: We present results on DANN model. Figure (a) and (b) show the results of domain adaptation from MNIST to MNIST-m. Figure (c) and (d) show the results of domain adaptation from MNIST-m to MNIST.
by cross entropy loss. We choose the sigmoid function as the activation function for them. With the commonly used logistic loss for L2, we let h(y; 2) = 1/(1 + exp(-y 2)). Ds(2) = log(z) and Dr(=)= log(1 z).
Since the dimension of the minimax problem is quite large, we implement the IMCN algorithm instead of the MCN algorithm for efficiency. We compare IMCN with GDA on the domain adaptation problem between two different datasets: MNIST [9] and MNIST-m [9] Since we do not know the close form of P(x). we estimate the value of P(x) maxy f(x, by AGD procedure. More details about our experimental setup can be found Appendix G.2
We compare IMCN and GDA algorithms via running time and oracle calls and show the results in Figure We run the experiments for five times with different random initialization and report the average results. The oracle calls of GDA only contains gradient while the oracle calls of IMCN contains both gradient and Hessian-vector product. Based on Figure D we observe that IMCN significantly outperforms GDA in both time and oracle comparison. Notice that IMCN requires to call much more gradient/Hcssianvverr vector oracles on y than the gradient oracles on x. These results verify our convergence analysis and show the advantage of proposed algorithm.
6 Conclusions and Future Work
In this paper, we study second-orde optimization methods for nonconnex--trrongyy-oones minimax problems. We have proposed novel algorithm so-called minimax cubic Newton (MCN) which could find an (E, 1..5 yp )-SSP the primal function with O1x2.5 Vpp -1.5) second-order oracle calls and Ö(n² Vpe-1.59 1.5) gradient oracle calls. We also provide an efficient algorithm for high dimensional problem, which avoids accessing second-order oracle and contains Ö(x2258e Hessian-vector oracle calls and Ö(k² ype -1.5) gradient oracle calls. To best of our knowledge, this paper first achieves non-asymptotic convergence result for finding SSP of minimax problem without convex- concave assumption.
There are several interesting problems for future work: (a) The proposed algorithms and analysis require the strongly convexity assumption on y. We would like study how find SSPs for general nonconvex-concave minimax problems,
(b) The upper complexity bounds of proposed algorithms look not optimal. is possible to apply the acceleration techniques to establish more efficient algorithms for our task. (c) The implementations of proposed IMCN still require accessing the Hessian-vecet veecoor oracle. pure first-order algorithms. (d) This paper does not consider the specific structure of the objective function. However, many machine learning models can formulated as minimax problems where the objective functions have finite-sum expectation form. Designing efficient stochastic algorithms for such formulations is an interesting problem to the machine learning community.
interesting to investigate how to find SSPs of our minimax problem by
Acknowledgements
Luo Luo is supported by National Natural Science Foundation of China (No. 62206058) and Shanghai Sailing Program (22YF1402900). Cheng Chen is supported by Singapore Ministry of Education (AcRF) Tier 1 grant RG75/21.
10

---

References
[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In STOC, 2017.
[2] Owe Axelsson. Iterative Solution Methods. Cambridge University Press, 1994.
[3] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. In Advances in Neural Information Processing Systems, pages 3873-3881, 2016.
[4] Yair Carmon and John Duchi. Gradient descent finds the cubic-regularized nonconvex newton step. SIAM Journal on Optimization, 2963):146-2178, 2019.
[5] Coralia Cartis, Nicholas L.M. Gould, and Philippe L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part I: motivation, convergence and numerical results. Mathematical Programming, 127(2))245-295, 2011.
[6] Coralia Cartis, Nicholas L.M. Gould, and Philippe L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part worst-case function-and derivative-evaluation complexity. Mathematical programming, 130(2):295-319, 2011.
[7] Ziyi Chen, Qunwei Li, and Yi Zhou. Escaping saddle points in nonconvex minimax optimization via cubic-regularized gradient descent-ascent. arXiv preprint arXiv:2110.070098, 2021.
[8] Tanner Fiez, Lillian Ratliff, Eric Mazumdar, Evan Faulkner, and Adhyyan Narang. Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games. In NeurIPS, 2021.
[9] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarin training of neural networks. Journal of Machine Learning Research, 17(1):2096 2030, 2016.
[10] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. In COLT, 2015.
[11] Rong Ge, Jason Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In NIPS, 2016.
[12] Zhishuai Guo, Zhuoning Yuan, Yan Yan, and Tianbao Yang. Fast objective & duality gap con- vergence for nonconvex nonconvex-stronglyy ssrooggyy-concve min-max problems. arXiv preprint arXiv:2006.066 2020.
[13] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint arXiv:2 103.02280. 2021.
[14] Filip Hanzely, Nikita Doikov, Yurii Nesterov, and Peter Richtarik. Stochastic subspace cubic newton method. In ICML, 2020.
[15] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-orrer momentum methods from mini to minimax optimization. arXiv preprint vrXiv:2008.08/70, 2020.
[16] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference Machine Learning, pages 1724-1732. PMLR, 2017.
[17] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In ICML, 2020.
[18] Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. In JCML, 2017.
[19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 96(11):2278-233 1998.

---

[20] Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICML, 2020.
[21] Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In COLT, 2020.
[22] Songtao Lu, Meisam Razaviyayn, Bo Yang, Kejun Huang, and Mingyi Hong. Finding second- order stationary points efficiently in smooth nonconvex linearly constrained optimization prob- lems. In NeurIPS, 2020.
[23] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions Signal Processing, 68:3676-3691, 2020.
[24] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic noncomvex--ttronglyyooo
minimax problems. In NeurlPS, 2020.
[25] Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic al- gorithms for finite-sum unbalanced convex-concaye minimax optimization. arXiv preprint arXiv:2106.0176,, 2021.
[26] Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) zero-sum games. arXiv preprint arXiv: 19t::/900.0000 900800038, 2019.
[27] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[28] Yurii Nesterov and Boris T. Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177-22)) 2006.
[29] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate o(1/k²). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[30] Barak A. Pearlmutter. Fast exact multiplication by the Hessian. Neural computation, 6(1): 147-160, 1994.
[31] Shuang Qiu, Zhuoran Yang. Xiaohan Wei, Jieping Ye, and Zhaoran Wang. Single-timescale stochastic nonconvex-conee optimization for smooth nonlinear TD learning. arXiv preprint 10X1: 2020.
[32] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D. Lee. On the convergence and ro- bustness of training GANs with regularized optimal transport. arXiv preprint arXiv: 192.02180..00849, 2018.
[33] Nicol N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation, 14(7):1723, 2002.
[34] Alexander Shapiro. Second-orde derivatives of extremal-value functions and optimality condi- tions for semi-infinite programs. Mathematics of Operations Research, 10(2):207-219) 1985.
[35] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In ICLR, 2018.
[36] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere I: Overview and the geometrie picture. IEEE Transactions on Information Theory, 63(2):853-884, 2016.
[37] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5): 131-11191 2018.
[38] Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. In NewrIPS, 2018.
[39] Yuanhao Wang and Jian Li. Improved algorithms for convex-concave minimax optimization. In NewrIPS, 2020.
12

---

[40] Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridg approach. In ICLR, 2019.
[41] Wenhan Xian, Feihu Huang, Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. NeurIPS, 2021.
[42] Tengyu Xu, Zhe Wang. Yingbin Liang, and H Vincent Poor. Gradient free minimax optimization: Variance reduction and faster convergence. arXiv preprint UrXiv:2006.09361, 2020.
[43] Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax optimization. arXiv preprint arXiv:2006. 14592, 2020.
[44] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex--tronglyyconneee minimax optimization. arXiv preprint arXiv:2103. 2021.
[45] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularization methods. Journal of Machine Learning Reseurch, 20(134): 2019.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "dvudCAtSlYK", "reviewer": "Reviewer_JH7L", "summary": "This is paper studies the problem of finding second-order stationary points (SSP) of Nonconvex-Strongly-Concave (NC-SC) minimax optimizaiton problems. The propose an algorithm called Minimax Cubic Newton (MCN) and show it provably converges to an approximate SSP and provide complexity bounds of calling first and second order oracles. The bounds are in terms of the condition number $\\kappa$, Lipschitz constant of Hessian $\\rho$ and level of stationarity $\\epsilon$. Next, to avoid call expensive second-order oracles, they further propose inexact MCN which only needs the less expensive Hessian-vector oracle. The also provide convergence rate for inexact MCN and finally conducted experiments to show their algorithm is better than GDA.", "questions": "Question:\n1. How good is the proposed algorithm and the corresponding rate? Are there any lower complexity bounds for the problem of interest?\n\nMinor comments:\n1. Some theorems look a bit complicated, maybe the authors could consider using more $\\tilde{O}$ to hide log factors.\n2. It might be better to use a larger font for the figures.", "limitations": "I do not think this paper has any potential negative societal impact. Regarding limitations, please see the weakness part.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The theoretical results are sound and look rigorous. The presentation is clear and easy to read. They also  provide clear intuition of how the results are shown.\n2.  They are the first one to study convergence to SSP for minimax optimization problems without convex-concave assumptions, which is novel.\n\nWeaknesses:\n1. The paper looks not novel enough. The exact MCN algorithm looks pretty natural, it looks like a combination of Accelerated Gradient method for the inner maximization problem and the Cubic Regularized Newton method for the outer minimization problem. The analysis seems also a combination. However, the inexact MCN and its analysis looks novel and interesting to me.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZVBFgeuz-c", "reviewer": "Reviewer_btzP", "summary": "Paper proposes and analyzes algorithms for solving for inexact second-order stationary points of nonconvex-stronglyconcave minimax problem. The first algorithm MCN adapts the known Cubic Newton method for nonconvex minimization for solving the Primal problem. This is done by generalizing the concept of strict-saddle in nonconvex minimization to nonconvex-stronglyconcave minimax problems. Since we don’t have access to gradient and Hessian of the Primal function, MCN approximates them by applying AGD on the maximization variable and the authors theoretically prove that this suffices. \n\nHowever this algorithm still requires matrix inversions due to the complicated Primal Hessian. The second algorithm IMCN approximates the matrix inversion using Hessian vector products and Chebyshev polynomials. Further it uses inexact cubic solver. Authors provide theoretical analysis of the run-time and space complexities of the algorithm and provide some experimental evaluation of their methods.", "questions": "1. Please explain why the Algorithm 4 can’t be used in lieu of Algorithm 5 in IMCN\n2. In the synthetic experiments, it is not clear why we are looking at P(x) - P^* instead of the gradient norm and Hessian minimum eigenvalue.\n3. In domain adaptation experiments, can the authors also plot the final metrics for the tasks?\n4. Please run the experiments over multiple random initialization and then provide mean and error bars in the plot.\n5. Please summarize and cite the past work as given in [21] and all the follow up works\n\nMinor:\n\n5. Is \"unexpected FSP\" a standard usage? Should you replace all \"unexpected FSP\" with “strict saddle point”?\n6. In Thm 1 what is s_t? Not defined yet.", "limitations": "Not a lot of discussion of the limitations of the work. Authors could try to discuss the challenges to the following\n1. Extending to nonconvex-concave setting\n2. Simplifying the algorithm to fewer loops and fewer sub-procedures", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n1. Clean idea of adapting known second-order algorithms and results in nonconvex optimization to nonconvex-stronglyconcave setting.\n2. Great presentation of the main ideas of the algorithm and the proof.\n3. Comprehensive presentation of the run-time and space complexities of the algorithms\n4. Provides an inexact method improving the run-time and space complexities of MCN by \n5. Some experimental evaluation\n6. Even though I didn’t read the carefully proof, the theoretical results passes spot checks\n\n*Weaknesses*\n1. Complicated multi-loop/multi-procedure algorithm\n2. Limited novelty in the algorithm, but this shouldn’t be a reason for not accepting\n3. There are a few concerns with the experimental evaluation (see below)\n4. Missing too many prior work on nonconvex-concave and non convex-strongly-concave optimization (see below) \n\n*Final*\n\nI appreciate the discussion with the authors. I keep my score the same.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GBDxfSPlZW", "reviewer": "Reviewer_byDE", "summary": "This paper mainly studied minimax optimization problem. It proposes an algorithm MCN to find SPP and also provides an algorithm for high dimensional problem. Numerical experiments are also conducted to validate the theory. ", "questions": "See \"Strengths and Weaknesses\"", "limitations": "See \"Strengths and Weaknesses\"", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The paper emphasizes that this is the first work without the convex-concave assumptions. Could you give more comparison with prior literature and explanation on how this is accomplished technically? \n\n2. The theory of this paper is developed under a group of assumptions. Could the author give more justifications on the practicality of the assumptions?\n\n3. The paper is generally clear and well-written. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Dn60wHdjulW", "reviewer": "Reviewer_KK4D", "summary": "This work studies the nonconvex-stronglyconcave minimax optimization and proposed an algorithm called Minimax Cubic-Newton (MCN), which finds an $\\mathcal{O}\\left(\\varepsilon, \\kappa^{1.5} \\sqrt{\\rho \\varepsilon}\\right)$-second-order stationary point of $P(\\mathbf{x}) \\equiv \\max_{\\mathbf{y}\\in \\mathbb{R}^d} f(\\mathbf{x}, \\mathbf{y})$ in a query complexity of $\\mathcal{O}\\left(\\kappa^{1.5} \\sqrt{\\rho} \\varepsilon^{-1.5}\\right)$ of second-order oracle and $\\tilde{\\mathcal{O}}\\left(\\kappa^{2} \\sqrt{\\rho} \\varepsilon^{-1.5}\\right)$ of first-order oracle, where $\\kappa$ is the condition number on $\\mathbf{y}$ and $\\rho$ is the Lipschitz constant of $\\nabla^{2} f(\\mathbf{x}, \\mathbf{y})$. This work also proposed a first-order approximation variant of MCN and finds an approximate second-order stationary point in a reduced query complexity of $\\mathcal{O}\\left(\\kappa^{1.5} \\ell \\varepsilon^{-2}\\right)$ of Hessian-vector oracle and $\\tilde{\\mathcal{O}}\\left(\\kappa^{2} \\sqrt{\\rho} \\varepsilon^{-1.5}\\right)$ first-order oracle.\n\nThe authors also discuss the concurrent work of [7] who also study the nonconvex-strongly-convex minimax problem and propose essentially the identical algorithm called Cubic-GDA, adopting a different output rule, which is helpful for the development of their stochastic Cubic-GDA. Two works have substantially different parts: this work studies the inexact variant of MCN but does not appear in [7], and [7] studies the stochastic setting which does not appear in this work.\n", "questions": "(I) Are there any lower bound arguments or results available, justifying (or negating) the optimality in complexities presented in this work and also the concurrent work [7]? Would the author mind briefly discussing this in your rebuttal at least? \n\n(II) Is the extension to either expectation or finite-sum case straightforward? Some remarks on this would be helpful.", "limitations": "This is a theoretical work and does not pose limitations to my best understanding.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe first part of the analysis relies on the objective function for minimization, $P(x)=\\max_y f(x,y)$, having its first-order and second-order Lipschitz constants specified well in earlier literature [20] [32]. The main complexity result, Corollary 1, provides a result that is of $\\tilde{O}(\\varepsilon^{-1.5})$ in both first-order and second-order query complexities, where I ignored here the $\\kappa$ and $\\rho$ dependencies in the $O(\\cdot)$ and $\\tilde{O}(\\cdot)$. It suffices to combine the complexity analysis of Theorem 1 on cubic regulasization using approximate oracles [36] and also Theorem 2 on fastly achieving this approximation. To be specific, Theorem 1 follows from the analysis of the standard cubic regularised Newton’s method to achieve an $O(\\varepsilon^{-1.5})$ iteration complexity via an approximate gradient and Hessian estimator. Theorem 2 applies Nesterov's AGD to find the total complexity for the ascent steps of $\\tilde{O}(\\varepsilon^{-1.5})$ query complexity. \n\nThis work also details the query complexity, space complexity, and flops involved in the complexity analysis. The author also introduces the concept of strict-minimax property of a nonconvex-stronglyconvex function, which is a nice generalization to the strict-saddle condition in saddle-point escaping literature [10] [16]. This is the first introduction of such a concept to my best knowledge. The mathematical derivations seem solid.\n\nI especially enjoyed reviewing the second part, from which I learned a lot myself. Although the matrix Chebyshev polynomials approximating the inverse Hessian is not new and is ubiquitous in numerical optimization (see, e.g., the blog post \\url{https://francisbach.com/chebyshev-polynomials/}), the introduction of such a method for solving the current problem using first-order oracles and Hessian-vector product oracles is considered innovative. The method for solving the inexact setting is written clearly and organically combined into the problem solution, leading to the complexity of $O(\\varepsilon^{-2})$ of Hessian-vector oracle and $\\tilde{O}(\\varepsilon^{-1.5})$ first-order oracle.\n\nThe presentation of this work is considered clear. This work will add value to the optimization community.\n\n\nWeakness:\n\nThe discussion on the optimality of the method seems unavailable. Consider the case where the function is constant in $y$, the condition number $\\kappa$ on the $y$ variable is equal to 1, and the upper and lower bounds are closely matched, c.f. Carmon et al. (2020), \"Lower bounds for finding stationary points I\". For the general minimax problem, a lower bound argument for finding a second-order stationary point would add strength to this work, even if it is matched by an upper bound only under a nontrivial subset of the problem-dependent regimes. In addition, the discussion on the extension to a stochastic setting (either finite-sum or expectation) seems unavailable. Given the state of affairs, I encourage the authors to satisfactorily address these two points.\n\n======\n\nAfter rebuttal: I acknowledge the contribution of this work and responses during the rebuttal period, and there are some valuable discussions regarding the optimality (and suboptimality) of the provided MCN (and IMCN) methods in general. Hence I decide to raise my rating to 6.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept