Constrained Two-step Look-Ahead Bayesian Optimization
Authors: Duke Zhang
Xiangyu Zhang
Peter I. Frazier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian optimization
Non-myopic
Gaussian processes
Derivative-free optimization

Abstract: Recent advances in computationally efficient non-myopic Bayesian optimization offer improved query efficiency over traditional myopic methods like expected improvement, with only a modest increase in computational cost. These advances have been largely limited to unconstrained BO methods with only a few exceptions which require heavy computation. For instance, one existing multi-step lookahead constrained BO method (Lam & Willcox, 2017) relies on computationally expensive unreliable brute force derivative-free optimization of a Monte Carlo rollout acquisition function. Methods that use the reparameterization trick for more efficient derivative-based optimization of non-myopic acquisition functions in the unconstrained setting, like sample average approximation and infinitesimal perturbation analysis, do not extend: constraints introduce discontinuities in the sampled acquisition function surface. Moreover, we argue here that being non-myopic is even more important in constrained problems because fear of violating constraints pushes myopic methods away from sampling the boundary between feasible and infeasible regions, slowing the discovery of optimal solutions with tight constraints. In this paper, we propose a computationally efficient two-step lookahead constrained Bayesian optimization acquisition function (2-OPT-C) supporting both sequential and batch settings. To enable fast acquisition function optimization, we develop a novel likelihood ratio-based unbiased estimator of the gradient of the two-step optimal acquisition function that does not use the reparameterization trick. In numerical experiments, 2-OPT-C typically improves query efficiency by 2x or more over previous methods, and in some cases by 10x or more.

Two-step lookahead Bayesian optimization with inequality constraints
Yunxiang Zhang Cornell University y22547@cornel1.cm edu
Xiangyu Zhang Comell University x25560cornel1.edd
Peter I. Frazier Coreell University
pf98@cornel1. edu
Abstract
Recent advances in computationally efficient non-myopic Bayesian optimization offer improved query efficiency over traditional myopic methods like expected improvement, with only a modest increase computational cost. These advances have been largely limited to unconstrained BO methods with only few exceptions which require heavy computation. For instance, one existing multi-step lookahead constrained BO method [1] relies computationally expensive unreliable brute- optimization Monte Carlo rollout acquisition function.
force derivative-Fi Methods that use the reparameterization trick for more efficient derivative- optimization of non-myopic acquisition functions in the unconstrained setting, like sample average approximation and infinitesimal perturbation analysis, do not extend: constraints introduce discontinuities in the sampled acquisition function surface. Moreover, argue here that being non-myopic even more important constrained problems because fear of violating constraints pushes myopic methods away from sampling the boundary between feasible and infeasible regions, slowing the discovery of optimal solutions with tight constraints. In this paper, we propose a computationally efficient two-step lookahead constrained Bayesian optimization acquisition function (2-OPT-C) supporting both sequential and batch settings. To enable fast acquisition function optimization, we develop novel likelihood- aatio-based unbiased estimator of the gradient of the two-step optimal acquisition function that does not use the reparameterization trick. In numerical experiments, 2-OPT-C typically improves query efficiency by 2x more over previous methods, and in some cases by 10x or more.
Introduction
We consider constrained optimization of continuous black-box function f under continuous black- box constraints y., minzes. / (xx) subject to yi (x) < 1,. within the compact design space A ACR.. Rd We suppose both f (xx and g: (x(x) are derivative-free, noise-free. Such problems arise, for example, in tuning hyperparameters of machine learning models subject to runtime or fairness constraints and policy optimization in reinforcement learning with safety constraints. For instance, neural networks deployed on mobile phones must be accurate but may also have limited computation available while needing to respond to users in real time, creating constraint how long the model takes predict test time (2]. Another example, from [3], is predicting recidivism risk in the criminal justice system with a faimesss constraint ensuring that false positive rates equal across racial and ethnic groups Other applications arise in drug discovery and aircraft design
and also
Bayesian optimization (BO) has proven successful at solving black-box optimization problems with expensive objectives 6 7) including constrained problems of the form above. BO methods for constrained problems include constrained expected improvement (EIC in [8) rediscovered
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

by 191, constrained BO with stepwise uncertainty reduction [10], predictive entropy search with
unknown constraints [M. Alternating Direction Method of Multipliers Bayesian optimizattion [[2]. constrained BO with max-value entropy search [3], and augmented I Lagrangian techniques that convert constrained problems into a sequence of unconstrained ones [14. It also includes methods designed specifically for equality and mixed constraints [5]. for batch observations [6] and for
problems with high dimensions [17].
All of these existing methods, however, for constrained Bayesian optimization (CBO), are myopic, in the sense that they only consider the immediate improvement in solution quality resulting from a function evaluation and ignore later improvements in solution quality enabled by this evaluation. (Notable exceptions are [ 18, discussed below.) This greedy behavior may hinder an algorithm's ability to find good solutions efficiently. While a recent flurry of activity is addressing this issue for unconstrained problems [19 20 22 23 and the performance improvements provided by these non-myopic algorithms for unconstrained BO suggest that non-myopic BO is promising for constraints as well, substantial non-myopic development has not reached the constrained setting.
Moreover, we argue in detail below that being non-myopic provides even more value in constrained settings than it does in unconstrained ones. To find a global optimum under constraints quickly, an algorithm benefits by efficiently learning the boundary between the feasible region where the constraint is satisfied and the infeasible region where it is not. This is facilitated by sampling points likely to be close to this boundary. Myopic methods. however, such as EIC, undervalue sampling such points because they have substantial probability of being infeasible and because infeasible points do not directly improve solution quality. Non-myopic methods, on the other hand, understand that learning about the boundary's ' location will provide future benefits, allowing them to value this information more appropriately. Localizing the boundary efficiently is especially important when the global optimum lies on this boundary, as it often does in constrained optimization when the objective (e.g., the quality of product) is negatively correlated with a constraint (e.g., the cost required to produce it). We illustrate this via simple example in $3 and our numerical experiments in $6, which show several-fold improvement over the Nfte-of-the-art in some problems.
One existing non-my non-myopic constrained BO method T first formulates CBO as a dynamic program (DP). However, this DP is intractable. To mitigate the issue, rollout, an approximate DP technique, is used. Nevertheless, this approach requires an extremely large amount of computation to approximate the multi-step lookahead policy well, especially in problems with more than a few dimensions, in part because it relies on computationally expensive derivative-free optimization, and because its acquisition function is computed via Monte Carlo, further increasing the computation required. This limits its applicability.
The constrained multi-information source BO method recently proposed by 18] is also non-myopic. It focuses on the multi-informationn source setting and assumes that the objective and constraint are evaluated in a decoupled fashion. In contrast, our applications of interest often compute the objective and constraints simultaneously. For example, when tuning ML hyperparameters to maximize accuracy subject to model execution time constraint, the marginal cost of evaluating accuracy is negligible once we evaluate model execution time and incur the training cost. Thus, a method that evaluates the objective and constraints in a decoupled way discards information in such settings.
Our Contributions. We provide novel non-myopic computationally efficient method for batch CBO. It substantially outperforms myopic CBO methods. In relation to [ it requires substantially less computation decide where to sample. Its query efficiency is substantially better in relatively higher-dimensional problems and is at least as good in lower liver-dimensional ones.
The key to our approach is a new method for optimizing stochastic acquisition functions, leveraging the likelihood ratio method [24]. Standard efficient approaches to optimizing stochastic non-myopic acquisition functions, such infinitesimal perturbation analysis (IPA) (25) or the one-shot method 26 (also called sample average approximation or SAA), rely on a sampled acquisition function surface created using the reparameterization trick. In CBO, however, this surface is discontinuous, preventing the efficient use of these methods. Our novel approach is potentially generalizable to other settings where such discontinuities prevent the use of IPA and one-shot optimization.
Our work builds on the unconstrained two-step optimal method (21), overcoming substantial com- putational difficulties created by constraints' inherent discontinuities. These difficulties require abandoning the IPA approach used in [21] and instead developing a new likelihood- ceteoodddrrttt-b-bsseee based
2

---

approach. The likelihood ratio method that we use here to estimate the gradient of the acquisition function relies on change of measure of the same type used within importance sampling. [2T coincidentally also uses importance sampling, but in a fundamentally different way: as a variance reduction technique, and not for gradient estimation.
2
Background
We briefly review the literature on myopic CBO. Then we summarize standard results needed later on Gaussian processes and the widely used myopic method EIC as well as its batch version.
2.1 Myopic Constrained Bayesian Optimization
This work builds on the larger literature on myopic CBO. We review this literature here, giving more details than in $1. [9] proposes constrained expected improvement, a weeghte expected improvement acquisition function which multiplies the expected improvement with the probability
of feasibility associated with each constraint, rediscovering an approach due [. (27 proposes
an approach in which the point to sample is found by maximizing EIC and then a decision is made
whether to evaluate the objective or the constraint based on the information gain. [10] proposes stepwise uncertainty reduction method in which the acquisition function aims to maximally decrease our uncertainty on the location the optimizer with a single evaluation. Predictive entropy search with constraints (PESC) [ an extension of predictive entropy search [28 is another information- gain based approach. It chooses the point to evaluate by approximating the expected information gain on the value of the constrained minimizer. [14] proposes hybrid approach combining the expected improvement with an augmented Lagrangian framework. [I5] extends this technique by introducing an alternative slack variable formulation that handles equality and mixed constraints. Integrated expected conditional improvement (IECI) [29] proposes a new acquisition function that integrates conditional improvement with respect to reference point the design space. [16] develops quasi-Mone Carlo approximation of expected improvement under batch optimization with noisy observations and noisy constraints. [13] modifies the mutual information criterion of max-value entropy search (30] and extends to the constrained setting with the ability to handle both continuous and binary constraints. [12] leverages the ADMM framework convert constrained problems into multiple unconstrained subproblems by introducing auxiliary variables for each constraint, then solves the subproblems using standard BO. Similar TuRBO (31), [17] proposes an acquisition function for constrained optimization that scales to high dimensions by maintaining and adjusting trust regions.
2.2 Gaussian Processes
BO makes productive use of Gaussian processes (GPs) (32]. We put a GP prior on the objective function f. which is specified by mean function pd-) and kernel function (-,-). After observing
the data points D = (1) (2) (2), ,..., _a))) } and their corresponding function values J(D) (f(x))), f(x(3)) ..... f..())) the GP prior over is updated by:
(()) ~ N (m(a; D), ox; D))
where plz; D) is the posterior mean and (I;; D) is the posterior standard deviation. μ(D) is the set of values of the prior mean function evaluated at points in D.
While support multiple constraints, focus single constraint g for ease of presentation. We use (-) and (-(..)) to denote the mean function and the kernel of the independent GP prior on respectively, and j (2; D) and (x;; D) denote the mean and standard deviation of the posterior. We refer readers to the supplement for multiple constraints.
2.3 Constrained Expected Improvement
We briefly review constrained expected improvement (EIC) 9 8 introducing notation used later. Suppose we have independent GP priors on f and g and observations S(D) = {f(x) : E D} and g(D) = (g(x) x e D} collection of datapoints D. Let f be the best point observed so far

---

subject to our constraints, f min f(z). The constrained expected improvement at r is:
EIC(#) = BB [(=) (g(x)) - 0)] B - f(a)]* + B()(o(a) < 0}} = Bl(a)) PF(x),
(1)
where [[[] the expectation taken with respect to the posterior given D. J(D,, and gDD). EI(x)) and PF(x)) are the expected improvement and the probability of feasibility at respectively, and both have analytic forms. Here, we assume the prior on and g are independent as in [9] We refer readers to (33 and [9] for more details.
We now define EIC the batch setting, building on the first discussion of which we are aware [16 Let X (æ(n+1) (x(+2) (n(++)) } be the batch of candidate points that consider evaluating next. Then the constrained multi- tallii-poins expected improvement EIC(X) (C) is,
EIC(X)
max x
(f (f=)
1 s =0]
The details of the derivation of (X) are provided in the supplement.
3 Constrained Two-step Acquisition Function
In this section, we first show that why being non non-m non-myopic is important in CBO. Then we formally define the novel acquisition function 2-OPT-C that is at the heart of our method.
3.1 The Importance of Being Non-Myopic in CBO
Figure I: EIC and 2-OPT-C optimizing a 1-d synthetic function. The first three graphs of each row the posterior on f. the posterior g, and the acquisition function under EIC, and the last three graphs are the corresponding quantities under 2-OPT-C. Each row shows one iteration, proceeding from the first iteration at the top to the last iteration at the bottom. In the plots of the posterior on and g. "x" denotes infeasible points and square denotes feasible points. The constraint threshold (0) plotted as red line. The red dot the point newly sampled in the current iteration. 2-OPT-C explores potentially infeasible points more aggressively and discovers a better feasible point.
Before presenting out non-myopic acquisition function, 2-OPT-C, we give intuition for why being non-myopic even more important constrained problems than it unconstrained ones. Suppose the constraint function value of the (unobserved) best feasible point is equal or close to the constraint threshold. To find this point with as few function evaluations as possible, the algorithms need to efficiently learn the feasible region's 's boundaries. This happens most quickly when evaluating points close to this boundary. Since the boundary is uncertain, this requires an algorithm to be willing to evaluate points that may be infeasible. However, the value of such points to myopic CBO algorithms like EIC significantly reduced because the probability of infeasibility is high - typically near 50%, lowering the PF(x) term in T). Thus, myopic CBO algorithms may insufficiently explore the boundary, instead sticking well inside the feasible region.
Figure lusttraess this with an example. On the first iteration, EIC evaluates point in region around an existing feasible point that likely feasible, getting a small one-step improvement but little information f and g for future evaluations. However, 2- 2-PPT-C (defined below) explores more

---

aggressively. The point it evaluates is not feasible but provides a significant amount of information about the boundary between the feasible and infeasible region. As a result, after progressing two steps, 2-OPT-C locates a new feasible point (g(x)) = -0.02) with much lower objective function value while EIC remains stuck near the previous feasible point.
3.2 Definition of 2-OPT-C
We define our two-step optimal acquisition function for CBO, called 2-OPT-C, for both sequential and batch settings, and then discuss its computational optimization in $7 As in other CBO methods, we sequentially evaluate f and g next at the point that maximizes our acquisition function. This point optimal measure now assuming we will be able to measure one additional point before being awarded the maximum value found over the two new measurements and in our previously collected data. In other words, 2-OPT-C looks two steps ahead instead of the ene-step ahead considered by myopic methods. For clarity, we assume a single constraint and treat multiple constraints in the supplement.
In the batch setting, we find the batch of q points to measure next assuming we will then measure one additional point before being awarded the best value found. We assume only one additional point rather than a full additional batch for computational tractability. We argue that even the single additional point allows 2-OPT-C to think non-myopically and to value information about the feasible region that will only be acted on later.
We first define notation. We use subscripts {0, 2, to denote stages. Stage O is the current stage when we will evaluate a batch of points. In stage I, we will evaluate one additional point based on the results of stage and then in stage 2 will be judged based on the best of these points evaluated. We put independent GP priors on f and g. Let D be the collection of data points that we have observed so far. Then given the information in D and their corresponding objective f(D) and constraint g( D) values, the posterior distribution on the objective f is a Gaussian process with a mean function μo and kernel Ku. Similarly, the posterior distribution on the constraint g is also Gaussian process with a mean function ' and kernel KG. Eg denotes taking the expectation with respect to the posterior distributions given D.
Let fö be the best evaluated point satisfying the constraint so far, i.e. fö min ((x). Let X1 be the set of candidate points that consider evaluating at the first stage and let Y {f(x) : x E {1} and Y, = {g(x) I E {1} be the sets of corresponding objective function values and constraint values respectively. We let M1. ff and K1, Kí denote the mean function and kernel for the posterior distributions of f and g respectively given D) and X1. Let (ar) / (x, x) and of(x) = v Kf(x, 2). Let E, indicate the expectation with respect to the corresponding Gaussian processes given both D and X,. Finally, we use x2 to denote single point to be evaluated in the second stage, based on the results of the first.
Let ff and ft be the best evaluated feasible point by the end of the first and second stage respectively, ft = min min)ex; fz)) and fi = min (ft. (x2)) if g( S and f2 = ft not.
Following the principle of dynamic programming, our goal is to choose X, to minimize the overall expected objective (fz) This is done under the assumption that 22 will be chosen optimally leveraging observations of X₁. Equivalently, our goal is to maximize
Eo max Is -22 = Eo -i-st max - [2] 22
over X1 chosen in the first stage. Efffi - fi] depends implicitly on the information obtained from X1, which is Yy and Yg. and is included in the posterior over which E, is taken.
Thus, we define the constrained two-step acquisition function:
2-PTT-C(X)) = Eo fō - fi max E, [fi fā1
22 A(6)
where A(8) is compact subset of A consisting of points at least 5 away from sampled points in DUX, X1. With 0, A A(8). We introduce the parameter 8 2 0 purely to overcome a technical hurdle in our theoretical analysis: that the standard deviation of the posterior distribution is not smooth at sampled points. We believe can be set to 0 in practice. Indeed, the theoretical analysis (Theorem I allows setting 8 at any arbitrary small positive value.
5

---

For use in $4 we derive a more directly computable expression for 2-OPT-C(X1). We rewrite
2- 2-OPT-C(X;) Eo
max (2EA(()
f
f
B1 fi
Eo
max a a(X1, x y) (cEA(())
where Y = (Y,, Yg) ~ X1) and p(u: X1) is the distribution of Y given f(D) and 9
specified explicitly as
P(y: = -(( x (16(X))
[X)
X1(
0 K8(X1, 1)
(3)
Then, a(,,, Y) can be written in closed form:
a(X1, #2, Y) = So fT+EI(Si - (1(22),, where Em v) mm mmmmm////////mmmmmm VV) + Vop(m// vV) and PF(m*, 09) 1 (-m²) poml/vo))
4 Optimizing 2-OPT-C Using Likelihood Ratios
Evaluating 2-OPT-C(Xi) requires performing a simulation where each replication samples Y and then evaluates mäX22 E A(8)a((1) 22, Y). Averaging these replications gives Monte Carlo estimate of 2-OPT-C(X Optimizing 2-OPT-C(Xi) using such Monte Carlo estimates is difficult because of noise from simulation and because there
straightforward way to obtain derivatives.
Indeed, we show in the supplement that the two widely used approaches to efficiently optimizing Monte Carlo acquisition functions, IPA and SAA, fail to optimize 2-OPT-C well because constraints cause discontinuities in the surface they sample using the reparameterization trick.
Here, we develop novel approach for optimizing Monte Carlo acquisition functions like 2-OPT-C without using the reparameterization trick, overcoming the challenges created by these discontinuities. This approach uses the likelihood ratio method to derive unbiased estimator of the gradient for 2-OPT-C. We then use this novel estimator in multistart stochastic gradient ascent to maximize 2-OPT-C. (For details multistart stochastic gradient ascent for maximizing Monte Carlo acquisition function, see [34.) To the best of our knowledge, we are the first to demonstrate the benefits of the likelihood ratio method for acquisition function gradient estimation in BO.
4.1 Background on the Likelihood Ratio Method
We first give background on the likelihood ratio method using generic notation before describing how we use it in our setting. Given generic random variable ((x) whose distribution depends on a control vector x with density p(0; .²) and function Vax, (z)). our goal solve max, E[V (a,, ((z)). To do this, we estimate the gradient of [V[(x, ((x)) ] for use within multistart stochastic gradient.
To provide this gradient estimator, which {0 p(0,2) x) > 0} C {0 p(0) > 0} for all æ. Using this density, we construct the likelihood ratio, L(0; x) p(0;)))0000)) x((() We then have that
first choose density f(0) that does depend and for
(IV,,,(()))) / V(x,0) p(0:z) do f V(z, L(0; x)p(0) d8.
This is referred as importance sampling and is referred as the importance sampling distribution. The likelihood ratio method uses this expression to construct gradient estimator. Under regularity conditions (35) exchange the gradient operator and integration,
V [[ V. / V(s, 0) L(0: (0)) d0 / V.V(2, I(0:)))))
From this create unbiased estimator of the gradient of EVV ((x)) by sampling from the density p(0) and returning as our estimator Vz, L(;
A natural choice for the importance sampling distribution suggested in 224 is to take p(0) p0 .)) when estimating VV (<))) at x = We make this choice when designing an unbiased gradient estimator for 2-OPT-C, We discuss this in detail later in $42

---

4.2 Optimizing 2-OPT-C
To apply the likelihood ratio method develop gradient estimator for 2-OPT-C, we begin by rewriting the expression to be differentiated using importance sampling.
Mapping the notation of our generic discussion of importance sampling onto specific problem, our control a is the batch of points 11, our random variable Y (whose distribution depends on X1), and V (zz, 0) maX,2 a(X1, 42, ). Y a multivariate normal random variable whose density we write ply: X1), noting that its mean and covariance matrix are determined by X1, We let p(y: X1) be our importance sampling density for Y. for some fixed point X1 X, is arbitrary for now but is specified below. Our likelihood ratio then L(y: X1, = p(y; X1) p)(();(())))
As discussed above, the key step in the likelihood ratio method is to interchange the integral and gradient operator. This is justified our setting by Theorem[[bel The proof is provided in the supplement. As result, we have
Vx, 2-PT-C((1)) - N..
(4)
where
T(X1, X1,1, :
LV; X1, xi)
max (2EA(6)
=[Vx,a(X1 22 Y)] Lyy X1, X1) + (X1,, Y) [V,, Xi)l /ply: X1)
with z E arg ma a(X,, Y). The last equality is by the envelope theorem [66, i.e., max 22, Y) can be differentiated with respect X1 by first optimizing over 222 given X1, then holding zł fixed while differentiating with respect to X1. From now on, we will drop the subscript of the differential operator V for simplicity.
By (4). T(X1, XI, Y) an unbiased estimator of V 2-OPT-C(Xi) when Y is drawn according to ply; X1). With this stochastic gradient estimator, we then can use stochastic gradient ascent [37] with multiple restarts to find a collection of stationary values for X1. Then we use simulation to evaluate 2-OPT-C(A ((X; at these values and select the one with the highest estimated 2-OPT-C. This then provides a computationally efficient algorithm for optimizing 2-OPT-C. Pseudocode for using 2-OPT-C is provided the supplement.
As discussed above, the key step to developing our unbiased estimator is to interchange the integral and gradient operator, which is justified by Theorem Thelow. The proof is provided in the supplement. Although Theorem I Jassumes > O, in practice, we choose 8 = 0 in our stochastic gradient estimator.
Theorem 1. We assume:
1. The prior on the objective function f is Gaussian Process f f~ (P( and the prior on the constraints g is another Gaussian Process GP K K,), (z,x²)) These Gaussian processes are independent.
2. μj and Pg continuously differentiable with z.
3. (z)xxx") and (z(2,²²) x') is continuously differentiable with and x'.
4. Given different points X (21, ..,, the matrix Ky X) and Kg(X,X) are of full rank.
Then 2-OPT-C(Xi)'s partial derivatives exist almost everywhere for any > 0. When 2-OPT-C(Xi) is differentiable.
V2-OPT-C(X.)= X(
Choice of Importance Sampling Distribution We have constructed an estimator of the gradient V2-OPT-C at X1. This estimator was constructed using an importance sampling distribution parameterized by X1. We are free to choose this X₁ wish. We recommend setting X, equal

---

to X1, as our gradient estimator takes particularly simple form and offers robust performance. In particular, when X1 X1, Lyy; X1, X1) 1, our gradient estimator is
T(X1, X1, =- al X1, 22. v) Vvly; X1)) /plu: /pllssx)) Xi) + VV((X1,22.10
where zá E arg max,, al a(X1, 22, v).
5 Numerical Experiments
This section numerically investigates our algorithms problems widely used as benchmarks in the constrained BO literature. Benchmarks demonstrate that 2-OPT-C usually provides significant improvements in query efficiency over state-of-the-ar methods. In the main paper, we focus on query efficiency for the sequential setting. The supplement includes additional experiments and discussions of batch evaluations and 2-OPT-C's computational overhead.
The benchmark problems include three synthetic problems from 0. named P1, P2, and P3, and two real-world problems, portfolio optimization and robot pushing. Detailed descriptions are in the supplement. We use these five problems in comparisons with myopic methods in $5.2 In $5.3 we compare with the non-myopic method from []]. Since code for [ was not available, we compare 2-OPT-C against the results previously published in that paper, consisting only of P1, P2, and P3.
5.1 Experiment Setup
Evaluation Metries We follow [1] in our evaluation methodology- Along with each evaluation n each algorithm makes a "recomendation", which the point we would evaluate if it were our last evaluation before being scored by the best point evaluated. From this recommended point, compute a score / for this algorithm in this timestep n. If the recommended point feasible, then fü is its objective function value. If not, ft"" is the best observed feasible value so far before the recommended point. Following [II. the point recommended is the one with the lowest posterior mean objective value, among those whose probability of satisfying each constraint is 0.975 or better. We then report the utility gap, e, = lfft f*1. which is the difference between this score and the global constrained optimum f We report the log 10 median utility gaps for P1, P2, P3, and the robot pushing problem in the main paper. Mean utility gap results are provided in the supplement. In the portfolio optimization problem, the optimum is unknown rate instead of the utility gap.
report the mean annualized return
Setup for $5. The 2-OPT-C implementation uses GPs with constant zero-mean prior and ARD square-exponential kernels for both objectives and constraints. GP hyperparameters are obtained by maximizing the marginal likelihood using GPy 38 SAA+CMA ES implemented similarly to 2-OPT-C and all the hyperparameters are the same or obtained in the same way as 2-OPT-C.
For all three synthetic problems (P1, P2, and P3), run 150 experiment replications for all algorithms. For the two real-world problems (portfolio optimization and robot pushing). we run 50 experiment replications. For the initialization of each experiment, with at least one feasible point from a Latin hypercube design. We run N = 40 function evaluations for Pl and P2. N 60 for P3, N 30 for portfolio optimization problem, and N 50 for robot pushing problem. We use batch size of 1 for all five experiments.
randomly sample three points
Setup for $5.
The setup for $5.3 is nearly the same as for 5.2 with three key differences. These arose from the need to replicate the experimental setup from
First, we run 500 experiment replications. Second, rather than initial points per problem, we use 1. Third, the evaluation method differs slightly. If the recommended point is infcasible, then rather than setting frr to the value of the best previously observed feasible point, we set it to the maximum of the objective function over all points in the domain, thus enforcing substantial penalty.
5.2 Comparison with Myopic Methods
Figure first compares the myopic methods ADMMBO 12]. BO_Slack 15
NEI 16 EIC 9
and PESC | on three synthetic problems. In general, O-PT offers significantly lower median
8

---

Figure 2: Log10 median utility gap Random Search, ADMMBO, BO Slack, NEL, EIC, PESC, CMAES, and 2-OPT-C with 95% confidence intervals for problems P1, P2, and P3.
FORTSE COR
Figure 3: Real-world experiment results on Random Search, NEI, EIC, PESC, and 2-OPT-C. We report the mean annualized return rate for portfolio optimization problem and log10 median utility gap for robot pushing problem.
utility gaps than the myopic methods across all three problems. For example, in P1, 2-OPT-C quickly converges to a utility gap 10-5 (in 27 evaluations), while the best of the other benchmarks (EIC) has utility gap of 10 at this many evaluations. There is only one method and problem, ADMMBO on problem P3, in which myopic method achieves an optimality gap comparable to 2-OPT-C, but 2-OPT-C reaches this optimality gap in fewer iterations.
Figure additionally compares with an SAA implementation of 2-OPT-C that uses CMA-ES 39 to optimize the SAA to the acquisition function on Pl, P2, and P3, denoted as SAA CMAES. We see that SAA CMAES generally perform better than myopic policies on all three problems (except EIC on PI), supporting the value of two-step lookahead for CBO over myopic approaches. However, due the discontinuity introduced by SAA, underperforms 2-OPT-C on all three synthetic problems. It also underperforms EIC in P1 and ADMMBO in P3. In addition, it requires substantially more computation. This is because, as we note in the supplement, discontinuities the SAA to the acquisition function make it extremely difficult to optimize. We provide additional experiments to illustrate this in the supplement.
Figure 3 compares 2-OPT-C with the mostly widely-used myopic methods, NEI, PESC, and EIC, on real-world problems. As in the synthetic problems, 2-OPT-C outperforms --OPT-Couperfomms the competing benchmarks. In portfolio optimization, 2-OPT-C provides roughly 0.5% more annualized return than the best myopic method (EIC). robot pushing, 2-OPT-C outperforms EIC and NEI over the full range of function evaluations; PESC eventually matches 2-OPT-C but there is range of function evaluations where 2-OPT-C performs strictly better.
5.3 Comparison with the Non-myopic Method
We compare 2-0PT-C with the non non-myopic rollout algorithm of [ on the three synthetic problems based on the results reported in their paper. We use the terms Rollout-1, Rollout-2, and Rollout-3 to denote this algorithm with horizons of 1, and respectively.
To compare with the rollout algorithm, we extract experimental data from I and replicate their experimental setup, adding 2-OPT-C's results their Figures 2 and 3.
Figure Figure(4report reports the results of these comparisons. shows that 2-OPT-C provides query efficiency that is at least good as the non-myopic rollout methods with different horizons all three problems and is sometimes substantially better. detail, for P1, 2-OPT-C increases solution quality by more than factor of 2 (10 (10-1.59) /1001192 compared to the best rollout strategies, i.c., Rollout-1. For P3,

---

3.0
2.4
Log33 Modan USKY Cap
22
-24
Logis
20 on Evals
Function Evols
Function Evals
Figure 4: Log10 median utility gap of 2-OPT-C and the existing non-myopic constrained BO algorithm with different rollout horizons on PI, P2, and P3. The three lines of the rollout algorithm extracted from Figure 3 in [1. Additional information is provided in Table 1 in the supplement.
2-OPT-C is able to improve solution quality the best competing rollout method by roughly factor when the evaluation budget is tight (after 30 function evaluations).
2-OPT-C also uses less computation than the rollout algorithm [] publicly available, we refer to discussion in (21) the computational time of an unconstrained version of the rollout algorithm, which we understand from private communication has similar cost to M This states that the unconstrained rollout strategies require from 10 minutes to hour to evaluate a single point even since we need separate GP to model the constraint function. 2-OPT-C CC is more computationally efficient. On P3, for instance, 2-OPT-C optimizes batch of points in 25-30 minutes.
Since the code from [ is not
low-dimensional problem. This may be even larger in constrained settings,
R actually attempting to optimize the same theoretical acquisition function used by 2-OPT-C. Indeed, [1] uses EIC as its rollout strategy, which is optimal over horizon of h = 1. Rollout-1 then trying to identify the point to evaluate now that would be optimal if one additional point were evaluated after using EIC. If this point could be found exactly, it would be 2-step optimal.
Despite attempting to optimize an acquisition function that is conceptually the same as 2-OPT-C, -C, the performance of Rollout- is substantially worse (the utility gap is roughly 2x larger over all budgets), despite requiring more than double the computation. This because [I] optimizes this two-step acquisition function without the type of derivative estimates provided by our likelihood ratio method.
6
Conclusion
This paper presents non-myopic CBO algorithm, supporting both batch and sequential settings, that substantially improves both query efficiency and computation time over the one previous method focused on this class of problems for both sequential and batch settings.
While our method offers significant improvements in query efficiency compared to the state-of-the-ar that more than offset computational expense, there are likely more opportunities for reducing its computational cost. This, well as further theoretical investigation regarding our method providing such significant improvements in query efficiency compared to other methods, presents valuable directions for future work.
Faster constrained optimization of fime-consuming-t--vvaaee functions with our methodology enables creation of new engincering systems, better supervised learning methods, and lower-cost business operations. While we believe technological innovation is on balance good, new technology created using our methods also has the potential for negative effects. Understanding the societal effects of improved optimization capabilities is an important area for future research.
Acknowledgements
The authors were partially supported by AFOSR FA9550-19- 19-2-2 and FA9550-20-1-0351.
10

---

References
[1] Remi Lam and Karen Willcox. Lookahead bayesian optimization with inequality constraints.
I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 1890-1900. Curran Associates, Inc., 2017.
[2] Scott Clark and Patrick Hayes. Sigopt web page. https://sigopt..om.
[3] Valerio Perrone, Michele Donini, Muhammad Bilal Zafar, Robin Schmucker, Krishnaram Kenthapadi, and Cédric Archambeau. Fair bayesian optimization, 2021.
[4] John D. Trawick and Christophe H. Schilling. Use of constraint-based modeling for the prediction and validation of antimicrobial targets. Biochemical Pharmacology, 71(7):1026 1035, 2006. Special Issue on Antibacterials.
[5] Berk Ozturk and Ali Saab. Optimal aircraft design deicions under uncertainty via robust signomial programming. In AIAA Aviation 2019 Forum, page 3351, 2019.
[6] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advunces in Neural Information Processing Systems, volume 25, pages 2951-2959, Curran Associates, Inc., 2012.
[7] Peter Frazier. A tutorial bayesian optimization. arXiv preprint arXiv: 1807.02811, 2018.
[8] Matthias Schonlau, William Welch, and Donald R. Jones. Global versus local search in constrained optimization of computer models. Lecture Notes-Monograph Series, 34:11-25, 1998.
[9] Jacob R. Gardner, Matt J. Kusner, Zhixiang Xu, Kilian Q. Weinberger. and John P. Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conference International Conference Machine Learning Volume 32, ICML' 14, pages 11-937-1--945. JMLR.org, 2014.
[10] Victor Picheny. A Stepwise uncertainty reduction approach constrained global optimization. In Samuel Kaski and Jukka Corander, editors, Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statisfies, volume 33 of Proceedings of Machine Learning Research, pages 787-795, Reykjavik, Iceland, 22-25 Apr 2014. PMLR.
[11] Jose Miguel Hernandez- Michael Gelbart, Matthew Hoffman, Ryan Adams, and Zoubin Ghahramani. Predictive entropy search for bayesian optimization with unknown constraints. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1699-1707, Lille, France, 07-09 Jul 2015. PMLR.
[12] Setareh Ariafar, Jaume Coll-Font, Dana Brooks, and Jennifer Dy. Admmbo: Bayesian op- timization with unknown constraints using admm. Journal of Machine Learning Research, 20(123):1-26, 2019.
[13] Valerio Perrone, Iaroslav Shcherbatyi, Rodolphe Jenatton, Cedric Archambeau, and Matthias Seeger. Constrained bayesian optimization with max-value entropy search. arXiv preprint 111.001910.07003, 2019.
[14] Robert B Gramacy, Genetha A Gray, Sébastien Le Digabel, Herbert KH Lee, Pritam Ranjan, Garth Wells, and Stefan M Wild. Modeling an augmented lagrangian for blackbox constrained optimization. Technometrics, 58(1): 2016.
[15] Victor Picheny, Robert B Gramacy, Stefan Wild, and Sebastien Le Digabel. Bayesian op- timization under mixed constraints with a slack-variabl augmented lagrangian. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, pages 1435-1443. Curran Associates, Inc., 2016.

---

[16] Benjamin Letham, Brian Karrer, Guilherme Ottoni, Eytan Bakshy, et al. Constrained bayesian optimization with noisy experiments. Bayesian Analysis, 14(2):495-51, 2019.
[17] David Eriksson and Matthias Poloczek. Scalable constrained bayesian optimization. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 730-738. PMLR, 13-15 Apr 2021.
[18] Seyede Fatemeh Ghoreishi and Douglas Allaire. Multi-information source constrained bayesian optimization. Structural and Multidisciplinary Optimization, 59(3)977-991,, 2019.
[19] Remi Lam, Karen Willcox, and David Wolpert. Bayesian optimization with a finite bud- get: An approximate dynamic programming approach. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances Neural Information Processing Systems, vol- ume 29, pages 883-891. Curran Associates, Inc., 2016.
[20] Javier Gonzalez, Michael Osborne, and Neil Lawrence. Glasses: Relieving the myopia of bayesian optimisation. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the I 19th International Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 790-799, Cadiz, Spain, 09-11 May 2016. PMLR.
[21] Jian Wu and Peter Frazier. Practical two-step lookahead bayesian optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Gamettt editors, Advances in Neural Information Processing Systems 32, pages 9810-9820. Curran Associates, Inc., 2019.
[22] Shali Jiang, Henry Chai, Javier Gonzalez, and Roman Garnett. BINOCULARS for efficient, nonmyopic sequential experimental design. In Hal Daumé III and Aarti Singh, editors, Proceed- ings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4794 4803. PMLR, 13-18 Jul 2020.
[23] Shali Jiang. Daniel Jiang, Maximilian Balandat, Brian Karrer, Jacob Gardner, and Roman Garnett. Efficient nonmyopic bayesian optimization via one-shot multi-step trees. Advances in Neural Information Processing Systems, 33, 2020.
[24] Søren Asmussen and Peter W. Glynn. Stochastic simulation algorithms and analysis. In Stochastic modeling and applied probability, 2007.
[25] Philip Heidelherger, Xi-Ren Cao, Michael Zazanis, and Rajan Suri. Convergence properties of infinitesimal perturbation analysis estimates. Management Science, 34: 14:12-1-3 11 1988.
[26) Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Eytan Bakshy. Botorch: A framework for efficient monte-carlo bayesian optimization. arXiv preprint arXiv:1910.08 064000,,6633 2019.
[27] Michael A Gelbart, Jasper Snoek, and Ryan Adams. Bayesian optimization with unknown constraints. arXiv preprint arXiv: 2014.
[28] José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. pages 918 918-926. Curran Associates, Inc., 2014.
[29] Robert B. Gramacy and Herbert K. H. Lee. Optimization under unknown constraints. Bayesian Statistics 9 (2011), no. 9, 229. eds.
[30] Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3627-3635. PMLR, 06-11 Aug 2017.
[31] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Mathias Poloczek. Scalable global optimization via local bayesian optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, Aluhé-BBu,, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
12

---

[32] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[33] J. Mockus, On bayesian methods for seeking the extremum. In Marchuk, editor, Optimiza- fion Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974, pages 400-404, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.
[34] Jialei Wang, Scott Clark, Eric Liu, and Peter Frazier. Parallel bayesian global optimization of expensive functions. Operations Research, 68(6): (600):1850-00 1850-1865. 2020.
[35] Pierre L'Ecuyer. unified view of the ipa, sf, and gradient estimation techniques. Management Science, 36(1 1):1364-1383, 1990.
[36] Paul Milgrom and Ilya Segal. Envelope theorems for arbitrary choice sets. Econometrica. 70(2):583-601, 2002.
[37] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[38] GPy. GPy: A gaussian process framework in python. http://ggttuu...cm//hhfflllll GPy since 2012.
[39] Nikolaus Hansen. The ema evolution strategy: comparing review. Towards a new evolutionary computation, pages 75-102, 2006.
13


Reviews:
[{"review_id": "j612djtZOA", "reviewer": "Reviewer_F2Td", "summary": "This work suggests a two-step lookahead Bayesian optimization strategy in the presence of inequality constraints, which is non-myopic and computationally efficient. The previous work [1] applies unreliable derivative-free optimization of acquisition function in such a constrained optimization problem, but the method proposed in this paper lets us to leverage a gradient-based optimization framework in a two-step lookahead Bayesian optimization strategy. Moreover, the proposed method supports either a sequential setting or a batch setting. Finally, the authors show the differentiability of the proposed acquisition function and experimental results.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper solves an interesting topic, which can be applied in many practical scenarios in the presence of constraints. Considering a constrained optimization problem with a non-myopic approach is pretty important and the method using a gradient-based optimization framework has the advantage of computational efficiency. My only concern is about numerical experiments. I think real-world experiments should be added in order to demonstrate the usefulness of the proposed method.\n\nPros\n\n+ Interesting topic.\n+ Well-written and well-organized paper.\n+ Clear description of contributions\n\nCons\n\n- No real-world experiments.\n\nDetailed Comments\n\n1. I would like to see the benefit of the proposed method in terms of computational cost, compared to other existing methods.\n2. How many times did you repeat the experiments? I cannot find it in the paper.\n3. I would like to ask if non-myopic approaches are always better than myopic approaches. I do not think that it needs to describe in the paper, but I was just curious about it.\n\nMinor issues\n\n* In Line 123, q should be $q$.\n* For Equation (2), a period should be added.\n* For the equations in Line 155 and Line 161, commas should be added.\n* In Line 191, q should be $q$.\n\n[1] R. Lam and K. Willcox. Lookahead Bayesian optimization with inequality constraints. In Advances in Neural Information Processing Systems, volume 30, pages 1890–1900, 2017.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not have any comments on limitations and societal impact. Please see \"Main Review\" for the detailed reviews.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "bAxdBFXjA3", "reviewer": "Reviewer_vkHd", "summary": "The paper studies look-ahead Bayesian optimization (BO) under inequality constraints. The authors\ndevelop a principled acquisitions for two-step look-ahead and motivate why it is necessary, especially\nin the constrained setting. They propose a method to optimize the acquisition based on an importance\nsampling strategy and evaluate the approach against other methods on 3 synthetic problems.\n\nWhile this direction of research is promising, I do not believe the paper is ready for publication\nyet at Neurips.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The paper does not do a good job of motivating the problem. The authors mention two applications\nin passing in lines 26/27, without sufficient explanation. For instance, can you give some concrete\ninstances where people have maximized model accuracy under run time and fairness constraints? What\nwould the fairness constraints look like?\nIn any case, you should delve deep into one or two of these examples, explain the reasons for the\nconstraints clearly, and cite other sources which have used such methods. **\n\n2. My main concern with the paper is its empirical evaluation. For a paper where the focus is on\nmethod and evaluation (as opposed to theory), one expects a more beefed up empirical evaluation.\nThis includes 1-3 real benchmarks which ideally arise out of motivating applications, more baselines,\nand ablation studies.\n- The authors have cited a bunch of papers in 2.1 and you should evaluate your method against them.\n  It is also usually a good idea to compare against random search when evaluating BO methods. Right\n  now, the paper has just 2 myopic baselines and 1 non-myopic baseline.\n- It is hard to make sense of Table 1 where all results except for 2-OPTC is obtained from another\n  paper. BO methods tend to be quite sensitive to hyperparameter choices so it is not clear if the\n  hyperparameters were set the same way. On the same note, how did you choose your GP\n  hyperparameters?\nIn its current form, the empirical evaluation does not make a strong case for its use in practice.\nHaving one or two compelling real benchmarks would also address 1 above, as it will motivate the\nsetting well.\n\n3. The claim that all BO methods are myopic is misleading. While EI is admittedly myopic,\nmethods such as UCB and Thompson sampling are known to optimally balance exploration and exploitation\nto optimize a function over several rounds. The authors' method essentially corrects the EI\ncriterion to work in this setting. I acknowledge that UCB methods are trickier to apply in the\nconstrained setting, there is a simple and intuitive TS implementation (simply sample from f and g\nconditioned on the posterior, say f', g', and choose the maximizer of f' under the g'>0 constraint).\n- On this note, you could also include TS as a potential baseline in your evaluation.\n\nOther comments/suggestions\n- I liked Figure 1 and the explanation that follows on why look-ahead is especially important in\n  constrained BO. It would recommend bringing this early on to motivate the method.\n- You might want to consider including a separate Related work section. Right now, parts of it is\n  included in the middle of the introduction, and parts in Section 2.1. A separate Related work\n  section, allows a reader to quickly locate and identify how your work is different from prior\n  work.\n- Don't use citations as nouns in a sentence. E.g. in line 90, use \"XYZ et al. propose ..\" instead\n  of \"[5] proposes ..\". This can be achieved via the \\citet latex command.\n- Do you have only one inequality constraint or multiple? Line 24 says multiple, but later on in the\n  text, you use only 1.\n\nPS:\n** One application that I have encountered in practice where such it is necessary to handle\ninequality constraints is drug discovery, where you wish to maximize potency, subject to constraints\non the specificity and toxicity. Ideally, you would motivate the problem set up with an application\nyou use in your experimental evaluation. If this is something that interests you, you could check\nout the ChemBL or PubChem databases.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4dUlZBPRXq", "reviewer": "Reviewer_wxwg", "summary": "This paper provides a batch constrained Bayesian optimization (CBO) method in a non-myopic way for continuous domain and functions. Compared to the previous method [1], the proposed approach demands less computational burden to choose where to sample. The paper proposes a constrained two-step acquisition function 2-OPT-C for both sequential and batch CBO settings and its gradient estimator for efficient optimization. The proposed method outperforms the non-myopic rollout algorithm of [1].\n\n[1] Lam and Willcox, Lookahead Bayesian Optimization with Inequality Constraints, NeurIPS (2017).", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper's main contribution builds on an unconstrained version of the two-step look-ahead BO [2]; however, its optimization approach uses likelihood ratios different from IPA used in [2] to overcome the discontinuity problem inherent in the reparameterization trick. This discontinuity problem creates the same optimization challenge for SAA. The observation and analysis are pretty reasonable, and the proposed approach has a novelty and demonstrates its numerical efficiency compared to IPA and SAA on a set of synthetic problems.\n\nHowever, the reviewer concerns that the experimental setting is too limited because no real datasets are considered; the paper only numerically compares the approach with related methods only on a set of synthetic problems from another reference [1]. At this point, the reviewer thinks the proposed method is a promising approach but needs more work on numerical experiments as in [3]. Also, in L66, the paper argues that the proposed method is better than the rollout algorithm [1] in high-dimensional problems. It seems there is no investigation nor numerical experiment on this.\n\nThe paper is generally well-written and given the technical content. The approach appears technically sound, and the reviewer considers the resulting algorithm quite interesting.\n\n**Conclusion**\nThe method shows promise, but the method is not sufficiently evaluated on real-data problems. The reviewer argues for rejecting the work in its current form.\n\n---\n**Update**: as the authors could clarify some of my concerns during the rebuttal, I raise my score to 5.\n\n[2] Wu and Frazier, Practical two-step lookahead Bayesian Optimization, NeurIPS (2019).\n\n[3] Gardner et al., Bayesian Optimization with Inequality Constraints, ICML (2014).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations of their work in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "02o8xn_EFtQ", "reviewer": "Reviewer_iK1S", "summary": "The paper is about a making computationally affordable a non-myopic (two step ahead) acquisition function for constrained Bayesian optimization. The contribution is relying on a likelihood ratio, akin to importance sampling, to obtain the required gradient. The instability of existing methods is detailed. Comparisons are offered against myopic, sequential, batch and rollout alternatives.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clear overall. Still, clarifications are required on some statements, as well as some additional details. The empirical evaluations is limited to toy functions and a few alternatives methods.\n\nDetailed comments and questions:\n\n- Section 3: why not considering another batch at stage 1 after a batch at stage 0?\n\n- Page 6, line 220: “To the best of our knowledge, we are the first to adopt the likelihood ratio method to design a gradient estimator for BO algorithms.” while this is already done in [17, section 3.2]. This requires further discussion than just the paragraph in introduction (in addition to the similarity).\n\n- How do you find x_2^* in practice (in Algorithm 2), which is the “bottleneck” of the approach (A.3)?\n\n- The point made in [25] (authors and editors are swapped in the citation) is close to what is said at the beginning that non-feasible points can bring information. This makes it a very pertinent candidate to add to the empirical comparison and figure 1. Random search should be added as well for reference.\n\n- How to deal with equality constraints in this framework? What about failures (no observation possible in non feasible regions) or 0-1 constraints? See e.g., Bachoc, F., Helbert, C., & Picheny, V. (2020). Gaussian process optimization with failures: classification and convergence proof. Journal of Global Optimization, 78(3), 483-506.\n\n\nMinor:\n- two titles appear (Constrained Two-step Look-Ahead Bayesian Optimization and Two-step lookahead Bayesian optimization with inequality constraints)\n\n\nTypos : \nsection A: recomendation ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a  two-step lookahead Bayesian optimization (BO) strategy in the presence of inequality constraints, which builds on a previous work on an unconstrained version of the two-step lookahead BO and overcomes the weakness of an earlier multi-step lookahead BO. The paper is generally well-written and given the technical content. However, most of reviewers have concerns in limit empirical evaluations. It is required to include 1-3 real benchmarks which ideally arise out of motivating applications, more baselines, and ablation studies. This work received split reviews. After the authors' response, I had more than a few communications with reviewers. Unfortunately none of reviewers are willing to champion this work.



Decision: Accept (Poster)