Venue: NeurIPS 2022 Conference

Reviews:

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: In this paper, the authors propose a Bayesian optimization method for black-box optimization problems using a new entropy search-type acquisition function that combines the advantages of predictive entropy search and max-value entropy search. The proposed method, joint entropy search (JES),  uses the mutual information between the optimal solution/optimal value pair (x^*, f^*) and the candidate query points (x, y) as the acquisition function. JES, like other entropy search acquisition functions, is expressed as the difference of two differential entropy terms. The main difference from other entropy search is that the second term takes the expected value of entropy with respect to the optimal pair (x^*, f^*). 

To compute this expectation with MC sampling, a parametric model representation of the kernel function is obtained using Bochner's theorem. By sampling its parameters, a sample path from the GP is obtained in the form of a basis function model, whose maximum solution and maximum value are estimates of x^* and f^*, respectively. In particular, the distribution of f conditioned on the maximum f^* is a truncated normal distribution and is approximated by moment matching. Like other entropy search type acquisition functions, JES can be greatly affected by model misspecification. Hence, in the proposed algorithm, the inverse gamma greedy method is used to ensure that the JES search and the search using the predictive mean as the acquisition function are executed with a certain probability each, so that the effect of model misspecification does not remain until later. 

In the experiments, the authors first explained the difference in behavior between JES and PES or MES through optimization of the benchmark function, and showed experimental results suggesting that JES is effective. The practical performance of JES compared to PES and MES was also evaluated by the MLP hyperparameter optimization task.
strengths_and_weaknesses: Strength

- In the entropy search acquisition function, using the optimal solution x^* and the optimal value f^* simultaneously as conditions is expected to increase the "amount of information" available for the search compared to PES and MES, which consider only one of each.

- The inverse gamma greedy method is proposed to mitigate the influence of model misspecification, which is a property of all entropy search type acquisition functions including PES and MES. Although this idea is a heuristic, it is considered to be a general-purpose method that can be applied to other entropy-search type acquisition functions.

- Experiments suggest that JES is more robust to observation noise than PES or MES. This has important implications for problems involving measurement errors of various magnitudes, such as medical research or materials science.

Weakness

see Questions
questions: - (weakness) Interpretation of the inverse gamma greedy method is difficult. In terms of mitigating the effects of model misspecification, it seems to me that acquisition by predictive variance that represents "exploration" is better than acquisition by predictive mean that represents "exploitation". Could you explain in detail that why does the latter mitigate the problem?

- Is the \gamma of the inverse \gamma greedy method a fixed value? Or does it require appropriate scheduling like \varepsilon in the \varepsilon-greedy method?

- (weakness) In the real task (MLP hyperparameter optimization), I am concerned that the performance of JES (that is considered robust to noisy observations) is not so different from that of MES in terms of accuracy relative to the number of observation points. I think that the robustness of JES should be verified in more detail with artificial data that controls the amount (and/or structures) of noise.
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper proposes a variant of entropy search for Bayesian optimization, which considers joint entropy of the optimal solution x* and the optimal value f*. The approximation for the entropy and the treatment of observation noise are mainly discussed. Further, a heuristics for model misspecification is also introduced. The performance is evaluated on GP prior functions, well-known benchmark functions, and an MLP optimization.
strengths_and_weaknesses: The paper proposes another variant of entropy search. 

+ The intuition behind the basic idea is simple.
+ A variety of empirical evaluations are provided. 

However, throughout the paper, the technical descriptions are fully misleading and inaccurate. The authors sometimes ignore techniques in the past work (nevertheless it is cited), which unfairly exaggerates own contributions. Many inaccurate descriptions hide approximations of the entropy computations in the proposed method, by which readers can misunderstand that the proposed method performs more accurate computations than it actually performs. Detailed comments are as follows.

- Although the authors implicitly assumes conventional MES is only for noiseless, it is not the case. [22] and [39] have already shown how to incorporate the additive noise. Note that although [39] is for multi-fidelity optimization, it contains the usual single-fidelity setting as a special case (For the detail of the noise treatment, I'll mention later again). Therefore, the description of the third main advantage listed in the end of introduction is misleading because readers would think that other information approaches cannot handle the observation noise. However, the observation noise can be handled by the above literature, and further, PES [15] can also incorporate the additive observation noise.

- From (8) to (9), p(y|D,x,x*,f*) is re-written as p(y|D U (x*,f*),x,f*). After that, in Section 3.4 (which describes the computations of the entropy of p(y|D U (x*,f*),x,f*))), it is further re-written as p(y|D,f*). This re-writing hides the fact that the original p(y|D,x,x*,f*) contains a condition that 'x* is the maximizer'. For example, in the case of PES [15], a condition that the hessian of x* should be negative definite is considered. This condition is implicitly ignored by the proposed method (without mentioning anything about this approximation), and the notation p(y|D,f*) makes difficult to be aware of that fact. 

- The proposed method incorporates (x*,f*) into GP to calculate p(y|D,f*), but f(x) <= f* is only (approximately) imposed for the current queried x. Note that f(x) for other x in \cal{X} is not constrained in the proposed method (though f(x) <= f* is originally imposed on all x). Similar approximations have been employed by past works, but in the paper, this approximation is implicitly introduced, by which readers can mistakenly consider that the calculation in the proposed method is exact computations unlike previous ones.

- About MES, the authors described that MES considers y* = f(x*) + \epsilon (according to the descriptions after (6)). However, this is not the case. In the original MES paper [43], y* is defined as f(x*) (noise is not included in y*). Therefore, although the authors claim the replacement y* with f* is one of differences from MES after (9), it is also misleading. 

- About MES, in line 103-104, the authors described

> p(y|D, x, y∗) is a truncated Gaussian distribution, for which the entropy can be computed in closed form. However, p(y|D, x, y∗) takes this form only in a strictly noiseless setting

This statement is weird because p(y|D, x, y∗) is not a truncated Gaussian distribution even when noiseless case. This is an approximation. In the noiseless case, the predictive distribution given the optimal value is at least should satisfy [C1] f(x) < y* for 'ALL' x and [C2] there exists x such that f(x) = f*. Note that here I assume the condition on x* is already omitted (e.g., the hessian condition) as I already mentioned. The predictive distribution under these condition is not a simple truncated Gaussian distribution anymore. More importantly, about this particular issue, the paper does not provide any novel treatment compared with existing studies. Although the authors seems claim novelty about the noise treatment, the noisy case also has been discussed in the past work (e.g., [15,22,39]). 

- In line 142-143, the author described

> after conditioning on f∗, the posterior predictive density over y is a sum of a truncated Gaussian distribution over f and the Gaussian noise \epsilon

Related to the above comments, this description is also wrong and misleading. As already mentioned, the conditioning on f* is more complicated. It is not a simple sum of truncated Gaussian and the noise Gaussian, which is just an approximation (note that [26] explicitly declared they use an approximation which simplifies [C1] to a condition only on input query throughout the paper (though [C2] is implicitly omitted)). 

- In line 183, the author described

> conditioning on f∗ yields a truncated normal distribution p(f|D, f∗), but the entropy is computed with regard to the density over noisy observations, y = f + \epsilon, which leads to an intractable entropy.

Under the replacement [C1, C2] to 'f(x) <= f* only for current input x' (the authors (implicitly) employs the almost same simplification), the computation of entropy of p(y | D, f*) is shown by [39] (Appendix C), in which f* is noiseless and y is additive noise contaminated. It is shown that the computation is tractable.

- Section 3.5 has no relation with the information theoretic approach. Further, I do not agree with selecting the argmax of the posterior mean mitigates the model misspecification issue. Using the posterior mean can be seen as fully exploiting the current model knowledge, and thus, it can be even risky if the model is misspecified. A rational that inverse-\gamma-greedy approach is not fully clear to me. 

- Figure 1 is misleading and difficult to interpret. It misleads that JES identifies the correct maximizer of f(x), but at the moment, GP does not accurately predict the true function around the maximizer. As indicated by p(x*|D) in the figure, currently, around the maximizer of PES has the highest probability density having the maximizer. Therefore, the maximizer of a sample path from GP should have the largest value around the maximizer of PES with much higher probability around the maximizer of JES. In this sense, f(x) of Figure 1 (black line) shows a rare case which is convenient for the authors. Further, for me, the suggestions of next querying by all of the three acquisition functions in the plot are reasonable. It is difficult to judge which one is most appropriate from this figure.

- The information I((x,y),(x*,f*)) is obviously difficult to evaluate than PES and MES (because the dimension of the entropy is higher). On the other hand, the approximation employed by the proposed method is a naive moment matching, which would be a stronger approximation than the computational approaches taken in those past works (PES employs the expectation propagation, and MES evaluates the entropy of the truncated Gaussian without using moment matching (for which [39] shows noisy case as well)). 

- Rationale for considering joint entropy of (x*,f*) is not fully clear to me. The purpose of a black-box optimization problem in general is to find x* = argmax f(x). Then, considering entropy p(x*) is quite natural. The Vapnik's principle says that you should not solve a problem more general than the problem of interest. In this sense, I consider that minimizing the entropy of p(x*,f*) can be more difficult than identifying x* only. 

- The authors describe when JES is applied to a noiseless case, it has the infinite information gain at the sampled optimal point. I guess this phenomenon would be an artifact caused by approximations the authors (sometimes implicitly) introduced. I even think this phenomenon is intriguing and worth studying, rather than simply avoiding it by adding the noise term.

==================================================
 Post-rebuttal 
==================================================

Thank you for providing many replies (and sorry that I could not reply during the feedback period). However, overall, I am not convinced by many of the responses. 

<1> Novelty about noise treatment 

Thank you for reflecting the comment. Since the authors explicitly cited the past works that deal with the observation noise in the original version, for me, it is quite surprising that the authors claimed novelty about the noise treatment, which is obviously not novel (To be honest, this degraded reliability of the paper).

<2> Misunderstanding about incorporation of f* globally

From the response, I consider that the authors have a fundamental misunderstanding about the discussion of the global truncation by f*.

I'd like to first note that the fact that p(f(x) | D, f*) is NOT a truncated normal distribution. This is an approximation. To confirm it, let me review the derivation of the predictive distribution of GPR. To simplify the discussion, I consider the noiseless setting (even in the noisy case, essential discussion is same).

In the usual (non-truncated) GP derivation, a predictive distribution p(f(x) | D) for a specific x is derived by (implicitly) marginalizing all other x' in the domain, which is possible because f(x) is jointly Gaussian for any x (sometimes called marginalization property).

On the other hand, in p(f(x) | D, f*), this marginalization becomes difficult, because the marginalization must be performed with a distribution in which f(x) is truncated for \forall x (given f*, f(x) \leq f* should hold for \forall x). In general, it is known that a marginal distribution of multivariate truncated Gaussian is not a truncated Gaussian (e.g., see Horrace 2005). 

In this sense, representing p(f(x) | D, f*) as a truncated Gaussian is a local truncation-based approximation (in other words, marginalization is performed WITHOUT truncating other f(x') (x' \neq x)). Please note that what the authors claimed 'global' just means applying this local approximation for all candidate x when it is queried (i.e., it is not the global truncation in the sense described here). 

The entire paper is seemingly written on the premise of this misunderstanding. For example, discussion in Sec3.2 implicitly assumes p(f(x) | D, f*) is a truncated Gaussian. Further, the discussion of '2. Dsregarding x* as optimumu' in the response, i.e., the Lipschitz based justification, is not correct (because except for the current queried x, f(x) is not truncated). Some other responses about truncated Gaussian would also be related.

Many information theoretic existing studies have employed this local approximations. For example, papers of Rectified MES [26] and PES [36] clearly explained about the local truncation, though the authors ignore it even after I pointed out in the first review. Similar to <1> above, here again, this makes me feel that the authors might not carefully read past works.

W. C. Horrace, Some results on the multivariate truncated normal distribution, Journal of Multivariate Analysis, 2005

<3> JES with a noiseless model 

Although the author explains noiseless JES has the infinite information gain because p(y | D U (x*,f*),x,f*) is deterministic at x*, this rather suggests the difficulty of dealing with joint information gain of (x*,f*) appropriately. It makes the finite sample MC approximation of the expectation in (11) difficult, and obviously, just adding the observation noise is not an essential remedy. Further, the authors mentioned when L points exists (the number of optimal point samplings), noiseless JES becomes Thompson sampling (TS) (i.e., sampling from p(x*)) by using a simple heuristics. This also makes justification as a mutual information (MI) approximation unclear, because it seemingly indicates that the quantity cannot be interpreted as an MI approximation even with a large L. 

<4> Existing studies for truncation by f* in the noisy setting (y is not truncated)

> Regarding the tractability of the computation: As the reviewer may agree on, we are after Eq. (24) in [39], Appendix C. Below Eq. (24), it is clearly stated that
> > The integral in (24) can be calculated by using numerical integration in the same way as (6).
>
> which indicates that the computation is not tractable, but needs approximation.

I'd have say that this reply is quite misleading. [39] intends that it is computationally tractable (though of-course it is analytically intractable). Their acquisition function actually performs the same type of numerical integration in the multi-fidelity setting, in which the highest fidelity is truncated but lower fidelity is not truncated (note that 1d numerical integration is often computationally easy), which is technically almost same as f(x) is truncated but y is not truncated also shown by the same paper. For me, this also seems that the authors might not pay sufficient attention to past works.
questions: In the experiment, what does 'end of the initial design' mean? Why is performance of each method is different at that point? (e.g., in Fig 5 and 7)
limitations: The limitations are show in Section 6.
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: The main idea of the proposed acquisition function in this work is to consider the information gain between evaluation point and both the optimum x* and optimal value f* of the black-box function; in some sense combining PES and MES that was proposed in the past. The new acquisition function samples functions from the posterior GP and optimize each one to obtain samples of x* and f*, which does not use more computational cost comparing to PES. 
strengths_and_weaknesses: Strengths:
- This is a clever idea to combine MES and PES, given that the Thompson sampling step will produce both x* and f*. PES only uses x* and MES only uses f*. Using both will in fact incorporate more information.
- The clarity of this work is very good. The motivation and most steps of the method are explained very well.
- Another interesting point is the inverse \gamma greedy approach. It's a simple and nice addon that can be used for all entropy search methods, whose goals are not evaluating the optima. 

Weaknesses / suggestions
- The most critical component of the proposed acquisition function is the computation of \sigma_{f|f*} but the main paper doesn't seem to talk about how it is computed. I think this results in a loss of main contribution of this work and would suggest focusing on how this quantity is computed in the main paper.
- This work might have some issues if f has multiple optima since it ignores regions of good x* from the same sampled function, which could be the problem of PES too. Also note that optimizing sampled functions in the Thompson sampling step might lead to suboptimal x* and f* depending on how good the global optimizer is. This will also lead to potential stability issues of the proposed method.
- While the method is very interesting, it also feels like an incremental step from PES and MES. The empirical gains on realistic tasks in section 4.3 doesn't really show much improvement comparing to baselines. Neither is there theoretical gains comparing to past methods. This problem is not easy to resolve. The next comment may shed some lights on this.
- The inverse \gamma greedy approach feels more like a heuristic in the current presentation. I think it's possible to further improve the presentation by analyzing why this approach is needed in entropy search methods. I think Figure 9 is a nice way towards better understanding. Some theoretical insights will also help this approach to be more principled, e.g. how to select \gamma. I think the authors can benefit a lot from making this greedy selection a highlight of this work (once we have some principled analysis). Doing so will also avoid criticisms on being too incremental.
questions: How much of the empirical gains of JES is because of the greedy selection approach in section 3.5? What does the comparison to baselines look like if JES does not use \gamma? Does using \gamma values still help if there's no model misspecification?

Optimizing sampled functions in the inner loop Thompson sampling step might lead to suboptimal x* and f*, especially for high dimensional functions. How much does this inner loop optimization matter to JES? Do we have any comparisons on different inner loop optimizers to show the sensitivity?
limitations: The authors mentioned model misspecification and lack of analysis on high dimensionality, multi fidelity etc as limitations. 

I think some more important limitations that don't seem to be mentioned is the stability of the method which depends on good inner loop optimization, good selection of \gamma, approximation errors and lack of theoretical guarantees. I think those need to be addressed in this work more systematically.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose Joint Entropy Search (JES), an acquisition strategy for Bayesian optimization (BO) that combines ideas from entropy search and max-value entropy search while retaining low computational complexity. As ingredients for this approach, the authors require a sampling scheme for potential candidates of optimum/optimal value pairs (i.e., f* and x* at which f*=f(x*)) and a method to compute the entropy of a truncated distribution. They also propose a scheme that prevents stalling in case the surrogate model is misspecified. The method is shown to outperform previously proposed information-theoretic acquisition strategies for BO.
strengths_and_weaknesses: The paper is well-written. The pictorial illustration of the method is exemplary and illuminating. The experimental evidence is convincing. The only possible critique I see is that the approach itself appears to be obvious and incremental, being a combination of existing approaches. On the other hand, the authors successfully show that their combination of techniques not only improves performance, but also reduces the computational complexity compared to existing approaches (ES and PES). This critique is, therefore, not a major weakness and I am very much in favor of the manuscript.

My only substantial suggestion is to accompany the theoretical section with a few explanations on why JES has the potential to outperform ES/PES/MES. For example, it is claimed that MES relies on the noiseless setting; what ingredients make JES robust in the noisy setting, then? Also, PES is said to be computationally expensive; why can't the computational approach of JES be utilized to reduce the computational complexity of PES (e.g., extending lines 177-181)?

I see a few minor weaknesses that can easily be resolved by answering the questions below. The following minor comments may help to further improve the quality of the manuscript:
- l21: "modeling the unknown objective". Should "objective" be replaced by "black-box function"? I would expect that not the objective is modeled by the surrogate, but the black box.
- l28: space missing around "PES"; also please check consistent typesetting of ES and PES.
- l79: "employ": in my understanding, acquisition functions do not employ, but rather define this trade-off.
- eq. (3): $y^*_{n+1}$ should be replaced by $y$, or even better by $f(x)$, since we assume a noiseless function.
- The usage of (1) and (2) in lines 130-136 is slightly confusing, as I was briefly looking for the presumably referenced equations.
- Algorithm 1: lin 5 uses $\mu$ and $s^2$, while I assume the correct notation would be $m_n$ and $s_n$; in line 10, $y^*_\ell$ should be replaced by $f^*_\ell$; in line 13, the subscript $JES$ should be in typewriter font.
- l242 claims that "half an order of magnitude" is gained except for 12D, while Fig. 5 suggests that this also does not happen for 6D.
questions: 1) How are (4) and (5) equivalent? The mutual information terms are clearly different.
2) More generally, in (4)-(6) it is not fully clear what objects are random and what are deterministic, i.e., instances. E.g., in (4) the term $I((x,y);x^*|\mathcal{D})$ suggests, in a strong information-theoretic understanding, that all objects are random. I assume, however, that $\mathcal{D}$ and $x$ are instances or fixed constants, while $y$ and $x^*$ are random. ($y$ being the random output associated with the fixed input $x$.) This ambiguity, which is due to the common abuse of notation, makes these equations a bit difficult to parse.
3) In line 101 the mutual information objective of MES differs from the one in (6). Which is correct?
4) In (10), the argument of the first expectation appears to be independent of $b$, while the argument of the second clearly is; how can this be reconciled?
5) The entropy of a truncated normal distribution is not much more complicated than the entropy of a normal distribution. For the sake of clarity, I would suggest to apply moment matching not to the truncated Gaussian distribution, but to the sum $y=f+\epsilon$. The final result is the same, but this way the approximation is applied to the object that has no tractable entropy, rather than to the object that has.
6) In Algorithm 1, what is the meaning of $y_n=f(x_n)+\epsilon$? Does that mean that a random $y_n$ is sampled?
7) In the noisy setting in Fig. 6, why is PES slowing down together with MES? The noise-free assumption is inherent in MES, but it is less clear what the impact of noise is on PES. A few lines of text would clarify that, which would also explain the suboptimal performance of PES in Fig. 8.
8) In the experiments, ES was not used as a competing method. I assume that this is related to the fact that usually higher-dimensional entropies need to be evaluated than for PES. Nevertheless, it would be interesting to hear the authors opinion on what they believe would be the performance of ES.
limitations: The authors acknowledge the limitations of their approach (performance under model misspecification and the requirement of a noisy surrogate model).
review_title: null

Meta-review: metareview: The authors propose a Bayesian optimization method for black-box optimization problems using a new entropy search-type acquisition function that combines the advantages of predictive entropy search and max-value entropy search. The proposed method, joint entropy search (JES), uses the mutual information between the optimal solution/optimal value pair (x^*, f^*) and the candidate query points (x, y) as the acquisition function. In the experiments, the authors first explained the difference in behavior between JES and the baselines PES or MES through optimization of the benchmark function, and showed experimental results suggesting that JES is effective. The practical performance of JES compared to PES and MES was also evaluated by the MLP hyperparameter optimization task.

Strengths:

1 - The intuition behind the basic idea is simple.
2 - A variety of empirical evaluations are provided.
3 - The inverse gamma greedy method is proposed to mitigate the influence of model misspecification, which is a property of all entropy search type acquisition functions including PES and MES. 
4 - Experiments suggest that JES is more robust to observation noise than PES or MES.

Weaknesses:

1 - While the method is very interesting, it also feels like an incremental step from PES and MES.
2 - As pointed out by reviewer 7H23, the authors incorrectly state that conditioning on f* yields a truncated Gaussian predictive distribution. Reviewer 7H23 correctly states that "it is known that a marginal distribution of multivariate truncated Gaussian is not a truncated Gaussian". The authors should revise the paper to indicate that they make the additional approximation that conditioning on f* yields a truncated Gaussian predictive distribution.

Decision:

A majority of reviewers are strongly positive about the paper. The only negative reviewer, 7H23, points out minor limitations, with the exception of the mistake made by the authors, as described in point 2 in the list of weaknesses above. The authors need to update the paper to clarify that they make the additional approximation that conditioning on f* yields a truncated Gaussian predictive distribution.
confidence: Certain
Decision: Accept