Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization

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