# Solving Zero-Sum Games with Fewer Matrix-Vector Products

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2025.

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

- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)

## Abstract (arXiv)

In this paper we consider the problem of computing an ε-approximate Nash Equilibrium of a zero-sum game in a payoff matrix A ∈ ℝm × n with O(1)-bounded entries given access to a matrix-vector product oracle for A and its transpose A^top. We provide a deterministic algorithm that solves the problem using tildeO(ε-8/9)-oracle queries, where tildeO(·) hides factors polylogarithmic in m, n, and ε-1. Our result improves upon the state-of-the-art query complexity of tildeO(ε-1) established by [Nemirovski, 2004] and [Nesterov, 2005]. We obtain this result through a general framework that yields improved deterministic query complexities for solving a broader class of minimax optimization problems which includes computing a linear classifier (hard-margin support vector machine) as well as linear regression.