Stopping Bayesian Optimization with Probabilistic Regret Bounds
Authors: James T. Wilson
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian optimization
Gaussian processes
Primary area: probabilistic_methods
TL;DR: Model-based stopping rules for Bayesian optimization with robust Monte Carlo estimators

Abstract: Bayesian optimization is a popular framework for efficiently tackling black-box search problems. As a rule, these algorithms operate by iteratively choosing what to evaluate next until some predefined budget has been exhausted. We investigate replacing this de facto stopping rule with criteria based on the probability that a point satisfies a given set of conditions. We focus on the prototypical example of an $(\epsilon, \delta)$-criterion: stop when a solution has been found whose value is within $\epsilon > 0$ of the optimum with probability at least $1 - \delta$ under the model. For Gaussian process priors, we show that Bayesian optimization satisfies this criterion under mild technical assumptions. Further, we give a practical algorithm for evaluating Monte Carlo stopping rules in a manner that is both sample efficient and robust to estimation error. These findings are accompanied by empirical results which demonstrate the strengths and weaknesses of the proposed approach.

Stopping Bayesian Optimization with Probabilistic Regret Bounds
James T. Wilson Morgan Stanley, New York, USA
j james wilssnetmorgannttnllly.... com
Abstract
Bayesian optimization a popular framework for efficiently tackling black-box search problems. As rule, these algorithms operate by iteratively choosing what to evaluate next until some predefined budget has been exhausted. We investigate replacing this de facto stopping rule with criteria based on the probability that point satisfies a given set of conditions. We focus on the prototypical example of an (e, --rriterio: stop when a solution has been found whose value is within >> of the optimum with probability at least 1 - under the model. For Gaussian process priors, show that Bayesian optimization satisfies this criterion under mild technical assumptions. Further, we give a practical algorithm for evaluating Monte Carlo stopping rules in manner that both sample efficient and robust to estimation error. These findings are accompanied by empirical results which demonstrate the strengths and weaknesses of the proposed approach.
Introduction
In the real world, we are often interested in finding high-quality solutions black-box problems. Many of these problems are not only expensive to solve but difficult to reason about without extensive discovering
background knowledge-such
chemicals [17], designing better experiments [48], or configuring machine learning algorithms [42].
A common approach is therefore to construct models for these problems and use them to predict real-world outcomes. recent years, Bayesian optimization (BO) has emerged as a leading approach for accomplishing these tasks. Precise definitions vary, but BO methods frequently characterized by their use of probabilistic models to guide the search for good solutions. The idea is for these models to provide distributions over the performance of competing alternatives, which can then be used to simulate the usefulness of evaluating different things. For a recent review, see Garnett [16].
Despite the success of these algorithms, an ongoing issue for practitioners has been the continued lack of interpretable stopping rules. The vast majority of BO runs proceed until a predetermined budget (e.g.. a number of evaluations amount of resources) is exhausted. We highlight two likely reasons for this trend and then give a brief prospective for model-based alternatives. The first reason is that stopping rules often revolve around quantities like optimums that difficult work with, even when defined under a model. The second is that even the best models sometimes go astray; and, if the model is bad, then model-based stopping is liable to stop much too soon far too late. To avoid potential disappointment, let us say upfront that this work addresses the former challenge and only provides mild commentary on the latter. We will revisit this topic in the closing sections.
At the same time, we argue there is much to gained by using models to help us decide whether given solution is "good-cnough" for its intended purpose [40]. One benefit of model-based stopping is its ability to adapt to the data. Sometimes, we will get lucky and stumble upon good solutions early Other times, our progress will be slow. If the model captures these events, then stopping can
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

be tailored to each run. Another benefit of model-based stopping is its ability to simplify the user experience by asking us to specify what we wish to find instead of how much we wish spend.
The basic idea we pursue is that, if we can simulate whether a solution is good-enough, then we can stop once we find one that probably is. We focus a prominent example of this framework, but stress that much of what follows holds for different choices of models and conditions. In particular, we investigate the setting where the user deems solution sufficient if its performance within e of the optimum with probability at least 1 - 8 under the model.
Our primary contributions to: i) combine recent work on scalable sampling techniques with algorithms for cost-efficient statistical testing; ii) show how the resulting estimators can be used as the basis for robust stopping rules; and, iii) introduce the first model-based stopping rule for BO with convergence and performance guarantees (up to model error).
The remaining text is organized as follows. Section 2 presents notation background material. Section 3 introduces the proposed stopping rule and evaluation strategy. Section 4 analyzes this algorithm's convergence and correctness. Finally, Section 5 investigates its empirical performance under idealized and realistic circumstances.
2 Background
We use boldface symbols to indicate vectors (lowercase) and matrices (uppercase). Given a sequence (a.), we denote an = [ai,..., an] Likewise, for function / X - R. we use the shorthand f(X,,) = [f(=))..... f(x,)]] By minor abuse of notation, we sometimes treat, e.g., X,, as set.
We focus on the task of sequentially querying function f: X' - IR. in order to find point X whose value f(x) is within c <> 0 of the supremum. Such point is said to be c-optimal if this condition holds and (e, oopttmal if holds with probability at least 1 d. Throughout, we write (æt) for the sequence of query locations.
At any given time L E No. our understanding of the target function's 's behavior is driven by domain knowledge and any data that we have already collected. We combine this information with the help of Bayesian model by placing prior on and defining observation model. Different types of models are eligible and techniques introduced in the sequel simply require that we are able to simulate the chosen stopping conditions (e.g.. e-optimality). We focus on the most popular family of models in this setting: Gaussian processes.
A Gaussian process (GP) is a random function f:X' - R such that, for any finite set X C X, the random variable f(X) E R [ is Gaussian in distribution. We write f ~ GP(O, k) for centered GP with covariance k : X' x X + and model observations as function values corrupted by independent Gaussian noise, i.e. (Xx,) f(X)) ~ ((((X) 2I) Conditional on (X,),, we therefore believe that f is distributed as ft ~ GP((pe where A = k(X,, X,) + 2 is used to define
(I) Finally, assume that X' is compact and that Hr and ke are both continuous their limits are attained on X' Among other things, this assumption allows us to write 8, E arg max (x) for a preferred solution at time t, where S, is either the set of evaluated points X, or the search space X.
(x(x)= k( X,)A X() yXx,))
(x( k(xx x') k(x, X,)A k x').
Method
Suppose Bayesian optimization terminates at time i No and returns a point æ E A' as the solution. Our regret for having returned this point is defined as the distance between f(z) and the optimum. Under the model ft, this (simple) regret manifests as a random variable
(x) lt [x(
ft sup (wx) xEX
Given a regret bound e > and a risk tolerance d > O, we would like to stop searching once we have found point so that v=())) < e with probability at least 1 8 and refer to this stopping rule as a probabilistic regret bound (PRB). Probabilities of this sort are usually intractable and we will therefore estimate them via sampling. To this end, we denote the probability that a point is
2

---

% Stopped
% Successful
Trials
.84
.89
.89
.90
22
17
14
12
Risk Tolerance d
.93
997
J96
977
.95
.95
.97
57
31
23
18
16
.82
.99
.90
.9T
98
.97
.97
.99
.99
655
39
26
22
18
61
91
.99
1
:98
1
7-1
19
33
26
20
15
10
.47
.77
.00
.97
.98
78
63
40
31
23
17
11
256
.34
.62
86
70
48
36
27
10
10
10P
10-2
Regret Bound
Regret Bound
Regret Bound e
Figure I: Overview of PRB stopping behavior when 0, 1Ja - - is drawn from a model with noise variance 7² 14-4. Regret bounds e > 0 dictate how close f()) must be to the optimum f for æ E X to be satisfactory. Tolerances 5 > upper bound the chance of returning an unsatisfactory point. Left: Percent of runs that stopped before time T = 128. Middle: Percent of stopped runs that returned e-optimal points. Right: Median number of trials performed by stopped runs.
e-optimal and an associated Monte Carlo estimator by
(x) = P(re(a)) ()
V (x=;e
n Σ (r((()) <c),
where (x)) is the i-th independent draw of the model-based regret (2). We will shortly explore how to construct estimators VT (a:) and use them to decide whether (x(x)) is above or below a level À E IR in manner that is both cost efficient and robust estimation errors. First, however, let introduce some basic terminology that will help us reason about potential failure modes.
We will say the estimator produces false positive if V (x) 2 X (x()) and true positive if VT (x) 2 A A , (x) 2 A. Since either scenario may lead to an unsatisfactory solution, the level that we compare against must exceed 5. Accordingly, let unod and 8est be nonzero probabilities such that 6mnd + Jest S ó. By defining = 5mods we will use dmod to limit the chance that a point is not c-optimal even though 7 (xx) produced
positive. Conversely, we will use dest to control the probability of encountering a false positive (see Section 3.2). This pattern guarantees that if V (x) X, then is e-optimal with probability least
5 under the model.
Algorithm sketches typical BO loop with the proposed stopping rule. At each iteration, we obtain model for the data. We then select candidate solutions C X and estimate their probabilities of being optimal under the model. If an estimate is greater than 5mod then the corresponding point satisfies the stopping conditions with probability at least and we terminate; otherwise, press
Algorithm BO with Monte Carlo PRB
1: input data D E (X x RR)h,, limit T E N, and parameters e, Smod. Sest > 0
2: (6'ms) t getSchedule, ( T To)
for To.... T do
4: + getModel(D)
C t getCandidates
The rest of this section examines two key questions: how to simulate model-based regrets (x) when | large (or infinite) and how to avoid false positives
Z MC-PRB C; 8mod )
max Z >
dmod then
8:
break
due to estimation eиror. Appendix A explores related topics such as how to choose C and schedule 5'm.
+
getNextQuery
10:
D D {Ix, y(x)))
Figure shows how the proposed algorithm behaves for different choices of and 5. Data was generated by running BO a hundred times and sampling rs(s:) thousand times per step using the strategy from 8mod where dmod 6/2. These results do not take advantage of the testing paradigm introduced in Section 3.2, but accurately reflects the algorithm's behavior. particular, we see that the number of function evaluations performed by each automatically adapts the definition of (e, 8) -optimally
11: return xz E C: Z. = max Z
Section 3.1. Stopping decisions were then made by comparing estimators V (sx) with À
3

---

Distribution of ft
Draws of ft
IP (r(((x) S 5e)
1.50
1.50
1.00
0.75
0.75
0.75
0.00
0.00
0.50
-0.75
0.75
0.25
-1.50
1.50
0.00
0.00
0.25
0.50 0.75 1.00
0.00
0.25
0.50 0.75 1.00
0.00
0.25
0.50 0.75 1.00
R
R
I
Figure 2: Left: Posterior mean and two standard deviations of f (blue) given eight noisy observations (black dots). The goal is to find a point a E X whose true function (black) value within c of the optimum f* (orange star). Middle: Draws of ft (P(M,, k2) and fü (orange stars). Right: Estimators for vr, Ground truth (dashed black) was established using location-scall sampling on dense grid. The joint-sampling strategy from Section 3.1 is shown in blue. Competing methods analytically integrated out fe(x:) Je by approximating it with: fe(a)), fe(x)) fe(x)) S fr" or
f()) (x) S fr A f+
where ft and x; arg =ax x fa()) were jointly sampled.
3.1 How to simulate stopping conditions
This section describes how to simulate whether point E X' satisfies the chosen stopping conditions. For PRB, this amounts to sampling Bernoulli random variables [(rr(x)) S E). We propose to generate this term by maximizing draws of ft. When dealing with parametric models, function draws are obtained by sampling parameter vectors. For GPs, analogous logic may be enacted by using parametric approximation to the prior [52], as outlined below. This approximate sampling step is necessary because the time complexity for exactly simulating fx( scales cubically in [X].
Let Φb X - Rm be finite-dimensional feature map so that, Var, x' E X, (bxx) ((xx) as k(ær, x' Note that feature maps of this sort are readily available for many popular covariance functions [37, 52]. Equipped with such map, may approximate prior GP(,, k) with Bayesian linear model
f(-) (b.))Tmu
N(O,
Letting A lxX,, X,) + I I and NO, y I), this linear model may be used to generate draws from an approximate posterior by sampling w from the prior and using Matheron's 's rule to write [51]
fa(-) 2 ((,+ f(x,) - -E].
(5)
For each draw of fú, the remaining problem is now to evaluate (1)( S e). We suggest using multi-start gradient ascent. In our case, we performed an initial random search to identify promising starting locations and then used a quasi-Newton method [28] to optimize. A helpful insight that we do not need to find f per se. Rather, it suffices to determine whether there exists point æ' e X such that (x') (x) > This property can exploited accelerate simulating (r, S e): however, its benefits wane as (x))) increases because (x()) implies that no such point x' exists.
The right panel of Figure 2 compares different estimators for Vr, For simplicity, assume that fi is sample continuous so that it almost surely attains its supremum on X' The goal of this plot is to conditioning on the maximum. We not only need to upper bound fú, but also account for the point(s) at which the maximum is achieved. This explains why the red estimator Fe, [P(Jf fa( S fx( = Si, f((x)) S ft)] outperforms the orange one E,; [IP(2 fx()) e)], while the green one EE; [PP[tt f((x) S fe(x)) S st)] fails to do so. We opted to avoid these issues by sampling fx jointly with ft rather than marginalizing it out.
highlight challenges inherent
The resulting blue estimator seen to more accurately follow the gold standard shown in black.
Lastly, it should be said that the suggested sampling procedure introduces a yet-to-be bedebee-ddeedeed amount of error in practice, since draws of fe are not only approximate non-convex. Initial results suggest these emror are small (see Figure 2), however we leave this topic for future investigation.

---

Log1o Sample Size
CDF of (T)
Time to Estimate v((x))
3.5
100
5.8
4.7
3.7
2.6
1.2
1.00
Risk Tolerance d
6.0
4.9
3.8
2.8
1.4
Probability
0.75
Logio Seconds
2.5
10
6.1
4.9
4.0
3.0
1.5
0.50
1.5
6.1
5.1
4.0
3.0
1.7
0.25
0.5
10-4
6.1
5.1
4.2
3.1
1.7
0.00
-0.5
10
10-2
10"
0.01
0.03
0.1
0.32
1.0
0.01
0.03
0.1
0.32
1.0
Bernoulli Parameter
Estimated Value
Distance from
Figure 3: Left: Median number of draws used by Algorithm 2 to decide if the expectation of Bernoulli random variable Z ~ Bern(p) exceeds = 10-5 (chosen arbitrarily). Middle: Empirical CDFs of V when optimizing draws from known priors GP k)) in two, four, and six dimensions with noise variance 72 10 (solid, o) or y2 = 10 (dashed, x). PRB parameters were set to e 0.1 and mmod dest 2.5%. Right: Runtimes for Algorithm 2 using the generative strategy from Section 3.1 and a (wall) time limit of roughly one thousand seconds.
3.2 How to efficiently make robust decisions with Monte Carlo estimates
This section discusses the general problem of using samples to decide whether the expectation of a random variable 7 E {0, }} exceeds level À E [0. 1]. For PRB, À 1 mood and each evaluation of the stopping rule corresponds to unique Z = [rr((z) I e). We will show how to make probably-correct decisions using a minimal number of samples n E N. In doing so, we first discuss confidence intervals for E|Z] based on a collection of i.i.d. draws Z, = {2, : = 1........
There many techniques for generating intervals that contain E[ with (coverage) probability at least 1 Sest- Clopper Pearson [13] gave an exact recipe for constructing confidence intervals for Bernoulli random variables Z as
CI(Z,, 5) [B k+ 1), B(1 1 k)].
(6)
where B denotes the beta quantile function and A: - Σ i=1 Zq is the number of successes in n draws. It is also possible to take a Bayesian by placing a prior on [E[2]. Differences between this Bayesian approach and (6) were observed be minimal however, so opted avoid modeling E[Z]. For further discussion, see Appendix A.1.
Given an estimate 7n 1 n E 2; and confidence interval I, = CI(Z,; Best), it follows that
E1Z E In and I 1 ( A) = 1 (Z, 2 A)
groundd
decision
If I,, collapses point -> 0o, then there exist sample sizes such that & In, whereupon the conclusion from (7) holds with probability at least &est." Said differently, we can lower bound the probability that we correctly decide whether R[Z] 2 À by generating enough draws of Z. With these details in mind, we now review an algorithm for adaptively choosing n E N in order to make probably-correct decisions using as few samples as messible-which crucial when simulating Z is computationally intensive as in Section 3.1.
The general idea of Algorithm 2 is to perform series of tests (each using more samples than the last), until a confidence interval for E[Z] is narrow enough for a decision to made. To better understand this, start by defining two sequences: sample sizes (nz) and risk tolerances (d,). The sizes should be increasing, while the tolerances should be positive and satisfy Σラ= dj S 8est-
Next, imagine that we generate draws of Z in batches of size n, 7 where no 0. At each round of sampling j. we construct an interval In, that contains E 2] with probability at least - dj. If A & Iny, we use Zn, to decide whether E 2 2 X. Otherwise, we proceed to the next iteration.
We may that assume P(A E|Z]) 0. Here, [ (=:()) is only random prior observing y(.)).
5

---

Per (7), this algorithm only makes an incorrect de- cision if the final interval fails contain [E| By definition of (dj) and the union bound however, the chance of any interval not containing E [ most
Algorithm 2 Monte Carlo PRB
I: imput point X, model f: Ω2 II
and parameters e, Smod, dest > 0
(d,) + get.chedule,, ((
dest. Hence, the algorithm makes the correct decision with probability at least 8est-
3: (nz) f getSchedule,,
Z -
Algorithm 2 was inspired by bandit methods, such
5: for j = 1.2,,..du do
as Mnih et al. [33] and references contained therein, who previously studied how concentration inequalities can be used to iteratively test whether
while [Z < < do f* getSample(f) ft + supzEx + f (z)
8:
P(IZ,, - [ S Z(Z) 2 --s Algorithm 2 is closer to Bardenet et al. [6] however, who used a sim- ilar strategy to decide whether to accept Metropolis-
9:
Z Zu f()) S {
10:
1 & CI dg) then
11:
break
Hastings proposals based on subsampled estimates of the data -og-liieldoodd
12:
return Average
Extending our earlier argument, let (B'se) be a sequence of risk tolerances such that Ei=1 8est S Sest- If Algorithm 2 run at each BO step with schedule (d²) such that Σÿ= dž S &est then the chance of encountering a false positive at any step is bounded from above by dast Consequently, the decision to stop will be correct with probability at least 8est.
We followed Mnih et al. [33] by defining d' = ja (a-1)) 8 and n2 [ We set a 1.1 so that (d') decayed slowly, 8 = 1.5 such that (nz) grew reasonably quickly, and N = 64 because smaller starting values took longer to run. These choices impact the algorithm's runtime, not its validity. Using a geometric schedule for (ny) prevents (d') ) from rapidly shrinking due large number of tests being performed with very few samples. In exchange, this schedule can lead to nearly times too many samples being requested.
The left panel of Figure 3 shows how many samples Algorithm 2 used to decide whether E[Z] 2 for Z ~ Bern(p). As p + 1, the distance between Zn and À tends to increase and decisions can be made with wider confidence intervals constructed using fewer draws. As dest + 1, these intervals shrink and decisions can similarly be made using fewer samples. The middle panel visualizes the empirical CDF of estimates V from BO experiments described in Section 5. For most of a typical BO run's 's life cycle, these estimates are far from À = 1 8mod so decisions can be made efficiently. This pattern is reflected in the rightmost panel, which illustrates the savings provided by Algorithm 2.
4 Analysis
We show that Bayesian optimization with the PRB stopping rule terminates under mild assumptions. Further, we prove that the given algorithm is correct in the sense that it returns an (e, 8e, -oottial point under the model.
We begin by discussing the assumptions made throughout this section, which are:
A1. The search space X' = [0, 1) is a unit hypercube.
A2. There exists a constant L3 > so that, Yx, x' E X. [k(x, x) k(x,, x') S Lx| - x' a'lloc.
A3. The sequence of query locations (x;) is almost surely dense in X.
A1 and A2 guarantee possible for the maximum posterior variance to become arbitrarily small given a finite number of observations. Note that if hyperparameters change over time, we only require that the (best) Lipschitz constant Lş and noise variance 7² do not grow without bounds as + co. Combined with these assumptions, A3 implics that, for any C' > 0, there exists time T E No such that, Vt > T. max Ke (x x) < C with probability one. More generally, A3 is necessary to ensure convergence when all we known is that X' is compact and f is continuous [45].
When A1 and A2 hold, popular strategies often produce almost surely dense sequences (æz). For instance, Vazquez& & Beet [47] proved Probability of Improvement [25] and Expected Improvement [38] exhibit this behavior for many covariance functions & when f is directly observed. In Appendix B, we show that this result holds for continuous acquisition functions that value informative queries over unambiguous ones. This family includes well-known acquisition functions such as Knowledge Gradient [15], Entropy Search [20], and variants thereof [21, 49]. Finally, dense sequences can be

---

guaranteed by introducing small chance for queries to be selected at random from an appropriately chosen distribution [44].
We first prove that points which maximize the posterior mean eventually satisfy the PRB criterion and then use this result to demonstrate convergence and correctness.
Proposition 1. Under assumptions Al-A3 and for all regret bounds 0 and risk tolerances å > 0, there almost surely exists T E No so that, at each time Z T, every 8, E arg =ax (r(a) satisfies
V (x( e) = (s)) <) 2 8.
(8)
Sketch. We sketch the proof below and provide full details in Appendix B for details. Consider the centered process g:(-) = [f(()) (s( + [Mee (s:) (4{ Since the second term is nonnegative,
gi = supzex (x(x) (5,)) ft - f(+) and it suffices upper bound the probability that gi 2 e. For e > B(g ), such a bound may be constructed by using the Borell-TIS inequality [8, 46] to write
c B(gi) -
P( 2 S exp
of
= max Var Varlye (2)).
de
aEd
Since B(g])) and (9) both vanish as or decreases, the claim holds so long as lim O2 O.
Similar ideas can be found in Grünewälder et al. [18], who proved that the expected supremums of centered process like 9i go to zero as (xx)) becomes increasingly dense in X. In Appendix B, we extend this result to the setting where observations are corrupted by i.i.d. Gaussian noise and combine with the BorelI-TIS inequality to show the probability that (=:)) 2 e vanishes. We also give a simple corollary for the case where solutions belong to X,. Next, we show that BO not only stops when Algorithm 2 is used to evaluate the proposed rule but does so correctly.
Proposition 2. Suppose assumptions Al-A3 hold. Given risk tolerance 8 > O, define nonzero probabilities dmod and Sest such that mmod + Sest I 8 and let (8 be a positive sequence so that Eizo 8es < dest. For any regret bound
O, if Algorithm 2 is run at each step No with tolerance 8emt to decide whether point 8, E arg max (x) satisfies the stopping criterion
(r(x;;) = P(r)(s)) S 2 1 6mod.
(10)
then BO almost surely terminates and returns an (c, 8) opptimal solution under the model.
Proof. By Proposition 1, there almost surely exists an S E No so that 2 - V((8,) 2 1-ddnd- Further, because " (s:) is unbiased, there exist times t 2 T at which Algorithm 2 produces true positives V/ (s))
5mod A (s(ss) 2 mmod Hence, BO stops with probability one. BO terminates at time T No. then the probability that 8T is not e-optimal is less than or equal to mod
in the event of a true positive and one otherwise. Since false positives 7/7 > 1 ômod V (s:) occur with probability at most dest, it follows that 8r is c-optimal with probability at least
L
In summary, we can design statistical tests to mitigate the risk of premature stopping due random fluctuations in Monte Carlo estimators like V.. Moreover, we can schedule these tests to ensure that points which pass them are sufficiently likely (under the model) to satisfy our stopping conditions. If the model is correct, we can therefore guarantee that a satisfactory solution is returned with high probability. Provided that one or more points almost surely satisfy the rule as -> oo, this result holds if we can simulate whether solutions are satisfactory and bound the error in the resulting estimator.
5 Experiments
To shed light on how our algorithm behaves in practice, we conducted a series of experiments. Focal questions here included: i) how does PRB perform in comparison to existing stopping rules, ii) how do these rules respond to different types of problems, and iii) what is the impact of model mismatch.
Experiments were performed by first running BO with conservatively chosen budgets T E N. We then stepped through each saved run with different stopping rules to establish stopping times and terminal performance. This paradigm ensured fair comparisons and reduced compute overheads. We performed a hundred independent BO runs for all problems other than hyperparameter tuning for convolutional neural networks (CNNs) on MNIST [14], where only fifty runs were carried out.
7

---

Problem
D
T
Oracle!
Budget'
Acq
ACB
AES
PRB (ours)
GP 10
2
64
10 (100)
17 (96)
28 (100)
16 (96)
22 (99)
17 (97)
GP 10-2
2
128
11 (100)
22 (96)
78 (100)
(100))0)
54 (100)
23 (99)
GP 10-6
4
128
27 (100)
64 (95)
90 (100)
(97)
93 (100)
64 (99)
GP 10
4
256
30 (100)
94 (95)
106 (98)
256
197
86 (96)
GP 10-6
6
256
40 (99)
124 (95)
142 (98)
150
256 (99)
134 (98)
GP 10-2
6
512
65 (100)
227 (96)
181 (96)
(100)
278 (99)
235 (100)
GP 10-6
4
128
35 (100)
79 (95)
92 (100)
41 (66)
77 (94)
61 (88)
GP 10-2
4
256
51 (100)
157 (95)
128 (97)
256 (100)
160 (96)
100 (92)
Branin
2
128
19 (100)
25 (95)
(100)
(100)
38 (100)
33 (99)
Hartmann
3
64
14 (100)
22 (96)
26 (100)
18
21 (97)
19 (100)
Hartmann
6
64
(67)
256 (67)
40 (67)
38 (67)
(67)
40 (64)
Rosenbrock
4
96
34 (100)
46 (95)
95 (100)
88 (100)
98 (100)
84 (100)
CNN 4
256
(100)
11 (96)
64 (100)
64 (100)
64 (100)
17 (100)
XGBoost
3
128
(100)
8 (97)
128 (100)
90 (100)
51 (100)
28 (99)
Table I: Median stopping times and success rates when seeking (c, -optimml points X' [0, 1] given an upper limit of e N function evaluations. For GP objectives, number beside each name specify noise levels 2 Superscripts indicate that model stopping rule parameters were given by an oracle. For each problem, non-oracle methods that returned e-optimal points at least 1 - percent of the time using the fewest function evaluations shown in blue.
Despite the general notation of the paper, all problems were defined as minimization tasks. Additional details and results can be found in Appendices C and D, respectively; and, code is available online at https:/ / tittub....... com/j wttlli/nntrritte_stoooooeee
Each BO run was tasked with finding an e-optimal point with probability at least 1 - 8 = 95%. On the Rosenbrock-4 fine-tuning problem, we used a regret bound c = 10-4, For CNNs, we aimed be within 0.5% of the best test error (i.e., misclassification rate) seen across all runs, namely 0.62%. Likewise, when fitting XGBoost classifiers [12] for income prediction [7], we sought be within 1% of the best found test error of 12.89%. For all other problems, set 0.1.
For PRB, we divided å evenly between dest and ōmod- Since experiments were carried out using preexisting BO runs that each began with five random trials and ended at times T, we employed constant schedule & T Sest for risk tolerances at steps e Ng. Parameter schedules for Algorithm 2 are discussed in Section 3.2.
As practical concession, we limited each run of Algorithm 2 to a thousand draws of ft and used the resulting estimate to decide whether to stop-even if the corresponding confidence interval was not narrow enough to afford guarantees. Results under this setup were consistent with preliminary experiments in which Algorithm 2 was run using fifteen minute time limit. Finally, when optimizing draws from GP priors in six dimensions with noise y 10 1002, we evaluated PRB once every five steps to expedite these experiments.
5.1 Baselines
We tested several baselines, some of which were granted access to information that would usually be unavailable (indicated by dagger f). We summarize these as 2
B1. Oracle': stops once an e-optimal point has been evaluated.
B2. Budgett: stops after fixed number of trials chosen by an oracle for each problem.
B3. Acq [23, 35]: stops when the acquisition value of the next query is negligible.
Note that these descriptions do not account for the presence of link function (see Appendix C.2).

---

B4. ACB [29]: stops once the gap between confidence bounds is less-equal to C' > 0, i.e.
max (z) max (x') S [U/L]CB((z) p.(x) + v (x,)(
=EX
x'eX,
BS. AES [22]: stops when an upper bound on [E(G)) E(fi-1) drops below level.
B1 is the optimal stopping rule, but requires perfect information for f. Likewise, B2 is the optimal fixed budget for each problem. These budgets were defined post-hoc as the minimum number of trials such that at least 95% percent of runs returned 6-optimal points (where possible).
The remaining methods all model-based and stop when target quantities are sufficiently small. For the chosen acquisition function (see Appendix C.3), B3 can be interpreted as the expected im- provement in solution quality given an additional trial, i.e. Eye,1 [axxeeX... (z) M (8x) Unfortunately, neither this quantity nor the change in the expected supremum used by B5 lend themselves to interpretation in terms of (c, 8) optimalliy.. B4 does admit such an interpretation for appropriate choice of constant 3r [43]: however, these constants are often difficult to obtain in practice however, so we followed [29] by defining B, = & log (Dt2222/6))
To combat these issues, we gave baseline methods a competitive advantage by retroactively assigning cutoff values to ensure they achieved the desired success rate when optimizing draws from the model (denoted GP Specifically, cutoff values for B3-B5 were obtained by dividing regret bounds c by the smallest powers of two for which this condition held-explicitly; 2 2 and 24 (respectively). Note that, in the absence of this fine tuning, these methods either proved unreliable or failed to stop within the allotted time depending on whether thresholds were too large or too small. For completion, additional results using é as the cutoff value for B4 and B5 are presented in Appendix D.
The main results of this section shown in Table and key findings are discussed below.
5.2 Results with true models
When optimizing functions drawn from known GP priors, denoted GPi, the proposed stopping rule performed exactly advertised and consistently returned (c, 8) opttmmll solutions. Moreover, PRB often requiring the fewest function evaluations. This result is not surprising when comparing with methods like B4 because unbiased estimate (1)) S e) should exceed level faster than corresponding lower bound. In many cases, PRB achieved a higher success rate than the fixed budget oracle using comparable or smaller number of trials. These gains occur because model-based stopping is able to exploit patterns in the data collected by individual runs.
Elsewhere, observe that B4 struggled to terminate when faced with moderate noise levels y2 10-2. This pathology likely emerges because, similar to alternative estimators discussed in Section 3.1, the method does not fully account for dependencies between f: and fi (z)). As extreme example, B4 may fail to terminate when a point x E X, simultaneously maximizes upper and lower confidence bounds, despite the fact that (x x; x) O.
Not surprisingly, BO runs that took longer to query an e-optimal point took longer to stop. However, the correlation between these terms paled in comparison to that of stopping times and a-quantiles of regrets incurred by uniform random points (approximately, 0.35 vs. -0.75). Said differently, PRB stopped faster when f was outlier. This pattern suggests that the one-step optimal strategy from Appendix C.3 is better at finding optimal solutions than verifying them. Future works may therefore wish to pursue stopping-aware approaches along the lines of McLeod et al. [32] or Cai et al. [11].
5.3 Results with maximum a posteriori models
In the real world, the high-level assumptions that govern how the model behaves (i.c., its hyperpa- rameters) are tuned online as additional data is collected using Type-Il maximum likelihood. We are therefore interested in seeing how discrepancies between the model and reality influence stopping behavior.
Results here were similar to the synthetic setting, albeit with some blemishes. Interestingly, the most glaring example of the risks posed by model mismatch occurred on the popular Hartmann-6 test function. Here, 33% of BO runs overestimated the objective function's smoothness and converged to a local minimum of -320 rather than the global minimum of -3.32. It is worth noting, however,

---

that e e cases (see Appendix D). Along similar lines, models occasionally underestimated the kernel variance when optimizing draws from GP priors and stopped prematurely.
0.1 had been slightly larger, all stopping rules would have succeeded in at least 95% of
These results also indicate that both hyperparameter tuning problems (CNN and XGBoost) were fairly easy and this may have masked potential failure modes. The fixed budget oracle's performance demonstrates that there was still room for model-based stopping rules fail, but we nevertheless recommend that these results be taken with grain of salt.
In additional experiments, we indeed found that it was easy construct cases where poor model fits led to poor stopping behavior. This vulnerability was large due to our choice hyperpriors (see Appendix C.I), which were purposefully broad and uninformative. Overall, argue that these results are both highly encouraging and also highlight the importance of uncertainty calibration. Potential remedies for this issue discussed below.
Based on these findings, we suggest that model-based stopping be used with more conservative priors that, e.g., favor smaller lengthscales and larger variances. Alternatively, calibration issues may be alleviated by marginalizing over hyperparamettrs [41] or utilizing more expressive models. These options help reduce the risk of overly confident models leading to premature stopping. Along the same lines, we recommend using a large fixed budget as an auxiliary stopping rule to avoid cases where poor model fits cause the algorithm to converge very slowly (see Appendix A.3 for discussion).
6 Conclusion
To the best of our knowledge, results presented here are among the first of their kind for Bayesian optimization. We have given practical algorithm for verifying whether a set of stopping conditions holds with high probability under the model. For the proposed stopping rule, we have further shown that the algorithm correctly terminates under mild technical conditions. If data is generated according to the model, we can therefore guarantee that BO likely to return a satisfactory solution.
The methods we have shared are largely generic. Echoing the introduction, if you can simulate it then you use it for stopping. While this approach is not without limitations, we believe that it will ultimately allow others to design stopping rules as they see fit. To the extent that it does, model-based stopping may one day become as common place as model-based optimization.
References
[1] Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis,
A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y.. Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: / /www. tensorflow org/. Software available from tensorflow.org.
[2] Adler, and Taylor, E. Random fields and geometry. Springer Science & Business Media, 2009.
[3] Agarap, A. F. Deep learning using rectified linear units (relu). arXiv preprint arXiv:1803.08375. 2018.
[4] Audibert, J.-Y., Munos, R., and Szepesvári, C. Tuning bandit algorithms in stochastic envi- ronments. In International conference on algorithmic learning theory, pp. 150-165. Springer, 2007.
[5] Balandat, M., Karrer, B., Jiang. D. R., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. In Advances in Neural Information Processing Systems 33, 2020.
[6] Bardenet, R., Doucet, A., and Holmes, C. Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach. International conference on machine learning, pp. 405 PMLR, 2014.
[7] Becker, B. and Kohavi, Adult. UCI Machine Learning Repository, 1996. DOI: http::/bb..or//02233225x5x
10

---

[8] Borell, C. The Brunn-Minkowski inequality in Gauss space. Inventiones mathematicae, 30(2): 207-216, 1975.
[9] Brown, D., Cai, T. T., and DasGupta, A. Interval estimation for a binomial proportion. Statistical science, 16(2):101-133, 2001.
[10] Byrd, R. H., Lu, P., Nocedal, J., and Zhu, C. A limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing, 16(5):1190-122 1995.
[11] Cai. X., Gomes, S., and Scarlett, J. Lenient regret and good-action identification in Gaussian process bandits. In International Conference on Machine Learning, pp. 1183-1192. PMLR. 2021.
[12] Chen, T. and Guestrin, C. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference knowledge discovery and data mining, pp- 785-794, 2016.
[13] Clopper, C. J. and Pearson, E. S. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 2644):404-413, 1934.
[14] Deng, L. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6): 141-22,4 2012.
[15] Frazier, P., Powell, W., and Dayanik, S. The soallldgggggrdieen policy for correlated normal beliefs. INFORMS journal on Computing, 21 21(4):599-613 2009.
[16] Garnett, R. Bayesian optimization. Cambridge University Press, 2023.
[17]
Griffiths, R.-R. and Hernández-Lobato, J. M. Constrained Bayesian optimization for automatic chemical design using variational autoencoders. Chemical science, 11(2):577-586, 2020.
[18] Grünewälder, S., Audibert, Y., Opper, M., and Shawe-Taylor, J. Regret bounds for Gaussian process bandit problems. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 273-280. JMLR Workshop and Conference Proceedings, 2010.
[19] Hansen, N. The CMA evolution strategy: A tutorial. arXiv preprint 1 2016.
[20] Hennig, P. and Schuler, C. J. Entropy search for information-efffiiient global optimization. Journal of Machine Learning Research, 13(6), 2012.
[21] Hernández-Lobate J. M., Hoffman, M. W., and Ghahramani, Z. Predictive entropy search for efficient global optimization of black-box functions. Advances in neural information processing systems, 27, 2014.
[22] Ishibashi, H., Karasuyama, M., Takeuchi, I., and Hino, H. A stopping criterion for Bayesian optimization by the gap of expected minimum simple regrets. International Conference on Artificial Intelligence and Statistics, pp. 6463-6497. PMLR, 2023.
[23] Jones, D. R. A taxonomy of global optimization methods based on response surfaces. Journal of global optimization, 21 :3453383, 2001.
[24] Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint 2014.
arXiv:1412.660
[25] Kushner, H. J. A versatile stochastic model of function of unknown and time varying form.
Journal of Mathematical Analysis and Applications, 5(1):100-667, 1962.
[26] Lederer, A., Umlauft, J., and Hirche, S. Posterior variance analysis of Gaussian processes with application to average learning curves. arXiv preprint 190iv: 01404, 2019.
[27] Lederer, A., Umlauft, J., and Hirche, S. Uniform error bounds for Gaussian process regression with application to safe control. Advances in Neural Information Processing Systems, 32, 2019.
[28] Liu. D. C. and Nocedal, J. On the limited memory bfgs method for large scale optimization. Mathematical programming. 45(1):503 528. 1989.
[29] Makarova, A., Shen, H., Perrone, V., Klein, A., Faddoul, J. B., Krause, A., Seeger, M., and Archambeau, C. Automatic termination for hyperparameter optimization. In International Conference on Automated Machine Learning, pp. 7-1. PMIRR, 2022.
[30] Massart, P. Concentration inequalities and model selection: Ecole d'Eté de Probabilités de Saint-Flour XXXIII-2003, Springer, 2007.

---

[31] Matthews, A. G. d. G., van der Wilk, M.. Nickson, T., Fujii, K., Boukouvalas, A., León- Villagrá, P., Ghahramani, Z.. and Hensman, J. GPflow: Gaussian process library using TensorFlow. Journal of Machine Learning Research, 18(40):1-6, apr 2017.
[32] McLeod, M., Roberts, S., and Osbore,, M. A. Optimization, fast and slow: optimally switching between local and Bayesian optimization. In International Conference Machine Leurning, pp. 3443-3452. PMLR, 2018.
[33] Mnih, V., Szepesvári, C., and Audibert, J.-Y. Empirical Bernstein stopping. In Proceedings of the 25th international conference on Machine learning, PP. 672-679, 2008.
[34] Močkus, On Bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference: Novosibirsk, July 1-7, 1974, pp. 400-404, Springer, 1975.
[35] Nguyen, V., Gupta, S., Rana, S., Li, C., and Venkatesh, S. Regret for expected improvement over the best-observed value and stopping condition. In Asian conference on machine learning.
pp.
PMLR, 2017.
[36] Picheny, V., Berkeley, J., Moss, H. B., Stojic, H., Granta, U., Ober, S. W., Artemev, A., Ghani, K., Goodall, A., Paleyes, A., Vakili, S., Pascual-Diaz, S., Markou, S., Qing. J., Loka, N. R.
B. S., and Couckuyt, I. Trieste: Efficiently exploring the depths of black-box functions with TensorFlow, 2023. URL https: patttss//aatee www.xiii..oo/abbaaee
08436.
[37] Rahimi, A. and Recht, B. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
[38] Saltenis, V. R. On a method of multi--ettrmml optimization. Automatics and Computers (Avtomatika i Vychislitelnayya Tekchnika), 3:33 1971.
[39] Scott, W., Frazier, P., and Powell, W. The correlated knowledge gradient for simulation optimization of continuous parameters using Gaussian process regression. SIAM Journal on Optimization, 21(3);99--1026, 2011.
[40] Simon, H. A. Rational choice and the structure of the environment. Psychological review, 63 (2):129, 1956.
[41] Simpson, F., Lalchand, V., and Rasmussen, E. Marginalised Gaussian processes with nested sampling. Advances in neural information processing systems, 34: 14:13613-22 3-133311165,,, 2021.
[42] Snoek, J., Larochelle, H.,, and Adams, R. P. Practical Bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
[43] Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:09/2.39995, 2009.
[44] Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
[45] Tömn, A. and Zilinskas, A. Global optimization, volume 350. Springer, 1989.
[46] Tsirelson, B., Ibragimov, I., and Sudakov, V. Norms of Gaussian sample functions. In
Proceedings of the Third Japan-USSR Symposium on Probability Theory, volume 550, pp.
20-41. Tashkent, 1976.
[47] Vazquez, E. and Bect, J. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. Journal of Statistical Planning and inference, 140(11): -088-3095,20 2010.
[48] von Kügelgen,, J., Rubenstein, P. K., Schölkopf, B., and Weller, A. Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networks. arXiv preprint arXiv:1910.0396. 2019.
[49] Wang, Z. and Jegelka, S. Max-value entropy search for efficient Bayesian optimization. In International Conference on Machine Learning, pp. 3627-3635. PMLR, 2017.
[50] Wilson, J., Hutter, F., and Deisenroth, M. Maximizing acquisition functions for Bayesian optimization. Advances in neural information processing systems, 31, 2018.
[51] Wilson, J.. Borovitskiy, V., Terenin, A., Mostowsky, P., and Deisenroth, M. Efficiently sampling functions from Gaussian process posteriors. In International Conference on Machine Learning. pp. (0292-1030)) PMLR, 2020.
[52] Wilson, J. T., Borovitskiy, V., Terenin, A., Mostowsky, P., and Deisenroth, M. P. Pathwise conditioning of Gaussian processes. The Journal of Machine Learning Research, 22(1):4741- 4787, 2021.
12

---

Bayesian (Jeffreys)
Bayesian (Uniform)
4.0
1.8
3.6
1.2
0.8
0.6
Risk Tolerance 6yst.
-
3.6
4.1
2.5
1.8
1.0
3.6
4.1
2.5
1.8
0.8
+
4.1
1.8
3.6
2.6
1.0
256
3.8
4.1
2.7
2.0
1.3
3.8
4.1
2.7
1.8
1.1
1021
4.1
2.2
3.8
2.8
1.4
Clopper-Peanee Pearson
Empirical Bernstein
3.6
4.0
2.5
1.8
1.0
3.6
3.8
2.9
2.5
2.2
Risk Tolerance dest
-12
4.1
1.9
3.6
3.1
2.2
-
3.6
4.1
2.7
1.9
1.3
3.6
3.9
3.1
2.7
2.3
4.1
2.0
3.8
3.1
2.4
1024
3.8
4.1
2.9
2.2
1.6
3.8
3.9
3.2
2.7
2.4
32
64
16
Rate Parameter
Rate Parameter p
Figure 4: Median number of samples (show in log1o) used by Algorithm 2 to decide if the expectation of ~ Bernoullip)) exceeds 2.5% using different types of intervals with nominal coverage probability 1 8est The number of samples drawn seen decrease in both dest and Ip A/.
A Practical recommendations
This section aims fill in some of the gaps left by Section 3 by providing further details for various subproblems and design choices encountered in practice.
A.1 How to construct confidence intervals
As discussed in the text, given random variable Z E R. there are different ways of generating intervals I, C IR that contain the true parameter [ with (nominal) coverage probability dest-
For Bernoulli random variables, Clopper-Pearson intervals (6) are a classic approach to this problem. This method is said be "exact" because (instead relying on the central limit theorem) uses the fact that X = Σi= 2, follows Binomial distribution, where Z; is the i-th independent copy of Z. This method also conservative; its (true) coverage probability greater than equal
dest-
Alternatively, one can take a Bayesian approach by placing prior on success rate E [0, 1] of the Binomial random variable X Bin(n,p). If this prior is chosen to be Beta distribution p ~ Beta(a, 3), then the posterior is conjugate and we have p ~ Beta(a + X, 3 + n X). Sensible choices include Jeffreys prior Beta(1/2, 1/2) and the uniform prior Beta 1).
The equal-tailed, Bayesian credible interval is obtained by taking the 6cnt/2 and 6/n/2 quantiles of X. Unlike those of Clopper-Pearson, Pearson, these intervals are not inherently conservative. Indeed,
13

---

Clopper-Peanee Pearson intervals contain Jeffreys intervals [9]. This property is sometimes desirable, since it may mean that fewer samples are required to make decision. In Bayesian optimization. however, one typically assumes that evaluating f is far more expensive than simulating it. We therefore opted to use the more conservative choice.
Lastly, it should be said that bounds on estimation errors can also be obtained when Z is not Bernoulli. For example, previous works [4, 33, 6] proposed use an empirical Bernstein bound to generate confidence intervals for random variables Z E [a, b]. defined here as
21og(3/6est) 3(b - a) log(3/6est)
E Zm| A. = /
(11)
n
where = and Sh = Σ ZZ, 21) denote the empirical mean and variance. While conservative, the resulting intervals Zn A, decay much faster than, e.g., their Hoeffding- inequality-basse counterparts when S, is much smaller than b b-6a a.
Figure illustrates how each of the methods discussed above perform in the context of Algorithm 2.
A.2 How to choose where to evaluate the stopping rule
Per Algorithm I, Algorithm may be evaluated in parallel on a set of candidates C S X. This confers certain advantages, such as the ability to share draws of fe and, hence, ft between points a E C. However, we must divide risk tolerance &est. by cardinality |C] to retain the union bound. Hence, Algorithm 2 may be slow when C is large. We should therefore chose C with care.
solutions must belong to the set of previously evaluate points, X,, then we suggest to define
C (ar X, P(f((s:) f(())) s <) )mod),
(12)
since the excluded points can safely be ignored. Empirically, we found that this heuristic usually eliminates all but a few points.
If solutions may be chosen freely on X' we instead recommend that C be constructed using one of the alternative estimators from Section 3.1 (all of which are differentiable). In particular, we recommend using gradient-basee methods to maximize the average of
(())())) S f((x) S S2. f7) + fi -z))
-1
(1++((2)) fi 1 =). (13)
ke+1 (0,22)))) x²/
k1+ (x, x/2²/
over multiple draws of ft and क; E arg max fix)), where ue+1 and k are the posterior mean and variance of fo given additional observation fx;t ft and & denotes the standard normal cumulative distribution function. The resulting set of points can then be tested using Algorithm 2.
A.3 How to schedule risk tolerances 8'st
Where possible, we recommend using (conservatively chosen) budget T E N for BO. This mean we suggest using PRB together with a fixed budget. Doing so not only ensures that the algorithm stops in a reasonable amount of time, but allows one use constant schedule 8 To E N denotes the starting time. Note that this how experiments from Section were run.
8wn T-7, where
no such budget is available, then we recommend adopting a strategy similar to Algorithm by only evaluating the stopping rule at certain steps t. For example, may employ geometric sequence of potential stopping times (f:). analogous to sample sizes (mz). and define
est = (a -1) Jest.
a >
1,
(14)
like de from Section 3.2. This practice ensures that &emt does not decay too quickly.
14

---

B Technical proofs
The main results of this section are follows.
i. Proposition shows that family of acquisition functions produce dense sequences (xt).
ii Lemma proves that variances vanish as X, becomes increasingly dense in X'.
ii. Lemma bounds the expected supremum of f ~ GP(O, ke) in terms of its maximum variance. iv. Proposition and Corollary 10 show that the PRB stopping criterion almost surely converges. Proposition 2 proves that BO with the PRB rule terminates and returns an (e, d'-optimal solution.
Many of the findings presented here and discussed previously borrow heavily from earlier works. Where appropriate, we attribute credit at the beginning of each proof.
Definition 3. Kernel k: X x X- the posterior variance (a)) [(X:)) point X goes zero as I - oo if and only if in is an adherent point of {at 1 0}.
+ has the no-empty-ball property [47] if. for any sequence (xx))
Proposition 4. Let f GP(O, k) be prior over functions on a compact space X ED and V; X + R be continuous acquisition function for ft. If k is continuous kernel that admits the no-empty-ball property and
ke(x, x) > "e(x',x') =0 Vi(x)) Vi(x))
Vt E N and Va, x' E X, (15)
then the sequence (xe) points 2t, E arg max Vi(ar) is dense in X.
Proof. Follows immediately from [47]. Without loss of generality, suppose Vi(x)) is non-negative and equals zero if and only if (xx 2) = 0. Let (xo,) and (2%,,) be subsequence of (æx) that converge to an accumulation point X' and write o maxfa: ag S () and 3r = max b, l). Then,
(arl)( [(x)) < VarlJ( f(
(16)
k( Vo,) k( TF,)) 2k (x., 23,))
Since (I..)) and (ass,) both converge to z and i assumed continuous, (16) goes to zero -> co. Consequently, Va, (Za.) and, therefore, Vi(z;) must also vanish as - cc [47, Proposition 12). By definition of xe, follows that lim m hi (xx x) The no-empty-ball property now gives the result.
Proposition 5. Let X C TR. be convex and suppose that X C X generates an e-cover of X. For every X and p the intersection of the set X and the ball B(x,, p) far X || x' e'll S p) generates 2e-cover of B(x, p).
p s. Since X' is convex, for every point E B(x, p) there exists a b E B(x, r) such that ||a - bll < E. Moreover, because X generates an X so that ||b cll S which implies that e E B(x, p). It follows by the triangle inequality that for every point a E B(x, p) there exists
Proof. Consider the ball Bxx,, r) with radius
E-cover of X, for every point b B(x, r) there exists
pair of points b, E B(x, r) x [B(x, p) n nx] such that
||a cl I |la bbla + |bb clloo S 22,
(17)
which completes the proof.
Lemma 6. Under assumptions Al and A2, if v()( ~ -NF()),)) is observed on a set of points
X C X that generates an s-cover X, 0 < E min(1, main[1,4aa.a Mz. then
Var[f(æ) vx)] (a()),
(18)
where
(x( [T<pp(e k( (ATxp(e)k(arrr)) - T m(E) + 2k
[k x)) (Lap()))ml +72
is given in terms of n(E)) ((xx(1,(ee//e)) and p(=) e for any 0 < <
15

---

Proof. This result extends Lederer et al. [26, Theorem 3.1], who showed that, for all 0 S k0,0)/La
Var[f(x) (( (4Laph(z, x) - x) L3pp² BB( +
(19)
(k(x, x) + 2L BB (x)) +
where [a)()) is the cardinality of the set (x)x) = B(x, p) n. We would like to convert this
upper bound into a function of 0 S. S 1. To this end, begin by noticing that the bound (19) increases monotonically on p S h(m,))/Lz and decreases monotonically on [B)()] No- Substituting p(E) for and v)(c) for n therefore yields a valid bound so long S p(=) I /// and 0 S T)()) S n. For clarity, note that p(z) defines the radius of ball around x and mnE) denotes
the minimum possible number of elements from X that lie within this ball.
Starting with the latter, lower bounds the cardinality of (x may be obtained from the fact that X is assumed to generate an s-cover of X. By Proposition 5, it follows that (x generates a 28-cover of (ax, p). Accordingly, [a)(2)) must be greater-equal the minimum number of points required to construct such cover. Under the I| norm, the e-covering number of a ball
D
Bxx,
II [max(aa (aa - p. 0), min(2a + p. 1)]
(20)
given by
(B = min (I p,1) (0, 2d p)
(21)
28
This number is minimized when B(:,)) is placed in a corner, such as B(0, -00, pl. Choosing
((e) 4
p(s)
n(E) = max 1,
(22)
4s
therefore ensures that 17(s) lower bounds the cardinality of every B,(.). Note that there are two factors of two at play here: one accounts for the fact that Bp(-) is only guaranteed to provide 28-cover of B(, p), and the other accounts for the fact that the corner balls are up to 2D times smaller than other balls with the same radius.
Turning our attention to the choice of function p(E). some desiderata come into focus. First, we require p(e) 2 E so that every Bp(-) is nonempty. Second, we desire lim p(=) = 0 because the resulting posterior variance bound will increase monotonically in p(E). Lastly, we want the ratio of p(E) to e to diverge to infinity as approaches zero from above so that lim n1E) co. Based on these criteria, convenient choice when X' = |0, is
p(E) =
0<a<l.
(23)
In summary, the claim follows by expressing p as a function of e and using to lower bound BB(+) with r))s) Var[f(a)) v(X) <
(ALap(E)k(zz x) -()p)) ((E) 722(00,
(24)
(k(2, + 2L4p())((e+
Proposition 7. For any choice of constants a > 0, b 0, c
lr log + be bbe///dde s / a- log b/o
(25)
Proof. This proof ammends Grünneäälder et al. [18, Appendix AI. Let (1 v/cb-11a so that
1. /log(1 bs 1/--1//de < l" Vlog(EV/be-V/o))
(26)
16

---

Next, define auxiliary functions
f(u) Vlog(u
g
(27)
such that [(((())) = / (ogg("vob and use them to integrate by substitution as
J Joog("/bbeti Vo)ds =6"
[o(c)
Vlog (ogg(uV/odde g6 rg(c) Va 3
log(u)du.
(28)
The Cauchy-Schwarr inequality now gives
g(()
(%.00) du)
(ate)
f/2
(-/o
19(c)
1/2
log(u)duu S
log(u)du
c
log
(29)
{ba
Eba
Hence, the claim follows
be Vo)e 1. beb S sov
+ log(Ebec
/ a + log + be Vo).
(30)
Remark 8. For comparison with Grünewääler al. [18], if 2c then Proposition gives
< 5= (1 < V
1+ log(Eb"c-1)
1 + log
log e
cV
(31)
which matches their reported result. Lemma 9. Ler f ~ GP((,, k:) be a Gaussian process with an Lx-Lipschir continuous covariance
function i X² >> R on X r) having maximum variance o² maX k(xx Then,
sup f(z) L
s 12 /20 Dlog(1 + ALgro-2) 2).
(32)
Proof. This proof paraphrases parts of Grünewälder et al. [18, Section 4.3).
Massart [30, Theorem 3.18] proved that the expected supremum of is upper bounded by
< 12 / Vlog N(X, N(K,d,,))e
E
sup f(x) x
(33)
where N(X' d2, E) is defined as the e-packing number-ia. -.c. the largest number of points that be "packed" inside of X' without any two points being within e of one another-under the canonical pseudo-metric
dy (xxxx)) [[(((x) (fe0))f(((')) f /k(x
2k(x x') k(æ', x')).,""..
(34)
We may use (33) by upper bounding the right-hand side with a known quantity. We will bound the e-packing number N (X' 5), translate this bound from the de pseudo-metric the infinity norm, and then integrate the result.
The first step follows immediately from the fact that the E-packing number is smaller than the ş- covering cumber-ddefined as the minimum number of balls B(, 5) required to cover X. The second accomplished by using Lipschitz continuity of & to show that the squared useudo-mettie d -ip-siicht for all w, x' E X.
(x xt [k x)) ((x,aa)) [k<('' x²) k(w', xx]] < 2T. x' alooo.
(35)
follows that, for any set X C X.
min | x' 11 C x'eX
max min du (z,, x') S V2LAC. x'eX
(36)
While de has most of the properties of proper metric. (x. x') 0 need not always imply w' [2].
17

---

An e//sL: = cover under the infinity norm therefore guarantees an f/2-cover under dg. The former may be constructed from grid of uniformly spaced points with elements at intervals of 6 2/ALL. This grid will consist of [ points assuming X' [0, meaning that
de =) (1 4L)rE
(37)
To complete the proof, use Proposition 7 with a 7.4 4hut, and c a to show that
E sup f(x) ØE
s 12vD
Vlog(1 4Lure d)de= I 120 2D + Dl + 4Lyro 3). (38) /
Proposition 1. Under assumptions Al-A3 for all regret bounds > 0 and risk tolerances > 0,
there almost surely exists T E 1% so that, each time 2 T, every 8, E arg = My (x) satisfies
V (x; E) = (s, S <) 2 1 1- 6.
(8)
Proof. Consider the centered process
(:(+) = [f((-) mx(+)] [fc(#t) [=)(8))]
(39)
with covariance
(æ. x') (x, x²) (x 8x) (B, x') - kis (8c, 8t).
(40)
The term (s;) (-) is nonnegative by construction such that
9t sup (x) 2 ft fe()))
fr = sup f((
(41)
=x
and, therefore,
P( 2 6) 2 P( fe()))
(42)
We would now like to use the Borell-TIS inequality [8. 46] to show that: if Elgi), then
1 c [
P 2 c) & exp
(43)
2
2
where or = maXxex / / x) and 20, appears in the denominator (rather than στ) because max C x) S 4a7. Since (43) an increasing, continuous function of both or 2 and O S B(gi) < the claim will hold if these quantities vanish as the (global) fill distance h4 = max minisigel
xx llo goes to zero.
The former result is an immediate consequence of Lemma 6. Regarding the latter, fe(st) - ((( is a centered random variable. It follows by linearity of expectation that
E(g,) E sup fi(x) - pe(c))
(44)
L
Next, denote the canonical pseudo-metric at time t by
de, (z, x²) = [[(f((=) - f((z')) 1/2 = /ks (xc x)- - -2k (2,("x"')) x²) + ke (x))
(45)
This meeudo-metric is non-increasing in l. To see this, let = k(#++1, x) k( x') and write d (x, x²2² kzt1 (x) .)) 22 (Iz, x²) + ket i (a',a')
kx x) 2k, (x, x') + Ky (æ', x²) 3² (1,(1111,21111 + +
(46)
du, (²
20
As increases, points therefore become closer together under the de, pseudo-metric. For this reason, e)
the posterior e-packing number N N(X, da,, ) is less-equal to the prior e-packing number N(X, NX,d,,, e). By Lemma 9, we now have
E(g.)
Vlog N( dk, E)de
Vlog N(X, (x, E)de
(47)
00
< 1200//2 2D D Doog (1 + ALxo, 2).
18

---

From here, note that (47) is an increasing, continuous function of o; that vanishes d, + oc. By Lemma the same is true o, as function hT. As result, (43) becomes arbitrarily small as hy - 0 and there exists constant h. > such that this upper bound is less-equal to å whenever
h4 h., Finally, since (xx) is almost surely dense in X, there almost surely exists a time No such that
t 2 T = h4 S h = P(g > >) = = P(ft - f((s)) > <) 6.
(48)
Corollary 10. Suppose assumptions AI-A3 hold and that there exists a constant é' > 0 so that
lim 10000
max un (x( - pe(st) s
(49)
with probability one, where 8; E arg mag (2( Then, for every e e' and (0, there almost surely exists a time T E N such that, for all t 2 T.
sup fe(a:) fe())) S 2 21-5. LEX
(50)
Proof. Per (49), there almost surely exists an S E such that 5 = max (4(2))
(x(8:) S é'. Proposition therefore implies there almost surely exists a T 2 S so that
12 T
= [P[ f((s,) 2 c s 6,
(51)
which completes the proof.
The assumption that the posterior mean approaches its maximum on (æx) protects against adversarial cases where- no matter how densely we observe f f-there is always an x E X, so that fe (x) exceeds μe (8;) by at least Note that (49) becomes necessary condition when å < 1 Nevertheless, unclear how to ensure this condition without making stronger assumptions for f and (x²). One can A2 and the Cauchy-Sehwarz inequality to show that the posterior mean is Lipschitz continuous [27]; but, its Lipschitz constant may continue to grow as t - oc, so (49) may not hold.
C Experiment details
Experiments were run using combination of GPFlow [31] and Trieste [36]. Runtimes reported in Figure were measured on an Apple M1 Pro Chip using an off-the-shelf build of TensorFlow [1].
C.1 Model specification
We employed Gaussian process priors f ~ GP k) with constant mean functions μu-) = c and Matém-552 covariance functions equipped with ARD lengthscales.
True When optimizing functions drawn from GP priors, we the prior mean to zero and used unit variance kernels with lengthscales 4, 1 VDD DD. Noise variances are reported alongside results.
MAP When optimizing black-box functions, we employed broad and uninformative hyperpriors. Let [x); [a,, by] be the range of the i-th design variable, qt [0, 1] IR be the empirical quantile function of y at time t, and v Var yt-1] be the empirical variance of observations Our hyperpriors are then as follows:
V1-1 =
Name
Distribution
Parameters
Constant Mean
Uniform (a, b)
(0.05))
b qu (0.95)
Log Kernel Variance
Uniform (a, b)
a = log(10 mn)
log (10g;)
Log Noise Variance
Uniform/ (a, b)
= log(10 9v2)
b = log(10rr)
i-th Lengthscale
Log)ormal(u.o)
J (b: 0:)
1
Note that directly parameterize certain hyperparamters in log-space and that, e.g., log(0) Uniform(q, 6) is not the same 0 ~ LogUniformme"
19

---

C.2 Link function
When modeling classification rates for MNIST and Adult, we used logit (i.e. inverse sigmoid) link function,
g(v) = -log y/
(z) = 1 1
(52)
in order so that -0 o X 10. When evaluating stopping rules, we handled this link functions by pulling draws of, e.g., fi(x) backward through g and using te resulting values to estimate expectations and probabilities. This approach was used for all but ACB [29], where we instead computed g - UCB, and
C.3 Acquisition function
In our experiments, we defined the set of feasible solutions at time & E N as the set of previously evaluated points X,, Under these circumstances, one can show that the optimal one-step policy is given by an "in-sample" version of the Knowledge Gradient strategy [34, 15]. Let
2))
Re x))
Pr+ (520, -+(+) + V (x, a)) +
---((;=== o.(.) ka a.) + +72
(53)
be the posterior mean and variance of f at time (++ if we observe yt+1 = pe(()) + 2 (x1, xx)
+
where z (0, 1). Further, at times and I define
v (x) = Bi(g o fi)(z) = Big (E)]
E (~N(M((z),o(()))
(54)
as the corresponding expected value when accounting for a link function. If no link function is given, then (-) = (+))). Then, the aforementioned acquisition function is given by
(s) E. (X U {=):,,)) :)]
max max; (X,)
2 10.
(55)
ISKG is identical to the Expected Improvement function when y² = 0 [39], but avoids pathologies (such as re-evaluating previously observed points) when 72 0.
In practice, we estimated (55) with Houss-Hermite quadrature and maximized it using multi- start gradient ascent [50, 5]. Likewise, we either evaluated (54) analytically or via quadrature. Starting positions we obtained by running CMA-ES [19] several times to partial convergence. The best point from each was then combined with large number of random points and the top 16 points were fine-tuned using L-BFGS-B [10].
C.4 Convolutional neural networks
Name
Low
High
When training convolutional neural networks (CNNs) on MNIST [14], we used a simple ar- chitecture consisting of two convolutional layers with x filters and ReLU activation functions [3] followed by max pooling layers with pool-
Num. filters
64
Num. epochs
25
Log learning rate
log (og(10))
0
Dropout rate
size of 2. The output of the final pooling layer was flattened and subjected to dropout before being passed to dense classification layer consisting of ten neurons. Each model was trained using Adam [24], with batches of size 64. The search space for this problem depicted on the right. Integer valued parameters were handled by rounding to the nearest value. To obtain reliable estimate of the minimum achievable misclassification rate, the same random seed was used for each training run.
C.5 XGBoost classifiers
Name
Low
High
We used an off-the-shelf implementation of XG- Boost [12] for the the adult income classifica- tion problem [7]. The search space was three- dimensional and is shown on the right. Integer valued parameters were handled by rounding to the nearest value. To obtain reliable estimate of the minimum achievable misclassification rate, the same random seed was used to when generating train-test splits and for each training run.
Max. tree depth
1
10
Log num. estimators
0
log(10")
Log learning rate
log (10(10))
20

---

D Extended results
D.1 Results without adjusted cutoff' values
Problem
D
Oracle
Budget
Acq
ACB
AES
PRB
GP 10-6
2
10 (100)
17 (96)
(100)
12 (89)
(9()))
17 (97)
GP 10-2
2
128
11 (100)
22 (96)
78 (100)
82 (100)
18 (91)
23 (99)
GP 10-6
4
128
27 (100)
64 (95)
90 (100)
23 (66)
28 (74)
64 (99)
GP 10-2
4
256
(100)
94 (95)
106 (98)
256 (100)
36 (65)
86 (96)
GP 10
6
256
40 (99)
124 (95)
142 (98)
31 (50)
46 (65)
134 (98)
GP 10-2
6
512
65 (100)
227 (96)
181 (96)
512 (100)
(34)
235 (100)
GP 10-6
4
128
35 (100)
(95)
92 (100)
18 (30)
(41)
61 (88)
GP 10-2
4
256
51 (100)
157 (95)
128 (97)
224 (80)
27 (22)
100 (92)
Branin
2
128
19 (100)
25 (95)
64 (100)
31 (99)
32 (100)
33 (99)
Hartmann
3
64
14 (100)
22 (96)
26 (100)
15 (83)
(84)
19 (100)
Hartmann
6
64
36 (67)
256 (67)
40 (67)
26 (46)
(56)
40 (64)
Rosenbrock
4
96
34 (100)
46 (95)
95 (100)
68 (99)
7100)
84 (100)
CNN 4
256
5 (100)
(96)
64 (100)
(92)
19
17 (100)
XGBoost
3
128
4 (100)
(97)
128 (100)
16 (97)
19 (99)
28 (99)
Table 2: Same Table 1, but where is used the cutoff value for ACB and AES.
D.2 Detailed results
This section provides an in-depth breakdown of experiments presented in the body. Results for each problem are presented in the order they appeared Table 1.
In each of the following table, we report statistics for each of the following metrics:
Succeeded: whether or not an e-optimal point was returned.
2. Terminated: whether or the stopping rule kicked in prior reaching upper limit T.
3. Stopping Time: the number of function evaluations requested.
4. Regret: latent values sup I [xx) f(s:) where E arg max 14 (z) is maximizer of the posterior mean time of stopping: reported in logio scale.
5. Excess Regret: latent values supzex f(x) fs:) + e for runs where regrets exceeded reported in log10 scale.
For the final three metries, medians and interquartile ranges are shown alongside the mean. Similar to the preceding section, results for ACB and AES are reported using the cutoff values to give better picture of how these methods perform the absence of post-hoe calibration.
21

---

Metric
Stat.
Oracle!
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.96
1.00
0.89
0.94
0.97
mean
1.00
1.00
1.00
1.00
1.00
1.00
mean
10.52
17.00
30.14
13.02
15.01
17.81
25%
8.00
17.00
24.00
10.00
12.00
14.00
Stopping Time
50%
9.00
17.00
28.50
12.00
14.00
17.00
75%
12.00
17.00
36.00
15.00
17.00
21.00
mean
-5.71
-3.59
4.78
-2.49
-3.07
-3.47
25%
-6.07
-4.33
-4999
-2.69
-3,47
-3.92
Regret
50%
-5.36
-3.20
4436
-2.04
-2.57
-2.99
75%
-4.82
-2.30
-4.00
-1.44
-2.00
-2.36
mean
-1.26
-0.69
-0.93
-1.15
Excess Regret 25%
-132
-1.00
-1.10
-1.30
50%
-0.98
-0.86
-0.98
-1.03
75%
-0.92
-0.21
-0.87
-0.94
Table 4: Results on GP in D = dimensions with noise variance 7,2 10-6.
Metric
Stat.
Oracle
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.96
1.00
1.00
0.91
0.99
mean
1.00
1.00
0.76
0.94
1.00
1.00
mean
10.35
22.00
77.62
84.80
18.36
27.06
25%
8.00
22.00
43.75
70.00
14.75
17.00
Stopping Time
50%
10.00
22.00
78.50
82.00
18.00
23.00
75%
12.00
22.00
126.25
99.00
21.00
32.00
mean
-4.48
-2.73
-3.48
-3.34
-2.51
-2.66
25%
-4.55
-2.63
-3.56
-3,61
-2.40
-2.65
Regret
50%
-3.97
-1.88
-2.88
-2.87
-1.77
-1.91
75%
-3.28
-1.46
-2.31
-2.30
-1.32
-1.59
mean
-159
-1.54
-0.11
25%
-1.84
-1.60
-0.11
Excess Regret 50%
-1.66
-1.21
-0.11
75%
-1.41
-1.02
-0.11
Table 6: Results on GP in D = 2 dimensions with noise variance 7:2 10
Metric
Stat.
Oraclet
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.95
1.00
0.66
0.74
0.99
mean
1.00
1.00
0.96
1.00
1,00
0.99
mean
28.48
64.00
86.36
25.61
30.36
63.68
25%
17.75
64.00
69.75
18.00
22.75
46.00
Stopping Time
50%
26.00
64.00
90.00
23.00
28.00
64.00
75%
34.00
64.00
104.00
30.25
37.00
78.00
mean
-3.86
-3.06
-3.47
-1.53
-1.89
-3.15
25%
-4.24
-3.56
-3.77
-1.98
-2.50
-3.9
Regret
50%
-3.73
-3.11
-3,41
-1.49
-1.84
-3.10
75%
-3.33
-2.67
-3.00
-0.81
-0.90
-2.70
mean
-1.32
-0.81
-0.87
-2.7
25%
-1.70
-1.26
-1.25
-2.77
Excess Regret 50%
-1.18
-0.82
-0.85
-2.67
75%
-0.62
-0.47
-0.53
-2.67
Table 8: Results on GP in D = dimensions with noise variance >
22

---

Metric
Stat.
Oracle!
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.95
0.98
1.00
0.65
0.96
mean
1.00
1.00
1.00
0.39
1.00
1.00
mean
35,48
94.00
111.38
235.76
38.16
90.32
25%
19.00
94.00
87.75
223.75
26.00
67.00
Stopping Time
50%
28.50
94.00
106.50
256.00
36.00
86.50
75%
42.00
94.00
138.25
256.00
46.00
113.25
mean
-2.62
-2.05
-2.09
-2.23
-1.34
-2.11
25%
-2.66
-2.35
-2.35
-2.46
-1.66
-2.11
Regret
50%
-2.36
-1.82
-1.87
-1.99
-1.25
-1.81
75%
-1.92
-1.52
-1.62
-1.73
-0.87
-1.50
mean
-1.50
-1.72
-1.08
-1.57
Excess Regret 25%
-163
-1.91
-1.50
-1.2
50%
-1.45
-1.72
-0.95
-1.49
75%
-1300
-1.54
-0.73
-1.14
Table 10: Results on GPI in D 4 dimensions with noise variance 72 10-2.
Metric
Stat.
Oracle
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
0.99
0.95
0.98
0.50
0.65
0.98
mean
0.99
1.00
0.92
1.00
1.00
0.96
mean
55.33
124.00
150.91
35,82
48.86
141.24
25%
25.00
124.00
112.25
24.00
29.75
97.00
Stopping Time
50%
39.50
124.00
142.50
31.00
45.50
133.50
75%
77.25
124.00
191.00
41.25
63.25
178.00
mean
-3.21
-2.60
-2.85
-1.11
-1.52
-279
25%
-3.71
-3.04
-3.17
-1.66
-2.13
-3.15
Regret
50%
-3.15
-2.69
-2.78
-1.03
-1.67
-2.77
75%
-2.69
-2.26
-2.50
-0.50
-0.74
-2.47
mean
-2.74
-1.23
-2.21
-0.75
-0.83
-2.1
25%
-2.74
-1.54
-2.47
-1.04
-1.11
-2.77
Excess Regret 50%
-2.74
-1.16
-2.21
-0.65
-0.76
-2.21
75%
-2.74
-0.84
-1.94
-0.23
-0.30
-1.94
Table 12: Results on GP in D = 6 dimensions with noise variance 72 10-6
Metric
Stat.
Oraclet
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.96
0.96
1.00
0.34
1.00
mean
1.00
1.00
1.00
0.29
1.00
1.00
mean
77.15
227.00
183.30
482.08
51.67
231.73
25%
33.00
227.00
138.00
499.00
30.50
170.00
Stopping Time
50%
64.00
227.00
181.00
512.00
45.00
235.00
75%
96.50
227.00
219.00
512.00
63.50
295.00
mean
-2.16
-1.71
-1.66
-1.98
-0.80
-177
25%
-2.41
-1.97
-185
-2.25
-1.19
-2.22
Regret
50%
-2.00
-1.70
-1.62
-1.91
-0.64
-1.76
75%
-1.72
-1.37
-1.35
-1.60
-0.38
-1.53
mean
-1.51
-1.98
-0.72
25%
-173
-2.69
-0.88
Excess Regret 50%
-1.60
-2.13
-0.56
75%
-1.39
-1.42
-0.37
Table 14: Results on GP in D = 6 dimensions with noise variance 72 = 10
23

---

Metric
Stat.
Oracle!
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.95
1.00
0.30
0.41
0.88
mean
1.00
1.00
0.92
1.00
1.00
0.98
mean
38.75
79.00
87.94
19.41
24.25
62.57
25%
21.50
79.00
70.75
15.75
18.00
48.25
Stopping Time
50%
34.00
79.00
91.50
18.00
22.00
61.00
75%
50.50
79.00
102.00
22.00
29.00
75.25
mean
-3.80
-3.08
-3.41
-0.70
-1.01
-2.70
25%
-4.17
-3.59
-3.70
-1.25
-1.79
-3.27
Regret
50%
-3.66
-3.13
-3.27
-0.34
-0.59
-285
75%
-3.15
-2.58
-2.55
-0.08
-0.17
-2.24
mean
-1.34
-0.37
-0.43
-0.87
Excess Regret 25%
-1770
-0.53
-0.59
-1.41
50%
-1.47
-0.25
-0.26
-0.66
75%
-0.88
-0.04
-0.07
-0.49
Table 16: Results on GP in D = dimensions with noise variance 72 = 10
Metric
Stat.
Oracle
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.95
0.97
0.80
0.22
0.92
mean
1.00
1.00
0.99
0.60
1.00
0.99
mean
58.53
157.00
130.53
179.00
28.60
100.40
25%
29.75
157.00
99.50
122.25
20.00
73.75
Stopping Time
50%
50.00
157.00
128.50
224.00
27.00
100.50
75%
74.75
157.00
154.50
256.00
35.00
129.50
mean
-2.59
-2.03
-2.05
-1.78
-0.52
-1.82
25%
-2.67
-2.24
-2.66
-2.29
-0.90
-207
Regret
50%
-2.32
-1.79
-1.79
-1.76
-0.33
-1.69
75%
-1.93
-1.51
-1.50
-1.20
-0.09
-1.39
mean
-1.65
-2.09
-0.48
-0.45
-1.22
25%
-283
-2.40
-0.84
-0.74
-1.78
Excess Regret 50%
-1.39
-1.76
-0.31
-0.27
-1.55
75%
-0.63
-1.62
-0.01
-0.06
-1.31
Table 18: Results on GP in D = dimensions with noise variance 722 = 10-2
Metric
Stat.
Oracle
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.95
1.00
0.99
1.00
0.99
mean
1.00
1.00
0.00
1.00
1.00
1.00
mean
17.40
25,00
64.00
29.39
31.27
32.17
25%
13.00
25.00
64.00
27.00
28.00
31.00
Stopping Time
50%
18.00
25.00
64.00
31.00
32.00
33.00
75%
21.25
25.00
64.00
32.00
34.00
35.00
mean
-6.27
-2.14
-5.93
-2.79
-3.00
-3.10
25%
-6.41
-2.79
-6.23
-3,08
-3.22
-3.44
Regret
50%
-6.34
-1.97
-5.99
-2.75
-2.95
-3.07
75%
-6.17
-1.45
-5.69
-2.36
-2.61
-2.72
mean
-1.49
0.16
0.16
25%
-1.22
0.16
0.16
Excess Regret 50%
-1.54
0.16
0.16
75%
-1.15
0.16
0.16
Table 20: Results on Branin in 2 dimensions.
24

---

Metric
Stat.
Oracle!
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.96
1.00
0.83
0.84
1.00
mean
1.00
1.00
1.00
1.00
1.00
1.00
mean
13.89
22.00
29.00
15.06
16.93
21.34
25%
11.00
22.00
24.00
14.00
16.00
17.00
Stopping Time
50%
13.00
22.00
26.00
15.00
17.00
19.00
75%
15.25
22.00
30.00
16.00
18.00
21.00
mean
-6.39
-3.59
4.71
-1.78
-2.33
-3.39
25%
-6.66
-4.99
-5.06
-2.20
-3.32
-3.81
Regret
50%
-6.64
-3.81
4..3
-1.98
-2.77
-3,41
75%
-6.58
-3.32
-4.33
-1.61
-2.38
-2.90
mean
-0.61
-0.26
-0.08
25%
-0.80
-0.17
-0.17
Excess Regret 50%
-0.37
-0.17
-0.17
75%
-0.18
-0.17
-0.17
Table 22: Results on Hartmann in D = 3 dimensions.
Metric
Stat.
Oraclet
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
0.67
0.67
0.67
0.46
0.56
0.64
mean
0.67
0.00
1.00
1.00
1.00
1.00
mean
104.85
256.00
41.30
23.15
29.43
40.52
25%
25.75
256.00
36.75
18.00
27.00
37.00
Stopping Time
50%
35.00
256.00
39.50
26.00
30.00
40.00
75%
256.00
256.00
42.00
31.00
35.00
43.00
mean
-4.12
-4.12
-2.44
-0.91
-1.56
-2.30
25%
-5.70
-5.70
-3.31
-1.75
-2.48
-3.29
Regret
50%
-5.69
-5.69
-2.88
-0.85
-1.98
-2.82
75%
-0.92
-0.92
-0.92
0.03
-0.84
-0.92
mean
-1.72
-1.72
-1.70
-0.36
-0.76
-.50
25%
-1.72
-1.72
-1.71
-1.09
-1.52
-1.11
Excess Regret 50%
-1.72
-1.72
-1.71
-0.59
-1.13
-1.70
75%
-1.72
-1.72
-1.69
0.47
0.42
-1.67
Table 24: Results on Hartmann in 6 dimensions.
Metric
Stat.
Oracle
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.95
1.00
0.99
1.00
1.00
mean
1.00
1.00
1.00
1.00
1.00
1.00
mean
32.78
46.00
95.28
67.05
71.66
84.17
25%
26.00
46.00
92.00
66.00
69.00
81.00
Stopping Time
50%
33.00
46.00
95.00
68.00
71.00
84.00
75%
41.00
46.00
99.00
71.00
74.00
88.00
mean
-9.00
-4.93
-9.00
-8.38
-8.85
-9.00
25%
-9.00
-5.00
-9.00
-9.00
-9.00
-9.00
Regret
50%
-9.00
4.60
-9.00
-9.00
-9.00
-9.00
75%
-9.00
-4288
-9.00
-9.00
-9.00
-9.00
mean
-5288
-3.27
25%
-5.35
-3.27
Excess Regret 50%
-5.23
-3.27
75%
44.0
-3.27
Table Results on Rosenbrock in D 4 dimensions.
25

---

Metric
Stat.
Oracle
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1.00
0.96
1.00
0.92
0.94
1.00
mean
1.00
1.00
0.00
1.00
0.98
0.96
mean
4.98
11.00
64.00
11.55
20.37
24.30
25%
2.00
11.00
64.00
6.00
11.00
10.25
Stopping Time
50%
4.00
11.00
64.00
8.00
14.00
17.00
75%
7.00
11.00
64.00
16.00
26.00
33.25
mean
-5.05
-2.89
-4.22
-2.75
-3.18
-3.47
25%
-9.00
-2.92
-3.52
-2.92
-3.15
-3.28
Regret
50%
-3.52
-2.80
-3.30
-2.72
-2.96
-3.05
75%
-3.40
-2.59
-3.15
-2.55
-2.74
-2.83
mean
-2.2
-2.68
-2.87
25%
-2.39
-2.93
-3.34
Excess Regret 50%
-2.32
-2.66
-2.68
75%
-2.24
-2.42
-2.31
Table 28: Results CNN in D dimensions.
Metric
Stat.
Oraclet
Budget
Acq
ACB
AES
PRB
Succeeded Terminated
mean
1,00
0.97
1.00
0.97
0.99
0.99
mean
1.00
1.00
0.21
1.00
1.00
1.00
mean
3.74
8.00
121.73
16.90
19.57
28.51
25%
2.00
8.00
128.00
11.00
13.00
22.50
Stopping Time
50%
3,00
8.00
128.00
16.00
19.00
28.00
75%
6.00
8.00
128.00
21.00
23.75
34.50
mean
-8.52
-2.83
-3.79
-3.25
-3.34
-3.59
25%
-9.00
-2.22
-3.61
-3.21
-3.31
-3.31
Regret
50%
-9.00
-2.66
-3.31
-2.83
-2.87
-3.07
75%
-9.00
-2.48
-3.01
-2.66
-2.62
-2.83
mean
-2.06
-2.39
-2.64
-2,64
25%
-2.19
-2.69
-2.64
-2.64
Excess Regret 50%
-1.94
-2.64
-2.64
-2.64
75%
-1.86
-2.21
-2.64
-2.64
Table 30: Results on XGBoost D dimensions.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims either discussed in the body or Appendix B.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The primary limitation of the proposed that it relies on an underlying model being well-calibrated. This issue is clearly discussed at prominent locations in the text, such as the introduction and experiments section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: Assumptions are clearly stated throughout the paper (e.g., in Section 4) and detailed proof' are provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Details are provided in the text or in supplementary material and code is available online.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Code available online at http://hwb..c///.aaaaaaaarrrtttt stopping.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips. cc/
olicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/pc//pp//o wewiii/ggieeeeeooe
iinaammissss issmiissionn watoomissssooooliiiiooooo onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details provided in the text in supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: Extended results are reported in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
29

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [No].
Justification: We ran thousands experiments on mixed hardware at different points in time and did not keep track.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp::///eeuis./eeeeee stttp:://eurrpss.ccppblll/ wwtp/c/pppppeeeeeeeeeeeeeeeeeeee Dtt.ai//eeehcsuuleeelllleee
Answer: [Yes]
Justification: This question is not particular relevant to our submission, since our focus is on making existing optimization algorithms, c.g., more cost-efficient.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This question is not particular relevant our submission, since our focus is making existing optimization algorithms, e.g., more cost-efficient.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
30

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The proposed methods do not lend themselves to this type of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The content of this paper either created by the authors for herein. Borrowed material has been cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwperswith thcode cwm/com//aaaa datasetss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No assets have been released at this time.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "0iaMrcS8Bg", "reviewer": "Reviewer_5ozp", "summary": "This paper proposes estimators for Bayesian optimisation stopping rules backed by theoretical guarantees. The stopping criterion estimators are probably approximately correct (PAC) and derived from sample-based estimates of algorithm’s simple regret according to a Gaussian process model. Experiments complement the theoretical findings on benchmark problems involving synthetic-data benchmarks and hyper-parameter tuning problems.", "questions": "* In Algorithm 1, what exactly is $Z$, given the dependence of $\\Psi$ on $\\mathbf{x}$?\n* It’s not clear how gradients are applied to evaluate the regret-bound indicators, as suggested in line 110. The sampled functions are likely to be non-convex. So, even if running gradient descent from the given $\\mathbf{x}$ does not lead to a point $\\mathbf{x’}$ satisfying $f_t(\\mathbf{x’}) - f_t(\\mathbf{x}) > \\epsilon$, there’s no guarantee that elsewhere on the search space this would not be achieved.\n* What was the runtime for the algorithms in the experiments reported in Table 1? Since the PRB strategy requires multiple samples from the GP at each iteration, it seems to me that the cost of running the algorithm ramps up quite fast. So it’d be good to compare the PRB runtimes against the baselines’ to have an idea of how much more computational resources are required by attempting an early stopping strategy.\n* What was the feature map $\\boldsymbol{\\phi}$ used for the experiments?\n* What is $D$ in the definition of $\\beta_t$ in line 270?\n* Hartmann, Rosenbrock and Branin are classic synthetic test functions for optimisation algorithms. So why are they included under a section labeled “Results on real problems”? That can be somewhat misleading, as we’d usually refer to “real problems” as cases involving real data or challenging application scenarios attached to a real-world application (e.g., complex physics simulators for scientific problems).\n* Scalability limitations are not discussed. For instance, the proposed PRB estimator is based on optimisation over samples from a GP, and finding their optima should become harder and harder as the dimensionality of the space grows. Are there useful approximations that could be applied without hurting the theoretical guarantees by too much? Also, the algorithm could be adapted to work with sparse GP models, especially sparse spectrum GPs, given the feature-based approximations for sampling in Eq. 4. However, I’ve missed a discussion on how to adapt the algorithm to scenarios involving large amounts of data (e.g., batch BO).", "limitations": "Some limitations are discussed in the main text, while other issues, such as scalability, might not have been addressed, as mentioned above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The text is mostly well written.\n* The theoretical results seem rigorous and the involved analysis techniques might benefit other areas of research in BO and bandits.\n* A reasonable number of baselines and benchmarks is included in the experiments and significant improvements are shown for the proposed approach.", "weaknesses": "* Some important details of the methodology are not clear, as the description tends to be quite verbose with a lack of technical details. It is not very clear how Algorithm 1 applied within the BO loop, for example.\n* Scalability limitations are not discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback. We will address most of your points below. \n\n\n**Missing details**\n\nYour comment that important details about how the presented material is used in the context of BO has been heard. We will rework the text to ensure this content is clearly communicated. Please see our global response for further details on this topic.\n\n\n**Scalability**\n\nThis is an interesting direction for future work. We agree that works about stopping criteria would ideally address the scaling issues they may invite. At the same time, we believe to have provided first-of-their-kind results for model-based stopping of BO. Further, we have taken the time to study how many theoretical model-based stopping algorithms can be converted to robust, practical ones. You have said that these results not only seem rigorous but (potentially) beneficial to related fields.  We therefore think it fair to say this topic is beyond the scope of our work.\n\n\n**Questions**\n1. The random variable $Z$ is introduced on line 128 and its definition in the specific context of PRB is given on line (134). In writing Section 3.2, we wanted to emphasize the fact that these methods are generic. Based on the feedback we received however, it seems that this ended up being confusing.\n\n1. What you have said is correct. Please see our global response for discussion of how we optimized $f_t$.\n\n1. Runtimes are shown on the right in Figure 3. We expressed these as a function of the distance between the final estimate $\\Psi_t^n(x)$ and target level $\\lambda = 1 - \\delta_{\\text{mod}}$ because this relationship dominated the observed trends. Re your comments about scalability: the number of observations in this plot is always less-equal to 512 and this number is anti-correlated with $\\lambda$. These details aside, we should better communicate that PRB is *much* more expensive to evaluate than the competing methods. We argue this price tag is acceptable since queries are usually far more expensive than the compute cost; however, it is important that we clearly communicate this information.\n\n1. Feature maps $\\boldsymbol{\\phi}$ were constructed using a thousand random Fourier features in the manner suggested by [1].\n\n1. We will clarify that $D$, defined in Assumption A1, denotes the dimensionality of the search space.\n\n1. We categorized problems as \"real\" or \"synthetic\" depending on whether model hyperparameters we fit online to the data. We will improve this terminology in future versions.\n\n#### References\n[1] Sutherland and Sneider, 2015. “On the Error of Random Fourier Features”.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pdDcKn7gUW", "reviewer": "Reviewer_pJBb", "summary": "This paper addresses the challenge of determining when to stop a Bayesian optimization process. Traditional methods rely on exhausting a predefined budget, but this work proposes an alternative approach based on probabilistic criteria as a stopping criterion.\nKey Contributions:\nNew Stopping Criterion: The paper introduces a stopping criterion based on the probability that a solution is within a certain threshold ($\\epsilon$) of the optimal solution with high confidence (1 - $\\delta$). This criterion is more adaptive and user-friendly compared to traditional budget-based stopping rules.\nTheoretical Guarantees: The authors prove that Bayesian optimization satisfies this new stopping criterion under mild technical assumptions for Gaussian process priors.\nPractical Algorithm: This paper presents a practical algorithm for evaluating the stopping rules using Monte Carlo estimators. This algorithm is designed to be robust against estimation errors.\nThe paper provides empirical results demonstrating the effectiveness and limitations of the proposed approach.", "questions": "Assumption 3 (A3), which requires the sequence of query locations $(\\vec{x}_t)$ to be almost surely dense in the search space $\\mathcal{X}$. Is this assumption practical in the high-dimensional data ?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper introduces a new stopping criterion for Bayesian optimization based on probabilistic regret bounds, addressing the challenge of indeterminate budget allocation in black-box optimization scenarios. The criterion is formulated as $P(r(x*) \\le \\epsilon) \\ge 1 - \\delta$  where $r(x*)$ represents the regret of the best solution found, $\\epsilon$ is the acceptable regret threshold, and $\\delta$ is the confidence parameter. This probabilistic approach provides a more adaptive and theoretically grounded alternative to traditional fixed-budget stopping rules, allowing the optimization process to terminate when a solution is found that is likely to be within $\\epsilon$ of the global optimum with high confidence $1-\\delta$", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are pleased to hear that you enjoyed our submission. \n\n\n**Is A3 practical for high-dimensional problems?**\n\nWe give a detailed reply below. The short answer is that what matters in practice is how smooth $f$ is relative to the size of $\\mathcal{X}$.\n\n\nFor simplicity, assume $f \\sim \\mathcal{GP}(0, k)$ where $k$ is a stationary kernel with unit variance. In discussing dimensionality, we are really talking distances. We used the infinity norm to measure distance in the main text for convenience. From a theoretical perspective, the particular choice of norm isn't so important here: $\\mathcal{X}$ is assumed finite-dimensional, so all norms are equivalent. What ultimately matters is the distance induced by $k$. This is easy to see in the sense that even if $||x - x'||$ is very large, the distance passed to the kernel may be very small (i.e., $f$ may be very smooth). Even this distance can be misleading however; consider a periodic kernel. \n\nIt turns out that the right distance for characterizing the supremum is the canonical pseudo-metric (29) \n\n$\nd_k(x, x') = \\sqrt{k(x, x) - 2 k(x, x') + k(x' , x')}.\n$\n\nTo build intuition for why this is the appropriate metric, notice that $d_k(x, x')$ goes from zero to four as the correlation between $f(x)$ and $f(x')$ goes from positive to negative one. Denoting this correlation by $\\rho$,  one can show that\n\n$\n\\mathbb{E}\\left[\\max(f(x), f(x'))\\right] = \\sqrt{\\frac{1 - \\rho}{\\pi}},\n$\n\nwhich exhibits the same trend. Further details can be found in Appendix A.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ph8NzV11RG", "reviewer": "Reviewer_GLW6", "summary": "This paper develops a $(\\varepsilon,\\delta)$ stopping criterion for Bayesian optimization algorithms.  The authors propose a probabilistic regret bound estimator, which is constructed through sampling the function and find the maximum points of these samples,  to decide when to stop the algorithm. They also give the theoretical analysis of this estimator and show their results in the numerical experiments.", "questions": "* I didn't understand the right figure in Fig 2. Do you mean that you change the posterior distribution for orange, green and red line through conditioning on the partial information of real optima?\n\n* How to decide the oracle budget in the experiment section? As the budget is chosen by an oracle, why sometimes the budget may be worse than other methods?", "limitations": "They adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper is well written and well organized.\n* The problem formulation is clear.\n* The algorithms are supported by some theoretical results (though I think the assumptions have some problem).", "weaknesses": "My concern is about the Assumption A.3, which is not a common assumption in BO field. This assumption, as you mentioned, is true for a generalized EI in [1]. However, it is still unknown if this assumption is held in a noisy case, and I am also not agree with that the Knowledge gradient is in the form of generalized EI defined in [1]. I think the UCB algorithm with a fix coefficient will never satisfiy this assumption. As a result, the theoretical analysis is restricitive and only suitable for several specific acquisition functions.\n\n\n\n\n[1] Convergence properties of the expected improvement algorithm with fixed mean and covariance functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We will respond to each of your comments below. \n\n\n**Assumption A3**\n\nIn order to make high-probability statements about $f$'s global properties, we must eventually learn enough about the function. We chose to enforce this condition by assuming that $(x_t)$ is dense in $\\mathcal{X}$ because it is simple to understand and popular strategies exhibit this behavior (in the noise-free setting). This condition can also be guaranteed by using an $\\epsilon$-greedy strategy. We argue this practice is desirable because it helps protect against model mismatch and ensures asymptotic performance no worse than that of random search.\n\nThis being a paper on Bayesian optimization however, that conclusion is somewhat underwhelming. As you’ve said, the set of acquisition functions (AFs) that satisfy A3 is an open question (even when $f$ is noise-free). Consider the following analysis.\n\nLet $s_t \\in \\arg\\max_{x \\in \\mathcal{X}} \\mu_t(x)$ and $x_t \\in \\arg\\max_{x \\in \\mathcal{X}} \\alpha_t(x)$, where $\\alpha_t$ denotes the chosen AF. The proof strategy from [1] is then: \n1. Define $\\alpha_t$ as a non-negative, continuous function such that $\\alpha_t(x) = 0 \\iff \\sigma_t(x) = 0 \\land \\mu_t(x) - \\mu_t(s_t) \\le 0$.\n2. Show that  $\\sigma_t(x_t)$ and $\\mu_t(x_x) - \\mu_t(s_t)$ are both non-positive when $t \\to \\infty$.\n3. Show that $\\alpha_t(x_t)$ therefore vanishes as $t \\to \\infty$.\n4. Show that (3), together with the no-empty-ball property [1] and the definition of $x_t$, implies that $(x_t)$ is dense in $\\mathcal{X}$.\n\nNotice that the proof is actually simpler if $\\alpha_t(x) = 0 \\iff \\sigma_t(x) = 0$, i.e. if a query has no value if and only if it provides no information. This family of AFs not only contains KG but other common non-myopic AFs (such as variants of entropy search). We will double check this result and update the paper accordingly. Note that the statement in the paper is not quite correct anyways since assumption A2 does not guarantee the NEB property.\n\nIf you agree with this analysis, then we hope you will reconsider your position on A3. Requiring noise-free assumption is undesirable, but this topic is beyond the scope of our submission. To our knowledge, previous works have made far stronger assumptions (such as use of GP-UCB with the theoretically correct $\\beta_t$) or omitted proofs entirely.\n\np.s. We also think that UCB with fixed $\\beta_t$ will not be space filling. See Section 5 of [2].\n\n\n**Figure 2**\n\nWe will improve the related text, but your interpretation is correct. For instance, $f_t(x) | f_t(x) \\le f_t^*(x)$ in green means that we truncated prior to approximating (3), i.e. we sampled $f_t^*$ and averaged over $P(f_t^* - f_t(x) \\le \\epsilon \\mid f_t(x) \\le f_t^*)$.\n\nProperly conditioning on $f_t^*$ would require us to truncate everywhere and marginalize over random sets $\\arg\\max f$, which is intractable. To illustrate this, let $f_1 \\sim N(0, 1)$ and $f_2 \\sim N(0, 10^{-9})$ be independent and suppose you are told that $\\max(f_1, f_2) = 3$. How confident can you be that $f_1 = 3$?\n\nWe ultimately ended up sampling functions $f_t$ instead, which avoids this issue. We thought it was interesting to show the impact of different ways of communicating information about the supremum. In hindsight, it may be better to move this to appendices.\n\n\n**Oracle budgets**\n\n Oracle budgets were defined retroactively by looking at the results and choosing, for each problem, the smallest time $T$ so that $95\\%$ of runs met the regret goal (where possible). Table 1 reports medians. If 94 out of 100 runs on a hypothetical problem took 10 trials to satisfy the regret bound and the remaining 6 took 50, then the oracle budget (and hence the median) would be 50. The median stopping times of other methods might be closer to 10 however. We will include problem-specific result tables in extended results that give a more detailed breakdown of our results.\n\n#### References\n[1] Vazquez and Bect, 2010. \"Convergence properties of the expected improvement algorithm with fixed mean and covariance functions\".\n\n[2] Jones, 2001. \"A Taxonomy of Global Optimization Methods Based on Response Surfaces\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3mP8hqk36P", "reviewer": "Reviewer_cuEF", "summary": "The paper introduces a Monte-Carlo-based stopping criterion for Bayesian optimization tasks, which has been neglected in the Bayesian optimization literatures. The authors provide a generic algorithm that can be tailored to Bayesian optimization setting and establish theoretical results and demonstrate numerical performances.", "questions": "1. The regret defined in (2) is not a simple regret, and it does not accurately measure the performance of the optimization as the objective function $f$ is not used, but instead a sequence of objective functions $(f_t)_{t \\in \\mathbb{N}}$, which vary over time, is considered. Can you clarify what the regret means in this case? It seems it makes more sense to stop the BO algorithm when $f(x^*) - f(x_t) \\le \\epsilon$ with probability at least $1-\\delta$. In the later parts of the manuscript, $f_t$ seems to be a sample path, and if this is the case, algorithms like GP-TS would easily satisfy the condition, which authors refer to as probabilistic regret bound, in the early stage of the algorithm. Such a condition would be virtually non-informative. \n\n2. In line 110, the authors claim that for each draw of $f_t$, the indicator can be evaluated using gradients. Can you elaborate more on this?", "limitations": "Not applicable.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper provides many interesting theoretical tools with relevant references that could be potentially useful in establishing stopping rules and other understandings in Bayesian optimization tasks.", "weaknesses": "The paper's writing can be improved significantly. Although the paper introduces the most generic version of the algorithm as in Algorithm 1, to be actually used in the BO setting, one needs to calibrate parameters $(\\delta^t_{est})_{t\\in \\mathbb{N}}$ that are highly nontrivial. Instead of presenting algorithm 1, readers would benefit more by seeing the algorithm directly targeted to the Bayesian optimization setting. Or perhaps it would be better if authors title the paper more broadly and consider applications beyond the Bayesian optimization. Section 3.2, in particular, needs to be modified to clarify its connection to the Bayesian optimization setting. A proper description of parameter scheduling and end-to-end algorithmic description would make the paper more solid and appreciated by a wider audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our submission. We are sorry to hear that you found our presentation of the material underwhelming. Some of your feedback was similar to that of another reviewer, so please see our global response for additional details.\n\n\n**What does $f_t$ represent?**\n\nPer the Section 2, $f_t$ denotes the posterior at time $t$ and this remains the case throughout the paper. In Section 3.1, we do talk about generating sample paths, but we usually say things like \"draws of $f_t$\". The only exception we have found is on line 102 where it says \"drawing functions $f_t$” instead of \"generating function draws of $f_t$\". We will amend this line (and any others) to avoid confusion. \n\nThis also addresses your concern that algorithms like GP-TS would easily satisfy the proposed criterion. This is not the case because we use Monte Carlo methods to integrate out $f_t$ when evaluating (3).\n\n\n**$r_t(x)$ is not a simple regret**\n\nEquation (2) defines the model-based (simple) regret as $r_t(x) = f_t^* - f_t(x)$, where $f_t^* = \\sup_{x \\in \\mathcal{X}} f_t^*$. Like $f_t$, $r_t(x)$ is a random variable. It denotes our regret for taking $x$ as our solution _according to the model_. Said differently, if we believe that the true function was drawn from the prior and that observations are indeed corrupted by independent Gaussian noise with variance $\\gamma^2$, then $P(r_t(x) < \\epsilon)$ is the subjective probability that $x$ satisfies the criterion given what is known a time $t$.\n\nHence, the proposed stopping rule does exactly what you suggested: it stops when the regret is less than $\\epsilon$ with probability at least $1 - \\delta$. The only difference is that the regret in question is defined under the model because the true supremum (hence the true regret) is unknown. \n\n\n**Scheduling $\\delta_{\\text{est}}^t$**\n\nWe agree that additional details are needed here and will include them in future versions. In our experiments, we set $\\delta_{\\text{est}}^t = T^{-1}$ where $T$ was an upper bound on the number of queries (line 245). As seen in Figure 3, the number of samples requested by Algorithm 1 increased very slowly in $\\delta_{\\text{est}}$, so this upper bound can be loose (e.g. hundreds of times larger than the anticipated number of queries). As will be shown in future versions, this trend holds for different approaches to bounding estimation errors, such as Clopper-Pearson intervals and equal-tailed Bayesian credible intervals with uninformative priors.\n\nIn cases where no such upper bound is available, we recommend using an \"outer schedule\" $(\\delta_{\\text{est}}^t)$ that is similar to the \"inner schedule\" for $(n_j)$ used by Algorithm 1, which is discussed in Appendix B.1. Under this approach, the stopping criterion is only evaluated at steps $\\beta^i t_0$ for $i \\in \\mathbb{N}$, where $t_0 \\in \\mathbb{N}$ is an initial time and $\\beta > 1$ is a scheduling parameter. The choice of $\\beta$ will depend on the ratio of the costs of making a query versus the cost of evaluating the stopping rule (approaching one as the ratio goes to infinity). Relative to the convergence time $T_0$ in Proposition 1 (and $S$ in the proof of Proposition 2), this approach results in at most $\\beta$ times more queries.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
This post discusses feedback that was common to multiple reviewers. Comments raised by individual reviewers will be addressed in subsequent posts. 

As a preliminary remark, we note that reviewers seem to think that our submission makes solid contributions to theory and/or practice. The primary criticism seems to have been that important practical details are either unclear or absent. We are committed to improving our work and hope that you will consider revising your scores if you feel that we have adequately addressed your concerns.


**Presentation**

In writing this paper, we attempted to provide generic explanations for the core components of our algorithm. Based on the feedback we received, it is clear that this ended up being confusing at times and that greater emphasis should have been placed on practical details and how the pieces fit together. We lost the forest for the trees.

We will tighten up the text to ensure that the broader picture stays in focus. Section 3.2 will be reworked to revolve around BO and its notation will be brought in line with the rest of the paper. Practical details will either be clearly presented in the paper or in a suitable appendix. If possible, pseudo-code for the entire BO loop will be added.


**Using gradients to obtain regret indicators**

Reviewers 5ozp and cuEF both pointed out that the text is overly vague about how gradients are used to obtain $\mathbb{1}(r_t(x) \le \epsilon)$. Using function draws gives us access to pathwise derivatives. Throughout, we used multi-start gradient ascent to maximize each path. In detail: we evaluated each path at previously queried locations and (up to) 64 batches of 256 random points, then random gradient ascent starting from the 16 points for each path. If desired, this process can be expedited by using early stopping (line 113).

Per Reviewer 5ozp, the sampled functions will typically be non-convex; so, there is no guarantee that this process succeeds. This is mentioned on line 124, but further discussion should be added (esp. for high-dimensional problems).

Meta-review: The paper introduces a novel stopping criterion for Bayesian optimization based on probabilistic regret bounds. The core novelty is a model-based stopping rule that leverages Monte Carlo estimators to decide when to terminate the optimization process, ensuring that the solution meets a predefined regret threshold with high confidence. The theoretical justification is strong, and the empirical results demonstrate the method's potential across a variety of benchmark problems.

Despite the strengths, there are concerns regarding the practical applicability of the method, particularly when modeling assumptions do not hold perfectly. Reviewer cuEF specifically raised concerns about the method's utility in real-world settings, where the alignment between the objective function and the model might not always be guaranteed. These concerns are valid and should be addressed in future revisions to ensure the method's broader applicability.

One point of note is that the idea of using a model to determine when to stop has some precedence in BO literature (e.g., https://arxiv.org/abs/1806.07555), which also deals with using models to estimate stopping conditions while acknowledging model mismatch. This similarity is worth mentioning as it shows that the concept of model-based stopping has been explored in different contexts.

During the discussion phase, reviewers acknowledged the technical contribution of the paper, though some practical concerns remain. Given these factors, the paper is leaning towards acceptance, provided there is room for further refinement, particularly in clarifying its practical significance and addressing concerns around real-world deployment.
Decision: Accept (poster)