Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper introduces a series of Bayesian neural networks that predict the performance across different, discrete fidelities. The models for higher fidelities use the prediction on lower ones as inputs, which makes this model auto-regressive. the authors use this flexible model and combine it with a new acquisition function that aims to minimize the mutual information of a batch of potential query points and the current belief over the optimum. By designing a heuristic to optimize the acquisition function, the authors are able to apply their model to the problem of Batch BO.

In the experiments, the proposed method is compared to other state-of-the-art methods for regular BO, batched BO and multifidelity BO.
main_review:  I think the paper contains a very interesting method for modeling multiple fidelities/tasks with a cascade of Bayesian neural networks. Based on the presented results. the method seems very sample efficient, but the overhead is unclear. To my surprise, the sequential version of the algorithm performs worse than the batch one, which I would like to hear the authors' feedback on.
Missing related work on batch BO and missing details on the parallelism of the presented experiments, also lower my impression of the paper a bit.
I think that the paper contains two orthogonal ideas: the DARN model itself, and a clever way to approximate the mutual information for multiple points. Because the effects of those are not separated by an ablation study, the effects of contributions both make are not separable.

The paper is easy to follow, although I would suggest to move some of the details of the benchmarks to the appendix and expand the discussion about the acquisition function (which I found too dense) and a more detailed analysis of the results.

## Specific remarks/questions:

- In the discussion of equation (2), I am missing the OG multi-task BO reference

  Swersky, K., Snoek, J., & Adams, R. P. (2013). Multi-task bayesian optimization.

  equation 2 is one particular way of approximating the MTBO kernel, which is more general.
- The discussion about the limitations of multi-fidelity BO is missing MTBO and potentially stacked GPs from: 

  Golovin, D., Solnik, B., Moitra, S., Kochanski, G., Karro, J., & Sculley, D. (2017, August). Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 1487-1495)

  which shows as a different way of approximating the full covariance across tasks.
- About equation (5): In the normal context of batch BO, the whole batch is suggested at once, then evaluated and the results incorporated into the model. If this pre-batch query and model-update is followed here, wouldn't $max \lambda_{m_k}$ be more meaningful if the evaluations are in parallel? Otherwise querying a batch wouldn't give any advantage.
- The related work section is missing a discussion about batch BO methods, including (but not limited to):

  Wu, J., & Frazier, P. (2016). The parallel knowledge gradient method for batch Bayesian optimization. Advances in Neural Information Processing Systems, 29, 3126-3134.

  González, J., Dai, Z., Hennig, P., & Lawrence, N. (2016, May). Batch Bayesian optimization via local penalization. In Artificial intelligence and statistics (pp. 648-657). PMLR.

- The method labeld as SHTL, is referred to as ABLR (adaptive Bayesian linear regerssion) in the paper itself. The method also uses L-BFGS to optimize all parameters, which was replaced by ADAM here. Not sure how much that impacts performance, but it should be pointed out in the paper.

- It is nowhere mentioned if evaluations where carried out in parallel. If they were, it should be stated how many parallel evaluations where performed. If they were all done sequentially, I would like to understand why the BMBO-DARN-1 performs worse. Usually, batch methods are outperformed by their sequential counterpart when the batch is evaluated sequentially, but become useful when the evaluations can be performed in parallel.

- BMBO-DARN is very performant across all shown benchmarks, but I wonder how much each contribution has, i.e. how does the auto regressive model compare against a simpler model, but with the same acquisition function, and how would the DARN model work with MF-MES.

- The performance is shown versus the  accumulated cost, so I assume the overhead of the HMC sampling and the elaborate acquisition function is not included. Especially for the XGBoost example, I would assume the overhead to be substantial. What would these plots look like if this overhead is included?

- Following up on the previous point, could you please comment on the average evaluation time for the benchmarks at the different fidelities? It is really hard to judge how many configurations have been evaluated across the different benchmarks.
limitations_and_societal_impact: The authors failed to address any limitations of the method. A discussion about the choices of the fidelities, and what happens if they are poorly chosen is missing. A discussion about the overhead of the model would also be appreciated.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper suggests a methodology for performing multi-fidelity Bayesian Optimziation (BO) using a particular (deep auto-regressive) Neural Network model as the surrogate. The authors formulate a batch acquisition strategy based on max-value entropy search, and propose an approximation using posterior sampling and cyclic optimization that renders the optimization of the acquisition function tractable. The method is evaluated on both synthetic and real experiments, where it shows improved performance over existing approaches.
main_review: 
### High-level summary
- The problem setting is relevant and of interest to the community.
- The modeling approach seems quite an incremental contribution over previous work, and it is unclear what the effect of the model on the performance of the overall approach is.
- There is some but not much methodological novelty in the approach; it essentially uses a standard batch MES formulation with a (slightly modified compared to previous work) BNN model and  some approximations of the acquisition function to render computations tractable. The main novelty is in these approximations; however, I am not convinced of the merits suggested approach.
- The writing is generally ok (some wording issues, repetitive in some places), overall the paper is relatively easy to follow.
- The empirical evaluation includes a good number of baselines, but is quite sparse on details and thus not clear; this section needs to be improved. In the current form, it's hard to assess the significance of the results. 
- Overall, a potentially interesting approach, but too many open questions in the current draft.
- Not making the bar for NeurIPS in the current form.


### Notes
- The authors appear to suggest that all GP approaches have computational complexity of N^3: There area  number of of ways around this (e.g. linearge conjugate gradient solves instead of Cholesky-based approaches, interpolation / sparse GPs, variational GPs, etc.). These have some other challenges but they should at least be mentioned as ways to reduce computational complexity.
- In all the examples considered in the paper, the different fidelities correspond to different "lengths" (epochs, weak learners, LBFGS-B steps). An alternative approach to pre-committing to the length of the evalution is to to not specify the fidelity of a candiate priori but perform early stopping while obtaining partial results. Such approaches are at least as good as pre-committing (since that is a special case of the early stopping setting). The paper should discuss the early stopping line of work; please also explain why you consider the pre-comitting approach.
- Modeling:
  - The modeling approach is not particularly well motivated and the contribution seems quite incremental compared to previous work.
  - Specifically, the main difference to the model of Li et al. is that fidelities here depend on the output of all previously modeled fidelities. This doesn't really cause any technical challenges and is a reasonably setup, but it's not clear from the paper what the effect of this change is.
  - In particular, there is no evaluation of the model fits, and a lack of an ablation study comparing to the simpler model from Li et al. means that it's not possible to separate the effect of the model and the effect of the different approach to optimizing the acquisition function (in the case of sequential optimziation).
  - This point is particular pertinent since in all of the real-world examples considered, one would expect a relatively simple (and not complex) relationship between the fidelities. It's not clear that in any of the real world the examples the additional model capacity obtained by the modified structure would be all that helpful.
  - The model is motivated with "complex, strong (nonstationary, nighly nonlinear) correlations across fidelites": Can you give some more conrete examples to provide some motiviation/intuition for where/in which practical applications this is / would be the case?
  - Model fitting fo BNNs is known to be much more finnicky than other approaches. The authors state they fit models by "looking at the trace plots", which does not seem particularly robust / automatable (e.g. "step size was chosen as 0.012" - why and how? how hard was it to determine this value?)
- Acquisition Function:
  - Sec 4.1 is a bit light on discussing similarities and differnces to other batch acquisition functions. How does this approach relate to the asynchronous variant in Takeno et al.? It would also be useful to discuss the relation to the GIBBON batch MVES approximation developed in [1].
  - There seems to be a bit of a tension between the modelinga approach using a BNN (much more flexible than existing GP-based formulations) and the efficient computation scheme that is based on moment moment matching.
    - The approach is based on Laplace approximation, which is presumably a pretty coarse approximation. If that is true, what is the motivation for building a complicated BNN model in the first place? It seems that the cases in which the more expressive model helps would likely be those where the approximation used in the computation of the acquisition function will be poor.
    - It's not clear how well the Laplace approximation works for this problem. It woudl be helpful to verify in simulations on real problems that this is in fact a reasonable thing to do.
  - The coordinate descent approach optimization is reasonable but has obvious issues that should be discussed (e.g. this can get easily get stuck in local optima).
- Experiments:
    - The difference between BMBO-DARN and DNN-MFBO isn't particularly large (would be good to see p-values of a hypothesis test for the difference).
    - The real-world application evaluation seems to be quite comprehensive, a few models and quite a few baselines. However, additional ablation studies are necessary to understand the impact of the modeling change and the impact of the acquisition function formulation (see above).
    - There is lack of detail on the evaluation criteria. Specifically, it is not clear to me what exactly the accumulated cost is, and how it is computed in the batch setting (e.g. how is it defined if there are heterogeneous fidelities that take different times to evaluate?). Reading this section, I was left confused and concerned that there might be an apples-to-oranges comparison of non-batch vs. batch methods going on. IN particular, the fact that BMBO-DARN-1 is a varaint that "queries at one input and fidelity each time (B = 1)" performs worse thatn BMBO-DARN is surprising, since purely sequential optimization should perform much better than any batch variant if given the same fidelities to choose from. Essentially I have two ways to read this: (1) The cost function is not actually summed across the cost of the batches running in parallel (i.e. only overall wall time is counted, not total CPU time), or (2) the BMBO-DARN-1 only evalues at the highest fidelity. EIther version would be somewhat misleading (in the latter case an obvious baseline that would need to be added would be one that only allows low fidelity evaluations to make sure the improvements observed here don't just come from the fact that using lower fidelities is generally enough). Please clarify this and be explicit about the evaluation metrics and the benchmark procedure.
    - Why don't the losses all start at the same value if the initial points are shared between methods?
    - How many function evaluations are actually performed in the experiments?
- Miscellaneous:
    - Somewhat repetitive discussion of "other approaches simplifying things" (introduction, background, related work): should consolidate this somehow as the repeated discussion does't really add anything
- Wording (selected):
    - "most commonly used surrogate is GP"
    - "this might because these models are not effective"



### Questions
- You mention "the standard one by one querying strategy": Can you elaborate on this? I don't think this is true, there has been a lot of work on batch and fully asynchronous candidate generation in the past (see e.g. ), e.g. via sequential conditioning on pending points.
- "running L-BFGS with 10, 100, 50K maximum iterations": Is this correct? this seems like an obscene difference in fidelities. It would also seem odd with the average training time. Or is the idea that 50K basically just means "LBFGS until convergence"?
- Timings in Figure 2:
    - Is this the average time per candidate or the average time per batch?
    - How much time is spent on model fitting, how much on acqf optimization?
- What MF-MES implementation is used? The paper just states "We used a Python implementation of MF-MES and MF-GP-UCB". It seems from Figure 2 that whatever was used is extremely slow; it seems quite possible to substantially reduce this time (and likely also optimization performance) with a proper implementation.
- Is there an assumption that the fidelities are ordered? If so, what if that's not the case? Will things still work ok? It seems like the auto-regressive model might not be the best approach in that case.
  - How could this approach work with continuous fidelities? These are common e.g. in HPO for ML training;  incorporating some prior information about the structure information should help with the modeling.


### References
[1] Moss, M., et al., GIBBON: General-purpose Information-Based Bayesian Optimisation. arXiv:2102.03324, 2020

limitations_and_societal_impact: -There is more room for discussing limitations; see main review for details. 
- No concerns regarding social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In multi-fidelity black-box optimization, f() can be queried at points x at different levels of precision. Higher levels of precision have higher costs. Prior work on Bayesopt for mfbbo used GP models for multi-fidelity observations that make simplistic assumptions about correlations across fidelities. In response, the authors propose instead using a flexible autoregressive model for modeling the sequence of fidelity scores for a given x. Bayesian inference on the model is performed using HMC.

The paper also introduces a batched form of max-value entropy search and an algorithm for optimizing this complex acquisition function that works well in practice.

The experimental results are impressive. The proposed method outperforms a large number of popular methods from the literature.
main_review: =originality=
The paper provides multiple novel methods (surrogate model, batch acquisition function, etc) that will be of broader interest to the Bayesopt community.

=clarity=
Overall, good. See comment below about the problem statement, though.

=significance=
Multi-fidelity black-box optimization has applications in a number of important domains, including neural network hyper-parameter tuning. This paper benchmarks against a variety of recent algorithms from the literature and demonstrates an impressive performance improvement. 

=comments=
The paper would be improved by a more formal problem statement. Lines 92-106 are largely focused on a discussion of related work. It's unclear to me, for example, why eq (2) is necessary. It would be helpful to better explain the action space for the algorithm. For example, do fidelities have to be queried in increasing order of cost? If you query f() at high fidelity, does that mean that you get a low-fidelity measurement for free? This is the case for neural network training (where high fidelity corresponds to more training steps), but not true in general.

 I'm assuming that for each x you can evaluate f at any given fidelity. However, the parametrization of the autoregressive model in (3) suggests that predicting at a given fidelity requires having data for every available measurement of x at lower fidelity. This places a considerable restriction at the action space that isn't reflected in a problem definition or in sec 4.3. There are ways to parametrize an autoregressive model such that it can handle missing data, but this is not discussed.

Also, it was unclear to me why you need to have a separate model for each fidelity in (4). Wouldn't there be a shared model that could model all of the fidelities, and thus would have more training data?

I'm not that familiar with the latest literature on max-value entropy search. Can you comment on what is novel in your usage of it. It was unclear to me, for example, what parts of sections 4.1 and 4.2 are new.

The experiments section contains a thorough ablation analysis of the impact of various surrogate models. This helps provide evidence for the importance of one of the paper's contributions. However, the paper's other contributions (batch acquisition function, strategy for optimizing the AF) are not analyzed. I'm curious, for example, what would happen if you used a simpler acquisition function that doesn't account for interactions within the batch or used something other than MVES.
limitations_and_societal_impact: no
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Multi-fidelity methods are prevalent in problem settings where high-quality (but difficult to acquire) observations are enhanced with lower-quality (but more easily obtained) samples of a function. In this paper, the authors focus on the application of multi-fidelity modelling to hyper parameter tuning, whereby different model settings are verified with varying fidelity constraints (such as epochs in a training loop) in order to achieve the best accuracy-cost trade-off. The model introduced here is based on chained neural networks, whereby the input at each fidelity layer combines the input in the original domain for the function to be estimated, along with the outputs from the preceding fidelities. In order to carry out BO, the authors develop a batch acquisition technique that encourages diversity across the samples being drawn. This is in contrast to other techniques where new samples are drawn one a time, thus incurring the risk of there not being sufficient diversity across successive iterations. In order to achieve this goal, the authors also propose an alternating optimisation scheme for iteratively selecting samples across different fidelities.
main_review: ### Strengths

- Having a multi-fidelity model that can be trained end-to-end is an appealing property, as it allows for learning the interactions across fidelities in a unified manner rather than disjointed. The batch acquisition function also arises quite naturally from the formulation of the model, meaning that the authors do not have to rely on a multitude of empirical tricks and implementation hacks to meet the desired goal.

- The performance of the method is evaluated over over benchmark functions (for assessing the quality of the multi fidelity model in isolation), while four hyper-parameter optimisation set-ups are used to validate the practical effectiveness of the BO proposal. This variety of experiments successfully addresses the different potential uses that the methods proposed in the paper might have. 

- The paper is very well-written and organised. The literature review adequately covers related work, and the experimental evaluation also includes a wide variety of competing methods, some of which were implemented by the authors themselves.


### Weaknesses

- The importance of having a multi-fidelity model that is either chained or trained end-to-end has already been explored by Perdikaris et al (2017) and Cutajar et al (2019) for deep GP model constructions. I think that discussing this connection could be beneficial to the paper as the superior uncertainty estimates that are typically expected of GP models should be relevant to the iterative BO procedure explored here.

- It would be interesting to more explicitly state the potential limitations of the proposal here. For example, how well does the MF model scale to large input dimensions, either in terms of computational efficiency or expressivity? The paper successfully leverages weaknesses in other methods for motivating the work work described here, but there is little insight into which conditions might cause this method to underperform.

- In the same vein of the above, the paper doesn’t really hint at how the method described here can be improved or extended further in future work.


### Writing and Clarity

The paper is very well-written and a pleasure to read. The proposal is well-motivated and the multi-fidelity batch acquisition function is properly explained. One possible suggestion would be to include a visualisation of the multi-fidelity model itself (and how the output of the various layers feeds into the next) within the main paper itself.

Some very minor typos:
- *L2:* between *the* cost and accuracy
- *L15:* reference to *alternating optimization* is a bit confusing here.
- *L41:* between successive queries *and* is at higher
- *L83:* most commonly used *class of surrogate models are Gaussian processes*
- *L114* might limit the *expressivity*
- *References:* Certain terms (e.g. Bayesian) and conference names need to appear as capitalised in the references.


### Overall Recommendation

Besides putting forward an interesting problem to solve, the authors propose a well-rounded solution and provide multiple experiments that showcase the diversity of settings this work can be applied to. Just as importantly, the paper and its writing are already in a state fit for publication, which gives me greater confidence in recommending it for acceptance.
limitations_and_societal_impact: As highlighted in the main review, I think it would interesting for the authors to expose the limitations for this work more clearly. Having more insight into what could constitute future work would also be appreciated. There is no immediate societal impact to consider here.
review_title: null

Meta-review: Ultimately, I am recommending this paper for acceptance because I believe the approach to multi-fidelity optimization proposed by the authors is sufficiently novel and the experimental evaluation is sufficiently strong, and I am thus in agreement with Reviewer gu5R and Reviewer Hcby that, after substantial incorporation of feedback from the reviewers, the paper is solid. Furthermore, I believe that you do indeed already include several of the ablation studies asked for (e.g., BMBO-DARN-1 vs MF-MES is equivalent to an ablation of how much the DARN matters). While I believe the paper has flaws (see below), I believe most of these flaws are in argumentation rather than in execution, and would not require changes significant enough to warrant rejection.

With that said, I want to be clear that several of the criticisms raised by Reviewer zV6Z and Reviewer JVN7 seem valid to me, and for at least a few of them, I found the author response to be unconvincing.

First, the claims made on lines 143-149 and repeated in the author feedback that it is expected for batch acquisition to be more query efficient than sequential acquisition seem specious to me, and I would remove or rephrase them. If I am selecting a set of points x_1,...,x_k, clearly there is nothing inherent about knowing the labels y_1,...,y_{k-1} that forces a worse choice of x_{k}. Rather, certain sequential acquisition functions like EI are known for being myopic. Having access to more information should always enable more informed decisions than having access to less information. Saying that sequential decision making can "underrate the correlations between consecutive queries" does not seem rigorous enough to explain this claim. Rather, batch acquisition is typically more efficient than sequential optimization in terms of total wall-clock time, and indeed the results presented in Figure 1 are given in terms of time. While the advantages of your approach in terms of time elapsed are clear, I would **strongly recommend** the authors additionally use the supplementary materials to report results in terms of query efficiency to remove this confusion.

Second, your claim that "our topic/work is multi-fidelity batch BO and is irrelevant to early-stopping" seems overly dismissive of Reviewer zV6Z's concern. Every experiment in Figure 4 falls precisely into the setting Reviewer zV6Z is describing, where training can be stopped at any time (e.g., early stopping) rather than pre-determining a set of training lengths to use as epochs, as for example Freeze-thaw BO (Swersky et al., 2014) does, which you yourself cite. While of course in the general setting, fidelities can be arbitrary discrete measures of precision that do not lend themself to early stopping, the experiments you choose to run in your paper do indeed fit the setting considered by Swersky et al. 2014 and others. I would strongly encourage the authors to reconsider which criticisms may be valid and which may be dismissed when preparing the camera ready version, as many of the questions raised here are likely to be shared by readers of the paper at large.
Decision: Accept (Poster)