Sublinear classical and quantum algorithms for general matrix games
- URL: http://arxiv.org/abs/2012.06519v1
- Date: Fri, 11 Dec 2020 17:36:33 GMT
- Title: Sublinear classical and quantum algorithms for general matrix games
- Authors: Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu
- Abstract summary: We investigate sublinear classical and quantum algorithms for matrix games.
For any fixed $qin (1,2), we solve the matrix game where $mathcalX$ is a $ell_q$-norm unit ball within additive error.
We also provide a corresponding sublinear quantum algorithm that solves the same task in time.
- Score: 11.339580074756189
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 $A\in\mathbb{R}^{n\times d}$, sublinear algorithms
for the matrix game $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}} y^{\top} Ax$
were previously known only for two special cases: (1) $\mathcal{Y}$ being the
$\ell_{1}$-norm unit ball, and (2) $\mathcal{X}$ being either the $\ell_{1}$-
or the $\ell_{2}$-norm unit ball. We give a sublinear classical algorithm that
can interpolate smoothly between these two cases: for any fixed $q\in (1,2]$,
we solve the matrix game where $\mathcal{X}$ is a $\ell_{q}$-norm unit ball
within additive error $\epsilon$ in time $\tilde{O}((n+d)/{\epsilon^{2}})$. We
also provide a corresponding sublinear quantum algorithm that solves the same
task in time $\tilde{O}((\sqrt{n}+\sqrt{d})\textrm{poly}(1/\epsilon))$ 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\'eodory problem and the $\ell_{q}$-margin
support vector machines as applications.
Related papers
- Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups
without Data-Dependent Parameters [10.602399256297032]
We develop a quantum algorithm that runs in $widetildeO(epsilon-1sqrtnd1.5) + mathrmpoly(d/epsilon)$ time.
It provides a quadratic quantum speedup in $n over the classical lower bound without any dependence on data-dependent parameters.
arXiv Detail & Related papers (2023-11-24T19:41:28Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
We give an algorithm which, given positive definite $mathbfK in mathbbRd times d$ with $mathrmnnz(mathbfK)$ nonzero entries, computes an $epsilon$-optimal diagonal preconditioner in time.
We attain our results via new algorithms for a class of semidefinite programs we call matrix-dictionary approximation SDPs.
arXiv Detail & Related papers (2023-10-27T16:54:29Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
We propose fast and practical quantum-inspired classical algorithms for solving linear systems.
Our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems.
arXiv Detail & Related papers (2023-07-13T08:46:19Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly.
We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability.
Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
arXiv Detail & Related papers (2022-09-30T04:15:44Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem.
We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
arXiv Detail & Related papers (2021-09-06T14:21:43Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$.
We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
arXiv Detail & Related papers (2021-05-17T16:40:48Z) - Quantum algorithms for matrix scaling and matrix balancing [9.010461408997646]
Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications.
We study the power and limitations of quantum algorithms for these problems.
We provide quantum implementations of two classical methods: Sinkhorn's algorithm for matrix scaling and Osborne's algorithm for matrix balancing.
arXiv Detail & Related papers (2020-11-25T15:26:59Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm.
We show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting.
arXiv Detail & Related papers (2020-09-15T17:58:25Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.