Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization
Authors: Kamil Dreczkowski
Antoine Grosnit
Haitham Bou Ammar
Venue: NeurIPS 2023 Datasets and Benchmarks Poster (2023)
Keywords: Bayesian Optimisation
Combinatorial Optimisation
Mixed Space Optimisation
Library
Benchmarks
TL;DR: A library offering modular implementation of combinatorial and mixed-space Bayesian optimisation solvers along for benchmarking on real world tasks.

Abstract: This paper introduces a modular framework for Mixed-variable and Combinatorial Bayesian Optimization (MCBO) to address the lack of systematic benchmarking and standardized evaluation in the field. Current MCBO papers often introduce non-diverse or non-standard benchmarks to evaluate their methods, impeding the proper assessment of different MCBO primitives and their combinations. Additionally,  papers introducing a solution for a single MCBO primitive often omit benchmarking against baselines that utilize the same methods for the remaining primitives. This omission is primarily due to the significant implementation overhead involved, resulting in a lack of controlled assessments and an inability to showcase the merits of a contribution effectively.
To overcome these challenges, our proposed framework enables an effortless combination of Bayesian Optimization components, and provides a diverse set of synthetic and real-world benchmarking tasks. 
Leveraging this flexibility, we implement 47 novel MCBO algorithms and benchmark them against seven existing MCBO solvers and five standard black-box optimization algorithms on ten tasks, conducting over 4000 experiments. 
Our findings reveal a superior combination of MCBO primitives outperforming existing approaches and illustrate the significance of model fit and the use of a trust region. We make our MCBO library available under the MIT license at \url{https://github.com/huawei-noah/HEBO/tree/master/MCBO}.

Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization
Kamil Dreczkowski *t Imperial College of London krd1158ic.ac ac.
Antoine Grosnit'
Haitham Bou-Ammar Huawei Noah's 's Ark Lab University College London
Huawei Noah's ' Ark Lab Technische Universität Darmstadt
Abstract
This paper introduces a modular framework for Mixed-variable and Combinatorial Bayesian Optimization (MCBO) to address the lack of systematic benchmarking and standardized evaluation in the field. Current MCBÒ papers often introduce non-diverse non-standard benchmarks to evaluate their methods, impeding the proper assessment different MCBO primitives and their combinations. Addi- tionally, papers introducing solution for a single MCBO primitive often omit benchmarking against baselines that utilize the same methods for the remaining primitives M+ This omission is primarily due to the significant implementation overhead involved, resulting in a lack controlled assessments and an inability showcase the merits of contribution effectively. To overcome these chal- lenges, our proposed framework enables an effortless combination Bayesian Optimization components, and provides diverse set of synthetic and real-world benchmarking tasks. Leveraging this flexibility, we implement 47 novel MCBO algorithms and benchmark them against seven existing MCBO solvers and five standard black-box optimization algorithms on ten tasks, conducting over 4000 experiments. Our findings reveal superior combination of MCBÓ primitives outperforming existing approaches and illustrate the significance of model fit and the use of trust region. We make MCBO library available under the MIT license at httph:tt//// //ggttt cwm/ com/huawei noah/ HEBO/ HEBD//tre////eeeeeeeeeeeeeeeeeee watree//mattee/CCCB
Introduction
The goal of mixed-variable and combinatorial optimization is to seck optimizers of functions defined over search spaces whose sizes grow exponentially with their dimensions. Applica- tions of this field ubiquitous, spanning wide range domains, such as supply chain optimiza- tion R 9. vehiele routing [10] [1] machine scheduling in manufacturing systems [12] [3].
Lin. rec. (SIT)
New
New
BOC'S
1
New
GP (DiI.)
COMBO
(SSK)
New
New
BOSS
GP (HED)
New
BODK
Now
New
(Trans
Over))
New
(Dver
New
New
New
New
CoC.BO
B
Model
asset optimization [14 15 among many others. general recipe for tackling such tasks involves using the knowledge of domain experts for- malize combinatorial problems within the scope of well-established suited mathematical frame- works, and to apply available heuristic-basee solvers. For instance, making the problem compatible with linear, quadratic, nonlinear or integer pro-
Aog. opt.
Exlanstivc
LS
Grad.
HC
dese.
Simulated
sancaling
algorishm
Geenttic
Grad.
MAB
desc.
Figure 1: the MCBO framework, we can build an existing new algorithm by choosing surro- gate model and an acquisition function optimizer using single line of code.
37th Conference on Neural Information Processing Systems (NeurIPS 2023) Track on Datasets and Benchmarks.
"These authors contributed equally to this work.
Work done during internship at Huawei Noah's Ark Lab in London RC.

---

gramming solvers, or reducing the combinatorial task at hand to standard problem such as knapsack []], traveling salesman [77. or network flow problem [1]] allows the application of optimized and scalable off-the-shelf software developed by many companies and academic laboratories [2]
Despite numerous successes many combinatorial tasks, standard heuristies like those mentioned above fall short in vital domains that require the optimization of black-box objectives. In those instances, we have, best. partial priori knowledge about the characteristics of the optimization objective, making it difficult, if not impossible, to map it to one of the forenamed mathematical frameworks. Although estalesst black-box optimization methods such as Simulated An- nealing (SA) [23 24], Genetic Algorithms (GAs) [25,, and Evolutionary Algorithmss (EAs) [26], as well as online learning methods like Multi-Armed- Ariddd---m-- (MABs) [27], can still be used to solve such problems, they often fall short at optimizing
objectives due to their high sample complexities. Consequently, addressing problems with expensive-to-evaluee black-box objectives necessitates the development of data-driven and sample-efficient solution methodologies.
One promizing strategy to handle such objectives is to 1) efficiently learn a (local) probabilistic model of the black-box function, and 2) balance exploration and exploitation by leveraging the model's uncertainty. This concept lies at the heart of Mixed-Variale
and Combinatorial Bayesian Optimization (MCBO), a machine learning (ML) subfield crucial for achieving efficient optimization with immense potential for solving practical mixed-variable and combinatorial optimization problems.
MCBO algorithms generally have three high-level primitives: probabilistic surrogate model, an acquisition function, and an acquisition optimizer that can operate in a trust region (TR). As shown in Fig. [] we can frame many published MCBO algorithms as a specific combination of primitives, illustrating the intrinsic modularity of MCBO. For example, BOiLS 4 uses a Gaussian Process its surrogate, and optimizes its acquisition function (expected improvement (EI) via TR TR-constrained Hill Climbing [5]. BOSS 7 shares two of its primitives with BOiLS but only differs in using a GA optimize its acquisition function.
(GP) (28] with the string subsequence kernel (SSK) 29 30
Although many existing MCBO algorithms share some of the primitives they use, it remains unclear which solutions are state-of-the-ard for each primitive and which combination of primitives constitutes state-of-the-art MCBO method. This issue arises due to two factors.
Firstly, MCBO papers often introduce non-diverse and/or non-standard benchmarks to evaluate their proposed methods. The lack of a standardized set of diverse benchmarks makes it difficult to assess the relative performance of the different MCBO primitives and their combinations. As observed in other fields, establishing standardized test domains is crucial for accelerating progress in MCBO. For example, the ImageNet dataset (31), ShapeNet, and MuJoCo [32 facilitated rapid advancements in 2D computer vision, 3D computer vision, and robotics research. Therefore, it is essential to establish a procedural generation of test domains in MCBO, enabling a systematic evaluation of existing methods to inspire the development of novel approaches.
Secondly, papers introducing a solution for a single MCBO primitive often forget to benchmark against baselines that use the same methods for the remaining primitives [14, failing to fully highlight the merits of their proposed solution in a controlled setting. This is most likely due to the need for time-consuming and tedious efforts to modify and combine MCBO primitives from existing open-source implementations, as no standardized API exists to allow the interactions among them.
To address the aforementioned problems, we propose flexible and comprehensive Python framework for MCBO. Our library provides high-level API for all the MCBO primitives, and implementations of the primitives of several key MCBO baselines. Our framework also features BoBuilder class that enables effortless implementation of existing and novel algorithms by flexibly combining MCBO primitives using single line of code. In Section [ we showcase the versatility of our library by implementing seven existing MCBO baselines and 47 novel MCBO algorithms. We evaluate these against five standard black-box optimization baselines on ten tasks, revealing insights into key MCBO design choices that contribute to robust algorithms.
Our library also includes implementations of a wide range of synthetic and real-world mixed- variable and combinatorial benchmarks, covering broad spectrum of domain dimensionalities and optimization difficulties. These benchmarks include well-known optimization problems, such as the Ackley function 33 and the Pest Control problem 22. and optimization problems that extend
2

---

the current application venues of BO, including Antibody Design, RNA inverse folding, and Logic
Synthesis optimization.
In the interest of space, throughout this paper we make heavy use of abbreviations. We therefore provide list of these abbreviations, alongside their definitions, in Table Tf Appendix A
2 Related Work
Bayesian Optimisation Frameworks Existing popular librarics for Bayesian Optimization (BO), such Spearmint (34), GPyOpt [35], Cornell-MOE (36), RoBO [37]. Emukit (38). Dragonfly [39],
ProBO 40), and GPFlowOpt 41]. offer diverse capabilities and modeling techniques for various optimization tasks. These libraries excel in different areas, including hyperparameter sampling. input
warping and parallel optimization 34 65 multi-fidelity optimization (6.38), and probabilistic
programming [4). However, in contrast to work, these libraries primarily focus continuous and discrete search spaces and lack direct support for combinatorial and mixed-varian domains.
Closest to our work is BoTorch 42 model-agnostic Python library that is integrated with GPyTorch 43 providing efficient and scalable implementations of GPs in PyTorch [4]. Although BoTorch includes the GP kernel for mixed-variable optimization proposed by Wan et al. [5]. it primarily focuses on continuous and discrete search spaces and does not provide direct built-in support for combinatorial formulations. In contrast, our framework is designed to tackle the unique challenges of BO in combinatorial and mixed-vvriable spaces and extends the capabilities of existing libraries by incorporating surrogate models and acquisition optimization techniques tailored to these domains.
Furthermore, our framework offers an unprecedented level of ease and flexibility in implementing BO algorithms by mixing-and-matching implemented BO primitives. With just a single line of code, users can combine different surrogate models, acquísition functions, and optimization methods. In contrast, other libraries would require time-consuming manual implementation processes to make components match.
Mixed-variable and Combinatorial Optimization Benchmarks Existing popular benchmarks for mixed-variable and combinatorial problems include the 24 synthetic mixed-integer test functions 45 that are part of the COCO 466] benchmarking suite. Our framework extends some of these functions, including the sphere, rotated hyper ellipsoid, Rastrigin, and Rosenbrock functions, accommodate arbitrary dimensional domains and combinations of variable types. Moreover, we introduce additional synthetic functions that uphold the same generalization principles.
Distinguishing our benchmarking suite from benchmarks such as HPOBench [47] HPO-B 48 and YAHPO Gym 49) which primarily focus a single domain such hyperparameter optimization, our framework takes more comprehensive perspective. Our suite encompasses broader spectrum of tasks, spanning hyperparameter tuning, antibody design, Electronic Design Automation, RNA inverse folding, along with the classical synthetic tasks. This multi-domain nature underpins our conviction that benchmarking on diverse tasks that cover a broad spectrum of problem types and complexities strengthens the robustness and reliability of findings. We hold firm to the notion that this multifaceted approach leads to more generalisable conclusions than scenarios where only single family of tasks is used for benchmarking, which can still be useful for important black-box families.
3 Mixed-Variable and Combinatorial Bayesian Optimization
BO is sequential model-based technique efficiently optimize a black-box function f(-) over search space X. Due to the black-box nature of f()), we can only evaluate it at input locations æ E X to get (noisy) outputs y E R. such that [=)] = f(z). BO tackles global optimization problems by iteratively repeating two steps. At iteration i, it first suggests a point Φ; to evaluate, and in æ;, To enable sample efficiency, the suggestion of æ; typically involves learning a (local) probabilistic surrogate model of f(.) from the set of already observed points, and is followed by the optimization an acquisition function a(-) trading-off off exploration exploitation. We highlight both steps in Alg. [ and depict a generic BO loop operating for a total budget of T Tuax-
second step, the learner observes y/s by evaluating the black-bor
3.1 The Surrogate Model
3

---

Algorithm 1: Generic BO Algorithm
Optimizing expensive black-box functions requires modeling the objective to enable efficient search by
Input:
Initial dataset
prioritizing informed decision-making over blind func-
Dno {æ, Mj j= budget
tion evaluations 34 When dealing with mixed-
Tmx.. black-box J.
variable and combinatorial formulations, various sur- rogate models are available, including Bayesian Lin- ear Regression [50], Random Forests [51]. Tree- Structured Parzen Estimators [52], and Bayesian Neu- ral Networks [53]. Still, GPs [28] remain the most widely adopted models in the literature due to their tractability, sample efficiency, and capacity main- tain calibrated uncertainties [28
for = mo + I,,... T max do
Learn a surrogate model M(-12;-1)
of f.
Use MM-[D;-1) to define
acquisition function a(x (D-1)). Optimize a(x) 1 1) to get æq.
Get ys by evaluating f at æ;.
54 55 and
Set D; < D U {2,, We). Output: x arg m.
therefore our library mostly focuses on their support.
Ys-
GP is a non-parametrie model that represents the prior belief about black-box function distribution over functions and updates this distribution as new observations become available, resulting in a posterior distribution. A GP is fully defined by its mean function mn() and kernel function, ke (.)..), where O are the kernel hyperparameters [28] [54) The mean function captures the overall trend and bias of the modeled function, while the kernel function characterizes the correlation between function values at different input locations. Specifically, the kernel function, ( x²), expresses our assumptions regarding the smoothness and periodicity of the modeled function, as it corresponds to the covariance between pairs of function values Cov( (ar), (ar)).
When modeling black-box functions defined over combinatorial spaces, one commonly used kernel function is the Overlap kernel 3 56 57]. defined using Kronecker delta function 8(.,.) as
1.0 ar x²)
Ap ō (<< x (v)),
with 0 = (o,, A1,.,....., E R4+1, where a represents the kernel variance, d is the dimensionality of x, and Ap denotes the Automatic Relevance Determining (ARD) (58) length scale for the pdh variable. In combinatorial problems, æ E {c]...., N X x {oM ...., Nas defining all the possible elements that the hth combinatorial variable can assume, N₁ is the cardinality of this set, and M is the total number of combinatorial variables. In this context, the Overlap kernel measures the extent to which variables in the two input vectors share the same categories.
.M J. where {ci, ..., c'v, } is the set
related kernel the Transformed Overlap (TO) kernel S applying the exponential function to the output of the Overlap kernel. This transformation enhances the kernel's expressive power, enabling it to model more complex functions
[5). Other kernels tailored for combinatorial inputs include the SSK 229 30). the Diffusion kernel (Diff.) [2], and the Hamming embedding via dictionary kernel (HED) 6,, which are all supported in our framework.
Given a dataset D = {æ,, 3 with Gaussian-corrupped observations yi = [(x;) + 6, with & ~ N o²), and given a GP prior, the posterior of the black-box function value at test point Press denoted (( ) |D, 0, is also a Gaussian distribution N' (Io(e)))) (arre))) For brevity, we defer Appendix the analytic expressions for (3ree)) and o (Wrea) along with the method to learn the optimal kernel hyperparameters 0* by minimizing the negative log-likelihood.
3.2 The Acquisition Function
The acquisition function plays crucial role in BO as it approximates the utility of evaluating the black-box function at a specific input x X. Since the black-box function is unknown, the acquisition function considers both the estimated value of the objective function and its associated uncertainty. This enables the acquisition function to effectively balance exploration of the search space, gathering more information about the underlying objective function and exploiting currently promising regions likely to contain the optimal solution. Ultimately, the acquisition function is a criterion for selecting the next point evaluate in the optimization process.
The Expected Improvement (EI) [59 60 acquisition function measures the utility of new query points by evaluating the expected gain compared to the function values observed so far, considering

---

the uncertainty of the model's 's posterior. During each iteration of the optimization process, let vi denote the best black-box function value in the dataset D The EI function is defined as:
(aI) [x) = E( [max - {[)),
where the expectation is taken with respect the posterior of trained model. Our framework supports EI as well as other popular acquisitions such as Probability of Improvement (PI) [6]] lower confidence bound (LCB) 62,, and Thompson sampling (TS) [63] all described in Appendix B.3
3.3 Acquisition Optimization Methods
The acquisition optimization method plays vital role in BO it determines the next evaluation point z; by optimizing the acquisition function (=) In general, maximizing the acquisition function find æ; is optimization problem defined globally over the entire search space:
arg max a<x) #Ex
When dealing with a continuous search space, optimizing the acquisition function is relatively straightforward and can be performed by using off off-the-shelf first or second-ore order optimization methods with random restarts (refer to [64] for comprehensive study on this topic). However, when dealing with combinatorial inputs, the absence of a defined gradient hinders the direct application of gradient-based optimization methods [65]. To address this challenge, various zero-order methods have been proposed for maximizing the acquisition function in combinatorial spaces. These methods encompass range of global optimization algorithms and heuristics, including Hill Climbing (HC) [S] exhaustive Local Search (LS) [2). SA []. GA 77. and MAB (3], which we include in our library.
These acquisition optimizers are often applied as global optimization algorithms to solve Equation 2 However, just like continuous spaces, when the dimensionality of the search space is high, the surrogate may struggle to accurately model the black box over the entire search space. Taking inspiration from related work in BÒ for continuous spaces [66]. some recent combinatorial BO algorithms, including Casmopolitan [S] introduce the notion of a TR to constrain the acquisition optimization procedure the context of MCBO. In Casmopolitan, the TR around the best input found so far in the current trust region, x. TR, is defined as
TR (R) (xc X' s.t. (n TR mx) T. and dr., (I F.,) $ 11;
(3)
where wh and Ty are vectors containing all the combinatorial inputs in x and respectively, d-(-.)) is the Hamming distance [5] and Ln is the size the TR for combinatorial variables. Similarly, .TR and 2n vectors containing all the numeric and discrete variables in TR and æ, respectively, (..)) is the maximum of the component-wist distance for numeric and discrete variables normalized by dimensional length scales I., E IR+ variables
dim(an) for the numeric and discrete
4 The MCBO Framework
To facilitate code reusability and enable benchmarking standardized set of tasks, we introduce the MCBO framework, whose source code is open-source under the MIT license. Our ready-to-use software provides 1) An API for defining BO primitives, 2) Multiple primitives from key existing MCBO baselines, 3) A BO constructor to effortlessly combine primitives into new algorithms, 4) A variety of mixed-type and combinatorial BO and non-BO baselines, 5) A suite of standard and novel mixed-type and combinatorial benchmarks, and 6) An API for defining novel optimization problems.
We structure the MCBO framework in modular fashion to allow for the rapid prototyping of new solutions by combining existing BO primitives. We build MCBO on top PyTorch 44 to make compatible with the rich ecosystem of code developed for training various regression models. The entire library structure naturally revolves around seven Python classes; the SearchSpace, TaskBase, Mode Mose, AcqBase, AcqDptimizerBaateet Opt OptimizerBase, and the BoBase class.
5

---

4.1 Defining Optimization Problems
To frame the optimization of a black-box within our framework, we need to create a task class (inher- iting from TaskBase) that implements two methods: get_search, search_ sacchsspaceee space_params params and evaluate. The latter implements the call to the black-box, while the former provides the list of variables that compose the optimization domain of the black-box. We build search space (an instance of Sear chSpcee) by providing this list of variables with their names, types, and any additional information needed, such as the categories they can take for categorical variables. As an example, consider combinatorial optimization problem whose search space contains five categorical variables (with categories "A", "B", "C", and "D") and for which black-box function already defined as black_ Black_bo_____ box_scripp in python script. In the MCBO framework, we can create the corresponding task as follows:
class BlackBox (TaskBaae)))))
def wtw.serrcchspcceparrreeee params (self) -> [isct Any]]: categories = ['A', 'B', 'C', 'D']
params (('name's f'x(i'' 'type': 'nominal', 'categories': categories)
for in range(5))]
return params
def evaluate x: pd. DataFrame)) >> np. ap.ndarray: return black_box_scripppe
black_box BlackBox()
search
search_space space black_ box, pet__search_sacee get instance of SearchSpace
4.2 Surrogate Models, Acquisition Functions, and Acquisition Optimizers
The MCBO framework includes three core BO primitives: surrogate models, acquisition functions, and acquisition optimizers. 1) Our implementation features several pre-implemented surrogate models, such GP with the string subsequence kernel (SSK) 71, overlap kernel (O) (3],
transformed-overlapp kernel (TO) [5], diffusion kernel (Diff.) 2 dietionary-based kernel (HED)
(6]. mixture kernel (5), and linear regression [50] with the Horseshoe prior [67] using maximum
likelihood, maximum a posteriori, and Bayes estimation (LHS) M. 2) On the acquisition function
side, include the widely used expected improvement [59 60), probability of improvement [61] and lower confidence bound [62] for GPs, and Thompson sampling 63 for LHS. 3) Furthermore,
library includes various acquisition optimizers, such exhaustive Local Search 22, Genetic Algorithm 77] Simulated Annealing [ and interleaved search (IS) alternating between Hill Climbing or Multi-armed Bandit for combinatorial variables and gradient-descent steps for numeric variables as developed for CoCaBO (3] and Casmopolitan (5). Moreover, we generalize the implementation of these acquisition optimizers so that all of them support "R-constrained acquisition optimization. extending [5] (68). and make them handle cheap-to-compute input domain constraints via rejection sampling.
4.3 Defining MCBO Algorithms
With our framework, defining MCBO algorithms is effortless. By specifying the IDs of the surro- gate model, acquisition function, acquisition optimizer, and TR manager in the BoBuilder class constructor, the corresponding BO primitives are automatically retrieved. In an optimization loop, the optimizer created with BoBuilder handles model fit, acquisition optimization, and TR adjust- ments. Thanks the BoBuilder class, we can easily mix-and-match BO primitives from existing algorithms, allowing the implementation of novel MCBO algorithms with just one line of code per algorithm. We demonstrate the versatility of this approach by implementing 47 novel MCBO algorithms and evaluating them on set of ten tasks in Section 5 As an example, we showcase on the next page how to use BoBuilder to construct the Casmopolitan algorithm and apply it to optimize generic black-box function for specified budget.

---

4.4 Baselines
MCBO baselines We leverage the aforementioned
BO primitives to implement seven existing MCBO algorithms: Casmopolitan [5]. BOILS 4 COMBO 21. CoCaBO 3. BOSS 7.. BOCS D. and
bo_builder BoBuilder(
model_id id= gp_to',
acq_opt_ide iopt_id='is 'is', wefffunc_d-''e
BODi G Furthermore, we explore the remaining combinations of implemented surrogate models and acquisition optimizers, including trust-region-ban optimizers, implementing 47 additional novel MCBO algorithms (See Fig. D. In Section 5 we benchmark the performance of these 54 MCBO algorithms and set of five standard non-BO baselines that we describe in the following paragraph.
traid='
**kwargs
# Corresponds to Casmopolitan
opt bo bo_builder build_bo(
n_init=20
Black-Bop Optimization Baselines To facilitate benchmarking against non-BO optimization methods, we include the following baselines in our library: Random Search (RS) [69] Hill Climbing (HC) [70], GA (2) SA 23 24 and MAB (27]. We make them inherit from the OptimizerBase class, ensuring
for range (budget):
x_next suggett ()
y_next black_ (x_next)
opt observe(x_neee y_next)
(oint best_x, opt. bestyy
consistent API with MCBO solvers with the use of suggest and observe methods.
4.5 Available Benchmarks
We include diverse benchmarks, enabling systematic evaluation of MCBO methods across various optimization domains, dimensionalities, and difficulties. The benchmarks encompass both synthetic and real-world tasks. While briefly overview the available benchmarks here, provide more detailed description, including specific constraints, dimensionalities, supported domains, and implementation details in Appendix C
The synthetic benchmark suite offers a controlled environment for evaluating the performance of MCBO methods, featuring the 21 Simon Fraser University (SFU) test functions [33] that generalize to d-dimensional domains, extended to handle continuous, discrete, and nominal variables, as well as combinations of these variable types. Additionally, include the pest control task [ that presents a challenging optimization landscape with high-order interactions.
For real-world tasks, the benchmark suite includes logic synthesis optimization 7 antibody design 772), RNA inverse folding (73), and hyperparameter tuning of ML models. The logic synthesis benchmarks optimize Boolean circuits represented by And-Inverter Graphs (AIG) and Majority- Inverter Graphs (MIG) 74). The antibody design task focuses on optimizing the CDRH3 region of antibodies for binding to specific antigen. RNA inverse folding aims to find RNA sequences that fold into a target secondary structure. Hyperparameter optimization tasks involve tuning the parameters of XGBoost [75] on the MNIST dataset (76) and y-Support Vector Regression (v-SVR) [77] on the UCI
slice dataset
78 for which we do feature selection along with the hyperparameter tuning as in [
Experiments
To illustrate the capacity of our library, we conduct experiments tackling the following questions:
1. Which implemented surrogate model and acquisition optimizer performs best?
2. Does incorporating a TR constraint improve the performance of MCBO?
3. Which implemented Combinatorial and Mixed-variable algorithm is the most robust?
We exploit the high modularity and flexibility of our framework to easily instantiate a total of 48 combinatorial BO algorithms using the BoBuilder class, and compare their performance on six combinatorial tasks, including Ackley-20D, pest control, sequence of operators tuning for AIG and MIG logic synthesis, antibody design, and RNA inverse fold task. We also run five non-BO baselines RS, HC, GA, SA, and MAB on these six combinatorial tasks. Similarly, we use BoBuilder to implement 24 mixed-variabee BO methods and evaluate them four mixed-variable
7

---

Average Ranis four 48)
Oneyo
84
GP (Dxi)
(HFD))
27
LS
GP (TO)
24
HC
GP (O)
(SSK)
22
10C
1.30
100
130
50
370
300
Numaerr of iocrations
Number iterations
Number of iteratioon
Figure 2: Evolution of the average rank of combinatorial BO algorithms across six tasks, aggregated by surrogate model (left), acquisition optimizer (center), and use of a trust-region (right).
tasks, including Ackley-53D, XGBoost hyperparameter tuning. v-SVR tuning with feature selection, and logic synthesis flow optimization for AIGs. We benchmark the mixed-variable BO algorithms against four non-BO baselines, RS, HC, GA, and SA. Each experiment is repeated across fifteen random seeds, resulting in over 4, 000 individual experiments.
5.1 Experimental Procedure
To ensure a fair and consistent comparison, we follow standardized experimental design. For given task and random seed, each BO algorithm suggests the same set of 20 uniformly sampled points and observes the corresponding black-box function values. For the next 180 steps, each algorithm suggests a new point to evaluate based on its surrogate model and acquisition function optimization process. We therefore query the black-box function 200 times per algorithm and per seed. For a given black-box evaluation budget = 1,... 200, we denote by y the best value attained so far, 2f = mini V D As the scales of the black-box values can differ drastically from one task to another, we compare the optimizers' performance across tasks by considering their ranks based on the sts. To analyze the impact of some primitives, We can then aggregate the ranks across tasks, random seeds, and the BO primitives not under investigation. For example, when assessing surrogate models, we average the rank of the optimizers sharing the same surrogate across tasks, random seeds, acquisition functions, and acquisition optimizers. In figures displaying the evolution of ranks, we show the mean rank in solid line, and the standard error with respect to tasks and seeds shaded area. We conduct a Friedman test see we can reject the hypothesis that all the methods" performances are equal, and if it is not the case, we add black vertical lines to connect the algorithms whose mean rank differences are smaller than the length of the critical interval given by the post-hoc Wilcoxon signed-rank test.
5.2 Hardware
We run our experiments on two machines with Tesla V100-SXM2-16GE GPUs and an Intel(R) Xcon(R) CPU E5-2699 v4 @ 2.20GHz with 88 threads, which allowed us to parallelize over tasks and seeds. It took us approximately two weeks to run the set of experiments described this paper.
5.3 Analyzing Combinatorial BO Design Choices
Surrogate model We observe in Fig. 2 (left) that BO methods with LSH or GP (Diff.) surrogate significantly underperform compared those based on GP (HED), GP (O), GP (TO), and GP (SSK). However, from the well rell-performing surrogate models, no single model outperforms the others significantly, indicating that certain models are better suited for specific types of black-box functions as we will investigate in Section 5.4
Acquisition function optimizers Fig. (center) shows that exhaustive LS performs best at very low budgets. But as the number of step increases, GA delivers superior mean performance. This suggests that the high exploitation offered by LS is beneficial when few suggestions are allowed, but the less myopic approach of GA achieves better increases.
trade-off as budget
'Reporting regret is not possible for the real- world tasks whose minima unknown.
8

---

Trust region (TR) Finally, Fig. 2 (right) shows that, on average, methods working with a dynamic TR fit local models and constrain acquisition optimization provide consistently better suggestions compared to global approaches. This confirms and extends the findings of Wan et al. [
5.4 Which is the Most Robust Combinatorial Algorithm?
In this section, consider each mix-and-match combinatorial BO algorithm individually (without ag- gregating ranks by primitives), and
Rondom Soorth
Melte-Amed Bandle
Average Rank (out of of 13)
BECS
compare them non-BO base-
COMBO
lines. We first order all the al- gorithms based on their average ranks across ten seeds and 6 tasks, and show on Fig. 3 the per- formance of the 6 known BO solvers, the 5 non-BO baselines,
BOLL
Hill Ulaubing
Gaustac Aluciiam
Stunlated Anneiing
Casmepolitan
BOLLS
BO6S
and the 2 (out of 42) new mix-and- match methods achieving the low- est rank.
(SSK) GA m/ TR
(TD) TR
Number of iterations
We observe that only the two new MCBO algorithms achieve a sta- tistically significant average rank improvement compared to the GA,
Figure Average rank of known combinatorial algorithms and the two best mix-and-match BO.
and SA black- -bx optimization baselines. These two algorithms utilize a GP (SSK) or GP (TO) surrogate model with GA and trust region constraint for acquisition optimization. Notably, these algorithms are novel and their design choices align with our conclusions from Section [33] However, it is important to highlight that the difference in rank between these algorithms and Casmopolitan (5), BOSS (7]. and BOiLS 4 not statistically significant. This can be attributed to the significant role of model fit (see Section 5.4) in BO and the averaging of results across diverse tasks, where different surrogate models may be optimal.
For each BO optimizer and the three best performing non-BO baselines, we show on Fig. 4 the evolution the best objective values attained. We note that on two tasks (Antibody design and RNA inverse fold), non-BO algorithm (SA and GA respectively) outperforms all BO solvers, highlighting the need for further development of combinatorial BO techniques when it comes to solving real- world tasks. Nevertheless, BO solvers are still the best on majority of tasks, though we observe that no single optimizer achieves the lowest objective value across all tasks. We investigate the variability of BO performance in the next paragraph.
Aucibady design
Arkley-21D 20D
AIG flow tuning
Best elojetive value
1.98
COMBO
BOn:
-120
BOSS
GP (SSK) GA w/ TR
MIG Bow tuning
Post Control
RNA Inverse Folding
GP (TD) - GA TR
15
Canepaliso
objestive
Algotthm
BOCS
18
Simplazed Annealing
130
30
1500
Number of inerations
Number of iberations
Number Inerations
Figure 4: Evolution of best observed value each combinatorial task achieved by the known combinatorial optimizers and the two best mix-and-match BO solvers built with MCBO framework. In all tasks, the aim is to minimize the black-box. Hence, the lower the best observed value the better.

---

Model fit and BO performance As underlined in Section 3.1 the choice of kernel impacts the GP modeling capacity, which could explain the variability of BО performance on the different black-box functions. To assess the relation between kernel choice and BO performance, we measure the Pearson correlation between the quality of a GP model fit, and the quality of the objective value attained after 200 iterations of BO equipped with the same surrogate. We get the quality of GP fit on given task and seed by conditioning the GP on the first 150 points { (æ; yt 1,50 coming from our GA run 1200
and computing the log-lik log-likelihood of the last 50 black-box values {3/: ii=15u under the GP prediction j 1 Fixing the acquisition optimizer and the use of TR, we collect for all tasks and seeds the GP log- ligeliid and the BO performance when using SSK, TO, O, HED and diffusion kernll. Given a task and seed, the set of points coming from the GA run are the same to limit a source of noise in the performance comparison. As expected, Fig. 5 shows positive correlation between BO performance and the capacity of its surrogate model to fit the black-box. The correlation is weaker for local acquisition optimizers (I.S) than more explorative ones (GA).
at {a:
HC acq. opt.
LS acq. opt. Correlation: 0.27
SA acq. opt. Correlation: 0.33
GA acq. opt. Correlation: 0.58
Correlation: 0.49
Regret rank ca
Pearson corr. (per subfig
w/O TR
0.8
us
3
Correlation: 0.50
Correlation: 0.48
Correlation: 0.55
Correlation: 0.70
Regret rank
83 00 2o Gn
W/ TR
sample
2 samples
3 samples
2 3
2 3
2 3
2
Fit rank
Fit rank
Fit rank
Fit rank
Figure 5: Pearson correlation between the quality of surrogate fit, and BO regret, split by acquisition function and use of a TR.
5.5 Mixed-variable optimization
Due to space limitations, we defer the analysis of results obtained on mixed tasks to Appendix D This analysis reveals that new mixed-variable BO algorithm, which combines GP (Matérn-5/2 and HED kernel) surrogate model with a GA acquisition optimizer and a trust region constraint, achieves statistically significant better rank averaged across all the considered tasks.
6
Conclusion
This work introduces a modular and flexible framework for MCBO, addressing the need for systematic benchmarking and standardized evaluation in the field. Leveraging this framework, we implement total of 48 combinatorial and 24 mixed-variable BO algorithms with just single line of code per algorithm. Benchmarking these algorithms in our framework, we conduct over 4000 individual experiments. Through these experiments, we provide insights into the choice of surrogate model based its fit, the selection of acquisition optimizer, and the use of a trust region constraint to constrain acquisition optimization.
set of 10 tasks, which is subset of the tasks available
It is important to note that these experiments represent only fraction of the possibilities frame- work offers. We aim to demonstrate the ease and potential of our MCBO framework, encouraging further analyzes and the development of new primitives. We also invite MCBO developers integrate their novel options into our flexible codebase, enabling easy mixing and matching of algorithms and facilitating benchmarking across various synthetic and real-world tasks with minimal effort.
10

---

References
[1] Ricardo Baptista and Mathhis Poloczek. Bayesian optimization of combinatorial structures. In International Conference Machine Learning, pages 462 471. PMLR, 2018.
[2] Changyong Oh, Jakub Tomezak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URLhttpss http:e///pooceedeeeeeee neurips Paper pdf
[3] Binxin Ru, Ahsan Alvi, Vu Nguyen, Michael Oshorne, and Stephen Roberts. Bayesian optimisation over multiple continuous and categorical inputs. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8276-8285, PMLR, 13-18 Jul 2020. URL htttp:://proceedingg mlr
html
[4] Antoine Grosnit, Cedric Malherbe, Rasul Tutunov, Xingchen Wan, Jun Wang, and Haitham Bou Ammar. BOiLS: Bayesian Optimisation for Logic Synthesis. In Proceedings the 2022 Conference & Exhibition on Design, Automation & Test in Europe, DATE '22, page 1193-1196, Leuven, BEL, Mar 2022. European Design and Automation Association. ISBN 9783981926366
[5] Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A Oshorne. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. International Conference on Machine Learning. 2021.
[6] Aryan Deshwal, Sebastian Ament, Maximilian Balandat, Eytan Bakshy, Janardhan Rao Doppa, and David Eriksson. Bayesian optimization over high high-dimensional combinatorial spaces via dictionary-based embeddings. CORR, abs/2303.01774 2023. doi: 10.485550axXx.22333007744 URL httpt:ttt//:o...ooo org. 10. 48540/ arivv 2303.01777
[7] Henry B. Moss, David S. Leslie, Daniel Beck, Javier Gonzalez, and Paul Rayson. BOSS: Bayesian optimization over string spaces. In NewrlPS, 2020. URL http:::/:///o
Abstract..
html
[8] Gülay Barbarosoglu and Demet Özgür. Hierarchical design of an integrated production and 2-echelon distribution system. European Journal of Operational Research, 11(()):464 484, 1999. ISSN 0377-2217. doi: http:///buurr////000000077721110
URL https
[9] Amr Arisha and Waleed Abo-Hamad. Simulation optimisation methods in supply chain applications: review. Irish Journal of Management, 30:95, 2009.
[10] G. Dantzig and J. H. Ramser. The truck dispatching problem. Management Science, 6:80-91.
10 1959.
[11] Samuel Raff. Routing and scheduling of vehicles and crews: The state of the art. Com- puters & Operations Research, 10(2):63-211, 1983. ISSN 0305-0548. doi: https://doi. org/10.1 (0001000660000505488833900000000
Utt /wwww sciencedirect. com/science Routing and Scheduling of Vehicles and Crews. The
article/pii/ aatticle/pi//80556488390333
State of the Art.
[12] R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.Rinnooy Kan. Optimization and approxi- mation in deterministic sequencing and scheduling: survey. In P.L. Hammer, E.L. Johnson, and B.H. Korte, editors, Discrete Optimization II, volume 5 of Annaly of Discrete Mathematics, pages 287-326. Elsevier, 1979. doi: wcc.h//ctttccccooccc//ao/coooooa https://wwwl www.ssciiieeeeceeeeeeeeeeeeeeeee http:://ww..ccieeeddreee..c
URL
[13] Q-K Pan, L. Wang, and Qian B. novel nulti-objective particle swarm optimization algorithm for no-wait flow shop scheduling problems. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 222(4):511-553) 2008. doi: 10.1243.
09544054JEM989, htLpstts::. h //ooii.//////oo org/ 100 1243 /2542443//44444441111

---

[14] Harry Markowitz. Portfolio selection. The Journal of Finance, 7(1):77-99 -91, 1952. ISSN 00221082, 15406261. URL http://w// jstor. org/ /tt.//tteeee///////////
[15] Fereshteh Vaezi, Seyed Jafar Sadjadi, and Ahmad Makui. portfolio selection model based on the knapsack problem under uncertainty. PLoS One, 14(5)xe011352,, May 2019.
[16] G. B. Mathews. On the Partition of Numbers. Proceedings of the London Mathematical Society, s $1-28(())486-490, 11 1896. ISSN 0024-6115. doi: http://m///l12.....44441 URL
https://doi.oog http:////do...0111..11111 111211.11111pmmmmmm s1../..111111111 1.886.
[17] B. Robinson. On the Hamiltonian game (a traveling- salesman problem). RAND Corporation, Santa Monica, CA, 1949.
[18] Andrew V. Goldberg, Éva Tardos, and Robert E. Tarjan. Network Flow Algorithms. Princeton Univ NJ Dept of Computer Science, 1989.
[19] Laurent Perron and Vincent Furnon. Or-tools, 2022. URL http:t:t////eeellperrsssgg google com/optimization/
[20] IBM ILOG Cplex. V12. User's manual for cplex. International Business Machines Corpora- tion, 46(53):157, 2009.
[21] Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, 2022. URL httph:////w www gurobi com
[22]
Java Binding. Gnu linear programming kit, 2011.
[23] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598) 1983. doi: 10.1 20.112//cieece..22... 459.04499.66.. URI.https://www.. h/tpe:/eee/we/eeneeeeeeeeeeeeeee
erg/doi/aba aatooi/abs/1ie 10. 1et// scicnee...ccc...cco.. 220. 4598.67
[24] V. V.Cemy. Thermodynamical approccc to the traveling salesman problem: An efficient simulation algorithm. J. Optim. Theory Appl., 45(1):11-51, jan 1985. ISSN 0022-3239. doi: 10. 1001/ BF009408 12. UtLtttss:///doi http://6d...rr/11110001///000000 1007/BF009400122
[25] Darrell Whitley. A genetic algorithm tutorial. Statistics and Computing, 4(2):65-85, Jun 1994. ISSN 1573-1375. doi: 10.1007/BF00175355. URL https::/aoi..or///
BF00175354]
[26] A. E. Eiben and James E. Smith. Introduction to Evolutionary Computing. Springer Publishing Company, Incorporated, 2nd edition, 2015. ISBN 3662448734.
[27] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48777, 2002. doi: 10.1137/ $0097539701398377. URL httph: //doi. org/ 10. 10117//000975377715555000
[28] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning, volume MIT Press, 2006. ISBN 978-0-262-18253-9.
[29] Huma Lodhi, Craig Saunders, John Taylor Nello Cristianini, and Chris Watkins. Text classification using string kernels. J. Mach. Learn. Res., 2:419 444, mar 2002. ISSN 1532-4435. doi: 10. 10.116221552444227000000 16322443027602068887
URL htRpsstps::/dat org/10..1110 1162/
[30] Nicola Cancedda, Eric Gaussier, Cyril Goutte, and Jean Michel Renders. Word sequence kernels. J. Mach. Learn. Res., 105910)005--108, mar 2003. ISSN 1532-4435.
[31] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hicrarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Iece, 2009.
[32] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, 2012. doi: 10. 10.1109/R0022002.33661000
12

---

[33] Sonja Surjanovic and Derek Bringham, 2013. URL https://wwyz sfu. ca/"ssur ano/
optimization. html
[34] Jasper Snoek, Hugo Larochelle, and Ryan Adams. Practical bayesian optimization of machine learning algorithms. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012. URL https: http:///pooceeen..///e//// www.eediiinnnnnnns....emm neurips wwwrris..cpppappeeeppeee 55516655a55555ff88666666663
[35] The GPyOpt authors. GPyOpt: A bayesian optimization framework in python. http:// github. www.cooo/eeeeee /tt///hffeeea////FFaa
2016.
[36] Jian Wu and Peter Frazier. The parallel knowledge gradient method for batch bayesian optimization. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL htttpps:/pproceeddnngg wwwpiinngnnneuuuree neurips... cc/ htsppappr__iiie httpsrfffleeppppppeeeeeee http:///////pppe///////ieee (aalaa6666eaddde2266e5333311 Paper pdr
[37] A. Klein, S. Falkner, N. Mansur, and F. Hutter. Robo: A flexible and robust bayesian opti- mization framework in python. In NIPS 2017 Bayesian Optimization Workshop, December 2017.
[38] Andrei Paleyes, Mark Pullin, Maren Mahsereci, Cliff McCollum, Neil Lawrence, and Javier González. Emulation of physical processes with emukit. In Second Workshop on Machine Learning and the Physical Sciences, NeurIPS, 2019.
[39] Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christo- pher R. Collins, Jeff Schneider, Barnabas Poczos, and Eric P. Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. Journal of Machine Learning Research, 21(81): 2020. URL http://rrroorrrrroo/////oo pappps/pprr/// 18-223. htmmmmll html
[40] Willie Neiswanger, Kirthevasan Kandasamy, Barnabas Poezos, Jeff Schneider, and Eric Xing. Probo: Versatile bayesian optimization using any probabilistic programming language, 2019.
[41] Nicolas Knudde, Joachim van der Herten, Tom Dhaene, and Ivo Couckuyt. GPflowOpt: A Bayesian Optimization Library using TensorFlow. arXiv preprint - arXiv:1711.03884 2017.
htt.tttss///axiii.rrrt hbsg///b///// 1711. 07711.00300 03845
[42] Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, Andrew Gordon Wilson, and Eytan Bakshy. BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. In Advances in Neural Information Processing Systems 33, 2020. URL
/etp://arxiv. org/ 1990s/1910..000 06403
[43] Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian Q Weinberger, and Andrew Gordon Wilson. Gpytorch: Blackbox matrix gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, 2018
[44] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-00240000 8035. Curran Associates. Inc., 2019. URL URL httphtt::/ppaprr http://ppapprr..nuipsppppp nwwrins.ii...o cc/paper/ 9015 9015-pytorch an -an--nn-immae an--ipperative style- high www.ppewrooooeeeeeeeeeee dewp-ee-eddde---eeeee--e-e Learning- -ibbaary pdf
[45] Tea Tušar, Dimo Brockhoff, and Nikolaus Hansen. Mixed-integer benchmark problems for single- and bi-objective optimization. In Proceedings of the Genetic and Evolutionary Com- putation Conference, GECCO '19, page 718-726, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 0788450031111 118, attps://dois org/10. 11111111111111 3321868
doi: 10. 10.1145/3321707.385 332133311666 1868. URL.
13

---

[46] Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar. and Dimo Brockhoff. Coco: a platform for comparing continuous optimizers in black- blx setting. Optimization Methods and Software, 36(1):114-144 2021. doi: 10. 1080/00556788.00000000 1at.:2200.....87... URL
https: ptttps:/doo... org. 1000//00.000//100
1080/ 1ww.11000011177888 10556788 2020. 1808977
[47] Katharina Eggensperger, Philipp Müller, Neeratyoy Mallik, Matthias Feurer, Rene Sass, Aaron Klein, Noor Awad, Marius Lindauer, and Frank Hutter. HPOBench: A collection of repro- ducible multi-fidclityy benchmark problems for HPO. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL
[48] Sehastian Pineda- Arango, Hadi S. Jomaa, Martin Wistuha, and Josif Grabocka. HPO-B: A large-scale reproducible benchmark for black-box HPO based on openml. Neural Information Processing Systems (NeurIPS) Track on Datasets and Benchmarks, 2021.
[49] Florian Pfisterer, Lennart Schneider, Julia Moosbauer, Martin Binder, and Bernd Bischl. Yahpo gym an efficient multi-objective multi-fidelit benchmark for hyperparameter optimization. In Isabelle Guyon, Marius Lindauer, Mihacla van der Schaar, Frank Hutter, and Roman Garnett, editors, Proceedings the First International Conference on Automated Machine Learning, volume 188 of Proceedings of Machine Learning Research, pages 3/1-39. PMLR, 25-27 Jul 2022. URL https::///// htttps://proceediiiieee
mlr. prwss/ pwwpss/vi/////eeepeeeeee http:///8/////fteeeeee http://ersseeeaaaaaema html
[50] Andrew Gelman, John B. Carlin, Hal Stern, and Donald B. Rubin. Bayesian Data Analysis. Chapman and Hal//CRC, 2nd ed. edition, 2004.
[51] Leo Breiman. Random forests. Machine Learning, 45(1):5-32, Oct 2001. ISSN 1573-0565. doi: 10. 10.1023/A:10100934444333 URL https://///do wttp://00..000031111000300000330
[52] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Cur- ran Associates, Inc., 201 URL httpss://rooceddinnn www.eewwwnn..iii.nn..... neurips..iccmmm hwt.spss.cppppppppppeeeeeeeeeeee wwtppappe///1/////eeea 86e8f 0668ff/ab2ccdd25777ccc22 /ttp///6622211063666-00-aP .pff
[53] Ethan Goan and Clinton Fookes. Bayesian neural networks: An introduction and survey. In Kerrie L. Mengersen, Pierre Pudlo, and Christian P. Robert, editors, Case Studies in Applied Bayesian Data Science: CIRM Mornet Chair; Fall 2018, pages 45-87. Springer Interna- tional Publishing, Cham, 2020. ISBN 978 3-030-42553-1 1. doi: 10.10077978-3 0-078--3-300-------- 000--330050------0 1_3
URL (RLLhhtt:://doo org
[54] Christopher Williams and Carl Rasmussen. Gaussian processes for regression. In D. Touret- zky, M. C. Mozer, and M. Hasselmo, editors, Advances Neural Information Processing Systems, volume 8. MIT Press, 1995. URL httpss://rocceeddiii www.gg.eerrpp.ccoo [996//1ee/cc33311077777777777722
pdf
[55] Alexander I. Coven-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan Rhys Griffiths, Alexandre Max Maraval, Hao Jianye, Jun Wang, Jan Peters. and Haitham Bou Ammar. An Empirical Study of Assumptions in Bayesian Optimisation. arXiv e-prints, art. arXiv:2012.03826, December 2020.
[56] Risi Imre Kondor and John D. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In Proceedings the Nineleenth International Conference Machine Learning, ICML '02, page 315-322, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. ISBN 1558608737.
[57] Frank Hutter. Automated Configuration of Algorithms for Solving Hard Computational Problems. PhD thesis, Technical University of Darmstadt, 2004.
[58] Kailong Liu, Yi Li, Xiaosong Hu, Mattin Lucu, and Widanalage Dhammika Widanage. Gaussian process regression with automatic relevance determination kernel for calendar aging prediction of lithium-ion batteries. IEFE Transactions on Industrial Informatics, 16(6))376733777 2020. doi: 19.1109912.011.2999111
14

---

[59] Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of Bayesian methods for seeking the extremum. Towards Global Optimization, 1(-12222, 1978.
[60] Donald R.
Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive blx functions, Journal of Global Optimization, (3(4):4554492 Dec 1998. ISSN 1573-2916. doi: 10.1023/A:10003364311144 URL /ttpp:://oi..rrg/11..... 1008306431147/
[61] H. J. Kushner. A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering, 86(1):97-106, 03 1964. ISSN 0021-9223. doi: 10.1115/1.3653121. URL httph:h/ppooot org/ 10. 111.11..111......
[62] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 1015-1022, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077.
[63] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Found. Trends Mach. Learn., 11(1):1-9,, jul 2018. ISSN 1935-8237. doi: 10.1561/2200000070. URL wwwph:ttth/oooo orgg 10112200000000
[64] Antoine Grosnit, Alexander I. Cowen-Rivers, Rasul Tutunov, Ryan-Rhys Griffiths, Jun Wang, and Haitham Bou-Ammar. Are we forgetting about compositional optimisers in bayesian optimisation? Journal of Machine Learning Research, 22(160):1 2021. URL http:
//jmlr. org www.llrrrgppppers///eeee v22/2222//2222 1422. html
[65] Samuel Daulton, Xingchen Wan, David Eriksson, Maximilian Balandat, Michael A. Osborne, and Eytan Bakshy. Bayesian optimization over discrete and mixed spaces via probabilistic reparameterization. In Advances in Neural Information Processing Systems 35, 2022.
[66] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. In H. Wallach, H. Larochelle, A. Beygellimeer, d'Alché-Buc, Buch E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL http::ttt///c httsttss:///proceeeee htto:ceess////ceeinnn// unttga////paarr/00111//0//aeeeep
[67] Carlos M. Carvalho, Nicholas G. Polson, and James G. Scott. The horseshoe estimator for sparse signals. Biometrika, 97(2)4665 2010. ISSN 00063444, 14643510. http/
www..jsstor.rr/sttaaeeeo
[68] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Advances in Neural Informa- tion Processing Systems, pages 5496-5507, 5507, 2019. URL http://paperss nips wwcppppprr.r...eecccccceee.eee/e pdf
8788 ort.lsach...lllaao.oo.o.oaaaaaaa http://aw...tttttooooooooooooaaa
[69] James Bergstra and Yoshua Bengio. Random search for byper- optmmiiztiinrriiiiiiiiiiiioo.... J. Mach. Learn. Res., 13:28 305. 2012. URL /ttpp:/d/// uni tew-trrrrrr. www.ttrrrreddddui http://r/dd//////oaaaaa/////////
jmlr13 htm #Bergstrar122
[70] Y. Crama, A. W. Kolen, and E. J. Pesch. Local search in combinatorial optimization, pages 157-174. Springer Berlin Heidelberg, Berlin, Heidelberg. 1995. ISBN 978-3-540-44228-2. doi: 10. 10.1007/BF60022002, URL/ttps:://dol org/ 10. 1
[71] Alan Mishchenko et al. Abe: A system for sequential synthesis and verification, 2005. URL https://people.eer eecs. berkeley. wwweeelee.edu///// /
[72] Asif Khan, Alexander Cowen-Rivers, Derrick-Goh-Xin Deik, Antoine Grosnit, Kamil Dreczkowski, Philippe A Robert, Victor Greiff, Rasul Tutunov, Dany Bou-Ammar, Jun Wang, al. Antbo: Towards real- cal-world automated antibody design with combinatorial bayesian optimisation. arXiv preprint 27115:2201.12550, 2022.
15

---

[73] Nono S. C. Merleau and Matteo Smerlak. A simple evolutionary algorithm guided by local mutations for an efficient ma design. In Proceedings of the Genetic and Evolutionary Com- putation Conference, GECCO '21, page 1027-1034, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383509, doi: 10.1145/3449699.3445 34552290. URL.
1111/11444444 3459280
[74] Luca Amarú,
Gaillardon, and Giovanni De Micheli. Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization. In 2014 51st ACM/EDAC/IEEE Design Automation Conference (DAC), pages 1-6, 2014. 10.1 (..114//593669.25999
doi:
[75] Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 16. pages 785-794, New York, NY, USA. 2016. ACM. ISBN 978-1-4503- 145033-4232-2. doi: 141144/9939977.29997555 URL http://doi acm. org/ 10. 1145/1999666. 2939778
[76] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142 2012.
[77] C. Chang and C. J. Lin. Training nu-support vector regression: theory and algorithms. Neural Comput, 1 198))1959-197,, Aug 2002.
[78]
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htttht/tp//cchive ics. uci. edu/ml ml
[79]
Javier Gonzalez, Zhenwen Dai, Philipp Hennig, and Neil Lawrence. Batch bayesian optimization via local penalization. In Arthur Gretton and Christian C. Robert, editors. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 648 657, Cadiz, Spain, 09-11 1 May 2016. PMLR. URL https::/prooceddings .mr.rrsss...r.....m...m.....mme. mlr peress/v51/gonzaleeeee
html
[80] Alexander G. de Matthews, Mark van der Wilk, Tom Nickson, Keisuke. Fujii, Alexis Boukouvalas, Pablo León-Ville Villagrá, Zoubin Ghahramani, and James Hensman. GPflow: A Gaussian process library using TensorFlow. Journal of Machine Learning Research, 18(40):
1-6, apr 2017. URL http://jmlr .rg. https/paapps///////eeee
.ttml
[81] Luca Amarú,
Gaillardon, and Giovanni De Micheli. Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization. In 2014 51st ACM/EDAC/IEEE Design Automation Conference (DAC), pages 1-6, 2014. doi: 0,.144/25593099255933
[82] Mathias Socken, Heinz Riener, Winston Haaswijk, Eleonora Testa, Bruno Schmitt, Giulia Meuli, Fereshte Mozafari, and Giovanni De Micheli. The EPFL logic synthesis libraries, November 2019. arXiv: 1eXXvv118050 105.05122v2..
[83] Luca Amaru, Fierre-Emmanue Gaillardon, Eleonora Testa, and Giovanni De Micheli. The epfl combinational benchmark suite, February 2019. URL, /tttts::///i..ooo org/1/00...../0.... 5281/zenodo
2572934
[84] Philippe A Robert, Rahmad Akbar, Robert Frank, Milena Pavlović, Michael Widrich, Igor Snapkov, Maria Chemigovskaya, Lonneke Scheffer, Andrei Slabodkin, Brij Bhushan Mchta, al. One billion synthetic Sd-antibody-antige complexes enable unconstrained machine- learning formalized investigation of antibody specificity prediction. BioRXiV, 2021.
[85] Matthew IJ Raybould, Claire Marks, Konrad Krawezyk, Bruck Taddese, Jaroslaw Nowak, Alan P Lewis, Alexander Bujotzek, Jiye Shi, and Charlotte M Deane. Five computational developability guidelines for therapeutic antibody profiling. Proceedings of the National Academy of Sciences, 1125100:025-44000 2019.
[86] Michael S Goldberg, Deyin Xing, Yin Ren, Sandra Orsulic, Sangeeta N Bhatia, and Phillip Sharp. Nanoparticle-meditte delivery of siRNA targeting parpl extends survival of mice bearing tumors derived from breal -deficient ovarian cancer cells. Proc Natl Acad Sci A, 108(2):745-75, December 2010.
16

---

[87] Douglas H. Turner and David H. Mathews. Nndb: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic acids research, 38(Databsee (022)):2280-D222, Jan 2010. ISSN 1362-4962. mih.
doi: 10. 10.1093/nar/gkp892 URL https
//pubmed. ncbi wtw..hhov19880081111111 198883811
[88] Chenhui Hao, Xiang Li, Cheng Tian, Wen Jiang, Guansong Wang, and Chengde Mao. Con- struction of ma nanocages by re-engineering the packaging of phi29 bacteriophage. Na- ture Communications, 5(1):3890, May 2014. doi: 10.1038//comms4800. URL https
//doi.org/10 1038 ncwmmm48cmmm
[89] Ronny Lorenz, Stephan H. Bernhart, Christian Höner Siederdissen, Hakim Tafer, Christoph Flamm, Peter F. Stadler, and Ivo L. Hofacker. Viennarna package 2.0. Algorithms for Molecular Biology, 6( 2626 Nov 2011. ISSN 1748-7188 1888.
doi: 10.1
URL https
//doi. 111.11111///11188-11111 7188-6-26
[90] Peter Eastman, Jade Shi, Bharath Ramsundar, and Vijay S. Pande. Puzzles in the Eterna100 benchmark., 6 2018. WtLpsttp::///llo figshare... cctp://arr.ccle//aatttte///eeeee in the Eterna100 benchmark /6638837
[91] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 22330, 2011.
[92] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference Learning Representations, 12 2014.
[93] David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro. Kriging Is Well-Suited to Parallelize Optimization, pages 131-162. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. ISBN 378-3-642-107011 doi: 000077777-3-64-- 10701-6 htthsttss:// /tmpps://do0 //doi. org/10 10
17

---

Appendix A Lexicon
In Table A
we include full list of the abbreviations used in this paper, alongside their definitions.
Table I: A full list of the abbreviations used in this paper alongside their definitions
Abbreviation
Definition
AIG
And-Inverter Graphs
API
Application Programming Interface
ARD
Automatic Relevance Determining
BO
Bayesian Optimization
Diff.
Diffusion kernel
EA
Evolutionary Algorithm
EI
Expected Improvement
GA
Genetic Algorithm
GP
Gaussian Process
HC
Hill Climbing
HED
Hamming embedding via dictionary kernel
IS
Interleaved Search
LCB
Lower Confidence Bound
LHS
Linear Regression with the Horseshoe Prior
Exhaustive Local Search
MAB
Multi-Armed-Bandde
MCBO
Mixed-variable and Combinatorial Bayesian Optimisation
MIG
Majority- Inverter Graphs
ML
Machine Learning
O
Overlap Kernel
PI
Probability of Improvement
RNA
Ribonucleic Acid
RS
Random Search
SA
Simulated Annealing
SFU
Simon Fraser University
SSK
String Subsequence Kernel
TO
Transformed Overlap
TR
Trust Region
TS
Thompson sampling
D-SVR
y-Support Vector Regression
Appendix B Bayesian Optimization
B.1 Inference with Gaussian Processes
Given dataset D = {wr, Vi In and assuming Gaussian-corrupter observations yı f(x;; ei where & ~ [0, o²), the joint probability distribution over the observed data and an arbitrary test input Brest can be written as:
No (0.
Kg + I2 k (Iress)
ki (Deest alwa)) 1):
1:m ((
(4)
Here, assume zero GP prior and use Yim to represent the vector of all outputs, i.e. Nim- [y1,.... ................................ Vr.] The block-covariance matrix in the equation above is defined as:
Kg = Kø( Iim)) E R"*", such that [K( x1m Ma.e = ke (0 xt)
(kk,))
ko (Dres) ko(#i.n: Trea) R such that [kø (# (res)) )e ko (m), Breat) Vk.
By conditioning the joint distribution, we can derive the posterior distribution for predicting ff (awes)
28 resulting in (2 pastt D, N (ur (mess), og (arees)), where:
no (Dess) = k (Ziees) Kg + 0²I) -1 "y...
o (Ieest) = ke (Erest Frest) K. (Frest (Ko + 0²I) -1)--kp(aa (F(eat))
18

---

The optimal kernel hyperparameters 0 can be learned by minimizing the negative log-likelihood
28
B.2 Learning Optimal Kernel Hyperparameters
To infer the optimal kernel hyperparameters 0* given D, we can minimize the negative log marginal likelihood (28), leading to the following optimization problem:
min = =z (Kg + o + 2 2 (Ko + o01) ym mm + cnst.
1
(5)
Since the problem in the equation above is non-convex with respect to 0, typical solvers employ off-the-shelf packages that often utilize random restarts to escape local minima 42
43 79 80]
B.3 Acquisition Functions
We now provide additional information about the Probability of Improvement (PI) [61], the Lower Confidence Bound (LCB) [62] and Thompson Sampling (TS) acquisition functions, assuming that the aim is to minimize the black-box function value.
Probability of Improvement: The PI acquisition function is closely related to El in that it also measures the utility of new query points with respect to the best black-box function value observed so far, y" Contrary EI, however, (PP) (x)) judges the probability of acquiring new gains compared to y" using the following definition:
a (P) o- < v"]]
where II is the indicator function that evaluates to f(x) < y² and to zero otherwise. Intuitively, the PI acquisition function estimates the probability of the black-box function value being lower than the lowest -lck-box function value observed so far.
Lower Confidence Bounds (LCB): Compared to the El [59 60 and the PI acquisition function, the LCB (62) trades-off the mean and the variance the posterior distribution through an additional tuneable hyperparameter 3 E R+:
(LCB) (x)
Pog (x) v VB0g- (x))
When minimizing black-box function LCB estimates the potential minimum value at given query location æ. Conversely, when maximizing the black-box, the Upper Confidence Bound (UCB) 622 should be used instead of the LCB, which is defined as;
(CCB) ( 1t. (x:) + VB0o (æ))
Thompson Sampling (TS): The TS 633 acquisition function balances the exploration-exploiiaaio trade-off by sampling function values from the posterior distribution of the black-box function and selecting the next query point based on the sampled values. In each iteration, TS samples potential query points x from the state space, estimates their mean black-box function values (see Appendix B.I.. and selects the query point associated with the best-performing estimated mean value. In our proposed framework, the TS acquisition function is currently only utilized by BO methods relying on the Linear Regression surrogate model I
Appendix C Available Benchmarks
To enable the wider adoption and systematic evaluation of MCBO methods, our proposed framework addresses the need for standardized development and benchmarking methodologies. Building on API for defining optimization problems, we provide a broad suite of real-world and synthetic benchmarks in our open-source software. These benchmarks consist of a diverse spectrum of optimization problems and their associated domains, covering a wide range of dimensionalities and difficulties. We provide the full list of the implemented tasks along with their domains in Table 2
19

---

Table 2: Tasks implemented in the MCBO framework and the optimization domains they support. In this table, we assume that a = [c, i, h] is partitioned into continuous variables c, integer-valued variables i and categorical variables h. min, and max, specify arbitrary bounds for continuous variables. {min, max;) defines a set containing all integers between min; and max;, Ne. N; and N₂, specify the number of continuous- valued, integer- and combinatorial variables respectively. MN, specifies the number of categories the 7th combinatorial variable can take. Objective f
Inputs
Arbitrary combination of input types and dimensionalities
c e [ming; max.] No
SFU Test Functions
i (min,, max; J.:
h E {hi,..., h., } X {hNN.. ...., NM.,,,,,,
11 categories per variable
Ackley-20D (included in SFU)
h E (-32.763 -
20..214,3..788-2
c [-
Ackley-53D (included in SFU)
h {0, 1].00
Pesticide choice at each stage (or pesticide)
Pest Control
h = {No pesticide, Pest. 1, Pest. 2, Pest. 3, Pest. 4)
E frewrite, rewrite -z, refactor, refactor -z, resub, balance, &blut, &sopb, &dsdb, fraig) 20
AIG Flow Tuning
h (balance, cut rewrite,
rewrite -7, refactor,
MIG Flow Tuning
refactor -z, resubstitute, functional functional_eeduucioon]]]
Let AA be the set of all 20 naturally occurring amino acids AA
Antibody Design
RNA Inverse Folding
E (A.C.G,UJN.
Sequence:
h E frewrite, rewrite -z, refactor, refactor -z, resub, balance, &blut, &sopb, &dsdb, fraig]
AIG Flow. and Hyp. Tuning
Hyperparameters of the operators:
14 Boolean Variables and 22 integer variables
c is learning rate, C2 is min split loss, es is subsample,
C4 is reg lambda, is max depth, hı is booster,
h2 is grow policy and h3 is objective.
c E [10-5,1]
C2 E [0, 10]
XGBoost - MNIST
E [0.001, 1]
4 E [0, 5]
É 10}
h1 E [gbtree, dart}
h2 [depthwise, lossguide)
ha (multisoftmaxx, multissftproob)
Ci i8 6, C2 is C, C3 is and h concerns features
6 [0.01,
V-SVR- Slice
02 E 100]
03 E [0]
(exclude, include]
Synthetic Tasks Our suite of synthetic benchmarks provides controlled setting for evaluating the performance of MCBO methods, where the true optima are often known, and objective function evaluations are inexpensive, enabling rigorous and scalable benchmarking. The benchmarks include the 21 Simon Fraser University (SFU) test functions described by [33]. which are generalized to d-dimensional domains. These functions cover a range of optimization difficulties such as steep ridges, many local minima, valley-shape functions, and bowl-shaped functions. To increase their versatility, we have extended these functions to handle continuous, discrete, nominal, and ordinal variables, well combinations of these variable types. As part of the implementation of the SFU
20

---

test functions, we also include the Ackley -53D [5 6 task, which is special case of the Ackley function.
In addition, we include the pest control task used in 2 pesticides in chain of 25 stations minimize the number of products with pests while minimizing expenses on pesticide control. This task involves selecting from four different pesticides at each station, with varying prices and effectiivnness, and has complex dynamics due to interactions between pesticides and pests. The pest control task provides a challenging optimization problem with high- order interactions.
which involves optimizing the use of
Real- World Tasks To evaluate the effectiveness of MCBO methods on real-world problems with practical objectives and constraints, our benchmark suite also includes a diverse set of real-world tasks spanning four domains: logic synthesis optimization, antibody design, RNA inverse folding, and hyperparameter tuning of ML models. We have selected these tasks for their relevance to different application domains and their challenging optimization landscapes.
Logic Synthesis: In the logic synthesis domain, we support benchmarks that involve optimizing the gate-level representation of Boolean circuits using a sequence of transformative operations. We consider two standard directed graph representations of Boolean circuits: the And-Inverter Graph (AIG) 7 and the Majority-Inverter Graph (MIG) [8]. We have a separate benchmark for each representation. Furthermore, we include an implementation of the AIG optimization benchmark that optimizes both the sequence of transformative operations and the hyperparameters of the underlying transformative algorithms. The AIG sequence and AIG sequence and hyperparameter optimization benchmark implementations rely on the ABC (71) codebase for applying transformative operations to the AIG representation, while the MIG sequence optimization benchmark relies on Mockturtle [82] library. All three logic synthesis benchmarks can be used to optimize any Boolean circuits, and notably the 20 Boolean functions from the open- EPFL Combinational Benchmark Suite that we use in our experiments.
In the antibody design benchmark, we aim optimize the CDRH3 sequence of an antibody for binding to a specific antigen. To achieve this, we use the Absolut! (84] software as an in silico framework for approximating the binding energy between an antibody and an antigen. Furthermore, we follow the recommendations of Khan et al. [72) for the developability constraint and check whether CDRH3 sequence has no more than five consecutive amino acids that are identical, whether its net charge is in the interval [- 2), and whether it is free of undesirable glycosylation motifs 85). Our antibody design benchmark suite includes a diverse set of 159 antigen-CDRHH CDRH3 binding tasks, where each task corresponds to a different antigen.
Antibody Design:
RNA Inverse Folding: In the RNA Inverse Folding task, the goal is find one more RNA sequences that fold into a target secondary structure. This task is of utmost importance to the RNA design process as it enables the design of novel RNA molecules with specific functions, such as catalysis and regulation [86.88). As done in (73., we also on the ViennaRNA folding package [89 model RNA inverse folding. However, as the ViennaRNA package does not deal with pscudoknots that can naturally occur in RNA structures, we further constrain the secondary structure by ensuring that it cannot have two base pairs (i.j) and (k: l) with i < k < j < l. In our benchmarking suite, we rely on the EteRNA100 100 dataset (90 to facilitate benchmarking on a collection of one hundred RNA secondary structures.
Hyperparameter Optimization of Machine Learning Models: Hyperparameters are critical tun- ing parameters that can greatly affect the performance of machine learning (ML) models. Optimizing these hyperparameters can improve the model's accuracy and robustness. In this work, we implement two tasks for hyperparameter optimization: one for the XGBoost [75] model on the MNIST [76] dataset (or any other dataset accessible through the Scikit-Learn [91] APD, and the other for the v-Support Vector Regression (v-SVR) (77) model on the UCI slice dataset (78)
The search space of the XGBoost task comprises three categorical and five numerical variables. The categorical variables include the choice of the booster type, the grow policy, and the training objective. The numerical variables include the learning rate, max tree depth, minimum split loss, amount of regularization and the sub-sample magnitude.
For the =-SRR task, we use the Scikit-Learn [9]] implementation of the D-SVR model. Similar to (6), we make the search space to include 3 continuous hyperparameters of the SVR, C, e, and 7,
21

---

Averne Bank of
Juan, 8/2-0)
MAB-CD
Juat 8/2- TO)
GA
GP Jeon 5/2- HEED)
N
IIC-D
12
O
-
m/ TB
Number
Number of Berations
Number Itorations
Figure 6: Evolution of the average rank of Mixed-variable BO algorithms across four tasks, aggregated by the surrogate model (left), acquisition optimizer (centre), and use a trust region (right).
as well as 50 Boolean parameters corresponding to feature selection. Originally, the slice dataset comprises 384 features, but reduce this number to 50 by fitting an XGBoost model and by keeping the 50 most important features according to the model. Then the 50 Boolean variables of the search space corresponds the inclusion exclusion of each of the retained features for the fit of D-SVR model. The task consist in determine which features and values the hyperparameters allow the minimization the RMSE obtained by the corresponding y-SVR model on held-out test set.
Appendix D Benchmarking Implemented Mixed- Variable Algorithms
D.1 Analyzing Mixed-variable BO Design Choices
Surrogate model We observe Fig. 6 (left) that BO methods using the GP (mat. HED) surrogate have statistically significant lower rank compared to methods that use the GP (mat. 5/2 O) and GP (mat. 5/2 - TO) surrogate. We hypothesize that this is because the HED kernel was better suited to modelling the interactions between the combinatorial variables for the four considered black-box functions.
Acquisition function optimizers Fig. 0 (centre) reveals that the MAB-GD acquisition optimizer significantly underperformed on average compared to the remaining acquisition optimizers. It also shows that the HC-GD and SA acquisition optimizers are best suited for scenarios with low budgets, while there is no statistically significant difference between their performance and that of the GA acquisition optimizer at high budgets.
Trust region (TR) Finally, Fig. 6 (right) encourages the the of TR in mixed-variable BO, as methods working with a dynamic TR to fit local models and constraining acquisition optimization provide consistently better suggestions compared global approaches. This confirms and extends the findings of Wan et al. [5] and is consistent with our results presented in section 5.3
D.2 Which is the Most Robust Varial- Algorithm
We now consider each mix-and match mixed-variable BO algo- rithm individually (without ag- gregating ranks by primitives) and compare them to non-BO
Bandon Soarch
Average Rank (out 9)
Genstic Abuithus
CoCado
Suntited Ansellax
baselines. We first order all the algorithms based on their aver- age ranks across fifteen seeds and four tasks, and we show on Fig. 7 the performance of the three known BO solvers, the four non-BO baselines and the 2 (out of 21) new mix--nd-matee meth- ods achieving the lowest rank.
Cludiix
ROTX
Compriiton
5/2 HED)- GA TR
Number Herrations
Figure 7: Average rank of known mixed-variable algorithms and the two best mix-and-match BO algorithms.
We observe that the new mixed- variable algorithm, GP (mat 5/2 HED) GA w/ TR, achieves a statistically significant average
22

---

rank improvement compared to the considered known mixed-variablee BO algorithms and non-BO baselines. Notably. this algorithm is novel, and its design is aligned with our conclusions from Appendix D.1
For each BO optimizer and the three best non-BO baselines, show Fig- the evolution of the best objective values attained. We note that on three of the considered tasks (Ackley-53D, AIG Flow. and Hyp. Tuning and XGBoost MNIST), a BO algorithm outperformed the considered non-BO solvers. However, on the final task, v-SVR Slice, the HC and SA non-BO baselines attained comparable performance
the best-pes pest-peforning BO solvers, highlighting the need for further development of teixed-variable BO techniques when it comes to solving real-world tasks. Nevertheless, BO solvers are still the best on most tasks, though we observe that single optimizer achieves the lowest objective value across all tasks.
Appendix E Notes on Compatibility of Implemented MCBO Primitives
The MCBO framework includes three core BO primitives: surrogate models, acquisition functions, and acquisition optimizers. Below we discuss some the limitations on the mix-and-match com- patibilities of the currently implemented MCBO primitives and their compatibility with various optimization domains.
E.1 Surrogate Models
Our implementation features the following pre-implemented surrogate models:
GP with SSK
GP with overlap kernel (0) 3
GP with wunsformed-overlap kernel (TO)
S
GP with diffusion kernel (Diff.) 2
GP with dictionary- kernel (HED) 6
GP with mixture kernel [
Linear Regression (50 with the Horseshoe prior 67 using maximum likelihood, maximum
a posteriori, and Bayes estimation (LHS)
Below we provide some additional details about the compatibility of each these models.
GP (SSK) is only applicable to combinatorial problems where each of the categorical variables shares the same possible categories.
GP (O) is only applicable to combinatorial problems.
GP (TO) is only applicable to combinatorial problems.
GP (Diff.) only applicable to combinatorial problems. Also, as the GP (Diff.) model as proposed by Oh et al. (2) is really ensemble of 10 models, any acquisition function the user wishes to class, which
combine with this model must be used initialize the AingleeDb can be subsequently mixed-and and-matched with the model.
A3D
AIG Hyp. Tining
PSVR
XGBoost MNIST
Ben jojtttive valtr.
1.97
D.00
222
B022
1.30
241.
30
110
150
500
150
40
Number of detaaionn
Number of ilecatione
Numdor of Berraioons
Namber of ilerationn
- BODS
C&CdBO
Coomspdilon
Hill Clizabnng
GP (mai, 5/2 HED) GA TT
GP (mull, 5/2 0) GA w/ TR
Genetie Algarthm
Stnmlated Anmailing
Figure 8: Evolution of the best observed value on each mixed-variable task achieved by the known mixed-variable optimizers and the two best mix-and-match BO solvers built with MCBO framework. In all tasks, the aim is to minimize the black-box. Hence, the lower the best observed value the better.
23

---

GP (HED) is only applicable to combinatorial problems.
GP (mixture kernel) is compatible with mixed-variable problems. The mixture kernel currently supports the use of the RBF or Mat. 5/2 kernel for numeric variables, and the use the O, TO or HED kernel for categorical variables, resulting in six different potential GP (mixture kernel) models.
LR (HS) is only applicable to combinatorial problems.
E.2
Acquisition Functions
Our implementation features the following pre-implemented acquisition functions:
Expected Improvement (EI) [59
60
Probability of Improvement (PI
Lower Confidence Bound (LCB) 62
Thompson Sampling (TS) 63
The EI, PI and LCB acquisition functions support surrogate models except for the LR (HS) surrogate model. The reason for this is that the LR (HS) does not maintain analytical estimate of the posterior but instead uses Gibbs sampling M to sample from it, making impossible to calculate EI, PI and LCB in closed form. In contrast, the TS acquisition function only supports the LR (HS) surrogate model.
E.3
Acquisition Optimizers
Our implementation features the following pre-implemented acquisition optimizers:
Exhaustive Local Search (LS) (2)
Genetic Algorithm (GA) 7
Simulated Annealing (SA) I
Interleaved Search (Hill Climbing Gradient Descent) (IS (HC GD)
Interleaved Search (Multi-Armed Bandit + Gradient Descent) (IS (MAB + GD) 3
Below we provide some additional details about the compatibility of each of these optimizers.
LS only applicable combinatorial problems.
GA compatible with combinatorial and mixed-variable problems.
SA is compatible with combinatorial and
problems.
IS (HC GD) is compatible with combinatorial and mixed-variable problems. For combinatorial problems, this acquisition optimizer will simply perform hill climbing, while for purely numeric problems, it will perform gradient descent.
IS (MAB GD) is compatible with combinatorial and vaxid-variable problems. For combinatorial problems, this acquisition optimizer will simply use MAB to optimize the combinatorial variables, while for purely numeric problems, it will perform gradient descent.
We also note that we have generalized the implementation of these acquisition optimizers so that all of them support TR-constrained acquisition optimization, extending [5] 68), and make them handle simple input domain constraints via rejection sampling and projections.
E.4 Implemented Mix-and-Matte Optimizers
Given the compatibilitics outlined above, in the MCBO framework, for combinatorial formulations, we support 48 different mix-and matdh BO optimizers. This results from combining the six different surrogate models suitable for combinatorial formulations (GP (SSK), GP (O), GP (TO), GP (Diff.), GP (HED) and LR), with the four compatible acquisition optimizers (LS, GA, SA and HC) both with and without trust region constraint.
Similarly, for dixeedvariabll formulations, we can instantiate 24 different mix-and-match BO optimizers. This results from combining three compatible surrogate models (GP (Mat. 5/2 O), GP (Mat. 5/2 TO) and GP (Mat. 5/2 HED)) with the four compatible acquisition optimizers (GA, SA. IS (HC + GD) and IS (MAB GD)), both with and without trust region constraint.
24

---

We note that 7 of these optimizers are known combinatorial and BO algorithms. After accounting for the fact that some mix aar--nd--aate combinatorial optimizers are special cases of the known BO algorithms, this results in total of 47 novel mix-and-match BO algorithms.
Appendix Experimental setup
Hyperparameters
We share in Table 3 comprehensive list of the hyperparameters used during training and inference in all experiments. More details can be found in the associated code repository.
Table 3: List MCBO primitives hyperparameters.
Surrogate model
GP mixed-kernel form
M(ea + Kmmm) + (1 A)(Kan Kmmm)
GP Kernel for numeric variables
Matértn-5/2
GP noise level lower bound
10-5
GP fit negative log-likelihood optimizer Diffusion GP characteristics [2
Adam(Ir (Ir = 0.03) [92 for 100 epochs
n. models 10, n burn init 100
Bayesian linear regression SH estimator
Order = 2, Threshold = 0.1, a= 2, b= gigbb = 10-3
Acquisition function optimizer
LS GA
n r_randdm_ertticen wew.eeericcc=20000,... _ aal.aasccettteeeeee init=20, sprayy=1
num iter= n_ 1__rstarts=3, init, init_temp=l, tolerance=
ga_num ja_num_iae num_iter=500, ga_pop_size=-000,
eat_ga_nmn Baci_num__pa caauu__aretts-20,.. cat_ga_nunn _0n__eitte=000
IS (HC + GD)
n. ittr=1000 n_ n_restarts=3, max_n, n _aax____etturbb... 20 num=20,
num optimizer=Adam, num soum_mr-le-,,- nom nom_tol==000 tol=100 max n iter=200, mab resample tol=500, cand=5000, restarts=5, num optimizer=SGD, cont Ir=3e-3, cont iter=100
IS (MAB GD)
Trust region Manager
tr_ "r_rstart_acq _acq__ame restart cand tr awi___nnn_radiiieeee
LCB min(100 (100 num dims, 5000) 2-5
max num radius
tr_ jiiitiniuunn ahnit_nm___t _aiiinmmmmruuussss radius
0.8x max num _an_nadius radius
tr_ ww_mminnnnnoe sop__nominal____ radius max nominal radius
nominal r0und max nominal radius) 1.S
init nominal radius radius multiplier suce_ tol fail tol
3
40
Appendix G
Implementation Details and Additional Features
G.1 Input and Output Normalization
For stable learning with GPs, we normalize all inputs to the range [0, 1] and standardize all black-box function values using the mean and standard deviation of all previously observed values. We apply this standardization independently during every iteration of BO, prior to fitting model.
G.2 Input Constraints
The MCBO framework supports cheap-to Seeap-to-comppe to-coputt constraints on the search space via rejection sampling. When defining an optimization problem via the TaskBase class, one can additionally define list of functions which can each take a sample as input and returns whether the sample valid or not. Then, we pass this list of functions an argument when constructing BO algorithm with the BoBui lder class, as we do for the Antibody design task to restrict the search space to feasible antibody sequences.
25

---

G.3 crust-Region-Basee Acquisition Optimization
All implemented acquisition optimizers support trus-region-coomee constrained acquisition optimization. Following [5], the trust region centred around the best input found so far in the current trust region, TT, is defined as
TR(x TK {a E & s.t. de(x: xte) S Le and d2,, (ax TR x..) S 1):
where 2 and are vectors containing all the combinatorial inputs in TR and æ respectively, d. (:: the Hamming distance, and Le is the size the TR for combinatorial variables. Similarly, an and are vectors containing all the numeric and discrete variables in x: and æ respectively, dr.,, (::-) the maximum of the component-wis. distance for numeric and discrete variables normalized by dimensional length scales L, E R didm(a..) i.e.
TR
[1] [+]l
dLn (1 Fn.
max aEdim((en.
[n
The radius of the combinatorial trust region, Les and the radii for the numeric variables, Lus adjusted dynamically during optimization. They are expanded on successive successes (i.e. when the best function value observed improves) and shrunk otherwise. They also have a predetermined maximum and minimum value. If any of the radii were to be expanded past their maximum allowable value, they would be capped at this value instead. However, if any of the radii were be shrunk smaller than their minimum value, this would trigger a trust region restart.
During a trust region restart, all the radii are set to their initial value, and global auxiliary surrogate model is used determine centre of new trust region. Suppose an algorithm restarts its trust region the 7th time. First, the global surrogate model is fitted to a subset of data D' {ar} y TR J==1
where 2 is the local maxima found after the jih restart, and y IR is its corresponding black-box function value. This auxiliary surrogate model is then used to define an acquisition function, which is then subsequently optimized to suggest new trust region centre.
G.4 Batch sampling
All currently implemented acquisition function optimizers support batch sampling using the Kriging Believer strategy [93] to select b points sequentially. To sample the 7hh point, the Kriging Believer strategy replaces the black-box function evaluation for the (i - 1)th point with the GP prediction, hal- lucinating what the black-box function value could have been, and retrains the GP on the aggregated dataset, before optimizing the acquisition function obtain the 7th suggestion.
26


Reviews:
[{"review_id": "zqWtIIw8hb", "reviewer": "Reviewer_m29E", "summary": "", "questions": "", "limitations": "The appendix includes a discussion of the hardware used and the compute time required to obtain the presented results. This information should be moved to the main paper as it sheds light on what would be required to reproduce the results reported in the paper (likely weeks of computation). It would also be helpful to break this down in terms of the run time required for the experiment needed to benchmark a single new method as this is the most likely use case for a user of this framework.", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "The decomposition of existing MCBO methods into their three constituent parts and the implementation of multiple variants of each part is a valuable contribution in terms of the structure of an MCBO software library. The implementation of multiple tasks for use in benchmarking is also a useful contribution. In terms of the benchmark results, the authors report some novel findings regarding the performance of new mix-and-match model variants as well as non-BO methods.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "HBgJ3t9BYw", "reviewer": "Reviewer_MaRf", "summary": "", "questions": "", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. Significance and relevance. \n\nThis paper makes significant and fundamental contributions to the field in benchmarking and evaluating BO algorithms. I appreciate the efforts in unifying BO algorithms, building easily accessible tookits for future use, providing various datasets and environments for application, and evaluating the performance of various BO algorithms. I believe the provided tools will greatly help the development of BO algorithms in the field. \n\n2. Quality of research.\n\nThis paper is of a high quality and contains fruitful results. The tools are well built; the datasets and environments are comprehensive; the experiments are fruitful. It is also well-written and easy to follow. ", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "HuQjYrDeyW", "reviewer": "Reviewer_Vgsh", "summary": "", "questions": "", "limitations": "As the authors propose a framework for implementing and benchmarking combinatorial and mixed-variable BO algorithms, direct societal impact is difficult to discuss.", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "Combinatorial and especially mixed-variable BO is timely research and especially in the context of black box functions, these kinds of problems appear to gain increased interest.\nRelevance and significance is given.\nThe framework itself appears to be well designed and user friendly.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "VoHVCnKt5k", "reviewer": "Reviewer_fKag", "summary": "", "questions": "", "limitations": "-", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "The paper is written very well and accessible and the provided code is written very well too (I evaluated only samples though). The representation of existing MCBO algorithms according to their primitives and the resulting matrix of yet unseen algorithms (Fig. 1) is very nice. Equally enlightening is Figure 2, about the performance of the individual MCBO primitives.\n\nAs stated in the paper, the presented framework can help in evaluating individual yet to be developed primitives in a standardized way. Also the extension to non MCBO algorithms to broaden the comparison is very helpful for this endeavor.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "2bfd8slPce", "reviewer": "Reviewer_X2sz", "summary": "", "questions": "", "limitations": "These issues are not discussed in the paper or the appendices. Other than what is mentioned in the previous section of this review, the breadth of coverage of the datasets and the process, if any, for enhancing the datasets with additional problem data should be addressed. In particular, a researcher may wish to use the Python script to evaluate different MCBO algorithms for their own dataset/problem.", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "Having a centralized repository of benchmark datasets will facilitate evaluation of new Bayesian optimizers and comparison with existing techniques. This reviewer is not aware of any similar public dataset.\n\nThe Python code for easily generating a new optimizer or to quickly implement existing optimizer also makes it much easier for researchers to compare other techniques. For a given problem, it may be possible to select a dataset that best matches the application, allowing an evaluation of different optimization techniques to see which performs best for this problem.\n\nThe research solution appears to be of high quality and the paper is well-written.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: Good paper to accept.
Decision: Accept (Poster)