On The Relative Error of Random Fourier Features for Preserving Kernel Distance
Not on the map. Why?
Abstract (arXiv)
The method of random Fourier features (RFF), proposed in a seminal paper by Rahimi and Recht (NIPS'07), is a powerful technique to find approximate low-dimensional representations of points in (high-dimensional) kernel space, for shift-invariant kernels. While RFF has been analyzed under various notions of error guarantee, the ability to preserve the kernel distance with relative error is less understood. We show that for a significant range of kernels, including the well-known Laplacian kernels, RFF cannot approximate the kernel distance with small relative error using low dimensions. We complement this by showing as long as the shift-invariant kernel is analytic, RFF with poly(ε-1 log n) dimensions achieves ε-relative error for pairwise kernel distance of n points, and the dimension bound is improved to poly(ε-1log k) for the specific application of kernel k-means. Finally, going beyond RFF, we make the first step towards data-oblivious dimension-reduction for general shift-invariant kernels, and we obtain a similar poly(ε-1 log n) dimension bound for Laplacian kernels. We also validate the dimension-error tradeoff of our methods on simulated datasets, and they demonstrate superior performance compared with other popular methods including random-projection and Nystr"om methods.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 25 of its 68 references that are in the map. First posted on arXiv 1 Oct 2022.
Builds on
25 of 68 references.
References · 25
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2016Generalization Properties of Learning with Random Featurescited by 163
- 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 107
- 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 76
- 2015On the Error of Random Fourier Featurescited by 76
- 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
- 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 69
- 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
- 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 41
- 2016Optimality of the Johnson-Lindenstrauss Lemmacited by 41
- 2018On Fast Leverage Score Sampling and Optimal Learningcited by 40
- 2015Optimal Rates for Random Fourier Featurescited by 38
13 more
- 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
- 2018But How Does It Work in Theory? Linear SVM with Random Featurescited by 28
- 2017Gaussian Quadrature for Kernel Featurescited by 21
- 2020Learning to Learn Kernels with Variational Random Featurescited by 18
- 2017Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Boundscited by 16
- 2020Fourier Sparse Leverage Scores and Approximate Kernel Learningcited by 16
- 2020Near Input Sparsity Time Kernel Embeddings via Adaptive Samplingcited by 12
- 2019Random Fourier Features via Fast Surrogate Leverage Weighted Samplingcited by 8
- 2018Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximationcited by 7
- 2017Data-driven Random Fourier Features using Stein Effectcited by 5
- 2017On Data-Dependent Random Features for Improved Generalization in Supervised Learningcited by 4
- 2016Relative Error Embeddings for the Gaussian Kernel Distancecited by 3
- 2020Fast Kernel k-means Clustering Using Incomplete Cholesky Factorizationcited by 1
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.