Timezone: »

 
Poster
Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization
Geoff Pleiss · Martin Jankowiak · David Eriksson · Anil Damle · Jacob Gardner

Thu Dec 10 09:00 AM -- 11:00 AM (PST) @ Poster Session 5 #1472
in Poster Session 6 »

Matrix square roots and their inverses arise frequently in machine learning, e.g., when sampling from high-dimensional Gaussians N(0,K) or “whitening” a vector b against covariance matrix K. While existing methods typically require O(N^3) computation, we introduce a highly-efficient quadratic-time algorithm for computing K^{1/2}b, K^{-1/2}b, and their derivatives through matrix-vector multiplication (MVMs). Our method combines Krylov subspace methods with a rational approximation and typically achieves 4 decimal places of accuracy with fewer than 100 MVMs. Moreover, the backward pass requires little additional computation. We demonstrate our method's applicability on matrices as large as 50,000 by 50,000 - well beyond traditional methods - with little approximation error. Applying this increased scalability to variational Gaussian processes, Bayesian optimization, and Gibbs sampling results in more powerful models with higher accuracy. In particular, we perform variational GP inference with up to 10,000 inducing points and perform Gibbs sampling on a 25,000-dimensional problem.

Keywords: Adversarial Networks · Generative Models · Deep Learning · Data, Challenges, Implementations, and Software -> Benchmarks; Deep Learning

Author Information

Geoff Pleiss (Columbia University)
Martin Jankowiak (Broad Institute)
David Eriksson (Facebook)
Anil Damle (Cornell University)
Jacob Gardner (University of Pennsylvania)

More from the Same Authors