Failure-Aware Gaussian Process Optimization with Regret Bounds
Authors: Shogo Iwazaki
Shion Takeno
Tomohiko Tanabe
Mitsuru Irie
Venue: NeurIPS 2023 poster (2023)
Keywords: Gaussian process optimization
regret analysis
black-box optimization
Bayesian optimization

Abstract: Real-world optimization problems often require black-box optimization with observation failure, where we can obtain the objective function value if we succeed, otherwise, we can only obtain a fact of failure. Moreover, this failure region can be complex by several latent constraints, whose number is also unknown. For this problem, we propose a failure-aware Gaussian process upper confidence bound (F-GP-UCB), which only requires a mild assumption for the observation failure that an optimal solution lies on an interior of a feasible region. Furthermore, we show that the number of successful observations grows linearly, by which we provide the first regret upper bounds and the convergence of F-GP-UCB. We demonstrate the effectiveness of F-GP-UCB in several benchmark functions, including the simulation function motivated by material synthesis experiments.

Failure-Aware Gaussian Process Optimization with Regret Bounds
Shogo Iwazaki MI-6 Ltd., Tokyo, Japan wwazaki@mi-6.cm jp
Shion Takeno RIKEN AIP, Tokyo, Japan shion. takeno@riken, jP
Tomohiko Tanabe MI-6 Ltd., Tokyo. Japan tanabe@mi -6. co.
Mitsuru Irie MI-6 Ltd., Tokyo, Japan irie@mi-6. co.
Abstract
world optimization problems often require black-box optimization with ob- servation failure, where otherwise, we can only obtain a fact of failure. Moreover, this failure region can be complex by several latent constraints, whose number also unknown. For this problem, we propose failure-aware Gaussian process upper confidence bound (F-GP-UCB), which only requires a mild assumption for the observation failure that an optimal solution lies on an interior of feasible region. Furthermore, we show that the number of successful observations grows linearly, by which we provide the first regret upper bounds and the convergence of F-GP-UCB. We demonstrate the effectiveness of F-GP-UCB several benchmark functions, including the simulation function motivated by material synthesis experiments.
obtain the objective function value if succeed,
Introduction
The effectiveness of optimization methods based on Gaussian process (GP) regression for expensive- to-evaluate black-box functions has been repeatedly shown in wide range of real-world applications, including robotics [34 35). experimental design [14), and hyperparameter optimization [4] 41]. On the other hand, failure of the observation itself must often be considered. For example, in the optimization of hyperparameters for a complicated physical model, the evaluation may crash for some hyperparameters. Another example is materials development, in which experimental testing of new materials can reveal that the synthesis procedure fails.
Therefore, this study considers the optimization of black-box function f with a black-box determin- istic failure function e: X' {0, 1). where is an input space. In this study, failure observation at the input is represented as c(x:) = 1, while the success of observation is represented as c(x:) 0. Then, our optimization problem can be formulated as follows:
x arg max (xx s.l. c(x) =0= 0,
where the observation of f can be obtained only if c(x)) = O, but the observation cost is consumed even if c(x) = Hence, the goal is efficiently identify the optimal point while considering the observation failure.
One of the notable technical difficulties of problem 1 is how to handle the failure function To model c, existing studies 32 use the GP classification (GPC) model 38 or its variants, which assume that can be represented by smooth latent function. However, the observation failure can
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

be caused by several latent constraints implicitly. In addition, since only the binary failure can be obtained, the number of latent constraints is also unknown. Therefore, modeling with the usual GPC is hard and often unsuitable, which can degrade the optimization performance. Hence, an optimization method under a mild assumption on e is demanded. Furthermore, the existence of c makes theoretical analysis and even securing the number of successful observations difficult.
Our contribution. In this paper, we propose a novel GP-based optimization algorithm, failure- aware GP upper confidence bound (F-GP-UCB), which chooses the next evaluation in an input domain except for the adaptively adjusted neighborhood of the past observation failures. Furthermore, we show that the number of successful observations grows linearly under very mild assumption of the failure function e that the optimal solution lies on an interior of feasible region. Then, we provide the first regret upper bound of the GP optimization problem ( which shows that F-GP-UCB converges to the optimal solution with high probability. We demonstrate the effectivvnesss of the F-GP-UCB algorithm with several benchmark functions, including heuristic simulation function motivated by materials research of quasicrystals.
Related work. In the past few decades, many GP-hased optimization algorithms have been devel- oped R7 42 18 [35.. addition to the standard optimization settings, various extensions have been studied, such parallel [9]. high-dimensional [54] multi-fidelity [25), and robust optimization [6].
19 has a close relation our study. It considers the black-box optimization under an inequality constraint g(x) < O, where is also a black-box function. If the failure function in this paper is recast as c(x) = [g(()) > 0}. the optimization problem matches that of problem (T). However, there are two crucial differences. First, in constrained optimization, observations at an input can be obtained even if the constraint is not satisfied, i.e..
GP-based constrained optimization [1
g(ar) > O. Under the setting of this paper, no information about the objective function can be obtained for input points that result failure. Second, constrained optimization problems, it is generally assumed that noisy observation of g(x) is possible. In the setting of our study, we cannot obtain direct observation from the latent function g.
There exist works on GP optimization that take into account failures. Lindberg and Lee 33 proposed an algorithm that combines the Expected Improvement (EI) criterion 337 with the posterior success probability of the classical GPC. Instead of GPC, Sacher et al. [39 used a support vector machine- based model. However, although is deterministic, these classifiers assume that observation failure is essentially stochastic, i.e., the evaluations at the same input can fail and succeed. This model misspecification can degrade the optimization performance, as described in Bachoc et al. [2]. Then, Bachoe et al. [2 proposed the deterministic variant of GPC which models as c(x))= = [((x)) 2 0}, where g is a latent function modeled by a GP. They also provide an El-based strategy and prove convergence to an optimal solution. From practical point of view, surrogate models of e navigate the optimization process efficiently when e is well represented through a smooth latent function g. However, practical applications often have too complex failure processes to model with one latent function (e.g., the failure function depends on several latent functions.) Furthermore, it difficult to know that such complex failure structure exists beforehand. Finally, from theoretical perspective, Bachoc et al. [2] give the convergence guarantee, but its rate and the regret- regret-based analysis are not provided.
2 Preliminaries
be an unknown fixed objective function and an unknown failure function, respectively, where X' = [0, 1] the input space. At each time step t, the user makes a selection æ, E X' and obtains the failure label c(x,). If c(ær) = O. the user proceeds to make a noisy observation y/ = -(;;) + E& where e is a noise term which is conditionally o-sub-Gaussian. Our noise model is mild one; examples include an arbitrary distribution over [-o, a] and a Gaussian noise with variance below o². Note that, in the case of c(x,)) = 1 (failure), the user obtains no further information.
Problem setup. f R and c: X {0.
The user's goal to efficiently identify the optimal solution x over the unknown feasible region S. = (ar E X c(xr = 0}. For convenience, we rephrase the problem (1) using S, as follows:
x arg max fxx)
(2)
=ES.

---

We assumee that Sc * 9 and that there exists a unique solution x". Furthermore, we define the failure region Fe. as F. X S.
Regret. We employ the regret to evaluate the algorithm's 's performance, The regret at step t is defined as r. = f(=") - f( if क. E Sc. otherwise r; = f(x") - minge (ax) where ã; E X is the algorithm's 's estimated solution In our definition of re. the algorithm is supposed to incur the worst-case regret when é; not in S... Similar definitions are also used in performance metrics of
GP-based constrained optimization [19
Regularity assumptions for the objective function. As regularity assumption, we assume that is an element of the reproducing kernel Hilbert space (RKHS) Hr. corresponding to known positive-definite kernel k : X' X + IR, and has a bounded Hilbert norm [|] < B. Furthermore,
the kernel & is assumed to be normalized, namely Va E X, k(æ,, x) 1. These are common assumptions existing GP optimization literature
Gaussian process modeling. Our algorithm uses the modeling information of f from GP (38), using only the successful observations. First, we assume zero-mean GP with the covariance function & as the prior of f. Next, we model the generating process of the value y/ queried at æ, y/+ fxx, te,, where E ~ (O (O). We note that the assumptions on the GP prior on f and Gaussian noise, assumptions only for constructing the GP model, which
as stated above, underlying true function f and the noise. Let I(5) = {i E (1...., c(ar;) = 0} be the index set of successful observations, x (5)
differ from the
( be the corresponding inputs, yt (8) = (EI be the corresponding outputs, and ne == |Z, (5) be the number of successful observations. In addition, {i {1....,t} | c(x,) 1}. Given x yt the posterior distribution of fxx becomes a normal distribution, whose posterior mean Me and posterior variance of (z) are given as follows:
also define the failure index set I
(S)
(z) = k(x, X TT
(((x(5) + IOII.)
Vi
(S)
(3)
of (x) = k(x, x) k( ( (K(X(3) (s)) + o² In:) k(x, (5)
Here, In, is a n4 x n, identity matrix. Furthermore, denoting the index of the j-th least element of I (5) as ij. (xxx E Rt represents a vector whose j-th element is k(æ, at,)). Similarly,
((X! (5) E R represents the kernel matrix whose jk-tt element is k(aaiy, )..))
Lastly, we define the maximum information gain 42 49 as quantity representing the GP complexity. The maximum information gain "/tAA from observing number of data points over the set A C R2d is de- fined as a = max x =E) / [[fx x, yx)., where [(fx, 9x) == 0.5 In det (I, o ((()) the mutual information between the latent function values fx ~ (O, (X)) and corresponding output values yx = fx + Ex, E, (O o2, 1)) of GP. In GP-based optimization, TtAA is often used as a quantity that characterizes the confidence bound and regret bound of f. Furthermore, for a compact convex set A, the upper bound for Yt,4 has been derived for some commonly used kernels. For example, Yt:A O((In ((Inn)dd1) 1)d-1) for Gaussian kernel and A ((dd(c+4)) (In ()2=/(+++)))))))) ) for Matérn kernel with the smoothness parameter v > 1/2 42 49]. The following Lemma 2.1 adapts the well-known result that gives the confidence bound of f for our problem setup. which is direct consequence of Theorem 3.11 in [T].
Lemma 2.1. Fix f E H₂ with [lf S B. Suppose the observation y+ = fxx,) + E, has a noise e, that is conditionally s-sub Sabb-Gaussian. Define (3e (5eteen as s./²² = B + a / 211022112xx +1+ (1/0)]
for 8 E (0,1) 1). Then the following holds with probability al least 1
Vt 2 1, Va E X, lob,(x)) S f(x) I ucbx(2x).
(5)
Here, lcb and (x) are defined as leb;(x)) = (x) - 31/20,0111 (x) and (cb;(x)) =
(==(xx) + / / (z)) respectively.
'Some applications prefer to assess the performance via cumulative regret. In Appendix C the analysis of the cumulative regret of our algorithm is provided.
3

---

Regularity assumption for failure function. A regret upper bound cannot be obtained without any assumption on c. As an extreme example, we consider the case where surrounded by Fe. Under this scenario, the worst case exists in which an arbitrary algorithm can never observe x² a finite number of trials. Therefore, in order to give a convergence guarantee, at least x² must be contained in subset of the feasible region Se having non-zero volume. In this paper, we focus on the case that x' is the interior point of S. as in the following assumption.
an isolated point
Assumption 2.2. There exists yj > O such that :n C S., where Na { E X || x= 10 n is an open infinity ball with radius n centered x²
The parameter Yj above depends on the size of the subset of the feasible region that x" belongs to and is an important quantity for theoretical analysis. Note that Assumption 2.2 is quite mild. For example, when is defined as c(x) - gg)(z) 2 }} with a continuous latent function g. there exists " > 0 such that Na C S. from the continuity of g. Since the analysis of (2 assumes the existence of the latent function which is a continuous sample path generated from GP, our assumption also subsumes their assumption. Finally, note that 77 not needed for running the algorithm and is only used as a quantity that characterizes the regret bound.
3 Proposed algorithm
Our proposed algorithm F-GP-UCB is shown as pseudo-code in Algorithm I Roughly speaking, our F-GP-UCB searches the input domain excluding the adaptively adjusted neighborhood of past failure points based on the existing GP-UCB [4 strategy. Below, we start by describing the background of the algorithm construction.
Philosophy of algorithm construction. Since Fe unknown, the algorithm needs to appropriately avoid the failure observation in Fe while balancing the trade-off between exploration and exploitation in way that guarantees convergence. The difficulty of this problem lies in the fact that there exist cases where the small feasible region containing x= is surrounded by the past failure observations and isolated as shown in the left plot of Fig. [] Since the algorithm unable to exclude the possibility that an arbitrary small feasible region exists between failure points only from Assumption [.2] the algorithm should be constructed so that it simultaneously satisfies the following two points: the failure observation should be avoided; and the inputs evaluated by the algorithm should eventually cover the arbitrarily close area of the past failure point.
F-GP-UCB satisfies the above requirements by adaptively controlling the GP-UCB search region by eliminating the neighborhood of the past failure points, and shrinking the eliminated region as step increase. Next, we describe below the details of and ideas behind each step.
Selection of wt. At each step f, the F-GP-UCB algorithm firstly computes the seach region X, as
X = E E X Vi E I 1|. - x x0 2 b,b(t)).
(6)
Here, O, and b: R4 + R_ are the scale parameter and monotonically decreasing function, respec- tively. The parameter d₂ is controlled by the algorithm at every step so that it decreases monotonically with respect to from its initial value 6g given by the user. plays the role of guaranteeing that the search space X; satisfies X, * Q. The function b is defined by the user before running the algorithm.
By using Xx, the F-GP-UCB algorithm chooses 0c
Ct arg max ucb, (x).
m
The middle and right plots in Fig. show an example behavior of the F-GP-UCB algorithm. By using the monotonically decreasing b,b(t) to control the search space, the algorithm's 's behavior can be qualitatively described as follows. First, during the early phase where t is small, 0,b(t) large, corresponding to choosing unexplored point for observation while avoiding a large neighborhood of the past failure points where there high possibility of failure. Then as t increases and the
"Our algorithm and theoretical analysis can be generalized for arbitrary norms over H such as Lorm and for compact convex subset X C Ie however the computational technique discussed in Sec assumes the infinity norm.

---

f(x)
Success Xt
Failure Xt
Sc
Iteration 5
Iteration 10
f(x)
f(x)
X
X
0,b(t)
Figure 1: An example problem in one dimension. The left plot shows the situation where there exists an isolated feasible region, which includes the optimum. The green and grey shaded areas represent the feasible region S. and the failure region Fe. respectively. The green (black) points represent the observed successful (failure) points. In this situation, it is necessary to identify the feasible region which hides among the observed failure points. The middle and right plots are example behaviors of the F-GP-UCB algorithm in = 5 and t 10, respectively. The gray shaded regions represent the neighborhood of the observed failure points which is excluded from the search space at the given step. The F-GG-UUG UCB algorithm performs searches in all the feasible regions while avoiding the observed failure points by iteratively narrowing down the excluded search space in the neighborhood of the failure points.
remaining unexplored space shrinks, it is expected that the algorithm's 's behavior will become more aggressive in considering the possibility that the region near the observed failure points contains feasible region that may be difficult to identify.
The choice of and 6 affects the performance of F-GP-UCB. In Sec. 4 we show the conver- gence of the regret under an appropriate choice of b. In Sec. the practical choices of 6g and b are discussed.
Algorithm 1 The F-GP-UCB algorithm
Input: 0o E (0, 1).b: R + R.,, (BeteeN
1: Initialize GP prior and set x/ = I((
2: for L 1 to T do
Shrinking Or. In the case where X; = 0, æx is defined. We ensure such cases do not occur by controlling the scale parameter 0,. In our algorithm, the main role of 0g to guarantee that o, is well-defined as follows. Specifically, before the step starts, 0g computed by halv- ing the previous scale parameter f:-1 until the union of all the neighborhoods does not fully
3: 6g < f1-1-
4: while X C CU U N m. do
5:
O. 0./2.
6:
end while
7:
6, < 0, and define X, as in (6)
8: Choose x; = argmax=exx (c).
9:
if c(a,) = 0 then
10:
Observe y/: f(xx) + and update GP.
cover X. This procedure requires that we solve the set covering problem find the cover of X with the neighborhoods of the past failure points.
I((s - [ (t). I I(-)
12:
else
I2 + 1( 1(9 + utt
Unfortunately, this problem is known to be NP complete (20]. In Sec. 5] we provide practical
13:
14: end if
approach to this problem. On the other hand, note that our analysis in Sec. 4 assumes that this procedure can be computed exactly.
15: end for
16: Calculate xg as in 88 if (9)
+ 0.
The estimated solution of the F-GP-UCB algorithm a; at step t is defined as follows:
Algorithm estimated solution.
t = where i= arg max)cb, (eI!3)
(8)
The definition of the estimated solution based on the observed points and Icb, is often used in exisiting
literature (6] 26 21. While the estimated solution of the proposed method resembles those in the
5

---

literature, it should be noted that the maximum of lcb, is computed over I,(5 Note ét is not defined all the points up to are failures (i.e., z = 0). Sec. 4 it is shown that there always exists øt for sufficiently large step size T. Finally, although the estimated solution ( is useful for discussing the theoretical performance, for practical purposes, ã; = zÚ where = argmax Icb, is We use this modified definition of i, the benchmark experiments in
often used instead 6 21 Sec. [6]
4 Theoretical analysis
The results of the theoretical analysis are discussed in this section. The complete proofs of the theorems and lemmas are described in Appendix
Key of regret analysis. To analyze the regret, we start by evaluating the growth rate of the number of successful observations nt in the algorithm. By noting that 0,b(t) is monotonically decreasing, we can find that the failure points of F-GP-UCB are separated by at least a distance 0,b(t) apart from each other. Therefore, ny can be evaluated via sab(t)-packing number of Fe. The following Lemma 44. based on the standard argument for the packing number, which gives the lower bound for the number of successful observations n4.-
Lemma 4.1. When running Algoritium 1
11 11,0. 0,b(t)/4) holds for any t E N4, where P(X,1 || lloo; denotes the e-packing number over the set X with respect to the norm || l
n4 2 - (XX
Using the above Lemma 4. designing the choice of b so that ( 1 P(X, ll ,,,,, 0,b(1)/4) (I) holds leads to ni = (1)). which means that the number of successful observations can be secured at the same rate as in the standard GP optimization setting. By using the fact P(X' (l [1/
(Lemma A.4) the choice of b(t) = o(t o(t-1/d) sufficient for n, = St(E { While our result holds for any b satisfying b(t) o(t 1/d),, we give results for b satisfying b(t) t- with a E (0, 1/d) in this section for simplicity. In Appendix A the result for general X and b is also provided.
Regret bound. The following Theorem 4.2 gives the regret bound of the F-GP-UCB algorithm.
d X 10. 1] and f E Hr such that [| S B. Let + In(1/0)) and b(t) = a. In addition. suppose that there exists " such that Na Se, where Na (æ X | a= 7) When applying
Theorem 4.2. Fix d (0,
8//2 = + o / =B+o 2(1-11
Algorithm| 7 under the above conditions, the estimated solution क. defined in (8) exists for all
T T, = (1x (1(--d)), + L, where 0 min(0o, n/23. Moreover, the following holds with probability at least 1 1 8:
2 VT z Top rT 5 T
2B(T.. + + VCSTTTTTS
where π. (0o/n) 1/0 + and Ci 8/ (1|n(1 + 2
In the analysis above, 17 is interpreted as the complexity of the failure function and 7 corresponds to the lower bound on 0, while running the algorithm. The constants T, and T. are important quantities that characterize the regret and can be respectively interpreted as follows.
The constant î, is the upper bound on the number of steps until the first successful observa- tion.
The constant T, is the upper bound on the number of steps needed until the search space X of the algorithm always contains the optimal solution x
The regret bound in Theorem 4.2 can be intuitively seen as evaluating the algorithm execution in terms of two stages along the time axis. The first term of (7) represents the regret generated when the algorithm's 's search space X; does not contain x". Specifically. the worst-case regret incurred during this phase is bounded by 2B using the fact that sup (xx) S from the kernel normalization
'Strictly speaking, we use the fact that 0, becomes constant for sufficiently large t. See Lemma A.8 in Appendix

---

condition. The second term is the regret incurred during the process of identifying x* after X includes x" and similar to the regret bound of standard GP-UCB. The only difference is that, in our setup, the observations of GP are only on Se, so the maximum information gain is defined over Se-
By noting that TT:S. Tr, in the second term and using the known results concerning the upper bound on YT,'' the more explicit form of regret upper bound can be obtained on a per- kernel basis. For example, in the case of the Gaussian kernel, we have that TT = O((In Tyd+1)
and Pr = 0 BT. + T TT (2+11) [ B+ +o+ovio / T) + In(1/5)) Thus, indeed we obtain rT (as T + oo). The F-GP-UCB algorithm is guaranteed to converge when the cumulative regret for ordinary GP-UCB (corresponding to the second term in (9) becomes sub-linear under the chosen setup and the kerne
The case where x" exists on the boundary of S.. The case where x' exists the boundary S. is not covered in Theorem 4.2] which is the case that often appears in real-world application. If undesirable Lipschitz-style dependencies are allowed to emerge in the regret upper bound, our F-GP-UCB algorithm is also guaranteed to have convergence in such cases (Theorem B.2 The details of the result and discussion about its limitation are in Appendix B
5 Practical considerations
In this section, we discuss several issues that arise in practical situations and provide their solutions. Due to the space limitation, we only give brief descriptions. The details are described in Appendix E
Computation of 0:. The computation of 0g requires us to know whether the union of all the neighborhoods of the failure points covers X. A simple solution might be partition X' into sufficiently fine grid by subdividing each axis and look for a feasible solution in each grid cell by brute force. However, as the step size and dimension d become large, the number of grid cells grows rapidly. Furthermore, even very fine grid will not be able to detect the case where feasible solution exists on the cell boundary. Another heuristic approach is to use a constrained optimization solver which does not require feasible solution as part of the initial points (e.g., penalty function method and augmented Lagrangian method [7)) and try to solve the problem 7 by using 0,-1- 1- In case that the solver is unable to find a feasible solution, it is decided that X of O, multiply 0:-1 by 1/2, then we try to solve problem 77) again. This is our chosen approach. A drawback of this approach is that, depending on the scale of O,, the constrained optimization problem must be solved many times. We show that, by performing an appropriate preprocessing, feasible solution can be obtained within two rounds of constrained optimization in the worst case. We give the details in Appendix E.
Selection of b. As stated in Sec. 4 the F-GP-UCB algorithm is valid for an arbitrary monotonically decreasing function such that t P(x , || ol. (,b(t) = (t)). However, the rate is slower than 1/t" (a E (0, 1/d)). for example, b(t)= 111mmmm lt 1), then the dominant term of regret upper bound can become O(1/In In (See Theorem B.3 in Appendix B and Corollary F.1 in Appendix F). This intuitively means that an exponentially large sample is needed to obtain an arbitrarily small regret and is not the desirable behavior. In this paper, we use b in the form of
b(() 1/(a with
= 1/d2) as a practical choice. (Additional discussion about is given in Appendix
E.2
Adaptive tuning of 0g- Although the choice of 0g does not affect the no-regret guarantee, it has large impact on the practical behavior when the number of steps is small. For example, if 0g is set to a large value when the failure region Fe, forms a relatively small region, then there is a risk of excessively avoiding the feasible region that should be searched. It practically difficult to find a desirable choice of dg as it depends on some conditions that are unknown to the user, such as the failure region Fo. In order to alleviate this issue while retaining the theoretical convergence. we use the strategy to adaptively choose Or based on the posterior standard deviation (a:)( of the observed points. We note that such a strategy using ( to adaptively select an unknown parameter is also developed in [54] to set the unknown kernel hyperparameters for ordinary GP optimization.
"s with the standard GP-UCB, & (rxx) in F F-GP-UCB, which leads to the regret of Ö /T)). In Appendix D we discuss the possibility of addressing this issue based on several existing works [48 30
7

---

Algorithm 4 in Appendix E.3 shows the pseudo-code of our modified strategy. In Algorithm 4
the user specifies the possible range for f; E [@min max] the threshold for the posterior standard deviation hr > O, the threshold for the step number & E N+, and a scaling factor w E (0, 1). As the initial value, we set 0g mmax. After that, if the observed point is lower than the posterior standard deviation for q consecutive number of times, 0, is multiplied by w to lower its value, but no less than the minimum value min. Intuitively, suppose the posterior standard deviation is repeatedly excessively small. In that case, there exists possibility that do was set to excessively large value, which may lead to the unwanted exclusion of the feasible region from the search space. In this procedure, by setting Bu to large value of mmax at the start, we expect it to get adjusted towards an appropriate neighborhood scale. In our simulation experiments, we set w = 0.75, ha = 0.02, q = 3, mmn = 0.0001, and 6 max 0.5. We emphasize that this procedure does not affect our convergence guarantee (Theorems
F22 in Appendix E..
Lastly, the pseudo-code, including all the considerations provided in this section, is described in Algorithm of Appendix
+
6 Numerical experiments
In this section, we show the performance of F-GP-UCB through numerical experiments. The detailed settings of the experiments and additional results can be found in Appendices and H respectively. First, for comparison, we use EI [37] and GP-UCB [42] as the baseline algorithms which do not consider failures. In each of these algorithms, the GP model is constructed using only the successful observations; the failure observations are not used. We also compare F-GP-UCB with the EFI-GPC- EP and EFI-GPC-Sign algorithms that leverage GPC models 2 EFI-GPC-EP the algorithm that uses the classic GPC model with probit likelihood, and posterior approximation is based on Expectation Propagation (EP). EFI-GPC-Sign uses a variant of GPC proposed in (2). Both EFI-GPC- EP and EFI-GPC-Sin choose the next input based the posterior success probability of GPC and the EI value of f as in 2 (Details are in Appendix H..
In EFI-GPC-EP and EFI-GPC-Sign, as the prior for the latent function of GPC, we use zero-mean GP with Gaussian kernel kg (z. y) of exp(-Ilæ - y/| (2(2). Before the experiment, we fix the kernel parameters of GPC a, and Le by marginal likelihood maximization using observations at a randomly generated Sobol sequence. All the kernel hyperparameters of the GPC fixed by this procedure are given in Appendix [ Furthermore, it is well-known that the theoretical choice of Be GP-UCB is excessively conservative. We set B, 2 l22t) as in (24 for GP-UCB and
F-GP-UCB. The other parameters in F-GP-UCB are fixed as described in Sec. 5 For the evaluation
of the algorithms, we confirm the behavior of the regret at each step Ti = f(x)) - f(::). We note that é is the estimated solution a.- = 2F where
argmax (e(ss) Icb, (m:). which is slightly
modified from the theoretical value as discussed in Sec. If we get that Z 0, then we set rs = fz*) - min f (xr). This definition is the same as the utility gap metric for constrained GP optimization [19]. In each experiment, we report the average performance of 20 numbers of optimization trials with different seeds. In each trial, we generate one point uniformly at random over X' and use it as the initial point. Lastly, we add artificial noise 6, ~ ~O, o²) with 0² = 0.0001 to the observation of f. We also fix the noise variance hyperparameter of the GP model for f to 0.0001.
Synthetic experiments with the Branin function. We perform synthetic benchmark experiments with the Branin function whose input space is scaled to j0, 1/2. The failure function used in these experiments is shown in Fig. [ This failure function has a feasible region on the upper right side which is easily identifiable. In addition, the failure function also contains multiple small isolated feasible regions, one of which contains the optimal solution. We use the Gaussian kernel k(x,)) y)= == of exp(-Ilæ y212 to construct GP model of f. The parameters a, and Iy are fixed beforehand by marginal likelihood maximization over Sobol sequence of 1024 points. The subsequent experiments also use the Gaussian kernel; and the parameters are fixed as described above.
F shows the result. Under this benchmark setting, F-GP-UCB has a better performance, We also give the detailed behavior of F-GP-UCB in Appendix G We note that, in El and GP-UCB, the regret stops decreasing in the early stage. This is because these algorithms get stuck on the same failure point.
8

---

Branin test problem
Branin test function
1.0
Optimal solution
GP-EI
10a
0.8
GP-UCB
EFI-GPC-EP
0.66
Regret
10a
EFI-GPC-Sign
Input
F-GP-UCB
0.4
10
10
0.0.0
0.2
0.4
0.6
0.8
1.0
50
100
150
200
250
Input
Iteration
The left plot shows the Branin function whose imput space is scaled to J0, 1J2. The shaded regions represent the failure regions. The right plot shows the regret the synthetic problem using the Branin functtion, where the average of 20 experiments with different random seeds is shown. The error bars correspond to two standard errors.
Figure 2:
I
GP-EI
I
GP-UCB
EFI-GPC-EP
+
EFI-GPC-Sign
+ F-GP-UCB
Gardner test function
Hartmann test function
Quasicrystal simulation function
109
10a
Regret
10
Regret
Regret
10
20
10-3
10
10
125 Iteration
Iteration
Iteration
Figure 3: Experiment results of benchmark function of the constrained optimization problems (left and middle) and quasicrystal simulation function (right). The left and middle plots show the result of Gardner and Hartmann test functions, respectively. The error bars correspond to two standard errors.
Test functions for constrained optimization. We adopt the two benchmark settings which are used in existing GP-based constrained optimization literature. Gardner [10] is 2D test problem whose objective and constraint functions are defined as a combination of sine and cosine functions. Hartmann [29] is 3D test problenf whose feasible region becomes unit hypersphere. To adapt the constrained problem to our settings, the feasible region in each benchmark is defined as the success region, while the rest is defined the failure region. Fig. 3 shows the result. Within the compared algorithms, F-GP-UCB has the best performance for the Gardner function, while EFI-GPC-Sigr has the best performance for the Hartmann function. This be understood from the fact that the feasible region of the Hartmann function, which is a unit hypersphere, and can be modeled casily by GPC. However, F-GP-UCB performs better compared to EFI-GPC-EP, which uses a classic GPC model. Moreover, the regret of F-GP-UCB continues to decrease as the number of iterations increases.
Numerical experiments with quasicrystals. We perform numerical experiment involving qua- sicrystals in the Al-Cu-Mn system. We consider the optimization of the phonon thermal conductivity for quasicrystals. In this setting, the input space is the relative composition of the three elements, restricted to be around the feasible region of quasicrystal stal formation. The feasible region is the composition values that form quasicrystals based on data [66. Outside of this region, quasicrystals do not form and so we consider as failure region, as the material property could not be probed with methods designed for quasicrystals. For the objective function, we use empirical formula for the phonon thermal conductivity which we extract from [46]. The details of the setting are described in
'The original paper (29 considers 6D problem and this setting leads to an excessively large failure region. We modify the setting by using 3D version of the Hartmann function with unit hypersphere constraint.

---

Appendix H.2 In Fig. 3
the right plot shows the result of the numerical experiments for quasicrystals.
shows that F-GP-UCB performs the best among the compared algorithms.
Conclusions
In this paper, we propose novel GP-hased optimization algorithm in the presence of unknown failure regions in the search space. Our algorithm only requires a very mild assumption of the failure function that the optimal solution lies interior of feasible region. We show that our algorithm achieves a convergence with high probability and provides the first regret upper bound by appropriately adjusting the search space. Its effectiveness verified empirically through numerical experiments, including the heuristic simulation experiment motivated by the material research of quasicrystals.
Acknowledgements
This work was partially supported by RIKEN Center for Advanced Intelligence Project.
References
[1] Yasin Abbasi- Yadkori. Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, 2013.
[2] François Bachoc, Céline Helbert, and Victor Picheny. Gaussian process optimization with failures: classification and convergence proof. Journal of Global Optimization, 78(3):483-506 2020.
[3] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: A framework for efficient Monte-Carlo Bayesian optimization. Advances in Neural Information Processing Systems, 33:21524-21538 2020.
[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, volume 24, 2011.
[5] Felix Berkenkamp, Andreas Krause, and Angela P Schoellig. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Machine Learning, pages 1-35, 2021.
[6] Ilija Bogunovic, Jonathan Scarlett, Stefanic Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. Advances in Neural Information Processing Systems, 31, 2018.
[7] Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental design and kernel bandits. In International Conference on Machine Learning, pages 1227-1237. PMLR, 2021.
[8] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 844 453, 2017.
[9] Thomas Desautels, Andreas Krause, and Joel W. Burdick. Parallelizing ppploration-exploitaiie tradeoff' in Gaussian process bandit optimization. Journal of Machine Learning Research, 15 (19):4053-4103 2014.
[10] Jacob Gardner, Matt J Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cunning- ham. Bayesian optimization with inequality constraints. Proceedings of the 3 31st International Conference on Machine Learning, 32(2):937-945, 22-24 Jun 2014.
[11] Michael A. Gelbart, Jasper Snoek, and Ryan P. Adams. Bayesian optimization with unknown constraints. Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI' 14, page 250-259, Arlington, Virginia, USA, 2014. AUAI Press. ISBN 9780974903910.
10

---

[12] Alan Genz. Numerical computation of multivariate normal probabilities. Journal of Computa- tional and Graphical Statistics, 1(2):141-49, 1992.
[13] Susana Gomez and Alejandro Velasco Levy. The tunnelling method for solving the constrained global optimization problem with several non-connected feasible regions. In Numerical Analysis, pages 34-47. Springer, 1982.
[14] Javier González, Joseph Longworth, David C James, and Neil D Lawrence. Bayesian optimiza- tion for synthetic gene design. arXiv preprint arXiv:1505.01622) 2015.
[15] GPy. GPy: A Gaussian process framework in python. http://github. http://gtccbb.coo//ffffeeddddl com/SheffieldML GPy since 2012.
[16] Benjamin Grushko and SB Mi. Al-rich region of Al-Cu-Mn. Journal of Alloys and Compounds, 688:957-963, 2016.
[17] PC Haarhoff and JD Buys. A new method for the optimization of a nonlinear function subject to nonlinear constraints. The Computer Journal, 13(2):178- 1970.
[18] Philipp Hennig and Christian Schuler. Entropy search for information-eeffcient global optimization. Journal of Machine Learning Research, 13677)1189--133, 2012.
[19] José Miguel Lrrndnddzz-Lbbato Michael A. Gelbart, Ryan Adams, Matthew W. Hoffmann, and Zoubin Ghahramani. A general framework for constrained Bayesian optimization using information-bent based search. Journal of Machine Learning Research, 17(1):5549-566 2016.
[20] Jörg Hoffmann and Sebastian Kupferschmid. A covering problem for hypercubes. In IJCAI, pages 1553-1522- 2005.
[21] Shogo Iwazaki, Yu Inatsu, and Ichiro Takeuchi. Mcan-vare variance analysis in Bayesian optimiza- tion under uncertainty. In International Conference Artificial Intelligence and Statistics, pages 973-981. PMLR, 2021.
[22] Steven G. Johnson. The NLopt nonlinear-optimization package, 2011. URL http:// ab- iiiiiio.mit www.mmittdduuu... edu/nlopt
[23] Donald R Jones, Cary D Perttunen, and Bruce E Stuckman. Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Applications, 19(1)1157-181, 1993.
[24] 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.
[25] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabas Poczos. Multi-fidelity Gaussian process bandit optimisation. Journal of Artificial Intelligence Research, 66:151-196, 2019.
[26] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 2174-2184. PMLR, 2020.
[27] Shunya Kusakawa, Shion Takeno, Yu Inatsu, Kentaro Kutsukake, Shogo Iwazaki, Takashi Nakano, Toru Ujihara, Masayuki Karasuyama, and Ichiro Takeuchi. Bayesian Optimization for Tyscade-Type Multistage Processes. Neural Computation, 34(12):2488-2433 11 2022. ISSN 0899-7667. doi: 10.1162/neco__ a 015550
[28] Madison Lee, Shubhanshu Shekhar, and Tara Javidi. Multi-scale zero-order optimization of smooth functions in an rkhs. In 2022 IEEE International Symposium on Information Theory (ISTT), pages 288-293. IEEE, 2022.
[29] Benjamin Letham, Brian Karrer, Guilherme Ottoni, and Eytan Bakshy, Constrained Bayesian optimization with noisy experiments. Bayesian Analysis, 14(2):95-511, 2019.
11

---

[30] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, pages 92-107. PMLR, 2022.
[31] Zihan Li and Jonathan Scarlett. Regret bounds for noise-free cascaded kernelized bandits. CoRR, abs/221 1.04330, 2022.
[32] David V Lindberg and Herbert KH Lee. Optimization under constraints by applying an asymmetric entropy measure. Journal of Computational and Graphical Statistics, 24(2):379- 393, 2015.
[33] Chang Liu, Erina Fujita, Yukari Katsura, Yuki Inada, Asuka Ishikawa, Ryuji Tamura, Kaoru Kimura, and Ryo Yoshida. Machine learning to predict quasicrystals from chemical composi- tions. Advanced Materials, 33(36):2102507, 2021.
[34] Daniel J Lizotte, Tao Wang. Michael H Bowling, Dale Schuurmans, et al. Automatic gait optimization with Gaussian process regression. In IJCAI, volume 7, pages 944-949, 2007.
[35] Ruben Martinez-Cantin, Nando de Freitas, Arnaud Doucet, and José A Castellanos. Active policy learning for robot planning and exploration under uncertainty. In Robotics: Science and systems, volume pages 321-328, 2007.
[36] Thomas P Minka. Expectation propagation for approximate Bayesian inference. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, pages 362-369, 2001.
[37] Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference, pages 400-404, 1975.
[38] Carl Edward Rasmussen and Christopher K. I. Williams, Gaussian Processes for Machine Learning. The MIT Press, 11 2005. ISBN 9780262256834. doi: (0.7551/mitprress/3000000 0001.
[39] Matthieu Sacher, Régis Duvigneau, Olivier Le Maitre, Mathieu Durand, Elisa Berrini, Frédéric Hauville, and Jacques-André Astolfi. A classification approach to efficient global optimization in presence of nompconpu domains. Structural and Multidisciplinary Optimization, 58(4):
1537-1557, 2018.
[40] Sudeep Salgia, Sattar Vakili, and Qing Zhao. A domain-shrinking based bayesian optimization algorithm with order-optimal regret performance. Advances in Neural Information Processing Systems, 34:28836-28847, 2021.
[41] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems, volume 25, 2012.
[42] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 1015-1022, 2010.
[43] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe exploration for optimization with Gaussian processes. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 997-1005, Lille, France, 07-09 Jul 2015.
[44] Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue. Stagewise safe Bayesian opti- mization with Gaussian processes. In International conference on muchine learning, pages 4781-4789. PMLR, 2018
[45] Krister Svanberg. A class of globally convergent optimization methods based on conservative convex separable approximations. SIAM Journal on Optimization, 12(2):555-573, 2002.
[46] Yoshiki Takagiwa, Ryota Maeda, Satoshi Ohhashi, and An-Pang Tsai. Reduction of thermal con- ductivity for icosahedral Al-Cu-Fe quasierystal through heavy element substitution. Materials, 14(18):523,, 2021.
12

---

[47] Shion Takeno, Tomoyuki Tamura, Kazuki Shitara, and Masayuki Karasuyama. Sequential and parallel constrained max-value entropy search via information lower bound. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages
17-23 Jul 2022.
[48] Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. Optimal order simple regret for gaussian process bandits. Advances in Neural Information Processing Systems, 34:21202-211 222211,, 2021.
[49] Sattar Vakili, Kia Khezeli, and Victor Picheny, On information gain and regret bounds in Gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
[50] Sattar Vakili, Jonathan Scarlett, and Tara Javidi. Open problem: Tight online confidence intervals for RKHS elements. Conference on Learning Theory, pages 4647 4652. PMLR, 2021.
[51] Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 654-663, 2013.
[52] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
[53] 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, 06-11 Aug 2017.
[54] Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian optimization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
13


Reviews:
[{"review_id": "qoiuZKFbVZ", "reviewer": "Reviewer_GLK5", "summary": "This paper investigates GPBO under a robust setting, where the failure of observations is taken into account in the overall budget.  An adaptive algorithm based on GP-UCB has been proposed to address this problem, and both theoretical and practical behavior have been analyzed and verified.", "questions": "To my knowledge, greedy elimination algorithms based on maximizing posterior variance usually achieve better theoratical convergence rates than UCB algorithms when it comes to robutsness considerations.  Do you have any idea that in the failure setting, a similar algorithm, say by replacing (5) with $x_t = \\arg \\max \\sigma_t(x)$, would work better or worse?", "limitations": "NA", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this is a well-written paper with comprehensive analysis of the proposed algorithm. The empirical studies also demonstrate that the proposed algorithm is effective for at least low-dimensional problems.", "weaknesses": "The empirical behaviour of the proposed algorithm is only verified for dimensions less than 3, and it would be nicer to see more practical settings.  In such cases, a vanilla GP-UCB might work even better than a specially designed algorithm.  Thus, It might be interesting to explore the trade-offs in practice between the two approaches.\n\nMinor:\nline 154 \"computes\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments.\n\n> To my knowledge, greedy elimination algorithms based on maximizing posterior variance usually achieve better theoratical convergence rates than UCB algorithms when it comes to robutsness considerations. \nDo you have any idea that in the failure setting, a similar algorithm, say by replacing (5) with, would work better or worse?\n\nPlease review the discussion in Appendix D. \nIn summary, obstacles arise when considering elimination-based or maximum posterior variance-based algorithms in our setup, primarily due to unknown failure regions. \nExploring a more theoretically well-behaved algorithm is an essential avenue for future research, and we leave this as a topic for future work.\n"}, {"review_id": "G6TTMCl1mu", "reviewer": "Reviewer_Mr4k", "summary": "The paper extends the gaussian process UCB algorithm to the case where some observations are failures. i.e. They solve for the case where x^* = argmax_{x in X} {f(x) such that c(x) =0}. Here c(x) = 1 may be thought of as an indicator of failure. The crucial part is to adaptively ignore the neighbourhood of the failure point to choose the next evaluation point. The paper does a number of experiments to show that their algorithm works with respect to the claims made.", "questions": "- What is scaling of regret with dimension? Though your experiments indicate poor scaling with d, your regret expression doesn't explicitly show the dependence?\n- \\hat{T}^* = \\theta_0/\\eta)^{1/alpha} + 1, and regret is less thant B(\\hat{T}^* -1). Why add and subtract 1? What is the order dependence on T?\n- Typically people speak about cumulative, or simple regret. You have a theorem for regret r_t at time t. Can your theorem be written as a cumulative regret guarantee?\n- What are your assumptions on C() that helps you to ignore the neighbourhood of a failure point? For example, adversarially, I could give c() to be a delta function at an arbitary number of points whose neighbourhood contains the optimal function. There are strong assumptions on f(), but the assumptions on c() were not clear to me.", "limitations": "- Seems like a minor improvement over non-failure aware GP based optimization Algorithms. \n- If you disregard failures in GP-UCB, does it not converge? If so, why is the regret on that algorithm in your experiments never below 1 (what is the function c you have considered)?\n- Seems like scaling with dimension d is quite poor? Does random restart help in such cases?", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Excellent numerical experiment on quasicrystals. This was quite novel to consider the Al-Cu-Mn crystal system.\n- The idea of applications of GP-UCB to account for failures of observation was quite novel.\n- The notation of failure as a simple function c() was well formulated.", "weaknesses": "- The model setup is slightly weak. For example, has consideration been given to stochastic c(·)? How easy is it to extend to unbounded domain beyond [0,1]^d?\n- The definition of r_t says that when \\hat{x}_t is not observable, r_t is f(x^*) - min_{x in X} f(x). This is just 0. Shouldn't regret be based on an output of the algorithm? If non-observable, the algorithm can simply output an element from observed data that it is sure is observable. Why are you defining regret to be 0 in such a case?\n- There could be improvements in paper clarity. For example:\n\n    > Please could you clean up the notations for kernel function k? Since it plays a central role in the theorems, it would be useful to setup the relationship between k(·) and the optimization function f(·) a little more cleanly.\n\n- The authors claim that \"Then, we provide the first regret upper bound of the GP optimization problem (1)...\" But from my understanding, this well cited paper from 2009 provides an upperbound for GP-UCB (see Theorem 1)? https://arxiv.org/pdf/0912.3995.pdf\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments.\nHowever, we believe that there are some misunderstandings in the \"Weaknesses\" section that the reviewer pointed out.\n\n> The definition of r_t says that when \\hat{x}t is not observable, r_t is f(x^*) - min{x in X} f(x). This is just 0.\n\nSince our setup considers the maximization problem as in Eq. (1), $r_t$ does not become $0$ if $\\hat{x}_t$ is not observable.\nOur definition of regret is based on the worst-case value of $f$ if $\\hat{x}_t$ is not observable. \nIt should be noted that this style of performance metric is common in constrained GP-optimization fields (see, e.g., [1]).\n\n[1]Hernández-Lobato et al., \"A general framework for constrained Bayesian optimization using information-based search.\", 2016\n\n> But from my understanding, this well cited paper from 2009 provides an upperbound for GP-UCB (see Theorem 1)?\n\nIt should be noted that Theorem 1 of Srinivas et al. is not applicable to our problem setup.\nThis is because, in our scenario, the standard GP-UCB, which disregards failures, leads to the posterior of the Gaussian process not being updated.\nThus, the standard GP-UCB can be trapped at the same failure point.\nOur contribution lies in presenting the first algorithm for which an upper bound on regret is derived in the presence of unknown failure regions.\n\n> Has consideration been given to stochastic c(·)?\n\nWhile our paper does not consider the stochastic failure function $c$, it should be noted that practical applications where failures occur deterministically are not limited (e.g., the applications are discussed in [2]). \nFurthermore, algorithms suited for such scenarios differ from those designed for stochastic failures. \n(The distinctions between deterministic and stochastic failures are also examined in [2].)\n\nGiven the fundamental dissimilarity between settings involving stochastic and deterministic failures, we believe that their theoretical analyses should be distinct and separate. \nFor instance, even the definition of regret for a stochastic failure problem is not straightforward, underscoring the difference between these contexts.\n\n[2]Bachoc et al., \"Gaussian process optimization with failures: classification and convergence proof.\", 2020\n\n\n\n> How easy is it to extend to unbounded domain beyond [0,1]^d?\n\n\nFrom a theoretical standpoint, our algorithm can be extended to any compact convex input domain, as described in a footnote on page 4. (Unbounded input domain is not generally considered even in standard GP-optimization field.)\nThe upper bound on regret for this extended version of the algorithm has already been provided in Appendix A.2 (Theorem A.6).\nIt should be noted that the fundamental contribution of our paper, which is to build the first regret upper bound within the context of a failure-aware setup, is not limited by this aspect.\n\n\nFrom a practical standpoint, our algorithm requires to solve the set-covering problem over the input domain (as detailed in Lines 178-185). \nHowever, set-covering problem is NP-complete in general.\nTherefore, we provide a heuristic way (discussed in Lines 250-262) to avoid this issue for the input domain of bounded hypercube, which is one of the common settings in the GP-optimization field. \nAnother common setting is a discrete input domain, in which the set-covering problem is easily solved. Thus, our algorithm is also applicable to the discrete input domain. \nThe practical extension for the more general continuous input domain is an important research direction. We will carefully add the discussions in a revised version of our paper.\n\nWe further give the answers to the reviewer's questions below.\n\n> What is scaling of regret with dimension? Though your experiments indicate poor scaling with d, your regret expression doesn't explicitly show the dependence?\n\nThe dependence on $d$ in the regret upper bound is characterized by the maximum information gain $\\gamma_{T; S_c}$ and $\\tilde{T}_s$. The rate of the former is shown in Lines 112-114. The latter's definition is provided explicitly in Theorem 4.2.\n\n> \\hat{T}^* = (\\theta_0/\\eta)^{1/alpha} + 1, and regret is less thant B(\\hat{T}^* -1). Why add and subtract 1? What is the order dependence on T?\n\nAdding one is needed to make $\\tilde{T}^*$ as the upper bound of the step, which search space of our algorithm contains the optimal solution (L226-227). \nWe believe the current definition of $\\tilde{T}^*$ will allow us to give an intuitive explanation that is helpful to readers to interpret our regret upper bound. \nFurthermore, it should be noted that $\\tilde{T}^*$ is not dependent on $T$, but is the constant which only depends on failure function $c$ and the initial parameter of the algorithm. \n\n\n> Can your theorem be written as a cumulative regret guarantee?\n\nAs described in a footnote of page 3, the cumulative regret guarantees of our algorithms are provided in Appendix C (Theorem C.1 and C.2)\n\n\n> What are your assumptions on C() that helps you to ignore the neighbourhood of a failure point?\nFor example, ...\n\nAssumption 2.2 eliminates the case where the neighborhood of a failure point contains the optimal solution at all times.\nIf $c$ is a function whose value is 1 (failure) at points that are arbitrarily close to the optimal solution, neighborhoods of their failure points can contain optimal solution at all times, i.e., Assumption 2.2 is violated. \nAs concisely described in Lines 242-246 of Sec.4, we also discuss the possibility of loosening Assumption 2.2 in Appendix B.\n\n\n\n> If you disregard failures in GP-UCB, does it not converge?\n\nStandard GP-UCB in our setup does not converge. \nThis is because the posterior of $f$ will not be updated when an observation is failed, and the algorithm could be trapped in the same failure point (Lines 329-330).\n\nWe believe that most of the reviewer's concerns described in the \"Weakness\" section came from misunderstandings. We will carefully revise our paper to improve clarity. \n"}, {"review_id": "Nq7icRh2WG", "reviewer": "Reviewer_Yqeo", "summary": "This paper studies Bayesian optimization in the setting where observing the unknown function might fail, for instance due to numerical simulator returning NaN. The authors propose a UCB-type acquisition function for this setting, which is based on first restricting the domain to a feasible regions where failures are less likely to occur, and then applying standard UCB-based acquisition function constrained to that region. The authors present a bound on the simple regret in this setting, and perform some experiments which consider only low-dimensional examples but show good performance compared to baselines.\n\nEDIT: I've updated my score in light of the rebuttal.", "questions": "Line 94: what do you mean by \"uses the modeling information of f\"? I didn't understand this sentence\n\nI'm confused about whether or not you assume you know the reproducing kernel of the RKHS the unknown function lies in explicitly, or not. Does the kernel of the unknown function need to match the kernel used for the GP prior? I think you assume it's known, which is reasonable - please let me know if that's correct and please make this more explicit in the text.\n\nTheorem 4.2: should there be a \"with probability 1-\\delta\" quantifier for \"the estimated solution exists ..\"? What stops the algorithm from getting arbitrarily unlucky and obtaining no data at arbitrarily large times? Does this have to do with the assumption that simulator failure is deterministic?\n\nTypos and English grammar fixes below:\n* Line 40: \"converges the optimal\" -> \"converges to the optimal\"\n* Line 47: what does it mean \"has a close relation to this study\"?\n* Line 52: \"under the settings\" -> \"under the setting\"\n* Line 54: \"that a noisy observation\" -> \"that noisy observation\"\n* Line 58: \"modifying the settings of our study\" -> unsure what this sentence means\n* Line 60: \"that takes into account failures\" -> \"that take into account failures\"\n* Line 63: \"that the observation failure\" -> \"that observation failure\"\n* Line 65: \"as described in [2]\" -> \"as described in Bachor et al. [2]\"\n* Line 70: \"one latent function. (e.g. ...\" -> \"one latent function (e.g. ...\"\n* Line 78: \"which is a conditional\" -> \"which is conditionally\"\n* Line 117: \"each of its observation\" -> \"each of its observations\"\n* Line 122: \"The regret upper bound cannot be obtained\" -> \"A regret upper bound cannot be obtained\"\n* Line 247: \"Practical consideration\" -> \"Practical considerations\"", "limitations": "*Almost* adequately - the main thing that is missing is a more comprehensive discussion on the dependence of their proposed methods on the dimension of the unknown function's domain.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper's topic is important and of key relevance for practical Bayesian optimization, where observation failure is a common issue which is mostly addressed using ad-hoc methods. They have clearly described their setting and distinguished it from others, and everything is properly cast into a well-defined mathematical problem, which is clearly described.\n\nThe introduction is well-written and does a good job of introducing the reader to both the setting and the authors' approach, and gives due credit to prior work.\n\nFigure 1 is conceptually very nice and provides a good illustration that makes it easy for the reader to see early on what is going on: the authors' algorithm splits the state space into a region where observations are likely to work, and another region where they are unlikely to work. One request: **please make the fonts bigger to match the font size of the text**, so readers with not the best eyesight can actually see everything.\n\nThe authors do a good job at focusing on their part of the contribution, and don't take up lots of space stating obvious corollaries of their result, but at the same time also do a good job at stating what else can be done, for instance by combining their analysis with prior work such as RBF specific bounds in the setting without failures.\n\nOverall, I think this is a good paper with various fixable flaws described below, so I don't have too many additional comments.", "weaknesses": "Details of the proposed algorithm are unclear. From my reading of the paper, I understand that what you do is define a \"failure-safe space\" consisting of the full space minus a set of infinity-balls around points where failure occurred. Then, at certain points in time whose definition I still don't fully grasp, you cut the radius of the balls by half, so that points which were previously excluded from consideration because they were too close to a failure are now considered again. Is this correct? If so, this needs to be stated much more explicitly and much more clearly, using an intuitive description in addition to equations or notation-heavy pseudocode. If not, please correct my understanding.\n* In particular, please provide a more intuitive explanation of what \\theta_t is doing, and in what cases it gets cut by half - I am still confused how when this happens\n\nExperiments\n* Unless I have missed something, the highest dimension problem used in experiments is three. This is very limiting compared to much of the literature and much smaller than many problems of practical interest\n* The quasicrystal experiment is very light on details, in spite of being a really cool illustration. This section deserves significantly more text on both the setup and results so that readers can understand and contextualize what is going on. The fact that this problem is, unless I am mistaken, three-dimensional, could also have been stated more explicitly\n\nIn the analysis, the regret bound presented seems fairly specific, since it is talking only about simple rather than cumulative regret, and has a fairly specific way through which the point returned is selected. In bandits at least this kind of setting is certainly out there, but not something I see in every paper, so I'm a bit unsure as to whether the ideas are general or very specific to this setting.\n* As a result, I'm curious: how strongly does the theoretical analysis and empirical performance depend on the specific way through which the point returned is selected?\n\nWriting: the paper tends to go back and from between parts that were very clear and well-written, and parts where I was confused. Part of this is due to typos and grammar, which is fixable. However, there are other times where grammar is not the issue, and there are many points where the paper would be much better if it provided helpful hints to the reader to orient their reading in the right way to avoid them becoming confused. Detailed presentation comments below:\n* The paper has slightly too many acronyms, for instance GPC, which is not an important enough concept in this paper to make it into an acronym and should instead be spelled out\n* There's slightly too much discussion on prior work, which takes up space that is needed elsewhere - I'd prefer to see this part tightened up\n* When I first read this, I was confused about definition of regret, namely why is r_t = f(x^*) - min_{x\\in X} f(x) not equal to zero, but then I realized this is because the authors are interested in reward maximization (bandit style) rather than cost minimization (online learning style). A line which saves the reader time by clarifying this should be added.\n* Aesthetic: curly brace notation for the posterior is really ugly - consider using parentheses\n* **Please number all equations, not just the ones you think are important.** The convention of only numbering important equations is archaic, outdated, and harmful to readers. Numbering everything prevents readers from having to ask about \"the second unnumbered equation on page 2\", and then the person who was asked is confused whether it's the second equation from the top or from the bottom. Doing so will significantly improve the paper.\n* Why should the logdet be called the maximum information gain? If you're going to use these terms, you should connect this with mutual information or some kind of related quantity. This choice of terminology should be explained rather than just parachuted in.\n* Since the notion of \"interior point\" is introduced in the definition directly below it, maybe the sentence should include \"introduced below\" or similar.\n* Assumption 2.2: please add a textual note that this is an infinity-ball, not a Euclidean ball, so that someone who misses the infinity symbol doesn't get confused\n* Proposed algorithm could be replaced with a more informative section title\n* No need to introduce packing numbers with too much detail, the audience of this paper will know about that", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. \nIn the revised version of our paper, we will carefully fix the typos, grammar mistakes, and clarity issues, which the reviewer kindly pointed out.\nWe describe the answers to the questions of the reviewer below.\n\n\n> Then, at certain points in time whose definition I still don't fully grasp, you cut the radius of the balls by half, so that points which were previously excluded from consideration because they were too close to a failure are now considered again. \nIs this correct?\n\nWe cut the radius of the balls by half when the algorithm detects that previous failure points exclude overall search space. \n(That is, $\\mathcal{X}_t$ defined on Eq.(4) becomes an empty set.) \nThe monotone decreasing function $b$ has a role in controlling so that points that were previously excluded from consideration because they were too close to a failure are considered again.\nThe detail is described in Lines 178-185.\n\n\n> In particular, please provide a more intuitive explanation of what $\\theta_t$ is doing, and in what cases it gets cut by half - I am still confused how when this happens\n\nThe parameter $\\theta_t$ has a role in avoiding the event that $\\mathcal{X}_t$ becomes an empty set. \nIf we do not halve $\\theta_t$ at all times (that is $\\theta_t = \\theta_0$ at all times), this event might occur, especially when the user sets $\\theta_0$ without prior knowledge about the failure function in practice. \nFor example, consider 1 dimensional problem with $\\mathcal{X} = [0, 1]$, $\\theta_0 = 0.2$, and $b(t) = (1/t)^{1/2}$. \nMoreover, let us assume that success region $S_c = [0.0001, 0.0002]$, and the user chooses $x_1$ as $x_1 = 0.0$. \nIn this extreme case, $\\mathcal{X}_t$ becomes empty set at least $t=25$ since $25$ is 0.04-packing number of $[0, 1]$ (the radius at $t=25$ is $0.04:= (0.2/\\sqrt{25})$, and all $x_t$ will fail before $t=25$).\nIntuitively, the event that $\\mathcal{X}_t$ becomes an empty set will occur if the user sets $\\theta_0$ with too large value (or sets $b(t)$ as too slow decreasing rate function) in contrast to the size of success region. \nBy halving \\theta_t when $\\mathcal{X}_t$ is detected to be an empty set, our algorithm could define non-empty search space $\\mathcal{X_t}$ and choose $x_t$ at any time step without knowing unknown failure regions.\n\n\n> In the analysis, the regret bound presented seems fairly specific, since it is talking only about simple rather than cumulative regret, and has a fairly specific way through which the point returned is selected. \nIn bandits at least this kind of setting is certainly out there, but not something I see in every paper, so I'm a bit unsure as to whether the ideas are general or very specific to this setting.\n\nAs far as we know, the estimated solution based on a lower confidence bound, such as Eq.(6), is commonly used in the GP-optimization field (e.g., [1, 2]). \nThe only difference between our setup and standard settings is that the index $\\hat{t}$ of Eq.(6) is defined over the previous success index set $I_t^{(S)}$. \n(The index $\\hat{t}$ of an estimated solution is defined over the overall time index set ${1, \\ldots, t}$ in the standard setting.)\nWe believe that our definition of $\\hat{x}_t$ is a natural extension of previous works and not too specific to our setting. \n(As described in a footnote of page 3, it should be noted that the cumulative regret upper bound of our algorithm is also provided in Appendix C.)\n\n[1]Bogunovic et al., Adversarially robust optimization with Gaussian processes, 2018\n\n[2]Kirschner et al., Distributionally robust Bayesian optimization, 2019\n\n\n> how strongly does the theoretical analysis and empirical performance depend on the specific way through which the point returned is selected?\n\nAs described in the earlier answer, the only specific point of our estimated solution is that the index $\\hat{t}$ of Eq.(6) is defined over the previous success index set $I_t^{(S)}$ without using failed index set. If we use failed index set to define $\\hat{t}$, the estimated solution might be a failure point (that is, worst-case regret will occur).\n\n\n> Line 94: what do you mean by \"uses the modeling information of f\"? I didn't understand this sentence\n\nThis sentence simply means that our algorithm uses the posterior mean and variance of the GP modeling of $f$ (e.g., Eq.(5), Eq.(6)).\n\n\n\n> I'm confused about whether or not you assume you know the reproducing kernel of the RKHS the unknown function lies in explicitly, or not. \nDoes the kernel of the unknown function need to match the kernel used for the GP prior? I think you assume it's known, which is reasonable - please let me know if that's correct and please make this more explicit in the text.\n\nYes, we assume that a kernel $k$, which corresponds to RKHS $\\mathcal{H}_k$ the function $f$ lies, is known. \nFurthermore, we assume that the kernel used in GP matches the kernel of $\\mathcal{H}_k$. We will make these assumptions more explicit in Sec.2 in the revision.\n\n\n> Theorem 4.2: should there be a \"with probability 1-\\delta\" quantifier for \"the estimated solution exists ..\"? \nWhat stops the algorithm from getting arbitrarily unlucky and obtaining no data at arbitrarily large times?\n\nThe guarantee for the existence of the estimated solution in Theorem 4.2 does not require probabilistic arguments. \nUnder Assumption 2.2, our algorithm design stops the algorithm from getting arbitrarily unlucky and obtaining no data at arbitrarily large times. \nIntuitively, as described in Lines 142-152, our algorithm is carefully designed to cover overall input space without breaking the regret guarantee. \nTherefore, if there exists a success region whose volume is strictly greater than zero (which is assumed in Assumption 2.2), the algorithm eventually observes the success point within finite time steps."}, {"review_id": "2npPfaHWr4", "reviewer": "Reviewer_ven9", "summary": "1. A failure-aware gaussian process optimization algorithm is proposed. A key difference from existing GP constrained optimization is that here we cannot obtain a direct observation from the latent failure function.\n2. The algorithm's regret bound is presented.\n3. Some practical issues are discussed.\n4. Numerical experiments are conducted, the proposed algorithm shows superiority on some benchmarks.\n", "questions": "Can we have a more \"rigorous\" theoretical analysis of the \"real\" algorithm(replacing set covering part by its heuristic approximation) and still derive the regret bound? ", "limitations": "No potential negative social impact is seem.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Problem formulation is novel.\n2. Theoretical derivation is solid\n3. Practical issues are considered and numerical experiments show its potential. ", "weaknesses": "1. Learning feasible set without knowing failure function is a key feature of paper's problem formulation. The NP-complete set covering problem is assumed to be fully solved in theoretical analysis while numerical experiments adopt a heuristic approximation algorithm.  It seems there is a gap between theoretical part and numerical part. \n2. Algorithm doesn't show dominant superiority on all all numerical benchmarks. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments.\n\n> Can we have a more \"rigorous\" theoretical analysis of the \"real\" algorithm(replacing set covering part by its heuristic approximation) and still derive the regret bound?\n\nWe consider the input domain of bounded hypercube, on which the NP-complete set-covering problem is needed to solve, as one of the most common settings of the GP-optimization field. Another common setting is a discrete input domain $\\mathcal{X}$, on which set-covering problems are easily solved by brute force way with $\\mathcal{O}(d|\\mathcal{X}|^2)$ computational costs.\nWe conjecture that by combining discretization arguments used in previous works (e.g., [1, 2, 3]), our algorithm can be extended to a general continuous input domain without breaking the theoretical guarantee so that the set-covering problem on the original continuous input domain is not required to solve. \nThis direction of research is interesting, and we leave it as future work. \n\n\n[1]Chowdhury et al., \"On kernelized multi-armed bandits.\", 2017\n\n[2]Vakili et al., \"Optimal order simple regret for Gaussian process bandits.\", 2021\n\n[3]Li et al., \"Gaussian process bandit optimization with few batches.\", 2022"}]

Author rebuttal:

Meta-review: This paper tackles the problem of black-box optimization with observation failures in certain regions of the objective function. It proposes an extension of GP-UCB to this setting and provides a theoretical analysis that culminates in regret bounds.

There is consensus among the reviewers that the setting of BO with observation failures is important and that this paper provides a nice solution for it. The authors provide a comprehensive theoretical analysis and empirical evaluation. One reviewer liked in particular the experiment on quasicrystals. Several reviewers also raised questions (e.g. why the radius of the balls are cut in half or the definition of regret in rounds with observation failures) and concerns regarding clarity. The authors' responses could clarify those questions and some misunderstandings so that there is consensus that the paper is overall well presented (after some modifications).

There is a generally positive assessment of the paper by all reviewers after the discussion with the authors, but some general weaknesses of this work persist. Although the analysis seems well executed, it largely follows existing techniques. The algorithm is perhaps also a somewhat expected extension of GP-UCB. Further, the empirical evaluation is limited to 3-dimensional problems. Although high-dimensional problems are still extremely challenging for BO, 3 dimensions are still smaller than what is usually considered in BO benchmarks (6+ dimensions). This does leave some questions open regarding the applicability of this work.

Overall, this leaves the paper in the borderline regime. Since all reviewers are leaning positively, the paper is recommended to be accepted.
Decision: Accept (poster)