Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization

Abstract

We study nonconvex-strongly-concave minimax problem ${\min }_{\mathbf{x}\in {\mathbb{R}}^{d_x}}{\max }_{\mathbf{y}\in {\mathbb{R}}^{d_y}}f(\mathbf{x},\mathbf{y})$ in which the objective has $\rho$-Lipschitz Hessian and condition number $\kappa$. We propose envelope cubic regularized Newton method (ECRN) which applies a refined inexact cubic regularized Newton method to the envelope of the primal function $\Phi (\cdot ):={\max }_{\mathbf{y}\in {\mathbb{R}}^{d_y}}f(\cdot ,\mathbf{y})$. We show that ECRN finds approximate second-order stationary points of $\Phi (\cdot )$ with $\tilde{\mathcal{O}}(\sqrt{\rho }{\kappa }^{3/4}{\epsilon }^{-3/2})$ second-order oracles, improving the condition number dependence $\mathcal{O}({\kappa }^2)$ achieved by the best known second-order methods. Our improvement comes from the key observation that the Hessian Lipschitz parameter of the envelope is $\mathcal{O}(\rho {\kappa }^{3/2})$, which is sharper than the order of $\mathcal{O}(\rho {\kappa }^3)$ for the function $\Phi (\cdot )$. We also conduct a lower bound on second-order methods to show that our complexity is optimal up to a logarithmic factor.