mlsanityData to 7 Oct 2026

Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning

arXiv 2106.09028 ↗First posted 16 Jun 2021quant-ph cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 25 of its 62 references that are in the map. First posted on arXiv 16 Jun 2021.

Builds on

25 of 62 references.

References · 25

  1. 2018Supervised learning with quantum enhanced feature spacescited by 654
  2. 2020A rigorous and robust quantum speed-up in supervised machine learningcited by 270
  3. 2016Generalization Properties of Learning with Random Featurescited by 163
  4. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 136
  5. 2017Quantum machine learning: a classical perspectivecited by 95
  6. 2021Information-theoretic bounds on quantum advantage in machine learningcited by 95
  7. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  8. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  9. 2016Quantum Recommendation Systemscited by 69
  10. 2020On the Quantum versus Classical Learnability of Discrete Distributionscited by 57
  11. 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 41
  12. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 40
13 more
  1. 2019Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learningcited by 37
  2. 2018Learning with SGD and Random Featurescited by 33
  3. 2018But How Does It Work in Theory? Linear SVM with Random Featurescited by 28
  4. 2019Sublinear quantum algorithms for training linear and kernel-based classifierscited by 19
  5. 2020Fourier Sparse Leverage Scores and Approximate Kernel Learningcited by 16
  6. 2017Exponential convergence of testing error for stochastic gradient methodscited by 13
  7. 2019Quantum-Inspired Support Vector Machinecited by 10
  8. 2020Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptionscited by 9
  9. 2019Random Fourier Features via Fast Surrogate Leverage Weighted Samplingcited by 8
  10. 2018Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errorscited by 6
  11. 2017Data-driven Random Fourier Features using Stein Effectcited by 5
  12. 2019On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guaranteescited by 5
  13. 2019Exponential Convergence Rates of Classification Errors on Learning with SGD and Random Featurescited by 1

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 0; 2023: 2.

4 papers.

  1. 2021Fock State-enhanced Expressivity of Quantum Machine Learning Modelscited by 11
  2. 2021Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuitscited by 7
  3. 2023Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computationcited by 5
  4. 2023Advantage of Quantum Machine Learning from General Computational Advantagescited by 4