Lower Bounds for Nonconvex-Concave Minimax Optimization

Abstract

We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives $f$ that are jointly $L$-smooth in the primal and dual variables $(x,y)$, concave in $y$, and whose primal value function $\Phi(x) := \max_{y\in\mathcal Y} f(x,y)$ satisfies the initial-gap condition $\Phi(0)-\inf_{x\in\mathcal X}\Phi(x)\le \Delta_\Phi$, with a bounded dual domain satisfying $\operatorname{diam}(\mathcal Y)\le D_{\mathcal Y}$. We measure stationarity by the norm of the gradient of the Moreau envelope of $\Phi+\iota_{\mathcal X}$ with parameter $1/(2L)$. We prove that any deterministic zero-respecting first-order algorithm requires $\Omega\left(L^2D_{\mathcal Y}\Delta_\Phi\epsilon^{-3}\right)$ oracle evaluations to find an $\epsilon$-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires $\Omega\left(L^3D_{\mathcal Y}^2\Delta_\Phi\epsilon^{-6}\right)$ oracle evaluations. The same lower bounds hold when $\Delta_\Phi$ is replaced by the initial primal-dual gap $\mathcal G_0$. These deterministic and stochastic lower bounds match the corresponding upper bounds of [14] and [29], respectively, up to a logarithmic factor in the deterministic setting.