Kernel multigrid: Accelerate backfitting via sparse Gaussian processes regression
Lu Zou, Liang Ding · IISE Transactions · 2025
Additive stationary Gaussian Processes (GPs) are popular nonparametric approaches for sensitivity analysis and feature selection. Bayesian backfitting is currently one of the most efficient training methods for these models. However, we prove that the convergence rate of backfitting for additive stationary GPs is no faster than (1−O(1n))t, where n and t denote the data size and the iteration number, respectively. Consequently, the backfitting requires a minimum of O(n log n) iterations to achieve convergence. We propose an algorithm called Kernel Multigrid (KMG) to enhance backfitting by incorporating a sparse Gaussian Process Regression (GPR) to process the residuals after each backfitting 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(n log n) and O(n) per iteration, respectively. Numerical experiments demonstrate that the KMG algorithm, using only a few dozen inducing points, can accurately approximate high-dimensional datasets with up to millions of randomly distributed observations in just five iterations.