Solving Matrix Games with Near-Optimal Matvec Complexity

Abstract

We study the problem of computing an $\hat{I}\mu$-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix $A\in {\mathbb{R}}^{m\times n}$, when the players' strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in $\tilde{O}(\hat{I}{\mu }^{-2/3})$ matrix-vector multiplies (matvecs) in two well-studied cases: ${\ell }_1$-${\ell }_1$ (or zero-sum) games, where the players' strategies are both in the probability simplex, and ${\ell }_2$-${\ell }_1$ games (encompassing hard-margin SVMs), where the players' strategies are in the unit Euclidean ball and probability simplex respectively. These results improve upon the previous state-of-the-art complexities of $\tilde{O}(\hat{I}{\mu }^{-8/9})$ for ${\ell }_1$-${\ell }_1$ and $\tilde{O}(\hat{I}{\mu }^{-7/9})$ for ${\ell }_2$-${\ell }_1$ due to [KOS '25]. In both settings our results are nearly-optimal as they match lower bounds of [KS '25] up to polylogarithmic factors.

v2: A few updates to the title, abstract, and intro to reflect the near optimality of our results for ${\ell }_1$-${\ell }_1$ games in light of arXiv:2412.06990 v3. v3: Overhauled Section 3 technical overview. Minor updates and typo fixes in other sections