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 $\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 Carath\'eodory problem and the $\ell_{q}$-margin
support vector machines as applications.

本研究提出了一种插值算法，该算法能够在两个特殊情况之间插值，并解决矩阵游戏问题。我们同时提供经典算法和量子算法，用于近似 Cara​théodore 问题和 lq-margin 支持向量机。