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

Abstract

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 $\epsilon$-OS and $\epsilon$-GS points have different dependence on $\epsilon$, 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: $\Omega ({\epsilon }^{-3})$ oracle queries for finding an $\epsilon$-OS point and $\Omega ({\epsilon }^{-5/2})$ for finding an $\epsilon$-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.

arXiv commentv2: Established matching bounds for both OS and GS across all parameter regimes, revealing an intrinsic separation in optimal accuracy dependence