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-art 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- 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., Ki (()(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 kemell 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////ooeeeeee

---

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-art 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-22 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 Hernández-Lohann 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/ 118, 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-Lobato 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, 1093)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": "s7ckLdW9Mp3", "reviewer": "Reviewer_czoi", "summary": "This paper proposes a method for Bayesian optimization in combinatorial spaces, i.e. spaces of general objects, e.g. trees and graphs.  Existing methods usually map these objects into a supspace of $\\mathbb{R}^n$ , then perform traditional BO in that latent space. However, doing this ignores the structural information in the original space, which can be valuable. The method presented in this work incorporates such structural information into BO.  The end result is a covariance function, which combines information both in the latent space and the original space.", "questions": "", "limitations": "", "rating": 5, "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": "The problem this paper tries to solve is very important, i.e. bayesian optimization for structured objects. Since this paper still use traditional acquisition functions, e.g. expected improvement, which can only handle fixed-dimensional vectors. The focus of this work is more of the GP modeling than bayesian optimization. \n\nStrengths of this paper:\n1. this paper is well-written. Authors express their ideas in a succinct way.\n2. the empirical experiments are detailed.\n3. this work makes it clear correctly incorporating the structural information can indeed improve the performance. \n\nWeaknesses of this paper:\n1. The derivation in eq(4) is wrong. Correct if I missed something. The derivation from eq(3) to eq(4) means  $L = \\sum_{i=1}^{m}  v_i v_i^T$.  Eigenvalues are missing. Besides, the empirical feature mapping is not the correct one. Authors put a footnote in page 5 and claim \"core concepts are the same\". This is not a rigorous way. \n2. The novelty of the proposed method is  limited.  The core of this work is the covariance function in eq(4). This covariance function can be built through kernel construction rules in a very straightforward way. i.e. $x^T A z$, where $A$ corresponds to $K^{-1/2} L K^{-1/2}$. See [1]\n3. It is better to use terminology in BO. For example, In BO literature, \"best uncovered value\" (L287) is called incumbent.\n\n1.Rasmussen, C.E., Williams, C.K.I.: Gaussian processes for machine learning. MIT Press, Cambridge, Mass (2006).\n\npost-rebuttal\n====\nI'd like to thank authors' detailed response. However, based on existing empirical results, I am still not convinced that the proposed method is effective. The question of whether the success mostly comes from a good structured kernel is to be answered by more empirical studies. Based on discussions with other reviewers, I increase my score to 5. \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. One question I have is whether the improvements come from such a combined kernel or solely come from the use of a proper structural covariance function. For completeness, I suggest an extra experiment where only the structural  covariance function is used. \n2. Authors already pointed out how to select the  structural covariance function is one limitation of this work. This is indeed a big limitation. In Fig4 right, the performance of LADDER is on a par with several existing methods. This indicates a wrongly or sub-optimal choice of the corresponding covariance function can dominate the performance of LADDER. \n3. In Fig4 left, it is possible that the huge success of LADDER solely comes from the string kernel.  This shares the same idea with point #1. An extra experiment is needed.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "gUIgppba7AF", "reviewer": "Reviewer_pjM7", "summary": "This paper introduces a method that allows one to perform Bayesian optimization over a latent space of a data set, whereby an encoder and decoder are available. The key contribution is the use of a structure-coupled kernel to incorporate the decoded outputs as well as the latent space when performing BO.", "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": "The paper is well-written and does a good job at motivating the problem and highlighting potential flaws in previous approaches. \n\nThe main contribution of the paper is the introduction of the structure-coupled kernel to incorporate the output of the decoder as well as the latent space when learning the GP surrogate. All the empirical evidence provided in the paper demonstrates that this is a useful addition and it is therefore difficult to find any issues with the method.\n\nThe key comment/issue with this work comes down to whether the advantage comes from simply the structure-coupled kernel or whether there is no reason to include the latent space at all. These are the questions that would help clarify this issue:\n\n* The LADDER approach seems to build a data set of the latent space and the decoded latent space. It is clear from the results that the decoded latent space is important for the surrogate model, however it is not clear from the experiments whether it is possible to directly optimize over the black-box functions by simply using just the sub-sequence kernel or just the fingerprint kernel. It would be helpful to include “direct BO approach” as a comparison for Figure 2.\n* As far as I understand it, the purpose of working in the latent space is to make it easier to learn a GP surrogate. It seems that by using the decoded structure, the problem is brought back to its original dimensionality. What are the input-output dimensionalities of the chemical design and the arithmetic expression problem? Does the dimensionality increase of LADDER cause any potential problems.\n\n### After author comments:\n\nThanks very much for providing that extra experiment and comments. As a result I will stick with my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ZnE6MMhy16j", "reviewer": "Reviewer_G6A5", "summary": "* The authors tackle BO over latent spaces obtained through applications of VAEs, and note that current strategies in the modeling phase do not account for the decoder, thus potentially leading to a model that doesn't’ reject the true objective function. \n\n* The authors deal with this problem by defining a new kernel that essentially couples interactions of points in the latent space and in the original space, through this Generalized Nystrom Extension idea. \n\n* A set of well-chosen experiments indicate this approach yields a significant performance benefit. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Important problem; well-founded approach; promising results. \n\nI leave a few additional questions and comments below:\n\n* I think the one thing that could greatly strengthen this paper is a small model calibration study comparing the “naive” model that just considers a kernel defined over the latent space, and your LADDER kernel. Doing this even over a toy problem, for which a metric such as RMSE can be easily computed, would help the reader intuitively understand why this approach is better. \n* As noted in the experiment section, many combinatorial problems admit a natural kernel over the full problem space. Presumably, many don’t; what if a poor kernel is chosen that does not accurately model the full problem space? This is somewhat noted as a limitation in the conclusion, but it would be nice if the authors provided some more intuition as to what conditions a good kernel for the combinatorial space ought to have. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FnkWbpTs3s4", "reviewer": "Reviewer_nmQh", "summary": "### Summary\n\n(+) Bayesian Optimization over Combinatorial Spaces is a relevant topic for the community\n\n(+) The paper is clear, well written and properly structured\n\n(+) The empirical evaluation is well structured and split according to clear questions.\n\n(-) In its current form, the paper makes it difficult  to precisely relate its claimed contributions to previous research\n\n(-) Some simple, generic baselines (e.g., random search) seem to be missing\n\n(-) The introduction of the “Generalized Nystrom” parametrization would deserve more intuition. \n", "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": "### Detailed comments\n\n* To clarify, in the “Challenge #2”, the concern is the fact that d is large (i.e., the dimension of Z)? If this is the case, this could be clarified.\n\n* “ Given kernels l and k with L and K...“: In this sentence, it should be clarified that the kernel l operates in Z x Z while k operates over X x X (at least this is my understanding).\n\n* I am under the impression that the paragraph “Structure-coupled kernel. ” is a bit difficult to follow. I check the refs associated with the “Generalized Nystrom extension idea”. I wonder if the material could be introduced differently, by building up more intuition? (e.g., would there be other alternatives, simpler to grasp but too expensive? What would be a more naive kernel, sitting in between LSBO and the more sophisticated proposal? etc.)\n\n* What’s the sensitivity of the results with respect to the amount of unsupervised pre-training?\n\n* I have two comments/questions for the paragraph “Comparison of surrogate models.”. \n(I) Why MAE is used and not a metric that would also quantify the uncertainty? (II) To further validate the hypothesis (“d is too large”), Fig. 2 should also display what happens if we pretrain the decoder/encoder for various sizes of d. \n\n* “The discrepancy in LADDER’s performance on the chemical design benchmark can be attributed to the low-flexibility of fingerprint kernel which doesn’t include any hyper-parameters”: Aren’t there options of richer kernels to test this hypothesis?\n\n* A relevant reference to add: Lu et al., Structured Variationally Auto-encoded Optimization (http://proceedings.mlr.press/v80/lu18c.html)\n\n* Why naive generic baselines like random search and a standard genetic algorithm aren’t reported?\n\n* I am not sure it is necessary to dedicate a section about “Reinforcement learning” in the related work. Instead, I would like to see further detailed discussion about the precise connections between the present submission and other works around BO + DGMs. The paper explains well how the proposed approach differs from LSBO but not how it differs from previous works. \n\n### Minor\n\n* In Sec. 2, second paragraph, some “x”’s, e.g.,  need to be made bold for consistency\n\n* “...large [15, 52, 11, 22]..” → “...large [15, 52, 11, 22].”\n\n* “A GP model defines a prior distribution on functions which is entirely characterized by a kernel defined over a pair of inputs…” → ...and a mean function\n\n* In the sentence “...and v_i is the eigenvector of the kernel…”, I am not sure the i index refers to the same i index for K_{i,j} (in the latter, this is the i-th data point z_i). In my understanding, they mean different things and different letters could be used to avoid confusion.\n\n* “Reinforcement learning” → “Reinforcement learning.”\n\n\n### UPDATE POST REBUTTAL\n\nI have gone through the reviews and the replies of the authors, whom I'd like to thank for the work put in the rebuttal.\n\nMany of my concerns/questions have been clarified, e.g.,\n\n* Added comparison to random search\n* Improved introduction and discussion of the “structure-coupled kernel”\n* The authors also promise to develop further their related work section to better discuss the links with previous research (beyond LSBO).\n\nWhile at this stage, I was willing to improve my score, the discussion with the other reviewers made me aware of important aspects that I had overlooked. \n\nIn particular, the experiments of the paper and those provided in the rebuttal do show that the performance hinges on the used structured kernel. Moreover, the latent information seems to contribute only moderately to the final gains, which, when combined with the expensive cost of pre-training, weakens the argument to use the latent information.\n\nAll in all, I am thus going to keep my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed, in the sense that I haven't seen any dedicated paragraph about this topic but the work does not present, to the best of my understanding, potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.0"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Recent work in Bayesian optimization has proposed latent space optimization, where Bayesian optimization is performed in the latent space of an autoencoder. This paper makes a potentially interesting advancement over the standard approach of using only latent codes as input to the GP. In particular, this paper defines a kernel jointly over a latent code z and the decoded structure \Phi(z). 

Ultimately, I think the simplicity of the authors' approach is its strength. An obvious weakness of latent space optimization is that, because the decoder is not perfect, the decoded structure \Phi(z) may not have the predicted objective value of z, even if the surrogate model were highly accurate. Directly incorporating the decoded structure into the surrogate model is an obvious and natural baseline approach to this, but (crucially) one that I have not seen elsewhere. 

Please incorporate the additional results run during the author feedback period and other reviewer feedback in the final version of the paper.
Decision: Accept (Poster)