Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
This 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.

============================================================================
Pros (in addition to the summary provided)
-	The 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.
-	A 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.

============================================================================
Cons
There 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.

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

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

Minor
-	In 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).



review_title: Official Blind Review #1

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

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


However, the proposed algorithm raises a lot of questions that are not addressed in this paper. 

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

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

Moreover, 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.


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


Further questions:

- 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).
- Also it is not clear how local search is accomplished with mixed continuous-integer-categorical hyper-parameters.
- 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?
- As per notation, given a budget $B$, the goal of the problem is to 
 $$ \min_x P.LossFunction(x)  \mbox{ subject to } G(\pi) \leq B,$$
 not necessarily minimizing $G(\pi)$.
- 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.
- 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.
- 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?
- 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$.
- 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.
- In "Step 3: Search thread creator....", what is precisely meant by "incumbent of a LS thread is reachable by another LS thread"
- 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

review_title: Next-step in blending local & global schemes for HPO; strong empirical performance; raises significant technical questions

final_score: rating: 7: Good paper, accept
review_content: 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).

Pros:
- Section 2 (related work) is well-written and quite comprehensive. 
- Extensive experiments on different applications (XGBoost, LightGBM, DeepTables, fine-tuning NLP) which show promising results. 

Cons:
- The paper is lacking intuitive explanations for how and why the algorithm works so well.
- Theoretical and/or experimental justifications are needed for some of the key statements in the paper.

My 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?

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

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

Additional comments:
- 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.  
- 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. 
- 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. 
- In Section 3 could be improved by carefully defining what exactly what is meant by a ‘thread’ in this context.
- 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. 

review_title: A complex algorithm with some impressive results, but lacking rigorous and/or intuitive justification.

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)