The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria
This work addresses the theoretical complexity of fundamental optimization problems in machine learning and game theory, providing rigorous lower bounds that are incremental but with specific exponential improvements.
The paper tackles the problem of solving matrix games, such as finding linear separators and Nash equilibria, by proving new oracle complexity lower bounds for algorithms under different access models. It shows that one-sided multiplication algorithms require Ω(γ_A^{-2}) iterations, while accelerated two-sided ones require Ω̃(γ_A^{-2/3}) iterations, and improves the lower bound for computing ε-approximate Nash equilibria to Ω̃(ε^{-2/5}), an exponential gain over prior work.
We study the problem of solving matrix games of the form $\max_{\mathbf{w}\in\mathcal{W}}\min_{\mathbf{p}\inΔ}\mathbf{p}^{\top}A\mathbf{w}$, where $A$ is some matrix and $Δ$ is the probability simplex. This problem encapsulates canonical tasks such as finding a linear separator and computing Nash equilibria in zero-sum games. However, perhaps surprisingly, its inherent complexity (as formalized in the standard framework of oracle complexity [Nemirovski and Yudin, 1983]) is not well-understood. In this work, we first identify different oracle models which are implicitly used by prior algorithms, amounting to multiplying the matrix $A$ by a vector from either one or both sides. We then prove complexity lower bounds for algorithms under both access models, which in particular imply a separation between them. Specifically, we start by showing that algorithms for linear separability based on one-sided multiplications must require $Ω(γ_A^{-2})$ iterations, where $γ_A$ is the margin, as matched by the Perceptron algorithm. We then prove that accelerated algorithms for this task, which utilize multiplications from both sides, must require $\tildeΩ(γ_{A}^{-2/3})$ iterations, establishing the first oracle complexity barrier for such algorithms. Finally, by adapting our lower bound to $\ell_1$ geometry, we prove that computing an $ε$-approximate Nash equilibrium requires $\tildeΩ(ε^{-2/5})$ iterations, which is an exponential improvement over the previously best-known lower bound due to Hadiji et al. [2024].