Research map / Learning theory and algorithms / Kernels and regression theory
On The Relative Error of Random Fourier Features for Preserving Kernel Distance
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RFF on analytic shift-invariant kernels (e.g., Gaussian) instead of general shift-invariant kernels | RFF for kernel distance · theory (relative error of kernel distance) | relative error preservation with poly(eps^-1 log n) dimensions | Helped |
| Use RFF on Laplacian kernels (non-analytic at origin) instead of analytic kernels | RFF for kernel distance · theory (lower bound, (Delta,rho)-bounded inputs) | required target dimension for constant relative error | Hurt |
| Oblivious embedding via l1 to squared-l2 embedding plus RFF on Gaussian kernel (New-Lap) for Laplacian kernels | Laplacian kernel distance · theory (target dimension) | target dimension for relative error | Helped |
| Nystrom (SVD low-rank approximation) as baseline for kernel distance | kernel distance preservation · synthetic Gaussian data, relative error | relative error | Hurt |
Closest papers by meaning
- A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent (NeurIPS 2020 · similarity 0.91)
- TRF: Learning Kernels with Tuned Random Features (AAAI 2022 · similarity 0.91)
- Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees (ICML 2017 · similarity 0.90)
- Quantization Algorithms for Random Fourier Features (ICML 2021 · similarity 0.89)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.87)
- Manifold Random Features (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.