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

Computer Science and Game TheoryComputational Complexity

Summary

The gist is being written…

Authors

Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis, Manolis Zampetakis

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 $Ω(1/\sqrtε)$ queries to find an $ε$-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}$.