← All Cracked Math projects
PM-W06NOT STARTEDWOWMATHPYTHONIMPACT ★★★★☆

Exact Gaussian process on hundreds of thousands of points, on a CPU

Never form the kernel matrix K: preconditioned CG plus stochastic Lanczos quadrature make an exact GP fit where Cholesky cannot.

EST.60 h
REWARD+600 XP
AFTERWang et al. 2019 + 1

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
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
GOAL · 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
Wang et al. 2019 (arXiv 1903.08114) multi-GPU results; GPyTorch · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

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

  1. 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).
  2. 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.