PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Fourier features for Gaussian processes

James Hensman, Nicolas Durrande, Arno Solin

arXiv:1611.06740v2stat.ML

TL;DR

Gaussian-process computation remains challenging because standard methods scale poorly with dataset size and may involve high-dimensional, non-Gaussian posteriors. The paper introduces Variational Fourier Features, combining variational sparse approximations with regularly spaced spectral features, and demonstrates good computational speed and predictive power under specific kernel structures.

  • Problem

    Gaussian-process computation is challenging because complexity usually scales cubically with data size while non-Gaussian likelihoods produce high-dimensional, non-Gaussian posteriors.

  • Method

    Variational Fourier Features combine variational sparse approximations with Fourier features on a regular frequency grid to construct a spectrally based approximation.

  • Results

    The method demonstrates good computational speed and predictive power in higher-dimensional problems with additive or separable covariance structures, and competitive performance on airline-delay data.

  • Takeaways & Limitations

    VFF provides a scalable Gaussian-process approximation with competitive predictive performance in tested settings involving additive or separable kernel structure.

Abstract

from arXiv · show

This work brings together two powerful concepts in Gaussian processes: the variational approach to sparse approximation and the spectral representation of Gaussian processes. This gives rise to an approximation that inherits the benefits of the variational approach but with the representational power and computational scalability of spectral representations. The work hinges on a key result that there exist spectral features related to a finite domain of the Gaussian process which exhibit almost-independent covariances. We derive these expressions for Matern kernels in one dimension, and generalize to more dimensions using kernels with specific structures. Under the assumption of additive Gaussian noise, our method requires only a single pass through the dataset, making for very fast and accurate computation. We fit a model to 4 million training points in just a few minutes on a standard laptop. With non-conjugate likelihoods, our MCMC scheme reduces the cost of computation from O(NM2) (for a sparse Gaussian process) to O(NM) per iteration, where N is the number of data and M is the number of features.

1. Introduction

The paper addresses computational and inferential challenges in Gaussian processes by combining variational Bayesian inference with Fourier features. It introduces Variational Fourier Features as a theoretically sound, expressive, fast approximation based on an almost-independent decomposition for Matérn kernels.

  • Motivation and challenges: GP computation is challenging because dense covariance decomposition scales cubically with N, non-conjugate likelihoods produce high-dimensional non-Gaussian posteriors, and covariance parameters create hierarchy.The introduction identifies these as three separate sources of difficulty.
  • Variational inference: Variational Bayesian inference minimizes KL[q||p] and addresses the three challenges through a single unified objective.The framework also supports monotonic accuracy improvements and ELBO-based comparison of approximations.
  • Variational Fourier Features: Variational Fourier Features combine variational inference with Fourier features, representing approximate posteriors through spectral-domain sinusoids rather than inducing inputs.The method combines the representational basis of Fourier features with the variational approach to sparse GP approximation.
  • Validity of spectral features: Naively combining Fourier features with sparse GP methods is invalid because standard stochastic-process Fourier transforms do not converge and yield infinite-variance random variables.Valid variational inducing features require finite, deterministic projections of the process.
  • Contributions: The paper introduces a Fourier GP approximation for Matérn kernels whose decomposition exhibits an almost-independent structure.It combines this approximation with variational Bayesian inference and extends the methodology to general likelihoods.
  • Contributions: The resulting inference scheme aims to be theoretically sound, strongly representative, extremely fast, and effective in practice.These properties summarize the paper’s stated objective.

2. Background

This section introduces Gaussian-process notation and reviews spectral and sparse approximations to motivate the paper’s variational Fourier-feature approach. It contrasts random, optimized, and regular Fourier features with inducing-point methods and variational inference.

  • Gaussian-process foundations: Gaussian processes define distributions over functions through mean and covariance functions, with finite function evaluations following multivariate normal distributions.The section considers zero-mean GPs over the real line and allows generally non-Gaussian likelihoods.
  • Spectral representations: Bochner’s theorem represents continuous positive-definite covariance functions through Fourier transforms of positive measures, linking covariance functions and spectral densities.For stationary kernels, this Fourier duality underlies spectral approximations.
  • Fourier approximations: Random Fourier Features approximate the Wiener–Khintchin integral by Monte Carlo sampling frequencies from a distribution proportional to the spectral density.The resulting finite cosine-and-sine basis yields a parametric Gaussian-process representation.
  • Fourier-feature variants: Optimized spectral locations can overfit and do not converge to the full GP, while integrating out frequencies reduces overfitting but differs from the approach developed here.Regular Fourier features instead use deterministic, regularly spaced frequencies as a quadrature approximation; with regularly gridded inputs, FFT methods reduce computation to O(N log N).
  • Sparse and variational approximations: Sparse Gaussian-process methods use inducing or pseudo-inputs in the same domain as the data, with M < N, and variational inference estimates parameters by optimizing the ELBO.The variational decomposition separates the projected process from its orthogonal complement, whose covariance matches the conditional process covariance.

3. Variational Fourier Features

This section develops variational Fourier features by windowing Fourier-based inducing variables and replacing their L2 inner product with an RKHS inner product. The resulting features are exactly sinusoidal and support efficient covariance computations through structured matrices.

  • Motivation and challenge: Fourier-based inducing variables combine sparse variational Gaussian processes with sinusoidal mean features, but whole-process Fourier transforms have infinite or undefined variance.The Fourier transform yields sinusoidal covariances, yet its covariance matrix is diagonal with undefined diagonal entries, making it invalid as an inducing variable.
  • Windowed Fourier features: Windowing the integral to a finite domain produces finite-variance inducing variables with tractable covariances for Matérn kernels.For Matérn-1/2, the covariance matrix is diagonal plus two rank-one matrices, while covariance features are almost sinusoidal away from boundaries.
  • RKHS features: RKHS inner-product inducing variables make the covariance features exactly sine and cosine functions instead of boundary-distorted L2 features.The approach replaces ui = ⟨f, φi⟩L2 with ui = ⟨f, φi⟩H and uses a truncated Fourier basis including a constant function.
  • Computational structure: The RKHS Gram matrix has exploitable structure, enabling covariance computations in O(NM) rather than O(NM2) using the Woodbury identity.The low-rank-plus-diagonal structure is presented as a source of computational efficiency for the variational Fourier approximation.
  • Boundary behavior: Beyond the finite domain, covariance features return smoothly to zero, with smoothness determined by the kernel order.The outside-domain covariance expressions are obtained in closed form and illustrated in Figure 2.

4. Extending the applicable kernel family

The approach extends beyond one-dimensional Matérn kernels to higher-dimensional inputs through additive and separable product kernels. Additive constructions yield independent feature groups, while product kernels preserve Kronecker structure in the inducing covariance matrix.

  • Additive kernels: For additive kernels, each input dimension uses a Matérn covariance function and is decomposed with Variational Fourier Features.The resulting construction combines independent Gaussian processes over the scalar inputs.
  • Additive kernels: DM features are obtained, with zero covariance between features from different Gaussian processes and one-dimensional covariance structure within each dimension.These independence structures can be exploited for computational scalability during inference.
  • Separable product kernels: Variational Fourier Features can be constructed for separable product kernels when every sub-kernel belongs to the Matérn family.The feature vector is formed as a Kronecker product of one-dimensional features, producing MD elements.
  • Separable product kernels: For product kernels, the inducing-variable covariance matrix Kuu has a Kronecker structure, with each sub-matrix matching the one-dimensional construction.The construction uses a hyper-rectangular boundary and extends the covariance function beyond that boundary analogously to the one-dimensional case.

5. Implementation details and computational complexity

The implementation plugs the derived Fourier-feature covariance expressions into the variational framework and analyzes computational costs across one-dimensional, additive, and separable kernels. Complexity depends on likelihood and covariance structure, with MCMC achieving linear scaling in data size but separable kernels becoming unsuitable for large input dimensions.

  • Implementation: The derived Kuu and ku(x) expressions plug directly into the sparse variational framework.This provides the implementation route for the RKHS Fourier features.
  • One-dimensional kernels: For one-dimensional non-Gaussian models, MCMC evaluation and differentiation cost O(NM) per iteration.The cost is dominated by computing q(f | u) marginals using KfuK−1_uu, with Kuu’s low-rank structure enabling efficient computation.
  • Additive kernels: For additive kernels, Gaussian-likelihood inference costs O(D3M3) per iteration after an initial O(NM2D2) cost.There are 2MD + 1 inducing variables, and non-Gaussian Gaussian-approximation costs O(NM2D2), reducible to O(NM2D) under factorization across dimensions.
  • Additive kernels: For additive-kernel MCMC, the cost is O(NMD), and block-diagonal Kuu structure allows the operations to be distributed across machines.The dominant KfuK−1_uu computation is performed once per input dimension.
  • Separable kernels: For separable kernels, inducing variables grow as (2M)D, making the approximation unsuitable for large D despite its detailed representation and exploitable Kronecker structure.With Gaussian noise, inversion of the MD × MD matrix gives a cost of O(M3D).
  • MCMC implementation: Effective MCMC re-centers u using a square root of Kuu; structured Kuu admits a convenient factor whose extra columns require extra variables in v.For Matérn-3/2 and Matérn-5/2 kernels, two or three extra columns, respectively, are needed.

6. Experiments

Experiments show that VFF often reaches accurate posterior and predictive approximations with fewer or faster-computed features than alternatives, while approximation quality depends on interval selection, feature count, and covariance structure. On a 5.93-million-point airline experiment, VFF completed in 265±6 seconds on a two-core laptop, and structured-covariance limitations were addressed with a sum of two Kronecker matrices.

  • Posterior approximation: VFF approaches the true posterior faster than Random Fourier Features as the number of basis functions increases.With 20 features, variational features are qualitatively better, while 100 random features still cannot replicate the full result for the heavy-tailed spectral density example.
  • Approximation parameters: The ELBO diagnoses interval and frequency choices: boundaries near or inside the data cause edge effects or low-quality approximations, while sufficient frequencies and a suitably distant interval make it close to the marginal likelihood.An interval that is too large produces overly low frequencies and sinusoidal behavior for M = 8 or M = 16, but M = 32 recovers a sensible solution.
  • Sparse GP comparison: In higher-dimensional comparisons, VFF provides comparable compute-time/accuracy tradeoffs to sparse GPs, with faster computation but potentially less representational power.In one dimension, both methods have similar KL accuracy for a given number of inducing variables, while VFF appears faster; at fixed computational time, accuracy is equivalent with different numbers of inducing variables.
  • Airline experiment: 265±6 seconds was sufficient for VFF to process all 5.93 million airline-arrival-delay data on a two-core MacBook Pro laptop.The same run required 626±11 s CPU time; the String GP experiment required 91.0 hours total CPU time, while SVIGP required 5.1±0.1 hours.
  • Covariance structure: Structured covariance can break the variational monotonicity guarantee, with more features worsening the approximation in some cases.A sum of two Kronecker-structured matrices restores a monotonically increasing ELBO with M, although its optimality is not guaranteed.
  • Classification experiment: On the banana classifier, the number of Fourier frequencies required for a good approximation is reasonable, and VFF requires fewer computations per iteration than inducing points.Direct comparison is not straightforward because the total Fourier basis count is twice the listed frequency count, squared under the Kronecker product.

7. Discussion and future directions

The discussion presents VFF as a variational sparse-GP method with spectral representations, extending to structured higher-dimensional kernels while retaining computational scalability. It also identifies low-dimensional limitations and future directions involving faster transforms, broader kernels and densities, and embedded GP models.

  • VFF combines variational sparse-GP approximations with spectral representations, inheriting variational construction alongside spectral representational power and scalability.
  • VFF extends to additive and separable covariance functions in several dimensions, enabling higher-dimensional experiments with good computational speed and predictive power.
  • For airline-delay subsets permitting full-model fitting, additive and isotropic models showed little performance difference, while VFF remained competitive and appeared to approximate the posterior well.
  • Separable kernels model covariate interactions but induce exponentially many inducing frequencies, limiting scalability to low-dimensional problems and producing a dense basis-function projection.
  • Future scaling options include projection methods, sparse spectral points, and NUFFT computations approximable in O(N log N), with initial experiments indicating speed gains and very small accuracy loss.
  • Future work could broaden VFF beyond half-integer Matérn kernels, including frequency-shifted Matérn or spectral mixture kernels, and beyond uniform bounded input densities.
  • VFF may benefit GPLVMs and deep Gaussian processes because sinusoidal Kuf matrices make convolution with Gaussian input approximations simple for uncertainty propagation.

Appendix A. L2 Projection on Fourier Features for Mat´ern-1

Appendix A derives Fourier-feature expressions using the L2 norm, specifically for the Matérn-1 setting.

  • L2 Projection on Fourier Features for Matérn-1: The appendix derives expressions for Fourier features.The derivation uses the L2 norm.
  • L2 Projection on Fourier Features for Matérn-1: The derivation is formulated using the L2 norm.
  • L2 Projection on Fourier Features for Matérn-1: The appendix focuses on the Matérn-1 Fourier-feature case.

A.1 Covariance between inducing variable and GP · A.2 Covariance between inducing variables

The appendix examines covariances among L2 Fourier features, distinguishing sine and cosine basis functions and separating real and imaginary components of the inducing variables. It introduces integrals computed using cos(ωx) = Re(eiωx), including a sine-block case for m, m′ > M.

  • A.2 Covariance between inducing variables: A.2 Covariance between inducing variables: Covariances between two L2 Fourier features depend on whether their basis functions are sines or cosines.The derivation therefore treats the two basis-function cases separately.
  • A.2 Covariance between inducing variables: A.2 Covariance between inducing variables: The analysis considers either the real or imaginary part of the inducing variable u.This distinction follows from the sine-versus-cosine dependence of feature covariances.
  • A.2 Covariance between inducing variables: A.2 Covariance between inducing variables: The appendix identifies integrals of particular interest for computing feature covariances.These integrals support the separate treatment of the two basis-function cases.
  • A.2 Covariance between inducing variables: A.2 Covariance between inducing variables: The relevant integrals can be computed using cos(ωx) = Re(eiωx).The cosine identity connects the real part of the complex exponential representation to the covariance calculations.
  • A.2 Covariance between inducing variables: A.2 Covariance between inducing variables: The supplied derivation begins by setting out the covariance dependence and the integrals needed for the Fourier-feature cases.The provided passages specifically identify the sine block and the sine-versus-cosine distinction.
  • A.2 Covariance between inducing variables: A.2 Covariance between inducing variables: The sine-block case is defined by m, m′ > M.This case is explicitly listed as case 2 in the covariance analysis.

Appendix B. Mat´ern inner products

This appendix establishes notation for Matérn RKHS inner products on [a, b], using identity and differentiation operators to express compact formulas.

  • Matérn RKHS inner-product expressions on [a, b] are adopted from Durrande et al. (2016).
  • The identity operator I maps any function h ∈ H to h, while D maps g to its derivative g′.
  • The shorthand (λI + D)^2(h) expands to λ^2h + 2λh′ + h′′.

B.1 Gram matrix between Fourier features for the exponential kernel

For the exponential kernel, the Fourier-feature Gram matrix uses harmonic cosine and sine features on [a, b]. Its cosine and sine blocks are diagonal, while the off-diagonal block vanishes.

  • The feature basis is φ0 = 1, with cosine and sine functions at harmonic frequencies on [a, b].
  • All non-diagonal cosine-basis terms have zero integral, yielding a block of Kuu equal to diag(αcos) + σ^-2.
  • The Kuu block for the sine basis functions is exactly diagonal.
  • The off-diagonal block satisfies Kφφ[i, j] = 0 when i ≤ 2M + 1 < j.

B.2 Gram matrix associated to Fourier features for the Mat´ern- 3 2 kernel

This section considers the Gram matrix associated with Fourier features for the Matérn-3/2 kernel, including the sine-block case for indices i, j > M.

  • Case 2 covers indices i, j > M.
  • For these indices, the relevant block is the sine block.

B.3 Gram matrix of Fourier features for the Mat´ern- 5 2 kernel

The section derives the Gram matrix entries for Fourier features under the Matérn-5/2 kernel, covering cosine, sine, and off-diagonal blocks. The off-diagonal block is zero, while diagonal entries include boundary terms G(a).

  • Cosine block: The cosine-block diagonal entries for i = j ≠ 0 equal 3(b −a)32λ5σ2 (λ2 + ω2_i )3 + G(a).This expression is given for the corresponding Fourier-feature Gram matrix case.
  • Zero-frequency case: The zero-frequency diagonal entry for i = j = 0 equals 3λ(b −a)16σ2 + G(a).The zero-frequency case is stated separately from the nonzero diagonal entries.
  • Sine block: The sine-block diagonal entries for i = j ≠ 0 equal 3(b −a)32λ5σ2 (λ2 + ω2_i )3 + G(a).The sine-block case uses the same displayed diagonal expression as the corresponding nonzero-frequency case.
  • Off-diagonal block: The off-diagonal block with i ≤M < j has Kφφ[i, j] = 0.This case concerns cross-block entries between the cosine and sine feature groups.
Loading 1611.06740v2…