Source-linked AI summary
Constant-Time Predictive Distributions for Gaussian Processes
Geoff Pleiss, Jacob R. Gardner, Kilian Q. Weinberger, Andrew Gordon Wilson
TL;DR
GP predictive uncertainty matters across applications, yet previous state-of-the-art methods have running times that depend on dataset size. LOVE applies Lanczos to predictive covariance computations, and experiments report accurate variances and samples with computations up to 18,000 times faster.
Problem
Method
LOVE applies Lanczos to predictive covariance computations, using the resulting structure for constant-time covariance entries and sampling independent of training-set size.
Source: §1 · p. 2Results
Up to 18,000 times faster: across seven datasets, LOVE's variances and samples were accurate within four decimals.
Source: §1 · p. 2Takeaways & Limitations
The authors conclude that constant-time variances and linear-time samples may improve applications requiring fast posterior samples and may unlock new applications.
Source: §5 · p. 8Precomputing terms has quadratic dependence on inducing-point count m, making it infeasible in practice when m is large.
Source: §3.1 · p. 4
Abstract
from arXiv · showhide
One of the most compelling features of Gaussian process (GP) regression is its ability to provide well-calibrated posterior distributions. Recent advances in inducing point methods have sped up GP marginal likelihood and posterior mean computations, leaving posterior covariance estimation and sampling as the remaining computational bottlenecks. In this paper we address these shortcomings by using the Lanczos algorithm to rapidly approximate the predictive covariance matrix. Our approach, which we refer to as LOVE (LanczOs Variance Estimates), substantially improves time and space complexity. In our experiments, LOVE computes covariances up to 2,000 times faster and draws samples 18,000 times faster than existing methods, all without sacrificing accuracy.
1. Introduction
GP uncertainty is valuable across applications, but covariance estimation and sampling remain costly even after inducing-point methods accelerate training and predictive means. LOVE uses Lanczos to approximate predictive covariances and reports accurate, substantially faster predictions and samples.
1. Introduction
- Predictive uncertainty matters in medicine, large-scale robotics, Bayesian optimization, and interpreting otherwise difficult-to-interpret predictions.Source: §1 · p. 1
- Inducing-point methods speed training and predictive means, but predictive covariance remains costly and existing fast approximations can incur significant error.Source: §1 · p. 1
- LOVE uses Lanczos to decompose a training-dependent matrix, enabling covariance entries in O(k) time and sampling in O(t + m) time, independent of training-set size.Source: §1 · p. 2
- Across seven datasets, variances and samples were accurate within four decimals and computed up to 18,000 times faster.Source: §1 · p. 2
2. Background
The background moves from Gaussian-process posterior distributions to matrix-vector inference, the Lanczos algorithm, and structured kernel interpolation. These tools motivate scalable predictive means and provide the foundation for the paper’s variance and sampling methods.
2. Background
- A Gaussian-process posterior over test-point function values is Gaussian, with mean and covariance determined from the prior and observed data.Sampling functions uses this joint predictive distribution.Source: §2 · p. 2
2.1. Inference with matrix-vector multiplies
- Cholesky solves with the noisy kernel matrix cost O(n^3), while conjugate gradients use matrix-vector multiplies and can need far fewer than n iterations.Structured data or inducing-point methods can make those multiplies faster.Source: §2.1 · p. 2
2.2. The Lanczos algorithm
- Lanczos builds a tridiagonal factorization from a Krylov subspace using matrix-vector multiplies; k iterations produce k basis vectors and coefficients.Lanczos solves can be accurate after k ≪ n iterations, though they require storing Q_k; factors can also jump-start later solves.Source: §2.2 · pp. 2–3
2.3. Kernel Interpolation for Scalable Structured GPs
- SKI approximates data-point kernel values by interpolation from inducing points; KISS-GP places those points on a grid to enable fast matrix-vector multiplies.For predictive means, training-dependent terms are precomputed, leaving a test-point multiplication using its sparse interpolation weights.Source: §2.3 · p. 3
3. Lanczos Variance Estimates (LOVE)
LOVE uses Lanczos low-rank approximation to make predictive covariance calculations efficient, then extends the approach to predictive sampling and additive kernel compositions.
3.1. A first O(m2) approach with KISS-GP
- The initial KISS-GP covariance approach has an O(m^2) precomputation cost, infeasible in practice when m = Θ(n), so variances are computed from scratch.Repeated variance calculations then cost O(kn + km log m) each.Source: §3.1 · p. 4
3.2. Fast predictive (co-)variances with LOVE
- LOVE approximates C with a low-rank Lanczos factorization, enabling O(k) predictive covariance calculations after O(kn + km log m) precomputation.The precomputation is performed during training; k depends on matrix conditioning, and k ≤100 suffices for most matrices in practice.Source: §3.2 · p. 4
3.3. Predictive distribution sampling with LOVE
- LOVE sampling uses a precomputed low-rank representation of the test-independent covariance term, with s samples over t points costing O(sk(t + m)) at test time.The standard Cholesky approach to the predictive covariance incurs O(t^3) cost, in addition to O(t^2) covariance evaluations.Source: §3.3 · p. 5
3.4. Extension to additive kernel compositions
- For d additive kernel components, LOVE's predictive variance computations cost only a factor O(d) more than their one-dimensional counterparts.The method applies by replacing the interpolation and kernel matrices with block forms; block interpolation takes O(d) time.Source: §3.4 · p. 5
4. Results
The results evaluate LOVE’s predictive variances and posterior samples for accuracy and speed. They report substantial computational gains while retaining accuracy across regression and Bayesian optimization experiments.
4.1. Predictive Variances
- For a 10-mixture SM kernel, KISS-GP with LOVE’s predicted variances have SMAE 1.29 × 10−4 versus Exact GP variances; test log-likelihoods across all methods range from −221 to −222.Source: §4.1 · p. 6
- LOVE matches KISS-GP without LOVE to at least 5 decimal points and approximates Exact variances with no more than 0.1% average error on large datasets.Maximum variance error is ≤2.6% on Skillcraft and ≤2.0% on PoleTele.Source: §4.1 · p. 6, Table 2 · p. 7
- At test time, LOVE computes variances up to 2,000× faster than KISS-GP without LOVE; including precomputation, its speedup is 4×–44×.Table 2 compares predictive-variance speed and accuracy; the reported speed results are GPU measurements.Source: §4.1 · p. 6, Table 2 · p. 7
4.2. Sampling
- At test time, LOVE draws samples up to 18,000 times faster than Exact GP; its sample covariance errors are 1–3 orders of magnitude below random Fourier features.From scratch, LOVE’s sampling speed is comparable to Fourier features and SGPR; Exact GP, SGPR, and LOVE all produce accurate sample covariance matrices.Source: Table 3 · p. 7, §4.2 · pp. 7–8
4.1. Predictive Variances
- After roughly 50 Lanczos iterations, predictive-variance error levels off, though the authors note this may reflect floating-point precision.Figure 2 plots error against Lanczos iterations on four datasets using KISS-GP with m = 10,000.Source: Figure 2 · p. 7, §4.1 · p. 7
4.2. Sampling
- On Eggholder after 100 Bayesian optimization iterations, LOVE’s sampled maximum-value distribution closely resembles Exact GP’s and is 700× faster.The Fourier-feature sampled distribution differs significantly from Exact GP’s.Source: Figure 3 · p. 8, §4.2 · p. 8
5. Discussion, Related Work, and Conclusion
LOVE is compatible with inducing-point methods beyond KISS-GP, with method-specific computational costs. The discussion also identifies conditions that can affect Lanczos solve accuracy and describes a numerical-stability correction.
Related work
- For SOR kernel approximations, setting k=m gives exact Lanczos solves, with O(nm^2) precomputation and O(m^2) prediction.The discussion says LOVE can cache test-invariant terms in O(knm + km^2) time for these methods.Source: §5 · p. 8
Discussion
- Lanczos solves may be inaccurate when columns of (W⊤X KUU) are nearly orthogonal to Qk; additional iterations with a new probe vector are almost never needed in practice.The authors report that the solves are almost always accurate.Source: §5 · p. 8
- When Lanczos vectors lose orthogonality from round-off, the implementation uses full reorthogonalization; its cost does not affect final running time in practice.The paper identifies loss of orthogonality in floating-point arithmetic as a source of incorrect decompositions.Source: §5 · p. 8
Conclusion
- The conclusion states that LOVE provides constant-time, near-exact predictive variances and linear-time samples, with potential to simplify GP applications requiring fast posterior samples.The authors also suggest these capabilities may enable new GP applications.Source: §5 · p. 8