Publication

Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization

Conference on Neural Information Processing Systems (NeurIPS)


Abstract

Matrix square roots and their inverses arise frequently in machine learning, e.g., when sampling from high-dimensional Gaussians 𝑁 (Ο, K) or “whitening” a vector b against covariance matrix K. While existing methods typically require O(N3) computation, we introduce a highly-efficient quadratic-time algorithm for computing K1/2b, K-1/2b, 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 × 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.

Related Publications

All Publications

EMNLP - October 1, 2021

Masked Language Modeling and the Distributional Hypothesis: Order Word Matters Pre-training for Little

Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, Douwe Kiela

IROS - September 30, 2021

Learning Navigation Skills for Legged Robots with Learned Robot Embeddings

Joanne Truong, Denis Yarats, Tianyu Li, Franziska Meier, Sonia Chernova, Dhruv Batra, Akshara Rai

IROS - September 27, 2021

Joint Sampling and Trajectory Optimization over Graphs for Online Motion Planning

Kalyan Vasudev Alwala, Mustafa Mukadam

RecSys - September 27, 2021

Transformers4Rec: Bridging the Gap between NLP and Sequential / Session-Based Recommendation

Gabriel De Souza Pereira Moreira, Sara Rabhi, Jeong Min Lee, Ronay Ak, Even Oldridge

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy