量子算法实现稀疏在线学习，速度比经典快两倍。
Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent
- 用截断梯度法在量子框架中实现稀疏在线学习。
- 在高维数据下保持 $O(1/\\/sqrt{T})$ 的损失界，维度越高压缩越明显。
- 适合处理实时高维数据的科研与工业场景。
逻辑回归、支持向量机（SVM）和最小二乘法是统计学与计算机科学领域广泛应用的经典方法。面对实时到达的高维数据，设计能生成稀疏解的在线学习算法至关重要。Langford、Li 与 Zhang（2009）提出的截断梯度下降方法实现了近似最优的在线后悔值。本文基于该方法，为逻辑回归、SVM 和最小二乘构建了量子稀疏在线学习算法。在具备高效量子输入访问的前提下，该算法在时间复杂度上相对于问题维度实现二次加速，同时维持 $O(1/\sqrt{T})$ 的后悔界，其中 $T$ 为迭代次数。
原文摘要 · Abstract (English)
Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of \hyperlink{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of $O(1/\sqrt{T})$, where $T$ is the number of iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。