Optimal Rates for Random Fourier Features

Abstract

Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives due to their capability to represent and model complex relations. While these methods show good versatility, they are computationally intensive and have poor scalability to large data as they require operations on Gram matrices. In order to mitigate this serious computational limitation, recently randomized constructions have been proposed in the literature, which allow the application of fast linear algorithms. Random Fourier features (RFF) are among the most popular and widely applied constructions: they provide an easily computable, low-dimensional feature representation for shift-invariant kernels. Despite the popularity of RFFs, very little is understood theoretically about their approximation quality. In this paper, we provide a detailed finite-sample theoretical analysis about the approximation quality of RFFs by (i) establishing optimal (in terms of the RFF dimension, and growing set size) performance guarantees in uniform norm, and (ii) presenting guarantees in $L^r$ ($1\le r<\infty$) norms. We also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.

To appear at NIPS-2015

References in corpus (4)

• Nonparametric sparsity and regularization
• Towards a Learning Theory of Cause-Effect Inference
• On the Error of Random Fourier Features
• Gradient-free Hamiltonian Monte Carlo with Efficient Kernel Exponential Families

Cited by in corpus (27)

• 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
• Generalization Bounds for Sparse Random Feature Expansions
• Gradient-free Hamiltonian Monte Carlo with Efficient Kernel Exponential Families
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Implicit Regularization of Random Feature Models
• Learning the kernel matrix via predictive low-rank approximations
• COKE: Communication-Censored Decentralized Kernel Learning
• Random Fourier Features for Operator-Valued Kernels
• On Kernel Derivative Approximation with Random Fourier Features
• Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Towards A Unified Analysis of Random Fourier Features
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey
• Kernel-Based Smoothness Analysis of Residual Networks
• Gauss-Legendre Features for Gaussian Process Regression
• Sampled Softmax with Random Fourier Features
• The Error Probability of Random Fourier Features is Dimensionality Independent
• A Survey on Large-scale Machine Learning
• Exponential Convergence Rates of Classification Errors on Learning with SGD and Random Features
• Additive function approximation in the brain
• A Temporal Kernel Approach for Deep Learning with Continuous-time Information
• Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features
• Deep Neural-Kernel Machines
• Large-scale Kernel Methods and Applications to Lifelong Robot Learning
• HD-cos Networks: Efficient Neural Architectures for Secure Multi-Party Computation