TY - JOUR
AU - Li, Tongyang
AU - Wang, Chunhao
AU - Chakrabarti, Shouvanik
AU - Wu, Xiaodi
PY - 2021/05/18
Y2 - 2023/05/29
TI - Sublinear Classical and Quantum Algorithms for General Matrix Games
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 35
IS - 10
SE - AAAI Technical Track on Machine Learning III
DO - 10.1609/aaai.v35i10.17028
UR - https://ojs.aaai.org/index.php/AAAI/article/view/17028
SP - 8465-8473
AB - We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix, sublinear algorithms for the matrix game were previously known only for two special cases: (1) the maximizing vectors live in the L1-norm unit ball, and (2) the minimizing vectors live in either the L1- or the L2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q between 1 and 2, we solve, within some additive error, matrix games where the minimizing vectors are in an Lq-norm unit ball. We also provide a corresponding sublinear quantum algorithm that solves the same task with a quadratic improvement in dimensions of the maximizing and minimizing vectors. Both our classical and quantum algorithms are optimal in the dimension parameters up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carathéodory problem and the Lq-margin support vector machines as applications.
ER -