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

Fangqing Zhang, Haihan Zhang, Wendao Wu, Chenheng Zhang, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2610.16771Oct 12, 2026math.OCscore 0

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}\varepsilon/L^2$. We establish matching deterministic upper bounds and randomized lower bounds, up to logarithmic factors and additive initialization…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.16771
curl -X POST /api/v1/records/arxiv/2610.16771/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16771/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'