Year: 2021

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.

heading: 1 INTRODUCTION
text: While the performance of machine learning algorithms crucially depends on their hyperparameters, setting them correctly is typically a tedious and expensive task. Hyperparameter optimization (HPO) emerged as a new sub-field in machine learning that tries to automatically determine how to configure a machine learning algorithm. One of the most successful strategies for HPO is Bayesian optimization (BO; Močkus, 1975; Chen et al., 2018; Snoek et al., 2012; Melis et al., 2018) which iteratively trains a 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 be defined in advanced. If this budget is too small, BO might return hyperparameters that result in a poor predictive performance. If the budget is too large, compute resources will be wasted and, in some cases, it may result in overfitting as we will show in our experiments. Automatically stopping BO is a rather under-explored topic in the literature. A simple baseline 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 as early stopping for neural network training. Another approach is to track probability of improvement (Lorenz et al., 2016) or expected improvement (Nguyen et al., 2017), and stop the optimization process once it 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, McLeod et al. (2018) propose to switch to local optimization when the global regret is smaller than a pre-defined target. This condition can also be used to terminate BO early, but it comes with additional complexity such as identifying a (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 high-probability confidence bound on the regret (i.e., the difference of our current solution to the global optimum) exploiting the probabilistic model of the objective. Thus, users are now asked to specify a 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-validation estimate of the generalization error. This choice takes into account the irreducible discrepancy between
the actual objective and the target function optimized via BO, namely the difference between the performance on new data (i.e., the population risk) and the validation error. Our extensive empirical evaluation on a 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., 2017). We also surface overfitting effects in HPO on both small and large datasets, arguably an overlooked problem in the literature, and demonstrate that our termination criterion helps to mitigate it.

heading: 2 BACKGROUND
text: Bayesian optimization (BO) refers to methods of optimizing a black-box objective f : Γ → R in an iterative manner. At every step t, a learner selects an input γt ∈ Γ and observes a noisy output
yt , f(γt) + εt,
where εt is typically assumed to be i.i.d. (sub)-Gaussian noise with some variance (proxy) σ2ε . 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 (µ, κ) (Rasmussen & Williams, 2006), specified by some mean function µ : Γ → R and some kernel κ : Γ × Γ → R. As observations y1:t = [y1, . . . , yt]
> for the selected inputs Gt = {γ1, . . . , γt} are being collected, they are used to update the posterior belief of the model defined by the posterior mean µt(γ) and variance σ2t (γ) as:
µt(γ) = κt(γ) T (Kt + σ 2 εI) −1y1:t (1) σ2t (γ) = κ(γ, γ)− κt(γ)>(Kt + σ2εI)−1κt(γ), (2)
where (Kt)i,j = κ(γi, γj) and κt(γ)T = [κ(γ1, γ), . . . , κ(γt, γ)]T . The next input to query is determined by an acquisition function that aims to trade off exploration and exploitation. Common choices include probability of improvement (Kushner, 1963), entropy search (Hennig & Schuler, 2012), GP upper-confidence bound (Srinivas et al., 2010), to name a few.
The convergence of BO can be quantified via (simple) regret, i.e., the sub-optimality in function value:
rt := f(γ ∗ t )− f(γ∗), (3)
where γ∗ is the global optimizer of f and γ∗t = arg minγ∈Gt f(γ). Specifying adequate tolerance that defines how small the regret should be to terminate BO is of high importance as it determine both the quality and the cost of the solution. However, this criterion cannot be directly evaluated in practice, as the input γ∗ and the optimum f(γ∗) are not known.
Hyperparameter optimization (HPO) is a widely considered application for BO. Consider a supervised learning setting training a machine learning model (e.g., a neural network)M on some feature-response data points D = {(xi, yi)}ni=1 sampled i.i.d. from some unknown data distribution P . The model is obtained by running a training algorithm (e.g., optimizing the weights of the neural network via SGD) on D, and the model returned also depends on hyperparameters γ (e.g., learning rates used, batch size, etc.). We use the notationMγ(x;D) to refer to the prediction that the model produced byM makes for an input x, when trained with hyperparameters γ on data D. Given some loss function `(·, ·), the population risk of the model on unseen data points is given by the expected loss EP [`(y,Mγ(x,D))]. The main objective of HPO is to identify hyperparameters γ, such that the resulting model minimizes the population risk:
f(γ) = EP [ ` ( y,Mγ(x,D) )] , γ∗ = arg min
γ∈Γ f(γ). (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 DV 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 γ∗D:
f̂(γ) = 1 |DV | ∑ xi,yi∈DV ` ( yi,Mγ(xi,D) ) , γ∗D = arg min γ∈Γ f̂(γ). (5)
At its core, BO-based HPO evaluates noisy empirical estimate f̂(γt) for promising hyperparameters γt for some finite number of iterations and the final performance after termination heavily depends on that number. Alternatively, one can also terminate BO when sufficiently close to the global optima, i.e., using an analogue to the simple regret rt for the validation loss f̂(γ) and f̂(γ∗t ) = min
γ∈Gt f̂(γ):
r̂t := f̂(γ ∗ t )− f̂(γ∗D). (6)
Inconsistency in the optimization objective. Importantly, the true HPO objective f(γ) in Eq. (4) and the empirical surrogate f̂(γ) in Eq. (5) used for tuning by BO generally do not coincide. Therefore, existing BO approaches may yield sub-optimal solutions to the population risk minimization, even if they succeed in globally optimizing f̂(γ). This issue, however, is typically neglected in practical HPO. In contrast, we propose a termination condition for BO motivated by the discrepancy in the objectives.

heading: 3 TERMINATION CRITERION FOR HYPERPARAMETER OPTIMIZATION
text: This section firstly motivates why early termination of HPO can be beneficial and then addresses the following two questions: (1) How to estimate the unknown simple regret and (2) What threshold of the simple regret can be used to stop HPO.

heading: 3.1 MOTIVATION FOR THE TERMINATION CRITERION
text: We start by analysing the true discrepancy of interest: between the population risk f(γ∗t ) at some input γ∗t and true optimum f(γ
∗). We then observe that this discrepancy sums from the statistical error of the empirical BO objective f̂(γ) as well the sub-optimality of the BO candidates (encoded in the simple regret r̂t). The key insight of the following proposition is that iterative reducing of r̂t to 0 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), respectively, and assume the statistical error of the estimator is bounded as ||f̂−f ||∞ ≤ st for some st ≥ 0. Let γ∗ and γ∗D be their optimizers: γ ∗ = arg minγ∈Γ f(γ) and γ ∗ D = arg minγ∈Γ f̂(γ). Let γ ∗ t be some candidate solution to minγ∈Γ f̂(γ) with sub-optimality in function value r̂t := f̂(γ∗t )− f̂(γ∗D). Then the gap in generalization performance f(γ∗t )− f(γ∗) can be bounded as follows:
f(γ∗t )− f(γ∗) ≤ f(γ∗t )− f̂(γ∗t )︸ ︷︷ ︸ ≤ st + f̂(γ∗t )− f̂(γ∗D)︸ ︷︷ ︸ =r̂t + f̂(γ∗D)− f̂(γ∗)︸ ︷︷ ︸ ≤0 + f̂(γ∗)− f(γ∗)︸ ︷︷ ︸ ≤ st
≤ 2 st + r̂t. Moreover, without further restrictions on f , f̂ , γ∗t and γ ∗, the upper bound is tight.
Proof: While the second inequality is due to the definition of γ∗t , the others can proved as follows:
f(γ∗t )− f̂(γ∗t ) ≤ |f(γ∗t )− f̂(γ∗t )| ≤ max γ∈Γ |f(γ)− f̂(γ)| = ||f̂ − f ||∞ ≤ st,
γ∗D = arg min γ∈Γ f̂(γ) −→ ∀γ ∈ Γ : f̂(γ∗D)− f̂(γ) ≤ 0 −→ f̂(γ∗D)− f̂(γ∗) ≤ 0.
The proposition provides the discrepancy bound in terms of the statistical error st and simple regret r̂t. This naturally incites terminating HPO at a candidate γ∗t for which the simple regret r̂t is of the same magnitude as the statistical error st (as further reduction in r̂t may not improve notably the true objective). However, neither of the quantities st and r̂t is known.
Below, we propose a 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 r̂t Srinivas et al. (2010); Ha et al. (2019). Secondly, we estimate the statistical error st 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 or bias) of such cross-validation-based 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 to the usage of interpretable upper bound of simple regret.

heading: 3.2 BUILDING BLOCKS OF THE TERMINATION CRITERION
text: Upper bound for the simple regret r̂t. The key idea behind bounding r̂t is that, as long as the GP-based surrogate model of f̂(·) is well-calibrated, we can use it to construct high-probability confidence bounds for f̂(·). In particular, Srinivas et al. (2010) show that as long as f̂ has bounded norm in the reproducing kernel Hilbert space (RKHS) associated with the covariance function κ used in the GP, f̂(γ) is bounded (with high probability) by lower and upper confidence bounds lcbt(γ) = µt(γ)− √ βtσt(γ) and ucbt(γ) = µt(γ) + √ βtσt(γ). Hereby, βt is a 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̂(γ∗t ) and f̂(γ ∗ D) that define the sub-optimality r̂t:
r̂t = f̂(γ ∗ t )− f̂(γ∗D) ≤ min γ∈Gt ucbt(γ)−min γ∈Γ lcbt(γ) =: r̄t, (7)
where the inequality for f̂(γ∗t ) is due to the definition of the reporting rule f̂(γ ∗ t ) = minγ∈Gt f̂(γ) over the evaluated points Gt = {γ1, . . . , γt}. We illustrate the idea with an example in Fig. 1a. Termination threshold. We showed how to control the optimization error via the (computable) regret upper bound r̄t in the above and now we propose to stop the BO when r̄t is smaller than some threshold BO, i.e. at an iteration T : r̄T ≤ BO. Following Proposition 1, we suggest setting BO to be of similar magnitude as the statistical error st (since smaller regret r̂t is not beneficial when st dominates). We now discuss how to estimate the statistical error st in case of cross-validation.
Cross-validation is the standard approach to compute an estimator f̂(γ) of the population risk. The data D is partitioned into k equal-sized sets D1, . . . ,Dk used for (a) training the modelMγ(·;D−i), where D−i = ∪j 6=iDi (i.e., training on all but the i-th fold), and (b) validatingMγ(·;Di) on the i-th fold of the data. These two steps are then repeated in a loop k times, and then the average over k validation results is computed, yielding the noisy BO evaluation y = f̂(γ) + ε where the noise is due to the randomness in the training procedure or to epistemic uncertainty.
The statistical error st of an estimate can be characterised in terms of its variance and bias where the latter can be neglected in case of cross-validation (Bayle et al., 2020). Though the variance of the cross-validation estimate Varf̂(γ) = E[(f̂(γ)− Ef̂(γ))2] is generally unknown, Nadeau & Bengio (2003) propose an estimate for it. Specifically, for the sample variance (denoted as s2cv) of k-fold cross-validation, a simple post-correction technique to estimate the variance Varf̂(γ) is
Varf̂(γ) ≈ ( 1
k + |Di| |D−i|
) s2cv(γ), (8)
where |Di|, |D−i| are the set sizes. For example, in the case of 10-fold cross-validation we have Varf̂(γ) ≈ 0.21s2cv(γ). We are now ready to propose our termination condition in the following.
Termination condition for BO. Consider the setup of Proposition 1 where f̂(·) is a cross-validationbased estimator being iteratively minimized by BO. Let yt = f̂(γt) + εt be a noisy evaluation at the input γt and γ∗t = arg min
γi∈{γ1,...,γt} yi denote the best observed input by BO iteration t. Let r̄t defined in
Eq. (7) be the simple regret bound computed at each iteration t. Let the variance Varf̂(γ∗t ) of the estimator f̂(·) be approximated according to Eq. (8). Then, BO is terminated once:
r̄t < √ Varf̂(γ∗t ). (9)
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.1.2. If cross-validation 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 accuracy. This case is demonstrated in Fig. 1b, with an example of automatic termination for tuning an MLP.

heading: 4 EXPERIMENTS
text: The main challenge of early 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.

heading: 4.1 EXPERIMENTAL SETUP
text: We start with describing our experimental setup to validation our approach. To establish a sensible experimental setup, we define two new metrics that account for the trade-off between resources saved and drop in final performance and provide a list of reasonable baselines.

heading: 4.1.1 BASELINES
text: To validate our proposed termination criterion we consider the following baselines:
• The first baseline is a näive convergence test controlled by a parameter i: BO is stopped once the best observed validation metric remains unchanged for i consecutive iterations. This convergence condition heavily relies on i, which needs to be chosen in 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-defined scale, rendering it hard to identify a sensible threshold in practice. We follow the recommendations from Nguyen et al. (2017); Lorenz et al. (2016) and consider the following values for EI {10−9, 10−13, 10−17} and for PI {10−5, 10−9, 10−13}. Empirically, we observe that all thresholds lead to significant speeds up 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−17 for EI and 10−13 for PI, and report the full results in Appendix A.2.

heading: 4.1.2 METRICS
text: To measure the effectiveness of a termination criterion, we analyze two metrics to quantify the change in test error and the time saved. Particularly, given a BO budget T, we compare the test error yes when early stopping is triggered to the test error yT . For each experiment, we compute the relative test error change RYC as
RYC = yT − yes
max(yT , yes) . (10)
This allows us to aggregate the results over different algorithms and datasets, as RYC ∈ [−1, 1] and can be interpreted as follows: A positive RYC represents an improvement in the test error when
applying early stopping, while a negative RYC indicates the opposite. Similarly, let the total training time for a predefined budget T be tT and the total training time when early stopping is triggered be tes. Then the relative time change RTC is defined as
RTC = tT − tes tT . (11)
A positive RTC, where RTC ∈ [0, 1], indicates a reduction in total training time. While reducing training time is desirable, it should be noted that this can be achieved through any simple stopping criterion (e.g., consider interrupting HPO with a fixed probability after every iteration). In other words, the RTC is not a meaningful metric when decoupled from the RYC and we will thus consider the two in tandem in the following experiments.

heading: 4.2 HOW TO SELECT THE DATA TO ESTIMATE THE BOUND?
text: 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 as 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 a surrogate model with all the hyperparameter evaluations poses a 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 high-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 of the true regret (2553). Our method would stop too early due to the under-estimation, which would negatively impact the quality measured by RYC scores, as shown in Fig. 2b. As a result, we use top 50% hyperparameters evaluations for the upper bound estimation throughout this paper.

heading: 4.3 STANDARD BO WITH CROSS-VALIDATION
text: We use standard BO with matérn 5/2 kernel in the GP surrogate. The hyperparameters of the GP are 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 cross-validation. The detailed BO setting, hyperparameter search space of the
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, we use Eq. (8) as our stopping threshold. We apply automatic termination 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. 3 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.
From Fig. 3, a general trend on i in the convergence check baseline is visible: as i increases, the speed-up decreases while the solution quality increases. The EI 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 a 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.

heading: 4.4 NEURAL HYPERPARAMETER AND ARCHITECTURE SEARCH
text: A main advantage or our termination criterion is that it is applicable for any iterative HPO method. To demonstrate this, we apply it to several state-of-the-art Bayesian optimization methods from the literature: TPE (Bergstra et al., 2011), BORE Tiao et al. (2021), GP-BO (Snoek et al., 2012) as well as random search (RS) (Bergstra & Bengio, 2012). For each method and dataset, we perform 50 independent runs with a different seed.
We consider two popular tabular benchmark suites from the literature: NAS-HPO-Bench (Klein & Hutter, 2019), which mimics the hyperparameter and neural architecture search of multi-layer perceptrons on tabular regression datasets, and NAS-Bench-201 (Dong & Yang, 2020) for neural architecture search on image classification datasets. Notice that for NAS-Bench-201, we used validation metrics to compute RYC instead of test metrics, thus, no positive RYC scores are observed. For a detailed description of these benchmarks we refer to the original paper. We consider the 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% and 1% compared to global optimum. Due to space constraints we will only show results for BORE in Figure Fig. 4 and Fig. 5, respectively, and provide all other results in Fig. 6 in the appendix.
While no method Pareto dominates the others, our termination criterion shows a 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.e a higher threshold saves more wall-clock time but potentially leads to a higher drop in performance. However, our criterion benefits from an intuitive and interpretable threshold. We further show a distribution of true regrets at the stopping iteration triggered by our method with the considered thresholds on HPO-Bench in Fig. 5d.
From Fig. 5d, with a 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 12 (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.
For every method we aggregated the scores over datasets with other HPO optimizers in Fig. 6. We can see 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 our 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.

heading: 4.5 OVERFITTING IN BO FOR HYPERPARAMETER OPTIMIZATION
text: Proposition 1 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. 8 (Appendix A.2) when tuning XGB and Random Forest on tst-census dataset.
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-validation on small datasets and one with medium-sized datasets. Hence, we would like raise attention to the possible overfitting issue that occurs in HPO for which our method can be used as a plugin to mitigate overfitting.

heading: 5 CONCLUSION
text: Despite the usefulness of hyperparameter optimizations (HPO), setting a budget in advance remains a 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 is 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 on 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 our work will draw the attention of the HPO community to the practical questions of how to set budget in advance and how to mitigate overfitting when tuning hyperparameters in machine learning.
Ethics Statement In a 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 we presented in this work can have a positive societal impact by further reducing the cost of tuning ML models. On the other hand, BO is a general methodology to 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. (2021) as well as for care at model-deployment time.
Reproducibility Statement To improve the reproducibility, the code to rerun the experiments can be found at https://anonymous.4open.science/r/BO-early-stopping-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 A.1.1, the search spaces of the algorithms are in Appendix A.1.3 and the datasets sources and descriptions are in Appendix A.1.4.

heading: A APPENDIX

heading: A.1 EXPERIMENTS SETTING

heading: A.1.1 BO SETTING
text: We used an internal BO implementation where expected improvement (EI) together with Mat‘ern-52 kernel in the GP are used. The hyperparameters of the GP includes output noise, a scalar mean value, bandwidths for every input dimension, 2 input warping parameters and a scalar covariance scale parameter. The closest open-source implementations are GPyOpt using input warped GP 1 or AutoGluon BayesOpt searcher 2. We maximize type II likelihood to learn the GP hyperparameters in our experiments.

heading: A.1.2 ALGORITHM

heading: A.1.3 SEARCH SPACES FOR CROSS VALIDATION EXPERIMENTS
text: XGBoost (XGB) and RandomForest (RF) are based on scikit-learn implementations and their search spaces are listed in Table 1.

heading: A.1.4 DATASETS IN CROSS VALIDATION EXPERIMENTS
text: We list the datasets that are used in our experiments, as well as their characteristics and sources in Table 2. For each dataset, we first randomly draw 20% as test set and for the rest, we use 10-fold cross validations for regression datasets and 10-fold stratified cross validation for classification datasets. The actual data splits depend on the seed controlled in 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 as validation set and the rest as training set.

heading: A.2 DETAILED RESULTS
text: We first show the scatter plots of RTC and RYC scores for different automatic termination methods on HPOBench-datasets in Fig. 6 and the results on NAS-Bench-201 in Fig. 7.

heading: A.2.1 DETAILED NUMBERS OF RYC AND RTC SCORES
text: We report detailed RYC scores and RTC scores of different HPO automatic termination methods for the experiments in the main text in Table 3, Table 4 and Table 5.
1https://github.com/SheffieldML/GPyOpt 2https://github.com/awslabs/autogluon
Algorithm 1 BO for HPO with cross-validation and automatic termination Require: ModelMγ parametrized by γ ∈ Γ , data {D1, . . . ,Dk} for k-fold cross-validation,
acquisition function α(γ) 1: Initialize y∗t = +∞ and Gt = {} 2: for t = 1, 2, . . . do 3: Sample γt ∈ arg maxγ∈Γ α(γ) 4: for i = 1, 2, . . . , k do 5: Fit the modelMγ(·;D−i), where D−i = ∪j 6=iDi 6: Evaluate the fitted model yit = 1 |Di| ∑ xi,yi∈Di
`(yi,Mγ(xi,D−i)) 7: end for 8: Calculate the sample mean yt = 1k ∑ k yit,
9: if yt ≤ y∗t then 10: Update y∗t = yt and the current best γ ∗ t = γt 11: Calculate the sample variance s2cv = 1 k ∑ i(yt − yit)2
12: Calculate the variance estimate Varf̂(γ∗t ) ≈ ( 1 k + |Di| |D−i| ) s2cv from Eq. (8) 13: end if 14: Update Gt = Gt−1 ∪ γt and y1:t = y1:t−1 ∪ yt 15: Update σt, µt with Eqs. (1) and (2) 16: Calculate upper bound r̄t := min
γ∈Gt ucbt(γ)−min γ∈Γ lcbt(γ) for simple regret from Eq. (7) 17: if the condition r̄t ≤ √
Varf̂(γ∗t ) holds then 18: terminate BO loop 19: end if 20: end for 21: Output: γ∗t

heading: A.2.2 CORRELATION BETWEEN VALIDATION AND TEST METRICS
text: A.2.3 THE CHOICE OF βt
High-probability concentration inequalities (aka confidence bounds) are important to reason about the unknown objective function and are used for theoretically grounded convergence guarantees in some (GP-UCB-based) BO methods (Srinivas et al., 2010; Ha et al., 2019; Kirschner et al., 2020; Makarova et al., 2021). There, βt stands for the parameter that balances between exploration vs. exploitation and ensures the validity of the confidence bounds. The choice of βt is then guided by the assumptions made on the unknown objective, for example, the
objective being a sample from a GP or the objective having the bounded norm in RKHS (more agnostic case used in Section 3).
In our experiments, we follow the common practice of scaling down βt which is usually used to improve performance over the (conservative) theoretically grounded values (see e.g., Srinivas et al. (2010); Kirschner et al. (2020); Makarova et al. (2021)). Particularly, throughout this paper, we set βt = 2 log(|Γ|t2π2/6δ) where δ = 0.1 and |Γ| is set to be the number of hyperparameters. We then further scale it down by a factor of 5 as defined in the experiments in Srinivas et al. (2010). We provide an ablation study on the choice of βt in Fig. 9.

Review summaries:
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.

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. 

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.