Lower Bounds for Nonconvex-PŁ Minimax Optimization

Abstract

We study the deterministic first-order oracle complexity of finding stationary points of the value function in smooth nonconvex-Polyak-Łojasiewicz (NC-PŁ) minimax optimization. We assume that the objective is jointly $\ell$-smooth and satisfies the $\mu$-PŁ condition in the dual variable, and that its value function $\Phi (x):={\max }_{y}f(x;y)$ satisfies $\Phi (0)-{\inf }_x\Phi (x)\le \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 $\Vert \nabla \Phi (x)\Vert \le \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.