Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
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.
Proposes AdaSAP, an approximate, distributed, accelerated sketch-and-project solver for large-scale Gaussian process posterior inference, with a DPP-based condition-number-free convergence analysis along top spectral basis functions.
Problem
Exact Gaussian process inference requires solving an n×n linear system, which is costly and ill-conditioned at large n; existing solvers (PCG, SDD) trade off scalability, robustness to ill-conditioning, and hyperparameter tuning.
Approach
Combines sketch-and-project with approximate Nyström subspace preconditioning, multi-GPU distributed matrix products, Nesterov acceleration, and default hyperparameters, and proves a DPP-based two-phase convergence rate along top spectral basis functions that is condition-number-free in the early phase.
Key results
- AdaSAP achieves the lowest test RMSE on all six benchmark datasets (e.g., 0.027 on houseelec vs 0.066 for AdaSAP-I, 0.119 for SDD-10, 1.278 for PCG).
- On the taxi dataset with n=3.31e8, AdaSAP reaches RMSE 0.50, versus 0.52 for SDD-10 (reached in 45% less time), while PCG runs out of memory.
- On large-scale Bayesian optimization, AdaSAP gives 10.42% and 13.86% improvement over random search at lengthscales 2.0 and 3.0, the best among methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ADASAP instead of the strongest listed external solver | GP inference · benzene and malonaldehyde test sets | RMSE: 0.265 -> 0.012; 0.270 -> 0.015 | Helped |
| use ADASAP instead of the strongest listed external solver | GP inference · yolanda and song test sets | RMSE: 0.795 vs 0.795; 0.752 vs 0.752 | No clear effect |
| use ADASAP instead of SDD-10 | GP inference · acsincome test set | RMSE: 0.792 -> 0.789 | Helped |
| use ADASAP instead of SDD-1 | GP inference · houseelec test set | RMSE: 0.268 -> 0.027 | Helped |
| replace the subspace preconditioner with the identity matrix (ablation) | ADASAP · large-scale regression datasets | RMSE: 0.795 -> 0.808 (yolanda); 0.752 -> 0.782 (song); 0.012 -> 0.168 (benzene); 0.015 -> 0.231 (malonaldehyde); 0.789 -> 0.79 | Hurt |
| replace the subspace preconditioner with the identity matrix (ablation) | ADASAP · Bayesian optimization, lengthscales 2.0 and 3.0 | improvement over random search (%): 10.42 -> 7.04; 13.86 -> 11.27 | Hurt |
| use ADASAP instead of SDD-10 | GP inference · taxi (n = 3.31 · 10^8) | RMSE: 0.52 -> 0.50 | Helped |
| use ADASAP instead of SDD-10 | GP inference · taxi (n = 3.31 · 10^8) | runtime to reach SDD-10's attained RMSE: 45% less time | Helped |
| use ADASAP instead of PCG | Bayesian optimization · lengthscale 2.0 | improvement over random search (%): 0.13 -> 10.42 | Helped |
| use ADASAP instead of PCG | Bayesian optimization · lengthscale 3.0 | improvement over random search (%): 5.54 -> 13.86 | Helped |
| use SDD-10 or SDD-100 | SDD · Bayesian optimization, both tested lengthscales | improvement over random search (%): 0.00 | No clear effect |
| omit tail averaging (ablation) | sketch-and-project · practical performance, larger block sizes | performance | Helped |
Surprising findings
- SDD with stepsize 100 diverges on all datasets, and SDD-10 diverges on malonaldehyde, showing high sensitivity to stepsize.
- Tail averaging was found not to improve practical performance, so experiments run AdaSAP without it.
Limitations
- Theory covers exact sketch-and-project with tail averaging and DPP sampling, not the approximate preconditioning, acceleration, or uniform sampling used in AdaSAP.
- Condition-number-free rate holds only for moderate-accuracy posterior mean estimates; high-accuracy regime is condition-number dependent.
- Experiments are in single precision only; lower precision left to future work.
Experimental setup
Datasets: yolanda song benzene malonaldehyde acsincome houseelec taxi (NYC subset)
Benchmarks: yolanda song benzene malonaldehyde acsincome houseelec taxi synthetic Bayesian optimization tasks
Metrics: test RMSE mean negative log-likelihood percentage improvement over random search
Baselines: SDD PCG AdaSAP-I (identity preconditioner)
Builds on: sketch-and-project stochastic dual descent pathwise conditioning randomized Nystrom preconditioning tail averaging
Closest papers by meaning
- Efficiently sampling functions from Gaussian process posteriors (ICML 2020 · similarity 0.91)
- Scalable Exact Inference in Multi-Output Gaussian Processes (ICML 2020 · similarity 0.89)
- Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference (NeurIPS 2024 · similarity 0.89)
- Bayesian Optimization through Gaussian Cox Process Models for Spatio-temporal Data (ICLR 2024 · similarity 0.88)
- Conditioning Gaussian Processes on Almost Anything (NeurIPS 2026 · similarity 0.88)
- Sparse Gaussian Processes: Structured Approximations and Power-EP Revisited (NeurIPS 2025 · similarity 0.87)
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.