02/02/2021

Sublinear Classical and Quantum Algorithms for General Matrix Games

Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, Xiaodi Wu

Keywords:

Abstract Paper Similar Papers

Abstract: 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949327
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 16:16 
 0
 0
 0
 0
 15:09 
 0
 0
 0
 0
 18:12 
 0
 0
 0
 0
 14:51 
 0
 1
 1
 1
 5:22 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 13:34 
 0
 0
 0
 0
 5:14 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 13:55 
 0
 0
 0
 0
 3:33 
 0
 0
 0
 0
 2:55 
 0
 0
 0
 0
 16:17 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 12:57 
 0
 0
 0
 0
 4:51 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 15:44 
 0
 0
 0
 0
 15:06 
 0
 0
 0
 0
 2:53 
 0
 0
 0
 0
 11:17 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 3:07 
 0
 0
 0
 0
 5:33 
 0
 0
 0
 0
 12:53 
 0
 0
 0
 0
 4:51 
 0
 0
 0
 0
 5:05 
 0
 0
 0
 0
 21:02 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 3:34 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 13:51 
 0
 0
 0
 1
 3:01 
 0
 0
 0
 0
 13:13 
 0
 0
 0
 0
 8:22 
 0
 0
 0
 0
 14:14 
 0
 0
 0
 0
 15:31 
 0
 0
 0
 0
 14:15