Random Fourier Features in Near-Linear Time

arXiv:2610.14751 · cs.LG, cs.DS · Submitted 2026-10-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Random Fourier Features in Near-Linear Time".

Jane: The gist: The authors prove that a random feature map for kernels like the Gaussian kernel can be computed in near-linear time, specifically O((d + m) log d),

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at a paper called "Random Fourier Features in Near-Linear Time." It's by Sandeep Mahabadi and Sandeep Silwal, published on Microsoft Research. The title itself tells you the main goal: they want to compute these random feature maps in near-linear time.

Jane: That sounds a bit intimidating when you hear "near-linear time," Tom. What does that actually mean for us? Are we talking about something that's fast enough to actually use in real AI applications, or is it just theoretical speed?

Lu: It means they're aiming for something like O((d plus m) log d) time complexity, where d is the dimension of the input data and m is the size of the feature map. That would be a significant improvement over what we see now.

Meng: If it's truly near-linear, that's good for deployment because we usually deal with massive datasets. But what about memory? Does this approach use a huge amount of memory to store these features?

Lalam: The paper suggests the feature map size m depends on some parameters like epsilon and delta, but the computation time is what they are really focusing on improving here, aiming for that O((d plus m) log d) bound <ref:2610.14751#pg3>.

Tom: Exactly. The authors are showing that while previous fast variants existed using things like Randomized Hadamard Transforms, they hadn't quite hit this near-linear time with good concentration guarantees yet. They're solving that gap by proving the existence of this map for the Gaussian kernel and others <ref:2610.14751#pg2>.

Jane: So, it sounds like they took an existing concept—random features—and used a new, tighter analysis based on something called Brascamp-Lieb inequalities to get that better time bound.

Lu: That's right. They are simplifying a map from the Fastfood feature map from Le and Smola in two thousand thirteen but their contribution is the new analysis showing that this simplified form works with near-linear time O((d plus m) log d) <ref:2610.14751#pg2>.

Meng: I wonder if they've actually tested this on any real traffic or large-scale data. Theoretical bounds are one thing, but production systems break when you hit real noise.

Lalam: The paper focuses heavily on the theoretical guarantees for the Gaussian kernel and extending it to other radial kernels <ref:2610.14751#pg3>. It establishes that this map yields strong concentration for the Gaussian kernel and also works for other kernels under mild assumptions <ref:2610.14751#pg3>.

The paper's summary: Tom: Okay, so what's the core finding? The main idea of "Random Fourier Features in Near-Linear Time" is that we can construct a random feature map F that approximates any shift-invariant kernel, like the Gaussian kernel, in near-linear time.

Jane: To put that plainly for someone driving right now, it means instead of taking a massive amount of time to calculate how similar two things are based on their distance—which is what kernels do—we can estimate that similarity using a map that's only slightly slower than the dimension of the data plus the size of our feature space.

Lu: The summary points out that this map F is a simplified version of the Fastfood feature map, and their key contribution is a new, tighter analysis using Brascamp-Lieb inequalities <ref:2610.14751#pg2>. This analysis allows them to show strong concentration guarantees for the Gaussian kernel and other radial kernels <ref:2610.14751#pg3>.

Meng: So, the implication is that we can get a good approximation of complex kernel relationships without incurring that massive computational penalty. That sounds like something that could actually make training larger models more feasible on smaller hardware.

Lalam: Exactly. They provide a randomized map F: R d to R 2m such that for any x and y, the expected inner product E

F(x) transpose F(y): equals exp(- x minus y squared / two) <ref:2610.14751#pg3>.

Tom: That inner product is exactly what defines the Gaussian kernel—the similarity based on Euclidean distance—and they show it's achieved in O((d plus m) log d) time <ref:2610.14751#pg2>.

Jane: And the concentration part is also strong. They have a tail bound showing that the actual feature map result is very close to that expected value, with a probability of failure bounded by something involving exp minus m t squared over four log(two d over eta) <ref:2610.14751#pg3>.

Lu: That strong concentration guarantee is what makes this result robust. It means the approximation isn't just usually good; it's very reliably good, which is crucial for building stable models on these features <ref:2610.14751#pg3>.

The paper's improvements: Tom: So, what are the specific improvements they are highlighting compared to what came before? It seems like the main improvement is getting that near-linear time computation while maintaining strong concentration for the Gaussian kernel.

Jane: Right. They are taking existing fast variants, which used randomized Hadamard transforms or RHTs, and showing that their new analysis allows them to achieve O((d plus m) log d) instead of whatever complexity those previous methods were hitting.

Lu: The improvement lies in the tighter analysis of the Fastfood feature map <ref:2610.14751#pg2>. They use Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels to prove this result <ref:2610.14751#pg2>.

Meng: It sounds like they're not just tweaking the algorithm; they're proving *why* it works with these specific mathematical tools, which gives us a lot of confidence in the result, even if we haven't run a full production test yet.

Lalam: They are also extending this beyond just the Gaussian kernel to other radial kernels under mild assumptions <ref:2610.14751#pg3>. This means they aren't limited just to one specific type of kernel anymore.

Tom: That extension is important because most real-world problems involve complex, non-Gaussian kernels. If this holds for other radial kernels, that's a big deal for broader applicability <ref:2610.14751#pg3>.

Jane: And they also showed that for standard kernels like the exponential and Matérn kernels, you only need to sample just two independent scalar Gamma random variables to get an expected sampling time of O(one) for each of those three specific cases <ref:2610.14751#pg3>.

Lu: That specific detail about the sampling efficiency is interesting because it shows they've optimized the construction for certain common kernels, making them very efficient to build in practice <ref:2610.14751#pg3>.

Conclusion: Tom: So wrapping up "Random Fourier Features in Near-Linear Time," the main thing is that we have a randomized feature map that computes in near-linear time, O((d plus m) log d), and gives strong concentration guarantees for the Gaussian kernel and other radial kernels <ref:2610.14751#pg3>.

Jane: The implication for us is that we can now build more powerful kernel methods without the training time becoming prohibitively long due to these feature maps. It makes using these approximations much more practical right now.

Lu: Yeah, the existence proof for this map is what opens up a new way to represent data in high dimensions efficiently <ref:2610.14751#pg2>. It suggests that representation learning can be done much faster than we thought <ref:2610.14751#pg3>.

Meng: From an engineering standpoint, it means we can build systems that handle higher dimensional inputs more efficiently without having to wait days for a feature map to compute. That’s a tangible win for deployment speed <ref:2610.14751#pg2>.

Lalam: The paper moves us toward practical applications like Kernel Density Estimation, showing how these features can lead to query times of O((d plus one over epsilon squared)) for an additive approximation guarantee <ref:2610.14751#pg3>.

Tom: Yeah, so the overall message is that we've found a way to get high-quality kernel approximations in time that scales much better than before, even though there are still lower bounds on the output dimension m <ref:2610.14751#pg3>.

Jane: That’s right. It sets a new benchmark for how fast we can approximate complex similarity functions using random features in machine learning and opens the door for more efficient modeling techniques to explore <ref:2610.14751#pg2>.

Sepideh Mahabadi, Sandeep Silwal, Tal Wagner

Microsoft Research Redmond · University of Wisconsin-Madison · Tel Aviv University

cs.LG, cs.DS

Submitted: 2026-10-10

Updated: 2026-10-10

The gist: The gist: The authors prove that a random feature map for kernels like the Gaussian kernel can be computed in near-linear time, specifically O((d + m) log d), achieving strong concentration

Key concepts

Random Fourier Features (RFF): RFFs approximate complex shift-invariant kernels by sampling independent frequencies from a spectral measure. This creates a randomized feature space of dimension O(m), allowing the kernel inner product to be computed efficiently, which is the core idea for fast kernel methods.
Fastfood Feature Map: This map is a simplified version of an earlier fast feature map construction. The authors analyze its structure, which involves a sequence of two randomized Hadamard transforms (RHTs), using inequalities like the Brascamp-Lieb inequality to control the complexity and ensure good approximation properties.
Radial Kernels: These are kernels whose value depends only on the Euclidean distance between two points, rather than their absolute positions. The results extend to other radial kernels (like exponential or Matérn) by sampling from their specific radial measure, requiring very few random variables for efficient computation.
Concentration Guarantees: These are mathematical proofs that show the randomized feature map's output is highly likely to be close to the true kernel function value. Strong concentration guarantees ensure that the approximation error is bounded with high probability, which is essential for reliable machine learning applications.

Summary

The gist: The authors prove that a random feature map for kernels like the Gaussian kernel can be computed in near-linear time, specifically O((d + m) log d), achieving strong concentration guarantees.

Random Fourier Features and Computational Bottleneck

Random Fourier features (RFF) approximate shift-invariant kernels by sampling independent frequencies from the spectral measure to construct an inner product in a randomized feature space of dimension O(m). A long line of work has focused on faster variants using structured transforms like randomized Hadamard transforms (RHTs), which can be computed in O(d log d) time and mimic properties of truly random rotations. However, previous fast variants have not achieved an RFF variant with nearly linear time O((d + m) log d) and nearly subgaussian concentration.

Near-Linear Time Feature Map Construction

The authors address this gap by proving the existence of a randomized map F that can be computed in time O((d + m) log d) and yields strong concentration for the Gaussian kernel and other kernels. This map is a simplified form of the Fastfood feature map from [LSS13], with the contribution being a new and tighter analysis. The proof relies on analyzing the Fastfood transform, which involves a sequence of two RHTs, where the inner RHT acts as flattening and the outer RHT is controlled using Brascamp-Lieb inequality.

Formal Statement of Results

Theorem 1.1 states that there exists a randomized map F: R d → R 2m, samplable in time O(d + m) and computable in time O((d + m) log d), such that for every x, y ∈ R d: E[F(x) T F(y)] = exp(-x - y 2/2), and for all t > 0 and 0 < η < 1: Pr[F(x) T F(y) − exp(-x - y 2/2) ≥ t] ≤ η + 2 exp(-mt 2/4 log(2d/η)). This result extends to other radial kernels under mild assumptions, with Theorem 1.2 providing a randomized map Fk: R d → R 2m computable in time O((d + m) log d).

Extension to Other Radial Kernels and Sampling Efficiency

Theorem 1.2 extends the result beyond the Gaussian kernel to other radial kernels, requiring only that the kernel k depends only on Euclidean distance. The map Fk is constructed by sampling R m samples from the radial measure νk of k, where R1,..., Rm are iid samples from νk. For standard kernels like the exponential, rational quadratic, and Matérn kernels, sampling from the radial measure requires sampling only two independent scalar Gamma random variables. This results in an expected sampling time T rad k in Theorem 1.2 that is O(1) for each of these three kernels.

Application to Kernel Density Estimation (KDE)

A canonical use case is Kernel Density Estimation (KDE), where the goal is to estimate the density at a query point y given a finite set X. A simple reduction involves computing F(X) = 1/X P x∈X F(x) during preprocessing, followed by reporting F(X) T F(y). The results yield the first KDE solution with query time O((d + 1/ε 2)) for an additive approximation guarantee. Theorem 7.3 further provides a differentially private Gaussian KDE mechanism that satisfies an epsilon-DP requirement, with initialization time O(n(d + m) log(2d)) and query time O((d + m) log(2d)).

Lower Bound on Output Dimension

Theorem 1.3 establishes a lower bound on the output dimension m required for the feature map, stating that m = Ω(log(1/δ)) ε squared log(1/ε). This lower bound is derived from a classical theorem on the rank of perturbed identity matrices and shows that computing F requires at least O(d + m) time. This dimension requirement is crucial for achieving the desired concentration guarantees in the feature map construction.

Computational Bounds and Privacy

Theorem 6.1 provides computational bounds for a KDE data structure using RFF, showing initialization time O(X(d + m) log d), memory size O(d + m), and query time O((d + m) log d). Theorem 7.3 details a differentially private Gaussian KDE mechanism, where the privacy noise error is controlled by choosing appropriate parameters for the Laplace distribution. The final privacy analysis shows that the total error bound for FX(y) − KDEX(y) is bounded by α/2 + η, satisfying the required additive approximation guarantee. This mechanism achieves a query time of O(d+α-2), with only polylogarithmic dependence on 1/η.

References

[AC09] Nir Ailon and Bernard Chazelle, The fast johnson–lindenstrauss transform and approximate nearest neighbors, SIAM Journal on computing 39 (2009), no. 1, 302–322.

[AI09] Alex Andoni and Piotr Indyk, Dimension reduction in kernel spaces from localitysensitive hashing, Journal of Machine Learning Research 17 (2016), no. 120, 1–38.

[Alo09] Noga Alon, Perturbed identity matrices have high rank: Proof and applications, Combinatorics, Probability and Computing 18 (2009), no. 1-2, 3–15.

[AR17] Francesco Alda and Benjamin IP Rubinstein, The bernstein mechanism: Function release under differential privacy, Thirty-First AAAI Conference on Artificial Intelligence, 2017.

[ASYM16] Haim Avron, Vikas Sindhwani, Jiyan Yang, and Michael W Mahoney, Quasi-monte-carlo feature maps for shift-invariant kernels, Journal of Machine Learning Research 17 (2016), no. 120, 1–38.

[Bac17] Francis Bach, On the equivalence between kernel quadrature rules and random feature expansions, Journal of machine learning research 18 (2017), no. 21, 1–38.

[BCELM09] Franck Barthe, Dario Cordero-Erausquin, Michel Ledoux, and Bernard Maurey, Correlation and Brascamp-Lieb inequalities for Markov semigroups, arXiv preprint arXiv:0907.2858 (2009).

[BCELM11], Correlation and Brascamp–Lieb inequalities for Markov semigroups, International Mathematics Research Notices 2011 (2011), no. 10, 2177–2216.

[BCEM06] Franck Barthe, Dario Cordero-Erausquin, and Bernard Maurey, Entropy of spherical marginals and related inequalities, Journal de math´ematiques pures et appliqu´ees 86 (2006), no. 2, 89–99.

[BIW19] Arturs Backurs, Piotr Indyk, and Tal Wagner, Space and time efficient kernel density estimation in high dimensions, Advances in neural information processing systems 32 (2019).

[BL76] Herm Jan Brascamp and Elliott H Lieb, Best constants in young’s inequality, its converse, and its generalization to more than three functions, Advances in Mathematics 20 (1976), no. 2, 151–173.

[BLM+24] Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, and Jakub Tarnawski, Efficiently computing similarities to private datasets, International Conference on Learning Representations (ICLR), 2024.

[BRS11] Yair Bartal, Ben Recht, and Leonard J Schulman, Dimensionality reduction: beyond the johnson-lindenstrauss bound, Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2011.

[CDP15] Wei-Kuo Chen, Nikos Dafnis, and Grigoris Paouris, Improved h¨older and reverse h¨older inequalities for gaussian random vectors, Advances in Mathematics 280 (2015), 643–689.

Improvements for AI systems

Improved Random Fourier Feature (RFF) Computation for Kernels: The system can compute feature maps in near-linear time, achieving a random feature map that can be computed in near-linear time O((d + m) log d) for the Gaussian kernel and other radial kernels, addressing the prior bottleneck of computing Fk(x) generally takes O(md) time.
Faster Kernel Density Estimation (KDE): The system can preprocess a finite set to report an estimate of 1/X P x∈X k(x, y) with a query time of "O(m) plus the time to compute y -> F(y), yielding the first KDE solution with query time Oe(d+ 1/ε2)" for additive error guarantees.
Robust and Private Kernel Density Estimation (DP-KDE): The system can return a function that satisfies an ϵ-DP KDE mechanism for the Gaussian kernel, achieving query time Oe(d+α−2) with required dataset size scaling as n ≥ Ω(√mL/ϵα!) to ensure accuracy within a specified failure probability η.
Efficient Sampling for Specific Kernels: The system can generate feature maps for standard kernels like the exponential, rational quadratic, and Matérn kernels in expected sampling time O(d + m) by using specific samplers based on Gamma random variables, which are assumed to take O(1) expected time.
Optimized Kernel Approximation with Concentration Guarantees: The system can provide an estimator for a radial kernel k satisfying the concentration bound: Pr[Fk(x)TFk(y) − k(x, y) ≥ t] ≤ η + 2 exp − mt232 log(2d/η) + 2 exp − mt28.