论文标题
一般矩阵游戏的司肌古典和量子算法
Sublinear classical and quantum algorithms for general matrix games
论文作者
论文摘要
我们研究了用于矩阵游戏的Sublrinear古典和量子算法，这是优化和机器学习的基本问题，并具有可证明的保证。给定一个矩阵$ a \ in \ mathbb {r}^{n \ times d} $，矩阵游戏$ \ min_ {x \ in \ mathcal {x}}}} \ max_ {y max_ {y mathcal in \ nathcal {y mathcal {y} y for for for for for for for for， $ \ MATHCAL {y} $是$ \ ell_ {1} $ - NORM单位球，（2）$ \ Mathcal {x} $是$ \ ell_ {1} $ - 或$ \ ell_ {2} $ - norm单位球。我们给出了可以在这两种情况下平稳插值的司额经典算法：对于任何固定的$ q \（1,2] $中的任何固定$ q \，我们求解了矩阵游戏，其中$ \ mathcal {x} $是$ \ ell_ {Q} $ \ tilde {o}（（n+d）/{ε^{2}}）$。 $ n $和$ d $的二次改进。
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.
