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

We study the smooth minimax optimization problem minbf xmaxbf y f(bf x,bf y), where f is ℓ-smooth, strongly-concave in bf y but possibly nonconvex in bf x. Most of existing works focus on finding the first-order stationary points of the function f(bf x,bf y) or its primal function P(bf x)triangleq maxbf y f(bf x,bf 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 big(varepsilon,kappa1.5√ρvarepsilon,big)-second-order stationary point of P(bf x) with calling mathcal Obig(kappa1.5√ρvarepsilon-1.5big) times of second-order oracles and tildemathcal Obig(kappa2√ρvarepsilon-1.5big) times of first-order oracles, where kappa is the condition number and ρ 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 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 tildemathcal Obig(kappa1.5ℓvarepsilon-2big) Hessian-vector oracle calls and tildemathcal Obig(kappa2√ρvarepsilon-1.5big) 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.