Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees

Abstract

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression. Qualitatively, our results are twofold: on the one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions. At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of low-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.

An extended abstract of this work appears in the Proceedings of the 34th International Conference on Machine Learning (ICML 2017)

Cited by in corpus (41)

• Learning with Density Matrices and Random Features
• Active Regression via Linear-Sample Sparsification
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Modeling of Spatio-Temporal Hawkes Processes with Randomized Kernels
• On Random Subsampling of Gaussian Process Regression: A Graphon-Based Analysis
• Towards an Understanding of Benign Overfitting in Neural Networks
• Generalized Leverage Score Sampling for Neural Networks
• word2ket: Space-efficient Word Embeddings inspired by Quantum Entanglement
• On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees
• Benign Overfitting and Noisy Features
• COKE: Communication-Censored Decentralized Kernel Learning
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• Towards A Unified Analysis of Random Fourier Features
• Gauss-Legendre Features for Gaussian Process Regression
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
• Importance Sampling via Local Sensitivity
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization
• Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features
• Scaling Neural Tangent Kernels via Sketching and Random Features
• Fast Statistical Leverage Score Approximation in Kernel Ridge Regression
• On the Downstream Performance of Compressed Word Embeddings
• The GaussianSketch for Almost Relative Error Kernel Distance
• Quantization Algorithms for Random Fourier Features
• ORCCA: Optimal Randomized Canonical Correlation Analysis
• A Temporal Kernel Approach for Deep Learning with Continuous-time Information
• 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
• Nonlinear Matrix Approximation with Radial Basis Function Components
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Random Features for the Neural Tangent Kernel
• The Statistical Cost of Robust Kernel Hyperparameter Tuning
• Random Fourier Features via Fast Surrogate Leverage Weighted Sampling
• Preconditioning Kaczmarz method by sketching
• Generalization Properties of hyper-RKHS and its Applications
• Optimal Sketching Bounds for Exp-concave Stochastic Minimization