Scaling Gaussian Processes Beyond Cubic Complexity

3,917 concepts2,701 papers86 proposals

Gaussian Processes (GPs) are celebrated for their ability to provide non-parametric regression with mathematically rigorous, well-calibrated uncertainty estimates. This makes them the gold standard surrogate model for active learning and Bayesian Optimization (BO). However, GPs possess a notorious Achilles' heel: their computational cost scales cubically ($\mathcal{O}(n^3)$) with the number of observed data points $n$.

To understand why this bottleneck occurs, we must look at how a Gaussian Process makes a prediction. At its core, a GP relies on a kernel matrix $K$, which computes the pairwise correlation between every single training point. If you have $n$ data points, $K$ is an $n \times n$ matrix. To calculate the posterior mean and variance at a new, unseen location, the GP must invert this matrix (or compute its Cholesky decomposition) to determine how much weight to assign to each historical observation.

Inverting an $n \times n$ matrix requires $\mathcal{O}(n^3)$ operations. If you double your dataset, the computation doesn't double—it increases eightfold.

The Downstream Impact of Cubic Scaling

This cubic scaling behavior creates a severe bottleneck in practical applications. In Bayesian Optimization, we evaluate an objective function sequentially, updating our surrogate model at each step to choose the next best point. As highlighted by Stefan Falkner et al. in BOHB: Robust and Efficient Hyperparameter Optimization at Scale, this overhead quickly renders traditional GPs impractical for large-scale optimization tasks where many configurations must be evaluated.

The problem manifests across diverse domains:

To use the power of GPs in the era of big data, we have to break the $\mathcal{O}(n^3)$ barrier. Modern research tackles this through two primary intuitions: global compression (sparse approximations) and local partitioning.

Global Compression via Sparse Approximations

The intuition behind sparse approximations is simple: not every data point provides unique information. If you have multiple data points clustered closely together, their contributions to the kernel matrix are highly redundant.

Instead of allowing all $n$ points to interact globally, sparse methods introduce a much smaller set of $m$ virtual points, known as inducing points (where $m \ll n$). The training data points are mapped only to these inducing points, effectively acting as a low-rank bottleneck that compresses the information. This reduces the computational complexity from $\mathcal{O}(n^3)$ to $\mathcal{O}(nm^2)$, turning a cubic scaling problem into a linear one with respect to the dataset size.

Early foundations for this approach emerged from statistical physics. Lehel Csató et al. in TAP Gibbs Free Energy, Belief Propagation and Sparsity demonstrated how sequential minimization and sparsity-based frameworks could maintain inference accuracy while drastically cutting down required matrix operations.

In modern streaming and online applications, this compression is vital to prevent models from slowing down over time. For instance, Wenlong Chen et al. developed an online sparse variational GP framework in Recurrent Memory for Online Interdomain Gaussian Processes that leverages time-varying basis functions to compress an entire streaming history into a fixed-size memory, avoiding catastrophic forgetting without incurring an exponential computational penalty.

However, compressing a dataset introduces a trade-off. As Natalie Maus et al. observe in Approximation-Aware Bayesian Optimization, sparse approximations impose a finite "representational budget." If this budget is allocated poorly, the model may smooth over sharp, localized peaks in the function space, causing optimization algorithms to miss global optima.

Exploiting Locality

A second intuition leverages the geography of data. Most standard GP kernels (like the Radial Basis Function or Matérn kernels) are stationary and local: the correlation between two points drops off exponentially as the distance between them increases. Points on the opposite side of a high-dimensional space have virtually zero influence on each other's predictions.

If global interactions are negligible at long distances, why force them into a massive global matrix inversion?

Instead of approximating the global matrix, local methods partition the space. Robert F Allison et al. exploit this in Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression by introducing Gaussian Process Nearest Neighbors (GPnn). By decoupling hyperparameter estimation from prediction and restricting the GP's focus entirely to localized nearest neighbors, the authors bypass global matrix calculations entirely. This allows them to deliver precise predictions and robust uncertainty intervals on datasets containing millions of points at a fraction of the traditional computational cost.

The Tension of Richer Data: Derivative Observations

The struggle against cubic complexity becomes even more pronounced when we try to make GPs more data-efficient by feeding them richer observations, such as gradients.

Intuitively, knowing the value of a function at a point gives you one piece of information. Knowing the slope (derivative) at that point tells you the direction of the landscape, effectively giving you the equivalent of multiple data points for the price of one.

However, incorporating derivatives is a double-edged sword. As E. Solak et al. demonstrate in Derivative Observations in Gaussian Process Models of Dynamic Systems, treating derivatives as observations forces the kernel matrix to expand. Instead of an $n \times n$ matrix, you must now construct a matrix that accounts for every data point and its partial derivatives across every input dimension $d$.

As a result, Jian Wu et al. point out in Bayesian Optimization with Gradients that joint modeling causes the computational cost to scale cubically not just with the number of observations, but also with the dimensionality of the input space. This compounding bottleneck makes the integration of sparse or structured kernel approximations an absolute necessity when dealing with derivative-enhanced surrogate models in high-dimensional spaces.

Ultimately, scaling Gaussian Processes is not about replacing their underlying mathematics, but about finding clever ways to avoid the global $n \times n$ interaction. Whether through compressing data into inducing points or isolating computations to local neighborhoods, breaking the cubic bottleneck allows us to deploy the unmatched uncertainty quantification of GPs to massive, real-world problems.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 2997 papers
  2. Version 1 · 2026-10-04 · 2558 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_gaussian_process_scalability_934d2d02,
  title = {Gaussian Process scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/gaussian-process-scalability/rdr_934d2d02c83342abb76ef6ff30e605b0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_gaussian_process_scalability_934d2d02_v2,
  title = {Gaussian Process scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/gaussian-process-scalability/rdr_934d2d02c83342abb76ef6ff30e605b0/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake