Optimal Complexity for P-P Minimax Optimization

We study the deterministic first-order oracle complexity of smooth two-sided Polyak–Łojasiewicz (PŁ) minimax optimization, where the objective $f(\mathbf{x},\mathbf{y})$ is jointly $\ell$-smooth, ${\mu }_{\mathbf{x}}$-PŁ in $\mathbf{x}$, and ${\mu }_{\mathbf{y}}$-PŁ in $\mathbf{y}$. Let ${\kappa }_{\mathbf{x}}:=\ell /{\mu }_{\mathbf{x}}$, ${\kappa }_{\mathbf{y}}:=\ell /{\mu }_{\mathbf{y}}$, and $\Phi (\mathbf{x}):={\max }_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$. Assuming $\Phi (0)-{\min }_{\mathbf{x}}\Phi (\mathbf{x})\le \Delta$, we prove that every deterministic first-order method requires $\Omega ({\kappa }_{\mathbf{x}}{\kappa }_{\mathbf{y}}\log (\Delta /ϵ))$ oracle queries in the worst case to find a point $\mathbf{x}$ satisfying $\Phi (\mathbf{x})-{\min }_{\mathbf{x}}\Phi (\mathbf{x})\le ϵ$. We further show, through a sharper analysis, that the existing single-loop Smoothed Gradient Descent–Ascent (S-GDA) method attains a matching upper bound, removing an extra logarithmic factor from previous upper bounds. Together, these results establish the optimal deterministic first-order oracle complexity of smooth two-sided PŁ minimax optimization.