Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduced new algorithms for second-order guarantees of nonconvex-strongly concave problems. First, the paper first gave convergence rate guarantees for the general setting; then it gave linear or superlinear convergence rate results under different orders of  Łojasiewicz gradient geometry. 
main_review: To the best of my knowledge, this is one of the very first second-order convergence rate results for nonconvex-strongly concave min-max problems (see another similar paper [1]). Both the results and analysis seem to be good to me. The theoretical contribution is also significant for this area. 

I have the following concerns:

In my understanding, ICLR is a conference that emphasizes relevance to practice. The optimization focus in the machine learning community is developing algorithms that are scalable for large-scale problems. This work seems to only focus on giving the convergence rates but not care about per-iteration cost. In fact, both forming the Jacobian matrix in the algorithm and solving the cubic subproblems exactly are very expensive in the machine learning context. So, I am not sure of the practical relevance of this paper. I hope that the authors can provide approximate optimization steps for the primal variable vector and provide the iteration complexity in terms of first-order oracle (i.e., gradient evaluation and Jacobian-vector product). 

For the results under Łojasiewicz gradient geometry, I hope that the authors can provide some practical cases that satisfy this assumption in the paper, not only just citing some relevant papers. 



[1] Luo, Luo, and Cheng Chen. "Finding Second-Order Stationary Point for Nonconvex-Strongly-Concave Minimax Problem." arXiv preprint arXiv:2110.04814 (2021).






summary_of_the_review: The authors provide the very first second-order convergence rate results for nonconvex-strongly-concave minimax problems. But I believe that the style of the current version is not very suitable for the machine learning community and the ICLR conference as it does not focus on the large scale setting and does not care about practical performance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 
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. 
main_review: Major issues:

1. The key takeaway is that Cubic-GDA converges to a “second-order stationary point” of the envelope function. While it is well-received in nonconvex optimization literature, the authors could explain why such a point is of interest in the context of minimax optimization, i.e., how it is related to the solution of (P). For instance, it appears to have connection with the second-order necessary condition for a local minimax point introduced in (Jin et al. 2020, “What is local optimality in nonconvex-nonconcave minimax optimization?”).  

2. The paper is not very novel in terms of algorithms development cause it basically runs the update of CRN method on the envelope function and reaches its second-order stationary point, which is known for CRN. The only technical challenge is addressing the accuracy required for solving the inner maximization problem. Indeed, this is not very challenging as in the strongly concave case the inner problems can be solved exponentially fast. 

3. The comparisons with related work seem insufficient. I expect the authors to discuss more on current first-order methods for the nonconvex-strongly-concave minimax problems. Also, given that the proposed method is in essence an inexact version of CR on the envelope function, the authors may need to justify why existing results on inexact CR method are not directly applicable.   

4. In Proposition 2, the choice of $\eta_x$ has a very bad dependence on the conditional number (on the order of \kappa^{-7}). This in turn leads to huge constants in most of the convergence results, which could potentially undo the benefit of using second-order methods if the required accuracy is moderate. 

5. The original CR method in (Nesterov and Polyak, 2006) is also shown to behave very well in the local neighborhood of a strict saddle point or a strict local minimum. So I am wondering whether cubic-GDA can retain these desired features or not. 

6. It will be helpful if the authors can include numerical experiments to support the theoretical findings. For instance, it will make a very good point if the authors can come up with a specific example where GDA converges to an undesired stationary point while cubic-GDA succeeds in finding a local minimax solution. 

Minor issues:

1. At the bottom of page 1: “envelop” -> “envelope”.
2. The paper refers to y^*(x) as the minimizer, but it is in fact the maximizer.
3. The authors describe their method as a “GDA-type algorithm”, which is a bit misleading. First of all, there is no gradient descent step. Also, since the update of x requires second-order information, it seems more appropriate to address it as a Newton-type method.
4. Both “Jin et al. 2017a” and “Jin et al. 2017b” point to the same reference. Also, “Jin et al. 2017b” mentioned in the related work on CR seems to be the wrong reference.
summary_of_the_review: I think the paper addresses an interesting problem, but its algorithm development is not very novel. Moreover, the authors need to better explain why achieving such second-order stationary point should be of interest in the context of minimax optimization.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies nonconvex minimax optimization problems and proposes a novel algorithm, called Cubic-GDA, which can escape the strict saddle points and find the second-order stationary points of the nonconvex minimax problem. The paper also provides the global convergence rate of the proposed algorithm and analyzes the convergence property under local nonconvex geometry.  
main_review: Finding second-order stationary points of a nonconvex minimax problem is an interesting and important problem in the optimization area. The proposed algorithm seems intuitive and reasonable with clear motivation. However, the theoretical contributions of the paper are not strong and the empirical study is missing.

My first concern is about the global convergence rate. According to Proposition 2, $\eta_x$ should be $O(\kappa^9)$. Then, the global convergence rate in Theorem 2 shows that cubic-GDA seems to require $O(\kappa^{13.5}\epsilon^{-1.5})$ total iterations to achieve an $\epsilon$-first-order stationary point which satisfies $||\nabla\Phi(x_t)||\leq \epsilon$. Notice that the convergence rate of GDA is only $O(\kappa^2\epsilon^{-2})$ (Lin et. al., 2020). The order of $\kappa$ in the results of Cubic-GDA  is much worse than that of GDA.
Such result is unbearable for ill-conditioned problems (which is very common in real applications).

My second concern is about the way of solving the cubic regularization sub-problem. The paper claims that the cubic regularized sub-problem can be efficiently solved by gradient descent methods (Carmon and Duchi, 2016). However, gradient descent can only achieve a sublinear convergence rate.
Hence, I think it is important to discuss how the inexact minimizer affects the convergence behavior of Cubic-GDA. 
The theoretical analysis of this paper is based on assuming the sub-problem can be solved exactly, which is not reasonable.

My last concern is this paper does not provide any empirical results. The previous two concerns show that the proposed algorithm may converge very slowly. Thus I doubt whether the proposed method can outperform GDA algorithms in real applications. I hope the authors perform some empirical studies to verify the effectiveness of the proposed algorithm. Additionally, it is preferred to conduct experiments to show Cubic-GDA can escape some unexpected suboptimal saddle points that GDA stuck.

Minors:

Do you have any ideas to generalize current results to nonconvex-concave (not strongly-concave) setting?
summary_of_the_review: Pros:
1. The studied problem is interesting and the proposed method is novel.

Cons:
1. Theoretical analysis is on the weak side.
2. No empirical results.

Overall, I recommend to reject this paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper develops Cubic-GDA—the first GDA-type algorithm that can find second-order stationary points in nonconvex minimax optimization, whereas the existing GDA algorithms can only converge to first-order stationary points. The developed algorithm leverages the popular Cubic regularization technique to escape saddle points in nonconvex minimax optimization. 

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.

main_review: This work develops a non-trivial extension of first-order GDA algorithm to second-order algorithms for escaping saddle points in nonconvex minimax optimization. Specifically, the Cubic-GDA algorithm uses gradient ascent to estimate the second-order information of the minimax objective function, and leverages the cubic regularization technique to efficiently escape the strict saddle points.

The paper provides a comprehensive convergence analysis of this algorithm. Including its global convergence properties and convergence rates in general nonconvex minimax optimization, as well as its convergence rates under a broad class of gradient dominant conditions. The analysis is based on a careful characterization of the Jacobian matrix of the minimax objective function and its Lipschitz continuity property (Prop. 1). The key to the analysis is characterization of a special potential function that is proven to be monotonically decreasing (Prop. 2). This is an elegant result that justifies the numerical stability and correctness of the algorithm. 

Under a wide spectrum of gradient dominant conditions, it is proved that Cubic-GDA achieves an orderwise faster convergence rate than the standard GDA. This demonstrates the effectiveness of introducing cubic regularization into nonconvex minimax optimization. This may inspire future developments of second-order minimax optimization algorithms.


The proposed Cubic-GDA algorithm can be viewed as an inexact cubic-regularization algorithm. Can the existing analysis of inexact Cubic regularization be applied here? 

The learning rate $\eta_x$ has a bad dependence of the problem condition number. This seems to be caused by the bounding techniques used in the proof. Is there a way to further reduce the dependence? Note that the GDA studied in (Lin 2020) only has a dependence of $\kappa^2$.

If we apply accelerated gradient descent to solve the strongly concave sub problem, then it may lead to a faster global convergence rate of the algorithm. I suggest the authors add more discussions on this point.




summary_of_the_review: Overall, this paper is nicely written and contains solid theoretical contributions to nonconvex minimax optimization. Given the emerging and growing interests in minimax optimization in the general machine learning community, I recommend accepting this work.

-----------------------------
After reading the other reviews, it seems that the present version indeed consists of a number of issues and is not yet ready for publication. But overall, I feel the paper contributes to analysis and algorithm design for minimax optimization. I have updated my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a second-order cubic regularization type method for an unconstrained min-max problem in which the function is twice continuously differential, strongly concave w.r.t the max decision variable, with Lipschitz continuous first and second derivatives.
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.
main_review: The paper combines gradient ascent-descent techniques with the second-order optimization approach of cubic regularization, leveraging on the preservation of Lipschitz properties of the solution of the max problem, while using only an approximated solution for the strongly concave max problem.
I found the approach interesting and sufficiently innovative. 
The paper is well-written, the mathematical  writing and analysis are nice and straightforward, and their combination of techniques is interesting.
I read most of the proofs in the appendix, and to the best of my knowledge, are correct, although I did not read too carefully; nonetheless, the results are sensible and coherent compared to standard analysis and known results.

A few issues:

1. The structure of the paper, or more precisely the locations of the problem formulation and baseline assumption, is confusing for the expert reader. The problem is declared in 3 locations, together with the definition of second-order stationarity, but the first two statements are lacking in terms of mathematical formulation. This can be solved easily by moving Assumption 1 to the beginning of the paper, so all the statements made up until page 4 will make sense...
Additionally, in the same context, pages 1-4 indeed feel a bit repetitive, consider maybe revising, and then you will have some spaces for additional things, such as proofs sketch, etc.
2. The cubic regularization approach was first taken by: Griewank, A.: The Modification of Newton’s Method for Unconstrained Optimization by Bounding Cubic Terms. Technical Report NA/12 (1981). 
Unfortunately, this is quite an unknown manuscript in the community that deserves the credit for being the first (to the best of my knowledge).
3. Another recent paper for second-order optimization that might be relevant and was not mentioned is: Hallak, N., and Teboulle, M., "Finding second-order stationary points in constrained minimization: A feasible direction approach." Journal of Optimization Theory and Applications 186.2 (2020): 480-503. 
I think this paper also has a version for unconstrained problems.
4. There is a typo in the declaration of Theorem 4. 

summary_of_the_review: Pros:
- New method combining elements from first and second order methods
- The method only approximates the solution of the max problem
- New convergence guarantees for the min-max problem
- Well-written mathematically and in general

Cons:
- Results are not surprising, and somewhat a direct implication, considering the techniques used and the current literature.

Overall: I recommend to accept the paper.
review_title: null

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