PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Fanghui Liu, Xiaolin Huang, Yudong Chen, Johan A. K. Suykens

arXiv:2004.11154v5stat.MLcs.LG

TL;DR

Large-scale kernel learning needs scalable approximations, while the rapidly expanding random-features literature lacks a unified overview of its algorithms, theory, experiments, and neural-network connections. This survey organizes ten years of work, compares representative methods, synthesizes approximation and risk results, and discusses over-parameterized regimes. It concludes that random features remain useful for understanding and improving DNNs despite important theoretical gaps.

  • Problem

    Kernel methods offer nonlinear learning but face high space and time complexity at large scale, while random-features research has expanded across algorithms, theory, applications, and neural-network analysis.

  • Method

    The survey unifies and reviews random-feature algorithms, theoretical approximation and generalization results, empirical comparisons, and connections to over-parameterized neural networks.

  • Results

    The survey reports that random features can require exponentially many features to approximate a single ReLU neuron, while documenting broad algorithmic, theoretical, and empirical developments.

  • Takeaways & Limitations

    Despite existing theoretical limitations, random-features models remain useful for understanding and improving deep neural networks and motivating future research.

  • Takeaways & Limitations

    The survey identifies a substantial gap between random-features theory and practical deep neural networks, including difficulty transferring results to deep but not-too-wide networks.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Kernel methods capture nonlinear structure but become impractical at large sample sizes, motivating explicit random-feature mappings and a decade of algorithmic and theoretical work. This survey organizes those developments, evaluates representative methods, and examines their links to over-parameterized models.

  • Motivation: O(n^3) training time and O(n^2) storage make kernel ridge regression difficult to scale with n samples.Kernel methods otherwise provide effective nonlinear learning through implicit RKHS feature maps.
  • Motivation: O(ns^2) time and O(ns) memory enable linear learning after constructing an explicit mapping Ψ with k(x, y) ≈ Ψ(x)⊤Ψ(y).The mapping provides a finite-dimensional approximation while retaining nonlinear-model expressiveness.
  • Random features: Random Fourier features approximate shift-invariant kernels by sampling frequencies from the inverse Fourier-transform distribution and using an explicit feature map.The number of features is commonly chosen between the original dimension d and sample size n when n ≫ d.
  • Theory: The survey reviews approximation and generalization questions, including how many features preserve approximation quality or avoid risk loss.It also discusses why good kernel approximation may fail to imply good generalization.
  • Scope: The survey covers algorithms, theory, experiments, and over-parameterized neural-network connections across work from the past ten years.Its stated contributions include a unified algorithmic framework, systematic empirical comparisons, and discussion of theoretical gaps.

2 PRELIMINARIES AND TAXONOMIES

This section introduces supervised learning with RKHS kernels, explicit random-feature approximations, and the theoretical foundations connecting kernels to Fourier, spherical-harmonic, and neural-network constructions. It also distinguishes kernel classes for which the available random-feature foundations differ.

  • Problem setting: The supervised-learning setup samples n labeled examples from an unknown distribution and evaluates estimators using empirical or expected risk.Regularization typically uses λ(n)→0, with λ := n^-α for α ∈ (0, 1].
  • Random-feature formulation: An explicit randomized map ϕ: R^d→R^s replaces k(x, x′) with an inner product and turns learning into finite-dimensional linear estimation.For least squares, the resulting problem is linear ridge regression in the span of the random features.
  • Theoretical foundation: Bochner’s theorem provides the foundation for stationary kernels by representing continuous shift-invariant positive-definite functions through Fourier spectral measures.RFF uses Monte Carlo samples from the normalized spectral distribution to construct the approximation.
  • Neural-network connection: Two-layer networks with fixed Gaussian first-layer weights and optimized output weights correspond to random-feature models, with the activation determining the kernel.Cosine and sine activations yield the Gaussian kernel, while ReLU yields the first-order arc-cosine kernel.
  • Kernel classes: Polynomial dot-product kernels require different random-feature foundations because they admit neither spherical harmonics nor the stationary-kernel representation in Eq. (6).Approaches include Maclaurin expansion, tensor sketching, and oblivious subspace embeddings.

3 DATA-INDEPENDENT ALGORITHMS

Data-independent algorithms construct random features without training data, using sampling, structured transforms, orthogonality, quantization, and low-discrepancy designs to balance computation, approximation quality, and variance.

  • Monte Carlo sampling: Fastfood, P-model, and SCRF accelerate feature construction with structured matrices while preserving unbiasedness under stated variance properties.The P-model has variance close to RFF and O(1/d) convergence; SCRF uses O(s) storage and has the same variance as RFF.
  • Quantization: Under the same memory budget, quantized random features achieve better generalization performance than Nyström approximation.LP-RFF quantizes Gaussian-kernel RFF, and related work uses Lloyd-Max quantization with fewer bits.
  • Variance reduction: Orthogonal random features reduce Monte Carlo randomness by making feature directions more uniform while retaining sampled norms.ORF is unbiased and has lower variance than RFF under conditions such as large d and small τ; SORF replaces dense orthogonal matrices with structured matrices.
  • Quadrature-based methods: Quadrature methods select deterministic or randomized integration points, but tensor-product Gaussian quadrature requires s = L^d points and suffers from the curse of dimensionality.Sparse-grid and stochastic spherical-radial rules reduce the number of points needed for high-dimensional integration.

4 DATA-DEPENDENT ALGORITHMS

Data-dependent algorithms use training data to design or learn random features, grouping into leverage-score sampling, feature selection, and kernel learning approaches.

  • Overview: Data-dependent methods design or learn random features from training data to improve approximation quality or generalization performance.They are grouped into leverage score sampling, random feature selection, and kernel learning by random features.
  • Leverage score sampling: Leverage-score sampling uses importance sampling to select Fourier features with fewer features and theoretical guarantees.LS-RFF approximates the kernel matrix to compute leverage scores, while SLS-RFF uses a surrogate distribution with O(ns^2) complexity.
  • Random feature selection: Random feature selection methods first generate many candidate features and then learn a sparse subset or weighted representation from data.KA-RFF uses kernel alignment, KP-RFF uses an energy-based rule, and CLR-RFF approximately solves a compressed low-rank optimization problem.
  • Kernel learning by random features: Kernel learning by random features learns a kernel spectral distribution from data and then trains a prediction model using the learned features.The common two-stage scheme first learns features and subsequently incorporates them into a kernel method or linear model.
  • Kernel learning by random features: One-stage methods jointly learn the nonlinear feature mapping and prediction model through a single optimization or spectral inference procedure.Examples combine hinge-loss optimization with alternating SGD, or Fourier-domain kernel alignment with SVM training.
  • Theoretical results: Theoretical work classifies data-dependent random-feature results by kernel approximation, spectral approximation, empirical risk, and related metrics.Figure 3 organizes representative results around approximation and generalization questions.

5 THEORETICAL ANALYSIS

Theoretical analyses ask how many random features ensure accurate kernel approximation or preserve learning risk, under assumptions governing sampling, noise, source conditions, and eigenvalue decay. Results show that feature requirements vary substantially by approximation metric, loss, sampling distribution, and regularization, while better kernel approximation need not imply better generalization.

  • Learning guarantees: Ω(n) features first guaranteed no loss for Lipschitz losses, later improving to Ω(√n log n) under refined analyses.For squared loss, Ω(√n log n) RFF features can achieve the minimax rate O(1/√n) under the stated assumptions.
  • Kernel approximation: Ω(ϵ^-2d log(1/ϵδ)) features ensure ϵ uniform approximation with probability greater than 1 − δ under covering-number analysis.This bound applies to stationary kernels and also extends to dot-product kernels through random Maclaurin features.
  • Kernel approximation: O(ϵ^-2 log |S|) features suffice for ϵ approximation accuracy, improving over O(ϵ^-2|S|^2 log(|S|/ϵ)) from earlier bounds.The improved result follows from a consistency rate of O_p(s^-1 log |S|) in compact-convergence topology.
  • Implementation effects: Low-precision LP-RFF has minimal feature-count impact when quantization noise is small relative to regularization.As s → ∞, Δ1 converges to zero for any precision b, while Δ2 is bounded by δ^2.
  • Expected-risk guarantees: Under suitable assumptions and parameter choices, Ω(√n log n) features suffice for KRR to attain minimax optimal rates.The generalization theorem unifies results across source, noise, and eigenvalue-decay assumptions; exponential decay can improve the requirement to Ω(√n log log n).
  • Other losses: For SVM with optimized sampling and low-noise or separation assumptions, theoretical bounds specify learning rates and required feature counts.The stronger separation condition improves the result relative to the low-noise setting.
  • Open problems: Better kernel approximation does not guarantee lower generalization risk, even when one approximation is closer to the original kernel in a norm.The survey identifies this approximation–generalization inconsistency as an open problem and gives a KRR proposition exhibiting it.

6 EXPERIMENTS

The experiments compare random-features algorithms across kernels and benchmark datasets using approximation error, computational cost, and classification accuracy. Results highlight strong approximation by SSF, ORF, and QMC in many cases, while approximation differences do not always translate into test-accuracy differences.

  • Experimental settings: Gaussian-kernel comparisons include RFF, ORF, SORF, ROM, Fastfood, QMC, SSF, GQ, and LS-RFF, spanning sampling, variance reduction, and structural speedup techniques.The compared methods include both data-independent and data-dependent approaches.
  • Experimental settings: Polynomial-kernel experiments use RM, TS, and TRP because polynomial kernels admit neither Bochner’s theorem nor the standard random-feature sampling formulation.The polynomial-kernel order is set to b = 2.
  • Experimental settings: Experiments evaluate approximation error, time cost, and test accuracy on non-image, image, and ultra-large-scale datasets.The evaluation combines random-feature kernel approximation with linear classification and uses streaming for MNIST 8M under memory constraints.
  • Non-image benchmark results: SSF, ORF, and QMC achieve promising approximation performance in most cases.SSF performs particularly well for small s, whereas its improvement may weaken when s is large; QMC and ORF often work well in the large-s setting.
  • Image classification results: ORF and SSF yield the best approximation quality on MNIST, but most algorithms show no significant difference in test accuracy.Figure 6(a) compares these quantities across s = 1000 to s = 10,000 random features.
  • Image classification results: Structured methods such as Fastfood, SORF, and ROM do not achieve significant time reductions in MATLAB because the Walsh-Hadamard transform implementation is relatively inefficient.Most algorithms have similar random-feature generation costs, except the data-dependent LS-RFF method.

7 TRENDS: HIGH-DIMENSIONAL RANDOM FEATURES IN OVER-PARAMETERIZED SETTINGS

High-dimensional random-feature analyses study over-parameterized regimes through asymptotic and random-matrix techniques, including their double-descent behavior. The survey also emphasizes that these models clarify some neural-network regimes while leaving substantial gaps in approximation power and practical DNN relevance.

  • Connections to DNNs: Random features can be viewed as two-layer large-width neural networks with random first-layer weights and an optimized output layer.This structure is more amenable to theoretical analysis than arbitrary deep networks.
  • Problem setting: High-dimensional analyses let n, d, and s grow together, with d/n → ψ1 and s/n → ψ2; overparameterization corresponds to ψ2 ≥ 1.The basic setting commonly uses Gaussian or spherical training data, linear targets, Gaussian label noise, and random Gaussian features with ReLU activation.
  • Analytical techniques: Random-matrix methods analyze spectral distributions and deterministic equivalents to characterize bias, variance, generalization, and double descent.Studies use Stieltjes transforms of related random matrices, including finite-size and asymptotic analyses.
  • Double descent: At the interpolation threshold ψ2 = 1, both bias and variance peak and diverge as λ → 0 in the stated asymptotic least-squares setting.The survey also describes refined variance decompositions by label noise, initialization, and feature-sampling randomness.
  • Discussion and limitations: Theoretical transfer to practical deep networks remains difficult because real DNNs are typically deep but not excessively wide, and random features can have limited approximation power in lazy regimes.Under spherical data, random features may capture only degree-ℓ polynomial projections, while NTK may capture only quadratic functions in the cited setting.
  • Discussion and limitations: A single ReLU neuron may require exponentially many random features in d, consistent with exponential worst-case requirements for several kernel-approximation methods.The cited classical result gives s = Ω(exp(d)) for achieving an ϵ approximation error.
  • Future directions: Despite worst-case exponential requirements, random features remain a useful tool for analyzing DNNs in certain regimes and may inform pruning-related theories such as the Lottery Ticket Hypothesis.The survey notes that random-feature RKHSs can still be dense for broad classes of features.

8 CONCLUSION

The survey reviews random-features algorithms, theory, applications, and over-parameterized DNN connections while identifying open problems and limitations. It highlights both practical usefulness and unresolved gaps between approximation quality, generalization, and neural-network behavior.

  • The survey reviews random-features algorithms, theoretical results, generalization in over-parameterized regimes, and their relationship to DNNs.It also discusses limitations, potential, and open problems for future research.
  • Random features are simpler to implement, easy to parallelize, and naturally applicable to streaming or dynamic data.
  • Better kernel approximation does not directly translate to lower generalization errors, and the survey only partly explains this phenomenon.The survey identifies this relationship as requiring further in-depth study.
  • Kernel learning via spectral density can be combined with GANs to characterize data relationships and similarities through an implicit probability density.The survey presents this as an area for further research.
  • Double-descent analyses remain limited by assumptions on data generation, model formulation, and target functions, with phenomena beyond double descent also under study.
  • Significant theoretical and empirical gaps remain between random-features models and practical neural networks, although random features may still help understand and improve DNNs.The survey cites Lottery Ticket Hypothesis connections as a promising direction.

APPENDIX A PROOF OF PROPOSITION 1

The proof compares prediction errors from two kernel approximations by expressing their residual matrix and vector errors and analyzing a scalar error term under stated assumptions. It establishes that one approximation can have a larger error-related quantity despite no larger residual norms, under additional spectral conditions.

  • The proof represents the random-features kernel as f K = ZZ⊤ and contrasts its estimator with the exact KRR estimator.The comparison uses the excess-risk formulation for least squares.
  • Kernel approximation preserves Hilbert-space inner products, but this preservation does not immediately guarantee a small estimator prediction error.The proof introduces residual matrix E and residual vector ˜ϵ to analyze the discrepancy.
  • The proof defines T(E, ˜ϵ) as an inner product involving the prediction residuals, then compares T1 and T2 for two algorithms.
  • The argument assumes a positive-semidefinite residual matrix, nonsingular approximated kernels, ordered largest eigenvalues, polynomial eigenvalue decay, and nonnegative T(E, ˜ϵ).These are the three assumptions used to prove existence of the comparison case.
  • The prediction-error comparison follows from resolvent identities and upper- and lower-bound inequalities involving the perturbation terms and eigenvalues.
  • Under ordered residual norms, the proof constructs a case where T1(E1, ˜ϵ1) ≥ cT2(E2, ˜ϵ2) for some constant c.The geometric construction is illustrated in Figure 8, and the conclusion relies on finite condition number or effective dimension conditions.

APPENDIX B EXPERIMENTS

The experiments compare random-features approaches across kernels, datasets, approximation error, computation time, and classification accuracy. They include Gaussian-kernel evaluations on eight non-image datasets, other kernel families, and an ultra-large-scale dataset.

  • The experiments evaluate compared approaches across several benchmark datasets and various kernels.The section organizes results by Gaussian, arc-cosine, polynomial, and ultra-large-scale settings.
  • Gaussian-kernel experiments on eight non-image datasets measure approximation error, random-feature generation time, and classification accuracy from linear regression and liblinear.
  • Arc-cosine and polynomial-kernel experiments report approximation error and linear-regression test accuracy.
  • An ultra-large-scale dataset is used to further validate the related algorithms.

B.1 Results on Gaussian kernels

Across Gaussian-kernel datasets, increasing the number of random features reduces approximation error and increases classification accuracy, while computational differences depend on the algorithm and implementation setting.

  • As the number of random features increases, algorithms achieve smaller approximation error and higher classification accuracy for both linear-regression and liblinear classifiers.
  • Most algorithms have similar random-feature generation time, except SSF and LS-RFF.SSF constructs a transformation matrix in advance, whereas LS-RFF computes approximated ridge leverage scores.
  • Fastfood, SORF, and ROM do not show reduced time cost in these experiments despite theoretical time-complexity reductions.The datasets generally have feature dimensions from 10 to 100, and Matlab's Walsh-Hadamard implementation is relatively inefficient.

B.2 Results on Arc-cosine kernels

Across zero- and first-order arc-cosine kernels, SSF and QMC generally provide the lowest approximation errors, while classification accuracies remain similar across most algorithms. ORF and SORF do not clearly outperform RFF, and their variance-reduction theory remains limited to Gaussian kernels.

  • SSF and QMC generally achieve lower approximation error than the other arc-cosine-kernel approaches.This agrees with the theoretical findings summarized in the survey.
  • RFF, ORF, and SORF show no distinct approximation difference on arc-cosine kernels.
  • Variance-reduction results for ORF and SORF are currently established only for the Gaussian kernel, leaving their transfer to arc-cosine kernels unclear.
  • Approximation error and test accuracy are evaluated across eight datasets for zero- and first-order arc-cosine kernels.
  • Most algorithms have relatively small differences in test accuracy, following a tendency similar to that observed for the Gaussian kernel.Arc-cosine approximation errors are often larger because the method approximates a d-dimensional integral whose integrand smoothness affects performance.

B.3 Results on Polynomial kernels

For polynomial kernels, TRP, TensorSketch, and random Maclaurin sketches are evaluated across eight datasets. TRP and TensorSketch achieve similar test accuracy and outperform random Maclaurin, while random Maclaurin is computationally efficient.

  • TRP, TensorSketch, and random Maclaurin are evaluated for polynomial-kernel approximation and prediction across eight datasets.
  • TensorSketch and TRP achieve similar test accuracy and significantly outperform random Maclaurin.The survey attributes random Maclaurin's weaker performance to its unnecessary generality for polynomial kernels.
  • Random Maclaurin is computationally efficient because it uses a Maclaurin expansion scheme.
  • TensorSketch requires substantial feature-generation time because it uses a fixed sampling probability, whereas TRP uses flexible sampling proportional to its Maclaurin coefficient.

B.4 Results on the MNIST-8M dataset

On MNIST-8M, the survey compares ten random-feature algorithms for Gaussian and arc-cosine kernels in a streaming setting under a fixed feature budget. Table 9 reports approximation, training, test, and total-time metrics, with ORF/SORF and SSF strongest for Gaussian approximation but ORF less effective on arc-cosine kernels.

  • Ten algorithms are evaluated on Gaussian and arc-cosine kernels for MNIST-8M using a streaming framework to reduce time and space complexity.
  • Table 9 reports approximation error, training error, test error, and total time cost under s = 4096.
  • ORF/SORF and SSF achieve the best approximation performance on the Gaussian kernel.
  • ORF does not significantly improve approximation ability on arc-cosine kernels.This matches the survey's earlier discussion of medium-sized datasets.
Loading 2004.11154v5…