Fast random features speed up kernel methods with strong accuracy
Random Fourier Features in Near-Linear Time
Machine LearningData Structures and Algorithms
Summary
Kernel methods help compare data points in complex ways but can be slow to compute. The authors improved a fast technique called Fastfood to make these computations run almost as fast as reading the data itself. Their method keeps the accuracy close to the best possible while being much quicker than before. This helps computers work better with large, high-dimensional datasets.
What this means in practice
- •For machine learning engineers: Speed up kernel-based learning algorithms on large, high-dimensional datasets by using near-linear time random feature approximations with strong accuracy guarantees.
- •For data analytics teams: Process and analyze large-scale data involving complex similarity measures faster without compromising on the quality of kernel approximations.
Authors
Sepideh Mahabadi, Sandeep Silwal, Tal Wagner
Abstract
Random Fourier features approximate a shift-invariant kernel in $\mathbb{R}^d$, such as the Gaussian kernel $\exp(-\tfrac12\|x-y\|_2^2)$, using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating $m$ such features requires $O(md)$ time. A long line of work on structured random features has accelerated this computation for the Gaussian kernel and other radial kernels, albeit with weaker concentration guarantees. We close this gap by showing a random feature map that can be computed in near-linear time $O((d+m)\log d)$ and yields near-subgaussian concentration. We obtain it through a new and tighter analysis of the Fastfood feature map of Le, Sarlós and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.