2024/03/20 by Lu Zou, Liang Ding, Zou, Lu +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Advanced Neural Network Applications #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.2403.13300
openalex publication_date 2024/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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((1)/(n)))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.