Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression
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-\mathcal{O}(\frac{1}{n}))^t$, where $n$ and $t$ denote the data size and the iteration number, respectively. Consequently, Back-fitting requires a minimum of $\mathcal{O}(n\log 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 $\mathcal{O}(\log n)$ while preserving the time and space complexities at $\mathcal{O}(n\log n)$ and $\mathcal{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.
Code (0)
등록된 구현이 없습니다.
Tasks
feature selectionGaussian ProcessesGPRregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A reinforcement learning strategy to automate and accelerate h/p-multigrid solvers
We explore a reinforcement learning strategy to automate and accelerate h/p-multigrid methods in high-order solvers. Multigrid methods are very efficient but require fine-tuning of numerical parameters, such as the numbe…
reinforcement-learningReinforcement LearningAlgebraic multigrid support vector machines
The support vector machine is a flexible optimization-based technique widely used for classification problems. In practice, its training part becomes computationally expensive on large-scale data sets because of such rea…
General ClassificationMGiaD: Multigrid in all dimensions. Efficiency and robustness by coarsening in resolution and channel dimensions
Current state-of-the-art deep neural networks for image classification are made up of 10 - 100 million learnable weights and are therefore inherently prone to overfitting. The complexity of the weight count can be seen a…
Allimage-classificationImage ClassificationLayer-Parallel Training with GPU Concurrency of Deep Residual Neural Networks via Nonlinear Multigrid
A Multigrid Full Approximation Storage algorithm for solving Deep Residual Networks is developed to enable neural network parallelized layer-wise training and concurrent computational kernel execution on GPUs. This work …
GPUMultigrid Training for Molecular Generation using Graph Neural Networks
Deep learning has demonstrated significant success for modeling biochemical molecular systems, where inputs are commonly represented as graphs or 3D grids. A major challenge is that computational cost scales with resolut…