Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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? 

2. The theory of this paper is developed under a group of assumptions. Could the author give more justifications on the practicality of the assumptions?

3. The paper is generally clear and well-written. 

questions: See "Strengths and Weaknesses"
limitations: See "Strengths and Weaknesses"
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. 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.
2.  They are the first one to study convergence to SSP for minimax optimization problems without convex-concave assumptions, which is novel.

Weaknesses:
1. 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.

questions: Question:
1. How good is the proposed algorithm and the corresponding rate? Are there any lower complexity bounds for the problem of interest?

Minor comments:
1. Some theorems look a bit complicated, maybe the authors could consider using more $\tilde{O}$ to hide log factors.
2. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

However 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.
strengths_and_weaknesses: *Strengths*
1. Clean idea of adapting known second-order algorithms and results in nonconvex optimization to nonconvex-stronglyconcave setting.
2. Great presentation of the main ideas of the algorithm and the proof.
3. Comprehensive presentation of the run-time and space complexities of the algorithms
4. Provides an inexact method improving the run-time and space complexities of MCN by 
5. Some experimental evaluation
6. Even though I didn’t read the carefully proof, the theoretical results passes spot checks

*Weaknesses*
1. Complicated multi-loop/multi-procedure algorithm
2. Limited novelty in the algorithm, but this shouldn’t be a reason for not accepting
3. There are a few concerns with the experimental evaluation (see below)
4. Missing too many prior work on nonconvex-concave and non convex-strongly-concave optimization (see below) 

*Final*

I appreciate the discussion with the authors. I keep my score the same.
questions: 1. Please explain why the Algorithm 4 can’t be used in lieu of Algorithm 5 in IMCN
2. 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.
3. In domain adaptation experiments, can the authors also plot the final metrics for the tasks?
4. Please run the experiments over multiple random initialization and then provide mean and error bars in the plot.
5. Please summarize and cite the past work as given in [21] and all the follow up works

Minor:

5. Is "unexpected FSP" a standard usage? Should you replace all "unexpected FSP" with “strict saddle point”?
6. 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
1. Extending to nonconvex-concave setting
2. Simplifying the algorithm to fewer loops and fewer sub-procedures
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

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

strengths_and_weaknesses: Strength:

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

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

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

The presentation of this work is considered clear. This work will add value to the optimization community.


Weakness:

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

======

After 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.
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? 

(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.
review_title: null

Meta-review: metareview: This paper studies the minimax optimization problem with smooth objective function, where the objective function $f(x,y)$ is assumed to be  strongly concave in $y$ but in general nonconvex in $x$. In comparison to prior non-asymptotic results that mostly focused on finding first-order stationary points, this paper takes an important step further by showing how to find a second-order stationary point with non-asymptotic convergence guarantees. Although the algorithm design herein is somewhat straightforward (i.e., it is accomplished via a simple combination of accelerated gradient methods and cubic regularized newton methods), the analysis for inexact MCN contains sufficient novelty.  As a result, I recommend acceptance of this paper.  
confidence: Certain
Decision: Accept