Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, a Bayesian optimization algorithm using Joint Entropy Search (JES), a new entropy search type acquisition function, is proposed to efficiently estimate the Pareto solution set for multi-objective optimization problems. JES is defined as the mutual information between the pair of optimal solution set and the optimal value set,  (X^*, Y^*) and the new query point (x, y). While PES and MES, the main conventional entropy search type acquisition functions, focus only on the marginal distribution of the optimal solution and optimal value, respectively, JES determines the next acquisition point by considering their joint distribution. 

JES can be expressed as the difference of two differential entropies as in other entropy search type acquisition functions. For its optimization, the authors proposed a method to approximate the expected value of entropy for the pair (X^*, Y^*) of the optimal solution set and the optimal value set that appears in the second term of the JES acquisition function. Specifically, when there is no observation noise, entropy can be calculated analytically since the argument distribution is a multivariate truncated normal distribution, and when there are observation error, the entropy of the multivariate normal distribution that bounds it from above can be used as an approximation. Specifically, when there is no observation noise, entropy can be calculated analytically since the argument distribution is a multivariate truncated normal distribution. When there are observation errors, a multivariate normal distribution whose 1st and 2nd moments are equivalent to the argument distribution can be used as an approximation. This is because the entropy of latter distribution is bounded above by the entropy of former one.

The proposed method, the JES acquisition function, is also extended to the batch optimization setting. Specifically, the authors proposed a method in which the entropy of the joint distribution for the batch points is bounded from above by the sum of entropies for each point, and the latter is used to select each point independently.

In the experiments, the proposed method is compared with existing multiobjective Bayesian optimization methods for different optimization problems with 2-, 3-, and 4-objectives, using the difference of hypervolumes as an evaluation criteria.
strengths_and_weaknesses: Strengths

- The proposed new entropy-search type acquisition function, JES, considers the joint distribution of optimal position x^* and optimal value y^*, and is expected to provide more information about the optimal solution than PES, which considers only the former, or MES, which considers only the latter. 

- Different computation methods have been proposed for the entropy of the second term in JES, with and without noise. Both are derived in an analytic form, and the advantage is that costly numerical computations can be avoided.

- As a method for obtaining batch points, the joint conditional distribution for a batch is upper bounded by the sum of the conditional distributions for each point, avoiding the intractable computations of the former. With respect to the goodness of this upper bound, the authors show that by showing the submodularity of the acquisition function, an iterative method of sequential acquisition at each point achieves a regret upper bound of e^-1.

- While the hypervolume of the Pareto set (e.g., its expected reduction), which is often used as an acquisition function in multi-objective optimization, is not invariant with respect to monotonic transformations of the output, the proposed method, JES, is shown to be invariant to the same transformation.

Weakness

- The assumption is made in Lemma 1 that the true Pareto optimal value set Y^* is a finite set, which appears to be a strong condition given that in general there are an infinite number of Pareto solutions. 

- The computations of the conditional distribution for the Pareto set and the computations for acquiring batch points are each broken down into a computations for each point, which is expected to become a computationally expensive method when the number of elements in the Pareto solution set increases as iteration progresses.
questions: - As pointed out in Weakness, the assumption that Y^* is a finite set, as placed in Lemma 1, seems to be a strong one; it seems to be the key lemma for the approximate computation of the JES acquisition function, but is it not an issue?

- As pointed out in weakness, since the proposed method decomposes all computations into point-by-point computations, I think that it needs to be carefully evaluated in terms of computational cost compared to existing methods. Have you done any comparison of actual computational costs?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a new information gain acquisition function for multi-objective Bayesian optimization. The method selects the input that maximizes the joint information gain about both input and output space. The paper provides several approximations of the acquisition function using lower bound and assumptions about the observed variance. The method is extended to batch selection accompanied by a submodularity study. The paper provides an analysis of the sensitivity of the hypervolume performance metric to functions transformations. 
strengths_and_weaknesses: Strengths:
+ The paper is technically rich and provides an extensive study of the problem space with several approximations and derivations
+ The idea of the use of joint information gain is novel and interesting. 
+ The extension to batch setting seems naïve however, the discussion of submodularity of the acquisition function is interesting 
+ The paper provides a thorough cost analysis in terms of analytical complexity and wall clock time of optimization 

Weaknesses:
+ Some design choices made in the approximation are not justified and seem ad hoc, including the cancellation of variance effect in the first approximation and choice of noise in experiments. 
+ Many parts of the derivation in the main paper and the appendix are inspired by [50] and [68]. However, this does not seem to be properly acknowledged in the paper. 
+ The paper has a significant presentation issue. In general, the derivations are very hard to follow, both in the main paper and the appendix. This is not due to the extensive mathematical formulation of the acquisition function but rather to the lack of smoothness in the writing and the assumption that the reader can easily follow all the equations and substitutions. I provide more details in the questions box.   
+ The experimental setup has several weaknesses that I discuss more in detail in the questions and comments box
+ The writing of the paper assumes the reader is familiar with previous work on Information-theoretic acquisition functions, which is not necessarily true. Several steps of the algorithm are not described thoroughly and have confusing notations.
+ The paper uses “incorrect” acronyms to refer to previous work. This is problematic because the acronyms used in this paper are usually used to refer to different algorithms in SOO. For example, MES and PES are usually used to refer to a single objective acquisition function. In MO, they are referred to as PESMO and MESMO. The EHVI is usually used to refer to the sequential EHI method. The method discussed in this paper is the recently developed batch approach qEHVI and qNEHVI. 

questions: Approximations
+ How is the 0 variance assumption made, and what are the consequences of this on the selections made by the acquisition function? Canceling the effect of the predictive variances can lead to more exploitation in the acquisition function. It seems to be a little ad hoc just to add an additional term to cancel the variance effect. The transition is not explained well or justified. 

Writing and presentation: suggestions for readability enhancement: 
+ Several equations and inequalities are written in the text without any numbering and then used in the derivation without a referral. 
+ I suggest adding all the equalities/inequalities and definitions of variables used in separately numbered equations. I am aware of the space constraint, but several definitions can fit in one line, and white space reduction can also be used. 
+ Adding the propositions/lemmas written in the main paper near their corresponding proofs in the appendix would make it easier to follow the derivations. The reader won’t need to jump back and forth between the main paper and the appendix. 
+ The connections and substitutions used in the derivations should be detailed, at least in the appendix. 
+ f(x) <= Y* is a notation used repeatedly in the paper. However, the relation between two Pareto fronts is not always quantified as higher or equal and would depend on the tradeoff between several functions. A more rigorous notation should be used.  
+ The confusion between SO and MO surfaces in the names used for algorithms and in the notation used in the paper. For example, in algorithm 1, line 3 can be confused as a single objective sampling or sampling from a single multi-task GP while each of the objectives is sampled separately. 

Experiments: 
+ Only batch sizes of 1 and 8 are used. Typically batch BO papers include extensive experiments on different batch sizes
+ More synthetic experiments can be useful to show the behavior of the algorithm when the number of functions and number of dimensions is varied 
+ The noise choice for each experiment is different. How is this choice made? 
+ Figure 13 does not easily provide the needed information. It would be more informative to plot all the algorithms using the same number of samples in the same figure and have different figures for different numbers of samples 
+ Some relevant and important baselines were not cited or compared to:  Diversity-Guided Multi-Objective Bayesian Optimization With Batch Evaluations, Neurips 2020
+ The standard errors are not plotted. The use of quantiles is unconventional and do not substitute or provide the same interpretation as the error. A light-colored error plot can still be readable.
+  The performance improvement is minor, and the baselines sometimes work better. 
+ In the Penicillin experiment, the hypervolume progress seems unstable for all algorithms; what is causing the fluctuation, and how is this interpreted? 
+ Figure 1 provides an analysis based on single objective optimization, which does not necessarily hold in the multi-objective case. This figure is not discussed or analyzed anywhere in the text. The same issue applies to Figures 6, 7, and 10. I suggest removing these studies. They are not relevant, and they add to the confusion between SO and MO.
+ The discussion on the sensitivity of the hypervolume as a metric is insightful. However, it is important to note that it is a common practice to fit the Gaussian processes to normalized data, and therefore the scale issues between the objectives become less problematic. Additionally, several other distance-based metrics overcome some of the weaknesses of HV when comparing equivalent Pareto fronts. Therefore, evaluating the performance using more than one metric is encouraged.

Typos:
+ Typo in line 186 “because the cost of evaluating”
+ The structure of the sentence in line 176,177 is incorrect

limitations: The paper discussed some of the work's limitations.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work proposes a novel acquisition function JES for multi-objective Bayesian optimization based on the joint entropy of the optimal inputs and outputs. Previously works have studied input and output entropy independently. The work proposes novel entropy approximations—particularly one based on moment-matching, which has been previously used in the single objective setting but not the multi-objective setting. The work extends the proposed JES acquisition function to the batch setting using an additional approximation. In addition, this work analyzes potential for negative pathologies when using the hypervolume indicator for evaluation and proposes an alternative weighted hypervolume evaluation criterion.
strengths_and_weaknesses: Although this paper is largely well-written and provides precise detail on the empirical setup and evaluation, the contributions are limited. Multi-objective BO is an important but well-studied space. Hence, the work can, inherently, at best be incremental. Furthermore, entropy-based methods have been studied in multi-objective BO. The contributions of a novel joint input/output entropy acquisition function and a new multi-objective entropy approximation show improvement over previous ES methods, but these are small contributions that leverage well-studied ideas from the literature. Although JES approximations show good empirical performance, the evaluation is limited to evaluating the out-of-sample model predicted Pareto frontier. This evaluation technique favors and is well-suited to information theoretic methods, but as the paper states often time decision-makers would prefer to launch a previously evaluated design (regardless of whether this is observation noise). Therefore, it is not clear that JES approximations outperform alternative approaches such as DGEMO and NEHVI when the decision maker is only interested in choosing a final design at implementation time from the set of previously evaluated designs. Evaluation of the performance using this in-sample Pareto frontier (under the noiseless objectives) would help provide more clarity. Furthermore, the absense of error bars in the empirical evaluation makes it impossible to determine which differences in performance are statistically significant. Moreover, the paper does not propose one single JES approximation to use. There are numerous JES methods and many confusing acronyms, and the empirical evaluation does not obviously indicate a single best JES method (even based on the mean performance, without accounting for uncertainty). In addition, JES is computationally intensive and is slower than even EHVI-based methods---which are known to be computationally demanding.

The additional contributions of an analysis of the HV indicator and the proposed weighted HV metric are a bit orthogonal to the new JES method and feel out of place with the rest of the paper, which focuses on JES. It seems like the weighted HV metric should be de-emphasized in the main text (specifically, the contributions), since it is not actually used in the main text and it is unclear what distribution is appropriate for sampling scalarization weights. The weighted HV and HV analysis are not JES specific, but is a general comment on multi-objective optimization that is out-of-place with the JES-focus of the paper.

It is worth noting that code is provided and well-documented. This is particularly notable because PES is known to be difficult to implement and most BO papers leverage an old Spearmint implementation with now unsupported dependencies. A high-quality PES implementation is of value to the community.

On a whole, a) the contributions are scattered (results on JES, results on ES methods handling monotonic transformations, an analysis of using HV for evaluating multi-objective optimization algorithms), b) the JES-specific contributions are incremental (a new joint entropy and a new application of an approximation techniques from the single objective setting), and c) the empirical evaluation is difficult to interpret (which JES method is best/should be used, what does performance look like if only in-sample---rather than out-of-sample---designs can be used in the Pareto frontier) and lacks measures of statistical significance.
questions: * How well does the constrained version work empirically?
* How robust is the performance to the noise level?  
* The JES approach seems quite incremental. 
  * The input entropy and output entropy are well-studied
  * The moment-matching approximation is well-studied in the single objective case [50]
  * The box decomposition-based entropy computation is proposed in [68]
  * Lemma 1 is not novel. It comes directly from [68]  and is used in [68] which should be made more prominent
  * The whole JES computation algorithm is an incarnation of BAX with a different acquisition function than PES and a different approximation method.
* JES does not support modeling correlated outcomes---independent GPs models are assumed to be used. Why then distinguish equations (10) and (11)? Also, Why does Figure 3 show correlation between outcomes? Aren’t the covariances matrices across outcomes for a single point always diagonal under the assumption of the independent GP models?
* The batch extension follows [50] and is “suboptimal” (L193) and approximates the joint JES across a batch of points with the sum of the independent entropies of each point. Why would the best batch of `q` points not be the same point `q` times using this acquisition function?
  * Also, sequential greedy batch selection is common practice. While the submodularity proof is neat, it applies to 1) approximating true batch JES with sequential greedy or 2) approximating the coarse approximation (sum of independent entropy) of batch JES with sequential greedy. It makes no guarantees about how well the coarse approximation (12) approximates batch JES (or some approximate version of JES without the batch independent entropy approximation (12)). This error seems like it could be quite large.
  * How does JES scale with increasing batch size both in terms of wall time and in terms of optimization performance? It is hard to draw conclusions from q=1 and q=8 alone.
* Why does this paper focus on multi-objective JES and not a single objective JES?
* Being invariant to component-wise monotonic transformations of the objectives is a nice property of entropy-based methods (prop 4). But this is not specific to JES, and therefore seems a bit odd to include.
* Page 7 footnote: “The reference point is typically chosen to be the nadir…”. Typically the reference point is typically chosen to be *slightly worse* than the nadir of the *Pareto frontier*, *not the entire objective space* as stated in the footnote. Using the nadir of entire objective space (as described) would often be a poor choice of reference point because it would be very far from the pareto frontier. Was this strategy used for evaluation purposes (hypervolume computation) in the experiments? Also using the nadir of the Pareto frontier directly would be a poor choice because it gives zero hypervolume to the end points, which is why the reference point is typically chosen to be slightly worse than the nadir (see Ishibuchi et al., 2011).
  * L954/983: using a nadir over all observed points as the reference point is also is likely a poor choice for solving the MOOP problem for recommendation and for use in NEHVI and EHVI. A point that is slightly worse than the nadir point over the pareto frontier across the observed designs is likely a much better choice because it 1) will ensure that it is not very far from the current pareto frontier, which could be the case with using the nadir across all observed points and 2) gives non-zero hypervolume to the endpoints of the pareto frontier and beyond the endpoints, which is likely very important for discovering designs outside of the currently observed Pareto frontier with EHVI/NEHVI. 
  * It is very hard to distinguish the trend lines in Figure 5. I would recommend focusing on one JES method. This would also help the reader understand which JES method is best and should be used. Currently, this is very hard to parse. The colors for TSEMO and LB-JES-0 are very similar.
  * Also, can you provide error bars please? Currently, it is not clear which differences in performance are statistically significant
* How does the performance look on noiseless problems?
* L288: Regarding being able to specify a preferred region (via the reference point) with hypervolume-based methods, this seems like a positive. It seems like a major drawback of entropy-based methods to only be able to identify the entire Pareto frontier and not just an area of interest.
* For problems such as the ZDT family, the optimal designs lie in a small region of design space. This means that the heuristic for selecting the initial points for gradient-based acquisition optimization is particularly important for improvement-based acquisition functions since they can be 0 over a large portion of the design space. In L903, the paper says that initial points were not sampled near the Pareto frontier, which would have led to faster convergence for entropy-methods. I think it would be even more important for improvement-based methods. Can you provide empirical results were the initialization heuristic does sample points near the current best (pareto optimal) for acquisition optimization?

Minor comments

L24: “trade-off” -> “trade-offs”

L31: “might suffer when the scale of the objectives is unknown apriori”. A common approach is simply to rescale the objectives to the unit cube based on the observed outcomes

L32: “or when the input space is high-dimensional”. Wouldn’t high-dimensional output spaces be more problematic for random scalarizations? 

L50: “analytically available, which enables the use of gradient-based optimization”. It is not clear here why analytic availability implies differentiable

L73: should be \subseteq instead of \subset

L196: These acronyms are very confusing

L298: it would be good to clarify that “multi-objective optimization” refers to the fact that computing JES requires solving a set of multi-objective optimization problems of optimizing GP function samples.

limitations: Some limitations are discussed in the last section, but further discussion around when to use which method would be useful. Additionally, characterizing drawbacks of the approach and sensitivity of the approach and entropy-based methods more generally to model-specification would be useful. Negative societal impacts are not discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: A new acquisition function for Bayesian Optimization (JES) is proposed in this paper. It considers the joint information gain for the optimal set of X and Y.  Several analytical approximations to the acquisition function are also introduced.
strengths_and_weaknesses: Strength: A new information-theoretic acquisition function for Bayesian Optimization is presented, and approximation methods are also discussed and analyzed in this paper.

Weakness: It is not quite clear why this new method is superior to the existing methods (for example PES and MES as mentioned in the paper) with respect to its cost-performance trade-off.
questions: - It is not quite clear from the paper why this new method is superior to the existing methods (for example PES and MES as mentioned in the paper) with respect to its cost-performance trade-off. The amount of work involved in using this new acquisition function may be large, especially compared to MES. 
- Maybe it is good to identify certain specific settings or scenarios where this joint information gain acquisition function has an advantage over both PES and MES. 
- For motivation and illustration purposes, maybe in the introduction, some small examples on a small instance can be worked out where this new method can be easily compared with PES and MES. In this way, this method can be better motivated.
- The approximation methods can achieve different accuracy levels using a different number of samples, if possible, some discussion or guidance on that will be helpful in that section.
limitations: Not applicable.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a new information-based acquisition function for multi-objective Bayesian optimization that combines the approaches from the known PES and MES acquisition functions. The authors derive various approximations to efficiently compute this acquisition function and provide a comparison of their performance characteristics against a number of baselines.

strengths_and_weaknesses: # Strengths:
- The paper is well written, in particular Section 2 provides a nice buildup of background to understand JES in relation to (P)ES and MES.
- The motivation for studying the new acquisition function and the theoretical contributions (in terms of JES and the various approximations) are solid; I view them primarily as well crafted technical work on top of a large body of existing literature in the field rather than a surprising or particularly novel set of contributions (which is not a bad thing).
- The main strength of the paper beyond this solid execution is that it provides a comprehensive comparison and ablation studies of various state-of-the art acquisition functions.
- The authors also provide a full implementation of the methods in a popular and maintained python library for Bayesian Optimization. This in itself is a significant contribution to the community, which can now easily use not just JES but also the other implemented baselines (without trying to get an unmaintained library such as spearmint running in a modern software environment...).
- Pointing out the potential issues with HV w.r.t. rescaling objectives is valuable, and the fact that JES is invariant to that is nice and useful (though not surprising as one would expect that from an information-based acquisition function).
- The supplementary material is very comprehensive and goes into lots of detail. This is very useful to the reader. For instance, I found the illustrations of the acquisition function in the contour plots instructive.

# Weaknesses:
- One shortcoming of the work is this that there aren't any variance estimates of the performance of the different algorithms in the empirical evaluation. The checklist states that "We do not include the error bars directly on the plots because it made it difficult to visually compare between the different algorithms.", but as a reader I would have hoped to see a more thorough analysis of this in the supplementary material. The quantile versions of the plots are useful to some extent, and by comparing the performance of the suggested methods across the detailed results of the benchmarks the reader can get a sense that the proposed algorithms may indeed improve over existing methods. However, this is a lot of work to require from the reader, and I would ask the authors to add a more comprehensive discussion to help practitioners understand in which the proposed methods are most useful and computationally feasible.
- The information gain estimates rely crucially on the assumption that the different objective functions are modeled by independent GPs. If the objectives are correlated, then this assumption could result in poor performance. Other approaches, such as Monte-Carlo based EHVI methods are not subject to these limitations since their methodology applies in the same fashion to multi-output GPs. In fact, as they are based on MC sampling from the model's posterior, such methods are also compatible with other probabilistic models, which is not the case for the approach proposed in this paper.
- Overall, I found the experimental section of the paper in the main text too brief to be able to get a good sense for the empirical performance of the JES approach in comparison to the baselines (both in terms of sample efficiency and computational footprint). I would suggest the authors move some of the mathy and notation-heavy details of Section 3  (e.g. Proposition 3) to the appendix, potentially streamline the exposition in other parts of the paper, and include additional results / discussion of the empirical performance in the main text.
questions: - l34: " The main drawback of these approaches is that the performance of these methods are biased towards a single scalar utility criterion, which can be inadequate to assess the multi-objective aspects of the problem". I don't really understand this point; after all, the scalar utility is defined specifically in order to capture the multi-objective aspects. In a sense your formulation is no different in that ultimately you optimize a scalar function, the information gain. Can you please clarify?
- l38: This sentence makes it seem as if other papers do not consider a "probabilistic perspective", which of course they do (this is BO after all).
- l156: what does "cancelling out" mean here? JES is computed on the covariance using the augmented set of observations so there shouldn't be any cancelling in the strict sense. Please clarify.

Nits / Typos:
- l28/29: it enables -> they enable
- l47: set-up -> set up
- l89: "and a property of the probabilistic model." <- not sure what is meant by this, please clarify

limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a novel information-theoretic acquisition function for BO called Joint Entropy Search (JES), which considers the joint information gain for the optimal set of inputs and outputs. The authors present several analytical approximations to the JES acquisition function and also introduce an extension to the batch setting. The authors show the effectiveness of this new approach on a range of synthetic and real-world problems in terms of the hypervolume and its weighted variants
strengths_and_weaknesses: Strength 1, it identifies the problem of predictive entropy search (PES) method, i.e., the acquisition function is heavily dependent on the approximation of p(y|x, Dn, X∗),  which is difficult to implement and optimize. Besides, it also shows that the max-value entropy search (MES) method, though comes with closed-form expressions, does not directly dealing with the maximum Y∗. JES combines the advantages of both methods.

Strength 2, it gives several theoretic property of the JES function, with in-depth study.

Strength 3, the experiments are very detail, and have a good overall design. 
questions: No
limitations:  the authors adequately addressed the limitations of their work. i.e., the computational complexity of JES.
review_title: null

Meta-review: metareview: The authors propose an entropy search method for multi-objective Bayesian optimization that considers the mutual information gain of the location and value of the optimizer simultaneously while selecting query points.  Most reviewers found the approach to be interesting.  The work is commendable in its attempt to rigorously compare different information-based acquisition functions via high-quality re-implementations of algorithms (e.g., PESMO).  Many reviewers left detailed comments that the authors addressed in part, or agreed to examine in the camera ready.  Examples include more rigorous examination of the performance with respect to noise and batch size, inferential statistics for the experiments, and transparent reporting on the strengths and weaknesses relative to the existing literature.
confidence: Certain
Decision: Accept