Quantum Algorithms for Projection-Free Sparse Convex Optimization

Abstract

This paper considers the projection-free sparse convex optimization problem for the vector domain and the matrix domain, which covers a large number of important applications in machine learning and data science. For the vector domain $\mathcal{D}\subset {\mathbb{R}}^d$, we propose two quantum algorithms for sparse constraints that finds a $\epsilon$-optimal solution with the query complexity of $O(\sqrt{d}/\epsilon )$ and $O(1/\epsilon )$ by using the function value oracle, reducing a factor of $O(\sqrt{d})$ and $O(d)$ over the best classical algorithm, respectively, where $d$ is the dimension. For the matrix domain $\mathcal{D}\subset {\mathbb{R}}^{d\times d}$, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to $\tilde{O}(rd/{\epsilon }^2)$ and $\tilde{O}(\sqrt{r}d/{\epsilon }^3)$ for computing the update step, reducing at least a factor of $O(\sqrt{d})$ over the best classical algorithm, where $r$ is the rank of the gradient matrix. Our algorithms show quantum advantages in projection-free sparse convex optimization problems as they outperform the optimal classical methods in dependence on the dimension $d$.