Quantum Algorithms for Projection-Free Sparse Convex Optimization
It addresses optimization problems in machine learning and data science with quantum speedups, though it appears incremental as it builds on existing quantum and classical frameworks.
This paper tackles projection-free sparse convex optimization for vector and matrix domains, proposing quantum algorithms that achieve query complexities of O(√d/ε) and O(1/ε) for vectors, and time complexities of Õ(rd/ε²) and Õ(√r d/ε³) for matrices, reducing factors like O(√d) and O(d) over classical methods.
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$.