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

Abstract

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.

arXiv commentShort version will be published on IEEE TPAMI

References in corpus (60)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Gaussian Error Linear Units (GELUs)
• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures
• Deep Neural Networks as Gaussian Processes
• On Exact Computation with an Infinitely Wide Neural Net
• Gaussian Process Kernels for Pattern Discovery and Extrapolation
• Fast rates for support vector machines using Gaussian kernels
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Properties of Learning with Random Features
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• A Divide-and-Conquer Solver for Kernel Support Vector Machines
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Random Feature Attention
• Random Projections through multiple optical scattering: Approximating kernels at the speed of light
• Distributing many points on spheres: minimal energy and designs
• Orthogonal Random Features
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Randomized Nonlinear Component Analysis
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Automated Scalable Bayesian Inference via Hilbert Coresets
• Compact Random Feature Maps
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Optimal Rates for Random Fourier Features
• Non-Stationary Spectral Kernels
• Bayesian Nonparametric Kernel-Learning
• Compact Nonlinear Maps and Circulant Extensions
• The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
• On the Error of Random Fourier Features
• Learning with SGD and Random Features
• Recycling Randomness with Structure for Sublinear time Kernel Expansions
• Quadrature-based features for kernel approximation
• But How Does It Work in Theory? Linear SVM with Random Features
• Multiple Descent: Design Your Own Generalization Curve
• Implicit Kernel Learning
• Structured adaptive and random spinners for fast machine learning computations
• Kernel computations from large-scale random features obtained by Optical Processing Units
• Optimal learning rates for Kernel Conjugate Gradient regression
• Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition
• Universality Laws for High-Dimensional Learning with Random Features
• A Precise Performance Analysis of Learning with Random Features
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• What causes the test error? Going beyond bias-variance via ANOVA
• Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
• On the Approximation Properties of Random ReLU Features
• Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off
• Data-dependent compression of random features for large-scale kernel approximation
• Harmonizable mixture kernels with variational Fourier features
• Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• The Error Probability of Random Fourier Features is Dimensionality Independent
• Quantization Algorithms for Random Fourier Features

Cited by in corpus (12)

• Universality Laws for High-Dimensional Learning with Random Features
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Reservoir Computing meets Recurrent Kernels and Structured Transforms
• How Powerful are Shallow Neural Networks with Bandlimited Random Weights?
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
• Positively Weighted Kernel Quadrature via Subsampling
• Kernel approximation on algebraic varieties
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Surrogate-Based Simulation Optimization
• An Insect-Inspired Randomly, Weighted Neural Network with Random Fourier Features For Neuro-Symbolic Relational Learning
• Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features
• Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamics