Random Fourier Features in Near-Linear Time

Sepideh Mahabadi; Sandeep Silwal; Tal Wagner

cs.LGOct 10, 2026

Random Fourier Features in Near-Linear Time

Authors: Sepideh Mahabadi, Sandeep Silwal, Tal Wagner

Organizations: Microsoft Research – Redmond · University of Wisconsin-Madison · Tel Aviv University

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.

Figures & tables

Reference	Method	Out dim.	Time for $x\mapsto F(x)$
[ 37 ]	Random Fourier features	$O(1/\varepsilon^{2})$	$O(d/\varepsilon^{2})$
[ 31 ]	Fastfood	$\widetilde{O}(\Delta^{2}/\varepsilon^{2})$	$\widetilde{O}(d+\Delta^{2}/\varepsilon^{2})$
[ 8 ]	Fast dim. reduction + RFF	$\widetilde{O}(1/\varepsilon^{2})$	$\widetilde{O}(d+1/\varepsilon^{4})$
[ 46 ]	Fast spherical emb. + Fastfood	$\widetilde{O}(1/\varepsilon^{3})$	$\widetilde{O}(d+\varepsilon\Delta^{2}+1/\varepsilon^{3})$
This work (Thm 1.1 )	Fastfood (new analysis)	$\widetilde{O}(1/\varepsilon^{2})$	$\widetilde{O}(d+1/\varepsilon^{2})$

Table 1: Random feature maps

F:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}

for the Gaussian kernel. The table lists the output dimension

m=m(\varepsilon,\delta)

needed for the tail bound

\Pr[\left|\exp(-\frac{1}{2}\lVert x-y\rVert_{2}^{2})-F(x)^{T}F(y)\right|\geq\varepsilon]\leq\delta

for every fixed pair

x,y\in\mathbb{R}^{d}

, as well as the time it takes to compute

x\mapsto F(x)

. The dependence on

\delta

is omitted since it is

\log^{O(1)}(1/\delta)

in all the bounds.

\Delta

denotes an upper bound on any

\lVert x-y\rVert_{2}

Random Feature Methods

Random feature methods approximate kernels and neural networks with finite randomized embeddings to reduce computation while retaining useful accuracy.

See all 46 papers

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization
Jun 8, 2026Taha BouhsineFourier Feature Embeddings Kernel Ridge Regression
Azetta AI
Signed random Fourier features for fast density estimation with indefinite kernels
Aug 29, 2026Xie Wang, Nicolas Langrené, Wen ChenKernel Density Estimation Random Feature Methods
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK · Guangdong Provincial/Zhuhai Key Laboratory of Interdisciplinary Research and Application for Data Science, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China.
Random features for Grassmannian kernel approximation with bounded rank-one projections
Aug 4, 2026Rémi Delogne, Laurent JacquesGeometric Representation Learning Random Feature Methods
INMA/ICTEAM, UCLouvain, Belgium

Jun 8, 2026J/K move · Enter open · S save

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

Taha Bouhsine

Azetta AI

Fourier Feature Embeddings Kernel Ridge Regression Randomized Sketching Random Feature Methods Kernel Methods

Open paper AskPDF arXiv

Bernstein--Schur kernels are products of a finite-feature kernel and a completely monotone shift-invariant kernel: nonstationary kernels falling between the shift-invariant and dot-product templates random features exploit, so neither Bochner sampling nor polynomial sketching applies to the full kernel directly. We give one random-feature construction for the whole class that randomizes both factors: it sketches the finite modulation and samples the radial factor's one-dimensional Bernstein--Widder scale before applying Gaussian random Fourier features, giving feature dimension

Dm

, free of the

O(d^2)

size of the exact modulation feature. With the modulation kept exact (the

m\to\infty

limit), we prove unbiasedness, an exact variance, and a matrix-Bernstein operator-norm bound controlled by the top kernel and modulation eigenvalues and an intrinsic dimension rather than the crude

N\max_{ij}

route. Whitening this argument at the ridge makes the effective dimension

d_{\mathrm{eff}}(λ)

the exact intrinsic dimension of the matrix variance, so

O((1+\|P\|_{\mathrm{op}}/λ)\log(d_{\mathrm{eff}}/δ))

radial draws preserve the kernel-ridge solution; tilting the draw by a closed-form whitened leverage improves this to the effective-dimension count

O((1+d_{\mathrm{eff}})\log(d_{\mathrm{eff}}/δ))

. Conditioning on the sketch carries every guarantee to the deployed doubly-randomized estimator up to one additive sketch term, and all hold for the whole class with the modulation Gram in place of the polynomial one. The flagship instance is the biased

yat

-kernel

k_{yat,b}(w,x)=(w^\top x+b)^2/(\|w-x\|^2+\varepsilon)

, whose family span contains the inverse-multiquadric kernel by finite differences in

b

Abstract

Random Feature Methods

Explore similar work

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

Signed random Fourier features for fast density estimation with indefinite kernels

Random features for Grassmannian kernel approximation with bounded rank-one projections