“Why Not Looking backward?” A Robust Two-Step Method to Automatically Terminate Bayesian Optimization
Authors: Shuang Li
Ke Li
Wei Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian Optimization
Termination Criterion
Looking Backward

Abstract: Bayesian Optimization (BO) is a powerful method for tackling expensive black-box optimization problems. As a sequential model-based optimization strategy, BO iteratively explores promising solutions until a predetermined budget, either iterations or time, is exhausted. The decision on when to terminate BO significantly influences both the quality of solutions and its computational efficiency. In this paper, we propose a simple, yet theoretically grounded, two-step method for automatically terminating BO. Our core concept is to proactively identify if the search is within a convex region by examining previously observed samples. BO is halted once the local regret within this convex region falls below a predetermined threshold. To enhance numerical stability, we propose an approximation method for calculating the termination indicator by solving a bilevel optimization problem. We conduct extensive empirical studies on diverse benchmark problems, including synthetic functions, reinforcement learning, and hyperparameter optimization. Experimental results demonstrate that our proposed method saves up to $\approx 80\%$ computational budget yet is with an order of magnitude smaller performance degradation, comparing against the other peer methods. In addition, our proposed termination method is robust in terms of the setting of its termination criterion.

"Why Not Looking backward?" A Robust Two-Step Method to Automatically Terminate Bayesian Optimization
Shuang Li
Control and Simulation Center, Harbin Institute of Technology, China. National Key Laboratory of Modeling and Simulation for Complex Systems, China. ShuangLi hit@outlook. com
Ke Li
Department of Computer Science University of Exeter, EX4 4RN, Exeter, UK. w.li@exette.arr ac.uk
Wei Li
Control and Simulation Center, Harbin Institute of Technology, China. National Key Laboratory of Modeling and Simulation for Complex Systems, China. frankChit edu. cn
Abstract
Bayesian Optimization (BO) is a powerful method for tackling expensive black- box optimization problems. As sequential model-based optimization strategy, BO iteratively explores promising solutions until a predetermined budget, either iterations time, is exhausted. The decision when terminate BO significantly influences both the quality of solutions and its computational efficiency. In this paper, we propose a simple, yet theoretically grounded, two-step method for automatically terminating BO. Our core concept is to proactively identify if the search is within convex region by examining previously observed samples. BO is halted once the local regret within this convex region falls below predetermined threshold. To enhance numerical stability, we propose an approximation method for calculating the termination indicator by solving bilevel optimization problem. We conduct extensive empirical studies on diverse benchmark problems, including synthetic functions, reinforcement learning, and hyperparameter optimization. Experimental results demonstrate that our proposed method saves up to 80% computational budget yet is with order of magnitude smaller performance degradation, comparing against the other peer methods. addition, our proposed termination method is robust in terms of the setting of its termination criterion.
Introduction
"Nature does not hurry, yet everything is accomplished." - -Lao Tzu
In this paper, we consider the black-box optimization problem (BBOP) defined as follows:
maximize f(x);
(1)
x=X
WWi Li is the corresponding author of this paper.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

-10
Ackley
0.4
1.2
Levy
0.3
0.9
0.5
0.3
10
13
16
19
0
10
13
16
19
Number of FFs
Number of OFF.R FFx
Number of FRs
and [24] on Ackley and Levy function where n 1. Results are collected from 21 independent runs of vanilla BO while the mean value of termination indicator of each termination criterion is plotted as the solid line associated with the confidence interval. Please refer to Section 3.2 for a description of these termination criteria, as well as the meaning of KPI, KEI and Kdiff-
Figure 1: Trajectories of termination criteria used in [2
28
where x (I1, (21,..., ,.,) TT decision vector (variable), Ω < R" represents the search space, and f $2 - R corresponds to the attainable set in the objective space. In real- world scenarios, function evaluations (FEs) of f(xx can be costly, giving rise to expensive BBOPs. Bayesian optimization (BO) has emerged as one of the most effective methods for addressing expensive BBOPs. BO is a sequential model-based optimization technique consisting of two iterative steps: i) employing limited expensive FEs construct a surrogate model of the physical objective function, such as Gaussian process (GP) model [35]; and ii) selecting the next point interest for costly FE by optimizing
acquisition function, e.g., probability of improvement (PI) [88) expected improvement (EI) [6], and upper confidence bound (UCB) [1], Numerous theoretical and methodological advancements have been made in BO. Interested readers can refer to comprehensive survey papers [29 and a recent textbook [13] for further information.
Nevertheless, the question of when to terminate the search process of BO remains largely underex- plored area in the literature. At present, the most prevalent termination criterion a pre-specified budget, such as the number of FEs or wall-clock time. Though intuitive, this approach neglects the search dynamics inherent to different BBOPs. result, this strategy is rigid while does not offer appropriate budget across various problem settings. If the budget
general rule for determining too small, BO may terminate prematurely, yielding a suboptimal solution. On the contrary, an excessive budget may lead to wasted computational resources. Another simple termination method involves stopping BO if the current best solution remains unchanged for a predetermined number of consecutive FEs. However, highlighted by (24), this strategy also fails to consider the observed data during the sequential model-based optimization process and relics on a pre-defined threshold.
Beyond the aforementioned 'naïve" approaches, limited number of dedicated efforts have been made to address the termination of BO. One notable method involves monitoring the progress of BO by termination indicators, such as the maximum of EI [28 [6] or PI (22). In this approach, BO terminated when the corresponding termination indicator falls below a pre-specified threshold. Very recently. Makarova al. proposed using the difference between the minimal of the lower confidence bound (LCB) and UCB as the termination indicator. As illustrated in Figure [ we observe that all criteria used in these termination approaches exhibit significant oscillation during the optimization process. This can be attributed to: i) the stochastic nature of BO itself, and it) numerical emrors arising from the non-convex optimization of acquisition functions. Furthermore, as shown in Figures [ Ta) and (b), the variation range of the same criterion can differ substantially when addressing problems with distinct fitness landscapes. These factors make determining universally applicable threshold in practice challenging, resulting in fragile and less intuitive termination criteria compared simply establishing budget. Additionally, 'myopic', as decision-making is based solely on the observations at the current step, leading to lagged termination. For instance, consider the selected samples shown in Figure 2 it difficult, if not impossible, to determine when to terminate BO until = 20. However, we Took backward to t t= 5. it becomes evident that BO is likely to converge by 10.
find that these termination criteria are
Our contributions. In light the aforementioned challenges, this paper proposes a novel termina- tion method for BO that proactively detects whether the search is located in convex region of (x() by examining previously observed samples. BO is terminated the local regret within this convex region falls below predetermined threshold. To improve numerical stability, we introduce an approx-

---

Predictive by GP
True Funetion
10
10
10
15
155
MAMM
20
20
20
20
250
20
10
10
20 20
20
(f
20)
Figure 2: Search dynamics of vanilla BO on the Ackley function (n = 1) at different time steps after the initialization. In particular, i indicates five samples collected after the initialization.
imation method for calculating the termination indicator by solving a bilevel optimization problem. Our proposed termination method is simple, yet it offers theoretical guarantees. To demonstrate its effectiveness, we compare the performance of our proposed method against four peer methods on variety of benchmark problems, encompassing synthetic functions, reinforcement learning, and hyperparameter optimization.
2
Proposed Method
This section starts with gentle tutorial of vanilla BO, Then, delineate the implementation of our proposed termination method, followed by a theoretical analysis at the end.
2.1 Vanilla Bayesian Optimization
As gradient- frree optimization method, BO comprises two major steps. The first step involves constructing a surrogate model based on GP to approximate the expensive objective function. Given set of training data D {(x', f(xx)) H Ji
GP learns a latent function g(x). such that Vx D, we have fxx = gxx + e, where e N (0, o²) is an i.i.d. Gaussian noise. For each testing input vector z Ωt the mean and variance of the target f(z") are predicted follows:
p(z²) = k* (K + o 0² (z") = "((z"22" k2 (K o?1)-'k',
where X = (x2,.... ) and (f(x*),... [(x-)) k" is the covariance vector between X and z", and is the covariance matrix of X. In this paper, we use the Matérn 5/2 kernel as covariance function measure the similarity between pair of data points. The second step consists of an infill criterion based on the optimization an acquisition function, which determines the next point of merit x to be evaluated by the actual expensive objective function:
X
argmax xef
fa0d (x).
where f=c1(x) = m(x) + (x) is the widely used UCB [1 to facilitate our theoretical analysis. Specifically, the parameter paper, controls the trade-off between exploration and exploitation. Subsequently, the next point of merit x is used update the training dataset D DU{(**) }, and BO iterates between the two aforementioned steps sequentially until a termination criterion is met. The convergence of BO can be evaluated by regret:
O, determined according the confidence level set 0.95 in this
r= f(x)) fxx*)
where x" represents the ground truth global optimum and x argmax f(x) denotes the current xED
best-found solution.
2.2 Proposed Termination Criterion
Inspired by the observations illustrated in Figure 2 propose a termination method that involves "looking back' at the last 7 > observed points in the dataset D, and storing these in temporary archive, denoted as D. The termination criterion we propose is predicated on two primary conditions.
Condition 1. The BO search process is deemed to have converged within convex hull Q if the following condition satisfied:
(*
X +x'
f(x) + f(x')
fxx')
( (T+1)
11
(5)
2
2
3

---

where 1() denotes the indicator function, returning 1 if the argument holds true and 0 otherwise. and x' are points selected randomly and distinctively from D. The convex hull, S2 = [ 22 jizr is subset of 22 where : argmin 24 and !.! argmax Zi.
xED
xED
Condition 2. Assuming Condition iis satisfied, and & denotes the most recently observed point in D, we calculate the local regret as follows:
i = (x) (x()) + w (x( + axx)),
(6)
where x argmax p(x) and x argmax o2 The BO process terminates if the following xei
xEΩ
inequality is satisfied:
S 7bb.
WO.
where is used as the termination indicator, denoted as Rib, and qhb is a predetermined threshold.
Remark The inequality within the indicator function 11 (-) equation (5) is derived from Jensen's
inequality 14), which yields convex function:
-f(ax
- - (1 -1- a))(xx)
(8)
where a E [0, 1] and x.x Ω. order to avoid the necessity of additional function evaluations when computing f(*tz ), we substitute xx*+x²)) ) into equation
Remark 2. In equation (6), we employ the widely-used L-BFGS algorithm [6] to compute & and x. To ensure numerical stability, we suggest the following strategies for initializing the algorithm and defining its termination criterion:
1. For ic, L-BFGS is initialized point randomly selected from Ω. The algorithm terminates when V p(x))l2 S In our work, we set = 10-6, 100- following Proposition 1
2. For 8, L-BFGS is initialized at the point argmax g² (x(x,, where g²(x) denotes the lower
xgû
bound of o² over Ô. The termination criterion is || V o² (x)]l2 S X, as per Proposition
Remark 3. Considering equation 7 given that -(x)-u(8) 2 0 and (xx)+ > 2, we deduce that
wa,
7h 2 2. The upper bound of qh is empirically determined, as detailed in Section 4.1
Remark 4. When the GP model is overfitting, BO tends to converge within the local region of the current best solution. In this case, both Condition and Condition 2 are easily met while BO will be terminated prematurely. On the other hand, when the model is underfitting, BO will explore Ω in a random manner. In this case, satisfying Condition 7 becomes challenging, and BO will face designed three mitigation strategies: 1) restrict
the risk of failing to be terminated. Therefore, the lengthscale to [0.05, 200] during GP training to prevent lengthscales from becoming excessively large or small; 2) normalize the inpul of training data to [0, 1}; and 3) standardize the output of the training data by centering it on the mean and scaling it by the variance.
Proposition Consider Vx E ÿt, where -p(x) represents convexfuuction If V ((x)l22 S we can establish:
m(x)
u(x) S
where x (222, & positive constant, and my denotes the strong convexity parameter of -p(x) 1
Lemma Assume the GP employs a stationary kernel k(.,)). For vx E 2 the lower bound of 22 (x) is given by:
DD] 2 (x,x')
=²(x)= - x) +
(10)
i=1
where is constant and x' for {1, |D]}.

---

Lemma 2. Given Lemmal
determining argmax (x) is equivalent to solving the following bilevel xei
optimization problem:
minimize xei
d(x, xx,)
=|x - x
=1x-xx
12 +
||x
- x211
subject to {x²,x²
argmax
||x
x²
(11)
x xDn /xx" (nD
where $2 = [2] n
li=1 C ② i!. min(a), =3) and a = max( 2.). Given that the lower-level
optimization can be addressed via exhaustive search, the analytical solution of [1 is given by x = (a) --
Ex -
Proposition 2. Leveraging Lemma
suppose minimize 0² (xx exhibits convexity in its local xei
optimal regions, the following inequality satisfied when || v o² (x)]l2 S A:
d² d² S E.
(12)
where == (2m=E) 1/2 E> O. m2 > 0 represents the strong convexity parameter of -x²(x)) in its local optimal regions 4 and 3 is constrained by 0 S B < (x) -²² (x).
2.3 Theoretical Analysis of the Proposed Termination Criterion
In this subsection, we delve into the theoretical underpinnings of the proposed termination method, focusing on the convergence of BO when the UCB is utilized as the acquisition function.
Lemma 3. As per Srinivas et al.] the optimization process in BO can be conceptualized as a sampling process from GP. Hence, for any Z, we have:
Pr (1f(x) - x(x) S (x)) > 8, where 5 > signifies the confidence level adhered to by the UCB.
(13)
Corollary 1. Based on Lemma and Condition 2 deduce that:
Pr (facg + f(x')) > 8,
(14)
where e is a numerical error when optimizing the acquisition function, X = argmax facq and xEΩ
x" represents the true global optimum. Furthermore,
0 S S x(x) + wo(x)) faca (x*);
(15)
where x. &, and X* are elements Ot, while 8 0 denotes the confidence level of the UCB.
Theorem 1. Leveraging Corollary [ when employing the termination method proposed in this paper. we deduce that the global regret bound of BO as:
Pr (r S (x)) 6,
(16)
where 8 > signifies the confidence level associated with the UCB.
Theorem 2. Building upon Condition 7 and Condition and employing the termination method proposed in this paper. we establish the local regret bound of BO as:
Pr Pr (f(x') - f(x) S f) > 5,
(17)
where x E Et x" denotes the true global optimum in át and 8 > 0 is the confidence level of the UCB
observe that if can be considered negligible when x is accurately determined by optimizing the UCB, 7 subsequently represents the upper bound of BO regret within the domain Q. Conversely, if cannot be disregarded, is posited as the upper bound of BO regret within the restricted domain 5
Remark 5. Drawing from Theorem 1 and Theorem
3 Experimental Settings
In this section, present the experimental setup for our empirical study, which encompasses the benchmark test problems, the peer algorithms, and the performance metrics used for evaluation.
5

---

3.1 Benchmark Problems
We evaluate the performance of our proposed method on three types of benchmark problems.
Synthetic functions: We consider Ackley, Levy, and Schwefel functions 33 with n E
{2, 10). The objective function f(x) is contaminated by Gaussian noise C ~~ (0.00,0.2) The maximal number of FEs is set to NFF. = 50n, with 5n allocated to initialization.
Reinforcement learning (RL): We examine two RL tasks chosen from OpenAl Gym [5] Lunar Lander with 12 and Swimmer with 16. We set NPF 50n, with 5n FFs allocated to initialization.
Hyperparameter optimization (HPO): We consider 5 HPO tasks picked up from the HPOBench [9] for tuning support vector machine (SVM) with n = 2, multi-layer per- ceptron (MIP) with 5, random forest with = 4 and XGBoost with 8. The computational budget is set the same as in the RI. tasks.
Note that, due to the use of termination criteria, it may not be necessary to exhaust the entire allocated computational budget to terminate BO. To ensure statistical significance, each experiment is independently conducted 21 times with different random seeds.
3.2 Peer Algorithms
As discussed in Section 1 the termination criterion for BO is understudied topic in the literature. In our experiments, we compare our proposed method with the following four termination methods.
Naïve method: This method ceases BO when X stays unchanged for consecutive itera- tions. Here, Kn is also the termination indicator. our experiments, we test three settings of the thresholds 7n as 150, 337 and 524, respectively.
Nguyen's method 28 In each iteration of BO, the optimization of acquisition function produces the current optimal EI. By using this the termination indicator, denoted as KgI, the Nguyen's 's method terminates BO when falls below a predetermined threshold M/s- In our experiments,
consider three settings of ME 0.01, 0.04 and 0.06, respectively.
Lorenz's s method [22]: Analogous to the Nguyen's 's method, the Lorenz's 's method replaces the El with PI the termination indicator, denoted KPT. In our experiments, the termination threshold 771 is set as 0.07, 0.2 and 0.33, respectively.
Makarova's 's method [24] : Similar to the previous two methods, the Makarova's method uses the difference between the lower and upper confidence bounds as the termination indicator, denoted as Kaiff. It terminates BO when KaH S Tjaiff, predetermined threshold and is set as 0.26, 0.62 and 0.97, respectively, in our experiments.
Our proposed method: According to Condition I and Condition 2, our proposed method terminates BO when Kig falls below predetermined threshold Mub. which is set 2.02, 2.05 and 2.08, respectively. Furthermore, we introduce a hyperparameter т to control the number of observed samples being looked backward, which LattaaA-aabbrattrr/piimaaaaaaaaa The code is available at sattps:/// http:::///tthbbb IS22025
10 in our experiments.
According the aforementioned settings. is evident that the naive method tends delay termination when a large 7), is used. On the other hand, other methods may incur a delayed termination if small threshold used. Note that the choices of the corresponding termination thresholds and the sensitivity of r are empirically examined in Sections 4.1 and 4.2
3.3 Performance Metries
In our experiments, we consider the following three performance metrics measure the effectiveness of termination method.
Empirical cumulative probability of termination indicator:
New x21
1
Teaf NFE x 21
(inSR))
(18)
(i and i (0.... NNE 21). For a given termination method, where R₂ K Nrgx21+ represents its termination indicator outlined in Section 3.2 The minimum and maximum

---

0.5
Adkay
0.4
Leay
0.4
0.4
0.4
Limar Lender
0.3
Selaaser
0.2
0.2
0.2
0.2
Kundom Fiemnt
SYM
14
1.6
18
2 22
-6
-3
0.03 0006
1008
0.32
011 0.2
033
0.1
0.5
0.5
1.5
25
Rig (a) natthdd
10) 100
08 (b)
muthhod
Rg (6) matthod
R, of (4) murthod
(6) moshod
Figure 3: Trajectories of Tear collected different benchmark problems. Here only show some results without loss of generality, while full results can be found in the supplementary document. Different subplots are (a) our proposed method, (b) Naive method, (c) Nguyen's method, (d) Lorenz's method, and (e) Makarova's method, respectively.
1.08
10
Bao
1.06
10-5
10
1.04
10
10p
1.02
10
(a) Proposed method
(b) Naive method
(c) Nguyen's method
(d) Lorenz's 's method (e) Malarova method
Figure 4: Bar charts with error bars of normalized n; for different termination methods when lede is set as 0.05, 0.1, 0.2, 0.3, 0.4, and 0.5 respectively.
values of represented by and R respectively, are determined across all 21 repeated experiments on each benchmark problem. Tear exhibits consistency across range of benchmark problems, it implies that the threshold choice for the corresponding termination method consistent and not dependent on the specific problem.
The relative computational cost:
NFE
LoOst
(19)
NFE
where Nyg is the number of FEs used by termination criterion when early stopping occurs. A lower value of Lcost indicates a higher degree of computational budget saving.
The relative performance degradation incurred by early stopping:
f(x) - f(x²) f(x) f(x)
Ieerf
(20)
where x and x are the best and the worst solutions found by BO when consuming all NFe FEs. X* signifies the best solution found when early stopping prompted by termination criterion. A smaller Iperf value indicates less performance degradation resulting from the application of the corresponding termination criterion.
Empirical Studies
In this section, our experiments" aim to investigate three aspects: i) the robustness of the termination threshold for different termination methods; ii) the trade-off between the computational budget saving versus the performance degradation; and iii) the sensitivity of T in our proposed termination method.
4.1 Robustness the Selection of Termination Threshold
In this subsection, we use the lear metric to scrutinize the threshold choice of various termination methods across different problems. As per equation (18), it is evident that Tear R; As discussed earlier in Section 3.2, a large R; can lead to premature early stopping. Consequently, we confine analysis instances where lear < 0.5. As shown in Figure 3 the trajectories of Lear for proposed method appear to converge, whereas those for the other methods diverge with different magnitudes. More specifically, as shown in Figure a). R; can be regarded transition point where Leat 2 0.95 if R 2 2. This empirical observation corroborates the theoretical result derived
Due page limits, additional ablation experiments be found in the supplementary document.

---

Aoccky 5VM
201
0.6
0.4
04
(00
0.3
f 40
0.2
0.1
25
30
100
25
30
75
100
25
50
75
100
100
N Numblex FB=
N Naubex FBx
Namber FBx
Number FE
(6)
Propures, mottod
(b) Naivo mothod
(c) Nguyen's method
(d) Loverat's method
(e)
Malarrou method
Figure 5: Trajectories of different termination indicators versus the number FEs during the BO
process on Ackley (n = 2) and HPO for SVM.
1.4
0.3
Tory B0 80
0.2
Loat
0.6
perf
1
0.1
(n)
(b)
(c)
(d)
(c)
(a)
(b)
(c)
(d)
Figure 6: Bar charts with error bars of lesst and pert obtained by using different settings of termination threshold suggested in Section 3.2 denoted as Vi. and 7/ respectively. Subplots (a) to (e) correspond to our proposed, Naive, Nguyen's, Lorenz's, and Makarova's methods respectively.
Addie
250
- Tamarr Lande
XLP
Switsner
XGBooo
9
Pigpoed rasked
Narpee's methed
150
0.3
200
0.3
Lebds ua aatibc
0.2
100
100
3
50
0
20
20
600
30
100
100 200 300 (00 600
0
50
100
150
200
250
200
100
600
800
100
20.0
300
100
Number of FEl
Number of F'Es
Number of Flls
Number of FEk
Number
FEl
Figure 7: Trajectories of the regret of BO versus the number of FEs during the BO process five selected problems. Full results can be found in the supplementary document.
in Condition 2
In contrast, there do not exist a consistent lower bound for the other termination methods. To further elucidate these observations, we plot the distributions of R; when Tear ranges from 0.05 to 0.5 in Figure 4 It is clear that the bar charts exhibit the least variation for our proposed method. For the naïve method, R; increases as Tear grows. However, the bars for the other three methods show significant fluctuations, particularly for the Nguyen's 's and the Lorenz's 's methods. These observations are further substantiated by the trajectories of the termination indicators throughout the BO process, as shown in Figure 5 We present results for the Ackley and HPO for SVM problems here, while complete results available in the supplementary document, These plots reveal that the trajectories for our proposed method converge to a certain threshold, while those for the other methods only diverge but also differ significantly on different problems. Based on this discussion, we use Lear = 0.05 as the capping point to guide the selection of the termination threshold for different termination methods: 7lb 2.1]. 7h E [57, 617). VEi [3.8 10-21 0.08), VPI E [2 x 10 10-21 .0.39], 7ai E [0.09, 1.15]. In our experiments, we apply the Latin hypercube design method 266 choose three settings listed in Section 3.2
4.2 Computational budget saving versus performance degradation
There is trade-off when early terminating BO, i.c., the performance of BO be compromised when using less FEs. In this subsection, we employ Teast and Iper! to characterize such trade-off. From the comparison results shown in Figure 6 and Table [] we can see that although the naive method achieves the best Iperf, it consumes almost all FEs. In contrast, our proposed method saves up to Rs 80% computation budget while the performance degradation is up to a order magnitude smaller than the other three termination methods. As the trajectories of the regret of BO versus the number FEs shown Figure we can see that the other three termination methods suffer from premature early stopping.

---

Table 1: The statistical comparison results of different termination methods on cosst and Aperf-
Metrics
Thresholds
Naive method
Ngayen's 's method
Lorenz's ' method
Makarova's s method
Proposed method
711
TOO)
0.1244(4.48FF-1) 0.
0. 0.7856(4.176.11
0.620663.17E-1)
Foon
1(0)
0. (E-82)).EE2))
0.1053(1447--2
0.1414(3.9E4)
0.3012(1.44E-)
0.8343(..1B-11)
0.1048(9.01E-3+
0.1043(4.20E-3)
0.1313(3.33: 33)-2)
0.2209(1.12E-I)
11
OC0)
0.0077(7.28E-2)
0.0067(7.71E-2)
0(1.56E-2)
066.81E-3)
Ipor
OC0)
0.0614(1.08E-I) I-T
0.0721(1.13E
0.0167 (6.51E-2)
0(3.35E-2)
7Js
0(0)
0.0704(1. 1-1-1)!
0.0978(1.18E-1)
0,0355 (8. (8.08E-2))
denotes the performance of our proposed method is significantly better than the other peers according to the Wilcoxon's 's rank sum test a 0.05 significunce level;
denotes the opposite case.
0.4
0.1
38 Propoeed method U8 without considering Condition
0.3
0.05
1ond
0.2
0
6
0.1
-0.05
2
6
8
10
12
14
16
18
2
8
10
12
14
16
18
Figure 8: Bar charts with error bars of Icast and peet when using T E {20] in our proposed termination method.
4.3 Parameter Sensitivity Study
In this subsection, we investigate the sensitivity our proposed termination method with respect to the parameter т. We consider various settings of r E [2i] and repeat the experiments on all benchmark problems introduced Iperf illustrated as bar charts with error bars in Figure 8 Specifically, for 7hb = 2.05, while the complete results can be found in the supplementary document. The plots show that the choice of 7 has minimal impact the results, except for cases with 2 and r = 4. This is reasonable, as the termination method may not utilize sufficient previous information when only considering few observed samples. Additionally, where the equality constraint in Condition [ i... equation (5) is relaxed. The comparison results in Figure [ reveal similar observations regarding the settings of r. However, also notice slight performance degradation and more aggressive early stopping in this case. These findings demonstrate Thelps mitigate the risk of premature early stopping.
Section 3.1 The aggregated comparison results for T and present the results
examine the scenario
that the Condition |
5 Other Partially Related Works
Despite the limited number of dedicated studies termination criteria for BO, various efforts have been made to explore early stopping strategies in different contexts.
The first category primarily focuses on detecting change points in sequential processes 34 with applications spanning various fields such as financial analysis (20). bioinformatics M7 and network traffic data analysis [23] among others. However, modeling the automatic termination of BO as change point detection (CPD) problem may present several challenges. These include: 1) the absence of suitable stopping metrics that can provide signals for CPD in the optimization process of BO; 2) the unknown and uncertain nature of signal distribution, the number of change points, and change point consistency; 3) limited data available for CPD; and 4) the necessity to further evaluate change points in order to determine an appropriate moment for terminating BO.
The second category primarily focuses on determining the statistically optimal stopping moment for generalized sequential decision- Dacksinn-making processes [4 [3]. For instance, in the classical secretary problem, termination criteria are developed to identify the maximum of an unknown distribution with minimal cost through sequential search [12). They typically establish relationships between
the costs and rewards of decision-making using cost coefficients 8 2 3 unknown observation costs [15 37 30 25
or discount factors [36]. subsequently deriving statistically optimal stopping
conditions. However, quantifying the relationship between the improvement of the fitness and the

---

cost of BO remains challenging. Furthermore, these criteria do not leverage the information provided by the surrogate model, which is crucial in BO.
The third category primarily aims to balance exploration and exploitation in the optimization process. Among them, heuristic methods, exemplified by simulated annealing, widely employed to halt the local search step of optimization algorithms [7 [21] However, such methods' hyperparameters lack interpretability and must be fine-tuned according to different problem characteristics. Additionally, McLeod et al. propose a regret-based strategy for switching between local and global optimization. Although promising for complex functions, this approach has certain limitations, including reliance on the authors' proposed regret reduction acquisition function and the potential need for additional computational resources approximate intractable integrals. Furthermore, Eriksson al. developed a trust-region regeed based BO that balances exploitation and exploration. This algorithm terminates local search when the trust region size reduced to zero. However, the termination criteria lack theoretical guarantees and are bound to the proposed trust region maintenance mechanism.
6 Conclusion
In this paper, we developed simple yet theoretically grounded two-step method for automatically terminating BO, The key insight is to proactively detect the local convex region and it terminates BO whenever the termination indicator built upon the local regret therein falls below a predetermined threshold. Our proposed termination method naturally strikes a balance between the quality of solution found by BO versus its computational efficiency. The proposed termination method is supported by robust theoretical underpinnings, and we have additionally introduced an approximation method to enhance the numerical stability by solving a bilevel optimization problem. Our extensive empirical studies, conducted across variety of benchmark problems, including synthetic functions, reinforcement learning, and hyperparameter optimization, consistently demonstrated the better performance of our proposed method compared to other state-of-the-art techniques.
Besides, experimental results also show that the termination criterion of our proposed method is robust across different problems. This property paves an additional opportunity for our proposed termination method go beyond automatically terminate BO, but broader range of applications. such as early stopping to avoid overfitting in neural network traing. change point or anomaly detection in data stream, and even new perspective strike the balance between exploitation and exploration under a bandit setting. The primary limitation of the proposed termination criterion is that it requires a predefined termination threshold, which needs be determined based on prior knowledge or empirical observations. Although recommended threshold selection range is given here, finding an optimal threshold that suits a wide range of optimization problems remains challenge.
Author Contributions
SL implemented the theoretical derivations and experiments, as well as drafted the manuscript; KL piloted the idea and re-wrote the manuscript; WL proofread the manuscript.
Acknowledgement
This work was supported in part by the UKRI Future Leaders Fellowship under Grant MR/S017062/1 and MR/X01 135/1; NSFC under Grant 62376056 and 62076056; the Royal Society under Grant IES/R2/212077: the Kan Tong Po Fellowship (KTP/R1/231017); the EPSRC under Grant 2404317; the Amazon Research Award and Alan Turing Fellowship; and the National Natural Science Founda- tion of China under Grant 62273119.
References
[1] Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In ICML'I8 I8: Proc. of the International Conference on Machine Learning, pages 462-471. PMLR. 2018.
[2] Bruno Betrò and Fabio Schoen. Sequential stopping rules for the multistart algorithm in global optimisation. Mathematical Programming, (8(3):271-288) 1987.
10

---

[3] Bruno Betro and Fabio Schoen. Optimal and sub-optimal stopping rules for the multistart algorithm in global optimization. Mathematical Programming. 57(1)4445-48, 1992.
[4] Stephen Boyd and Lieven Vandenberghe. Convex oplimization. Cambridge university press, 2004.
[5] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. Retrieved January 20, 2023, from https://gitthe com/openai gym
[6] Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing, 16(5): 190-1208, 1995.
[7] Souhil Chakar, E Lebarbier, Céline Lévy-Leduc, and Stéphane Robin. A robust approach for estimating change-points in the mean an ar(1) process. Bernoulli, 23(2):1408 1447, 2017.
[8] Herman Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3):755-77,, 1959.
[9] Katharina Eggensperger, Philipp Müller, Neeratyoy Mallik, Matthias Feurer, Rene Sass, Aaron Klein, Noor Awad, Marius Lindauer, and Frank Hutter. HPOBench: collection of reproducible multi-fidelity benchmark problems for HPO. In NeurlPS Proc. of the Thirty-fifth Conference on Nearal Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[10] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
[11] Peter Frazier. tutorial on bayesian optimization. CoRR, abs/1807.00 000.002811.200 2018.
[12] PR Freeman. The secretary problem and its extensions: A review. International Statistical Review/Revue Internationale de Statistique, pages 189-206, 1983.
[13] Roman Garnett. Bayesian Optimization. Cambridge University Press, 2023.
[14] Daniel G Goldstein, R Preston McAfee, Siddharth Suri, and James R Wright. Learning when to stop searching. Management Science, 66(3):1375-1394, 2020.
[15] Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown Sequential model-based optimization for general algorithm configuration. In LION' 11: Proc. of the Fifth International Conference on Learning and Intelligent Optimization, pages 507-523, Springer, 2011.
[16] Donald Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. J. Glob. Optim., (3(44)455-499) 1998.
[17] Scott Kirkpatrick, C Daniel Gelatt and Mario Vecchi. Optimization by simulated annealing. science, 220(4598):671
1983.
[18] H. J. Kushner. new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. J. Basic Eng., 86( 1964.
[19] P. Langley. Crafting papers on machine learning. In Pat Langley, editor, ICMI/000 Proc. of the 17th International Conference on Machine Learning, pages 1207-1216, Stanford, CA, 2000. Morgan Kaufmann.
[20] Mare Lavielle and Gilles Teyssiere. Adaptive detection of multiple change-points in asset price volatility. In Long memory in economics, pages 129-156. Springer, 2007.
[21] Daniel James Lizotte. Practical bayesian optimization. 2008.
[22] Romy Lorenz, Ricardo P Monti, Ines R Violante, Aldo A Faisal, Christoforos Anagnostopoulos, Robert Leech, and Giovanni Montana. Stopping criteria for boosting automatic experimental design using real-time fmri with Bayesian optimization, 2016.

---

[23] Alexandre Lung- Yut-Fong. Céline Lévy-Ledue, and Olivier Cappé. Distributed detec- tion/localization of change-poimts pointss high-dimensional network traffic data. Statistics and Comput- ing, 22(2):485-496 2012.
[24] Anastasia Makarova, Huibin Shen, Valerio Perrone, Aaron Klein, Jean Baptiste Faddoul, Andreas Krause, Matthias W. Seeger, and Cédric Archambeau. Automatic termination for hyper- parameter optimization. In AutoML'22. Proc. of 2022 International Conference Automated Machine Learning. volume 188 of Proceedings of Machine Learning Research, pages 7/1-21. PMLR, 2022.
[25] Gustavo Malkomes, Charles Schaff, and Roman Garnett. Bayesian optimization for automated model selection. pages 2892-2900, 2016.
[26] Michael D. McKay, Richard J. Beckman, and William J. Conover. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 42(1):55-66) 2000.
[27] Mark McLeod, Stephen Roberts, and Michael A Osborne. Optimization, fast and slow: optimally switching between local and bayesian optimization. In ICML'18: Proc. of the International Conference on Machine Learning, pages 3443-3452. PMLR, 2018.
[28] Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. In ACML' Proc. of The 9th Asian Conference Machine Learning, volume 77 of Proceedings of Machine Learning Research, pages 279-294, PMLR, 2017.
[29] Bobak Shahriari, Kevin Swersky, Ziyu Wang. Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proc. IEEE, 104(1):148-11) 2016.
[30] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In NewrlPS 12: Proc. of the Twenty-sixth Conference on Neural Information Processing Systems, pages 2951 12599, 2012.
[31] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML'I0: Proc. of the 27th International Conference on Machine Learning, pages 1015-1022. Omnipress, 2010.
[32] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information- theoretic regret bounds for gaussian process optimization in the bandit setting. IEEE Trans. Inf. Theory, (2:5553350-3666 2012.
[33] S. Surjanovic and D. Bingham. Virtual library of simulation experiments: Test functions and datasets. Retrieved January 20, 2023, from http: sfu. cal.cca/ssssss ano
[34] Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. Signal Processing, 167:107299, 2020.
[35] Christopher Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. MIT press Cambridge, MA, 2006.
[36] Tianyi Zhang, Daniel Russo, and Assaf Zeevi. Learning to stop with surprisingly few samples. In COLT"21: Proc. of the Conference on Learning Theory, pages 3887-3888. PMLR, 2021.
[37] Shlomo Zilberstein. Using anytime algorithms in intelligent systems. Al magazine, 17(3):73-88)
1996.
12


Reviews:
[{"review_id": "64ta9tHDWv", "reviewer": "Reviewer_pzre", "summary": "This paper proposes a two-step termination method for Bayesian optimization. The proposed termination method first identifies if the optimization has converged within convex region, then it would stop the optimization procedure when estimated local regret is below predefined threshold. The authors compute estimated the local regret by solving a bilevel optimization problem, and theoretically prove that the regret is upper bounded by the defined local regret. Experiment shows that the proposed methods is more rubust and sample-efficient than other termination methods.", "questions": "1. As mentioned in weakness part, is the assumption of convex variance function easy to satisfied on the benchmarks used in this paper?\n\n2. In Lemma 2,  why does the equation need to satisfy $\\hat \\Omega \\cap D = \\emptyset$ ?\n\n3. What is the error bar in result figures?", "limitations": "The author addressed the limilations. I did not see potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The idea is novel and easy to implemented to various problems.\n\n2. The experiment is comprehensive for various benchmarks and evaluation metrics.", "weaknesses": "1. During the local regret estimation, the proposed method assumes convexity of the variance function, which is hard to satisfy even if the Condition 1 is satisfied.\n\n2. The paper writing and presentation need to be improved, which I found difficult to follow. For example, in section 2, some intuition or explanation should be provided after the lemma or theorem is proposed. It would be better if the proposed method is highlighted in the result figures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W\\#1:** We do not assume the existence of convexity across the entire search space $\\Omega$. Instead, as claimed in the **Proposition 2** of our manuscript, we suppose $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{minimize}}-\\sigma^2(\\mathbf{x})$ exhibits convexity in its local optimal region(s). Note that there have been studies in the Bayesian optimization community leverage the assumption of the existence of local convexity either in the underlying black-box optimization problem (Kirschner et al., ICML'19) or the Gaussian process model (McLeod et al., ICML'18). Their rationality have been validated both theoretically and empirically in these two works. Different, this work makes an assumption of the local convexity of the variance estimated by the GP model. This is backed up by our theoretical analysis and empirical study.\n\n\n**W\\#2:** To facilitate the understanding of our theoretical analysis, we have provided remarks in our manuscript. In particular, **Remarks 1** to **3** explain the **Conditions 1** and **2**. **Remark 4** explains the **Theorems 1** and **2**. In the experimental part, since there are many trajectories generated by different peer methods. To mitigate potential confusion, each comparison method is presented in a subplot while their names are explained in the caption (Figures 3 to 6 of our manuscript). We appreciate the reviewer pointed out our presentation issues. We will further polish our manuscript in the camera-ready version.\n\n\n**Q\\#1:** We believe our local convexity assumption of the variance estimated by the GP is always met in the benchmarks used in this work. This is backed up by our validation experiments, although they were not presented in our manuscript. From our experiments, we found that the Hessian matrices of the solutions of $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{minimize}}-\\sigma^2(\\mathbf{x})$ are almost positive definite, thus supporting the convexity. For the ease of illustration, we plot two examples in **Fig. 1 of the author rebuttal PDF**. It is easy to identify local convexity of $\\sigma^2(\\mathbf{x})$, the variance estimated by the GP. This observation applies to other more complex scenarios.\n\n\n**Q\\#2:** We argue that the constraint $\\hat{\\Omega}\\cap D=\\emptyset$ is important. Based on this constraint, we can utilize the sample points of $\\mathcal{D}$ to split $\\tilde{\\Omega}$ into several non-overlapping convex hulls, i.e., $\\hat{\\Omega}$. Since the volume of $\\hat{\\Omega}$ is proportional (though not strictly linear) to the extreme value of $\\underset{\\mathbf{x} \\in \\hat{\\Omega}}{\\operatorname{maximize}}\\ \\sigma^2(\\mathbf{x})$, we can find the $\\hat{\\Omega}$ where the $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ \\underline{\\sigma}^2(\\mathbf{x})$ is located by solving the lower-level optimization problem defined in eq $(11)$. Thereafter, we can find $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ \\underline{\\sigma}^2(\\mathbf{x})$ by solving the corresponding upper-level optimization problem. On the other hand, without this constraint, the $\\hat{\\Omega}$ obtained by solving the lower-level optimization problem will contain all the sample points of $\\mathcal{D}$. For this reason, the volume of $\\hat{\\Omega}$ is no longer proportional to the extreme value of $\\underset{\\mathbf{x} \\in \\hat{\\Omega}}{\\operatorname{maximize}}\\ \\sigma^2(\\mathbf{x})$. This means that the $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ \\underline{\\sigma}^2(\\mathbf{x})$ cannot be found by solving the upper-level optimization problem.\n\n\n**Q\\#3:** The error bars are used to show the difference between the upper and lower quarterlies of **$\\frac{\\tilde{\\kappa}_i}{\\tilde{\\kappa}_i^{\\operatorname{min}}}$** in Figure 4, **$\\mathrm{I}_\\mathrm{cost}$** in the left subplot of Figure 6 and 8, and **$\\mathrm{I}_\\mathrm{perf}$** in the right subplot of Figure 6 and 8 respectively."}, {"review_id": "AGRVxltuL6", "reviewer": "Reviewer_TmDT", "summary": "The paper proposes a new termination criteria for Bayesian Optimization (BO). Early stopping is an important, and understudied problem in BO, as function evaluations tend to be expensive and therefore terminating the optimization (once a good enough solution has been reached) can save a large amount of resources.\n\nThe criteria is based on two stages: in the first stage we check whether the search process can be said to have converged to a convex hull. This is checked by testing the convexity of the black-box function in the area around the last $\\tau$ observations, where the mean of the GP is used to approximate $f$ where we do not have observations. If this condition is fulfilled, we then calculate the local regret and determine if it falls below a pre-specified threshold. \n\nThe calculation of local regret requires finding the values of $\\arg\\max_{x \\in \\tilde{\\Omega}} \\mu(x) $ and $\\arg\\max_{x \\in \\tilde{\\Omega}} \\sigma^2(x) $. This may lead to numerically unstable results if done naively, so the authors propose using L-BFGS on the convex hull with termination criteria: $|| \\nabla \\mu(x) ||_2 \\leq \\lambda $ and $|| \\sigma^2 ||_2 \\leq \\lambda $ and with specific initializations. Propositions and Lemmas 1 and 2 back-up their recommendations and show we should expect numerically stable results.\n\nThere is then a theoretical analysis of the termination criteria, showing (through Theorems 1 and 2) that if the acquisition function is properly optimized, then their calculation of local regret represents an upper bound on global regret. Otherwise, if there is numerical error when optimizing the acquisition function, then at worst their calculation of local regret will be an upper-bound on the regret restricted to the convex hull $\\tilde{\\Omega}$.\n\nExperiment results are carried out against 4 benchmarks: (a) a naive method that stops the optimization once there is no improvement in observations for a specific amount of observations, (b) Nguyen's method that considers the maximum expected improvement, (c) Lorenz's method that considers the maximum probability of improvement, and (d) Makarova's method that considers the difference between the lower and upper confidence bounds as the termination indicator. They further compare on 3 synthetic benchmarks, 2 reinforcement learning tasks, and 5 hyper-parameter tuning problems.\n\nThe metrics used to compare are: (i) the empirical cumulative probability which explores how consistent the termination criteria is across a range of tasks, (ii) the relative computational cost, which calculates which percentage of the budget is used during the optimization, and (iii) the relative performance degradation, which measures the regret sacrificed by early stopping against letting the optimization continue. \n\nThe results show the following: the proposed method is the most consistent across tasks, having the same termination threshold leads to similar performance no matter the task (something other methods fail at doing). In addition, the proposed method has the smallest performance degradation for all methods except the naive one (which mostly uses all the budget), with the proposed method allowing us to save up to 80% of the budget. Finally, an empirical study shows that the method is robust to the choice of $\\tau$, given $\\tau > 4$.", "questions": "- What is the intuition behind initializing the L-BFGS for $\\arg\\max_{x \\in \\tilde{\\Omega}} \\sigma^2(x)$ at the maximum of the lower bound?\n\n- In the proof of Lemma 2, the authors mention \"give a stationary, isotropic kernel $k(\\cdot, \\cdot)$, we have: $k^2(x, x^i) \\propto - ||x - x^i||^2_2$\". Is the \"$\\propto$\" symbol meant to represent 'proportional to', if so, why is it the case that the statement holds? It does not seem to hold for the RBF kernel. After a few readings, I think it means that the LHS if an increasing function of the RHS, but usually I have seen the symbol to mean direct linear proportionality so maybe it should be clarified.\n\n- Furthermore, how is it that equation (19) follow from equation (18) _in the appendix_, it is not clear to me (relating to the proof of Lemma 2).\n\n- Is there a more intuitive explanation of $I_{cdf}$? I found it difficult to understand what the CDF variable is. Indeed, $\\tilde{\\kappa}_i$ seems to be fully defined in L200, but it is treated as a variable in Figure 3. I am also failing to understand how the maximum and minimum values of $\\kappa$ are calculated, is it empirically from the test runs? If so, what variable can we vary? This made understanding Figures 3 and 4 difficult. Figure 5 was clear though, and backs up the claims of the authors. \n\n- The termination criteria in equation (7) seems to depend on the level of noise in the black-box function. What would be the effect of varying levels of noise? \n\n- It is my understanding (from reading the appendix) that $\\varepsilon$ in equation (14) is the numerical error when optimizing the acquisition function. Is this correct? If so, it would be good to include in the main paper. \n\n- In my experience of working with early termination BO, I sometimes found that model misspecification can lead to early termination. For example, by underestimating the EI. How would you expect model misspecification to affect your algorithm? \n\n- What is the computational overhead of calculating the stopping criteria for your method? For other methods it seems to be very cheap / free. ", "limitations": "The authors do not address any limitations. It would be good for the authors, who know the work best, to try and mention the main ones.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Originality: The proposed algorithm is novel condition very different from any I have seen before. The idea of testing for convexity and comparing local regret is excellent, and the theoretical study to justify the choice of criteria complements the paper very well. \n\nQuality: The ideas used in the paper are well justified, and explored thoroughly. Previous literature is considered, and compared against fully, and the empirical results test in a large variety of tasks, and further explore the behavior of the algorithm for different hyper-parameter settings. \n\nClarity: The paper has a difficult task of explaining many different things it is introducing, including previous work, theoretical results, and evaluation metrics. It does a great job at many of these things: it explains previous work, gives an _intuition_ of the meaning of the performance metrics, and the figures showcasing the results are excellent. Nonetheless, there are parts of the paper that lack clarity and perhaps can be improved (see later).\n\nSignificance: Given that Bayesian Optimization has seen a surge of interest in the physical sciences where experiments can be very costly, it is very important to have strong termination criteria to save costs as much as possible. The same holds true for most applications of Bayesian Optimization. As the authors suggest, this has been an understudied area, so papers like this one should be very useful to the larger scientific community.", "weaknesses": "- I found a few vital parts of the paper difficult to follow, and perhaps some improvements in the clarity of exposition could improve it. In particular it was difficult to (i) follow some of the proofs in the appendix, in particular the proofs of Theorems 1 and 2 could be expanded upon as it required me to write down a few equations manually to understand them. I was unable to understand the proof of Lemma 2. (ii) understand the intuition behind some of the choices made by the authors, and (iii) it is still unclear to me exactly why $I_{cdf}$ is constructed in such a way. I leave the details to the 'questions' section. \n\n- The naive baseline seems to be implemented _too naively_, indeed the termination thresholds in L176 initially gave me the impression of being too large, and this was confirmed by Figure 6. It would be better if a more diverse set of thresholds were investigated, including smaller values and scaling with the dimension of the problem (indeed for 2d problems a small amount of non-improvements could lead to good results, but early termination on high dimensions). Indeed, most of the budget is used in all benchmarks, showing it is a poor baseline to compare against. \n\nMinor weaknesses:\n\n- Figure 1 was initially a little confusing. Perhaps it would be a good idea to include the algorithm's explanations of section 3.2 into the introduction.\n\nWhile I list important weaknesses, which have an important impact on the score, I want to clarify that I thoroughly enjoyed the paper and I think it is great work. The low score stems from reluctance to fully recommend acceptance when I feel I do not understand important parts of the paper, but I look forward to discussing with the authors and other reviewers and having many of my doubts clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W#1:** We will amend the proofs to improve their readability in the final version. The proof of Lemma 2 is elaborated in the response to **Q#3**, while the intuition of $\\mathrm{I}_\\mathrm{cdf}$ is explained in the response to **Q#4**.\n\n**W#2:** The choice of the termination thresholds are non-trivial. They are determined according to the statistical analysis of $\\mathrm{I}_\\mathrm{cdf}$ (elaborated in the response to **Q#4**). Note that we need to consider two conflicting objectives when designing an early termination criterion, i.e, cost as few FEs as possible but also minimize regret as much as possible. In this case, a small termination threshold has a risk of premature termination for the other termination criteria. This is reflected in the experiments on the Lunar Lander in Fig. 30 of Page 23 and the Swimmer in Fig. 43 of Page 36 in the supplementary file.\n\n**Minor:** We will amend a statement in the caption of Figure 1: \"Please refer to Section 3.2 for a description of these termination criteria, as well as the meaning of $\\kappa_\\mathrm{PI}$, $\\kappa_\\mathrm{EI}$, and $\\kappa_\\mathrm{diff}$\".\n\n**Q#1:** As the results shown in Table 1 of Page 9 in the supplementary file, we find that initializing the L-BFGS at the maximum of the lower bound is helpful to improve its performance lower bound when dealing with $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ \\underline{\\sigma}^2(\\mathbf{x})$, as opposed to a random initialization.\n\n**Q#2:** Yes, $\\propto$ does not represent \"proportional to\". We will add a footnote to eq (17) to clarify this: \"$\\propto$ symbol indicates that $k^2\\left(\\mathbf{x},\\mathbf{x}^i\\right)$ will increase with $-\\left|\\mathbf{x}-\\mathbf{x}^i\\right|_2^2$\".\n\n**Q#3:** To find the exact solution of $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ \\underline{\\sigma}^2(\\mathbf{x})$, we reformulate it as a bilevel optimization problem, i.e., eq (19) in the supplementary file. The lower-level optimization problem is applied to determine the $\\hat{\\Omega}$ that contains the $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ \\underline{\\sigma}^2 (\\mathbf{x})$. Once $\\hat{\\Omega}$ is determined, we can simplify $\\underline{\\sigma}^2(\\mathbf{x})$ as $\\underline{\\sigma}^2(\\mathbf{x})=-(k^2(\\mathbf{x},\\mathbf{x}^{1})+k^2(\\mathbf{x},\\mathbf{x}^{2}))$. This is implemented by ignoring samples outside of $\\hat{\\Omega}$ as well as the effects of $k(\\mathbf{x},\\mathbf{x})$ and $c$. Since $k(\\cdot,\\cdot)$ is stationary and isotropic, the $\\underset{\\mathbf{x}\\in\\hat{\\Omega}}{\\operatorname{argmax}}\\ -(k^2(\\mathbf{x},\\mathbf{x}^{1})+k^2(\\mathbf{x}, \\mathbf{x}^{2}))$ coincides with $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{argmax}}\\ -d\\left(\\mathbf{x},\\mathbf{x}^1,\\mathbf{x}^2\\right)$, which has the analytical solution. Thus, in practice, we use $\\underset{\\mathbf{x}\\in\\hat{\\Omega}}{\\operatorname{minimize}}\\ d\\left(\\mathbf{x},\\mathbf{x}^1,\\mathbf{x}^2\\right)$ to replace $\\underset{\\mathbf{x}\\in\\tilde{\\Omega}}{\\operatorname{maximize}}\\ \\underline{\\sigma}^2(\\mathbf{x})$ as the upper-level optimization problem of eq (19). In addition, we plotted the trajectories of $\\underline{\\sigma}^2(\\mathbf{x})$ and $d\\left(\\mathbf{x},\\mathbf{x}^1,\\mathbf{x}^2\\right)$ in **Fig. 2 of the rebuttal PDF** to illustrate our rationality.\n\n**Q#4:** The motivation of $\\mathrm{I}_\\mathrm{cdf}$ (note that the variable is $\\tilde{\\kappa}_i$ instead of $\\kappa$.) is to estimate the distribution of different termination indicators with regard to $\\tilde{\\kappa}_i$ collected from different problems in our experiments. Such statistics constitute the rationality of the threshold selection provided in Section 3.2. Let us use an illustrative example **Fig. 3 of the rebuttal PDF** on Ackley with 5 FEs to help your understanding.\n\n**Q#5:** The termination criterion in eq (7) is indeed affected by the level of noise. When the noise level ($\\sigma_\\epsilon$) is extremely low, the numerical error of with $\\frac{\\tilde{r}}{\\omega \\sigma_\\epsilon}$ will be magnified. To reduce the effect of $\\sigma_\\epsilon$ and improve the numerical stability of our method during experimentation, we set a lower bound of $\\sigma_\\epsilon$ as 0.05 during the training of the GP.\n\n**Q#6:** Yes, $\\varepsilon$ is a numerical error when optimizing the acquisition function. We will clarify this in the final version.\n\n**Q#7:** We encountered a similar issue in our research. When the model is overfitting, BO tends to converge within the local region of the current best solution. In this case, both **Conditions 1** and **2** are easily met while BO will be terminated prematurely. On the other hand, when the model is underfitting, BO will explore $\\Omega$ in a random manner. In this case, satisfying **Condition 1** becomes challenging, and BO will face the risk of failing to be terminated.\n\nWe designed three mitigation strategies: 1) restrict the lengthscale to $[0.05,200]$ during GP training to prevent lengthscales from becoming excessively large or small; 2) normalize the input of training data to $[0, 1]$; and 3) standardize the output of the training data by centering it on the mean and scaling it by the variance.\n\n**Q#8:** Although we did not have a rigorous complexity analysis, we can estimate the computational costs of both our method and Makarova's method is relatively more computationally demanding than the Nguyen's and the Lorenz's methods. This is because both of us need to solve two optimization problems while the other two only need to solve one.\n\n**Limitations:** We will add a discussion of limitations in the final version. The primary limitation of the proposed termination criterion is that it requires a predefined termination threshold, which needs to be determined based on prior knowledge or empirical observations. Although a recommended threshold selection range is given here, finding an optimal threshold that suits a wide range of optimization problems remains a challenge."}, {"review_id": "XVC9xBBwk2", "reviewer": "Reviewer_ffwe", "summary": "The authors of this paper propose a new stopping criterion for Bayesian optimization. The idea is to consider the last designs visited during optimization to compute a local regret involving another optimization problem. A theoretical analysis is provided as well as an empirical comparison with some alternative termination criteria.", "questions": "- Could you give a high level description of the conditions ?\n- Could you give an interpretation of the threshold? For instance, criteria on expected improvement and probability of improvement are easy to choose. It would be more natural to select \\tilde{r} as threshold and then do the empirical comparison based on it (this is partially done in Fig. 7).\n- Similarly, in Section 3.2 the values considered seem quite arbitrary, how are they chosen?\n- What happens on multi-modal test functions such as Branin, where local minima are also global ?\n- Could you compare with McLeod et al., that also consider a convexity test?\n- On figure 2: are the hyperparameters fixed? The lengthscale is clearly too large.\n- Could you provide a pseudo-code of the computation of the stopping criterion?", "limitations": "NA", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- a theoretical analysis of the proposed criterion is given.\n- the empirical results are promising.", "weaknesses": "- stopping criteria have been proposed since the early works on BO, e.g., the discussion by Jones et al. It would be worth considering this option (optimization of EI with convergence guarantees). Another relevant work to compare with is Queipo, N. V., Pintos, S., & Nava, E. (2013). Setting targets for surrogate-based optimization. Journal of Global Optimization, 55, 857-875.\n- the description of the BO setup is vague: what is used for the acquisition function search? Are the hyperparameters optimized? Plus it is typical to increase omega in UCB and decrease lengthscales over time.\n- The selection of the threshold \\eta and the chosen metrics are not easy to interpret (see more detailed questions below).\n\n** The rebuttal and discussion have been lengthy. My main criticisms remains and can be summarized in two points:\n- the link between the general idea and the actual criterion is not clear, and it is not obvious how to use it to control the level of convergence or accuracy in practice.\n- the comparison with existing works lacks at least the works by Jones et al., to test the robustness against model mis-specification and quality of the acquisition function optimization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W#1:** Thank you for your suggestion, we will add the two papers you mentioned to Section 5 of the main paper. However, both the reviewer mentioned works are not applicable in our context. As for the Jones et al.'s work, it terminates BO when EI is less than 1% of the current optimal value. However, since EI is always positive, it cannot be applied to problems with negative objective values. As for the Queipo et al.'s method, it estimates the optimum of the underlying problem as a probability density function based on the training data. It cannot be used as a termination criterion because the data is collected in a sequential manner on-the-fly in BO.\n\n**W#2:** In this work, the hyperparameters of a Gaussian process (GP) model are obtained by solving the maximal likelihood estimation via L-BFGS, so as the optimization of the acquisition function.\n\n**W#3:** The rationality of our threshold selection is delineated in the response to your **Q#3**.\n\n**Q#1:** **Condition 1** detects whether the search process of BO already reaches a convex region of $-f(\\mathbf{x})$, by \" looking back\" $\\tau>1$ observed points; while **Condition 2** evaluates whether the local regret within this convex region falls below a predefined threshold. When both conditions are met, we consider BO cannot find better candidates any longer and thus can be terminated.\n\n**Q#2:** There are two reasons for using $\\frac{\\tilde{r}}{\\omega \\sigma_\\epsilon}$ as the termination indicator.\n\n- We found that $\\mu(\\dot{\\mathbf{x}})-\\mu(\\tilde{\\mathbf{x}})$ quickly diminishes to $0$ during the search process of BO. This leads to $\\tilde{r}$ turn out to be $\\omega(\\sigma(\\ddot{\\mathbf{x}})+\\sigma(\\tilde{\\mathbf{x}}))$. In this case, we want to mitigate the effect of $\\omega$ on $\\tilde{r}$ by using $\\frac{\\tilde{r}}{\\omega\\sigma_\\epsilon}$.\n- The noise level, quantified by $\\sigma_\\epsilon$ in this paper, varies across different problems. Since $\\sigma(\\mathbf{x})$ will increase with $\\sigma_\\epsilon$, it implies that $\\frac{\\tilde{r}}{\\omega \\sigma_\\epsilon}$ can reduce the effect of $\\sigma_\\epsilon$ on $\\sigma(\\ddot{\\mathbf{x}})$ and $\\sigma(\\tilde{\\mathbf{x}})$, thereby enhancing the adaptability of predefined threshold on different noise levels.\n\n**Q#3:** We argue that the threshold selection is not ad-hoc. It relies on the calculation of **$\\mathrm{I}_\\mathrm{cdf}$**, which is applied to estimate the distribution of different termination indicators with regard to **$\\tilde{\\kappa}_i$** collected from different problems in our experiments (details are given in Section 4.1). Such statistics constitute the rationality of the threshold selection provided in Section 3.2. To help your understanding, we provide an illustrative example on Ackley with **$N_\\mathrm{FE}=5$** in **Fig. 3 of the author rebuttal PDF**. \n\n**Q#4:** Although we did not test on Branin, Levy function considered in our experiments is similar to the reviewer mentioned Branin function. Both of them have large flat regions, within which the global optimum is located. The empirical results showed that our proposed algorithm effectively saves FEs while concurrently minimizing regret. Specifically, across the three threshold configurations, our method achieves substantial FE savings (approximately **22.3%**, **56.1%**, and **68.1%**, respectively). Please refer to Pages 22, 23, 28, 29, and 35 in the supplementary file.\n\n**Q#5:** There are three reasons that make McLeod et al.'s method cannot be compared with us.\n\n- The motivation of the convexity test is different. McLeod et al. used the convexity test as an indicator to switch between the two different acquisition functions, i.e., the predictive entropy search and the global regret reduction. Differently, we use convexity test to evaluate the local regret within local convex regions.\n\n- The mathematics of the convexity test is different. McLeod et al. investigate the positive definiteness of a Hessian matrix; while we reply on the Jensen's inequality.\n\n- Since the switching criterion, search strategy, and the acquisition function are closely tiled in the McLeod et al.'s method, the convexity test itself cannot be decoupled as a standalone criterion to serve the early termination purpose.\n\n\n**Q#6:** As stated in our response to your **W#2**, the hyperparameters of the GP model in Figure 2 are not fixed a priori. They are obtained by maximizing the marginal likelihood function. As for the lengthscale, we set it to be within $[0.05,200]$ during the GP training process to make sure it remains within reasonable limits.\n\n**Q#7:** Sorry for this confusion, the corresponding pseudo-code is given in Page 1 of the supplementary file."}]

Author rebuttal:
To facilitate the understanding of reviewers, we provide three figures in the submitted PDF file. Specifically, the Figure 1 corresponds to the response to **pzre Q\#1**,  the Figure 2 corresponds to the response to **TmDT Q\#3**, the Figure 3 corresponds to the response to **TmDT Q\#4** and **ffwe Q\#3**.

Meta-review: This paper proposes a novel termination method in Bayesian optimization. It first detects whether the search is in a convex region by examining previously observed samples and then terminates the search if the local regret falls below a predetermined threshold. The method is well motivated, justified with theories, and evaluated empirically in a variety of tasks.

There are divergent opinions among reviewer ffwe and TmDT on whether this paper requires a major revision to address the following concerns.
1. Stopping conditions have been proposed in early works such as Jones et al. 1998 and Queipo, N. V., Pintos, S., & Nava, E. (2013), and used in practice. One reviewer considers the set of alternative baselines to be too narrow.

2. How to set hyperparameters of the proposed method. One reviewer finds the stopping criterion difficult to understand and modify in practice "from a user point of view". Particularly, the predetermined thresholds such as $\tau$ and $\eta_{lb}$ lack interpretation and are therefore hard to set by a user to control the behavior. But some reviewer consider it a practical method as the suggested hyperparameter values are robust across experiments.

3. Lack of clarity. This is a concern raised by all reviewers but some reviewers consider the rebuttal provide sufficient explanation. One of the remaining concerns is around the example in Figure 2 where the hyperparameter of GP is clearly mis-estimated based on the observation. It leads to multiple confusing questions: whether the region of the global optimum can be reliably identified based on the posterior, the misspecification is not transparent in the proposed stopping criterion, etc

Despite the remaining different views among reviewers on the aforementioned points after extensive discussion, this submission proposes a valuable novel approach to the important problem and provides both theoretical and empirical justification. The concerns on clarity and interpretation of hyperparameters should be able to be addressed without a major revision. I strongly suggest the authors to take into consideration all reviewers' comments and discussion, and prepare the revision accordingly.
Decision: Accept (poster)