UQ-Guided Hyperparameter Optimization for Iterative Learners

Authors: jiesong  liu
feng  zhang
jiawei  guan
xipeng  shen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 16:20:07

Abstract: Hyperparameter Optimization (HPO) plays a pivotal role in unleashing the potential of iterative machine learning models. This paper addresses a crucial aspect that has largely been overlooked in HPO: the impact of uncertainty in ML model training. The paper introduces the concept of uncertainty-aware HPO and presents a novel approach called the UQ-guided scheme for quantifying uncertainty. This scheme offers a principled and versatile method to empower HPO techniques in handling model uncertainty during their exploration of the candidate space.
By constructing a probabilistic model and implementing probability-driven candidate selection and budget allocation, this approach enhances the quality of the resulting model hyperparameters. It achieves a notable performance improvement of over 50\% in terms of accuracy regret and exploration time.

Main paper: 
 introduction: 
 Hyperparameter optimization (HPO) is essential for unleashing the power of iterative machine learning models [4, 18, 40] . Hyperparameters include traditional parameters like learning rates and more complex ones like neural architectures and data augmentation policies. For iterative learners (multi-fidelity and early stopping methods specifically), practitioners can obtain intermediate validation loss after each iteration and use them for model assessment; the main goal of HPO is to explore a vast candidate space to find candidates that lead to optimal model performance.There are many designs in the literature to solve the HPO problem. Successive Halving (SH) [19] , for example, terminates training of candidate configurations with poor performance early so as to save computing resources for more well-behaved candidates. Bayesian optimization [17, 34] , another optimization method, uses a surrogate model to guide the selection of candidate configurations for assessment.There is however a lack of systematic treatment of an important factor in HPO designs, the uncertainty inherent in the dynamics of the training process of iterative machine learning applications. Because of the uncertainty, a model with a candidate hyperparameter configuration (or candidate in short) performing poorly in an early stage of its training could turn out to be the best model after convergence. Such candidates are however likely to be stopped from proceeding further or be completely discarded by existing HPO methods in the early stages, because their selections of candidates are mostly based on the currently observed performance, for lack of a way to treat the uncertainty properly. In 100 experiments of Successive Halving, for instance, the actually best candidates were discarded in the first 8-22 iterations of training, causing 48% performance regrets in validation loss (details in Section 3.1 Figure 1 and Section 4 Figure 3 ). This paper introduces model uncertainty into the design of HPO methods for iterative learners and establishes the concept of uncertainty-aware HPO. At the core of uncertainty-aware HPO is a novel uncertainty quantization (UQ) guided scheme, named UQ-guided scheme, which unifies the selection of candidates and the scheduling of training budget-two most important operations in HPO-into a single UQ-based formal decision process. The UQ-guided scheme builds on a probabilistic uncertainty-based model, designed to approximate the statistical effects of discarding a set of candidates at the end of a step in HPO. It uses a lightweight method to efficiently quantify model uncertainty on the fly. It offers a principled, efficient way for HPO to treat model training uncertainty.As a general scheme, the UQ-guided scheme can be integrated into a variety of HPO methods for iterative learners, especially DNNs. This paper demonstrates its usefulness and generality for DNNs by integrating it into four existing HPO methods. Experiments on two widely used HPO benchmarks, NAS-BENCH-201 [9] and LCBench [42] , show that the enhanced methods produce models that have 21-55% regret reduction over the models from the original methods at the same exploration cost. And those enhanced methods need only 30-75% time to produce models with accuracy comparable to those by the original HPO methods. The paper further gives a theoretical analysis of the impact of the UQ-guided scheme for HPO. 
background and related work: 
 Many studies are committed to solving the HPO problem for iterative learners efficiently [26, 20, 29, 39, 41] . Bayesian optimization, early stop-based mechanisms, and multi-fidelity optimizations are some important approaches.Bayesian Optimization (BO). BO is a sequential design strategy used to optimize black-box functions [34, 17, 11] . In HPO scenarios, it can be used as a surrogate model to sample high-quality candidates.Early Stop Mechanisms. Early stop-based approaches can be effective since they evaluate different candidates during training and make adaptive selections accordingly [2, 8, 35] . The early stopping mechanism, which stops the training of poorly-performed candidates early, has been widely employed in the HPO community including Successive Halving (SH) [19] and Hyperband (HB) [25] ; BOHB [11] combines both BO and HB methods to take advantage of both the BO surrogate model and the early stopping mechanism.Multi-fidelity Optimizations. Multi-fidelity evaluation focuses on using low-fidelity results trained with small resources to accelerate the evaluation of candidates [2, 3, 8, 22, 23, 38, 21, 35, 36, 14, 26] . Sub-sampling (SS) [15] is proposed mainly using multi-fidelity methods to collect high-quality data to select good configurations without early stopping.Model Uncertainty in HPO. Various optimization methods in HPO scenarios focus on specific training metrics to assess candidate performance. However, these methods typically overlook the uncertainty in the candidate selection process. Machine learning models inherently have approximation uncertainties [5, 6, 10, 12, 24, 28, 31] . Some HPO designs sample the candidate space based on distributions on the effect of each hyperparameter dimension on the quality of the candidates, but without considering the uncertainty in the model training process. For example, one of the studies [33] separates candidates into "good" or "bad" groups in order to build the distributions. The separation is based on the same deterministic metrics as other HPO methods use, giving no consideration of the uncertainty in model trainings. The only work we find that considers uncertainty in training metrics [32] selects configurations for further training based on its assessment of the upperbound of those configurations. In each round, the configurations it chooses are those that, considering the best possible performance at the last iteration, show a smaller validation loss than the validation loss current best configuration shows. The selection treats model uncertainty preliminarily and does not use it to guide the allocation of training budget. We compare other related works in Appendix E. 
uncertainty quantification (uq)-guided hyperparameter optimization: 
 This section gives an exploration of model uncertainty, introduces UQ-guided scheme for incorporating UQ into the design of HPO, discusses examples of ways to use the UQ-guided scheme to enhance existing HPO methods, and theoretically analyzes its effects.Uncertainty in iterative machine learning originates mainly from two factors: inherent noise in the data and the variability of model predictions due to restricted knowledge [16, 1] . Since data uncertainty is constant, it is the variability in model predictions, referred to as model uncertainty, that primarily influences decisions on HPO. To estimate the model uncertainty, we can incur small perturbations to the model, evaluate these model variants, and calculate the variance of the results as the approximation for the model uncertainty [16] .Figure 1 shows how the model uncertainty affects the quality of the returned candidate. In a given SH run, half of the candidates are eliminated at each checkpoint marked by a vertical red dashed line. The solid blue line represents the best validation loss up to the current point, while the orange dashed line signifies the true quality (in terms of validation loss after convergence) of the candidates SH retains at that specific juncture. From the figure, we see that in every round, SH discards the actually best candidates, causing a continuous increase of the regret. The reason is that the discarding decision of SH is solely based on the current validation loss, but model uncertainty, particularly pronounced in the early stages, obfuscating the true model potential. We explain how we quantify model uncertainty, and how, based on it, at any point of time, estimate the performance and uncertainty of a candidate model when its training converges.High efficiency is essential here as the UQ happens during the HPO process. We employ a lightweight approach to conduct the UQ efficiently on the fly, as explained next.Let Our objective here is a way that can, at any point in the HPO process, estimate σ * 2 c and µ * c for a candidate model configured with γ c . Our solution leverages the validation history in the HPO process, ℓ(y, M 1 γc (X)), • • • , ℓ(y, M t γc (X)), to construct an estimated loss curve, explained as follows. Decomposition of momentum and the underlying structure of the metric. This part uses breakdowns to characterize the loss curve and introduces the objective function we want to minimize to estimate the curve parameters. The first component, referred to as momentum, models the decaying trend of the loss curve. The second component is the bias term for each candidate's loss curve; it models a latent effect underlying the hyperparameter space by allowing correlation among the candidates. The details are as follows.γ 1 , γ 2 , • • • , γ K ∈ Γ be K candidatesTypically a candidate in HPO can be represented as a vector. We use a set U r ⊂ R r to represent the candidates {γ i , i ∈ [n]}; r > 0 is the vector length. For modeling the loss curve, we set k t ∈ R L as a vector whose elements are functions of training epochs t = 1, 2, • • • . (In our experiments, we set k t = [t -1/2 , t -1 ], for the general decreasing trend of loss curves as training epochs increase.) We model metric ℓ u t of candidate u ∈ U r at time t as the summation of the impact from three sources:EQUATIONwhere η u and Z are the parameter vectors to determine. The three components in Equation 3.1 are (1) the momentum part (k ⊤ t η u ) that denotes the contribution from the trends in the loss curve of the training specific candidate model variant, (2) the contribution from the underlying model structure (u ⊤ Z), and (3) the noises by other elements ϵ u t , which is asssumed to follow a Gaussian distribution N (0, σ 2 t ) independent of each other and of Z. For a candidate u ∈ U r , let α u = u ⊤ Z. The loss curve parameters {α u , η u } can be determined by optimizing a weighted least squares objectiveG = min α u ,η u T t=1 F k j=1 w jt (ℓ u jt -α u -k ⊤ t η u ) 2 (3.2)where w jt = For a given candidate u (for better readability, we omit the superscript u in the notations in the following discussion), the weighted least squares problem can be formulated as solving the equation W1 2 v = W 1 2 Aβ for β with W ∈ R D×D being a diagonal matrix of weights W dd = 1 Ft d σ 2 t d . A = [1 K], K ∈ R D×(L+1) with K[d, :] = k ⊤ t d , and β ⊤ = [α η ⊤ ]. The empirical estimate of σ 2i is computed as the variance of the loss in the recent several epochs of i-those instances can be regarded as results of small perturbations to the model at epoch i.Solving the weighted least square objective, we have the estimator as β = (A ⊤ WA) -1 (A ⊤ Wv). The covariance of the estimator is given byΣ β = (A ⊤ WA) -1 .Since the estimated curve is given by v(t) = [1 k ⊤ t ] β, the variance of this estimation is given byσ2 (t) = [1 k ⊤ t ]Σ β 1 k t .With the formulas for v(t) and σ2 (t), we can then approximate the distribution of ℓ(y, M * γi (X)) as N (v(N ), σ2 (N )) for a large N value (N = 200 in our experiments).Algorithm. Based on the analysis, we devise an iterative algorithm to compute the estimated loss and variance. Without the loss of generality, we make the following assumption. Assumption 1. There exist positive constants u such that for any r, max u∈Ur ∥u∥ ≤ u, and the set ofcandidates U r ⊂ R r has r linearly independent elements b 1 , • • • , b r .The algorithm goes as follows. At the beginning of HPO, it sets Z with a random vector. At the end of each epoch, it conducts the following two operations. First, it solves the weighted least squares objective 3.2 for each of the r candidates (mentioned in Assumption 1) by following the formulas described earlier in this section, with the current Z value being used. Second, for p = 1, 2, • • • r, it observes the metrics X bp (t) = ℓ bp t -k ⊤ t ηbp and refines the ordinary least square estimate for Z as follows:Z = r p=1 b p b ⊤ p -1 r p=1 b p X bpAt the end of an HPO round (e.g., at the halving time in SH), it performs the first step for every candidate model to compute the estimated distributions of their ℓ(y, M * γi (X)), so that the HPO can use the estimates to select promising candidates to continue in the next round.We next show how to use the approximated loss and uncertainty to compare two candidates: Definition 1 (UQ-guided comparison of candidates). UQ-guided comparison of candidates compares two candidates based on the probability that the validation loss of the converged model γ c1 is lower than that of γ c2 , represented as follows based on the approximation from the current validation losses and uncertainty of the two candidates: P = Pr ℓ(y, M * γc 1 (X)) > ℓ(y, M * γc 2 (X)) ℓ(y, Ml i ~N (µ i , σ i 2 ) l 1 l 2 l KFigure 2 : Illustration of using UQ-guided scheme to enhance Successive Halving. The goal is to select an optimal hyperparameter configuration from K candidates. It involves multiple rounds. R is the predefined budget resources (e.g., training epochs) for each round. For the first round, K candidates each get trained for R K epochs. Based on the observed validation loss and the quantified uncertainty for each candidate, our method represents each candidate's converged loss with a probability distribution. From that, it constructs a confidence curve, capturing the probability that the best configuration is among the current top k candidates for 1 ≤ k ≤ K. From the curve, it then calculates f ((µ i , σ 2 i ) K i=1 , k), which captures the effects of keeping k top candidates (1 ≤ k ≤ K) for the next round, by considering the tradeoff between the risks of discarding the best candidate and the training budget each top candidate can get. From that, it identifies the best k value, discards the least promising K -k candidates, and enters the next round. The process continues until the total budget is used up.The main idea of Definition 1 is to use the current validation loss history and quantified uncertainty to approximate the converged validation loss, so that we compare two candidates -more precisely, we compute the probability that one candidate is better than the other -based on the probability distribution of their converged validation loss. For example, if the approximated loss and uncertainty of two candidates γ j and γ k , at epoch t, are (µ j , σ j ) and (µ k , σ k ), using converged validation loss as the metric, we have Pr(ℓ(y,M t γj (X)) > ℓ(y, M t γ k (X)))= Φ µ k -µj √ σ 2 j +σ 2 k, where Φ denotes the cumulative distribution function (CDF) of the standard normal distribution.We next present UQ-guided scheme, a principled way to use UQ to guide HPO.Figure 2 illustrates how UQ-guided scheme works in HPO. For the purpose of clarity, we base our explanation of the scheme on HPO that uses early stop mechanisms, but will show in Section 3.5 that the scheme is general, applicable to other HPO methods for iterative learners as well.The original HPO method, Successive Halving [19] , evaluates and eliminates candidates over multiple rounds. At the end of each round, it drops those candidates regarded as unpromising. With our UQ-guided scheme, at the end of each round, the scheme derives a confidence curve from the current probabilistic model, and uses a discarding mechanism to drop candidates that are unlikely to perform well after convergence. In contrast to the original HPO that drops a fixed amount (or fraction) of candidates in each round, the UQ-guided scheme carefully calculates the number of candidates to drop in a round based on the probabilistic model such that the expected quality of the HPO outcomes can be maximized, as explained later.The UQ-guided scheme respects the HPO budget-that is, the total amount of time usable by the HPO for identifying the best candidate. By default, it works around the given budget constraint: the budget for each round (R) equals the total budget divided by the number of rounds. We next discuss each step.The concept of confidence curve is central in UQ-guided HPO. Define[n] = {1, 2, • • • , n}.Definition 2 (Confidence curve). At epoch t, we evaluate each candidate's performance and sort them based on validation loss. A confidence curve C is a trajectory of a series of probabilities, {P k |k ∈ [n]}, that depicts the probability that the optimal configuration (with the lowest loss after convergence) is among the first k configurations. For k ∈ [n], P k can be expressed asP k = Pr min(ℓ(y, M * γ1 (X)), • • • , ℓ(y, M * γ k (X))) ≤ min(ℓ(y, M * γ k+1 (X)), • • • , ℓ(y, M * γn (X))) .The confidence curve is derived based on joint probability distribution in the following way. Suppose there are n candidates. At the end of a certain round, the probabilistic model returnsn pairs of (µ 1 , σ 1 ), (µ 2 , σ 2 ), • • • , (µ n , σ n ) as estimations for ℓ(y, M * γ1 (X)), ℓ(y, M * γ2 (X)), • • • , ℓ(y, M * γn (X)). For simplicity, assume that µ 1 < µ 2 < • • • < µ n , and σ 1 = σ 2 = • • • = σ.Let Φ and ϕ be the CDF and PDF of the standard normal distribution. For k = m, we can calculateP m = ∞ -∞ 1 σ m i=1 ϕ( y+µi σ ) Φ( y+µi σ ) • n i=1 Φ( y + µ i σ )dy. (3.4)The details of obtaining Equation 3.4 are in Appendix A.1.The next step is to decide, at the end of each round, the appropriate value of k, which determines how many (n -k) lowest-ranked candidates will be discarded in this round. Our scheme decides k based on the confidence curve: choosing the smallest k that satisfies P k ≥ τ , where τ is a parameter determined by our scheme adaptively as follows.Choosing τ . At the end of round i, we have the confidence curveC i (P i 1 , P i 2 , • • • , P i n )that is the trajectory of a series of probabilities. We quantify how τ influences the probability for the HPO to select the best candidate.Let τ i be the value of τ for round i, k i be min{k : C i (P k ) ≥ τ i }. As the scheme discards the worst n -k i candidates and further trains the best k i candidates in round i + 1, we can derive the confidence curve of round i + 1 as C i+1 (P i+11 , P i+1 2 , • • • , P i+1ki ) based on those selected k i candidates. Since we want to quantify the effect of τ on the probability that the scheme returns the best candidate (that is, to suppose round i + 1 is our final round), P i+1 1 is the target we desire to maximize. Define ξ i to be the current conditionEQUATION. We want to use a selector functionΨ : D → [0, 1] where D = ([0, ∞) × [0, ∞)) n × [0, 1]. Ψ takes ξ i as input and returns an optimal τ i :Ψ(ξ i ) = arg max τ i ∈[0,1] {f (ξ i , τi)}. (3.5)The effect of τ i on f manifests through its influence on the number of candidates k i retained in the subsequent round, and can be ultimately broken down into the influence of (1) exploration, meaning keeping more candidates in the next round can reduce this round's discarding error, and(2) exploitation, meaning keeping fewer candidates in the next round can allow each candidate to receive more training time (recall that the training time budget is fixed for each round) and hence will increase the reliability of the validation at the end of the next round.Exploration. If k i drops by 1 to k ′ i , according to the definition of the confidence curve, the probability that the final optimal configuration is among the remaining candidates we keep drops by ∆c ↓ = P ki -P k ′ i : Let ζ be the coefficient that relates the increase in the number of training epochs to its corresponding effect on confidence. Using an approach similar to that employed in formulating the confidence curve,EQUATIONζ = ∞ -∞ 1 σ -∆tσ ϕ( y + µ1 σ -∆tσ ) • k i i=2 Φ( y + µi σ -∆tσ )dy - ∞ -∞ 1 σ ϕ( y + µ1 σ ) • k i i=2 Φ( y + µi σ )dy (3.7)where t represents the current total number of epochs and ∆ t σ represents the reduction in the uncertainty σ that would result from training each candidate for one additional epoch. The specifics for Equations 3.6 and 3.7 can be found in Appendix A.2. Given that b increases byR k ′ i -Rki , the overall influence of exploitation on the probability of selecting an optimal candidate is ∆c↑ = R ki(ki-1) ζ.Let ζ(k i , ξ i ) be the confidence increase, given condition ξ i , when each of the k i candidates gets a unit extra training budget. C i (P k ), k ∈ [n] are the confidence curves. Balancing exploration and exploitation leads to a sweet point where ∆c ↓ = ∆c ↑ . That gives the way to derive the appropriate value for τ , which just needs to make the following hold:P k i -P k i -1 = R ki(ki -1) ζ(ki, ξ i ).(3.8)We consider how the method performs in terms of identifying the best candidate. For convenience, we let ℓ i,t be the approximation of the converged loss for the model with hyperparameter γ i at time t. For each i, assume ν i = lim τ →∞ ℓ i,τ exists. The goal is to identify arg min i ν i . Without loss of generality, assume thatν 1 < ν 2 ≤ • • • ≤ ν n .The assumption that lim τ →∞ ℓ i,τ exists implies that as τ grows, the overall gap between ℓ i,τ and ν i decreases. Let σ t = f (t) be the model uncertainty at epoch t. We then introduce a random variable that characterizes the approximation error of ℓ i,t relative to ν i , modeling it as a distribution that incorporates t as a parameter:X t = ℓ i,t -ν i , X t ∼ N (0, σ 2 t ) ∀t.By applying Chebyshev inequality, we havePr |ℓi,t -νi| > νi -ν1 2 ≤ 4σ 2 t (νi -ν1) 2 = 4f (t) 2 (νi -ν1) 2 i = 2, • • • , n.(3.9)Let A denote the event ℓ i,t > ℓ 1,t , then by Equation 3.9Pr(A) = Pr (ℓi,t -νi) + (ν1 -ℓ1,t) + 2 • ( νi -ν1 2 ) > 0 ≥ 1 - 4f (t) 2 (νi -ν1) 2 2 .(3.10) Equation 3.10 tells us that ℓ i,t > ℓ 1,t has a high probability with respect tot if f (t) ∈ O(t -1/4 ) (see Lemma in Appendix C).That is, comparing the intermediate values at a certain time t is likely to establish an order similar to the order of the final values of ν i and ν 1 .The following theorem is stated using the abovementioned quantities with proofs in Appendix C.1.Theorem 1. Let n be the number of total candidates, and ν i = lim τ →∞ ℓ i,τ . For a given c > 0, there exists a T > 0 s.t.n i=2 (1 -( 4f (T ) 2 (νi-ν1) 2 ) 2 ) > 1 -c . If the round budget R > T • n, then the best candidate is returned with probability P > (1 -⌊ B R ⌋c)(1 -c),where B is the total budget.In comparison, the bound in the UQ-oblivious approach is as follows:EQUATIONz ob = 2⌈log 2 (n)⌉ max i=2,...,n i 1 + γ -1 ( νi-ν1 2 , δ) ≤ 2⌈log 2 (n)⌉(n + i=2,...,n γ -1 ( νi-ν1 2 , δ)).If the UQ-oblivious early stopping method is run with any budget B ob > z ob then the best candidate is returned with probability P ob > 1 -nδ.Example 3. Consider f (t) = 1 t . According to Theorem 2, if B ob > 2⌈log 2 (n)⌉(n + i=1,...,n γ -1 ( νi-ν12 , δ)), the UQ-oblivious method can return the best candidate with probability over1 -nδ. But if B U Q ≃ γ -1 ( ν2-ν12 , δ) • n1 , the UQ method can return the best candidate with probability over 1 -nδ. As shown in Appendix C.2, Theorems 1 and 2 together show that the UQ approach guarantees the same probability of identifying the optimal candidate as the UQ-oblivious counterpart with a smaller budget lowerbound B (see Corollary 6).The UQ-guided scheme is a general approach to enhancing HPO with uncertainty awareness. We next explain how it is integrated into several existing HPO methods to transform them into UQ-guided ones, yielding a UQ-guided HPO family. In the following, we use the suffix "plus (+)" to indicate the UQ-guided HPO methods. Successive Halving plus (SH+) is derived from the early stop-based HPO design Successive Halving (SH) [19] . Algorithms 1 and 2 in Appendix A.3 show the pseudo-code. Given total budget B and round budget R and an initial K, SH+ first trains K candidates each with the initial b = ⌊ R K ⌋ units of budget, and ranks them by the evaluation performance. Then SH+ updates K based on Section 3.3.2 and keeps the top K configurations according to the UQ-guided scheme (OracleM odel in Algorithms 1 and 2), and continues the process until the budget runs out. Hyperband plus (HB+) originates from the popular HPO design Hyperband (HB). HB is an HPO method trying to better balance exploration and exploitation than SH does [25] by adding an outer loop for grid search of the value of K. HB+ simply extends HB by using SH+ rather than SH as its inner loop, changing the target of the grid search to the initial value of K. Bayesian Optimization and Hyperband plus (BOHB+) is developed from BOHB [11] . BOHB is similar to HB except that it replaces the random sampling from the uniform distribution with BO-based sampling. BOHB+ makes the corresponding changes from HB+ by adopting BO-based sampling for its outer loop. Sub-sampling plus (SS+) is derived from the Sub-sampling (SS) algorithm [15] . It showcases the applicability of the UQ-guided scheme to non-early stop-based methods. Similar to other methods, in each round, SS also chooses candidates for further training based on its assessment of the potential of those candidates. But unlike the other methods, SS does not discard any candidates, but keeps all in play throughout the entire HPO process. In each round, the candidates it chooses are those that show smaller validation loss than the most trained candidate shows. If there is none, it trains only the most trained candidate in that round. SS+ integrates the UQ-guided scheme into the candidate selection process of SS. When SS+ compares a candidate (c i ) against the most trained candidate (c m ), rather than checking their validation losses, it uses the UQ-guided scheme to compute the probability for the convergence loss of c i to be smaller than that of c m and checks whether the probability is over a threshold τ (0.9 in our experiments), that is, Pr(ℓ(y,M * γc m (x)) ≥ ℓ(y, M * γc i (x))) ≥ τ . 
experiments: 
 We conduct a series of experiments on the four UQ-guided HPO methods to validate the efficacy of the UQ-guided scheme for HPO.Methodology. To check the benefits of the UQ-guided scheme for HPO, we apply the proposed UQ-guided HPO family to different HPO benchmarks, including NAS-BENCH-201 and LCBench, each for 30 repetitions, to measure the performance for different hyperparameter optimization tasks, and compared those with their original UQ-oblivious versions.Platform. Our experiments are conducted on a platform equipped with an Intel i9-9900k CPU and an NVIDIA GEFORCE RTX 2080 TI GPU. The CPU has 8 cores, each of which can support 2 threads. The GPU has 4,352 cores of Turing architecture with a computing capability of 7.5. The GPU can achieve a maximum memory bandwidth of 616 GB/s, 0.4 tera floating-point operations per second (TFLOPS) on double-precision, and 13 TFLOPS on single-precision.Workloads. We evaluate the UQ-guided methods on two real-world benchmarks. Nas-Bench-201 [9] (CC-BY 4.0) encompasses three heavyweight neural architecture search tasks (NAS) on CIFAR-10, CIFAR-100, and ImageNet-16-12 (CC-BY 4.0) datasets. In addition, we investigate the performance of optimizing traditional ML pipelines, hyperparameters, and neural architecture in LCBench [42] .For example, we optimized 7 parameters for the Fashion-MNIST dataset [7] , where the resource type is determined by the number of iterations. Additional information regarding these benchmarks can be found in Appendix F. In this context, one unit of budget equates to a single training epoch, and by default, the total HPO budget (B) allocated for each method is 4 hours. metrics, namely top-1 rank on different trials, top-1 rank on different fractions of budgets, and regret on different fractions of budgets. The fraction of budgets denotes the portion of the budget that we allocate for that particular experiment compared to the standard full budget. Top-1 rank refers to the real ranking of the candidate ultimately chosen by the method. Regret (%) refers to the accuracy difference between the returned candidate and the real best candidate. In Figure 3 , the average results of 30 repetitions are reported. For the right two columns, we also report the uncertainty bands, defined as the interval between the 30th and 70th percentiles. The benefits of the UQ-guided scheme are obvious, both for individual trials and across different fractions of budgets. It brings a 21-55% regret reduction. Similar results are observed on other benchmarks (LCBench results shown in Appendix G).Table 1 provides the fraction of the total exploration time needed for the UQ-guided methods to achieve comparable model accuracy as the original methods do. The UQ-guided methods need much less time than their counterparts to obtain a similar performance. For instance, SH+ achieves the same average regret of 5% on NAS with only half of the budgets required by SH. These results indicate that the UQ technique can conduct HPO efficiently and effectively.  
conclusion: 
 This paper points out the importance of systematic treatment to the uncertainty in model trainings for HPO. It introduces a novel scheme named UQ-guided scheme, which offers a general way to enhance HPO methods for DNNs with uncertainty awareness. Experiments demonstrate that the UQ-guided scheme can be easily integrated into various HPO methods. The enhanced methods achieve 21-55% reduction of regret over their original versions, and require only 30-75% time to identify a candidate with a matching performance as the original methods do. The paper in addition provides a theoretical analysis of the effects of the UQ-guided scheme for HPO.The key characteristic of the UQ method is the necessity to rank multiple learners during the HPO process. Gradient-based HPO methods [30] , for instance, may not benefit from our UQ-guided scheme because of their sequential properties. One limitation of this paper is that it is mostly suitable for iterative learners, and needs adaptations for other learners: To go beyond, it could be, for instance, applied to the model selection work in previous studies [31] that use training dataset size as the budget dimension. In this case, the learner does not need to be iterative; the selection is based on the validation loss history trained with incremental dataset sizes. The UQ component can still guide the configuration selection and budget allocation in the HPO process.Overall, this study concludes that UQ is important for HPO to consider, simple on-the-fly UQ goes a long way for HPO, and the UQ-guided scheme can serve as a general effective scheme for enhancing HPO designs.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We include them in the supplemental material. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: See Section 4.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We conducted 30 repetitions for the experiments. For the right two columns in Figure 3 , besides the average results of the repetitions, we also report the interval between the 30th and 70th percentiles.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] .Justification: See Section 4.1.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: As stated in Section 5, our work is a general algorithm aiming at optimizing HPO and belongs to a foundational research; its societal impacts are neutral.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]  
 
 Appendix: The following contents detail how to compute the confidence curve C(P 1 , P 2 , • • • , P n ) based on current validation loss and quantified uncertainty of the n candidates.Let Y be the random variable denoting the negation of the lowest converged validation loss:Y = max(-ℓ(y, M * γ1 (X)), -ℓ(y, M * γ2 (X)), • • • , -ℓ(y, M * γn (X))). Since ℓ(y, M * γi (X)) ∼ N (µ i , σ 2 i ), the cumulative distribution function (CDF) of Y , F Y (y), is F Y (y) = Pr(Y ≤ y) = Pr(-ℓ(y, M * γ1 (X)) ≤ y, -ℓ(y, M * γ2 (X)) ≤ y, • • • , -ℓ(y, M * γn (X)) ≤ y) = n i=1 Φ( y + µ i σ ) = exp( n i=1 ln Φ( y + µ i σ )).Accordingly, the probability density function (PDF) of Y , f Y (y), isf Y (y) = dF Y (y) dy = 1 σ n i=1 ϕ( y+µi σ ) Φ( y+µi σ ) • n i=1 Φ( y + µ i σ ).Now we can construct the confidence curve by calculating each P k (k ∈ [n]). For k = m, P k can be expressed asP m = Pr(min(ℓ(y, M * γ1 (X)), • • • , ℓ(y, M * γm (X))) ≤ min(ℓ(y, M * γm+1 (X)), • • • , ℓ(y, M * γn (X)))).Let ℓ(y, M * γ1 (X)), • • • , ℓ(y, M * γn (X)) be mutually independent, thusP m = ∞ -∞ f Y (y) Pr(-N (µ m+1 , σ m+1 ) ≤ y, • • • , -N (µ n , σ n ) ≤ y)dy = ∞ -∞ f Y (y)Φ( y + µ m+1 σ ) × • • • × Φ( y + µ n σ )dy = ∞ -∞ 1 σ m i=1 ϕ( y+µi σ ) Φ( y+µi σ ) • n i=1 Φ( y + µ i σ )dy.(A.1)Equation 3.6 can be calculated by directly subtracting P ki by P ki-1 :∆c ↓ = ∞ -∞ 1 σ ki i=1 ϕ( y+µi σ ) Φ( y+µi σ ) • n i=1 Φ( y + µ i σ )dy - ∞ -∞ 1 σ ki-1 i=1 ϕ( y+µi σ ) Φ( y+µi σ ) • n i=1 Φ( y + µ i σ )dy = ∞ -∞ 1 σ • ϕ( y+µ k i σ ) Φ( y+µ k i σ ) • n i=1 Φ( y + µ i σ )dy.ζ is the coefficient that relates the increase in the number of training epochs to its corresponding effect on confidence. Consider a working round that starts with k candidates. We have approximations at the end of the round for the converged loss ℓ(y, M* γi (x)) ∼ N (µ i , σ 2 ) for i ∈ [k].Here, t denotes the epochs. Letting each candidate train one extra unit of resource results in lower uncertainty, thus increasing the f score. First compute f (ξ, τ ) at epoch t:f (ξ, τ ) t = ∞ -∞ 1 σ ϕ( y + µ 1 σ ) • k i=2 Φ( y + µ i σ )dy. (A.2)If each configuration is trained with one extra unit of resource (a total of t + 1 epochs), model uncertainty would be reduced. We use the same µ i to approximate the converged validation loss for t + 1 epochs, and use σ -∆ t σ as an approximation for model uncertainty. Here ∆ t σ is the decrease in model uncertainty that is determined through offline profiling with details in Section D. This approximation leads us to f (ξ, τ ) at epoch t + 1 asf (ξ, τ ) t+1 = ∞ -∞ 1 σ -∆ t σ ϕ( y + µ 1 σ -∆ t σ ) • k i=2 Φ( y + µ i σ -∆ t σ )dy. (A.3)Subtracting Equation A.3 by Equation A.2 gives us the result in Equation 3.7:ζ = f (ξ, τ ) t+1 -f (ξ, τ ) t = ∞ -∞ 1 σ -∆ t σ ϕ( y + µ 1 σ -∆ t σ )• k i=2 Φ( y + µ i σ -∆ t σ )dy- ∞ -∞ 1 σ ϕ( y + µ 1 σ )• k i=2 Φ( y + µ i σ )dy.A.3 Pseudo-code for UQ-Guided Hyperparameter Optimization (SH+)Algorithm 1 UQ-Guided Hyperparameter Optimization (SH+) Input: Total budget B, the set of K configurations Γ = {γ 1 , γ 2 , • • • , γ K },, M t2 γ2 , • • • , M t K γ K K = OracleM odel(M t1 γ1 , M t2 γ2 , • • • , M t K γ K ) Keep top K candidates until total budget B runs outAlgorithm 2 OracleM odel for determining K candidates into the next round.Input: K instances of Machine Learning models M t1 γ1 , M t2 γ2 , • • • , M t K γ KOutput: A new K that tells the model how many candidates to keep Get a τ from the probabilistic model Construct the confidence curve 4 Pseudo-code for UQ-Guided Hyperparameter Optimization (HB+) Algorithm 3 Hyperband plus (HB+) C(P 1 , P 2 , • • • , P K ) based on ℓ(y, M t1 γ1 (X)), ℓ(y, M t2 γ2 (X)), • • • , ℓ(y, M t K γ K (X)) return min{k : P k > τ } A.Input: Total budget B, the set of K configurations Γ = {γ 1 , γ 2 , • • • , γ K }, maximum budget R,Input: Total budget B, the set of K configurations Γ = {γ 1 , γ 2 , • • • , γ K }, maximum budget R, minimum budget b, ratio η (default η = 3) Output:The configuration with the best performance r = 1, evaluate all configurations with budget b. for r = 2 to ⌊log η (R/b)⌋ do Select γ ζ with the most observations.I ′ = {k : c k ∈ Γ\γ ζ , γ k ⪯ γ ζ ∧ pass UQ check} if I ′ == ∅ then Evaluate γ ζ with budget η r b. else Evaluate γ k with budget η r b for each k ∈ I ′ . end if end forWe have been concerned with identifying the best candidate, while in practice, it is often sufficient to consider a situation where the difference between the result of candidate i ϵ (ν iϵ ) and the result of the best candidate (ν 1 ) is less than or equal to a small value ϵ. We obtain the following theorem with proofs in Appendix C.3. Theorem 4. For a budget B > R and a set of n candidates, let î be the output of the UQ-guided approach. ThenE(ν î -ν 1 ) ≤ 2⌊ B R ⌋ √ 2f (R) √ π .In comparison, îD , the output of the UQ-oblivious counterpart, satisfiesE(ν îD -ν 1 ) ≤ 2⌈log 2 (n)⌉ √ 2f (⌊ B n⌈log 2 (n)⌉ ⌋) √ π .Example 5. Consider f (t) = 1 t . Substitution of f (t) in Theorem 4 can clearly show a smaller upperbound of the UQ-guided approach than that of the UQ-oblivious counterpart (see Appendix C.3 for details).The theorems provide some insights into the theoretical benefits of the UQ-guided scheme. But it is worth noting that neither this bound comparison nor the budget bound comparison in Example 3 is sufficient to prove that the UQ-guided approach definitely would outperform the UQ-oblivious approach, a reason for the empirical comparisons in Section 4.In this section, we provide proofs for the theorems presented in Section 3.4. At the end of the proof, we let f (t) = 1 t and obtained the results in Example 3 and Example 5. The Lemma stated next will prove to be useful. Lemma 1. For i > 1, if min{t 1 , t i } > t, then we have a high probability that ℓ i,ti > ℓ 1,t1 with respect to t if f (t) ∈ O(t -1/4 ).Proof. In Section 3.4, we come to the conclusion thatPr(ℓ i,t > ℓ 1,t ) ≥ 1 -( 4f (t) 2 (ν i -ν 1 ) 2 ) 2 = 1 -( 2 ν i -ν 1 ) 4 • f (t) 4 > 1 -O 1 t .This shows that the event ℓ i,t > ℓ 1,t happens with high probability with respect to t.Now consider a more general setting, where each ℓ i has its own t i :Pr(|ℓ i,ti -ν i | > ν i -ν 1 2 ) ≤ 4f (t i ) 2 (ν i -ν 1 ) 2 i = 1, • • • , n.Comparing ℓ i,ti and ℓ 1,t1 for a particular i ∈ [n] gives us the following:Pr(ℓ i,ti > ℓ 1,t1 ) = Pr((ℓ i,ti -ν i ) + (ν 1 -ℓ 1,t1 ) + 2 • ν i -ν 1 2 > 0) ≥ 1 - 4f (t 1 ) 2 (ν i -ν 1 ) 2 • 4f (t i ) 2 (ν i -ν 1 ) 2 . (C.1) Since t 1 > t and t i > t, (C.1) > 1 -O 1 t .Proof. Let S i be the set of candidates the UQ scheme evaluates at the beginning of the i-th round.We assume that the n infinitely long loss sequences [ℓ i,t ] with limits {ν i } n i=1 . We compute the probability that the algorithm includes the best candidate in the last round, namely, 1 ∈ S ⌊ B R ⌋ , and the probability that the UQ scheme returns the best candidate in S ⌊ B R ⌋ . Let r k be the round budget for each candidate in S k . R k = k j=0 r k . The probability that the best candidate is among the final kept candidate set isPr(1 ∈ S ⌊ B R ⌋ ) = 1 - r=⌊ B R ⌋ k=1 Pr(1 / ∈ S k , 1 ∈ S k-1 ) = 1 - r=⌊ B R ⌋-1 k=0 (Pr(1 ∈ S k-1 ) -Pr(1 ∈ S k , 1 ∈ S k-1 )) ≥ 1 - r=⌊ B R ⌋-1 k=0   1 -Pr i∈S k \{1} ℓ i,R k > ℓ 1,R k   . (C.2)Since the probability that ℓ 1,t is the smallest among all ℓ k,t (k ∈ [n]) is greater thann i=2 Pr(ℓi,t > ℓ1,t) ≥ n i=2 (1 - 4f (t) 2 (νi -ν1) 2 we have (C.2) ≥ 1 - ⌊ B R ⌋-1 k=0 (1 - n i=2 (1 -( 4f (R k ) 2 (ν i -ν 1 ) 2 ) 2 )) = 1 - ⌊ B R ⌋-1 k=0 (1 - n i=2 (1 -( 4f k j=0 R |Sj | 2 (ν i -ν 1 ) 2 ) 2 )) ≥ 1 -⌊ B R ⌋c.Therefore, the probability that the scheme returns the best candidate is no less thanPr(1 ∈ S ⌊ B R ⌋ ) • Pr i∈S ⌊ B R ⌋ ℓ i,R ⌊ B R ⌋ > ℓ 1,R ⌊ B R ⌋ ≥ (1 -⌊ B R ⌋c)(1 -c). (C.3)That is to say, for a given confidence threshold c, there exists a T such that as long as min{t 1 , t 2 , ..., t n } > T , then Pr(∧ i=2,...,n (ℓ i,ti > ℓ 1,t1 )) > 1 -c. Recall that in the UQ scheme design, the goal is to select an optimal hyperparameter configuration from n candidates, and each round is allocated for R resources. This means that if choose R ≥ T • n, then the best candidate is returned from the algorithm with probability P > (1-⌊ B R ⌋c)(1 -c).The representation of z ob on the right-hand-side of the inequality is very intuitive: For each i, to confirm that the final loss of the i-th candidate is greater than the best candidate's with a probability of at least 1 -δ, it is necessary to train both candidates for at least the number of steps indicated by the i-th term in the sum. Repeating this reasoning for all i justifies the sum over all candidates.Proof. First we show that, given budget z = z ob , round budget for round k satisfiesr k ≥ z |S k |⌈log 2 n⌉ -1 = 2 |S k | max i=2,...,n i 1 + γ -1 ( νi-ν1 2 , δ) -1 ≥ 2 |S k | (⌊|S k |/2⌋ + 1) 1 + γ -1 ( ν ⌊|S k |/2⌋+1 -ν1 2 , δ) -1 ≥ γ -1 ( ν ⌊|S k |/2⌋+1 -ν1 2 , δ).The last inequality is derived because⌊|S k |/2⌋ ≥ |S k |/2 -1.Let τ i := γ -1 ( νi-ν1 2 , δ). We then show that, for a time t:t ≥ τ i ⇒ t ≥ γ -1 ( νi-ν1 2 , δ) ⇔ 1 - 4f (t) 2 (ν i -ν 1 ) 2 2 ≥ 1 -δ ⇒ Pr(ℓ i,t > ℓ 1,t ) ≥ 1 -δ.The second line follows by the definition of γ -1 (ϵ, δ). Since r k ≥ τ ⌊|S k |/2⌋+1 , we can compute the following probabilityPr(1 ∈ S k+1 |1 ∈ S k ) = Pr i∈S k 1{ℓ i,R k > ℓ 1,R k } ≥ ⌊|S k |/2⌋ ≥ Pr( |S k | i=⌊|S k |/2⌋+1 1{ℓ i,R k > ℓ 1,R k } ≥ ⌊|S k |/2⌋) ≥ (1 -δ) ⌊ |S k | 2 ⌋where the first line follows by the definition of the early stopping algorithm (Successive Halving), the second by τ i being non-increasing. Namely, for all i > ⌊|S k |/2⌋ + 1, we haveτ i ≤ τ ⌈|S k |/2⌉+1 and consequently, Pr(ℓ i,R k > ℓ 1,R k ) ≥ Pr(ℓ ⌊|S k |/2⌋,R k > ℓ 1,R k ) ≥ 1 -δ.Consequently, the probability that the UQ-oblivious approach returns the optimal candidate isP ob ≥ Pr i=0,...,⌈log 2 n⌉-1 (1 ∈ S k+1 |1 ∈ S k ) ≥ ⌈log 2 n⌉-1 k=0 (1 -δ) ⌊ |S k | 2 ⌋ ≥ 1 -nδ.We show in the next Corollary that, for c = n•δ 2 , the probability P obtained in Theorem 1 is no less than 1 -nδ. Corollary 6. For the threshold c in Theorem 1 and δ in Theorem 2, let c = n•δ 2 andβ -1 (ϵ 2 , ϵ 3 , • • • , ϵ n , c) = min{T : n i=2 (1 -( f (T ) ϵi ) 4 ) ≥ 1 -c} .Then by Theorem 1 the UQ approach returns the best candidate with probability over1 -nδ if B ≃ γ -1 ( ν2-ν1 2 , δ) • n. Proof. Let T > 4 √ 2 • γ -1 ( ν2-ν1 2 , δ), we have n i=2 (1 -( 4f (T ) 2 (ν i -ν 1 ) 2 ) 2 ) > (1 - δ 2 ) n ≥ 1 - nδ 2 = 1 -c.This shows us that T > β -1 ( ν2-ν1 2 , ..., νn-ν1 2 , c). Consequently, according to Theorem 1, for B = R > T • n, the UQ approach returns the best candidate with probability(1 -c) 2 ≥ 1 -2c = 1 -nδ.The UQ-oblivious approach returns the optimal candidate with probability over 1 -nδ if the budget B ob > z ob . But the UQ approach achieves the guarantee with budget B > 4 √ 2 • γ -1 ( ν2-ν1 2 , δ) • n, which can be empirically substantially smaller than the budget required in Theorem 2.Proof. Let R k = k j=0 r k , namely, the total number of epochs allocated for each candidate in S k . We can guarantee that, for the UQ-oblivious approach, the output candidate îD satisfiesE(ν îD -ν 1 ) = E min i∈S ⌈log 2 (n)⌉ ν i -ν 1 = E ⌈log 2 (n)⌉-1 k=0 min i∈S k+1 ν i -min i∈S k ν i ≤ E ⌈log 2 (n)⌉-1 k=0 2|ν i -ℓ i,R k | + min i∈S k+1 ℓ i,R k -min i∈S k ℓ i,R k = E ⌈log 2 (n)⌉-1 k=0 2|ν i -ℓ i,R k | ≤ 2⌈log 2 (n)⌉ √ 2f (⌊ B n⌈log 2 (n)⌉ ⌋) √ π = 2 √ 2n⌈log 2 (n)⌉ 2 √ πB .by inspecting how the approach eliminates candidates and plugging in an upper bound for E(2|ν iℓ i,R k |) for all k in the last inequality. We can calculate the bound for the UQ-guided method in a similar way:E(ν î -ν 1 ) = E min i∈S ⌊ B R ⌋ ν i -ν 1 = E ⌊ B R ⌋-1 k=0 min i∈S k+1 ν i -min i∈S k ν i ≤ E ⌊ B R ⌋-1 k=0 min i∈S k+1 (ν i -ℓ i,R k+1 + ℓ i,R k+1 ) -min i∈S k (ν i -ℓ i,R k + ℓ i,R k ) ≤ E ⌊ B R ⌋-1 k=0 2|ν i -ℓ i,R k | + min i∈S k+1 ℓ i,R k+1 -min i∈S k ℓ i,R k ≤ E ⌊ B R ⌋-1 k=0 2|ν i -ℓ i,R k | + ( min i∈S k+1 ℓ i,R k+1 -min i∈S k+1 ℓ i,R k ) + ( min i∈S k+1 ℓ i,R k -min i∈S k ℓ i,R k ) ≤ E ⌊ B R ⌋-1 k=0 2|ν i -ℓ i,R k | ≤ 2⌊ B R ⌋ √ 2f (R) √ π = 2 √ 2⌊ B R ⌋ √ πR .The smaller upperbound of the UQ-guided approach than that of the UQ-oblivious counterpart in Theorem 4.A simple calculation reveals that2⌊ B R ⌋ R 2 ϵ < 2n 2 ⌈log 2 (n)⌉ 3B 2 ϵ by diving the first term by the second:2⌊ B R ⌋ Rϵ 2n⌈log 2 (n)⌉ 2 Bϵ = ⌊ B R ⌋ B R • 1 n⌈log 2 (n)⌉ 2 < 1.The last inequality holds because both B R and ⌈log 2 (n)⌉ are the number of rounds and are considered the same.Approximating ∆σ for Candidates. In our probabilistic model, ℓ(y, M * γc (X)) is approximated by a Gaussian distribution parameterized by µ c and σ c . To compute the uncertainty reduction that would result from training each candidate for one additional epoch, we consider the uncertainty as a time series in the form of (σ c (t)) T t=1 . We examine the uncertainty trendings in NAS-BENCH-201 [9] . Figure 4 shows a certain pattern of uncertainty behavior as t increases, both individually and aggregately, for different candidates.We then model (σ c (t)) T t=1 according to different phases in the following way:1. For t ∈ (0, 6), σ(t) increases. We use linear regression to fit the σ(t), namely, σ(t) = a 1 t + b 1 .2. For t ∈ (6, 50), σ(t) drops quickly. We use the exponential model to fit σ(t), namely, σ(t) = a 1 e -b1x . After obtaining the confidence curve, a threshold τ determines the number of candidates we will keep (k 1 for round 1, k 2 for round 2, and k 3 for round 3). We choose the smallest k such that P k ≥ τ for each round, proceed training with the best performed k candidates, and discard the rest configurations.4. For t ∈ (180, 200), σ(t) reverses the trend and decreases again. We use linear regression.For each launch, we sample a few candidates and train each one fully till convergence. We then use the abovementioned way to model the uncertainty behavior for the whole dataset. This makes the approximation for ∆ t σ = σ(t) -σ(t + 1) effective and efficient.An alternative way to approximate ∆ t σ is to use1 δ b∈Dt-1 (ℓ(y, M b γc (X))-E Dt-1 [ℓ(y, M b γc (X))]) 2 - 1 δ b∈Dt (ℓ(y, M b γc (X))-E Dt [ℓ(y, M b γc (X))]) 2 .Building Probabilistic Model. At any given time t, the approximation of converged validation loss follows the Gaussian distribution: ℓ(y, M * γc (X)) ∼ N (µ c , σ 2 c ). In our experiments, δ = 10, µ c is the current accuracy ℓ(y, M t γc (X)), and σ c is the unbiased estimation of the standard deviation of ℓ(y, M i γc (X)) t i=t-10 .Freeze-thaw Bayesian optimization. This paper proposes a new method to improve Bayesian optimization (BO) for HPO. It avoids the limits of the expected improvement (EI) criterion in naive BO which always favors picking new candidates rather than running old ones for more iterations. Instead of always sampling new candidates, it can also choose old candidates for further evaluation based on the modified EI in each round. This method, however, is limited to BO method. In contrast, our UQ scheme is applicable to the vast number of early stopped and multi-fidelity-based HPO methods.HyperJump improves HB in that, during HPO, it skips certain rounds for certain candidates if the risk of skipping is within a threshold. For the NAS-BENCH-201 trained on ImageNet-16-120, HJ reduces the running time compared to the original HB method (only needs a 5.3% fraction of budget to achieve close to optimal results achieved by the original HB with a standard full budget), but it does not improve the HPO performance (i.e., Top-1 Rank and Regret). In contrast, our method only needs less than a 3% fraction of the budget to achieve close to optimal results and when using around 5% fraction of budget, our method reduces the regret by 33%.Table 2 consolidates information on the datasets, hyperparameters, fidelity, and dataset sizes for Nas-Bench-201 and LCBench. The datasets for LCBench are drawn from various sources [37, 13] . We include more results on NAS-Bench-201 and LCBench. For example, Figure 10 and 11 show the results on LCBench, where we proved the consistently better performance of the UQ-guided approaches than the UQ-oblivious methods on Fashion-MNIST. Figure 10 shows the results of the validation loss while Figure 11 demonstrates the results of regret. UQ-guided approaches obtained an average of over 50% improvement over the UQ-oblivious counterparts. • The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.f ≃ g if there are constants c, c ′ s.t. cg(x) ≤ f (x) ≤ c ′ g(x).), 


Decision: This paper studies the uncertainty of the metric estimation in hyperparameter optimization. It introduces the concept of uncertainty-aware HPO and proposes the UQ-guided scheme for quantifying uncertainty. The proposed method applies to a board arrange of iterative learning methods and shows strong empirical performance.

All reviewers appreciate its theoretical analysis of the proposed method and the convincing empirical performance. Some reviewer also considers it a strength being versatile to apply to different conventional HPO algorithms.

There were some concerns in the original reviewers as follows,
1. Estimating the mean and variance of the performance metrics curve may need to take some epochs, which is not feasible with large datasets
2. The proposed method is limited to deep learning algorithms, in contrast to the claimed any iterative learner
3. Question about estimating the epistemic uncertainty decoupled from the aleatoric uncertainty
4. Lack of discussion and comparison with related work that also considers metric uncertainty

The authors feedback resolved many of those concerns, and two reviewers raised their rating to weak accept after the rebuttal, mainly due to its strong empirical performance in the experiments. The reviewers reach a consensus of acceptance.

Reviewers' concerns about point 1 and 2 above are not fully resolved from authors' response but are not considered major weaknesses against publication. I would encourage the authors to discuss the limitations more explicitly in the final revision. Also, please incorporate the clarification in the rebuttal, including the comparison with missed related work in the original version.

The following is additional comments from reviewers during the reviewer-AC discussion:

*"I still have doubts about the general applicability of the approach to any kind of iterative learner, defining a too broad scope by the title of the paper which has not been properly understood by the authors as I raised this point already in a previous revision (at another venue) of the paper.*"

"*I worry about the theoretical guarantees of approaches like SHA or Hyperband and whether they can maintain these guarantees with the changed promotion or budget allocation scheme."*

"*they didn't address the question that if $\hat{v}$ and $\hat{\sigma}^2$ and are estimated with just a few epochs, would one still observe the performance boosting. The concern I have is the performance may be unstable if and are estimated with only a few epochs.*"

Reviews: review: paper_summary: paper_summary: This paper proposed an incorporate uncertainty quantification for hyperparamter tuning (learning rate, neural architecture). It is assumed the model performance metrics of interest, such as validation error, are Gaussian, and we can use the training output of first $N$ epochs to estimate the mean and variance of the performance metrics distribution. Using the distribution, this paper proposes a UQ-guided scheme by using confidence curves to find the highest performant combinations of hyperparameters.
strength_weakness: strength_weakness: Estimating the mean and variance of the performance metrics curve may need to take some epochs.
questions: questions: 1. On page 4, it is stated that $\hat v$ and $\hat\sigma^2$ are estimated with N=200 epochs. My understanding is that the first N=200 epochs are only for estimating $\hat v$ and $\hat\sigma^2$ and the UQ-guided HPO are not used in these 200 epochs. However, I suspect we don’t have the luxury of running more than 200 epochs in some applications with large data. 

2. The $Z$ in eq (3.1) seems to model a latent effect underlying the hyper parameter space. $Z$ is initialized randomly and then updated using the equation on p.4. No further analysis about $Z$ is provided in later sections, for example, whether we can use $Z$ to measure the contribution of certain combinations of hyperparameters. If estimating $Z$ explicitly doesn’t yield any useful products, perhaps there is no need to estimate Z and we just need to estimate $\alpha_u$?

3. Theorems:
- How to interpret the assumptions of Theorem 1?
- Does Theorem 2 apply to “any” UQ oblivious method like SH, HB? If so, it may be good to comment on/verify whether these existing methods satisfy the assumptions of Thm 2.

4. Can more details about $z_ob$ in Theorem 2 be given, e.g. how to arrive at the inequality? It is unclear how to interpret this quantity.
The proof of Theorem 1 refers to two assumptions but it looks the pdf was not compiled correctly so the reference hyperlinks are missing
limitations: limitations: The work is regarding a general algorithm aiming at optimizing HPO and belongs to a foundational research; its societal impacts are neutral.
paper_summary: paper_summary: In the paper "UQ-Guided Hyperparameter Optimization for Iterative Learners" the authors present an uncertainty quantification method for optimizing the hyperparameters of iterative learners in a multi-fidelity setting. It is argued that the best possible candidate is often mistakenly discarded at some point and uncertainty quantification can help avoid such mistakes. Furthermore, it can help to identify the best-performing candidate with certainty earlier than running the entire promotion scheme of, e.g., successive halving.
strength_weakness: strength_weakness: - The authors claim that their method is working for any kind of iterative learners. However, this claim is not supported in the experimental section as only deep learning methods are considered. Therefore, it is questionable whether the same quality of results could be observed for other iterative learners, e.g., logistic regression.
- Moreover, to make their approach work, the authors need a learner that is able to quantify its epistemic uncertainty, i.e., model uncertainty. However, I do not see how you would make this work for iterative learners in general where you cannot make use of simple tricks as in deep learning models to obtain ensembles through MCMC dropout or something similar.
- It could be made clearer that the authors specifically target multi-fidelity/early stopping methods with their method.
- The writing of the paper could be improved. For example, in the introduction the authors write about "steps" but it is not clear what is meant by steps, in particular, what are "steps of exploration". In general, there are some linguistic issues throughout the paper which the authors could easily get rid off using tools like Grammarly.
- In Section 3.2 the authors formalize their setting by attributing hyperparameters to a model, however, some hyperparameters belong to the learning algorithm, e.g., weight decay or learning rate, but not to the model.
- It is somewhat strange that the plus variants (including UQ) always start better than the basic method. In particular, it seems awkward for zero budget that the proposed method can better identify the top 1 rank than the base method. Also for the regret it is unclear how UQ can help identifying a more suitable candidate if nothing is known about this candidate.
questions: questions: - How can the epistemic uncertainty be quantified for other learners?
- Why does the performance of X+ always improve already over X if there is no budget used?
- How is the uncertainty or let us say better certainty about the top 1 rank leveraged in the HPO tool? It would be quite straightforward to stop evaluating other candidates if there is enough evidence already that the top 1 candidate is correctly identified.
- If in every iteration of successive halving the amount of budget spent for this iteration is kept at a certain level, how is then the budget distributed if more candidates are to be evaluated in that iteration or could it also happen that more budget is assigned to every remaining candidate than originally planned according to e.g. successive halving?
limitations: limitations: Limitations are not sufficiently addressed. Although the authors mention in the questionaire that limitations would be addressed there is just a single sentence that it is mostly suitable for iterative learners and needs adaptions for other learners. This is definitely not a sufficient limitations discussion.
paper_summary: paper_summary: The paper presents UQ-guided scheme, an approach for hyper-parameter optimisation (HPO) that quantifies uncertainty of each candidate configuration. This uncertainty quantification mechanism is applied to several state-of-the-art iterative HPO algorithms to prevent that promising configurations that have low performance in the early stages of the iterative process are not incorrectly discarded. The evaluation shows that UQ allows to find similarly performing configurations at a fraction of the exploration budget.
strength_weakness: strength_weakness: See above for strengths and weaknesses.
questions: questions: **a)** 
Why do you claim that "data uncertainty is constant"? (This is in the beginning of section 3.1)

**b)** 
Section 3.3. -- exploration vs exploitation: is k_1 - 1 == k'_i ?

**c)** 
Section 3.4, Example 3 is not clear to me. In both cases you mention in the example, the UQ method "can return the best candidate with probability over 1 − n\delta". Do you mean that the probability of UQ returning the best candidate is larger than "1 − n\delta" (which is the probability of the UQ-oblivious method returning the best candidate)? Also, there is a 'But' in the middle of the example, but I don't understand the 'But' and I don't see where the expression  for B_{UQ} comes from.

**d)** 
Which parameters does the UQ approach have and that a user must set? How do those parameters affect the improvements attainable by UQ?

&NewLine;  
**Comments:**

- Section C.1 of the appendix has some missing pointers to assumptions.

- The evaluation plots would all be much easier to read if the y-axis was labelled. 

- You could also highlight the moment when the UQ-version of each baseline achieves comparable performance to the UQ-oblivious version. This would make it easier to visually identify the gains achievable via UQ in terms of budget savings.
limitations: limitations: There could be more discussion on the limitations of the proposed method. For example, when is it applicable, how do the different assumptions impact its applicability, how could future work improve the current version of the proposal to address these limitations.
paper_summary: paper_summary: The authors presented a novel scheme for hyperparameter optimization (HPO) in machine learning (ML) based on quantization uncertainty. The paper reflects a clear consequent way of discussion from introduction and literature overview to conclusions and very detailed appendixes. The authors demonstrated a strong mathematical background of these results with a full understanding uncertainly in machine learning model optimization process. Work presents theoretical analysis, examples and experiments on different related algorithms. Presented uncertainly quantization guided scheme can be widely applied for HPO in ML models optimization.
strength_weakness: strength_weakness: Perhaps authors should provide more detailed discussion about UQ-scheme limitations and adaptation for non-iterative learners and add some links about such learners

Mistypes and etc.
Appendix C, page 21, lines 2 and 3 in the first paragraph. Broken links.
Appendix D, page 24, line four in the first paragraph. Broken equation link.
questions: questions: Has the UQ-scheme some limitations depending on the number of initial candidates for SH algorithm, for example? Could this be the case where UQ-scheme performance will be almost the same as in the original HPO algorithm, where regret between SH will equal SH+ with large or small vise-versa amount of the initial candidates? Or accuracy derivation for confidence curve is absolutely stable for any quantity of candidates?
limitations: limitations: Limitations this work mainly addressed to HPO in machine learning applications. Authors build adequate descriptions and analysis of their technique only within ML applications (abstract introduction and conclusion). Moreover, the authors noted that their HPO tuning scheme can be mostly suitable for iterative learners.

Comments: title: Response to Reviewer P7Zr
Response to Rebuttal
comment: >**Commet 8: (Response to Comment 1) Why is the step size fixed in this example? Would not it make sense to tune the step size too?**

Response: We follow the original benchmark setting where we set the decreasing step size according to epochs and tune the penalty parameter.
The step size can be tuned as well. 
By applying different step schedulers, we can further expand the search space.

>**Comment 9: (Response to Comment 2) How would the loss curves be leveraged to extract the epistemic uncertainty? Learning curves can be pretty noisy and are also affected from the chosen hyperparameter values such as the step size. Just imagine a step size chosen by the tuner that is way too big. To me, it is not entirely clear how the aleatoric uncertainty is disentangled from the epistemic uncertainty and as the paper is claimed to work for iterative learners in general, for me, this is an essential part of the paper to be demonstrated. If the title of the paper was for deep learning methods, I would be satisfied with the scope of the paper.**

Response: The “Solving for the Momentum Mean and Variance” part from the bottom of Page 3 to Page 4 explains how the uncertainty of the model’s predictions is estimated. Essentially, it strives to approximate the variations of the loss of the model at any given epoch, including the distribution of the loss of the converged model, and hence the uncertainty of its predictions. Details are described in that part of the paper. 



It is important to note that it is a statistical prediction process based on history. As with any typical statistical prediction, there is influence of some kinds of inseparable noises from various sources. The default schedule in our experiments already uses large learning rates at the beginning; fluctuations of loss curves at the early stage of HPO are commonly observed in our experiments. The existence of such influence is why empirical evaluations are necessary to validate whether the statistical prediction process could practically deliver good (of course, imperfect) predictions, which is what the results in our paper demonstrate. 



The experiments in our paper concentrate on DNN due to the importance of efficient HPO to the time-consuming nature of DNN training. Our ridge regression experiment in the rebuttal demonstrates the applicability of the methodology to other iterative learners. But because there was very limited time in the rebuttal period, the added experiment is a demonstration rather than a series of systematic experiments. We can understand the point of view of the reviewer about the scope of the paper. For the final version, we can narrow the main claims to DNN and use the ridge regression as a demonstration to show the potential of the methodology for other iterative learners, and leave a systematic study of which to the future. 

>**Comment 10: (Response to Comment 4) If the quantification yields that the best candidate is identified with a probability of 99\%, would not it make sense to spare resources and stop the evaluation?**

Response: It absolutely makes sense, and our approach is designed to incorporate this principle.
If the quantification indicates that the best candidate is identified with a sufficiently high probability (exceeding $\tau_i$ in round $i$), only this top candidate will be retained for that round. At this point, the HPO process is considered completed, and the remaining budget resources can be spared, as there is no need to evaluate additional candidates when only one remains.

> **Comment 11: (Response to Comment 5) Could not this flaw the overall HPO process? If you for example encounter a setting where you can never certainly drop any candidate, either due to very similar performance or large uncertainty bands, you will not return a model that is trained on the full assignable budget, do you?**

Response: If candidates have very similar performance or large uncertainty, our approach will retain 
$k$ candidates whose total probabilities of being the best candidate meet the threshold $\tau_i$, dropping the rest for that round. As rounds progress, this strategy exponentially reduces the number of candidates, efficiently narrowing down to the best options.
Thanks for your responses. I will remain the score.
Thank you very much for the detailed response and the clarification.

Ad Response to Comment 1:
Why is the step size fixed in this example? Would not it make sense to tune the step size too?

Ad Response to Comment 2:
How would the loss curves be leveraged to extract the epistemic uncertainty? Learning curves can be pretty noisy and are also affected from the chosen hyperparameter values such as the step size. Just imagine a step size chosen by the tuner that is way too big. To me, it is not entirely clear how the aleatoric uncertainty is disentangled from the epistemic uncertainty and as the paper is claimed to work for iterative learners in general, for me, this is an essential part of the paper to be demonstrated. If the title of the paper was for deep learning methods, I would be satisfied with the scope of the paper.

Ad Response to Comment 4:
Yes I got that from the paper. But if the quantification yields that the best candidate is identified with a probability of 99%, would not it make sense to spare resources and stop the evaluation?

Ad Response to Comment 5:
Got it. But could not this flaw the overall HPO process? If you for example encounter a setting where you can never certainly drop any candidate, either due to very similar performance or large uncertainty bands, you will not return a model that is trained on the full assignable budget, do you?
Thank you for answering my questions.
Thank you for the clarifications.