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 $\varepsilon$-optimal solution with the query complexity of $O(\sqrt{ d}/\varepsilon)$ and $O(1/\varepsilon)$ 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/\varepsilon^2)$ and $\tilde{ O}(\sqrt{ r}d/\varepsilon^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$.
Categories: quant-ph cs.LG