Solving Zero-Sum Games with Fewer Matrix-Vector Products

2025/09/04 by Karmarkar, Ishani, O'Carroll, Liam, Sidford, Aaron
#Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2509.04426

Abstract

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 O(ε^-8/9)-oracle queries, where O(⋅) hides factors polylogarithmic in m, n, and ε^-1. Our result improves upon the state-of-the-art query complexity of 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.

Citations

• Reusing Samples in Variance Reduction
• The Oracle Complexity of Simplex-based Matrix Games
• Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
• Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization
• A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions
• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
• ReSQueing Parallel and Private Stochastic Convex Optimization
• Optimal and Adaptive Monteiro-Svaiter Acceleration
• Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities
• Distributionally Robust Optimization via Ball Oracle Acceleration
• Stochastic Bias-Reduced Gradient Methods
• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
• Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
• Coordinate Methods for Matrix Games
• Acceleration with a Ball Optimization Oracle
• The gradient complexity of linear regression
• Variance Reduction for Matrix Games
• Complexity of Highly Parallel Non-Smooth Convex Optimization
• Near-optimal method for highly smooth convex optimization
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Towards Deep Learning Models Resistant to Adversarial Attacks
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient\n Descent on Non-Convex Functions
• Stochastic Variance Reduction Methods for Saddle-Point Problems
• Tight Complexity Bounds for Optimizing Composite Objectives
• Randomized Block Krylov Methods for Stronger and Faster Approximate\n Singular Value Decomposition
• Optimization, Learning, and Games with Predictable Sequences
• Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems
• On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
• Sublinear Optimization for Machine Learning
• A Note on Preconditioning by Low-Stretch Spanning Trees
• Smooth minimization of non-smooth functions
• The perceptron: A probabilistic model for information storage and organization in the brain.

Related

• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
• Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
• The Oracle Complexity of Simplex-based Matrix Games
• Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games