Sublinear Classical and Quantum Algorithms for General Matrix Games
Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, Xiaodi Wu
Abstract
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.
BibTeX
@inproceedings{aaai2021_sublinearclassic,
title = {Sublinear Classical and Quantum Algorithms for General Matrix Games},
author = {Tongyang Li and Chunhao Wang and Shouvanik Chakrabarti and Xiaodi Wu},
booktitle = {AAAI 2021},
year = {2021}
}