PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Fourier Features in Near-Linear Time

Sepideh Mahabadi, Sandeep Silwal, Tal Wagner

arXiv:2610.14751v1cs.LGcs.DS

TL;DR

Kernel methods can be costly because they may require manipulating a Gram matrix. The paper gives a tighter analysis of Fastfood random features, yielding a near-linear-time map and a first KDE solution with query time eO(d+1/ε2) for an additive approximation guarantee.

  • Problem

    Kernel methods can be computationally costly because training may require storing or manipulating an n × n Gram matrix.

    Source: §1 · p. 1

  • Method

    The paper gives a tighter analysis of the simplified Fastfood map, whose two Hadamard stages enable a Brascamp-Lieb analysis using well-spread directions.

    Source: §1 · p. 2, §3.2 · p. 7

  • Results

    The first KDE solution has query time eO(d+1/ε2) for an additive approximation guarantee.

    Source: §1 · p. 2

  • Takeaways & Limitations

    This gives an affirmative answer to the main open question posed in about KDE query time.

    Source: §1 · p. 2

    For non-Gaussian extensions, the stated result assumes a continuous, positive-definite, normalized radial kernel.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

The section addresses the gap between fast structured random features and strong concentration with a tighter Fastfood analysis. It also presents a KDE application with near-linear query time.

1 Introduction

  • Independent spectral sampling gives unbiased random Fourier features with subgaussian concentration, but computing them generally takes O(md) time.Kernel methods can also require storing or manipulating an n × n Gram matrix.Source: §1 · p. 1

1.3 Related work

  • Prior fast methods use randomized Hadamard transforms; the cited approaches include for-each and for-all guarantees, while SORF lacks a comparable kernel-estimation tail bound.The related-work discussion also identifies quasi-Monte Carlo, quadrature, Nyström, and hashing-based feature methods.Source: §1 · p. 2, §1.3 · p. 4

1 Introduction

  • The KDE solution achieves query time eO(d + 1/ε^2) for additive approximation, the first such solution reported in the section.The construction preprocesses the average feature vector and answers queries with an inner product.Source: §1 · p. 2

1.1 Formal statement of results

  • Theorem 1.1 gives a randomized feature map samplable in O(d + m) time and computable in O((d + m) log d) time; Theorem 1.2 extends the result to continuous, positive-definite, normalized radial kernels when d is a power of 2.The section also states that the running time is nearly optimal, with the computation time optimal up to logarithmic factors.Source: §1.1 · pp. 2–3
  • Theorem 1.3 establishes a lower bound that makes Theorem 1.1’s computation time optimal up to logarithmic factors.The lower-bound construction uses pairwise kernel values that mimic a Gram matrix of nearly orthogonal vectors.Source: §1.1 · p. 3, §1.2 · p. 4

1.2 Techniques

  • The analysis applies Brascamp-Lieb to dependent outer-transform features, using inner-transform flattening to make their directions sufficiently well-spread; Schoenberg’s representation extends the approach to radial kernels.Earlier analyses incurred excess dependence on the input diameter.Source: §1.2 · p. 4

2 Random Fourier features: technical background

Random Fourier features approximate shift-invariant kernels by mapping inputs to a randomized finite-dimensional space, where inner products estimate kernel values. This preserves unbiasedness and concentration but can be costly to compute or sample.

2 Random Fourier features: technical background

  • Bochner’s theorem identifies a continuous, normalized, shift-invariant positive definite kernel with the Fourier transform of its unique spectral probability measure.For the Gaussian kernel, that measure is the standard multivariate Gaussian distribution.Source: §2 · p. 5
  • RFF samples frequencies from a kernel’s spectral measure and maps inputs to O(m) dimensions so feature inner products estimate kernel values.For each fixed pair, the estimator is unbiased and has subgaussian concentration as m grows.Source: §2 · p. 5
  • Computing the standard random feature map takes O(md) time, which can be costly when d is large.Sampling the map can also take O(m(1 + T_spec)) time, where T_spec is the cost of one spectral-measure sample.Source: §2 · p. 5
  • The alternative phase-shift form of RFF adds independent uniform phases, but this paper omits them to simplify its analysis.The two forms are both used in the literature.Source: §2 · p. 5

3 Fast random features for the Gaussian kernel (Theorem 1.1)

The Gaussian-kernel construction uses a simplified Fastfood map built from Hadamard transforms and random diagonal matrices. Its analysis handles dependent output features with Brascamp-Lieb inequalities, using flattening to make the relevant directions sufficiently spread; the proof extends to m > d by combining smaller maps.

3 Fast random features for the Gaussian kernel (Theorem 1.1)

  • The map is a simplified Fastfood construction using Hadamard transforms and random sign and Gaussian diagonal matrices.The input dimension is assumed to be a power of 2, by padding with zeros; the proof first treats m ≤ d.Source: §3 · pp. 5–6

3.1 Preliminaries

  • Conditioned on B, each entry of Vz is marginally Gaussian, although the different rows are not independent.The proof also uses norm preservation under the orthogonal Hadamard transform with sign flips.Source: §3.1 · p. 6

3.2 Proof of Theorem 1.1

  • Brascamp-Lieb bounds the moment-generating function of dependent features as if there were about c* m independent terms, while Fast JL flattening makes the directions sufficiently well-spread.Conditioned on B, each output feature is a projection of the Gaussian diagonal vector; the inner Hadamard stage flattens the input before the outer stage.Source: §3.2 · p. 7

3.3 The m > d regime

  • For m > d, the construction partitions the features into groups of size at most d and combines independently sampled maps that share B.The proof uses independence of the maps conditional on B to extend the concentration argument.Source: §3.3 · pp. 9–10

4 Fast random features for other radial kernels (Theorem 1.2)

For radial kernels, the paper builds features by sampling radii and applying a spherical version of its concentration analysis. Schoenberg’s representation connects these constructions to the kernel, while explicit radial samplers yield efficient implementations for several standard kernels.

4.2 Proof of Theorem 1.2

  • For the other radial kernels, the construction samples independent radii from the kernel’s radial measure and applies a spherical Brascamp-Lieb inequality to analyze concentration.The proof assumes d ≤ m first and extends to m > d by the same grouping argument used for the Gaussian case.Source: §4 · p. 11, §4.1 · p. 11, §4.2 · p. 12

4.1 Preliminaries

  • Schoenberg’s representation expresses a continuous positive definite normalized radial kernel as a mixture of spherical shell kernels.The radial measure is the distribution of the norm of a spectral-measure sample; for radial kernels, it fully encodes the kernel because the angular component is uniform on the sphere.Source: §4.1 · p. 11, §4 · p. 11

4.2 Proof of Theorem 1.2

  • By Lemmas 4.4 and 4.2, Fk(x)^T Fk(y) averages terms cos(R·Θ^T z), with R sampled from νk and Θ from U(d); each term has mean k(x,y).Sampling Fk takes O(d + m(1 + Tν)) time: B and G take O(d), and R1,...,Rm take O(m(1 + Tν)) to sample.Source: §4 · p. 11, §4.2 · p. 12

4.3 Specific radial kernels beyond gaussian

  • For the exponential, rational quadratic, and Matérn kernels, radial sampling uses two independent scalar Gamma samples and takes expected O(1) time per radius.The resulting maps have expected sampling time O(d + m) and evaluation time O((d + m) log d), while retaining unbiasedness and the theorem’s concentration guarantee.Source: §4.3 · pp. 13–15

5 Lower bound: Proof of Theorem 1.3

The lower-bound argument constructs inputs whose Gaussian-kernel Gram matrix resembles a perturbed identity, then invokes a rank bound to constrain feature dimension. The paper also notes the unavoidable cost of reading inputs and writing outputs.

5 Lower bound: Proof of Theorem 1.3

  • Theorem 1.3 gives a lower bound on feature dimension under its stated assumptions, and any map requires Ω(d + m) time to read its input and write its output.The dimension bound follows from Lemma 5.1; the time bound follows directly from the required input and output coordinates.Source: §5 · p. 15
  • Alon’s rank bound for perturbed identity matrices supplies the rank argument behind the feature-dimension lower bound.The proof applies it after relating the feature Gram matrix to a near-identity matrix.Source: §5 · p. 15
  • The proof constructs points whose Gaussian-kernel Gram matrix has diagonal entries 1 and off-diagonal entries between 0 and ε/2.A union bound yields a feature Gram matrix with diagonal entries 1 and off-diagonal magnitudes at most 3ε/2.Source: §5 · p. 15

6 Kernel density estimation

Section 6 defines KDE approximation and gives a Gaussian KDE data structure with additive error and stated computational bounds. The bounds also extend to other radial kernels.

6 Kernel density estimation

  • The data structure initializes on X and answers queries y with an approximation to KDE, with its additive guarantee measured over internal randomness.The stated operations are initialization and query.Source: §6 · pp. 15–16
  • The Gaussian KDE result gives query time ˜O(d + ε^-2) and answers the main open question posed in.The section distinguishes this pure additive-error setting from multiplicative-error KDE approaches.Source: §6 · p. 16
  • The Gaussian KDE structure has (ε, δ)-additive error, initialization time O(|X|(d + m) log d), memory O(d + m), and query time O((d + m) log d).Here m = O(ε^-2 log(d/εδ) log(d/εδ)).Source: §6 · p. 16
  • The same type of theorem applies to other radial kernels, with corresponding radial-sampling cost during initialization and unchanged query time and memory.Source: §6 · p. 17

7 Differential privacy with KDE function release

Section 7 constructs an ε-DP function-release mechanism for Gaussian KDE using a noisy random-feature representation. It gives bounds for initialization, representation size, and per-query evaluation.

7 Differential privacy with KDE function release

  • The Gaussian function-release mechanism is ε-DP and provides an α-accurate KDE function with failure probability η under the theorem's dataset-size condition.Source: §7 · p. 17
  • The mechanism uses initialization time O(n(d + m) log(2d)), representation size O(d + m), and evaluation time O((d + m) log(2d)) per query.Source: §7 · p. 18
  • The construction adds independent Laplace noise to the feature sum and count, releases the feature map and noisy sum, then evaluates their inner product with the query features.The release is ε-DP by the Laplace mechanism and standard DP composition.Source: §7 · p. 18
  • The accuracy analysis combines non-private KDE approximation error and privacy-noise error using the triangle inequality and a union bound.Source: §7 · pp. 18, 20

AI use statement

The authors report using generative AI in developing the paper's proofs, alongside substantial human input.

AI use statement

  • The authors say all proofs were found through interactions with generative AI, primarily GPT 5.6 Sol, with substantial human input.They report manually writing the manuscript based on those interactions to ensure correctness, readability, and faithfulness to existing literature.Source: AI use statement · p. 20
  • The authors state that they are accountable for the content and correctness and welcome feedback to improve the paper.Source: AI use statement · p. 20

A Brascamp-Lieb inequalities

The appendix relates its Gaussian and spherical Brascamp–Lieb lemmas to prior results and gives a derivation for a relaxed Gaussian condition.

A Brascamp-Lieb inequalities

Related papers

Loading 2610.14751v1…