# A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 67 references that are in the map.
- First posted on arXiv 17 Nov 2023.

## Builds on (most cited first, 30 of 34)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Minimizing the Maximal Loss: How and Why?](https://mlsanity.com/paper/1602.01690/) (2016)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems](https://mlsanity.com/paper/1305.1922/) (2013)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Efficient Inverse Maintenance and Faster Algorithms for Linear Programming](https://mlsanity.com/paper/1503.01752/) (2015)
- [An Optimal High-Order Tensor Method for Convex Optimization](https://mlsanity.com/paper/1812.06557/) (2018)
- [Near-optimal Approximate Discrete and Continuous Submodular Function Minimization](https://mlsanity.com/paper/1909.00171/) (2019)
- [Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs](https://mlsanity.com/paper/2009.01802/) (2020)
- [The global rate of convergence for optimal tensor methods in smooth convex optimization](https://mlsanity.com/paper/1809.00382/) (2018)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)

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

- [The Oracle Complexity of Simplex-based Matrix Games](https://mlsanity.com/paper/2412.06990/) (2024)
- [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 design algorithms for minimizing maxi∈[n] fi(x) over a d-dimensional Euclidean or simplex domain. When each fi is 1-Lipschitz and 1-smooth, our method computes an ε-approximate solution using widetildeO(n ε-1/3 + ε-2) gradient and function evaluations, and widetildeO(n ε-4/3) additional runtime. For large n, our evaluation complexity is optimal up to polylogarithmic factors. In the special case where each fi is linear -- which corresponds to finding a near-optimal primal strategy in a matrix game -- our method finds an ε-approximate solution in runtime widetildeO(n (d/ε)2/3 + nd + dε-2). For n>d and ε=1/√n this improves over all existing first-order methods. When additionally d = ω(n8/11) our runtime also improves over all known interior point methods. Our algorithm combines three novel primitives: (1) A dynamic data structure which enables efficient stochastic gradient estimation in small ℓ2 or ℓ1 balls. (2) A mirror descent algorithm tailored to our data structure implementing an oracle which minimizes the objective over these balls. (3) A simple ball oracle acceleration framework suitable for non-Euclidean geometry.