UQ-Guided Hyperparameter Optimization for Iterative Learners
Authors: Jiesong Liu
Feng Zhang
Jiawei Guan
Xipeng Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: Uncertainty quantification; Hyperparameter Optimization; iterative learners
Primary area: optimization_for_deep_networks

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.

UQ-Guided Hyperparameter Optimization for Iterative Learners
Jiesong Liu", Feng Zhang", Jiawei Guan', Xipeng Shen',
'Department of Computer Science. North Carolina State University
"School of Information, Renmin University of China jliu93 @0093.nccsu.dde guanjwdd @ ruc.edu.cn. fengzhang @ ruc. edu.en, xshen5 @ ncsu.edu
Abstract
Hyperparameter Optimization (HPO) plays pivotal role in unleashing the potential of iterative machine learning models. This paper addresses crucial aspect that has largely been overlooked in HPO: the impact of uncertainty in ML model training. The paper introduces the concept of uncerlainty-aware IPOO and presents 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 probabilistic model and implementing probability -driive candidate selection and budget allocation, this approach enhances the quality of the resulting model hyperparameters. It achieves notable performance improvement of over 50% in terms of accuracy regret and exploration time.
1 Introduction
Hyperparameter optimization (HPO) is essential for unleashing the power of iterative machine learning models [4. [8| 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 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 surrogate model to guide the selection of candidate configurations for assessment.
There however lack of systematic treatment of 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 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 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 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 Figure and Section Figure
This paper introduces model uncertainty into the design of HPO methods for iterative learners and establishes the concept of uncertainty-awal HPO. At the core of uncertainty-awarc HPO is 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 HPO-into a single UQ-based formal decision process. The UQ-guided scheme builds on probabilistic uncertainty-base model, designed to approximate the statistical effects of discarding
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

set of candidates at the end of a step in HPO. It uses lightweight method to efficiently quantify model uncertainty on the fly. It offers a principled, efficient way for HPO to treat model training uncertainty.
As general scheme, the UQ-guided scheme be integrated into variety of HPO methods for iterative learners, especially DNNs. This paper demonstrates its usefulness and generality for DNNs by integrating into four existing HPO methods. Experiments on two widely used HPO benchmarks, NAS-BENCH-201 p and LCBench 22), 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 theoretical analysis of the impact of the UQ- lo-dgddde scheme for HPO.
2 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-fidell optimizations are some important approaches.
Bayesian Optimization (BO). BO is a sequential design strategy used to optimize black-box functions [1 HPO scenarios, it can be used as a surrogate model to sample high-qualit candidates.
Early Stop Mechanisms, Early stop-based approaches can be effective since they evaluate different candidates during training and make adaptive selections accordingly [2] 35). The early stopping mechanism, which stops the training of poorly-performed candidates early, has been widely em- ployed in the HPO community including Successive Halving (SH) [19] and Hyperband (HB) (25); BOHB [II] 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 g 23
38
21
35
36
14 26).
Sub-sampling (SS) [15) is proposed mainly using multi 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 approxima- tion uncertainties (5) 6 10 22
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 the same deterministic metrics other HPO methods use, giving 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 guide the allocation of training budget. We compare other related works in Appendix E
24
3 Uncertainty Quantification (UQ)-Guide Hyperparameter Optimization
This section gives an exploration of model uncertainty, introduces UQ-guided scheme for incorporat- ing 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.
3.1 Uncertainty in Iterative Machine Learning
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 I. 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 [ shows how the model uncertainty affects the quality of the returned candidate. In given SH run, half of the candidates are eliminated at each checkpoint marked by 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 conver- gence) 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.
3.2 Quantify Uncertainty and the Impact
We explain how we quantify model uncertainty, and how, based on it, at any point of time, estimate the performance and uncertainty of candidate model when its training converges.
Validation Loss
Last bahiig
Cunesa Best
2
Iopinz
Finui
Reget
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.
Graund
40
100
Iteration
Figure 1: Demonstration of the negative im- pact from uncertainty on HPO; Successive Halving (SH) is used; the benchmark is NAS- BENCH-2.0 (9) More detailed are in Sec- tion 4.1 and Appendix [F] Due to its over- looking model uncertainty, at each halving point, SH discards the actual best candidates, causing an increase in the regret.
Let 71, 72.-.
E I be K candidates drawn from the hyperparameter space I. Consider a su- pervised learning setting, where machine learning model M is trained on some training set Drrain {(x1. y1), (X2, y2), (Nteracn : (nsras.) }} Let M denote the model with hyperparameter y trained on Drrain after epochs, and M the converged model. (x) gives the prediction on a given input x IRd.
We use -(:-)) to denote the metric that evaluates the performance of candidate model. Given a hyperparameter configuration Yo: the validation loss of a model instance, f(y, M (X)), can be affected by training data and other factors, and hence has some uncertainty. Let WV (Me*, +) represent the distribution of E(y, M (X)), where, of+ embodies the uncertainty.
Our objective here is a way that can, at any point in the HPO process, estimate o² and μe for candidate model configured with Yc. Our solution leverages the validation history in the HPO process, E(y, M! (X)). .... [yy M (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 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; models a latent effect underlying the hyperparameter space by allowing correlation among the candidates. The details are as follows.
Typically a candidate in HPO can be represented as a vector. We use set Ur C RR to represent the candidates (7,, i E [n]]: > 0 is the vector length. For modeling the loss curve, we set k, E R- as a vector whose elements are functions of training epochs t = 1,2,.... (In our experiments, we set k, = it- 1/2 t-1], for the general decreasing trend of loss curves as training epochs increase.) We model metric ! of candidate u E U, at time as the summation of the impact from three sources:
tx fly M (X) k. 17 Z E
(3.1)
where 17" and Z are the parameter vectors to determine. The three components in Equation 3.1 are (I) the momentum part (k, 17") that denotes the contribution from the trends in the loss curve the training specific candidate model variant, (2) the contribution from the underlying model structure (u Z), and (3) the noises by other elements <f, which is asssumed to follow a Gaussian distribution (0 of) independent of each other and of Z.
For candidate u E Ur let a optimizing a weighted least squares objective
Z. The loss curve parameters (a", .7") can determined by
3

---

9 min sy
ΣΣ (=1
Ce -a - kg n))
(3.2)
where Wijt = Foo7" Fg is the number of models trained with time t.
Solving for the Momentum Mean and Variance. This part analyzes the mean and variance of the loss curve constructed and makes inferences to the converged loss based the loss curve. The quantified uncertainty of the estimated converged loss is then used for model selection and budget resource allocation. The specifies are follows.
For candidate at iteration T, concatenating the validation losses across training epochs (indexed by t) will lead to a validation loss vector v of dimension D Σi= Ft. For each d E {1..... . the t element in v is an observation of loss at time ta that follows (( otg)) to its corresponding epoch f.
: with ta mapping
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 W W A,3 for with W E DxD being diagonal matrix of weights W dd -.
= 1 K]. K RDx(L+) with K[d,:] ] k and B [a n =) The empirical estimate of of is computed the variance of the loss in the recent several epochs of i instances be regarded as results of small perturbations to the model at epoch i.
Solving the weighted least square objective, we have the estimator as 3 = (AT (TT Wv).
The covariance of the estimator is given by 3 = (A T -A)
Since the estimated curve is given by i(t) [1 k, 18, the variance of this estimation is given by
a² (t) = k, I ke
With the formulas for 6(1) and (1). we can then approximate the distribution of M (X)) as ((((N)) for 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 T. such that for any max ||u||| S T. and the set of candidates Ur C. R" has linearly independent elements b,...., ,b,
uell,
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, ......... it and refines the ordinary least square estimate for Z as
observes the metrics X (1)= t. kj b follows:
2 = byb
b,,
p=1
At the end of HPO round (e.g., at the halving time in SH), performs the first step for every candidate model to compute the estimated distributions of their e M (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 "je is lower than that of Yeg represented as follows based on the approximation from the current validation losses and uncertainty of the two candidates:
P= Pr [(y, M (X)) > Ely, M (X)) Ely,
M0 M==122... (X)), Oc, Ely, Mty,M 202
M1=12..... (X)), 3
(3.3)

---

Determine the number of
Uncertainty Quantification
models to keep flm V
l-- N (n, of)
Sweet Point
lx
1
prohability distribution of loss after convergence
Mx
Confidence Curve
p
Probabilistic
Discarding Mcchanism
Model
Conligs
Budget
Ends
Round Start
Round
Round Round 3 Round
Figure 2: Illustration of using UQ-guided scheme to enhance Successive Halving. The goal is to select 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 epochs. Based the observed validation loss and the quantified uncertainty for each candidate, our method represents each candidate's 's converged loss with prob- ability distribution. From that, constructs confidence curve, capturing the probability that the best configuration is among the current top k candidates for 1 S. k < K. From the curve, it then calculates f f(p), of { k). which captures the effects of keeping top candidates (1 < k S 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 value, discards the least promising K k candidates, and enters the next round. The process continues until the total budget used up.
The main idea of Definition T is to use the current validation loss history and quantified uncertainty to approximate the converged validation loss, that 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 "i and 7k. at epoch I, are (リz5dş) and (JoK, ok),, using converged validation loss
as the metric, we have Pr(f(y, M (X)) > E(y, Mr (X))) Vot+o?
Mk-MS where c denotes the
cumulative distribution function (CDF) of the standard normal distribution.
We next present UQ-guided scheme, principled way UQ guide HPO.
3.3 UQ-Guided Scheme
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 Section (35 that 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 rounds. At the end of each round, it drops those candidates regarded as unpromising. With our UQ-guided scheme, the end of each round, the scheme derives 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 the original HPO that drops fixed amount (or fraction) of candidates in each round, the UQ-guided scheme carefully calculates the number of candidates to drop a round based on the probabilistic model such that the expected quality of the HPO outcomes can be maximized, as explained later.
multiple
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.
3.3.1 Confidence Curve Derived from Uncertainty Quantification
The concept of confidence curve is central in UQ-guided HPO. Define [n] = (1, ...
5

---

Definition 2 (Confidence curve), At epoch we evaluate each candidate's 's performance and sort them based on validation loss. A confidence curve C is a trajectory of a series of probabilities, [Palk E [n]], that depicts the probability that the optimal configuration (with the lowest loss after convergence) is among the first l. configurations. For E [n], Pk can be expressed as
PA = -r min(E(y, MM, e(yy,
_eyy,,",, M (X))) I min(E(y, M y1 (X)), . ,ely, M
The confidence curve is derived based on joint probability distribution in the following way. Suppose there are candidates. At the end of certain round, the probabilistic model returns pairs of (H) 1)), (H2, 02), (Hh, Fn) as estimations for E(y, M (X)), M (X)), f(y, M (X)). For simplicity, assume that μr < 122 < ................................ < Mn, and 01 = 02
Let o and & be the CDF and PDF of the standard normal distribution. For ls m, we can calculate
m
y P4 dy.
P
(3.4)
0
The details of obtaining Equation 3.4 are in Appendix A.
3.3.2 Discarding Mechanism
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 based on the confidence eurve: choosing the smallest & that satisfies Ps 2 T, where is parameter determined by our scheme adaptively as follows.
Choosing т. At the end of round i, we have the confidence curve Cs( Cs(Pi, Pg. Ph that is the trajectory of a series of probabilitics. We quantify how T influences the probability for the HPO to select the best candidate.
Let Tú be the value of for round i, k; be min(k: C,(P)) 2 T.). As the scheme discards the worst 1--; k; candidates and further trains the best k; candidates in round i- 1, we can derive the confidence curve of round i + as C.+.1 ( p :... PP-1) based on those selected k; candidates. Since we want to quantify the effect of on the probability that the scheme returns the best candidate (that is, suppose round + is final round), pf++1 is the target we desire maximize. Define & to be the current condition (pt: 0% ) Let f(:--) be mapping such that f(,, T4) Pitt1 1 We want to use a selector function V/ : D - [0, 1] where D = ((0, x)) x [0, oo)) x [0, 1]. W takes &, as input and returns an optimal Tj:
((,)) = arg max (f(S.,
(3.5)
The effect of TÚ on manifests through its influence on the number of candidates k; retained in the subsequent round, and can be ultimately broken down into the influence of (1) exploration. meaning keeping more candidates 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. k; drops by I k/, according to the definition of the confidence curve, the probability that the final optimal configuration is among the remaining candidates we keep drops by Ac Pk. Pw:
Aq
1
II Φ
R
y
Pi dy.
(3.6)
Exploitation. At the same time, a drop K; leads an increase in the individual training budget b. Let Ç be the coefficient that relates the increase in the number of training epochs its corresponding effect on confidence. Using an approach similar to that employed in formulating the confidence curve,
30 - -- 0-200 II
y リ
Idy
(3.7)
0-A.0
where 1. represents the current total number of epochs and A,O represents the reduction in the uncertainty that would result from training each candidate for one additional epoch. The specifics for Equations and 3.7 can be found in Appendix A.2 Given that b increases by It R the overall
K k,
influence of exploitation on the probability of selecting optimal candidate is Act K,
R

---

Let ,(k;, be the confidence increase, given condition &. when each of the K; candidates gets unit extra training budget. (,(P)), [n] are the confidence curves. Balancing exploration and exploitation leads to sweet point where Dq = Aey- That gives the way to derive the appropriate value for т, which just needs make the following hold:
R
Pk. Pk,-1 le 1) ((Ri, E.).
(3.8)
3.4 Theoretical Analysis
We consider how the method performs in terms of identifying the best candidate. For convenience, let fi be the approximation of the converged loss for the model with hyperparameter % at time t. For each i, assume V/ = 4im lir exists. The goal to identify arg min; V4. Without loss of generality, assume that 21 <2
Un- The assumption that limy lir exists implies that as 7 grows, the overall gap between lir and decreases. Let og f(() be the model uncertainty epoch l. We then introduce random variable that characterizes the approximation error of C, relative to v4, modeling it as a distribution that incorporates t as parameter:
X, lee U4 X₂ N(O,, 11.
By applying Chebyshev inequality, we have
Pr [ mz| 1/4 1/
40
4f(t)²
i= 2-2,...,
(3.9)
(vi n3
(vs v1)2
Let A denote the event Ci,t > b,,s then by Equation 3.9
Pr(A) = Pr { (lis vi) + (u) - E1.e) +
1/ 1
0J
21
4f((1²
(3.10)
2
(po -v
Equation 3.10 tells that l..: L1,t has high probability with respect to if f(t) E O(t-1/4) (see Lemma in Appendix C). That is, comparing the intermediate values at a certain time t likely to establish an order similar to the order of the final values of v and v1.
The following theorem is stated using the abovementioned quantities with proofs in Appendix C.I
Theorem 1. Let n. be the number of total candidates, and v4 lim l, For a given c 0, there T-
exists > s.t. candidate is returned with probability >> (1 - c) - c). where B is the total budget.
11
c. c If the round budget R T n, then the best 4f(T) )²) > -
i=2
In comparison, the bound in the UQ-oblivious approach is as follows:
Theorem 2. Let 8 > 0, = lim lir and assume 11 S S ... S vn. Let ( = min(t e
7-000
N : 100 < J.., and
Rob 2[0ogg(n) max {(1 + ( 8))
2.....n
< (1))
mummn 5)).
2
the UQ-oblivious early stopping method run with any budget Bob >> Zob then the best candidate is returned with probability P.b > nô.
$. According to Theorem 2 if Bas (n)ogg(n) (n E ( ,8), the UQ-oblivious method can return the best candidate with probability over nó. But if Buq ~ 7 1 (22-""
Example 3. Consider f(()
the UQ method can return the best candidate with probability over 1 nó. As shown in Appendix C.2 Theorems 7 [ show that the UQ approach guarantees the same probability of identifying the optimal candidate as the UQ-oblivious counterpart with smaller budget lowerbound B (see Corollary 0
If g if there constants c' s.t. cg(x) S f(x) S ddg(x).
7

---

3.5 UQ-Guided HPO Family
The UQ-guided scheme is general approach 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 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) [9]. Algorithms 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 = K units of budget, and ranks them by the evaluation performance. Then SH+ updates K based on Section 333.2 and keeps the top K configurations according to the UQ-guided scheme (OracleModel in A Algorithms and () 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 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+) developed from BOHB M. 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,) against the most trained candidate (cm.) rather than checking their validation losses, it uses the UQ-guided scheme to compute the probability for the convergence loss of e; to be smaller than that of G. and checks whether the probability is over threshold (0.9 in our experiments), that is, Pr(E(y, M Tem (x)) 2 Ely, M (x)) 2 T.
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.
4.1 Experimental Setup
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- 19-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 (TFL.PS) on pouble--recision, 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-I0, CIF,R-100, and ImageNet-16-122 (CC-BY 4.0) datasets. In addition, we investigate the performance of optimizing traditional ML pipelines, hyperparameters, and neural architecture in LCBench [4] For example, we optimized 7 parameters for the Fashion-MNIST dataset (7], where the resource type 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 hours.
4.2 Experimental Results
Figure 3 illuttrates the results of MAS-BENCC-201 trained on 1mageNet-16-120, It shows the results of four UQ-guided methods compared to their original ones. For each comparison, show three
8

---

15
Sit+
5 06
Slit
10
SH1t
0.8
0.2
Different Trials
Fraction Budects
Fraction Budacts
HB HBB
HB
10
Rank
HB
10
5
2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Different Trials
Fraction Budacts
Fraction of Budgets
15
BOHB BOHB
BOHB BOHBB
BOHB
10
5
Rogua
10-
BOHIB
5
100
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
Different Trials
Fraction of Budgets
Fraction of Budacts
15
S8
SS
SS
Kank
S8
10-
SSI
5
600
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Different Trials
Fraction of Budgets
Fraction of Budgets
Figure 3: Experimental results of UQ-oblivious HPO methods and their UQ-guided enhancements NAS-BENCH-2.0.
metrics, namely top-1 rank on different trials, top-1 rank 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 the standard full budget. Top-1 rank refers 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. 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 21-55% regret reduction. Similar results are observed on other benchmarks (LCBench results shown in Appendix G
Figure 3 the average
Table provides the fraction of the total exploration time needed for the UQ-guided methods achieve comparable model accuracy as the original methods do. The UQ-guided methods need much less time than their counterparts obtain 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.
Table 1: Fraction time (%) required for the UQ-guided methods to achieve comparable model performance as the original HPO methods do.
Methods
NAS BAS-BENC--201
LCBench
SH+
50.78
43
HB+
75
60
BOHB+
68.4
53.34
SS+
47.84
30.93
Our paper's experiments concentrate on DNN because efficient HPO is crucial for the time-consuming nature of DNN training. We also the ridge regression in Section H
as demonstration to show the

---

potential of the methodology for other iterative learners, and leave a systematic study of which to the future.
5 Conclusion
This paper points out the importance of systematic treatment to the uncertainty in model trainings for HPO. It introduces novel scheme named UQ UQQ-uided scheme, which offers 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 regret over their original versions, and require only 30-75% time to identify a candidate with matching performance the original methods do. The paper in addition provides 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-bad basdd 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 [3] that use training dataset size as the budget dimension. In this case, the learner does not need to be iterative; the selection based on the validation loss history trained with incremental dataset sizes. The UQ component can still guide the configuration selection and budget allocation the HPO process.
Overall, this study concludes that UQ is important for HPO to consider, simple on-the-fft fly UQ goes long way for HPÓ, and the UQ- (Qgguided scheme can serve as general effective scheme for enhancing HPO designs.
References
[1] Moloud Abdar, Farhad Pourpanah, Sadig Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, Rajendra Acharya, al. review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information fusion, 76:243-299 2021.
[2] Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. arXiv preprint ar05v: 10823, 2017.
[3] Hadrien Bertrand, Roberto Ardon, Matthieu Perrot, and Isabelle Bloch. Hyperparameter optimization of deep neural networks: Combining hyperband with bayesian model selection. In Conférence l'Apprentissage Automatique, 2017.
[4] Bernd Bischl, Martin Binder, Michel Lang, Tobias Pielok, Jakob Richter, Stefan Coors, Janek Thomas, Theresa Ullmann, Mare Becker, Anne-Laure Boulesteix, et al. Hyperparameter optimization: Foundations. algorithms, best practices, and open challenges. Wiley Intendisciplinary Reviews: Data Mining and Knowledge Discovery, 13(2)e1484, 2023.
[5] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International conference on machine learning, pages 1613-1622. PMLR, 2015.
[6] Danruo Deng, Guangyong Chen, Yang Yu. Furui Liu, and Pheng-Am Ann Heng. Uncertainty estimation by fisher information-based evidential deep learning. In International conference on machine learning. PMLR, 2023.
[7] Li Deng. The mnist datahase of handwritten digit images for machine learning research [best of the web). IEEE signal processing magazine, 1916):14 2012.
[8] Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In Twenty-fourth international joint conference on artificial intelligence. 2015.
[9] Xuanyi Dong and Yi Yang. Nas-hench-201: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.000 2020.
[10] Vincent Dumont, Casey Garner, Anuradha Trivedi, Chelsea Jones, Vidya Ganapati, Juliane Mueller, Talita Perciano, Mariam Kiran, and Mare Day. Hyppo: A surrogate- based multi-level parallelism tool for hyperparameter optimization. In 2021 IEEE/ACM Workshop on Machine Learning in High Performance Computing Environments (MLHPC), pages 81-93. IEEE, 2021.
10

---

[11] Stefan Falkner. Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter optimization at scale. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pages 1437-1446. PMLR. 10-15 Jul 2018.
[12] Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1050-1059, New York, New York, USA, 20-22 Jun 2016. PMLR.
[13] Pieter Gijsbers, Erin LeDell, Janek Thomas, Sébastien Poirier, Bernd Bischl, and Joaquin Vanschoren. An open source automl benchmark. arXiv preprint ar 117:1907000000 2019.
[14] Yi-Qi Hu, Yang Yu, Wei-Wos Wei Tu, Qiang Yang, Yuqiang Chen, and Wenyuan Dai. Multi-fidelity automatic hyper-parameter tuning via transfer series expansion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3846 3853, 2019.
[15] Yimin Huang. Yujun Li, Hanrong Ye, Zhenguo Li, and Zhihua Zhang. Improving model training with multi-fidelity hyperparameter evaluation. D. Marculescu, Chi, and C. Wu, editors, Proceedings of Machine Learning and Systems, volume 4, pages 485-502, 2022.
[16] Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning. 110:457-506, 2021.
[17] Frank Hutter, Holger H. Hoos, and Kevin eeeyton-Brown Sequential model-based optimization for general algorithm configuration. In Carlos A. Coello Coello, editor, Learning and Intelligent Optimization, pages 507-523, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[18] Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren, Automated machine learning: methods, systems, challenges. Springer Nature, 2019.
[19] Kevin Jamicson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimiza- tion. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference Artificial Intelligence and Statistics, volume S1 of Proceedings of Machine Learning Reseurch, pages 240-248, Cadiz, Spain, 09-11 May 2016. PMLR.
[20] Jiang, Jiawei Jiang, Bin Cui, and Ce Zhang. Tencentboost: A gradient boosting tree system with parameter server. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 281 181. IEEE, 2017.
[21] Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás P6czos. Multi-fidelity bayesian optimisation with continuous approximations. In International Conference Machine Learning, pages 1799-1808, PMLR, 2017.
[22] Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast bayesian optimization of machine learning hyperparameters on large datasets. In Artificial intelligence and statistics, pages 528-536. PMLR. 2017.
[23] Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter. Learning curve prediction with bayesian neural networks. In International Conference Learning Representations, 2016.
[24] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
[25] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadch, and Amect Talwalkar, Hyperband: A novel bandit-based approach to hyperparameter optimization. J. Mach. Learn. Res., 18(1):675566166 jan 2017.
[26] Yang Li, Yu Shen, Jiawei Jiang, Jinyang Gao, Ce Zhang, and Bin Cui. Mfes-hh: Efficient hyperband with multi-fidelity quality measurements. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8491-8500, 2021.
[27] M. Lichman. Uci machine learning repository, 2013. Accessed: [Insert access date here].
[28] Siyan Liu, Pei Zhang, Dan Lu, and Guannan Zhang. P13NN: distiidddtiiitiion-aaee aware prediction intervals from three neural networks. In International Conference Learning Representations, 2022.
11

---

[29] Jingwei Ma. Jiahui Wen, Mingyang Zhong, Weitong Chen, and Xue Li. Mmm: multi-source multi-net micro-video recommendation with clustered hidden item representation learning. Data Science and Engineering, 4:240-253, 2019.
[30] Paul Micaelli and Amos J Storkey. Gradient-based hyperparameter optimization over long horizons. Advances in Neural Information Processing Systems, 11798-108099 2021.
[31] Felix Mohr and Jan N van Rijn. Towards model selection using learning curve cross-validation. In 8th ICML Workshop on automated machine learning (AutoML). 2021.
[32] Felix Mohr and Jan N Rijn. Fast and informative model selection using learning curve cross- validaaali. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2023.
[33] Alejandro Morales-Hernández, Inneke Van Nieuwenhuyse, and Gonzalo Nápoles. Multi-objective hyper- parameter optimization with performance uncertainty. Communications Computer and Information Science, 1684:37-44 2022.
[34] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization machine learning algorithms. In Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neurul Information Processing Systems, volume 25, Curran Associates, Inc., 2012.
[35] Kevin Swersky, Jasper Snoek, and Ryan P Adams. Multi-task bayesian optimization. Advances in neural information processing systems, 26, 2013.
[36] Shion Takeno, Hitoshi Fukuoka, Yuhki Tsukada, Toshiyuki Koyama, Motoki Shiga, Ichiro Takeuchi, and Masayuki Karasuyama. Multi-fidelity bayesian optimization with max-van value entropy search and its parallelization. In International Conference on Machine Learning, pages 9334 9345. PMLR, 2020.
[37] Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo Openml: networked science in machine learning, ACM SIGKDD Explorations Newsletter, 15(2):49-66) 60, 2014.
[38] Jiazhuo Wang, Jason Xu, and Xuejun Wang. Combination of hyperband and bayesian optimization for hyperparameter optimization in deep learning, arXiv preprint arXiv: 180100199, 2018.
[39] Shiwen Wu, Yuanxing Zhang. Chengliang Gao, Kaigui Bian, and Bin Cui. Garg: anonymous recommenda- tion of point-of-intert mobile networks by graph convolution network. Data Science and Engineering, 5:433 447, 2020.
[40] Quanming Yao, Mengshuo Wang. Yugiang Chen, Wenyuan Dai, Yu-Feng Li, Wei- Wei Tu, Qiang Yang, and Yang Yu. Taking human out of learning applications: survey on automated machine learning. arXiv preprint or Xiv: 13306, 2018
[41] Wentao Zhang, Jiawei Jiang. Yingxia Shao, and Bin Cui. Snapshot boosting: a fast ensemble framework for deep neural networks. Science China Information Sciences, 63:1-12, 2020.
[42] Lucas Zimmer, Marius Lindauer, and Frank Hutter. Auto-pytorch: Multi-fidelity metalearning for efficient and robust autodl. IEEE Transactions on Pattern Analysis and Machine Intelligncee 43(9):3079 3090, 2021.
12

---

A Method Details
A.1 Formulation of Confidence Curve
The following contents detail how to compute the confidence curve current validation loss and quantified uncertainty of the candidates.
based on
Let Y be the random variable denoting the negation of the lowest converged validation loss:
Y max(-e(y Mr (X)): -(y, M ... (x (X))). Since f(y, M (X)) ~ NN4, of)), the cumulative distribution function (CDF) Y. Fy (v), is
(v) = Pr(Y s v) = Pr(Pr((1 Mr, (X) s v. 1---(8 v-y, Mx, s V. f(y M (X)) S v)
II
Φ y + Ui
exp( Σ In +
y + μi
t=1
Accordingly, the probability density function (PDF) of Y, (y), is
fy
dFy
1 " - 2its
II
n
1i
dy 0
a
Now construct the confidence curve by calculating each Pk (k (ni)). For h: m, Pa be expressed as
Pm = Pr(min (ely, M,, (X)), ... ,E(y, M (X)) & min(E(y, M Tm (X)), .. Eyy, M,, (x)))).
Let E(y, M (X)),
fly, M (X)) be mutually independent, thus
Pm
fr (v) (N mm+1) S y. y. -.....--(p on) S yd
(y) y pm+11
4 + pn dyy
(A.1)
M
+ ddy.
A.2 Computing
Equation
3.6 can be calculated by directly subtracting Pk. by Pkp-1:
y +
+
AC
ydy
+ [ml
dy
y+
aml
00
M+
y +
T
ddy.
M+PE
( is the coefficient that relates the increase in the number of training epochs to its corresponding effect confidence. Consider working round that starts with & candidates. We have approximations the end of the round for the converged loss Ely. M (x)) ~ NN o²) for E [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(E,T) T) at epoch t:
+
+ Mi dd..
f(5,T). =
0
Φ 2
(A.2)
If each configuration trained with one extra unit of resource (a total of + 1 epochs), model uncertainty would be reduced. We use the same μi approximate the converged validation loss
13

---

for t + epochs, and use - A approximation for model uncertainty. Here A. is the decrease model uncertainty that is determined through offline profiling with details in Section D This approximation leads us to / (5,7) 7) at epoch / + 1 as
f(5,7)
1 + M1
II Φ
Mi
)dy.
(A.3)
D 10
0
D.o
o
4,0
2
Subtracting Equation A.3 by Equation
A.2 gives us the result in Equation 3.7
<= -(557))+-
+
p1 D.o
Φ + Mi
Jdy
00
1
11
y
+
p4
dyy.
A,o
A.o
i=2
1
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 I' = {n, "2. 7K), minimum round budget
R
Output:
The configuration with the best performance
repeat
for i= to do
Evaluate Mr with budget b and get M2++b 4+==b
end for
Rank according to performance and obtain new M M M2.... .. M
K = -OacleMMdel (M M M ... M", MM
Keep top K candidates until total budget B runs out
Algorithm 2 OracleMode odel for determining K candidates into the next round.
Input: K instances of Machine I Learning models M 712 Maa,.. ... .... M
Output: A new K that tells the model how many candidates to keep Get a r from the probabilistic model the f(y, M (X)), M (X)) Ely, M (X))
Construct
confidence
curve
C(P, Pk)
based
return min(k: Pv > T}
A.4 Pseudo-code for UQ-Guided Hyperparameter Optimization (HB++)
Algorithm 3 Hyperband plus (HB+)
Input: Total budget B, the set of K configurations I' {7i 72, "M ,Yk) ) maximum budget R.
ratio r7
Output:
The configuration with the best performance
Smax [log,, RR.6
for $ = to Smax do
.+1 ]
=
Sample configurations randomly
Call SH+ with (ki, b, 2) end for
A.5 Pseudo-code for UQ-Guided Hyperparameter Optimization (BOHB+)
14

---

Algorithm 4 Bayesian Optimization Hyperband plus (BOHB+)
Input: Total budget B, the set of K configurations I {m, (2,") .k), maximum budget R.
ratio yy (default = 3)
Output: The configuration with the best performance Smax log,, RJ.
for to Smax do
A s+1
Sample & configurations using Bayesian optimizer
Call SH+ with (k. b, ")
end for
A.6 Pseudo-code for UQ-Guided Hyperparameter Optimization (SS+)
Algorithm 5 Sub-Sampling plus (SS+)
Input: Total budget B, the set of K configurations I' = {11 72,111 minimum budget ratio 7 (default 77 3)
(2,722 "*1 77k maximum budget R.
Output: The configuration with the best performance
1, evaluate all configurations with budget
for r 2 to [log,, [R/b] do Select 7<c with the most observations.
I' {k: E Pr 7 3 % A pass UQ check]
if I'' = 0 then
Evaluate 75 with budget r
else
Evaluate VA with budget 17' for each & T'
end end for
B More Theoretical Analysis
We have been concerned with identifying the best candidate, while in practice, is often sufficient to consider a situation where the difference between the result of candidate i, (V;,) and the result of the best candidate (11) is less than or equal small value c. We obtain the following theorem with proofs in Appendix C.3
Theorem 4. For a budget B R. and a set of candidates, let be the output of the UQ-guided approach. Then
E(y; 11) 21 2 (2
VT
In comparison, ip. the output of the UQ-oblivious counterpart, satisfies
E(U; v1) ([log2(n)]v22
[og.
VTT
Example 5. Consider f(t) 1. Substitution of ft) Theorem can clearly show smaller upperbound of the UQ- 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 is worth noting that neither this bound comparison nor the budget bound comparison in Example sufficient to prove that the UQ-guided approach definitely would outperform the UQ-oblivious approach, reason for the empirical comparisons in Section
15

---

C Proofs
In this section, we provide proofs for the theorems presented in Section 3.4 At the end of the proof, let f(t) and obtained the results in Example 3 and Example 5
The Lemma stated next will prove to be useful.
Lemma For > 1, if min 4 > 1, then we have a high probability that Ci, > li with respect to if f(t) E O(+
Proof. In Section 3.4 we come to the conclusion that
45(1)²
2 1
Pr(Le 6,1 2 1 (v4 )2 )2 = =1- 1/4 14-11
This shows that the event l, > 1,, happens with high probability with respect to t.
Now consider more general setting, where each & has its own 4;
Pr(ler, V/l
Vi 11
4f(()2
i= 1,
2
(14 n2)
Comparing l,,, and l,e, for a particular [n|] gives us the following:
Pr(fia, > l1,1,) Pr((ei,, v.) + (v1 - -1, +2
V1
0)
4f(t1)2
4f(tt)²
2
(v: v1)2
(1z -1)
(C.1)
Since > t and t, > t.
C.1 > 1 1 0 (
C.1 Proof of Theorem 1
Proof. Let S; 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 [e,,,] with limits {
We compute the probability that the algorithm includes the best candidate
last round, namely,
1 E S g and the probability that the UQ scheme returns the best candidate in S |J--
Let Fæ be the round budget for each candidate in St. Rs= = Eý The probability that the best candidate is among the final kept candidate set is
Pr(1 E S(n)==
Pr(1 & St, 1 E Sx-1)
-1
=1
(Pr(1 E St-1) - -Pr(1 St, 1 E Sk-1))
(C.2)
21
1- Pr
lim.
k==
iES
Since the probability that f,, is the smallest among all lR,t (k E [n|] greater than
n
4f(1)² 2 ) (vs - )1
I
PT(e, Bx, > II
16

---

we have
8
71
Af( )2
C.2
(v. - v1)2 )2))
0=
8
4f(E)=0
1 )
18;1 )2)
=
(1
(1: - 11)
k=
2=2
2
R
Therefore, the probability that the scheme returns the best candidate is no less than
Pr(1 S ((2)) Pr
(
L. # ) z (1-1
(1-
B
(C.3)
$ES [J
That is to say, for a given confidence threshold C, there exists a such that as long as min(11, (n)
T, then Pr(Ai:2.... (1,)) 1 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 2 T n, then the best candidate is returned from the algorithm with probability P > (1 L c)) - c).
C.2 Proof of Theorem
The representation of Zob 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 's with a probability of at least - 8, it is necessary to train both candidates for at least the number of steps indicated by the i-th term the sum. Repeating this reasoning for all justifies the sum over all candidates.
Proof. First we show that, given budget Zob, round budget for round k satisfies
Tk 2
S
fogg n
2
(1 + 7 .8))
max 22
S
2
+ +1 [1 (1-1-11(19///2111--" 0)) -1 (L[S&l/2]
>
[&
27 ("16,1111--1111111 5).
The last inequality is derived because [|Sk//2] 2 | 1.
Let T. :=> > - 8). We then show that, for time t:
12 12 ("mmm
4/(1)2 2
1 - (v: 12
2 1 -
3 Pr(bee > (,,t) 2 8.
The second line follows by the definition of 7 (c, Since nh [1S$1/2]+1 we can compute the following probability
Pr(1 E Sk+1l1 Sx) Pr Σ
Ills,ta > mm 211sa/211)
SES
S&
> Pr(
Σ
1ll.R > (1 Z (1Ss/22)
$= ==119 1/2/+1
2 (1 - 8) الاا
17

---

where the first line follows by the definition of the early stopping algorithm (Successive Halving), the second by 7, being non increasinn. Namely, for all / + have 7; S -1|5,1/2]+ and consequently, Pr(ei,R, > R.) 2 Pr(f115,1/21,.a R. 2 1- 8.
Consequently, the probability that the UQ-oblivious approach returns the optimal candidate is
(1 Sk+1/1 E Est)
Pob 2 Pr
0
[lgg211 n1
[log n -1
15 (1 - 8)
k=0
2 1 - nó.
We show in the next Corollary that, for c than nó.
n.ó 2 the probability P obtained in Theorem | is no less
Corollary 6. For the threshold in Theorem and 5 in Theorem let n-f and
(e2 c3. c) = min(T approach returns the best candidate with probability over 1 no B x ( .8) ...
-1 (2 -
c) Then by Theorem
the UQ
i=2
Proof. Let 1/2
7 7 1
( we have
4f(T)²
8
nd
II ==2
(1
2
(vi v1)
This shows us that 7 >
(-1(-= ب c). Consequently, according to Theorem for B = R > T n, the UQ approach returns the best candidate with probability
(1 c)² 2 2c nz.
The UQ-oblivious approach returns the optimal candidate with probability over no if the budget
Bab Rob- But the UQ approach achieves the guarantee with budget B > v22 -- ( 8) which can be empirically substantially smaller than the budget required in Theorem
C.3 Proof of Theorem 4
Proof. Let R2 Ex rk: namely, the total number of epochs allocated for each candidate in Sk- We can guarantee that, for the UQ-oblivious approach, the output candidate ip satisfies
E(v; vn = E
min (ooggto)
U/ vi
SES
[x)
min
V
min Vi rESt
vESx41
0=
[1)]
18
2/13 Li + min 1E
min Ri iESt
k=
[o)
E
2/14 li.
2 [n)] (2 Iogg (m)
2v2n (n)]2
V
/
by inspecting how the approach eliminates candidates and plugging in an upper bound for EE(2), (.) for all & in the last inequality. We can caleulate the bound for the UQ-guided method in
18

---

similar way:
E(u - -v) = 12
min 1/ - vi
$ --1
E
min 1ES++1
min vs)
168%
< E
min (v: B111 + (i, iES
min(v: Ri + li,Ru)) reSt
E
2/14 l., + min 1ESE+1
Re
min R, sESx
K=
1-1-1
E
2/14 L. +
min iES++1
min Ri ) + iE8N+1
min R, min ls 1ES++1
se
k=0
1 -1
2/1; et.mul)
E
B
(R)
2
VTR
The smaller upperbound of the UQ-guided approach than that of the UQ-oblivious counterpart in Theorem 4 simple calculation reveals that
2L
2n
Toga (n))3
Rec
B
by diving the first term by the second:
_ Re
2
2n logg (1))2
B
<I
Be
n [flog2(m)) (n))²
The last inequality holds because both H
E and [log are the number of rounds and are considered
the same.
D Computational Details
Approximating Ar for Candidates. In our probabilistic model, E(y, M (X)) is approximated by Gaussian distribution parameterized by lr and ae. To compute the uncertainty reduction that would result from training each candidate for one additional epoch, we consider the uncertainty as time series in the form of (a.())){_ We examine the uncertainty trendings in NAS-BENCH- 201 [9) Figure shows a certain pattern of uncertainty behavior as increases, both individually and aggregately, for different candidates.
We then model (o.(t))== according to different phases in the following way:
1. For t E (0,6), o(t) increases. We use linear regression to fit the att), namely, (tt) att + by.
2. For (6, 50), at) drops quickly, We use the exponential model to (t),, namely,
(t) bie
3. For t (50, 180), (t)) increases steadily. We use another linear regression fit at)..
19

---

Average
0.03
101
11
HH
171
66
(1)
111
131
15
16)
17
(a) Uncertainty scope for different candidates.
(b) Average uncertainty for different candidates.
Figure 4: Landscape of the uncertainty scope for different epochs.
Confidence
Confidence
Threshold
round
for round
Threshold
AAc
kg kg kj
Candidates
kj" k;
Candidates
(a) Confidence curves in different rounds.
(b) Analysis of the choice of r.
Figure 5: Illustration for confidence curve and discarding mechanisms. After obtaining the confidence curve, threshold determines the number of candidates will keep (ki for round k2 for round 2, and ki for round 3). We choose the smallest such that Ps 2 7 for each round, proceed training with the best performed & 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 model the uncertainty behavior for the whole dataset. This makes the approximation for A,o o(l) (1 + 1) effective and efficient.
An alternative way to approximate A is to Σ (C(y, (x)) - 2 BED.
Σ (Mly, (X) [B M (X)))) bED,-1
Building Probabilistic Model. At any given time the approximation of converged validation loss follows the Gaussian distribution: E(y, M (X)) ~ NNue, o²). In our experiments, = 10, Ph is the current accuracy M M (X)), and oe is the unbiased estimation of the standard deviation of
f(y, M (X))
E Additional Related Work
Freeze-thaw Bayesian optimization. This paper proposes new method to improve Bayesian optimization (BO) for HPO. 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, can also choose old candidates for further evaluation based on the modified El in each round. This method, however, is limited to BO method. In contrast, our UQ scheme applicable the vast number of early stopped and multi-fidelity methods.
HPO
20

---

HyperJump improves HB in that, during HPO. it skips certain rounds for certain candidates if the risk of skipping is within threshold. For the MAS-BENCH-201 trained on ImageNet-16-1 reduces the running time compared to the original HB method (only needs 5.3% fraction of budget to achieve close optimal results achieved by the original HB with a standard full budget), but does not improve the HPO performance (i.e., Top-1 I Rank and Regret). In contrast, our method only needs less than a 3% fraction the budget to achieve close to optimal results and when using around 5% fraction of budget, our method reduces the regret by 33%.
HJ
F Benchmark and Dataset Information
Table 2 consolidates information on the datasets, hyperparameters, fidelity, and dataset sizes for Nas-Bench-201 and LCBench. The datasets for LCBench drawn from various sources [3]
Table 2: Benchmark and Dataset information.
Tasks
Durascts
Hyperparameicrs
Fidelity
Training set
Validation set
Test set
Nos Noo-Bench-201 201
CITAR-10
1--00
25K images images
25K images
10K images
2 [0.13"
1-200
images
5K images
IetgeNet- 16-120
[0.1,23
images
images
3K images
Range: [none, skips conneet, conyooov__r nor por_conv___e _33, avg 3xg_pool_3x3)
Fashion-MNIST
Batch size: [16, 512), log-scale
"Whenever possible, we use the given test split with a 33% test split and ad- ditionally fixed 33% of the training data as validation split. case there no such OpeaML task with a % split available for dataset, test split and across the configura- tions." [
Learning rate: [1e" 1e log-scale
L.Heench
biggs
Momentum: [0.1. 0.991
jasmine
Weight decay: [lc_), lc
1-50
vehicle
Number of layers: [1,5]
33%
volkert
Maximum number of units per layer. [64, 1024), log-scale
Dropout: [0.0,
G More Results on Experiments
We include more results on MAS-Bench-201 and LCBench. For example, Figure 10 and 11 show the results on LCBench, where we proved the consistently better performance the UQ-guided approaches than the UQ-oblivious methods on Fashion-MNIST. Figure 10] shows the results of the validation loss while Figure [ demonstrates the results of regret. UQ-guided approaches obtained an average of over 50% improvement over the UQ-oblivious counterparts.
90
$11
.10
89.5
89.5
SH-
HB
1e-2
le-1
Le0
le:2
le-1
1e0
Fraction Budgets
Fraction Budget
BOTT
SS
9.5
BOUIB
89
8.5
82
80
1e-2
Io-1
120
Fraction Budget
Fraction of Rudget
Figure Results of test accuracy when optimizing on CIFAR-10.
21

---

2
SH
HB
SH+
HBH
0.5
1c=2
To-] Fraction of Budget
160
le
Let
Fraction Budget
8
BOHB
BOHB
SS+
16-2
Ic-1 Fraction of Budget
Icfl
Fraction of Budget
Figure 7: Results of regret (%) when optimizing on CIFAR-10. 10.
70
S11
69
11B
68
S11
66
65
1c0
1e:2
1c:1
1e0
Fraction of Budgets
Fraction Budget
70
68
BOHB
SS
66
BOHB
SS
64
62
1e-2
1e-1
160
Frraction of Budget
Fraction Budget
Figure 8: Results of test accuracy when optimizing on CIFAR-100.
22

---

SH
HB
SH-
HB
Fraction of Budget
Fraction Budget
BOHB
SS+
le22
1e-3
Ieb
Ie-2
1e-1
1e0
Frmction Budget
Budget
Figure 9: Results test accuracy when optimizing on CIFAR-100.
SH
HB
15
SH
HB
13
0.3
0.6
0.9
Fraction of Budgets
Fraction of Budget
-OBBB
SS
BOHB+
SS-
14
0.3
0.6
0.9
0.6
Fraction of Budget
Fraction of Budget
Figure 10: Results validation error for optimizing on Fashion-MNIST.
4
IIB
SI
2
0
0.3
0.6
0.6
Fraction of Budget
Fraction of Budget
BOHB
SS
BOHB
0.3
0.9
0.3
0.9
Fraction of Budget
Fraction of Budget
Figure Results of regret (%) on test accuracy optimizing on MaSHIon-MNIST.
23

---

H Experiments on Other Iterative Learners
We focus on DNNs in our experiments because (1) DNNS are among the most influential models today and (2) DNN training takes long time so selecting the optimal hyperparameters is critical concern, making the problem more pressing.
Even though we focus on DNN methods, our approach can be applied to other iterative learners. We consider ridge regression problem trained with stochastic gradient descent on this objective function with step size _01 02/v2- T. The l2 penalty hyperparameter À [10-6, 10 was chosen uniformly at random on a log scale per trial. We use the Million Song Dataset year prediction task [27] with the same experiment settings in the original SH paper. We show the results of ridge regression "SH" and "SH+". Figure [2 shows the 1 Rank results and the regret of the test error for different fractions of budgets. The average results of 30 repetitions are reported. The benefits are obvious: SH+ obtained an average of over 40% improvement over the SH.
0.05
SH
SH
Top Rank
0.04
7-
SH+
Regret
0.03
SH-
0.02
0.01
0.03
0.2
0.4
0.6
0.8
0.03
0.2
0.4
0.6
0.8
Fraction of Budgets
Fraction of Budgets
Figure 12: Results of Top-1 Rank and Regret on test error for optimizing ridge regression.
Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Section 1
Section 3.4 and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We state them at the end of Section The key characteristic of the UQ method is the necessity to rank multiple learners during the HPO process. Gradient-bass 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
mostly suitable for iterative learners, and needs adaptations for other learners: To go beyond, it could be, for instance, applied the model selection work previous studies (II that use training dataset size as the budget dimension. In this case, the learner does not need to be iterative; the selection
24

---

is based on the validation loss history trained with incremental dataset sizes. The UQ component can still guide the configuration selection and budget allocation the HPO process.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes].
Justification:
See Section 3.4 and appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We include them in Section and the supplemental material.
Guidelines:
25

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
oow.ssabbsisiioooioooooooooooiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https Codeeuumiiii wwwiiisssooosiiiiio
c/nips.cc/publi///guu
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
26

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
See Section 4
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
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 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 include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful 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 the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification:
See Section
Guidelines:
The answer NA means that the paper does not include experiments.
27

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htcpge///aarrpssc.ccaa/ll/hcccce
Answer:
[Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration 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 D our work is a general algorithm aiming at optimizing HPO and belongs foundational research; its societal impacts 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 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
functioning correctly, harms that could arise when the
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
28

---

Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the creators for the existing assets and included the name the license. See Section 4.1
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi twwoeethcde...m caree.com/aee com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
See supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "Scnkbmenq8", "reviewer": "Reviewer_BPGo", "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.", "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. \n\n2. 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$?\n\n3. Theorems:\n- How to interpret the assumptions of Theorem 1?\n- 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.\n\n4. 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.\nThe proof of Theorem 1 refers to two assumptions but it looks the pdf was not compiled correctly so the reference hyperlinks are missing", "limitations": "The work is regarding a general algorithm aiming at optimizing HPO and belongs to a foundational research; its societal impacts are neutral.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is shown by theory and empirical study that the proposed UQ method can enhance the existing hyperparameter tuning method like successive halving, which suffers from model uncertainty and incorrectly eliminating highly performant hyperparameter values", "weaknesses": "Estimating the mean and variance of the performance metrics curve may need to take some epochs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Comment 1: On page 4, it is stated that \n$\\hat{v}$ and $\\sigma^2$ are estimated with N=200 epochs. My understanding is that the first N=200 epochs are only for estimating $\\hat{v}$ and $\\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.**\n\nResponse: With our method, after any number of epochs, we can use the formula on page 4 to estimate the loss and uncertainty for any $N$ values. We do not need to wait for $N$ epochs before estimating. We plug in $N=200$ to the formula to estimate the uncertainty value at the $200$ epochs when most models would have already entered the convergence stage.\n\n>**Comment 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 \n$Z$ explicitly doesn’t yield any useful products, perhaps there is no need to estimate $Z$ and we just need to estimate \n$\\alpha^{\\mathbf{u}}$?**\n\nResponse: Estimating $Z$ is an indirect way to estimate $\\alpha^{\\mathbf{u}}$ in our setting so it allows correlation between the candidates.\nWe can also estimate $\\alpha^{\\mathbf{u}}$ directly for each candidate; the experiments show satisfying results as well.\n\n> **Comment 3: Theorems:\nHow to interpret the assumptions of Theorem 1?\nDoes 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.**\n\nResponse: Interpretation of the assumptions of Theorem 1: \n\nThe assumption $ \\nu_i=\\lim\\limits_{\\tau \\to \\infty} \\ell_{i, \\tau}$ implies that the machine learning model will eventually converge after enough epochs. $\\nu_i$ here denotes the converged loss for the machine learning model.\n\nTheorem 2 analyzes the UQ-oblivious early stop approaches and can be applied to methods such as HB as long as there are intermediate results available for comparison. \nWe only make assumptions that the machine learning models will eventually converge after enough epochs and without loss of generality, these models are ordered according to their converged loss, namely, $\\nu_1 \\le \\nu_2 \\le \\cdots \\le \\nu_n$.\nWe make these assumptions regardless of the HPO method and they are easy to verify by looking into individual candidate's validation loss curve.\n\n>**Comment 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.**\n\nResponse: The representation of $z_{ob}$ on the right-hand-side of the inequality is very intuitive:\nFor each $i$, to merely verify that the $i$th candidate's final loss is higher than the best candidate's with a probability larger than or equal to $1-\\delta$, one must train each of the two candidates at least a number of steps equal to the $i$th term in the sum. \nRepeating this argument for all $i$ explains the sum over all candidates.\n\n\nThe two assumptions in the proof of Theorem 1 are (1): $\\ell(\\mathbf{y}, M_{\\gamma_c}^{*}(\\mathbf{X})) = \\lim\\limits_{t\\to \\infty}\\ell(\\mathbf{y}, M_{\\gamma_c}^{t}(\\mathbf{X}))$  exists for $\\gamma_c \\in \\Gamma$ and (2) $ \\nu_i=\\lim\\limits_{\\tau \\to \\infty} \\ell_{i, \\tau}$. As addressed in the previous question, these assumptions imply that the machine learning model will eventually converge after enough epochs. \nWe will fix that in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "36zp8Wv6dD", "reviewer": "Reviewer_P7Zr", "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.", "questions": "- How can the epistemic uncertainty be quantified for other learners?\n- Why does the performance of X+ always improve already over X if there is no budget used?\n- 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.\n- 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 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.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a novel and interesting approach to HPO considering uncertainties throughout the HPO process to incorporate them and making decisions more cautiously.\n- The approach is theoretically grounded and the authors also provide a theoretical framework for their method.\n- In experiments, the method also performs favorably compared to methods that do not leverage the information about uncertainty.", "weaknesses": "- 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.\n- 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.\n- It could be made clearer that the authors specifically target multi-fidelity/early stopping methods with their method.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Comment 1: 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.**\n\nResponse: We focus on DNNs in our experiments because (1) DNNs are among the most influential models today and (2) DNN training takes a long time so selecting the optimal hyperparameters is a critical concern, making the problem more pressing. \n\nEven though we focus on DNN methods, our approach can be applied to other iterative learners.\nWe consider a ridge regression problem trained with stochastic gradient descent on this objective function with step size $.01/\\sqrt{2 + T}$.\nThe $l_2$ penalty hyperparameter $\\lambda \\in [10^{-6}, 10^0]$ was chosen uniformly at random on a log scale per trial.\nWe use the Million Song Dataset year prediction task [1] with the same experiment settings as in the original SH paper.\nIn the limited time, we managed to get the results of ridge regression on \"SH\" and \"SH+\". \nFigure 12 in the attached pdf in the global rebuttal shows the Top-1 Rank results and the regret of the test error for different fractions of budgets.\nThe average results of 30 repetitions are reported.\nThe benefits are obvious: SH+ obtained\nan average of over 40\\% improvement over the SH.\n\n[1] Lichman, M. UCI machine learning repository, 2013. URL http://archive.ics.uci.edu/ml.\n\n>**Comment 2: 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.\nHow can the epistemic uncertainty be quantified for other learners?**\n\nResponse: For other iterative learners (e.g., regression problem trained with stochastic gradient descent on the objective function with step size and $\\ell_2$ penalty hyperparameter $\\lambda$), we can leverage the loss curves of the training process of the models we have already observed and use the formula in page 4 to estimate the epistemic uncertainty.\n\n>**Comment 3: Why does the performance of X+ always improve already over X if there is no budget used?**\n\nResponse: We have updated Figure 3 with the fixed $x$-axis label in the attached pdf in the global rebuttal. There was a minor typo in the figure: The label 0 in the $x$-axis was supposed to be 0.03. \nFigure 3 shows that the UQ-guided approach can always achieve better Top-1 Rank and regret results than the UQ-oblivious method does even with a small budget (3\\% of the standard full budget).\n\n>**Comment 4: 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.**\n\nResponse: The key issue is that identifying the top-1 candidate during the HPO process is challenging.\nAs shown in Figure 1, candidates that initially appear to be top-1 often turn out to be inferior after convergence. Our entire paper, therefore, focuses on how to quantify this uncertainty of the model quality during the intermediate steps of HPO and integrate this uncertainty into the selection process to maximize the likelihood of choosing the right candidate.\n\n>**Comment 5: 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?**\n\nResponse: As mentioned in Figure 2, the budget is evenly assigned among candidates in each round, so each candidate will adopt $\\frac{R}{K}$ budget resource ($R$ is the round budget and $K$ is the number of candidates kept in this round). That is to say, if, according to our probabilistic model, we need to keep more candidates to evaluate, then the budget for each candidate in this round is reduced. Likewise, more budgets are assigned to each one if fewer candidates remain.\nNote that we determine the number of candidates to keep by considering the tradeoff between the risks of discarding the best candidate and the training budget each top candidate can get.\n\n>**Comment 6: 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\".**\n\nResponse: \"8-22 steps of the exploration\" here indicate that the best candidate is discarded after that number of iterations of training (because its validation loss is not in the better half among all the candidates that still remain).\nTo make it clear and consistent with Figure 1, we will change the term \"steps of exploration\" to \"iterations of training\". We will also fix other linguistic issues in the paper.\n\n>**Comment 7: 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.**\n\nResponse: We will replace \"a model\" with \"a candidate\" to denote a candidate hyperparameter configuration that can include hyperparameters for both the model and the learning algorithm.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rQ2i4vYaGR", "reviewer": "Reviewer_gRaV", "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.", "questions": "**a)** \nWhy do you claim that \"data uncertainty is constant\"? (This is in the beginning of section 3.1)\n\n**b)** \nSection 3.3. -- exploration vs exploitation: is k_1 - 1 == k'_i ?\n\n**c)** \nSection 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.\n\n**d)** \nWhich parameters does the UQ approach have and that a user must set? How do those parameters affect the improvements attainable by UQ?\n\n&NewLine;  \n**Comments:**\n\n- Section C.1 of the appendix has some missing pointers to assumptions.\n\n- The evaluation plots would all be much easier to read if the y-axis was labelled. \n\n- 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": "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**Originality:** \n\nThe authors claim the method is new and that they only found one work that accounts for uncertainty (reference 30), however there are more works that account for uncertainty when performing hyper-parameter optimization. For example, the following:\n\n[a] Mendes, Pedro, et al. \"HyperJump: accelerating HyperBand via risk modelling.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.\n\nThis other work may also be of relevance for the authors:\n\n[b] Swersky, Kevin, Jasper Snoek, and Ryan Prescott Adams. \"Freeze-thaw Bayesian optimization.\" arXiv preprint arXiv:1406.3896 (2014).\n\nI would have liked to see a comparison of the proposed method against reference [30], given that it was the only work the authors found that accounted for uncertainty, and also against [a].\n\n&NewLine;  \n**Quality:** \n\nThe claims seem well supported and the theoretical methodology sound. The methods used are appropriate. Weaknesses could be discussed in more detail and comparison agains related work could be improved/extended.\n\n&NewLine;  \n**Clarity:** \n\nOverall, the paper is well written. There are a couple of sentences here and there that could be improved, but it doesn't substantially affect understandability. \n\nI believe the main manuscript should have pseudo-code illustrating the extra steps that should be added to any iterative learner that a user would like to change to account for model uncertainty. There is one example in the supplemental material but it seems to be specific to SH. What is generalisable from that example and what is not?\n\nThe manuscript is quite heavy on math and it seems like some parts could profit from an intuition-guided explanation. For example, in section 3.2, paragraphs \"Decomposition of momentum and the underlying structure of the metric\" and \"Solving for the Momentum Mean and Variance\" could have a more high-level description of why it is important to analyse those decomposed parts, what type on information is expected to be extracted from each, and how that information can contribute to improving the selection of the (near-)optimal configuration. Some math details can be relegated to the supplemental material, should space be a concern.\n\nFinally, which parameters does the UQ approach have and that a user must set? How do those parameters affect the improvements attainable by UQ?\n\n&NewLine;  \n**Significance:**\n\nImproving the efficiency of hyper-parameter optimization is a relevant problem and efficient methods that are shown to substantially improve over existing methods are relevant. However, I felt the current version of the manuscript misses comparisons against recent related work.", "weaknesses": "See above for strengths and weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Comment 1: Why do you claim that \"data uncertainty is constant\"? (This is in the beginning of section 3.1)**\n\nResponse: In our setting, each candidate is trained on the same set of training data so the data uncertainty among different candidates is the same.\n\n> **Comment 2: Section 3.3. -- exploration vs exploitation: is $k_1 - 1 == k'_i$ ?**\n\nResponse: $k'_i$ is just another name for $k_i -1$. So yes, $k_i -1 == k'_i$.\n\n> **Comment 3: 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.**\n\nResponse: Yes, we mean the UQ method can return the best candidate with probability greater than $1-n\\delta$.\nTo guarantee the same probability of identifying the optimal candidate, the UQ-oblivious method needs a budget $B_{ob}$ greater than what the UQ method needs ($B_{UQ}$). `But' here stresses that $B_{UQ}$ is smaller than $B_{ob}$. The expression denotes a lower bound budget, specifically, $\\sqrt[4]{2} \\cdot \\gamma^{-1}(\\tfrac{\\nu_2-\\nu_1}{2}, \\delta) \\cdot n\\simeq \\gamma^{-1}(\\tfrac{\\nu_2-\\nu_1}{2}, \\delta) \\cdot n$, for the UQ method to guarantee the 1-$n\\delta$ success probability. This lower bound is proved in Corollary 6.\n\n> **Comment 4: Which parameters does the UQ approach have and that a user must set? How do those parameters affect the improvements attainable by UQ?**\n\nResponse: \nParameters for the UQ approach include the total budget and the predefined budget resources (e.g., training epochs) for each round. We set these parameters according to the same default value as in the paper HB.\nTo quantify the uncertainty in the HPO process, we leverage the validation history to construct an estimated loss curve. This estimation uses parameters $\\mathbf{k}_t$ to model the loss curve from $F_t$ samples for each candidate. More complex parameters for modeling the loss curve may better fit the current observed loss curve but at a risk of losing generality. $F_i$ is always small in our experiments because each sample requires training an entire model.\n\n>**Comment 5: 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.**\n\nResponse: We will add a detailed discussion on the limitations of our proposed methods in the revision. Please see the global comment ``Limitations of the current work\".\n\n>**Comment 6: The work may also be of relevance for the authors:\n[b] Swersky, Kevin, Jasper Snoek, and Ryan Prescott Adams. \"Freeze-thaw Bayesian optimization.\" arXiv preprint arXiv:1406.3896 (2014).**\n\nResponse: 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.\nInstead of always sampling new candidates, it can also choose old candidates for further evaluation based on the modified EI in each round.\nThis method, however, is limited to BO method.\nIn contrast, our UQ scheme is applicable to the vast number of early stopped and multi-fidelity-based HPO methods.\n\n>**Comment 7: I would have liked to see a comparison of the proposed method against reference [30], given that it was the only work the authors found that accounted for uncertainty, and also against [a].\n[a] Mendes, Pedro, et al. \"HyperJump: accelerating HyperBand via risk modeling.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.**\n\nResponse: Comparison with the HyperJump (HJ) work.\n\nHyperJump improves HB in that, during HPO, it skips certain rounds for certain candidates if the risk of skipping is within a threshold.\nFor 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).\nIn 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\\%.\n\nComparison with [30].\nThe performance gaps (regret) of [30] are lower than that of SH (a reduction of 30\\%) but the execution time used for [30] is two times that of SH. This is because [30] needs to evaluate most of the models despite that it can skip some intermediate evaluations based on the upper-bound predictions.\nOur UQ method, however, can reduce 50\\% of regret with the same budget resources as SH.\n\n>**Other comments on Clarity.**\n\nWe will address these according to the comments and add a more high-level description for paragraphs \"Decomposition of momentum and the underlying structure of the metric\" and \"Solving for the Momentum Mean and Variance\".\n\nWe will also include the pseudo-code for the other UQ-guided methods.\n\nThe two assumptions in the proof of Theorem 1 are (1): $\\ell(\\mathbf{y}, M_{\\gamma_c}^{*}(\\mathbf{X})) = \\lim\\limits_{t\\to \\infty}\\ell(\\mathbf{y}, M_{\\gamma_c}^{t}(\\mathbf{X}))$  exists for $\\gamma_c \\in \\Gamma$ and (2) $ \\nu_i=\\lim\\limits_{\\tau \\to \\infty} \\ell_{i, \\tau}$. These assumptions imply that the machine learning model will eventually converge after enough epochs. We will fix this in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dsnQN7g0id", "reviewer": "Reviewer_ffRZ", "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.", "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 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.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "•\tUniversalizing provided improving technique (originality and quality). \n•\tUsing different conventional HPO algorithms for demonstration novel approach (clarity and quality).\n•\tStrong mathematical background and proofs (quality, originality and significance).\n•\tTheorical analysis presented guided scheme (quality and significance).\n•\tClear experiments methodology and results (clarity).", "weaknesses": "Perhaps authors should provide more detailed discussion about UQ-scheme limitations and adaptation for non-iterative learners and add some links about such learners\n\nMistypes and etc.\nAppendix C, page 21, lines 2 and 3 in the first paragraph. Broken links.\nAppendix D, page 24, line four in the first paragraph. Broken equation link.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**Comment 1: 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?**\n\nResponse: We compare different numbers of initial candidates in the same setting for NATS-BENCH-201 on ImageNet. \n\n|                    |     SH     |        |     SH+    |        |\n|:------------------:|:----------:|:------:|:----------:|:------:|\n| Initial Candidates | Top-1 Rank | Regret | Top-1 Rank | Regret |\n|         50         |     4.2    |  5.06  |    1.96    |  2.52  |\n|         500        |    22.95   |   5.3  |    5.29    |  2.74  |\n\nWhen the total number of initial candidates increases, both SH and SH have a higher Top-1 Rank; the regret, however, stays stable, showing that the UQ-scheme SH+ scales well as the number of initial candidates increases.  \n\n> **Comment 2: Perhaps authors should provide more detailed discussion about UQ-scheme limitations and adaptation for non-iterative learners and add some links about such learners.**\n\nResponse: We will add a detailed discussion on the limitations of our proposed methods in the revision. Please see the global comment ``Limitations of the current work\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for the insightful feedback and suggestions. We address the common concern of the reviewers here:

## Limitations of the current work


The key characteristic of the UQ method is the necessity to rank multiple learners
during the HPO process. Gradient-based HPO methods [1], for instance, may not benefit
from our UQ-guided scheme because of their sequential properties.

### For non-iteration learners
The current version of our method is most suitable for iterative learners. To go
beyond, it could be, for instance, applied to the model selection
work in previous studies [2] 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.

[1] Micaelli, Paul, and Amos J. Storkey. ``Gradient-based Hyperparameter Optimization Over Long Horizons.” 34th Advances in Neural Information Processing Systems (NeurIPS). 2021.

[2] Mohr, Felix, and Jan N. van Rijn. ``Towards model selection using learning curve
cross-validation.” 8th ICML Workshop on automated machine learning (AutoML). 2021.

Meta-review: 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.*"
Decision: Accept (poster)