Random Feature Approximations for Non Stationary Kernels

55 concepts47 papers1 proposal

Kernel methods offer a elegant way to model complex, non-linear relationships by implicitly mapping data into infinite-dimensional Hilbert spaces. However, this expressivity comes at a steep price: computing the full kernel matrix $K \in \mathbb{R}^{N \times N}$ scales quadratically in space ($O(N^2)$) and cubically in time ($O(N^3)$) for tasks like Gaussian Process (GP) regression or Kernel Ridge Regression (KRR).

To scale these methods to massive datasets, researchers frequently turn to Random Fourier Features (RFF). As Tianbao Yang et al. explain, RFF constructs a low-dimensional, data-independent randomized feature map $\phi(x) \in \mathbb{R}^m$ such that the inner product $\langle \phi(x), \phi(x') \rangle$ approximates the true kernel evaluation $k(x, x')$. This converts expensive non-linear operations into fast linear ones, dropping the computational burden to $O(Nm^2)$.

Yet, this scalability relies on a massive theoretical compromise. The mathematical engine powering RFF—Bochner’s Theorem—is strictly restricted to shift-invariant (stationary) kernels, where the relationship between two points depends solely on their relative distance ($k(x, x') = k(x - x')$). This constraint creates a fundamental barrier when modeling real-world systems that exhibit localized, evolving, or non-stationary behaviors.

Why Bochner's Theorem Binds Us to Stationarity

To understand why traditional random features fail on non-stationary data, we must look at the mechanics of Bochner's Theorem. The theorem states that a continuous, positive-definite kernel $k(x, x')$ is shift-invariant if and only if it can be represented as the Fourier transform of a positive finite Borel measure (a valid probability density function) $p(\omega)$:

$$k(x - x') = \int_{\mathbb{R}^d} e^{i \omega^T (x - x')} p(\omega) d\omega = \mathbb{E}_{\omega \sim p} \left[ e^{i \omega^T x} (e^{i \omega^T x'})^* \right]$$

Because the integral factorizes neatly into a product of a function of $x$ and a function of $x'$, we can approximate the expectation by drawing $m$ random frequency samples $\omega_1, \dots, \omega_m$ from the spectral density $p(\omega)$. This yields the familiar randomized feature map composed of sines and cosines.

But what happens if the similarity between $x$ and $x'$ changes depending on where they are located in the input space? For example, in spatial mapping or financial time series forecasting, patterns fluctuate, and volatility changes across different regions. As Jean-François Ton et al. and Gregory W. Benton et al. point out, if a kernel cannot be written strictly as a function of the displacement $\Delta = x - x'$, the Fourier transform trick breaks down. The spectral density is no longer invariant across the input space, meaning we can no longer sample from a single, data-independent distribution $p(\omega)$ to build our feature map.

The Cost of the Shift-Invariance Constraint

The dependency on shift-invariance excludes several of the most powerful and widely used kernel families in modern machine learning:

  1. Dot-Product Kernels: Kernels such as the polynomial kernel $k(x, x') = (\langle x, x' \rangle + c)^d$ or the softmax kernels underpinning Transformer attention mechanisms depend on the inner product of vectors rather than their difference. As Jonas Wacker et al. note, standard RFF cannot be applied here, limiting our ability to scale these architectures using traditional spectral tricks.
  2. Deep and Neural Tangent Kernels (NTK): The implicit kernels defined by deep neural networks are highly non-stationary, adapting their features locally to the geometry of the data.
  3. Structured Domains: Kernels designed for non-Euclidean structures like graphs, strings, or discrete manifolds do not possess a straightforward translation-invariant geometry (Deyu Meng et al.).

Furthermore, downstream algorithmic optimizations inherit this limitation. Analytical leverage score approximations (Yifan Chen et al.), pathwise Gaussian process sampling routines (James T. Wilson et al.), and universal feature quantization schemes (Ping Li et al.) are traditionally locked into stationary assumptions, failing when forced onto non-stationary alternatives.

Escaping the Stationarity Trap

To preserve the linear-time efficiency of random features while unlocking non-stationary modeling, recent research focuses on bypassing Bochner's theorem. Three primary strategies have emerged.

1. Non-Stationary Spectral Expansions

Instead of assuming a global, static spectral density, one can allow the spectral distribution to vary as a function of the input space. Jean-François Ton et al. introduce nonstationary Fourier features by pairing spectral approximations with deep learning regularization techniques, allowing the model to learn localized, evolving covariance structures directly from heterogeneous data without increasing the computational complexity.

2. Swapping Fourier Bases for Polynomial Embeddings

For dot-product kernels, the trigonometric basis functions (sines and cosines) can be replaced with orthogonal polynomial expansions. To scale dot-product and softmax kernels, Jonas Wacker et al. utilize complex-valued random features alongside a data-driven optimization framework that intelligently distributes features across different polynomial degrees.

Expanding on this direction, Insu Han introduces Random Gegenbauer Features. By leveraging the orthogonal properties of Gegenbauer polynomials, this framework unifies Gaussian, dot-product, and Neural Tangent Kernels under a single mathematical umbrella. This allows researchers to compute low-rank approximations of deep neural network representations with strict spectral guarantees, bypassing shift-invariance entirely.

Standard RFF (Stationary):
Input Space (x, x') ──> Displacement (x - x') ──> Bochner's Theorem ──> Fourier Basis (Cos/Sin)

Modern Extensions (Non-Stationary):
Input Space (x, x') ──> Inner Product ⟨x, x'⟩ ──> Maclaurin/Gegenbauer ──> Polynomial Basis
Input Space (x, x') ──> Context-Dependent ───> Deep Generative Models ──> Implicit Random Features

3. Implicit and Meta-Learned Random Features

Rather than analytically deriving a feature map from a closed-form kernel function, a more flexible approach is to train a neural network to generate the random features directly from data.

Chun-Liang Li et al. introduce Implicit Kernel Learning (IKL), which uses deep generative models to implicitly sample from an optimal spectral distribution, allowing the network to discover complex, non-parametric kernel representations. To extend this capability to changing environments, John Isak Texas Falk et al. propose Implicit Kernel Meta-Learning (IKML). This framework trains a neural network to generate random features conditioned on specific tasks, allowing the learned similarity measures to dynamically adapt to varying spatial or temporal contexts where stationary assumptions fail.

Key Foundational Work

Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison (2012) — contributed 1 concept elements to this direction.
Random Features for Large-Scale Kernel Machines (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_shift_invariant_kernel_restriction_490076c8,
  title = {shift-invariant kernel restriction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shift-invariant-kernel-restriction/rdr_490076c8c8644916b6f144e30252a5f8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_shift_invariant_kernel_restriction_490076c8_v1,
  title = {shift-invariant kernel restriction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shift-invariant-kernel-restriction/rdr_490076c8c8644916b6f144e30252a5f8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake