UQ-Guided Hyperparameter Optimization for Iterative Learners

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?

Response: We compare different numbers of initial candidates in the same setting for NATS-BENCH-201 on ImageNet.

When 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.

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.

Response: 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".

Comment 1: Why do you claim that "data uncertainty is constant"? (This is in the beginning of section 3.1)

Response: In our setting, each candidate is trained on the same set of training data so the data uncertainty among different candidates is the same.

Comment 2: Section 3.3. -- exploration vs exploitation: is $k_1 - 1 == k'_i$ ?

Response: $k'_i$ is just another name for $k_i -1$. So yes, $k_i -1 == k'_i$.

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.

Response: Yes, we mean the UQ method can return the best candidate with probability greater than $1-n\delta$. To 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.

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?

Response: Parameters 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. To 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.

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.

Response: 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".

Comment 6: The work may also be of relevance for the authors: [b] Swersky, Kevin, Jasper Snoek, and Ryan Prescott Adams. "Freeze-thaw Bayesian optimization." arXiv preprint arXiv:1406.3896 (2014).

Response: This paper proposes a new method to improve Bayesian optimization (BO) for HPO. It avoids the limits of the expected improvement (EI) criterion in naive BO which always favors picking new candidates rather than running old ones for more iterations. Instead of always sampling new candidates, it can also choose old candidates for further evaluation based on the modified EI in each round. This method, however, is limited to BO method. In contrast, our UQ scheme is applicable to the vast number of early stopped and multi-fidelity-based HPO methods.

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]. [a] Mendes, Pedro, et al. "HyperJump: accelerating HyperBand via risk modeling." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.

Response: Comparison with the HyperJump (HJ) work.

HyperJump improves HB in that, during HPO, it skips certain rounds for certain candidates if the risk of skipping is within a threshold. For the NAS-BENCH-201 trained on ImageNet-16-120, HJ reduces the running time compared to the original HB method (only needs a 5.3% fraction of budget to achieve close to optimal results achieved by the original HB with a standard full budget), but it does not improve the HPO performance (i.e., Top-1 Rank and Regret). In contrast, our method only needs less than a 3% fraction of the budget to achieve close to optimal results and when using around 5% fraction of budget, our method reduces the regret by 33%.

Comparison with [30]. The 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. Our UQ method, however, can reduce 50% of regret with the same budget resources as SH.

Other comments on Clarity.

We 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".

We will also include the pseudo-code for the other UQ-guided methods.

The 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.

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.

Response: 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.

Even though we focus on DNN methods, our approach can be applied to other iterative learners. We consider a ridge regression problem trained with stochastic gradient descent on this objective function with step size $.01/\sqrt{2 + T}$. The $l_2$ penalty hyperparameter $\lambda \in [10^{-6}, 10^0]$ was chosen uniformly at random on a log scale per trial. We use the Million Song Dataset year prediction task [1] with the same experiment settings as in the original SH paper. In the limited time, we managed to get the results of ridge regression on "SH" and "SH+". Figure 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. The average results of 30 repetitions are reported. The benefits are obvious: SH+ obtained an average of over 40% improvement over the SH.

[1] Lichman, M. UCI machine learning repository, 2013. URL http://archive.ics.uci.edu/ml.

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. How can the epistemic uncertainty be quantified for other learners?

Response: 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.

Comment 3: Why does the performance of X+ always improve already over X if there is no budget used?

Response: 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. Figure 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).

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.

Response: The key issue is that identifying the top-1 candidate during the HPO process is challenging. As 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.

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?

Response: 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. Note 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.

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".

Response: "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). To 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.

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.

Response: 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.

Comment 1: On page 4, it is stated that $\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.

Response: 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.

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 $Z$ explicitly doesn’t yield any useful products, perhaps there is no need to estimate $Z$ and we just need to estimate $\alpha^{\mathbf{u}}$?

Response: Estimating $Z$ is an indirect way to estimate $\alpha^{\mathbf{u}}$ in our setting so it allows correlation between the candidates. We can also estimate $\alpha^{\mathbf{u}}$ directly for each candidate; the experiments show satisfying results as well.

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

Response: Interpretation of the assumptions of Theorem 1:

The 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.

Theorem 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. We 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$. We make these assumptions regardless of the HPO method and they are easy to verify by looking into individual candidate's validation loss curve.

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.

Response: The representation of $z_{ob}$ on the right-hand-side of the inequality is very intuitive: For 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. Repeating this argument for all $i$ explains the sum over all candidates.

The 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. We will fix that in the revision.