Sublinear classical and quantum algorithms for general matrix games
This work addresses a fundamental optimization problem in machine learning, offering efficient algorithms for broader matrix game settings, though it is incremental as it builds on prior special cases.
The paper tackles the problem of solving general matrix games with sublinear algorithms, extending previous work limited to specific norm constraints by providing classical and quantum algorithms that handle a broader range of ℓq-norm unit balls for 𝒳, achieving additive error ε in time Õ((n+d)/ε²) classically and Õ((√n+√d)poly(1/ε)) quantumly, with optimal dimension scaling up to poly-logarithmic factors.
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\in\mathbb{R}^{n\times d}$, sublinear algorithms for the matrix game $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}} y^{\top} Ax$ were previously known only for two special cases: (1) $\mathcal{Y}$ being the $\ell_{1}$-norm unit ball, and (2) $\mathcal{X}$ being either the $\ell_{1}$- or the $\ell_{2}$-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed $q\in (1,2]$, we solve the matrix game where $\mathcal{X}$ is a $\ell_{q}$-norm unit ball within additive error $ε$ in time $\tilde{O}((n+d)/{ε^{2}})$. We also provide a corresponding sublinear quantum algorithm that solves the same task in time $\tilde{O}((\sqrt{n}+\sqrt{d})\textrm{poly}(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éodory problem and the $\ell_{q}$-margin support vector machines as applications.