Sublinear classical and quantum algorithms for general matrix games

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix Ainmathbb{R}^{ntimes d}, sublinear algorithms for the matrix game min_{xinmathcal{X}}max_{yinmathcal{Y}} y^→p Ax were previously known only for two special cases: (1) mathcal{Y} being the ell₁-norm unit ball, and (2) mathcal{X} being either the ell₁- or the ell₂-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed qin \(1,2], we solve the matrix game where mathcal{X} is a ell_q-norm unit ball within additive error ε in time {O}((n+d\)/{ε²}). We also provide a corresponding sublinear quantum algorithm that solves the same task in time {O}\((sqrt{n}+sqrt{d}\)textrm{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 ell_q-margin support vector machines as applications.