On the Error of Random Fourier Features

Abstract

Kernel methods give powerful, flexible, and theoretically grounded approaches to solving many problems in machine learning. The standard approach, however, requires pairwise evaluations of a kernel function, which can lead to scalability issues for very large datasets. Rahimi and Recht (2007) suggested a popular approach to handling this problem, known as random Fourier features. The quality of this approximation, however, is not well understood. We improve the uniform error bound of that paper, as well as giving novel understandings of the embedding's variance, approximation error, and use in some machine learning methods. We also point out that surprisingly, of the two main variants of those features, the more widely used is strictly higher-variance for the Gaussian kernel and has worse bounds.

Published at UAI 2015

References in corpus (2)

• Learning from Distributions via Support Measure Machines
• FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test

Cited by in corpus (24)

• Kernel Mean Embedding of Distributions: A Review and Beyond
• Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
• Domain Generalization by Marginal Transfer Learning
• Online Distributed Learning Over Networks in RKH Spaces Using Random Fourier Features
• Optimal Rates for Random Fourier Features
• Dictionary-Free MRI PERK: Parameter Estimation via Regression with Kernels
• DP-MERF: Differentially Private Mean Embeddings with Random Features for Practical Privacy-Preserving Data Generation
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Efficiently Sampling Functions from Gaussian Process Posteriors
• Random Fourier Features for Operator-Valued Kernels
• No-Trick (Treat) Kernel Adaptive Filtering using Deterministic Features
• Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
• Pathwise Conditioning of Gaussian Processes
• Towards A Unified Analysis of Random Fourier Features
• Randomized Kernel Multi-view Discriminant Analysis
• The Error Probability of Random Fourier Features is Dimensionality Independent
• On Learning the Transformer Kernel
• Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features
• Exponential Convergence Rates of Classification Errors on Learning with SGD and Random Features
• Quantization Algorithms for Random Fourier Features
• A Note on Simulation-Based Inference by Matching Random Features
• Intrinsic Exploration as Multi-Objective RL
• Nonlinear Distribution Regression for Remote Sensing Applications