Re-Examining Linear Embeddings for High-dimensional Bayesian Optimization
Authors: Benjamin Letham
Roberto Calandra
Akshara Rai
Eytan Bakshy
Venue:  (2020)
Keywords: Bayesian optimization
high-dimensional
Gaussian process

Abstract: Bayesian optimization (BO) is a popular approach to optimize resource-intensive black-box functions.
A significant challenge in BO is to scale to high-dimensional parameter spaces while retaining sample efficiency.
A solution considered in previous literature is to embed the high-dimensional parameter space into a lower-dimensional manifold, often a random linear embedding. In this paper, we identify several crucial issues and misconceptions about the use of linear embeddings for BO. We thoroughly study and analyze the consequences of using linear embeddings and show that some of the design choices in current approaches adversely impact their performance. Based on this new theoretical understanding we propose ALEBO, a new algorithm for high-dimensional BO via linear embeddings that outperforms state-of-the-art methods on a range of problems.

Under review as a conference paper at ICLR 2020
RE- RE-EXAMINING LINEAR EMBEDDINGS FOR HIGH-DIMENSIONA BAYESIAN OPTIMIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Bayesian optimization (BO) is popular approach to optimize expensive-to- evaluate black-box functions. A significant challenge in BO is to scale to high- dimensional parameter spaces while retaining sample efficiency. A solution con- sidered in previous literature is to embed the nigh-dimensional parameter space into ovwer-dimensionll manifold, often random linear embedding. In this pa- per, we identify several crucial issues and misconceptions about the use of linear embeddings for BO. We thoroughly study and analyze the consequences of using linear embeddings and show that some of the design choices in current approaches adversely impact their performance. Based on this new theoretical understanding we propose ALEBO, new algorithm for nigh-dimensional BO via linear embed- dings that outperforms state-of-the-an methods on a range of problems, including learning a gait policy for robot locomotion.
INTRODUCTION
Bayesian optimization (BO) is a robust, sample-efficient technique for optimizing expensive-to-
evaluate black-box functions (Mockus 1989, Jones (001T) BO has been successfully applied to diverse applications, ranging from automated machine learning (Snoek et al. 2012, Hutter et al.) 2011) to robotics (Lizotte et al. 2007 Calandra et al. 2015 Rai et al. 2018). One of the most active topics of research in BO is how to extend current methods to higher-dimensional spaces. A common framework tackle this problem is to consider a high-dimensional BO (HDBO) task as a standard BO problem in a low-dimensional embedding, where the embedding can be either linear (typically a random projection) nonlinear (e.g. via multi neural network); see Sec. 2 for full review. An advantage of this framework is to explicitly decouple the problem of finding low-dimensional representations suitable for optimization from the actual optimization technique.
In this paper we study the use of linear embeddings for HDBO, and in particular we re-examine prior efforts use random linear projections. Random projections attractive for BO because, by the Johnson- Lindenstrauss lemma, they can be approximately distance-preseerinng (Johnson & Lindenstrauss 1984) without requiring any data learn the embedding, Random embeddings come with several strong theoretical guarantees, but have shown mixed empirical performance for HDBO.
The contributions of this paper are: 1) We provide new results that identify why linear embeddings have performed poorly in HDBO. We show that existing approaches produce representations that cannot be well-modeled by a Gaussian process (GP), or representations that likely do not contain an optimum (Sec. 4). 2) We construct a representation with better properties for BO (Sec. 5): we improve modelability by deriving a Mahalanobis kernel tailored for linear embeddings and adding polytope bounds to the embedding, and we show how to maintain a high probability that the em- bedding contains an optimum. 3) We show that using this representation for BO outperforms a wide range of previous approaches for HDBO, including test functions up D 1000, and on real- world problems, such as gait optimization multi-legged robot (Sec. b). These include the first results for HDBO with black-box constraints.
2 RELATED WORK
There are generally two approaches to extending BO into high dimensions. The first to produce dowesinnlli embedding, do standard BO in this low-dimensional space, and then project up

---

Under review as a conference paper at ICLR 2020
to the original space for function evaluations. The foundational work on embeddings for BO is REMBO (Wang et al. 2016), which creates a linear embedding by generating a random projection matrix. Sec. Sec.Bprroiice provides thorough description of REMBO and several subsequent approaches based on random linear embeddings (Qian et al., 2016 Binois et al. 2019 Nayebi et al.) 2019). If deriva- tives of are available, the active subspace method can be used recover linear embedding (Con- stantine ct al. 2014; Eriksson et al.] 20118) or approximate gradients can be used (Djolonga et al. 2013). BO can also be done in nonlinear embeddings through VAEs (-ómez-Bombaree
et al. 2018 Lu et al. 2018 Moriconi et al. 2019]. An attractive aspect of random embeddings is that they can be extremely sample-effciint, since the only model to be estimated is a -ww-dimesioonl GP.
The second approach to extend BO to high dimensions is to make use of surrogate models that better handle high dimensions, typically by imposing additional structure on the problem. Work along these lines include GPs with an additive kernel (Kandasamy et al. 2015| Wang et al. 2017 Gardner et al. 2017 Wang et al.) 2018] Rolland et al.) 2018: Mutný & Krause 2018), cylindrical kernels (Oh) et al. 2018 or deep neural network kernels (Antonova al. 2017). Random forest is used as the
surrogate model in SMAC (Hutter et al. 2011). These methods produce trade-offs between sample efficiency of the model and the ability to effectively optimize the acquisition function.
Here, we focus on the embedding approach and in particular the use of linear embeddings for HDBO. Without box bounds, REMBO comes with strong guarantee: with probability 1, the embedding contains an optimum (Wang et al. 2016] Thm. 2). However, if function evaluations are limited to the box bounds, as is typical in BO problems, REMBO requires a collection of heuristics for which there are no longer guarantees on performance. While REMBO can perform well in some HDBO tasks, subsequent papers have found it can perform poorly even on tasks with a true low-dimensional linear subspace (e.g. Nayebi et al. 2019). In this paper, we analyze the properties of linear embeddings as they relate to BO, and show how to improve the representation of the function we seek to optimize.
PROBLEM FRAMEWORK AND REMBO
In this section we define the problem framework and notation, and then describe BO via random linear projections (REMBO) promising method for HDBO-alov with known challenges and follow-up work that has been proposed to address these issues.
Bayesian optimization We consider optimization problems of the form m f(z) where f is a black-box function and B are box bounds. We assume gradients of f are unavailable. The box bounds on æ specify the range of values that are reasonable or physically possible to evaluate. For instance, instance,GGramacy et al. (2016) use BO for an environmental remediation problem in which each at represents the pumping rate of a particular pump, which has physical limitations. The problem may also include nonlinear constraints c, (x) < O where each ej is itself a black-box function. BO is form of sequential model-based optimization, where we construct a surrogate model for f and use that model to identify which parameters should be evaluated next, according to explore-exploit strategy. The surrogate model is typically a GP, ʃ ~ (m))), ().. with mean function m(()) and kernel k(.,-). Under the GP prior, the posterior for the value of f(x) any point in the space is a normal distribution with closed-form mean and variance. Using that posterior, we construct an acquisition function ((z) that specifies the value of function evaluation æ. such as Expected Improvement (EI) (Jones et al. 1998). We find xt E arg max (x)), and evaluate f fx="..
The GP is useful for BO because it provides well-calibrated posterior in closed form. With typical kernels and acquisition functions, axx) is differentiable and can be effectively optimized. However, with typical kernels like the ARD RBF kernel, there are significant limitations. GPs are known to predict poorly in high dimensions, which for GP is D larger than 15-20 (Wang et al.) 2016 Li let al. 2016 Nayebi et al. 2019). This prevents BO from being a useful tool in high dimensions.
In HDBO, the objective f: D + IR operates in a high-dimensional (D) space, which we call the ambient space. When using linear embeddings for HDBO, we assume there exists a low-dimensional linear subspace that captures all of the variation of f. Specifically, let fa R2 - RR d < D, and let T E d 17 be a projection matrix from D down to d dimensions. The linear embedding assumption is that f(x) fa(Tx> Vx R 2 T is unknown, and we only have access to f. not fa. We assume without loss of generality that the box bounds are B = [-1, 1]"; the ambient space can always be
scaled these bounds.
2

---

Under review as a conference paper at ICLR 2020
REMBO: Bayesian optimization via random embedding REMBO (Wang et al. 2016) gener-
ates a random projection matrix A E R Dxxd with each element drawn independently from N (0, 1) to specify de-dimensional embedding. BO is done in the embedding to identify a point y E R' to be evaluated, which is given objective value f' [Aay). The embedding dimension de should satisfy de 2 d for the REMBO guarantee of containing optimum hold.
The main challenges for using REMBO come when dealing with box bounds in the ambient space. We may select a point y in the embedding be evaluated and find that its projection to the ambient space, Ay. falls outside B. The first challenge this poses is a theoretical challenge: IR is guaranteed to contain an optimum, but that optimum is not guaranteed to project up to B. When function evaluations are restricted to the box bounds, the embedding may not contain an optimum it is not difficult to construct examples of this. REMBO has no theoretical guarantees in this setting. The second challenge posed by box bounds is the practical challenge of how function evaluations should be done for points that project up outside B. Here REMBO introduces three heuristics. First, the embedding is given box bounds [-vde, vd. BO will only select points within those bounds to be projected up and evaluated. Second, if point y in the embedding projects up outside B, then it is clipped to B. Let Ps: R R be the L projection that maps æ to its nearest point in B. A point y in the embedding is given objective value (Ay)), which can always be evaluated. Note that clipping to B renders the projection of y to the ambient space nonlinear transformation whenever Ay $ B. Third, the optimization is done with k=4 separate projections, to improve the chances of generating an embedding that contains an optimum inside [-vde, vd de Since these embeddings are independent, no data can be shared across them, which reduces sample efficiency.
Extensions of REMBO Binois et al. (0155) consider the issue of non-injectivity, where the La projection causes many points in the embedding to map to the same vertex of B. They define warped kernel that reduces non-injectivity, which is called REMBO-oky. [Binois et al. (2019) con- -
sider the issue of setting bounds on the embedding. They define projection matrix B E 1 that maps from the ambient space down to the embedding, and replace the L projection with a projec- tion y that maps y to the closest point in B that satisfies Bæ = y. The 7 projection resolves the core challenge of REMBO related to setting bounds in the embedding: we can restrict the optimization in the embedding to points for which Ex E B s.t. Bæ = y. and so heuristic box bounds in the embedding are no longer required. The 7 projection projects to the same points on the facets of B as the 7,2 projection. Paired with the warped kernel of Binois et al. (2015), this is called REMBO-7ku-
Binois (2015) studies different choices for the projection matrix and shows that BO performance can be improved for small d by sampling each row of A from the unit hypersphere $d.-1, If (0, Ia_ ). then TTl is a random sample from gd, so this amounts to normalizing the rows of the usual REMBO projection matrix.
HeSBO (Nayebi et al., 2019) is a recent extension of REMBO that avoids clipping to B and heuristic box bounds in the embedding by changing the projection matrix A. In de 1, it is easy see that the projection matrix A = 1, which sets every xj = y, is optimal. With this projection we can set bounds of [-1, 1] on the embedding and there is no need for L projections because every point in the embedding will map to point in B. HeSBO extends this to de > 1 by setting each row of A to have a single non-zero element, which is randomly set to #1. The column with the non-zero value is chosen uniformly at random. Thus, each parameter in the ambient space is mapped directly to parameter the embedding: x; = +リj, where j is sampled uniformly from (1,...,d, de and + is chosen uniformly at random. The embedding is given box bounds of [-1, 1]de.
4 CHALLENGES WITH LINEAR EMBEDDINGS
Heuristics for handling box bounds when utilizing linear embeddings introduce several issues that impact HDBO performance. We highlight one recent observation from Binois et al. (2019), that most points in the embedding project up outside the box bounds, and discuss three novel observations about how existing methods can make it difficult to learn high-dimensional surrogates.
Projection to the facets of B produces nonlinear distortion in the function. The function value at any point in the embedding is measured as f ((p((A)), For points y that project up outside of B, this will be nonlinear mapping from the embedding the ambient space, despite the use of
3

---

Under review as a conference paper at ICLR 2020
Branin function,
REMBO embedding, -= 100, d.
1.4
1.0
0.5
0.5
0.0
0.0
00.5
0.5
1.0
1..0
-14
1.0
0.5
0.0
0.5
1.0
-1.4
-1.0
00.5
0.0
0.5
1.0
1.4
Hartmann6 function,
6
REMBO embedding, D 100, d,
2
1
0
0.5
-1
-1.0
-1.0
0.5
0.0 0.5 1.0
Figure 1: A visualization of REMBO embeddings for two test functions. (Top left) The Branin function, d=2, extended to D=100. (Top right) A REMBO embedding the D=100 Branin func- tion. (Bottom left) A center slice of the d=6 Hartmann6 function, similarly extended to D=100. (Bottom right) The same slice REMBO embedding of that function. The embedding produces distortions in the function that render it difficult to model.
linear embedding. This has powerful, detrimental effect the ability model f in the embedding. Fig. provides visualizations an actual REMBO embedding for two classic test functions: the Branin (d=2) and Hartmann6 (d=6) functions, both extended D=100 by adding unused variables. The REMBO embedding for the Branin function contains all three optima, however there is visible distortion to the function caused by the the clipping to B. The embedding for the Hartmann6 function even more heavily distorted.
Even if the function is well-modeled by GP in the true low-dimensional space, the distortion pro- duced by the REMBO projection transforms it into one on the embedding that not appropriate for GP. This can happen for any embedding strategy that cannot guarantec all points in the embedding project into B. The distortion induced by mapping to the facet depends on the relative angles of the facet and the true embedding. Projection kernel: each of the 2D facets sits at different angles to the true subspace, and so the change in the rate of function variance will differ for each. To correct for the non-stationarity. we would have to estimate the true subspace T, which with d x D entries is not feasible for D large.
facet essentially induces a -taatiooinn in the
The idea behind using low diwensinsiioal embeddings for HDBO is that it enables the use standard BO techniques on the embedding. However, from these results we see that for the REMBO projec- tion with box bounds we cannot expect to successfully model the function on the embedding with regular GP. The problem is especially acute for de where, as we will see next, nearly all points in the embedding map to one of the 2D facets.
Most points the embedding map to the facets of Fig. shows the probability that an interior point in the embedding projects up the interior of B. This is measured empirically by sampling y uniformly at random from [-vde, / dd. sampling A with A/ 1) entries, and then checking if Ay B (with 1000 samples). Even for small D. with de 2 practically all of the volume in the embedding projects up outside the box bounds, and is thus clipped to a facet of B.
This is issue because it means the optimization will be done primarily the facets of B and not in the interior, which will likely not even be reached a typical BO initialization. We saw in Fig, that the function behaves very differently on points projected to the facets, and that these parts of
4

---

Under review as a conference paper at ICLR 2020
the space be hard to model with GP. The problem cannot be resolved by simply shrinking the box bounds in the embedding. Binois et al. (2019) provide an excellent study of the issue of setting bounds in the embedding and show that with the REMBO strategy there is good way to do this. The projection of B onto the embedding produces a star-shaped object called a zonotope, which has up to 2 Ei=
i=0 (P=') vertices (Ferrez et al. 2005). Shrinking box bounds in the embedding cuts off the vertices of the zonotope and increases the chance of not containing an optimum.
Linear projections do not preserve product ker- nels. Although less visible than that produced by the projection to the facets, there is also distortion to interior points just from the linear projection A. The ARD kernels typically used in GP modeling are product kernels that decompose the covariance into the covariance across each dimension. Inside the embedding, moving along single dimension will move across all dimensions of the ambient space, rates depending on the projection matrix. Con-
0.5
Probability projection satisfies box bounds
* D = 100
0.4
* D = 1000
0.3
0.2
0.1
0.0
sider moving along a single dimension in the em-
1
2
5
bedding, from Y/1 to Y/2 where only a single element has changed. The corresponding points in the am- bient space are æ = Ayı and 22 = Ay2: even though yı and y/2 differ in only one element, 22 will differ in all their elements. Thus product kernel in the true subspace will not produce prod- uet kernel in the embedding; this is shown mathe- matically in Proposition 1
Embedding dimension de
Figure 2: The probability that a randomly se- lected point in the REMBO embedding satis- fies the ambient box bounds after being pro- jected up. For de > nearly all points in the embedding map outside the box bounds.
and
Linear embeddings have low probability of containing optimum. HeSBO avoids the challenges of REMBO related to box bounds: all interior points in the embedding map to interior points of B, and there is no need for the L projection and thus the ability model in the embedding is improved. However, for de >> 1 there no guarantee that the embedding will contain an optimum, and in fact the probability of containing an optimum can be quite low. Consider the example of an axis-aligned true subspace: f operates only on some set of d elements of æ, which we denote = (ii)....aa). For d and de 2, there are three possible embeddings: Fi, and Fig map to different features in the embedding, Zi, Fig. or Ij, visualized in Appendix [A.] In the first case the embedding successfully captures the entire true subspace and we can expect the optimization to be successful. However, in the other two cases the embedding is only able to reach the diagonals of the true subspace, which, unless f happens to the diagonal, will not reach the optimal value. Under a uniform prior the
-ii-- These three embeddings are
have an optimum location of optima, we can compute analytically the probability that the HeSBO embedding contains an optimum (see Appendix A. The probability is independent of D, but is low for moderate values of d. For instance, with d = 6, de = 20 gives only a 44% chance of recovering an optimum.
Relative to REMBO, HeSBO improves the ability effectively model and optimize in the embed- ding, but reduces the likelihood of the embedding containing an optimum. Empirically, this trade-off' leads to HeSBO having better BO performance than REMBO. Like HeSBO, here we wish elimi- nate the L projection and thus improve our ability to model and optimize in the embedding. We will show that this can be done while maintaining a much higher chance of the embedding containing an optimum, which will further improve BO performance.
LEARNING AND OPTIMIZING IN LINEAR EMBEDDINGS
We now show how to overcome the embedding issues described in Sec. Similarly to Binois et al. 2019), we define the embedding via a matrix B E < that projects from the ambient space down to the embedding, and fø f(Biz) as the function evaluated on the embedding, where B denotes the matrix pseudo-invers inverse. The new techniques we develop here are applicable to any linear embedding, not just random emheddings.
5

---

Under review as a conference paper at ICLR 2020
5.1 A KERNEL FOR LEARNING IN LINEAR EMBEDDING
As discussed in Sec. 4 a product kernel over dimensions of the true subspace (ARD) does not trans- late to product kernel over dimensions in the embedding. However, stationarity in the subspace does imply stationarity in the embedding, and this result gives the appropriate kernel structure.
Proposition Suppose the function on the true subspace is drawn from GP with an ARD RBF kernel: Ja GP (ml)), kear(:, For any pair of points in the embedding y and y'.
fa())) = o2
- (y')
where o² is the kernel variance of fa and I E Rddxde is symmetric and positive definite.
Proof. To determine the covariance in function values of points in the embedding, first project up to the ambient space and then project down to the true subspace
fB(y) = f(B fa(TB' y).
Then,
Covlfe()), = (T
= 0² exp (-(TB'y- -
where D diag 22 follows that I is symmetric and positive definite.
Let -
Because D is positive definite,
27
This kernel replaces the ARD Euclidean distance with a Mahalanobis distance, and we refer to as the Mahalanobis kernel. Similar kernels have been used for GP regression in other settings (Vivarelli & Williams) 1999: Snnlssn & Ghahramani] 2006). This result shows that the impact of de(d++1)
the linear projection on the kernel can be correctly handled by fitting a 2 -parameter distance metric rather than the typical de-parameter ARD metric. The use of this kernel is vital for obtaining good model fits in the embedding. Appendix A shows GP predictive performance on a linear embedding of the Hartmann6 function, in which ARD RBF kernel entirely fails to predict, while the Mahalanobis kernel does not. We handle uncertainty in I by posterior sampling from a Laplace approximation of its posterior; this is described in the appendíx.
5.2 AVOIDING NONLINEAR PROJECTIONS
The most significant distortions in Fig. I result from clipping projected points to B. We can avoid this by constraining the optimization in the embedding to points that do not project up outside the bounds, that is, Bi E B. Let a(y) be the acquisition function evaluated in the embedding that we wish to optimize. We select the next point to evaluate by solving
max a(y) subject to VER
1 1 Bt B1 1
(1)
Note that there are no box bounds on the embedding. The constraints -1 S B'y S 1 form polytope, which is convex and can be efficiently optimized over with off-the-shelf optimization tools. Appendix A.3 provides visualizations of the embedding subject to these constraints. Within this space, the projection is entirely linear and can be effectively modeled with the GP described in Sec. 5.1
5.3 THE PROBABILITY THE EMBEDDING CONTAINS AN OPTIMUM
Restricting the embedding with the constraints in (1) eliminates distortions from clipping to B, but it also reduces the volume of the ambient space that can be reached from the embedding and thus reduces the probability that the embedding contains an optimum. To understand the performance of BO in the linear embedding, it is critical understand this probability, which denote Popt- Recall that even with clipping, the REMBO theoretical result does not hold when function evaluations are restricted box bounds, and so even REMBO will generally have Po < 1.

---

Under review as a conference paper at ICLR 2020
6
d 10
Probability embedding contains optimizer
1.0
0.8
0.6
REMBO
HeSBO
Hypersphere
0.0
10
15
20
5
10 15
20
5
15
Embedding dimension de
Embedding dimension d.
Eibbedding dimennsoon de
Figure 3: Probability the embedding contains optimum (Pups) when restricted the constraints of I under a uniform prior for the location of the optima and D = 100, for three embedding strategies. Setting de > d rapidly increases Popt. and high probabilities can achieved with reasonable values of de. Hypersphere sampling produces the best embedding, particularly for d small.
Pops depends on where the optima are in the ambient space-for for instance, an optimum at will always be contained in the embedding. Suppose the true subspace has an optimum at x". Then, OTT =²) = (æ: To = 2"} defines the set of optima in the ambient space. We wish to determine if any of these optima can be reached from the embedding. The points æ that can be reached from the embedding are those for which there exists a y in the embedding that projects up to æ, that is, B = Since the embedding itself is produced from the projection Bx, {(B) defines the set of points in ambient space that can be reached from the embedding. The embedding contains optimum if and only if the intersection OTT 2 E(B) n B is non-empty. Given prior for the locations of optima (that is, over T and )) we can compute Papt as
{x: B Bx = x}
Popt EB,T,* )n(()==))
(2)
Importantly, O(T, =²), EB)), and B all polyhedra, so their intersection can be tested by solving a linear program (see Appendix A.44). The expectation can be estimated with Monte Carlo sampling from the prior over T and x* and from the chosen generating distribution of B.
For our analysis here, we give T a uniform prior over axis-aligned subspaces as described in Sec. and we give 2" uniform prior in that subspace. Under these uniform priors, we can evaluate (2) to compute Paps as a function of B. D, d, and de. Fig. shows these probabilities for D = 100 as function and de, for three strategies for generating the projection matrix: the REMBO strategy of (0, 1), the HeSBO projection matrix, and the unit hypersphere sampling described in Sec. Increasing de above dl rapidly improves the probability of containing an optimum. For d = with de 6 the probability is nearly O, while increasing de to 12 is sufficient to raise it to 0.5 and with de = 20 it is nearly 1. Across all values and de, hypersphere sampling produces the embedding with the best chance of containing optimum. Appendix A.4 shows Popt for more values of D and d. By using hypersphere sampling and selecting de > d, we can maintain a high Paps while still avoiding clipping to B.
5.4 A NEW METHOD FOR BO WITH LINEAR EMBEDDINGS: ALEBO
We combine the results and insight gained into a new method for HDBO, which we call adaptive linear embedding BO (ALEBO), since the kernel metric and embedding bounds are adapted with the choice of B. The approach is given in algorithm form in Algorithm [ Code is available at github. com/ www.omiiedddaooooooooooeo review] Line 1 the embedding is specified by generating random projection matrix. We use hypersphere sampling, which gave the best Papi in Fig. BJmon strategies tried here, but this could be replaced with a different projection strategy should one be more appropriate for particular setting.
6 BENCHMARK EXPERIMENTS
We evaluate the performance of ALEBO on synthetic HDBO tasks, and compare its performance to broad selection of HDBO methods. We include in these benchmarks: REMBO and HeSBO;

---

Under review as a conference paper at ICLR 2020
Algorithm 1: ALEBO method for high-dimensional BO in a linear embedding.
Data: D. des Tlinis TIOO-
Result: Approximate optimizer x².
Generate random projection matrix by sampling points from the hypersphere S
2 Generate Winnt random points y' in the embedding using rejection sampling to satisfy polytope J(B y") Ne
Let D = [
be the initial data.
for j = 1 ,...; Tloo do
Fit GP by maximizing marginal log-likelihood of DD with the Mahalanobis kernel.
Draw posterior samples of I using Laplace approximation. Marginalize over the posterior
with moment matching.
Use the GP to find y that maximizes the acquisition function according Update DD with ((Bgg))
return B Bly", """""""o""" the best point y"
REMBO variants Φke (Binois et al. 2015) and 7he (Binois et al. 2019); additive kernel methods Add-GP-UCB (Kandasamy et al.] 2015) and Ensemble BO (HBO) (Wang et al.] 2018); SMAC, which uses a random forest model: CMA-ES, an evolutionary strategy (Hansen et al., 2003); and quasirandom search (Sobol). For ALEBO we took de 2d for these experiments. In their evaluation of HeSBO, Nayebi et al. (019)) used de 2d when d = 2 but de = d on the Hartmann6 problem. Our results Fig. 3 indicate that with d 6 HeSBO will have much higher chance of reaching an optimum with de 2d, so we evaluate this alongside their original choice of de =
Fig. shows optimization performance for three HDBO tasks: the Branin problem extended to D=100 as described above; the Hartmann6 problem extended to D=1000; and the Gramacy prob- lem extended D=100. The Gramacy problem (Gramacy al.) 2016) includes two black-box straints. The linear embedding methods (ALEBO, REMBO, and HeSBO) can naturally be extended constrained optimization described in Appendix A.5 The D=100 problems were repeated with 50 runs, and the D=1000 problem was repeated with 25 runs. Appendix 6.6 provides additional de- tails of the benchmark methods, additional experimental results (including plots of log regret and error bars), and an extended analysis of the results.
For all problems, ALEBO had the best average optimization performance. Relative other linear embedding approaches, ALEBO also had low variance in the final best-value, which is important in real applications where one can typically only run one optimization run. For the D=1000 problem, REMBO-ykp. EBO, and Add-GP-UCB did not finish single run after 24 hours and so were termi- nated and not included in the results. These methods, along with SMAC and CMA-ES, also do not not included in the results for the Gramacy problem.
support blackbox constraints and
We used the Branin problem to explore the sensitivity of optimization performance to and de, by varying de from 2 to 8 and D from 50 to 1000. We found that de = d performed significantly worse than larger values, but for de > d and across all values of there was little change in the BÔ performance. Figures with these results are in Appendix A.6
7 POLICY SEARCH FOR ROBOT LOCOMOTION
Next, we evaluate our approach on hexapod robot simulation for learn- ing walking controllers. Sample efficiency is crucial in robotics as col- lecting data on real robots is time consuming and can cause wear-and- tear on the robot. We optimize the walking gait of the simulated hexapod robot "Daisy" (Hebi Robotics 2019). The Daisy robot is simulated in PyBullet (Coumans & McCutchan, 2008), and has legs with motors in each leg, as shown in Fig. 5] The goal is to learn the policy parame- ters that enable the robot to walk to a target location while avoiding high joint velocities and height deviations. More details about this task can be found in Appendix A.7
Figure 5: The simulated hexapod robot Daisy.
8

---

Under review as a conference paper at ICLR 2020
ALEBO REMBO
HeSBO, d,=d HeSBO, d,=2d
REMBO- okp
BBO
SMAC
REMBO-yko
Add-GP-UCB
CMA-ES
Sobol
Branin, d=2, 100
Best valuue found
15
Final value
4
10
2
10
Hartmann6, d=6, 1000
Best value found
Final value
100
150
200
Gramacy, d=2, D 100
1.0
Bost valtie found
Final value
1.2
0.8
1.0
0.7
0.6
0.6
0
10
20
30
40
50
ALEBO
REMBO
HeSBO, d. d.
HeSBO, d. =2
REMBO- 4kk
REMBO- kyp
HB0
Add-CP-UCB
SMAC
CMA-ES
Sobol
Function evaluations
Figure 4: Optimization performance on three HDBO minimization problems. For each row, the left plot shows the best value by each iteration, averaged over repeated runs. The right plot shows the distribution of the best value at the final iteration. For all three tasks, ALEBO achieved the best average performance, and had the lowest variance in final performance of the linear embedding methods.
We use Central Pattern Generator (CPG) (Crespi & Ijspeert 2008) with robot. The CPG controller induces cyclical motion in each joint of the robot. Different param- eters of the CPG change the phase, amplitude, frequency, and offset each joint. While the 72- dimensional controller assumes that each joint is independent of the others, one could construct lower-dimensional embedding by coupling multiple joints. For example, the tripod gait in hexapods assumes three sets of legs synced, and out of phase with the remaining three legs. The dimension- ality of the CPG controller can be reduced to dimensions by restricting the movement to a tripod gait, and learning the common amplitude, offset and frequency of the joints. The existence of such
to control the

---

Under review as a conference paper at ICLR 2020
ALERO
REMBO
H&SBO
Sobal
20
Value at final iteration
Best value found
0
100
200
300
500
ALEBO
REMBO
HcSBO
Sobol
Function evaluations
Figure 6: Optimization performance on the 72 hexapod locomotion task (higher is better). (Lefft) Mean and two standard errors (over 50 repeated runs) of the best value found by each iteration. (Right) Distribution of the best value found across repeated runs. ALEBO had the best average performance, and the lowest variance.
low-dimensional parameterizations motivates the use of ALEBO for learning the parameters of CPG controller, although it is not known if there is linear low-dimensional representation. In real robot, each motor can have different physical properties, such as friction, damping, etc. This could make pre-defined constrained space sub-optimal, and could benefit from learning with flexible embedding, as ALEBO.
Fig. shows optimization performance for the linear embedding methods this task, which is maximization problem. ALEBO improves on the state-of-thh-aar with both higher mean perfor- mance and lower variance (thus, a lower chance of poor performance). Expert tuning achieve reward values above 40, so while ALEBO is an advance in terms of linear embedding BO, there is still much room for additional work in nigh-dimensional BO.
DISCUSSION
Our work highlights the importance of two basic requirements for an embedding to be useful for optimization that are often not examined critically by the literature: 1) the function must be well- modeled on the embedding: and 2) the embedding should contain an optimum. To the first point, we showed how polytope constraints a Mahalanobis kernel appropriate for GP modeling in a linear embedding. These two contributions allow effective modeling in the embedding space. To the second point, developed approach for computing the probability that the embedding contains an optimum, which we then used to construct embeddings with higher chance of containing optimum, via hypersphere sampling and selecting de larger than d.
the embedding eliminate boundary distortions, and we derived
These same considerations are important for any embedding, not not just linear. For instance, when constructing a VAE for BO it will be equally important to ensure the function remains well-modeled on the embedding and that box bounds are not handled in a way that adds distortion. We must also ensure that the VAE embedding captures enough of the ambient space to have a high chance of containing an optimum. With linear embeddings we were able to derive analytical quantities for answering these questions-mov work in this area is needed for nonlinear embeddings. Here we applied linear constraints restrict the acquisition function optimization to points that project up inside the ambient box bounds. For VAE these constraints will be general nonlinear functions, but their gradients can backpropped and so constrained optimization could be done in a similar way.
Given D and d, we can solve to determine the probability of containing optimum for any des and thus select de based on a desired target probability. We showed on test problems that BO per- formance not too sensitive the exact choice of de. In reality, such in the robot locomotion task, we do not know d, or even if the problem has low-dimensional linear structure. In this case selecting appropriate embedding dimension remains important open question.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Rika Antonova, Akshara Rai, and Christopher G Atkeson. Deep kernels for optimizing locomotion controllers. In Ist Conference on Robot Learning, CoRL, pp. 47-56, 2017.
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Bytan Bakshy. BoTorch: Programmable Bayesian optimization in PyTorch. arXiv preprint arXiv:1910.06400. 2019.
Mickaël Binois. Uncertainty quantification on Pareto fronts and high-dimensional strategies in Bayesian optimization, with applications in multi-objectiin automotive design. PhD thesis, Ecole Nationale Supérieure des Mines de Saint-Ftienne, 2015.
Mickaël Binois, David Ginsbourger, and Olivier Roustant. A warped kernel improving robustness in Bayesian optimization via random embeddings. In Proceedings of the International Conference on Learning and Intelligent Optimization. LION, pp. 281-286. 2015.
Mickaël Binois, David Ginsbourger, and Olivier Roustant. On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of Global Optimization, 2019.
Roberto Calandra, André Seyfarth, Jan Peters, and Mare P. Deisenroth. Bayesian optimization for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76(1):5-23, 2015.
Paul G. Constantine, Eric Dow, and Qiqi Wang. Active subspace methods in theory and practice: applications to Kriging surfaces. SIAM Journal on Scientific Computing, 36:A 06.A1500-11524, 2014.
Erwin Coumans and John McCutchan, Pybullet simulator.
https:://ithub.. com/
Bolletphyssics/bulett 2008. Accessed: 2019-09.
Alessandro Crespi and Auke Jan Ijspeert. Online optimization of swimming and crawling in an amphibious snake robot. IEEE Transactions on Robolics, 24(1):75-87, 2008.
Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional Gaussian process bandits.
In Advances Neural Information Processing Systems 26, NIPS, pp. 1025-1033, 2013.
David Eriksson, Kun Dong. Eric Hans Lee, David Bindel, and Andrew Gordon Wilson. Scaling Gaussian process regression with derivatives. In Advances in Neural Information Processing Systems 31, NIPS, pp. 6867-6877, 2018.
Jean-Albert Ferrez, Kornei Fukuda, and Th. M. Liebling. Solving the fixed rank convex quadratic maximization in binary variables by parallel zonotope construction algorithm. European Journal of Operational Research, 166(1):35-55 2005.
Jacob Gardner, Chuan Guo, Kilian Q. Weinberger, Roman Garnett, and Roger Grosse, Discovering and exploiting additive structure for Bayesian optimization. In Proceedings of the 20th Interna- tional Conference on Artificial Intelligence and Statistics, AISTATS, pp.
2017.
Jacob R. Gardner, Matt J. Kusner, Zhixiang Xu, Kilian Q. Weinherger, and John P. Cunningham. Bayesian optimization with incquality constraints. In Proceedings of the 31st International Con- ference Machine Learning, ICML, 2014.
Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobatoo Sänchez--engeling,
Benjamín Sánchez-I Lengeling, Dennis Sheherla, Jorge Aguilera-Iparraguirre Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru- Guzuk. Automatic chemical design using data-driven contin- uous representation of molecules. ACS Central Science, 4(2):268-276, 2018.
Robert B. Gramacy, Genetha A. Gray, Sébastien Le Digabel, Herbert K. H. Lee, Pritam Ranjan, Garth Wells, and Stefan M. Wild. Modeling an augmented Lagrangian for blackbox constrained optimization. Technometries, 58(1 1811), 2016.
Nikolaus Hansen, Sibylle D. Miler, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 1 11(1):1-18, 2003.

---

Under review as a conference paper at ICLR 2020
Hebi Robotics. robotic-kits
Daisy hexapod, 2019.
Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brows Sequential model-based optimization for general algorithm configuration. In International Conference Learning and Intelligent Optimization, LION, pp- 507-523, 2011.
William Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into Hilbert space. Contemporary Mathematics, 26(1 89-2066:1, 1984.
Donald R. Jones. A taxonomy of global optimization methods based on response surfaces. Journal of Global Optimization, 21(4):345-385 383, 2001.
Donald R. Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expen- sive black-box functions. Journal of Global Optimization, 13:455-492, 1998.
Kirthevasan Kandasamy, Jeff Schneider, and Barnabás P6ezos, High dimensional Bayesian optimi- sation and bandits via additive models. In Proceedings of the 32nd International Conference on Machine Learning, ICML, pp. 295-304, 2015.
Johannes Kirschner, Mojmir Mutný, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adap- tive and safe bayesian optimization in high dimensions via one-dimensional subspaces. In Pro- ceedings of the 36th International Conference on Machine Learning, ICMI., 2019.
Benjamin Letham, Brian Karrer, Guilherme Ottoni, and Eytan Bakshy. Constrained Bayesian opti- mization with noisy experiments. Bayesian Analysis, 14(2):495-51) 2019.
Chun-Liang Li, Kirthevasan Kandasamy, Barnabás Póczos, and Jeff Schneider. High dimensional Bayesian optimization via restricted projection pursuit models. In Proceedings of the 19th Inter- national Conference Artificial Intelligence and Statistics, AISTATS, pp. 884-892 2016.
Daniel J. Lizotte, Tao Wang, Michael Bowling, and Dale Schuurmans. Automatic gait optimization with Gaussian process regression. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAL, pp. 944-949, 2007.
Xiaoyu Lu, Javier González, Zhenwen Dai, and Neil Lawrence. Structured variationally auto- encoded optimization. In Proceedings of the 35th International Conference on Muchine Learning. ICML, pp. 3267-3275, 2018.
Jonas Mockus. Bayesian approach to global optimization: theory and applications. Mathematics and its Applications: Soviet Series. Kluwer Academic, 1989.
Riccardo Moriconi. K. S. Sesh Kumar, and Mare Deisenroth. High-dimensional Bayesian opti- mization with manifold Gaussian processes. arXiv preprint arXiv: 2019.
Mojmúr Mutný and Andreas Krause. Efficient high dimensional Bayesian optimization with addi- tivity and quadrature Fourier features. In Advances in Neural Information Processing Systems 31, NIPS, pp. 9005-9016, 2018
Amin Nayebi, Alexander Munteanu, and Matthias Poloczek. A framework for Bayesian optimiza- tion in embedded subspaces. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 4752-4761, 2019.
Chang Yong Oh, Efstratios Gavves, and Max Welling. BOCK : Bayesian optimization with cylindri- cal kernels. In Proceedings of the 35th International Conference on Machine Learning, ICML, pp. 3868-3877, 2018.
Hong Qian, Yi-Qi. Hu, and Yang Yu. Derivative-free optimization of figh-dimensional non-convex functions by sequential random embeddings. In Proceedings of the 25th International Joint Con- ference on Artificial Intelligence, IJCAI, 2016.
Akshara Rai, Rika Antonova, Seungmoon Song, William Martin, Hartmut Geyer, and Christo- pher G. Atkeson. Bayesian optimization using domain knowledge on the ATRIAS biped. In Proceedings of the IEÉE International Conference on Robotics and Automation, ICRA, pp. 1771 1778, 2018
12

---

Under review as a conference paper at ICLR 2020
Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. High- dige-dimensional Bayesian optimization via additive models with overlapping groups. Proceedings of the 2 Interna- tional Conference on Artificial Intelligence and Statistics, AISTATS, pp. 298-307, 2018.
Edward Snelson and Zoubin Ghahramani. Variable noise and dimensionality reduction for sparse Gaussian processes. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelli- gence, UAI, pp. 461-468, 2006.
Jasper Snoek, Hugo Larochelle, and Ryan Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems 25, NIPS, pp. 2951- 2959, 2012.
Francesco Vivarelli and Christopher K. Williams. Discovering hidden features with Gaussian processes regression. In Advances in Neural Information Processing Systems 11, pp. 613-619, 1999.
Zi Wang, Chengtao Li, Stefanie Jegelka, and Pushmeet Kohli. Batched high-dimensional Bayesian optimization via structural kernel learning. In Proceedings of the 34th International Conference on Machine Learning. ICML, pp. 3656-3664 2017.
Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanic Jegelka. Batched large-scale Bayesian optimization in high-dimensional spaces. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, AISTATS, 2018
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando de Feitas. Bayesian op- timization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
13

---

Under review as a conference paper at ICLR 2020
A APPENDIX
This appendix contains a number additional results and analyses to supplement the main text.
A. HESBO EMBEDDINGS
We consider HcSBO embeddings in the case of random axis-aligned true subspace. and uniform prior on the location of the optimum within that subspace. As explained in Sec. 4 with = and this prior, regardless of de D there three possible embeddings: (1) each of the active parameters are captured by a parameter in the embedding: (2) the embedding is constrained to the diagonal 24 Zizi (3) the embedding constrained the diagonal Ii. -22 Fig. shows these three embeddings for the Branin problem from the top row of Fig.
Within the first embedding, the optimal value of 0.398 can be reached. Within the second, the best value is 0.925 and within the third it is 17.18. Under a uniform prior on the location of the optimum within random axis-aligned true subspace, it is easy to compute the probability that the HeSBO embedding contains an optimum:
da!
(opr (de djld?
(3)
For d = 2, this exactly the probability of the first embedding shown in Fig. 7 This probability increases with de, and is exactly the probability shown in Fig.
A.2 THE MAHALANOBIS KERNEL
When fitting the Mahalanobis kernel derived Proposition [ we use an approximate Bayesian treatment of I to improve model performance while still maintaining tractability. We propagate uncertainty in P into the GP posterior by first constructing posterior for using a Laplace approx- imation with diagonal Hessian, and then drawing samples from that posterior. The marginal posterior for fyy can then be approximated as:
m
p(f())) E((())) m
Because of the GP prior, each conditional posterior ((f()) is normal distribution with known mean 14; and variance of- Thus the posterior p(f(y)) is a mixture of Gaussians, which we can approximate using moment matching:
p(f(v)) x N
N4:
1
o Vari(us))
1.0
0.5
0.0
0.5
-1.0
0..5
0.0
0.5
1.0
-10
00.5
1.0
-0.5
1.0
I1
Figure 7: Three possible HeSBO embeddings of the 2 Branin function. (Left) The first em- bedding fully captures the function, and thus captures all three optima. (Middle) The second is restricted the subspace Ø1 - -2. This subspace does not contain an optimum, but comes fairly close. (Right) The third embedding is restricted to the subspace I I2 and does not come close to any optima.
14

---

Under review as a conference paper at ICLR 2020
Mahalanobis point estimate
Mahalanobis posterior sampled
ARD RBF
Model prediction
0.5
0.5
-1.0
1.0
-1.
1.5
-2
-3
-2.5
-2.5
True value
True value
True value
Figure 8: Test-set model predictions for three GP kernlls on the same train/test data generated by evaluating the Hartmann6 D=100 function on a fixed linear embedding. A typical ARD kernel fails learn and predicts the mean. The Mahalanobis kernel predicts well, and posterior sampling is important for getting reasonable predictive variance.
0.5
Average test test-sel set log likelihood
0.5
-1.0
-1.5
2.0
2.5
Mahalanobis, sampled
-3.0
ARD RBF
150
Training set size
Figure 9: Average test-set log likelihood as a function of training set size, for training sets randomly sampled from a fixed linear embedding. Log marginal probabilities were averaged over a fixed test set of 1000 random points. For each training set size, 20 random training sets were drawn of that size and the figure shows the average result over those draws (with error bars two standard errors). The ARD RBF kernel continues predict the mean the training set size is increased, while the Mahalanobis kernel is able to learn as the training set is expanded.
We do this to maintain Gaussian posterior, under which acquisition functions like El have analytic form and can easily be optimized, even subject to constraints as in [T].
We show the importance of the Mahalanobis kernel using models fit to data from the Hartmann6
D=100 function, from Fig. [ We generated a projection matrix B using hypersphere sampling define 6-d linear embedding. We then generated training set (100 points) and test (50 points) within that embedding (that is, within the polytope given by (I)) using rejection sampling. We fit three GP models with different kernels to the training set, and then evaluated each on the test set: typical ARD RBF kernel in 6 dimensions, the Mahalanobis kernel using a point estimate for T, and the Mahalanobis kernel with posterior marginalization for T as described above.
Fig. 8 compares model predictions for each of these models with the actual test-set outcomes. With an ARD RBF kernel, the GP predicts the function mean everywhere, which is typical behavior of GP that has failed to learn the function. With the same training data, the Mahalanobis kernel is able to make accurate predictions on the test set. Using a point estimate for significantly underestimates the predictive variance, which is rectified by using posterior sampling described above. In BO exploration is driven by model uncertainty, so well-calibrated uncertainty intervals are especially important.
15

---

Under review as a conference paper at ICLR 2020
40
20
20
32
20
-20
40
10
-20
20
10
-50
25
0
25
50
Figure 10: (Left) An embedding from a A((0,) 1) projection matrix on the same Branin D = 100 problem from Fig. subject to constraints of ① (Right) The embedding from the same projection matrix after normalizing the columns to produce unit circle samples. Sampling from the unit circle increases the probability that optimum will fall within the embedding, and polytope bounds avoid nonlinear distortions.
Fig. 9 evaluates the predictive log marginal probabilities for the ARD RBF kernel and the Maha- lanobis kernel with posterior sampling across a wide range of training sets with different sizes (with- out posterior sampling, Fig. 8 shows that the Mahalanobis point estimate significantly under covers and so has very poor predictive log marginal probabilities). We used the same linear embedding and Hartmann6 D=100 function used in Fig. S to sample 1000 test points which
held fixed. For each of 8 training set sizes ranging from 40 to 200, we randomly sampled 20 training sets from the embedding. For each training set, fit the two GPs, made predictions and then computed the average marginal log probability of the true values. Fig. 9 shows that as we vary the training size from 40 200, the ARD RBF kernel continues to predict the mean, in Fig. 88 even 200 points in the 6-d embedding are not sufficient to learn. For small training set sizes, the Mahalanobis kernel (with sampling) has high variance log likelihood, as it has the potential to overfit and thus under cover. But for training set sizes of 50 and greater it had better predictive log likelihood than the ARD RBF, and continued to learn as the training set size was increased. For small datasets, the Mahalanobis kernel can overfit and thus have poor predictive likelihood, but for the purposes of BO, overfitting can be better than not fitting at all (predicting the mean), even when predicting the mean has better predictive log likelihood. This can be seen in the optimization results (Figs. and where ALEBO shows strong performance even with less than 50 iterations.
the 1000 test points,
A.3 POLYTOPE BOUNDS ON THE EMBEDDING
Rather than using projections to the box bounds B, we specify polytope constraints in (T. Fig. 10 illustrates the embedding with these constraints for the same Branin D 100 problem from the top row of Fig. [ The embedding in the left figure was created with the REMBO strategy sampling each entry from (0 1). For the embedding in the right figure, that same projection matrix had each column normalized. This converts the projection matrix to be a sample from the unit circle, as described in Sec. 4
The (O, 1) embedding does not contain any optima within the polytope bounds. Converting that projection matrix to a hypersphere sample rounds out the vertices of the polytope and expands the space to capture two of the optima. Consistent with Fig. 3 we see that hypersphere sampling significantly improves the chances of the embedding containing optimum. Fig. 10 also shows that with the polytope bounds, we avoid the nonlinear distortions seen Fig.
A.4 EVALUATING THE PROBABILITY THE EMBEDDING CONTAINS AN OPTIMUM
As in other parts of the paper, we consider a uniform prior on the location of the optimum within random axis-aligned subspace. A random true projection matrix T is sampled by selecting d columns at random and setting each to one of the d-dimensional unit vectors. x is then sampled uniformly random from [- 11. 1]d B is sampled according the desired strategy, which in experiments was REMBO. HeSBO, or hypersphere. Given these three quantities, we can evaluate whether not B contains optimum subject to the constraints of [ by solving the following
16

---

Under review as a conference paper at ICLR 2020
D 50
D 100
D 200
True subspace dimension d
18
1.00
14
0.75
10
0.50
0.25
0.00
6
14
2
10
14
18
10
18
Embodding de
Embodding de
Embodding de
Figure 11: Popt for hypersphere sampling, estimated in Fig. but here for wider range of values of d and D. Contour color indicates Pom- Doubling D decreases Pom for d and de fixed, however D 200, high values of Pop with reasonable values of d, can be had for many values of d.
linear program:
maximize 0
subject Tw z",
(B B I) = 0, x 2 -1,
x S
If this problem is feasible, then the embedding produced by B contains an optimum. If it is infea- sible, then does not. Solving this over many draws of T, z", and produces an estimate of Poot under that prior for the location of optima. Here we used uniform prior, but this linear program can be taken to compute Popt under any prior.
Fig. 11 shows Papi for wide range of values of d and D, for hypersphere sampling. Across this wide range we see that for many values of d we can achieve high values of Pap with reasonable values of de, even for relatively high values of D.
A.5 HANDLING BLACK-BoL -Bo CONSTRAINTS OPTIMIZATION
DIMEESIINNSI BAYESIAN
In many applications BO, in addition the black-box objective f there are black-box constraints Cj and we seek to solve the optimization problem
minimize f(x) subject cx(x) S 0, j= 1=1,...,JJ
a 2EB
In most settings the constraint functions cj are evaluated simultaneously with the objective Con- straints are typically handled in BO by fitting a separate GP to each outcome (that is, to ff and to each e,). The acquisition function is then modified to consider not only the objective value but also whether the constraints are likely to be satisfied (e.g., Gardner et al. 2014p.
The extension of BO in an embedding constrained BO straightforward, so long as the same embedding is used for every outcome. A separate GP (in our case, using the Mahalanobis kernel) is fit to data from each outcome. Because the embedding is shared, predictions can be made for all of the outcomes any point in the embedding. This allows us evaluate and optimize acquisition function for constrained BO in the embedding. Once point is selected, is projected up to the ambient space and evaluated f and each cj usual. Random projections especially well- suited for constrained BO because there is no harm in requiring the same projection for all outcomes, since it random projection anyway.
17

---

Under review as a conference paper at ICLR 2020
A.6 ADDITIONAL EXPERIMENTAL RESULTS
Here we provide results from additional problem (Hartmann6 D=100), three additional methods (LineBO variants), and provide study the sensitivity of ALEBO performance to de and D. We also provide implementation details for the experiments.
A. METHOD IMPLEMENTATIONS AND EXPERIMENT SETUP
The linear embedding methods (REMBO, HeSBO, and ALEBO) were all implemented using BoTorch, framework for BO in PyTorch (Balandat et al. 2019), and so used the same acquisi- tion functions and the same tooling for optimizing the acquisition function. El was the acquisition function for the Hartmannó and Branin benchmarks, and NEI (ettham al., 2019) was used to handle the constraints in the Gramacy problem. ALEBO and HeSBO were given a quasirandom ini- tialization 10 points from a scrambled Sobol sequence. REMBO was given a Sobol initialization of 2 points for each of its 4 projections used within run.
The remaining methods used reference implementations from their authors with default settings for the package: REMBO-şKu and REMBO-7kK EBC Add-GP-UCB P] SMA CMA-ES and Coordinatel.nneBC Randoml.ineBe and Descentl .ineB EBO requires an estimate of the best function value, and for each problem was given the true best function value. SMAC and CMA-ES require an initial point, and were given the point at the center of the ambient space box bounds.
The function evaluations for all problems were noiseless, so the stochasticity throughout the run and in the final value all comes from stochasticity in the methods themselves. For linear embedding methods the main sources of stochasticity are in generating the random projection matrix and in the quasirandom initialization.
A.6.2 ANALYSIS OF EXPERIMENTAL RESULTS
Fig. 12 provides different view of the benchmark results of Fig. showing log regret for each method, averaged over runs with eтror bars indicating two standard errors of the mean. This is evaluated by measuring the difference between the best point found far, subtracting from that the optimal value for the problem, and then taking the log of that difference. The results are consistent with those seen Fig. 4 and the standard errors show that ALEBO's improvement in average performance over the other methods is statistically significant. We now discuss some specific aspects of these experimental results.
Branin D=100 The additive kernel methods and SMAC all performed similarly on this problem, and, starting from around iteration 20, ALEBO performed the best. The distribution of final itera- tion values shows that in one iteration the ALEBO embedding did not contain an optimum and so achieved final value near 10. However, across all 50 runs nearly all achieved value very close to the optimum, leading to the best average performance.
The poor performance of HeSBO on this problem (particularly in Fig. without the log, where it is outperformed by all methods other than Sobol) can be attributed entirely to the embedding not containing an optimum. Recall that for this problem there are exactly three possible HeSBO embeddings, which are shown in Fig. 7 As explained in Appendix A the first embedding contains the optimum of 0.398, while the best value in the other embeddings are 0.925 and 17.18. Thus, the BO were able to find the true optimum within each embedding with the budget of 50 function evaluations given in this experiment, the expected best value found by HeSBO would be:
1- - Popt
Popt
0.398P opt + 0.925
+ 17.18
2
2
githabb.ccm/mbinniii///eeess
athub..ca//rraoonlly/aagooottt with option acq="add,ucb"
@ithub..com/autmm////AcC SMAC4AC mode
@ithub.ccom/CWAA////yvooo
gi g/thb..ccm////rssherr////
18

---

Under review as a conference paper at ICLR 2020
Branin, d=2, D=100
ALEBO
REMBO
Log regret
HeSBO, de=d
-2
HcSBO, de=2d
REMBO-
REMBO-;ku
FRO
Add-CP-UCB
10
20
30
40
50
SMAC
Gramacy, d-2, D
100
CMA-ES
Sobol
CoordinateeIneeBO
Log regret
RandomLineBO
DescentL.neBO
-4
50
Hartmann6, d-6, D- 1000
Log regret
-1
25
50
75
100
125
150
175
200
Hartmann6, d-6, D-100
Log regret
-2
-4
0
25
50
75
100
125
150
175
200
Function evaluations
Log regret for benchmark experiments of Fig. plus Hartmann6 D=100. Each trace is the mean over repeated runs with errors bars showing two standard errors of the mean. On the first three problems ALEBO performs significantly better than the other methods, and on Hartmann6 D=100 it is tied with REMBO-r/ks the best methods.
Figure 12:
This the best average performance one can hope to achieve using the HeSBO embedding on this problem. Using (3) can compute Popt for de 4 0.75, and it follows that the HeSBO expected best value is 2.56. This is nearly exactly the average best-value shown in Fig. The poor performance of HeSBO is thus related to BO, but comes entirely from the 12.5% chance of generating an embedding whose optimal value is 17.18. The presence of these embeddings can be clearly seen in the distribution final best values in Fig.
Hartmann6 D=1000 As noted in the main text, the additive kernel methods and REMBO-yke could not scale up to the 1000 dimensional problem. A nice property of linear embedding ap- proaches is that the running time not significantly impacted by the ambient dimensionality. Table
19

---

Under review as a conference paper at ICLR 2020
Table 1: Average running time per iteration in seconds the Hartmann6 problem, D=100 and D=1000.
D=100
D=1000
ALEBO
29.5
32.6
REMBO
1.3
1.4
HeSBO, d==d
1.6
HeSBO, d.=2d
1.0
1.4
REMBO-AKy
2.1
1.1
REMBO-Y/K
7.2
EBO
27.3
Add-GP-UCB
695.2
SMAC
9.5
404.5
CMA-ES
0.0
0.0
Sobol
0.0
0.0
1 gives the average running time per iteration for the various benchmark methods. Inferring the additional parameters in the Mahalanobis kernel and the added linear constraints make ALEBO slower than other linear embedding methods, but it has similar running time as EBO and is an order of magnitude faster than Add-GP-UCB. and at D=1000 is even order of magnitude faster than SMAC. The average 30s per iteration is short relative to the function evaluation time of typical resource-intensive BO applications.
Hartmannó D=100 REMBO performed worse than Sobol this problem, despite there being a true linear subspace that satisfies the REMBO assumptions. The source of the poor performance the poor representation of the function the embedding illustrated in Fig. [ The remaining methods all performed better than quasirandom. CMA-ES was competitive with all of the methods except SMAC, REMBO-yke, and ALEBO, which is somewhat surprising since it is not designed to have the same degree of sample efficiency as BO methods. HeSBO and Add-GP-UCB both did very well early on, but then got stuck and did not progress significantly after about iteration 50.
This problem was used to test three additional methods beyond those in Fig. 4 CoordinateLineBOO RandomLineBO and DescentLineBO (Kirschner et al. 2019). These are recent methods developed for high-ding dimenssonn safe BO, in which one must optimize subject to safety constraints that certain bounds on the functions must not be violated. The performance of these methods can be seen in the bottom panel of Fig. 12] all three LineBO variants perform much worse than Sobol, and show almost no reduction of log regret. This finding consistent with the results Kirschner et al.) (2019), who used the Hartmannó D=20 problem a benchmark problem. At D=20, they found that CoordinateLinet required about 400 itcrations to outperform random search, and even after 1200 iterations RandomLineBl and Descentl LineBO did not perform better than random search. These methods are designed specifically for safe BO, which is a significantly harder problem than usual BO that has much worse scaling with dimensionality. The primary challenge for high-dimensional safe BO lies in optimizing the acquisition function, which is difficult even for relatively small numbers of parameters where there is no difficulty in optimizing the traditional BO acquisition function. The LineBO methods develop new techniques for acquisition function optimization, but do not consider difficulties with GP modeling in high dimensions, which is the main focus of HDBO work. LineBO methods perform very well on safe BO problems relative to other methods, but ultimately non-safe HDBO not the problem that they were developed for, and so it not surprising to see that they were not successful on this task.
A.6.3 SENSITIVITY OF ALEBO TO EMBEDDING AND AMBIENT DIMENSIONS
We study sensitivity of ALEBO optimization performance the embedding dimension de and the ambient dimension D using the Branin function. To test dependence on de, for = 100 we ran 50 optimization runs for each of d, E (2, 4, 6, 7, To test dependence D, for de = 4 50 optimization runs for each of D E (50, 100, 200, 500, 1000}. Note that the d, = and D 100 case in each of these is exactly the optimization problem of Fig.
20

---

Under review as a conference paper at ICLR 2020
Branin, 100
Branin, de
de
d
D
Bost value found
D 200
d
D = 500
4
d,
D 1000
2.
0
0
10
20
30
40
50
10
20
30
40
50
Function evaluations
Function evaluations
Figure 13: ALEBO performance on the Branin problem, (Left) as function of embedding dimen- sion de and (Right) as function of ambient dimension D. Performance shown is the average of 50 repeated runs. Optimization performance is poor with de = 2, but shows little sensitivity to de for values greater than 2. Optimization performance shows little sensitivity with D, all the way up to
D = 1000.
Branin, D = 100
Branin, dg =
Best value found
2.5
2.0
1.5
1.0
0.5
2
6
50
200
500
1000
Embodding dimension
Ambient dimension D
Figure 14: Final best value for the Branin problem optimizations Fig. showing two standard errors. With the exception of de 2, optimization performance good across a wide range of values of de and D.
13
as mean with error bars
The results the optimizations are shown in Figs, 13 and 14 For d, = d, optimization performance was poor. From Fig. we know this is because there is low probability of the embedding contain- ing an optimizer. Increasing de increases that probability, but also increases the dimensionality of the embedding and thus reduces the sample efficiency of the BO in the embedding. This trade-off can be seen clearly in the figure: with de = there is rapid improvement that then flattens out because of the lack of good solutions in the embedding, whereas for d, 8 the initial iterations worse but then ultimately is able to find much better solutions. Even at de 8 the average best final value was better than that of any of the comparison methods in Fig.
The ambient dimension D will not directly impact the GP modeling in ALEBO, which depends only de, however will impact the probability the embedding contains an optimum shown in Fig. II Consistent with the strong ALEBO performance for the Hartmann6 D=1000 problem, we see here that even increasing D 1000 produces only small degradation in optimization perfor- mance. Even at D 1000, ALEBO had better performance than the other benchmark methods had on D 100.
A.7 LOCOMOTION BENCHMARK PROBLEM
The task for the final set of experiments was to learn a gait policy for a simulated robot. As a controller, the Central Pattern Generator (CPG) from Crespi & Tjspeert (200). The goal in
21

---

Under review as a conference paper at ICLR 2020
this task is for the robot to walk to target location in given amount of time, while reducing joint velocities, and average deviation from a desired height
f(p) = C - [final 2gooal
Σ
(will @l@l - W2 Rtyobot. Rearges 1)
(4)
where C= 10, w1 = 0.005, and W2 = 0.01 are constants. Dinal is the location of the robot on
plane at the end of the episode, Zgoal is the target location, q. the joint velocities time during the trajectory, /rooba.. is the height of the robot at time I, and hurget is a target height. T = 3000 is the total length of the trajectory, leading 30s of experiment. Cost is evaluated at the end of the trajectory.
22


Reviews:
[{"review_id": "Syli-Rq2Fr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors investigate pitfalls common to random embedding-based approaches to high-dimensional Bayesian optimization (HDBO). Each of several practical shortcomings is separately analyzed and, subsequently, addressed in straightforward fashion:\n\n  a. Large-scale distortions caused by clipping are handled by generalizing box constraints\n     (in the embedded space) to the polytope corresponding to the set of points that project\n     to the interior of the original search space.\n\n  b. Local distortions caused by defining squared Euclidean distances in embedded spaces\n     are handled by substitution for Mahalanobis distances.\n\n  c. Embedded spaces potentially failing to contain optima are handled by constructing an\n     estimator for the probability of this happening, which is then be used to pick better\n     embeddings.\n\n\nFeedback:\n    To the extent that I enjoyed reading this piece, I am not sure that it warrants publication at this time. Specifically, the degree of novelty on offer seems minimal and the empirical results are underwhelming.\n\n  1) Constraints on embedded candidate $\\mathbf{y}$ are naively defined in terms of a polytope, but this formulation has previously been deemed impractical. If nothing else, it would be good to clarify this matter: why did preceding works chose not to explore this direction and/or how did you make it work here?\n\n  2) Regarding use of Mahalanobis distances, evidence here (as provided in A.2) seems thin. Firstly, predictive MSE (Figure 6) seems like an odd choice of metric; log marginal probabilities would seemingly be more natural for GPs. Reporting of MSE is particularly suspect when results shown in Figure 7 indicate that the Mahalanobis distance based GPs are (markedly) overconfident. This issue is allegedly improved by marginalizing Mahalanobis parameters $\\Gamma$; however, the appropriate baseline here would be ARD with marginalized lengthscales (which, to my knowledge, is not shown).\n\n  3) Regarding ALEBO itself, Algorithm 1 states that acquisition functions were expressed in terms of an approximate posterior formed via moment matching against the Gaussian mixture formed by $m$ different samples of hyperparameters $\\Gamma$?  One usually pushes this uncertainty through the acquisition function as, e.g., $\\mathbb{E}_{\\Gamma}[\\alpha(\\mathbf{x}; \\Gamma)]$. What motivated this design choice?\n\n\nQuestions:\n - Does $\\mathcal{B}$ need to be sampled or can it chosen to maximize $P_{opt}$?\n - Marginalization of hyperparameters\n    - Did you jointly marginalize over all hyperparamerters or just Mahalanobis parameters $\\Gamma$?\n    - Why was a Laplace approximation used lieu of, e.g., slice sampling?\n\nNitpicks, Spelling, & Grammar:\n  - Various figures: 'NewMethod' -> 'ALEBO'\n  - Please report log immediate regret along with error bars\n  - To the extent that testing on e.g. \"high-dimensional\" variants of Branin and Hartmann-6 is standard, it isn't particularly convincing.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg7FudRYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a well-written paper and I enjoyed reading it. In summary the paper tries to address the following shortcomings of REMBO:\n\n(1)\tREMBO uses a random embedding to project a point in high dimensional space to a lower dimensional embedding space basing on the relation f(x) = f(Ay) with high probability, where x in D dimensions and y in d dimensions and d<<D. The problem of REMBO is that the relation f(x) = f(Ay) is only guaranteed with high probability and so, the embedding space may not contain an optimum. Second, When a point y  where Ay is outside the search space X, REMBO uses a projection to map Ay to its nearest point in X. This projection is not enough good. These observation are identified in paper of Binois et al (2018)as well.\n(2)HESBO is an extension of REMBO that avoid above restrictions by proposing a new random projection. However, as the paper mentioned, HeSBO have a limitation is that the probability that the embedding will contain an optimum can be quite low! \n(3)Besides, the paper also identify a new observation that linear projections do not preserve product kernels. \n\nThen, the paper proposes a new solution of BO to overcome these restrictions by using a Mahalanobis kernel to avoid (3). This kernel is a replace of ARD Euclidean distance to a Mahalanobis distance. To avoid (1), the paper use equation 1 (please find in the paper). To avoid (2), they use the projection P_opt. In all , I think the theoretical contribution is good enough.\n\nHaving said that, I am a bit disappointed that this paper does not talk about LineBO (ICML 2019).  LineBO is a good solution for high dimensions without any assumption on structure like low effective dimensionality. It uses even one-dimensional subspaces to solve high dimensional problem with the strong theoretical guarantee. It do not need to learn subspace, and so it avoids disvantages (1), (2) and (3) that cause due to the fact that the embedding may not contain an optimum as mentioned above. Thus, LineBO is a stronger contender to the proposed algorithm. I will lift my rating if the author provide their response to this point.\n\nAdditionally, the author should compare their method to the algorithm of Binois et al (2018) that solved very well disadvantages of REMBO by setting bounds to avoid (1). Moreover, because the problem of the paper is high-dimensional Bayesian optimization under the assumption of low effective dimensionality, they should compare to other strong algorithms under the same assumption such as SI-BO algorithm( NIPS 2013) that used active learning to learn the low-dimensional subspace instead of using random embedding like REMBO.\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlTr1daYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper criticizes existing High Dimensional BO (HDBO) via linear embedding literature for the following reasons:\n\n- Points in the embedded space projected mostly to the facet of the bounding box in the original space.\n- The projection induces a distorted space which is not fit to be modeled by a GP.\n- Linear projections do not preserve product kernels.\n- Linear embeddings have low probability of containing an optimum.\n\nThe paper then proposes ALEBO which supposedly improves these aspects over other linear embedding BO techniques.\n\nI have the following concerns regarding the authors' criticisms above:\n\n1. What is wrong with the points being projected mostly to the facet of the original bounding box?\nIf I understand correctly, Theorem 3 of the REMBO paper proved that there exists y* \\in R^{d_e} such that f(Ay*) = f(x*)\n(i.e., the projected space contains the optimum) with high probability so to me, it does not really matter if the projection does not include the interior of the bounding box. Fig. 1 seems to make a point that most projections seem to indeed land on the facet of the bounding box (to be thorough, how many points did the authors sample to make this plot) but given what I said above, I do not think there is much of a point in Fig. 1 here. \n\n2. The authors claimed that it is not appropriate to model the distorted space with GP, but ended up using GP \nfor ALEBO anyway (although with a different kernel). I understand that the authors did not project Ay back to B\nlike REMBO did, but the authors also gave me no reason to believe that this will improve things either. In fact, I think \nthe authors should show the space induced by ALEBO embedding as a comparison. I suspect that with the imposed \nconstraint -1 <= (B^T)y <= 1 the space will have discontinuous regions and is also not fit to be modeled \nwith any GP. \n\n3. The authors stated that \"A product kernel in the true subspace will not produce a product kernel in the embedding; \nwe will see this more explicitly in Sec. 5.1\" but I did not see it explicitly in Sec. 5.1. At the very\nleast, I do not see how REMBO fails to do the same thing. Also, the authors claimed that \"Inside the embedding, \nmoving along a single dimension will move across all dimensions of the true subspace, at rates depending \non the angles between the embedding and the true subspace\". This seems like a very qualitative claim.\nCan the authors formally define what this statement means, and prove it or at least provide some backup citations?  \n\nOther comments:\n\n4. Why do the authors use conjugate transpose (if B^T means what i think it means) instead of normal transpose \nwhen B is drawn from R^{d_e \\times d}? Shouldn't they be the same?\n\n5. Please explain the choice of \\Epsilon(B) = {x: B^T B x = x} \n\n6. The experiments provided are very limited. There is only one set of experiments showing performance of\nALEBO against other methods and it was done on a very small extrinsic dimension too (D = 100). I would like to see how \nALEBO scales with truly large dimension (REMBO also claimed that it could scale up to much higher extrinsic dimension). What about other important properties like does it guarantee that an optimum lies in the constraint space? What about rotational invariance? There are so many elements missing from the analysis.\n\nOverall conclusion:\n\nThis paper is largely empirical and lacks technical depth. It is not at all convincing that the problem it\naddresses is real, much less important. It also does not offer strong empirical evidence (too few experiments). \nGiven these reasons, I do not think the paper is not ready to be published as it is. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores the practice of using lower-dimensional embeddings to perform Bayesian optimization on high dimensional problems.  The authors identify several issues with performing such an optimization on a lower-dimensional projection and propose solutions leading to better empirical performance of the optimization routine.  Overall the reviewers found the work well written and enjoyable.  However, the reviewers were concerned primarily about the connection to existing literature (R2) and the empirical analysis (R1, R3).  The authors claim that their method outperforms state-of-the-art on a range of problems but the reviewers did not feel there was sufficient empirical evidence to back up this claim. 
 Unfortunately, as such the paper is not quite ready for publication.  The authors claim to have significantly expanded the experiments in the response period, however, which will likely make it much stronger for a future submission.

Decision: Reject