ECONOMIC HYPERPARAMETER OPTIMIZATION WITH BLENDED SEARCH STRATEGY
Authors: Chi Wang
Qingyun Wu
Silu Huang
Amin Saied
Venue: ICLR 2021 Poster (2021)
Keywords: HYPERPARAMETER OPTIMIZATION
COST

Abstract: We study the problem of using low cost to search for hyperparameter configurations in a large search space with heterogeneous evaluation cost and model quality.
We propose a blended search strategy to combine the strengths of global and local search, and prioritize them on the fly with the goal of minimizing the total cost spent in finding good configurations. Our approach demonstrates robust performance for tuning both tree-based models and deep neural networks on a large AutoML benchmark, as well as superior performance in model quality, time, and resource consumption for a production transformer-based NLP model fine-tuning task.

ECONOMICAL HYPERPARAMETER OPTIMIZATION WITH BLENDED SEARCH STRATEGY
Chi Wang', Qingyun W Huang, Amin Saied
Microsoft Corporation, Redmond, WA 98052, USA (wang. ccii, , q ngyunn wu, si lu. huang, ami n sai ed) (mm wwwoott..ccoooomm
ABSTRACT
We study the problem of using low cost to search for hyperparameter configura- tions in a large search space with heterogeneous evaluation cost and model quality. We propose a blended search strategy to combine the strengths of global and lo- cal search, and prioritize them the fly with the goal of minimizing the total cost spent in finding good configurations. Our approach demonstrates robust per- large
formance for tuning both tree-based models and deep neural networks AutoML benchmark, as well as superior performance in model quality, time, and resource consumption for production transformer-bas based NLP model fine-tuning task.
INTRODUCTION
Hyperparameter optimization (HPO) of modern machine learning models is resource-consuminng task, which is unaffordable to individuals or organizations with little resource (Yang & Shami 2020). Operating HPO low-cost regime has numerous benefits, such as democratizing ML techniques, enabling new applications of ML, which requires frequent low-latency tuning, and reducing the carbon footprint. It is inherently challenging due to the nature of the task: trying large number of configurations of heterogeneous cost and accuracy in a large search space. The expense can accumulate from multiple sources: either a large number of individually cheap trials or small number of expensive trials can add up the required resources.
There have been multiple attempts to address the efficiency of HPO from different perspectives. Each of them has strengths and limitations. For example, Bayesian optimization (BO) (Brochu et al., 2010), which a class of global optimization algorithms, is used to minimize the total number of iterations reach global optima. However, when the cost of different hyperparameter configura- tions is heterogeneous, vanilla BO may select a configuration that incurs unnecessarily high cost. As opposed BO, local search (LS) methods (Wu et al.) (02T) able control total cost. by pre- venting very expensive trials until necessary. but they may get trapped in local optima. Multi-fidelity methods (Jamieson Talwalkar 2016) aim use cheap proxies to replace some of the expensive trials and approximate the accuracy assessment, but can only be used when such proxies exist. A single search strategy is difficult to meet the generic goal of economical HPO.
In this work, we propose blended search strategy which combines global search and local search strategy such that we can enjoy benefits from both worlds: (1) global search can ensure the con- vergence to the global optima when the budget is sufficient; and (2) local search methods enable better control on the cost incurred along the search trajectory. Given a particular global and local search method, framework, which named BlendSearch, combines them according to the following design principles. (I) Instead of sticking with a particular method for configuration selection, consider both of the candidate search methods and decide which one use each round of the configuration selection. (2) We use the global search method to help decide the starting points of local search threads. (3) We use the local search method to intervene the global search method's configuration selection to avoid configurations that may incur unnecessarily large evalu- ation cost. (4) We prioritize search instances both methods according their performance and efficiency of performance improvement on the fly. Extensive empirical evaluation on the AutoML
"Equal contribution

---

2.0
2.0
BlendSearch
1.8
1.8
Logs
1.6
Losa
1.6
1.4
BlendSearch
1.4
BO
1.2
0g
1.2
90
00
LS
0
500
1000
1500
2000
1000
2000
3000
Time(s)
Time(s)
(a) Loss vs. evaluation time for configs tried by each method. One point represents one config. The lower is the loss the better is the quality of the config. Longer evaluation time corresponds to larger training cost
(b) Best loss vs. optimization time per method. Col- ored circles configs proposed by LS threads in our method (color change indicates thread change): dia- monds configs proposed by BO in our method
Figure 1: A typical example of the different behaviors of BO, LS and our proposed Bl endSea in tuning a set of 11-dim hyperparameters for XGBoost. BO is prone to selecting expensive but not necessarily good configs. LS avoids expensive configs in the beginning but is prone to getting stuck in local regions. BlendSearch switches between one BO and multiple LS search threads and prioritizes the more promising ones, and turns out to try more low-cost, high-quality configs.
Benchmark (Gijsbers et of datasets. BlendSearch is now publicly available in open-source AutoML Library
al. 2019) validates the robust performance of our method on a wide variety
2 BACKGROUND AND RELATED WORK
We first briefly introduce the vanilla Bayesian optimization methods and local search methods, which are among the building blocks our method. Bayesian optimization is a class of global optimization algorithms which is suitable for optimizing expensive black-box functions. It mod- els the probabilistic distribution of the objective conditioned on the optimization variables. Typical models include Gaussian process (Snock al. 2012), random forest (Hutter et al. 2011), and tree Parzen estimator (TPE) (Bergstra et al.) 2011). In BO methods, an acquisition function is used determine the next point evaluate. Two common acquisition functions are the expected im- provement (EI) (Bull 2011) over the currently best-observed objective and upper confidence bound (UCB) (Srinivas al. (209).. Local search methods are prevalent in the general optimization liter- ature (Spall et al. 1992, Nesterov & Spokoiny (017)) but less studied in the HPO literature due to the possibility of getting trapped in local optima (György & Kocsis 201T). Recent work (Wu al.) 2021) shows that a local search method FLOW2 can make HPO cost-effective when combined with low-cost initialization and random restart. At each iteration, it samples a pair of vectors (with oppo- site directions) uniformly at random from unit sphere, the center of which is the best configuration found so far (a.k.a. incumbent) and the radius of which is the current stepsize. Expensive configu- rations are avoided in the beginning each iteration proposes configuration Random restart of the local search is performed once the convergence condition is satisfied.
the incumbent.
There several attempts to address the limitations of vanilla BO or local search methods. BOwLS (BO with local search) (Gao et al. (2020) uses BO model to select the starting point of a local search thread. Each local search thread is run until convergence and the BO model is updated with the start point and the converged loss. Trust region BO (Eriksson et al. 2019) fits fixed number of local models and performs principled global allocation of samples across these models via an implicit bandit approach. It is primarily designed for HPO problems with high- sich-dimensionall numerical hy- perparamters. Unfortunately, all existing work that tries to combine global search with local search methods does not consider the heterogeneity of evaluation cost incurred along with the search. There are also a lot of attempts in making HPO efficient by speeding up configuration evaluation. Multi- fidelity optimizations (Klein et al. 2017 Li et al.) 2017 Kandasamy et al. 2017 Falkner et al. 20188] Lu et al, 2019 Li et al., 2020) are proposed for this purpose. They usually require an additional degree of freedom in the problem called 'fidelity,, to allow performance assessment configura-
https://githubs http://ggththh.cco httptttwwwcccmmmoccrrottt///....
2

---

Search Thread Pool
Thread D (global search)
Create new LS thread starting from
Thread 1 search)
Search Thread Creator
Search Thread Updater & Cleaner
Thread (local scarch)
Yes
Search Thread Selector
create thread condition is
met?
selected ts Is
Config x,
loss l(x).
Yes:
Yes: Config proposed by thread 0; backup thread
Config x,
No: Config proposed by selected thread
cost c(x)
Config Validator
loss (xx),
cost c(x)
Valid config x proposed by Thread 0 or backup thread
Config x is proposed by Thread 0?
Config Evaluator (Can use multi-fidelity pruning)
①
Figure 2: Framework. Both paths from 'Config Evaluator' are executed independently.
tion with different fidelities. There is surprisingly little prior work for generic cost-effective HPO. Gaussian process with expected improvement per second (GPEIPS) (Snoek et al. 2012) models the evaluation cost using another Gaussian process, and heuristically adds the estimated cost into the ac- quisition function. It does not always outperform GPEI as the acqusition function can overpenalize good but expensive configurations.
BLENDSEARCH
Our framework needs the following information as inputs.
B is the total budget of cost. In this work, we measure the cost by CPU/GPU time.
the input HPO problem, which has the following attributes characterizing the problem. P.X is the search space in which each element is d-dimensional hyperparameter configu- ration. For a non-categorical hyperparameter coordinate i E [d]. different values of x; lead to heterogeneous cost and there is known value P.r.!.wwCost corresponding to low cost, it is considered as a controlled dimension. We use P.D to denote such a set of controlled dimen- sions.
(.LossFunc(.) .) is the loss function to be minimized in terms of the configurations x E P.A'. P.CosttFunee is the cost function that outputs the cost incurred when evaluating The goal of an HPO algorithm is to minimize the loss P.LossFunc(Xx with the constraint that the total cost incurred G(x)) ExE((H) P.CostFunc(x)
B, where I(T)) is the search tra- jectory of algorithm т. Note that both P.LossFunc(x) and P.CostFunc(x) are black-box functions meaning that typically the analytic form is not available, and only function values can be observed. In order to distinguish the operation of querying from loss/cost function and the loss/cost observation,
use P.LossFunc(Xx and P.CostFunc(S use !(x) and c(x) to denote the latter. / and (omitting x) are used when there is no ambiguity. G is the global search method be used, L is the local search method to be used. C.A the largest stepsize used in local search method L. i.c., the largest possible change on a hyperparameter value between two consecutive search steps.
denote the former, and
The overall design of our framework is presented in Figure 2 and Algorithm I maintain pool of search threads, one of which corresponds to global search and the others local search. The pool starts with one global search thread and gradually adds local search threads as the search goes on. Here a search thread is an instance of a global search or local search method, each with its own search trajectory. At each round, search thread selector selects one of the search threads from the pool according to a priority metric that reflects the search threads' current performance and efficiency of performance improvement. The selected search thread will then be used to propose a configuration to evaluate this round. When the selected search thread is the global search thread, config validator first checks whether the proposed configuration is within
The key idea is to
3

---

the "admissible" region for evaluation. If not, it uses backup local search thread instead. A local search thread will be created only when the global search thread proposes a valid config and a certain create thread condition is met, and will be deleted once it converges. Two local search threads will be merged into one if they are close enough. The priority of each search thread is updated after each evaluation round.
Algorithm 1 BlendSearch
Inputs: HPO problem P. global search method G. a local search method L, total budget B. Initialization: Initialize F.S [So] where So an instance of G. We denote by F.xo the initial point of the search. By design, the values of the controlled dimensions of F.xo are set to be P.xLouCost and those for the other dimensions are proposed by Sg.
2: while F.c < do
3: Shak < SelectThreac(F))
4: (x,1,)) c- aearchEvaluatel Seartteeeeee((SS....
5: if x is invalid id then (,) + SearchEvaallateelstttp/baaa
6: if is proposed by global search & CreateNNewisSSoondit tion is satisfied then Initialize $ Add the new LS thread S into the pool: F.S + F.S 9: De DeleteArddMergees(((1
7:
resaalliaaaacrrccccaca.... ((x.
8:
Merge or delete existing LS threads when necessary
10:
Update F.Priority
xf' is proposed by global search then UpdateGSModel((5. (x)
For convenience, we use F to denote a collection of framework-level variables:
F.S is the list of search threads maintained in our framework. F.S contains at least one search thread and among them there one and only one global search thread, i.e., So. in S..
F.rrirriyy is priority dictionary, in which the keys the search threads in F.S, and the values are the priority of the corresponding search threads.
Bookkeeping information of F: F.l" is the best loss achieved among all the search threads and F.c is the total cost consumed in our framework.
F.R is the 'admissible' region on the controlled dimensions of the current search, which is hyperrectangle and can be written in the form of F.R == {[F .xmii F.xmaa]]iee with F.xmii and F.u.uax denoting the minimum and maximum value along the i-th dimension in F.R respec- tively. They initially set as F.x.min = F.r..ax region gradually expands during the search: (1) it is expanded to cover all the points evaluated by all the search threads and all the points that one search step, as shown in line 7 and 8 of Algorithm 2 (2) it expands if a local search thread converges, as shown in line 3 of Algorithm 7 (included in Appendix Ap.
P. P.ofooCosst for all E D. The 'admissible'
possible to be reached by the local search within
In the following, we explain the key steps in our algorithm.
Step 1: Search thread selector (line 3 of Alg [). In addition to the primary search thread Š, Select also outputs a backup search thread Spak which is guaranteed to be local search thread. It is set be none when there is no local search thread yet in F.S. Specifically,
arg max F.Priority(S)
FS So +
$ arg max F.r.oriii)) Shak = SEF
None
FS So = 0,
(1)
The design of the priority metric follows the principle of optimism the face of uncertainty from the multi-armed bandit problem to balance exploitation and exploration (Lattimore & Szepesvári (222))
Specifically, linear extrapolation performed adaptively and locally to calculate the improvement speed of each search thread. The estimated future reward based on such linear extrapolation
provides a first-order upper bound of the ground truth future reward assuming each search thread has diminishing return, i.e., the speed of improvement decreases we introduce the following variables and functions for each search thread S E F.S.
resource is spent. Formally,
Bookkeeping information: St and Snd the best loss far and second best loss before the best loss is achieved. S and 2nd are the total cost taken when Sst and Smd are achieved respectively. S.c is the total cost spent in S. S.x is the best configuration found far.
4

---

S.s is the performance improvement speed of S. It is calculated S.s 8.1 S..
S.c-S.caa This
formula is only valid when there is least one improvement. Otherwise, do not have enough information to estimate the speed of improvement. We set the speed to the highest speed of all the search threads when S.12nd = S.ttst It is due to implicit assumption of diminishing return. S.x and S.y=axx are the minimum and maximum value of the i-th dimension of all hyperpa- rameters configurations evaluated in S respectively.
S.Cost Imp(-) is a function whose input is a target loss and output is the anticipated cost for S generate better loss than this target. We use the following formula to compute it, which is intuitively using the cost for improvement in the past to estimate that in the future.
S.Cost Imp(() max { S.c S.c. SS...t S.c2nd _-
S.1 -
S.s
Our proposed priority metric essentially the negative of the projected loss of S:
F.riority(S}- -(S.'' S.s x 6) in which b = min(max S.Cost Imp(F.1)), -.cc). F.c). considered the resouree needed for every S to have better performance than the currently best performance F.l". Our priority metric estimates the loss of each search thread if such an amount of resource (restricted by the budget left B F.c) is given. By considering both the search threads' current performance and potential improvement, it provides a fair trade-off between exploiting the currently-best and exploring the potentially- choices.
(3)
maxser.s S.Cost Imp(F.1") can be
Algorithm 2 Sea
Inputs: HPO problem P. search thread S, and F
1: if S is None then Construct as follows: generate the controlled dimensions of by adding Guassian noises on the corresponding dimensions of F.xo and for the rest of the dimensions sample uniformly random from the search space P.X.
2: else x + S.ProposeConfige
3: if = Su (i.e., S is the global search thread) &x $ F.R then <invalidd t Evaluate configuration x
4: else 1, P.Loss (x)) P.CostFunc(x)
5: x & invalid then
6: BookKeeping(S.
F) and update speed S.s, 7: Vi P.D. S.x.in min(x;, S.x.fin, F.r:min t- min S.x:iin - L.A.F F. ..min]]
8: P.D, S.x + max(x, (x,, S.xmax], F.rmaxx + ( + C.A. F.r,may
9: Outputs: x,
Step 2: Config validator and evaluator (line 4-5 of Alg D]. After a search thread (and a backup search thread) is selected, the next step is to propose the next configuration to try with the chosen search th)ead(s). Intuitively speaking, we consider generating the next configuration to try primarily according to the selected search thread Š whose priority is ranked the highest. But we set a guard rail for the global search thread it may propose an unnecessarily high-cost configuration. We thus introduce a config validator to validate the configurations proposed by global search according to whether they are within the current admissible region of our framework F.R (line 3 of Alg ( A configuration marked as 'invalid" d' means that it is considered to be prone to incur unnecessarily high cost and will not evaluated at this round. In this case, the selected backup search thread will be used to perform another round of SearchEva SerchhEvalaaelllll wwllllllsss. search thread (i.e., not none). In the case where the backup thread is none, we generate the new configuration according to line of Alg 2 The config validator helps avoid potentially high-cost evaluation and thus avoid creating local search threads from high-cost points until necessary. It does not stick to local searches forever because the admissible region F.R gets expanded. Note that according to the definition of F.R, only the controlled dimensions of the hyperparameter configura- tions subject validation check. If needed, multi-fidelin pruning strategy be used in this config evaluator component. Multi-fidelity pruning does not necessarily yield better performance. So the adoption of multi-fidelity pruning in BlendSearch ch is optional.
(line 5 of Alg I if it is valid
Step 3: Search thread creator, updater and cleaner (line 6-11 of Alg If the newly proposed configuration is proposed by global search and it is not marked as 'invalid', consider creating
5

---

new local search thread using the proposed configuration starting point. To make sure the newly created local search thread is relatively good, we first check whether the proposed configura- tion's 's performance is better than at least half of the existing threads' performance (specified in the Creat wewtteeee..Coom active search thread pool S. In DeleteAndMe rgeLS, we check whether local search thread has converged according to the convergence condition of the specific local search method. If it is, the search thread will be removed from S. In addition, we also go through all the local search threads to see whether the incumbent of a LS thread is reachable in one step by another LS thread with lower loss (ref. Appendix A If so, the former LS thread will be deleted. After a configuration proposed by global search is evaluated, the observation tuple (x, I, c) is then used to update the model of the global search method through function method is Bayesian optimization method, the model is the surrogate model used.
oo). If so, a new local search thread will be initialized and added to the
For example, when the global search
Due to page limit, detailed pseudocode for several of the straightforward functions men- tioned in our framework are provided in Appendix A including DeleteAndMergges, Initiallieeeerchhiiieii
and BookKeeping.
4 EXPERIMENTS
We evaluate BlendSearch in tuning tabular machine learning libraries with an AutoML bench- mark (Gijsbers et al. 2019), and in fine-tuning NLP models for text data. The AutoML benchmark consists of 39 tabular datasets that represent real-world data science classification problems. It in- cludes datasets of all sizes, of different problem domains and with various levels of difficulty. As each dataset has 10 cross- validaaal folds, all the results reported in this paper are averaged over the 10 folds. With this benchmark, we are able to evaluate multiple HPO methods on large number of datasets within a manageable computational budget, for tuning three machine learning libraries: XGBoost (Chen & Guestrin 2016), LightGBM (Ke et al., 2017) and Deep'Tablesf The first two are popular libraries based on gradient boosted trees, and the third is an easy-to-use deep learn- ing toolkit which utilizes latest research findings for tabular data. We chose them because gradient boosted trees and deep neural networks are the most frequent winners in data science competitions. We run experiments for XGBoost and LightGBM on the AutoML benehmark and report the results in Section 4.1 As real application, we report an NLP model fine-tuning task for a production use case in Section 4.2 Finally, in Section 4.3 we perform ablation study to investigate the effectiveness of several important components of our framework. Due to page limit, we include the results for We include the following baselines in our experiments.
tuning DeepTables in Appendix
BO (Akiba et al. 2019) the Bayesian optimization baseline. We choose modern HPO library Optuna and use the TPE sampler because of its flexibility in handling mixed continuous and discrete space and good peformance reported in existing work (Falkner et al. 2018).
LS (Wu et al.) 202T) the recent bascline of using local search with random restart, based on FLOW It is proved to be able control cost effectively and outperform BO methods for numer- ical cost-related hyperparameter search.
BOwLS (Gao et al. 2020) the baseline of an existing approach of combining local search with
BO, i.c., using B0 to propose start points for local search.
ASHA (Li et al., 2020). i.c., asynchronous successive halving state-of-the-ar HPO method
that uses multi- fultiffidelity optimization and supports parallel tuning.
Initialization setting. For the local search method used in our framework, a low-cost initialization needed realize its unique advantages in controlling the cost. It is implemented via setting a low- cost initial value for each of the controlled dimensions. For example, among the hyperparameters tuned in LightGBM (shown in Table of Appendix B) three hyperparameters, including 'tree num', "leaf num' and 'min child weight' have initial values corresponding to the min or max values in their range, depending on whether they have a positive or negative correlation with the evaluation cost. does not require the loss of the initial configuration to be low. Only one single low-cost initial value for each controlled dimension needs to be specified as input. To ensure a fair evaluation, we use the same low-cost initial point (if controlled dimensions exist) as the starting point of all the basclines.
httpps///github..coo//attat

---

BlendSearch
16x
1.3x
BO
1.510
14x10'
1955
1055
13x10"
10
10x
time
time (4)
time
(6)
(a) credit, loss 1-auc
(b) KDDCup09, loss
1-auc (c) volkert, loss log-loss
Figure 3:
Optimization performance curve for XGBoost. Lines correspond to the mean loss over 10 folds, and shades correspond to 95% confidence intervals. 1-auc is used for binary classification and log-loss is used for multi-class classification.
10a
4.0
BlendSeeach
5.0 BS-Priority RoundRobin
BS-wlh-CenfiiWWlllatte
3.5
BOWLS
4.5
BS-Cr 15-CreatComdiAAwwpy
BS
Scaled Loss
3,0
2.0
2.5
2.0
1.5
(a) Rank
(b) Scaled loss
(c) Rank for ablation
Figure 4: Aggregated rank and scaled loss on LightGBM and XGBoost. The scaled loss is obtained by min-max scaling using the max and min loss over all time across all the methods. Sub-figure (a) & (b) share the same legend, and BS is short for BlendSearch in sub-figtt sub-figure (c). Both rank and scaled regret are aggregated first across datasets then across 10 folds of data each dataset.
4.1 TUNING XGBOOST AND LIGHTGBM
We tune set of 9-dimensional hyperparameters (all numerical) in LightGBM and I--dimensional hyperparameters (9 numerical and 2 categorical) in XGBoost. A detailed description of the search space can be found Appendix B In this section, we omit the multi-fidelity baseline method, i.e., ASHA, because do not find good 'fidelity' dimension that works well in tuning LightGBM and XGBoost (ref. additional results in Appendix B). We perform the evaluation on out of the 39 datasets from the AutoML benchmark ('Robent' and 'Dionis' memory error and extremely long training time). The input budget B (in terms of CPU time) is set be 4 hours for the largest datasets among the 37 datasets, and hour for the rest. From the performance curves shown in Figure 3 we observe that BO tends to perform well on small datasets, e.g., 'credit' in Figure where the Th budget is sufficient. Under the same budget, it may perform badly on large datasets, e.g., 'volkert' in Figure Bjc), as it may try configurations which consume very large portion of the budget at the early stage of the search. On the medium size dataset, e.g., "DDDCup09" in Figure [b), the local search method is more efficient than BO in the early stage but outperformed in the later stage. Bl eelnnSSerre rch performs similarly to the better one between L.S and BO in the early stage, and surpasses both of them in the later stage. We also observe that BOwLS performs similarly with LS (sometimes worse). This is because BOwLS needs to wait until local search converges before proposing Figure 4 a) & (b) consistent with these observations.
excluded due to out-of-
one. The aggregated result over all the test cases in
The interplay between local and global search in BlendSearch. We investigated the dynamics of local and global search thread selection in BlendSearch. As a case study, we show the results in mning XGBoost
datasets in Figure b)) and Figure aa) The result in Figure Tb)) shows

---

BaaccSearch
200
0.22
107
150
102
0.16
1000
2000
3000
Time(s)
# of thread switches
of threods induced by GS
Search thread selection in BlendSearch in tuning XGBoost on dataset KDDCup09. In this figure (and Figure [Tb,, which shows the result for dataset Volkert), each marker corresponds to time of search thread selection in BlendSearch. The diamonds correspond to the global search thread, and the solid circles correspond to the local search threads (different colors for different threads).
Figure 5:
Figure 6: The distributions of the # of thread switches and the of local search threads in- duced by the GS (short for global search) in B BlendSearch for tuning XGBoost. The result is aggregated over all the datasets evaluated in tunning XGBoot. The outliers with very large of thread switches and threads induced by GS are from very small datasets, where the number of evaluations large.
that the global search indeed plays a role after 1000s which contributes to Bl elnndSea c''h' better performance comparing to L.S. The result in Figure shows that although the first point suggested by the global search (at around 200s) does not yield significantly better performance immediately, the induced new local search thread (the thread in green circle) lead to a significantly better per- formance soon. These two figures together indicate that global search is not only responsible for directly finding better configurations, but also for creating local search threads that achieve yet better performance. We show two statistics about the overall interplay between global and local search in B BlendSearch all the datasets evaluated for tuning XGBoost in Figure
We provide additional experiments for tuning XGBoost and LightGBM in Appendix B, including a comparison with ASHA under different settings of fidelity, and an empirical study about the effect of low-cost initialization.
Takeaway. (1) Bl BlendSearch is able overcome the limitations of BO and LS and at the same time, inherit their advantages. By blending BO and LS, BlendSearch is able to outperform both on this large collection of datasets over time. (2) The interplay between global and local search indeed contribute to BlendSearch's good performance.
4.2 TRANSFORMER-BAST NLP MODEL FINE-TUNING
This section presents an application of economical hyperparameter optimization to an NLP model fine tuning task used in a large software company. It starts from a large transformer- basedd model Turing-NLRy2 with 24 transformer layers, each with 16 attention heads and hidden-dimension 1024 totaling 340M parameters. It is pretrained on English Wikipedia (2,500M words) and BookCorpus (800M words), and uses byte-pair encoding This pre-trained model is then fine-tuned (Dai & Le 2015) for use in multiple production scenarios, including sequence classification, named entity recognition and question answering. The fine-tuning procedure is performed for dozen separate tasks, and repeated on regular cadence, typically every few weeks. We focus our experiment on single sequence classification fine-tuning task where the objective is to label document (con- sisting of one or more sentences) with one of five possible classes. For fine-tuning this model we introduce classification layer with 1024 x 5 5120 additional weight parameters, randomly ini- tialized. The dataset used for training consists of 52K labeled examples, which we split 80/20 for training/validation. The objective maximize the fl-score obtained on the validation set of 10.4K labeled documents. Selecting hyperparameters for fine-tuning this model has been a manual process that typically takes data scientist a few days.
msturing eeturing.ors org
8

---

Table I: Results of language model fine-tuning.
method
wall-clock
GPU-hours
fl
Manual
(I0-20 working hours, spanned to few days)
40-80h
0,645
BlendSearch
3h
12h
0.652
ASHA-1
6h
24h
0,624
ASHA-16
6h
384h
0.640
In our experiment we use a 6-dimensional search space (4 numerical and 2 categorical). A detailed description of all the hyperparameters tuned, including their ranges, can be found in Table S in Appendix B We compare to ASHA and let it use 16 VMs with 4 NVIDIA Tesla V100 GPUs on each VM. We run ASHA with 16 concurrent jobs for 6 hours in wallclock time. That amounts to 4 x 16 x 6 384 GPU hours of hardware cost. We run Bl BlendSearch on a single VM of the same configuration for 3 hours, which uses 12 GPU hours in total. For comparison, we include ASHA-1 using the same single VM. The results summarized in Table [
Takeaway. Not only BlendSearch finds a more accurate model than both ASHA and manual effort, it does so faster and consumes only 3% of the resources of ASHA-16.
4.3 ABLATION STUDY
To investigate the effectiveness of several important modules of our framework (colored in orange in Figure 2) we perform an ablation study in tuning XGBoost on a random subset of the datasets (one third of the datasets mentioned in Section 4.1p. We show the aggregated rank of different variants of our method in Figure Ic). Specifically, we study the following three modules of the framework. (1) Priority metric. -BS-Priorty:
uses the round-robin policy in the search thread selector. (2) Config validator. 'BS-w/o- www/Coofiiggg//ee Validatrr skips the validity check of the proposed configuration. (3) Create new thread condition. In BBS-CreateConn:Alvvee 'BS-Creat SSS-CreatCond: BestOrFirst', the following two conditions are used as the condition for creating new local search threads respectively: always create, and create better than all the existing search threads' loss or there is no local search thread yet.
and
thread only when the loss is
From this ablation study, we have the following observations: (I) Making round-robin selection is worse than doing selection using our designed priority metric. Round-robin's 's relative performance becomes worse in the later stage of the search because it cannot avoid bad sad-performing search threads. (2) The config validator is also vital in our framework. (3) Overall, the conditions for creating new threads has smaller impact our method comparing the other designs studied. 'Better than half" condition used by default tends to perform the best.
5 EXTENSION AND FUTURE WORK
In the low-resource scenario which is targeted by this paper, each single trial is not resource-saturated if we spend all resources in it. So we do not recommend parallel trials in this low-resource scenario. In the case where more resources than the maximum resource each single trial can consume are available, our framework can be extended by running the trials from different search threads on multiple workers. For example, if there are additional workers available, we can keep invoking the search thread selector (but skip the local search threads that have (dd) trials running). Our design of having multiple independent local search threads naturally allows efficient asynchronous parallel trials. The design of utilizing existing global optimization methods allows existing easy- to-parallelize global optimization (such as random search or batch versions of BO) to be plugged in. The prioritization of search threads still useful as long as the maximal concurrent number of trials divided by the number of search threads is smaller than Odd). Since our method can be used together with multi- miltti-idelity pruning methods, can naturally inherit the asynchronous resource scheduling when used in the parallel setting. Parallelization is now supported in the latest version of BlendSearch' 's implementation.
In this work, we show the effectiveness of BlendSearch through extensive empirical study. As future work, it is worth studying the theoretical properties of BlendSearch, including theoretical guarantees about its convergence rate and total resource consumption.

---

REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Advances in neural information processing systems, 2011.
Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on bayesian optimization of expensive cost functions, with application active user modeling and hierarchical reinforcement learning- CoRR, abs/1012.2599, 2010.
Adam D. Bull. Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Res., 12:2879-2904, November 2011.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In KDD, 2016.
Andrew M Dai and Quoe V Le. Semi-super sequence learning. Advances in neural information processing systems, 2015.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D) Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. In Advances Neural Information Process- ing Systems, 2019.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter op- timization at scale. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), 2018.
Yuzhou Gao, Tengchao Yu, and Jinglai Li. Bayesian optimization with local search. In International Conference Machine Learning, Optimization, and Data Science, 2020.
Pieter Gijshers, Erin LeDell, Janek Thomas, Sébastien Poirier, Bernd Bischl, and Joaquin Van- schoren. An open source automl benchmark. In AutoML Workshop at ICML 2019, 2019.
András György and Levente Kocsis. Efficient multi-start strategies for local search algorithms.
Journal of Artificial Intelligence Research, 41:407 444,, 2011.
Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization, 2011.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial Intelligence and Statistics, 2016.
Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabás Póezos. Multi-fidelity
bayesian optimisation with continuous approximations. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, 2017.
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast bayesian op- timization of machine learning hyperparameters on large datasets. In Artificial Intelligence and Statistics, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms.. Cambridge University Press, 2020.
Liam Li. Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Jonathan Ben-tzur Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. A system for massively parallel hyperparame- ter tuning. Proceedings of Machine Learning and Systems, 2020.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel handit-based approach to hyperparameter optimization. In ICLR 17, 2017.
10

---

Zhiyun Lu, Liyu Chen, Chao-Kai Chiang, and Fei Sha. Syper-parameter tuning under budget constraint. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial In- telligence, IJCAI-19, 2019.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine
learning algorithms. In Advances neural information processing systems, 2012.
James C Spall et al. Multivariate stochastic approximation using a simultancous perturbation gradi- ent approximation. IEEE transactions automatic control, 37(3):332 341, 1992.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Gaussian pro-
Qingyun Wu, Chi Wang, and Silu Huang. Frugal optimization for cost-related hyperparameters. In AAA/'21, 2021.
Li Yang and Abdallah Shami. On hyperparameter optimization of machine learning algorithms: Theory and practice. Neurocomputing, 415:295 316,, 2020.

---

A MORE DETAILS ABOUT BLENDSEARCH
We provide detailed pseudocode of the sub-algorithms used in our framework.
Algorithm 3 SelectThread
Inputs: Framework-level state F which keeps a list of candidate search thread F,S and a pri- ority function F.Priority.
1: S arg m
arg maggaxseFFssss) F.rrioityy
S. F. S.
2: Shak
So
Outputs: S, Shak
Algorithm 4 BookKeeping
Inputs: Search thread S, one entry of observation x, generated by S, and F.
1: S.c. + S.c c
2: if S is local search thread then Update {(S.:.ii) hield and {S.a::max hie(d) (emm)))ee)))
3: i < S, then
4: S.52d S.c < S. S.c S. S. + I, S.c; and Sextest + X
5: if < F.I" then F.I +
Algorithm Ini.iaalieeearrchheette.
Inputs:
Search method L or G. problem P and initial point (x, c).
1: S. = L.T or G.
2: Initialize bookkeeping information of S: 8.4 S.l2 1, S. S. S.c C, and S.r.inn S.r,aax
for i E P.D
Choice of L.A used in constructing the 'admissible' region F.R. We normalize each numeric hyperparameter into [0.1]. The setting of C.A is decided by the local search method. For the local search method we chose, C.A is constant corresponding to the initial stepsize (fixed as 0.1).
Definition of ReachableInnneSteee by S2 if the distance between their incumbents is no larger than the maximal distance between the next proposal of S2 and the incumbent of S2. In the local search method we used, the incumbent the currently best config, and the maximal distance is equal to the stepsize.
in Alg 7
We define local search thread S to be reachable
B
MORE DETAILS ABOUT EXPERIMENTS AND ADDITIONAL RESULTS
B.1 EXPERIMENT SETUP
Settings of BO and LS. For BO, use implementation from Optuna 2.0.0 /bttps://optuna readthedocs 1o/ en/ stable Index. .ntll) with default settings for TPE sampler. For LSS, we follow the implementation guidelines from Wu al. (202T). After a local search thread is created from particular starting point, we fix the categorical dimensions and only search for numerical dimensions that local search thread. local search thread S considered to have converged (corresponding to S. S.cooverged() in Algorithml 7) once the stepsize of the local search thread is smaller than lower bound introduced by Wu et al. (202T).
Experiments in tuning XGBoost and LightGBM. The XGBoost and LightGBM experiments performed in server with Intel Xeon E5-2690 v4 2.6GHz, and 256GB RAM. A full list of hyperpa- rameters tuned and their ranges hyperparameters aligns with the search space used (Wu et al. 2021). l). On the same fold, the same random seed is used for LS, BO and BS. Experiments different folds different random seeds.
be found in Table and Table 2 The search space for numerical
Experiments in NLP model fine tuning, For ASHA, we set min and max epochs as and 16, and reduction factor 4.
12

---

Algorithm 6 Creaateleei.SSCnditiion
Inputs: I.F.
Outputs: [FS] Median((S. (SFF.sss)))
Algorithm DelettenndMrreels
Inputs: S.F
1: if S.cooverged)) then
2:
F. F.S
3:
F.R.x.! t F.R.... L.A, and F. F.R. & F.R.a. ViE
4: else
5:
for AS' E F
6:
if S' S.eeeaccabbll))))eee))) S'.1 < S.1 then F break else 5' &S..eachableennnessteel & S.1 S".1 then F. F
7:
8:
9:
() calculated as follows: (1) per dataset per fold, the method is ranked based on the loss validation set at each second (X-axis), starting from when there at least one finished config evaluation in any method; (2) the rank is then averaged across datasets per fold; (3) we finally compute the average rank (line) and confidence interval (shaded area) across folds. Scaled loss in Figure Per dataset per fold, min-max scaling applied each method using the maximum and minimum loss along the whole performance curve across all methods.
Result aggregation details. Aggregated rank in Figure (C)(() and [2[c)
calculated similarly.
B.2 ADDITIONAL EXPERIMENTAL RESULTS LIGITGBM AND XGBooST
More performance curves on LightGBM and XGBoost. The performance curves for tuning LightGBM on 3 representative datasets with 1h budget are shown in Figure 7 We observe that the performance of LS quite good (comparing to BO), especially on large datasets. This result is consistent with the results reported in (Wu et al. 2021). where all the hyperparameters for tuming numerical. our experiment XGBoost tuning, we include categorical hyperparameters. LS per- forms worse in this case because the introduction of categorical hyperparameters amplifies the local search method's limitation of being trapped in local optima. The observations about Bl BlendSear ch for LightGBM similar XGBoost tuning. The performance curves on the three large datasets with a 4h budget are shown in Figure and where similar conclusions can be drawn.
Multi-fidelity.
We compare BO and Bl BlendSearch with the multi-fidelity baseline ASHA for tuning LightGBM and XGBoost in Figure I0 In this experiment, we tried two choices of fidelity dimensions with ASHA, including number of iterations and sample size (the sample size begins with 10K, so small datasets are excluded) respectively. The results show that the multi-fidelit baseline overall perform no better than BO and are significantly worse than BlendSearch.
Table 2: Hyperparameters tuned LightGBM.
hyperparameter
type
range
init
tree num
int
[4, min(32768, # vinstance]]
4
leaf num
int
[4, min(32768. # instance)]
4
min child weight
float
[0.001, 20]
20
learning rate
float
[0.01, 0.1]
random
subsample
float
[0.6, 1.0]
random
reg alpha
float
[le-10, 1.0]
random
reg lambda
float
[le-10, 1.]]
random
max bin
int
[7, 10231
random
colsample by tree
float
[0.7, 1.0]
random
13

---

Table 3: Hyperparameters tuned in XGBoost.
hyperparameter
type
range
init
tree num
int int
[4, min(32768, instance)
leaf num
[4, min(32768, # instance)]
4
min child weight
float
[0.001, 20]
20
learning rate
float
[0.01, 0.1]
random
subsample
float
[0.6, 1.0]
random
reg alpha
float
[le-10, 1.0]
random
reg lambda
float
[le-10, 1.0]
random
colsample by level
float
[0.6, 1.0]
random
colsample by tree
float
[0.7, 1.]
random
booster
categorical
[ghtree, gblinear)
gblinear
tree method
categorical
|att, approx, hist)
random
Table 4: Hyperparameters tuned in DeepTables.
hyperparameter early stopping rounds
type int int float
range
init
[1, max(min(1...M)) instance),1500,10))
10
batch size dropout learning rate
[16, 1024]
512
[0, 0.5]
0.1
float
[1e-4, 3e-2]
3e-4
dense dropout
float
[0, 0.5)
0.1
net
categorical boolean
(DCN, dnn_nets}
random
auto discrete
False,, True]
random
apply gbm features fixed embedding dim
boolean boolean
False, True
random
False, True)
random
Table 5: Hyperparameters tuned in fine-tuning Turing language model.
hyperparameter
type
range
init
learning rate
float
[le-6, le-3]
random
hidden dropout probability warmup proportion batch size epochs
float
[0.05, 0.4]
random
float
[0.2, 0.4]
random
categorical
{16, 32}
32
int
[1, 16]
learning rate scheduler
categorical
(Warmup linear decay polynomial, random
Warmup linear, Warmup linear decay exponential]
2.
x
31x10
5x1e
LS BOWLS
29x10
24410-
1055
4,85 10
4.8 x
22x10-1
4.7
2.111--
24x10-1
1.00
2000 time (s)
3009
1090
2000
5000
1800
2000
3000
time (4)
time (s)
(a) blood, loss auc
(b) numerai28.6. loss 1 auc
(c) Albert, loss = 1 auc
Figure 7: Optimization performance eurve for LightGBM (1h).
14

---

BlandSearch
104
BOWLS
1035
6x10
4x10-1
10000
Fashion-MNISS loss log-loss
(b) dilbert, loss log-loss
(c) Covertype, loss log-loss
Figure 8: Optimization performance curve for LightGBM (4h).
BlandSearch
BO
LS
loss
16-1
time
time (s)
time (6)
(a) Fashion-MNIST, loss log-loss
(b) dilbert, loss log-loss
(c) Covertype, loss log-loss
Figure 9: Optimization performance curve for XGBoost (4h).
Rank
10-1
B0
PruneWithSamppe
PruneWithlter
10-2
time (s)
time (s)
(a) Average rank
(b) Scaled loss
Figure 10: Aggregated results on LightGBM and XGBoost. 'Purne and 'Prune Iter' represent ASHA using sample size and iteration number resource dimension respectively. BO and BlendSearch are the same those in Figure
15

---

2,8
BlendSearch
BlendSearch
B0
BO
Scaled Loss
10-1
2.0
1.8
166
10²
10
3x10
(s)
(a) Average rank
(b) Scaled loss
Figure 11: Aggregated rank and scaled loss on LightGBM with random initialization.
10
ВOHB
Hyperband
ASHA
BlendSearch-BoHt
BlendSearch-Hyppere
loss
BlendSearch ASHA
Scaled
10-1
4x10-1
187 time (s)
18.2
107
time (s)
time (s)
vehicle, loss log-loss
(b) Aggregated rank
(c) Aggregated scaled loss
Figure 12: Performance curves on cane, aggregated rank and aggregated loss on DeepTables.
Ablation study on the low-cast initialization. In this work, we use low-cost initialization for the controlled dimensions of the hyperparameters. Although such information is fairly easy to ob- tain, we investigate our method's robustness when controlled dimension is provided. We test LeenSeearch in controlled dimension agnostic setting: there are still hyperparameters with het- erogeneous cost, but the controlled dimensions and a low-cost initial point is not specified input. In such scenarios, BlendSearoo rch will use random initialization and the config validator always returns 'yes'. We compare Bl endSea rch with local search and BO under such a setting using the same random initial point. In Figure I we report the results including the aggregated rank and scaled loss LightGBM across half of the datasets mentioned in Section 44. Figure Iaaa & (b). The results show that even if BleedSeeacch is agnostic to the controlled dimensions and a random initialization used, it still able outperform both the local search method and BO.
B.3 TUNING DEEPTABLES.
In this experiment, we tune 9-dimensional hyperparameterss (5 numerical and 4 categorical as detailed in Table in DeepTables. Since the training of deep neural networks are more time-consuming than that of XGBoost, we run experiments for Deep'Tables on the datasets where they are worse than the best known performance tle', 'cnae". 'mfeat", 'vehicle', 'phoneme'. 'kel'. All experiments for DeepTables are performed in a server with the same CPU, 110GB RAM, and one Tesla P100 GPU, full list of hyperparameters tuned and their ranges can be found in Table
benchmark, including 'shut-
Recall that we mentioned multi-fidelity pruning strategies could be incorporated into BlendSearch in the config evaluator component. In this experiment, terested showing the performance B1 BlendSearch when combined with multi multi--idelity methods. To this end, include the three state-of-the-ar multi-fidelity methods, including BOHB (Falkner
particularly in-
16

---

et al. 2018), ASHA Li et al. 2020). and asynchronous HyperBand (Li et al. 2017 2020
which are shown efficient for tuning deep neural networks and the BlendSearch based on each of them. We use the following libraries for baselines: For BOHB, use HpBandSter 0.7.4 inttps://gitaeie
com aattmml /HpRandSter). For ASHA and asynchronous HyperBand, implementations from Optuna 2.0.0. In all the methods compared, including both existing methods and variants of BlendSearch, the number of training epochs is used as the fidelity di- mension, with maximum epochs 4. For ASHA, we set the minimum early stopping rate to be 4 (we adopted this setting as it yields better performance comparing the default setting, i... 0). The number of training epochs used as the fidelity dimension.
be 1024, reduction factor set to be 3, and minimum epochs
B. anlendeearee rch incorporates existing multi-fidelity methods in the following way: Each config, either proposed by global search or local search, uses the same schedule to increase the fidelity and check its pruning condition. For example, when ASHA (Li et al. 2020), i.e., asynchronous successive halving, with a reduction factor of is used as the pruning strategy, after each config evaluated by a certain fidelity, it is compared with other configs already evaluated by the same fidelity. The config will be pruned if its loss is ranked in the worst 1/n. Otherwise, the fidelity is multiplied by 17. In addition to the original pruning conditions specified by the fidelity method, configuration will also be pruned at particular fidelity level where pruning is performed yet, and the configuration does not yield superior performance (comparing to the currently-best performance) when evaluated that fidelity level.
We present the performance of all compared methods for tuning DeepTables in Figure 12 Fig- ure 12 a) shows the learning curves on dataset cane with budget 1h. Figure [2]b) and (c) show the aggregated rank and loss on all the datasets within budget 1h. The performance of multi-fidelity methods are significantly improved when used in our BlendSearen rc framework.
17


Reviews:
[{"review_id": "qAj5jpK-DoM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposes BlendSearch, which combines global and local optimisation for the problem of hyperparameter optimisation when search cost is heterogenous. To achieve so, they use the combination of one global search instance (e.g. Bayesian optimisation; used to identify promising regions as starting points for local search) with multiple local search instances (which actually do the search). The local search instances will be created, merged and deleted on the fly using the criteria proposed by the authors. The paper finally experimentally validates their approach in various hyperparameter tuning experiments to show promising results.\n\n============================================================================\nPros (in addition to the summary provided)\n-\tThe paper addresses an important problem and proposes a sensible strategy that builds on two successful ingradients. The paper is also quite well-written and easy to follow.\n-\tA plus in my opinion (not necessarily emphasised by the authors) is that this framework seems to be a plug-in improvement that is agnostic to the exact global and local optimisation algorithms used. Therefore, it can be potentially be used in a wide range of setups.\n\n============================================================================\nCons\nThere is generally no theoretical discussion in this paper. While the method can still be successful empirically, the reviewer thinks that having some sort of theoretical expositions will strengthen the paper and would more strongly motivate some of the algorithm design decisions the authors made. For example, the most important design is Step 1 of Blendsearch which is intended to balance exploration and exploitation, and it looks like the current approach (Eq (2)-(3)) are predicting the cost by the simple heuristic of extrapolating (linearly) past the observations, and I’m not sure how true this simplistic model is in reality. Given that a major selling point of this paper is about ‘cost awareness’, I feel that this aspect needs a bit more clarification/justification.\n\nThe idea of maintaining a simultaneous pool of different optimization instances is not new, and one example is TurBO-M that the authors cited, which formulate the selection of optimization instances as an implicit multi-armed bandit (MAB) problem.  While TurBO does not consider the cost heterogeneity and do not use local optimization instances, I think that their selection method is more principled and could be food for thoughts for the authors.\n\nAnother question is did authors consider batch version of BlendSearch, as currently the paper seems to rely on a purely sequential setup? Search in a parallel (and possibly asynchronous) way would greatly improve the applicability of the method in a practical setup. It would be nice to have discussions how easy it is to parallelize BlendSearch without degrading its performance.\n\nMinor\n-\tIn Fig 2, is the bottom leftmost diamond missing a ‘No’ path? I suppose there should be a No and a path straight from that diamond to upper rightmost ‘Search Thread Updater & Cleaner).\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ol6BZ0qqnlx", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The proposed BlendedSearch (BS) presents an intuitive next step in the combination of global and local search schemes for hyper-parameter optimization (HPO). Global search schemes are widely used for HPO but can suffer from large HPO times since their vanilla forms do not account for function evaluation costs. Local search schemes are usually not widely used for HPO but seem useful if the goal is to restrict the search to a region of the search space where the function evaluation costs do not grow drastically. The proposed BS interleaves global and local search steps to ensure that the global search does not go into regions of high evaluation costs while also avoiding being stuck in local minima.\n\nThe empirical evaluation of BS against various baselines demonstrate that BS has a better anytime performance relative to both local and global schemes. BS is also able to leverage multi-fidelity HPO schemes for reduced evaluation times and further improve upon them. The empirical evaluations also highlight the effect of the different parts of the proposed algorithm through an ablation study.\n\n\nHowever, the proposed algorithm raises a lot of questions that are not addressed in this paper. \n\nMost importantly, in my opinion, the empirical advantage of this proposed scheme is tied to how low-cost (and maybe low-loss) the initialization is from where the global and the local searches start. The initializations for the empirical evaluations are chosen to be low-cost (and maybe low-loss) for BS -- it is not completely clear from the main paper how these initializations were chosen and how (if at all) the considered baselines leveraged these initializations. It is not clear how BS would perform if initialized with a high-cost, high-loss point. It seems to me that having low-cost initialization(s) would also benefit something like GPEIPS -- instead of picking a single initial point, the GPEIPS could be initialized (similar to the proposed scheme) with a set of low-cost evaluations -- this would counter the issue in GPEIPS of requiring high-cost evaluations initially.\n\nAnother unknown is the interplay between the global and local search -- it is not clear whether the proposed scheme really leverages both global and local searches. In this current setup, where the local search threads focus on local \"low-cost\" regions, it seems plausible that the global search constantly get rejected repeatedly and never really used much (beyond initiating a few local threads). Given the \"exploitation\" evaluations obtained from the clearly favored local search threads, the current surrogate model (such as the GP regressor) would probably be in the \"exploration\" mode (trying out regions of the search space not part of the valid bounding box), which will often just get classified as invalid. For points to be valid, the $\\Delta_i$ for the local searches need to be large, but the choice of these $\\Delta_i$s are not discussed in this paper.\n\nMoreover, the MBB of the union of the all the local thread regions does not imply that the evaluation costs stay low for anything in that region for the global thread to pick without additional assumptions on the cost structure. It might be good to justify such a choice. The ablation study shows that the anytime performance is heavily reliant on such a \"ConfigValidator\" that keeps the search in low cost regions, but this ties back to the question about how the search gets initiated and how that would affect the performance of BS. It is not technically clear how the current algorithm can recover if started from high-cost region.\n\n\nBeyond this, there are various other questions which makes me think that we are not understanding the technical reason for the strong empirical performance, which makes me score this as a borderline paper. \n\n\nFurther questions:\n\n- The $\\Delta_i$ in the local search drives where the global search can look, so it is not clear how best to set that value (especially given the varying types and ranges for the hyper-parameters).\n- Also it is not clear how local search is accomplished with mixed continuous-integer-categorical hyper-parameters.\n- Why is \"Trust region BO\" (Eriksson et al., 2019) not applicable where the local models have \"low-cost\" initializations similar to the low-cost initializations used for BS?\n- As per notation, given a budget $B$, the goal of the problem is to \n $$ \\min_x P.LossFunction(x)  \\mbox{ subject to } G(\\pi) \\leq B,$$\n not necessarily minimizing $G(\\pi)$.\n- In Fig 4(a), where evaluations are not costly, how is it that BS is outperforming the BO? What is the intuition behind that? Shouldn't BO be the best? Fig 1(b) makes more sense -- eventually BO and BS have similar performance but BS has improved anytime performance.\n- Regarding \"performance improvement speed S.s\", it is unclear why speed is set to highest when the formula suggests it should be 0. This needs better clarification.\n- Again, pertaining to the definition of performance improvement speed, if $S.l^{2nd} = S.l^{1st}$, isn't $S.c^{1st} = S.c^{2nd}$ by definition? What does that mean for the definition of speed?\n- Formula in eq(2) could use more justification -- intuitively using the notion of \"speed\", we would have $S.s = (S.l^{1st} - l) / (S.CostImp(l) + S.c - S.c^{1st})$, implying $S.CostImp(l) = (S.c^{1st} + (S.l^{1st} - l) / S.s) - S.c$.\n- It appears that the \"Priority(S)\" is some form of a UCB over a local thread -- it would be good to formally discuss how (if at all) this priority is connected to well established notions of UCB/EI.\n- In \"Step 3: Search thread creator....\", what is precisely meant by \"incumbent of a LS thread is reachable by another LS thread\"\n- The paper does not clearly discuss how the fidelity of the global search (handled by HyperBand, BOHB, etc) translates to the fidelity of the local searches when leveraging multi-fidelity schemes\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AhiKr6qN6Ma", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new algorithm for black-box optimization (BlendSearch) that combines global search methods together with local search methods. The stated goal is to ensure convergence to the global optimum, while avoiding configurations with a high cost (e.g. that take a long time to evaluate).\n\nPros:\n- Section 2 (related work) is well-written and quite comprehensive. \n- Extensive experiments on different applications (XGBoost, LightGBM, DeepTables, fine-tuning NLP) which show promising results. \n\nCons:\n- The paper is lacking intuitive explanations for how and why the algorithm works so well.\n- Theoretical and/or experimental justifications are needed for some of the key statements in the paper.\n\nMy main criticism of the paper is regarding Section 3 and how the BlendSearch algorithm is described and presented. Clearly, the algorithm itself is a complex piece of engineering, and while that by itself is not a problem, very little intuition is provided to help the reader understand why the different design choices were made. Furthermore, it is not very clear to me how or why the fundamental claims made about the algorithm are true. For instance, it is stated that the algorithm will converge to the global optimum given sufficient budget. Is it guaranteed under all conditions? Maybe this needs a theoretical proof or maybe it is somehow obvious by construction, but either way the paper should explain this clearly. Additionally, it is not very clear why the config validator step helps to avoid configurations with a high cost: the process is described in technical detail but what is the intuition here? Fundamentally: why does local search help to avoid evaluating high cost configurations?\n\nIn Section 1 it is stated that multi-fidelty methods (e.g. successive halving or Hyperband) can only be used when cheap proxies for the “accuracy assessment” exist. However,  isn’t it always possible to construct such a proxy by taking a random subsample of the training data (e.g. as suggested in the Hyperband paper). In Section 4.1 the authors say that multi-fidelity methods were not considered as a baseline when tuning XGBoost and LightGBM, because they tried using both subsample size as well as number of iterations and in both cases it “hurt the performance”. It would improve the paper to include some experimental results to justify this statement. While of course it is true that a hyper-parameter configuration that works well on a small subsample (or small number of boosting iterations) may not work well on the full dataset (or with a large number of iterations), similar arguments can be made about the number of epochs when training neural networks (e.g. optimal learning rate for small number of epochs is not necessarily the optimal learning rate for a large number of epochs). This does not stop multi-fidelity methods being widely used to tune neural networks. \n\nAnother area where I think the paper could be improved is with how the authors deal with parallelism. While there does seem to be a paragraph in the Appendix stating that BlendSearch can be parallelized, it is not discussed in the main manuscript. Methods like Hyperband and successive halving and in the extreme case, random search, admit very high degree of parallelism. Because of this, in many real applications they are often preferred over more complex methods. While the results of Section 4.3 indicate that BlendSearch using 1 worker can out-perform asynchronous successive halving (ASHA) using 16 workers which is a nice result, it is not clear whether any parallelism was employed for the results in Section 4.2. If no parallelism was used, does ASHA even make sense (e.g. without any parallelism there is no need for the ‘asynchronous’ aspect)?. The paper could be made stronger by showing how the performance of BlendSearch improves as more workers are added, and how it compares to schemes like Hyperband and AISA with the same number of workers. \n\nAdditional comments:\n- Figure 1 does not seem to be referenced from anywhere the text. There are also no error bars shown on the plots. Given that the algorithms being compared are highly sensitive to their initial conditions, it is not possible to make statements without running multiple times with different random seeds.  \n- In Section 4.2, the author state that ‘BlendSearch-HyperBand’ uses random search for global search and HyperBand pruning strategy. However, the concept of a pruning strategy is not discussed anywhere in the manuscript. It is hard to understand what this means. \n- The notation used in Section 3 to group certain variables as “attributes” (e.g. P.CostFunc(.)) is quite non-standard and a bit hard to read, but maybe this is a personal preference. \n- In Section 3 could be improved by carefully defining what exactly what is meant by a ‘thread’ in this context.\n- In the experimental section, were the optimization algorithms re-run using different random seeds, or are all statistics generated over multiple folds with the same optimization seed? If the latter, the results could be severely biased if one algorithm uses a ‘lucky’ seed that results in a good sequence of configurations that work well across most datasets. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a hyperparameter optimization (HPO) method in which two search strategies: global and local optimizations, are effectively combined. All reviewers evaluated the proposed method positively. The experimental results clearly show the effectiveness of the proposed method, and it could be an important contribution to the AutoML research community. On the other hand, since there is no theoretical justification for the proposed method, it is not clear why the performance of the proposed method is improved so much. The author's rebuttal has alleviated some of our concerns on this point, but the further theoretical analysis is desirable.
Decision: Accept (Poster)