# Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond

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

## Key facts

- Cited by 109 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2020.

## Built on by (most cited first, 30 of 109)

- [A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness](https://mlsanity.com/paper/2205.00403/) (2022)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Precise Asymptotic Analysis of Deep Random Feature Models](https://mlsanity.com/paper/2302.06210/) (2023)
- [Sampling weights of deep neural networks](https://mlsanity.com/paper/2306.16830/) (2023)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [Large-Scale Learning with Fourier Features and Tensor Decompositions](https://mlsanity.com/paper/2109.01545/) (2021)
- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [TransNet: Transferable Neural Networks for Partial Differential Equations](https://mlsanity.com/paper/2301.11701/) (2023)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [Diverse Sample Generation: Pushing the Limit of Generative Data-free Quantization](https://mlsanity.com/paper/2109.00212/) (2021)
- [Learning with Asymmetric Kernels: Least Squares and Feature Interpretation](https://mlsanity.com/paper/2202.01397/) (2022)
- [Attention-based Random Forest and Contamination Model](https://mlsanity.com/paper/2201.02880/) (2022)
- [Localized Contrastive Learning on Graphs](https://mlsanity.com/paper/2212.04604/) (2022)
- [Random Feature Models for Learning Interacting Dynamical Systems](https://mlsanity.com/paper/2212.05591/) (2022)
- [Efficient Sketches for Training Data Attribution and Studying the Loss Landscape](https://mlsanity.com/paper/2402.03994/) (2024)
- [Concentration of Random Feature Matrices in High-Dimensions](https://mlsanity.com/paper/2204.06935/) (2022)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networks](https://mlsanity.com/paper/2406.04657/) (2024)
- [Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensions](https://mlsanity.com/paper/2201.08082/) (2022)
- [A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression](https://mlsanity.com/paper/2310.00987/) (2023)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)
- [Random Fourier Features for Asymmetric Kernels](https://mlsanity.com/paper/2209.08461/) (2022)
- [Hyperparameter Optimization for Randomized Algorithms: A Case Study on Random Features](https://mlsanity.com/paper/2407.00584/) (2024)

## Abstract (arXiv)

Random features is one of the most popular techniques to speed up kernel methods in large-scale problems. Related works have been recognized by the NeurIPS Test-of-Time award in 2017 and the ICML Best Paper Finalist in 2019. The body of work on random features has grown rapidly, and hence it is desirable to have a comprehensive overview on this topic explaining the connections among various algorithms and theoretical results. In this survey, we systematically review the work on random features from the past ten years. First, the motivations, characteristics and contributions of representative random features based algorithms are summarized according to their sampling schemes, learning procedures, variance reduction properties and how they exploit training data. Second, we review theoretical results that center around the following key question: how many random features are needed to ensure a high approximation quality or no loss in the empirical/expected risks of the learned estimator. Third, we provide a comprehensive evaluation of popular random features based algorithms on several large-scale benchmark datasets and discuss their approximation quality and prediction performance for classification. Last, we discuss the relationship between random features and modern over-parameterized deep neural networks (DNNs), including the use of high dimensional random features in the analysis of DNNs as well as the gaps between current theoretical and empirical results. This survey may serve as a gentle introduction to this topic, and as a users' guide for practitioners interested in applying the representative algorithms and understanding theoretical results under various technical assumptions. We hope that this survey will facilitate discussion on the open problems in this topic, and more importantly, shed light on future research directions.