



01601nas a2200145   4500008004100000245007200041210006900113260001500182520114400197100001701341700001801358700002701376700001501403856003701418       2020                        eng d00aSublinear classical and quantum algorithms for general matrix games0 aSublinear classical and quantum algorithms for general matrix ga  c12/11/20203 a<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 ℓ1-norm unit ball, and (2) X being either the ℓ1- or the ℓ2-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 ℓq-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éodory problem and the ℓq-margin support vector machines as applications.</p>1 aLi, Tongyang1 aWang, Chunhao1 aChakrabarti, Shouvanik1 aWu, Xiaodi  uhttps://arxiv.org/abs/2012.06519