Abstract
In this paper we consider the problem of computing an ε-approximate Nash Equilibrium of a zero-sum game in a payoff matrix A ∈ R^m × n with O(1)-bounded entries given access to a matrix-vector product oracle for A and its transpose A. We provide a deterministic algorithm that solves the problem using O(ε^-8/9)-oracle queries, where O(·) hides factors polylogarithmic in m, n, and ε⁻¹. Our result improves upon the state-of-the-art query complexity of O(ε⁻¹) 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.