Lower Bounds for Nonconvex-P{\L} Minimax Optimization

Abstract

We study the deterministic first-order oracle complexity of finding stationary points of the value function in smooth nonconvex-Polyak-{\L}ojasiewicz (NC-P{\L}) minimax optimization. We assume that the objective is jointly $\ell$-smooth and satisfies the $\mu$-P{\L} condition in the dual variable, and that its value function $\Phi(x):=\max_y f(x;y)$ satisfies $\Phi(0)-\inf_x\Phi(x)\leq\Delta$. When $\kappa:=\ell/\mu\gtrsim 1$ and $0<\epsilon^2\lesssim\ell\Delta$, we prove that every deterministic first-order method requires $\Omega(\ell\Delta\kappa/\epsilon^2)$ oracle queries in the worst case to find $x$ satisfying $\|\nabla\Phi(x)\|\leq\epsilon$. This rate matches the known upper bound in its dependence on $(\ell,\Delta,\kappa,\epsilon)$ [Yang et al., 2022] and shows that the linear dependence on $\kappa$ is unavoidable for deterministic first-order methods.