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 Φ(x)=maxy f(x,y), assume that f has an L-Lipschitz gradient, a ρ-Lipschitz Hessian, and is μ-strongly concave in y. Let κ=L/μ, let Δ denote the initial value gap, and define r=ρκ3/2ε/L2. 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 Θ̃ ( ΔL/ε2Ψκ(r) ), Ψκ(r)= r1/2, & 0<r≤ 1, r2/7, & 1<r<κ7/4, √κ, & r≥κ7/4. Despite the stronger oracle, the optimal complexity exhibits a nontrivial dependence on accuracy, conditioning, and Hessian smoothness. In particular, these regimes exhibit accuracy dependencies ε−3/2, ε−12/7, and ε−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.
Related
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
- Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{zhang2026matching,
title = {{Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization}},
author = {Fangqing Zhang and Haihan Zhang and Wendao Wu and Chenheng Zhang and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16771},
eprint = {2610.16771},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16771},
}
RIS
TY - UNPB
TI - Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
AU - Fangqing Zhang
AU - Haihan Zhang
AU - Wendao Wu
AU - Chenheng Zhang
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.16771
UR - https://arxiv.org/abs/2610.16771
AB - 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 Φ(x)=max_y f(x,y), assume that f has an L-Lipschitz gradient, a ρ-Lipschitz Hessian, and is μ-strongly concave in y. Let κ=L/μ, let Δ denote the initial value gap, and define r=ρκ^3/2ε/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 Θ̃ ( ΔL/ε^2Ψ_κ(r) ), Ψ_κ(r)= r^1/2, & 0<r≤ 1, r^2/7, & 1<r<κ^7/4, √κ, & r≥κ^7/4. Despite the stronger oracle, the optimal complexity exhibits a nontrivial dependence on accuracy, conditioning, and Hessian smoothness. In particular, these regimes exhibit accuracy dependencies ε^−3/2, ε^−12/7, and ε^−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.
ER -