acceptodds
Under review as a conference paper at ICLR 2027

Random Fourier Features in Near-Linear Time

Abstract

Random Fourier features approximate a shift-invariant kernel in , such as the Gaussian kernel , using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating such features requires 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 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.

Primary area:
learning theory
Keywords:
random features, random fourier features, schoenberg, kernel, kde, kernel density estimation, brascamp lieb, fast JL, fastfood, hadamard

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_rhSBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper provides a sharper concentration analysis of Fastfood for approximating Gaussian and other radial kernels. For the Gaussian kernel, it establishes an unbiased feature map with evaluation time O((d+m)log⁡d)O((d+m)\log d) and additive error ε\varepsilon with failure probability δ\delta using m=O(ε−2log⁡(1/δ)log⁡(d/δ))m=O(\varepsilon^{-2}\log(1/\delta)\log(d/\delta)) frequencies. The bound removes the dependence on input distance present in earlier analyses and nearly matches the concentration of independent random Fourier features.

The main technical contribution combines randomized Hadamard flattening with a Brascamp–Lieb inequality to control dependencies between features. A spherical version of this argument, together with Schoenberg's representation, extends the result to continuous positive-definite normalized radial kernels. The paper also gives a lower bound establishing optimality up to logarithmic factors and an application to additive-error kernel density estimation. Validation is entirely theoretical; no new experiments are presented.

Critical strengths
  1. A substantial improvement in the computational guarantees for an established method. The analysis combines near-linear feature evaluation with nearly subgaussian concentration, without dependence on the distance between the input points. This resolves a significant limitation of previous Fastfood guarantees and shows that its computational advantage can be obtained with only a logarithmic overhead in feature count relative to independent RFF. The accompanying lower bound and kernel-density-estimation application make the significance of this improvement concrete.

  2. An effective proof technique with applicability beyond the Gaussian kernel. The Brascamp–Lieb argument controls dependent features through the geometry of their projection directions, avoiding the distance-dependent losses of earlier approaches. Its extension through spherical concentration and Schoenberg's representation gives the contribution broader scope, including exponential, rational-quadratic, and Matérn kernels. This is a meaningful methodological advance rather than merely a refinement of constants.

Critical weaknesses

The guarantees establish pointwise kernel approximation, while their implications for learning remain indirect. The main concentration result concerns each fixed input pair, and the principal application concerns additive-error estimation at a fixed query. The paper does not establish spectral approximation of a dataset's kernel matrix or downstream statistical guarantees that preserve the computational improvement. This limits the demonstrated reach of the result for learning applications, although it does not diminish the validity of the stated kernel-approximation contribution.

Mathematical Consistency and Rigor:

The main proofs appear sound on inspection. The issues identified below concern local inaccuracies and clarification of the computational model, rather than a demonstrated failure of the principal theorems.

1. Definition 4.1 omits assumptions needed to define the radial measure as a probability distribution.

On page 7, Definition 4.1 assumes that the kernel is shift-invariant and positive definite, but does not explicitly require normalization or continuity. It then treats the spectral measure μk\mu_k as a probability measure and defines the radial measure as the distribution of ∥ω∥2\|\omega\|_2 for ω∼μk\omega\sim\mu_k.

For a continuous positive-definite shift-invariant kernel, the spectral measure has total mass k(0)k(0). It is therefore a probability measure only when k(0)=1k(0)=1. The range restriction k∈[−1,1]k\in[-1,1] does not imply this normalization; for example, the constant kernel k≡1/2k\equiv 1/2 satisfies that restriction.

2. The independence statement in the RFF background is incorrect as written.

On page 4, lines 201–204, the paper justifies Hoeffding concentration by saying that the coordinates of FF are i.i.d. This is false for the sine–cosine construction: sin⁡(ωi⊤x)\sin(\omega_i^\top x) and cos⁡(ωi⊤x)\cos(\omega_i^\top x) share the same frequency and are dependent. The sine and cosine coordinates also generally have different distributions.

The correct argument is that

F(x)⊤F(y)=m−1∑i=1mcos⁡(ωi⊤(x−y)),F(x)^\top F(y)=m^{-1}\sum_{i=1}^m \cos(\omega_i^\top(x-y)),

and these mm summands are independent, identically distributed, and bounded in [−1,1][-1,1].

3. The stated evaluation complexity needs a convention for d=1d=1.

Theorems 1.1 and 1.2 allow d=1d=1 but state evaluation time O((d+m)log⁡d)O((d+m)\log d). Literally, this expression vanishes when d=1d=1, although producing the features still requires computation.

Questions for authors
  1. Clarification of the optimality claim: The upper and lower bounds leave logarithmic gaps in their dependence on dimension, accuracy, and failure probability. Could you explicitly distinguish which dependencies are established as necessary from those introduced by the flattening and concentration arguments? In particular, is there evidence that the additional log⁡(d/δ)\log(d/\delta) factor is intrinsic to this Fastfood construction?

  2. Clarification of the computational lower bound: The proof of Theorem 1.3 combines an output-dimension lower bound with the assertion that evaluating the map requires reading all dd input coordinates. Could you specify the computational model and justify the Ω(d)\Omega(d) term for randomized evaluation procedures, including whether the claimed bound concerns worst-case or expected running time?

2 comments

Thank you for your helpful and thorough review.

The guarantees establish pointwise kernel approximation, while their implications for learning remain indirect [...] although it does not diminish the validity of the stated kernel-approximation contribution.

Our response to TSbv shows that our results also yield uniform approximation guarantees, which are more relevant for learning settings where queries are adaptive. Spectral approximation remains an intriguing extension to future work. Our response to Hhha demonstrates that our techniques are quite general and robust and may be more broadly applicable. We believe they could be applicable to spectral kernel matrix approximation, although this remains to be explored in future work.

Mathematical Consistency and Rigor

Thank you for the careful reading and comments. We hope it is evident that these are not substantive errors but rather the result of common colloquial writing and do not bear on the mathematical correctness of our paper. Nonetheless, we will revise the text accordingly. Specifically:

Definition 4.1 assumes that the kernel is shift-invariant and positive definite, but does not explicitly require normalization or continuity.

We required continuity and normalization in the definition of the spectral measure (line 186), and since Definition 4.1 assumes the existence of a spectral measure, we deemed them implied. However, we agree this may be confusing, and we will add them explicitly to Definition 4.1.

On page 4, lines 201–204, the paper justifies Hoeffding concentration by saying that the coordinates of are i.i.d.

Correct, we meant that we sample summands where each summand represents a pair of sine-cosine coordinates with the same frequency, rather than single coordinates, as you point out.

Theorems 1.1 and 1.2 allow d=1 but state evaluation time O((d+m)log d). Literally, this expression vanishes when d=1

Correct: the statements are trivial for d=1d=1, and therefore we implicitly assumed d>1d>1 in the theorems; we will write this explicitly.

Clarification of the optimality claim: The upper and lower bounds leave logarithmic gaps in their dependence on dimension, accuracy, and failure probability. Could you explicitly distinguish which dependencies are established as necessary from those introduced by the flattening and concentration arguments? In particular, is there evidence that the additional log(d/eta) factor is intrinsic to this Fastfood construction?”

Correct, we only claim that the lower bound is nearly optimal (line 122) up to log factors (line 131). Specifically, our lower bound shows that the term O(ε−2log⁡(1/δ))O(\varepsilon^{-2}\log(1/\delta)) is necessary in the regime δ≤ε4\delta\leq\varepsilon^4. We have no evidence that the additional log(d/eta) factor is intrinsic to Fastfood. Tightening the log factors between the upper and lower bounds, and perhaps gauging the precise asymptotic bound, is an interesting topic for future work.

Clarification of the computational lower bound: The proof of Theorem 1.3 combines an output-dimension lower bound with the assertion that evaluating the map requires reading all d input coordinates. Could you specify the computational model and justify the Omega(d) term for randomized evaluation procedures, including whether the claimed bound concerns worst-case or expected running time?

Theorem 1.3 gives a lower bound on the expected time to evaluate the map on worst-case inputs, in the standard unit-cost RAM model with dense input and explicit output. The expectation is over the random choice of the map and any randomness used during evaluation. The input x∈Rdx\in\mathbb R^d is assumed to be given as a dense array, the evaluator may read coordinates adaptively, and it returns F(x)∈RmF(x)\in\mathbb R^m written explicitly. Each coordinate read or written costs one unit.

Thank you for the detailed responses and clarifications. These address my concerns, and I appreciate the proposed revisions. I maintain my original score of 3 (Weak acceptance).

Reviewer_HhhaOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a new, tighter mathematical analysis of the well-known method by Le, Sarlos and Smola, proposing structured random projections used to construct computationally efficient random feature mechanisms for radial kernels (e.g. Gaussian kernels). Those structured mechanisms replace original O(md) time complexity of constructing random features (where m is the number of random projections and d is the dimensionality of the feature vectors under consideration) to O((d+m)logd) and thus are particularly relevant for computations in high-dimensional spaces.

Critical strengths

The paper provides solid, new theoretical analysis that leads to new, tighter bounds (see: Theorem 1.1) with error terms decaying exponentially with the number of random projections used. The proofs look correct and apply a variety of techniques. Lemma 3.6 is particularly useful and important on its own, also in the context of the orthogonal projections that are not induced by the Hadamard mechanism considered in this paper, but other methods (see: my comments later).

Critical weaknesses

The considered mechanism is already known in the field for 13 years and is not the most efficient method in practice. The Authors do not propose a new mechanism, yet its much more thorough theoretical analysis. Empirically, methods constructing random features and based on the products of O(d \log d) Givens rotations (also characterized by small computational footprint) are usually more accurate. The Reviewer suspects that the techniques presented in this paper (in particular Lemma 3.6) can be used to provide deeper theoretical insight also to other constructions based on the orthogonal directions (e.g. the aforementioned Givens-based approaches), but since the theoretical analysis is limited only to the Fastfood method, this remains only an educated guess. It also should be emphasized that the approximation mechanism that is the focus of this paper is inherently biased (Gaussian matrices are replaced with their structured combinatorial-like proxies and activations given by the the trigonometric functions). It is also clear from the theoretical results (the eta parameter in the theorems). In fact the only setting, where the Hadamard-based approach provides unbiasedness is the dot-product kernel estimation, but that is not the subject of this paper. The Reviewer thinks that the presented analysis would be much more relevant for the unbiased structured mechanisms approximating Gaussian kernels, based on the orthogonal projections (e.g. leveraging Gram-Schmidt orthogonalization of the unstructured Gaussian matrices) and simplex projections. It would be particularly interesting to show that such constructions provide strictly better concentration results that the approaches based on the idd sampling (several relevant results are already known, but mostly focusing on variance rather than higher order moments). Finally, it would be great if the Authors can extend the analysis to the PNG kernels, where orthogonality seems to also provide solid empirical gains (as it is the case for the angular and dot-product kernels).

As of now, the presented analysis is tailored to the setting that is too constrained. For that reason, the impact of the presented results on the field is very limited.

Questions for authors

The Reviewer would like to ask the Authors to address the points mentioned in the Critical Weaknesses section.

3 comments

Thank you for your helpful and thorough review.

the approximation mechanism that is the focus of this paper is inherently biased (Gaussian matrices are replaced with their structured combinatorial-like proxies)

To be precise, the Fastfood estimator is unbiased – this was proven in the Fastfood paper (Lemma 7 in their arxiv version). To briefly recap the argument: Given a pair x,yx,y, let z=x−yz=x-y and u=HBzu=HBz where HBHB is the inner RHT. Fix any realization of BB and let V=dHGHBV=\sqrt{d}HGHB (from our line 222), where HGHG is the outer RHT and GG has diagonal Gaussian entries g1,…,gdg_1,\ldots,g_d.

Then, (Vz)i=(Vz)_i=

d∑j=1dHijujgj∼N(0,∑j=1duj2)=N(0,∥∣z∥∣2)\sqrt{d} \sum_{j=1}^d H_{ij} u_jg_j \sim N(0,\sum_{j=1}^d u_j^2) = N(0,\lVert| z \rVert|^2) (this is cited as our Lemma 3.3).

Thus,

EG[cos((Vz)i)]=e−∥z∥2/2E_G[cos((Vz)_i)]=e^{-\lVert z \rVert^2/2}

(by the fact we cite as Lemma 3.4). Our Lemma 3.7 (which is a standard trigonometric derivation) states that the Fastfood estimator F(x)TF(y)F(x)^TF(y) is equal 1m∑i=1mcos((Vz)i)\frac{1}{m}\sum_{i=1}^m cos((Vz)_i), and therefore it is an unbiased estimator for e−∥x−y∥2/2e^{-\lVert x-y \rVert^2/2}.

The distinction from purely combinatorial sign-diagonal constructions is indeed important: the unbiasedness argument stands on the fact that the diagonal matrix of the outer randomized Hadamard transform in Fastfood has Gaussian diagonal entries. Methods that use only sign diagonal matrices in their RHTs, like the SORF estimator (Yu et al., NeurIPS 2016), do not yield unbiased estimators (as discussed in the SORF paper).

The η\eta parameter in our theorems does not impact the unbiasedness of the estimator, but only the tail bounds.

The Reviewer suspects that the techniques presented in this paper (in particular Lemma 3.6) can be used to provide deeper theoretical insight also to other constructions based on the orthogonal directions (e.g. the aforementioned Givens-based approaches)

We agree: our Fastfood analysis was a natural starting point, being the classical fast-RFF candidate in the literature, but our techniques appear more generally applicable. We demonstrate this in the concatenated follow-up comment.

AuthorsOpenReview ↗

(Continued response)

The Reviewer thinks that the presented analysis would be much more relevant for the unbiased structured mechanisms approximating Gaussian kernels, based on the orthogonal projections [...] and simplex projections.

Our approach is directly applicable to these: take mm fixed unit directions aia_i, apply a random rotation, and sample their lengths independently from the kernel’s radial measure. Writing Λ=∥∑iaiaiT∥op\Lambda=\lVert \sum_i a_i a_i^T\rVert_{\mathrm{op}}, the spherical Brascamp–Lieb argument of Lemma 4.3 gives the fixed-pair bound Pr[∣k^(x,y)−k(x,y)∣≥t]≤2exp⁡(−mt24Λ)Pr[|\widehat k(x,y)-k(x,y)|\ge t] \leq 2\exp(-\frac{mt^2}{4\Lambda}). One can check that for orthonormal directions we have Λ=1\Lambda=1, and for the mm vertices of a regular simplex, Λ=m/(m−1)\Lambda=m/(m-1). Thus both geometries give exponential concentration of the same order as independent sampling, across the radial kernel class of Theorem 1.2. Furthermore, we agree that identifying when a particular geometry gives strictly better tails is an interesting further question, especially in light of the mean-square improvements observed for these constructions.

it would be great if the Authors can extend the analysis to the PNG kernels, where orthogonality seems to also provide solid empirical gains (as it is the case for the angular and dot-product kernels).

A partial result can be easily derived by a small extension of our analysis, namely for PNGs with bounded activations: for Kf(x,y)=Eg[f(gTx)f(gTy)]K_f(x,y)=\mathbb E_g[f(g^T x)f(g^T y)], each feature product depends on at most two Gaussian projections, corresponding to spanx,yspan\\{x,y\\}. By the same flattening argument our analysis uses, one can show that the hypothesis of the block Gaussian Brascamp–Lieb inequality holds. Then, the same Hoeffding argument we use gives the fixed-pair tail rate of Theorem 1.1 up to constants for ∣f∣≤1|f|\leq1, with the same fast transform. This includes the sign activation underlying the angular kernel.

Givens rotations (also characterized by small computational footprint) are usually more accurate

Our analysis can also be extended to Givens rotations: by Pillai-Smith (2017), a random rotation on a fixed vector can be simulated up to total variation η\eta with O(dlog⁡dlog⁡(1/η))O(d \log d \log(1/\eta)) Givens rotations. Hence the spherical Brascamp-Lieb analysis we give in the paper goes through for Givens rotations with an additional additive loss of η\eta in the final tail bound.

Reference: Natesh Pillai and Aaron Smith, “Kac’s Walk on nn-Sphere Mixes in nlog⁡nn\log n Steps”, Annals of Applied Probability, 2017.

As of now, the presented analysis is tailored to the setting that is too constrained. For that reason, the impact of the presented results on the field is very limited.

We hope our answers above demonstrate that our analysis isn’t particularly tailored to Fastfood, but rather has the potential to be more broadly applicable and impactful for various random feature variants and settings. The reviewer has raised a host of intriguing directions for future work. We believe Fastfood was a natural starting point for analysis, and that the techniques we developed through analyzing it would be useful in pursuing these proposed highly relevant directions.

Dear reviewer,

As the discussion phase is coming to a close, we wanted to check in once again in case there are remaining questions about our paper that we would address.

Thanks,

The authors

Reviewer_TSbvOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work provides a tighter analysis of a simplified Fastfood feature map. For the Gaussian kernel, it proves an unbiased fixed-pair approximation with a near-subgaussian tail bound and O((d+m)log⁡d)O((d+m)\log d) evaluation time, removing the input-distance dependence of earlier bounds discussed in the paper. The argument combines randomized Hadamard flattening with a Gaussian Brascamp–Lieb inequality. A spherical version extends the result to continuous positive-definite normalized radial kernels in power-of-two dimensions. Its contribution is theoretical; it does not introduce a new Gaussian feature algorithm or report experiments.

Critical strengths
  1. The paper provides improvements to the theoretical guarantees for an established method. The proof bounds the conditional moment-generating function through sub-isotropy and bounded cosine features, avoiding a factor proportional to ∥x−y∥\|x-y\|. The result is useful even though the underlying Gaussian feature construction is existing work.
  2. The paper also provides a spherical argument that covers radial kernels beyond Gaussian, with explicit radial samplers for standard examples. The lower bound supports near-optimality up to logarithmic factors in its stated regime.
Critical weaknesses
  1. The concentration result concerns fixed input pairs. It does not directly establish uniform approximation over a domain or provide guarantees for inputs selected after observing the feature map. This limits direct transfer to adaptive uses.
  2. The near-linear evaluation advantage comes with logarithmic losses in the sufficient feature count. Without a finite-parameter comparison, the practical gain over i.i.d. features is less clear than the asymptotic gain. This is a limitation of practical interpretation.
  3. This work is presented cleanly with extensions to existing work. However, the contribution leans incremental.
Questions for authors
  1. See weaknesses. 2.What do the stated bounds imply about the (d,ε,δ)(d,\varepsilon,\delta) regime where total evaluation cost improves over i.i.d. features, including the larger sufficient feature count? Clarification on this would help.
3 comments

Thank you for your helpful and thorough review.

The concentration result concerns fixed input pairs. It does not directly establish uniform approximation over a domain or provide guarantees for inputs selected after observing the feature map. This limits direct transfer to adaptive uses.

It is correct that our result, like both the original Rahimi-Recht paper and the Fastfood paper, is pointwise: the kernel value is approximated for each fixed pair x,y with high probability. Nevertheless, we can immediately leverage it into a uniform bound over a bounded domain, which facilitates adaptive query settings. Cherapanamjeri and Nelson (NeurIPS 2020) gave a generic technique for turning a pointwise guarantee into a uniform guarantee (their Theorem 1.3). Applying it to our Theorem 1.1 or 1.2, we get uniform kernel approximation over any bounded domain with query time O~(d+1/ε2)\tilde O(d+1/\varepsilon^2), similar to the pointwise query time in our theorems. The pre-preprocessing time and space usage are both O~(n(d2+d/ε2)log⁡Δ)\tilde O(n(d^2+d/\varepsilon^2)\log\Delta), where Δ\Delta is the diameter of the bounded domain. We can add this to the revised version.

Another possible approach to a uniform guarantee, which could potentially improve the above pre-processing time and space usage, is combining our techniques with those of Cherapanamjeri-Nelson (STOC 2022). This seems promising though much more technically involved, and it is an intriguing direction for future work.

References:

Yeshwanth Cherapanamjeri and Jelani Nelson, “On Adaptive Distance Estimation”, NeurIPS 2020.

Yeshwanth Cherapanamjeri and Jelani Nelson, “Uniform approximations for randomized hadamard transforms with applications”, STOC 2022.

The near-linear evaluation advantage comes with logarithmic losses in the sufficient feature count. Without a finite-parameter comparison, the practical gain over i.i.d. features is less clear than the asymptotic gain.

The logarithmic loss in the number of features compared to iid RFF can be easily removed by subsampling the output features as a post-processing step. Thank you for pointing this out – this is a useful addition to the paper, and we will include it.

To see this, recall that Theorem 1.1 outputs mm sin-cos pairs as features. We can subsample s=O(ε−2log⁡(1/δ))s=O(\varepsilon^{-2}\log(1/\delta)) of those pairs, the same number as iid RFF. For each pair x,yx,y, the contribution of one sin-cos pair of features to the kernel estimator F(x)TF(y)F(x)^TF(y) is bounded in [−1m,1m][-\frac{1}{m},\frac{1}{m}]. Therefore, by the standard Hoeffding inequality, subsampling ss pairs preserves the kernel estimator up to ±ε\pm \varepsilon with probability 1−δ1-\delta. This yields the same statement as our Theorem 1.1 with O(ε−2log⁡(1/δ))O(\varepsilon^{-2}\log(1/\delta)) output features and otherwise only a change of constants.

This work is presented cleanly with extensions to existing work. However, the contribution leans incremental.

We view our contribution as significant rather than incremental: RFF has been a cornerstone in ML for two decades. Achieving them in near-linear time has been conjectured in Fastfood in 2013 and has remained open since, motivating a long line of work (lines 46-47 and Table 1). We thus settle a long-standing problem that has attracted considerable attention and efforts. Furthermore, as our answer to Hhha demonstrates, our techniques seem broadly applicable to a host of related problems.

Dear reviewer,

As the discussion phase is coming to a close, we wanted to check in once again in case there are remaining questions about our paper that we would address.

Thanks,

The authors

Apologies for the delayed response. In the meantime, I have taken the opportunity to review the relevant literature more thoroughly. I appreciate the authors' efforts in addressing my concerns during the rebuttal. Their responses have satisfactorily addressed my questions and clarified the issues raised in my initial review. Therefore, I have decided to increase my score from 2 to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.