Quantum Algorithms for Projection-Free Sparse Convex Optimization

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 D subset ℝd, we propose two quantum algorithms for sparse constraints that finds a varepsilon-optimal solution with the query complexity of O(√d/varepsilon) and O(1/varepsilon) by using the function value oracle, reducing a factor of O(√d) and O(d) over the best classical algorithm, respectively, where d is the dimension. For the matrix domain D subset ℝd× d, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to tildeO(rd/varepsilon2) and tildeO(√rd/varepsilon3) for computing the update step, reducing at least a factor of O(√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.