量子算法加速稀疏凸优化，维度越高越快。
Quantum Algorithms for Projection-Free Sparse Convex Optimization
- 用量子查询替代经典投影，降低计算复杂度。
- 向量域提速√d倍，矩阵域提速至少√d倍。
- 适合高维机器学习与数据科学中的优化任务。
本文研究向量域和矩阵域上的无投影稀疏凸优化问题，涵盖机器学习与数据科学中大量重要应用。对于向量域 $/mathcal{D} sub R^d$，提出两种量子算法，仅需 $O(qrt{d}/eps)$ 和 $O(1/eps)$ 次函数值查询即可获得 $eps$-最优解，相比最优经典算法分别降低 $O(qrt{d})$ 与 $O(d)$ 因子。对于矩阵域 $/mathcal{D} sub R^{d imes d}$，针对核范数约束提出两种量子算法，计算更新步的时间复杂度降至 $ ilde{O}(rd/eps^2)$ 与 $ ilde{O}(qrt{r}d/eps^3)$，相较最优经典算法至少降低 $O(qrt{d})$ 因子，其中 $r$ 为梯度矩阵的秩。结果表明，量子算法在无投影稀疏凸优化中具有显著优势。
原文摘要 · Abstract (English)
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$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。