



@article {2722,
	title = {Sublinear classical and quantum algorithms for general matrix games},
	journal = {To appear in the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)},
	year = {2020},
	month = {12/11/2020},
	abstract = {<p>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\&isin;Rn\&times;d, sublinear algorithms for the matrix game minx\&isin;Xmaxy\&isin;Yy⊤Ax were previously known only for two special cases: (1) Y being the l1-norm unit ball, and (2) X being 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\&isin;(1,2], we solve the matrix game where X is a lq-norm unit ball within additive error ε in time O~((n+d)/ε2). We also provide a corresponding sublinear quantum algorithm that solves the same task in time O~((n\&minus;\&minus;\&radic;+d\&minus;\&minus;\&radic;)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{\'e}odory problem and the lq-margin support vector machines as applications.</p>},
	url = {https://arxiv.org/abs/2012.06519},
	author = {Tongyang Li and Chunhao Wang and Shouvanik Chakrabarti and Xiaodi Wu}
}
