Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces
Authors: Aryan Deshwal
Jana Doppa
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian optimization
Gaussian process
Combinatorial spaces

Abstract: We consider the problem of optimizing combinatorial spaces (e.g., sequences, trees, and graphs) using expensive black-box function evaluations. For example, optimizing molecules for drug design using physical lab experiments. Bayesian optimization (BO) is an efficient framework for solving such problems by intelligently selecting the inputs with high utility guided by a learned surrogate model. A recent BO approach for combinatorial spaces is through a reduction to BO over continuous spaces by learning a latent representation of structures using deep generative models (DGMs). The selected input from the continuous space is decoded into a discrete structure for performing function evaluation. However, the surrogate model over the latent space only uses the information learned by the DGM, which may not have the desired inductive bias to approximate the target black-box function. To overcome this drawback, this paper proposes a principled approach referred as LADDER. The key idea is to define a novel structure-coupled kernel that explicitly integrates the structural information from decoded structures with the learned latent space representation for better surrogate modeling. Our experiments on real-world benchmarks show that LADDER significantly improves over the BO over latent space method, and performs better or similar to state-of-the-art methods.

Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces
Aryan Deshwal School of EECS
Janardhan Rao Doppa
School of EECS
Washington State University aryan.
Washington State University jana. doppa@xsu. edu
aryan.deshwal dwwhwallwwww.... @ws..wwwsue..om edu
Abstract
We consider the problem of optimizing combinatorial spaces (e.g., sequences, trees, and graphs) using expensive black-box function evaluations. For example, optimizing molecules for drug design using physical lab experiments. Bayesian op- timization (BO) is an efficient framework for solving such problems by intelligently selecting the inputs with high utility guided by learned surrogate model. A recent BO approach for combinatorial spaces is through a reduction to BO over continu- spaces by learning latent representation of structures using deep generative models (DGMs). The selected input from the continuous space is decoded into a discrete structure for performing function evaluation. However, the surrogate model over the latent space only uses the information learned by the DGM, which may not have the desired inductive bias to approximate the target black-box function. To overcome this drawback, this paper proposes principled approach referred as LADDER. The key idea define a novel structure-coupp coupled kernel that explicitly integrates the structural information from decoded structures with the learned latent space representation for better surrogate modeling. Our experiments on real-worle benchmarks show that LADDER significantly improves over the BO over latent space method, and performs better or similar to state-of-the-ar art methods.
Introduction
A huge range of science and engineering applications involve optimizing combinatorial spaces (c.g..
sequences, trees, graphs) using expensive black-box function evaluations [8 70 17). For example, in drug design application, each candidate structure is molecule and evaluation involves performing an
expensive physical lab experiment. Bayesian optimization (BO) [59 20 is effective framework for
optimizing expensive black-box functions and has shown great success in practice [63 74 21 6 5)
The key idea to learn a cheap-to-evaluat surrogate statistical model, e.g., Gaussian process (GP), from past function evaluations and employ it to select inputs with high-utility for evaluation. BO for combinatorial spaces relatively less-studied problem with many challenges in the small-data setting (number of function evaluations is small).
recent approach solve some of these challenges through a reduction to BO over continuous spaces, which we refer as BO over latent space [26] 68] This method relies on two ideas. First, we learn latent space representation from a database of unsupervised structures (i.e.. function evaluations are not available) using a encoder-decode style deep generative model (DGM) B3 Second, we build a surrogate model over this latent space to perform BO. Each selected input from the latent space is decoded into a structured object for performing function evaluation. BO over latent
space has shown good success when the number of function evaluations large [26 68 19 34)
However, we conjecture that this approach may not be effective in the small-data settings for the following reasons. 1) The surrogate model over the latent space only uses the information learned by the DGM, which may not have the desired inductive bias to approximate the target black-box
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

function. 2) The learned surrogate model may not generalize well beyond the training instances from the latent space, Indeed, our experiments on real-world problems demonstrate the ineffectivenesss of this Naïve surrogate model over the latent space.
In this paper, we propose novel approach referred LADDER to overcome the above drawbacks for the small-data setting. We name it LADDER because it acts as a ladder in connecting the rich structural information of structures in the combinatorial space with their corresponding latent space representations. Intuitively, it improve surrogate modeling by combining the best of both representations. We provide principled Gaussian process based method to integrate the latent space representation with the structural information from decoded structures using novel structure-coupled kernel. The key insight is to extend a kernel over the latent space (with its peper--arameters estimated on the evaluated points) to non-evallle non-evaluated points in the space by utilizing the features of structured kernels deñieed over combinatorial spaces (e.g., string kernels and graph kernels). LADDER has multiple advantages. First, we can leverage large body of research on kernels over structured data. Second, allows the use of deep generative models (DGMs) to learn latent space as a plug-and-play technology. This means advances in DGMs will directly improve the effectiveness of LADDER. Our experiments on real-world benchmarks show that LADDER performs better or similar to state-of- the-art methods, and significantly better than the Naive latent space BO approach in our problem setting. We also empirically demonstrate that superiority of LADDER's s performance is due to better surrogate model resulting from the proposed method to combine representations.
Contributions. The key contribution of this paper the development and evaluation of the LADDER approach to perform BO over combinatorial spaces in the small-data setting. Specific list includes:
Identifying the key reasons for the ineffectiveness of the Naïve latent space BO method in the small-data setting and providing empirical evidence on real-world problems.
Development a principled Gaussian process approach for improved surrogate modeling by combining the structural information from decoded structures with the learned latent space representation using a novel structure-coupled kernel.
Experiments on real-world benchmarks to show the efficacy of LADDER over prior methods in our problem setting. The code and data are available on the GitHub repository link ccm//aryaadesswaa//LDDDS
2 Problem Setup and Background
Let X' be a space of combinatorial structures (e.g., sequences, trees, and graphs). We assume the availability of a black-box objective function f X + IR defined over the combinatorial space X. Evaluating each candidate structure x X using function f (also called an experiment) is expensive in terms of the resources consumed and produces output = [x)). For example, in the drug design application, each x E is molecule, and f(xx) corresponds to running a physical lab experiment. Our overall goal is to find a structure x X' that approximately optimizes f by minimizing the number of experiments and observing their outcomes.
We are also provided with a database of unsupervised structures X₂ C X. Unsupervised means that we do not know the function evaluations (z) for structures in X,. This assumption is satisfied by many scientific applications including chemical design and material design. We assume the availability of latent space Z learned from unsupervised structures X., using a decoder style deep generative model, e.g., variational autoencoders (VAEs) for structured data such as junction tree VAE 33 and grammer VAE (37]. Formally, the encoder denoted by Y embeds a given combinatorial structure x E X' into a point in the latent space E 4== (xx) where d is the number of dimensions of the latent space Z and the decoder denoted by & converts a given point from latent space z' E Z into structured object x' E X = (xz'). Encoder Y and decoder & are typically realized by neural networks.
Bayesian optimization. To solve optimization problems using black-box evaluations of expensive objective functions, Bayesian optimization (BO) an efficient framework. BO algorithms select inputs with high utility guided by learned surrogate statistical model from past observations. The three key elements of BO are as follows: 1) Surrogate model of the black-box function f((x), e.g., Gaussian process; 2) Acquisition function to score the utility of evaluating candidate inputs using the surrogate model, e.g., expected improvement; and 3) Acquisition function optimizer to select the input with maximum utility. In each BO iteration, we select one input for function evaluation

---

and update the statistical model based on the new training example. BO has shown great success for continuous spaces, but BO over combinatorial spaces is relatively less-studied problem space.
Naïve latent space BO. This approach reduces the problem of BO over combinatorial space X' to BO over the latent space 2, which is continuous. We construct surrogate model Mz over the latent space Z using training points selected from Z for evaluation. Each selected input E Z is decoded into structured object using the decoder b. We perform function evaluation using the decoded structure (z) and the surrogate model Mz is updated using the new training example (z, (z)())) This reduction approach allows us to leverage prior research on BO for continuous spaces and has shown success when the the number of function evaluations is large (26 68 19 (3]. In this paper, we study the small data setting (number of function evaluations is small) by addressing the drawbacks of this Naive latent space BO approach in a principled manner.
3 LADDER: Latent Space BO guided by Decoded Structures
In this section, we first discuss the challenges with the Naive latent space BO approach. Next, we describe our proposed LADDER approach with focus on the novel surrogate model by combining kernels over structured data and latent space representation, which is our key technical contribution.
3.1 Challenges with the Naïve latent space BO approach
As mentioned above, the Naïve latent space BO approach builds surrogate model over the latent space using kernlls for continuous spaces (e.g., Matern or Squared Exponential kernel) and performs acquisition function optimization in the latent space using optimizers for continuous spaces (e.g.. gradient-based methods) to select point E Z for evaluation. However, the expensive objective function f (x) is defined over the space of combinatorial structures X' and not the latent space Z. Therefore, we need to decode this point z using the decoder 4 to get the corresponding combinatorial structure x=)(2) for function evaluation fx). All the existing work on BO over latent space do not account for this decoding process. As consequence, we need to deal with two inter-related challenges, which are especially significant for small-data settings.
Challenge #1: The kernel over the latent space only uses the information learned by the deep generative model. It doesn't explicitly incorporate information about the decoded structure. This means the corresponding Gaussian process surrogate model may not have the desired inductive bias to approximate the black-box objective function. Therefore, are not able to leverage this potentially useful inductive bias and rich structural information available in decoded structures.
Challenge #2: The surrogate statistical model itself might not generalize well beyond the training examples from the latent space (set of points in the latent space and their corresponding function evaluations). This is especially true in the small-data setting for latent spaces learned using DGMs in real-world scientific applications, where the number of dimensions of latent space can be large when compared to the standard BO setup.
Indeed, we provide empirical evidence to demonstrate these challenges and our key hypothesis in Figure 2 We show that by incorporating the rich structural information from the decoded output, we can address both these challenges to improve the overall BO performance.
3.2 Overview of LADDER algorithm and key advantages
LADDER is an instantiation of the latent space BO framework that employs a novel surrogate statistical model to address the two challenges with the Naive method. The surrogate model is a Gaussian process that combines the complementary strengths of the latent space representation with the rich structural information from decoded outputs using structured kernels (c.g., string kernels and graph kernels). The key idea is to define structure structure-coupled coupled kernel that extends the continuous kernel on the evaluated points in the latent space to unknown points using the rich information from structured kernels. We employ expected improvement (EI) as the acquisition function. For optimizing the acquisition function to select high utility inputs from the latent space, we employ evolutionary search due to its recent successes (39 including policy search in high-dimensional spaces (55).
Figure shows a high-level illustration of LADDER and Algorithm provides the complete pseudo- code. We use a small set of initial training data in the form of points in the latent space and their
3

---

Combinatorial space X
Black-box objective
Decoder +
Xnext ((Inext)
f f(xnext)
Structure-coupled kernel
}
next
Gaussian process Model
Acquisition function optimization nnext = arg max AF(M, 2)
Latent space Z
Figure 1: High-level conceptual illustration of our proposed LADDER approach, which acts
"ladder" in connecting the rich structural information of each structure in the combinatorial space with its corresponding latent space representation. Structure-coupled kernel the key element that enables this connection to build an effective Gaussian process based surrogate model.
corresponding function evaluations bootstrap the GP based surrogate model using the structure- coupled kernel. In each iteration we optimize the acquisition function to select a point Zę from the latent space Z for evaluation. The corresponding decoded structure x,=((z,) is evaluated to measure the outcome fxx)). The GP model with dructure-couple kernel is updated using the new 3-tuple training example (z,, Xt. [x:)). We repeat these sequence of steps until covergence or maximum query budget and then return the best uncovered combinatorial structure & E X as the output.
Advantages of LADDER. Some of the key advantages of our proposed approach listed below.
We are allowed employ any existing trained deep generative model for structured data in plug-ant aati--and-lay manner with LADDER. Therefore, any advances in the latent-space generative modeling technology will directly improve the overall BO performance.
LADDER is generic approach that is applicable to any combinatorial space of structures (e.g., sequences, trees, graphs, sets, and permutations). This method just requires an appropriate structured kernel over the given combinatorial space. Therefore, we can leverage large body of research on generic kernels over structured data (e.g., string kernels and graph kernels) and hand-designed kernels based on domain knowledge for specific applications. For example, in our experiments, we employ sub-sequence string kernel (generic) and fingerprint kernel (domain-spy -secific to concretely instantiate the LADDER approach for strings and molecules respectively to demonstrate its flexibility.
Combines the complementary strengths of latent space representations and structured kernels in a principled manner to create highly-effective surrogate statistical models.
3.3 Novel surrogate statistical model via structure-coupled kernel
We consider Gaussian process (GP) 52 as the surrogate model of the expensive black-box objective function f(x E X). GPs are known have excellent statistical properties including principled uncertainty quantification, which is critical for the effectiveness of BO algorithms. A GP model defines prior distribution on functions which is entirely characterized by a kernel defined over pair of inputs. Most of the existing work on latent space BO employs standard continuous space kernel represented by 1(2; E 2, 2j E 2), e-g., Radial Basis Function (RBF) Gaussian and Matern kernels, over points in the latent space to create the GP model. However, this surrogate model is

---

Algorithm Latent Space Bayesian Optimization guided by Decoded Structures (LADDER)
1: Input: Objective function f(x), Encoder (T) Decoder (Φ) style model for latent space 2, Kernel for latent space I(z; E 2,2j E 2), Kernel for combinatorial space k(x; E X, E X))
2: Initialize dataset Du by evaluating few random points: Do <- (Zo. Xu. f(x)) t +-0 slight abuse of notation here since Zo is the set of initial points from latent space and Xo is the set of corresponding decoded structures from X' with function evaluations s(Xo)
3: repeat
4: Learn Gaussian process model on the dataset Dj with the proposed kernel in Equation 4
5: Optimize acquisition function over the latent space to find the next point 2, for evaluation
6: Compute the decoded structure for point 2, using decoder +>
7: Evaluate the combinatorial structure X, to get [(x,)
8: Add new training triple: D D, J (z,, X,, fxx)) increment the iteration t +- t
9: until convergence or maximum iterations
10: Output: best uncovered structure & and the corresponding function value ʃ(x)
highly-ineffecttve for small data settings, especially when the number of dimensions of latent space large, which is the common case for deep generative models for scientific applications.
Structure-coupled kernel. We propose to utilize the rich structural information that available from the decoded combinatorial structure x corresponding to each point z from the latent space 2. The key idea behind our approach is to integrate the structure information from the decoded outputs with the learned representation of inputs from the latent space achieve better surrogate modeling performance. To include this structure information in a principled manner within a GP model, we leverage the Generalized Nystrom extension idea (57 69 to extrapolate the eigenfunctions of the kernel matrix over latent space (L = {Ly = (zz z, Zj E 2}) with basis functions from a kernel &(x, X, X, E X') defined over the decoded combinatorial structures.
Without loss of generality, let m be the number of evaluated inputs from the latent space, which are denoted as Z = [Z1, 22." , 7m)) For example, these are the points accumulated after m iterations of the latent space BO approach. Let the corresponding set of decoded structures be X (x1 ((1)). X2 = (20(((z)) (Z2),
Xm & (2m)) with their function evaluations {f(x)), fxx), f(xm)) }.
Given kernels : x z + and k x x x + R with L and K representing their corresponding kernel matrices, Generalized Nystrom extension generates an m-dimensional feature vector {(z) for
a point z in the latent space. The ith component of (z) is given as follows:
(z) = kg T 02
E (1,2, ,m}
(1)
where k, is an m-diimensional vector evaluated between x (decoded output of latent space input z) and other combinatorial structures from X:
[k: ( (z), (21)), ... (z) ((zm)) )) [k (x, (x,x1),
(x, xm)]
(2)
K is an m x m kernel matrix for combinatorial structures in the set X, i.e., Kij (()(z)), (zz))
k(x,, xj), and v; is the eigenvalue-scaled eigenvector of the kernel matrix L defined over the latent space inputs in the set Z, i.e. V [u1, U2 ... umm //!/2 where U and are eigenvectors and eigenvalues of L respectively.
The reader should note that the term l (2;( ( )) in means that the structured kernel is applied to the decoded structures X, = (2,) and Xj + (2z) of latent space inputs z₁ and zj respectively. This is a key term in the above expression because it integrates each input from latent space with its decoded structure in the new feature map Ez)). For any two inputs and z' in the latent space, the resulting structure-coupled kernel denoted z(z,z')) is defined as the dot product of their corresponding feature vectors {zz) and {(z'):
c(z, z [(2) T((z)
(3)
c(z, z') = KK"KK-LK-1
(4)
Intuitively, by this construction, we are extending the kernel over the latent space / on the evaluated points to non-evaluated points in the latent space by utilizing the rich structural features from kernel & defined over combinatorial spaces. For training points (candidate inputs from latent space
5

---

along with their function evaluations), the resulting kernel matrix will be L since Equation becomes KK LLK K L. For latent space points not the training set, the structured kemnll is acts like smooth extrapolating kernel. It can also be seen by interpreting the Equation 4 through the definition of a kernel in terms of the empirical kernel map with respect to the decoded structured outputs) endowed with a dot product induced by the positive Dositiveedefiniie matrix KK
i.e.
clz, z') - <k2, kx IL- = <k2, K "L'KKK 'zy>>
(5)
Importantly, the above general construction of structure-coupled kernel allows us leverage extensive research on kernel methods for combinatorial objects. For example, string kernels [38 count the number of common sub-strings in string inputs, fingerprint kernels [51] capture gegghborhoo-aggregaann properties of molecules, and features such as number of random walks and shortest paths are utilized by graph kernels 7
data, which try to exploit structural features of
Experiments and Results
In this section, we empirically evaluate the effectiveness of the proposed LADDER approach on real-world benchmarks, and perform comparison with baseline methods.
4.1 Real-world benchmarks
We employ two widely used real-world benchmarks for combinatorial Bayesian optimization.
Arithmetic expressions optimization. In this benchmark, the goal is to search in the space of uni-variate arithmetic expressions (generated from given grammar) to find the best expression that fits a given target expression (37] As described in [37], the latent space model is trained on 100K randomly generated expressions from the following grammar:
S + S .+* T 1 S
>* T S 2/> I
T + ' s ")² 'sin(' ")² 'exp(' S '))
T 'v> >1' 22 '3'
We follow the same setup as discussed in the state-of-the-art paper for this benchmark (68] We consider the log mean-squared error between expression and the target expression x" =/=1/3+ sin(v²) (computed over 1000 evenly-spaced values of v in the interval 1-0 10)) as the objective function which should be minimized.
Chemical design optimization. This benchmark considers finding molecules with best drug-like properties (37] and is similar in prototype for many scientific applications. Specifically, the goal is to maximize the water-octanol partition coefficient (logP) over the space of molecules. The latent space model is trained the Zine molecule dataset of 250K molecules. For consistency purposes, all our results are shown as minimization obtained by taking negation of the logP objective.
4.2 Experimental setup
Configuration of algorithms. The BO part of the source code is written using the popular GpyTord 22 and BoTorch (2] libraries for all BO methods including LADDER. We employ ARD (automatic relevance determination) Matern kernel for the latent space inputs in all our experiments. Matern kernel is commonly advocated as a better choice than RBF kernel for BO algorithms since the sample functions from the latter are impractically smooth (63) Hyperparameters of Gaussian process models are fitted by marginal likelihood maximization after every BO iteration. We employed Junction tree VAE 33 and Grammar VAE (37) the latent-space model for chemical design and arithmetic expression optimization benchmarks respectively. Both pretrained encoder-decoder models are taken from the source code provided by the authors' of [68] We employed expected improvement (EI) as the acquisition function for all the BO methods. All experiments are performed on a machine with the following configuration: Intel(R) Core(TM) 19- 7960X CPU @ 2.80GHz with 128 GB RAM.
We refer to empirical kemnel map as commonly defined in (56) (Definition 3)
PPositive definiteness of K "LK" -1 can be easily seen consequence of the following three facts: i) K. L. being kernel matrices, are positive definite; ii) inverse of psd matrix psd: and iii) A N M psd and N are two psd matrices.
https:/ thub. httppp//ggttttao.oo////aggggggg/ http:////mmiiigggggo////goeeeeee

---

LADDER instantiations. In addition to the ancoder-decoder style latent space model, which is same as the Naive latent space BO (LSBO), LADDER also requires an appropriate structured kernel for the given combinatorial space. To demonstrate the generality of our proposed approach, we instantiate LADDER with two different kernels for our two optimization benchmarks. We employed sub-sequence string kernel for the arithmetic expressions task and fingerprints kernel for the chemical design task. We briefly describe both kernels below.
Sub-sequence string kernel. This kernel captures the similarity between two strings by counting the number of matching substrings. where the substrings can be non- contiguous [38, [0]. Following the notation in [42]. given an alphabet II, the kernel between two strings 81 and 82 is given as: k(81, 82) Event" ((8)))(82) where p(s)
(Xg " (u : (i())) for any string s where Xg and Am are gap decay and match decay hyper- pypaa--prameters. Since arithmetic expressions are naturally represented as strings, we use this kernel for the arithmetic expressions task.
Fingerprints kernel. There is a large body of work in the chemical informatics literature for designing structural features for molecular inputs. These hand-engineered features by domain experts are commonly known as molecular fingerprints [4]] We employ Morgan fingerprints [53] which are high-dimensional binary features to capture different substruc- tures in a molecule while being invariant to atom relabeling. Since combinatorial structures in the chemical design task are molecules, given two molecules mi and m2, we consider the dot product of their Morgan fingerprints as the structured kernel for the chemical design task. Hence, we refer to this kernel the Fingerprints kernel. We employed 2048- bit fingerprints with a bond radius of 3 43
In all our results and figures, the corresponding structured kernel for LADDER is denoted in the parenthesis, e.g., LADDER (String). We employed the evolutionary search algorithm CMA-ES [28) as the acquisition function optimizer for LADDER. The parameters of CMA-ES" were fixed with sigma- = 0.2 and a population size of 50. The performance of CMA-ES was found to be highly robust to different choice of these parameters. We ran CMA-ES from 10 different starting inputs for 10 iterations each and picked the best optimizer found. As discussed later, we consider one instance of Naïve LSBO with the same configuration of CMA-ES optimizer for fair comparison and to test our key hypothesis that surrogate modeling within LADDER is better. We use 10 random points (uniformly picked from the dataset) initialize the GP models.
Evaluation metric. We evaluate all methods on the best objective (log MSE for the arithmetic expressions task and logp for the chemical design task) value uncovered as function of the number of experiments (expensive function evaluations). The method that finds high-performing structures with less number of function evaluations is considered better.
We ran each method on all benchmarks for 10 different runs with the same initialization (small number of randomly selected structures and function evaluations). We plot the mean and two times the standard error for all our experimental results.
4.3 Results and discussion
Comparison of surrogate models. Recall that the key hypothesis of this paper is that surrogate model employed by the Naïve LSBO approach (GP model with Matern kernel in our case) is ineffective and GP model with our proposed structure-coupled kernel for small-data settings. To test this hypothesis, we compare the quality of the model fit for these two GP models (Naïve LSBO and LADDER) by evaluating the mean absolute error (MAE) of their predictions on a testing set. To perform this experiment, we generate 50 (uniformly) random training sets of different sizes and evaluate the models on 20 random testing sets. The averaged MAE results over these 1000 training and testing set pairs are shown in Figure? 2 We make following observations. 1) The standard GP model on latent space denoted by Naive LSBO shows some improvement in MAE for the arithmetic expressions task while the improvement is minimal for the chemical design task. 2) Our proposed surrogate model, i.e., GP with structure-couple kernel, denoted by LADDER has significantly lower MAE than Naïve LSBO on both the benchmarks and continuously decreases function
'napss//gituub.oo//MMAABB ES/pyema
7

---

0.75
LADDER (String)
LADDER (Fingerprint)
1.65
LSBO
0.70
1.60
Mean absolura
0.65
1.50
0.60
1.45
1.40
1.35
20
40 60
8D
100
20
40
600
80
100
Training
Training
(a) Arithmetic expression optimization
(b) Chemical design optimization
Figure 2: Mean absolute error results comparing the quality of model fit for varying sizes of training sets with two models: GP model with Matern kernel (Naive LSBO) and GP model with the proposed structure-coupled kernel (LADDER). Lower MAE values mean better surrogate model.
of the training set size. These strong results corroborate our key hypothesis and demonstrate the effectiveness of proposed surrogate model with the structure-coupled kernel.
Naïve latent space BO vs. LADDER. A natural question based on the above results is whether improved surrogate modeling results in better overall BO performance. To answer this question, we compare the BO performance (best uncovered or incumbent objective value vs. number of function evaluations iterations) of Naïve ISBOO and LADDER. We consider two choices for acquisition function optimizer within the Naïve LSBO approach: zeroth order CMA based optimizer (same LADDER) and second-order gradient based optimizer (L-BFGS). We make the following observations from the results shown in Figure 3 1) LADDER consistently uncovers significantly better structures than those from the Naive LSBO approach both benchmarks. This direct consequence of the better surrogate model of LADDER since the acquisition function optimizer is kept the same for both methods, i.e., CMA. 2) L-BFGS based acquisition function optimizer slightly improves the BO performance of Naïve LSBO but still cannot match the performance of LADDER.
LADDER (String)
-1.00
LADDER (Fingerprints)
(CMA)
Naive (CMA)
Naive LSBO (L-BGFS)
-2.00
Naave LSBO (L-8GF5)
-2.5
-2.00
22.5
2-
3..0
1-
33.25
-3.50
20
40
60
80
100
60
80
100
Number of Iterations
Number of ineratioon
(a) Arithmetic expression dataset
(b) Chemical design dataset
Figure 3: Results comparing the BO performance of LADDER and Naïve latent space BO.
LADDER vs. State-of-the-art. To further analyze LADDER, we compare its performance with set of state-of-the-ard methods. We include weighted retraining approach which was recently proposed [68] to update the latent space model as the BO algorithm progresses (Naīve LSBO w/ retraining). We also consider design by adaptive sampling (DbAS) [ the cross-entropy method with probability of improvement (CEM-PI) [54], the feedback VAE (FB- VAE) [77], and reward-weighted
weighted regression (RWR) 449. We employ the publicly available implementation of these baseline methods. We make the following observations from the results shown in Figure 1) LADDER performs significantly better on arithmetic expressions task and similar to the best method on the chemical design task. We verify the similar performance of LADDER on the chemical design task by performing two-sided paired Wilcoxon test 1 significance. The performance LADDER and Naïve LSBOO w/ retraining is statistically similar the chemical design task (p-value = 0.0489). 2) Retraining

---

JADDIR (SHIT))
-1.00
LADDER (Fingemdees)
1.75
Nalve roclaiing
Dorl
2.00
4-
CEN-
CEN-F1
2.25
-250
-2.7
-3.00
-3.2
-350
20
40
60
80
100
20
40
60
80
100
Number of iterations
Number of iteeraioon
(a) Arithmetic expression dataset
(b) Chemical design dataset
Figure 4: Results comparing the BO performance of LADDER and different state-of- of-he--rr-r methods.
the latent space model helps in improving the performance of Naive LSBO on both tasks. 3) DbAS and CEM-PI perform similar to Naïve LSBO w/ retraining since they are special case of retraining method as described in [68]. The discrepancy in LADDER's performance on the chemical design benchmark can be attributed to the low-flexibility of fingerprint kernel which doesn't 't include any
hyper-parameters (as opposed to string kernel) to tune it for specific dataset.
Related Work
In this section, we discuss the most closely related work for the problem setting studied in this paper.
Deep generative models for structured data. Scientific domains including chemistry and molecular biology involve highly structured data [58]. To address the challenges of structured data, there is growing body of work on deep generative models (DGMs). Some notable examples include grammar VAE 377, junction tree VAE (33) and syntax-directed VAE [II] This line of work is complementary to our work as advances in DGMs will automatically improve the BO performance of LADDER.
Kernels over structured data. There is large body of research generie kernels over structured data including strings (38 10, trees [1], graphs (7]. sets [9], and permutations [32]. LADDER allows us leverage this prior research to perform sample-efficient BO over combinatorial spaces.
BO over latent space. The use of DGMs to learn latent space and to perform BO in this continuous space was first started by followup work motivated by applications from multiple domains 40 19
et al., for chemical design 266 This led to a lot of
34 33 A recent work by Tripp et al., (68] noted that this decoupled approach of training DGM and BO process can make the overall optimization problem hard; and proposed an approach referred as weighted retraining. The key idea is to periodically retrain the DGM by giving more weight to inputs with high function values. Our LADDER approach and weighted retraining have complementary strengths. For small-data settings, LADDER is much more effective than weighted retraining as demonstrated by experiments.
BO over combinatorial space. We can categorize these methods based on the choice of surrogate model and search strategies for acquisition function optimization. Linear models [ Gaussian processes with kernels over discrete structures [46]
15]
24
36), and random forest 30 are considered
for surrogate modeling. Search strategies include mathematical optimization 13 15), heuristic
search methods [30, 46 14), and combination thereof [6
66 44 (31 provided BO approach for
tree structured spaces. LADDER is complementary to this line of work. First, it allows to combine the complementary strengths of two picces of knowledge, namely, generic/domain-speeeee over structured data and data-driven representations learned using DGMs, for improved surrogate modeling. Second, it is well known in the AI search literature that effective search strategies varies from one problem to another. For example, recent work on BO over string spaces 42], showed that we need to specialize genetic algorithms for different problems. In contrast, we can use generic search strategies for continuous spaces with LADDER.
kernels
Reinforcement learning (RL) formulations are also studied to solve this optimization problem 71 73 47
62 50
60) RL is very effective for sinulated environments where collection of large
amount of data to improve the policy is possible. Unfortunately, this requirement impractical when need to perform expensive experiments collect new training examples.

---

6 Discussion and Limitations
The main contribution of this paper is to improve the performance of latent-space BO methods. However, alternative approach to solve the problem discussed in this paper is to perform BO directly on the structured space. We evaluate one instance of this approach (BO with Fingerprints kernel) on the chemical design task and results are shown in the below table. We make two observations: 1) LADDER has better accuracy for a large number of initial BO iterations compared to BO w/ Fingerprints approach; and 2) BO with Fingerprints kernel alone reached slightly better accuracy than LADDER in the end. It should be noted that if we improve the latent space by training deep generative models on larger amounts of unsupervised structures. LADDER will be able achieve comparable or better accuracy when compared to the BO with Fingerprints kernel approach.
Iteration: 15
Iteration: 25
Iteration: 50
Iteration: 75
Iteration: 100
BO w/ Fingerprints
2.46 +- 0.32
2.80 +- 0.23
3.11 +- 0.11
3.32 +- 0.23
3.36 + 0.23
LADDER
2.78 +- 0.26
2.93 +- 0.23
3.18 +- 0.20
3.25 +- 0.18
3,25 +- 0.18
Moreover, there is general argument to justify the research direction of combining the strengths of latent space and structured kernels. Given a perfect kernel that captures all the relevant domain- specific characteristiis//tttuturr then the utility for latent space BO methods or LADDER will be limited. However, generic kernels over combinatorial structures (e.g., strings, trees, and graphs) may not always capture the critical domain-specifie characteristics. Consider the example of optimizing Metal-Organic Framework (MOF) materials [17] for adsorption property, e.g, storage of gases for hydrogen-powentt vehicles. For this problem, can use graph kernels over the graph representation of MOF materials, but they won't 't be able to capture some critical characteristics such as pore size, which is important to predict the adsorption property of MOF materials. In such scenarios, domain experts and practitioners can either spend time to engineer a hand-designed kernel (e.g. Fingerprints kernel from the chemical sciences community) or use large amounts of unsupervised structures data to learn a latent representation to capture these domain-specific characteristics in an automated manner. This paper takes the first step to synergistically combine the advantages of latent space and generic/domain-speciine
kernels to automate the overall BO workflow, which is highly advantageous for scientists and engineers who are the real-users of this technology. We do not claim that LADDER is the optimal algorithm to achieve this goal, but our hope is that LADDER will inspire the BO community to explore this important research direction to develop better algorithms in the future
One potential limitation of LADDER might be selecting the right choice of structured kernel for given task. Theoretically, the representation power of kernels is studied in terms of properties including universal and characteristic [64]. Satisfying these properties is basic requirement for selecting a kernel. However, since many known kernels are universal, this criterion might not be enough for all problem settings. Nevertheless, for combinatorial spaces, most of the generic kernels are roughly defined in terms of counting the number of common substructures in a given pair of combinatorial structures (25). Kernels that capture large sub-structures are generally more powerful in terms of their representational capacity. However, there is trade-off between representation power and time complexity of kernel computation. For our problem setting of optimizing combinatorial spaces using expensive function evaluations, an instance of small data problem (i.e., with a small number of structure and function evaluation pairs), it is best to select a kernel with the highest representation power and some hyper-parameter that can be optimized in a data-driven manner.
7 Summary and Future Work
We introduced a sample-efficient Bayesian optimization (BO) approach for combinatorial spaces called LADDER. The key idea behind LADDER is Gaussian process based surrogate model that combines the complementary strengths of latent space representation with rich information about decoded outputs using structured kernels. We showed that the BO performance of LADDER is better or similar than state-of-the-af methods and significantly better than the Naïve latent space BO method. Since LADDER's ' key contribution is in the surrogate model part of the BO procedure, provides the flexibility to use any acquisition function, which opens up an avenue for various type of extensions including -bjti-obeecctve 4 65
multi-fidelity 66 35 72 and constrained BO
29 23
'There is concurrent paper [45 at NeurlPS-202 that leverages epistemic uncertainty of the decoder to guide the optimization process.
10

---

Acknowledgements.
This research is supported in part by NSF grants IIS- 1845922, OAC-1910213 and SII-2030159. The authors' would like thank the anonymous reviewers for their constructive feedback and suggestions to improve the paper.
References
[1] Christof Angermueller, David Dohan, David Belanger, Ramya Deshpande, Kevin Murphy, and Luey Colwell. Model-based reinforcement learning for biological sequence design. In International Conference on Learning Representations, 2019.
[2] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy, BoTorch: A framework for efficient conte-carlo bayesian optimization. In Advances in Neural Information Processing Systems, 2020.
[3] Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In Proceedings of the 35th International Conference on Machine Learning, pages 462-471, 2018.
[4] Syrine Belakaria and Aryan Deshwal. Max-value entropy search for multi-objective bayesian optimization. In Advances in Neural Information Processing Systems, 2019.
[5] Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, and Janardhan Rao Doppa. Uncertainty- search framework for multi-objective Bayesian optimization. In AAAI conference on Artificial Intelligence, 2020.
[6] Syrine Belakaria, Derek Jackson, Yue Cao, Janardhan Rao Doppa, and Xiaonan Lu. Machine learning enabled fast multi-objective optimization for electrified aviation power system design. In JEEE Energy Conversion Congress and Exposition, 2020.
[7] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-Lópzz, Leslie O' Bray, and Bastian Rieck. Graph kernels: state-of-the-arr and future challenges. arXiv preprint arXiv:201 1.03854, 2020.
[8] David H Brookes and Jennifer Listgarten. Design by adaptive sampling. arXiv preprint 1rXiv:1810.03714, 2018.
[9] Poompol Buathong, David Ginsbourger, and Tipaluck Krityakierne. Kernels over sets of finite sets using RKHS embeddings. with application to bayesian (combinatorial) optimization. In International Conference on Artificial Intelligence and Statistics, pages 2731-2741. PMLR, 2020.
[10] Nicola Cancedda, Eric Gaussier, Cyril Goutte, and Jean Michel Renders. Word sequence kernels. Journal of Machine Learning Research, 3: 1:159-0008,, 2003.
[11] Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song. Syntax-directed variational autoencoder for structured data. In International Conference on Learning Representations, 2018.
[12] Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hyper- volume improvement for parallel multi-objective bayesian optimization. arXiv preprins arXiv:2006.05078, 2020.
[13] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Scalable combinatorial Bayesian optimization with tractable statistical models. CoRR, abs/2008.08177, 2020.
[14] Aryan Deshwal, Syrine Belakaria. and Janardhan Rao Doppa. Bayesian optimization over hybrid spaces. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages
2021.
[15] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Mercer features for efficient combinatorial Bayesian optimization. In AAAI conference on Artificial Intelligence, 2021.
[16] Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, and Alan Fern. Optimizing discrete spaces via expensive evaluations: a learning to search framework. Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 3773-3780, 2020.
11

---

[17] Aryan Deshwal, Cory Simon, and Janardhan Rao Doppa. Bayesian optimization of nanoporous materials. Molecular Systems Design and Engineering, Royal Society of Chemistry, 2021.
[18] Janardhan Rao Doppa. Adaptive experimental design for optimizing combinatorial structures. In Proceedings the Thirlieth International Joint Conference on Artificial Intelligence (IJCAI), pages 4945, 2021.
[19] Stephan Eissman, Daniel Levy, Rui Shu, Stefan Bartzsch, and Stefano Ermon. Bayesian optimization and attribute adjustment. Proceedings of the Thirty Fourth Conference on Uncertainty in Artificial Intelligence, 2018.
[20] Peter Frazier. A tutorial on bayesian optimization. arXiv preprint
2018.
[21] Peter Frazier and Jialei Wang. Bayesian optimization for materials design. In Information Science for Materials Discovery and Design, pages 45-75. Springer, 2016.
[22] Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson. GPyTorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, volume 31, 2018.
[23] Jacob R Gardner, Matt J Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cun- ningham. Bayesian optimization with inequality constraints. In International Conference on Machine Learning, volume 2014, pages 937-945, 2014.
[24] Eduardo C Merrido-Merchán and Daniel Hernández-Lobato. Dealing with categorical and integer- integer-valued variables in bayesian optimization with gaussian processes. Neurocomputingg. 380:20-34 35, 2020.
[25] Thomas Gärtner. A survey of kernels for structured data. ACM SIGKDD explorations newsletter, 5(1):49-58, 2003.
[26] Rafael Gömmez-Bombarelii Jennifer N Wei, David Duvenaud, José Miguel Hernández- Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Maallara-pprrrgirrrr,e Timothy D Hirzel, Ryan Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 4(2):268-27) 276, 2018.
[27] Anvita Gupta and James Zou. Feedback GAN for DNA optimizes protein functions. Nature Machine Intelligence, 1(2): 2019.
[28] Nikolaus Hansen. The ema evolution strategy: comparing review. Towards a new evolutionary computation, pages 75-102, 2006.
[29] José Miguel Beeránddz--Lobae. Michael A. Gelbart, Ryan P. Adams, Matthew W. Hoffman, and Zoubin Ghahramani. A general framework for constrained bayesian optimization using information-based search. Journal of Machine Learning Research, 77(1):5549-5601, 2016.
[30] Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown Sequential model-based optimization for general algorithm configuration. In International conference on Learning and Intelligent Optimization, pages 507-523, 2011.
[31] Rodolphe Jenatton, Cedric Archambeau, Javier González, and Matthias Seeger. Bayesian optimization with tree-structured dependencies. In International Conference on Machine Learning, pages 1664. PMLR, 2017.
[32] Yunlong Jiao and Phillpee Vert. The kendall and mallows kernels for permutations. In International Conference on Machine Learning, pages 1935-1944, PMLR, 2015.
[33] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pages 2323-22 2332.. PMLR, 2018
[34] Hiroshi Kajino. Molecular hypergraph grammar with its application to molecular optimization. In International Conference on Machine Learning, pages 3183-3191. PMLR, 2019.
12

---

[35] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabás Póc- zos. Gaussian process optimisation with multi- fulti-fidelity evaluations. In Advances in Neural Information Processing Systems, 2016.
[36] Jungtaek Kim, Michael McCourt, Tackgeun You, Saehoon Kim, and Seungjin Choi. Bayesian optimization over sets, arXiv preprint arXiv: 09780, 2019.
[37] Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In International Conference on Machine Learning, pages 1945-1954. PMLR, 2017.
[38] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. Text classification using string kernels. Journal of Machine Learning Research, 2(Feb):419.444, 2002.
[39] llya Loshchilov, Mare Schoenauer, and Michèle Sebag. Bi-population CMA-ES agorithms with surrogate models and line searches. In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computcation, pages 1177-1184, 2013.
[40] Xiaoyu Lu, Javier Gonzalez, Zhenwen Dai, and Neil Lawrence. Structured variationally auto- encoded optimization. In International Conference on Machine Learning, pages 3267-3275. PMLR, 2018.
[41] Andrea Mauri, Viviana Consonni, Manuela Pavan, and Roberto Todeschini. Dragon software: an easy approach to molecular descriptor calculations. Match, 56(2):237-248, 2006.
[42] Henry B Moss, Daniel Beck, Javier González, David S Leslie, and Paul Rayson. BOSS: Bayesian optimization over string spaces. arXiv preprint arXiv:2010.00999, 2020.
[43] Henry Moss and Ryan-Rhys Griffiths. Gaussian process molecule property prediction with flowmo. arXiv preprini urXiv:2010.01/ /18, 2020.
[44] Dang Nguyen, Sunil Gupta, Santu Rana, Alistair Shilton, and Svetha Venkatesh. Bayesian optimization for categorical and category-specific continuous inputs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5256-5263, 2020.
[45] Pascal Notin, José Miguel Hernández-Lobatt and Yarin Gal. Improving black-box optimization in vae latent space using decoder uncertainty. arXiv preprint vrXiv:2107.00090 2021.
[46] Changyong Oh, Jakub Tomczak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. In Advances in Neural Information Processing Systems, pages 2910-2920, 2019.
[47] Marcus Olivecrona, Thomas Blaschke, Ola Engkvist, and Hongming Chen. Molecular de-novo design through deep reinforcement learning. Journal of cheminformutics, 9(1):4,, 2017.
[48] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi-objeccive bayesian optimization using random scalarizations. Uncertainty in Artificial Intelligence, pages 766-776. PMLR, 2020.
[49] Jan Peters and Stefan Schaal. Reinforcement learning by woward-weighte regression for operational space control. In International Conference on Machine Learning, pages 745-750, 2007.
[50] Mariya Popova, Olexandr Isayev, and Alexander Tropsha. Deep reinforcement learning for de novo drug design. Science Advances, 4(7)xcaap7885, 2018.
[51] Liva Ralaivola, Sanjay J Swamidass, Hiroto Saigo, and Pierre Baldi. Graph kernels for chemical informatics. Neural Networks, 1893)11933 2005.
[52] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. Adaptive Computation and Machine Learning. MIT Press, 2006.
[53] David Rogers and Mathew Hahn. Extended-cooneectvvig fingerprints. Journal of Chemical Information and Modeling, 50(5):742-754, 2010.
13

---

[54] Reuven Rubinstein. The cross- method for combinatorial and continuous optimization. Methodology and Computing in Applied Probability, 1(2):127-190, 1999.
[55] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and llya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv: /703. 7703.03864, 2017.
[56] Bernhard Scholkopf, Sebastian Mika, Chris JC Burges, Philipp Knirsch, K-R Muller, Gunnar Ratsch, and Alexander Smola. Input space versus feature space in kemnl-based methods. IEFE transactions neural networks, 10(5):1000-100
1999.
[57] Anton Schwaighofer, Volker Tresp, and Kai Yu. Learning gaussian process kernels via hier- archical bayes. In Advances in Neural Information Processing Systems, pages 1209-1216, 2005.
[58] Daniel Schwalbe-Kode and Rafael Gómezz-oobarelli. Generative models for automatic chemical design. In Machine Learning Meets Quantum Physics, pages 445-467. Springer, 2020.
[59] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas, Taking the human out of the loop: review of bayesian optimization. Proceedings of the IEEE, 104())114--17,,22 2016.
[60] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. arXiv preprint AXXi:20011003822 2020.
[61] Kilho Shin, Marco Cuturi, and Tetsuji Kuboyama. Mapping kernels for trees. In International Conference Machine Learning. 2011.
[62] Gregor Simm, Robert Pinsler, and José Miguel Hernández-Lobato. Reinforcement learning for molecular design guided by quantum mechanics. In International Conference Machine Learning, pages 8959-8989 8969. PMLR, 2020.
[63] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms, In Advances in Neural Information Processing Systems- Volume 2, page 2951-2959, 2012.
[64] Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
[65] Shinya Suzuki, Shion Takeno, Tomoyuki Tamura, Kazuki Shitara, and Masayuki Karasuyama. Multi-objective bayesian optimization using pareto-frontier entropy. In International Conference on Machine Learning, pages
PMLR, 2020.
[66] Kevin Swersky, Yulia Rubanova, David Dohan, and Kevin Murphy. Amortized bayesian optimization over discrete spaces. In Conference on Uncertainty in Artificial Intelligence, pages 769-778. PMLR, 2020.
[67] Shion Takeno, Hitoshi Fukuoka, Yuhki Tsukada, Toshiyuki Koyama, Motoki Shiga, Ichiro Takeuchi, and Masayuki Karasuyama. Multi Multi-fidelity bayesian optimization with max-value entropy search and its parallelization. In International Conference on Machine Learning, pages PMLR, 2020.
[68] Austin Tripp, Erik Daxberger, and José Miguel Hernández-Lobato. Sample-efficient optimiza- tion in the latent space deep generative models via weighted retraining. Advances Neural Information Processing Systems, 33, 2020.
[69] Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In Annual Conference on Neural Information Processing Systems, 2001.
[70] Kevin K Yang, Zachary Wu, and Frances Arnold. Machine-learning--eeeee -euiddnng-guudedd directed evolution for protein engineering. Nature methods, 16(8):687-694, 2019.
14

---

[71] Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in Neural Information Processing Systems, pages 6410-6421, 2018.
[72] Yehong Zhang, Trong Nghia Hoang, Bryan Kian Hsiang Low, and Mohan Kankanhalli. information-basee multi-fidelity bayesian optimization. In NIPS Workshop on Bayesian Opti- mization, 2017.
[73] Zhenpeng Zhou, Steven Kearnes, Li, Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific Reports, 9()::1-10, 2019.
[74] Zhiyuan Zhou, Syrine Belakaria, Aryan Deshwal, Wookpyo Hong, Janardhan Rao Doppa. Partha Pratim Pande, and Deukhyoun Heo. Design of multi-outpul switched voltage regulator via machine learning. In DATE, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discussed potential limitation in Section 6.
(c) Did you discuss any potential negative societal impacts of your work?
[Yes] Since LADDER is general expensive black-box optimization algorithm, it's social impact is determined by the nature of end-application is employed in and the optimization objective for particular application. For example, accelerating the design of drugs/vaccines vs. gain of function experimental selection.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL.)?
[Yes] We provide our code in the supplementary material and a thorough description of the experimental setup is given in Section 4.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)?
[Yes] All the training details are given in Section 4.2.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)?
Yes] We show the error bars in all our figures.
(d) Did you include the total amount compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] provide the details of the computing resource used for our experiments in Section 4.2.
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators?
[Yes] We cited the original authors' for code libraries and datasets that we used in Section 4.
(b) Did you mention the license of the assets?
[Yes] The license is kept in the supplementary material.
(c) Did you include any new assets either in the supplemental material as a URL?
[Yes] We added our Bayesian optimization code in the supplementary material.
15

---

(d) Did you discuss whether and how consent was obtained from people whose data you'le re using/curating?
Yes]] We use all open-source codes available on public Github repositories.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? N/A
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "s9BIdKsa3qp", "reviewer": "Reviewer_mmhZ", "summary": "This paper proposes to improve Bayesian optimization over combinatorial space by introducing a structure-coupled kernel for the Bayesian surrogate model for BO. The structure-coupled kernel takes not only the embedded location in the latent space but also the corresponding representations in the combinatorial space. It uses a stationary kernel as well as a kernel for structured space such as string kernel and fingerprints kernel and combines them using a kernel construction based on generalized Nystrom extension. The proposed method is compared with the previous latent space based BO method as well as other state-of-the-art BO methods on the Arithmetic expression and chemical design datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper tries to tackle a limitation of the current latent space based BO approach for searching combinatorial space. It is a known issue that the surrogate model in BO does not take account of the information of the original structured representations. The proposed method feeds the information of the structured representation into the surrogate model via a structure-coupled kernel.\n\nThe paper is easy to follow, although sections 1-3 are a bit repetitive. The proposed method is quite interesting and the experimental results are promising. This work could be potentially a good contribution to the BO community. \n\nI have a few reservations regarding the proposed method and am happy to change my rating according to the authors’ feedback.\n\n1. Could the author provide some intuition about how the structure-coupled kernel behaves? It is easy to see that for the training points the covariance matrix equals L as K K^{-1} L K^{-1} K = L, but what about other data points?\n\n2. How does the proposed method compare with only using a structured kernel? In other words, what is the benefit of using the covariance matrix L from the embedded locations?\n\n3. The proposed method is computationally very expensive when there is lots of data due to the cubic computational complexity of GP. On the other hand, the latent space embedding model like the mentioned VAEs needs a lot of data in order to achieve a good embedding. In the experiments, the sizes of the training sets are all very small (up to 100). With this data size, VAE is known to perform badly. (i) Is latent space embedding helpful in this scenario? What would be the performance of only using a structured kernel such as a string kernel? (ii) If we increase the training set size to a few thousands, how does the proposed method compare with the pure latent space based method? \n\nMissing Reference:\n“Structured variationally auto-encoded optimization”, X Lu, J Gonzalez, Z Dai, ND Lawrence, ICML, 2018.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the limitations of the proposed method.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "hW9nV7EyimZ", "reviewer": "Reviewer_JPaw", "summary": "The authors propose LADDER, a BO method based on VAEs, and a new GP kernel that tackles structured spaces. \n\nThe contribution of the paper is the introduction of a new GP kernel that takes into account the decoded structures of points in the latent space. \n\nThe work is relevant for the BO community, the paper is well written. The experimental section and the structure of the paper can be improved. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "In general, the paper is relevant and well-written. I believe that the community will benefit from this type of work and the new kernel will be easy to integrate into existing frameworks. \n\nThere are two main negative points: \n1) The main criticism of this paper is that it goes into a long description of a problem setting that is fairly well-known at this point. In the last few years, the BO community has seen several papers on Latent Space Optimization (LSO) and an expert reader would be familiar with most of the content in this paper. The new part comes on page 5 from lines 170 to 202, fairly short. While this part is short, it is very relevant for the BO community and this is reflected in my final score.\nI would perhaps recommend the authors to go faster to the method and perhaps spend a bit more time describing the following points: \n- Why there is a \"fundamental disconnect between the modeling process and the objective function\", citing the words of the authors. Could you give a simple example to illustrate this point better, where you use the \"rich structural information\" as a working example? \n- Since the paper heavily relies on the Generalized Nystrom extension idea, it'd be useful to use some of the paper space to illustrate that extension a bit more extensively. \n- Describe the applications better. The reader has the feeling that it is expected to know these applications already while they are not mainstream applications. \n\n2) The experimental section would be much stronger if the authors used a commonly used Naive LSBO method instead of reimplementing their own. For example, the authors could have used SMAC or Spearmint, which are well-adopted frameworks. This lack of comparison makes Figure 3 much weaker. I strongly recommend the authors add such a comparison in Figure 3. And in that case, the curves in green and orange become irrelevant. \nIt is also unclear to me how much better the result is in Figure 3 (right). The final performance difference seems pretty small (0.5) and the curves are noisy. So, if you are not an expert on this application you are not able to judge how better those numbers are. \n\nThe authors don't mention if they considered retraining the VAE. They mention Tripp et al that do the retraining but I'd be curious to know if they experimented with the retraining and if that gives any improvement. \n\nThe authors could make more explicit in the text at their own advantage that they use the same benchmarks as in Tripp et al. with the 2D shape area which would be interesting to add so as to give a more thorough experimental setting. Comparing the results on at least three benchmarks would give more insights into the new method and make the experimental section stronger. \n\n\n\nMinor: \n- The name LADDER may conflict with the Ladder Variational Autoencoder which is in a similar space to this work: \nhttps://papers.nips.cc/paper/2016/file/6ae07dcb33ec3b7c814df797cbda0f87-Paper.pdf\n- Line 98: \"..\"\n- Line 126: it is usually bad writing practice to refer to Figure 2 when you didn't mention Figure 1 yet. \n- Line 161-169: it is bad writing practice to describe what GPs are in the middle of the method section. That paragraph should be moved into the background section. \n- Line 174: witin -> within  \n- Equation (1): add comas\n- Line 188: \"the eigenvector\" -> \"an eigenvector\" \n- Figure 2: move the figure to the bottom (or the top) of the page for good writing practice.  \n- Line 273: there is a grammar error in that sentence. \n- Line \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the checklist, the authors say in point 1.c that the potential negative societal impact was discussed in the paper. However, I think they only talk about this in the checklist which is against the writing guidelines. The authors should add this paragraph to the main paper. \n\nAdditionally, in point 3.d, while the authors describe the CPU used they don't describe the amount of compute used. This should be added to the main text. \n ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "HHNZdMKuvvS", "reviewer": "Reviewer_KoaP", "summary": "This paper proposes a new kernel specifically designed for performing Bayesian optimization in the latent space of deep [latent variable] generative models. The new kernel is formed by taking two existing kernels, one over the latent variable z (e.g. Matern, RBF) and another over the input space x (e.g. a string kernel), then combining them using the Generalized Nystrom Extension. They provide a motivating argument as to why a kernel that uses both x and z might be superior to one that just uses z, and perform experiments which suggest that this kernel improves overall Bayesian optimization performance.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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\n\nThis paper presents an interesting idea and was exciting to read. The proposed method, LADDER, is a novel combination of several already published methods. They demonstrate promising empirical performance of their method. However, I thought that the paper made a lot of imprecise claims and that the experimental evaluation was missing important baselines.\n\nBecause this is a chiefly empirical paper, to recommend acceptance I feel that the authors must show that their combination of methods leads to meaningful performance increases on relevant problems compared to baselines. Given their lack of comparison to important baselines, I was not convinced that their specific combination of methods was responsible for their reported performance increase and think it is plausible that they are instead leveraging advantages of an established method which is known to be superior. Given this I must recommend rejection, but I will be happy to change my mind if presented with new evidence.\n\n## Motivation (sections 1-3.1)\n\nAlthough I liked the idea of LADDER, to my surprise I disagreed with many statements the authors made when trying to motivate their work. Here are some key examples:\n\n1. Challenge #1 states that naive LSBO \"ignores\" the decoder, leading to \"fundamental disconnect between the modeling process and the objective function\" (lines 34, 116). Since the encoder is an approximate inverse of the decoder, even a BO method using just the encoder implicitly has a lot of information from the decoder, just not explicitly. Furthermore, the decoder *is* explicitly used in the naive LSBO procedure, as mentioned in lines 96-97. Therefore I think that the various claims made about \"ignoring the decoder\" are misleading and should be rephrased. For example, I think that a more moderate and accurate claim would be that \"kernels only using z don't explicitly incorporate information about the structure x, only what has been learned by the VAE, which may not have the desired inductive bias to approximate f(x) with a GP.\".\n2. Challenge #2 states that \"the statistical model itself might not be expressive enough to generalize well beyond the training examples from the latent space\". While this could happen for simple parametric models, GPs with RBF/similar kernels can approximate any continuous function to arbitrary accuracy [1,2], and therefore modelling failures are unlikely to be caused by the model \"not being expressive enough\". I agree that a GP may fail to generalize when trained on a small amount of data but I would attribute that to 1) poor choice of kernel/kernel hyperparameters 2) a large search space such that it is easy to find points far away from the training data where almost all ML models will fail to generalize.\n3. In line 125 you claim that Figure 2 provides \"strong empirical evidence to demonstrate these challenges and our key hypothesis\", when in fact it only shows that the predictive accuracy of the posterior mean with your kernel improves faster in the small data regime than the baseline kernel. This figure does not specifically provide evidence that the failure of naive LSBO is due to lack of expressiveness of the statistical model, nor does it show that it is inextricably linked to the kernel not using the decoded x explicitly.\n\nIn future versions of this manuscript, I think that the authors should tone down the strength of their claims, and either clearly present their motivation as \"conjecture\" or try to provide more specific arguments/evidence to support their claims about why naive LSBO doesn't perform well in the low data regime.\n\n## LADDER itself\n\nUsing a kernel that incorporates x explicitly is a good idea, and to my knowledge this has not been studied before in the context of BO with VAEs. The structure-coupled kernel that you use does not appear to be novel (after briefly skimming the reference that you cited), but it is certainly novel in this context.\n\nThe proposed structure-coupled kernel seems like a reasonable choice, although I think it could be motivated more in the paper. Why was this kernel in particular chosen? Why not a sum kernel like $k(x,x) + l(z,z)$ or a product kernel like $k(x,x)l(z,z)$? A priori these all seem like quite reasonable choices to me. You claim that your specific kernel is \"principled\" but it's not obvious to me what these principles are...\n\n## Experimental evaluation\n\n### Experiments performed\n\nIn general I think that the experiments supported the claims of the paper, although I have some questions and suggestions for improvement.\n\n1. Choice of experiments (logP and arithmetic expression task) was good and in line with prior work (although these tasks are somewhat contrived and I personally hope that the field will move away from them).\n2. Setup in section 4.2 is well-described and fairly comprehensive. I noticed 2 small things with your fingerprint kernel: 1) you didn't specify a radius of your fingerprints, which is an important parameter 2) you use the dot product between fingerprints, rather than the jaccard distance which is more standard [3].\n3. In \"Comparison of surrogate models\" (line 271) I had several issues with the experimental setup. Given these I don't think that you can conclude that the LADDER GP is better than the naive LSBO GP (even though I do think it's likely that it actually is better).\n    1. Firstly, you don't specify how the 50 random training sets are generated (i.e. random according to what distribution?).\n    2. Secondly, MAE is a very unusual evaluation metric for a GP, given that a) marginal log likelihood and not MAE is the GP training objective b) the BO process uses more than just the mean prediction from the GP; it also uses the predictive variance. I therefore think that MLL should be reported instead of MAE, and I'm not sure whether the trend will still hold.\n    3. Thirdly, you don't report baselines (e.g. MLL of prior GP, MAE of mean predictor) so it's unclear how significant the decreases in MAE shown are. If for example the variance of the dataset is normalized to be 1, then a MAE of >1 is already quite poor, suggesting that neither model fits the data well.\n    4. You don't specify how the GP hyperparameters are chosen for this experiments. You are using ARD kernels in what I presume is >=20 dimensions, so there are >=20 kernel hyperparameters to fit. It is very reasonable to assume that if the hyperparameters are found by MLL maximiation on only ~20 data points that there is a strong risk of overfitting which could explain the poor performance.\n4. Naive LSBO vs LADDER experiment (line 285): the methodology seems good here, but you don't seem to mention the number of initial training points used to fit the first GP, which is a very important omission. Nonetheless it does show that LADDER outperforms LSBO.\n5. LADDER vs. State-of-the-art (line 296). Again the number of initial training points is not shown: my understanding is that many of the baseline methods will perform better if given more training points, so this number is quite important. The difference for the arithmetic expression task seems quite significant, although it was disappointing that the performance for the chemical design task was not significantly better than the baselines. Thank you for being transparent about this.\n\n### Missing baselines\n\nI think that many important baselines were missing from this work. It is widely known that fingerprint-based methods perform well on a variety of small data tasks. However, you only compare against other latent space optimization methods.\n\nIn particular, **I would like to see a comparison against a Tanimoto kernel between the Morgan fingerprints.** I believe that this will be a strong baseline. It would also clarify whether your increased performance is due to using a kernel more similar to the Morgan fingerprint kernel or whether it is truly the combination of the latent space kernel together with the fingerprint kernel. *I think it is quite plausible that the latent space contributes very little to your method and that the reason you have performance increases is because you approach the performance of the Morgan fingerprint GP.* Note that for this baseline, because CMA-ES will no longer be applicable, I believe that your search strategy should be to sample a large number of points from the VAE (e.g. 10000) and choose the one with the highest acquisition function value. This is a key reason why I have decided to recommend rejection, so I would appreciate this point being addressed very directly and explicitly in your rebuttal.\n\nFurthermore, having worked with the ZINC250K dataset, I also think that randomly sampling from the dataset might be competitive with the performance you show in Figures 3-4. It would be nice to see this baseline too. I have less intuition about the arithmetic expression task.\n\n## Related work\n\nThe related work mentioned seems sufficiently comprehensive to me.\n\n## Overall review\n\n- Originality: I think the application of a Nystrom extension kernel to latent space Bayesian optimization is original.\n- Quality: I had issues with the writing and thought that the paper made too many vague claims, didn't justify important design decisions, and was missing important experiments to convince the reader of the usefulness of their method.\n- Clarity: the paper was clear in some parts but very unclear in other parts. I believe that the manuscript could use more polishing\n- Significance: the paper makes a contribution to an important problem, but I don't feel convinced that this contribution is large.\n\n\n# References\n\n[1] https://stats.stackexchange.com/questions/268429/do-gaussian-process-regression-have-the-universal-approximation-property#268884\n\n[2] https://jmlr.csail.mit.edu/papers/volume7/micchelli06a/micchelli06a.pdf\n\n[3] https://en.wikipedia.org/wiki/Jaccard_index#Tanimoto_similarity_and_distance\n\n# Post-rebuttal\n\nThank you again for your detailed response to my comments. After thinking about it and discussing my concerns with the other reviewers I have decided to keep my score. My primary reasons for this are:\n\n- performance is too comparable with the Tanimoto kernel (a strong baseline). I think that you should come up with an experiment that explicitly demonstrates the difference that the latent space makes here. I think that BO performance is too far removed from the model since it depends on the GP hyperparameters, acquisition function, and a lot of randomness (especially in the low-data setting). Perhaps reporting something like marginal log likelihood would be better, or plotting the predictions made during BO to see why it is doing better.\n- Other structured kernels should be explored as baselines\n- Structure-coupled kernel could be explained better see my Q5, although this was the least important reason because I trust that you will improve the description in the next version of the manuscript.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not believe that there are potential negative societal impacts of this work.\n\nI think that the authors mentioned some important limitations of the work, but focused heavily on its advantages. I believe that the following limitations should be mentioned or highlighted:\n\n1. Using a predefined structured kernel requires you to choose the *right* kernel, which can be an advantage if you know how to do that but can potentially be a disadvantage. Indeed, this is how the authors explain their poor performance in line 311. However elsewhere you mainly refer to this as an advantage. I think that this point deserves more nuanced treatment.\n2. Using a structured kernel means that you can no longer use gradient-based optimization to optimize the GP acquisition function, which is an important advantage of LSBO.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CnobC-nPWVd", "reviewer": "Reviewer_iwAZ", "summary": "This paper proposes a Bayesian optimization method to solve a combinatorial optimization problem by combining a latent space and structured kernels. Because optimizing an unknown function on a combinatorial space via Bayesian optimization is intractable, a problem is converted to a problem of optimizing on a continuous space (i.e., a latent space). The authors suggest a principled approach, dubbed LADDER. The main idea is to integrate structural information from decoded structures. Finally, the experimental results show that the proposed method outperforms other baseline methods.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "Combinatorial optimization is one of the most important problems in many science and engineering fields. This paper solves such a problem using Bayesian optimization, and the authors suggest a new approach to solving an optimization problem on a latent space. However, I have some concerns on novelty and numerical experiments. Please see the comments described below and provide a response for those comments in the rebuttal.\n\nPros\n\n+ The topic solved in this work is very interesting.\n+ The paper is well-written and well-organized.\n\nCons\n\n- The novelty of this work is limited, since similar studies [1, 4] have been proposed recently. They should be discussed in the paper.\n- I think some well-known baselines such as [2, 3, 5] are not included in the experiments. In my experience, those baselines might show robust performance in combinatorial optimization.\n- Real-world experiments are needed.\n\nDetailed Comments\n\n1. I would like to ask if the authors have a specific reason that does not include an approach based on Bayesian optimization as a baseline.\n2. How do you determine a search space for an acquisition function, i.e., $\\mathcal{Z}$? If this space is not well-defined, this approach might not work. Or, if there is a method to restrict an embedded vector into a compact and convex space, please describe in the rebuttal.\n3. How do you train a pair of encoder and decoder? Even though it is trained via unsupervised manner, it should be described in detail.\n4. Can you guarantee that a decoder always creates a valid example on combinatorial space? For example, if a chemical compound that is determined by a decoder might be invalid or impossible to synthesize, how did you cope with it?\n\nMinor issues\n\n* In Line 9, *doesn't* should be *does not*.\n* In Line 48, *Second, allows* should be *Second, it allows*. Please use a formal expression.\n* In Line 112, an equal symbol $=$ seems like not a mathematical font. Please check it.\n\n[1] R. Moriconi, M. P. Deisenroth, and K. Kumar. High-dimensional Bayesian optimization using low-dimensional feature spaces. Machine Learning, 109 (9):1925–1943, 2020.\n\n[2] R. Baptista and M. Poloczek. Bayesian optimization of combinatorial structures. In Proceedings of the International Conference on Machine Learning (ICML), pages 462–471, Stockholm, Sweden, 2018.\n\n[3] C. Oh, J. Tomczak, E. Gavves, and M. Welling. Combinatorial Bayesian optimization using the graph cartesian product. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 2914–2924, Vancouver, British Columbia, Canada, 2019.\n\n[4] T. Iwata and T. Otsuka. Efficient Transfer Bayesian Optimization with Auxiliary Information. arXiv preprint arXiv:1909.07670, 2019.\n\n[5] H. B. Moss, D. Beck, J. Gonzalez, D. S. Leslie, and P. Rayson. BOSS: Bayesian Optimization over String Spaces. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, Virtual, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not have any comments on limitations and societal impact. Please see \"Main Review\" for the detailed reviews.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for the additional clarifications provided in the rebuttal. All reviewers agreed that this work made interesting contributions and is relevant to the community. However, the consensus was that it missed important related work and baselines. In addition to the references indicated by the reviewers, the authors also missed [XYZ] where an explicit link was made to string kernels. Also, additional experiments conducted by authors showed that the improvement were marginal compared to missing comparable baselines. The fact that the proposed approach (namely, the combination of a structured kernel and a latent space based on the generalized Nystrom) lacked motivation as indicated by several reviewers suggests this work is not ready for publication yet.


[XYZ] R. Jenatton, et al. (2017): Bayesian Optimization with Tree-structured Dependencies. ICML 34.
Decision: Accept (Poster)