# The Oracle Complexity of Simplex-based Matrix Games

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 9 Dec 2024.

## Builds on (most cited first, 13 of 13)

- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [On Accelerated Perceptrons and Beyond](https://mlsanity.com/paper/2210.09371/) (2022)
- [Faster width-dependent algorithm for mixed packing and covering LPs](https://mlsanity.com/paper/1909.12387/) (2019)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space](https://mlsanity.com/paper/2011.03495/) (2020)
- [Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games](https://mlsanity.com/paper/2304.12768/) (2023)
- [Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems](https://mlsanity.com/paper/2405.18809/) (2024)

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

- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension](https://mlsanity.com/paper/2602.12471/) (2026)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)

## Abstract (arXiv)

We study the problem of solving matrix games of the form minp∈Deltamaxw∈WptopAw, where A is a matrix and Delta is the probability simplex. This problem encapsulates canonical tasks such as finding a linear separator and computing Nash equilibria in zero-sum games. However, perhaps surprisingly, its inherent complexity (as formalized in the standard framework of oracle complexity) is not well understood. In this work, we first identify different oracle models that are implicitly used by prior algorithms, corresponding to multiplying the matrix A by a vector from either one or both sides. We then prove complexity lower bounds for algorithms under both access models, which in particular imply a separation between them. As our main result, we prove that in the general ℓp/simplex setting where W is an ℓp ball for p∈[1,∞], any algorithm that utilizes two-sided matrix-vector multiplications requires tildeOmega(ε-2/3) iterations to return an ε-suboptimal solution. For any p∈[1,∞], this is either the first lower bound for such problems, or an exponential improvement over the previously best-known results. Moreover, for the canonical tasks of finding a linear separator and computing a Nash equilibrium, our lower bounds match (up to log factors) recent algorithms of Karmarkar, O'Carroll and Sidford (2026), thereby resolving their oracle complexities in a natural setting.