这是用户在 2025-7-6 11:21 为 file:///Users/zoe/Downloads/Yang-%E7%AD%89---2023---Efficient-Robust-Bayesian-Optimization-for-Arbit... 保存的双语快照页面，由沉浸式翻译提供双语支持。了解如何保存？

Efficient Robust Bayesian Optimization for Arbitrary Uncertain Inputs
高效鲁棒贝叶斯优化算法应对任意不确定输入

Lin Yang 林阳

Huawei Noah's Ark Lab
华为诺亚方舟实验室

China 中国

yanglin33@huawei.com

Junlong Lyu 吕俊龙

Huawei Noah's Ark Lab
华为诺亚方舟实验室

Hong Kong SAR, China
中国香港特别行政区

lyujunlong@huawei.com

Wenlong Lyu 吕文龙

Huawei Noah's Ark Lab
华为诺亚方舟实验室

China 中国

lvwenlong2@huawei.com

Zhitang Chen 陈志堂

Huawei Noah's Ark Lab
华为诺亚方舟实验室

Hong Kong SAR, China
中国香港特别行政区

chenzhitang2@huawei.com

Abstract 摘要

Bayesian Optimization (BO) is a sample-efficient optimization algorithm widely employed across various applications. In some challenging BO tasks, input uncertainty arises due to the inevitable randomness in the optimization process, such as machining errors, execution noise, or contextual variability. This uncertainty deviates the input from the intended value before evaluation, resulting in significant performance fluctuations in final result. In this paper, we introduce a novel robust Bayesian Optimization algorithm, AIRBO, which can effectively identify a robust optimum that performs consistently well under arbitrary input uncertainty. Our method directly models the uncertain inputs of arbitrary distributions by empowering the Gaussian Process with the Maximum Mean Discrepancy (MMD) and further accelerates the posterior inference via Nyström approximation. Rigorous theoretical regret bound is established under MMD estimation error and extensive experiments on synthetic functions and real problems demonstrate that our approach can handle various input uncertainties and achieve a state-of-the-art performance.
贝叶斯优化(BO)是一种样本高效的优化算法，被广泛应用于各类场景。在某些具有挑战性的 BO 任务中，由于加工误差、执行噪声或环境变异等优化过程中不可避免的随机性，会导致输入不确定性。这种不确定性使得实际评估值偏离预期输入，最终造成结果性能的显著波动。本文提出了一种新型鲁棒贝叶斯优化算法 AIRBO，能够有效识别在任意输入不确定性下均表现稳定的鲁棒最优点。我们通过将高斯过程与最大均值差异(MMD)相结合，直接对任意分布的不确定输入进行建模，并利用 Nyström 近似进一步加速后验推理。在 MMD 估计误差下建立了严格的理论遗憾界，同时通过合成函数和实际问题的广泛实验表明，本方法能处理多种输入不确定性并实现当前最优性能。

1 Introduction 1 引言

Bayesian Optimization (BO) is a powerful sequential decision-making algorithm for high-cost black-box optimization. Owing to its remarkable sample efficiency and capacity to balance exploration and exploitation, BO has been successfully applied in diverse domains, including neural architecture search [32], hyper-parameter tuning [4, 29, 12], and robotic control [18, 5], among others. Nevertheless, in some real-world problems, the stochastic nature of the optimization process, such as machining error during manufacturing, execution noise of control, or variability in contextual factor,inevitably introduces input randomness,rendering the design parameter $x$ to deviate to ${x}^{\prime }$ before evaluation. This deviation produces a fluctuation of function value $y$ and eventually leads to a performance instability of the outcome. In general, the input randomness is determined by the application scenario and can be of arbitrary distribution, even quite complex ones. Moreover, in some cases,we cannot observe the exact deviated input ${x}^{\prime }$ but a rough estimation for the input uncertainty. This is quite common for robotics and process controls. For example, consider a robot control task shown in Figure 1a,a drone is sent to a target location $x$ to perform a measurement task. However, due to the execution noise caused by the fuzzy control or a sudden wind, the drone ends up at location ${x}^{\prime } \sim P\left( x\right)$ and gets a noisy measurement $y = f\left( {x}^{\prime }\right) + \zeta$ . Instead of observing the exact value of
贝叶斯优化(BO)是一种针对高成本黑箱优化问题的强大序列决策算法。凭借其卓越的样本效率与探索-开发平衡能力，BO 已成功应用于神经网络架构搜索[32]、超参数调优[4,29,12]、机器人控制[18,5]等多个领域。然而在某些实际问题中，制造过程中的加工误差、控制执行噪声或环境因素变异等随机特性，会不可避免地引入输入随机性，导致设计参数 $x$ 在评估前偏离至 ${x}^{\prime }$ 。这种偏离会引起函数值 $y$ 的波动，最终导致输出结果的性能不稳定。通常而言，输入随机性由应用场景决定，可能服从任意分布（甚至是相当复杂的分布）。此外在某些情况下，我们无法观测到确切的偏离输入 ${x}^{\prime }$ ，而只能获得输入不确定性的粗略估计——这在机器人与过程控制领域尤为常见。例如，考虑图 1a 所示的机器人控制任务：派遣无人机前往目标位置 $x$ 执行测量任务。然而由于模糊控制产生的执行噪声或突发的阵风干扰，无人机最终抵达位置 ${x}^{\prime } \sim P\left( x\right)$ 并获取到含噪声的测量值 $y = f\left( {x}^{\prime }\right) + \zeta$ 。此时系统无法观测到确切的

Figure 1: Robust Bayesian optimization problem.
图 1：鲁棒贝叶斯优化问题

${x}^{\prime }$ ,we only have a coarse estimation of the input uncertainty $P\left( x\right)$ . The goal is to identify a robust location that gives the maximal expected measurement under the process randomness.
${x}^{\prime }$ ，我们仅对输入不确定性有一个粗略的估计 $P\left( x\right)$ 。目标是在过程随机性下找到一个能提供最大预期测量值的稳健位置。

To find a robust optimum, it is crucial to account for input uncertainty during the optimization process. Existing works [24, 3, 7, 10] along this direction assume that the exact input value, i.e., ${x}^{\prime }$ in Figure 1b,is observable and construct a surrogate model using these exact inputs. Different techniques are then employed to identify the robust optimum: Nogueira et al. utilize the unscented transform to propagate input uncertainty to the acquisition function [24], while Beland and Nair integrate over the exact GP model to obtain the posterior with input uncertainty [3]. Meanwhile, [7] designs a robust confidence-bounded acquisition and applies min-max optimization to identify the robust optimum. Similarly, $\left\lbrack {10}\right\rbrack$ constructs an adversarial surrogate with samples from the exact surrogate. These methods work quite well but are constrained by their dependence on observable input values, which may not always be practical.
为寻找鲁棒最优解，在优化过程中考虑输入不确定性至关重要。现有相关研究[24,3,7,10]均假设可以观测到精确输入值（即图 1b 中的 ${x}^{\prime }$ ），并基于这些精确输入构建代理模型。随后采用不同技术识别鲁棒最优解：Nogueira 等人利用无味变换将输入不确定性传递至采集函数[24]，Beland 和 Nair 则通过对精确 GP 模型积分来获得包含输入不确定性的后验分布[3]。同时，[7]设计了鲁棒置信边界采集函数，并应用极小极大优化来识别鲁棒最优解。类似地， $\left\lbrack {10}\right\rbrack$ 通过精确代理模型的采样构建对抗性代理模型。这些方法虽效果良好，但受限于对可观测输入值的依赖，在实际应用中可能存在局限。

An alternative approach involves directly modeling the uncertain inputs. A pioneering work by Moreno et al. [20] assumes Gaussian input distribution and employs a symmetric Kullback-Leibler divergence (SKL) to measure the distance of input variables. Dallaire et al. [13] implement a Gaussian process model with an expected kernel and derive a closed-form solution by restricting the kernel to linear, quadratic, or squared exponential kernels and assuming Gaussian inputs. Nonetheless, the applicability of these methods is limited due to their restrictive Gaussian input distribution assumption and kernel choice. To surmount these limitations, Oliveira et al. propose a robust Gaussian process model that incorporates input distribution by computing an integral kernel. Although this kernel can be applied to various distributions and offers a rigorous regret bound, its posterior inference requires a large sampling and can be time-consuming.
另一种方法直接对不确定输入进行建模。Moreno 等人[20]的开创性工作假设输入服从高斯分布，并采用对称 Kullback-Leibler 散度(SKL)来衡量输入变量的距离。Dallaire 等人[13]实现了带有期望核的高斯过程模型，通过将核函数限制为线性、二次或平方指数核，并假设高斯输入，推导出闭式解。然而，这些方法由于受限于高斯输入分布假设和核函数选择，其适用性较为有限。为克服这些限制，Oliveira 等人提出了一种鲁棒高斯过程模型，通过计算积分核来纳入输入分布。虽然该核函数可适用于多种分布并提供严格的遗憾界，但其后验推断需要大量采样且耗时较长。

In this work, we propose an Arbitrary Input uncertainty Robust Bayesian Optimization algorithm (AIRBO). This algorithm can directly model the uncertain input of arbitrary distribution and propagate the input uncertainty into the surrogate posterior, which can then be used to guide the search for robust optimum. To achieve this, we employ Gaussian Process (GP) as the surrogate and empower its kernel design with the Maximum Mean Discrepancy (MMD), which allows us to comprehensively compare the uncertain inputs in Reproducing Kernel Hilbert Space (RKHS) and accurately quantify the target function under various input uncertainties(Sec. 3.1). Moreover, to stabilize the MMD estimation and accelerate the posterior inference, we utilize Nyström approximation to reduce the space complexity of MMD estimation from $O\left( {m}^{2}\right)$ to $O\left( {mh}\right)$ ,where $h \ll m$ (Sec. 3.2). This can substantially improve the parallelization of posterior inference and a rigorous theoretical regret bound is also established under the approximation error (Sec. 4). Comprehensive evaluations on synthetic functions and real problems in Sec 5 demonstrate that our algorithm can efficiently identify robust optimum under complex input uncertainty and achieve state-of-the-art performance.
本文提出了一种任意输入不确定性鲁棒贝叶斯优化算法（AIRBO）。该算法可直接对任意分布的不确定输入进行建模，并将输入不确定性传递至代理后验分布，从而指导鲁棒最优解的搜索。为实现这一目标，我们采用高斯过程（GP）作为代理模型，并通过最大均值差异（MMD）增强其核函数设计，使我们能够在再生核希尔伯特空间（RKHS）中全面比较不确定输入，并精准量化不同输入不确定性下的目标函数（第 3.1 节）。此外，为稳定 MMD 估计并加速后验推断，我们采用 Nyström 近似将 MMD 估计的空间复杂度从 $O\left( {m}^{2}\right)$ 降至 $O\left( {mh}\right)$ （其中 $h \ll m$ ，见第 3.2 节）。该方法可显著提升后验推断的并行化效率，并在近似误差范围内建立了严格的理论遗憾界（第 4 节）。第 5 节中对合成函数和实际问题的综合评估表明，我们的算法能在复杂输入不确定性条件下高效识别鲁棒最优解，并实现最先进的性能表现。

2 Problem Formulation 2 问题表述

In this section, we first formulize the robust optimization problem under input uncertainty then briefly review the intuition behind Bayesian Optimization and Gaussian Processes.
本节首先形式化表述输入不确定性下的鲁棒优化问题，随后简要回顾贝叶斯优化与高斯过程背后的原理。

2.1 Optimization with Input Uncertainty
2.1 含输入不确定性的优化

As illustrated in Figure 1b,we consider an optimization of expensive black-box function: $f\left( x\right)$ , where $x$ is the design parameter to be tuned. At each iteration $n$ ,we select a new query point ${x}_{n}$ according to the optimization heuristics. However, due to the stochastic nature of the process, such as machining error or execution noise,the query point is perturbed to ${x}_{n}^{\prime }$ before the function evaluation. Moreover,we cannot observe the exact value of ${x}_{n}^{\prime }$ and only have a vague probability estimation of its value: ${P}_{{x}_{n}}$ . After the function evaluation,we get a noisy measurement $y = f\left( {x}_{n}^{\prime }\right) + {\zeta }_{n}$ ,where ${\zeta }_{n}$ is homogeneous measurement noise sampled from $\mathcal{N}\left( {0,{\sigma }^{2}}\right)$ . The goal is to find an optimal design parameter ${x}^{ * }$ that maximizes the expected function value under input uncertainty:
如图 1b 所示，我们考虑对昂贵黑箱函数 $f\left( x\right)$ 进行优化，其中 $x$ 是待调整的设计参数。在每次迭代 $n$ 时，我们根据优化启发式方法选择新的查询点 ${x}_{n}$ 。然而由于加工误差或执行噪声等随机因素影响，该查询点在函数评估前会被扰动为 ${x}_{n}^{\prime }$ 。此外，我们无法观测 ${x}_{n}^{\prime }$ 的确切值，仅能获得其取值的模糊概率估计： ${P}_{{x}_{n}}$ 。函数评估后，我们将得到含噪声的测量值 $y = f\left( {x}_{n}^{\prime }\right) + {\zeta }_{n}$ ，其中 ${\zeta }_{n}$ 是从 $\mathcal{N}\left( {0,{\sigma }^{2}}\right)$ 采样的同质测量噪声。我们的目标是在输入不确定性条件下，找到能最大化期望函数值的最优设计参数 ${x}^{ * }$ 。

{x}^{ * } = \underset{x}{\arg \max }{\int }_{{x}^{\prime } \sim {P}_{x}}f\left( {x}^{\prime }\right) d{x}^{\prime } = \underset{x}{\arg \max }{\mathbb{E}}_{{P}_{x}}\left\lbrack f\right\rbrack \tag{1}

Depending on the specific problem and randomness source,the input distribution ${P}_{x}$ can be arbitrary in general and even become quite complex sometimes. Here we do not place any additional assumption on them, except assuming we can sample from these input distributions, which can be easily done by approximating it with Bayesian methods and learning a parametric probabilistic model [16]. Additionally,we assume the exact values of ${x}^{\prime }$ are inaccessible,which is quite common in some real-world applications, particularly in robotics and process control [25].
根据具体问题和随机性来源的不同，输入分布 ${P}_{x}$ 通常可以是任意的，有时甚至相当复杂。此处我们不对其施加任何额外假设，仅假定能够从这些输入分布中进行采样——这可以通过贝叶斯方法近似估计或学习参数化概率模型轻松实现[16]。此外，我们假设无法获取 ${x}^{\prime }$ 的精确值，这在实际应用中（尤其是机器人学和过程控制领域[25]）十分常见。

2.2 Bayesian Optimization
2.2 贝叶斯优化

In this paper, we focus on finding the robust optimum with BO. Each iteration of BO involves two key steps: I) fitting a surrogate model and II) maximizing an acquisition function.
本文重点研究如何通过贝叶斯优化(BO)寻找鲁棒最优解。BO 的每次迭代包含两个关键步骤：I)拟合代理模型 II)最大化采集函数。

Gaussian Process Surrogate: To build a sample-efficient surrogate, we choose Gaussian Process (GP) as the surrogate model in this paper. Following [34], GP can be interpreted from a weight-space view: given a set of $n$ observations, ${\mathcal{D}}_{n} = \left\{ {\left( {{x}_{i},{y}_{i}}\right) \mid i = 1,\ldots ,n}\right\}$ . Denote all the inputs as $X \in {\mathbb{R}}^{D \times n}$ and all the output vector as $y \in {\mathbb{R}}^{n \times 1}$ . We first consider a linear surrogate:
高斯过程代理模型：为构建样本高效的代理模型，本文选择高斯过程(GP)作为基础模型。根据文献[34]，GP 可以从权重空间视角进行解释：给定一组 $n$ 观测值， ${\mathcal{D}}_{n} = \left\{ {\left( {{x}_{i},{y}_{i}}\right) \mid i = 1,\ldots ,n}\right\}$ 。将所有输入记为 $X \in {\mathbb{R}}^{D \times n}$ ，输出向量记为 $y \in {\mathbb{R}}^{n \times 1}$ 。我们首先考虑线性代理模型：

f\left( x\right) = {x}^{T}w,y = f\left( x\right) + \zeta ,\zeta \sim \mathcal{N}\left( {0,{\sigma }^{2}}\right) , \tag{2}

where $w$ is the model parameters and $\zeta$ is the observation noise. This model’s capacity is limited due to its linear form. To obtain a more powerful surrogate,we can extend it by projecting the input $x$ into a feature space $\phi \left( x\right)$ . By taking a Bayesian treatment and placing a zero mean Gaussian prior on the weight vector: $w \sim \mathcal{N}\left( {0,{\sum }_{p}}\right)$ ,its predictive distribution can be derived as follows (see Section2.1 of [34] for detailed derivation):
其中 $w$ 为模型参数， $\zeta$ 为观测噪声。由于线性形式的限制，该模型表达能力有限。为获得更强大的代理模型，可通过将输入 $x$ 投影到特征空间 $\phi \left( x\right)$ 进行扩展。采用贝叶斯处理方法并对权重向量施加零均值高斯先验： $w \sim \mathcal{N}\left( {0,{\sum }_{p}}\right)$ ，其预测分布可推导如下（详细推导参见[34]第 2.1 节）：

{f}_{ * } \mid {x}_{ * },X,y \sim \mathcal{N}\left( {{\phi }^{T}\left( {x}_{ * }\right) {\sum }_{p}\phi \left( X\right) {\left( A + {\sigma }_{n}^{2}I\right) }^{-1}y,}\right. \tag{3}

\left. {{\phi }^{T}\left( {x}_{ * }\right) {\sum }_{p}\phi \left( {x}_{ * }\right) - {\phi }^{T}\left( {x}_{ * }\right) {\sum }_{p}\phi \left( X\right) {\left( A + {\sigma }_{n}^{2}I\right) }^{-1}{\phi }^{T}\left( X\right) {\sum }_{p}\phi \left( {x}_{ * }\right) }\right) \text{,}

where $A = {\phi }^{T}\left( X\right) {\sum }_{p}\phi \left( X\right)$ and $I$ is a identity matrix. Note the predictive distribution is also a Gaussian and the feature mappings are always in the form of inner product with respect to ${\sum }_{p}$ This implies we are comparing inputs in a feature space and enables us to apply kernel trick. Therefore,instead of exactly defining a feature mapping $\phi \left( \cdot \right)$ ,we can define a kernel: $k\left( {x,{x}^{\prime }}\right) =$ $\phi {\left( x\right) }^{T}{\sum }_{p}\phi \left( {x}^{\prime }\right) = \psi \left( x\right) \cdot \psi \left( {x}^{\prime }\right)$ . Substituting it into Eq. 3 gives the vanilla GP posterior:
其中 $A = {\phi }^{T}\left( X\right) {\sum }_{p}\phi \left( X\right)$ 和 $I$ 为单位矩阵。需要注意的是预测分布同样服从高斯分布，且特征映射始终以 ${\sum }_{p}$ 为基准采用内积形式。这意味着我们是在特征空间中进行输入比较，从而能够应用核技巧。因此，无需精确定义特征映射 $\phi \left( \cdot \right)$ ，我们可以直接定义核函数： $k\left( {x,{x}^{\prime }}\right) =$ $\phi {\left( x\right) }^{T}{\sum }_{p}\phi \left( {x}^{\prime }\right) = \psi \left( x\right) \cdot \psi \left( {x}^{\prime }\right)$ 。将其代入公式 3 即可得到标准高斯过程后验：

{f}_{ * } \mid X,y,{X}_{ * } \sim \mathcal{N}\left( {{\mu }_{ * },{\sum }_{ * }}\right) \text{,where}{\mu }_{ * } = K\left( {{X}_{ * },X}\right) {\left\lbrack K\left( X,X\right) + {\sigma }_{n}^{2}I\right\rbrack }^{-1}y\text{,} \tag{4}

{\sum }_{ * } = K\left( {{X}_{ * },{X}_{ * }}\right) - K\left( {{X}_{ * },X}\right) {\left\lbrack K\left( X,X\right) + {\sigma }_{n}^{2}I\right\rbrack }^{-1}K\left( {X,{X}_{ * }}\right) .

From this interpretation of GP,we note that its core idea is to project the input $x$ to a (possibly infinite) feature space $\psi \left( x\right)$ and compare them in the Reproducing Kernel Hilbert Space (RKHS) defined by kernel.
从高斯过程的这种解释中，我们注意到其核心思想是将输入 $x$ 投影到（可能是无限维的）特征空间 $\psi \left( x\right)$ ，并在由核函数定义的再生核希尔伯特空间(RKHS)中进行比较。

Acquisition Function Optimization: Given the posterior of GP surrogate model, the next step is to decide a query point ${x}_{n}$ . The exploitation and exploration balance is achieved by designing an acquisition function $\alpha \left( {x \mid {\mathcal{D}}_{n}}\right)$ . Through numerous acquisition functions exist [28],we follow [25,7] and adopt the Upper Confidence Bound (UCB) acquisition:
采集函数优化：给定 GP 代理模型的后验分布，下一步是确定查询点 ${x}_{n}$ 。通过设计采集函数 $\alpha \left( {x \mid {\mathcal{D}}_{n}}\right)$ 来实现开发与探索的平衡。尽管存在多种采集函数[28]，我们遵循[25,7]采用上置信界(UCB)采集函数：

\alpha \left( {x \mid {\mathcal{D}}_{n}}\right) = {\mu }_{ * }\left( x\right) + \beta {\sigma }_{ * }\left( x\right) , \tag{5}

where $\beta$ is a hyper-parameter to control the level of exploration.
其中 $\beta$ 是控制探索程度的超参数。

3 Proposed Method 3 研究方法

To cope with randomness during the optimization process, we aim to build a robust surrogate that can directly accept the uncertain inputs of arbitrary distributions and propagate the input uncertainty into the posterior. Inspired by the weight-space interpretation of GP, we empower GP kernel with MMD to compare the uncertain inputs in RKHS. In this way, the input randomness is considered during the covariance computation and naturally reflected in the resulting posterior, which then can be used to guide the search for a robust optimum(Sec. 3.1). To further accelerate the posterior inference, we employ Nyström approximation to stabilize the MMD estimation and reduce its space complexity (Sec. 3.2).
为应对优化过程中的随机性，我们旨在构建一个能直接接受任意分布不确定输入，并将输入不确定性传递至后验分布的鲁棒代理模型。受高斯过程权重空间解释的启发，我们通过最大平均差异（MMD）增强高斯过程核函数，在再生核希尔伯特空间中进行不确定输入的比较。这种方法在协方差计算时考虑了输入随机性，并自然地反映在最终后验分布中，从而可用来指导鲁棒最优解的搜索（第 3.1 节）。为进一步加速后验推断，我们采用 Nyström 近似法来稳定 MMD 估计并降低其空间复杂度（第 3.2 节）。

3.1 Modeling the Uncertain Inputs
3.1 不确定输入建模

Assume ${P}_{x} \in {\mathcal{P}}_{\mathcal{X}} \subset \mathcal{P}$ are a set of distribution densities over ${\mathbb{R}}^{d}$ ,representing the distributions of the uncertain inputs. We are interested in building a GP surrogate over the probability space $\mathcal{P}$ ,which requires to measure the difference between the uncertain inputs.
假设 ${P}_{x} \in {\mathcal{P}}_{\mathcal{X}} \subset \mathcal{P}$ 是定义在 ${\mathbb{R}}^{d}$ 上的一组概率密度函数，表示不确定输入的分布。我们的目标是在概率空间 $\mathcal{P}$ 上构建高斯过程代理模型，这需要度量不确定输入之间的差异。

To do so, we turn to the Integral Probabilistic Metric (IPM) [23]. The basic idea behind IPM is to define a distance measure between two distributions $P$ and $\bar{Q}$ as the supremum over a class of functions $\mathcal{G}$ of the absolute expectation difference:
为此，我们采用积分概率度量(IPM)[23]。IPM 的核心思想是将两个分布 $P$ 和 $\bar{Q}$ 之间的距离定义为函数类 $\mathcal{G}$ 上期望差绝对值的上确界：

d\left( {P,Q}\right) = \mathop{\sup }\limits_{{g \in \mathcal{G}}}\left| {{\mathbb{E}}_{u \sim P}g\left( u\right) - {\mathbb{E}}_{v \sim Q}g\left( v\right) }\right| , \tag{6}

where $\mathcal{G}$ is a class of functions that satisfies certain conditions. Different choices of $\mathcal{G}$ lead to various IPMs. For example, if we restrict the function class to be uniformly bounded in RKHS we can get the MMD [15],while a Lipschitz-continuous $\mathcal{G}$ realizes the Wasserstein distance [14].
其中 $\mathcal{G}$ 是满足特定条件的函数类。不同的 $\mathcal{G}$ 选择会导出不同的 IPM。例如，若将函数类限制在 RKHS 中一致有界，则可得到 MMD[15]；而选择 Lipschitz 连续函数 $\mathcal{G}$ 则实现 Wasserstein 距离[14]。

In this work, we choose MMD as the distance measurement for the uncertain inputs because of its intrinsic connection with distance measurement in RKHS. Given a characteristic kernel $k$ : ${\mathbb{R}}^{d} \times {\mathbb{R}}^{d} \rightarrow \mathbb{R}$ and associate RKHS ${\mathcal{H}}_{k}$ ,define the mean map $\psi : \mathcal{P} \rightarrow {\mathcal{H}}_{k}$ such that $\langle \psi \left( P\right) ,g\rangle =$ ${\mathbb{E}}_{P}\left\lbrack g\right\rbrack ,\forall g \in {\mathcal{H}}_{k}$ . The MMD between $P,Q \in \mathcal{P}$ is defined as:
本研究选择 MMD 作为不确定输入的距离度量，因其与 RKHS 中的距离度量存在本质关联。给定特征核 $k$ ： ${\mathbb{R}}^{d} \times {\mathbb{R}}^{d} \rightarrow \mathbb{R}$ 及其关联的 RKHS ${\mathcal{H}}_{k}$ ，定义均值映射 $\psi : \mathcal{P} \rightarrow {\mathcal{H}}_{k}$ 使得 $\langle \psi \left( P\right) ,g\rangle =$ ${\mathbb{E}}_{P}\left\lbrack g\right\rbrack ,\forall g \in {\mathcal{H}}_{k}$ 。分布 $P,Q \in \mathcal{P}$ 之间的 MMD 定义为：

\operatorname{MMD}\left( {P,Q}\right) = \mathop{\sup }\limits_{{\parallel g{\parallel }_{k} \leq 1}}\left\lbrack {{\mathbb{E}}_{u \sim P}g\left( u\right) - {\mathbb{E}}_{v \sim Q}g\left( v\right) }\right\rbrack = \begin{Vmatrix}{{\psi }_{P} - {\psi }_{Q}}\end{Vmatrix}, \tag{7}

Without any additional assumption on the input distributions,except we can get $m$ samples ${\left\{ {u}_{i}\right\} }_{i = 1}^{m},{\left\{ {v}_{i}\right\} }_{i = 1}^{m}$ from $P,Q$ respectively,MMD can be empirically estimated as follows [21]:
在不对输入分布做任何额外假设的情况下，只要我们能分别从 $P,Q$ 中获取 $m$ 样本 ${\left\{ {u}_{i}\right\} }_{i = 1}^{m},{\left\{ {v}_{i}\right\} }_{i = 1}^{m}$ ，即可通过以下方式经验性估计 MMD[21]：

{\operatorname{MMD}}^{2}\left( {P,Q}\right) \approx \frac{1}{m\left( {m - 1}\right) }\mathop{\sum }\limits_{{1 \leq i,j \leq m,i \neq j}}\left( {k\left( {{u}_{i},{u}_{j}}\right) + k\left( {{v}_{i},{v}_{j}}\right) }\right) - \frac{2}{{m}^{2}}\mathop{\sum }\limits_{{1 \leq i,j \leq m}}k\left( {{u}_{i},{v}_{j}}\right) , \tag{8}

To integrate MMD into the GP surrogate,we design an MMD-based kernel over $\mathcal{P}$ as follows:
为了将 MMD 整合到高斯过程代理模型中，我们设计了基于 MMD 的 $\mathcal{P}$ 核函数如下：

\widehat{k}\left( {P,Q}\right) = \exp \left( {-\alpha {\mathrm{{MMD}}}^{2}\left( {P,Q}\right) }\right) , \tag{9}

with a learnable scaling parameter $\alpha$ . This is a valid kernel,and universal w.r.t. $C\left( \mathcal{P}\right)$ under mild conditions (see Theorem 2.2, [11]). Also, it is worth to mention that, to compute the GP posterior, we only need to sample $m$ points from the input distributions,but do not require their corresponding function values.
其中 $\alpha$ 为可学习的缩放参数。这是一个有效的核函数，在温和条件下对 $C\left( \mathcal{P}\right)$ 具有普适性（参见定理 2.2，[11]）。值得注意的是，计算 GP 后验时仅需从输入分布中采样 $m$ 个点，而无需其对应的函数值。

With the MMD kernel,our surrogate model places a prior $\mathcal{G}\mathcal{P}\left( {0,\widehat{k}\left( {{P}_{x},{P}_{{x}^{\prime }}}\right) }\right)$ and obtain a dataset $\left. {{\mathcal{D}}_{n} = \left\{ {\left( {{\widehat{x}}_{i},{y}_{i}}\right) \mid {\widehat{x}}_{i} \sim {P}_{{x}_{i}},i = 1,2,\ldots ,n}\right) }\right\}$ . The posterior is Gaussian with mean and variance:
通过 MMD 核函数，我们的代理模型设置先验 $\mathcal{G}\mathcal{P}\left( {0,\widehat{k}\left( {{P}_{x},{P}_{{x}^{\prime }}}\right) }\right)$ 并获取数据集 $\left. {{\mathcal{D}}_{n} = \left\{ {\left( {{\widehat{x}}_{i},{y}_{i}}\right) \mid {\widehat{x}}_{i} \sim {P}_{{x}_{i}},i = 1,2,\ldots ,n}\right) }\right\}$ 。其后验分布为高斯分布，其均值与方差为：

{\widehat{\mu }}_{n}\left( {P}_{ * }\right) = {\widehat{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n} \tag{10}

{\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) = \widehat{k}\left( {{P}_{ * },{P}_{ * }}\right) - {\widehat{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) , \tag{11}

3.2 Boosting posterior inference with Nyström Approximation
3.2 利用 Nyström 近似加速后验推断

To derive the posterior distribution of our robust GP surrogate, it requires estimating the MMD between each pair of inputs. Gretton et al. prove the empirical estimator in Eq. 8 approximates MMD in a bounded and asymptotic way [15]. However,the sampling size $m$ used for estimation greatly affects the approximation error and insufficient sampling leads to a high estimation variance(ref Figure 3a). Such an MMD estimation variance causes numerical instability of the covariance matrix and propagates into the posterior distribution and acquisition function, rendering the search for optimal query point a challenging task. Figure 3b gives an example of MMD-GP posterior with insufficient samples, which produces a noisy acquisition function and impedes the search of optima. Increasing the sampling size can help alleviate this issue. However, the computation and space complexities of the empirical MMD estimator scale quadratically with the sampling size $m$ . This leaves us with a dilemma that insufficient sampling results in a highly-varied posterior while a larger sample size can occupy significant GPU memory and reduce the ability for parallel computation.
为推导鲁棒高斯过程代理模型的后验分布，需计算每对输入间的最大均值差异(MMD)。Gretton 等人证明公式 8 中的经验估计器能以有界渐近方式近似 MMD[15]。但用于估计的采样规模 $m$ 会显著影响近似误差，采样不足将导致较高的估计方差（参见图 3a）。这种 MMD 估计方差会造成协方差矩阵数值不稳定，并传递至后验分布和采集函数，使得最优查询点的搜索变得困难。图 3b 展示了采样不足时 MMD-GP 后验的实例，其产生的噪声采集函数会阻碍最优值搜索。增大采样规模可缓解此问题，但经验 MMD 估计器的计算与空间复杂度会随采样规模 $m$ 呈平方级增长。这使我们陷入两难困境：采样不足会导致后验分布波动剧烈，而增大样本量又会占用大量 GPU 内存并削弱并行计算能力。

To reduce the space and computation complexity while retaining a stable MMD estimation, we resort to the Nyström approximation [33]. This method alleviates the computational cost of kernel matrix by randomly selecting $h$ subsamples from the $m$ samples $\left( {h \ll m}\right)$ and computes an approximated matrix via $\widetilde{K} = {K}_{mh}{K}_{h}^{ + }{K}_{mh}^{T}$ . Combining this with the MMD definition gives its Nyström estimator:
为在保持稳定 MMD 估计的同时降低空间和计算复杂度，我们采用 Nyström 近似法[33]。该方法通过从 $m$ 样本 $\left( {h \ll m}\right)$ 中随机选取 $h$ 个子样本，并经由 $\widetilde{K} = {K}_{mh}{K}_{h}^{ + }{K}_{mh}^{T}$ 计算近似矩阵，从而缓解核矩阵的计算开销。将其与 MMD 定义结合可得到 Nyström 估计量：

{\operatorname{MMD}}^{2}\left( {P,Q}\right) = {\mathbb{E}}_{u,{u}^{\prime } \sim P\bigotimes P}\left\lbrack {k\left( {u,{u}^{\prime }}\right) }\right\rbrack + {\mathbb{E}}_{v,{v}^{\prime } \sim Q\bigotimes Q}\left\lbrack {k\left( {v,{v}^{\prime }}\right) }\right\rbrack - 2{\mathbb{E}}_{u,v \sim P\bigotimes Q}\left\lbrack {k\left( {u,v}\right) }\right\rbrack

\approx \frac{1}{{m}^{2}}{\mathbf{1}}_{m}^{T}U{\mathbf{1}}_{m} + \frac{1}{{m}^{2}}{\mathbf{1}}_{m}^{T}V{\mathbf{1}}_{m} - \frac{2}{{m}^{2}}{\mathbf{1}}_{m}^{T}W{\mathbf{1}}_{m}

\approx \frac{1}{{m}^{2}}{\mathbf{1}}_{m}^{T}{U}_{mh}{U}_{h}^{ + }{U}_{mh}^{T}{\mathbf{1}}_{n} + \frac{1}{{m}^{2}}{\mathbf{1}}_{m}^{T}{V}_{mh}{V}_{h}^{ + }{V}_{mh}^{T}{\mathbf{1}}_{m} - \frac{2}{{m}^{2}}{\mathbf{1}}_{m}^{T}{W}_{mh}{W}_{h}^{ + }{W}_{mh}^{T}{\mathbf{1}}_{m}

(12)

where $U = K\left( {\mathbf{u},{\mathbf{u}}^{\prime }}\right) ,V = K\left( {\mathbf{v},{\mathbf{v}}^{\prime }}\right) ,W = K\left( {\mathbf{u},\mathbf{v}}\right)$ are the kernel matrices, ${\mathbf{1}}_{m}$ represents a m-by-1 vector of ones, $m$ defines the sampling size and $h$ controls the sub-sampling size. Note that this Nyström estimator reduces the space complexity of posterior inference from $O\left( {{MN}{m}^{2}}\right)$ to $O\left( {MNmh}\right)$ ,where $M$ and $N$ are the numbers of training and testing samples, $m$ is the sampling size for MMD estimation while $h \ll m$ is the sub-sampling size. This can significantly boost the posterior inference of robust GP by allowing more inference to run in parallel on GPU.
其中 $U = K\left( {\mathbf{u},{\mathbf{u}}^{\prime }}\right) ,V = K\left( {\mathbf{v},{\mathbf{v}}^{\prime }}\right) ,W = K\left( {\mathbf{u},\mathbf{v}}\right)$ 表示核矩阵， ${\mathbf{1}}_{m}$ 代表一个 m×1 的全 1 向量， $m$ 定义采样大小， $h$ 控制子采样规模。需要注意的是，这种 Nyström 估计器将后验推断的空间复杂度从 $O\left( {{MN}{m}^{2}}\right)$ 降低至 $O\left( {MNmh}\right)$ ，其中 $M$ 和 $N$ 分别表示训练样本与测试样本数量， $m$ 是 MMD 估计的采样规模，而 $h \ll m$ 为子采样规模。该方法通过支持更多并行 GPU 推理计算，能显著提升鲁棒高斯过程的后验推断效率。

4 Theoretical Analysis 第四章理论分析

Assume $x \in \mathcal{X} \subset {\mathbb{R}}^{d}$ ,and ${P}_{x} \in {\mathcal{P}}_{\mathcal{X}} \subset \mathcal{P}$ are a set of distribution densities over ${\mathbb{R}}^{d}$ ,representing the distribution of the noisy input. Given a characteristic kernel $k : {\mathbb{R}}^{d} \times {\mathbb{R}}^{d} \rightarrow \mathbb{R}$ and associate RKHS ${\mathcal{H}}_{k}$ ,we define the mean map $\psi : \mathcal{P} \rightarrow {\mathcal{H}}_{k}$ such that $\langle \psi \left( P\right) ,g\rangle = {\mathbb{E}}_{P}\left\lbrack g\right\rbrack ,\forall g \in {\mathcal{H}}_{k}$ .
假设 $x \in \mathcal{X} \subset {\mathbb{R}}^{d}$ 和 ${P}_{x} \in {\mathcal{P}}_{\mathcal{X}} \subset \mathcal{P}$ 是定义在 ${\mathbb{R}}^{d}$ 上的一组分布密度，表示含噪输入的分布。给定特征核 $k : {\mathbb{R}}^{d} \times {\mathbb{R}}^{d} \rightarrow \mathbb{R}$ 及其对应的再生核希尔伯特空间 ${\mathcal{H}}_{k}$ ，我们定义均值映射 $\psi : \mathcal{P} \rightarrow {\mathcal{H}}_{k}$ 使得 $\langle \psi \left( P\right) ,g\rangle = {\mathbb{E}}_{P}\left\lbrack g\right\rbrack ,\forall g \in {\mathcal{H}}_{k}$ 成立。

We consider a more general case. Choosing any suitable functional $L$ such that $\widehat{k}\left( {P,{P}^{\prime }}\right) \mathrel{\text{:=}}$ $L\left( {{\psi }_{P},{\psi }_{{P}^{\prime }}}\right)$ is a positive-definite kernel over $\mathcal{P}$ ,for example the linear kernel ${\left\langle {\psi }_{P},{\psi }_{{P}^{\prime }}\right\rangle }_{k}$ and radial kernels $\exp \left( {-\alpha {\begin{Vmatrix}{\psi }_{P} - {\psi }_{{P}^{\prime }}\end{Vmatrix}}_{k}^{2}}\right)$ using the MMD distance as a metric. Such a kernel $\widehat{k}$ is associated with a RKHS ${\mathcal{H}}_{\widehat{k}}$ containing functions over the space of probability measures $\mathcal{P}$ .
我们考虑更一般化的情况。选择任意合适的泛函 $L$ 使得 $\widehat{k}\left( {P,{P}^{\prime }}\right) \mathrel{\text{:=}}$ $L\left( {{\psi }_{P},{\psi }_{{P}^{\prime }}}\right)$ 成为定义在 $\mathcal{P}$ 上的正定核，例如采用 MMD 距离作为度量的线性核 ${\left\langle {\psi }_{P},{\psi }_{{P}^{\prime }}\right\rangle }_{k}$ 和径向基核 $\exp \left( {-\alpha {\begin{Vmatrix}{\psi }_{P} - {\psi }_{{P}^{\prime }}\end{Vmatrix}}_{k}^{2}}\right)$ 。此类核函数 $\widehat{k}$ 关联着一个再生核希尔伯特空间 ${\mathcal{H}}_{\widehat{k}}$ ，该空间包含定义在概率测度空间 $\mathcal{P}$ 上的函数。

One important theoretical guarantee to conduct $\mathcal{{GP}}$ model is that our object function can be approximated by functions in ${\mathcal{H}}_{\widehat{k}}$ ,which relies on the universality of $\widehat{k}$ . Let $C\left( \mathcal{P}\right)$ be the class of continuous functions over $\mathcal{P}$ endowed with the topology of weak convergence and the associated Borel $\sigma$ -algebra, and we define $\widehat{f} \in C\left( \mathcal{P}\right)$ such that
构建 $\mathcal{{GP}}$ 模型的重要理论保证在于：目标函数可由 ${\mathcal{H}}_{\widehat{k}}$ 空间中的函数逼近，这依赖于 $\widehat{k}$ 的普适性。设 $C\left( \mathcal{P}\right)$ 为 $\mathcal{P}$ 上赋予弱收敛拓扑及相应 Borel $\sigma$ -代数的连续函数类，我们定义 $\widehat{f} \in C\left( \mathcal{P}\right)$ 满足

\widehat{f}\left( P\right) \mathrel{\text{:=}} {\mathbb{E}}_{P}\left\lbrack f\right\rbrack ,\forall P \in \mathcal{P},

which is just our object function,For $\widehat{k}$ be radial kernels,it has been shown that $\widehat{k}$ is universal w.r.t $C\left( \mathcal{P}\right)$ given that $\mathcal{X}$ is compact and the mean map $\psi$ is injective [11,22]. For $\widehat{k}$ be linear kernel which is not universal,it has been shown in Lemma 1,[26] that $\widehat{f} \in \overline{{\mathcal{H}}_{\widehat{k}}}$ if and only if $f \in \mathcal{H}$ and further $\parallel \widehat{f}{\parallel }_{\widehat{k}} = \parallel f{\parallel }_{k}$ . Thus,in the remain of this chapter,we may simply assume $\widehat{f} \in {\mathcal{H}}_{\widehat{k}}$ .
这正是我们的目标函数。对于径向核 $\widehat{k}$ ，已有研究表明，当 $\mathcal{X}$ 是紧集且均值映射 $\psi$ 是单射时， $\widehat{k}$ 相对于 $C\left( \mathcal{P}\right)$ 具有普适性[11,22]。而对于非普适性的线性核 $\widehat{k}$ ，文献[26]中的引理 1 证明 $\widehat{f} \in \overline{{\mathcal{H}}_{\widehat{k}}}$ 当且仅当 $f \in \mathcal{H}$ 且进一步满足 $\parallel \widehat{f}{\parallel }_{\widehat{k}} = \parallel f{\parallel }_{k}$ 。因此，在本章后续内容中，我们可以直接假设 $\widehat{f} \in {\mathcal{H}}_{\widehat{k}}$ 成立。

Suppose we have an approximation kernel function $\widetilde{k}\left( {P,Q}\right)$ near to the exact kernel function $\widehat{k}\left( {P,Q}\right)$ . The mean ${\widehat{\mu }}_{n}\left( {p}_{ * }\right)$ and variance ${\widehat{\sigma }}_{n}^{2}\left( {p}_{ * }\right)$ are approximated by
假设我们有一个近似核函数 $\widetilde{k}\left( {P,Q}\right)$ 接近于精确核函数 $\widehat{k}\left( {P,Q}\right)$ 。其均值 ${\widehat{\mu }}_{n}\left( {p}_{ * }\right)$ 和方差 ${\widehat{\sigma }}_{n}^{2}\left( {p}_{ * }\right)$ 可通过以下方式近似得到。

{\widetilde{\mu }}_{n}\left( {P}_{ * }\right) = {\widetilde{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widetilde{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n} \tag{13}

{\widetilde{\sigma }}_{n}^{2}\left( {P}_{ * }\right) = \widetilde{k}\left( {{P}_{ * },{P}_{ * }}\right) - {\widetilde{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widetilde{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widetilde{\mathbf{k}}}_{n}\left( {P}_{ * }\right) , \tag{14}

where ${\mathbf{y}}_{n} \mathrel{\text{:=}} {\left\lbrack {y}_{1},\cdots ,{y}_{n}\right\rbrack }^{T},{\widetilde{\mathbf{k}}}_{n}\left( {P}_{ * }\right) \mathrel{\text{:=}} {\left\lbrack \widetilde{k}\left( {P}_{ * },{P}_{1}\right) ,\cdots ,\widetilde{k}\left( {P}_{ * },{P}_{n}\right) \right\rbrack }^{T}$ and ${\left\lbrack {\widetilde{\mathbf{K}}}_{n}\right\rbrack }_{ij} = \widetilde{k}\left( {{P}_{i},{P}_{j}}\right)$ . The maximum information gain corresponding to the kernel $\widehat{k}$ is denoted as
其中 ${\mathbf{y}}_{n} \mathrel{\text{:=}} {\left\lbrack {y}_{1},\cdots ,{y}_{n}\right\rbrack }^{T},{\widetilde{\mathbf{k}}}_{n}\left( {P}_{ * }\right) \mathrel{\text{:=}} {\left\lbrack \widetilde{k}\left( {P}_{ * },{P}_{1}\right) ,\cdots ,\widetilde{k}\left( {P}_{ * },{P}_{n}\right) \right\rbrack }^{T}$ 和 ${\left\lbrack {\widetilde{\mathbf{K}}}_{n}\right\rbrack }_{ij} = \widetilde{k}\left( {{P}_{i},{P}_{j}}\right)$ 。与核函数 $\widehat{k}$ 对应的最大信息增益定义为

{\widehat{\gamma }}_{n} \mathrel{\text{:=}} \mathop{\sup }\limits_{{\mathcal{R} \in \mathcal{P}\mathcal{X};\left| \mathcal{R}\right| = n}}\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid \mathcal{R}}\right) = \frac{1}{2}\ln \det \left( {\mathbf{I} + {\sigma }^{-2}{\widehat{\mathbf{K}}}_{n}}\right) ,

Denote $e\left( {P,Q}\right) = \widehat{k}\left( {P,Q}\right) - \widetilde{k}\left( {P,Q}\right)$ as the error function when estimating the kernel $\widehat{k}$ . We suppose $e\left( {P,Q}\right)$ has an upper bound with high probability:
记 $e\left( {P,Q}\right) = \widehat{k}\left( {P,Q}\right) - \widetilde{k}\left( {P,Q}\right)$ 为核函数 $\widehat{k}$ 估计过程中的误差函数。我们假设 $e\left( {P,Q}\right)$ 以高概率存在上界：

Assumption 1. For any $\varepsilon > 0,P,Q \in {\mathcal{P}}_{\mathcal{X}}$ ,we may choose an estimated $\widetilde{k}\left( {P,Q}\right)$ such that the error function $e\left( {P,Q}\right)$ can be upper-bounded by ${e}_{\varepsilon }$ with probability at least $1 - \varepsilon$ ,that is, $\mathbb{P}\left( {\left| {e\left( {P,Q}\right) }\right| \leq {e}_{\varepsilon }}\right) > 1 - \varepsilon$
假设 1. 对于任意 $\varepsilon > 0,P,Q \in {\mathcal{P}}_{\mathcal{X}}$ ，我们总能选择一个估计量 $\widetilde{k}\left( {P,Q}\right)$ ，使得误差函数 $e\left( {P,Q}\right)$ 能以至少 $1 - \varepsilon$ 的概率被 ${e}_{\varepsilon }$ 上界控制，即满足 $\mathbb{P}\left( {\left| {e\left( {P,Q}\right) }\right| \leq {e}_{\varepsilon }}\right) > 1 - \varepsilon$

Remark. Note that this assumption is standard in our case: we may assume $\mathop{\max }\limits_{{x \in \mathcal{X}}}\parallel \phi {\parallel }_{k} \leq \Phi$ , where $\phi$ is the feature map corresponding to the $k$ . Then when using empirical estimator,the error between ${\mathrm{{MMD}}}_{\text{empirical }}$ and MMD is controlled by ${4\Phi }\sqrt{2\log \left( {6/\varepsilon }\right) {m}^{-1}}$ with probability at least $1 - \varepsilon$ according to Lemma E.1, [8]. When using the Nyström estimator, the error has a similar form as the empirical one,and under mild conditions,when $h = O\left( {\sqrt{m}\log \left( m\right) }\right)$ ,we get the error of the order $O\left( {{m}^{-1/2}\log \left( {1/\varepsilon }\right) }\right)$ with probability at least $1 - \varepsilon$ . One can check more details in Lemma 1,
注记。请注意这一假设在本研究中是标准设定：我们可以设 $\mathop{\max }\limits_{{x \in \mathcal{X}}}\parallel \phi {\parallel }_{k} \leq \Phi$ ，其中 $\phi$ 表示对应于 $k$ 的特征映射。当采用经验估计量时，根据文献[8]中的引理 E.1， ${\mathrm{{MMD}}}_{\text{empirical }}$ 与 MMD 之间的误差以至少 $1 - \varepsilon$ 的概率被 ${4\Phi }\sqrt{2\log \left( {6/\varepsilon }\right) {m}^{-1}}$ 控制。使用 Nyström 估计量时，误差形式与经验估计量相似，在温和条件下当 $h = O\left( {\sqrt{m}\log \left( m\right) }\right)$ 时，我们以至少 $1 - \varepsilon$ 的概率获得 $O\left( {{m}^{-1/2}\log \left( {1/\varepsilon }\right) }\right)$ 量级的误差。更多细节可参阅引理 1，

Now we restrict our Gaussian process in the subspace ${\mathcal{P}}_{\mathcal{X}} = \left\{ {{P}_{x},x \in \mathcal{X}}\right\} \subset \mathcal{P}$ . We assume the observation ${y}_{i} = f\left( {x}_{i}\right) + {\zeta }_{i}$ with the noise ${\zeta }_{i}$ . The input-induced noise is defined as $\Delta {f}_{{p}_{{x}_{i}}} \mathrel{\text{:=}}$ $f\left( {x}_{i}\right) - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = f\left( {x}_{i}\right) - \widehat{f}\left( {P}_{{x}_{i}}\right)$ . Then the total noise is ${y}_{i} - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = {\zeta }_{i} + \Delta {f}_{{p}_{{x}_{i}}}$ . We can state our main result, which gives a cumulative regret bound under inexact kernel calculations,
现在我们将高斯过程限制在子空间 ${\mathcal{P}}_{\mathcal{X}} = \left\{ {{P}_{x},x \in \mathcal{X}}\right\} \subset \mathcal{P}$ 中。假设观测值 ${y}_{i} = f\left( {x}_{i}\right) + {\zeta }_{i}$ 带有噪声 ${\zeta }_{i}$ 。输入诱导噪声定义为 $\Delta {f}_{{p}_{{x}_{i}}} \mathrel{\text{:=}}$ $f\left( {x}_{i}\right) - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = f\left( {x}_{i}\right) - \widehat{f}\left( {P}_{{x}_{i}}\right)$ 。则总噪声为 ${y}_{i} - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = {\zeta }_{i} + \Delta {f}_{{p}_{{x}_{i}}}$ 。我们可以给出主要结论，即在核函数计算不精确情况下的累积遗憾界，

Theorem 1. Let $\delta > 0,f \in {\mathcal{H}}_{k}$ ,and the corresponding $\parallel \widehat{f}{\parallel }_{\widehat{k}} \leq b,\mathop{\max }\limits_{{x \in \mathcal{X}}}\left| {f\left( x\right) }\right| = M$ . Suppose the observation noise ${\zeta }_{i} = {y}_{i} - f\left( {x}_{i}\right)$ is ${\sigma }_{\zeta }$ -sub-Gaussian,and thus with high probability $\left| {\zeta }_{i}\right| < A$ for some $A > 0$ . Assume that both $k$ and ${P}_{x}$ satisfy the conditions for $\Delta {f}_{{P}_{x}}$ to be ${\sigma }_{E}$ -sub-Gaussian, for a given ${\sigma }_{E} > 0$ . Then,under Assumption 1 with $\varepsilon > 0$ and corresponding ${e}_{\varepsilon }$ ,setting ${\sigma }^{2} = 1 + \frac{2}{n}$ , running Gaussian Process with acquisition function
定理 1。设 $\delta > 0,f \in {\mathcal{H}}_{k}$ ，其对应 $\parallel \widehat{f}{\parallel }_{\widehat{k}} \leq b,\mathop{\max }\limits_{{x \in \mathcal{X}}}\left| {f\left( x\right) }\right| = M$ 。假设观测噪声 ${\zeta }_{i} = {y}_{i} - f\left( {x}_{i}\right)$ 是 ${\sigma }_{\zeta }$ -次高斯的，因此以高概率 $\left| {\zeta }_{i}\right| < A$ 对某个 $A > 0$ 成立。假定 $k$ 和 ${P}_{x}$ 均满足使 $\Delta {f}_{{P}_{x}}$ 成为给定 ${\sigma }_{E} > 0$ 的 ${\sigma }_{E}$ -次高斯条件。则在 $\varepsilon > 0$ 的假设 1 及对应 ${e}_{\varepsilon }$ 下，设定 ${\sigma }^{2} = 1 + \frac{2}{n}$ ，运行采用获取函数的高斯过程

\widetilde{\alpha }\left( {x \mid {\mathcal{D}}_{n}}\right) = {\widetilde{\mu }}_{n}\left( {P}_{x}\right) + {\beta }_{n}{\widetilde{\sigma }}_{n}\left( {P}_{x}\right) \tag{15}

\text{where}{\beta }_{n} = \left( {b + \sqrt{{\sigma }_{E}^{2} + {\sigma }_{\zeta }^{2}}\sqrt{2\left( {{\widehat{\gamma }}_{n} + 1 - \ln \delta }\right) }}\right) \text{,}

we have that the uncertain-inputs cumulative regret satisfies:
不确定输入的累计遗憾度满足：

{\widetilde{R}}_{n} \in O\left( {\sqrt{n{\widehat{\gamma }}_{n}\left( {{\widehat{\gamma }}_{n} - \ln \delta }\right) } + {n}^{2}\sqrt{\left( {{\widehat{\gamma }}_{n} - \ln \delta }\right) {e}_{\varepsilon }} + {n}^{3}{e}_{\varepsilon }}\right) \tag{16}

with probability at least $1 - \delta - {n\varepsilon }$ . Here ${\widetilde{R}}_{n} = \mathop{\sum }\limits_{{t = 1}}^{n}{\widetilde{r}}_{t}$ ,and ${\widetilde{r}}_{t} = \mathop{\max }\limits_{{x \in \mathcal{X}}}{\mathbb{E}}_{{P}_{x}}\left\lbrack f\right\rbrack - {\mathbb{E}}_{{P}_{{x}_{t}}}\left\lbrack f\right\rbrack$
置信度不低于 $1 - \delta - {n\varepsilon }$ 。此处 ${\widetilde{R}}_{n} = \mathop{\sum }\limits_{{t = 1}}^{n}{\widetilde{r}}_{t}$ ，且 ${\widetilde{r}}_{t} = \mathop{\max }\limits_{{x \in \mathcal{X}}}{\mathbb{E}}_{{P}_{x}}\left\lbrack f\right\rbrack - {\mathbb{E}}_{{P}_{{x}_{t}}}\left\lbrack f\right\rbrack$

The proof of our main theorem 1 can be found in appendix B. 3
主定理 1 的证明详见附录 B.3

The assumption that ${\zeta }_{i}$ is ${\sigma }_{\zeta }$ -sub-Gaussian is standard in $\mathcal{{GP}}$ fields. The assumption that $\Delta {f}_{{P}_{x}}$ is ${\sigma }_{E}$ -sub-Gaussian can be met when ${P}_{x}$ is uniformly bounded or Gaussian,as stated in Proposition 3, [26]. Readers may check the definition of sub-Gaussian in appendix, Definition 1,
假设 ${\zeta }_{i}$ 服从 ${\sigma }_{\zeta }$ -次高斯分布是 $\mathcal{{GP}}$ 领域的标准假设。根据命题 3 和文献[26]所述，当 ${P}_{x}$ 具有一致有界性或服从高斯分布时， $\Delta {f}_{{P}_{x}}$ 服从 ${\sigma }_{E}$ -次高斯分布的假设即可成立。读者可查阅附录定义 1 中关于次高斯的定义。

To achieve an regret of order ${\widetilde{R}}_{n} \in O\left( {\sqrt{n}{\widehat{\gamma }}_{n}}\right)$ ,the same order as the exact Improved $\mathcal{{GP}}$ regret (23), and ensure this with high probability,we need to take $\varepsilon = O\left( {\delta /n}\right) ,{e}_{\varepsilon } = O\left( {{n}^{-\frac{5}{2}}{\widehat{\gamma }}_{n}\left( {{\widehat{\gamma }}_{n}^{-2} \land {n}^{-\frac{1}{2}}}\right) }\right)$ , and this requires a sample size $m$ of order $O\left( {{n}^{5}{\widehat{\gamma }}_{n}^{-2}\left( {{\widehat{\gamma }}_{n}^{4} \vee n}\right) \log \left( n\right) }\right)$ for MCMC approximation,or with a same sample size $m$ and a subsample size $h$ of order $O\left( {{n}^{\frac{5}{2} + \nu }{\widehat{\gamma }}_{n}^{-1 - \nu }\left( {{\widehat{\gamma }}_{n}^{2} \vee {n}^{\frac{1}{2}}}\right) }\right)$ for Nyström approximation with some $\nu > 0$ . Note that (16) only offers an upper bound for cumulative regret,in real applications the calculated regret may be much smaller than this bound, as the approximation error ${e}_{\epsilon }$ can be fairly small even with a few samples when the input noise is relatively weak.
为实现与精确改进 $\mathcal{{GP}}$ 遗憾(23)同阶的 ${\widetilde{R}}_{n} \in O\left( {\sqrt{n}{\widehat{\gamma }}_{n}}\right)$ 阶遗憾，并以高概率确保这一结果，我们需要选取 $\varepsilon = O\left( {\delta /n}\right) ,{e}_{\varepsilon } = O\left( {{n}^{-\frac{5}{2}}{\widehat{\gamma }}_{n}\left( {{\widehat{\gamma }}_{n}^{-2} \land {n}^{-\frac{1}{2}}}\right) }\right)$ 。这就要求马尔可夫链蒙特卡洛（MCMC）近似所需的样本量 $m$ 达到 $O\left( {{n}^{5}{\widehat{\gamma }}_{n}^{-2}\left( {{\widehat{\gamma }}_{n}^{4} \vee n}\right) \log \left( n\right) }\right)$ 阶，或在使用 Nyström 近似时保持相同样本量 $m$ 的同时，使子样本量 $h$ 达到 $O\left( {{n}^{\frac{5}{2} + \nu }{\widehat{\gamma }}_{n}^{-1 - \nu }\left( {{\widehat{\gamma }}_{n}^{2} \vee {n}^{\frac{1}{2}}}\right) }\right)$ 阶（其中 $\nu > 0$ 为某常数）。需注意，(16)式仅给出了累积遗憾的上界，实际应用中计算得到的遗憾可能远小于该上界——因为当输入噪声较弱时，即使采用少量样本，近似误差 ${e}_{\epsilon }$ 也可能相当小。

To analysis the exact order of ${\widehat{\gamma }}_{n}$ could be difficult,as it is influenced by the specific choice of embedding kernel $k$ and input uncertainty distributions ${P}_{{x}_{i}},{x}_{i} \in \mathcal{X}$ . Nevertheless,we can deduce the following result for a wide range of cases, showing that cumulative regret is sub-linear under mild conditions. One can check the proof in appendix B. 4
要精确分析 ${\widehat{\gamma }}_{n}$ 的阶数可能较为困难，因为这受到嵌入核函数 $k$ 和输入不确定性分布 ${P}_{{x}_{i}},{x}_{i} \in \mathcal{X}$ 具体选择的共同影响。不过对于大多数情况，我们可以推导出以下结论：在温和条件下，累积遗憾呈现次线性增长。具体证明可参见附录 B.4。

Theorem 2 (Bounding the Maximum information gain). Suppose $k$ is r-th differentiable with bounded derivatives and translation invariant,i.e., $k\left( {x,y}\right) = k\left( {x - y,0}\right)$ . Suppose the input uncertainty is i.i.d.,that is,the noised input density satisfies ${P}_{{x}_{i}}\left( x\right) = {P}_{0}\left( {x - {x}_{i}}\right) ,\forall {x}_{i} \in \mathcal{X}$ . Then if the space $\mathcal{X}$ is compact in ${\mathbb{R}}^{d}$ ,the maximum information gain ${\widehat{\gamma }}_{n}$ satisfies
定理 2（最大信息增益上界）。假设 $k$ 具有 r 阶有界导数且满足平移不变性，即 $k\left( {x,y}\right) = k\left( {x - y,0}\right)$ 。若输入不确定性服从独立同分布，即含噪输入密度满足 ${P}_{{x}_{i}}\left( x\right) = {P}_{0}\left( {x - {x}_{i}}\right) ,\forall {x}_{i} \in \mathcal{X}$ ，则当空间 $\mathcal{X}$ 在 ${\mathbb{R}}^{d}$ 上紧致时，最大信息增益 ${\widehat{\gamma }}_{n}$ 满足：

{\widehat{\gamma }}_{n} = O\left( {{n}^{\frac{d\left( {d + 1}\right) }{r + d\left( {d + 1}\right) }}\log \left( n\right) }\right) .

Thus,when $r > d\left( {d + 1}\right)$ ,the accumulate regret is sub-linear respect to $n$ ,with sufficiently small ${e}_{\varepsilon }$ .
因此当 $r > d\left( {d + 1}\right)$ 时，只要 ${e}_{\varepsilon }$ 足够小，累积遗憾相对于 $n$ 将保持次线性增长。

Figure 2: Modeling results under different types of input uncertainties.
图 2：不同类型输入不确定性下的建模结果。

5 Evaluation 5 评估

In this section, we first experimentally demonstrate AIRBO's ability to model uncertain inputs of arbitrary distributions, then validate the Nyström-based inference acceleration for GP posterior, followed by experiments on robust optimization of synthetic functions and real-world benchmark.
本节首先通过实验验证 AIRBO 对任意分布不确定输入的建模能力，随后检验基于 Nyström 方法的高斯过程后验推断加速效果，最后在合成函数和现实基准测试上进行鲁棒优化实验

5.1 Robust Surrogate 5.1 鲁棒代理模型

Modeling arbitrary uncertain inputs: We demonstrate MMDGP's capabilities by employing an RKHS function as the black-box function and randomly selecting 10 samples from its input domain. Various types of input randomness are introduced into the observation and produce training datasets of $\mathcal{D} = {\left\{ \left( {x}_{i},f\left( {x}_{i} + {\delta }_{i}\right) \right) \mid {\delta }_{i} \sim {P}_{{x}_{i}}\right\} }_{i = 1}^{10}$ with different ${P}_{x}$ configurations. Figure 2a and 2b compare the modeling results of a conventional GP and MMDGP under a Gaussian input uncertainty ${P}_{x} = \mathcal{N}\left( {0,{0.01}^{2}}\right)$ . We observe that the GP model appears to overfit the observed samples without recognizing the input uncertainty, whereas MMDGP properly incorporates the input randomness into its posterior.
对任意不确定输入的建模：我们通过采用 RKHS 函数作为黑盒函数，并从其输入域中随机选取 10 个样本，展示了 MMDGP 的建模能力。在观测中引入多种类型的输入随机性，生成具有不同 ${P}_{x}$ 配置的 $\mathcal{D} = {\left\{ \left( {x}_{i},f\left( {x}_{i} + {\delta }_{i}\right) \right) \mid {\delta }_{i} \sim {P}_{{x}_{i}}\right\} }_{i = 1}^{10}$ 训练数据集。图 2a 和 2b 比较了传统高斯过程与 MMDGP 在高斯输入不确定性 ${P}_{x} = \mathcal{N}\left( {0,{0.01}^{2}}\right)$ 下的建模结果。观察到传统 GP 模型似乎过度拟合观测样本而未能识别输入不确定性，而 MMDGP 则正确地将输入随机性纳入其后验分布。

To further examine our model's ability under complex input uncertainty, we design the input distribution to follow a beta distribution with input-dependent variance: ${P}_{x} =$ beta $(\alpha = {0.5},\beta =$ ${0.5},\sigma = {0.9}\left( {\sin {4\pi x} + 1}\right)$ ). The MMDGP posterior is shown in Figure 2c. As the input variance $\sigma$ changes along $x$ ,inputs from the left and right around a given location ${x}_{i}$ yield different MMD distances,resulting in an asymmetric posterior (e.g.,around $x = {0.05}$ and $x = {0.42}$ ). This suggests that MMDGP can precisely model the multimodality and asymmetry of the input uncertainty.
为深入检验模型在复杂输入不确定性下的能力，我们设计输入分布遵循具有输入相关方差的贝塔分布： ${P}_{x} =$ beta $(\alpha = {0.5},\beta =$ ${0.5},\sigma = {0.9}\left( {\sin {4\pi x} + 1}\right)$ ）。图 2c 展示了 MMDGP 的后验分布。当输入方差 $\sigma$ 沿 $x$ 变化时，给定位置 ${x}_{i}$ 左右两侧的输入会产生不同的 MMD 距离，从而形成非对称后验（例如在 $x = {0.05}$ 和 $x = {0.42}$ 附近）。这表明 MMDGP 能精确建模输入不确定性的多模态和非对称特性。

Moreover,we evaluated MMDGP using a step-changing Chi-squared distribution ${P}_{x} = {\chi }^{2}(g\left( x\right) ,\sigma =$ ${0.01})$ ,where $g\left( x\right) = {0.5}$ if $x \in \left\lbrack {0,{0.6}}\right\rbrack$ ,and $g\left( x\right) = {7.0}$ otherwise. This abrupt change in $g\left( x\right)$ significantly alters the input distribution from a sharply peaked distribution to a flat one with a long tail. Figure 2d illustrates that our model can accurately capture this distribution shape variation, as evidenced by the sudden posterior change around $x = {0.6}$ . This demonstrates our model can thoroughly quantify the characteristics of complex input uncertainties.
此外，我们采用阶跃变化的卡方分布 ${P}_{x} = {\chi }^{2}(g\left( x\right) ,\sigma =$ ${0.01})$ 对 MMDGP 进行了评估，其中当 $x \in \left\lbrack {0,{0.6}}\right\rbrack$ 时 $g\left( x\right) = {0.5}$ ，否则 $g\left( x\right) = {7.0}$ 。这种 $g\left( x\right)$ 的突变使输入分布从尖锐峰值分布显著转变为具有长尾的平坦分布。图 2d 显示我们的模型能准确捕捉这种分布形态变化， $x = {0.6}$ 附近后验概率的突变即为明证。这表明我们的模型能全面量化复杂输入不确定性的特征。

Comparing with the other surrogate models: We also compare our model with the other surrogate models under the step-changing Chi-squared input distribution. The results are reported in Figure 7 and they demonstrate our model outperforms obviously under such a complex input uncertainty (see Appendix D. 1 for more details)
与其他代理模型对比：我们还在阶跃变化卡方输入分布下将本模型与其他代理模型进行对比。结果如图 7 所示，表明在此类复杂输入不确定性条件下本模型具有明显优势（详见附录 D.1）。

5.2 Accelerating the Posterior Inference
5.2 加速后验推断

Estimation variance of MMD: We first examine the variance of MMD estimation by employing two beta distributions $P = \operatorname{beta}\left( {\alpha = {0.4},\beta = {0.2},\sigma = {0.1}}\right)$ and $Q = \operatorname{beta}(\alpha = {0.4},\beta = {0.2},\sigma =$ 0.1) $+ c$ ,where $c$ is an offset value. Figure 3a shows the empirical MMDs computed via Eq. 8 with varying sampling sizes as $Q$ moves away from $P$ . We find that a sampling size of 20 is inadequate, leading to high estimation variance, and increasing the sampling size to 100 stabilizes the estimation
MMD 估计方差分析：我们首先通过采用两个贝塔分布 $P = \operatorname{beta}\left( {\alpha = {0.4},\beta = {0.2},\sigma = {0.1}}\right)$ 和 $Q = \operatorname{beta}(\alpha = {0.4},\beta = {0.2},\sigma =$ （0.1） $+ c$ 来检验 MMD 估计的方差，其中 $c$ 为偏移量。图 3a 展示了根据公式 8 计算的经验 MMD 值，随着 $Q$ 逐渐远离 $P$ 时不同采样规模下的变化情况。研究发现，20 的采样规模会导致较高的估计方差，而将采样规模提升至 100 则能稳定估计结果

We further utilize this beta distribution $P$ as the input distribution and derive the MMDGP posterior via empirical estimator in Figure 3b. Note that the MMD instability caused by inadequate sampling subsequently engenders a fluctuating posterior and culminates in a noisy acquisition function, which prevents the acquisition optimizer (e.g., L-BFGS-B in this experiment) from identifying the optima Although Figure 3c shows that this issue can be mitigated by using more samples during empirical
我们进一步利用这个β分布 $P$ 作为输入分布，并通过图 3b 中的经验估计器推导出 MMDGP 后验分布。需要注意的是，采样不足导致的 MMD 不稳定性会引发后验分布波动，最终形成噪声较大的采集函数，这使得采集优化器（本实验中采用 L-BFGS-B）难以定位最优解。尽管图 3c 表明，通过增加经验采样数量可以缓解该问题

Figure 3: The posterior derived from the empirical and Nyström MMD approximators with varying sampling sizes.
图 3：采用不同采样规模时，经验 MMD 近似器与尼斯特罗姆 MMD 近似器得到的后验对比。

Table 1: Performance of Posterior inference for 512 samples.
表 1：512 个样本的后验推断性能

$Method$	Sampling Size 采样量	Sub-sampling Size 子采样量	Inference Time (seconds) 推断时间（秒）	Batch Size (samples) 批量大小（样本数）
Empirical 经验值	20	-	$1.143 \pm 0.083$	512
Empirical 经验值	100	-	$8.117 \pm 0.040$	128
Empirical 经验值	1000	-	$840.715 \pm 2.182$	1
Nystrom	100	10	$0.780 \pm 0.001$	512
Nystrom 尼斯特罗姆法	1000	100	$21.473 \pm 0.984$	128

MMD estimation, it is crucial to note that a larger sampling size significantly increases GPU memory usage because of its quadratic space complexity of $O\left( {{MN}{m}^{2}}\right) (M$ and $N$ are the sample number of training and testing, $m$ is the sampling size for MMD estimation). This limitation severely hinders parallel inference for multiple samples and slows the overall speed of posterior computation.
在 MMD 估计中必须注意，较大的采样规模会显著增加 GPU 内存占用，因其空间复杂度与训练样本数 $O\left( {{MN}{m}^{2}}\right) (M$ 、测试样本数 $N$ 的平方成正比（ $m$ 为 MMD 估计的采样规模）。这一限制严重阻碍了多样本的并行推断，拖慢了后验计算的整体速度。

Table 1 summarizes the inference time of MMDGP posteriors at 512 samples with different sampling sizes. We find that, for beta distribution defined in this experiment, the Nyström MMD estimator with a sampling size of 100 and sub-sampling size of 10 already delivers a comparable result to the empirical estimator with 100 samples (as seen in the acquisition plot of Figure 3d). Also, the inference time is reduced from 8.117 to 0.78 seconds by enabling parallel computation for more samples. For the cases that require much more samples for MMD estimation (e.g., the input distribution is quite complex or high-dimensional), this Nyström-based acceleration can have a more pronounced impact.
表 1 总结了 512 个样本在不同采样规模下 MMDGP 后验的推断时间。我们发现，对于本实验定义的 beta 分布，采用 100 采样规模和 10 子采样规模的尼斯特罗姆 MMD 估计器，已能达到与 100 样本经验估计器相当的效果（见图 3d 的采集曲线）。同时通过启用更多样本的并行计算，推断时间从 8.117 秒缩短至 0.78 秒。对于需要更多 MMD 估计样本的情况（如输入分布非常复杂或高维时），这种基于尼斯特罗姆法的加速将产生更显著的效果。

Effect of Nyström estimator on optimization: To investigate the effect of Nyström estimator on optimization, we also perform an ablation study in Appendix D.2, the results in Figure 8 suggest that Nyström estimator slightly degrades the optimization performance but greatly improves the inference efficiency.
Nyström 估计器对优化的影响：为研究 Nyström 估计器对优化的影响，我们在附录 D.2 进行了消融实验。图 8 结果显示，Nyström 估计器虽轻微降低优化性能，但显著提升了推理效率。

5.3 Robust Optimization 5.3 鲁棒优化

Experiment setup: To experimentally validate AIRBO’s performance,we implement our algorithm ${}^{1}$ based on BoTorch [2] and employ a linear combination of multiple rational quadratic kernels [6] to compute the MMD as Eq. 9. We compare our algorithm with several baselines: 1) uGP-UCB [26] is a closely related work that employs an integral kernel to model the various input distributions. It has a quadratic inference complexity of $O\left( {{MN}{m}^{2}}\right)$ ,where $M$ and $N$ are the sample numbers of the training and testing set,and $m$ indicates the sampling size of the integral kernel. 3)GP-UCB is the standard GP with UCB acquisition, which represents a broad range of existing methods that
实验设置：为验证 AIRBO 性能，我们基于 BoTorch[2]实现算法 ${}^{1}$ ，采用多个有理二次核[6]的线性组合计算 MMD（如公式 9 所示）。对比基线包括：1) uGP-UCB[26]采用积分核建模不同输入分布，其推理复杂度为二次方 $O\left( {{MN}{m}^{2}}\right)$ （其中 $M$ 和 $N$ 分别为训练集与测试集样本数， $m$ 表示积分核采样规模）；3) GP-UCB 是采用 UCB 采集函数的标准高斯过程，代表现有广泛方法

${}^{1}$ The code will be available on https://github.com/huawei-noah/HEBO and more implementation details can be found in Appendix C. 1
${}^{1}$ 代码将在 https://github.com/huawei-noah/HEBO 上公开，更多实现细节详见附录 C.1

Figure 4: Robust optimization results on synthetic functions.
图 4：合成函数上的鲁棒优化结果

focus on non-robust optimization. 3) SKL-UCB employs symmetric Kullback-Leibler divergence to measure the distance between the uncertain inputs [20]. Its closed-form solution only exists if the input distributions are the Gaussians. 4) ERBF-UCB is the robust GP with the expected Radial Basis Function kernel proposed in [13]. It computes the expected kernel under input distribution using the Gaussian integrals. Assuming the input distributions are sub-Gaussians, this method can efficiently find the robust optimum. Since all the methods use UCB acquisition, we simply distinguish them by their surrogate names in the following tests.
专注于非鲁棒优化。3) SKL-UCB 采用对称 Kullback-Leibler 散度衡量不确定输入间的距离[20]，其闭式解仅当输入分布为高斯分布时存在。4) ERBF-UCB 是文献[13]提出的采用期望径向基函数核的鲁棒高斯过程，通过高斯积分计算输入分布下的期望核函数。该方法在假设输入分布为次高斯分布时，能高效找到鲁棒最优解。由于所有方法均采用 UCB 采集函数，后续测试中我们直接以其代理模型名称进行区分。

At the end of the optimization,each algorithm needs to decide a final outcome ${x}_{n}^{r}$ ,perceived to be the robust optimum under input uncertainty at step $n$ . For a fair comparison,we employ the same outcome policy across all the algorithms: ${x}_{n}^{r} = \arg \mathop{\max }\limits_{{x \in {\mathcal{D}}_{n}}}{\widehat{\mu }}_{ * }\left( x\right)$ ,where ${\widehat{\mu }}_{ * }\left( x\right)$ is the posterior mean of robust surrogate at $x$ and ${\mathcal{D}}_{n} = \left\{ {\left( {{x}_{i},f\left( {{x}_{i} + {\delta }_{i}}\right) }\right) \mid {\delta }_{i} \sim {P}_{{x}_{i}}}\right\}$ are the observations so far. The optimization performance is measured in terms of robust regret as follows:
在优化过程结束时，每个算法都需要确定一个最终输出结果 ${x}_{n}^{r}$ ，该结果被视为步骤 $n$ 时输入不确定性下的鲁棒最优解。为确保公平比较，我们在所有算法中采用相同的输出策略： ${x}_{n}^{r} = \arg \mathop{\max }\limits_{{x \in {\mathcal{D}}_{n}}}{\widehat{\mu }}_{ * }\left( x\right)$ ，其中 ${\widehat{\mu }}_{ * }\left( x\right)$ 是鲁棒代理模型在 $x$ 处的后验均值， ${\mathcal{D}}_{n} = \left\{ {\left( {{x}_{i},f\left( {{x}_{i} + {\delta }_{i}}\right) }\right) \mid {\delta }_{i} \sim {P}_{{x}_{i}}}\right\}$ 表示迄今为止的观测数据。优化性能通过以下鲁棒遗憾度进行衡量：

r\left( {x}_{n}^{r}\right) = {\mathbb{E}}_{\delta \sim {P}_{{x}^{ * }}}\left\lbrack {f\left( {{x}^{ * } + \delta }\right) }\right\rbrack - {\mathbb{E}}_{\delta \sim {P}_{{x}_{n}^{r}}}\left\lbrack {f\left( {{x}_{n}^{r} + \delta }\right) }\right\rbrack , \tag{17}

where ${x}^{ * }$ is the global robust optimum and ${x}_{n}^{r}$ represents the outcome point at step $n$ . For each algorithm, we repeat the optimization process 12 times and compare the average robust regret.
其中 ${x}^{ * }$ 表示全局鲁棒最优解， ${x}_{n}^{r}$ 代表步骤 $n$ 时的输出点。针对每个算法，我们重复优化过程 12 次并比较平均鲁棒遗憾度。

1D RKHS function: We begin the optimization evaluation with an RKHS function that is widely used in previous BO works [1,24,10]. Figure 4a shows its exact global optimum resides at $x = {0.892}$ while the robust optimum is around $x = {0.08}$ when the inputs follow a Gaussian distribution $\mathcal{N}\left( {0,{0.01}^{2}}\right)$ . According to Figure 4b,all the robust BO methods work well with Gaussian uncertain inputs and efficiently identify the robust optimum, but the GP-UCB stagnates at a local optimum due to its neglect of input uncertainty. Also, we notice the regret of our method decrease slightly slower than uGP works in this low-dimensional and Gaussian-input case, but later cases with higher dimension and more complex distribution show our method is more stable and efficient.
一维 RKHS 函数：我们首先采用先前贝叶斯优化研究中广泛使用的 RKHS 函数进行优化评估[1,24,10]。图 4a 显示当输入服从高斯分布 $\mathcal{N}\left( {0,{0.01}^{2}}\right)$ 时，其精确全局最优解位于 $x = {0.892}$ ，而鲁棒最优解约在 $x = {0.08}$ 位置。根据图 4b 所示，所有鲁棒贝叶斯优化方法在高斯不确定输入下表现良好，均能有效识别鲁棒最优解，但 GP-UCB 因忽略输入不确定性而陷入局部最优。值得注意的是，在这个低维高斯输入案例中，本方法的遗憾值下降速度略慢于 uGP 方法，但在后续更高维度及更复杂分布的场景中，本方法展现出更优的稳定性和效率。

1D double-peak function: To test with more complex input uncertainty, we design a blackbox function with double peaks and set the input distribution to be a multi-modal distribution ${P}_{x} =$ beta $\left( {\alpha = {0.4},\beta = {0.2},\sigma = {0.1}}\right)$ . Figure 4c shows the blackbox function (black solid line) and the corresponding function expectations estimated numerically via sampling from the input distribution (i.e.,the colored lines). Note the true robust optimum is around $x = {0.251}$ under the beta distribution, but an erroneous location at $x = {0.352}$ may be determined if the input uncertainty is incorrectly presumed to be Gaussian. This explains the results in Figure 4d, the performance of SKL-UCB and ERBF-UCB are sub-optimal due to their misidentification of inputs as Gaussian variables, while our method accurately quantifies the input uncertainty and outperforms the others.
一维双峰函数：为测试更复杂的输入不确定性，我们设计了一个具有双峰的黑箱函数，并将输入分布设定为多模态的 beta 分布。图 4c 展示了该黑箱函数（黑色实线）以及通过输入分布采样数值估算得到的对应函数期望值（即彩色线条）。需注意在 beta 分布下真实的稳健最优解位于 $x = {0.251}$ 附近，但若错误假设输入不确定性为高斯分布，则可能误判最优解位于 $x = {0.352}$ 。这解释了图 4d 所示结果——由于 SKL-UCB 和 ERBF-UCB 错误地将输入识别为高斯变量，其表现欠佳；而我们的方法能准确量化输入不确定性，性能优于其他方法。

10D bumped-bowl function: we also extend our evaluation to a 10D bumped-bowl function [27] under a concatenated circular distribution. Figure 9 demonstrates AIRBO scales efficiently to high dimension and outperforms the others under complex input uncertainty(see Appendix D.3).
十维凸底隆起函数：我们还将评估扩展至拼接环形分布下的十维凸底隆起函数[27]。图 9 表明 AIRBO 能高效扩展至高维空间，在复杂输入不确定性条件下表现优于其他方法（详见附录 D.3）。

Robust robot pushing: To evaluate AIRBO in a real-world problem, we employ a robust robot pushing benchmark from [31], in which a ball is placed at the origin point of a 2D space and a robot learns to push it to a predefined target location $\left( {{g}_{x},{g}_{y}}\right)$ . This benchmark takes a 3-dimensional input $\left( {{r}_{x},{r}_{y},{r}_{t}}\right)$ ,where ${r}_{x},{r}_{y} \in \left\lbrack {-5, + 5}\right\rbrack$ are the $2\mathrm{D}$ coordinates of the initial robot location and ${r}_{t} \in \left\lbrack {0,{30}}\right\rbrack$ controls the push duration. We set four targets in separate quadrants,i.e., ${g1} =$ $\left( {-3, - 3}\right) ,{g}_{2} = \left( {-3,3}\right) ,{g}_{3} = \left( {{4.3},{4.3}}\right)$ ,and a "twin" target at ${g}_{3}^{\prime } = \left( {{5.1},{3.0}}\right)$ ,and describe the input uncertainty via a two-component Gaussian Mixture Model (defined in Appendix D.4). Following [7 10], this blackbox benchmark outputs the minimum distance to these 4 targets under squared and linear distances: $\operatorname{loss} = \min \left( {{d}^{2}\left( {{g}_{1},l}\right) ,d\left( {{g}_{2},l}\right) ,d\left( {{g}_{3},l}\right) ,d\left( {{g}_{3}^{\prime },l}\right) }\right)$ ,where $d\left( {{g}_{i},l}\right)$ is the Euclidean distance between the ball’s ending location $l$ and the $i$ -th target. This produces a loss landscape as shown in Figure 5a. Note that ${g}_{2}$ is a more robust target than ${g}_{1}$ because of its linear-form distance while pushing the ball to quadrant I is the best choice as the targets, ${g}_{3}$ and ${g}_{3}^{\prime }$ ,match the dual-mode pattern of the input uncertainty. According to Figure 5b, our method obviously outperforms the others because it efficiently quantifies the multimodal input uncertainty. This can be further evidenced by the push configurations found by different algorithms in Figure 6, in which each dot represents the robot's initial location and its color represents the push duration. We find that AIRBO successfully recognizes the targets in quadrant I as an optimal choice and frequently pushes from quadrant III to quadrant I. Moreover, the pushes started close to the origin can easily go far away under input variation, so our method learns to push the ball from a corner with a long push duration, which is more robust in this case.
鲁棒机器人推球任务：为评估 AIRBO 在现实问题中的表现，我们采用[31]提出的鲁棒机器人推球基准测试。该测试将小球置于二维空间原点，机器人学习将其推至预设目标位置 $\left( {{g}_{x},{g}_{y}}\right)$ 。基准测试采用三维输入 $\left( {{r}_{x},{r}_{y},{r}_{t}}\right)$ ，其中 ${r}_{x},{r}_{y} \in \left\lbrack {-5, + 5}\right\rbrack$ 表示机器人初始位置的 $2\mathrm{D}$ 坐标， ${r}_{t} \in \left\lbrack {0,{30}}\right\rbrack$ 控制推动持续时间。我们在四个象限分别设置目标点 ${g1} =$ $\left( {-3, - 3}\right) ,{g}_{2} = \left( {-3,3}\right) ,{g}_{3} = \left( {{4.3},{4.3}}\right)$ ，并在 ${g}_{3}^{\prime } = \left( {{5.1},{3.0}}\right)$ 位置设置"孪生"目标点，通过双组分高斯混合模型（定义见附录 D.4）描述输入不确定性。参照[7 10]，该黑箱基准测试输出小球在平方距离和线性距离下与这 4 个目标点的最小距离： $\operatorname{loss} = \min \left( {{d}^{2}\left( {{g}_{1},l}\right) ,d\left( {{g}_{2},l}\right) ,d\left( {{g}_{3},l}\right) ,d\left( {{g}_{3}^{\prime },l}\right) }\right)$ ，其中 $d\left( {{g}_{i},l}\right)$ 表示小球终点位置 $l$ 与第 $i$ 个目标点的欧氏距离。由此产生的损失景观如图 5a 所示。值得注意的是，由于采用线性距离形式， ${g}_{2}$ 是比 ${g}_{1}$ 更鲁棒的目标；而将球推至第一象限是最佳选择，因为目标点 ${g}_{3}$ 和 ${g}_{3}^{\prime }$ 与输入不确定性的双峰模式相匹配。根据图 5b 所示，我们的方法明显优于其他方法，因为它能有效量化多模态输入的不确定性。图 6 中不同算法发现的推动配置进一步佐证了这一点——图中每个圆点代表机器人的初始位置，颜色深浅代表推动持续时间。我们发现 AIRBO 成功识别出第一象限目标作为最优选择，并频繁从第三象限向第一象限实施推动。此外，靠近原点发起的推动在输入变异下容易偏离目标，因此我们的方法学会从角落位置实施长时间推动，这种策略在本案例中展现出更强的鲁棒性。

Figure 6: The robot's initial locations and push times found by different algorithms
图 6：不同算法发现的机器人初始位置与推动时长

6 Discussion and Conclusion
6 讨论与结论

In this work, we generalize robust Bayesian Optimization to an uncertain input setting. The weight-space interpretation of GP inspires us to empower the GP kernel with MMD and build a robust surrogate for uncertain inputs of arbitrary distributions. We also employ the Nyström approximation to boost the posterior inference and provide theoretical regret bound under approximation error. The experiments on synthetic blackbox function and benchmarks demonstrate our method can handle various input uncertainty and achieve state-of-the-art optimization performance.
本研究将鲁棒贝叶斯优化推广至不确定输入场景。高斯过程的权重空间解释启发我们通过最大平均差异(MMD)增强 GP 核函数，构建适用于任意分布不确定输入的鲁棒代理模型。我们采用 Nyström 近似加速后验推理，并在近似误差下提供理论遗憾界。针对合成黑箱函数与基准测试的实验表明，本方法能处理多种输入不确定性，并实现最先进的优化性能。

There are several interesting directions that worth to explore: though we come to current MMD-based kernel from the weight-space interpretation of GP and the RKHS realization of MMD, our kernel design exhibits a deep connection with existing works on kernel over probability measures [22, 11] Along this direction, as our theoretic regret analysis in Section 4 does not assume any particular form of kernel and the Nyström acceleration can also be extended to the other kernel computation, it is possible that AIRBO can be further generalized to a more rich family of kernels. Moreover, the MMD used in our kernel is by no means limited to its RKHS realization. In fact,any function class $\mathcal{F}$ that comes with uniform convergence guarantees and is sufficiently rich can be used, which renders different realizations of MMD. With proper choice of function class $\mathcal{F}$ ,MMD can be expressed as the Kolmogorov metric or other Earth-mover distances [15]. It is also interesting to extend AIRBO with the other IPMs.
有几个值得探索的有趣方向：虽然我们当前基于 MMD 的核函数源自 GP 的权重空间解释和 MMD 的 RKHS 实现，但我们的核设计与现有关于概率测度核函数的研究[22,11]存在深刻联系。沿着这个方向，由于第 4 节的理论遗憾分析并未假设任何特定核形式，且 Nyström 加速也可推广至其他核计算，AIRBO 有可能进一步推广到更丰富的核函数族。此外，我们核中使用的 MMD 绝不限于其 RKHS 实现——实际上任何具有一致收敛保证且足够丰富的函数类 $\mathcal{F}$ 都可使用，这将产生不同的 MMD 实现。通过恰当选择函数类 $\mathcal{F}$ ，MMD 可表达为 Kolmogorov 度量或其他推土机距离[15]。将 AIRBO 扩展至其他积分概率度量也颇具研究价值。

7 Acknowledgements 7 致谢

We sincerely thank Yanbin Zhu and Ke Ma for their help on formulating the problem. Also, a heartfelt appreciation goes to Lu Kang for her constant encouragement and support throughout this work. References
我们衷心感谢严斌朱和马柯在问题建模方面给予的帮助。同时，特别感谢康璐在整个研究过程中持续的鼓励与支持。参考文献

[1] John-Alexander M Assael et al. "Heteroscedastic treed bayesian optimisation". In: arXiv preprint arXiv:1410.7172 (2014).
[1] John-Alexander M Assael 等. "异方差树贝叶斯优化". 见于: arXiv 预印本 arXiv:1410.7172 (2014).

[2] Maximilian Balandat et al. "BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization". In: Advances in Neural Information Processing Systems 33. 2020. URL: http: //arxiv.org/abs/1910.06403
[2] Maximilian Balandat 等. "BoTorch: 高效蒙特卡洛贝叶斯优化框架". 见于: 神经信息处理系统进展 33. 2020. 网址: http://arxiv.org/abs/1910.06403

[3] Justin J Beland and Prasanth B Nair. "Bayesian Optimization Under Uncertainty". In: Advances in neural information processing systems (2017), p. 5.
[3] Justin J Beland 与 Prasanth B Nair. "不确定性条件下的贝叶斯优化". 见于: 神经信息处理系统进展 (2017), 第 5 页.

[4] James Bergstra et al. "Algorithms for hyper-parameter optimization". In: Advances in neural information processing systems 24 (2011).
[4] James Bergstra 等.《超参数优化算法》. 见: 神经信息处理系统进展 24 (2011).

[5] Felix Berkenkamp, Andreas Krause, and Angela P Schoellig. "Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics". In: Machine Learning (2021), pp. 1-35.
[5] Felix Berkenkamp, Andreas Krause 与 Angela P Schoellig.《带安全约束的贝叶斯优化：机器人学中安全自动的参数调谐》. 见: 机器学习 (2021), 第 1-35 页.

[6] Mikołaj Bińkowski et al. Demystifying MMD GANs. 2021. DOI: 10.48550/arXiv. 1801 01401. arXiv: 1801.01401
[6] Mikołaj Bińkowski 等.《揭秘 MMD 生成对抗网络》. 2021. DOI: 10.48550/arXiv.1801.01401. arXiv: 1801.01401

[7] Ilija Bogunovic et al. "Adversarially Robust Optimization with Gaussian Processes". In: Advances in Neural Information Processing Systems. Vol. 31. Curran Associates, Inc., 2018.
[7] Ilija Bogunovic 等.《基于高斯过程的对抗鲁棒优化》. 见: 神经信息处理系统进展. 第 31 卷. Curran Associates 公司, 2018.

[8] Antoine Chatalic et al. "Nyström Kernel Mean Embeddings". In: International Conference on Machine Learning. 2022.
[8] Antoine Chatalic 等. "Nyström 核均值嵌入". 见: 国际机器学习大会. 2022.

[9] Sayak Ray Chowdhury and Aditya Gopalan. "On Kernelized Multi-armed Bandits". In: International Conference on Machine Learning. 2017.
[9] Sayak Ray Chowdhury 与 Aditya Gopalan. "核化多臂老虎机研究". 见: 国际机器学习大会. 2017.

[10] Ryan B. Christianson and Robert B. Gramacy. Robust Expected Improvement for Bayesian Optimization. 2023. arXiv: 2302.08612
[10] Ryan B. Christianson 与 Robert B. Gramacy. 贝叶斯优化的鲁棒期望改进方法. 2023. arXiv 预印本: 2302.08612

[11] Andreas Christmann and Ingo Steinwart. "Universal Kernels on Non-Standard Input Spaces". In: NIPS. 2010. URL: https://api.semanticscholar.org/CorpusID:16968759
[11] Andreas Christmann 和 Ingo Steinwart. "非标准输入空间的通用核函数". 见: 神经信息处理系统会议. 2010. 网址: https://api.semanticscholar.org/CorpusID:16968759

[12] Alexander I Cowen-Rivers et al. "HEBO: pushing the limits of sample-efficient hyper-parameter optimisation". In: Journal of Artificial Intelligence Research 74 (2022), pp. 1269- 1349.
[12] 亚历山大·I·考恩-里弗斯等。"HEBO：突破高效超参数优化的样本效率极限"。见：《人工智能研究杂志》74 卷（2022 年），第 1269-1349 页。

[13] Patrick Dallaire, Camille Besse, and Brahim Chaib-draa. "An Approximate Inference with Gaussian Process to Latent Functions from Uncertain Data". In: Neurocomputing. Adaptive Incremental Learning in Neural Networks 74.11 (2011), pp. 1945-1955. DOI: 10.1016/j neucom.2010.09.024
[13] 帕特里克·达莱尔、卡米耶·贝斯与布拉希姆·柴卜-德拉。"基于高斯过程的隐函数近似推理方法处理不确定数据"。见：《神经计算：神经网络的自适应增量学习》74 卷 11 期（2011 年），第 1945-1955 页。DOI：10.1016/j.neucom.2010.09.024

[14] Arthur Gretton, Dougal Sutherland, and Wittawat Jitkrittum. "Interpretable comparison of distributions and models". In: Advances in Neural Information Processing Systems [Tutorial] (2019).
[14] 亚瑟·格雷顿、杜格尔·萨瑟兰与威塔瓦·吉克里通。"分布与模型的可解释性比较"。见：《神经信息处理系统进展》[教程]（2019 年）。

[15] Arthur Gretton et al. "A kernel two-sample test". In: The Journal of Machine Learning Research 13.1 (2012), pp. 723-773.
[15] 亚瑟·格雷顿等。"核双样本检验"。见：《机器学习研究杂志》13 卷 1 期（2012 年），第 723-773 页。

[16] Trevor Hastie et al. The elements of statistical learning: data mining, inference, and prediction. Vol. 2. Springer, 2009.
[16] 特雷弗·哈斯蒂等。《统计学习基础：数据挖掘、推断与预测》。第 2 卷。施普林格出版社，2009 年。

[17] Thomas Kühn. "Eigenvalues of integral operators with smooth positive definite kernels". In: Archiv der Mathematik 49 (1987), pp. 525-534. URL: https://api.semanticscholar org/CorpusID:121372638
[17] 托马斯·库恩。"具有光滑正定核的积分算子特征值"。发表于：《数学档案》49 卷（1987 年），第 525-534 页。URL：https://api.semanticscholar org/CorpusID:121372638

[18] Ruben Martinez-Cantin et al. "Active policy learning for robot planning and exploration under uncertainty." In: Robotics: Science and systems. Vol. 3. 2007, pp. 321-328.
[18] 鲁本·马丁内斯-坎廷等。"不确定性下机器人规划与探索的主动策略学习"。发表于：《机器人学：科学与系统》第 3 卷。2007 年，第 321-328 页。

[19] Seyedali Mirjalili and Andrew Lewis. "Obstacles and difficulties for robust benchmark problems: A novel penalty-based robust optimisation method". In: Information Sciences 328 (2016), pp. 485-509.
[19] 赛义德阿里·米尔贾利利与安德鲁·刘易斯。"鲁棒基准问题的障碍与难点：一种新型基于惩罚的鲁棒优化方法"。发表于：《信息科学》328 卷（2016 年），第 485-509 页。

[20] Pedro Moreno, Purdy Ho, and Nuno Vasconcelos. "A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications". In: Advances in Neural Information Processing Systems. Vol. 16. MIT Press, 2003.
[20] 佩德罗·莫雷诺、珀迪·何与努诺·瓦斯科塞洛斯。《基于 Kullback-Leibler 散度的 SVM 分类核函数及其在多媒体应用中的应用》。发表于：《神经信息处理系统进展》第 16 卷。麻省理工学院出版社，2003 年。

[21] Krikamol Muandet et al. "Kernel Mean Embedding of Distributions: A Review and Beyond". In: Foundations and Trends® in Machine Learning 10.1-2 (2017), pp. 1-141. DOI: 10.1561/ 2200000060. arXiv: 1605.09522
[21] 克里卡莫尔·穆安迪特等。《分布核均值嵌入：综述与展望》。发表于：《机器学习基础与趋势》10.1-2（2017 年），第 1-141 页。DOI：10.1561/2200000060。预印本：arXiv:1605.09522。

[22] Krikamol Muandet et al. "Learning from Distributions via Support Measure Machines". In: NIPS. 2012.
[22] 克里卡莫尔·穆安迪特等。《通过支持测度机从分布中学习》。发表于：《神经信息处理系统大会》。2012 年。

[23] Alfred Müller. "Integral probability metrics and their generating classes of functions". In: Advances in applied probability 29.2 (1997), pp. 429-443.
[23] 阿尔弗雷德·穆勒。《积分概率度量及其生成函数类》。发表于：《应用概率进展》29.2（1997 年），第 429-443 页。

[24] Jose Nogueira et al. "Unscented Bayesian Optimization for Safe Robot Grasping". In: 2016 IEEE/RSJ Ineternational Conference on Intelligent Robots and Systems (IROS). Daejeon, South Korea: IEEE, 2016, pp. 1967-1972. ISBN: 978-1-5090-3762-9. DOI: 10.1109/IROS. 2016. 7759310
[24] Jose Nogueira 等.《基于无迹变换贝叶斯优化的机器人安全抓取》.见:2016 年 IEEE/RSJ 智能机器人与系统国际会议(IROS).韩国大田:IEEE,2016 年,第 1967-1972 页.ISBN:978-1-5090-3762-9.DOI:10.1109/IROS.2016.7759310

[25] Rafael Oliveira, Lionel Ott, and Fabio Ramos. "Bayesian Optimisation under Uncertain Inputs". In: Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 1177-1184.
[25] Rafael Oliveira,Lionel Ott 和 Fabio Ramos.《不确定输入下的贝叶斯优化》.见:第二十二届人工智能与统计国际会议论文集.PMLR,2019 年,第 1177-1184 页.

[26] Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs. 2019. arXiv: 1902.07908.
[26] Rafael Oliveira,Lionel Ott 和 Fabio Ramos.不确定输入下的贝叶斯优化.2019 年.arXiv:1902.07908.

[27] Nicholas D. Sanders et al. Bayesian Search for Robust Optima. 2021. arXiv: 1904.11416
[27] Nicholas D. Sanders 等.鲁棒最优解的贝叶斯搜索.2021 年.arXiv:1904.11416

[28] Bobak Shahriari et al. "Taking the Human Out of the Loop: A Review of Bayesian Optimization". In: Proceedings of the IEEE 104.1 (Jan. 2016), pp. 148-175. DOI: 10.1109/JPROC 2015.2494218
[28] Bobak Shahriari 等."将人类移出循环：贝叶斯优化方法综述".见：《IEEE 会刊》104 卷 1 期(2016 年 1 月)，第 148-175 页.DOI：10.1109/JPROC 2015.2494218

[29] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. "Practical bayesian optimization of machine learning algorithms". In: Advances in neural information processing systems 25 (2012).
[29] Jasper Snoek, Hugo Larochelle 与 Ryan P Adams."机器学习算法的实用贝叶斯优化".见：《神经信息处理系统进展》第 25 卷(2012 年).

[30] Niranjan Srinivas et al. "Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design". In: International Conference on Machine Learning. 2009. URL: https://api.semanticscholar.org/CorpusID:59031327
[30] Niranjan Srinivas 等."多臂老虎机设置下的高斯过程优化：无遗憾与实验设计".见：国际机器学习大会.2009 年.URL：https://api.semanticscholar.org/CorpusID:59031327

[31] Zi Wang and Stefanie Jegelka. "Max-value entropy search for efficient Bayesian optimization". In: International Conference on Machine Learning. PMLR. 2017, pp. 3627-3635.
[31] Zi Wang 与 Stefanie Jegelka."基于最大价值熵搜索的高效贝叶斯优化".见：国际机器学习大会.PMLR 出版社.2017 年，第 3627-3635 页.

[32] Colin White, Willie Neiswanger, and Yash Savani. "Bananas: Bayesian optimization with neural architectures for neural architecture search". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. 12. 2021, pp. 10293-10301.
[32] 科林·怀特、威利·内斯旺格与雅什·萨瓦尼。《香蕉算法：基于神经架构贝叶斯优化的神经网络架构搜索》。见：AAAI 人工智能会议论文集。第 35 卷。第 12 期。2021 年，第 10293-10301 页。

[33] Christopher Williams and Matthias Seeger. "Using the Nyström Method to Speed Up Kernel Machines". In: Advances in Neural Information Processing Systems. Vol. 13. MIT Press, 2000.
[33] 克里斯托弗·威廉姆斯与马蒂亚斯·西格。《利用尼斯特伦方法加速核机器》。见：神经信息处理系统进展。第 13 卷。麻省理工学院出版社，2000 年。

[34] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. Vol. 2. 3. MIT press Cambridge, MA, 2006.
[34] 克里斯托弗·KI·威廉姆斯与卡尔·爱德华·拉斯穆森。《机器学习中的高斯过程》。第 2 卷。第 3 期。麻省理工学院出版社，剑桥，2006 年。

A Nyström Estimator Error Bound
尼斯特伦估计量误差界

Nyström estimator can easily approximate the kernel mean embedding ${\psi }_{{p}_{1}},{\psi }_{{p}_{2}}$ as well as the MMD distance between two distribution density ${p}_{1}$ and ${p}_{2}$ . We need first assume the boundedness of the feature map to the kernel $k$ :
Nyström 估计器可以轻松近似核均值嵌入 ${\psi }_{{p}_{1}},{\psi }_{{p}_{2}}$ 以及两个分布密度 ${p}_{1}$ 与 ${p}_{2}$ 之间的 MMD 距离。我们首先需要假设核函数 $k$ 的特征映射有界性：

Assumption 2. There exists a positive constant $K \leq \infty$ such that $\mathop{\sup }\limits_{{x \in \mathcal{X}}}\parallel \phi \left( x\right) \parallel \leq K$
假设 2. 存在正常数 $K \leq \infty$ 使得 $\mathop{\sup }\limits_{{x \in \mathcal{X}}}\parallel \phi \left( x\right) \parallel \leq K$

The true MMD distance between ${p}_{1}$ and ${p}_{2}$ is denoted as $\operatorname{MMD}\left( {{p}_{1},{p}_{2}}\right)$ . The estimated MMD distance when using a Nyström sample size ${m}_{i}$ ,sub-sample size ${h}_{i}$ for ${p}_{i}$ respectively,is denoted as ${\operatorname{MMD}}_{\left( {p}_{i},{m}_{i},{h}_{i}\right) }$ . Then the error
真实 MMD 距离在 ${p}_{1}$ 与 ${p}_{2}$ 之间记为 $\operatorname{MMD}\left( {{p}_{1},{p}_{2}}\right)$ 。当分别使用 Nyström 样本量 ${m}_{i}$ 、子样本量 ${h}_{i}$ 来估计 ${p}_{i}$ 时，其 MMD 距离估计值记为 ${\operatorname{MMD}}_{\left( {p}_{i},{m}_{i},{h}_{i}\right) }$ 。则误差

{\operatorname{Err}}_{\left( {p}_{i},{m}_{i},{h}_{i}\right) } \mathrel{\text{:=}} \left| {\operatorname{MMD}\left( {{p}_{1},{p}_{2}}\right) - {\operatorname{MMD}}_{\left( {p}_{i},{m}_{i},{h}_{i}\right) }}\right|

and now we have the lemma from Theorem 5.1 in [8]
根据文献[8]中定理 5.1 可得如下引理

Lemma 1. Let Assumption 2 hold. Furthermore,assume that for $i \in 1,2$ ,the data points ${X}_{1}^{i},\cdots ,{X}_{{m}_{i}}^{i}$ are drawn i.i.d. from the distribution ${\rho }_{i}$ and that ${h}_{i} \leq {m}_{i}$ sub-samples ${\widetilde{X}}_{1}^{i},\cdots ,{\widetilde{X}}_{{h}_{i}}^{i}$ are drawn uniformly with replacement from the dataset $\left\{ {{X}_{1}^{i},\cdots ,{X}_{{m}_{i}}^{i}}\right\}$ . Then,for any $\delta \in \left( {0,1}\right)$ ,it holds with probability at least $1 - {2\delta }$
引理 1. 设假设 2 成立。此外，假设对于 $i \in 1,2$ ，数据点 ${X}_{1}^{i},\cdots ,{X}_{{m}_{i}}^{i}$ 是从分布 ${\rho }_{i}$ 中独立同分布抽取的，且 ${h}_{i} \leq {m}_{i}$ 个子样本 ${\widetilde{X}}_{1}^{i},\cdots ,{\widetilde{X}}_{{h}_{i}}^{i}$ 是从数据集 $\left\{ {{X}_{1}^{i},\cdots ,{X}_{{m}_{i}}^{i}}\right\}$ 中有放回地均匀抽取的。那么对于任意 $\delta \in \left( {0,1}\right)$ ，以下结论以至少 $1 - {2\delta }$ 的概率成立：

{\operatorname{Err}}_{\left( {p}_{i},{m}_{i},{h}_{i}\right) } \leq \mathop{\sum }\limits_{{i = 1,2}}\left( {\frac{{c}_{1}}{\sqrt{{m}_{i}}} + \frac{{c}_{2}}{{h}_{i}} + \frac{\sqrt{\log \left( {{h}_{i}/\delta }\right) }}{{h}_{i}}\sqrt{{\mathcal{N}}^{{p}_{i}}\left( \frac{{12}{K}^{2}\log \left( {{h}_{i}/\delta }\right) }{{h}_{i}}\right) }}\right) ,

provided that,for $i \in \{ 1,2\}$ , 当且仅当对于 $i \in \{ 1,2\}$ ，

{h}_{i} \geq \max \left( {{67},{12}{K}^{2}{\begin{Vmatrix}{C}_{i}\end{Vmatrix}}_{\mathcal{L}\left( \mathcal{H}\right) }^{-1}}\right) \log \left( {{h}_{i}/\delta }\right)

where ${c}_{1} = {2K}\sqrt{2\log \left( {6/\delta }\right) },{c}_{2} = 4\sqrt{3}K\log \left( {{12}/\delta }\right)$ and ${c}_{4} = {6K}\sqrt{\log \left( {{12}/\delta }\right) }$ . The notation ${\mathcal{N}}^{{p}_{i}}$ denotes the effective dimension associated to the distribution ${p}_{k}$ .
其中 ${c}_{1} = {2K}\sqrt{2\log \left( {6/\delta }\right) },{c}_{2} = 4\sqrt{3}K\log \left( {{12}/\delta }\right)$ 和 ${c}_{4} = {6K}\sqrt{\log \left( {{12}/\delta }\right) }$ 。符号 ${\mathcal{N}}^{{p}_{i}}$ 表示与分布 ${p}_{k}$ 相关的有效维度。

Specifically,when the effective dimension $\mathcal{N}$ satisfies,for some $c \geq 0$ ,
具体而言，当有效维度 $\mathcal{N}$ 满足以下条件时（对于某个 $c \geq 0$ 而言）：

\text{- either}{\mathcal{N}}^{{\rho }_{i}}\left( {\sigma }^{2}\right) \leq c{\sigma }^{{2}^{-\gamma }}\text{for some}\gamma \in \left( {0,1}\right) \text{,}

\text{- or}{\mathcal{N}}^{{\rho }_{i}}\left( {\sigma }^{2}\right) \leq \log \left( {1 + c/{\sigma }^{2}}\right) /\beta \text{,for some}\beta > 0\text{.}

Then,choosing the subsample size $m$ to be
那么，将子样本大小 $m$ 设定为

${h}_{i} = {m}_{i}^{1/\left( {2 - \gamma }\right) }\log \left( {{m}_{i}/\delta }\right)$ in the first case
第一种情况下的 ${h}_{i} = {m}_{i}^{1/\left( {2 - \gamma }\right) }\log \left( {{m}_{i}/\delta }\right)$
or ${h}_{i} = \sqrt{{m}_{i}}\log \left( {\sqrt{{m}_{i}}\max \left( {1/\delta ,c/\left( {6{K}^{2}}\right) }\right) }\right)$ in the second case,
或第二种情况下的 ${h}_{i} = \sqrt{{m}_{i}}\log \left( {\sqrt{{m}_{i}}\max \left( {1/\delta ,c/\left( {6{K}^{2}}\right) }\right) }\right)$

we get ${\operatorname{Err}}_{\left( {\rho }_{i},{m}_{i},{h}_{i}\right) } = O\left( {1/\sqrt{{m}_{i}}}\right)$ 我们得到 ${\operatorname{Err}}_{\left( {\rho }_{i},{m}_{i},{h}_{i}\right) } = O\left( {1/\sqrt{{m}_{i}}}\right)$

B Proofs of Section 4
B 第 4 节证明

B.1 Exact Kernel Uncertainty GP Formulating
B.1 精确核不确定性高斯过程建模

Following the same notation in Section 4,now we can construct a Gaussian process $\mathcal{{GP}}\left( {0,\widehat{k}}\right)$ modeling over $\mathcal{P}$ . This $\mathcal{G}\mathcal{P}$ model can then be applied to learn $\widehat{f}$ from a given set of observations ${\mathcal{D}}_{n} = {\left\{ \left( {P}_{i},{y}_{i}\right) \right\} }_{i = 1}^{n}$ . Under zero mean condition,the value of $\widehat{f}\left( {P}_{ * }\right)$ for a given ${P}_{ * } \in \mathcal{P}$ follows a Gaussian posterior distribution with
沿用第 4 节中的相同符号约定，我们现在可以构建一个在 $\mathcal{P}$ 上建模的高斯过程 $\mathcal{{GP}}\left( {0,\widehat{k}}\right)$ 。该 $\mathcal{G}\mathcal{P}$ 模型随后可用于从给定观测集 ${\mathcal{D}}_{n} = {\left\{ \left( {P}_{i},{y}_{i}\right) \right\} }_{i = 1}^{n}$ 中学习 $\widehat{f}$ 。在零均值条件下，对于给定 ${P}_{ * } \in \mathcal{P}$ 的 $\widehat{f}\left( {P}_{ * }\right)$ 值服从具有高斯后验分布

{\widehat{\mu }}_{n}\left( {P}_{ * }\right) = {\widehat{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n} \tag{18}

{\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) = \widehat{k}\left( {{P}_{ * },{P}_{ * }}\right) - {\widehat{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) , \tag{19}

where ${\mathbf{y}}_{n} \mathrel{\text{:=}} {\left\lbrack {y}_{1},\cdots ,{y}_{n}\right\rbrack }^{T},{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) \mathrel{\text{:=}} {\left\lbrack \widehat{k}\left( {P}_{ * },{P}_{1}\right) ,\cdots ,\widehat{k}\left( {P}_{ * },{P}_{n}\right) \right\rbrack }^{T}$ and ${\left\lbrack {\widehat{\mathbf{K}}}_{n}\right\rbrack }_{ij} = \widehat{k}\left( {{P}_{i},{P}_{j}}\right)$ . Now we restrict our Gaussian process in the subspace ${\mathcal{P}}_{\mathcal{X}} = \left\{ {{P}_{x},x \in \mathcal{X}}\right\} \subset \mathcal{P}$ . We assume the observation ${y}_{i} = f\left( {x}_{i}\right) + {\zeta }_{i}$ with the noise ${\zeta }_{i}$ . The input-induced noise is defined as $\Delta {f}_{{p}_{{x}_{i}}} \mathrel{\text{:=}}$ $f\left( {x}_{i}\right) - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = f\left( {x}_{i}\right) - \widehat{f}\left( {P}_{{x}_{i}}\right)$ . Then the total noise is ${y}_{i} - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = {\zeta }_{i} + \Delta {f}_{{p}_{{x}_{i}}}$ . To formulate the regret bounds, we introduce the information gain and estimated information gain given any ${\left\{ {P}_{t}\right\} }_{t = 1}^{n} \subset \mathcal{P}$ :
其中 ${\mathbf{y}}_{n} \mathrel{\text{:=}} {\left\lbrack {y}_{1},\cdots ,{y}_{n}\right\rbrack }^{T},{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) \mathrel{\text{:=}} {\left\lbrack \widehat{k}\left( {P}_{ * },{P}_{1}\right) ,\cdots ,\widehat{k}\left( {P}_{ * },{P}_{n}\right) \right\rbrack }^{T}$ 和 ${\left\lbrack {\widehat{\mathbf{K}}}_{n}\right\rbrack }_{ij} = \widehat{k}\left( {{P}_{i},{P}_{j}}\right)$ 。现在我们将高斯过程限制在子空间 ${\mathcal{P}}_{\mathcal{X}} = \left\{ {{P}_{x},x \in \mathcal{X}}\right\} \subset \mathcal{P}$ 中。假设观测值为 ${y}_{i} = f\left( {x}_{i}\right) + {\zeta }_{i}$ ，噪声为 ${\zeta }_{i}$ 。输入引起的噪声定义为 $\Delta {f}_{{p}_{{x}_{i}}} \mathrel{\text{:=}}$ $f\left( {x}_{i}\right) - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = f\left( {x}_{i}\right) - \widehat{f}\left( {P}_{{x}_{i}}\right)$ 。则总噪声为 ${y}_{i} - {\mathbb{E}}_{{P}_{{x}_{i}}}\left\lbrack f\right\rbrack = {\zeta }_{i} + \Delta {f}_{{p}_{{x}_{i}}}$ 。为表述遗憾界，我们引入给定任意 ${\left\{ {P}_{t}\right\} }_{t = 1}^{n} \subset \mathcal{P}$ 时的信息增益与估计信息增益：

\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) \mathrel{\text{:=}} \frac{1}{2}\ln \det \left( {\mathbf{I} + {\sigma }^{-2}{\widehat{\mathbf{K}}}_{n}}\right) , \tag{20}

\widetilde{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) \mathrel{\text{:=}} \frac{1}{2}\ln \det \left( {\mathbf{I} + {\sigma }^{-2}{\widetilde{\mathbf{K}}}_{n}}\right) , \tag{21}

and the maximum information gain is defined as ${\widehat{\gamma }}_{n} \mathrel{\text{:=}} \mathop{\sup }\limits_{{\mathcal{R} \in {\mathcal{P}}_{\mathcal{X}};\left| \mathcal{R}\right| = n}}\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid \mathcal{R}}\right)$ . Here ${\widehat{\mathbf{f}}}_{n} \mathrel{\text{:=}}$ ${\left\lbrack \widehat{f}\left( {p}_{1}\right) ,\cdots ,\widehat{f}\left( {p}_{n}\right) \right\rbrack }^{T}$ .
最大信息增益定义为 ${\widehat{\gamma }}_{n} \mathrel{\text{:=}} \mathop{\sup }\limits_{{\mathcal{R} \in {\mathcal{P}}_{\mathcal{X}};\left| \mathcal{R}\right| = n}}\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid \mathcal{R}}\right)$ 。此处 ${\widehat{\mathbf{f}}}_{n} \mathrel{\text{:=}}$ ${\left\lbrack \widehat{f}\left( {p}_{1}\right) ,\cdots ,\widehat{f}\left( {p}_{n}\right) \right\rbrack }^{T}$ 。

We define the sub-Gaussian condition as follows:
我们定义次高斯条件如下：

Definition 1. For a given ${\sigma }_{\xi } > 0$ ,a real-valued random variable $\xi$ is said to be ${\sigma }_{\xi }$ -sub-Gaussian if:
定义 1. 对于给定 ${\sigma }_{\xi } > 0$ ，若实值随机变量 $\xi$ 满足以下条件，则称其为 ${\sigma }_{\xi }$ -次高斯：

\forall \lambda \in \mathbb{R},\mathbb{E}\left\lbrack {e}^{\lambda \xi }\right\rbrack \leq {e}^{{\lambda }^{2}{\sigma }_{\xi }^{2}/2}

Now we can state the lemma for bounding the uncertain-inputs regret of exact kernel evaluations, which is originally stated in Theorem 5 in [26].
现在我们可以陈述关于精确核评估的不确定输入后悔值界限的引理，该引理最初见于文献[26]的定理 5。

Lemma 2. Let $\delta \in \left( {0,1}\right) ,f \in {\mathcal{H}}_{k}$ ,and the corresponding $\parallel \widehat{f}{\parallel }_{\widehat{k}} \leq b$ . Suppose the observation noise ${\zeta }_{i} = {y}_{i} - f\left( {x}_{i}\right)$ is conditionally ${\sigma }_{\zeta }$ -sub-Gaussian. Assume that both $k$ and ${P}_{x}$ satisfy the conditions for $\Delta {f}_{{P}_{x}}$ to be ${\sigma }_{E}$ -sub-Gaussian,for a given ${\sigma }_{E} > 0$ . Then,we have the following results:
引理 2. 设 $\delta \in \left( {0,1}\right) ,f \in {\mathcal{H}}_{k}$ ，且对应的 $\parallel \widehat{f}{\parallel }_{\widehat{k}} \leq b$ 。假设观测噪声 ${\zeta }_{i} = {y}_{i} - f\left( {x}_{i}\right)$ 是条件 ${\sigma }_{\zeta }$ -次高斯的。对于给定的 ${\sigma }_{E} > 0$ ，若 $k$ 和 ${P}_{x}$ 都满足使 $\Delta {f}_{{P}_{x}}$ 成为 ${\sigma }_{E}$ -次高斯的条件，则我们有以下结果：

The following holds for all $x \in \mathcal{X}$ and $t \geq 1$ :
对于所有 $x \in \mathcal{X}$ 和 $t \geq 1$ ，以下结论成立：

\left| {{\widehat{\mu }}_{n}\left( {P}_{x}\right) - \widehat{f}\left( {P}_{x}\right) }\right| \leq \left( {b + \sqrt{{\sigma }_{E}^{2} + {\sigma }_{\zeta }^{2}}\sqrt{2\left( {\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) + 1 + \ln \left( {1/\delta }\right) }\right) }{\widehat{\sigma }}_{n}\left( {P}_{x}\right) }\right. \tag{22}

Running with upper confidence bound (UCB) acquisition function $\alpha \left( {x \mid {\mathcal{D}}_{n}}\right) = {\widehat{\mu }}_{n}\left( {P}_{x}\right) +$ ${\widehat{\beta }}_{n}{\widehat{\sigma }}_{n}\left( {P}_{x}\right)$ where
使用上置信界(UCB)获取函数 $\alpha \left( {x \mid {\mathcal{D}}_{n}}\right) = {\widehat{\mu }}_{n}\left( {P}_{x}\right) +$ ${\widehat{\beta }}_{n}{\widehat{\sigma }}_{n}\left( {P}_{x}\right)$ 运行时

{\widehat{\beta }}_{n} = b + \sqrt{{\sigma }_{E}^{2} + {\sigma }_{\zeta }^{2}}\sqrt{2\left( {\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) + 1 + \ln \left( {1/\delta }\right) }\right) },

and set ${\sigma }^{2} = 1 + 2/n$ ,the uncertain-inputs cumulative regret satisfies:
并设 ${\sigma }^{2} = 1 + 2/n$ ，不确定输入的累积遗憾满足：

{\widehat{R}}_{n} \in O\left( {\sqrt{n{\widehat{\gamma }}_{n}}\left( {b + \sqrt{{\widehat{\gamma }}_{n} + \ln \left( {1/\delta }\right) }}\right) }\right) \tag{23}

with probability at least $1 - \delta$ .
概率至少为 $1 - \delta$ 。

Note that although the original theorem restricted to the case when $\widehat{k}\left( {p,q}\right) = {\left\langle {\psi }_{P},{\psi }_{Q}\right\rangle }_{k}$ ,the results can be easily generated to other kernels over $\mathcal{P}$ ,as long as its universal w.r.t $C\left( \mathcal{P}\right)$ given that $\mathcal{X}$ is compact and the mean map $\psi$ is injective [11,22].
需注意，虽然原定理仅限于 $\widehat{k}\left( {p,q}\right) = {\left\langle {\psi }_{P},{\psi }_{Q}\right\rangle }_{k}$ 的情况，但只要 $\mathcal{X}$ 是紧致的且均值映射 $\psi$ 是单射[11,22]，这些结果可以轻松推广到 $\mathcal{P}$ 上的其他核函数，前提是该核关于 $C\left( \mathcal{P}\right)$ 是通用的。

B.2 Error Estimates for Inexact Kernel Approximation
B.2 非精确核近似的误差估计

Now let us derivative the inference under the inexact kernel estimations.
现在让我们推导在非精确核估计下的推理过程。

Theorem 3. Under the Assumption 1 for $\varepsilon > 0$ ,let ${\widetilde{\mu }}_{n},{\widetilde{\sigma }}_{n},\widetilde{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right)$ as defined in [13],[14],[21] respectively,and ${\widehat{\mu }}_{n},{\widehat{\sigma }}_{n},\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right)$ as defined in [18],[19],[20]. Assume $\mathop{\max }\limits_{{x \in \mathcal{X}}}\overline{f\left( x\right) } = M$ ,and assume the observation error ${\zeta }_{i} = {y}_{i} - f\left( {x}_{i}\right)$ satisfies $\left| {\zeta }_{i}\right| < A$ for all $i$ . Then we have the following error bound holds with probability at least $1 - {n\varepsilon }$ :
定理 3. 在假设 1 对 $\varepsilon > 0$ 成立的条件下，令 ${\widetilde{\mu }}_{n},{\widetilde{\sigma }}_{n},\widetilde{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right)$ 分别如[13],[14],[21]中所定义， ${\widehat{\mu }}_{n},{\widehat{\sigma }}_{n},\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right)$ 如[18],[19],[20]中所定义。假设 $\mathop{\max }\limits_{{x \in \mathcal{X}}}\overline{f\left( x\right) } = M$ ，并假设观测误差 ${\zeta }_{i} = {y}_{i} - f\left( {x}_{i}\right)$ 对所有 $i$ 满足 $\left| {\zeta }_{i}\right| < A$ 。那么以至少 $1 - {n\varepsilon }$ 的概率有以下误差界成立：

\left| {{\widehat{\mu }}_{n}\left( {P}_{ * }\right) - {\widetilde{\mu }}_{n}\left( {P}_{ * }\right) }\right| < \left( {\frac{n}{{\sigma }^{2}} + \frac{{n}^{2}}{{\sigma }^{4}}}\right) \left( {M + A}\right) {e}_{\varepsilon } + O\left( {e}_{\varepsilon }^{2}\right) \tag{24}

\left| {{\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) - {\widetilde{\sigma }}_{n}^{2}\left( {P}_{ * }\right) }\right| < {\left( 1 + \frac{n}{{\sigma }^{2}}\right) }^{2}{e}_{\varepsilon } + O\left( {e}_{\varepsilon }^{2}\right) \tag{25}

\left| {\widetilde{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) - \widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) }\right| < \frac{{n}^{3/2}}{2{\sigma }^{2}}{e}_{\varepsilon } + O\left( {e}_{\varepsilon }^{2}\right) \tag{26}

Proof. Denote $e\left( {{P}_{ * },Q}\right) = \widetilde{k}\left( {{P}_{ * },Q}\right) - \widehat{k}\left( {{P}_{ * },Q}\right) ,{\mathbf{e}}_{n}\left( {P}_{ * }\right) = {\left\lbrack e\left( {P}_{ * },{P}_{1}\right) ,\cdots ,e\left( {P}_{ * } \cdot {P}_{n}\right) \right\rbrack }^{T}$ ,and 证明. 记 $e\left( {{P}_{ * },Q}\right) = \widetilde{k}\left( {{P}_{ * },Q}\right) - \widehat{k}\left( {{P}_{ * },Q}\right) ,{\mathbf{e}}_{n}\left( {P}_{ * }\right) = {\left\lbrack e\left( {P}_{ * },{P}_{1}\right) ,\cdots ,e\left( {P}_{ * } \cdot {P}_{n}\right) \right\rbrack }^{T}$ ，且

${\left\lbrack {\mathbf{E}}_{n}\right\rbrack }_{i,j} = e\left( {{P}_{i},{P}_{j}}\right)$ . Now according to the matrix inverse perturbation expansion,
${\left\lbrack {\mathbf{E}}_{n}\right\rbrack }_{i,j} = e\left( {{P}_{i},{P}_{j}}\right)$ 。根据矩阵逆扰动展开定理，

{\left( X + \delta X\right) }^{-1} = {X}^{-1} - {X}^{-1}{\delta X}{X}^{-1} + O\left( {\parallel {\delta X}{\parallel }^{2}}\right) ,

we have 我们有

{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I} + {\mathbf{E}}_{n}\right) }^{-1} = {\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1} - {\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{E}}_{n}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1} + O\left( {\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}^{2}\right) ,

thus 因此

{\widetilde{\mu }}_{n}\left( {P}_{ * }\right) = {\left( {\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) + {\mathbf{e}}_{n}\left( {P}_{ * }\right) \right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I} + {\mathbf{E}}_{n}\right) }^{-1}{\mathbf{y}}_{n}

= {\widehat{\mu }}_{n}\left( {P}_{ * }\right) + {\mathbf{e}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n} - {\widehat{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{E}}_{n}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n}

+ O\left( {\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}^{2}\right) + O\left( {\begin{Vmatrix}{{\mathbf{e}}_{n}\left( {P}_{ * }\right) }\end{Vmatrix}\parallel \cdot \begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}\right)

{\widetilde{\sigma }}_{n}^{2}\left( {P}_{ * }\right) = {\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) + e\left( {{P}_{ * },{P}_{ * }}\right) - {\left( {\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) + {\mathbf{e}}_{n}\left( {P}_{ * }\right) \right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I} + {\mathbf{E}}_{n}\right) }^{-1}\left( {{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) + {\mathbf{e}}_{n}\left( {P}_{ * }\right) }\right)

= {\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) + e\left( {{P}_{ * },{P}_{ * }}\right) - 2{\mathbf{e}}_{n}{\left( P\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right)

+ {\widehat{\mathbf{k}}}_{n}{\left( P\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{E}}_{n}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right)

+ O\left( {\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}^{2}\right) + O\left( {\begin{Vmatrix}{\mathbf{e}}_{n}\end{Vmatrix} \cdot \begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}\right) + O\left( {{\begin{Vmatrix}{\mathbf{e}}_{n}\end{Vmatrix}}^{2} \cdot \begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}\right)

Notic that the following holds with a probability at least $1 - {n\varepsilon }$ ,according to the Assumption 1,
请注意，根据假设 1，以下结论至少以 $1 - {n\varepsilon }$ 的概率成立：

\left| {{\mathbf{e}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{K}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n}}\right| \leq {\begin{Vmatrix}{\mathbf{e}}_{n}\left( {P}_{ * }\right) \end{Vmatrix}}_{2}{\begin{Vmatrix}{\left( {\widehat{K}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}\end{Vmatrix}}_{2}{\begin{Vmatrix}{\mathbf{y}}_{n}\end{Vmatrix}}_{2} \leq \frac{n}{{\sigma }^{2}}\left( {M + A}\right) {e}_{\varepsilon },

\left| {{\widehat{\mathbf{k}}}_{n}{\left( {P}_{ * }\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{E}}_{n}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\mathbf{y}}_{n}}\right| \leq {\begin{Vmatrix}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right) \end{Vmatrix}}_{2}{\begin{Vmatrix}{\left( {\widehat{K}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}\end{Vmatrix}}_{2}^{2}{\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}_{2}{\begin{Vmatrix}{\mathbf{y}}_{n}\end{Vmatrix}}_{2}

\leq \sqrt{n}{\sigma }^{-4}n{e}_{\varepsilon }\sqrt{n}\left( {M + A}\right) = \frac{{n}^{2}}{{\sigma }^{4}}\left( {M + A}\right) ,

here we use the fact that ${\widehat{K}}_{n}$ semi-definite (which means ${\begin{Vmatrix}{\left( {\widehat{K}}_{n} + {\sigma }^{2}I\right) }^{-1}\end{Vmatrix}}_{2} \leq {\sigma }^{-2}$ ), $\widehat{k}\left( {{P}_{ * },{P}_{ * }}\right) \leq 1$ , $\left| {y}_{i}\right| \leq M + A$ . Combining these results,we have that
这里我们利用了 ${\widehat{K}}_{n}$ 半正定（即 ${\begin{Vmatrix}{\left( {\widehat{K}}_{n} + {\sigma }^{2}I\right) }^{-1}\end{Vmatrix}}_{2} \leq {\sigma }^{-2}$ ）、 $\widehat{k}\left( {{P}_{ * },{P}_{ * }}\right) \leq 1$ 、 $\left| {y}_{i}\right| \leq M + A$ 的性质。综合这些结果可得

\left| {{\widetilde{\mu }}_{n}\left( {P}_{ * }\right) - {\widehat{\mu }}_{n}\left( {P}_{ * }\right) }\right| < \left( {\frac{n}{{\sigma }^{2}} + \frac{{n}^{2}}{{\sigma }^{4}}}\right) \left( {M + A}\right) {e}_{\varepsilon } + O\left( {e}_{\varepsilon }^{2}\right) ,

holds with a probability at least $1 - {n\varepsilon }$ .
以至少 $1 - {n\varepsilon }$ 的概率成立。

Similarly,we can conduct the same estimation to ${\mathbf{e}}_{n}{\left( P\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right)$ and ${\widehat{\mathbf{k}}}_{n}{\left( P\right) }^{T}\left( {\widehat{\mathbf{K}}}_{n}\right. +$ ${\sigma }^{2}\mathbf{I}{)}^{-1}{\mathbf{E}}_{n}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right)$ ,and get $\left| {{\widetilde{\sigma }}_{n}^{2}\left( {P}_{ * }\right) - {\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) }\right| < {\left( 1 + \frac{n}{{\sigma }^{2}}\right) }^{2}{e}_{\varepsilon } + O\left( {e}_{\varepsilon }^{2}\right)$ holds with a probability at least $1 - {n\varepsilon }$ .
同理，我们可以对 ${\mathbf{e}}_{n}{\left( P\right) }^{T}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right)$ 、 ${\widehat{\mathbf{k}}}_{n}{\left( P\right) }^{T}\left( {\widehat{\mathbf{K}}}_{n}\right. +$ ${\sigma }^{2}\mathbf{I}{)}^{-1}{\mathbf{E}}_{n}{\left( {\widehat{\mathbf{K}}}_{n} + {\sigma }^{2}\mathbf{I}\right) }^{-1}{\widehat{\mathbf{k}}}_{n}\left( {P}_{ * }\right)$ 进行相同的估计，并以至少 $1 - {n\varepsilon }$ 的概率得到 $\left| {{\widetilde{\sigma }}_{n}^{2}\left( {P}_{ * }\right) - {\widehat{\sigma }}_{n}^{2}\left( {P}_{ * }\right) }\right| < {\left( 1 + \frac{n}{{\sigma }^{2}}\right) }^{2}{e}_{\varepsilon } + O\left( {e}_{\varepsilon }^{2}\right)$ 成立。

It remains to estimate the error for estimating the information gain. Notice that, with a probability at least $1 - {n\varepsilon }$ ,
仍需估计信息增益的误差。注意，以至少 $1 - {n\varepsilon }$ 的概率，

\left| {\widetilde{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {p}_{t}\right\} }_{t = 1}^{n}}\right) - \widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {p}_{t}\right\} }_{t = 1}^{n}}\right) }\right| = \left| {\frac{1}{2}\log \frac{\det \left( {\mathbf{I} + {\sigma }^{-2}{\widetilde{\mathbf{K}}}_{n}}\right) }{\det \left( {\mathbf{I} + {\sigma }^{-2}{\widehat{\mathbf{K}}}_{n}}\right) }}\right|

= \left| {\frac{1}{2}\log \det \left( {\mathbf{I} - {\left( {\sigma }^{2}\mathbf{I} + {\widehat{\mathbf{K}}}_{n}\right) }^{-1}{\mathbf{E}}_{n}}\right) }\right|

= \left| {\frac{1}{2}\operatorname{Tr}\left( {\log \left( {\mathbf{I} - {\left( {\sigma }^{2}\mathbf{I} + {\widehat{\mathbf{K}}}_{n}\right) }^{-1}{\mathbf{E}}_{n}}\right) }\right) }\right|

= \left| {\frac{1}{2}\operatorname{Tr}\left( {-{\left( {\sigma }^{2}\mathbf{I} + {\widehat{\mathbf{K}}}_{n}\right) }^{-1}{\mathbf{E}}_{n}}\right) + O\left( {\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}^{2}\right) }\right|

\leq \frac{{n}^{3/2}}{2{\sigma }^{2}}{e}_{\varepsilon } + O\left( {\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}^{2}\right) ,

here the second equation uses the fact that $\det \left( {A{B}^{-1}}\right) = \det \left( A\right) \det {\left( B\right) }^{-1}$ ,and the third and fourth equations use $\log \det \left( {I + A}\right) = \operatorname{Tr}\log \left( {I + A}\right) = \operatorname{Tr}\left( {A - \frac{{A}^{2}}{2} + \cdots }\right)$ . The last inequality follows from the fact
此处第二个等式利用了 $\det \left( {A{B}^{-1}}\right) = \det \left( A\right) \det {\left( B\right) }^{-1}$ 的性质，第三和第四个等式运用了 $\log \det \left( {I + A}\right) = \operatorname{Tr}\log \left( {I + A}\right) = \operatorname{Tr}\left( {A - \frac{{A}^{2}}{2} + \cdots }\right)$ 。最后一个不等式源于

\operatorname{Tr}\left( {{\sigma }^{2}\mathbf{I} + {\widehat{\mathbf{K}}}_{n}{)}^{-1}{\mathbf{E}}_{n}}\right) \leq {\begin{Vmatrix}{\left( {\sigma }^{2}\mathbf{I} + {\widehat{\mathbf{K}}}_{n}\right) }^{-1}\end{Vmatrix}}_{F}{\begin{Vmatrix}{\mathbf{E}}_{n}\end{Vmatrix}}_{F} \leq {n}^{3/2}{\sigma }^{-2}{e}_{\varepsilon }

and ${\widehat{\mathbf{K}}}_{n}$ is semi-definite. With the uncertainty bound given by Lemma 3, let us prove that under inexact kernel estimations, the posterior mean is concentrated around the unknown reward function $\widehat{f}$
且 ${\widehat{\mathbf{K}}}_{n}$ 是半正定的。根据引理 3 给出的不确定性边界，让我们证明在核估计不精确的情况下，后验均值集中在未知奖励函数 $\widehat{f}$ 周围

Theorem 4. Under the former setting as in Theorem 3 with probability at least $1 - \delta - {n\varepsilon }$ ,let ${\sigma }_{\nu } = \sqrt{{\sigma }_{\zeta }^{2} + {\sigma }_{E}^{2}}$ ,taking $\sigma = 1 + \frac{2}{n}$ ,the following holds for all $x \in \mathcal{X}$ :
定理 4. 在定理 3 相同设定下，以至少 $1 - \delta - {n\varepsilon }$ 的概率成立，令 ${\sigma }_{\nu } = \sqrt{{\sigma }_{\zeta }^{2} + {\sigma }_{E}^{2}}$ ，取 $\sigma = 1 + \frac{2}{n}$ ，则对所有 $x \in \mathcal{X}$ 均有：

\left| {{\widetilde{\mu }}_{n}\left( {P}_{x}\right) - \widehat{f}\left( {P}_{x}\right) }\right| \leq {\beta }_{n}{\widetilde{\sigma }}_{n}\left( {P}_{x}\right) + {\beta }_{n}\left( {1 + n}\right) {e}_{\varepsilon }^{1/2} + \left( {n + {n}^{2}}\right) \left( {M + A}\right) {e}_{\varepsilon }, \tag{27}

\text{where}{\beta }_{n} = \left( {b + {\sigma }_{\nu }\sqrt{2\left( {{\widehat{\gamma }}_{n} - \ln \left( \delta \right) + 1}\right) }}\right)

Proof. According to Lemma 2, equation (22), we have
证明. 根据引理 2 的式(22)可得

\left| {{\widehat{\mu }}_{n}\left( {P}_{x}\right) - \widehat{f}\left( {P}_{x}\right) }\right| \leq {\widehat{\beta }}_{n}{\widehat{\sigma }}_{n}\left( {P}_{x}\right)

with 其中

{\widehat{\beta }}_{n} = b + {\sigma }_{\nu }\sqrt{2\left( {\widehat{I}\left( {{\mathbf{y}}_{n};{\widehat{\mathbf{f}}}_{n} \mid {\left\{ {P}_{t}\right\} }_{t = 1}^{n}}\right) + 1 + \ln \left( {1/\delta }\right) }\right) } \leq {\beta }_{n}.

Notice that 注意到

\left| {{\widetilde{\mu }}_{n}\left( {P}_{x}\right) - \widehat{f}\left( {P}_{x}\right) }\right| \leq \left| {{\widetilde{\mu }}_{n}\left( {P}_{x}\right) - {\widehat{\mu }}_{n}\left( {P}_{x}\right) }\right| + \left| {{\widehat{\mu }}_{n}\left( {P}_{x}\right) - \widehat{f}\left( {P}_{x}\right) }\right| , \tag{28}

We also have [25], which means
我们还拥有[25]，这意味着

{\widehat{\sigma }}_{n}\left( {P}_{x}\right) = \sqrt{{\widehat{\sigma }}_{n}{\left( {P}_{x}\right) }^{2}} \leq \sqrt{{\widetilde{\sigma }}_{n}{\left( {P}_{x}\right) }^{2} + {\left( 1 + n\right) }^{2}{e}_{\varepsilon }} \leq {\widetilde{\sigma }}_{n}\left( {P}_{x}\right) + \left( {1 + n}\right) {e}_{\varepsilon }^{1/2}, \tag{29}

combining (24), (28) and (29), we finally get the result in (27).
结合(24)、(28)和(29)，我们最终得到(27)中的结果。

B.3 Proofs for Theorem 1
B.3 定理 1 的证明

Now we can prove our main theorem 1 .
现在我们可以证明我们的主要定理 1。

Proof of Theorem 1 Let ${x}^{ * }$ maximize $\widehat{f}\left( {P}_{x}\right)$ over $\mathcal{X}$ . Observing that at each round $n \geq 1$ ,by the choice of ${x}_{n}$ to maximize the acquisition function $\widetilde{\alpha }\left( {x \mid {\mathcal{D}}_{n - 1}}\right) = {\widetilde{\mu }}_{n - 1}\left( {P}_{x}\right) + {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{x}\right)$ ,we have
定理 1 的证明设 ${x}^{ * }$ 在 $\mathcal{X}$ 上最大化 $\widehat{f}\left( {P}_{x}\right)$ 。观察到在每轮 $n \geq 1$ 中，通过选择 ${x}_{n}$ 来最大化采集函数 $\widetilde{\alpha }\left( {x \mid {\mathcal{D}}_{n - 1}}\right) = {\widetilde{\mu }}_{n - 1}\left( {P}_{x}\right) + {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{x}\right)$ ，我们得到

{\widetilde{r}}_{n} = \widehat{f}\left( {P}_{{x}^{ * }}\right) - \widehat{f}\left( {P}_{{x}_{n}}\right)

\leq {\widetilde{\mu }}_{n - 1}\left( {P}_{{x}^{ * }}\right) + {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}^{ * }}\right) - {\widetilde{\mu }}_{n - 1}\left( {P}_{{x}_{n}}\right) + {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}_{n}}\right) + 2\operatorname{Err}\left( {n - 1,{e}_{\varepsilon }}\right)

\leq 2{\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}_{n}}\right) + 2\operatorname{Err}\left( {n - 1,{e}_{\varepsilon }}\right) .

Here we denote $\operatorname{Err}\left( {n,{e}_{\varepsilon }}\right) \mathrel{\text{:=}} \left( {{\beta }_{n}\left( {1 + n}\right) + {\widetilde{\sigma }}_{n}\left( {P}_{x}\right) {\sigma }_{\nu }{n}^{3/4}}\right) {e}_{\varepsilon }^{1/2} + \left( {n + {n}^{2}}\right) \left( {M + A}\right) {e}_{\varepsilon }$ . The second inequality follows from [27],
此处记 $\operatorname{Err}\left( {n,{e}_{\varepsilon }}\right) \mathrel{\text{:=}} \left( {{\beta }_{n}\left( {1 + n}\right) + {\widetilde{\sigma }}_{n}\left( {P}_{x}\right) {\sigma }_{\nu }{n}^{3/4}}\right) {e}_{\varepsilon }^{1/2} + \left( {n + {n}^{2}}\right) \left( {M + A}\right) {e}_{\varepsilon }$ 。第二个不等式源自[27]，

\widehat{f}\left( {P}_{{x}^{ * }}\right) - {\widetilde{\mu }}_{n - 1}\left( {P}_{{x}^{ * }}\right) \leq {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}^{ * }}\right) + \operatorname{Err}\left( {n - 1,{e}_{\varepsilon }}\right)

{\widetilde{\mu }}_{n - 1}\left( {P}_{{x}_{n}}\right) - \widehat{f}\left( {P}_{{x}_{n}}\right) \leq {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}_{n}}\right) + \operatorname{Err}\left( {n - 1,{e}_{\varepsilon }}\right) ,

and the third inequality follows from the choice of ${x}_{n}$ :
第三个不等式来自 ${x}_{n}$ 的选择：

{\widetilde{\mu }}_{n - 1}\left( {P}_{{x}^{ * }}\right) + {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}^{ * }}\right) \leq {\widetilde{\mu }}_{n - 1}\left( {P}_{{x}_{n}}\right) + {\beta }_{n - 1}{\widetilde{\sigma }}_{n - 1}\left( {P}_{{x}_{n}}\right) .

Thus we have 因此我们得出

{\widetilde{R}}_{n} = \mathop{\sum }\limits_{{t = 1}}^{n}{\widetilde{r}}_{t} \leq 2{\beta }_{n}\mathop{\sum }\limits_{{t = 1}}^{n}{\widetilde{\sigma }}_{t - 1}\left( {P}_{{x}_{t}}\right) + \mathop{\sum }\limits_{{t = 1}}^{T}\operatorname{Err}\left( {t - 1,{e}_{\varepsilon }}\right) .

From Lemma 4 in [9], we have that
根据文献[9]中的引理 4，我们可得

\mathop{\sum }\limits_{{t = 1}}^{n}{\widetilde{\sigma }}_{t - 1}\left( {P}_{{x}_{t}}\right) \leq \sqrt{4\left( {n + 2}\right) \ln \det \left( {I + {\sigma }^{-2}{\widetilde{K}}_{n}}\right) } \leq \sqrt{4\left( {n + 2}\right) \left( {{\widehat{\gamma }}_{n} + \frac{{n}^{\frac{3}{2}}}{2}{e}_{\varepsilon }}\right) },

and thus 因此

2{\beta }_{n}\mathop{\sum }\limits_{{t = 1}}^{n}{\widetilde{\sigma }}_{t - 1}\left( {P}_{{x}_{t}}\right) = O\left( {\sqrt{n{\widehat{\gamma }}_{n}} + \sqrt{n{\widehat{\gamma }}_{n}\left( {{\widehat{\gamma }}_{n} - \ln \delta }\right) } + \sqrt{{n}^{\frac{5}{2}}{e}_{\varepsilon }} + \sqrt{{n}^{\frac{5}{2}}\left( {{\widehat{\gamma }}_{n} - \ln \delta }\right) {e}_{\varepsilon }}}\right) . \tag{30}

On the other hand, notice that
另一方面，注意到

\mathop{\sum }\limits_{{t = 1}}^{n}\operatorname{Err}\left( {t - 1,{e}_{\varepsilon }}\right) = O\left( {{n}^{2}\sqrt{\left( {{\widehat{\gamma }}_{n} - \ln \delta }\right) {e}_{\varepsilon }} + \left( {{n}^{2} + {n}^{3}}\right) {e}_{\epsilon }}\right) , \tag{31}

we find that the ${e}_{\varepsilon }$ term in (30) can be controlled by in (31),thus we immediately get the result.
我们发现式(30)中的 ${e}_{\varepsilon }$ 项可由式(31)控制，从而立即得出该结论。

B.4 Proofs for Theorem 2
B.4 定理 2 的证明

Proof. Define the square of the MMD distance between ${P}_{{x}_{1}},{P}_{{x}_{2}}$ as ${d}_{M}\left( {{x}_{1},{x}_{2}}\right)$ ,we have
证明。定义 ${P}_{{x}_{1}},{P}_{{x}_{2}}$ 之间的 MMD 距离平方为 ${d}_{M}\left( {{x}_{1},{x}_{2}}\right)$ ，可得

{d}_{M}\left( {{x}_{1},{x}_{2}}\right)

= {\int }_{{\mathbb{R}}^{d}}k\left( {x,{x}^{\prime }}\right) {P}_{{x}_{1}}\left( x\right) {P}_{{x}_{1}}\left( {x}^{\prime }\right) \mathrm{d}x\mathrm{\;d}{x}^{\prime } + {\int }_{{\mathbb{R}}^{d}}k\left( {x,{x}^{\prime }}\right) {P}_{{x}_{2}}\left( x\right) {P}_{{x}_{2}}\left( {x}^{\prime }\right) \mathrm{d}x\mathrm{\;d}{x}^{\prime }

- 2{\int }_{{\mathbb{R}}^{d}}k\left( {x,{x}^{\prime }}\right) {P}_{{x}_{1}}\left( x\right) {P}_{{x}_{2}}\left( {x}^{\prime }\right) \mathrm{d}x\mathrm{\;d}{x}^{\prime }

= {\int }_{{\mathbb{R}}^{d}}\left( {k\left( {x - {x}_{1},{x}^{\prime } - {x}_{1}}\right) + k\left( {x - {x}_{2},{x}^{\prime } - {x}_{2}}\right) - {2k}\left( {x - {x}_{1},{x}^{\prime } - {x}_{2}}\right) }\right) {P}_{0}\left( x\right) {P}_{0}\left( {x}^{\prime }\right) \mathrm{d}x\mathrm{\;d}{x}^{\prime }.

It is not hard to verify that ${d}_{M}$ is shift invariant: ${d}_{M}\left( {{x}_{1},{x}_{2}}\right) = {d}_{M}\left( {{x}_{1} - {x}_{2},0}\right)$ ,and ${d}_{M}$ has $r$ -th bounded derivatives,thus ${\widehat{k}}^{ * }\left( {{x}_{1},{x}_{2}}\right) \mathrel{\text{:=}} \widehat{k}\left( {{P}_{{x}_{1}},{P}_{{x}_{2}}}\right) = \exp \left( {-\alpha {d}_{M}\left( {{x}_{1},{x}_{2}}\right) }\right)$ is shift invariant with $r$ -th bounded derivatives. Then take $\mu \left( x\right)$ as the Lebesgue measure over $\mathcal{X}$ ,according to Theorem 4, [17],the integral operator ${T}_{k,\mu } : {T}_{k,\mu }f\left( x\right) = {\int }_{\mathcal{X}}K\left( {x,y}\right) f\left( y\right) {d\mu }\left( y\right)$ is a symmetric compact operator in ${L}_{2}\left( {\mathcal{X},\mu }\right)$ ,and the spectrum of ${T}_{k,\mu }$ satisfies
不难验证 ${d}_{M}$ 具有平移不变性： ${d}_{M}\left( {{x}_{1},{x}_{2}}\right) = {d}_{M}\left( {{x}_{1} - {x}_{2},0}\right)$ ，且 ${d}_{M}$ 具有 $r$ 阶有界导数，因此 ${\widehat{k}}^{ * }\left( {{x}_{1},{x}_{2}}\right) \mathrel{\text{:=}} \widehat{k}\left( {{P}_{{x}_{1}},{P}_{{x}_{2}}}\right) = \exp \left( {-\alpha {d}_{M}\left( {{x}_{1},{x}_{2}}\right) }\right)$ 是具有 $r$ 阶有界导数的平移不变函数。取 $\mu \left( x\right)$ 为 $\mathcal{X}$ 上的勒贝格测度，根据文献[17]中的定理 4，积分算子 ${T}_{k,\mu } : {T}_{k,\mu }f\left( x\right) = {\int }_{\mathcal{X}}K\left( {x,y}\right) f\left( y\right) {d\mu }\left( y\right)$ 是 ${L}_{2}\left( {\mathcal{X},\mu }\right)$ 空间中的对称紧算子，且 ${T}_{k,\mu }$ 的谱满足

{\lambda }_{n}\left( {T}_{k,\mu }\right) = O\left( {n}^{-1 - r/d}\right) .

Then according to Theorem 5 in [30],we have ${\widehat{\gamma }}_{n} = O\left( {{n}^{\frac{d\left( {d + 1}\right) }{r + d\left( {d + 1}\right) }}\log \left( n\right) }\right)$ ,which finish the proof.
根据文献[30]中的定理 5，我们得到 ${\widehat{\gamma }}_{n} = O\left( {{n}^{\frac{d\left( {d + 1}\right) }{r + d\left( {d + 1}\right) }}\log \left( n\right) }\right)$ ，至此完成证明。

C Evaluation Details C 评估细节

C.1 Implementation C.1 实现方案

In our implementation of AIRBO,we design the kernel $k$ used for MMD estimation to be a linear combination of multiple Rational Quadratic kernels as its long tail behavior circumvents the fast decay issue of kernel [6]:
在 AIRBO 的实现中，我们将用于 MMD 估计的核函数 $k$ 设计为多个有理二次核的线性组合，因其长尾特性规避了核函数[6]的快速衰减问题：

k\left( {x,{x}^{\prime }}\right) = \mathop{\sum }\limits_{{{a}_{i} \in \{ {0.2},{0.5},1,2,5\} }}{\left( 1 + \frac{{\left( x - {x}^{\prime }\right) }^{2}}{2{a}_{i}{l}_{i}^{2}}\right) }^{-{a}_{i}}, \tag{32}

where ${l}_{i}$ is a learnable lengthscale and ${a}_{i}$ determines the relative weighting of large-scale and small-scale variations.
其中 ${l}_{i}$ 为可学习的长度尺度参数， ${a}_{i}$ 用于确定大尺度与小尺度变化的相对权重。

Depending on the form of input distributions, the sampling and sub-sampling sizes for Nyström MMD estimator are empirically selected via experiments. Moreover, as the input uncertainty is already modeled in the surrogate,we employ a classic UCB-based acquisition as Eq. 5 with $\beta = {2.0}$ and maximize it via an L-BFGS-B optimizer.
根据输入分布的形式，通过实验经验性地选择 Nyström MMD 估计器的采样和子采样规模。此外，由于代理模型中已对输入不确定性进行建模，我们采用如公式 5 所示的经典 UCB 采集函数（含 $\beta = {2.0}$ 参数），并通过 L-BFGS-B 优化器实现最大化。

Figure 7: Modeling performance with a step-changing Chi-squared distribution.
图 7：阶跃变化卡方分布下的建模性能表现

D More Experiments D 补充实验

D.1 Comparing with the Other Models
D.1 与其他模型的对比

To compare the modeling performances with the other models, we design the input uncertainty to follow a step-changing Chi-squared distribution: ${P}_{x} = {\chi }^{2}\left( {g\left( x\right) ,\sigma = {0.01}}\right)$ ,where $g\left( x\right) = {0.5}$ if $x \in \lbrack {0.0},{0.6})$ and $g\left( x\right) = {7.0}$ when $x \in \left\lbrack {{0.6},{1.0}}\right\rbrack$ . Due to this sudden parameter change,the uncertainty at point $x = {0.6}$ is expected to be asymmetric: 1) on its left-hand side,as the Chi-squared distribution becomes quite lean and sharp with a small value of $g\left( x\right) = {0.5}$ ,the distance from $x = {0.6}$ to its LHS points, ${x}_{lhs} \in \lbrack {0.0},{0.6})$ ,are relatively large,thus their covariances are small,resulting a fast-growing uncertainty. 2)Meanwhile,when $x \in \left\lbrack {{0.6},{1.0}}\right\rbrack$ ,the $g\left( x\right)$ suddenly increases to 7.0, rendering the input distribution a quite flat one with a long tail. Therefore, the distances between $x = {0.6}$ and its RHS points become relatively small,which leads to large covariances and small uncertainties for points in $\left\lbrack {{0.6},{1.0}}\right\rbrack$ . As a result,we expect to observe an asymmetric posterior uncertainty at $x = {0.6}$ .
为评估不同模型的建模性能，我们设计了一种阶梯式变化的卡方分布输入不确定性： ${P}_{x} = {\chi }^{2}\left( {g\left( x\right) ,\sigma = {0.01}}\right)$ ，其中当 $x \in \lbrack {0.0},{0.6})$ 时 $g\left( x\right) = {0.5}$ ，而 $x \in \left\lbrack {{0.6},{1.0}}\right\rbrack$ 时 $g\left( x\right) = {7.0}$ 。由于这种参数突变，点 $x = {0.6}$ 处的不确定性预计呈现非对称特征：1) 在左侧区间，随着卡方分布因 $g\left( x\right) = {0.5}$ 值较小变得极为陡峭，从 $x = {0.6}$ 到其左侧点 ${x}_{lhs} \in \lbrack {0.0},{0.6})$ 的距离相对较大，导致协方差较小，不确定性快速攀升；2) 当 $x \in \left\lbrack {{0.6},{1.0}}\right\rbrack$ 时， $g\left( x\right)$ 骤增至 7.0，使输入分布呈现长尾扁平形态，因此 $x = {0.6}$ 与其右侧点之间的距离相对较小，使得 $\left\lbrack {{0.6},{1.0}}\right\rbrack$ 区间内的点具有较大协方差和较小不确定性。最终我们预期在 $x = {0.6}$ 处观察到非对称的后验不确定性。

Several surrogate models are employed in this comparison, including:
本对比研究采用了多种代理模型，包括：

MMDGP-nystrom(160/10) is our method with a sampling size $m = {160}$ and sub-sampling size $h = {10}$ . Its complexity is $O\left( {MNmh}\right)$ ,where $M$ and $N$ are the sizes of training and test samples (Note: all the models in this experiment use the same training and testing samples for a fair comparison).
MMDGP-nystrom(160/10)是我们的方法，采样大小为 $m = {160}$ ，子采样大小为 $h = {10}$ 。其复杂度为 $O\left( {MNmh}\right)$ ，其中 $M$ 和 $N$ 分别是训练样本和测试样本的规模（注：本实验中所有模型均使用相同的训练和测试样本以确保公平比较）。
uGP(40) is the surrogate from [25], which employs an integral kernel with sampling size $m = {40}$ . Due to its $O\left( {{MN}{m}^{2}}\right)$ complexity,we set the sampling size $m = {40}$ to ensure a similar complexity as ours.
uGP(40)是文献[25]提出的代理模型，采用积分核函数且采样大小为 $m = {40}$ 。由于其 $O\left( {{MN}{m}^{2}}\right)$ 的复杂度，我们将采样大小设为 $m = {40}$ 以保持与我们的方法相近的复杂度。
uGP(160) is also the surrogate from [25] but uses a much larger sampling size $\left( {m = {160}}\right)$ . Given the same training and testing samples, its complexity is 16 times higher than MMDGP-nystrom(160/10).
uGP(160)同样来自文献[25]，但采用更大的采样规模 $\left( {m = {160}}\right)$ 。在相同训练和测试样本条件下，其复杂度比 MMDGP-nystrom(160/10)高出 16 倍。
skl is a robust GP surrogate equipped with a symmetric KL-based kernel, which is described in [20].
skl 是配备对称 KL 核的鲁棒高斯过程代理模型，具体描述见文献[20]。
ERBF [13] assumes the input uncertainty to be Gaussians and employs a close-form expected RBF kernel.
ERBF [13] 假设输入不确定性服从高斯分布，并采用闭式期望 RBF 核进行计算。

Figure 8: Ablation test for the Nyström approximation.
图 8：Nyström 近似法的消融测试结果。

GP utilizes a noisy Gaussian Process model with a learnable output noise level. According to Figure 7a, our method, MMDGP-nystrom(160/10), can comprehensively quantify the sudden change of the input uncertainty,evidenced by its abrupt posterior change at $x = {0.6}$ . However, Figure 7b shows that uGP(40) with the same complexity fails to model the uncertainty correctly. We suspect this is because uGP requires much larger samples to stabilize its estimation of the integral kernel and thus can perform poorly with insufficient sample size, so we further evaluate the uGP(160) with a much larger sampling size $m = {160}$ in Figure 7c. It does successfully alleviate the issue but also results in a 16 times higher complexity. Apart from this, Figure 7d suggests the noisy GP model with a learnable output noise level is not aware of this uncertainty change at all as it treats the inputs as the exact values instead of random variables. Moreover, Figure 7e and 7f show that both the skl and ERBF fail in this case, this may be due to their misassumption of Gaussian input uncertainty.
高斯过程（GP）采用带有可学习输出噪声水平的含噪高斯过程模型。根据图 7a 所示，我们的方法 MMDGP-nystrom(160/10)能够全面量化输入不确定性的突变，这体现在其 $x = {0.6}$ 处的后验概率突然变化上。然而图 7b 显示，相同复杂度的 uGP(40)无法正确建模这种不确定性。我们推测这是因为 uGP 需要更大的样本量来稳定其积分核估计，因此在样本不足时表现欠佳，为此我们在图 7c 中进一步评估了采样量大幅增加的 uGP(160) $m = {160}$ 。该方法虽成功缓解了问题，但复杂度也相应增加了 16 倍。此外，图 7d 表明具有可学习输出噪声水平的含噪 GP 模型完全未能感知这种不确定性变化，因其将输入视为确定值而非随机变量。图 7e 和 7f 则显示 skl 与 ERBF 方法在此案例中均告失败，这可能是由于它们对高斯输入不确定性的错误假设所致。

D.2 Ablation Test for Nyström Approximation
D.2 尼斯特罗姆近似消融实验

In this experiment, we aim to examine the effect of Nyström approximation for optimization. To this end, we choose to optimize an RKHS function (Figure 4a) under a beta input distribution: ${P}_{x} =$ beta $\left( {\alpha = {0.4},\beta = {0.2},\sigma = {0.1}}\right)$ . Several amortized candidates include:
本实验旨在检验 Nyström 近似对优化效果的影响。为此，我们选择在贝塔输入分布 ${P}_{x} =$ beta $\left( {\alpha = {0.4},\beta = {0.2},\sigma = {0.1}}\right)$ 下优化 RKHS 函数（图 4a）。采用的几种摊销候选方案包括：

MMDGP-nystrom is our method with Nystrom approximation, in which the sampling size $m = {16}$ and sub-sampling size $h = 9$ . Its complexity is $O\left( {MNmh}\right)$ ,where $M$ and $N$ are the sizes of training and test samples respectively, $m$ is the sampling size for MMD estimation,and $h$ indicates the sub-sampling size during the Nystrom approximation.
MMDGP-nystrom 是我们采用 Nystrom 近似的方法，其中采样规模 $m = {16}$ 与子采样规模 $h = 9$ 。其复杂度为 $O\left( {MNmh}\right)$ ，这里 $M$ 和 $N$ 分别表示训练样本与测试样本的规模， $m$ 指代 MMD 估计时的采样规模，而 $h$ 表示 Nystrom 近似过程中的子采样规模。
MMDGP-raw- $S$ does not use the Nystrom approximation but employs an empirical MMD estimator. Due to its $O\left( {{MN}{m}^{2}}\right)$ complexity,we set the sampling size $m = {12}$ to ensure a similar complexity as the MMDGP-nystrom.
MMDGP-raw- $S$ 未采用 Nystrom 近似，而是使用经验 MMD 估计器。由于其 $O\left( {{MN}{m}^{2}}\right)$ 的复杂度，我们将采样规模设为 $m = {12}$ 以确保与 MMDGP-nystrom 保持相近复杂度。
MMDGP-raw-L also uses an empirical MMD estimator, but with a larger sampling size $\left( {m = {16}}\right)$ .
MMDGP-raw-L 同样采用经验 MMD 估计器，但使用更大的采样规模 $\left( {m = {16}}\right)$ 。
${GP}$ utilizes a vanilla $\mathrm{{GP}}$ with a learnable output noise level and optimizes with the upper-confidence-bound acquisition ${}^{2}$ .
${GP}$ 采用了一个可学习输出噪声水平的普通 $\mathrm{{GP}}$ ，并使用置信上限获取函数 ${}^{2}$ 进行优化。

According to Figure 8, we find that 1) with sufficient computation power, the MMDGP-raw-L can obtain the best performance by using a large sample size. 2)However, with limited complexity, the performance ${MMDGP}$ -raw-S degrades obviously while the ${MMDGP}$ -nystrom performs much better. This suggests that the Nyström approximation can significantly improve the efficiency with a mild cost of performance degradation. 3) All the MMDGP-based methods are better than the vanilla ${GP} - {UCB}$ .
根据图 8 所示，我们发现：1）在计算资源充足的情况下，MMDGP-raw-L 通过使用大样本量能获得最佳性能；2）然而在复杂度受限时， ${MMDGP}$ -raw-S 的性能明显下降，而 ${MMDGP}$ -nystrom 表现更为优异，这表明 Nyström 近似能以轻微的性能下降为代价显著提升效率；3）所有基于 MMDGP 的方法都优于普通 ${GP} - {UCB}$ 。

D.3 Optimization on 10D Bumped-Bowl Problem
D.3 10 维凸包问题的优化

To further evaluate AIRBO's optimization performance on the high-dimensional problem, we employ a 10-dimensional bumped bowl function from [27, 19]:
为了进一步评估 AIRBO 在高维问题上的优化性能，我们采用了文献[27,19]中的 10 维凸包函数：

f\left( \mathbf{x}\right) = g\left( {\mathbf{x}}_{1 : 2}\right) h\left( {\mathbf{x}}_{3 : }\right) \text{,where}\left\{ \begin{array}{l} g\left( \mathbf{x}\right) = 2\log \left( {{0.8}\parallel \mathbf{x}{\parallel }^{2} + {e}^{-{10}\parallel \mathbf{x}{\parallel }^{2}}}\right) + {2.54} \\ h\left( \mathbf{x}\right) = \mathop{\sum }\limits_{i}^{d}5{x}_{i}^{2} + 1 \end{array}\right. \tag{33}

${}^{2}$ For a fair comparison,all the methods in this test use a UCB acquisition.
${}^{2}$ 为确保公平比较，本次测试中所有方法均采用 UCB 采集函数。

Figure 9: Optimization regret on 10D bumped-bowl problem.
图 9：10 维凸碗问题上的优化遗憾值。

Figure 10: The input GMM distribution.
图 10：输入的高斯混合模型分布。

Figure 11: Simulation results of the push configurations found by different algorithms.
图 11：不同算法发现的推送配置仿真结果。

Here, ${x}_{i}$ is the i-th dimension of $\mathbf{x},{\mathbf{x}}_{1 : 2}$ represents the first 2 dimensions for the variable,and ${\mathbf{x}}_{3}$ : indicates the rest dimensions. The input uncertainty is designed to follow a concatenated distribution of a 2D circular distribution $\left( {r = {0.5}}\right)$ and a multivariate normal distribution with a zero mean and diagonal covariance of 0.01 .
此处， ${x}_{i}$ 表示变量 $\mathbf{x},{\mathbf{x}}_{1 : 2}$ 的第 i 个维度，其中前两个维度由 $\mathbf{x},{\mathbf{x}}_{1 : 2}$ 表示，而 ${\mathbf{x}}_{3}$ 则代表其余维度。输入不确定性被设计为遵循一个由二维圆形分布 $\left( {r = {0.5}}\right)$ 与均值为零、对角线协方差为 0.01 的多元正态分布拼接而成的联合分布。

Figure 9 shows the mean and std values of the optimization regrets. We note that 1) when it comes to a high-dimensional problem and complex input distribution, the misassumption of Gaussian input uncertainty renders the ${skl}$ and ${ERBF}$ fail to locate the robust optimum and get stuck at local optimums. 2)Our method outperforms the others and can find the robust optimum efficiently and stably, while the ${uGP}$ with a similar inference cost suffers the instability caused by insufficient sampling and stumbles over iterations, which can be evidenced by its high std values of optimization regret.
图 9 展示了优化遗憾值的均值与标准差。我们注意到：1）当面临高维问题及复杂输入分布时，对高斯输入不确定性的错误假设会导致 ${skl}$ 和 ${ERBF}$ 无法定位鲁棒最优解，并陷入局部最优；2）我们的方法表现优于其他方法，能高效稳定地找到鲁棒最优解，而具有相似推理成本的 ${uGP}$ 由于采样不足导致的不稳定性，在迭代过程中表现波动，这从其较高的优化遗憾标准差值中可以得到验证。

D.4 Robust Robot Pushing
D.4 鲁棒机器人推挤实验

This benchmark is based on a Box2D simulator from [31], where our objective is to identify a robust push configuration, enabling a robot to push a ball to predetermined targets under input randomness. In our experiment,we simplify the task by setting the push angle to ${r}_{a} = \arctan \frac{{r}_{u}}{{r}_{v}}$ ,ensuring the robot is always facing the ball. Also, we intentionally define the input distribution as a two-component Gaussian Mixture Model as follows:
该基准测试基于[31]中的 Box2D 模拟器，我们的目标是找到一个稳健的推动配置，使机器人能在输入随机性的条件下将球推向预定目标。实验中我们将推动角度简化为 ${r}_{a} = \arctan \frac{{r}_{u}}{{r}_{v}}$ ，确保机器人始终正对球体。同时，我们特意将输入分布定义为如下双组分高斯混合模型：

\left( {{r}_{x},{r}_{y},{r}_{t}}\right) \sim {GMM}\left( {\mu = \left\lbrack \begin{matrix} 0 & 0 & 0 \\ - 1 & 1 & 0 \end{matrix}\right\rbrack ,}\right. ,\mathbf{\sum } = \left\lbrack \begin{matrix} {0.1}^{2} & - {0.3}^{2} & {1e} - 6 \\ - {0.3}^{2} & {0.1}^{2} & {1e} - 6 \\ {1e} - 6 & {1e} - 6 & {1.0}^{2} \end{matrix}\right\rbrack ,w = \left\lbrack \begin{array}{l} {0.5} \\ {0.5} \end{array}\right\rbrack , \tag{34}

where the covariance matrix $\sum$ is shared among components and $w$ is the weights of mixture components. Meanwhile, as the SKL-UCB and ERBF-UCB surrogates can only accept Gaussian input distributions, we choose to approximate the true input distribution with a Gaussian. As shown in Figure 10, the approximation error is obvious, which explains the performance gap among these algorithms in Figure 5b.
其中协方差矩阵 $\sum$ 在各组分间共享， $w$ 表示混合组分的权重。由于 SKL-UCB 和 ERBF-UCB 代理模型仅能接受高斯输入分布，我们选择用高斯分布来近似真实输入分布。如图 10 所示，这种近似存在明显误差，这也解释了图 5b 中这些算法间的性能差距。

Apart from the statistics of the found pre-images in Figure 6, we also simulate the robot pushes according to the found configurations and visualize the results in Figure 11. In this figure, each black hollow square represents an instance of the robot's initial location, the grey arrow indicates the push direction and duration, and the blue circle marks the ball's ending position after the push. We can find that, as the GP-UCB ignores the input uncertainty, it randomly pushes to these targets and the ball ending positions fluctuate. Also, due to the incorrect assumption of the input distribution, the SKL-UCB and ERBF-UCB fail to control the ball's ending position under input randomness. On the contrary, AIRBO successfully recognizes the twin targets in quadrant I as an optimal choice and frequently pushes to this area. Moreover, all the ball's ending positions are well controlled and centralized around the targets under input randomness.
除图 6 中统计的预映射发现结果外，我们还根据寻得的配置参数模拟了机器人推球动作，并将可视化结果呈现在图 11 中。该图中每个黑色空心方块代表机器人初始位置的一个实例，灰色箭头表示推动方向与持续时间，蓝色圆圈则标记推动后小球的终止位置。可以发现：由于 GP-UCB 忽略了输入不确定性，其推送目标具有随机性，导致小球终止位置呈现波动状态；同时由于对输入分布的错误假设，SKL-UCB 和 ERBF-UCB 在输入随机性下均无法有效控制小球终止位置。与之形成鲜明对比的是，AIRBO 成功识别出第一象限的双目标区域作为最优选择，并频繁向该区域推送。更重要的是，在输入随机性条件下，所有小球终止位置均得到精准控制，紧密聚集在目标区域周围。

Efficient Robust Bayesian Optimization for Arbitrary Uncertain Inputs高效鲁棒贝叶斯优化算法应对任意不确定输入

Abstract 摘要

1 Introduction 1 引言

2 Problem Formulation 2 问题表述

2.1 Optimization with Input Uncertainty2.1 含输入不确定性的优化

2.2 Bayesian Optimization2.2 贝叶斯优化

3 Proposed Method 3 研究方法

3.1 Modeling the Uncertain Inputs3.1 不确定输入建模

3.2 Boosting posterior inference with Nyström Approximation3.2 利用 Nyström 近似加速后验推断

4 Theoretical Analysis 第四章 理论分析

5 Evaluation 5 评估

5.1 Robust Surrogate 5.1 鲁棒代理模型

5.2 Accelerating the Posterior Inference5.2 加速后验推断

5.3 Robust Optimization 5.3 鲁棒优化

6 Discussion and Conclusion6 讨论与结论

7 Acknowledgements 7 致谢

A Nyström Estimator Error Bound尼斯特伦估计量误差界

B Proofs of Section 4B 第 4 节证明

B.1 Exact Kernel Uncertainty GP FormulatingB.1 精确核不确定性高斯过程建模

B.2 Error Estimates for Inexact Kernel ApproximationB.2 非精确核近似的误差估计

B.3 Proofs for Theorem 1B.3 定理 1 的证明

B.4 Proofs for Theorem 2B.4 定理 2 的证明

C Evaluation Details C 评估细节

C.1 Implementation C.1 实现方案

D More Experiments D 补充实验

D.1 Comparing with the Other ModelsD.1 与其他模型的对比

D.2 Ablation Test for Nyström ApproximationD.2 尼斯特罗姆近似消融实验

D.3 Optimization on 10D Bumped-Bowl ProblemD.3 10 维凸包问题的优化

D.4 Robust Robot PushingD.4 鲁棒机器人推挤实验

Efficient Robust Bayesian Optimization for Arbitrary Uncertain Inputs
高效鲁棒贝叶斯优化算法应对任意不确定输入

2.1 Optimization with Input Uncertainty
2.1 含输入不确定性的优化

2.2 Bayesian Optimization
2.2 贝叶斯优化

3.1 Modeling the Uncertain Inputs
3.1 不确定输入建模

3.2 Boosting posterior inference with Nyström Approximation
3.2 利用 Nyström 近似加速后验推断

4 Theoretical Analysis 第四章理论分析

5.2 Accelerating the Posterior Inference
5.2 加速后验推断

6 Discussion and Conclusion
6 讨论与结论

A Nyström Estimator Error Bound
尼斯特伦估计量误差界

B Proofs of Section 4
B 第 4 节证明

B.1 Exact Kernel Uncertainty GP Formulating
B.1 精确核不确定性高斯过程建模

B.2 Error Estimates for Inexact Kernel Approximation
B.2 非精确核近似的误差估计

B.3 Proofs for Theorem 1
B.3 定理 1 的证明

B.4 Proofs for Theorem 2
B.4 定理 2 的证明

D.1 Comparing with the Other Models
D.1 与其他模型的对比

D.2 Ablation Test for Nyström Approximation
D.2 尼斯特罗姆近似消融实验

D.3 Optimization on 10D Bumped-Bowl Problem
D.3 10 维凸包问题的优化

D.4 Robust Robot Pushing
D.4 鲁棒机器人推挤实验