Finding Second-Order Stationary Points of Nonconvex—Strongly-Concave Minimax Problems under Weaker Smoothness Assumption

Most existing studies on computing second-order stationary points of minimax problems focus on the nonconvex–-strongly-concave setting under higher-order smoothness assumptions. We adopt the notion of Goldstein approximate second-order stationarity and, for the first time, extend the study of second-order stationarity to the weaker setting where the objective is only continuously differentiable with a Lipschitz continuous gradient. Specifically, we propose a first-order method, called Smoothed Minimax Cubic Newton (SMCN), for finding an $\epsilon$-Goldstein approximate second-order stationary point of the primal function. We show that with high probability, SMCN requires at most $\tilde{\mathcal{O}}({\kappa }^4{\ell }^{4}n{\epsilon }^{-5})$ outer iterations and $\tilde{\mathcal{O}}({\kappa }^{8.5}{\ell }^8{n}^2{\epsilon }^{-9}+{\kappa }^{6.5}{\ell }^6{n}^3{\epsilon }^{-7})$ first-order oracle calls, where $\ell$ denotes the Lipschitz constant of the gradient, $\kappa$ is the condition number, and $n$ is the primal dimension. We conduct numerical experiments to further demonstrate the effectiveness of the proposed method.