@article{Li_Wang_Chakrabarti_Wu_2021, title={Sublinear Classical and Quantum Algorithms for General Matrix Games}, volume={35}, url={https://ojs.aaai.org/index.php/AAAI/article/view/17028}, DOI={10.1609/aaai.v35i10.17028}, abstractNote={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.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Li, Tongyang and Wang, Chunhao and Chakrabarti, Shouvanik and Wu, Xiaodi}, year={2021}, month={May}, pages={8465-8473} }