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

arXiv: https://arxiv.org/abs/2106.09028 · HTML: https://mlsanity.com/paper/2106.09028/

## Key facts

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

## Builds on (most cited first, 25 of 25)

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Exponential convergence of testing error for stochastic gradient methods](https://mlsanity.com/paper/1712.04755/) (2017)
- [Quantum-Inspired Support Vector Machine](https://mlsanity.com/paper/1906.08902/) (2019)
- [Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions](https://mlsanity.com/paper/2004.10756/) (2020)
- [Random Fourier Features via Fast Surrogate Leverage Weighted Sampling](https://mlsanity.com/paper/1911.09158/) (2019)
- [Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors](https://mlsanity.com/paper/1806.05438/) (2018)
- [Data-driven Random Fourier Features using Stein Effect](https://mlsanity.com/paper/1705.08525/) (2017)
- [On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees](https://mlsanity.com/paper/1903.08329/) (2019)
- [Exponential Convergence Rates of Classification Errors on Learning with SGD and Random Features](https://mlsanity.com/paper/1911.05350/) (2019)

## Built on by (most cited first, 4 of 4)

- [Fock State-enhanced Expressivity of Quantum Machine Learning Models](https://mlsanity.com/paper/2107.05224/) (2021)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)

## 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.