Automatic Termination for Hyperparameter Optimization
Authors: Anastasia Makarova
Huibin Shen
Valerio Perrone
Aaron Klein
Jean Baptiste Faddoul
Andreas Krause
Matthias Seeger
Cedric Archambeau
Venue: ICLR 2022 Submitted (2022)
Keywords: Bayesian optimization
hyperparameter optimization
automatic termination

Abstract: Bayesian optimization (BO) is a widely popular approach for the hyperparameter optimization (HPO) of machine learning algorithms. At its core, BO iteratively evaluates promising configurations until a user-defined budget, such as wall-clock time or number of iterations, is exhausted. While the final performance after tuning heavily depends on the provided budget, it is hard to pre-specify an optimal value in advance. In this work, we propose an effective and intuitive termination criterion for BO that automatically stops the procedure if it is sufficiently close to the global optima. Across an extensive range of real-world HPO problems, we show that our termination criterion achieves better test performance compared to existing baselines from the literature, such as stopping when the probability of improvement drops below a fixed threshold. We also provide evidence that these baselines are, compared to our method, highly sensitive to the choices of their own hyperparameters. Additionally, we find that overfitting might occur in the context of HPO, which is arguably an overlooked problem in the literature, and show that our termination criterion mitigates this phenomenon on both small and large datasets.

Under review as a conference paper at ICLR 2022
AUTOMATIC TERMINATION FOR HYPERPARAMETER OPTIMIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
Bayesian optimization (BO) is a widely popular approach for the hyperparameter optimization (HPO) of machine learning algorithms. At its core, BO iteratively evaluates promising configurations until a user-defined budget, such as wall-clock time or number of iterations, exhausted. While the final performance after tuning heavily depends on the provided budget, it is hard to pre-specify an optimal value in advance. In this work, we propose an effective and intuitive termination criterion for BO that automatically stops the procedure if it is sufficiently close to the global optima. Across an extensive range of real-world HPO problems, we show that termination criterion achieves better test performance compared to existing baselines from the literature, such as stopping when the probability of improvement drops below fixed threshold. We also provide evidence that these baselines are, compared to our method, highly sensitive to the choices of their own hyperparameters. Additionally. we find that overfitting might occur in the context of HPO, which is arguably an overlooked problem in the literature, and show that our termination criterion mitigates this phenomenon on both small and large datasets.
INTRODUCTION
While the performance of machine learning algorithms crucially depends on their hyperparameters, setting them correctly is typically tedious and expensive task. Hyperparameter optimization (HPO) emerged as a new sub-field in machine learning that tries to automatically determine how configure machine learning algorithm. One of the most successful strategies for HPO is Bayesian optimization (BO; Močkus 1975 Chen et al. 2018, [nook al,, 2012, Melis al., 2018) which iteratively trains probabilistic model on the evaluations of the tuned algorithm. to select the most promising next candidate point that trades-off exploration and exploitation.
In practice, the quality of the final solution found by BO heavily depends on a user defined budget, such as wall-clock time or the number of iterations, which needs to defined advanced. If this budget is too small, BO might return hyperparameters that result in poor predictive performance. If the budget is too large, compute resources will be wasted and, in some cases, it may result in will show in our experiments. Automatically stopping BO is rather under-explored topic in the literature. A simple haseline is to stop if BO has not found a better solution than the current best incumbent for some successive iterations, which is in the same vein early stopping for neural network training. Another approach is to track probability of improvement (Lorenz et al. 2016) expected improvement (Nguyen al. 2017). and stop the optimization process once falls below a given threshold. However, determining this threshold may in practice be less intuitive than setting the number of iterations or the wall-clock time. Instead of stopping BO completely.
overfitting
McL.od et al. (2018) propose to switch to local optimization when the global regret is smaller than pre-defined target. This condition can also be used to terminate BO early, but it comes with additional complexity such as identifying (convex) region for local optimization and again a predefined budget.
In this work, we propose a simple and interpretable automatic termination criterion for BO. In our criterion, we construct nigh-probability confidence bound on the regret (i.e., the difference of our current solution to the global optimum) exploiting the probabilistic model the objective. Thus, users now asked to specify desired tolerance that defines how accurate should the final solution be compared to global optimum. In addition, we propose to determine the threshold via a cross-valt valiidaan estimate of the generalization error. This choice takes into account the irreuucible discrepancy between

---

Under review as a conference paper at ICLR 2022
the actual objective and the target function optimized via BO, namely the difference between the per- formance on new data (i.e.. the population risk) and the validation error. Our extensive empirical evalu- ation on variety of HPO and NAS benchmarks suggests that our method is more robust and effective in maintaining the final solution quality than common baselines (Lorenz et al. 2016 Nguyen et al.) 2017p. We also surface overfitting effects in HPO on both small and large datasets, arguably an over- looked problem in the literature, and demonstrate that our termination criterion helps to mitigate it.
2 BACKGROUND
Bayesian optimization (BO) refers to methods of optimizing black-box objective / r + R in an iterative manner. At every step t, a learner selects an input Y E I and observes a noisy output
1/s
f(1)) t
where E, is typically assumed to be i.i.d. (sub)-Gaussiae noise with some variance (proxy) o.. The decision of the next input to evaluate depends on a probabilistic model, used to approximate the objective f. and an acquisition function, which determines the decision rule. A popular choice for the probabilistic model is a Gaussian process (GP): f GP(j, x) (Rasmussen & Williams, 2006), specified by some mean function j - + E and some kernel K x - R. As observations V1:t = [yt..... ye] for the selected inputs G2 = {?I,... [t are being collected, they are used to update the posterior belief of the model defined by the posterior mean (e(7) and variance (1) as:
(+(+) = (e( + T² - o?(7) =(7,7) - -x((7) (K. + 10
(2)
where (K))..) = x(71,7)) and ke(T)² = [M(7) ?),... (77e, 7)1² The next input to query is
determined by acquisition function that aims to trade off exploration and exploitation. Common
choices include probability of improvement (Kushner (963). entropy search (Hennig & Schuler 2012). GP upper-confidence bound (Srinivas et al. 2010). to name few.
The convergence of BO can be quantified via (simple) regret, i.e., the sub-optimality in function value:
= f(x)) - [(>",,
where 7 is the global optimizer of f and 7/- = arg gin, f(7). Specifying adequate tolerance that defines how small the regret should be to terminate BO is of high importance as determine both the quality and the cost of the solution. However, this criterion cannot be directly evaluated in practice, as the input 7* and the optimum /((²*) are not known.
Hyperparameter optimization (HPO) is widely considered application for BO. Consider su- pervised learning setting training a machine learning model (e.g., a neural network) M on some feature-respone data points D = 8xx,,)))
sampled i.i.d. from some unknown data distribution P. The model is obtained by running a training algorithm (c.g., optimizing the weights of the neural network via SGD) D, and the model returned also depends on hyperparameters " (e.g., learning rates used, batch size, etc.). We use the notation (x; D) to refer to the prediction that the model produced by M makes for an input x, when trained with hyperparameters y on data D. Given some loss function É(., -), the population risk of the model on unseen data points is given by the expected loss Ep( M,, (x, D))] The main objective of HPO is identify hyperparameters y, such that the resulting model minimizes the population risk:
f(r) = EE[[(((x (x, D))],
arg mf))(()) Er
(4)
In practice, however, the population risk cannot be evaluated since P is unknown. Thus, typically, it is estimated on a separate finite validation set Dy drawn from the same distribution P. As the result, practical HPO focuses on minimizing the empirical estimate f()) of the expected loss f()) leading to (probably different) optimizer 7/:
f(7) = [Dv
Σ X..IEDV
e(y,, M,,,, D)),
D = arg min (r).
(5)
TEr
2

---

Under review as a conference paper at ICLR 2022
At its core, BO-based HPO evaluates noisy empirical estimate f(r) for promising hyperparameters "t for some finite number of iterations and the final performance after termination heavily depends on that number. Alternatively, i.e. using an analogue the simple regret 73 for the validation loss f(1) and f(ni) min f(r): yEG.
also terminate BO when sufficiently close to the global optima,
Pt = f(x)) f(1b).
(6)
Inconsistency in the optimization objective. Importantly, the true HPO objective f()) in Eq.
and the empirical surrogate f(7) in Eq. (5) used for tuning by BO generally do not coincide. Therefore,
existing BO approaches may yield sub-optimal solutions the population risk minimization, even they succeed globally optimizing f(7).. This issue, however, is typically neglected in practical HPO. In contrast, we propose termination condition for BO motivated by the discrepancy in the objectives.
3 TERMINATION CRITERION FOR HYPERPARAMETER OPTIMIZATION
This section firstly motivates why early termination of HPO can be beneficial and then addresses the following two questions: (1) How estimate the unknown simple regret and (2) What threshold of the simple regret can be used to stop HPO.
3.1 MOTIVATION FOR THE TERMINATION CRITERION
We start by analysing the true discrepancy of interest: between the population risk f(n?) some input Yf and true optimum f(r"). We then observe that this discrepancy sums from the statistical error of the empirical BO objective f(7) as well the sub-optimality of the BO candidates (encoded in the simple regret ft). The key insight of the following proposition is that iterative reducing of to O may not bring any benefits if the statistical error dominates.
Proposition 1. Consider the expected loss f and its estimator f defined in Eqs. (4 and (5. respec- fively, and assume the statistical error the estimator bounded as flf S Et some some Est O. Let - and TD be their optimizers: 7 arg min f(r) and v/p arg min f(r). Let 7i be some candidate solution to min,er f(7) with sub-optimality in function value i; := f(rtt) f(1)). Then the gap in generalization performance f(rtt f((r) can be bounded as follows:
f(rtt) f((() < f(()) - f((x)) f(xtt - f((r)) f(y)) --((((((++))))))))))) + f(r*) f(r))
Seat
S DE + fr.
Moreover, without further restrictions on f. f. 7tt and y², the upper bound tight.
Proof:
While the second inequality is due to the definition of 7f. the others can proved as follows:
- - f(x)) s lf(()) f(xi)) max (f() f(>) = 11. flloo S Est:
TET
10 arg min f(:) - Vy e f(()) j(>) s - 5-+1((6)) - -(7))-(6") 5o. 7er
The proposition provides the discrepancy bound in terms of the statistical error e and simple regret P.. This naturally incites terminating HPO at a candidate 7f for which the simple regret ft is of the same magnitude as the statistical error ext (as further reduction in f. may not improve notably the true objective). However, neither of the quantities G,t and f known.
Below, we propose termination criterion that relies on estimates of both quantities. Firstly, we show how to use confidence bounds on f(>) to obtain high probability upper bounds on the simple regret ég (Srinvas et al. (210)); Ha et al. (2019), Secondly, we estimate the statistical error Ear in the case of cross-validation (Stone 1974 Geisser 1975) where the model performance is defined as an average over several training- validation runs. To this end, we rely on the statistical characteristics (i.e.. variance bias) of such cross dedddttioonnsseee estimator that are theoretically studied by Nadeau & Bengio (2003); Bayle et al. (2020). When cross validation is not used, one could define an intuitive threshold in advance due the usage of interpretable upper bound of simple regret.
3

---

Under review as a conference paper at ICLR 2022
Objective
Milloe (ock())
Upper bouné.
Model
mi lob(1)
righet
Noisy observations p
Stop
f(
1013
7 T
BO Reerations
(a) Key ingredients the termination criterion
(b) Example of triggering termination
Figure I: (a) Visualization of the upper bound for rt. The gap between green and orange lines is the es- timate of the upper bound for f, (b) Illustration of automated BO termination when tuning MIP on the naval dataset from IPO-Benchh (Klein & Hutter 2019) with the BORE optimizer (Tiao et al. 202
3.2 BUILDING BLOCKS OF THE TERMINATION CRITERION
Upper bound for the simple regret f. The key idea behind bounding i that, long as the GP-based surrogate model of f()) is well-calibrated, we can use to construct high-probability confidence bounds for f(-). In particular, Srinivas et al. (0110) show that as long as has bounded norm in the reproducing kernel Hilbert space (RKHS) associated with the covariance function & used in the GP, f(7) is bounded (with high probability) by lower and upper confidence bounds lcb,(7) = (1())) (1)) and neb;(7) = (e(7) + / (1)) Hereby, 8e is parameter that ensures validity of the confidence bounds (see Appendix [A.2.3 for practical discussion and ablation study).
Consequently, we can bound the unknown f(x)) and ((+bb that define the sub-optimality fz:
P. = f(a) f(r/) s min ucb,(1) - min lcb:(r) =: Fi,
ZEG.
yer
where the incquality for f()/) is due to the definition the reporting rule f(r²) = min eG. f(7) the evaluated points G. = (. 34) We illustrate the idea with example in Fig. la
Termination threshold. We showed how to control the optimization error via the (computable) regret upper bound in the above and now propose to stop the BO when F is smaller than some threshold Bo. i.e. at an iteration T FT S BO. Following Proposition 1, we suggest setting no to be of similar magnitude the statistical error ést (since smaller regret is not beneficial when est dominates). We now discuss how to estimate the statistical етгог in case of cross- validation.
Cross-validation the standard approach to compute an estimator f(r)) of the population risk. The data D is partitioned into & equal-sized sets D.,..., Db used for (a) training the model M, D). where D_, Uj D; (i.e., training on all but the i-th fold), and (b) validating (; (;) on the i-th fold of the data. These two steps are then repeated in a loop times, and then the average over validation results is computed, yielding the noisy BO evaluation y = f()) + E where the noise is due to the randomness in the training procedure or to epistemic uncertainty.
The statistical error cat of an estimate can be characterised in terms of its variance and bias where the latter can be neglected in case of cross- vross-validation (Bayle al. 2020). Though the variance of the cross-validation estimate Varf (?) E7(f()) [ is generally unknown, Nadeau & Bengio (2003) propose an estimate for it. Specifically, for the sample variance (denoted as $2,) of k-fold cross-validation, a simple post- cotrecorretton technique to estimate the variance Varf(y) is
Varf(y) ~ (++
[Di (D_)) (7).
(8)
where [D,], |D_il [D=il are the set sizes. For example, in the case of 10-fold cross-validation we have Var x 2 (7). We are ready to propose termination condition in the following.
4

---

Under review as a conference paper at ICLR 2022
Termination condition for BO. Consider the setup of Proposition where f(-) is cross -oos-validationn based estimator being iteratively minimized by BO. Let y/ f(()) + Et be a noisy evaluation the input "it and 7/- arg min Yi denote the best observed input by BO iteration t. Let Fs defined in
Eq. 7 be the simple regret bound computed at each iteration &. Let the variance Varf(nt) of the estimator f(-) be approximated according to Eq. 8). Then, BO is terminated once:
Varf(rt).
Intuitively, the termination is triggered once the maximum plausible improvement becomes less than the standard deviation of the estimate. This variance-based termination condition adapts to different algorithms or datasets and its computation comes with negligible computational cost on top of cross-validation. The pseudo code for the criterion is summarised in Appendix A..12 If vross-valiattion cannot be used or is computationally prohibitive, the user can define the right-hand side of the termination condition. In this case, the upper bound on the left-hand side still has an intuitive interpretation: the user can set the threshold based on their desired solution aceuracy. This case is demonstrated in Fig. Tb. with an example of automatic termination for tuning an MLP.
4 EXPERIMENTS
The main challenge carly stopping HPO is to find the right trade-off between reducing runtime and performance degradation. We thus study in experiments how the speed-up gained from different termination criterions affects the final test performance.
4.1 EXPERIMENTAL SETUP
We start with describing our experimental setup validation approach. To establish sensible experimental setup. we define two new metrics that account for the trade-off between resources saved and drop in final performance and provide list of reasonable baselines.
4.1.1 BASELINES
To validate proposed termination criterion we consider the following baselines:
The first baseline is näive convergence test controlled by a parameter BO is stopped once the best observed validation metric remains unchanged for i consecutive iterations. This convergence condition heavily relies on i, which needs be chosen advance. We consider values commonly used in practice, namely i {10, 30, 50).
We also compare to Lorenz et al. (2016); Nguyen et al. (2017), which terminates BO once the value of the Probability of Improvement (PI) or Expected Improvement (EI) drops below a pre-defined threshold. Both acquisition functions do not live on a well-definel scale, rendering it hard to identify sensible threshold in practice. We follow the recommendations from Nguyen et al. (2017): Lorenz et al. (2016) and consider the following values for El {10 1,009,10-0 10 } and for PI (10 10 133.. Empirically, we observe that all thresholds lead to significant speeds but, at the same time, to a severe degradation of the final solution quality. Because of space constraints, we only show the results for 10 for
El and 10- for Pl, and report the full results in Appendix A.2
4.1.2 METRICS
To measure effectiveness a termination criterion, we analyze two metrics to quantify the change in test error and the time saved. Particularly, given a BO budget T, compare the test error yes when early stopping is triggered to the test error yr. For each experiment, we compute the relative test error change RYC
yT Yes
RYC
(10)
max (yr (er)
This allows us to aggregate the results over different algorithms and datasets, as RYC E [-1, and be interpreted follows: A positive RYC represents an improvement in the test error when
5

---

Under review as a conference paper at ICLR 2022
applying early stopping, while negative RYC indicates the opposite. Similarly, let the total training time for a predefined budget T be tr and the total training time when early stopping is triggered be tes. Then the relative time change RTC is defined
lT Lea
RTC
(11)
br
A positive RTC, where RTC E J0, II. indicates reduction in total training time. While reducing training time is desirable, should be noted that this can be achieved through any simple stopping criterion (e.g., consider interrupting HPO with fixed probability after every iteration). In other words, the RTC is not meaningful metric when decoupled from the RYC and we will thus consider the in tandem in the following experiments.
4.2 HOw TO SELECT DATA TO ESTIMATE THE BOUND?
Since we are only interested in estimating the upper bound of the regret of the incumbent, we conjecture that using only the top performing hyperparameter evaluations may improve the estimation quality. To validate this, we use BORE (Tiao et al. 2021) tuning results on the naval dataset from HPO-Bench Klein & Hutter 2019) (described in Section 4.4) where we can quantify the true regret. We compute the upper bound by Eq. 7 using three options: 100%, top 50% or top 20% of the hyperparameters evaluated so far. The quality of the bound is measured by the difference to the true regret. Results are shown in Fig, 2a where the median of 50 replicates are shown solid line and the 20'th and 80' th quantiles are shown as dashed and dotted lines, respectively. We also show the number of negative differences (the upper bound is smaller than the true regret) in the legend next to the different options in the this figure.
From Fig. 2a fitting surrogate model with all the hyperparameter evaluations poses challenge for estimating the upper bound of the regret, which is aligned with recent findings on more efficient BO with local probabilistic model, especially for nigh-dimensional problems (Eriksson et al. 2019). Using the top 20% evaluations gives the best upper bound estimation quality in the median, at the cost of the most under-estimations the true regret (2553). Our method would stop early due to the
which would negatively impact the quality measured by RYC scores, as shown Fig. 26] As result, we use top 50% hyperparameters evaluations for the upper bound estimation throughout this paper.
64-
upper bound true
10-4
Tap ((regssiio)))
Zop-21.0f8 (#ioggative-200)
-00-
Top-50.0% (#07
-06
-10-
50
00901
0X000
BO iterations
Ubrestoold
(a) Bound quality for using all, the top 50% and top (b) Box plots of RYC scores when using the top 20% hyperparameter evaluations, measured by the 50% and top 20% hyperparameter evaluations under difference between upper bound and true regret. common thresholds.
The upper bound estimation quality affected by the of hyprparrameters evaluations used in the surrogate model training.
Figure 2:
4.3 STANDARD BO WITH CROSS-VALIDATION
We use standard BO with matérn 5/2 kernel the GP surrogate. The hyperparameters of the GP estimated with type II maximum likelihood estimation. We tune two algorithms: XGBoost (XGB) with 9 hyperparameters and Random Forest (RF) with three hyperparameters on 19 small tabular datasets using vross-validation. The detailed BO setting, hyperparameter search space of the

---

Under review as a conference paper at ICLR 2022
algorithms, as well as the characteristics of the datasets can be found in Appendix A.1 We optimize classification error or rooted mean square error for classification and regression datasets, respectively,
For our stopping method, only after the first 20 iterations to ensure a robust fit of the surrogate models both for our method and the baselines. We present the aggregated results across datasets for XGB and RF in Fig. [ where the mean (shown in the dots) and standard deviation (shown in the error bars in both RTC and RYC dimensions) of RTC and RYC scores for different termination methods are shown.
Eq. (8)
stopping threshold. We apply automatic termination
From Fig. a general trend on in the convergence check baseline is visible: as i increases, the speed-up decreases while the solution quality increases. The El and PI based stopping criteria behave similarly in terms of both RTC and RYC scores. The methods tend to stop BO very early, thus leading to significant speed up. However, maybe not surprisingly, such an aggressive early stopping leads to worse test performance on average. The convergence check baseline and our method could achieve various trade-offs between speed and solution quality effectively by changing patience hyperparameter or the post-correction term, and our method prioritizes quality over speed.
Furthermore, the standard deviations of the RYC and RTC scores also provide us with interesting insights. The RYC variances of our method are usually smaller than the baselines ones, indicating that we successfully maintain a high solution quality across wide range of scenarios. On the other hand, the RTC variances of our method are usually higher than the baselines, which highlights that our method adapts to different scenarios rather than stopping BO at similar iterations.
Cress Validition XGB
Croes Validation RF
615
8.00
0100
RYC
Cum-10 10
Comes 0
0006
Cuno-50
Cane30
Coar
Cous-30
Pi-1e-12
P1-1-12
FI-1e-16
RI-1e-10
Otes 0.21
Ouns 0.21
35
06
RTC
RTC
Figure 3: The mean and standard deviation of RYC and RTC scores for the compared automatic termination methods when using cross validation in the hyperparameter evaluation when tuning XGB (left) and RF (right). The mean value is shown the large dot and the standard deviation is shown as an error bar both dimensions.
4.4 NEURAL HYPERPARAMETER AND ARCHITECTURE SEARCH
main advantage or our termination criterion is that it applicable for any iterative HPO method. To demonstrate this, we apply it to several fate-off-thearr Bayesian optimization methods from the literature: TPE (Bergstra et al. 201 BORE Tiao et al. (2021), GP-BO (Snock et al. 2012) as well as random search (RS) (Bergstra & Bengio 2012). For each method and dataset, we perform 50 independent runs with different seed.
We consider two popular tabular benchmark suites from the literature: NAS-HPO- SAS--POO-Bentis -erhchBecchh (Klein & Hutter 2019), which mimics the hyperparameter and neural architecture search of multi- perceptrons on tabular regression datasets, and NAS-Bench-201 (Dong & Yang 2020 for neural architecture search on image classification datasets. Notice that for validation metrics to compute RYC instead of test metrics, thus, no positive RYC scores are observed. For a detailed description of these benchmarks following thresholds on the final regret {0.0001 0.001, 0.01) } in our experiments, corresponding to a loss of performance of 0.01%, 0.1% 1% and 1 % compared to global optimum. Due to space constraints we will only show results for BORE in Figure Fig. and Fig. respectively, and provide all other results in Fig. 6 in the appendix.
we used
refer to the original paper. We consider the
7

---

Under review as a conference paper at ICLR 2022
While method Pareto dominates the others, termination criterion shows similar trend as in Section 4.3 and tends to prioritise accuracy over speed. Users need to choose the threshold based on their own preference with respect to the speed-accuracy tradeoff, i.c higher threshold saves more wall-clock time but potentially leads to a higher drop in performance. However, our criterion benefits from intuitive and interpretable threshold. We further show distribution of true regrets the stopping iteration triggered by our method with the considered thresholds on HPO-Bench in Fig, [5d
From Fig. 5d with high threshold of 0.01, all the experiments (4 datasets with 50 replicates) are early stopped by our method and 41 (20%) experiments end up with true regret being higher than the threshold. With a low threshold of 0.0001, 112 experiments are stopped and (10.7% experiments end up with true regret being higher than the threshold. In short, our method achieves 80% to 90% success rate of stopping the BO with true regret within the user-defined tolerance.
naval
parkinsons
05-
-02
Cone-0
Can-30
Cony-00
-02-
Crae-50
Cone-50
-15
0us=0.0001
0uze0.0001
Ous-11000
Oun-0,001 0,001
-00
815
0.55
RTC
RTC
protein
slice
68-
RYC
-044
Com-30
Con-30
Care-50
-86-
Chno-50
0us-8.0001
O.0--.0001
Oun-0
Ocre0
Ous-0:11
Ouz-L.01
dn
04 RTC
C6
145
650
6de
000
1000
RTC
Figure 4: The mean and standard deviation of RYC and RTC scores for considered automatic termination methods for HPO-Bench datasets. The mean value is shown in the large dot and the standard deviation is shown an error bar in both dimensions.
For every method we aggregated the scores over datasets with other HPO optimizers in Fig. We can that the speed up of the convergence check baseline is affected very mildly by the optimizers while the RYC scores largely depend on the optimiser: RYC scores with random search are worse than with BORE. In contrast, the RYC scores for termination criterion are similar across optimisers, especially for smaller thresholds. On the other hand, the speed up for a given threshold tends to vary. This can be explained by the difference of the optimizer's performance, for examples random search is not as efficient as BORE, and hence the regret is mostly above the stopping threshold. In summary, while convergence check baselines are by design robust in terms of time saved, our method is more robust in terms of maintaining the solution quality.
4.5 OVERFITTING IN BO FOR HYPERPARAMETER OPTIMIZATION
Proposition emphasises an important problem of BO-based HPO: while focusing (and minimizing) the validation error, we cannot fully reduce the discrepancy between the validation and test errors. Empirically, we show this might happen when correlation between the test and validation errors is low, thus improvement in validation performance does not lead to the better test results. A particular example of such low correlation in the small error region is presented in Fig. g (AppendixxAA2) AA22) when tuning XGB and Random Forest tst-census dataset.
8

---

Under review as a conference paper at ICLR 2022
eifar10
cifar 100
010
400
0090
Cone:2
Can-3I
Cone330
-1.3
Cane-50
0unet12001
0.55
O0o-0001
Ous40.001
-0.3
14
RTC
RTC
(a)
(b)
imegenel
4Sto-=112 #Woung-12
@Soppi11 L1T Woonn-l1 Oun=Q.001
#Stop-200 #Woong-4 Ous-0.01
-187
30-
BYC
Com--10
-180
Can--30
Conr-30
Our
-1 19
Oun 0.1
0.
1079
31
10-1
10-1
13
10"
RTC
true regret stopped iteration
(c)
(d)
Figure 5: Fig. (a) -c) (c), the mean and standard deviation of RYC and RTC scores for considered automatic termination methods for MAS-Bench-200 datasets. Notice that validation metrics are used in these experiments, thus positive RYC scores observed. The mean value is shown in the big dot and the standard deviation is shown as error bar in both dimensions. In Fig. [5d] shows distribution of true regrets the stopping iteration triggered by method with considered thresholds for HPO-Bench. The number of stopped experiments and the number of "wrong" cases where the true regret is larger than the threshold are shown in the legend in Fig. 5d
In our experiments, a positive RYC score is an indicator of overfitting, showing that the test error at the terminated iteration is lower than the test error in the final round. We observe positive RYC scores in both Fig. 3 and Fig. 4 one with cross-validttion on small datasets and one with medium-sized datasets. Hence, we would like raise attention the possible overfitting issue that occurs HPO for which our method can be used as plugin to mitigate overfitting.
5 CONCLUSION
Despite the usefulness of hyperparameter optimizations (HPO), setting budget in advance remains challenging problem. In this work, we propose an automatic termination criterion that can be plugged into many common HPO methods. The criterion uses an intuitive and interpretable upper bound of simple regret, allowing users explicitly control the accuracy loss. In addition, when cross validation used in the evaluations of hyperparameters, we propose to use an analytical threshold rooted from the variance of cross validation results.
The experimental results suggest that our method can be robustly used across many HPO optimizers. Depending the user-defined thresholds, with 80% to 90% chance, our method achieves true regret within that threshold, saving unnecessary computation and reducing energy consumption. We also observe that overfitting exists in HPO even when cross-validation is used. We hope work will draw the attention of the HPO community to the practical questions of how to set budget in advance and how mitigate overfitting when tuning hyperparameters in machine learning.

---

Under review as a conference paper at ICLR 2022
Ethics Statement In broader context, we highlight that BO can reduce the computational cost required to tune ML models, mitigating the electricity consumption and carbon footprint associated with brute force techniques such as random and grid search. The automatic termination criterion presented in this work can have a positive societal impact by further reducing the cost of tuning MI models. On the other hand, BO is general methodology optimize gradient-free functions and is not limited to specific application domains. Our early-stopping approach does not decrease the risk for misuse, calling for methods to enforce fairness constraints Perrone et al. (202I) as well for care at model-deploymmnt time.
Reproducibility Statement To improve the reproducibility, the code to rerun the experiments can be found at lbttps: / ptctps://anonyan anonymouu...... 4open. scicnnce///B-oarr//a... peteeerrlysstoopnngeeee. sppping-5555 555E which will be made publicly available after the paper is published. Besides, we also detail the experiments setting in relevant aspects: the choices for BO are in Appendix [. the search spaces of the algorithms are in Appendix A.1.3 and the datasets sources and descriptions are in Appendix A.1.4
REFERENCES
Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey. Cross-validation confidence intervals for test error. In Neural Information Processing Systems (NeurlPS), 2020.
James Bergstra and Yoshua Bengio. Random search for hyperparameter optimization. Journal of Machine Learning Research, 2012.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyperparameter optimiztiinn............ In Neural Information Processing Systems (NeurIPS), 2011.
Yutian Chen, Aja Huang, Ziyu Wang, loannis Antonoglou, Julian Schrittwicser, David Silver, and Nando de Freitas. Bayesian optimization in AlphaGo, 2018
Xuanyi Dong and Yi Yang. Nas-hench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Neural Information Processing Systems (NeurIPS), 2019.
Geisser. The predictive sample reuse method with applications. Journal of The American Statistical Association, 1975.
Huong Ha, Santu Rana, Sunil Gupta, Thanh Nguyen, Hung Tran-The, and Svetha Venkatesh. Bayesian optimization with unknown search space. In Newral Information Processing Systems (NeurIPS), pp- 11795- 11804. Curran Associates, Inc., 2019.
Philipp Hennig and Christian J Schuler. Entropy search for information-efffcient global optimization. Journal of Machine Learning Research, 2012.
Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Aaron Klein and Frank Hutter. Tabular henchmarks for joint architecture and hyperparameter optimization. (.0iv:/995.04450 2019.
Harold J. Kushner. new method of locating maximum point of an arbitrary multipeak curve the presence of noise. Joint Automatic Control Conference, 1963.
Romy Lorenz, Ricardo Monti, Ines R Violante, Aldo Faisal, Christoforos Anagnostopoulos, Robert Leech, and Giovanni Montana. Stopping criteria for boosting automatic experimental design using real-time fMRI with Bayesian optimization. arXiv: /511::/5/110782/ 1.0827,, 2016.
Anastasiia Makarova, Inura Usmanova, Ilija Bogunovic, and Andreas Krause. Risk-averse heteroscedastic bayesian optimization, 2021.
Mark McLeod, Stephen Roberts, and Michael A. Osborne. Optimization, fast and slow: optimally switching between local and Bayesian optimization. In International Conference on Machine Learning (ICML), 2018.
Gábor Melis, Chris Dyer, and Phil Blunsom. On the state the art of evaluation in neural language models, In International Conference on Learning Representations (ICLR), 2018.
Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques, 1975.
10

---

Under review as a conference paper at ICLR 2022
Claude Nadeau and Yoshua Bengio. Inference for the generalization In Neural Information P Processing Systems (NeurIPS), 2003.
Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. In Asian Conference on Machine Learning, 2017.
Valerio Perrone, Michele Donini, Bilal Muhammad Zafar, Robin Schmucker, Krishnaram Kenthapadi, and Cédric Archambeau. Fair Bayesian optimization. AIES, 2021.
Carl Edward Rasmussen Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, 2006.
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical Bayesian optimization of machine learning algorithms. In Conference Neural Information Processing Systems (NeurIPS), 2012.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Sceger. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning (ICML), 2010.
Mervyn Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the royal statistical society. Series B (Methodologicau), 1974.
Louis C Tiao, Aaron Klein, Matthias Seeger, Edwin V. Bonilla, Cedric Archambeau, and Fabio Ramos. BORE; Bayesian optimization by density-ratio estimation. In International Conference on Machine Learning (ICML), 2021.
A APPENDIX
A.1 EXPERIMENTS SETTING
A.1.1 BO SETTING
We used internal BO implementation where expected improvement (EI) together with Mat'ern-52 kernel the GP used. The hyperparameters of the GP includes output noise, scalar value, bandwidths for every input dimension, input warping parameters and a scalar covariance scale parameter. The closest. open-source implementations are GPyOpt using input warped GP or AutoGluon BayesOpt searcher We maximize type Il likelihood to learn the GP hyperparameters in experiments.
A.1.2 ALGORITHM
A.1.3 SEARCH SPACES FOR CROSS VALIDATION EXPERIMENTS
XGBoost (XGB) and RandomForest (RF) are based on scikit-learn implementations and their search spaces are listed in T
A.1.4 DATASETS IN CROSS VALIDATION EXPERIMENTS
We list the datasets that used in experiments, well as their characteristics and sources in Table For each dataset, first randomly draw 20% regression datasets 10-fold stratified eross validation for classification datasets. The actual splits depend on the seed controlled our experiments. For a given experiment, all the hyperparameters trainings use the same data splits for the whole tuning problem. For the experiments without cross-validation, we use 20% dataset validation set and the rest as training set.
set and for the rest,
10-fold validations for
A.2 DETAILED RESULTS
We first show the scatter plots of RTC and RYC scores for different automatic termination methods on HPO- Bench-datasets in Fig. and the results on
in Fig.
A.2.1 DETAILED NUMBERS OF RYC AND RTC SCORES
We report detailed RYC scores and RTC scores of different HPO automatic termination methods for the experiments the main text in Table 3
Table 4 and Table
htt.

---

Under review as a conference paper at ICLR 2022
Algorithm 1 BO for HPO with cross-validation and automatic termination
Require: Model M, parametrized by 7 r data (Di....,Dyy for k-fold cross cross- validation.
acquisition function a())
1: Initialize y/
and G. 0
2: fort= ........ do
3: Sample 7/ arg ea a(r) 4: for .... do
5: Fit the model M, (: D-i)) where D_1 UjziD;
6:
Evaluate the fitted model yf [Di Σ My D-:))
X..VED:
7:
end for
8:
Calculate the sample mean y1 Et.
9:
if yt S. oe then
Update yi = yr and the current best 3/ = 7/
11:
Calculate the sample variance s2. 1 E, (1= vi)²
12:
Calculate the variance estimate Var f(x) 2
[P_d
[Dd
s from Eq. (
13:
end if
14:
Update G, = G "t and V/: V1:--1 U V/
15:
Update oz (4 with Eqs. (1) and (2)
Calculate upper bound Fr min ucb, min (cb,(>) for simple regret from Eq. 7 7EG.
17:
if the condition F; S /Var(>)) holds then
18:
terminate BO loop
end if
20:
end for
21:
Output: 7/
Table I: Search spaces description for each algorithm.
tasks
hyperparameter
search space
scale
eestimatorss
[2, 2
log
learning_ rate
[10 1]
log
gamma
[10-6 2
log
min
min_child_weight
[10-6
log
XGBoost
max_depll
[2,2*]
log
subsample
[0.5.
linear
colsample_bytres
[0.3.
linear
reg. leg_lamdda
[10-6.2]
log
reg reg_alphi alpha
[10-6.2]
log
estimators
[1,2
log
RandomForest
min_samples_sphe
[0.01, 0.5]
log
max_de depthh
[1,5]
log
A.2.2
CORRELATION BETWEEN VALIDATION AND TEST METRICS
In Fig. show the correlation between validation and test metries of hyperparameters when tuning XGB and on tst-census dataset Fig.
A.2.3 THE CHOICE
high-probability concentration inequalities (aka confidence bounds) are important reason about unknown objective function and are used for theoretically grounded convergence guarantees some (GP-UCB-AA UCB-based) BO methods (Srinivas et al. 2010 Ha et al. 2019 Kirschner et al. 2020 Makarova et al. 2021). There, 9e stands for the parameter that balances hetween exploration vs. exploitation and ensures the validity of the confidence then guided by the assumptions made the unknown objective, for example, the
bounds. The choice
12

---

Under review as a conference paper at ICLR 2022
dataset
problem _ype
n n_rows
n cols
n classes
source
openml14
classification
1999
76
10
openml
openm120
classification
1999
240
10
openml
Ist-hate-crimes
classification
2024
43
63
data.gov
openml-9910
classification
3751
1776
2
openml
farmads
classification
4142
4
2
uci
openml-3892
classification
4229
1617
2
openml
sylvine
classification
5124
21
2
openml
op100-9952
classification
5404
5
2
openml
openm128
classification
5619
64
10
openml
philippine
classification
5832
309
2
data, gov
fabert
classification
8237
801
2
openml
openm132
classification
10991
16
10
openml
openml34538
regression
1744
43
openml
tst-census
regression
2000
44
data.gov
openml405
regression
4449
202
openml
tmdb mndb-movie-metadee metaaatetadata
regression
4809
22
kaggle
openml503
regression
6573
14
openml
openm1558
regression
8191
32
openml
openm1308
regression
8191
32
openml
Table 2: Datasets used in experiments including their characteristics and sources.
GP-BO HPO-Reenhh
TPE HPO-Bench
01-
-07
-85-
-0-5
Gen
Oan D0:
3.
14
68
15
RTC
RTC
(a)
(b)
RS HPO-Bench
BORE HPO-Bench
02:
Com--0
Cooo 30
Crne-0
Cimo-3))
Cour-50
Ous--LL000
-66
0.000
-8b
Ocs-40001
Ous-B/1
Oue-0.01
RTC
RTC
(c)
(d)
Figure 6: Fig. (a) (d), the mean and standard deviation of RYC and RTC scores for considered automatic termination methods on HPO-Bench datasets using GP based BO (GP-BO), Random Search (RS), TPE and BORE optimizers. The mean value is shown in the big dot and the standard deviation is shown as error bar in both dimensions.
objective being sample from GP or the objective having the bounded norm in RKHS (more agnostic case used in Section 3).
13

---

Under review as a conference paper at ICLR 2022
GP-BO NAS-Bench201
TPE AAS-Bench201
02
-02
-15
-08
Orstutt
-10
14
RTC
RTC
(a)
(b)
RS NAS- MSS-Bench201
BORE 2S-Bench201
005
-038
-0.00
Cam-10
Cones 0
Cuns-50
Cany-30
Coun
Cony-30
Otes 01000
0.000.2001
0,000,001
Otes DUll
Ouns 0,61
-22
60
RTC
RTC
(c)
(d)
Figure 7: Fig. (a) (d), the mean and standard deviation of RYC and RTC scores for considered automatic termination methods on NAS-Bench-201 datasets using GP based BO (GP-BO), Random Search (RS), TPE and BORE optimizers. The mean value is shown in the big dot and the standard deviation is shown as error bar in both dimensions.
RTC
RYC
algo
RF
XGB
RF
XGB
Conv_ 10
0.840
0.841
-0.031
-0,051
Conv_30 30
0.686
0.666
-0.022
-0.026
Conv_50
0.498
0.504
-0.015
-0.021
EI 1e-08
0.896
0.850
-0.057
-0.052
EI_ 1e-12
0.895
0.779
-0.055
-0.047
El_
0.893
0.718
-0.052
-0.055
PI 0.0001
0.898
0.875
-0.059
-0.059
PI le-08
0.895
0.814
-0,055
-0.052
PI_ 12-ee-1
0.894
0.739
-0.055
-0.044
Ours 0121
0.318
0.144
-0.004
-0.003
Ours_0.5
0.580
0.224
-0.013
-0.006
Table 3: RTC and RYC scores for early stopping methods in cross validation benchmarks.
In our experiments, we follow the common practice of scaling down B, which is usually used to improve performance over the (conservative) theoretically grounded values (see e.g., Srinivass et al. (2010): Kirschner
22020) Makarova et al. (2021)) Particularly, throughout this paper, we set 3r log Ii .² 66) where 0.1 and is set he the number hyperparamcters. then further scale down by factor of as
defined in the experiments in Srinivas et al. (010).. We provide an ablation study on the choice of f in Fig. 9
14

---

Under review as a conference paper at ICLR 2022
RTC
RYC
dataset
naval
parkinsons
protein
slice
naval
parkinsons
protein
slice
Conv 10
0.943
0.947
0.946
0.942
-0.605
-0.582
-0.117
-0.432
Conv_30 30
0.826
0.837
0.837
0.840
-0.064
-0.235
-0.021
-0.119
Conv 50
0.748
0.729
0.734
0.747
-0.038
-0.107
-0.008
-0.058
Ours 0.0001
0.790
0.018
0.198
0.822
-0,041
-0.012
-0.005
-0.072
Ours 0.001
0.910
0.038
0.271
0.934
-0.220
-0.031
-0.018
-0.281
Ours 0.01
0.941
0.901
0.906
0.953
-0.498
-0.378
-0.071
-0.466
Table 4: RTC and RYC scores for early stopping methods in HPO-Bench.
RTC
RYC
dataset
ImageNet
cifar10
cifar100
ImageNet
cifar10
cifar100
Conv_10
0.880
0.889
0.888
-0.034
-0.098
-0.097
Conv_30 _0
0,612
0.611
0.606
-0.010
-0.019
-0.036
Conv 50
0.372
0.361
0.372
-0,004
-0.006
-0.014
Ours 0.0001
0,274
0.311
0.519
-0.002
-0.008
-0.026
Ours 0.001
Ours_0.001
0.377
0.622
0.582
-0.005
-0.023
-0.033
Ours 0001
0.837
0.902
0.879
-0.022
-0.106
-0.099
Table RTC and RYC scores for early stopping methods in
test eiTor
11-
[tsl
validltionn error
validation error
(a) Training XGB on test-census dataset
Training on test-census dataset.
Figure 8: We show validation error for training XGB (a) and RF (b) tst-census dataset on z-axis and test error on the y-axis. the low error region, validation metrics are not well correlated with the test metrics.
15

---

Under review as a conference paper at ICLR 2022
BORE on Naval dataset
upper bound - true regret
109
HP (#negative=537)
10-1
B = 0.2 (#negative=6655) 6654)
10
10-3
10
10-5
10-6
10
100
200
300
400
500
BO iterations
Figure 9: The differences between upper bound and true regret for every BO iterations when using BORE to tune an MLP on the Naval dataset. The number negative differences (the upper bound is smaller than the true regret) shown in the legend next the two options for computing 3,.
16


Reviews:
[{"review_id": "xKgA2LmZAt6", "reviewer": "Reviewer_MRmf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem setting of early terminating the entire BO process is interesting and novel. How to effectively pre-specify a termination criterion is a practical challenge in the field of HPO. The proposed mechanism of bounding the regret based on a user-defined tolerance makes intuitive sense. It is also reasonable to notice that overfitting can occur in HPO. Here are a few detailed comments:\n\n- Figure 1a is not very visually informative. It is hard to understand that the orange line is the ucb and the green line is the lcb visually.\n- Some typos: \"prooved\"-->\"proved\" in page 3, \"letter\"--> \"latter\" in page 4.\n- It is hard to understand intuitively why the suboptimal solution resulted from the empirical surrogate can be mitigated by early stopping. It is suspicious to draw the conclusion that it can be mitigated by the proposed method. Could you explain more?\n\nQuality: The submission is technically sound. The claims in the contribution are well-supported by theoretical analyses and empirically results. It is a complete piece of work that outperforms prior work empirically.\n\nClarity: This paper is well-written and easy to follow. The problem is also well-motivated. The experimental details are also very specific, such that reproducing the results should be possible. \n", "summary_of_the_paper": "This paper studies the problem of pre-specifying the optimal termination criterion for Bayesian optimization. Different from prior work that tracks the value of acquisition function, this paper proposes an automatic termination criterion for BO. In particular, they construct a high-probability confidence bound on the regret, and then the users can specify a desired tolerance that shows how accurate the final solution should be compared to the global optimal. They estimate the threshold via a cross-validation estimate of the generalization error. Empirically, they design two evaluation metrics, relative test error change RYC and relative time change RTC, and compare to the comprehensive prior work. The results demonstrate the effectiveness of their proposed approach.\n", "summary_of_the_review": "This paper proposes a novel early stopping criterion for Bayesian optimization. It is well-written and well-motivated. The proposed idea is simple and technically sound. The claims are well-supported by theoretical analyses and extensive experimental results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jOUpzseQnU", "reviewer": "Reviewer_QxQD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Lack of literature review:\nIn general, this paper aims to solve the early/optimal stopping of the Bayesian optimization (BO). Plenty of related works are even not mentioned in the paper, e.g. Freeze-thaw BO [1],  Multi-fidelity BO [2], Hyperband BO [3], and BOS-BO [4], these works all discussed how to achieve efficiency and saving budget in BO. A detailed discussion of the difference between the proposed method and all the previous works needs to be mentioned, not to mention comparison experiments. \n\nThe stopping criterion is mainly decided by Eq. (7), specifically, determined by the upper confidence bound and lower confidence bound. However, this bound is quite loose, since there is one variable determining the magnitude of it: $\\beta_t$. Through the paper, the authors do not mention the role of $\\beta_t$ and its impact on regret. In fact, if $\\beta$ is set small enough, the condition in Proposition 2 can be easily satisfied right? \n\nMoreover, the variance estimate of $\\hat{f}$ lacks theoretical analysis. I am expecting the authors to giving theoretical guarantee of the estimate to the real variance. Otherwise, it won't be possible to determine whether the estimate is to the same magnitude of the real variance. \n\n\n[1] Swersky, K., Snoek, J., and Adams, R. P. Freeze-thaw Bayesian optimization. arXiv:1406.3896, 2014.\n\n[2] Kandasamy, K., Dasarathy, G., Oliva, J. B., Schneider, J., and Poczos, B. Gaussian process bandit optimization with multi-fidelity evaluations. In Proc. NIPS, 2016.\n\n[3] Falkner, S., Klein, A., and Hutter, F. BOHB: Robust and efficient hyperparameter optimization at scale. In Proc. ICML, 2018.\n\n[4] Dai, Z., et al. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML, 2019.", "summary_of_the_paper": "This paper proposes an automatic termination criterion for Bayesian optimization (BO) by using the upper bound of the simple reget. Various experiments are conducted to demonstrate that with the utilization of the termination criterion, computation and energy consumption can be reduced. The major contribution of this paper lies in the two propositions. Proposition 1 discusses the relationship between statistical error and optimization error, the authors claim that due to the irreducible statistical error, it is appropriate to reduce the optimization error $\\epsilon_{BO}$ to the same magnitude w.r.t. the statistical error. Since the statistical error $\\epsilon_{st}$ is unknown, the authors adopt an existing cross-validate method to estimate it. Then in proposition 2, the termination criterion is detailed once the BO regret is less than the standard deviation of statistical variance. ", "summary_of_the_review": "Given the lack of literature review and comparison experiments, plus the bound for $\\epsilon_{BO}$ lacks theoretical guarantee. This paper needs a major revision. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BwLQCnJxfcl", "reviewer": "Reviewer_yUir", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think the main idea of the work is interesting. The writing of the paper is generally clear, except Section 3, which I think is not mathematically rigorous. This section causes me a lot of confusion and I find it's hard to understand all the maths behind the proposed approach. I have several questions listed below:\n1.\tI'm confused by the definition of \\epsilon_{BO}. Is \\epsilon_{BO} a user-defined threshold or is there any formula showing the definition of \\epsilon_{BO}? I can't find the definition of \\epsilon_{BO} in the paper. Also, in Proposition 1, it says that \\hat{\\gamma}_D is a candidate solution of min_{\\gamma \\in \\Gamma} \\hat{f}(\\gamma) such that \\hat{f}(\\hat{gamma}_D) - \\hat{f}(\\gamma^*_D) \\leq \\epsilon_{BO}, this means the set of \\hat{\\gamma}_D depends on \\epsilon_{BO}. If this is the case, then I expect the notation of \\hat{gamma}_D should be changed to reflect the dependent (because for different values of \\epsilon_BO, there will be a different set of \"candidate solutions\".\n2.\tIn the first sentence right after the proof of Proposition 1, it is stated that the optimization error \\epsilon_{BO} is bounded by the simple regret \\hat{r}_t? Why is this the case? If \\epsilon_{BO} is a user-defined threshold then it shouldn’t have any relation with the simple regret? Why is it bounded by the simple regret? I think the confusion here is also related to my confusion on the definition of \\epsilon_{BO}.\n3.\tIn the paragraph \"Upper bound for \\hat{r}_t\" at the end of Page 3, there is a statement saying that \"with high probability, \\hat{f}(\\gamma) is bounded by lower and upper confidence bounds defined as lcb_t(\\gamma) = \\mu_t(\\gamma) - \\beta_t \\sigma_t(\\gamma) and ucb_t(\\gamma) = \\mu_t(\\gamma) + \\beta_t \\sigma_t(\\gamma)\". This statement is not always true, it is only true when the domain of the objective function is discrete. When the domain is continuous, it needs to have another term O(1/t^2) in the upper and lower bound because of the discretization process (see Lemmas 5.5, 5.6, 5.7 in Srinivas et al (2010)).\n4.\tIn Eq. (7), I do not understand why \\epsilon_{BO} is smaller than \\hat{r}_t. Can the authors explain in more detail?\n5.\tIn the sentence right below Eq. (7), it states that \\hat{f}(\\gamma_t^*) = min_{\\gamma \\in G_t} \\hat{f}(\\gamma). On the other hand, In Eq. (6), it states that \\hat{f}(\\gamma_t^*) is the best value found by iteration t. Combining these two equations, this means \\gamma_t^* is the value with the lowest value of \\hat{f}(\\gamma)? In practice, this is only true when the empirical loss function \\hat{f}(\\gamma) is noiseless. However, note that to apply the regret analysis in Srinivas et al (2010) the objective function needs to be noisy.\n6.\tI'm also confused with Proposition 2. Is this a proposal from the paper, that is, to terminate BO when \\bar{r}_t < \\sqrt{Var \\hat{f} (\\gamma_t^*)}? Or is this a mathematical proposition (i.e. when the condition in Eq. (9) occurs, BO is automatically terminated)? I can't find a proof of Proposition 2 in the Appendix. Also, by checking the Algorithm 1 in Page 12 in the Appendix, I have a feeling that this Proposition 2 is just a proposal from the paper. Is this the case?\n7.\tI found it's a bit hard to read Figure 3. More detailed explanation for Figure 3 is needed in the revised version of the paper.\n", "summary_of_the_paper": "The paper proposes a new approach for automatic termination of hyperparameter optimization based on Bayesian Optimization (BO).  The idea is to construct high-probability confidence bound on the regret and then determine when to terminate the BO process. Empirical experiments are conducted on various real-world HPO and NAS benchmarks to show the efficacy of the proposed approach.", "summary_of_the_review": "Like I mentioned in the previous section, I think the overall idea of the work is interesting. But the maths behind the proposed approach is not rigorous and confused. I find a lot of confusion reading Section 3, which is the main section of the paper. I have several questions to the authors listed in the previous sections, hopefully, the answers from the authors will be able to clear my doubt.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the stopping condition of Bayesian Optimization (BO) is discussed. This problem is very important when BO is applied to the Hyper-parameter optimization (HPO) task. All the reviewers agree that the proposed approach based on high-probability confidence bound on the regret is interesting and reasonable.  An important issue raised by a reviewer is that many existing BO works discussed how to achieve efficiency and saving budget in BO although they did not explicitly mention the stopping condition. Due to the lack of discussion regarding the relationship with these highly related studies, we have to conclude that the paper cannot be accepted in its current form.
Decision: Reject