Solving Zero-Sum Games with Fewer Matrix-Vector Products

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.