Active Learning for Level Set Estimation Using Randomized Straddle Algorithms
Authors: Yu Inatsu
Shion Takeno
Kentaro KUTSUKAKE
Ichiro Takeuchi
Venue: Accepted by TMLR ()

Abstract: Level set estimation (LSE) the problem of identifying the set of input points where a function takes a value above (or below) a given threshold is important in practical applications. When the function is expensive to evaluate and black-box, the straddle algorithm, a representative heuristic for LSE based on Gaussian process models, and its extensions with theoretical guarantees have been developed. However, many existing methods include a confidence parameter, $\beta^{1/2}_t$, that must be specified by the user. Methods that choose $\beta^{1/2}_t$ heuristically do not provide theoretical guarantees. In contrast, theoretically guaranteed values of $\beta^{1/2}_t$ need to be increased depending on the number of iterations and candidate points; they are conservative and do not perform well in practice. In this study, we propose a novel method, the randomized straddle algorithm, in which $\beta_t$ in the straddle algorithm is replaced by a random sample from the chi-squared distribution with two degrees of freedom. The confidence parameter in the proposed method does not require adjustment, does not depend on the number of iterations and candidate points, and is not conservative. Furthermore, we show that the proposed method has theoretical guarantees that depend on the sample complexity and the number of iterations. Finally, we validate the applicability of the proposed method through numerical experiments using synthetic and real data.

Published in Transactions on Machine Learning Research (11/2024)
Active Learning for Level Set Estimation Using Randomized Straddle Algorithms
Yu Inatsu
imatsr..pn@nttech.c...
Deportment of Computer Science, Nagoya Institute of Technology
Shion Takeno
mall
Department of Mechanical Systems Engineering, Graduate School of Engineering, Nagoya University RIKEN Center for Advanced Intelligence Project
Kentaro Kutsukake
Batssukake.kentaeee maw.eerro.@.ff...ll....mo. mai.aagoyau......
Instttute of Materials and Systems for Sustainabilily, Nogoya University Department of Materials Process Engineering, Graduate School of Engineering, Nagoya University
Ichiro Takeuchi
takeuchi, icciio.icchio..... cecaaioonnn.. wagoyuwwww..
Department of Mechanical Systems Engineering, Graduate School of Engineering, Nagoya University RIKEN Center for Advanced Intelligence Project
Reviewed OpenReview: https: openreview. net/ formm? id= N8M2ygRics
Abstract
Level set estimation (LSE) the problem of identifying the set of input points where func- tion takes a value above (or below) a given threshold important in practical applications. When the function expensive to evaluate and black-box, the straddle algorithm,, a rep- resentative heuristic for LSE based on Gaussian process models, and its extensions with theoretical guarantees have been developed. However, many existing methods include confidence parameter, 81/2 that must specified by the user. Methods that choose s//²2 heuristically do not provide thcoretical guarantecs. In contrast, theoretically guarantced values of 3//22 need to be increased depending on the number of iterations and candidate points; they are conservative and do not perform well in practice. In this study, we propose a novel method, the randomized straddle algorithm, in which B, in the straddle algorithm replaced by a random sample from the chi-squared distribution with The confidence parameter in the proposed method does not require adjustment. does not depend on the number of iterations and candidate points, and is not conservative. Further- more, we show that the proposed method has theoretical guarantees that depend on the sample complexity and the number iterations. Finally, we validate the applicability of the proposed method through numerical experiments using synthotic and real data.
degrees of freedom.
1 Introduction
In various practical applications, including engineering, level set estimation (LSE) the estimation of the region where the value of function is above (or below) given threshold, 0 is important. A specific example of LSE is the estimation of defective regions in materials for quality control. For instance, in silicon ingots, which are used in solar cells, the carrier lifetime value a measure of the ingot's quality is observed at each point on the ingot's surface before shipping, allowing identification of regions that can or cannot be used as solar cells. Since many functions encountered in practical applications, such as the carrier lifetime the silicon ingot example, are black-box functions with high evaluation costs, is desirable identify the desired region without performing exhaustive search of these black-box functions.

---

Published in Transactions on Machine Learning Research (11/2024)
Bayesian optimization (BO) (Shahriari et al. 2015) is powerful tool for optimizing black-box functions with high evaluation costs. BO predicts black-box functions using surrogate models and adaptively observes the function values based on a criterion called acquisition functions (AFs). Many studies have focused on BO, particularly on developing new AFs. Among these, BO based on the AF known as Gaussian process upper confidence bound (GP-UCB) (Srinivas el al. 2010) offers a theoretical guarantee for finding the optimal solution and a useful method that is flexible and extendable to various problem scttings. GP-UCB-base methods have been proposed in various settings, such as the LSE algorithm (Gotovos al.] 2013). multi- fidelity BO (Kandasamy et al., 2016; 2017).
multi-objective BO (Zuluaga et al. 2016 Inatsu et al. 2024
high-dimensional BÓ (Kandasamy et al. 2015
Rolland et al.) 2018), parallel BÔ (Contal et al. 2013), , cascade Kirschner et al. 2020). These GP-UCB-based methods, like
BO Kusakawa et al. 2022), and robust BO
the original GP-UCB-based BO, provide some theoretical guarantee for optimality in each problem setting,
However, GP-UCB and its related methods roquire the user to specify a confidence paramcter, ////2 to adjust the trade-off between exploration and exploitation, where t is the mumber of iterations in BO. As a theoretical value for GP-UCB, (Srinivas et al. (2010) proposes that 8//² should increase with the iteration 4, but this value is conservative, and Takkeoo el al. 2023) has pointed out that it results in poor practical performance. To solve this issue, [erk et al. (2021) proposed a randomized GP-UCB (RGP-UCB), replacing Br with a ramdom sample from a gamma distribution. They demonstarated through numerical experiments that the practical performance of RGP-UCB is better than that of the original GP-UCB. Althought they also provided the theoretical regret analysis, their theoretical results and proofs of theorems contain some non- ignorable technical issues (see, Appendix C in Takeno et al. (2023)). Recently, Takeno et al. (2023) proposed an improved RGP-UCE (IRGP-UCB), which uses an AF that randomizes Bg in GP-UCB by replacing it with random sample from a two-parameter exponential ial distribution. IRGP-UCB does not require parameter tuning, and the realized values from the exponential distribution are less conservative than the theoretical values in GP-UCB, resulting in better practical performance. Furthermore, it has been shown that IRGP- UCB provides a tighter bound for the Bayesian regret, one of the optimality measures in BO, than existing methods. However, it is not clear whether IRGP-UCB can be extended to various methods, including LSF. This study proposes a new method for LSE based on the randomization used in IRGP-UCB.
1.1 Related Work
GPs Rasmussen & Williams 2005) are often used as surrogate models in BCJ and mothods using GPs for LSE have also been proposed. A representative houristic using GPs is the straddle hcuristic by Bryann et al. (2005). The straddle method balances the trade-off between the absolute value of the difference bet the GP model's predicted mean and the threshold value, and the uncertainty of the prediction. However, no theoretical analysis has been performed on this method. An extension of the straddle hcuristic to cases where the black-box function is a composite ionction was proposed by Bryan & Schneider (2008), but this too is a heuristic method that lacks theoretical analysis.
As a GP-UCB-bascd method using GPs, Gotovos et al. 2013 proposed the LSE algorithm. The LSE algorithm uses the same confidence parameter, 8372 as GP-UCB and is based on the degree of violation from the threshold relative to the confidence interval determined by the GP prediction model. It has been shown that the LSE algorithm returns an e-accurate solution for the true set with high probability. [Bogunoiic let al. (2016) proposed the truncated variance reduction (TRUVAR) method, which can handle both BO and LSE. TRUVAR also accounts for situations where the observation cost varies across observation points and is designed to maxinize the reduction in uncertainty in the uncertain set for each observation point per unit cost. Additionally, Shekhar & Javidi (2019) proposed chaining- method, which handles the case where the input space is continuous. As an expected improvement-bent based method, Zanette et al. (2019) proposed the maximum improvement for level-set estimation (MILE) method. MILE is an algorithm that selects the input point with the highest expected number of points estimated to be in the super-level set,, one step ahead, based on data observation.
Although both BO and LSE for black-hox functions adaptively select the next input point, their objectives are fundamen- tally different. and we will leave the detailed description of BO comprehensive survey (Shahriari et al. 2015).
2

---

Published in Transactions on Machine Learning Research (11/2024)
LSE methods have also been proposed for different settings of black-box functions. For example, Letham et al. (0222) introduced method for cases where the observation of the black-box function is binary. In the robust BO framework, where the imputs of black-box functions are subject to uncertainty, LSE methods for various robust measures have been developed. [wazaki et al. (2020) proposed LSE for probability threshold
robustness measures, and Tnatsu et al. (2021) introduced LSE for distributionally robust probability threshold
robustness measures both of which are acquisition functions based on MILE. Additionally, Hozumi et al. (2023) proposed straddle-based method within the framework of transfer learning, where large amount of data for similar functions is available alongside the primary black-box function to be classified. [nnasu ct al. (020)) introduced MTL.-baaeed method for the LSF. problem in settings where the uncertainty of the input changes depending on the cost. Mason et al. (2022) addressed the LSE problem in the context where the black-box function is an element of a reproducing kernel Hilbert space.
The straddle method, LSE algorithm, TRUVAR, chaining-based algorithm, and MILE, which have been proposed under scttings similar to those considered in this study, have the following issues. The straddle method is not an acquisition function proposed based on GP-UCB, but it includes the confidence parameter 8./2 which is essentially the same as in GP-UCB, However, the value of this parameter is determined heuristically, resulting in method without theoretical guarantees. The LSE algorithm and TRUVAR have been theoretically analyzed, but, like GP-UCB, they require increasing the theoretical value of the confidence parameter according to the iteration t, which makes them conservative. The chaining-based algorithm can handle continuous spaces through discretization, but it involves many adjustment parameters. The recommended theoretical values depend on model parameters, including kernel parameters of the surrogate model, and are known only for specific settings. MILE is designed for cases with a finite number of candidate points and does not support continuous settings like the chaining- based algorithm.
1.2 Contribution
This study proposes a novel straddle AF called the randomized straddle, which introduces the confidence parameter randomization technique used IRGP-UCB and solves the problems described in Section [.] Figure Ssoows a comparison of the confidence parameters in the proposed AF and those in the LSE algorithm. The contributions of this study are as:
This study proposes randomized straddle AF, which replaces P in the straddle hcuristic with a random sample from the chi-squared distribution with two degrees of freedom (one-parameter exponential distribution with parameter 1/2). We emphasize that unlike the LSE algorithm, the confidence parameter in the randomized straddle does not need to increase with the iteration t. Additionally, / in the LSE algorithm depends the number of candidate points |2), and a!!² increases as | increases, while 3//² in the randomized straddle does not depend on |2 and can be applied even when X' is an infinite set. Furthermore, the expected value of the realized value of // in the randomized straddle is 22T/2 se 1.25, which is less conservative than the theoretical value in the LSE algorithm.
We show that the randomized straddle guarantees that the expected loss for misclassification in LSE converges to O. In particular, for the misclassification loss ri = | Exex 4(xx), the randomized straddle guarantees E[r.] = O(Vn/t), where 4(x) is 0 if the input point x is correctly classified, and (xx) - 0), misclassified, and 7t. is the maximum information gain which a commonly used sample complexity measure.
Additionally, we conducted numerical experiments using synthetic and real data, which confirmed that the proposed method has performance equal or better than existing methods.
2 Preliminary
Let f x + R be an expensive-to-evaluut black- box function, where X C Rd is finite set, or an infinite compact set with positive Lebesgue measure Vol(2'). Also let 0 E R be known threshold given by the user.
3

---

Published in Transactions on Machine Learning Research (11/2024)
Histagram g
Borrtion g
Number candidate points &
Proposed LSE
Proposed
100000
LSE
Confictnce paramriter
Confidlezce parairater
60000
20000
200
400
600
800
1000
1e+00
1e+02
1e+04
1e406
1e+08
1e=10
B.
Iteration
Number candidate points
Comparison of the confidence parameter 31/2 in the randomized straddle and LSE algorithms. The left-hand side figure shows the histogram of g1/2 when 3 is sampled 1,000,000 times from the chi- squared distribution with two degrees of freedom. The red line in the center and right figure denotes E = /2 1.25, the shaded area denotes the 95% confidence interval of 8!/², and the black line denotes the theoretical value of 31/² in the LSE algorithm given by 8, = / log( (//////2//(66)))) where 0.05. The figure in the center shows the behavior of 8!/2 as the number of iterations increases when the number of candidate points |X] fixed at 1000, whereas the figure on the right shows the behavior of s//² as the number of candidate points | increases when the number of iterations is fixed at 100.
Figure 1:
The aim of this study to efficiently identify subsets H and L of X defined
H = (x X f(x) ( 0), L' fo E <)).
For each iteration 2 follows the normal distribution with mean 0 and variance - In this study, we assume that f is sample path from a GP GP(O, k), where GP(O, k) is the zero mean GP with a kernel function k(.-). Moreover, we assume that -) is a positive-definite kernel that satisfies k(æ, < for all x E X, and f, are mutually independent.
query X, and f(x,) is observed with noise y f(x)) + Ex, where
Gaussian Process Model We use a GP surrogate model GP(O, k) for the black-box function. Given a the number of iterations, the posterior distribution of is again a
dataset Dt = ((zj. My where GP. Then, its posterior mean (a() and posterior variance (x) can be calculated as:
(=)x) = kx(x)) (K, + noose I (x)) k(xx x) (x))) (Ke + -
yt,
(1)
kx(x),,
where (x( is the t-dimensional vector whose i-th element is k(x,, x(),,;), He (yI...., ..) K, the t matrix whose (j, k))thh element is ax),,,))), I, is the t t identity matrix, with superscript T that indicates the transpose of vectors or matrices. In addition, we define Do 0, po(x) 0 and (z()) k(x
3 Proposed Method
In this section, we describe method for estimating H* and L based on the GP posterior and an AF for determining the next evaluation.
4

---

Published in Transactions on Machine Learning Research (11/2024)
3.1 Level Set Estimation
First, we propose a method estimate H and I.* While an existing study (Gotovos al. 2013 proposes an estimation method using the lower and upper bounds of credible interval of f(æ), this study proposes estimation method using the posterior mean instead of the credible interval.
Definition 3.1 (Level Set Estimation). For each & 2 1, we estimate H* and I,* as:
H {x E X (4-1(1) 0), T, far X (-)) k)
(2)
By definition 3.1 any X' belongs either Hy or Lt, and He L, X. Therefore, the unknown set, in existing study (Gotovos al. 2013). is not defined in this study.
3.2 Acquisition Function
In this section, propose AF for determining the next point to be evaluated. For each t 2 and X, we define the upper bound uc) and lower bound 1cb;-((x) in the credible interval of f f(x) as
ucb;-1(z) = (1-(()))))) + 2/ 1 leb;-1(x) pc-1(x)) - 2 1
where 3//2 2 0 is a user-spocified confidence parameter. Here, the straddle heuristic STR,-1(2)) proposed by Bryan et al. (2005) defined as:
STR,-1 6///3 01-20_1())) (x)) 0).
Thus, by using ucb and (x)), (TR(-1(x) can rewritten as
STR,-1(4) = min(ucb((1(z)) - 0, leb;-1(x)).
We consider sampling 3r of the straddle heuristic from probability distribution. In the framework of black- box function maximization, Takeno et al. (2023) uses sample from two-parameter exponential distribution as the confidence parameter of the original GP-UCB. The two-parameter exponential distribution considered by Takeno et al. (2023) can be expressed as 2 log( (1/2))+s where s follows the chi-squared distribution with two degrees freedom. Therefore, we use a similar argument and consider 3e of the straddle heuristic as a sample from the chi-squared distribution with two degrecs of froedom, and propose the following randomized straddle AF.
Definition 3.2 (Randomized Straddle). For each 22 1, let Be be sample from the chi-squared distribution with two degrees of freedom, where B Br, $1,...,,,, are mutually independent. Then, the randomized straddle (x) is defined as follows:
(x)( = max max (ucb: - 0, (cb;-1
(3)
Hence, using (x), the next point to be evaluated is selected by æ; arg max (x)). Figure 2 shows the difference in the input points selected when using (x)) with different ,/ Takeno et al. (2023 adds a constant >log(1X')/2) which depends on the number of elements in X' to the sample from the chi-squared distribution with two degrees of freedom. In contrast, the random sample proposed in this study does not require the addition of such constant. As result, the confidence parameter in the randomized straddle does not depend on the number of iterations t or the number of candidate points. The only difference between the straddle hcuristic (TR,-1(x) and equation 3 is that /2//2 is randomized, and equation 3 performs a max operation with 0. We describe in Section that this modification leads to theoretical guarantees. Finally, we give the pseudocode of the proposed algorithm in Algorithm
5

---

Published in Transactions on Machine Learning Research (11/2024)
Itaration 20
Itaration 20
Iteration 20
2
8
xX
P
"
5
-3
B 81/2
B B1/2 = 10
Proposed
Figure 2: Comparison of points selected by (x-1(x) with different 8//2. The red line represents the true black-box function f(x) 5 exp(-(x + 5)2) cx 5)3) 2 exp((=²²) - 1, the black line represents the posterior mean, and the blue crosses represent the observed points. The figures on the left, center and right show the differences for 20 observation points when using, respectively, 81/2 = 1, 3./² 10 and which follows the chi-squared distribution with two degrees of freedom, in the calculation of (x), where = - is chosen the initial point under the observation noise o 10-2 and threshold 0 = 3. Since (TR;-1(x) represented as STR;-1(#) = 3//²0 the second term of (1) dominates, and a result, it can be seen that only values whose posterior mean are close to the threshold are observed. Conversely, when 8. = 10, 3//2 is large so the first term of (TR,-1(x) dominates, resulting in the AF that almost the same as uncertainty sampling, and can be seen that the selected inputs are spaced almost equally apart. the other hand, these behaviors are not observed with the proposed method.
oz a (x) (x)))()) 0,, when 3!/2 = 1, 8 is small so
Algorithm Active Learning for Level Set Estimation Using Randomized Straddle Algorithms Input: GP prior GP(O, k), threshold 0 e TR
for t= 1,2,,...., do Compute (z:) and (x) for each X' by equation 1 Estimate He and L, by equation 2
Generate 3r from the chi-squared distribution with two degrees of freedom Compute uz),-1(x), (c) and (x))(x)
Select the next evaluation point a; by æ; arg max (x=) Observe 1/1 = fxx;) + Er at the point æ;
Update GP by adding the observed data end for
Output: Return Hy and Lr as the estimated sets
4 Theoretical Analysis
In this section, we give theoretical guarantees for the proposed model. First, we define the loss (xx) for each x E N' and 2 as
if H x H
if x L x Lt-
((xx)=
[(x) 0
lap if a E L Hr
if if E H
0 f(x)

---

Published in Transactions on Machine Learning Research (11/2024)
Then, the loss r(H,, L)) for the estimated sets H2 and L, is defined as
1 [ Emex ((x)) Vol(x) Sx (x))d
if X is finite
r r(H, L1) =
if X is infinite
We also define the cumulative loss as R2 Ei= ri. Let " be a maximum information gain where T is one of indicators for measuring the sample complexity. The maximum information gain % often used in theoretical analysis of BO and LSE using GP (Srinivas et al., 2010 Gotovos et al., 2013), and Y is given by
sup N 2 {
log det [ + onii K2),
(4)
where T1...., Bt are any clements of X, and K, is the t x matrix whose (J. k)-th clement is k( Tx). Then, the following theorem holds.
Theorem 4.1. Assume that f follows GP(O, k), where k(;--) is a positive-definite kernel satisfying k(x, x) S for any x E X. For each 2 1, let 3e be sample from the chi-squared distribution with two degrees of freedom, where BI,..., Br, fl.....ep E,, f are mutually independent. Then, the following inequality holds:
E[R,] Vilh.
where Ci = 4/log(1 + ) and the expectation is taken with all randomness including J, St and Br.
From Theorem 4.1 the following theorem holds.
Theorem 4.2. Under the assumptions of Theorem 4.1 the following inequality holds:
Cire t
Ard
S
where Cj is given in Theorem 4.1
Note that Theorem 4.1 and 4.2 hold whether X' is a finite or infinite set. By the definition of the loss 44 (x), (ar) represents how far f(x) ) is from the threshold when x is misclassified, and rt represents the average value (x(x) across all candidate points. Under mild assumptions, it is known that 7r is sublinear (Srinivas lt al., 2010). Therefore, by Theorem 4.1 is guaranteed that R, also sublinear in the expected value sense. Furthermore, by Theorem 4.2. is guaranteed that Tt converges to 0 in the expected value sense. Here, we must emphasize that Theorem 4.1 and 4.2 cannot be derived by simply randomizing the confidence parameters of existing methods. First, although the proposed method is similar to existing methods in that it randomly samples the confidence parameters of the AF, several issues had to be resolved in order to derive theoretical guarantees in the LSE setting addressed in this paper. The proposed method is inspired by IRGP-UCB in Takeno et al. 2002). but they deal with maximization problems in the first place and consider regret/ f(==' - (ax;, which is the difference between the maximum value f(x²) and the function value / f(x;) at the observation point xy. They consider a Bayesian cumulative (or simple) regret as an evaluation index for theoretical analysis, and the theoretical validity of their method is based the fact that f(x") can be bounded from above with high probability, and as result, the expected value of f(x") can be bounded above by a certain expected value (Lemma 4.1 and 4.2 in Takeno et al. (2023) which is achieved by using UCB. On the other hand, the losses (((x) and ri (HH,, of the LSE addressed in this paper are essentially different from the regret f f(x*) (xx) and Bayesian cumulattve (or simple) regret in maximization problems. Therefore, was not clear whether claims similar to Lemma 4.1 and 4.2 in Takeno al. (2023) could be derived by simply randomizing the confidence parameters of some AF of LSE. In addition, existing LSE
2The discussion of the case where the loss is defined based on the maximum value r(He, Lt) maxzex 4(x) is given in Appendix A
According to equation 7t should be called the supremum information gain, but since the term maximum information gain also used when using sup operator (see, e.g., Vakili et (2023)) ). the rest of this paper will contimue call n the maxinum information gain.
7

---

Published in Transactions on Machine Learning Research (11/2024)
studies such as Gotovos et al. (2013) the classification rule includes the posterior mean, posterior standard deviation, and 3t, and the loss function depends on the classification rule. Therefore, since the classification rule includes Bi, theoretical analysis based on randomization was difficult. On the other hand, although the loss of the proposed mothod is based on the classification rule, unlike theirs, the classification rule itself does not include Be because the classification rule uses only the posterior mean, and as a result, randomization analysis became possible.
On the other hand, it is challenging to directly compare the proposed method with GP-based methods such the LSE algorithm and TRUVAR in terms of theoretical analysis. This difficulty arises because, first, the proposed method and these methods use different approaches to estimate H and L", and second, the criteria for evaluating the quality of the estimated sets differ. However, it is important to note that the proposed method has theoretical guarantees, and the confidence parameter B//² does not depend on the number of iterations t or the input space X, making it applicable whether X is finite or infinite. Additionally, since T[0,/9] /2r/2 x 1.25, the realized values of 8/ not conservative. To the best of our knowledge, existing method satisfies all of these properties. Morcover, confirm in Scction that the practical performance of the proposed method is equal to or better than existing methods.
Finally, we give a theorem on bish-probability bounds for Rg and r when using the proposed method. Since Theorem 4.1 and 4.2 provide bounds on the expected values of R₂ and rt, we can casily derive high-probability
bounds by using Markov's inequality, P[[ 2 a) I [| where X is random variable and is positive number. If Rg is used as X, then since R = R4: using Theorem 4.1 and Markov's inequality the incquality
P(R, 20) Cits holds. Therefore, for a given 8 (0, if we set a = 8-' VCiti, then RG 8- VCiyy holds with probability at least 1 - 8. Similarly, for re, if we set a 8- V-in/tt/ then Tr S 8-1 V-V/Crn/t holds with probability at least - 6. We summarize these results Theorem 4.3
Theorem 4.3. Let E (0, 1) and C₁ = log(11++4 moiss)) For each / 2 1, under the assumptions of Theorem
4.1 the following inequalities hold with probability at least 1 - 8:
R₁ 55 no 1
From Theorem 4.3 it is possible to derive high- probability bounds for R2 and Te, but the problem of the right-hand side not being tight remains. Specifically, the term 8-1 remains in the right-hand side. On the other hand, in many studies that deal with Vlog(5-1) appears in the bound, which is tighter than 8-1. Therefore, one of the issues for the future is to improve 8-1 in Theorem 4.3 Lo Vlog(O-1).
bounds such as Srinivas et al. (2010). the term
5 Numerical Experiments
We confirm the practical performance of the proposed mothod using synthetic functions and real-world data.
5.1 Synthetic Data Experiments when X' Finite
In this section, the input space X' was defined as a set of grid points that uniformly cut the region [I,u,] x [/2 u2] into 50 50. In all experiments, we used the following Gaussian kernel:
o exp exp (- (-1xx=x']]
|
x' 11
k(x,x')= of
L
As black-box functions, considered the following three synthetic functions:
Case 1 The black-box function f(x1, 22) is a sample path from GP(O, k), where k(.,)) is given by
k( x²) exp( exx(-l1ar a x11l//2).
8

---

Published in Transactions on Machine Learning Research (11/2024)
Table 1: Experimental parameters for each setting in Section 5.1
Black-box function
41
l2
U2
oj
L
noise
0
GP sample path
-5
5
-5
5
2
10
0.5
Sinusoidal function
0
0
2
cxp(2)
2 2exp(
3)
exp( 2)
1
Himmelblau's function
-5
-5
5
exp(8)
2
exp(4) 4)
0
Case 2 The black-box function f(11, x2) is the following sinusoidal function:
x2) = sin(10x1) + cos(4r2) - cos(3z1222)
Case 3 The black-box function f(x1, 22) is the following shifted negative Himmelblau function:
(2), = -af + 22 - 11)² - (x1 - 2 7)2 + 100.
Furthermore, we used the normal distribution with mean and variance noise for the observation noise,
The threshold and the parameters used for each setting are summarized in Table The settings for the
sinusoidal and Himmelblau functions are the same those used in Zanette et al. 2019 The performance was evaluated using the loss and Fscore,, where Fscore, is the F-score calculated by
He n H [He]
Rec; = H, H
x Pre, X Rec;
Pre.
Fscore; = Pre: + Rec,
H*1
Then, we compared the following six AFs:
(Random) Select æt by using random sampling.
(US) Perform uncertainty sampling, that is, a. arg = of (z)..
(Straddle) Perform the straddle heuristic proposed by Bryan et al.
2005 that is, 2; = arg max E STR(-1(x)
(LSE) Perform the LSE algorithm using the LSE AF 0--1 (LSB) (a:).
(LSE)
(x) proposed by Gotovos al. (001)) that is,
æt arg wxx at-1
(MILE) Perform the MILE algorithm proposed by Zanette et al. (019)) that is, x, = arg max EE dg (MILE) (x: is the same as the robust MILE, another AF proposed by Zanctte et al. 2001 with the tuning parameters and y set to and -00, respectively.
(MILE) x
where, a;11
(Proposed) Select ar by using equation 3 that is, arg max (zz).
In all experiments, the classification rules were the same for six methods, and only the AF was changed. We used g1/2 3 as the confidence parameter required for MILE and Straddle, and g//2 /2 lolgg22000 x 7²(2/(6) x 0.05)) for LSE. Under this setup, one initial point was taken at random and the algorithm was run until the number of iterations reached 300. This simulation was repeated 100 times, and the average rt and Fscore, at cach itcration were calculated, where in Case 1, f was generated for each simulation from GP(O,k).
As shown in Fig. 3 the proposed method consistently performs well as or better than the comparison methods in all three cases, in terms of both the loss rt and the Fscore,
5.2 Synthetic Data Experiments when X' Infinite
In this section, we used the region [-5,5] 5)5 C R as X' and the same kernel as in Section 5.1 As black-box functions, used the following three synthetic functions:

---

Published in Transactions on Machine Learning Research (11/2024)
GP sample path
Sinusoidal
Himmelblau
Bandom
Random
Rancom
US
85
US
Straddie
Stradde
Stradd
0.15
MILE
LSE
MILE
LSE
HILE
Proposed
0.30
Proposed
8
Proposed
LonE
0.30
Love
Losk
0.05
19
0.00
0.00
100
150
200
250
300
50
100
150
200
300
50
100
200
250
Iteration
Iteration
Iteration
GP sample path
Sinusoidal
Himmelblau
1.
10
0.8
0.8
08
0.6
0.6
0.8
F-acom
P-acome
0.4
0.4
Random
Random
US
Stradde LSE
Stradde
Stradde
LSE
LSE
MILE
HILE
MILE
Proposed
0.
Proposed
Proposed
100
150
200
250
300
50
100
150
200
300
50
100
200
250
300
Ieeaaton
Iteration
Iteration
Figure 3: Averages for the loss r, and Fscore, for each AF over 100 simulations across different settings when the input space finite. The top row shows Tt, and the bottom row shows Fscore, Error bars represent six times the standard error.
Case 1 The black-box function f( va, 25) is the following shifted negalive sphere function:
f2, 22, Fz, T3, 25) = 41.65518
x
Case 2 The black-box box function f(11, 22, 33, vz, Is) is the following shifted negative Rosenbrock function:
[2 f211,22 02, T4, xs) = 53458.91
[100(1241 =x3)² + (1 xa)
Case 3 The black-box function f( T2, 24, 25) ) is the following shifted negative Styblinski-Tann function:
f01,, 23, 200.8875 Ed= (xd 16x² + 5xa)
2
Additionally, we used the normal distribution with mean and variance o for the observation noise. The threshold and parameters used for each setting are sunmarized in Table The performance was evaluated using and Fscore, For each simulation, 100,000 points were randomly selected from [-5, 5]5, which were used the imput point set X to calculate and Fscore, The values of and Fscore, in X were calculated as approximations of the true values. As AFs, we compared five methods used in Section 5.1 except for MIL.E, which does not handle continuous settings. We used g./² = 3 the confidence parameter required
10

---

Published in Transactions on Machine Learning Research (11/2024)
Table 2: Experimental parameters for each setting in Section 5.2
Black-box function
oj
L
noise
0
Sphere
900
40
10-6
9.6
Rosenbrock
30000
40
10-6
14800
Styblinski- Tang
75
40
10 10-6
12.3
for Straddle, and 8/ v log x /6 x 0.05)) for LSE. Here, the original LSE algorithm uses the interscction of (2) and lcb,-1 (2) in the previous iterations given below to calculate the AF: ucb;-1(x)
min ucb,-1 (x)) lcb;-1 max 1c.) isigt
isige
Conversely, we did not perform this operation in the infinite set setting, and calculated the AF instead using ucb;-1(z) = uc) and lcb;-1(x) (2). Under this setup, one initial point was chosen at random and the algorithm and Fscore, each iteration were caleulated.
for 500 iterations. This simulation was repeated 100 times and the average rt.
From Fig it can be confirmed that the proposed method has performance equal to or better than the com- parison methods in terms of both r2 and Fscore, in the sphere function setting. In the case of the Rosenbrock function sctting, the proposed method cxhibited performance equivalent to or better than the comparison method in lerms rz- Moreover, in terms of Escore,, the Random method showed the best performance up 250 iterations, but the proposed method matched or outperformed the comparison methods by the end of the iterations. In the Styblinski- Tang function sctting, Random performed bost in terms of ra and Fscore; up to around 300 iterations, but the proposed method equaled or surpassed the comparison methods by the final iterations.
5.3 Real-world Data Experiments
In this section, we conducted experiments using the carrier lifetime value, measure of the quality per- formance of silicon ingots used in solar cells (Kutsukake et al. 2015). The data we used include the two-dimensional coordinates x = x2) E I² of the sample surface and the carrier lifetime values ((x) [0.091587, 7.4613) at each coordinate, where 21 E +2a+61 6 S a 89), x2 E (2a + 6 S a S 74) and | 89 74 6586. In quality evaluation, identifying defective regions, known red zones areas where the value of f(x) falls below certain threshold is crucial. In this experiment, the threshold to 3, and we focused
set
identifying regions where f(x) is 3 or less. We considered f(x) -f(x) + the black-box function and performed experiments with 0 = 0. Additionally, the experiment was conducted assumiin there was no noise in the observations. Moreover, to stabilize the posterior distribution calculation, mnise: = 10 was used in the calculation. We used the following Matérn 3/2 kernel:
x k( x²) 4 (1 /3 -3
v33 x - 1|2
exp
25
25
The performance was evaluated using the loss r, and Fscore, As AFs, we compared six methods used in Section 5.1 We used 8//²2 as the confidence parameter required for MILE and Straddle, and 3! /2 /2log(658)) 6586 x 7²t2/(6 0.05)) for L.F.. Under this setup, one initial point was chosen at random and the algorithm was run for 200 iterations. Because the observation noise was conducted under the setting that point that had been observed once would not be observed thereafter. This simulation was repeated 100 times and the average тi and Fscore, at each iteration were calculated.
O, the experiment was
As shown in Fig. 5) the proposed method demonstrates performance that is equal to or better than the comparison methods in terms of both loss rÜ and Fscore,-
6 Conclusion
In this study, we proposed a novel method called the randomized straddle algorithm, an extension of the straddle algorithm for LSE problems in black-box functions. The proposed method replaces the value of
11

---

Published in Transactions on Machine Learning Research (11/2024)
Sphere
Rosenbrock
Styblinskk-
8300
Random
Random
Rancom
US
85
25
Straddie
Stradde
Stradde
LSE
6000
LSE
R
LSE
Proposed
Proposed
Proposed
20
15
Love
4000
Low
1.0
2000
0.5
100
200
300
500
100
200
300
400
500
100
200
300
400
500
Iteration
Iteration
Iteration
Sphere
Rosenbrock
Styblinski-Tann
1.
1.0
0.8
0.
0.6
F-acom
0.6
P-acome
0.6
044
0.4
0.4
Random
02
Random
Rancom
US
US
Straddie
Straddi
Strade
LSE
LSE
LSE
Proposed
0.
Proposed
Proposed
160
200
300
500
100
200
300
400
500
100
200
300
400
500
Iteration
Iteration
lteration
Figure 4: Averages the loss re and Fscore, for each AF over 100 simulations for each sctting when the input space is infinite. The lop row shows Tt, the bottom row shows Fscore,, and each error bar length represents the six times the standard error.
Defective area identification
Defective area identification
Random
US
0.8
MILE
Proposed
0.6
F-ocore
Loss
0.4
Random
0-
US
Stradde
0.0
Proposed
100
200
50
150
200
Iteration
Iteratio
Figure 5: Averages of the loss r. and Fscore; for each AF over 100 simulations using the carrier lifetime data. The left figure shows rt, while the right figure shows Fscore,, with error bars representing six times the standard error.
8 the straddle algorithm with random sample from the chi-squared distribution with two degrees of freedom, performing LSE based on the GP posterior mean. As mensioned in Section g by considering an appropriate AF for appropriate loss function and solving the difficult problem of appropriately designing
12

---

Published in Transactions on Machine Learning Research (11/2024)
the distribution of the confidence parameters, we proved non-trivial theoretical results that the expected value of the loss in the estimated sets and that of the sum of losses are (/v)//) and O(yin)) respectively.
Compared to existing methods, the proposed approach offers three key advantages. First, most theoretical analyses of existing methods involve confidence parameters that depend on the number of candidate points and iterations, whereas such terms are not present in the proposed method. Second, existing methods either do not apply to continuous search spaces or require discretization, with parameters for discretization often being unknown. In contrast, the proposed method is applicable to continuous search spaces without requiring algorithmic adjustments, providing the same theoretical guarantees as for finite search spaces, Third, while confidence parameters in existing methods tend to be overly conservative, the expected value of the confidence parameter in the proposed method is v2x/2 R 1.25, which is not excessively conservative. Furthermore, numerical experiments demonstrated that the performance of the proposed method is equal to or better than that of existing methods. This indicates that the proposed method performs comparably heuristic methods while offering the added benefit of thcoretical guarantoes.
On the other hand, the proposed method has three drawbacks and limitations. First, since the proposed method does not make any significant changes other than adding randomization to the existing straddle, the practical performance is not dramatically improved compared to the case of using fixed B.. For example, if the next point is selected as the point at which E|r(H,, L,)] is the largest, practical performance can be expected to improve, but theoretical analysis in this case is not easy. Second, as mentioned in Section g the high-probabiility bounds derived by Theorem 4.3 are not tight. Fimally, it is not easy to extend to other settings. As mentioned in Section 4 the theoretical analysis of the proposed method was achieved by appropriately selecting the loss, AF, and distribution of the confidence parameter. Therefore, simply replacing the parameters used in some AF with a chi-square distribution cannot directly apply the method to, for example, cases where the F-score is used as an evaluation index or to other problem settings. However, the insight gained from derivation of the theoretical results in this paper is that even if the problem setting is different and the evaluation index considered changes, if an AF is designed that can bound the evaluation index with high probability, it can be expected to be extended to other problem settings. In particular, both the results of Takeno al. (2023) and the results of this paper use the property that some loss function can be bounded from above by 5. 1/2 o with high probability. Therefore, it can be said that the key point of the theoretical analysis is to consider a combination of AF and loss that satisfies this property.
Future work includes resolving the above-mentioned drawbacks and limitations. In addition, since BO and LSE for black-box functions become difficult to handle when the input variables are high-dimensional, extending the proposed method to high-dimensional settings is also one of future work.
Acknowledgments
This work was partially supported by JSPS KAKENHI [PP20000...PPPKK11444PPP:1111111 JST ACT-X (JPMJAX23CD), JST CREST (JPMJCR21D3, JPMJCR22N2), JST Moonshot R&D (JPMJMS2083-05), JST ATP Acceleration Research (JPMJCR21U2), NEDO (JPNP18002, JPNP20006) and RIKEN Center for Advanced Intelligence Project.
References
Julian Berk, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Randomised gaussian process upper confi- dence bound for bayesian optimisation. In Proceedings of the Twenly- Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 2284 2290, 2021.
Ilija Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher. Truncated variance reduction: A unified approach to bayosian optimization and level-set estimation. Advances in neural information processing systems, 29, 2016.
Brent Bryan and Jeff Schneider. Actively learning level-sets of composite functions. In Proceedings of the 25th international conference on Machine learning, pp. 80 80-87, 2008
13

---

Published in Transactions on Machine Learning Research (11/2024)
Brent Bryan, Robert C Nichol, Christopher R Genovese, Jeff Schneider, Christopher J Miller, and Larry Wasserman. Active learning for identifying function threshold boundaries. Advonces in neural information processing systems, 18, 2005.
Emile Contal, David Bulfoni, Alexandre Robiequet, and Nicolas Vayatis. Parallel gaussian process opti- mization with upper confidence bound and pure exploration. In Joint European Conference on Machine Springer, 2013.
Learning and Knowledge Discovery in Databases, pp.
Alkis Gotovos, Nathalic Casati, Gregory Hitz, and Andreas Krause. Active learning for level set estimation. In Proceedings of the Twenly- Third international joint conference on Artificial Intelligence, pp. 1344 1350, 2013.
Shota Hozumi, Kentaro Kutsukake, Kota Matsui, Syunya Kusakawa, Toru Ujihara, and Ichiro Takeuchi. Adaptive defective area identification in material surface using active transfer learning-basii level set estimation. arXiv preprint ar 2xx::2344001444 2023.
Yu Inatsu, Masayuki Karasuyama, Keiccii Inoue, and Ichiro Takeuchi. Active Learning for Level Set Es- timation Under Input Uncertainty and Its Extensions. Neural Computation, 32(12):2488) 2531, 12 2020, ISSN 0899-7667. doi: 10.1162/ncci a 01332. URL https: http//i...grggg/ 10. www.//eccccccoce a 01332
Yu Inatsu, Shogo Iwazaki, and Lchiro Takeuchi. Active learning for distributionally robust level-set estima- tion. In International Conference on Machine Learning, pp. 4574-4584. PMLR, 2021.
Yu Inatsu, Shion Takeno, Hiroyuki Hanada, Kazuki Iwata, and Lchiro Takeuchi. Bounding box- based multi- objective Bayesian optimization of risk measures under input uncortainty. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4564-4572. PMLR, 02-04 May 2024. URL httph: htttpp://prooceeingg.. mlr. wwtpss//w/////eeppp http:////inatt22aa.aa2 html html
Shogo Twazaki, Yu Inatsu, and Ichiro Takeuchi. Bayesian experimental design for finding reliable level set under input uncertainty. IEEE Access, 8:203982 203993, 2020.
Kirthevasan Kandasamy, Jeff Schneider, and Barnabás Póezos. High dimensional bayesian optimisation and bandits via additive modcls. In International conference on machine learning, pp. 295-304. PMLR, 2015.
Kirthevasan
Kandasany, Gautam Dasarathy, Junier B Oliva, Jeff Schneider, and Barnabás Póczos. Gaussian process bandit optimisation with multi-fidelity evaluations. Advances in neural information processing systems, 29, 2016.
Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás Póczos. Multi-fidelity bayesian optimisation with continuous approxinations. In International conference on machine learning, pp. 1799 1808. PMLR, 2017.
Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust bayesian optimization. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third Interna- tional Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learn- ing Research, pp. 2174-2184. PMLR, 26-26 28 Aug 2020. URL https::/ mlr. press/v108/ kirschner20a.htmll
Shunya Kusakawa, Shion Takeno, Yu Inatsu, Kentaro Kutsukake, Shogo Iwazaki, Takashi Nakano, Toru Ujihara, Masayuki Karasuyama, and Ichiro Takeuchi. Bayesian optimization for cascade-type multistage processes. Neural Computation, 34(12):2408 24311, 2022.
Kentaro Kutsukake, Momoko Deura, Yutaka Ohno, and Ichiro Yonenaga. Characterization silicon in-
gots: Mono-like versus high-performance multierystalline. Japanese Journal of Applied Physics, 54(8S1): 08KD10, 2015.
Benjamin Letham, Phillip Guan, Chasc Tymms, Eytan Bakshy, and Michael Shvartsman. Look-ahead acquisition functions for bernoulli level set estimation. In International Conference on Artificial Intelligence and Statistics, pp. 8493 8513. PMLR, 2022.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Blake Mason, Lalit Jain, Subhojyoti Mukherjee, Romain Camilleri, Kevin Jamieson, and Robert Nowak. Nearly optimal algorithus for level set estimation. In Gustau Camps- Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 Proceedings of Machine Learning Research, pp. 7625-7658. PMLR, 28-30 Mar 2022. URL
httpps//prroceedings. wttpeeceeeiinnsml....e.ee.. Saai..prrees//15mmmsorttt
html
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussion Processes for Machine Learning (Aduplive Computation and Machine Learning). The MIT Press, 2005. ISBN 026218253X.
Paul Rolland, Jonathan Scarlett, Miija Bogunovic, and Volkan Cevher. High-dimensional bayesian optimiza- tion via additive models with overlapping groups. In International conference artificial intelligence and statistics, pp. 298 307. PMLR, 2018.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148 175, 2015.
Shubhanshu Shekhar and Tara Javidi. Multiscale gaussian process level set estimation. In The 22nd Inter- national Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2019.
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, pp. 1015 1022, 2010.
Shion Takeno, Yu Inatsu, and Masayuki Karasuyama. Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 23-29 Jul 2023. URL htttps://proceedinn: mlr ppess/v202/ 2ttps////oo//aaae2222222 taweno2kaen.a....a html
PMLR,
Sattar Vakili, Danyal Ahmed, Alberto Bernacchia, and Ciara Pike-Burke. Delayed feedback in kernel bandits. In International Conference on Machine Learning, pp. 34779-34792. PMLR, 2023.
Andrea Zanette, Junzi Zhang, and Mykel J Kochendorfer. Robust super-level set estimation using gaussian processes. In Machine Learning and Knowledge Discovery in Databases: European. Conference, ECML PKDD 2018, Dublin, Ireland, September 10 14, 2018, Proceedings, Part 11 18, pp. 276 291. Springer, 2019.
Marcela Zuluaga, Andreas Kranse, al. e-pal: An active learning approach to the multi-objoctive optimiza- tion problem. Journal of Machine Learning Research, 17(104):1 32, 2016.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm 2 Randomized Straddle Algorithms for Max-value Loss in the Finite Setting Input: GP prior GP(O, k), threshold 0 E R
for t= 1.2..... do
Compute ( and (x) for each &' by equation 1
Estimate He and Lt by equation 2
Generate & from the chi-squared distribution with two degrees of freedom
Compute 3. = & + 2 log([>X)), ucb;-1 (2), l and ūt-1 (a:) Select the next evaluation point a; by æ = arg max (x)1 Observe 1/t f(x))= + Er at the point æt
Update GP by adding the observed data end for
Output: Return Htp and Li as the estimated sets, where 7 is given by equation 6
A Extension to Max-value Loss
In this section, consider the following max-value loss defined based the maximum value of (x)):
r( r(H, L.)
max (xx)) f øEX
When is finite, we need to modify the definition the AF and the estimated sets returned at the end of the algorithm. Conversely, if X' an infinite set, the definitions of H, and 1a should be modified in addition the above. Therefore, we discuss the finite and infinite cases separately.
A.1 Proposed Method for Max-value Loss when X' is Finite
When is finite, we propose the following AF with a modified distribution that 3r follows.
Definition A.1 [Randomized Straddle for Max-value Loss). For each & 2 1, let & be a random sample from the chi-squared distribution with two degrees of freedom, where f.....,Ee. E1..,, are mutually independent. Define Bg = &t + log([>X)). Then, the randomized straddle AF for the max-value loss, (x)) is defined as:
0ي- 1 (2)) max
(ucb. (ni 0.0 l
By using (x),, the next point to be evaluated is selected by arg max=ex* (x)) Additionally, change estimation sets returned at the end of iterations T in the algorithm to the following instead of Hy and Ly: Definition A.2. For each f, define
= arg min E,[F,],
(6)
13i
where [x[-] represents the conditional expectation given Di-1. Then, at the end of iterations T, we define Hy andLş to be the estimated sets.
Finally, give the pseudocode of the proposed algorithm in Algorithm 2
A.1.1 Theoretical Analysis for Max-value Loss when A' is Finite
For the max-value loss, the following theorem holds under Algorithm 2
Theorem A.1. Let f be a sample path from gP(O,,) k), where k(.,)) is a positive-defintee kernel satisfying k(n, < for any X. For each & 1, let & be random sample from the chi-squared distribution with two degrees of freedom, where (.....,, Then, the following holds for Rs >i=1 Pr:
are mutually independent. Define B, = & 2 log()
E[R.] S / Vihn
16

---

Published in Transactions on Machine Learning Research (11/2024)
where Ō (4 (l))(())))) Iog)/ + o and 3.-
and the expectation is taken with all randomness including f. From Theorem A.1 the following theorem holds.
Theorem A.2. Under the assumptions of Theorem the following incquality holds:
Cim t
Fraa
S
where i and Õ₁ are given in equation 6 and Theorem
A.1 respectively.
Comparing Theorems 4.1 and A.1 when considering the max-value loss, 5 should be 2log([X() larger than in the case of rt, and the constant that appears in the upper bound of the expected value of the cumulative loss has the relationship Õ (1 (1+ log(IX())C Note that while the upper bound for Tr does not depend X, it depends the logarithm of the mumber of elements in X for the max-value loss. Also, when comparing Theorem 4.2 and A.2 it is not necessary to consider & in Tt, whereas it is necessary to consider in the max-value loss. For the max-value loss, it is difficult to analytically derive I., [f.]. and hence, it is also difficult to precisely calculate f. Nevertheless, because the posterior distribution of f given D.-1 is again a GP, generate M sample paths from the GP posterior distribution and calculate the realization +(()) of f; from each sample path f6), and calculate the estimate i of i as
M
i= arg min isist
Σ
M
j=1
A.2 Proposed Method for Max-value Loss when X' is Infinite
In this section, assume that the imput space X' Rdd is compact set and satisfies X [0,r] where 0. Furthermore, we assume the following additional assumption for Assumption A.1. Let f differentiable with probability Assuming positive constants a, exist, such that
Of
L S aexp (-(t) j E [d].
sup x
0x,
where zy is the j-th element of and [d] {1..... d}.
Next, we provide LSE method based on the discretization the input space.
A.2.1 Level Set Estimation for Max-value Loss when X' is Infinite
For each 2 1, let X, be a finite subset of X. Also, for any x E X, let [x]e be the element of X that has the shortest L1 distance from a Then, we define He and L, as
H. {o E X (-=)) 0}, L, {o E X [+- < 0}.
(7)
A.2.2 Acquisition Function for Max-value Loss when X' Infinite
We define randomized raddle AF based on X4:
Definition A.3. For each t 2 1, let & a random sample from the chi-squared distribution with two degrees of freedom, where f...... E f are mutually independent. Define B, 2 [lg((( + & Then, the randomized straddle AF for the max-value loss when X' is infinite, ă (xx),,,, is defined as:
o (x) = max / ( (ucb;- - 0, (
The next point to be evaluated is selected by s arg = (2=) Finally, we give the pseudocode of the proposed algorithm in Algorithm 3
IIf there multiple 2 with the shortest L1 distance, determine the that is unique. For example, first choose the option with the smallest first component. If unique determination possible, then select the option with the smallest second component. This process is repeated up the d-th component, achieve unique determination.
17

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm 3 Randomized Straddle Algorithms for Max-value Loss in the Infinite Setting
Input: GP prior GP(O, k), threshold 0 E R, discretized sets Rp
for t= I. do
Compute ( and (x)) for each & by equation
Estimate He and Le by equation 7
Generate & from the chi-squared distribution with two degrees of freedom
Compule 3. = & + 2 log( ucb;-1(#), Icb:-1 (2x) and ( Select the next evaluation point 2; by æ = arg max (x) Observe 1/t f(x))= + Er at the point æt
Update GP by adding the observed data end for
Output: Return Htp and Lip as the estimated sets, where f = arg min SiST Er[;
A.2.3 Theoretical Analysis for Max-value Loss when X' is Infinite
Under Algorithm the following theorem holds.
Theorem A.3. Let c [0, [0, be a compact set with r > 0. Assume that a sample path from GP(O, k): where k) positive-definite kernel satisfying k(x, a) s for any æ E X. Also assume that Assumption A.1 holds. Moreover, for each 1, let T₁ [bdrl2 (1 /log(ad) + v=/2)], and let X be finite subset of X satisfying [&]] 7t! and
dr [a]ell1
|
E.
TO
Suppose that & is random sample from the chi-squared distribution with two degrees of freedom, where fI....,5,, E1,,,, f are mutually independent. Define Bt = 2dlog([bdrf((() (Vlo(a)))) + /T/2)]) + & Then, the following holds for RG = Ei= Ps:
E & T² + (2 st),
6
0 and 8, = 2dlog( (bbgg(((rrt(( (VTo(ad) + / and the expectation is taken with where Č 2/
randomness including f, e, and Br.
From Theorem
A.3 the following holds.
Theorem A.4. Under the assumptions of Theorem A.3 define
= arg min [r isis
Then, the following holds:
x²
(2+
B
+ V
6t
t
where ő and are given in Theorem
A.3
B Proofs
B.1 Proof of Theorem 41
Proof. Let E (0, 1). For any 1 2 1, D.-1 and X, from the proof of Lemma 5.1 Srinivas al. (010
the following holds with probability least 8:
lcb)-1,((2)) = (x)) 0///2 a- ( S f(x) < pr (xx) + 13/22 az (0-1(0) (x) = ucb)-1,s(#;,
(8)
18

---

Published in Transactions on Machine Learning Research (11/2024)
where 35 log(1/6). Here, consider the case where E Hy. If x H", have 4(xx) 0. In contrast, if a E I", noting that (c))-1,((z)) I (x) by equation g we get
4xx) 0 f(x) S 0 lcbt-1,6
Moreover, the inequality (x) 2 0 holds because E H4. Hence, from the definition of lcbe- and ucb)-1,((2), we obtain
1cb)-1,8(2z) S ucb, u.bb-1,5(2)) 0.
Therefore, we get
(xx)) 5 (() = 1, (z)) 0,0 -o,--lcb,,,10 lcb)
S max (oxx(mmi(uububu.m (,cb,_ 0, 1,b;-1,5(2)) 03 01-15(2)).
Similarly, we consider the case where L. x L", we obtain 4(xx) Thus, because 0(-1,( 2 0, get 4xxx)) & a Moreover, if x E H*, noting that f(x) s ucb4-1,8 (x=) by equation obtain
(xx)) f(x)) 0 ucb;-1,5(ar) 0.
Here, the inequality (x) < 0 holds because x L. Therefore, from the definition of (,b(-1,5(x;) and ucb)-1,5(z), obtain
ucb,-1,5(0) 0 < 0 - (16bb-1,5((2))
Thus, the following inequality holds:
(xx) S ucb; - min(ucbe-1..((2) - 0, lcb; S 1,-)))
Therefore, for all cases, the inequality (xxx) S a=-1,,( holds. This indicates that the following inequality holds with probability at least
6:
4(xx) S (1-1,5(x))) S max a 11-1.8
(9)
#E
Next, we consider the conditional distribution of le(x) given Dz-1. Note that this distribution does not depend on Bs. Let F--1(-) be a distribution function of lx(x) given D.-1- Then, from equation g we have
Fi-1 max 1,-) @Ex
2 1 - 6.
Hence, by considering the generalized inverse function of Fi-1(.) for both sides, the following inequality holds:
FL - 8) S max (.))
2e
Here, if 5 follows the uniform distribution on the interval (0, 1), then 1 1 follows the same distribution. In this case, the distribution of (1 8) is equal to the distribution of te(x) given D,-1. This implies that
[x)]] < E, max a (1-1,6(x))
#ext
where Es[-] means the expectation with respect to 6. Furthermore, because 2 llg((/8) and B follow the chi-squared distribution with two degrees freedom, the following holds:
[x)]())]] & Eg, [at)1(x:)]-
Thus, if X is finite, from the definition of ra we obtain
B.(re] = E,
Σ l(x)))
Σ
[,(+(())]
Σ
Eg, (a:)1 = Es, [x:-1
X
X
xE
#EN
19

---

Published in Transactions on Machine Learning Research (11/2024)
Similarly, if X' is infinite, from the definition of and non-negativity of 11(x), using Fubini's theorem we get
1 Ed/rd E, Vol(x) J ((z))dz) Vol(x) / (x](())) V Vol(x) L Es, [at-1 dx Eg, [at-1 (xx))
Therefore, the incquality Eg[ra] I Es, la=-1(x;)] holds for both cases. Morcover, from the definition of (x), the following inequality holds:
0-11(x,) S 3//11/00000 12-1
Hence, we get the following inequality:
E R4
E
< E
1/2
o (2;))
Li=l
1/2
1/27
Cauchy-Schwarz inequality
<
E
Σ
Bi
Σ
/i (2)1)
i=
i=1
Hölder's inequality
E
3
E
of (2:i)
B
V2t,
E
Σ
o
(2o.)
S 2t
E
Y
log(1 +
2 noise
where the last inequality is derived by the proof of Lemma 5.4 in Srinivas et al. 2010).
B.2 Proof of Theorem 4.2
We first give three lemmas to prove Theorem 4.2
Theorem
4.2 is proved by Lemma B. and B.3
Lemma B.l. Under the assumptions of Theorem 4.1 let
arg min Ee[ra].
13ist
Then, the following inequality holds:
Ci
E rrl <
t
Σi_
Be[ro]
Proof. From the definition of f, the incquality Ee(rg]
holds. Therefore, we obtain
E Σ ==
Err Err
[[R
E/rd]
By combining this and Theorem 4.1 we get the desired result.
Lemma B.2. For any 2 1, S and æ E X, the expectation [x]] can be calculated as follows:
E, [x)(])]] = {
(x) (o(-a) + t (((- if L ( (o(a) - a [1-+(a)) if H;
-;v() where (=)= and 2(2) and (2)) are the density and distribution function of the standard normal
distribution, respectively.
20

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. From the definition of (x)), if x E L,, 4(x) can be expressed (xx) -f( 2 8), where [[]] is the indicator function which takes if the condition holds, otherwise 0. Furthermore, the conditional
distribution of f(z) given D:-1 is the normal distribution with mean ( and variance (z) Thus, from the definition of E,H.], the following holds:
( ( 0)
1
(y p4 12))2
[.[4(x))
exp
200-
dy
2TO
(x)
1-1
14-1(2))
14-1 (2)) -0)
1
(- (y - pr ( (xx))² 20 (z)
12))
(2-1(
11-1(x0)
/ 1
exp
dy
1
O 02-1(x) (2 + aa)
exp
dz
V2T
2
= 0)-1(()) (3 a) ((2)dz = o 1 (1= + + - D(-a))}
= -z- (d) + {1 - +(-a)))
Similarly, if x E H;, (xx) can be expressed as l(xx)) = (0 f(x)))][(<>> < 0). Then, we obtain
(y - He- 12=))
[x]4
(0 y)
exp
207-1(2) (20)
dy
00
2 (x:)
o- (1x)
00 (1-14-11 (0)-110) (x))(xx)
14-
(x)
+
Me-
1 (20) -1
exp
(y 14- (x=))²
dy
02-1(x)
2 (x))
20 (x)
1
2²
(x) (z 12-a) a)
exp
(-1)dz
2m
2
100
(2 a) ((2)d: = .- (x) (1-((=)] -a(1 ((a)))
= = [o(a) {1 - +(a))).
Lemma B.3. Under the assumptions of Thcorem 4.1 the equality f = t holds.
Proof. Let x X. If x He, the inequality 1 (x) 2 0 holds. This implies that a 2 0. Hence, from
Lemma B.2 we obtain
Bx(b(x))] ())1( (a(a)= aa - +(aa)))
Thus, since 2 0, the following incquality holds:
(x) (0(a) - a (1 - {(a))) < -- (m) (0) + a ((-))}
Therefore, from the definition of (x)), we get
Ee[4(x)] = (z)
- a (( [E((
Similarly, if a E La, using the same argument have
+ [o- (0-a)(())) [,(((())))
Here, X is finite, from the definition of rs we obtain
Edrd = E,
14(2) = Σ Ee[((x))
1
< Σ [x[((x)] = Ex(rr]-
X
X
X
FEX
TEX
mEX
Similarly, if is infinite, by using the same argument and Fubini's theorem, we get E2 [rt] S [r.). Therefore, for all cases the inequality [r]] Er[r:] holds. This implies that f f=6 t.
From Lemma
B.1 and
B.3
get Theorem
4.2
21

---

Published in Transactions on Machine Learning Research (11/2024)
B.3 Proof of Theorem A.
Proof. Let d E (0, 1). For any 1 2 and D from the proof of Lemma 5.1 in Srinivas et al. 2010 with probability at least - 6, the following holds for any æ E R::
lcb = ()-1(x)) 03 S f()) S (c-1(x) + B3/2 0, = ucb(-1,6
where 88 = 2og (1/)). Here, by using the same argument as in the proof of Theorem 4.1 the incquality (ax) S (xr)) holds. Hence, the following holds with probability at least - 6:
Nt = max 4 (xx S max 01))) ØEA
(10)
øEA
Next, we consider the conditional distribution Ft given D2-1- Note that this distribution does not depend on 38. Let Ft-1(-) be a distribution function of Pz given De-1. Then, from equation 10] we obtain
Fi-1 max (,1)))))))2)) 2 5.
Therefore, by taking the generalized inverse function for both sides, we get
F1 8) S max (z)).
Here, follows the uniform distribution on the interval (0, 1), 1 5 follows the same distribution. Fur- thermore, since the distribution of F - 5) is equal to the conditional distribution of ñn given D,-1, we have
R F+
Es
max ā #EX
Moreover, noting that llo(((X100) and Br follow the same distribution, we obtain
[Frr S Es, (xx)).
Additionally, from ãz-1(z), the following inequality holds:
fx.1( S /3 o (xx.)
Therefore, since B|3²] = 2 + 2 log((>())), the following inequality holds:
E R| = E
7
<
8 o
(2x))
1=1
1/2
1/2
<
Σ i=1
B1
Σ
0
-
E
8
E
of
(mxt
S V1122 2 log (o1((121)))
R
Σ of (2:))
2
S <t2 + log 210g(1221))
E
log(1 + o -2
nensse
22

---

Published in Transactions on Machine Learning Research (11/2024)
B.4 Proof of Theorem A.2
Proof. Theorem A.2 proved by using the same argument in the proof of Lemma B.1
B.5 Proof of Theorem A.3
Proof. Let a E X. If x E H n H. or a E L n Lt, the equality 4xx)) = 0 holds. Hence, the following inequality holds:
((x)) S (((=)))))))))))))))())) S ((())) + [f(x)) [(x))
We consider the case where æ E H' and a E L,, that is, 1((x) = f(x) 9. Here, since Le, the inequality
(t-1((=]))) < 0 holds. This implies that [æ=]e E L. If [at] E H" noting that (e(ar)))) = [(x))+) 0 we get
(<(x)= f(x) - = f(x) f((=):) + f((])) 0 - f(())) -0 - 1f(x) f((=))) = ((()))))(((()))))))))()))))))))) If(x)) f((=)+))
Similarly, if [z)| E L", noting that f((x))) and S [(([)))) we obtain
= f(x) - = f((=)))) - 0 f(x) - f((=))) - 0 + f(x=) - f((=))) s 4((=))) + [f(x)) - -((x=))
Next, consider the case where E L and E He, that is, (xx) = 0 f(x). Here, since æ E H,, the inequality p 2 Pholds. This implies that ax) E He. If [=le E L", noting that 4([x)))) = 0 f((x)), we have
(xx) 0 - f(x) 0 (((a).) + [(=])a) (a) z (((l))))) + 15(x) - [(x))))
Similarly, if [z)] E H*, noting that f([=)))) 2 0 and 0 S (<(z)))) get
4((2) = f(x) f([x).) f((=))) f(x) 0 f((=))) f(z) 4(<{))) + If(x) f((x)/))
Therefore, for all cases the following inequality holds:
(xx) < <((=)) If(x) f(()):)
Here, let Lmax supjetd sup
af An;
Then, the following holds:
f(x) - f(x)))] & Lunax - [=]ell2 I Lmax dr Te
Thus, noting that
4(x)) (6((z)))) + Lmax dr
TB.
we obtain
dr
max ((())))))))))))))))))) = Lmax dr wEx
+ max (x))) = Lmmx dr + Fr-
F, max le (xx) 5 Lmmx =EA
aEA.
In addition, from Lemma H.1 in Takeno et al. 2023 the following inequality holds:
Lmaax < log(ad) + 22)2).
Hence, we get
Lmax dr b( MVloggad)) + (F/2) Tt
b( (VVolaad v7/22) dr [bdrt? / log(( (dd) + /T//2]]
<
dr
Tt
v dr
bdrt? (Vlog + /x/2) t
23

---

Published in Transactions on Machine Learning Research (11/2024)
Therefore, the following incquality holds:
2 5
E [R = E
E
P
E
6
Here, iy is the maximum value of the loss (.))) restricted on X; and since X; is finite set, by replacing X with 2 in the proof of Theorem A.1 and performing the same proof, we obtain E, I Es [maxxexx, (
Furthermore, since the next point to be evaluated is selected from X, the following inequality holds:
E M <
Es max ā; (æ) S Es Sa 12=1 DEA:
=E
Therefore, we have
E
E
8
1/2
o (2:+)
1/2
1/27
S
Σ
3
Σ
0. (20))
E
3
E
(2:))
V /BB3)1
Σ of (xx))
V 1(2 + 2d (ollo((brrt() (Vlo((ad) + vx/2)1))
[[m]]]
O1tm st).
B.6 Proof of Theorem A.4
Proof. Theorem A.4 proved by using the same argument the proof of Lemma B.1
24


Reviews:
[{"review_id": "IMQZ0XpI8K", "reviewer": "Reviewer_ok7A", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\n1.\tThe presentation of the work is clear.\n\n2.\tThe proposed method is simple yet effective.\n\n3.\tThe proposed method provides strong theoretical guarantees regarding the expected loss for misclassification.\n\n**Weaknesses**:\n\n1.\tThe idea of replacing user-specified value of $\\beta$ in UCB by a random sample from a distribution is not new [1,2]. For readers familiar with references [1] and [2], it seems that they can grasp the main conclusions of this article based on the abstract alone. Then, what’s the main challenge when extending this idea to level set estimation? Additionally, are there any new insights when extending this idea to level set estimation? It seems such idea can also be easily extended for other scenarios like multifidelity BO, multiobjective BO, high-dimensional BO, and robust BO.\n\n2.\tDetermining the value of $\\beta$ through random sampling is helpful for analyzing the average-case regret. In experimental studies, the author repeated each experiment 100 times. However, in real-world scenarios, users typically have only one opportunity to run the algorithm. Then, are there any regret analysis results on the high probability bound?\n\n3.\tThroughout the paper, the analysis on the drawback and limitations of determining the value of $\\beta$ through random sampling is deficient.\n\n[1] Berk, Julian, Sunil Gupta, Santu Rana, and Svetha Venkatesh. \"Randomised Gaussian process upper confidence bound for Bayesian optimisation.\" In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 2284-2290. 2021.\n\n[2] Takeno, Shion, Yu Inatsu, and Masayuki Karasuyama. \"Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds.\" In International Conference on Machine Learning, pp. 33490-33515. PMLR, 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the Randomized Straddle Algorithm for Level Set Estimation (LSE) in black-box functions. The proposed method offers theoretical guarantees and eliminates the need for any user-specified parameters to be adjusted. The effectiveness of this approach is validated through extensive numerical experiments conducted on both synthetic and real-world data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tA chi-squared distribution with 2 degrees of freedom (k = 2) is an exponential distribution with a mean value of 2.  To maintain consistency with previous works, I suggest that the author use the description of the exponential distribution in the manuscript.\n\n2.\tAlthough [2] is more solid than [1], I still recommend that the authors also cite [1], even if it serves as a stepping stone. \n\n3.\tThe authors should list the drawback and improvements of the proposed algorithms more in detail.\n\n4.\tPage 5, ‘In contrast, the random sample proposed in this study does not require the addition of such a constant’ Is the random sampling approach in this paper significantly different from the random sampling used in reference [2]? Can the techniques presented here be applied to the problems studied in [2]? In other words, is the random sampling method proposed in this paper a general technique that can be adapted for other applications?\n\n[1] Berk, Julian, Sunil Gupta, Santu Rana, and Svetha Venkatesh. \"Randomised Gaussian process upper confidence bound for Bayesian optimisation.\" In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 2284-2290. 2021.\n\n[2] Takeno, Shion, Yu Inatsu, and Masayuki Karasuyama. \"Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds.\" In International Conference on Machine Learning, pp. 33490-33515. PMLR, 2023.", "broader_impact_concerns": "No statement-requiring ethical implication from my point of view.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5M2VNSj9Mp", "reviewer": "Reviewer_2yzN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n- Introduction of the problem and related work are extremely well written and particularly well fitted for a journal submission like TMLR where clarity and concise references are a must.\n\n- The technical side of the paper, that finally leads to Eq. (3) is understandable and clear. Also the theoretical results in Section 4 are clear and easy to follow for the reader. In general, I find that both the LSE problem is well explained and is clear what the contributions are. \n\n- Even if experimental results are somehow synthetic in most of its parts, the is performance clearly equal-or-better than the rest of SOTA methods. I also appreciate the effort of the authors for making a comparison with 4 or 5 methods that are indeed similar to the one proposed.\n\n### Weaknesses:\n\n- Even if the LSE problem is not exactly BO, I am a bit suprised that little connection are drawn in the manuscript after the related work. For example, the exploration-explotation side of the problem is kind of missed in the methodology. I am saying this, for instance, because it would nice to see what are the consequences in terms of computational cost when the parameter $\\beta$ is oddly set and the function of interest is super difficult to evaluate. \n\n- Even if we are treating here an LSE problem, where we are concerned with having function values over or below a certain threshold, I am missing a bit of some visually clear experiments where the effect of a well-fitted confidence parameter shines. Figures are fine, but some other types of results would have helped me to understand better the differences between SOTA methods and this one.\n\n- The role of the loss in pp. 6 and Theorems is clear, but somehow secondary to me. LSE is concerned about a similar BO problem where we want to estimate function values over or below a threshold, fine, but then what does this loss function for us in the problem setting and what type of behavior should we expect? To select subsets of X that target areas with low/higher function values around the threshold, ok, but it is not well explained or at least integrated in the story telling of the paper...\n\n- I assume we are treating here with regression/real-valued problems in terms of f(x), right? No comments are made on this side.\n\n- Experiments are fine, but it would be nicer to test the method in less synthetic problems and perhaps more real-world datasets. Introducing an analysis on the effect of the dimensionality $d$ of X would also help to see if the method also outperforms when large-dimensionality plays a role.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper makes advances in level set estimation (LSE), a variant of Bayesian optimization where the main problem is to identify the set of input points where a function takes a value above or below a given threshold $\\theta$. Several works have studied and introduced new models/versions around LSE, particularly since GP-UCB (Srinivas, 2010), but one challenge remains: the selection of the confidence parameter $\\beta_t^{1/2}$. This parameter basically adjusts the trade-off between exploitation-exploration, making the process more expensive if it is oddly tuned. To solve this problem, the paper introduces a new acquisition function (AF) method where the confidence parameter is sampled independently of the number of iteration, what used to increase it in the past. The main result is that now, having the confidence parameter model by a chi-squared distribution allows a theoretical result around the loss values (with two inequalities in Theorems 4.1 and 4.2), avoids an increasing parameter with the number of iterations and provides equal-or-better performance results than the other 4 or 5 previous SOTA methods", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The manuscript is in general in a good direction. I would love to see some improvements in terms of the weaknesses that I previously mentioned. In general, there is room in the manuscript for further improvement, particularly in the second half -- where theoretical analysis and experiments could even shine a bit more.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OagW5qrjPZ", "reviewer": "Reviewer_PU6D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My research expertise resides mainly in Gaussian Process regression, not familiar with Level Set Estimation. The following comments are based on this manuscript and brief reading of the related works LSE (Gotovos 2013) and GP-UCB (Srinivas et al. 2010) model.\n\nStrengths:\n\n1. The paper is well written.\n\n2. Experimental results looks good, justifies the effectiveness of the model.\n\nWeakness:\n\n1. The overall contribution is limited, because 1) the proposed algorithm is an extension of the LSE (Gotovos 2013) model, with \\beta_t drawn from a chi-squared distribution (Theorem 1) instead of a fixed value given the size of the finite data space (Theorem 1, Gotovos 2013) and 2) the proof of Theorem 1 on the infinite set \\mathcal{X} case (Theorem A.3, Appendix A.2) looks very similar to Theorem 2, Srinivas et al. 2010, which also tackles the infinite set \\mathcal{X} case. Thus the claim that this algorithm \"can be applied even when \\mathcal{X} is an infinite set\" may not be a significant contribution.\n\n2. Some statement are unclear. In definition of the maximum information gain \\gamma_t (Page 6), the maximization is with respect to what? A subset of \\mathcal{X} with t elements? What if \\mathcal{X} is continuous as discussed in the Theorem 1?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focus on the Level Set Estimation problem, where:\n\nTheoretical Contributions:\n1. A randomized straddle algorithm is proposed, where the model parameter \\beta_t^{1/2} is drawn from a chi-squared distribution instead of fixed in previous algorithms (e.g. Gotovos 2013).\n2. It is proved that the expected misclassification rate of the proposed model converge to 0, with a convergence rate only related to noise \\sigma in the Gaussian Process model and maximum information gain.\n\nExperimental Contributions:\n1. Experimental results are provided with superior performance in most of the setups for synthesized dataset and real world dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would be happy if the authors can:\n\n1. Clarify the difference between Theorem A.3 (Appendix A.2) and Theorem 2, Srinivas et al 2010. and provide evidence that the novelty is significant compare with Srinivas et al 2010.\n\n2. Provide more discussion of the maximum information gain, especially in the infinite data space \\mathcal{X} case.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers find this work is clear and well written, the proposed method is effective, and the experimental results are good. They also appreciate the clear, easy-to-follow, and strong theoretical analysis provided in this work. After rebuttal, most of the concerns raised were properly addressed, and one reviewer voted to accept this paper while two reviewers leaned toward accepting. In the official recommendation, Reviewer 2yzN suggests that the high-dimensional side of the problem could be worthy to be explored in future follow-up work, which I also believe is a very good suggestion.

I read the paper in detail and totally agree with all reviewers that this work clearly meets the TMLR acceptance criteria (solid and well-supported claims, potential audience). Therefore, I am happy to accept this work as is.
Decision: Accept (poster)