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 subsequent to 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.

通过利用核包技术（KP），我们证明了后向拟合的收敛速度不会比（1-1/n）^t 更快，其中 n 和 t 分别表示数据大小和迭代次数。因此，后向拟合需要至少 O (n*logn) 次迭代才能达到收敛。在 KP 的基础上，我们进一步提出了一种称为核多网格（KMG）的算法。该算法通过在每次后向拟合迭代之后引入稀疏高斯过程回归（GPR）来处理残差，适用于具有结构化和离散数据的附加 GP。从理论上讲，我们证明了 KMG 将所需迭代次数降低到 O (logn)，同时保持时间和空间复杂度分别为 O (n*logn) 和 O (n)。通过仅使用 10 个诱导点的稀疏 GPR，数值上证明 KMG 可以在 5 次迭代内生成高维目标的精确近似。

核多重网格：通过稀疏高斯过程回归加速反向拟合

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

How can we efficiently gather information to optimize an unknown function,
when presented with multiple, mutually dependent information sources with
different costs? For example, when optimizing a robotic system, intelligently
trading off computer simulations and real robot testings can lead to
significant savings. Existing methods, such as multi-fidelity GP-UCB or Entropy
Search-based approaches, either make simplistic assumptions on the interaction
among different fidelities or use simple heuristics that lack theoretical
guarantees. In this paper, we study multi-fidelity Bayesian optimization with
complex structural dependencies among multiple outputs, and propose
MF-MI-Greedy, a principled algorithmic framework for addressing this problem.
In particular, we model different fidelities using additive Gaussian processes
based on shared latent structures with the target function. Then we use
cost-sensitive mutual information gain for efficient Bayesian global
optimization. We propose a simple notion of regret which incorporates the cost
of different fidelities, and prove that MF-MI-Greedy achieves low regret. We
demonstrate the strong empirical performance of our algorithm on both synthetic
and real-world datasets.

本文研究了多个输出之间具有复杂结构依赖关系的多认真贝叶斯优化，并提出了 MF-MI-Greedy，一种解决此问题的原则算法框架。