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.

Short version will be published on IEEE TPAMI

References in corpus (26)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Understanding deep learning requires rethinking generalization
• Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures
• Fast rates for support vector machines using Gaussian kernels
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Random Feature Attention
• Orthogonal Random Features
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• 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
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Compact Nonlinear Maps and Circulant Extensions
• Multiple Descent: Design Your Own Generalization Curve
• Implicit Kernel Learning
• 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
• A Precise Performance Analysis of Learning with Random Features
• Universality Laws for High-Dimensional Learning with Random Features
• What causes the test error? Going beyond bias-variance via ANOVA
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• 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
• 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