A Framework for Bayesian Optimization in Embedded Subspaces
嵌入式子空间中的贝叶斯优化框架

Alexander Munteanu ${}^{1\ast }$ Amin Nayebi ${}^{2\ast }$ Matthias Poloczek ${}^{32}$
亚历山大·蒙特亚努 ${}^{1\ast }$ 阿明·纳耶比 ${}^{2\ast }$ 马蒂亚斯·波洛切克 ${}^{32}$

We present a theoretically founded approach for high-dimensional Bayesian optimization based on low-dimensional subspace embeddings. We prove that the error in the Gaussian process model is bounded tightly when going from the original high-dimensional search domain to the low-dimensional embedding. This implies that the optimization process in the low-dimensional embedding proceeds essentially as if it were run directly on an unknown active subspace of low dimensionality. The argument applies to a large class of algorithms and GP models, including non-stationary kernels. Moreover, we provide an efficient implementation based on hashing and demonstrate empirically that this subspace embedding achieves considerably better results than the previously proposed methods for high-dimensional BO based on Gaussian matrix projections and structure-learning.
我们提出了一种基于低维子空间嵌入的高维贝叶斯优化理论方法。我们证明，当从原始高维搜索域转换到低维嵌入时，高斯过程模型中的误差被严格限制。这意味着低维嵌入中的优化过程基本上就像是在未知的低维活跃子空间上直接运行一样。这一论点适用于包括非平稳核在内的大量算法和 GP 模型。此外，我们提供了一种基于哈希的高效实现，并通过实证表明，这种子空间嵌入相较于先前提出的基于高斯矩阵投影和结构学习的高维 BO 方法，能取得显著更好的结果。

Bayesian optimization (BO) has recently emerged as powerful technique for the global optimization of expensive-to-evaluate black-box functions (Brochu et al., 2010; Shahriari et al., 2016; Frazier, 2018). Here 'black-box' means that we may evaluate the objective at any point to observe its value, possibly with noise but without derivative information. The advantages of Bayesian optimization are sample-efficiency, convergence to a global optimum, and a low computational overhead. A critical limitation is the number of parameters that BO can optimize. The limit is usually seen around 15 parameters for the most common form of BO that uses Gaussian process (GP) regression as a surrogate model for the objective function. Thus, it is not surprising that expanding $\mathrm{BO}$ to higher-dimensional search spaces is widely acknowledged as one of the most important goals in the field. For example, Frazier (2018, p. 16) states that "developing Bayesian optimization methods that work well in high dimensions is of great practical and theoretical interest".
贝叶斯优化（BO）最近已成为一种强大的技术，用于全局优化评估成本高昂的黑盒函数（Brochu 等人，2010；Shahriari 等人，2016；Frazier，2018）。这里的“黑盒”意味着我们可以在任何点评估目标以观察其值，可能带有噪声但没有导数信息。贝叶斯优化的优势在于样本效率高、能收敛到全局最优解且计算开销低。一个关键限制是 BO 能优化的参数数量。对于最常见的使用高斯过程（GP）回归作为目标函数代理模型的 BO 形式，参数限制通常在 15 个左右。因此，将 $\mathrm{BO}$ 扩展到更高维搜索空间被广泛认为是该领域最重要的目标之一也就不足为奇了。例如，Frazier（2018，第 16 页）指出“开发在高维情况下表现良好的贝叶斯优化方法具有重要的实践和理论意义”。

This paper advances the field in the theory of high-dimensional Bayesian optimization and improves the practical performance. Specifically, the contributions are:
本文在高维贝叶斯优化的理论领域取得进展，并提升了实际应用性能。具体贡献包括：

Related Work. Bayesian optimization has recently received significant interest for the optimization of expensive-to-evaluate black-box functions. We refer to (Brochu et al., 2010; Shahriari et al., 2016; Frazier, 2018) for an overview. Aside of the general setting of optimizing an objective black-box function, several extensions have been studied, including constrained (Gardner et al., 2014; Hernández-Lobato et al., 2015; Picheny et al., 2016) and multifidelity optimization (Kennedy & O'Hagan, 2000; Huang et al., 2006; Swersky et al., 2013; Kandasamy et al., 2016; Poloczek et al., 2017), expensive functions with derivative information (Wu et al., 2017; Eriksson et al., 2018), and neural network architecture search (Klein et al., 2017; Kandasamy et al., 2018).
相关工作。贝叶斯优化近年来因在昂贵评估的黑盒函数优化中的应用而受到广泛关注。相关综述可参阅（Brochu 等人，2010；Shahriari 等人，2016；Frazier，2018）。除了一般性的黑盒目标函数优化外，还研究了几种扩展场景，包括带约束的优化（Gardner 等人，2014；Hernández-Lobato 等人，2015；Picheny 等人，2016）、多保真度优化（Kennedy & O'Hagan，2000；Huang 等人，2006；Swersky 等人，2013；Kandasamy 等人，2016；Poloczek 等人，2017）、含导数信息的昂贵函数优化（Wu 等人，2017；Eriksson 等人，2018）以及神经网络架构搜索（Klein 等人，2017；Kandasamy 等人，2018）。

${}^{\ast }$ Equal contribution ${}^1$ Dortmund Data Science Center,Faculties of Statistics and Computer Science, TU Dortmund, Dortmund,Germany ${}^2$ Department of Systems and Industrial Engineering,University of Arizona,Tucson,AZ,USA ${}^3$ Uber AI Labs, San Francisco, CA, USA. Correspondence to: Matthias Poloczek .
${}^{\ast }$ 同等贡献 ${}^1$ 多特蒙德数据科学中心，统计学与计算机科学学院，多特蒙德工业大学，德国多特蒙德 ${}^2$ 系统与工业工程系，亚利桑那大学，美国图森 ${}^3$ Uber 人工智能实验室，美国加利福尼亚州旧金山。通讯作者：Matthias Poloczek。

Proceedings of the ${36}^{\text{th }}$ International Conference on Machine Learning, Long Beach, California, PMLR 97, 2019. Copyright 2019 by the author(s).
《机器学习国际会议论文集》，美国加利福尼亚州长滩，PMLR 97，2019 年。版权归作者所有。

Kandasamy et al. (2015) extended Bayesian optimization to higher-dimensional search spaces composed of disjoint low-dimensional subspaces that can be optimized over separately if the latent additive structure is learned. The ADD algorithm of Gardner et al. (2017) and SKL of Wang et al. (2017) use sophisticated sampling procedures to learn the decomposition, and Rolland et al. (2018) and Mutny & Krause (2018) extended the idea to overlapping subspaces. Inferring the latent structure of the search space from data via extensive sampling introduces a considerable computational load in practice, which limits the applicability to objective functions with high evaluation cost (see Sect. 3). This bottleneck was recently addressed by Wang et al. (2018) whose ensemble BO method (EBO) uses an ensemble of additive GP models for scalability. We evaluated ADD, EBO and SKL from this line of research and found EBO indeed more scalable than SKL, but still considerably more expensive than the other approaches that we evaluated.
Kandasamy 等人（2015）将贝叶斯优化扩展至由可分离低维子空间构成的高维搜索空间，前提是学习到潜在的加性结构。Gardner 等人（2017）的 ADD 算法与 Wang 等人（2017）的 SKL 通过复杂采样程序学习分解方式，Rolland 等人（2018）及 Mutny & Krause（2018）进一步将该思想推广至重叠子空间。实践中，通过大量采样从数据推断搜索空间的潜在结构会带来巨大计算负担，限制了该方法在高评估成本目标函数上的适用性（见第 3 节）。Wang 等人（2018）近期提出的集成 BO 方法（EBO）采用加性高斯过程模型集合来解决这一瓶颈问题。我们评估了该研究方向的 ADD、EBO 和 SKL 方法，发现 EBO 确实比 SKL 更具可扩展性，但相比其他评估方法仍显昂贵。

Chen et al. (2012); Wang et al. (2016b) bypassed scala-bility issues by leveraging the observation that for many applications only a small number of tunable parameters have a significant effect on the objective function. This phenomenon is known as "active subspace" and "effective dimensionality". Wang et al. (2016b) used a projection matrix with standard Gaussian entries and showed that the active subspace is rank-preserved but strongly dilated. Thus, they expanded the low-dimensional search space to ensure that its projection to the high-dimensional space contains an optimal solution with reasonable probability. Their REMBO algorithm fits a GP model to the low-dimensional space and projects points back to the high-dimensional space using the inverse random projection. Points whose high-dimensional image is outside the search domain $\mathcal{X}$ are convex-projected to the boundary $\partial \mathcal{X}$ ,which may lead to over-exploration of the boundary regions. Binois et al. (2015) suggested a new warping kernel $k_{\psi }$ to address this issue by an improved preservation of distances among such points. Recently, Binois et al. (2019) proposed a novel choice of the low-dimensional search space to handle the distortion of Gaussian projections. Djolonga et al. (2013) and Eriks-son et al. (2018) propose learning the active subspace, in the latter paper from derivative information, and therefore avoid the random projection. We compare to the methods in (Wang et al., 2016b; Binois et al., 2015) in Sect. 3. We also compare to the BOCK algorithm of Oh et al. (2018) that is based on a cylindrical transformation. This provides scalability to high dimensional problems and an implicit prior that the optimizer is in the interior of the search space.
Chen 等人(2012); Wang 等人(2016b)通过利用观察到的现象绕过了可扩展性问题，即在许多应用中只有少量可调参数对目标函数有显著影响。这种现象被称为"活动子空间"和"有效维度"。Wang 等人(2016b)使用具有标准高斯项的投影矩阵，并表明活动子空间保持了秩但被强烈扩张。因此，他们扩展了低维搜索空间，以确保其向高维空间的投影以合理概率包含最优解。他们的 REMBO 算法将高斯过程模型拟合到低维空间，并使用逆随机投影将点投影回高维空间。高维图像位于搜索域 $\mathcal{X}$ 之外的点被凸投影到边界 $\partial \mathcal{X}$ ，这可能导致边界区域的过度探索。Binois 等人(2015)提出了一种新的扭曲核 $k_{\psi }$ ，通过改进这些点之间距离的保持来解决这个问题。最近，Binois 等人 （2019 年）提出了一种新颖的低维搜索空间选择方法，以处理高斯投影的失真问题。Djolonga 等人（2013 年）和 Eriksson 等人（2018 年）提出学习主动子空间，后者论文中利用导数信息，从而避免了随机投影。我们在第 3 节中与（Wang 等人，2016b；Binois 等人，2015 年）的方法进行了比较。我们还与 Oh 等人（2018 年）基于圆柱变换的 BOCK 算法进行了对比，该方法为高维问题提供了可扩展性，并隐含了优化器位于搜索空间内部的先验假设。

Outline. Sect. 2 introduces probabilistic subspace embed-dings and the HeSBO method, followed by the theoretical foundation. The experimental evaluation is given in Sect. 3 and the discussion is in Sect. 4. Sections denoted by letters are found in the Supplement.
概述。第 2 节介绍了概率子空间嵌入及 HeSBO 方法，随后是理论基础。实验评估在第 3 节中给出，讨论部分位于第 4 节。标有字母的章节可在补充材料中找到。

This section introduces probabilistic subspace embeddings and their use in BO. Sect. 2.2 motivates the approach. The theoretical foundation is given in Sect. 2.3 and generalized to large classes of popular kernels in Sect. 2.4.
本节介绍概率子空间嵌入及其在贝叶斯优化中的应用。第 2.2 节阐述了该方法的动机，理论基础在第 2.3 节中给出，并在第 2.4 节中推广至多种流行核函数的广泛类别。

Given an objective function $f$ defined on the high-dimensional domain $\mathcal{X}={[-1,+1]}^D$ ,we suppose that there exists an unknown $d_e$ -dimensional active subspace $\mathcal{Z}$ . Informally,the objective $f$ is invariant to coordinate changes outside $\mathcal{Z}$ . Note that we do not suppose that $\mathcal{Z}$ is axis-aligned with $\mathcal{X}$ . Our approach is to choose a $d$ -dimensional subspace $\mathcal{Y}$ of $\mathcal{X}$ randomly such that the optimization process proceeds on $\mathcal{Y}$ essentially as it would on $\mathcal{Z}$ with good probability. This enables to run a BO method on $\mathcal{Y}$ in order to find an $x^{\ast }\in \arg \underset{x\in \mathcal{X}}{max}f\left(x\right)$ . The proposed embedding can easily be combined with many GP-based BO methods: Algorithm 1 shows the generic BO algorithm (Shahriari et al., 2016; Frazier, 2018) with the embedding incorporated via the highlighted steps. We call this Hashing-enhanced Subspace Bayesian Optimization (HeSBO).
给定在高维域 $\mathcal{X}={[-1,+1]}^D$ 上定义的目标函数 $f$ ，我们假设存在一个未知的 $d_e$ 维活跃子空间 $\mathcal{Z}$ 。非正式地说，目标函数 $f$ 对 $\mathcal{Z}$ 之外的坐标变化保持不变。注意，我们并不假设 $\mathcal{Z}$ 与 $\mathcal{X}$ 轴对齐。我们的方法是随机选择一个 $d$ 维子空间 $\mathcal{Y}$ 作为 $\mathcal{X}$ 的子空间，使得优化过程在 $\mathcal{Y}$ 上的进行基本上如同在 $\mathcal{Z}$ 上进行，且具有较高的概率。这使得能够在 $\mathcal{Y}$ 上运行贝叶斯优化方法以找到 $x^{\ast }\in \arg \underset{x\in \mathcal{X}}{max}f\left(x\right)$ 。所提出的嵌入方法可以轻松地与多种基于高斯过程的贝叶斯优化方法结合：算法 1 展示了通用贝叶斯优化算法（Shahriari 等人，2016；Frazier，2018），其中通过高亮步骤嵌入了该方法。我们称之为哈希增强的子空间贝叶斯优化（HeSBO）。

The embedding is constructed in Algorithm 2 that initializes two hash functions which implicitly represent the embedding matrix $S^{\prime }$ (see Sect. 2.2 for details): The hash function $h$ chooses one single non-zero entry for each of the $D$ dimensions,and the function $\sigma$ determines the sign of the corresponding non-zero entry. Algorithm 3 maps the low-dimensional vector $y\in \mathcal{Y}$ to the high-dimensional domain $\mathcal{X}$ . The algorithm iterates over the high-dimensional coordinates: for each entry it invokes the two above hash functions to determine the associated coordinate in the low-dimensional vector $y$ and the sign that the corresponding value of $y$ is multiplied with. Note that by construction the columns of the matrix are orthogonal. Moreover, for any fixed coordinate (dimension) $d_i$ of the low-dimensional space we have that the number of coordinates in the high dimensional space that map to $d_i$ is concentrated at $D/d$ , i.e.,this number has mean $D/d$ and a variance that drops (quickly) as $D$ increases. The reason is that $h$ picks the target of each dimension uniformly at random. The dilation is thus roughly $\sqrt{D/d}$ ,and the search domain $\mathcal{Y}={[-1,1]}^d$ is mapped to $S^{\prime }\mathcal{Y}=\left\{S^{\prime }y\mid y\in \mathcal{Y}\right\}\subset \mathcal{X}={[-1,1]}^D$ with low distortion. We contrast this with REMBO's search space that was chosen as ${[-\sqrt{d},+\sqrt{d}]}^d$ to cope with dilations; see Sect. B. It is critical to note that the operations of copying the coordinates and multiplying them by $\{-1,1\}$ assert that no point is projected outside $\mathcal{X}$ . Thus, $\mathrm{HeSBO}$ avoids complex corrections in contrast to the REMBO variants. The analysis in Sect. C in the supplement shows that REMBO applies these corrections frequently.
嵌入构造在算法 2 中，该算法初始化了两个哈希函数，它们隐式地表示了嵌入矩阵 $S^{\prime }$ （详见第 2.2 节）：哈希函数 $h$ 为每个 $D$ 维度选择一个非零条目，而函数 $\sigma$ 确定相应非零条目的符号。算法 3 将低维向量 $y\in \mathcal{Y}$ 映射到高维域 $\mathcal{X}$ 。该算法遍历高维坐标：对于每个条目，它调用上述两个哈希函数来确定低维向量 $y$ 中的关联坐标以及 $y$ 对应值相乘的符号。注意，通过构造，矩阵的列是正交的。此外，对于低维空间中任何固定的坐标（维度） $d_i$ ，映射到 $d_i$ 的高维空间坐标数量集中在 $D/d$ ，即该数量的均值为 $D/d$ ，且方差随着 $D$ 的增加而（迅速）下降。原因是 $h$ 均匀随机地选择每个维度的目标。因此，扩张大致为 $\sqrt{D/d}$ ，搜索域 $\mathcal{Y}={[-1,1]}^d$ 被映射到 $S^{\prime }\mathcal{Y}=\left\{S^{\prime }y\mid y\in \mathcal{Y}\right\}\subset \mathcal{X}={[-1,1]}^D$ 且具有低失真。 我们将其与 REMBO 的搜索空间进行对比，后者选择 ${[-\sqrt{d},+\sqrt{d}]}^d$ 以应对维度扩展问题，详见附录 B。关键需要注意的是，复制坐标并通过 $\{-1,1\}$ 进行乘法的操作确保了没有任何点会被投影到 $\mathcal{X}$ 之外。因此， $\mathrm{HeSBO}$ 避免了复杂的修正，这与 REMBO 的变体形成鲜明对比。补充材料中 C 节的分析表明，REMBO 频繁应用了这些修正措施。

Algorithm 1 The Generic BO Algorithm with the probabilistic subspace embedding
算法 1 采用概率子空间嵌入的通用贝叶斯优化算法

: Input: Objective $f:\mathcal{X}\to \mathbb{R}$ ; acquisition criterion $\alpha$
输入：目标 $f:\mathcal{X}\to \mathbb{R}$ ；采集准则 $\alpha$

(e.g.,EI); target dimension $d\in \mathbb{N}$ .
（例如，EI）；目标维度 $d\in \mathbb{N}$ 。

2: Output: An optimizer $x^{\ast }\in \arg \underset{x\in \mathcal{X}}{max}f\left(x\right)$ .
2：输出：优化器 $x^{\ast }\in \arg \underset{x\in \mathcal{X}}{max}f\left(x\right)$ 。

3: Construct embedding $S^{\prime }:\mathcal{Y}\to \mathcal{X}$ with Algorithm 2.
使用算法 2 构建嵌入 $S^{\prime }:\mathcal{Y}\to \mathcal{X}$ 。

Sample initial points $Y_0\in \mathcal{Y}$ using a space filling design
采用空间填充设计采样初始点 $Y_0\in \mathcal{Y}$

and let $D_0=\left(Y_0,\left\{\text{observation for}f\left(S^{\prime }y\right)\mid y\in Y_0\right\}\right)$ .
并设 $D_0=\left(Y_0,\left\{\text{observation for}f\left(S^{\prime }y\right)\mid y\in Y_0\right\}\right)$ 。

Estimate the hyperparameters ${\theta }_0$ for the GP prior on $\mathcal{Y}$
估计高斯过程先验中关于 $\mathcal{Y}$ 的超参数 ${\theta }_0$

given $D_0$ . Then calculate the posterior conditioned
给定 $D_0$ ，然后计算基于 $D_0$ 和@1#的条件后验

on ${\theta }_0$ and $D_0$ .
基于 ${\theta }_0$ 和 $D_0$ 的条件后验

for $n=1$ to $N$ do
对于 $n=1$ 到 $N$ 执行循环

Compute $y^{n+1}\in \arg \underset{y\in \mathcal{Y}}{max}\alpha \left(y,D_n\right)$ .  计算 $y^{n+1}\in \arg \underset{y\in \mathcal{Y}}{max}\alpha \left(y,D_n\right)$ 。

Evaluate $f\left(S^{\prime }{y}^{n+1}\right)$ ,for the projection of $y^{n+1}$ to $\mathcal{X}$
评估 $f\left(S^{\prime }{y}^{n+1}\right)$ ，针对 $y^{n+1}$ 到 $\mathcal{X}$ 的投影

via Algorithm 3. Let $z^{n+1}$ be the (noisy) observation.
通过算法 3，设 $z^{n+1}$ 为（含噪声的）观测值。

Update the posterior distribution with the new obser-
用新的观测更新后验分布

vation $D_{n+1}=D_n\cup \left(y^{n+1},z^{n+1}\right)$ .  观测 $D_{n+1}=D_n\cup \left(y^{n+1},z^{n+1}\right)$ 。

end for  结束循环

Return $x^{\ast }\in \arg \underset{x\in \mathcal{X}}{max}f\left(x\right)$ if observations are
若观测无噪声，则返回 $x^{\ast }\in \arg \underset{x\in \mathcal{X}}{max}f\left(x\right)$ ；

noise-free, or a point with maximum expected value
否则返回后验分布下具有最大期望值的点。

under the posterior given $D_N$ otherwise.
基于给定 $D_N$ 的后验分布。

Next we provide the motivation and background for the proposed embedding, before we prove its theoretical properties in Sect. 2.3. Random projections have often been used to reduce the dependence on the dimension of an algorithm's running time, memory, or communication cost. The seminal result of Johnson & Lindenstrauss (1984), JL for short, states that any set of $n$ points in a $D$ -dimensional space can be embedded into $d\in O\left(\log n/{\epsilon }^2\right)$ dimensions such that all pairwise ${\ell }_2$ distances are preserved up to a $\left(1\pm \epsilon \right)$ - factor. This can be achieved probabilistically by a linear map where each entry of the embedding $G\in {\mathbb{R}}^{d\times D}$ is an i.i.d. rescaled standard Gaussian. Much effort was put into making the construction computationally more efficient and sparse (Achlioptas, 2003; Ailon & Chazelle, 2009; Ailon & Liberty, 2009; Kane & Nelson, 2014). Sarlós (2006) was the first who generalized such embeddings to entire linear subspaces with target dimension roughly $O\left(d_e/{\epsilon }^2\right)$ which is optimal, see (Nelson & Nguyên, 2014). Charikar et al. (2004) introduced an alternative projection, called count-sketch, based on hashing to identify heavy hitters in a large vector, often a data stream, based on a summary stored in a low-dimensional vector. The count-sketch can be formalized as a sparse matrix with only one non-zero entry per column that is drawn randomly in $\{-1,1\}$ . We give an example of such a map reducing from five to three dimensions:
接下来，在证明其理论性质之前（见第 2.3 节），我们将阐述所提出嵌入方法的动机和背景。随机投影常被用于降低算法运行时间、内存或通信成本对维度的依赖。Johnson & Lindenstrauss (1984)的开创性成果（简称 JL 引理）指出：任何 $n$ 个点组成的集合在 $D$ 维空间中，均可嵌入到 $d\in O\left(\log n/{\epsilon }^2\right)$ 维空间，且所有成对 ${\ell }_2$ 距离能以 $\left(1\pm \epsilon \right)$ 因子近似保持。这种嵌入可通过线性映射概率实现，其中映射矩阵的每个元素均为独立同分布的重缩放标准高斯变量。后续研究（Achlioptas, 2003; Ailon & Chazelle, 2009; Ailon & Liberty, 2009; Kane & Nelson, 2014）致力于提升计算效率并实现稀疏化。Sarlós (2006)首次将此类嵌入推广到整个线性子空间，其目标维度约 $O\left(d_e/{\epsilon }^2\right)$ （此为最优解，参见 Nelson & Nguyên, 2014）。Charikar 等人... （2004 年）提出了一种称为计数草图（count-sketch）的替代投影方法，该方法基于哈希技术，用于通过存储在低维向量中的摘要来识别大型向量（通常是数据流）中的频繁项。计数草图可形式化为一个稀疏矩阵，每列仅含一个随机选取的非零元素，具体实现参见 $\{-1,1\}$ 。以下是一个从五维降至三维的映射示例：

Algorithm 2 Construction of an inverse subspace embedding $S^{\prime }$ implicitly given by $\left(h,\sigma \right)$ ,see details in the text.
算法 2 由 $\left(h,\sigma \right)$ 隐式给出的逆子空间嵌入构造方法 $S^{\prime }$ ，详见正文说明。

Input: Input dimension $D$ ,target dimension $d$ .
输入：输入维度 $D$ ，目标维度 $d$ 。

Output: Implicit representation of a linear map
输出：线性映射的隐式表示

$S^{\prime }:{\mathbb{R}}^d\to {\mathbb{R}}^D$ ,by two hash functions $h$ and $\sigma$ .
通过两个哈希函数 $h$ 和 $\sigma$ 。

: Initialize a pairwise independent and uniform hash func-
初始化一个两两独立且均匀的哈希函数

tion $h:\left[D\right]\to \left[d\right]$ .  tion $h:\left[D\right]\to \left[d\right]$ 。

Initialize a 4-wise independent and uniform hash func-
初始化一个 4-wise 独立且均匀的哈希函数

tion $\sigma :\left[D\right]\to \{-1,1\}$ .  tion $\sigma :\left[D\right]\to \{-1,1\}$ 。

Return $\left(h,\sigma \right)$ ,which implicitly defines $S^{\prime }$ ,see detailed
返回 $\left(h,\sigma \right)$ ，其隐式定义了 $S^{\prime }$ ，详见

description in Sect. 2.2.
第 2.2 节中的描述

Algorithm 3 Computes $S^{\prime }y\in \mathcal{X}$ via the inverse subspace embedding $S^{\prime }$ implicitly given by $\left(h,\sigma \right)$
算法 3 通过由 $\left(h,\sigma \right)$ 隐式给出的逆子空间嵌入 $S^{\prime }$ 计算 $S^{\prime }y\in \mathcal{X}$

: Input: Low-dimensional vector $y\in \mathcal{Y}\subset {\mathbb{R}}^d$ .
输入：低维向量 $y\in \mathcal{Y}\subset {\mathbb{R}}^d$ 。

for $i=1$ to $D$ do
从 $i=1$ 到 $D$ 循环执行

$x_i=\sigma \left(i\right)\cdot y_{h\left(i\right)}$

end for  结束循环

Return $x$ .  返回 $x$ 。

This is equivalent to uniformly hashing each entry $x_i$ to a random coordinate $j=h\left(i\right)\in \left[d\right]$ and multiplying it by a random sign ${\sigma }_i\in \{-1,1\}$ for all $i\in \left[D\right]$ . The low-dimensional summary $y=Sx$ is given by $\mathrm{\forall }j\in$ $\left[d\right]:y_j=\sum _{i:h\left(i\right)=j}\sigma \left(i\right)x_i$ . Charikar et al. (2004) showed that ${\tilde{x}}_i=\sigma \left(i\right)y_{h\left(i\right)}$ is a good estimate for $x_i$ . We recover this idea for the projection from the low-dimensional to the high-dimensional domain, $x\approx S^{\prime }y$ ,in Algorithms 2 and 3. This type of embedding is not capable of preserving pairwise distances for arbitrary sets of points, as JL does. However, Clarkson & Woodruff (2013) showed that it yields a subspace embedding for an entire linear subspace with constant probability. Informally,they used the fact that a $d_e$ - dimensional (active) subspace can have only $O\left(d_e\right)$ coordinates that are large (have high leverage) and thus important. These are exactly the heavy hitters which can be estimated reasonably well. The other low values mostly cancel in the sum with random signs (up to a small error). Nelson & Nguyen (2013) improved and simplified their analysis and complemented with a tight lower bound, settling the target dimension of subspace embeddings via the count-sketch to $\mathrm{\Theta }\left(d_e^2/\left({\epsilon }^2\delta \right)\right)$ ,where $\delta$ is the failure probability. We define $\epsilon$ -subspace embeddings more formally.
这相当于将每个条目 $x_i$ 均匀哈希到一个随机坐标 $j=h\left(i\right)\in \left[d\right]$ ，并为所有 $i\in \left[D\right]$ 乘以一个随机符号 ${\sigma }_i\in \{-1,1\}$ 。低维摘要 $y=Sx$ 由 $\mathrm{\forall }j\in$ $\left[d\right]:y_j=\sum _{i:h\left(i\right)=j}\sigma \left(i\right)x_i$ 给出。Charikar 等人（2004 年）表明， ${\tilde{x}}_i=\sigma \left(i\right)y_{h\left(i\right)}$ 是 $x_i$ 的良好估计。我们在算法 2 和 3 中，将这一思想应用于从低维到高维域的投影 $x\approx S^{\prime }y$ 。这种类型的嵌入无法像 JL 那样为任意点集保持成对距离。然而，Clarkson 和 Woodruff（2013 年）证明，它以恒定概率为整个线性子空间产生子空间嵌入。非正式地说，他们利用了一个事实： $d_e$ 维（活跃）子空间最多只有 $O\left(d_e\right)$ 个坐标是大的（具有高杠杆），因此很重要。这些正是可以合理估计的重击者。其他低值在随机符号的求和过程中大多相互抵消（误差很小）。Nelson 和 Nguyen（2013 年）改进并简化了他们的分析，并通过一个严格的下界补充，将通过计数草图进行子空间嵌入的目标维度确定为 $\mathrm{\Theta }\left(d_e^2/\left({\epsilon }^2\delta \right)\right)$ ，其中 $\delta$ 是失败概率。 我们更正式地定义 $\epsilon$ -子空间嵌入。

Definition 1 ( $\epsilon$ -subspace embedding,cf. Sarlós (2006); Woodruff (2014)). Given a matrix $V\in {\mathbb{R}}^{D\times d_e}$ with orthonormal columns,an integer $d\le D$ and an approximation parameter $\epsilon \in \left(0,\frac{1}{2}\right)$ ,an $\epsilon$ -subspace embedding for $V$ is a map $S:{\mathbb{R}}^D\to {\mathbb{R}}^d$ such that $\mathrm{\forall }x\in {\mathbb{R}}^d$ :
定义 1（ $\epsilon$ -子空间嵌入，参见 Sarlós (2006)；Woodruff (2014)）。给定具有正交列的矩阵 $V\in {\mathbb{R}}^{D\times d_e}$ 、整数 $d\le D$ 和近似参数 $\epsilon \in \left(0,\frac{1}{2}\right)$ ， $\epsilon$ -子空间嵌入对于 $V$ 是一个映射 $S:{\mathbb{R}}^D\to {\mathbb{R}}^d$ ，使得满足 $\mathrm{\forall }x\in {\mathbb{R}}^d$ ：

or, equivalently (cf. Paul et al. (2014); Cohen et al. (2016))
或等价地（参见 Paul 等人（2014）；Cohen 等人（2016））

Note that (1) is closer to the original JL property preserving Euclidean norms and thus distances, but generalized to the entire subspace spanned by $V$ ,while (2) is often analytically more convenient and intuitively states that the isometry property $V^{\prime }V=I_d$ is approximately preserved under the random projection. Note that the definition directly implies that the singular values of an embedded subspace are preserved up to $\left(1\pm \epsilon \right)$ multiplicative distortion,which in particular means that its rank is preserved.
注意，(1)式更接近原始的 JL 性质，即保持欧几里得范数及距离，但推广至由 $V$ 张成的整个子空间；而(2)式通常在分析上更为便利，直观表明随机投影下近似保持了等距性质 $V^{\prime }V=I_d$ 。该定义直接意味着嵌入子空间的奇异值在 $\left(1\pm \epsilon \right)$ 乘性失真范围内得以保持，这尤其表明其秩被保留。

Assuming the existence of a low-dimensional active subspace, Wang et al. (2016b) showed that preserving the rank and controlling the dilation ensures that an optimal point is contained in a low-dimensional projection of this subspace. We improve on their analysis by leveraging the above definition. Our main theoretical contribution is to show that any $\epsilon$ -subspace embedding preserves the mean and variance functions of a Gaussian process with linear kernel, i.e., the standard inner product in Euclidean space. In Sect. 2.4 we further extend this result to other important classes of kernel functions like polynomial kernels, (squared) exponential and Matérn kernels. Note that the guarantee is independent of how the subspace embedding is achieved algorithmically.
假设存在一个低维活跃子空间，Wang 等人（2016b）研究表明，保持秩并控制扩张能确保最优解包含在该子空间的低维投影中。我们通过利用上述定义改进了他们的分析。我们的主要理论贡献是证明任何 $\epsilon$ 子空间嵌入都能保留高斯过程（具有线性核，即欧几里得空间中的标准内积）的均值与方差函数。在 2.4 节中，我们进一步将该结果扩展至其他重要核函数类别，如多项式核、（平方）指数核及 Matérn 核。需注意，该保证与子空间嵌入的算法实现方式无关。

Priors based on Gaussian process regression are popular in BO. Let the error distribution be normal with mean 0 and positive semidefinite kernel $K\left(x,y\right)$ . Then the predictive distribution,given data matrix $X=\left(x_1,\dots ,x_l\right)$ and the vector of their function evaluations $f=\left(f\left(x_1\right),\dots ,f\left(x_l\right)\right)$ , is also normal with mean and variance functions
基于高斯过程回归的先验在贝叶斯优化中广泛应用。设误差分布服从均值为 0、半正定核为 $K\left(x,y\right)$ 的正态分布，则给定数据矩阵 $X=\left(x_1,\dots ,x_l\right)$ 及其函数评估值向量 $f=\left(f\left(x_1\right),\dots ,f\left(x_l\right)\right)$ 时，预测分布同样服从正态分布，其均值与方差函数为...

where $x\in \mathcal{X}$ and $k\left(x\right)$ denotes the vector given by ${(K(x,x_1)\dots K(x,x_l))}^{\prime }$ ,and the kernel matrix is defined by $K_{i,j}=K\left(x_i,x_j\right),i,j\in \left[l\right]$ . By $K^{-}$ we denote the Moore-Penrose pseudoinverse which coincides with the standard inverse but generalizes to non-invertible cases. For the sake of illustration, assume for the moment that we have the simple linear kernel $K\left(x,y\right)=x^{\prime }y$ ,i.e.,the standard inner
其中 $x\in \mathcal{X}$ 和 $k\left(x\right)$ 表示由 ${(K(x,x_1)\dots K(x,x_l))}^{\prime }$ 给出的向量，核矩阵由 $K_{i,j}=K\left(x_i,x_j\right),i,j\in \left[l\right]$ 定义。 $K^{-}$ 表示摩尔-彭罗斯伪逆，它与标准逆矩阵在可逆情况下一致，但推广至不可逆情形。为便于说明，假设我们暂时采用简单的线性核 $K\left(x,y\right)=x^{\prime }y$ ，即标准内积。

product. Then Equations (2) and (3) simplify to
积。则方程（2）和（3）可简化为

Now,to bound the effect of an $\epsilon$ -subspace embedding $S$ under the assumption of low effective dimensionality, consider $V$ ,an orthonormal basis for the active subspace,and $V^{\mathrm{\perp }}$ , an orthonormal basis for its nullspace. We can replace any point $x=Vy+V^{\mathrm{\perp }}z$ by $x^{\mathrm{\top }}=Vy$ ,its projection to the subspace,since $f\left(x\right)=f\left(Vy+V^{\mathrm{\perp }}z\right)=f\left(Vy\right)=f\left(x^{\mathrm{\top }}\right)$ . We stress that $V$ and $V^{\mathrm{\perp }}$ can be arbitrary bases for those subspaces. While Definition 1 and our results do not depend on the representative,it will be convenient to choose $V$ derived from a singular value decomposition (SVD). Our main result states that the Gaussian process in this subspace is simulated very accurately conditioned on the (probabilistic) event that we have an $\epsilon$ -subspace embedding.
现在，为了在低有效维度的假设下约束 $\epsilon$ 子空间嵌入 $S$ 的影响，考虑 $V$ （活动子空间的正交基）和 $V^{\mathrm{\perp }}$ （其零空间的正交基）。我们可以用任意点 $x=Vy+V^{\mathrm{\perp }}z$ 在子空间上的投影 $x^{\mathrm{\top }}=Vy$ 来替代原值，因为 $f\left(x\right)=f\left(Vy+V^{\mathrm{\perp }}z\right)=f\left(Vy\right)=f\left(x^{\mathrm{\top }}\right)$ 。需要强调的是， $V$ 和 $V^{\mathrm{\perp }}$ 可以是这些子空间的任意基。虽然定义 1 及我们的结果不依赖于具体基的选择，但选择源自奇异值分解（SVD）的 $V$ 将更为便利。我们的主要结果表明，在获得 $\epsilon$ 子空间嵌入（概率性事件）的条件下，该子空间中的高斯过程能被高度精确地模拟。

Theorem 2. Consider a Gaussian process that acts directly in the unknown active subspace of dimension $d_e$ with mean and variance functions $\mu (\cdot ),{\sigma }^2(\cdot )$ . Let $\tilde{\mu }(\cdot ),{\tilde{\sigma }}^2(\cdot )$ be their approximations using an $\epsilon$ -subspace embedding for the active subspace. Then we have for every $x\in \mathcal{X}$
定理 2. 考虑一个高斯过程，其直接作用于维度为 $d_e$ 的未知活跃子空间，具有均值与方差函数 $\mu (\cdot ),{\sigma }^2(\cdot )$ 。设 $\tilde{\mu }(\cdot ),{\tilde{\sigma }}^2(\cdot )$ 为使用 $\epsilon$ -子空间嵌入对活跃子空间进行近似的结果。则对于任意 $x\in \mathcal{X}$ ，我们有

Proof. We can express $x=Vy$ and by the SVD we have $X=V\sum U^{\prime }$ . Then for the mean function and its approximation we have by the triangle inequality
证明. 我们可以表示 $x=Vy$ ，并通过 SVD 得到 $X=V\sum U^{\prime }$ 。于是对于均值函数及其近似，根据三角不等式可得

We bound both terms separately
我们分别对两项进行界定

and for the second summand (7),
对于第二个被加数（7），

The last inequality follows from the following two observations. First, the inverse singular values are approximated to within a factor $\left(1\pm 2\epsilon \right)$ by Observation 1 in (Geppert et al., 2017). Thus $\Vert \begin{array}{c}{\left(V^{\prime }{S}^{\prime }SV\right)}^{-}-V^{\prime }V\end{array}\Vert \le 2\epsilon$ . Second,we have
最后一个不等式源于以下两个观察结果。首先，根据（Geppert 等人，2017）中的观察 1，逆奇异值被近似到因子 $\left(1\pm 2\epsilon \right)$ 以内。因此 $\Vert \begin{array}{c}{\left(V^{\prime }{S}^{\prime }SV\right)}^{-}-V^{\prime }V\end{array}\Vert \le 2\epsilon$ 。其次，我们有

Summing up, the triangle inequality implies
综上所述，三角不等式意味着

Similarly, we can show for the variance function that
类似地，对于方差函数我们可以证明

Again we bound items (8)-(11) separately. We have
我们再次分别对条目(8)-(11)进行约束。我们有

and  以及

and  以及

For the last summand, observe
对于最后一项求和，注意到