# Random Fourier Features via Fast Surrogate Leverage Weighted Sampling

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2019.

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

- [Quantum Adaptive Fourier Features for Neural Density Estimation](https://mlsanity.com/paper/2208.00564/) (2022)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Generalized Leverage Scores: Geometric Interpretation and Applications](https://mlsanity.com/paper/2206.08054/) (2022)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Decentralized Kernel Ridge Regression Based on Data-Dependent Random Feature](https://mlsanity.com/paper/2405.07791/) (2024)
- [Spectral Convergence of Random Feature Method in Multiple Dimensions](https://mlsanity.com/paper/2609.03401/) (2026)
- [A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features](https://mlsanity.com/paper/2609.10729/) (2026)

## Abstract (arXiv)

In this paper, we propose a fast surrogate leverage weighted sampling strategy to generate refined random Fourier features for kernel approximation. Compared to the current state-of-the-art method that uses the leverage weighted scheme [Li-ICML2019], our new strategy is simpler and more effective. It uses kernel alignment to guide the sampling process and it can avoid the matrix inversion operator when we compute the leverage function. Given n observations and s random features, our strategy can reduce the time complexity from O(ns^2+s^3) to O(ns^2), while achieving comparable (or even slightly better) prediction performance when applied to kernel ridge regression (KRR). In addition, we provide theoretical guarantees on the generalization performance of our approach, and in particular characterize the number of random features required to achieve statistical guarantees in KRR. Experiments on several benchmark datasets demonstrate that our algorithm achieves comparable prediction performance and takes less time cost when compared to [Li-ICML2019].