Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization

@misc{pan2026optimal,
  title = {{Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization}},
  author = {Siyu Pan and Taoli Zheng and Jiajin Li},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.14235},
  eprint = {2609.14235},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14235},
}

TY  - UNPB
TI  - Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
AU  - Siyu Pan
AU  - Taoli Zheng
AU  - Jiajin Li
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.14235
UR  - https://arxiv.org/abs/2609.14235
AB  - We study the deterministic first-order oracle complexity of smooth nonconvex-concave minimax optimization over a bounded convex dual domain under two notions of stationarity: optimization stationarity (OS) and game stationarity (GS). OS concerns stationarity of the value function, viewed as a structured nonsmooth objective obtained by maximizing over the dual variable. GS concerns the joint first-order optimality conditions for both primal minimization and dual maximization, each with the other variable held fixed. Existing upper bounds on the oracle complexity of first-order methods for finding ε-OS and ε-GS points have different dependence on ε, but whether this difference reflects an intrinsic separation in computational hardness remains unresolved. We resolve this question by establishing worst-case lower bounds for arbitrary deterministic first-order methods: Ω(ε^−3) oracle queries for finding an ε-OS point and Ω(ε^−5/2) for finding an ε-GS point, with the remaining problem parameters fixed. These bounds match existing upper bounds up to logarithmic factors. To close the remaining logarithmic gap, we introduce Tracked-FOAM, a new first-order algorithm whose oracle complexity matches our lower bounds for both OS and GS. Together, these results establish an intrinsic separation between OS and GS in the optimal accuracy dependence of deterministic first-order oracle complexity.
ER  -