# Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2023.

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

- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [Optimistic Online Learning in Symmetric Cone Games](https://mlsanity.com/paper/2504.03592/) (2025)

## Abstract (arXiv)

We investigate different aspects of area convexity [Sherman '17], a mysterious tool introduced to tackle optimization problems under the challenging ℓ_∞ geometry. We develop a deeper understanding of its relationship with more conventional analyses of extragradient methods [Nemirovski '04, Nesterov '07]. We also give improved solvers for the subproblems required by variants of the [Sherman '17] algorithm, designed through the lens of relative smoothness [Bauschke-Bolte-Teboulle '17, Lu-Freund-Nesterov '18]. Leveraging these new tools, we give a state-of-the-art first-order algorithm for solving box-simplex games (a primal-dual formulation of ℓ_∞ regression) in a d × n matrix with bounded rows, using O(log d · ε-1) matrix-vector queries. As a consequence, we obtain improved complexities for approximate maximum flow, optimal transport, min-mean-cycle, and other basic combinatorial optimization problems. We also develop a near-linear time algorithm for a matrix generalization of box-simplex games, capturing a family of problems closely related to semidefinite programs recently used as subroutines in robust statistics and numerical linear algebra.