Gaussian Processes (GPs) are the gold standard for Bayesian nonparametrics, offering elegant uncertainty quantification and flexible function fitting. However, they suffer from a notorious computational bottleneck: training requires inverting a covariance matrix, an operation that scales cubically ($O(N^3)$) with the number of data points. To make GPs viable for modern datasets, researchers have converged on a shared strategy: summarizing the entire dataset through a small set of "inducing points."
The Intuition of Inducing Variables
The core idea behind sparse Gaussian Processes is that we don't need every single data point to understand the underlying function. If a function is relatively smooth, a few well-placed "landmarks" can capture its global structure. These landmarks are the inducing points (or inducing variables).
Think of inducing points as a communication bottleneck. Instead of every data point talking to every other data point, they all communicate through a small set of $M$ proxies. This reduces the complexity from $O(N^3)$ to $O(NM^2)$, where $M \ll N$. Early foundational work, such as Nonlinear Inverse Reinforcement Learning with Gaussian Processes by Sergey Levine and Vladlen Koltun, demonstrated that these sparse approximations could enable complex tasks like imitation learning where full GPs would be computationally prohibitive.
From Heuristics to Optimization
The effectiveness of a sparse GP depends entirely on where these inducing points are placed. Historically, researchers relied on simple heuristics like random subsampling or k-means clustering. However, as noted in GaussianProcesses.jl: A Nonparametric Bayes Package for the Julia Language by Christopher Nemeth and colleagues, these heuristics often lead to suboptimal performance.
Modern research has shifted toward treating inducing point locations as parameters to be optimized. By maximizing a variational lower bound (ELBO), the model can "move" the inducing points to the most informative regions of the input space. Simone Rossi and Maurizio Filippone took this further in Rethinking Sparse Gaussian Processes, arguing that these locations should be treated as random variables themselves, using Hamiltonian Monte Carlo to capture their uncertainty.
For specific domains like engineering, Heine Havneraas Røstum and Ketil Aas-Jakobsen introduced the Peak Singular Values (PSV) method, which uses structural modes to automatically place points where they are most needed for finite element analysis.
Breaking the Dimensionality Barrier
While $O(NM^2)$ is better than $O(N^3)$, it still struggles when $M$ needs to be large to capture high-frequency details. To address this, researchers have looked toward structured inducing points.
Andrew Gordon Wilson and Hannes Nickisch pioneered Massively Scalable Gaussian Processes (MSGP), which places inducing points on a grid. This allows the use of Kronecker algebra, enabling inference on billions of points. Building on this, Trefor W. Evans and Prasanth B. Nair developed GP-GRIEF, which uses grid-structured eigenfunctions to handle an astronomical number of inducing points—up to $10^{33}$—by exploiting the properties of Khatri-Rao products.
Decoupling for Expressiveness
A significant limitation of standard sparse GPs is the "coupling" of the mean and covariance. To get a more complex mean function, you usually have to add more inducing points, which increases the cost of the covariance calculation.
Xinran Zhu and Jacob R. Gardner proposed a solution in Variational Gaussian Processes with Decoupled Conditionals. By using different sets of inducing points for the mean and the covariance, they allow the model to fit complex data patterns without the cubic growth in complexity that usually accompanies a high inducing point count. This decoupling leads to significantly better uncertainty calibration and performance in downstream tasks like Bayesian Optimization.
Theoretical Reliability
As these approximations become more complex, a natural question arises: can we trust their "error bars"? Luke Travis and Kolyan Ray provided a critical theoretical foundation in Pointwise uncertainty quantification for sparse variational Gaussian process regression. They proved that as long as the number of inducing points is sufficiently large and the prior is chosen correctly, sparse GPs provide reliable, albeit conservative, uncertainty estimates.
This theoretical backing, combined with innovations in optimization and structural scaling, has transformed sparse GPs from a niche approximation into a robust framework for large-scale Bayesian machine learning, applicable to everything from malaria risk mapping to fine-tuning Large Language Models.