Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization

Abstract

We characterize the oracle complexity of finding first-order stationary points in smooth nonconvex--strongly-concave (NC--SC) minimax optimization when each query provides the full Hessian in addition to the function value and gradient. For $\Phi(x)=\max_y f(x,y)$, assume that $f$ has an $L$-Lipschitz gradient, a $\rho$-Lipschitz Hessian, and is $\mu$-strongly concave in $y$. Let $\kappa=L/\mu$, let $\Delta$ denote the initial value gap, and define $r=\rho\kappa^{3/2}\varepsilon/L^2$. We establish matching deterministic upper bounds and randomized lower bounds, up to logarithmic factors and additive initialization costs. When the leading term dominates initialization, the resulting minimax complexity is \[ \widetilde{\Theta}\!\left( \frac{\Delta L}{\varepsilon^2}\Psi_\kappa(r) \right), \qquad \Psi_\kappa(r)= \begin{cases} r^{1/2},&0<r\le 1,\\ r^{2/7},&1<r<\kappa^{7/4},\\ \sqrt{\kappa},&r\ge\kappa^{7/4}. \end{cases} \] Despite the stronger oracle, the optimal complexity exhibits a nontrivial dependence on accuracy, conditioning, and Hessian smoothness. In particular, these regimes exhibit accuracy dependencies $\varepsilon^{-3/2}$, $\varepsilon^{-12/7}$, and $\varepsilon^{-2}$, respectively. The upper bounds combine second-order regularity estimates for a saddle Moreau envelope with certified accelerated reduced-dual solves and amortized warm starts. The lower bounds combine an all-derivative lift with a serial composition of private-handle constructions, using hard instances chosen independently of the algorithm's realized random seed. The resulting characterization quantifies improvements over the classical first-order benchmark under gradient smoothness alone and identifies the regime in which that benchmark is recovered.