Lower Bounds for Nonconvex-PL Minimax Optimization

We study the deterministic first-order oracle complexity of finding stationary points of the value function in smooth nonconvex-Polyak-Lojasiewicz (NC-PL) minimax optimization. We assume that the objective is jointly ℓ-smooth and satisfies the μ-PL condition in the dual variable, and that its value function Phi(x):=maxy f(x;y) satisfies Phi(0)-infxPhi(x)≤Delta. When kappa:=ℓ/μgtrsim 1 and 0<ε2lesssimℓDelta, we prove that every deterministic first-order method requires Omega(ℓDeltakappa/ε2) oracle queries in the worst case to find x satisfying |nablaPhi(x)|≤ε. This rate matches the known upper bound in its dependence on (ℓ,Delta,kappa,ε) [Yang et al., 2022] and shows that the linear dependence on kappa is unavoidable for deterministic first-order methods.