The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria

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/3})$ iterations, which is an exponential improvement over the previously best-known lower bound due to Hadiji et al. [2024].