Solving Matrix Games with Near-Optimal Matvec Complexity
We study the problem of computing an $ε$-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix $A \in \mathbb{R}^{m \times n}$, when the players' strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in $\tilde{O}(ε^{-2/3})$ matrix-vector multiplies (matvecs) in two well-studied cases: $\ell_1$-$\ell_1$ (or zero-sum) games, where the players' strategies are both in the probability simplex, and $\ell_2$-$\ell_1$ games (encompassing hard-margin SVMs), where the players' strategies are in the unit Euclidean ball and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.02347
curl -X POST /api/v1/records/arxiv/2601.02347/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.02347/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'