CLS Hardness of 2D Min-Max Optimization with Product Constraints

Abstract

We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For black-box access to the objective, we prove that any algorithm requires $\Omega (1/\sqrt{\epsilon })$ queries to find an $\epsilon$-first-order Nash point. In the white-box setting, we establish CLS-hardness by reducing from End-of-Potential-Line. These results show that even the simplest min-max setting with one dimensional min and max players is at least as hard as CLS and therefore does not admit polynomial-time algorithms unless $\mathsf{CLS}\subseteq \mathsf{P}$.