# Sublinear classical and quantum algorithms for general matrix games

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2020.

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

- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [Payoff-based learning with matrix multiplicative weights in quantum games](https://mlsanity.com/paper/2311.02423/) (2023)
- [Statistical Analysis of Quantum State Learning Process in Quantum Neural Networks](https://mlsanity.com/paper/2309.14980/) (2023)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)

## Abstract (arXiv)

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix A∈ℝn× d, sublinear algorithms for the matrix game minx∈Xmaxy∈Y ytop Ax were previously known only for two special cases: (1) Y being the ℓ1-norm unit ball, and (2) X being either the ℓ1- or the ℓ2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q∈ (1,2], we solve the matrix game where X is a ℓq-norm unit ball within additive error ε in time tildeO((n+d)/ε2). We also provide a corresponding sublinear quantum algorithm that solves the same task in time tildeO((√n+√d)textrmpoly(1/ε)) with a quadratic improvement in both n and d. Both our classical and quantum algorithms are optimal in the dimension parameters n and d up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carath'eodory problem and the ℓq-margin support vector machines as applications.