Timezone: »
Poster
Log-Linear-Time Gaussian Processes Using Binary Tree Kernels
Michael K. Cohen · Samuel Daulton · Michael A Osborne
Gaussian processes (GPs) produce good probabilistic models of functions, but most GP kernels require $O((n+m)n^2)$ time, where $n$ is the number of data points and $m$ the number of predictive locations. We present a new kernel that allows for Gaussian process regression in $O((n+m)\log(n+m))$ time. Our "binary tree" kernel places all data points on the leaves of a binary tree, with the kernel depending only on the depth of the deepest common ancestor. We can store the resulting kernel matrix in $O(n)$ space in $O(n \log n)$ time, as a sum of sparse rank-one matrices, and approximately invert the kernel matrix in $O(n)$ time. Sparse GP methods also offer linear run time, but they predict less well than higher dimensional kernels. On a classic suite of regression tasks, we compare our kernel against Mat\'ern, sparse, and sparse variational kernels. The binary tree GP assigns the highest likelihood to the test data on a plurality of datasets, usually achieves lower mean squared error than the sparse methods, and often ties or beats the Mat\'ern GP. On large datasets, the binary tree GP is fastest, and much faster than a Mat\'ern GP.
Author Information
Michael K. Cohen (University of Oxford)

I'm studying a DPhil with Mike Osborne at Oxford. My research focuses on the expected behavior of generally intelligent artificial agents. I am interested in designing agents that we can expect to behave safely.
Samuel Daulton (Meta, University of Oxford)
Research Scientist at Meta, PhD Candidate at Oxford. My research focuses on Bayesian optimization.
Michael A Osborne (U Oxford)
More from the Same Authors
-
2022 Poster: Bezier Gaussian Processes for Tall and Wide Data »
Martin Jørgensen · Michael A Osborne -
2022 Poster: Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization »
Samuel Daulton · Xingchen Wan · David Eriksson · Maximilian Balandat · Michael A Osborne · Eytan Bakshy -
2022 Poster: Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombination »
Masaki Adachi · Satoshi Hayakawa · Martin Jørgensen · Harald Oberhauser · Michael A Osborne -
2021 Poster: On Pathologies in KL-Regularized Reinforcement Learning from Expert Demonstrations »
Tim G. J. Rudner · Cong Lu · Michael A Osborne · Yarin Gal · Yee Teh -
2021 Poster: Adversarial Attacks on Graph Classifiers via Bayesian Optimisation »
Xingchen Wan · Henry Kenlay · Robin Ru · Arno Blaas · Michael A Osborne · Xiaowen Dong -
2021 Poster: Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement »
Samuel Daulton · Maximilian Balandat · Eytan Bakshy -
2020 : Contributed Talk 7: Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning »
Samuel Daulton · Hongseok Namkoong -
2020 Poster: Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization »
Samuel Daulton · Maximilian Balandat · Eytan Bakshy -
2020 Poster: Gaussian Process Bandit Optimization of the Thermodynamic Variational Objective »
Vu Nguyen · Vaden Masrani · Rob Brekelmans · Michael A Osborne · Frank Wood -
2020 Poster: Bayesian Optimization for Iterative Learning »
Vu Nguyen · Sebastian Schulze · Michael A Osborne -
2019 : Poster Session »
Gergely Flamich · Shashanka Ubaru · Charles Zheng · Josip Djolonga · Kristoffer Wickstrøm · Diego Granziol · Konstantinos Pitas · Jun Li · Robert Williamson · Sangwoong Yoon · Kwot Sin Lee · Julian Zilly · Linda Petrini · Ian Fischer · Zhe Dong · Alexander Alemi · Bao-Ngoc Nguyen · Rob Brekelmans · Tailin Wu · Aditya Mahajan · Alexander Li · Kirankumar Shiragur · Yair Carmon · Linara Adilova · SHIYU LIU · Bang An · Sanjeeb Dash · Oktay Gunluk · Arya Mazumdar · Mehul Motani · Julia Rosenzweig · Michael Kamp · Marton Havasi · Leighton P Barnes · Zhengqing Zhou · Yi Hao · Dylan Foster · Yuval Benjamini · Nati Srebro · Michael Tschannen · Paul Rubenstein · Sylvain Gelly · John Duchi · Aaron Sidford · Robin Ru · Stefan Zohren · Murtaza Dalal · Michael A Osborne · Stephen J Roberts · Moses Charikar · Jayakumar Subramanian · Xiaodi Fan · Max Schwarzer · Nicholas Roberts · Simon Lacoste-Julien · Vinay Prabhu · Aram Galstyan · Greg Ver Steeg · Lalitha Sankar · Yung-Kyun Noh · Gautam Dasarathy · Frank Park · Ngai-Man (Man) Cheung · Ngoc-Trung Tran · Linxiao Yang · Ben Poole · Andrea Censi · Tristan Sylvain · R Devon Hjelm · Bangjie Liu · Jose Gallego-Posada · Tyler Sypherd · Kai Yang · Jan Nikolas Morshuis -
2017 Poster: Robust and Efficient Transfer Learning with Hidden Parameter Markov Decision Processes »
Taylor Killian · Samuel Daulton · Finale Doshi-Velez · George Konidaris -
2017 Oral: Robust and Efficient Transfer Learning with Hidden Parameter Markov Decision Processes »
Taylor Killian · Samuel Daulton · Finale Doshi-Velez · George Konidaris -
2016 Poster: Bayesian Optimization for Probabilistic Programs »
Thomas Rainforth · Tuan Anh Le · Jan-Willem van de Meent · Michael A Osborne · Frank Wood -
2015 Workshop: Probabilistic Integration »
Michael A Osborne · Philipp Hennig -
2015 Symposium: Algorithms Among Us: the Societal Impacts of Machine Learning »
Michael A Osborne · Adrian Weller · Murray Shanahan -
2015 Poster: Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees »
François-Xavier Briol · Chris Oates · Mark Girolami · Michael A Osborne -
2015 Spotlight: Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees »
François-Xavier Briol · Chris Oates · Mark Girolami · Michael A Osborne -
2014 Poster: Sampling for Inference in Probabilistic Models with Fast Bayesian Quadrature »
Tom Gunter · Michael A Osborne · Roman Garnett · Philipp Hennig · Stephen J Roberts -
2013 Workshop: Bayesian Optimization in Theory and Practice »
Matthew Hoffman · Jasper Snoek · Nando de Freitas · Michael A Osborne · Ryan Adams · Sebastien Bubeck · Philipp Hennig · Remi Munos · Andreas Krause -
2012 Workshop: Probabilistic Numerics »
Philipp Hennig · John P Cunningham · Michael A Osborne -
2012 Poster: Active Learning of Model Evidence Using Bayesian Quadrature »
Michael A Osborne · David Duvenaud · Roman Garnett · Carl Edward Rasmussen · Stephen J Roberts · Zoubin Ghahramani -
2011 Workshop: Bayesian optimization, experimental design and bandits: Theory and applications »
Nando de Freitas · Roman Garnett · Frank R Hutter · Michael A Osborne