High Dimensional Bayesian Optimization Using Dropout
高维贝叶斯优化中的 Dropout 应用

Cheng Li, Sunil Gupta, Santu Rana, Vu Nguyen, Svetha Venkatesh, Alistair Shilton
李成、Sunil Gupta、Santu Rana、Vu Nguyen、Svetha Venkatesh、Alistair Shilton

Centre for Pattern Recognition and Data Analytics (PRaDA), Deakin University, Australia cheng.1@deakin.edu.au
澳大利亚迪肯大学模式识别与数据分析中心(PRaDA)，邮箱：cheng.1@deakin.edu.au

Scaling Bayesian optimization to high dimensions is challenging task as the global optimization of high-dimensional acquisition function can be expensive and often infeasible. Existing methods depend either on limited "active" variables or the additive form of the objective function. We propose a new method for high-dimensional Bayesian optimization, that uses a dropout strategy to optimize only a subset of variables at each iteration. We derive theoretical bounds for the regret and show how it can inform the derivation of our algorithm. We demonstrate the efficacy of our algorithms for optimization on two benchmark functions and two real-world applications - training cascade classifiers and optimizing alloy composition.
将贝叶斯优化扩展至高维环境面临重大挑战，因为高维采集函数的全局优化计算成本高昂且常不可行。现有方法要么依赖有限的“活跃”变量，要么基于目标函数的加性形式。我们提出了一种新的高维贝叶斯优化方法，采用 Dropout 策略在每次迭代中仅优化部分变量。我们推导了遗憾的理论界限，并展示了其如何指导算法设计。通过两个基准函数优化及两个实际应用（级联分类器训练与合金成分优化），验证了所提算法的有效性。

From mixture products (e.g. shampoos, alloys) to processes for mixture (e.g. heat treatments for alloys), the need to find the optimal values of control variables to achieve a target product lies at the heart of most industrial processes. The complexity arises because we do not know the mathematical relationship between the control variables and the target - it is a Black-Box Function. This exploration done through experimental optimization is a laborious process and limited by resource restrictions and cost.
从混合物产品（如洗发水、合金）到混合工艺（如合金的热处理），寻找控制变量的最优值以实现目标产品是大多数工业流程的核心。复杂性源于我们不清楚控制变量与目标之间的数学关系——这是一个黑箱函数。通过实验优化进行的这种探索是一个费力的过程，并受到资源限制和成本的制约。

The process of experimental optimization quickly hits limit as soon as the number of control variables are increased. For example, since the Bronze Age, fewer than 12 elements have been combined to make alloys. But the periodic table contains 97 naturally occurring elements. Only a tiny fraction of the target space has been explored because of the underlying complexity. By increasing the number of elements to just 15 in order to find a high-strength alloy with 3 mixing levels per element, the search space escalates to more than 14 million choices [Xue et al., 2016]. Another illustrative problem is that wing configuration design of a high speed civil transport (HSCT) aircraft may include upto 26 variables to reach a targeted wing configuration [Koch et al., 1999].
实验优化过程在控制变量数量增加时很快达到极限。例如，自青铜时代以来，用于制造合金的元素组合不超过 12 种。然而，元素周期表中天然存在的元素多达 97 种。由于潜在的复杂性，仅探索了目标空间的极小部分。若将元素数量增至 15 种以寻找每种元素 3 种混合比例的高强度合金，搜索空间会激增至超过 1400 万种选择[Xue 等人，2016]。另一个例证是，高速民用运输机(HSCT)的机翼构型设计可能涉及多达 26 个变量才能达到目标机翼配置[Koch 等人，1999]。

Bayesian optimization (BO) [Snoek et al., 2012; Nguyen et al., 2016] is a powerful technique to optimize expensive, black-box functions. A classical BO uses Gaussian process (GP) [Rasmussen and Williams, 2005] to model the mean and variance of the target function. As the function is expensive to interrogate, a surrogate function (or acquisition function) is constructed from the GP to trade-off exploitation (where mean is high) and exploration (where uncertainty is high). The next sample is determined by maximizing the acquisition function. Scaling BO methods to handle functions in high dimension presents two main challenges. Firstly, the number of observations required by the GP grows exponentially as input dimensions increase. This implies more experimental evaluations are required, often expensive and infeasible in real applications. Secondly, global optimization for high-dimensional acquisition functions is intrinsically a hard problem and can be prohibitively expensive to be feasible [Kan-dasamy et al., 2015; Rana et al., 2017].
贝叶斯优化（BO）[Snoek 等人，2012；Nguyen 等人，2016]是一种优化昂贵黑盒函数的强大技术。经典 BO 使用高斯过程（GP）[Rasmussen 和 Williams，2005]来建模目标函数的均值和方差。由于函数评估成本高昂，通常基于 GP 构建替代函数（或称采集函数），以权衡开发（均值较高区域）与探索（不确定性较高区域）。下一个采样点通过最大化采集函数来确定。将 BO 方法扩展到高维函数时面临两大挑战：首先，GP 所需的观测数量随输入维度增加呈指数级增长，这意味着需要更多实验评估，而这在实际应用中往往成本高昂且难以实现；其次，高维采集函数的全局优化本身是一个难题，其计算成本可能高到无法承受[Kan-dasamy 等人，2015；Rana 等人，2017]。

Solutions have been proposed to tackle high-dimensional Bayesian optimization. Wang et al. [2013] projected the high-dimensional space into a low-dimensional subspace and then optimized the acquisition function in a low-dimensional subspace (REMBO). The assumption that only some dimensions $\left(d_e\ll D\right)$ are effective is often restrictive. Qian et al. [2016] studied the case when all dimensions are effective, but many of them only have a small bounded effect by using sequential random embedding to reduce the embedding gap. These methods may not work if all dimensions in the high-dimensional function are similarly effective. The additive decomposition assumption is another solution for high-dimensional function analysis. Kandasamy et al. [2015] proposed the Add-GP-UCB model in which the objective function is assumed to be the sum of a set of low-dimensional functions with disjoint dimensions and then BO can be performed in the low-dimensional space. Add-GP-UCB allows the objective function to vary along the entire feature domain. Li et al. [2016] generalized the Add-GP-UCB by eliminating an axis-aligned representation. However, in practice it is difficult to know the decomposition of functions in advance, especially for non-separable functions. The most related one to our work is DSA [Ulmasov et al., 2016], which reduces the number of variables at each iteration by PCA. There are two problems when using DSA: (1) using PCA for selecting variables is effective only when there are large number of data points. This is especially not true for Bayesian optimization where in the beginning we do not have many points. Eigen vector estimation using small number of data points are often inaccurate and can be misleading. (2) DSA may get stuck in a local optimum since it only clamps the other coordinates to their current best values.
已有多种解决方案被提出以应对高维贝叶斯优化问题。Wang 等人[2013]将高维空间投影至低维子空间，随后在低维子空间中优化采集函数（REMBO）。但"仅部分维度 $\left(d_e\ll D\right)$ 有效"的假设往往具有局限性。Qian 等人[2016]研究了所有维度均有效但多数仅具微弱边界效应的情况，通过序列随机嵌入降低嵌入间隙。若高维函数中所有维度均具有相似效力，这些方法可能失效。加性分解假设是分析高维函数的另一解决方案。Kandasamy 等人[2015]提出 Add-GP-UCB 模型，该模型假设目标函数为若干互斥维度的低维函数之和，从而可在低维空间执行贝叶斯优化。Add-GP-UCB 允许目标函数在整个特征域上变化。Li 等人[2016]通过消除轴对齐表示对 Add-GP-UCB 进行了推广。 然而，在实践中，尤其是对于不可分离的函数，提前了解函数的分解情况十分困难。与我们的工作最为相关的是 DSA [Ulmasov et al., 2016]，该方法通过 PCA 在每次迭代中减少变量数量。使用 DSA 时存在两个问题：（1）仅当数据点数量庞大时，利用 PCA 选择变量才有效。这在贝叶斯优化初期尤为不适用，因为初始阶段数据点较少。基于少量数据点估计的特征向量往往不准确且可能产生误导。（2）DSA 可能陷入局部最优解，因为它仅将其他坐标固定为其当前最佳值。

This paper proposes an alternative approach that does not rely on the assumptions that the objective function depends on limited "active" features - projections can be made into lower dimensional sub-spaces (fixed [Djolonga et al., 2013; Wang et al., 2013] or updated [Ulmasov et al., 2016]) or objective function decomposed in additive forms [Kandasamy et al., 2015; Li et al., 2016]. Motivated by the dropout algorithm in neural networks [Srivastava et al., 2014], we explore dimension dropout in high-dimensional Bayesian optimization. We choose $d$ out of $D$ dimensions $\left(d<D\right)$ randomly at each iteration and only optimize variables from the chosen dimensions via Bayesian optimization. To "fill-in" the variables from the left-out dimensions, we consider alternate strategies - random values, values of these variables from the best found function value thus far, and a mixture of these two methods. We formulate our dropout algorithms and apply them on benchmark functions and two real-world applications of training cascade classifiers [Viola and Jones, 2001] and an aluminium alloy design. We compare them with baselines ( random search, standard BO, REMBO [Wang et al., 2013] and Add-GP-UCB [Kandasamy et al., 2015] ). The experimental results demonstrate the effectiveness of our algorithms. We derive regret bound theoretically. As expected the cost of Dropout algorithm is a remaining "regret gap", and we provide insights to how this gap can be reduced through the strategies we have formulated to fill-in the dropped-out variables. Our main contributions are:
本文提出了一种不依赖于目标函数仅受限于少数"活跃"特征假设的替代方法——可将投影降至低维子空间（固定维度如[Djolonga et al., 2013; Wang et al., 2013]或动态更新如[Ulmasov et al., 2016]），或将目标函数分解为加性形式[Kandasamy et al., 2015; Li et al., 2016]。受神经网络中 dropout 算法[Srivastava et al., 2014]启发，我们探索高维贝叶斯优化中的维度丢弃策略：每次迭代随机从 $D$ 个维度中选取 $d$ 个维度，仅通过贝叶斯优化调整选定维度的变量。针对未选中维度的变量填补，我们研究了三种策略——随机赋值、沿用当前最优解对应变量值，以及两种策略的混合方法。我们构建了 dropout 算法框架，并在基准测试函数、级联分类器训练[Viola and Jones, 2001]和铝合金设计两个实际应用中进行了验证。 我们将其与基线方法（随机搜索、标准贝叶斯优化、REMBO [Wang et al., 2013] 和 Add-GP-UCB [Kandasamy et al., 2015]）进行对比。实验结果证明了我们算法的有效性。我们从理论上推导了遗憾界。正如预期，Dropout 算法的代价是存在一个残余的“遗憾间隙”，我们通过提出的填补丢弃变量的策略，深入分析了如何缩小这一间隙。我们的主要贡献包括：

Preliminaries Bayesian optimization is used to maximize or minimize a function $f$ in the input domain $\mathcal{X}\subseteq {\mathbb{R}}^D$ . It includes two critical components: prior and acquisition functions. Gaussian process (GP) is a popular choice for the prior due to its tractability for posterior and predictive distributions and it is specified by its mean $m\left(\text{.}\right)andcovariancekernel$ function $k\left(.,\right)$ . Give a set of observations ${\mathbf{x}}_{1:t}$ and the corresponding values $\mathbf{f}\left({\mathbf{x}}_{1:t}\right)$ ,the probability of any finite set of $\mathbf{f}$ is Gaussian
预备知识 贝叶斯优化用于在输入域 $\mathcal{X}\subseteq {\mathbb{R}}^D$ 中最大化或最小化函数 $f$ 。它包含两个关键组件：先验和采集函数。高斯过程（GP）因其后验和预测分布的可处理性而成为先验的流行选择，并通过其均值 $m\left(\text{.}\right)andcovariancekernel$ 函数 $k\left(.,\right)$ 来指定。给定一组观测值 ${\mathbf{x}}_{1:t}$ 及其对应值 $\mathbf{f}\left({\mathbf{x}}_{1:t}\right)$ ，任何有限集 $\mathbf{f}$ 的概率服从高斯分布。

where $\mathbf{K}{(\mathbf{x},{\mathbf{x}}^{\prime })}_{i,j}=k\left({\mathbf{x}}_i,{\mathbf{x}}_j^{\prime }\right)$ is the covariance matrix. Two popular choice of $k$ are the squared exponential (SE) kernel and the Matérn kernel. The predictive distribution of a new point ${\mathbf{x}}_{t+1}$ is given as
其中 $\mathbf{K}{(\mathbf{x},{\mathbf{x}}^{\prime })}_{i,j}=k\left({\mathbf{x}}_i,{\mathbf{x}}_j^{\prime }\right)$ 是协方差矩阵。 $k$ 的两种流行选择是平方指数（SE）核和 Matérn 核。新点 ${\mathbf{x}}_{t+1}$ 的预测分布由下式给出：

(2)where ${\mathbf{f}}_{1:t}=\mathbf{f}\left({\mathbf{x}}_{1:t}\right),{\mu }_{t+1}\left(\text{.}\right)={\mathbf{k}}^T{\mathbf{K}}^{-1}{\mathbf{f}}_{1:t}$ , ${\sigma }_{t+1}^2(.)=k\left({\mathbf{x}}_{t+1},{\mathbf{x}}_{t+1}\right)-{\mathbf{k}}^T{\mathbf{K}}^{-1}\mathbf{k}$ and $\mathbf{k}=$ $\left[k\left({\mathbf{x}}_{t+1},{\mathbf{x}}_1\right),\cdots ,k\left({\mathbf{x}}_{t+1},{\mathbf{x}}_t\right)\right]$ .
（2）其中 ${\mathbf{f}}_{1:t}=\mathbf{f}\left({\mathbf{x}}_{1:t}\right),{\mu }_{t+1}\left(\text{.}\right)={\mathbf{k}}^T{\mathbf{K}}^{-1}{\mathbf{f}}_{1:t}$ 、 ${\sigma }_{t+1}^2(.)=k\left({\mathbf{x}}_{t+1},{\mathbf{x}}_{t+1}\right)-{\mathbf{k}}^T{\mathbf{K}}^{-1}\mathbf{k}$ 和 $\mathbf{k}=$ $\left[k\left({\mathbf{x}}_{t+1},{\mathbf{x}}_1\right),\cdots ,k\left({\mathbf{x}}_{t+1},{\mathbf{x}}_t\right)\right]$ 。

Acquisition function is a proxy function derived from the predictive mean and variance and it determines the next sample point. We denote acquisition function $a\left(\mathbf{x}\mid \left\{{\mathbf{x}}_{1:t},f_{1:t}\right\}\right)$ and the next sample point ${\mathbf{x}}_{t+1}={\mathrm{argmax}}_{\mathbf{x}\in \mathcal{X}}a(\mathbf{x}\mid$ $\left\{{\mathbf{x}}_{1:t},f_{1:t}\right\})$ . Some examples of acquisition functions include Expected Improvement (EI) and GP-UCB [Srinivas et al., 2010]. The EI-based acquisition function is to compute the expected improvement with respect to the current maximum $f\left({\mathbf{x}}^{+}\right)$ ,or $\mathbf{E}\mathbf{I}\left(\mathbf{x}\right)=\mathbb{E}(max\left\{0,f_{t+1}\left(\mathbf{x}\right)-f\left({\mathbf{x}}^{+}\right)\right\}$ ${\mathbf{x}}_{1:t},{\mathbf{f}}_{1:t}$ ). The closed form has been derived in [Mockus et al., 1978; Jones et al., 1993]. The GP-UCB [Srinivas et al., 2010] is defined as $\mathrm{UCB}\left(\mathbf{x}\right)=\mu \left(\mathbf{x}\right)+\sqrt{\beta }\sigma \left(\mathbf{x}\right)$ ,where $\beta$ is a positive tradeoff. The first term contributes to the exploitation and the second term contributes to the exploration. DIRECT [Jones et al., 1993] is often used to find the global maximum in acquisition function.
采集函数是从预测均值和方差中派生出的代理函数，它决定了下一个采样点。我们将采集函数记为 $a\left(\mathbf{x}\mid \left\{{\mathbf{x}}_{1:t},f_{1:t}\right\}\right)$ ，下一个采样点记为 ${\mathbf{x}}_{t+1}={\mathrm{argmax}}_{\mathbf{x}\in \mathcal{X}}a(\mathbf{x}\mid$ $\left\{{\mathbf{x}}_{1:t},f_{1:t}\right\})$ 。采集函数的例子包括期望改进（EI）和 GP-UCB [Srinivas 等人，2010]。基于 EI 的采集函数旨在计算相对于当前最大值 $f\left({\mathbf{x}}^{+}\right)$ 或 $\mathbf{E}\mathbf{I}\left(\mathbf{x}\right)=\mathbb{E}(max\left\{0,f_{t+1}\left(\mathbf{x}\right)-f\left({\mathbf{x}}^{+}\right)\right\}$ ${\mathbf{x}}_{1:t},{\mathbf{f}}_{1:t}$ 的期望改进量。其闭式解已在[Mockus 等人，1978; Jones 等人，1993]中给出。GP-UCB [Srinivas 等人，2010]定义为 $\mathrm{UCB}\left(\mathbf{x}\right)=\mu \left(\mathbf{x}\right)+\sqrt{\beta }\sigma \left(\mathbf{x}\right)$ ，其中 $\beta$ 为正权衡参数。第一项促进利用，第二项促进探索。DIRECT [Jones 等人，1993]常用于寻找采集函数中的全局最大值。

We seek to maximize a function $f$ in the restricted domain $\mathcal{X}={[0,1]}^D$ (this can always be achieved by scaling). We assume the maximal function value can be achieved at a query point ${\mathbf{x}}^{\ast }$ ,i.e. ${\mathbf{x}}^{\ast }={\mathrm{argmax}}_{\mathbf{x}\in \mathcal{X}}f\left(\mathbf{x}\right)$ . At iteration $t$ and the corresponding query point ${\mathbf{x}}_t\in \mathcal{X}$ ,the instantaneous regret $r_t$ is defined $r_t=f\left({\mathbf{x}}^{\ast }\right)-f\left({\mathbf{x}}_t\right)$ and the cumulative regret $R_T$ is defined $R_T=\sum _{t=1}^T{r}_t$ . A desirable property of an algorithm is to have no-regret: $\underset{T\to \mathrm{\infty }}{lim}\frac{1}{T}{R}_T=0$ .
我们寻求在限定域 $\mathcal{X}={[0,1]}^D$ 内最大化函数 $f$ （总可通过缩放实现）。假设最大函数值可在查询点 ${\mathbf{x}}^{\ast }$ 处达到，即 ${\mathbf{x}}^{\ast }={\mathrm{argmax}}_{\mathbf{x}\in \mathcal{X}}f\left(\mathbf{x}\right)$ 。在第 $t$ 次迭代及对应查询点 ${\mathbf{x}}_t\in \mathcal{X}$ 时，瞬时遗憾 $r_t$ 定义为 $r_t=f\left({\mathbf{x}}^{\ast }\right)-f\left({\mathbf{x}}_t\right)$ ，累积遗憾 $R_T$ 定义为 $R_T=\sum _{t=1}^T{r}_t$ 。算法的理想特性是无遗憾性： $\underset{T\to \mathrm{\infty }}{lim}\frac{1}{T}{R}_T=0$ 。

Dropout Algorithms We refer to $I_d$ as the indices of $d$ out of $D$ dimensions and $I_{D-d}$ as the indices of the left-out $D-d$ dimensions so that $I_d\cup I_{D-d}=\{1,\cdots ,D\}$ and $I_{D-d}\cap I_d=$ . The corresponding variables from $I_d$ and $I_{D-d}$ dimensions are respectively denoted as ${\mathbf{x}}^{I_d}$ and ${\mathbf{x}}^{I_{D-d}}$ . For the convenience we later use ${\mathbf{x}}^d={\mathbf{x}}^{I_d},{\mathbf{x}}^{D-d}={\mathbf{x}}^{I_{D-d}}$ and hence $\mathbf{x}=\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]$ .
我们称 $I_d$ 为从 $d$ 个维度中选出的 $D$ 维度的索引， $I_{D-d}$ 为被排除的 $D-d$ 维度的索引，因此 $I_d\cup I_{D-d}=\{1,\cdots ,D\}$ 且 $I_{D-d}\cap I_d=$ 。对应的变量分别来自 $I_d$ 和 $I_{D-d}$ 维度，记为 ${\mathbf{x}}^{I_d}$ 和 ${\mathbf{x}}^{I_{D-d}}$ 。为方便起见，后续我们使用 ${\mathbf{x}}^d={\mathbf{x}}^{I_d},{\mathbf{x}}^{D-d}={\mathbf{x}}^{I_{D-d}}$ ，因此 $\mathbf{x}=\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]$ 。

Motivated by the dropout algorithm in neural networks [Srivastava et al., 2014], we explore dimension dropout for high-dimensional Bayesian optimization. We randomly choose $d$ out of $D$ dimensions $\left(d<D\right)$ at each iteration and only optimize the $d$ -dimensional variables through Bayesian optimization. Specifically we assume in the $d$ -dimensional space the observations $y=f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]\right)+\epsilon$ with $\epsilon \sim$ $\mathcal{N}\left(0,{\sigma }^2\right)$ for all ${\mathbf{x}}^{D-d}$ . Gaussian process then is used to model the function values $f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]\right),\mathrm{\forall }{\mathbf{x}}^{D-d}$ . The predictive mean $\mu \left({\mathbf{x}}^d\right)$ and variance $\sigma \left({\mathbf{x}}^d\right)$ can be computed. As with GP-UCB [Srinivas et al., 2010], we construct the acquisition function in the $d$ -dimensional space
受神经网络中 Dropout 算法[Srivastava 等人，2014]的启发，我们探索了高维贝叶斯优化中的维度丢弃策略。每次迭代时，我们随机从 $D$ 个维度中选取 $d$ 个维度 $\left(d<D\right)$ ，仅通过贝叶斯优化对 $d$ 维变量进行优化。具体而言，在 $d$ 维空间中，假设观测值 $y=f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]\right)+\epsilon$ 满足对所有 ${\mathbf{x}}^{D-d}$ 有 $\epsilon \sim$ $\mathcal{N}\left(0,{\sigma }^2\right)$ 。随后使用高斯过程对函数值 $f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]\right),\mathrm{\forall }{\mathbf{x}}^{D-d}$ 建模，可计算预测均值 $\mu \left({\mathbf{x}}^d\right)$ 和方差 $\sigma \left({\mathbf{x}}^d\right)$ 。与 GP-UCB[Srinivas 等人，2010]类似，我们在 $d$ 维空间中构建采集函数。

where ${\beta }_t^d$ is a factor controlling tradeoff between the exploitation ${\mu }_{t-1}\left({\mathbf{x}}^d\right)$ and exploration ${\sigma }_{t-1}\left({\mathbf{x}}^d\right)$ . At each iteration, we determine a new ${\mathbf{x}}^d$ by maximizing the Eq .(3).
其中 ${\beta }_t^d$ 是控制利用 ${\mu }_{t-1}\left({\mathbf{x}}^d\right)$ 与探索 ${\sigma }_{t-1}\left({\mathbf{x}}^d\right)$ 之间权衡的因子。每次迭代时，我们通过最大化式(3)来确定新的 ${\mathbf{x}}^d$ 。

Given ${\mathbf{x}}_t^d$ ,we still need to fill-in the variables ${\mathbf{x}}_t^{D-d}$ from the left-out $D-d$ dimensions to evaluate the function. We devise three "fill-in" strategies for ${\mathbf{x}}_t^{D-d}$ :
给定 ${\mathbf{x}}_t^d$ ，我们仍需从遗漏的 $D-d$ 维度中填补变量 ${\mathbf{x}}_t^{D-d}$ 以评估函数。为此我们设计了三种针对 ${\mathbf{x}}_t^{D-d}$ 的“填补”策略：

where $u(\cdot )$ is a uniform distribution.
其中 $u(\cdot )$ 为均匀分布。

where ${\mathbf{x}}_t^{+}$ is the variables of the best found function value till $t$ iterations.
其中 ${\mathbf{x}}_t^{+}$ 表示截至第 $t$ 次迭代时，所找到的最佳函数值对应的变量。

Dropout-Random does not work effectively when a large number of dimensions are influential. However, it can still improve the optimization since we optimize $d$ variables each iteration. Copying the value of the variables from the best function value so far seems to be an efficient strategy to consistently improve the previous best regret. However, this method may get stuck in a local optimum. This problem is solved by the third strategy, which helps the copy method to escape the local optimum with a probability $p$ .
当大量维度具有影响力时，Dropout-Random 方法效果不佳。然而，由于每次迭代优化 $d$ 个变量，它仍能提升优化效果。复制当前最佳函数值对应的变量值似乎是一种能持续改善先前最佳遗憾的有效策略。但此方法可能陷入局部最优，该问题通过第三种策略得以解决，即以概率 $p$ 帮助复制方法逃离局部最优。

Our approach performs Bayesian optimization in the $d$ - dimensional space and thus DIRECT requires $\mathcal{O}\left({\zeta }^{-d}\right)$ calls to the acquisition function to achieve $\zeta$ accuracy [Jones et al., 1998]. It is significantly better than full-dimensional BO where DIRECT requires $\mathcal{O}\left({\zeta }^{-D}\right)$ objective function calls. Both our approach and the full-dimensional BO need the time complexity $\mathcal{O}\left(n^3\right)$ to compute the inverse of the covariance matrix,where $n$ is the number of observations. We summarize our algorithms in the following.
我们的方法在 $d$ 维空间中进行贝叶斯优化，因此 DIRECT 需要调用 $\mathcal{O}\left({\zeta }^{-d}\right)$ 次采集函数以达到 $\zeta$ 的精度[Jones 等人，1998]。这明显优于全维度贝叶斯优化，后者 DIRECT 需要 $\mathcal{O}\left({\zeta }^{-D}\right)$ 次目标函数调用。我们的方法与全维度贝叶斯优化均需 $\mathcal{O}\left(n^3\right)$ 的时间复杂度来计算协方差矩阵的逆，其中 $n$ 为观测次数。我们在下文中对算法进行总结。

Algorithm 1 Dropout Algorithm for High-dimensional Bayesian Optimization
算法 1 高维贝叶斯优化的 Dropout 算法

Input: ${\mathcal{D}}_1=\left\{{\mathbf{x}}_0,y_0\right\}$  输入： ${\mathcal{D}}_1=\left\{{\mathbf{x}}_0,y_0\right\}$

for $t=1,2,\cdots$ do  对于 $t=1,2,\cdots$ 执行

randomly select $d$ dimensions
随机选择 $d$ 个维度

${\mathbf{x}}_t^d\leftarrow {\mathrm{argmax}}_{{\mathbf{x}}_t^d\in {\mathcal{X}}^d}a\left({\mathbf{x}}^d\mid {\mathcal{D}}_t\right)\left(\mathrm{Eq}.\left(3\right)\right)$

${\mathbf{x}}_t^{D-d}\leftarrow$ one of three "fill-in" strategies (Sec 2.)
三种“填空”策略之一（见第 2 节）

${\mathbf{x}}_t\leftarrow {\mathbf{x}}_t^d\cup {\mathbf{x}}_t^{D-d}$

$y_t\leftarrow$ Query $y_t$ at ${\mathbf{x}}_t$
在 ${\mathbf{x}}_t$ 处查询 $y_t$

${\mathcal{D}}_{t+1}={\mathcal{D}}_t\cup \left\{{\mathbf{x}}_t,y_t\right\}$

end for  结束循环

Our main contribution is to derive a regret bound for our algorithm and discuss heuristic strategies. We denote $f\left({\mathbf{x}}^d\right)$ as the worst function value given ${\mathbf{x}}^d$ ,i.e. $f\left({\mathbf{x}}^d\right)=f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}_w^{D-d}\right]\right)$ , where ${\mathbf{x}}_w^{D-d}={\mathrm{argmin}}_{{\mathbf{x}}^{D-d}}f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]\right)$ .
我们的主要贡献是推导出算法的遗憾界并讨论启发式策略。我们将 $f\left({\mathbf{x}}^d\right)$ 定义为给定 ${\mathbf{x}}^d$ 时的最差函数值，即 $f\left({\mathbf{x}}^d\right)=f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}_w^{D-d}\right]\right)$ ，其中 ${\mathbf{x}}_w^{D-d}={\mathrm{argmin}}_{{\mathbf{x}}^{D-d}}f\left(\left[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}\right]\right)$ 。

Assumption 1. Let $f$ sample from GP with the kernel $k\left(\mathbf{x},{\mathbf{x}}^{\prime }\right)$ ,which is L-Lipschitz for all $\mathbf{x}$ . Then the partial derivatives of $f$ satisfy the following high probability bound for some constants $a,b>0$ ,
假设 1. 令 $f$ 从具有核函数 $k\left(\mathbf{x},{\mathbf{x}}^{\prime }\right)$ 的高斯过程中采样，该核函数对所有 $\mathbf{x}$ 满足 L-利普希茨条件。那么，对于某些常数 $a,b>0$ ， $f$ 的偏导数满足以下高概率边界，

The assumption implies the following equation holds with the probability greater than $1-\delta /2$ for all $\mathbf{x}$ ,
该假设意味着以下等式以大于 $1-\delta /2$ 的概率对所有 $\mathbf{x}$ 成立，

where $L=b\sqrt{\log \left(2\left(D-d\right)a/\delta \right)}$ .  其中 $L=b\sqrt{\log \left(2\left(D-d\right)a/\delta \right)}$ 。

Lemma 2. Pick $\delta \in \left(0,1\right)$ and set ${\beta }_t^d=2\log \left(4{\pi }_t/\delta \right)+$ $2d\log \left(d{t}^{2}br\sqrt{\log \left(4da/\delta \right)}\right)$ ,where ${\sum }_{t\ge 1}{\pi }_t^{-1}=1,{\pi }_t>0$ . Then in the $d$ -dimensional space,with the probability $\ge 1-$ $\delta /2$
引理 2. 选取 $\delta \in \left(0,1\right)$ 并设定 ${\beta }_t^d=2\log \left(4{\pi }_t/\delta \right)+$ $2d\log \left(d{t}^{2}br\sqrt{\log \left(4da/\delta \right)}\right)$ ，其中 ${\sum }_{t\ge 1}{\pi }_t^{-1}=1,{\pi }_t>0$ 。那么在 $d$ 维空间中，以概率 $\ge 1-$ $\delta /2$

The Lemma 2 is derived from the Bayesian optimization in the $d$ -dimensional space. The proof is identical to Theorem 2 in [Srinivas et al., 2010].
引理 2 源自于 $d$ 维空间中的贝叶斯优化。其证明与[Srinivas 等人，2010]中的定理 2 相同。

Lemma 3. Let ${\beta }_t^d$ be defined as in Lemma 2 and set ${\sigma }_{t-1}^{\prime }\left({\mathbf{x}}^d\right)={\sigma }_{t-1}\left({\mathbf{x}}^d\right)+\frac{L\left(D-d\right)}{\sqrt{{\beta }_t^d}}$ . Then
引理 3. 设 ${\beta }_t^d$ 如引理 2 所定义，并令 ${\sigma }_{t-1}^{\prime }\left({\mathbf{x}}^d\right)={\sigma }_{t-1}\left({\mathbf{x}}^d\right)+\frac{L\left(D-d\right)}{\sqrt{{\beta }_t^d}}$ 。则

holds with the probability $\ge 1-\delta$ .
以概率 $\ge 1-\delta$ 成立。

Proof. The following is true for all $t\ge 1$ and for all $\mathbf{x}\in \mathcal{X}$ with probability $>1-\delta$ ,
证明。以下对所有 $t\ge 1$ 及所有 $\mathbf{x}\in \mathcal{X}$ 以概率 $>1-\delta$ 成立，

where ${\sigma }_{t-1}^{\prime }\left({\mathbf{x}}^d\right)={\sigma }_{t-1}\left({\mathbf{x}}^d\right)+\frac{L\left(D-d\right)}{\sqrt{{\beta }_t^d}}$ . The Line 3 to Line 4 In Eq.(10) exploits Eq.(7). The variance difference $\frac{L\left(D-d\right)}{\sqrt{{\beta }_t^d}}$ will reduce with iteration $t$ since ${\beta }_t^d$ is increasing.
其中 ${\sigma }_{t-1}^{\prime }\left({\mathbf{x}}^d\right)={\sigma }_{t-1}\left({\mathbf{x}}^d\right)+\frac{L\left(D-d\right)}{\sqrt{{\beta }_t^d}}$ 。式(10)中从第 3 行到第 4 行的推导利用了式(7)。方差差异 $\frac{L\left(D-d\right)}{\sqrt{{\beta }_t^d}}$ 将随着迭代次数 $t$ 的增加而减小，因为 ${\beta }_t^d$ 是递增的。

Lemma 4. Pick $\delta \in \left(0,1\right)$ and Let ${\beta }_t^d$ be defined as in Lemma 2. Then the regret $r_t$ is bounded by $2\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\mathbf{x}}^d\right)+\frac{1}{t^2}$ .
引理 4。选取 $\delta \in \left(0,1\right)$ ，并令 ${\beta }_t^d$ 如引理 2 所定义。则遗憾值 $r_t$ 的界限由 $2\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\mathbf{x}}^d\right)+\frac{1}{t^2}$ 给出。

Proof. By definition of ${\mathbf{x}}_t^d:{\mu }_{t-1}\left({\mathbf{x}}_t^d\right)+\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\mathbf{x}}_t^d\right)\ge$ ${\mu }_{t-1}\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)+\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)$ . According to Lemma 5.7 in [Srinivas et al.,2010], ${\mu }_{t-1}\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)+\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)+\frac{1}{t^2}\ge$ $f\left({\mathbf{x}}^{\ast }\right)$ ,where ${\left[{\mathbf{x}}^{\ast }\right]}_t$ denotes the closest point in discretizations $D_t\subset \mathcal{X}$ to ${\mathbf{x}}^{\ast }$ . Then
证明。根据 ${\mathbf{x}}_t^d:{\mu }_{t-1}\left({\mathbf{x}}_t^d\right)+\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\mathbf{x}}_t^d\right)\ge$ 的定义 ${\mu }_{t-1}\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)+\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)$ 。依据[Srinivas 等，2010]中的引理 5.7， ${\mu }_{t-1}\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)+\sqrt{{\beta }_t^d}{\sigma }_{t-1}^{\prime }\left({\left[{\mathbf{x}}^{\ast }\right]}_t^d\right)+\frac{1}{t^2}\ge$ $f\left({\mathbf{x}}^{\ast }\right)$ ，其中 ${\left[{\mathbf{x}}^{\ast }\right]}_t$ 表示离散化集合 $D_t\subset \mathcal{X}$ 中与 ${\mathbf{x}}^{\ast }$ 最接近的点。随后

Lemma 5. Pick $\delta \in \left(0,1\right)$ and let ${\beta }_t^d$ be defined as Lemma 2. Then the cumulative regret holds with the probability $\ge 1-\delta$ and $C_1=8/\log \left(1+{\sigma }^{-2}\right)$ ,
引理 5。选取 $\delta \in \left(0,1\right)$ ，并令 ${\beta }_t^d$ 如引理 2 所定义。则累积遗憾以概率 $\ge 1-\delta$ 和 $C_1=8/\log \left(1+{\sigma }^{-2}\right)$ 成立，

Figure 1: The effect of the number of dimensions $d$ in Dropout-Copy. The y-axis in Gaussian mixture function presents the real function value (Higher value is better). The y-axis in Schwefel's 1.2 function presents the logarithm of function value (Lower value is better).
图 1：维度数量 $d$ 对 Dropout-Copy 方法的影响。高斯混合函数中 y 轴表示实际函数值（数值越高越好）。Schwefel's 1.2 函数中 y 轴表示函数值的对数（数值越低越好）。

Proof. we prove Lemma 5 in the following
证明。我们将在下文中证明引理 5。

where $\sum _{t\le T}\left(2\sqrt{{\beta }_t^d}{\sigma }_{t-1}\left({\mathbf{x}}^d\right)\right)$ in the second line of Eq. (12) can be bounded via the Theorem 1 in [Srinivas et al., 2010]. ${\gamma }_T$ can be bounded for different kernels. For the SE kernel, ${\gamma }_T=\mathcal{O}\left({(\log T)}^{d+1}\right)$ .
其中，式(12)第二行中的 $\sum _{t\le T}\left(2\sqrt{{\beta }_t^d}{\sigma }_{t-1}\left({\mathbf{x}}^d\right)\right)$ 可通过[Srinivas et al., 2010]中的定理 1 界定。对于不同核函数， ${\gamma }_T$ 均可被界定。对于平方指数核， ${\gamma }_T=\mathcal{O}\left({(\log T)}^{d+1}\right)$ 。

Lemma 5 indicates $\underset{T\to \mathrm{\infty }}{lim}\frac{1}{T}{R}_T\le 2L\left(D-d\right)$ - that is,a regret gap remains in the limit. This is introduced through the bound on the worst-case of ${\Vert \begin{array}{c}\mathbf{x}-[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}]\end{array}\Vert }_1,\mathrm{\forall }{\mathbf{x}}^{D-d}$ (Eq.(7)). In reality a judicious choice of the $D-d$ dimensions will improve this bound by reducing this difference. We have thus formulated three options for filling in the variables of the dropped out dimensions: random, best value and mixture of the two. Intuitively if the current optimum is far away from the global optimum, random values are an appropriate guess for the "fill-in" as there is no other information. If the current optimum is close to the global optimum, copying the value of the dropped-out variables from the best found function value is likely to improve the best regret obtained by the previous iterations. This behaves like block coordinate descent [Nesterov, 2012] that optimizes a chosen block of coordinates while keeping others fixed. The difference is that block coordinate descent assumes that the previous iteration has reached the best value, while Dropout-Copy starts from the best of previous iterations. When the current optimum value is close to a local optimum, Dropout-Copy may get stuck. To escape this local optimum, we use Dropout-Mix that introduces a random fill-in with a pre-specified probability into Dropout-Copy.
引理 5 表明 $\underset{T\to \mathrm{\infty }}{lim}\frac{1}{T}{R}_T\le 2L\left(D-d\right)$ ——即在极限情况下仍存在遗憾间隙。这是通过对 ${\Vert \begin{array}{c}\mathbf{x}-[{\mathbf{x}}^d,{\mathbf{x}}^{D-d}]\end{array}\Vert }_1,\mathrm{\forall }{\mathbf{x}}^{D-d}$ 最坏情况的约束（式(7)）引入的。实际上，明智地选择 $D-d$ 维度将通过减小这一差异来改进该界限。为此我们提出了三种填补缺失维度变量的方案：随机填充、最优值填充以及两者混合填充。直观而言，若当前最优解远离全局最优解，随机值作为"填充"是合理猜测，因无其他信息可用；若当前最优解接近全局最优解，则从已找到的最佳函数值中复制缺失变量值，有望提升前序迭代获得的最佳遗憾值。该机制类似块坐标下降法[Nesterov, 2012]——在固定其他坐标块的同时优化选定坐标块。区别在于块坐标下降法假设前次迭代已达最优值，而 Dropout-Copy 从先前迭代的最佳值起步。当当前最优值接近局部最优时，Dropout-Copy 可能陷入停滞。 为跳出这一局部最优解，我们采用 Dropout-Mix 方法，它以预设概率在 Dropout-Copy 中引入随机填充。

Figure 2: The effect of the probability $p$ in Dropout-Mix.
图 2：概率 $p$ 对 Dropout-Mix 的影响。

We evaluate our methods on benchmark functions and two real applications. We compare our methods with four baselines: random search, which is a simple random sampling method, the standard BO, REMBO [Wang et al., 2013] which projects high dimensions to lower dimensions, and ADD-GP-UCB [Kandasamy et al., 2015] which optimizes disjoint groups of variables and combines them. For standard BO we allocate a budget of 30 seconds (which is larger than the time returned by our algorithms) to optimize the acquisition function at each iteration. The number of initial observations are set at $d+1$ . We use the SE kernel with the lengthscale 0.1 and DIRECT [Jones et al., 1993] to optimize acquisition functions. We run each algorithm 20 times with different initializations and report the average value with standard error.
我们在基准函数和两个实际应用场景中评估了所提方法，并与四种基线方法进行对比：随机搜索（一种简单随机采样方法）、标准贝叶斯优化（BO）、将高维空间投影至低维的 REMBO[Wang 等人，2013]，以及优化变量不相交组并组合结果的 ADD-GP-UCB[Kandasamy 等人，2015]。标准 BO 每次迭代分配 30 秒预算（超过本算法耗时）用于优化采集函数。初始观测点数量设为 $d+1$ 。采用长度尺度为 0.1 的 SE 核函数，并使用 DIRECT[Jones 等人，1993]优化采集函数。每种算法均以不同初始化方式运行 20 次，报告平均值及标准误差。

To demonstrate that Dropout-Mix can deal with local convergence, we choose a bimodal Gaussian mixture function as our test function. The Gaussian mixture function is defined as $y=\mathcal{N}\mathcal{P}\left(\mathbf{x};{\mu }_1,{\sum }_1\right)+\frac{1}{2}\mathcal{N}\mathcal{P}\left(\mathbf{x};{\mu }_2,{\sum }_2\right)$ ,where $\mathcal{N}\mathcal{P}$ is the Gaussian probability function, ${\mu }_1=\left[2,2,\cdots ,2\right]$ , ${\mu }_2=\left[3,3,\cdots ,3\right]$ and ${\sum }_1={\sum }_2=\mathrm{diag}\left(\left[1,1,\cdots ,1\right]\right)$ . The domain of definition $\mathcal{X}={[1,4]}^D$ and its global maximum is located at ${\mathbf{x}}^{\ast }=\left[2,2,\cdots 2\right]$ . This function has a local maximum and no interacting variables. To demonstrate that our algorithms can effectively work for functions with interacting variables, we use the unimodal Schwefel's 1.2 function $f\left(x\right)=\sum _{j=1}^D{(\sum _{i=1}^j{\mathbf{x}}_i)}^2$ as our second test function. It is defined in the domain $\mathcal{X}={[-1,1]}^D$ and has the global minimum at ${\mathbf{x}}^{\ast }=\left[0,0,\cdots 0\right]$ . We compare the algorithms in terms of the best function values reached upto any iteration.
为证明 Dropout-Mix 能有效应对局部收敛问题，我们选用双峰高斯混合函数作为测试函数。该高斯混合函数定义为 $y=\mathcal{N}\mathcal{P}\left(\mathbf{x};{\mu }_1,{\sum }_1\right)+\frac{1}{2}\mathcal{N}\mathcal{P}\left(\mathbf{x};{\mu }_2,{\sum }_2\right)$ ，其中 $\mathcal{N}\mathcal{P}$ 为高斯概率函数， ${\mu }_1=\left[2,2,\cdots ,2\right]$ 、 ${\mu }_2=\left[3,3,\cdots ,3\right]$ 和 ${\sum }_1={\sum }_2=\mathrm{diag}\left(\left[1,1,\cdots ,1\right]\right)$ 。定义域为 $\mathcal{X}={[1,4]}^D$ ，其全局最大值位于 ${\mathbf{x}}^{\ast }=\left[2,2,\cdots 2\right]$ 。此函数存在一个局部最大值且无交互变量。为展示算法在含交互变量函数中的有效性，我们采用单峰 Schwefel's 1.2 函数 $f\left(x\right)=\sum _{j=1}^D{(\sum _{i=1}^j{\mathbf{x}}_i)}^2$ 作为第二测试函数，其定义域为 $\mathcal{X}={[-1,1]}^D$ ，全局最小值位于 ${\mathbf{x}}^{\ast }=\left[0,0,\cdots 0\right]$ 。我们通过比较各算法在迭代过程中达到的最佳函数值来评估性能。

Figure 3: The optimization for the Gaussian mixture function. Higher value is better. Four different dimensions are tested from left to right (a) $D=5$ (b) $D=10$ (c) $D=20$ (d) $D=30$ . The BO for $D=5$ and $D=10$ is terminated once it converges. The graphs are best seen in color.
图 3：高斯混合函数的优化过程（数值越高越好）。从左至右测试了四种不同维度：(a) $D=5$ (b) $D=10$ (c) $D=20$ (d) $D=30$ 。当 $D=5$ 和 $D=10$ 的贝叶斯优化收敛时即终止。图示效果建议彩色查看。