Gaussian Processes (GPs) are a cornerstone of Bayesian machine learning, prized for their non-parametric flexibility and rigorous uncertainty quantification. However, exact GP inference requires manipulating the full covariance matrix of the dataset, incurring a computational cost that scales cubically ($O(n^3)$) with the number of observations $n$. This computational wall traditionally restricts GPs to small datasets.
To break this bottleneck, sparse Gaussian Process approximations introduce a small set of $m$ auxiliary variables known as inducing points (or pseudo-inputs). Instead of computing interactions across all $n$ data points, the model routes information through these $m$ representative landmarks, slashing the computational complexity to $O(nm^2)$ or $O(m^3)$ (as shown by James Hensman et al. in Scalable Variational Gaussian Process Classification and by James Hensman in Gaussian Processes for Big Data).
The core challenge of this paradigm shifts from matrix computation to a strategic selection problem: How do we choose the number and spatial distribution of inducing points to maximize accuracy while minimizing computational overhead?
The Resolution and Expressivity Trade-Off
The fundamental tension in sparse GPs lies between model fidelity and computational tractability, a balance highlighted by Hao Peng et al. in Asynchronous Distributed Variational Gaussian Process for Regression. Inducing points act as a low-rank summary of the true function space. If the number of inducing points $m$ is too small relative to the complexity of the data, the approximation acts as a low-pass filter, over-smoothing the underlying function and failing to resolve fine-grained local variations (as discussed in Varying-coefficient models for geospatial transfer learning by Matthias Bussas et al. and Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP) by Andrew Gordon Wilson et al.).
To capture rapid local fluctuations or short lengthscales, a high spatial density of inducing variables is required, as noted by So Takao in Actually Sparse Variational Gaussian Processes. However, simply increasing $m$ to achieve global coverage across the input space quickly reintroduces the cubic computational bottleneck, negating the speed advantages of the sparse approximation itself (Trefor W. Evans et al. in Scalable Gaussian Processes with Grid-Structured Eigenfunctions (GP-GRIEF)).
Placement Strategies: Heuristics vs. Optimization
Because model performance is highly sensitive to where these landmarks are placed, researchers have developed several strategies to position inducing points effectively:
- Geometric Heuristics: Early or computationally cheap approaches often rely on clustering algorithms like K-means to partition the input space and place inducing points at the cluster centroids (Hao Peng et al. in Asynchronous Distributed Variational Gaussian Process for Regression; Edwin Simpson et al. in Scalable Bayesian preference learning for crowds). While simple, Hao Peng argues in EigenGP: Gaussian Process Models with Adaptive Eigenfunctions that geometric heuristics do not optimize for predictive performance and can place basis functions in locations that fail to capture the most informative features of the data distribution.
- Continuous Variational Optimization: Rather than keeping locations fixed, modern frameworks treat the coordinates of the inducing points as continuous parameters that are optimized jointly with the kernel hyperparameters by maximizing a variational lower bound (James Hensman et al. in Scalable Variational Gaussian Process Classification).
- Greedy and Probabilistic Subsampling: Alternatively, points can be selected directly from the training set using greedy insertion and deletion criteria based on error metrics (Jens Schreiter in Fast greedy insertion and deletion in sparse Gaussian process regression). The authors of Large scale variable fidelity surrogate modeling demonstrate that prioritizing base points based on their self-covariance can serve as an effective proxy for informativeness, ensuring the most critical features are captured efficiently.
Determining Cardinality and Dynamic Allocation
Even when the spatial locations of inducing points are optimized, determining the total number (cardinality) of these points remains a difficult challenge (Simon Rodriguez Santana et al. in Function-space Inference with Sparse Implicit Processes; JIAN XU et al. in Sparse Variational Student-t Processes). As the dimensionality of the state space increases, it becomes increasingly unclear how the count of these points must scale to maintain predictive accuracy without destroying computational benefits (Zhidi Lin et al. in Efficient Transformed Gaussian Process State-Space Models for Non-Stationary High-Dimensional Dynamical Systems; Weifeng Zhang et al. in GPan-LoRA: Gaussian Process Amortized Networks for Bayesian Low-Rank Adaptation in Large Language Models).
This problem is particularly acute in online or continual learning scenarios, where the complexity of the incoming data stream is unknown in advance. The model faces a delicate trade-off: it must retain enough inducing points to prevent catastrophic forgetting of past data, yet keep the set small enough to remain computationally viable for real-time processing.
To resolve this, Guiomar Pescador-Barrios et al. introduced Vegas Inducing Point Selection (VIPS) in Adjusting Model Size in Continual Gaussian Processes: How Big is Big Enough?. Instead of fixing the number of points upfront, VIPS dynamically monitors the gap between a novel online upper bound and the standard lower bound of the marginal likelihood. By tracking this gap, the framework automatically grows the model's capacity only when necessary, balancing memory representation against computational waste.
Ultimately, the success of sparse Gaussian processes depends on treating inducing points not merely as a static hyperparameter, but as a dynamic, optimized resource that bridges the gap between exact Bayesian inference and big-data scalability.