Abstract
We study the problem of computing an ε-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix A ∈ R^m × n, when the players' strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in O(ε^-2/3) matrix-vector multiplies (matvecs) in two well-studied cases: ℓ₁-ℓ₁ (or zero-sum) games, where the players' strategies are both in the probability simplex, and ℓ₂-ℓ₁ 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 O(ε^-8/9) for ℓ₁-ℓ₁ and O(ε^-7/9) for ℓ₂-ℓ₁ due to [KOS '25]. In both settings our results are nearly-optimal as they match lower bounds of [KS '25] up to polylogarithmic factors.