aiqbench analysis
This paper gives a theoretical speedup for random Fourier features, a standard way to approximate kernel methods in machine learning. The proposed map computes features in near-linear time while keeping near-subgaussian concentration, closing a gap that earlier fast variants left open with weaker guarantees. For ML practitioners, the result matters mainly for scaling kernel approximations to large feature counts, though its practical benefit depends on empirical validation beyond the analysis.
Random Fourier Features in Near-Linear Time
arXiv:2610.14751v1 Announce Type: new 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\'{o}s and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.
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.
Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
arXiv:2610.14751 [cs.LG]
(or arXiv:2610.14751v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.14751 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 221 words
