Lower Bounds for Nonconvex-Concave Minimax Optimization

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) := maxy∈mathcal Y f(x,y) satisfies the initial-gap condition Phi(0)-infx∈mathcal XPhi(x)≤ Delta_Phi, with a bounded dual domain satisfying operatornamediam(mathcal Y)≤ Dmathcal Y. We measure stationarity by the norm of the gradient of the Moreau envelope of Phi+iotamathcal X with parameter 1/(2L). We prove that any deterministic zero-respecting first-order algorithm requires Omegaleft(L2Dmathcal YDelta_Phiε-3right) oracle evaluations to find an ε-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires Omegaleft(L3Dmathcal Y2Delta_Phiε-6right) oracle evaluations. The same lower bounds hold when Delta_Phi is replaced by the initial primal-dual gap mathcal G0. 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.