Sublinear Classical and Quantum Algorithms for General Matrix Games


  • Tongyang Li University of Maryland Massachusetts Institute of Technology
  • Chunhao Wang Pennsylvania State University University of Texas at Austin
  • Shouvanik Chakrabarti University of Maryland
  • Xiaodi Wu University of Maryland



Learning Theory


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.




How to Cite

Li, T., Wang, C., Chakrabarti, S., & Wu, X. (2021). Sublinear Classical and Quantum Algorithms for General Matrix Games. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10), 8465-8473.



AAAI Technical Track on Machine Learning III