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}\epsilon /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Θ\!\left( \frac{ΔL}{\varepsilon^2}Ψ_κ(r) \right), \qquad Ψ_κ(r)= \begin{cases} r^{1/2}, & 0<r\le 1,\\ r^{2/7}, & 1<r<κ^{7/4},\\ \sqrtκ, & r\geκ^{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 ${\epsilon }^{-3/2}$, ${\epsilon }^{-12/7}$, and ${\epsilon }^{-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.