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 points 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 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,\kappa^{ 1.5}\sqrt{ \rho\varepsilon}\,\big)$-second-order stationary point of $P({ \bf x})$ with calling ${ \mathcal O}\big(\kappa^{ 1.5}\sqrt{ \rho}\varepsilon^{ -1.5}\big)$ times of second-order oracles and $\tilde{ \mathcal O}\big(\kappa^{ 2}\sqrt{ \rho}\varepsilon^{ -1.5}\big)$ 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 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}\big(\kappa^{ 1.5}\ell\varepsilon^{ -2}\big)$ Hessian-vector oracle calls and $\tilde{ \mathcal O}\big(\kappa^{ 2}\sqrt{ \rho}\varepsilon^{ -1.5}\big)$ 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.
Categories: math.OC cs.LG