Solving Matrix Games with Near-Optimal Matvec Complexity

We study the fundamental problem of computing an approximate Nash equilibrium of a two-player zero-sum game and the approximate solution of hard-margin SVM given access to only a small number of matrix-vector products in the payoff/utility matrix. We provide the first algorithm that provably converges to an $\epsilon$-approximate Nash equilibrium in $\tilde{O}(\epsilon^{-2/3})$ matrix-vector products, which improves upon our prior work and matches the lower bounds of Koronowski and Shamir (2025) and (2026). (arxiv)