Solving Matrix Games with Even Fewer Matrix-Vector Products

We study the problem of computing an $ε$-approximate Nash equilibrium of a two-player, bilinear, zero-sum 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}(ε^{-2/3})$ matrix-vector multiplies (matvecs) in two well-studied cases: $\ell_1$-$\ell_1$ games, where the players' strategies are both in the probability simplex, and $\ell_2$-$\ell_1$ games, 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}(ε^{-8/9})$ for $\ell_1$-$\ell_1$ and of $\tilde{O}(ε^{-7/9})$ for $\ell_2$-$\ell_1$ due to [KOS '25]. In particular, our result for $\ell_2$-$\ell_1$, which corresponds to hard-margin support vector machines (SVMs), matches the lower bound of [KS '25] up to polylogarithmic factors.