mlsanityData to 14 Oct 2026

Random Fourier Features in Near-Linear Time

arXiv 2610.14751 ↗First posted 10 Oct 2026cs.LG cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

Random Fourier features approximate a shift-invariant kernel in ℝd, such as the Gaussian kernel exp(-tfrac12|x-y|22), 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'os and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 20 of its 46 references that are in the map. First posted on arXiv 10 Oct 2026.

Builds on

20 of 46 references.

References · 20

  1. 2021Random Feature Attentioncited by 354
  2. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
  3. 2016Orthogonal Random Featurescited by 91
  4. 2014Fastfood: Approximate Kernel Expansions in Loglinear Timecited by 74
  5. 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 45
  6. 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 42
  7. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 33
  8. 2020Kernel Density Estimation through Density Constrained Near Neighbor Searchcited by 29
  9. 2018Quadrature-based features for kernel approximationcited by 26
  10. 2015The Bernstein Mechanism: Function Release under Differential Privacycited by 13
  11. 2016Recycling Randomness with Structure for Sublinear time Kernel Expansionscited by 9
  12. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 9
8 more
  1. 2023Fast Private Kernel Density Estimation via Locality Sensitive Quantizationcited by 9
  2. 2024Efficiently Computing Similarities to Private Datasetscited by 9
  3. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 5
  4. 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 3
  5. 2025Scalable Unsupervised Segmentation via Random Fourier Feature-based Gaussian Processcited by 1
  6. 2026New Bounds for Kernel Sums via Fast Spherical Embeddingscited by 1
  7. 2026Flexformer: Flexible Linear Transformer with Learnable Attention Kernelcited by 1
  8. 2026Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimationcited by 1

Built on by

Not cited yet.