mlsanityData to 7 Oct 2026

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

arXiv 2403.13300 ↗First posted 20 Mar 2024stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

29 of 86 references.

References · 29

  1. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 603
  2. 2015Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)cited by 175
  3. 2019Exact Gaussian Processes on a Million Data Pointscited by 118
  4. 2016Variational Fourier features for Gaussian processescited by 85
  5. 2020Sparse Gaussian Processes with Spherical Harmonic Featurescited by 43
  6. 2016Preconditioning Kernel Matricescited by 32
  7. 2018Product Kernel Interpolation for Scalable Gaussian Processescited by 31
  8. 2022Posterior and Computational Uncertainty in Gaussian Processescited by 23
  9. 2021Preconditioning for Scalable Gaussian Process Hyperparameter Optimizationcited by 22
  10. 2019Randomly Projected Additive Gaussian Processes for Regressioncited by 19
  11. 2022Additive Gaussian Processes Revisitedcited by 19
  12. 2017Variable selection for Gaussian processes via sensitivity analysis of the posterior predictive distributioncited by 15
17 more
  1. 2021Bias-Free Scalable Gaussian Processes via Randomized Truncationscited by 15
  2. 2021When are Iterative Gaussian Processes Reliably Accurate?cited by 12
  3. 2020Linear-time inference for Gaussian Processes on one dimensioncited by 11
  4. 2023Large-Scale Gaussian Processes via Alternating Projectioncited by 11
  5. 2022Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlationscited by 10
  6. 2020Variational Orthogonal Featurescited by 9
  7. 2018A Bayesian Conjugate Gradient Methodcited by 7
  8. 2017Additive Models with Trend Filteringcited by 6
  9. 2020Backfitting for large scale crossed random effects regressionscited by 6
  10. 2020Sample and Computationally Efficient Stochastic Kriging in High Dimensionscited by 6
  11. 2020Projection Pursuit Gaussian Process Regressioncited by 5
  12. 2021Scalable logistic regression with crossed random effectscited by 4
  13. 2022High-dimensional additive Gaussian processes under monotonicity constraintscited by 4
  14. 2019Conjugate Gradients for Kernel Machinescited by 2
  15. 2023Sparse Gaussian Processes with Spherical Harmonic Features Revisitedcited by 2
  16. 2023Scalable solution to crossed random effects model with random slopescited by 2
  17. 2018Fast Automatic Smoothing for Generalized Additive Modelscited by 1

Built on by

Not cited yet.