Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper focuses on the setting of multi-objective Bayesian Optimization (BO), when observations are corrupted by noise. Existing approaches only consider the uncertainty in the new point where the function is being evaluated, but consider the Pareto front from prior observations to be fixed. This work, on the other hand, additionally assumes uncertainty in the Pareto front - this is a natural assumption when observations contain noise. The authors introduce a new acquisition function, NEHVI, which extends the classical expected hypervolume improvement (EHVI) criterion. They also derive a new parallel variant with polynomial complexity, qNEHVI, which can replace the more complex qEHVI variant; this is made possible by re-using cached box decompositions. Various experiments demonstrate strong performance and competitive wall-times.
main_review: Strengths of this work
- The work is very well motivated. Assuming uncertainty in the Pareto front is not just desirable but also required, in the standard BO setting where observations contain noise.
- The idea of caching the box decompositions is a central contribution of this work. This idea allows the efficient (polynomial) computation of qNEHVI (or qEHVI), which would otherwise be intractable (exponential) is we use the standard inclusion-exclusion principle (IEP).
- The experiments are quite comprehensive, in the sense that they include several competitors from prior literature and a number of synthetic and real benchmarks. qNEHVI with cached box decompositions performs consistently well in terms of Pareto front quality and wall time.
- The CBD-based algorithm offers very visible benefits in terms of execution time compared to the IEP-based algorithm. The latter cannot even handle batch sizes beyond a certain size (e.g., 16 or 32).
- The work seems to be technically sound, and it contains a rigorous sample average approximation convergence result for NEHVI.
- The paper is well written.

Concerns about this work
- My major concern is that this work is more or less an extension of (Daulton, Balandat and Bakshy 2020). That work already introduces some important concepts: (i) the q-expected hypervolume improvement (qEHVI), (ii) box decompositions for the computation of hypervolume improvement, (iii) computing q-HVI with the inclusion-exclusion principle, (iv) (quasi-)MC methods for computing qEHVI, (v) differentiability of the MC-estimator qEHVI, and (vi) sample average approximation convergence results for qEHVI. The major contributions of the current work compared to (Daulton, Balandat and Bakshy 2020) are in my view:
  - Assuming noise/uncertainty in the Pareto front when computing the expected hypervolume improvement.
  - Caching the box decompositions to avoid computing the Pareto front and performing an expensive box decomposition every time we draw new samples (this is a very central idea in this work).
  - Algorithm for efficient sequential greedy batch selection using cached box decompositions (polynomial complexity versus exponential with inclusion-exclusion principle). 

The idea of caching the box decompositions is certainly interesting and has the potential to improve efficiency, but overall the novelty is not very strong. To me, this work seems to be mostly about efficient computation of  qEHVI (or the more general qNEHVI).
- Related to the point above, the convergence result is very reminiscent of the convergence proof in (Daulton, Balandat and Bakshy 2020).
- The scope of this work is a bit unclear. On the one hand, this work is about extending EHVI or qEHVI with noise. But on the other hand, it is about efficient computation of both the noiseless and noisy variants. The efficient batch selection algorithm could even be applicable in the original noiseless setting.
- The asymptotic complexities for CBDs or IEP depend exponentially on the number of objectives. This means that even with the efficient algorithm proposed in this work, multi-objective BO over several objectives could be prohibitively expensive. On the other hand, for up to 4 objectives approaches based on trust regions (e.g., (Eriksson et al. 2019) or (Eriksson and Poloczek 2021)) might be able to handle high-D inputs and multiple constraints better. Furthermore, Thompson sampling for evaluation of candidate points could lead to high efficiency. It is not clear how this line of work compares to such approaches in terms of solution quality or efficiency.

Additional questions to authors
- Are there new technical elements in the convergence proof compared to the convergence result in (Daulton, Balandat and Bakshy 2020)?
- Have the authors tried experiments with more than 4 objectives? Could the CBD-based algorithm handle several objectives?
- At what noise levels (e.g., in terms of std) does it start to make a difference whether we use EHVI or NEHVI? Are small noise levels still able to lead to visible errors when using EHVI?
limitations_and_societal_impact: The authors discuss openly the limitations of their work in Section 8 (Discussion Section).
The authors discuss the potential societal impact of their work in detail in Appendix A.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a novel method to perform multi-objective BO based on Expected HyperVolume Improvement. Specifically, the authors argue that taking into account noisy observations and dealing with that noise improves the optimisation as they introduce a new acquisition function NEHVI. They moreover introduce a parallelisation framework enabling scalable batch acquisition in their novel acquisition function. This paper is well written. The ability to use EHVI in a noisy environment is useful in practice and in my opinion, the improvement in scalability is important for the community. However, I would have liked to see experiments led with varying numbers of objectives as it is known that it’s a main bottleneck of EHVI in practice.
main_review: 1) The authors interestingly avoid having to decompose their hypervolumes at each iteration using a cache mechanism. I think this is a good direction and really relevant. What is not clear to me, however, is what order of error is introduced using the above mechanism? Can the authors please elaborate a bit on this in their rebuttal? 

2) Is the decomposition fixed for each BO step? If so, what is the impact on estimating (2)? It would be interesting to see such an analysis.

3) It is mentioned by the authors that IEP and CBD are mathematically equivalent but can CBD - while producing the exact same acquisition value for a set of points, is significantly cheaper – scale to as many objectives and what is the cost of using CBD over IEP in practice, maybe in terms of convergence of the acquisition optimisation apart from purely memory & wall-time?

4) Related to the above, Theorem 1 relates to NEHVI but not qNEHVI. What is the cost of SAA in that case on the convergence during the acqusition Optimisation?

5) There are many benchmarks in this paper which is great. However, I would really like to see the performance as a function of an increase in the number of objectives as well as in terms of higher dimensions. Can the authors perform such an analysis?

Related Work: 
I think the paper covers the most relevant related work. I do, however, think include and benchmarking against the following can aid in further improving the paper: 
1. http://proceedings.mlr.press/v80/lyu18a/lyu18a.pdf
2. https://arxiv.org/pdf/2012.03826.pdf

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a version of a parallel Expected Hypervolume Improvement acquisition function for multi-objective Bayesian optimization. They show improved scaling over existing methods on a variety of benchmarks.
main_review: The technical contribution is incremental but solid. Some claims must be clarified, as well as highlighting when simplifications are done for speeding up computations (e.g., not just in appendix). The empirical results are strong.  

Detailed comments

In the abstract, the authors “argue that, even in the noiseless setting, the problem of generating multiple candidates in parallel can be reduced to that of handling uncertainty in the Pareto frontier.” but the meaning is unclear in the rest. Note that there are works on quantifying the uncertainty in the Pareto front, see e.g., 
- Calandra, R., Peters, J., & Deisenrothy, M. (2014). Pareto front modeling for sensitivity analysis in multi-objective bayesian optimization. In NIPS Workshop on Bayesian Optimization (Vol. 5).
- Binois, M., Ginsbourger, D., & Roustant, O. (2015). Quantifying uncertainty on Pareto fronts with Gaussian process conditional simulations. European journal of operational research, 243(2), 386-394.
In addition, this is seemingly in contradiction with the beginning of Section 5 where sampled Pareto fronts are not updated based on the batch points (in the noisy case).

It is referred several times to the “exponential” complexity of the batch variant, presumably related only to the method in [7]. This should be clarified.

In section 4, it is written “To our knowledge, all previous work on EHVI assumes that observations are noiseless” while there is a dedicated paragraph starting line 128, and just below, line 182, is the obvious fix. Note that reinterpolation is another commonly used option in practice, see, e.g., Forrester, A., Sobester, A., & Keane, A. (2008). Engineering design via surrogate modelling: a practical guide. John Wiley & Sons.
 

Minor points:
- Figure 1: Add true Pareto front and reference point
- Page 1, line 66: what is a “high-quality implementation”?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors describe an BO algorihm for multi-objective optimization using hypervolume improvement. The main contribution is the incorporation of noise into the estimation of the improvement measure. The algorithm is evaluated on four functions and theoretical analysis is performed. In the experiments, the algorithm performed best on the set of functions.
main_review: strengths:
- Straight forward idea that is easy to understand
- Theoretical and empirical analysis

weaknesses
- The evaluation section features significantly more algorithms than objective functions that are evaluated.
- Some of the literature/contributions in ES-based MOO are missing
- In parts the paper feels like it is using much too much text to present a small(but neat!) idea.

Details:
- I would have liked to see some more functions to evaluate. An easy target would have been parts of the BBOB-biobj benchmark (with and w/o artificial simulated noise). The noise-free version would give an indication of how well the algorithm is positioned within the overall segment and would enable comparisons to strong noise-free baselines like the UP-MO-CMA-ES. This would also give strong indications of how more difficult the functions become under the chosen level of noise.

- The idea of doing greedy optimization for hypervolume improvement in section 5.1 is not new. The MO-CMA-ES is doing that (under the name hypervolume contribution, see[*]) to select which subsets of point to keep in the pareto front. Otherwise the adaptation to the noisy case seems to follow straight forward from the approach. 

- I feel that the presentation could be improved and shortened a lot. e.g. the rhs of (3) feels unnecessary since it just spells out how the HVI is computed by the algorithm. The paragraph "Conditional Posterior Sampling" reads like standard optimization techniques used to acquire GP samples and has nothing to do with CBD. 5.1 similarly seems to be completely independent of CBD and any algorithm for computing the HVI could be inserted here. Moreover, it feels like the novel core of 5.1 is just a short addendum to 4.2. This is a bit of a shame because some of the "meat" of the paper has been moved to the appendix to make space for these computational basics which do not serve the presentation of the core idea.

I do think the idea is good and if i have not missed any important prior work, it does present a good contribution to the field (even though I am not an expert in the BO side of MOO). But I think, the authors should take some time to add a few more results and to slightly clean up the paper to make the core idea more prominent.

Note: Contrary to what the checklist states, i could not find any mention of compute time spent on the experiments. There is a statement of higher efficiency i have found, but no measurement of approximate compute resources required to repeat the experiments. If I missed it, maybe the authors can provide me a hint to where it is written.

[*]Thomas Voß, Nikolaus Hansen, Christian Igel: Improved Step Size Adaptation for the MO-CMA-ES


limitations_and_societal_impact: limitations are discussed.
review_title: null

Meta-review: We thank the authors for the additional clarifications provided in their rebuttal. All reviewers agreed that this work is of practical importance and made solid contributions by building on top of prior work, addressing an issue overlooked in the literature (namely the uncertainty residing in the Pareto front). The authors conducted an extensive set of experiments. They pre-dominantly focus on BO methods; including multi-objective approaches not relying on the BO paradigm could strengthen the paper. It was is also surprising the author missed to include the following reference/baseline:

Daniel Golovin and Qiuyi Zhang. Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization. 2020.
Decision: Accept (Poster)