Brief
An exact GP needs K^-1 y and log|K| for the n x n kernel matrix K. Cholesky gets them in O(n^3) time and O(n^2) memory, which is impossible for hundreds of thousands of points. Reimplement BBMM (Black-Box Matrix-Matrix inference, the method behind GPyTorch) in NumPy. It has three parts: batched preconditioned CG with a pivoted-Cholesky preconditioner (a cheap low-rank approximation of K) for K^-1 y; stochastic Lanczos quadrature (estimate log|K| from a few random probe vectors and short Lanczos runs) for log|K| and its gradient; and tiled kernel matvecs that never materialise K (compute K times a vector block by block, on the fly). Train exact GPs on the UCI datasets used by Wang et al. 2019, up to their 3DRoad dataset, on a single CPU machine.
VICTORY CONDITIONS
- RMSE within 10% of the paper's exact-GP number on 4 datasets including 3DRoad, on one CPU in < 24 h; log-det estimates within 1% of exact Cholesky on subsets <= 20k points (Test RMSE and NLL (negative log-likelihood of the test data, which also scores the uncertainty estimates) vs the exact-GP results in Wang et al. 2019; wall time on CPU; log-det estimate error).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- BBMM
- Black-Box Matrix-Matrix inference: doing all GP computations with batched matrix-vector products and iterative solvers instead of a Cholesky factorisation.
- Pivoted Cholesky preconditioner
- A partial Cholesky factorisation that picks the most important rows first, giving a cheap low-rank approximation of K that speeds up CG.
- Stochastic Lanczos quadrature
- Estimating log|K| (the trace of log K) by averaging over random probe vectors, each handled with a short Lanczos run.
- Matvec
- A matrix-vector product; here computed tile by tile from the kernel formula without ever storing K.
- NLL (negative log-likelihood)
- A test score that rewards accurate predictions and well-sized error bars; lower is better.
Why it rates ★★★★☆
Matching a multi-GPU paper's exact-GP results on a CPU, with your own Krylov machinery, is a striking systems-math result.