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_𝐰∈𝒲min_𝐩∈Δ𝐩^⊤A𝐰, 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 Ω̃(γ_A^-2/3) iterations, establishing the first oracle complexity barrier for such algorithms. Finally, by adapting our lower bound to ℓ_1 geometry, we prove that computing an ϵ-approximate Nash equilibrium requires Ω̃(ϵ^-2/5) iterations, which is an exponential improvement over the previously best-known lower bound due to Hadiji et al. (2024).