Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization

We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of Omega (root kappa epsilon(-2) for deterministic oracles, where epsilon defines the level of approximate stationarity and kappa is the condition number. Our lower bound matches the best existing upper bound in the epsilon and kappa dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of Omega (root kappa c(-2) vertical bar kappa 1/3c(-4). It suggests that there is a gap between the best existing upper bound O(kappa(3)epsilon(-4)) and our lower bound in the condition number dependence.