2021/06/16 by Hayata Yamasaki, Sho Sonoda, Yamasaki, Hayata +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques #cs.LG #quant-ph #stat.ML
paper · pdf · doi:10.48550/arxiv.2106.09028
42 pages, no figure
openalex publication_date 2021/06/16 · openalex created_date 2021/06/22 · arxiv created 2022/06/13 · arxiv updated 2022/06/15 · openalex updated_date 2026/07/28
Classification is a common task in machine learning. Random features (RFs) stand as a central technique for scalable learning algorithms based on kernel methods, and more recently proposed optimized random features, sampled depending on the model and the data distribution, can significantly reduce and provably minimize the required number of features. However, existing research on classification using optimized RFs has suffered from computational hardness in sampling each optimized RF; moreover, it has failed to achieve the exponentially fast error-convergence speed that other state-of-the-art kernel methods can achieve under a low-noise condition. To overcome these slowdowns, we here construct a classification algorithm with optimized RFs accelerated by means of quantum machine learning (QML) and study its runtime to clarify overall advantage. We prove that our algorithm can achieve the exponential error convergence under the low-noise condition even with optimized RFs; at the same time, our algorithm can exploit the advantage of the significant reduction of the number of features without the computational hardness owing to QML. These results discover a promising application of QML to acceleration of the leading kernel-based classification algorithm without ruining its wide applicability and the exponential error-convergence speed.