# Solving Matrix Games with Near-Optimal Matvec Complexity

arXiv: https://arxiv.org/abs/2601.02347 · HTML: https://mlsanity.com/paper/2601.02347/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jan 2026.

## Built on by (most cited first, 2 of 2)

- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)

## Abstract (arXiv)

We study the problem of computing an ε-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix A ∈ ℝm × n, when the players' strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in tildeO(ε-2/3) matrix-vector multiplies (matvecs) in two well-studied cases: ℓ1-ℓ1 (or zero-sum) games, where the players' strategies are both in the probability simplex, and ℓ2-ℓ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 tildeO(ε-8/9) for ℓ1-ℓ1 and tildeO(ε-7/9) for ℓ2-ℓ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.