{'fraction_non_alphanumeric': 0.034371026619088633, 'fraction_numerical': 0.01160739920429843, 'mean_word_length': 4.619151878312976, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach

The rising growth of deep neural networks (DNNs) and datasets in size motivates the need for efficient solutions for simultaneous model selection and training. Many methods for hyperparameter optimization (HPO) of iterative learners including DNNs attempt to solve this problem by querying and learning a response surface while searching for the optimum of that surface. However, many of these methods make myopic queries, do not consider prior knowledge about the response structure, and/or perform biased cost-aware search, all of which exacerbate identifying the best-performing model when a total cost budget is specified. This paper proposes a novel approach referred to as Budget-Aware Planning for Iterative Learners (BAPI) to solve HPO problems under a constrained cost budget. BAPI is an efficient non-myopic Bayesian optimization solution that accounts for the budget and leverages the prior knowledge about the objective function and cost function to select better configurations and to take more informed decisions during the evaluation (training). Experiments on diverse HPO benchmarks for iterative learners show that BAPI performs better than state-of-the-art baselines in most of the cases.


Introduction
Hyperparameter optimization (HPO) for machine learning models, and pipelines is the task of automatic tuning of those parameters which affects model selection and training. A variety of HPO approaches have been developed for classical ML models, e.g., SVMs, random forests, utilizing Bayesian optimization (BO) [43; 44], meta-learning [10; 12], and ensembling [46; 38; 28; 8] to name a few. For HPO, the inclusion of modern deep neural networks (DNNs) as a pipeline, introduces a temporal dimension to the problem of selecting pipeline queries due to the iterative nature of DNNs. Fixing the number of training epochs per query is clearly inefficient since poorly performing pipelines will waste resources, leading to more promising candidates not being identified when the resource budget is small. This paper considers the problem of HPO for such iterative learners (ILs) under a fixed total budget. In this setting, the budget is defined as some measure of resource cost for evaluating queries such as wallclock time or energy. The key challenge is to reason about the available budget to intelligently select the candidate queries for evaluation to uncover high-quality configurations within the remaining budget. BO is known to be an effective framework to solve such problems. However, most BO algorithms ignore the fact that the cost of different configurations/queries can vary significantly and are unknown prior to their evaluation. We refer to this problem of utilizing BO to select amongst iterative learners under a constrained budget as budget-aware Bayesian optimization.
The key idea behind BO for HPO is to learn a response surface (e.g., Gaussian process) which serves as a surrogate for test set performance and use it to perform a sequence of queries by trading off exploration and exploitation. The response and cost modeling, and the planning of querying a sequence of different configurations have individually been addressed in the BO literature. To some extent, the interaction of these two components was studied as well. For ILs, modeling the side-information in the form of the shape of learning curves (i.e., accuracy vs. training epochs) will allow us to make fine-grained decisions such as early stopping to save resources. In our problem setting, we refer to the learning curve as the structured response. The structure of responses have been considered and modeled to varying degrees in methods that extrapolate performance to determine good candidates [23; 7] as well as in BO over vector-valued responses [51; 37]. However, none of these settings consider a fixed total budget. To summarize the drawbacks of prior work for our problem setting: standard approaches for handling structured responses, heterogeneous cost-modeling (i.e., different queries have varying costs), and query selection have inefficiencies or are even inaccurate in some cases, especially when applied to the fixed budget setting. Standard cost-aware modeling for BO utilizes a separate model for cost predictions and then weights the selection of the next candidate query by these predictions [43]. However, cost-aware modeling via weighting suffers from a known pathology where the method tends to select low-cost queries with lower accuracy leading to an overall poor performance [30; 3]. Fundamentally, the issue is one of mis-calibration between the response and cost models. For query selection, non-myopic BO methods provide approximations of varying quality to the optimal solution defined by the Bellman recursion for BO [39; 26; 17]. These non-myopic methods [26; 50; 52; 18; 29; 31; 3] use a variety of techniques to solve the sequence of nested integrations and maximizations including dynamic programming and rollouts. However, only the two most recent methods of Lee et al. [31] and Astudillo et al. [3] take the heterogeneous cost and a finite budget into account. Lee et al. [31] proposed to leverage the known pathology of standard cost-aware modeling to promote early exploration but the resulting policy does not adapt its horizon to the remaining budget. Astudillo et al. [3] also propose a non-myopic policy, but the horizon adaptation of their method is post-hoc, i.e. already selected queries are removed depending on the remaining budget. Contributions: Our proposed solution BAPI executes a non-myopic query selection policy by wrapping standard BO in a layer of budget-aware planning for iterative learners. The key innovations of BAPI include leveraging side-information and expert knowledge such as the objective function's monotonicity, heteorgenity of query costs, and linearity of cost w.r.t training epochs into the planning procedure; overcoming known pathologies of standard cost-aware BO; and principled approach for adapting the horizon to the amount of remaining budget. Therefore, our technical contributions span both budgeted non-myopic BO and hyper-parameter optimization sub-areas. The list of synergistic contributions made by this paper are as follows: • Development of a new approach for budget-aware non-myopic BO enabling an adaptive horizon to solve HPO problems for iterative learners. To the best of our knowledge, this is the first work that proposes a budgeted non-myopic approach specifically for HPO.
• Refining previous response modeling approaches by leveraging the monotonicity of the objective function through model derivatives to enable: (1) a new conservative stopping estimation approach to decide when a learner becomes -close to its asymptotic value, and (2) a general modeling approach with minimal assumptions about the shape of the response resulting in accurate extrapolation for improved decision-making.
• Design of a new efficient early termination method aimed to early stop the training of poorly performing HP configurations.
• A new alternative kernel for modeling the training cost of iterative learners while capturing the linearity of the cost w.r.t the number of epochs and its variability across different HPs • Empirical evaluation on several state-of-the art benchmarks to demonstrate the performance of BAPI compared to algorithms designed for HPO, generic BO, and non-myopic BO.

Problem Setup and Background
In this section, we state our problem and briefly review Gaussian processes, Bayesian optimization, and myopic vs. non-myopic query selection policies. Consider the problem of sequentially optimizing a blackbox objective function f over the input space X where the evaluation of each candidate input x ∈ X is expensive and where the cost c of each input is unknown before the evaluation. In the context of HPO for iterative machine learning models, each input candidate z := [x, t], where x represents model/pipeline hyperparameters and t ∈ T =[1 .
is the number of training epochs. We let the objective function f (x, t) be defined as the accuracy 1 and the unknown cost c(x, t) be defined as the training time. The objective is to identify the maximum of f in a number of queries whose cumulative cost is bounded by a total budget B T . Let Z := X × T , our problem can be stated as where P (Z) denotes the power set of Z and Z = {z 1 . . . z h } is the sequence of inputs evaluated until the budget B T is exhausted. In other words, the optimal HP z * is defined as z * ← arg max Z f (z) with z * ∈ Z and z∈Z c(z) ≤ B T . The problem in Equation (1) is solved using a non-myopic policy, where at each iteration, the algorithm accounts for the sequence of inputs that can be evaluated within the remaining budget, i.e., the horizon h is adaptive. We define the non-myopic setting later in this section, which is similar to the setting considered in Lee et al. [31] and Astudillo et al. [3].
We focus on problem settings where the objective function is monotonic in the number of epochs t. Specifically, for a fixed hyperparameter x, f (x, t) ≤ f (x, t ) when t ≤ t . This is a reasonable assumption for iterative learners. Even if monotonicity does not hold over all training epochs, keeping track of the best model over training epochs is a standard practice [6].
Gaussian processes: GPs are characterized by a mean function m and a covariance or kernel function K. If a function f is sampled from GP(m, K), then f (x, t) is distributed normally ) for a finite set of inputs from [x, t] ∈ X × T . The predictive mean and uncertainty for a GP for any new input z * ∈ Z is defined as: Z is the set of evaluated inputs and Y is their corresponding function values.
A typical choice to model blackbox functions with a temporal component is using a product kernel . K x , defined over the input space x ∈ X , is often selected to be an RBF For the temporal component K t , previous work for GPs over iterative learners [45] proposed an exponential decay (ED) kernel, defined as K t (t, t ) = β α /(t + t + β) α , to model decreasing covariance with increasing time. However, this kernel does not guarantee that the predictive mean of GP or sampled functions would necessarily follow a desired monotonic shape. Nguyen et al. [37] argued that the use of ED is not appropriate for reinforcement learning models where the reward might follow a logistic shape and proposed the use of an RBF kernel for K t .
Bayesian optimization and non-myopic query policies: BO is a sequential, model-based approach for optimizing blackbox functions [42]. BO is often performed with the specification of a GP prior over the function, and an acquisition function. The GP posterior acts as a surrogate for the true unknown response. The potential or utility of points in the input space to be the optimizer is scored by the acquisition function. Two examples of acquisition functions are expected improvement (EI) and upper confidence bound (UCB) and both are considered myopic since they only aim to maximize the function for the next query without accounting for the effect of possible future queries. We review some standard facts for optimal sequential decision-making [39; 17]. Consider having collected a set of i responses D i and let u denote the utility of D i for maximizing f (z) = y, i.e., u(D i ) = max (z,y)∈D i y.
The marginal gain in utility of the query z w.r.t. D i is expressed as: The one-step expected marginal gain is equivalent to the expected improvement (EI) strategy [35]: Now, consider the case where r steps are remaining. The r-steps expected marginal gain can be expressed through the Bellman recursion as [17]: Maximizing (4) w.r.t. z results in the optimal r-steps "lookahead" query. Being a sequence of r nested integrals of maximizations, optimizing (4) is intractable for even small r.
Lower bound to optimal policy: The previous discussion focused on the optimality of selecting single queries. We review recent work by [17] which makes a connection between single selection and batch selection of size r, Z = {z 1 . . . z r }. Assuming parallel evaluation, the optimal set of selected points Z * maximizes the expected marginal utility of the new associated evaluations Y = {y 1 . . . y r }: Jiang et al. [17] showed that choosing a query z * ∈ Z * is equivalent to solving arg max z V (z|D) and that the second term of (6) is a lower bound to the second term in (4): Given this observation, Jiang et al. [17] proposed approximating the optimal policy (4) by optimizing its lower bound (6) which is equivalent to optimizing the batch EI known as q-EI. Jiang et al. [17] proposed using joint q-EI which is budget-unaware and scales poorly with increased dimensions [49].

Proposed Approach
In this section, we start by providing a high-level overview of the proposed BAPI algorithm and briefly explain its key components. Next, we provide complete details of each component. First, we describe how to perform an efficient budget-aware non-myopic search. Second, we explain our approach to model structured response for iterative learning which can be used to estimate conservative stopping for increased resource-efficiency. Finally, after describing an alternative kernel for the cost model, we provide the full BAPI approach with all its component coherently put together.

Overview of BAPI Algorithm
Let GP f and GP c be the surrogate probabilistic models learned given a set of observed data points D i of the objective function f and the cost function c respectively. Let µ c and σ 2 c be the predictive mean and variance of GP c and µ and σ 2 be the predictive mean and variance of GP f . As shown in Figure 1, BAPI is a sequential algorithm with three key components listed below:

Learning GPs of Structure Responses
Linear Kernel w.r.t epochs  Figure 1: Overview of BAPI algorithm illustrating its three key components explained in section 3.1

Evaluation of Iterative ML Model with Early Termination
1. Learning surrogate models: We build two surrogate models GP f for the objective function and GP c for the cost function by fitting independent GPs using queries evaluated in the past. We enforce shape constraint on the posterior of GP f with respect to t (epoch number) to incorporate prior knowledge about the monotonicity of the function. We use a special kernel for GP c to leverage our knowldge about the variability of the cost across different HPs and its linearity with respect to t.
2. Budget aware non-myopic optimization with adaptive horizon: We perform non-myopic optimization to approximate the optimal lookahead horizon Z * defined as the potential sequence of inputs that can be evaluated until their conservative stopping t opt x without violating the remaining budget B r : While constructing the horizon Z * , each input x i is selected based on its expected improvement. The associated conservative stopping t opt x i and cost µ c (x i , t opt x i ), are estimated upon the input selection. 3. Evaluation with early termination: From Z * obtained from the second step, we select the input with highest expected improvement per unit cost at its estimated conservative stopping for evaluation. After training the model for a fraction of the maximum number of epochs, we re-estimate the performance of the input at its conservative stopping epoch. We early terminate the training if the expected performance is poor with high certainty.

Budget aware BO with adaptive horizon
Approximating the non-myopic optimization with the batch expected improvement q-EI, where the batch size q is equal to the horizon of the lookahead optimization r, is an efficient approach [17]. However, the joint q-EI via reparametrization trick and Monte Carlo sampling proposed in Wang et al. [47] and used in Jiang et al. [17] requires the size of the batch to be fixed in advance and solves a joint one-shot optimization problem of (d × q) dimensions. Challenges: 1) In the context of budgeted non-myopic optimization, the horizon of remaining queries r is unknown: it depends on remaining budget B r and expected costs of horizon queries z i , i ∈ {1 . . . r}. An efficient method should allow the horizon to be adaptive to the budget. Therefore, the joint q-EI is not a suitable solution. 2) Given an optimization problem with reasonable medium-size dimension and a medium length horizon, the dimensionality of the joint optimization problem can significantly increase. Wilson et al. [49] showed that the performance of the joint q-EI deteriorates for large optimization dimension.
Proposed Alternative: To overcome the above two challenges, we propose to employ the sequential greedy q-EI via reparametrization trick and Monte Carlo sampling proposed in Wilson et al. [49]. Wilson et al. [49] showed that q-EI is a submodular acquisition function, which guarantees a near-optimal maximization via a sequential greedy approach. This incremental version of the acquisition function has several distinct advantages over the joint one: 1) It is amenable to an adaptive horizon, where we can stop adding points to the batch based on the remaining budget. 2) It is more efficient and produces better performance when the value of d × q is high [49]. After the batch approximation returns a sequence (horizon) of inputs, we select one input to query its expensive function evaluation. We discuss an input selection strategy, that is relevant to iterative machine learning models optimization, in section 3.4. Note that our approximation can clearly extend to the use of any other batch acquisition function that satisfies the submodularity condition and have a sequential greedy approach, namely the q-UCB, q-PI, and q-SR [49]. It is important to highlight that in practice, our approach can naturally extend to parallel BO evaluation (batch setting). The user can choose more than one point from the approximated horizon and evaluate them in parallel as long as the horizon length is fairly larger than the number of selected points for evaluation. Even though in this paper we focus on the sequential setting, we enable this option in our implementation. We provide a summary of the budget-aware BO approach in Algorithm 1.

Algorithm 1 Budget Aware Non-myopic BO
Input: Z, f (z), c(z), models GP f , GPc, utility function u(y|z, D), a total budget BT Output: D, z * , f (z * ) 1: Initialize the remaining budget Br ← BT 2: while Br ≥ 0: do 3: Approximate the optimal horizon via adaptive optimal batch computation Z * of size r such that r i=0 µc(zi) ≤ Br

4:
Select a candidate input z * ∈ Z * and observe its evaluation f (z * ) = y * and cost c(z * ) = y * c 5:

Structured responses
In this section, we describe our proposed approaches to leverage prior knowledge about the structure of the responses, namely, the monotonicity and shape of function f and the linearity of the cost c.
We propose to use a GP with monotonicity constraint over the t variable to model the function f .
Recent work [1] proposed an efficient approach to introduce linear operator inequality constraints to GPs. Let f be the function modeled by a GP and L be a linear operator. The proposed approach enables the posterior prediction to account for inequality constraints defined as a(z) ≤ Lf (z) ≤ b(z).
The derivative operator is a linear operator. Hence, to apply monotonicity, this condition can be seen as the partial derivative of the model of f with respect to t is positive. For this condition to hold, Agrell [1] proposed to define a finite set of input locations named virtual observation locations where the condition is guaranteed to be satisfied.
The posterior predictive distribution of the monotonic GP is f * |Y, C, which is the distribution of The final derivation of the predictive distribution, provided by Agrell [1], is defined as follows: The definition of the matrices A, B, A 1 , B 1 and Σ can be found in Appendix A. The computation of the posterior of the monotonic GP requires the definition of derivatives of the kernel function. In this work we consider monotonicity with respect to one dimension t. Therefore, first order kernel derivatives would be needed. In cases where the function is known to be exponentially decaying (e.g., neural network training), the kernel over dimension t should be defined as an ED kernel. However, in cases where the shape of learning curve is monotonic but not necessarily exponentially decaying (e.g., cumulative and average reward for RL models), an RBF kernel with monotonicity over dimension t should be used. Leveraging monotonicity in the modeling allows flexibility and the generalization of our approach for several types of ILs. We provide the derivatives for both kernels and the details about the specification of the location of virtual observations with each kernel in Appendix A and in our implementation. We additionally provide insights about the efficient posterior computation of the monotonic GP. For more details, we refer the reader to Agrell [1].
Conservative stopping estimation: Previously proposed BO approaches for HPO consider a maximum number of epoch t max at which the objective function will reach its best value. However, in practice, different HPs do not need to necessarily run to the maximum number of epochs to reach their optimal value as the objective stops improving (reaches a plateau) Kaplan et al. [21]. Therefore, running them for longer epochs can be a waste of limited resource budget with diminishing returns. Existing work proposed early stopping of HPs based on their performance compared to previously evaluated data points [32; 6; 45] or based on the expected improvement per unit cost [37] which leads to the selection of very low number of epoch due to the high cost of t max . We propose to define a conservative stopping t opt x for each HP x as the smallest number of epoch needed to reach the best function value at x. Our approach enables the estimation of when a learner becomes -close to its asymptotic value. To the best of our knowledge, no previous work used the estimation of the function values at another location to reason about the HP selection and optimal early termination before reaching that epoch. The problem of estimating t opt x for a HP x based on the GP posterior is defined as below and efficiently solved using binary search.
Cost modeling: The cost prediction is an important component in our algorithm. Therefore, it is important to have an accurate and informative model for the cost. We propose to model the cost by an independent Gaussian process GP c that captures two important characteristics: 1) The cost of the training of different HPs for the same number of iterations t can vary significantly.
2) The cost of training of a fixed HP x increases linearly with the number epochs t. We propose to use the product where K cx is an RBF kernel over x and K ct is a linear kernel over t. Note that previous work assumes the cost is same for different HP x and linear with respect to t. This might lead to an inaccurate estimation of the cost especially if some of the dimensions of x represent architectural variables (e.g number of layers, number of hidden nodes etc.)

Budget-Aware Planning for Iterative Learners (BAPI)
In this section, we describe the overall budget-aware non-myopic BO algorithm for HPO of iterative learners. The main idea is to use the reparametrized iterative greedy q-EI proposed in Wilson et al. [49] to approximate the optimal sequence of selections with respect to the available budget. q-EI will have an adaptive batch size with budget exhaustion as a stopping criteria. We propose to adaptively add inputs to the horizon based on their expected improvement at their conservative stopping iteration without normalizing the utility function by the cost during the optimization. The details of execution can be found in the Non-Myopic Optimization (NMO) function described in Algorithm 4. This function returns a set of inputs representing the optimal horizon Z * .
Input selection from horizon: Given the set of inputs Z * , how to select the next input to evaluate? We propose to select the input with the highest immediate expected reward per unit cost at its conservative stopping iteration. We note here that this is different from optimizing the utility function per unit cost and the issue of selecting low non-informative number of iterations would not arise. In this case, the number of iterations is already fixed to an optimal high value for each input x * .
Early termination: After selecting the next candidate HP to evaluate, the function evaluation will return a y t value after each epoch. Based on the function values of the initial p epochs, we can re-estimate the final performance of x and its new conservative stopping t optn x . The algorithm makes a decision to continue model training with the current HP or early-stop it. If both 1. µ(x, t optn x ) ≤ y best , and 2. σ(x, t optn x ) ≤ τ σ(x, t), then model training will be early stopped in epoch t, otherwise, the conditions will be verified again after running another set of p epochs or when it reaches the estimated t optn x , whichever happens earlier. The first condition will recommend stopping the training if the predicted function value at t optn x will not be higher than the current best value achieved across all evaluated HP. The second condition recommends the early stopping only if the uncertainty of the model about the predicted function value at the estimated conservative stopping is no more than a factor τ ≥ 1 of the uncertainty of the model about the last evaluated epoch. In another word, condition 2 will prevent the early stopping if the model is not certain enough about its prediction of the function value at t optn x . Algorithm 5 summarizes evaluation with early termination.

Algorithm 3 Conservative Stopping Estimation
ConservativeStopping(GP f , x) s.t µ(x, tmax) − µ(x, t) < 3: Return t opt # Add x based on the highest number of epochs x ← arg maxx∈X q-EI(x, tmax) 4: # Estimate the conservative stopping for x t opt x ← ConservativeStopping(GP f , x) 5: Deduct estimate cost at t opt if µ(x, t optn x ) ≤ y best and σ(x, t optn x ) ≤ τ σ(x, t): Continue ← F alse 6: else: Continue ← T rue t ← min(t optn x , t + p) 7: Return y, yc Data points selection from learning curve: Iterative machine learning models evaluated with an input configuration x * and a number of epochs t * return a vector of t * function values and a vector of t * cost values associated with each iteration t ≤ t * . Most of existing work, do not utilize these data points and use only the function value at the last epoch. However, leveraging part of this data can help the learning of the monotonic shape of the objective function and result in a more accurate extrapolation. We select, from each curve, the points with the highest model uncertainty(variance) following the approach proposed in Nguyen et al. [37].
Practical considerations: Considering a perfect model of the function, querying a complete lookahead horizon in each iteration would be optimal. However, as pointed out by previous work on non-myopic BO [17; 31; 29; 52], the model is usually uncertain about long term predictions. Consequently querying a long horizon can hurt the optimization by evaluating misleading points and causing a higher computational cost. Therefore, we follow previous work and set a maximum horizon length as an additional stopping condition to the size of the horizon. Given this mitigation, we expect that the horizon adaptation to the remaining budget occurs towards the end of the budget. We provide additional practical considerations about the cost of a restarted HP in Appendix B.

Related Work
Our problem setting and the proposed BAPI solution have many intersections with previous work in hyperparameter optimization, Bayesian optimization, non-myopic optimization and sequential decision making which we attempt to summarize here.
HPO/BO for iterative learning. [7] proposed learning curve prediction in order to allow early termination of non-promising candidates. This approach utilizes approximate Bayesian inference w.r.t. a pre-defined finite set of learning curve models to perform extrapolation to a fixed horizon. [23] built on this method by showing Bayesian neural networks could be used for learning curve prediction. [45] proposed a hierarchical GP model for HP tuning that includes learning curve prediction upon which decisions for exploration (freeze current and test new candidate) and exploitation (thaw current and continue learning) are based. More recently, [6] proposed an optimal stopping procedure for increasing the sample efficiency of BO and showed competitive performance with [7] for iterative learners. While this procedure obtains theoretical guarantees, it must generate a sample of large size from the GP in order to make a reliable decision. Moreover, solving for the stopping rule requires an approximate backward induction technique after each epoch. Our proposal for early termination is conceptually simpler and far less computationally demanding. The method of [33] considers a finite set of learners modeled with freeze/thaw [45] selecting between exploration and exploitation with a heuristic -greedy rule. [51] extend the knowledge gradient acquisition function [11] to trace-valued observations that occur in multi-fidelity applications. BOIL [37] also considers trace-valued observations, but compresses the trace via learned weighted sum as well as adding carefully-chosen intermediate trace values as observations. The setting for BOIL includes reinforcement learning problems with reward functions taking non-exponentially decaying shapes. Our BAPI approach uses a product kernel to jointly model correlations between HPs and epochs within training. Kandasamy et al. [20] developed BOCA, an extension of UCB to general multi-fidelity BO setting. We note that there exist orthogonal approaches that focus on the ability to extrapolate responses based on smaller datasets where the cost is varied based on the size or fraction of the dataset used for training. These methods propose algorithms based on multi-task BO [44; 22] and importance sampling [2].
Non-myopic policies:While there were early attempts at non-myopic selection for length-two horizons [e.g., 39], most work proposing practical methods for longer horizons is very recent. Wu and Frazier [50] developed gradient estimates for two-step EI admitting gradient-based search for the optimal two-step selection. Lam et al. [26] utilized a Markov decision process (MDP) formalism and performed rollouts with a predefined base policy to estimate the value function. GLASSES [14] approximates the solution for the optimal non-myopic selection by a combination of approximate integration given future selections and approximating the future selections by a diversity-promoting batch selection procedure from González et al. [13]). Closely-related to our work is BINOCULARS Jiang et al. [17] which was discussed in Section 2. The major differences to our proposed BAPI approach are that (a) BINOCULARS uses joint batch expected improvement q-EI Wang et al. [47] while we use the sequential greedy selection Wilson et al. [49], (b) BINOCULARS uses a fixed horizon that is budget agnostic while we use a budget-adaptive horizon, and (c) BINOCULARS does not take cost into account when returning its non-myopic selected query while our method does factor cost in. Lee et al. [31] consider the general cost-aware setting and frame the problem as a constrained MDP. Their method approximately solves the intractable problem by performing rollouts of a base policy that does not adapt the horizon to the budget. Their method Moreover, it's base policy is normalized by cost leading to a bias towards low-cost queries. Building upon the efficient one-shot multi-step tree approach of Jiang et al. [18], Astudillo et al. [3] introduce cost-modeling and develop a budget-aware method. However, the adaptation of their method to the horizon is post-hoc in the sense that the horizon has to be fixed in advance and cannot be adaptive to the remaining budget due to utility function formulation and optimization. This leads to an unnecessary higher dimensional optimization and a manual zero padding technique to handle cases where the selected horizon violates the remaining budget.
Bandit algorithms: Given that the objective in (1) is equivalent to optimizing for simple regret, there is a large amount of relevant work within the multi-armed bandits literature. Audibert et al. [4] developed the upper confidence bound exploration (UCB-E) policy, for the best arm identification (BAI) in the budgeted setting by providing conditions under which simple regret decays exponentially with increasing budget. Hoffman et al. [15] considered linear bandits and proposed the BayesGap algorithm which is an exploration policy within budget constraints. Later, Jamieson and Talwalkar [16] analyzed successive halving as an instance of non-stochastic multi-armed bandits in the setting where the budget is greater than the number of learners. HyperBand [32] is an implementation of successive halving running this algorithm in multiple successive rounds and is a very general algorithm for HPO including non-iterative learners. Most recently, BOHB [9] modified HyperBand by utilizing BO within the successive halving procedure which guides the selection process for the learners that will be trained for longer budgets.

Experiments and Results
In this section, we first provide details about our experimental setup. Next, we evaluate the performance of BAPI approach and compare it to state-of-the-art baselines.
Baselines. We evaluate several state-of-the-art baselines, described in the related work, from nonmyopic BO, general BO and HPO for iterative learners literature. We compare BAPI to BINOCULARS We also add the expected improvement (EI) [19] as a baseline from the general BO literature. Astudillo et al. [3] uses MS-EI as a base policy therefore we expect it to have similar performance. Each baseline implementation uses settings recommended by the original authors and publicly available code. We also evaluated GLASSES [14] 2 and random search. However, both of them performed always poorly when compared to all other baselines. Therefore, for clarity of the figures, we do no report them. We note that previous work on non-myopic BO do not include HB and BOHB as baselines but given their competitive performance in iterative learning settings, we recommend they become standard in future work in this problem setting.
Experimental setup. All experiments were averaged over 10 runs with different random seeds. The code of our BAPI implementation and experiments can be found at github.com/belakaria/BAPI. We considered several state-of-the-art HPO benchmarks: 1) Logistic regression with MNIST dataset; 2) Multi-layer perceptron with Olivetti dataset; 3) Multi-layer perceptron with Covtype dataset ; 4) Fully connected network with MNIST dataset 5) CNN on image dataset CIFAR10; 6) CNN on SVHN dataset; and 7) Resnet on CIFAR100 dataset. Full experimental details are listed in Appendix C. We evaluated benchmarks 4, 5, and 6 with two t max settings. We report the validation error as the evaluation metric for consistency across datasets. We evaluate two different variants of our algorithm: BAPI-4 and BAPI-8, where the maximum horizon is set to 4 and 8 respectively. BAPI-8 was evaluated on two benchmarks (LR with MNIST and MLP with Olivetti) to demonstrate the effect of varying the maximum horizon on the performance. The uncertainty threshold τ is set to 2 for all experiments. The parameter p is set to 20% of the maximum number of epochs for all experiments except for CNN-SVHN, where it is set to 10% due to the high cost of each epoch. is set to 0.01 except for CNN-SVHN, where it is set to 0.005 due the small variation in the validation error. We select at most three data points from each learning curve. Due to space limitation, we provide additional results and discussion in Appendix C. Results and Discussion: Figure 2 shows the results (best validation error as a function of wall-clock time) of all methods on four HPO tasks. We make the following observations. 1) BAPI identifies better candidates with less total cost than the baselines due to its ability to plan selections while accounting for budget and early terminating non-promising candidates. 2) A longer horizon for BAPI was tested on the relatively cheaper experiments LR MNIST and MLP Olivetti datasets and shows some performance degradation (LR MNIST) and some improvement (MLP Olivetti) suggesting that optimal horizon length is problem-dependent but clearly helpful in some cases. 3) HB and BOHB can identify good candidates faster than most algorithms in the beginning, mainly because their strategy forces initial evaluations to be low-epoch trained runs. In the mid-range, their performance slows down, perhaps a consequence of their exploitation behavior and reliability on successive halving which might limit their extrapolation ability and stop promising candidates very early. Similar analysis has been reported in previous work [6]. With longer search times, however, BOHB can catch up. 4) Other non-myopic approaches, BINOCULARS and MS-EI, are slower to uncover promising candidates due to spending more budget in evaluating all selected candidates to the maximum number of epochs. However, they both arrive at a competitive performance towards the end that can be attributed to their planning capabilities. 5) BOIL is worse than most baselines across all benchmarks. As discussed in Section 1, BOIL selects the next candidates by weighting EI by the cost and might suffer from the cost miscalibration pathology. Similar observations were made in Astudillo et al. [3]. Additional results included in Appendix C show that BAPI becomes less competitive when the total budget is significantly increased, but also provides results suggesting that performance loss can be brought back by adjusting the pruning behavior, a topic of on-going work.

Summary
This paper considered the problem of hyperparameter optimization (HPO) for iterative learners under a constrained cost budget. The proposed BAPI approach addressed gaps in prior work including modeling of structured responses and mis-calibration between response and cost models leading to biased search. More importantly, our planning-based BAPI approach allows for non-myopic candidate selection over horizons adaptive to the budget. Combined with subset selection and early termination procedures, our experimental evaluation on a variety of HPO benchmarks shows BAPI's efficacy over previous methods in finding high-performing candidates with less cost budget.

A Details of the monotonic Gaussian process
The posterior predictive distribution of the monotonic GP is f * |Y, C which is the distribution of f * = f (z * ) for some new inputs z * = [x * , t * ], conditioned on the observed data Y and the constraint C defined as a(Z v ) ≤ Lf (Z v ) ≤ b(Z v ). The final derivation of the predictive distribution is defined as follow: where T N (·, ·, a, b) is the truncated Gaussian N (·, ·) conditioned on the hyper-rectangle The matricies A, B, A 1 , B 1 and Σ are defined as follow: Additionally, the probability that the unconstrained version of C falls within the constraint region, p(C|Y ), is defined as follow: and the unconstrained predictive distribution is Sampling from the posterior distribution with constraints has been a challenging task in previous work Riihimäki and Vehtari [40]. However, Agrell [1] proposed to use a new method based on simulation via minimax tilting proposed by Botev [5]. This sampling approach was proposed for high-dimensional exact sampling and was shown to efficient and fast compared to previous approaches like rejection sampling and Gibb sampling Kotecha and Djuric [24].
The specification of the location of virtual observations Z v can have an important effect on the efficiency and scalability of the monotonic Gaussian process. Agrell [1] proposed to have a suboptimization problem to find the optimal location. The idea is to iteratively place virtual observation locations where the probability that the constraint holds is low. However, this optimization becomes suboptimal when the dimension of the problem grows. Given that our function is monotonic with respect to only one dimension, we chose to define linearly spaced locations with respect to dimension t. The number of points is defined based on the kernel: • ED kernel: The virtual observations locations will mainly enforce the direction of the monotonicity, therefore adding only two locations is sufficient.
• RBF Kernel: The number and location of virtual observations depends on the smoothness (lengthscale) of the kernel. The distance between every two virtual observations should be smaller than the lengthscale in order to maintain the monotonicity and avoid any fluctuations.
For more details about the the efficient posterior computation of the monotonic GP we refer the reader to Agrell [1].

kernels derivatives
The computation of the posterior of the monotonic Gaussian process requires the definition of derivatives of the kernel function. In this work we consider monotonicity with respect to one dimension t. Therefore, kernel derivatives would be defined as follow

C.1 Experimental Setup Details
Logistic Regression with MNIST: We train the logistic regression classifier on the MNIST image dataset LeCun et al. [27]. The dataset consists of 70,000 images categorized into 10 classes. We use 80% for training and 10% for validation. We optimize the model over three hyperparameter: the learning rate ∈ [10 −6 , 1], the L 2 regularization ∈ [0, 1] and the batch size ∈ [20,2000]. We apply a log transformation to the learning rate and batch size. We set the maximum number of epochs to 100.

MLP with Olivetti and Covtype:
We train a multi-layer perceptron with two fully connected layers on the Olivetti dataset Samaria and Harter [41] and Covtype dataset. We use 10% of the data for the validation set. We optimize four hyperparameters learning rate ∈ [10  figure 3 we report the results with the maximum number of epochs set to t max = 25 and in figure 4 we report the results with the maximum number of epochs set to t max = 50. The total wallclock time budget is extended accordingly. These experiments were run on Tesla V100 GPU machine.

CNN with CIFAR10 and SVHN:
We train a CNN model on two image datasets CIFAR10 [25] and the Street View House Numbers (SVHN) [36]. For CIFAR10 we use 40,000 image for the training set and 10,000 for the validations set. For SVHN 63,257 image for the training set and 10,000 for the validations set. We optimize six hyperparameters: the batch size∈ [32,1024], the learning rate∈ [10 −6 , 0.1], the momentum∈ [0.1, 0.9], the L 2 regularization∈ [10 −7 , 10 −3 ], the number of convolutional filters∈ [32,256], and the number of dense units ∈ [64, 512]. We apply a log transformation to the learning rate, the batch size. We set evaluate all algorithms on two different setups where in figure 2 we report the results with the maximum number of epochs set to t max = 25 and in figure 4 we report the results with the maximum number of epochs set to t max = 50. The total wallclock time budget is extended accordingly. These experiments were run on Tesla P100 GPU machine.

Resnet with CIFAR100:
We train a ResNet model on a the image dataset CIFAR100 [25]. We employ 40,000 images for the training set and 10,000 for the validations set. We optimize six hyperparameters: the batch size ∈ [32,512], the learning rate ∈ [1e − 6, 1e − 1], the momentum ∈ [0.1, 0.9], the L 2 regularization∈ [1e − 7, 1e − 3], the number of convolutional filters∈ [32,256], and the number of layers ∈ [10,18]. We report the results with the maximum number of epochs set to t max = 100 in Figure 3. The total wall-clock time budget is extended accordingly. These experiments were run on a Tesla V100 GPU machine.

DQN CartPole:
We train a Dueling DQN (DDQN) [48] agent in the CartPole-v0 environment. We employ the same setting proposed by Nguyen et al. [37]. We optimize two hyperparameters: the discount factor ∈ [0.8, 1] and the learning rate for the model ∈ [1e − 6, 0.01]. We vary the number of episodes from 200 to 500. We map the episodes into epochs with each three episodes equivalent to one epoch, resulting in a maximum number of epochs t max = 100. We report the results in Figure 4. The total wall-clock time budget is extended accordingly. These experiments were run on a 1 core of a Xeon CPU machine.

A2C Reacher:
We train a Advantage Actor Critic (A2C) [34] agent in the Reacher-v2 environment. We employ the same setting proposed by Nguyen et al. [37]. We optimize three hyperparameters: the discount factor ∈ [0.8, 1], the learning rate for the actor ∈ [1e − 6, 0.01], and the learning rate for the critic ∈ [1e − 6, 0.01]. We vary the number of episodes from 200 to 500. We map the episodes into epochs with each three episodes equivalent to one epoch, resulting in a maximum number of epochs t max = 100. We report the results in Figure 4. The total wall-clock time budget is extended accordingly. These experiments were run on a 1 core of a Xeon CPU machine.

A2C Inverted Pendulum:
We train a Advantage Actor Critic (A2C) [34] agent in the InvertedPendulum-v2 environment. We employ the same setting proposed by Nguyen et al. [37]. We optimize three hyperparameters: the discount factor ∈ [0.8, 1], the learning rate for the actor ∈ [1e − 6, 0.01], and the learning rate for the critic ∈ [1e − 6, 0.01]. We vary the number of episodes from 700 to 1500. We map the episodes into epochs with each eight episodes equivalent to one epoch, resulting in a maximum number of epochs t max = 100. We report the results in Figure 4. The total wall-clock time budget is extended accordingly. These experiments were run on a 1 core of a Xeon CPU machine.

C.2 Additional Results and Discussion
We report additional results of our BAPI approach and existing baselines. We report an additional variant of our algorithm that we name BAPI-4-L. We test the case where we do not add additional points from each curve but rather use only the last epoch. We notice that this variant performs competitively and sometimes better than adding additional points to the curve. This opens a discussion about the utility of leveraging additional data points from each curve especially while using the monotonic GP. It is important to note that previous methods built for HPO frequently suggest using additional points. This includes approaches proposed in the papers by Nguyen et al. [37]; Dai et al. [6], and Wu et al. [51]. We plan to work on investigating this problem further to develop a sound theoretical understanding of this phenomenon. In Figure 4, we test all algorithms on settings with extended budget and a higher number of maximum epochs t max = 50. We observe that given a sufficiently large budget, most of the baselines converge to statistically comparable results. We notice that HB, in most of the experiments, is able to reduce the validation error in the beginning but does not always converge to good results. However, BOHB performance was remarkably stronger with a higher number of maximum epochs. Increasing the maximum number of epoch enables BOHB to evaluate a larger number of configurations at a low budget and therefore we can see a significant drop in the validation error earlier than all baselines. The results in Figure 3 and Figure 4 show that BAPI-4 becomes less competitive when the total budget is significantly increased and the maximum number of epochs is higher, but also provides results suggesting that performance loss can be brought back by adjusting pruning behavior in BAPI-4-L.
We report additional results for reinforcement learning experiments optimized with RBF kernel over the number of epochs. Figure 4 shows the increasing discounted cumulative reward with discount factor 0.9 as suggested by [6]. The results show that BAPI-4 performs better or similar to the baselines. We observe that HB and BOHB performance degrades significantly with RL experiments most likely because they do not account for the possibility that the learning curve can be flat in the middle. We additionally notice that BAPI-4-L performance is competitive but worse than BAPI-4. One candidate reason for this behavior is due to the use of the RBF kernel, where adding intermediate points from the curve can be more crucial to avoid fluctuations.