mlsanityData to 7 Oct 2026

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

arXiv 2004.11154 ↗First posted 23 Apr 2020stat.ML cs.LGcited by 107

Not on the map. Why?

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.

Key facts. Cited by 107 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 25; 2023: 17; 2024: 25; 2025: 16; 2026: 10.

107 papers.

Sort:

By area:

  1. 2022A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awarenesscited by 49
  2. 2021Positively Weighted Kernel Quadrature via Subsamplingcited by 25
  3. 2021Hybrid Random Featurescited by 25
  4. 2023Precise Asymptotic Analysis of Deep Random Feature Modelscited by 22
  5. 2023Sampling weights of deep neural networkscited by 20
  6. 2023Taming graph kernels with random featurescited by 17
  7. 2023Tanimoto Random Features for Scalable Molecular Machine Learningcited by 15
  8. 2021The Separation Capacity of Random Neural Networkscited by 14
  9. 2021Large-Scale Learning with Fourier Features and Tensor Decompositionscited by 14
  10. 2021On Learning the Transformer Kernelcited by 14
  11. 2021Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learningcited by 13
  12. 2023TransNet: Transferable Neural Networks for Partial Differential Equationscited by 13
38 more
  1. 2021Diverse Sample Generation: Pushing the Limit of Generative Data-free Quantizationcited by 11
  2. 2022Improved Random Features for Dot Product Kernelscited by 11
  3. 2022Learning with Asymmetric Kernels: Least Squares and Feature Interpretationcited by 11
  4. 2022Attention-based Random Forest and Contamination Modelcited by 10
  5. 2022Localized Contrastive Learning on Graphscited by 10
  6. 2022Random Feature Models for Learning Interacting Dynamical Systemscited by 10
  7. 2024Efficient Sketches for Training Data Attribution and Studying the Loss Landscapecited by 10
  8. 2023Simplex Random Featurescited by 9
  9. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  10. 2023Random Fourier Signature Featurescited by 9
  11. 2024From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networkscited by 9
  12. 2022Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensionscited by 8
  13. 2022Concentration of Random Feature Matrices in High-Dimensionscited by 8
  14. 2023A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regressioncited by 8
  15. 2025GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projectioncited by 8
  16. 2021Random matrices in service of ML footprint: ternary random features with no performance losscited by 7
  17. 2022Random Fourier Features for Asymmetric Kernelscited by 7
  18. 2024Hyperparameter Optimization for Randomized Algorithms: A Case Study on Random Featurescited by 7
  19. 2021On the Double Descent of Random Features Models Trained with SGDcited by 5
  20. 2022Local Random Feature Approximations of the Gaussian Kernelcited by 5
  21. 2022AGBoost: Attention-based Modification of Gradient Boosting Machinecited by 5
  22. 2022AD-DMKDE: Anomaly Detection through Density Matrices and Fourier Featurescited by 5
  23. 2024KnowFormer: Revisiting Transformers for Knowledge Graph Reasoningcited by 5
  24. 2021Kernel approximation on algebraic varietiescited by 4
  25. 2022Towards a Unified Framework for Uncertainty-aware Nonlinear Variable Selection with Theoretical Guaranteescited by 4
  26. 2022Attention and Self-Attention in Random Forestscited by 4
  27. 2023On Generalization Bounds for Projective Clusteringcited by 4
  28. 2023Robust and Communication-Efficient Federated Domain Adaptation via Random Featurescited by 4
  29. 2024Optimal Kernel Quantile Learning with Random Featurescited by 4
  30. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  31. 2025Dynamic Regret Reduces to Kernelized Static Regretcited by 4
  32. 2021Sharp Analysis of Random Fourier Features in Classificationcited by 3
  33. 2022Generalized Leverage Scores: Geometric Interpretation and Applicationscited by 3
  34. 2022Kernelized multi-graph matchingcited by 3
  35. 2022Gradient-enhanced deep neural network approximationscited by 3
  36. 2023Optimal Nonlinearities Improve Generalization Performance of Random Featurescited by 3
  37. 2024Optimal Rates and Saturation for Noiseless Kernel Ridge Regressioncited by 3
  38. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 3

50 most cited of 107 All 107 (JSON)