# Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 86 references that are in the map.
- First posted on arXiv 20 Mar 2024.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Sparse Gaussian Processes with Spherical Harmonic Features](https://mlsanity.com/paper/2006.16649/) (2020)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Product Kernel Interpolation for Scalable Gaussian Processes](https://mlsanity.com/paper/1802.08903/) (2018)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Randomly Projected Additive Gaussian Processes for Regression](https://mlsanity.com/paper/1912.12834/) (2019)
- [Additive Gaussian Processes Revisited](https://mlsanity.com/paper/2206.09861/) (2022)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Variable selection for Gaussian processes via sensitivity analysis of the posterior predictive distribution](https://mlsanity.com/paper/1712.08048/) (2017)
- [When are Iterative Gaussian Processes Reliably Accurate?](https://mlsanity.com/paper/2112.15246/) (2021)
- [Linear-time inference for Gaussian Processes on one dimension](https://mlsanity.com/paper/2003.05554/) (2020)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations](https://mlsanity.com/paper/2203.03116/) (2022)
- [Variational Orthogonal Features](https://mlsanity.com/paper/2006.13170/) (2020)
- [A Bayesian Conjugate Gradient Method](https://mlsanity.com/paper/1801.05242/) (2018)
- [Additive Models with Trend Filtering](https://mlsanity.com/paper/1702.05037/) (2017)
- [Backfitting for large scale crossed random effects regressions](https://mlsanity.com/paper/2007.10612/) (2020)
- [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)
- [Scalable logistic regression with crossed random effects](https://mlsanity.com/paper/2105.13747/) (2021)
- [High-dimensional additive Gaussian processes under monotonicity constraints](https://mlsanity.com/paper/2205.08528/) (2022)
- [Conjugate Gradients for Kernel Machines](https://mlsanity.com/paper/1911.06048/) (2019)
- [Sparse Gaussian Processes with Spherical Harmonic Features Revisited](https://mlsanity.com/paper/2303.15948/) (2023)
- [Scalable solution to crossed random effects model with random slopes](https://mlsanity.com/paper/2307.12378/) (2023)
- [Fast Automatic Smoothing for Generalized Additive Models](https://mlsanity.com/paper/1809.09445/) (2018)

## Abstract (arXiv)

Additive Gaussian Processes (GPs) are popular approaches for nonparametric feature selection. The common training method for these models is Bayesian Back-fitting. However, the convergence rate of Back-fitting in training additive GPs is still an open problem. By utilizing a technique called Kernel Packets (KP), we prove that the convergence rate of Back-fitting is no faster than (1-O(frac1n))t, where n and t denote the data size and the iteration number, respectively. Consequently, Back-fitting requires a minimum of O(nlog n) iterations to achieve convergence. Based on KPs, we further propose an algorithm called Kernel Multigrid (KMG). This algorithm enhances Back-fitting by incorporating a sparse Gaussian Process Regression (GPR) to process the residuals after each Back-fitting iteration. It is applicable to additive GPs with both structured and scattered data. Theoretically, we prove that KMG reduces the required iterations to O(log n) while preserving the time and space complexities at O(nlog n) and O(n) per iteration, respectively. Numerically, by employing a sparse GPR with merely 10 inducing points, KMG can produce accurate approximations of high-dimensional targets within 5 iterations.