# Representing Additive Gaussian Processes by Sparse Matrices

arXiv: https://arxiv.org/abs/2305.00324 · HTML: https://mlsanity.com/paper/2305.00324/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 29 Apr 2023.

## Builds on (most cited first, 9 of 9)

- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [Randomly Projected Additive Gaussian Processes for Regression](https://mlsanity.com/paper/1912.12834/) (2019)
- [Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations](https://mlsanity.com/paper/2203.03116/) (2022)
- [A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix](https://mlsanity.com/paper/1503.00374/) (2015)
- [Sample and Computationally Efficient Stochastic Kriging in High Dimensions](https://mlsanity.com/paper/2010.06802/) (2020)
- [Projection Pursuit Gaussian Process Regression](https://mlsanity.com/paper/2004.00667/) (2020)

## Abstract (arXiv)

Among generalized additive models, additive Mat'ern Gaussian Processes (GPs) are one of the most popular for scalable high-dimensional problems. Thanks to their additive structure and stochastic differential equation representation, back-fitting-based algorithms can reduce the time complexity of computing the posterior mean from O(n3) to O(nlog n) time where n is the data size. However, generalizing these algorithms to efficiently compute the posterior variance and maximum log-likelihood remains an open problem. In this study, we demonstrate that for Additive Mat'ern GPs, not only the posterior mean, but also the posterior variance, log-likelihood, and gradient of these three functions can be represented by formulas involving only sparse matrices and sparse vectors. We show how to use these sparse formulas to generalize back-fitting-based algorithms to efficiently compute the posterior mean, posterior variance, log-likelihood, and gradient of these three functions for additive GPs, all in O(n log n) time. We apply our algorithms to Bayesian optimization and propose efficient algorithms for posterior updates, hyperparameters learning, and computations of the acquisition function and its gradient in Bayesian optimization. Given the posterior, our algorithms significantly reduce the time complexity of computing the acquisition function and its gradient from O(n2) to O(log n) for general learning rate, and even to O(1) for small learning rate.