{"ID":2874734,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.04426","arxiv_id":"2509.04426","title":"Solving Zero-Sum Games with Fewer Matrix-Vector Products","abstract":"In this paper we consider the problem of computing an $ε$-approximate Nash Equilibrium of a zero-sum game in a payoff matrix $A \\in \\mathbb{R}^{m \\times 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 $\\tilde{O}(ε^{-8/9})$-oracle queries, where $\\tilde{O}(\\cdot)$ hides factors polylogarithmic in $m$, $n$, and $ε^{-1}$. Our result improves upon the state-of-the-art query complexity of $\\tilde{O}(ε^{-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.","short_abstract":"In this paper we consider the problem of computing an $ε$-approximate Nash Equilibrium of a zero-sum game in a payoff matrix $A \\in \\mathbb{R}^{m \\times 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...","url_abs":"https://arxiv.org/abs/2509.04426","url_pdf":"https://arxiv.org/pdf/2509.04426v1","authors":"[\"Ishani Karmarkar\",\"Liam O'Carroll\",\"Aaron Sidford\"]","published":"2025-09-04T17:46:48Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\",\"cs.GT\"]","methods":"[]","has_code":false}