Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies numerical stability of inducing-point GP approximations, links minimum separation of inducing points to bounded condition numbers, proposes a breadth-first cover tree algorithm for selecting separated inducing points and a clustered-data inducing point approximation with diagonal noise.
Problem
Inducing-point Gaussian process approximations can be numerically unstable (ill-conditioned kernel matrices and failing Cholesky factorizations) when inducing points are closely spaced, especially for geospatial and other low-dimensional data.
Approach
Show via interpolation-theory eigenvalue bounds that a minimum separation condition on inducing points bounds condition numbers independently of data size; adapt the cover tree into a breadth-first, globally separated construction that selects inducing points at a given spatial resolution; and propose a clustered-data approximation whose diagonal noise matrix Lambda further stabilizes the linear s
Key results
- Cover tree inducing points give near-identical condition numbers and RMSE to other stable methods at a given inducing point count on the East Africa geospatial data, while running in O(N log N).
- Standard SVGP with Cholesky fails at the finest spatial resolution (M=6851 inducing points) without increased jitter, whereas the clustered-data approximation with conjugate gradients runs reliably at all resolutions with slightly worse RMSE.
- K-means yields the worst performance and stability among methods except possibly uniform subsampling, and KL-optimized inducing points can be as unstable as K-means.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Select inducing points with a cover tree to promote minimum separation | Sparse variational GP · East Africa | condition number | Helped |
| Select inducing points with a cover tree to promote minimum separation | Sparse variational GP · East Africa | predictive performance | No clear effect |
| Use partial pivoted Cholesky for inducing point selection | Sparse variational GP · Combined Cycle Power Plant | condition number | Helped |
| Optimize inducing point locations directly | Sparse variational GP · East Africa and Combined Cycle Power Plant | predictive performance | Helped |
| Optimize inducing point locations directly | Sparse variational GP · East Africa and Combined Cycle Power Plant | condition number | Hurt |
| Use ordinary K-means for inducing point selection | Sparse variational GP · East Africa and Combined Cycle Power Plant | predictive performance | Hurt |
| Use K-means++ instead of ordinary K-means | Sparse variational GP · East Africa and Combined Cycle Power Plant | condition number | Helped |
| Use the clustered-data approximation with its diagonal noise matrix | Sparse GP regression · East Africa land surface temperature | Cholesky factorization reliability | Helped |
| Use the clustered-data approximation instead of the sparse variational approximation | Sparse GP regression · East Africa land surface temperature | RMSE | Hurt |
| Increase spatial resolution coarseness (ablation) | Cover tree inducing points · Synthetic squared-exponential GP data | Wasserstein distance | Hurt |
| Increase spatial resolution coarseness (ablation) | Cover tree inducing points · Synthetic squared-exponential GP data | condition number | Helped |
| Increase the number of inducing points at fixed data size (ablation) | Inducing point methods · East Africa | RMSE | Helped |
Surprising findings
- K-means, despite its clustering nature, produces poorly separated inducing points and the worst numerical stability, while K-means++ does better.
- Optimizing inducing point locations to minimize KL achieves the best predictive performance but can be as numerically unstable as K-means or uniform subsampling.
Limitations
- Stability guarantees for the cover tree are proven for stationary, continuous kernels with spatial decay; non-stationary kernels only conjectured.
- Cover tree approach is best suited to low-dimensional or low intrinsic-dimension data; in higher dimensions performance gains over uniform subsampling are not clear.
- Clustered-data approximation trades a small amount of predictive performance for stability.
Experimental setup
Datasets: East Africa geospatial dataset East Africa land surface temperature dataset Combined Cycle Power Plant (UCI) synthetic uniform hypercube data
Benchmarks: East Africa geospatial dataset Combined Cycle Power Plant
Metrics: condition number RMSE negative log predictive density evidence lower bound Wasserstein distance conjugate gradient iterations
Baselines: SVGP (Titsias 2009) K-means inducing points K-means++ online inducing point selection (Galy-Fajou 2021) partial pivoted Cholesky (Foster 2009) uniform subsampling KL-optimized inducing points
Builds on: Titsias variational sparse GP Hensman stochastic variational GP Opper-Archambeau sparse approximation cover tree K-means++ partial pivoted Cholesky
Closest papers by meaning
- Sparse Additive Gaussian Process Regression (NeurIPS 2022 · similarity 0.87)
- Sparse Gaussian Processes: Structured Approximations and Power-EP Revisited (NeurIPS 2025 · similarity 0.82)
- Distributed Sparse Regression via Penalization (NeurIPS 2024 · similarity 0.82)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.81)
- Pre-trained Gaussian Processes for Bayesian Optimization (NeurIPS 2024 · similarity 0.81)
- Robust Gaussian Processes via Relevance Pursuit (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.