Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization
Authors: Sam Daulton
Xingchen Wan
David Eriksson
Maximilian Balandat
Michael A Osborne
Eytan Bakshy
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian Optimization

Abstract: Optimizing expensive-to-evaluate black-box functions of discrete (and potentially continuous) design parameters is a ubiquitous problem in scientific and engineering applications. Bayesian optimization (BO) is a popular, sample-efficient method that leverages a probabilistic surrogate model and  an acquisition function (AF) to select promising designs to evaluate. However, maximizing the AF over mixed or high-cardinality discrete search spaces is challenging standard gradient-based methods cannot be used directly or evaluating the AF at every point in the search space would be computationally prohibitive. To address this issue, we propose using probabilistic reparameterization (PR). Instead of directly optimizing the AF over the search space containing discrete parameters, we instead maximize the expectation of the AF over a probability distribution defined by continuous parameters. We prove that under suitable reparameterizations, the BO policy that maximizes the probabilistic objective is the same as that which maximizes the AF, and therefore, PR enjoys the same regret bounds as the original BO policy using the underlying AF. Moreover, our approach provably converges to a stationary point of the probabilistic objective under gradient ascent using scalable, unbiased estimators of both the probabilistic objective and its gradient. Therefore, as the number of starting points and gradient steps increase, our approach will recover of a maximizer of the AF (an often-neglected requisite for commonly used BO regret bounds). We validate our approach empirically and demonstrate state-of-the-art optimization performance on a wide range of real-world applications. PR is complementary to (and benefits) recent work and naturally generalizes to settings with multiple objectives and black-box constraints.

Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization
Samuel Daulton
Xingchen Wan
David Eriksson
University of Oxford, Meta
University of Oxford xwan@robots. ox. ac uk
Meta
sdaulton@meta.com
deriksson@meta.com com
Maximilian Balandat
Michael A. Osborne University of Oxford mosb@robots. ox. ac uk
Eytan Bakshy
Meta balandat@meta..com com
Meta ebakshymmeta.com com
Abstract
Optimizing sipensive-to-evaluate black-box functions of discrete (and potentially continuous) design parameters is ubiquitous problem in scientific and engineering applications. Bayesian optimization (BO) is popular, sample-efficient method that leverages probabilistic surrogate model and an acquisition function (AF) to select promising designs evaluate. However, maximizing the AF over mixed or high-cardinality discrete search spaces is challenging standard gradient-basee methods cannot be used directly or evaluating the AF at every point in the search space would be computationally prohibitive. To address this issue, propose using probabilistic reparameterization (PR). Instead of directly optimizing the AF over the search space containing discrete parameters, we instead maximize the expectation the AF over probability distribution defined by continuous parameters. We prove that under suitable reparameterizations, the BO policy that maximizes the probabilistic objective the same as that which maximizes the AF, and therefore, PR enjoys the regret bounds the original BO policy using the underlying AF. Moreover, our approach provably converges to a stationary point of the probabilistic objective under gradient ascent using scalable, unbiased estimators of both the probabilistic objective and its gradient. Therefore, as the number of starting points and gradient steps increase, approach will recover maximizer the AF (an often-neglected requisite for commonly used BO regret bounds). We validate our approach empirically and demonstrate state-of-the- art optimization performance on a wide range of real-world applications. PR is complementary to (and benefits) recent work and naturally generalizes to settings with multiple objectives and black-box constraints.
Introduction
Many scientific and engineering problems involve tuning discrete and/or continuous parameters to optimize an objective function. Often, the objective function "black-box", meaning it has no known closed-fone form expression. For example, optimizing the design of electrospun oil sorbent-a material that can be used to absorb oil in the case of a marine oil spill to mitigate ecological harm- to maximize properties such the oil absorption capacity and mechanical strength (59 involve tuning both discrete ordinal experimental conditions and continuous parameters controlling the composition of the material. For another example, optimizing the structural design of a welded beam can involve tuning the type of metal (categorical), the welding type (binary), and the dimensions of the different components of the beam (discrete ordinals)-resulting in search space with over 370 million possible designs S
We consider the scenario where querying the objective function is
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

expensive and sample-efficiene is crucial. In the case of designing the oil sorbent, evaluating the objective function requires manufacturing the material and measuring its properties in laboratory. requiring significant time and resources.
Bayesian optimization (BO) is a popular technique for sample-efficient black-box optimization, due to its proven performance guarantees in many settings [3] [2] and its strong empirical performance BO leverages a probabilistic surrogate model of the unknown objective(s) and an acquisition function (AF) that provides utility values for evaluating a new design to balance exploration and exploitation. Typically, the maximizer of the AF is selected as the next design to evaluate. However, maximizing the AF over mixed search spaces (i.e., those consisting of discrete and continuous parameters) or large discrete search spaces is challenging' and continuous (or gradient- based) optimization routines cannot be directly applied. Theoretical performance guarantees of BO policies require that the maximizer of the AF is found and selected as the next design to evaluate on the black-box objective function 152 When the maximizer is not found, regret properties are not guaranteed, and the performance of the BO policy may degrade.
A [55
To tackle these challenges, we propose a technique for improving AF optimization using a probabilis- tic reparameterization (PR) of the discrete parameters. Our main contributions are:
1. We propose a technique, probabilistic reparameterization (PR), for maximizing AFs over discrete and mixed spaces by instead optimizing a probabilistic objective (PO): the expecta- tion of the AF over a probability distribution of discrete random variables corresponding to the discrete parameters.
2. We prove that there is an equivalence between the maximizers of the acquisition function and the the maximizers of the PO and hence, the policy that chooses designs that are best with respect the PO enjoys the same performance guarantees as the standard BO policy.
3. We derive scalable, unbiased Monte Carlo estimators of the PO and its gradient with respect to the parameters of the introduced probability distribution. We show that stochastic gradient ascent using our gradient estimator is guaranteed to converge to a stationary point the PO surface and will recover a global maximum of the underlying AF as the number of starting points and gradient steps increase. This is important because many BO regret bounds require maximizing the AF (52). Although the AF is often non-convex and maximization is hard, empirically, with a modest number of starting points, PR leads better AF optimization than alternative methods.
4. We show that PR yields state-of-the-ee optimization performance on a wide variety of real-world design problems with discrete and mixed search spaces. Importantly, PR is com- plementary to many existing approaches such as popular multi-objective, constrained, and trust region- approaches; in particular, PR is agnostic the underlying probabilistic model over discrete parameters- which is not the case for many alternative methods.
2 Preliminaries
Bayesian Optimization We consider the problem of optimizing a black-box function f x'x - RR over a compact search space X' x 2, where X' = (1) x .... x (e(d) is the domain of the d 2 0 continuous parameters (z(() E (x))) for i = I,... d) and 2 = ( x ... x Z(d.) is the domain of the d2 2 discrete parameters (= E g for i = 1,... d=).
BO leverages (i) a probabilistic surrogate model tyyicaly a Gaussian process (GP) 46 fit to data set D, = {ar, Zi, y/ )a )== of designs and corresponding (potentially noisy) observations y: = f x)) + E;, 6, (O0 )²). and (ii) an acquisition function a(x, x) that uses the surrogate model's posterior distribution to quantify the value of evaluating a new design. Common AFs include
expected improvement (EI) (2 and upper confidence bound (UCB) 52 the latter of which enjoys
no-regret guarantees in certain settings 152 The next design to evaluate is chosen by maximizing
'If' the discrete search space has low enough cardinality that the AF can be evaluated at every discrete element, then acquisition optimization can be solved trivially.
'Throughout this paper, we use mixed search space x Z in our derivations, theorems, and proofs, without loss of generality with respect to the case of a purely discrete search space. If = 0, then the objective function f Z + R is defined over the discrete space Z and the continuous parameters in this exposition can simply be ignored.
2

---

the AF a1x 2) over X' x Z. Although the black-box objective f is pegeenivee-o--valuuae the AF is relatively cheap-to-query and therefore, can be optimized numerically. Gradient-bard based optimization routines are often used to maximize the AF over continuous domains [25
Discrete Parameters In its basic form, BO assumes that the inputs are continuous. However, discrete parameters such as binary, discrete ordinal, and non-ordered categorical parameters are ubiquitous in many applications. In the presence of such parameters, optimizing the AF is more difficult, as standard gradient-baad based approaches cannot be directly applied. Recent works have proposed various approaches including multi-armi armed bandits 40 48
and local search 44 for discrete
domains and interleaved discrete/continuor optimization procedures for mixed domains [15 57 A simple and widely-used approach across many popular BO packages [ 53 is to one-hot encode the categorical parameters, apply a continuous relaxation when solving the optimization, and discretize (round) the resulting continuous candidates. Examples of continuous relaxations and discretization functions are listed in Table
Table I: Different parameter types, their continuous relaxations, and discretization functions.
TYPE
DOMAIN
CONT. RELAXATION
discretize FUNCTION
BINARY
E 10
2' 0.
round (z')
ORDINAL
26 (O..... C- 13
2'C 0.5, C 0.5)
round (=)
CATEGORICAL
2 E (0,..,, C-
z' E 0, 0,
arg max, 2((0)
Although using continuous relaxation allows for efficient optimization using standard optimization routines in an alternate continuous domain Z' C IR" the AF value for an infeasible continuous value (i.e., z' & Z) does not account for the discretization that must occur before the black-bor function evaluated. Moreover, the acquisition value for an infeasible continuous value can be larger than the AF value after discretization. For illustration of this, see Fig. | (middle/right), In the worst case, BO will repeatedly select the same infeasible continuous design due to its high AF value, but discretization will result in design that has already been evaluated and has zero AF value. To mitigate this degenerate behavior and avoid the over-estimation issue, Marrido-Merchal and Hernández-Lobato [26] propose discretizing z' before evaluating the AF, but the AF then non-differentiable with respect to the z'. While this improves performance on small search spaces, the response surface has large flat regions after discretizing z', which makes difficult to optimize the AF The authors of [26] propose to approximate the gradients using finite differences, but, empirically, we find that this approach be leads sub-optimal AF optimization relative to PR.
3 Probabilistic Reparameterization
We propose alternative approach based on probabilistic reparameter- ization, a relaxation of the original optimization problem involving dis- crete parameters. Rather than di- rectly optimizing the AF via a con- tinuous relaxation z' of the design z, we instead reparameterize the
Algorithm 1 BO with PR
1: Input: black-box objective f: x Z - R
2: Initialize Do + 0, GPp < GP(O, k)
3: for
to Niterations do
4: (æn, 0,) + arg
xxxxxx Ez aa Z)
5: Sample nn ~ (Z))0n)
6: Evaluate f( Znn
optimization problem by introdue-
ing discrete probability distribu-
7:
Dn, < Dn- U (In, Zn, f 2n))}
tion p( Z () over a random variable 8: Update posterior GP,, given D,
9: end for
Z with support exclusively over Z. This distribution is parameterized
by a vector of continuous parameters 0. We use z to denote the vector (2(1), ..., (d.)), where each element is a different (possibly vector-valued) discrete parameter. Given this reparameterization, we define the probabilistic objective (PO):
Ezzp(zzo) Z)J.
(1)
Algorithm Noutlines BO with probabilistic reparameterization.
allows us to optimize and x over a continuous space to maximize the PO instead of optimizing x and to maximize directly over the mixed search space X Z. As we will show later, maximizing
3

---

Cont. Relax. AF Value
PO Value
1.0
1.0%
0.12
Interleaved
0.6
0.6
0.08
0.06
Cost. Relax.
H
0.4
0,4
0.2
(% Optimal Value: 86)
(% Optimal Value: 100)
Candidate
0.02
Exact Round
0.00
0.0
0.0
0.03 0.04
0.50
Final AF Valne
Xo
XD
Figure (Left) A comparison of AF optimization using different methods over a mixed search space shows that PR outperforms alternative methods for AF optimization and has much lower variance across replications. The violin plots show the distribution of final AF values and the mean. "Cont. Relax." denotes optimizing continuous relaxation of the categoricals with exact gradients. "Exact Round" refers to optimizing continuous relaxation with approximate gradients (via finite difference), but discretizes the relaxation before evaluating the surrogate 26 "Interleaved" alternates between one step of local search on the discrete parameters and one step of gradient ascent on the continuous parameters (used in CASMOPOLITAN (57]). For each method, the best candidate across 20 restarts selected (after discretization) and the acquisition value of the resulting feasible candidate is recorded. The AF is expected improvement E2]. (Middle/Right) AF values with continuous relaxation (middle) and the PO (right) for the Bramin function over mixed domain with one continuous parameter (zo) and one binary parameter (zo) (see Appendix C for details Branin). (Middle) Under a continuous relaxation, the maximizer the AF is an infeasible point in the domain (grey circle), which results in a suboptimal AF value when rounded (black star); the resulting candidate only has 86% of the AF value the true maximizer. The maximum AF value across the feasible search space is shown in white and the red regions indicate that the continuous relaxation overestimates the AF value since it is greater than the maximum AF value of any feasible design. (Right) The PO is maximized at the AF unique maximizer within the valid search domain. These contours show that PR avoids the overestimation issue that the naive continuous relaxation suffers from.
the PO allows recover maximizer of over the space X' x Z. Choosing p p(Z to be discrete distribution over Z means the realizations of Z are feasible values in Z. Hence, the AFF is only evaluated for feasible discrete designs. Since p( (0) is discrete probability distribution, can express Ez-p(z|o][4 (a Z) as a linear combination where each discrete design is weighted by its probability mass:
Ez Ezzp(z00)aa(,, 2) = Σ p(2(0)a(22,2))
(2)
#E2
Example distributions for binary, ordinal, and categorical parameters are provided in Table
Table 2: Examples of probabilistic reparameterizations for different parameter types. We denote the
(C (C-1)-sse 1)-smssipplex as A CC-1
PARAMETER TYPE
RANDOM VARIABLE
CONTINUOUS PARAMETER
BINARY ORDINAL
7 BERNOULLI())
0 [0
7 [0] + B. B BERNOULLI(0 (0)
0 0,
CATEGORICAL
2 CATEGORICAL(O)) (0()...., O(0)) 0 C-1 C-1
Although ordinal parameters could use the same categorical distributions the non-ordered categori- cal parameters, we opt for the provided proposal distribution since uses a scalar 0 (rather than a C-element vector) and it naturally encodes the ordering of the values. Using an independent random variable (
pl (1) g(0) for each parameter 2 for i 1,... de means that the probabilistic

---

objective can be expressed as
d_ a s z(()))
Ez _z~p(z10)aa2,, Z)]
Σ z0EZ 2((=)
E
II p( 10(00
3.1 Analytic Gradients
One important benefit of PR is that the PO in ① is differentiable with respect to 0 (and æ, if the gradient of with respect to a exists), whereas (xx x) gradients of the PO with respect to 0 and x can be obtained by differentiating Equation P
not differentiable with respect z. The
VolRz~pzz10) 2)] ] = Σ
a(x 2) Vop(z(()
(4)
#EZ
ValBz~p(z10)(0(1; Z)]
Σ
p(z
(5)
ZE2
This enables optimizing the PO (line 4 of Algorithm D efficiently and effectively using gradient-based methods.
3.2 Theoretical Properties
In this section, derive theoretical properties of PR. Proofs are provided in Appendix B Our first result is that there is an equivalence between the maximizers of the PO and the maximizers of the AF over X' Z.
Theorem (Consistent Maximizers). Suppose that a is continuous in for every E 2. Let H"
be the maximizers of a(x, 2): H = {(x x) arg max( a(x, 3)}. Let C X x θ be
the maximizers of Ezzp(Z (xx Z)]: J {(x, 0) E arg (a) E Ez 2 Z)]} where is the domain of 0. Let H S x Z be defined as: H* ((x, (x, E J 2 p(Z]0)). Then, H" H"
Algorithm outlines BO with probabilistic reparameterization. Importantly, Theorem I states that sampling from the distribution parameterized by a maximizer of the PO yields a maximizer of a, and therefore, Algorithm enjoys the performance guarantees of cx.))
Corollary 1 (Regret Bounds). Let a(x, 2) be acquisition function over search space X x Z such that when a is applied as part of a BO strategy that strategy has bounded regret If the conditions for the regret bounds of that BO strategy using satisfied, then Algorithm Musing enjoys the same regret bound.
Examples of BO policies with bounded regret include those based on AFs such as upper confidence bound (UCB) 52 or Thompson sampling (TS) 449 for single objective optimization, and UCB or TS with Chebyshev
4
or hypervolume (66 scalarizations the multi-objective setting.
Although the BO policy selects a maximizer of a is equivalent to the BO policy in Algorithm I maximizing the AF over mixed high-dimensional discrete search spaces is challenging because commonly used gradient-based methods cannot directly be applied. The key advantage of our approach is that maximizers of the AF can be identified efficiently and effectively by optimizing the PO using gradient information instead of directly optimizing the AF. We find that optimizing PR yields better results than directly optimizing a or other common relaxations as shown in Figure Left). where we compare AF optimization methods on the mixed Rosenbrock test problem (see Appendix C for details).
4 Practical Monte Carlo Estimators
4.1 Unbiased estimators of the Probabilistic Reparameterization and its Gradient
As the number of discrete configurations ([ž)) increases, the PO and its gradient may become computationally expensive to evaluate analytically because both require summation of [2] terms. Therefore, we propose to estimate the PO and gradient using Monte Carlo (MC) sampling. The
MC estimator of the PO is given by
5

---

1 N Σ a E.);
Ez [z=p(2100aa(z; Z) Rd
(6)
where ,1,..., nn are samples from p 2Z)) This estimator is unbiased and can be computed for a large number of samples by evaluating the AF independently (or in chunks) for each input (ar, 2n).
MC can also be used estimate the gradient of the PO with respect to 0. We opt for using a score function gradient estimator [35] (also known as REINFORCE (2) and the likelihood ratio estimator
277 because is simple, scalable, and can be computed using the acquisition values {a(x, } }==1
that are used in the MC estimator of the PO. Many alternative lower variance estimators (e.g. Yin
al. 64 Yin al. 665 would require many additional AF evaluations (see Mohamed et for review of MC gradient estimation). The score function is the gradient of the log probability with
respect the parameters of the distribution: Vo p( 0) Vop(Z10) Using this score function, we can express the analytic gradient as
(a(x, Z) = Σ
a(x, =) =))(= logp(z10) = Ez _zz (ollogp(Z1))
ZEZ
The unbiased MC estimator of the gradient of the PO with respect to is given by
N
V TelEz~p(210))e Z)] ~
a(x, 2, Vo log
Since the score function gradient is only defined when p(= > 0, we reparameter- ize 0 to ensure p(=10) > 0 for all z and 0 by using the softmax transformations pro- vided in Table B which are commonly used for computational convenience and stabil- ity in probablistic reparameteriiztion Moreover, even though p(z(0) > 0, when p(= is small, a small num- ber N of MC samples are unlikely to produce any samples where Σ z. Instead of optimizing 0 directly, we instead optimize Φb Since the trans- formations g(-) are differentiable with respect to Φ, the gradient (and MC gradient estimator) of the PO with respect to dp are easily obtained using the gradient of the PO with respect to and simple application the chain rule (multiplying by V)
651. and the solution converges T 0.
PARAMETER TYPE
TRANSFORMATION (0 = 9(6))
BINARY
0 ((Φ 1)/r) 0 0= [0] [6] 4)/7)
ORDINAL
CATEGORICAL
((0) = SOFTMAX 0.5)/T)(o)
Table 3: Transformations where E R4 and ي, 0 O.
4.2 Variance Reduction in Monte Carlo Gradient Estimation
Although the MC gradient estimator in is unbiased, score function gradient estimators can suffer from high variance 39 Therefore, we adopt a popular technique for variance reduction where the score function itself is used as a control variate, since its expectation is zero under pl (() [39]] Score function estimators with this control variate have been shown be among the best performing gradient estimators 39 Moreover, this technique is simple and merely amounts to subtracting value 3 from the acquisition value the score function estimator Equation
N
1
VoEz=pizze/a(z, Z)]
ia( 2,) Vo Vol 1))
N
The 8 is commonly known baseline and is often taken to be moving average of the (acquisition) values 39) See Appendix C for details on B3
4.3
Convergence Guarantee using Stochastic Gradient Ascent
Since the score function gradient estimator is unbiased, can leverage previous work convergence in probability under stochastic gradient ascent 47 to arrive at our main convergence result for acquisition optimization.
Theorem 2 (Convergence Guarantee). Let a X x 2 + R be differentiable in x for every E Z. Let (a. m, om.m) be the best solution after running stochastic gradient ascent for time steps on the

---

probabilistic objective Zz-nzzio]a(zz from m starting points with its unbiased MC estimators proposed above. Let {at be a sequence of positive step sizes such that 0 < Et= of = A < co and Ei=1 at 00, where at is the step size used in stochastic gradient ascent at time step t. Let 2t,m z Then as - co, m + 00, and -> 0, (fe,m: 2s,m) (x" 2²)
arg (xX a(x 2) in probability.
The significance of Theorem 2 is that optimizing the PO is guaranteed to converge in probability to a global maximizer of the AF, meaning that optimizing the PO guarantees that resulting candidate design has maximal AF value. The implication is that the intended BO policy is followed and the underlying regret bounds of the AF are recovered (provided that the other conditions of the regret bound are met). Although global convergence is only guaranteed as + co, observe in Figure Ieftt that PR yields strong, stable acquisition optimization with only m = 20 starting points, 200 steps, and Io (see Appendix G further discussion) and outperforms alternative optimization approaches.
Related Work
Many methods for BO over discrete and mixed search spaces have been proposed. Previous work has largely focused on (i) improving the surrogate models or (ii) improving AF optimization.
Improving models: Historically, methods leveraging tree-based surrogate models, e.g., SMAC BC and TPE [.. have been popular for optimizing discrete or mixed search spaces. Many recent works have considered alternative surrogate models. BOCS encodes categorical parameters as binary variables and uses Bayesian linear regression with pairwise interactions (2]. COMBO uses diffusion kernel on the graph defined by the Cartesian product of discrete parameters exploits the combinatorial graph, but with Mercer features and Thompson sampling [1.. HYBÒ extends the diffusion kernels to mixed continuous-discrt scale poorly with respect to the number of data points and parameters. Moreover, of the methods listed above, only HYBO supports continuous parameters without restricting them to a discrete set. HYBO enjoys universal function approximation property, but relies on summing over all possible orders of interactions between base kernels for each parameter which results in exponential complexity with respect to the number of parameters and limits its applicability to low-dimensional problems. Moreover, the computational issues of such approaches make it difficult to apply them to multi-objective and constrained optimization. GRYFFIN is limited to categorical search spaces. MIVABO uses a linear combination of basis functions (e.g. pseudo Boolean features 7 for discrete parameters) with interaction terms
MERCBO similarly
spaces 15.. However, these methods
20 uses kernel density estimation, but
[ MVRSM [6] uses ReLU-based surrogates for computational efficiency, but is limited by the expressiveness of these models.
Optimizing acquisition functions: As discussed previously, Garrido-Merchán Merchán and Hernández- Lobato 26 propose using continuous relaxation and discretize the inputs before evaluating the AF. However, the resulting AF after discretization is piece-wise-fle along slices of the continuous relaxation of the discrete parameters and therefore is difficult to optimize. CoCABO ال samples discrete parameters using a multi-armas bandit and optimizes the continuous parameters conditional upon the sampled discrete parameters. However, CoCABO's 's performance degrades as number of discrete configurations increases. CASMOPOLITAN 157] uses local trust regions combined with an interleaved AF optimization strategy that alternates between local search steps the discrete parameters and gradient ascent for the continuous parameters. Furthermore, both COCABO and CASMOPOLITAN do not inherently exploit ordinal structure.
Probabilistic reparameterization: PR has been considered for optimizing discrete parameters in other domains such reinforcement learning (62) and sparse regression [65]. However, PR has not been leveraged for BO. Although the reparameterization trick used by Wilson et al. [X3] is in a similar vein to PR, Wilson et al. [ reparameterize an existing multivariate normal random variable in terms of standard normal random variables and then use sample-po path gradient estimators. In contrast, our approach introduces new probabilistic formulation using discrete probability distributions and uses sieelihood-ration ratio-based gradient estimators since sample- -ath gradients cannot be computed through discrete sampling.
Alternative methods for propagating gradients: Alternative methods for propagating gradients through discrete structures have been considered in the deep learning community (among others).
7

---

One approach is to use approximate discrete Concrete distributions B1 37,, which admit sample- path gradients. However, samples from Concrete distributions are not discrete and approximation enror can result in pathologies similar to evaluating the AF using continuous relaxation. Moreover, approximately discrete samples prohibit using surrogate models that require discrete inputs (without discretizing the samples)- e.g., GPs with Hamming distance kernels A8 Another approach for gradient propagation in the deep learning community is to use straight- (STE) f where the gradient of the discretization function with respect to its input is estimated using, for example, an identity function. This approach works well empirically in some cases, these estimators not well- groundedd theoretically. Nevertheless, we discuss and evaluate using STE for AF optimization in Appendix H
gradient estimators
Experiments
In this section, we provide an empirical evaluation of PR on a suite of synthetic problems and real world applications. For PR, we stochastic mini-batches of N = 128 MC samples in our experiments and demonstrate that PR is robust with respect to the number of MC samples (and compare against analytic PR, where computationally feasible) in Appendix R We optimize PR using Adam 34 with an initial learning rate of 1 40' We show that PR Adam is generally robust to the choice of learning rate (more so than vanilla stochastic gradient ascent) in the sensitivity analysis in Figure 2 in Appendix M We compare PR against two alternative acquisition optimization strategies: using continuous relaxation (CONT. RELAX.) and using exact discretization with approximate gradients (EXACT ROUnD) [26] These approaches optimize the acquisition function with L-BFGS-B with exact and approximate gradients, respectively. In addition, we compare against two state-of- the-art methods for discrete/mixed BO: a modified version of CASMOPOLITAN (57] that additionally supports ordinal variables introduced in Wan et al. [58] and HYBO [T,, both of which are shown to outperform the other related works discussed in Section 5 In addition, we showcase how PR is complementary to existing methods such as trust region methods [22). We demonstrate this by using PR with a trust region for the continuous and discrete ordinal parameters and optimize PR within this trust region. In Appendix H we provide comparison of TR methods with alterative optimizers and find that PR is the best optimizer when using TRs on 6 of the 7 benchmark problems. See Appendix C for additional discussion of PR + TR. For PR, EXACT ROUND, and PR TR we use the sum of a product kernel and a sum kernel of a categorical kernel 4X for the categorical parameters and Matérn-5// kernel for all other parameters." 3 Alternative kernels over different representations of categorical parameters such as one-hot encoded vectors, latent embeddings [67]. and known embeddings (e.g. using fingerprint-bart
reaction encodings for categorical parameters in chemical reaction optimization [51] are evaluated in Appendix !
CONT. RELAX., EXACT ROUND, PR, and PR TR use expected improvement 2 32 for single objective (constrained problems) and expected hypervolume improvement 20) for the multi nulti--bjective oil sorbent problem (where exact gradients with respect to continuous parameters are computed using auto-diiferentiation R ). We report the mean for each method + 2 standard errors across 20 replications. Performance evaluated in terms of regret (feasible regret for constrained problems and hypervolume regret for multi-objective problems). CASMOPOLITAN and HYBO are not run on Welded Beam and Oil Sorbent as they do not support constrained and multi-objectivv optimization. We also leave the multi-objective extension of PR+TR to future work because it would add additional complexity [II. For HYBO, we only run 60 BO iterations on SVM due to the large wall time (see Figure B) and only report partial results Cellular Network due to singular covariance matrix error. See Appendix M details on the experiment setup, regret metrics, benchmark problems, and methodological details. We leverage existing open source implementations of CASMOPOLITA and HYBO (see Appendix forr links), and the implementations of all of other methods are available at https://gitthen thwp:////ttttu..../ http.ccom/faeee cwwm/aacebokkeeeerrcccco
pr
6.1 Synthetic Problems
We evaluate all methods on 3 synthetic problems. Ackley is a 13-dimensional function with 10 binary and 3 continuous parameters (a modified version of the problem in Blick et al. (6). Mixed Int F1 is 16-dimensional variant of the F1 function from Tušar et al. [56] with 2 binary, 6 discrete ordinal parameters, and 8 continuous parameters. The discrete ordinal parameters have following
*CONT. RELAX. is incompatible with categorical kemel, so we use a Matérn-572 5/2 with one-hot encoded
categorical parameters.
8

---

cardinalities: 2 parameters with 3 values, 2 with 5 values, and 2 with 7 values. Rosenbrock is 10-dimensional Rosenbrock function with discrete ordinal parameters with 4 values each and continuous parameters.
6.2 Real World Problems
We consider real world applications including problem with black-box outcome constraints and a 3-objective problem (see Appendix D for details on constrained and multi-objective BO),
Welded Beam Optimizing the design of welded steel beam is a classical engineering optimization. In this problem, the goal is to minimize manufacturing cost subject to 5 black-box constraints on structural properties of the beam (including shear stress, bending stress, and buckling load) by tuning 6 parameters: the welding configuration (binary), the metal material type (categorical with 4 options), and 4 ordinal parameters controlling the dimensions of the beam 52
SVM Feature Selection This problem involves jointly performing feature selection and hyperparam- eter optimization for a Support Vector Machine (SVM) trained on the CTSlice UCI data set [18] 36 The design space for this problem involves 50 binary parameters controlling whether a particular feature is included not, and continuous hyperparameters of the SVM.
Cellular Network Optimization this 30-dimensional problem, the goal is to tune the tilt (ordinal
with 6 values) and transmission power (continuous) for a set of 15 antennas [50] to maximize a coverage quality metric that is a function of signal power and interference
38 over a geographic
region of interest. We use the simulator from Dreifuerst et al. [17].
Direct Arylation Chemical Synthesis Palladium-catalyser direct arylation has generated significant interest in the pharamceutical development sector[12) In this problem, the goal is maximize yield for a direct arylation chemical reaction by tuning 3 categorical parameters corresponding to the choice of solvent, base, and ligand, as well 2 continuous parameters controlling the temperature and concentration. We fit surrogate model the direct arylation dataset from Shields et al. [51] in order to facilitate continuous optimization of temperature and concentration. In Appendix J we demonstrate that PR can leverage kernel over fingerprint-bast based reaction encodings computed via density functional theory (DFT) for the categorical parameters [5]].
Electrospun Oil Sorbent Marine oil spills can cause ecological catastrophe. One avenue for miti- gating environmental harm is to design and deploy absorbent materials to capture the spilled oil. In this problem, tune 5 ordinal parameters parameters with 5 values and 2 with 4 values) and continuous parameters controlling the composition and manufacturing conditions for an electrospun oil sorbent material maximize 3 competing objectives: the oil absorbing capacity, the mechanical strength, and the water contact angle [59].
Mixed Int F1
Rosenbrock
Ackley
Welded Beam (5 constmints)
3
Log Regret
0
1
-0.5
0
-1.0
100
100
SVM
Celliiarr Network
Chemical Reaction
Oil Sorbent (3 objectives)
6
-0.7
Log Regret
-0.8
-0.8
5
-0.9-
4-
-1.0
-1
100
200
0
200 Iteration
400
100
200
0
100
200
Iteration
Iteration
Iteration
Sobol
Cont. Relax
Exact Roand
PR +
Casmapolitan
HyBO
Figure 2: PR (or PR + TR) consistently outperforms alternatives with respect to log regret.

---

Mixed Int F!
Rosenbrock
Ackley
Welded Beam (5 constraints)
100
100
100
100
Wall Time
10
32
10
10
50
100
0
50
100
50
100
0
50
100
Celhnlar
Chemical Reaction
Sorbent (3 objectives)
100
100
Wall Time (5)
100
100
10
10
100
200
200
400
100
200
0
100
200
Iteration
Iteration
Tteration
PR
Sobol
Cont. Relax.
Exact Round
PR + TR
Casmapolitan
Hy80
Figure 3: Wall time for candidate generation at each BO iteration in seconds. CONT. RELAX., EXACT ROUND, PR, and PR + TR are run on single Tesla V100-SXM2-16GB GPU and other methods are run Intel Xeon Gold 6252N CPU.
6.3 Results
We find PR consistently delivers strong empirical performance as shown in Figure 2 On all benchmark problems, PR (or PR TR) outperforms all baseline methods (except for Mixed Int FI, where HYBO performs comparably). Figure shows the wall time for candidate generation over the number of BO iterations. Although PR is computationally intensive, the computation is embarrassingly parallel and therefore exploiting GPU acceleration yields competitive wall times. Importantly, PR's wall time scales well with the number of observations and design parameters, unlike HY which scales poorly with both. However, the complexity of PR scales additively in the number of GPs being used (e.g. outcomes being modeled), assuming they are evaluated sequentially. Hence, in multi-objective or constrained settings, PR incurs a high cost in terms of wall time. However, empirically PR achieves better optimization performance constrained and multi- objective problems relative to CONT. RELAX. and EXACT ROUND. We note that CASMOPOLITAN does not support multi-objective BO or constrained BO, and although HYBO could be used in those settings, would be impractically slow because 1) its wall time would scale linearly with the number of modeled outcomes (using independent GPs) and 2) its diffusion kernel is non-differentiable, which would make optimizing hypervolume-basee AFs slow
shows
7 Discussion
The performance and regret properties of BO depend critically properly maximizing the AF, For problems with discrete features, exhaustively trying all possible combinations of discrete values quickly becomes infeasible as the number of combinations grows. Alternatives such trying subset of the possible combinations or resorting to continuous relaxations often leads to a failure to effectively optimize the AF which may result in sub-optimal BO performance. As alternative, propose using PR to better optimize the AF, and we demonstrate that PR achieves strong performance large number of wellwwrldd problems. Our approach is complementary to many other BO extensions, and combines seamlessly with, for example, trust region- based BO and specialized kernels for discrete parameters. One limitation of PR is that it requires computationalll--demaan MC integration. However, given that the computation in PR is embarrassingly parallel, it motivates for future research on optimizing AFs distributed hardware.
Acknowledgements
We thank Ben Letham, James Wilson, and Michael Cohen, as well as the members of the Oxford Machine Learning Research Group, for providing insightful feedback.
10

---

References
[1] 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: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[2] Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In Proc. of ICML, volume 80 of Proceedings of Machine Learning Research, pages 47 471- PMLR, 2018
[3] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. ArXiv preprint, abs/1308.3432, 2013.
[4] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Advances in Neural Information Processing Systems 24: 25th Annual Conference Neural Information Processing Systems 2011. Proceedings of meeting 2011.
held 12-14 December 2011, Granada, Spain, pages
[5] Felix Berkenkamp, Angela Schoellig, and Andreas Krause. No-regret Bayesian optimization with unknown hyperparameters. Journal of Machine Learning Research, 20(50): 1-24, 2019. URL htttp://jmlr wwwpoo//ww.///////////////// 213. html
[6] Laurens Bliek, Arthur Guijt, Sicco Verwer, and Mathijs de Weerdt. Black-box variable optimisation using a surrogate model that satisfies integer constraints. GECCO '21, page 1851-1859, Association for Computing Machinery, 2021.
[7] Endre Boros and Peter I.. Hammer. Pseudo-boolean optimization. Discrete Applied Mathemat- ics, 123(1):155 225, 2002. ISSN 0166-218X. doi: https://doi.or// wwt.:////....0010010000000666000 00341-9.
[8] Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hypervol- ume improvement for parallel multi-objective bayesian optimization. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
[9] Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Parallel Bayesian optimization of multiple noisy objectives with expected hypervolume improvement. M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2187-2200. Curran Associates, Inc., 2021.
[10] Samuel Daulton, Sait Cakmak, Maximilian Balandat, Michael Osborne, Enlu Zhou, and Eytan Bakshy, Robust multi-objective Bayesian optimization under input noise. arXiv preprint arXiv:2202.07544, 2022.
[11] Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Multi-objective Bayesian optimization over high-dimensional search spaces. In Proceedings the Conference on Uncertainty in Artificial Intelligence, UAI 2022, Eindhoven, Netherlands, August 1-5, 2022, Proceedings of Machine Learning Research. AUAI Press, 2022.
[12) Huw MI. Davies and Daniel Morton. Recent advances in c-h functionalization. The Journal of Organic Chemistry, 81(2)3333-350, 2016.
[13] Erik A. Daxberger, Anastasia Makarova, Matteo Turchetta, and Andreas Krause. Mixed-variable Bayesian optimization. In Proceedings of the Twetty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 2633-2639, ijeai.org, 2020. doi: 10. 10.24963/ijci 2020/ 365.
[14] Aryan Deshwal and Jana Doppa. Combining latent space and structured kernels for Bayesian optimization over combinatorial spaces. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 8185-8200. Curran Associates, Inc., 2021. URL https:://tt //ppcedddiggss Papo00-app.pp..ee pdff

---

[15] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Bayesian optimization over hybrid spaces. Proc. of ICML, volume 139 of Proceedings of Machine Learning Research, pages 2632-2643. PMLR, 2021.
[16] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa. Mercer features for efficient combinatorial Bayesian optimization. In Thirty-Fift AAAI Conference on Artificial Intelligence (AAAI), pages 7210-7218, 2021.
[17] Ryan M Dreifuerst, Samuel Daulton, Yuchen Qian, Paul Varkey, Maximilian Balandat, Sanjay Kasturia, Anoop Tomar, Ali Yazdan, Vish Ponnampalam, and Robert W Heath. Optimizing coverage and capacity in cellular networks using machine learning. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8138-88 8142. IEEE, 2021.
[18] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[19] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Comb. Probab. Comput., 13(4-5): 577-625, jul 2004. ISSN 0963-5483.
doi: 10.101 10017//096635483400663311
[20] M. T. M. Emmerich, K. C. Giannakoglou, and B. Naujoks. Single- and multiobjective evo- lutionary optimization assisted by gaussian random field metamodels. IEEE Transactions Evolutionary Computation, 10(4):421-433 2006.
[21] David Eriksson and Matthias Poloczek. Scalable constrained Bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 730-738. PMLR, 2021.
[22] David Eriksson, Michael Pearce, Jacob R. Gardner, Ryan Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 5497-5508, 2019.
[23] Peter Frazier. A tutorial on Bayesian optimization. ArXiv preprint, abs/1807 ht//1807.000 00000000111. 1, 2018.
[24] Jacob R. Gardner, Matt J. Kusner, Zhixiang Eddie Xu, Kilian Q. Weinberger, and John P. Cunningham. Bayesian optimization with inequality constraints. In Proc. of ICML, volume 32 of JMLR Workshop and Conference Proceedings, pages 937-945. JMLR.org, 2014.
[25] Roman Garnett, Bayesian Optimization. Cambridge University Press, 2022. in preparation.
[26] Eduardo Garrido-Merchán and D. Hermández-Lobato. Dealing with categorical and integer- valued variables in Bayesian optimization with gaussian processes. Neurocomputing, 380:
20-35. 2020.
[27] Peter W Glynn. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33(10):75-84, 1990.
[28] Nikolaus Hansen, Dimo Brockhoff, Olaf Mersmann, Tea Tusar, Dejan Tusar, Ouassim Ait ElHara, Phillipe Sampaio, Asma Atamna, Konstantinos Varelas, Umut Batu, et al. Comparing continuous optimizers: numbbo/coco on github. 2019.
[29] Florian Häse, Matteo Aldeghi, Riley Hickman, Loic M Roch, and Alán Aspuru-Guzik, Gryffin: An algorithm for Bayesian optimization of categorical variables informed by expert knowledge. Applied Physics Reviews, 8(3):334006 2021.
[30] Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brower Sequential model-based optimiza- tion for general algorithm configuration. In Proceedings of the 5th International Confer- ence on Learning and Intelligent Optimization, page 507-523. Springer- Springer-Verlag, 2011. ISBN
9783642255656.
[31] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In Prec. of ICLR. OpenReview.net, 2017.
[32] Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13:455-492, 1998.
12

---

[33] Kirthevasan Kandasamy, Jeff Schneider, and Barnabas Poczos. High dimensional Bayesian optimisation and bandits via additive models. In Francis Bach and David Blei, editors, Proceed- ings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 295-304, Lille, France, 07-09 Jul 2015. PMLR. URI. https://proceeeding. mlr prwss/ v37 /37/kaaaaaamm115555 html
[34] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
[35] Jack PC Kleijnen and Reuven Y Rubinstein. Optimization and sensitivity analysis of computer simulation models by the score function method. European Journal of Operational Research, 88(3):413-427, 1996.
[36] Sulin Liu, Qing Feng, David Eriksson, Benjamin Letham, and Eytan Bakshy. Sparse Bayesian optimization. arXiv preprint urXiv:2203.01900 2022.
[37] Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation discrete random variables. In Proc. of ICLR. OpenReview.net, 2017.
[38] Wesley J Maddox, Maximilian Balandat, Andrew G Wilson, and Eytan Bakshy. Bayesian optimization with high nigh-diimensionl outputs. In Advances in Neural Information Processing Systems, volume 34, 2021.
[39] Shakir Mohamed, Mihacla Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. J. Mach. Learn. Res., 21(132):1-62, 2020.
[40] Dang Nguyen, Sunil Gupta, Santu Rana, Alistair Shilton, and Svetha Venkatesh. Bayesian optimization for categorical and category-specific continuous inputs. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 5256-5263. AAAI Press, 2020.
[41] ChangYong Oh, Jakub M. Tomczak, Efstratios Gavves, and Max Welling. Combinatorial Bayesian optimization using the graph cartesian product. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2910 2910-2920, 2019.
[42] Art Owen. Quasi-monte carlo sampling. Monte Carlo Ray Tracing: Siggraph, 1:69-88, 2003.
[43] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi- objective Bayesian optimization using random scalarizations. In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pages 766-776. AUAI Press, 2019.
[44] Julien Pelamatti, Loic Brevault, Mathieu Balesdent, El-Ghazali Talbi, and Yannick Guerin. Bayesian optimization of variable-size design space problems. Optimization and Engineering. 22(1):387-447, 2021.
[45] J. Rapin and O. Teytaud. Nevergrad A gradient-fres free optimization platform. https://Gittie com hom///acebooieesaaa///eeerrrraas
2018
[46] Carl Edward Rasmussen. Gaussian processes in machine learning. In Advanced Lectures on Machine Learning: ML. Summer Schools 2003, Canberra, Australia, February 2 14, 2003, Tübingen, Germany, August 4- 16, 2003, Revised Lectures, 2004.
[47] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400-400 407, 1951. ISSN 00034851.
[48] Bin Xin Ru, Ahsan S. Alvi, Vu Nguyen, Michael A. Osborne, and Stephen J. Roberts. Bayesian optimisation over multiple continuous and categorical inputs. In Proc. of ICML., volume 119 of Proceedings of Machine Learning Research, pages 0276-8285. PMLR, 2020.
13

---

[49] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling, arXiv preprint: arXiv 1301.2609, 2014.
[50] Soumya Ranjan Samal, Kaliprasanna Swain, Shuvabrata Bandopadhaya, Nikolay Dandanov, Vladimir Poulkov, Sidheswar Routray, and Gopinath Palai. Dynamic coverage optimization for 5g ultra-dense cellular networks based on their user densities. 2021.
[51] Benjamin J Shields, Jason Stevens, Jun Li, Marvin Parasram, Farhan Damani, Jesus Martinez Alvarado, Jacob M Janey, Ryan P Adams, and Abigail G Doyle. Bayesian reaction optimization as tool for chemical synthesis. Nature, 590(7844):89-96 2021.
[52] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. of ICML, pages 1015-1022. Omnipress, 2010.
[53] The GPyOpt authors. github. com. hwtp///hffffedddai..
GpyOpt: Bayesian optimization framework in python. http:// 2016.
[54] Anh Tran, Minh Tran, and Yan Wang. Constrained mixed-integer gaussian mixture Bayesian optimization and its applications in designing fractal and auxetic metamaterials. Structural and Multidisciplinary Optimization, 59(6):2131-2154 2019.
[55] Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Eero Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020, In NeurIPS 2020 Competition and Demonstration Track, pages 3-26, 2021.
[56] 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 11, page 718-726. Association for Computing Machinery, 2019.
[57] Xingchen Wan, Vu Nguyen, Huong Ha, Bin Xin Ru, Cong Lu, and Michael A. Osborne. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. In Proc. of ICML, volume 139 of Proceedings of Machine Learning Research, pages 10663- 10674. PMLR, 2021.
[58] Xingchen Wan, Cong Lu, Jack Parker-Holder, Philip J Ball, Vu Nguyen, Binxin Ru, and Michael Osborne. Bayesian generational population-bes training. In ICLR Workshop on Agent Learning in Open-Ended,sss, 2022.
[59] Boqian Wang, Jiacheng Cai, Chuangui Liu, Jian Yang. and Xianting Ding. Harnessing novel machine-learning beccinn-learning-assstttee -asssssted assisted evolutionary algorithm to co-optimize three characteristics of an electrospun oil sorbent. ACS Applied Materials & Interfaces, 12(38)442422 42849, 2020.
[60] Jialei Wang, Scott Clark, Eric Liu, and Peter Frazier. Parallel Bayesian global optimization of expensive functions. Operations Research, 68(6): 18000188501185 2020.
[61] Rui Wang, Jian Xiong, Hisao Ishibuchi, Guohua Wu, and Tao Zhang. On the effect of reference point in moea/d for multi-objectivee optimization. Applied Soft Computing, 58:25-34, 2017. ISSN 1568-4946. doi:
[62] Ronald J Williams. Simple statistical gradient- algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-25) 1992.
[63] James T. Wilson, Frank Hutter, and Mare Peter Deisenroth. Maximizing acquisition functions for Bayesian optimization. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9906-9917, 2018.
[64] Mingzhang Yin, Yuguang Yue, and Mingyuan Zhou. ARSM: augneent-einfoore-wa--neeee es- timator for gradient backpropagation through categorical variables. In Proc. of ICMI., volume 97 of Proceedings of Machine Learning Research, pages 7095-7104. PMLR, 2019.
14

---

[65] Mingzhang Yin, Nhat Ho, Bowei Yan, Xiaoning Qian, and Mingyuan Zhou. Probabilistic Best Subset Selection by Sradient-Basee Optimization. arXiv e-prints, 2020.
[66] Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi- objective black box optimization. In Proc. of ICML, volume 119 of Proceedings of Machine Learning Research, pages 11096-11105 PMLR, 2020.
[67] Yichi Zhang, Siyu Tao, Wei Chen, and Daniel Apley. latent variable approach to gaussian process modeling with qualitative and quantitative factors. Technometrics, 62:1-19, 07 2019. doi: 10. 00080/00401106.20999904
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix A
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "s8C0wPVZzb8", "reviewer": "Reviewer_9pbz", "summary": "This paper proposes a Bayesian optimization method over mixed spaces, i.e., discrete space and continuous space, via probabilistic reparameterization.  Since optimizing an acquisition is a challenging task where discrete variables exist, probabilistic reparameterization is used to allow us to optimize the acquisition function with gradient information.  The authors provide the theory that the proposed method serves a consistent optimizer.  Finally, they demonstrate that the proposed method works well in diverse experiments.", "questions": "I would like to ask the authors some questions.\n\n1. In Table 1, ordinal variables have the form of continuous relaxation $z' \\in [0, C - 1]$ and categorical variables have the form of continuous relaxation $z' \\in [0, 1]^C$.  Are they correct?  For ordinal variables, $[0, 1) \\to 0, [1, 2) \\to 1, \\ldots [C-2, C-1) \\to C-2, [C-1, C-1] \\to C-1$.  Thus, $C-1$ has a smaller range than the other integers.  I think it should be $[0, C)$.  Moreover, for categorical variables, $[0, 1]^C$ should be a simplex.  More precisely, a probability vector for categories has to sum to one, so I think it should be $[0, 1]^{C-1}$ where a sum-to-one constraint is assumed.  It is a generalization of binary case, which implies that its continuous relaxation is $[0, 1]^1$.\n\n1. I am not sure if the continuous relaxations are changed, other parts are still same.  Or the current version is just equivalent to the continuous relaxations I described.  If updates are required, please describe in the rebuttal.", "limitations": "I do not think that this work has any negative societal impacts and any specific limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n+ It solves an interesting topic regarding discrete and mixed spaces.\n\n+ It proposes a solid method using probabilistic reparameterization.\n\n+ The experimental results are reasonable.\n\n## Weaknesses\n\n- I think this work is quite novel, but some previous work such as [20, 50] should be discussed more thoroughly.\n\nPlease see the text box described below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aed2z6ofCU", "reviewer": "Reviewer_mBPd", "summary": "This work proposes a method for optimization of acquisition functions in Bayesian optimization (BO), where at least some of the input variables are discrete (binary, integer, or categorical). The method is based on a probabilistic reformulation, whereby the discrete variables are cast as random variables, drawn from probability distributions. Optimization can then performed on the expected value of the acquisition function, using the parameters of the assumed probability distributions as inputs instead of the original (discrete) variables. This reformulation enables the use of gradient-based optimization; the authors propose a Monte Carlo approach to estimate the gradients.", "questions": "Could a comparison be added to show that the proposed MC method results in more sample-efficient (in terms of optimization) performance than existing methods? E.g., when 1024 MC samples are used, would it be a more fair comparison to allow the multi-start methods to have 1024 starts?\n\nSince the proposed method effectively updates continuous parameterizations used to compute the \"discretized\" values of the original updates, is there an equivalent relaxation and iterative optimization method in the original space?", "limitations": "Yes, provided in supplementary material.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS:\n\n1. The method and significance are well presented, and the introduction and case studies show why the setting of BO over mixed variable spaces is both challenging and important.\n\n2. The computational studies demonstrating the method are very thorough, with a wide range of case studies and tests considered.\n\n3. The authors prove mathematically that the proposed reformulation does not affect the convergence guarantees of standard BO.\n\nWEAKNESSES:\n\n1. I am not very familiar with probabilistic reformulation, but it seems the proposed reformulation effectively inherits the weaknesses of BO on discrete inputs that it purports to avoid. For example, a binary variable is recast as a binomial distribution, which must be again \"discretized\" (in Algorithm 1) to create feasible values for $z_n$. Moreover, the secondary transformation in Table 3 introduces similar techniques used to relax discrete variables for optimization.\n\n2. While the main advantage of the proposed method is that it enables gradient based optimization, the accuracy of the gradients relies on Monte Carlo estimation, which must be evaluated over the original discretized space (eg. 6). This introduces the same curse of dimensionality that would arise from optimization over a mixed variable space (e.g., by enumeration or branch-and-bound), and, as a result, the computational results may be unfair as the proposed method is given much more information in the form of MC samples. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PyZBBTkyhDF", "reviewer": "Reviewer_H7wp", "summary": "Maximizing Bayesian optimization acquisition function (AF) over mixed or high-cardinality discrete search spaces is challenging when the space is too large to enymerate directly. This is important because the theoretical regret bounds that come with certain AFs only apply if the AF can be maximized. The paper proposes to reparameterize the discrete parameters into probability distribution defined by continuous parameters, and then to maximize a probabilistic objective (PO) consisting of the expectation of the AF over those continuous parameters. The authors call this a probabilistic reparameterization (PR) of the AF. The paper then proves that maximizing this objective also maximizes the original AF, providing the same guarantees as maximizing the AF. They then derive unbiased and efficient Monte Carlo estimates of the PO and its gradients and show empirically that their method outperforms other mixed-variable optimizers on both maximizing the AF and the overall Bayesian optimization task. \n", "questions": "- In the middle and right panels of Figure 1, what does the color represent? I think it's the AF value, but in that case, why is it so different between the two panels?\n", "limitations": "The primary limitation is the computational cost of the MC estimation and maximization, which the authors address. This could be improved by explicitly stating the compute required for their experiments. ", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The idea of inducing a distribution with continuous parameters and then optimizing the expectation of the AF over the new parameters is both performant and elegant. It's the kind of solution that seems obvious once written down.\n- The paper addresses an important limitation when applying Bayesian optimization to many (most?) real-world problems. \n- The paper is well-contextualized in relation to previous work. \n- The writing is generally clear, and the importance of the theorems is easy to see. \n- The experiments seem sound, and the conclusions are supported by the results. \n\n## Weaknesses\n- I understand that there is limited space, but section 4.3 is very difficult to understand without a lot of prior knowledge.\n- The experiments would be stronger with comparisons to non-BO black-box optimization methods, such as evolutionary algorithms or to methods that use eg a VAE to embed the discrete variables into a continuous space. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KeM7YvVl1gs", "reviewer": "Reviewer_EFXz", "summary": "The paper addresses BO in mixed decision spaces, where part of the space is continuous and part is discrete. Namely, it focuses on the problem where the discrete space is large and cannot be exhaustively evaluated. The proposed strategy reparametrize the objective with a parametrized discrete probability distribution over the discrete decision space, which can be optimized using continuous optimization tools. Further extensions with MC sampling and extensive benchmark is provided. ", "questions": "- In Fig. 1, AF evaluates the expectation exactly? I would not expect there to be no spread if used with monte-carlo sampling.\n- Why not use Comsopolitan and HyBO on more realistic benchmarks? Could you not just add the constraint in the AF selection?\n- Why on Ackley PR-TR performs better?\n- Can in any of these experiments exhaustive search be performed? It would be nice to understand the effect of MC sampler. \n", "limitations": "1. The whole approach is sensible only if one of these two conditions are met:\na) mixed space. Let me denote the effort to optimize \\mathcal{X} given a specific z to B. If B*|\\mZ| is less than optimizing \\mathcal{Z}, \\mathcal{X} jointly with the Monte-Carlo or exact calculation\nb) discrete space, but very efficient evaluation of MC sampling exists \n\nMy conjecture is that b) does not occur in practice much, and a) can be indeed practical. \n\n2. Effect of MC sampling is not investigated in the experiments and in the motivating Figure. \n\n", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----------\n- I think this is a very practical algorithm if certain conditions are met (see Limitations). Authors identify problems where these conditions are met. \n- solid empirical analysis beyond the standards of the BO field. \n- optimization of AF is indeed an elephant in the room, nice to see that it is being recognized as a problem. \n\nWeakness\n---------\n- I feel the contribution to the field does not warrant publication at the most prestigious venue. I think people were aware of the reparameterization trick in this context. The problem with it is that for discrete spaces its complexity is larger than evaluating the whole \\mZ once. In mixed spaces, there are conditions where it could be better, but how much better is not addressed in this paper. \n- The paper cites a lot of by now folclore theorems, such as unbiasedness of monte carlo, SGD convergence and regret rates of algorithms depending on AF. I think the paper could be explained in 1 page and experiments take 2 pages, exactly suitable for a workshop paper. \n- The best performing algorithm PR+TR is not mentioned in the main text.\n- Convergence of SGD on the non-convex objective is also not ideal, but I guess this is not addressed in the paper since the “discrete part” is the challenge. But its good to point out that by creating a continuous relaxation not all issues are removed. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept