We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix $Ainmathbb{R}^{ntimes d}$, sublinear algorithms for the matrix game $min_{xinmathcal{X}}max_{yinmathcal{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 $qin (1,2]$, we solve the matrix game where $mathcal{X}$ is a $ell_{q}$-norm unit ball within additive error $epsilon$ in time $tilde{O}((n+d)/{epsilon^{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/epsilon))$ 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 Caratheodory problem and the $ell_{q}$-margin support vector machines as applications.
Download