Joint Entropy Search For Maximally-Informed Bayesian Optimization
Authors: Carl Hvarfner
Frank Hutter
Luigi Nardi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian Optimization
Entropy Search
Hyperparameter Optimization
AutoML

Abstract: Information-theoretic Bayesian optimization techniques have become popular for optimizing expensive-to-evaluate black-box functions due to their non-myopic qualities. Entropy Search and Predictive Entropy Search both consider the entropy over the optimum in the input space, while the recent Max-value Entropy Search considers the entropy over the optimal value in the output space. We propose Joint Entropy Search (JES), a novel information-theoretic acquisition function that considers an entirely new quantity, namely the entropy over the joint optimal probability density over both input and output space. To incorporate this information, we consider the reduction in entropy from conditioning on fantasized optimal input/output pairs. The resulting approach primarily relies on standard GP machinery and  removes complex approximations typically associated with information-theoretic methods. With minimal computational overhead, JES shows superior decision-making, and yields state-of-the-art performance for information-theoretic approaches across a wide suite of tasks. As a light-weight approach with superior results, JES provides a new go-to acquisition function for Bayesian optimization. 

Joint Entropy Search for Maximally-nfoomeed Bayesian Optimization
Carl Hvarfner carl. www.waaffa frrarfnercc..o 1tt.. se Lund University
Frank Hutter
fhecs uni uni-freiburg de
University of Freiburg
Bosch Center for Artificial Intelligence
Luigi Nardi
luigi. www.iarddee..ooo lt Lund University
Stanford University DBtune
Abstract
Information ciemmattoo--thoretic Bayesian optimization techniques have become popular for black-box functions due their non-myopic qual- ities. Entropy Search and Predictive Entropy Search both consider the entropy over the optimum in the input space, while the recent Max-value Entropy Search consid- ers the entropy over the optimal value in the output space. We propose Joint Entropy Search (JES), a novel information-theoreti acquisition function that considers an entirely new quantity, namely the entropy over the joint optimal probability density over both input and output space. To incorporate this information, we consider the reduction in entropy from conditioning fantasized optimal input/output pairs. The resulting approach primarily relies on standard GP machinery and removes complex approximations typically associated with information -thhorettic methods. With minimal computational overhead, JES shows superior decision- macksion-making, and yields state-of-the-an performance for inoommation-thereee wide suite of tasks. As a light-weight approach with superior results, JES provides new go-to acquisition function for Bayesian optimization.
optimizing axpensive-to-evaluneee
approaches across
Introduction
The optimization of expensive black-box functions is prominent task, arising across wide range of applications. Bayesian optimization (BO) 25 35 is a sample-efficient approach, and has been successfully applied to various problems, including machine learning hyperparameter optimization [2]
20 33 37, robotics 3
23 24 hardware design I 27], and tuning reinforcement learning agents like AlphaGo 77. In BO. probabilistic surrogate model is used for modeling the (unknown) objective. The selection policy employed by the BO algorithm is dictated by an acquisition function, which draws on the uncertainty of the surrogate guide the selection of the next query.
6
The choice of acquisition function is significant for the success the BO algorithm. A popular line of acquisition functions takes an cotrmatiionthhoredee angle, and considers the expected information gain regarding the location of the optimum that obtained from an upcoming query. Entropy Search (ES) [15), Predictive Entropy Search (PES) [16] and the earlier work of IAGO [46] select queries by maximizing this quantity. While ES and PES are efficient in the number of queries to optimize
the objective, they both require significant computational effort and complex approximations of the
expected information gain, which impacts their performance and practical use [6] 47].
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A related nnermatiionthhoreeee family of approaches considers the information gain on the optimal objective value [8] 31 47 Max-value Entropy Search (MES) 47 was the first
approach to have proven convergence rate, albeit only in noiseless problem setting. Moreover, its consideration of one-dimensional density over the output space as opposed to D-dimensional input space and reduction in intricate approximations yielded a computationally efficient alternative to the ES/PES line of approaches. Despite its empirical success, some crucial shortcomings of MES have been highlighted in recent works. Its convergence rate has been disputed [42], and crucially, it does not differentiate between the (unobserved) maximal objective value f and the observed noisy maximum Vmaz [26 28 41 42 As such, its assumption
the posterior distribution of the output DDylD, x) does not hold in any setting where noise is present, and several follow-ups have been proposed to address the noisy problem setting [26 28 42).
We propose an approach which merges the ES/PES and MES lines of work, and provides an all- encompassing perspective on information gain regarding optimality. We introduce Joint Entropy Search (JES), a novel acquisition function which has the following advantages over existing infomation-theoretic approaches:
1. It utilizes two sources of information, by considering the entropy over both the optimum and the noiseless optimal value;
2. It utilizes the full optimal observation, allowing it to rely primarily on exact computation through standard GP machinery instead of complex approximations; and
3. It is computationally light-weight, requiring minimal pre-computation relative to other information-theoortii approaches which consider the input space.
Simultaneously to our work, a similar approach aimed at the multi-objective setting, was proposed by Tu et al. 24. The authors independently came up with the same JES acquisition function, with a subtly different approximation scheme to the one we present. We see our work as being complementary to theirs because both demonstrate the effectiveness of this new acquisition function in different settings theirs being multi-objective and batch evaluations, ours being single- objective and large levels of output noise. Our code for reproducing the experiments is available at hhtpps///gt cww/co///aa//ceee wwwaarrheee/iintttttoppeeeer
Background and related work
Bayesian optimization. We consider the problem of optimizing black-box function f across set of feasible inputs X' C Idd
x² E largmas fax)
(1)
#EX
We assume that f(x) is expensive to evaluate, and can potentially only be observed through a noise-corrupted estimate, y. where y = f() c, + N(0,03 o?)
for some noise level o². In this setting, we wish to maximize f in an efficient manner, typically while adhering to a budget which sets a cap on the number of points that can be evaluated. BO aims to globally maximize f by an initial design and thereafter sequentially choosing new points F, for some iteration n. creating the data DD, = Dn-1 (( ). After each new observation, BO constructs probabilistic surrogate model P()) and uses that surrogate to build an acquisition function axx D,). The combination of surrogate model and acquisition function encodes the strategy for selecting the next point xn+11 After the full budget of N iterations is exhausted, best configuration xyy is returned as either the arg max of the observed values, or the optimum as predicted by the surrogate model.
Gaussian processes. When constructing the surrogate, the most common choice is Gaussian processes (GPs) 330. Formally, a GP an infinite collection of random variables, such that every finite subset of those variables follows multivariate Gaussian distribution. The GP utilizes covariance function k. which encodes a prior belief for the smoothness of f. and determines how previous observations influence prediction. Given observations D,, at iteration n, the posterior p(f(D,,. over the objective is characterized by the posterior mean m, and variance sn of the GP:
m, (x) T (K,, + oi-I= 'y, (x) = k( x) (x) (K,, + +²'l) k,,
(2)
where (K,);j = k( 2r,), (x) = [k( m1), k(ar, ar,,]] and af is the noise variance. Alternative surrogate models include random forests [9] and Bayesian neural networks [38 39].
2

---

Acquisition functions. The acquisition function acts on the surrogate model to quantify the attractiveness of a point in the search space. Acquisition functions employ a trade-off between exploration and exploitation, typically using greedy heuristic to do so. Simple, computationally cheap heuristics are Expected Improvement (EI) [5 21]. For a noiseless function, selects the next. point #+++ as
En+1 E arg max IE (v. - ++] arg max Zs, (z))((()))))))))))))))))))))(( (z))))(()
(3)
ΦEX
=EX
where 2 (vin m. (an) (z). Other acquisition functions which use similar heuristics are the
Upper Confidence Bound (UCB) [40]. and Probability of Improvement (PI) [22]. A more sophisticated approach related to EI is Knowledge Gradient (KG) [1]
Information-theoreti acquisition functions.
informatiionthhorree acquisition functions 15 16
32 47 and their various adaptations [7 34 seek to maximize the expected information gain I from observing a subsequent query (x: y) regarding the optimum, x". This equates to reducing the uncertainty of the density over the optimum, p(z*(D) P(z arg "ax fxx using the information obtained through (x, y). By quantifying uncertainty through the differential entropy H, design points selected based on the expected reduction in this quantity over p(a= (D). Formally, this is expressed as the difference between the current entropy over (D), and the expected entropy of that density after observing the next query:
Org (z) [((z, v): x (D) H(p(æ" [D)] - By |H[p(=" ID U (æc v)ll
(4)
By utilizing the symmetric property of the mutual information, one can arrive at an equivalent expression, where the entropy is computed with regard to the density over the output y.
pEs (x) (y; (ax, x²) (D) H[p(v (D, at] Ezz [Hppyy|D, xx) x"]]]
Elss the original formulation used in ES 15 and Siss the formulation introduced with PES [6]. Both formulations require a series of approximations and expensive computational steps to compute the entropy in the second term. For PES specifically, with data points of dimension d, the second term is estimated through Monte Carlo (MC) methods by computing Cholesky decompositions of size On + de /2)5. and approximating the Hessian the optimum for each MC sample.
MSS 147 avoids this computational hurdle by considering the information gain [( y): (D) regarding the optimal value y". As such, it computes the entropy reduction for a one-dimensional density:
OMEES (a) = Tyy: (ac, y )) H(p(u/D, =)) E.. [H[p(u|D, az y²"]]-
Here, it is assumed that the posterior predictive distribution P(y/D, y²) is truncated Gaussian distribution, for which the entropy can be computed in closed form. However, P(y]D, x. y²) takes this form only in strictly noiseless setting [28] 41), where it holds true that f ymazz iec when the maximal observation and the optimal value of the objective function coincide. For noisy applications, this assumption leads to overestimation of the entropy reduction (28).
3 Joint Entropy Search
We now present Joint Entropy Search (JES), novel information- theoortic approach for Bayesian optimization. As for other enformation-theorret acquisition functions, JES considers mutual information quantity. However, unlike its predecessors, JES adds an additional piece of information: compared to ES/PES, adds the density over the noiseless optimal value f", and compared to MES, it adds the density over æ². It utilizes a novel two-step reduction in the predictive entropy from conditioning on sampled optima and their associated values. Throughout the section, we will refer to sampled optimum and its associated value, (x", f²)., an optimal pair.
3.1 Joint density over the optimum and optimal value: pictorial
JES considers the joint probability density p(#", ; f*) over both the optimum x and the true, noiseless optimal value f*. Fig. visualizes the densities ))) and p(J"), considered by ES/PES and MES, respectively, and the joint density p(#", f*), considered by JES. As highlighted by the vertical dashed lines for the point selection of each strategy (bottom), PES chooses strictly to reduce the
3

---

Distribution over optimum optimal value
(29
p(
JES
PES
Posterior uncect, ptjja
MES
X
Okseevations
pts". ((
The densities considered by ES/PES (top), MES (right) and JES (center) on a one-dimensional toy example. The multimodal density p(=", f"") is reduced to a heavy-tailed density over f for the density used by MES (right), which does not capture the multi- modality of the density over the optimum. The density over x² used by PES (top) does not capture the apparent exploration/exploittton trade-off that exists between the modes. The acquisition functions and their next point selections are highlighted with dashed lines (hottom).
Figure 1:
uncertainty over x", and as such, considers region where the uncertainty over the optimal value is low. However, can effectively determine that the right side of the local optimum more promising to query next. MES seeks to reduce the tail of the probability density over /" (right), which in this case leads to an exploratory query. JES joint probability density over optimum and optimal value captures uncertainties over both "where" and "how large" the optimum will be. As such, it selects a point which is uncertain under both measures. As such, JES will learn about likely locations for the optimum, while simultancously learning probable lower and upper bounds for the optimal value, which by itself yields an effective query strategy [47] and provides valuable knowledge for future queries. For the selected query in Fig. [ JES will learn substantially about both x² and f by querying it, whereas PES and MES learn only about one of them.
3.2
The Joint Entropy Search acquisition function
We consider the mutual information between the random variables (æ", f") and future query (æz, y):
oues( = [((x, y): f
H[p(y/D, x²] - B( [H[p(y]D, "n, (")]] ff)).
H[p([y x)] - ((-) [H[p(y (f
(9)
Eq. 8 is similar to Eq. but with the addition conditioning of the second term. The expectation is computed with respect to a D + 1-dimensional joint probability density over x" and f². In Eq. [ we make explicit that the conditional density inside the expectation is obtained after 1. conditioning the GP on the previous data D. plus one additional noiseless optimal pair (a:", f*), and 2. knowing that the noiseless optimal value fact f By utilizing the complete observation (*), we can treat it like any (noiseless) observation. As such, we quantify much of the entropy reduction by utilizing standard GP conditioning functionality. For 2., cannot globally condition on f(x') < fr Væ'. As such, we follow previous work [26] 28 42 47 and enforce the condition locally at the current query æ. The resulting effect to truncate the GP's posterior over f locally at upper bounding it to f*. Notably, utilizing the fantasized observation (x" ff) guarantees that the conditioned optimal value f" in JES actually obtained, rather than serving a possibly unattained upper bound, which is typical in the MES family of acquisition functions. The expectation in Eq. D approximated through MC by sampling L optimal pairs ((x), f2)) from p(æ" ff) using approximate version of Thompson Sampling (TS) 48 as explained in Sec. 3.3 In Fig.21 the resulting posterior distribution of the two-step conditioning is shown in greater detail. As pointed out in [88 41, after conditioning
and the replacement of y" with f* in the
f*, the posterior predictive density over is a sum of a truncated Gaussian distribution over f and the Gaussian noise e. The entropy reduction from the two-step conditioning yields two separate variance reduction steps over P(ylD, (D, æ): a conditioning term and truncation term. The former is computed exactly, while the latter, generally smaller term, requires approximation, as shown Sec. 3.4

---

Posterior distributionn (11)) ply!zt
Posterior condttoning (x',
conditioning truncation
Olgecuie
plyss Uncortarry,
potet
Coniiticeed
Figure 2: Step-by-step modeling when conditioning on one optimal pair (x", The posterior with noise P(y(D) and without noise p(f observations, before conditioning on (ar", ; ff) is shown
illustrated in blue and yellow. respectively. The GP after (noisy) the left. the middle panel, we draw (x", f") and condition on it, making p(f (x' (x",f") (f") a delta distribution the conditioning point as the fantasized observation f is noiseless. Since f" is also the presumed noiseless maximum, we truncate its posterior p(/(D U (w' [") globally in the right panel. The observation noise allows for non-zero density on p(y D ("). We note that, while the noise is homoscedastic, its relative contribution to the total variance differs over the input space, As such, and since we're plotting standard deviations (not variances). the blue region wider near observed data, where p(f) (D) has lower variance.
D) (D)
Fig. 3 shows the difference in log variance over plyl D x:) resulting from conditioning (in blue) and truncation (in orange) for the scenario in Fig. 2 The overall reduction is largest close to the point of conditioning, and the truncation term mainly contributes at uncertain regions far away from the conditioned point. Moreover, the magnitude of the conditioning term will rely on the prior variance at the conditioned point, as a larger prior variance will lead a larger reduction in entropy from con- ditioning. As we average over optimal pairs, many such entropy reduction terms accumulate.
Condition ing location Conditioning term.
Tautcation torm
1.3
131
Figure 3: Reduction in log variance from the condi- tioning step and the truncation step visualized in Fig. The local conditioning term (blue), and the globally variance-reducing truncation term (orange).
3.3 Incorporating optimal pairs
To obtain samples ff we utilize an approximate variant of TS 43 PES [16]. We utilize Bochner's theorem [4), which, for any stationary kernel k asserts the existence of its Fourier dual s(w). By normalizing s(w), we obtain the spectral density p(w) = s(w)/a,
originally proposed in
where is normalization constant. We can then write the kernel as an expectation,
k(xx x') aEw (e (x- 2n o [cos(ww (wT b) cos(w x' + b)],
(10)
where b~ (0, I). Following Rahimi and Recht (29). we sample b and w obtain an unbiased estimate of the kernel kt From this approximation, approximate sample paths can be drawn weighted sum of basis functions. This form allows for fast and dense querying of the sample paths the arg max and max of which is an approximate draw from p(æ=", f*). In PES, each sample of along with its inverted Hcssian required for computing the acquisition function. To obtain the Hessian, each sample needs to be thoroughly optimized through gradient- based optimization. JES on the other hand, only requires (x*, f"). As such, it can rely on cheap, approximate optimization of these samples, e.g., by densely querying sample points on non-uniform grid.
After obtaining set of optimal pairs {(x} vē) v JES computes the conditional entropy quantity over the output y. Concretely, we generate L GPs, each modeling a posterior density {p(y) 'D U (e a:) } conditioned on an optimal pair and previously observed data D. Since each optimal pair is drawn from the current GP hyperparameter set, we know that the current hyperparameter set is the correct one even after adding the optimal pair to the data. By consequence, JES can compute the updated inverse Gram matrix, (K + through rank-1 update, instead of solving linear system
5

---

of equations. Utilizing the Sherman Morrison formula [36]. we obtain updated Gram matrices in Onn)) for each sample, as opposed to Onn") for solving the linear system of equations.
Cheemann-Moriioo
3.4 Approximating the truncated entropy
As highlighted in the right panel of Fig. 2 conditioning on f yields a truncated normal distribution
P(fID U (x", ff). x f*) after having locally enforced the inequality f(z) < f". The entropy. however, is computed with regard to the density over noisy observations, y = + e, which follows an Extended Skew distribution [28] and such, does not have tractable entropy. We approximate this quantity through moment matching (26) of the truncated Gaussian distribution over f. which yields a valid lower bound on the information gain [26]. Consequently, we obtaín two Gaussian densities P( U (a", ["), 2. f*) ~ N (imirr=; ;(イ and p(c) (0, where f/ and f| are the mean and variance of the truncated Gaussian posterior p U (x* [ x, f*). Due to independence between f and c and the linearity of Gaussian distributions, we can then compute the entropy of the approximate density Py exactly as (i(jy))u(x",,, ff)), x, (fr log (2 + o fir-)). Moreover, the variance of the truncated Gaussian 2 computed as
(z; (xt, f7)) = of ( (x), s,,
(11)
where aa μu, o²) is the variance of an upper truncated Gaussian distribution with parameters (n, o²), truncated at a, and m (a) and of (a) are the mean and covariance functions of the GP which is conditioned on the optimal pair (ar J(). The quality of the moment matching approximation is
studied in greater detail in Appendix
3.5 Exploitative selection to guard against model misspecification
As with all coermatiio-thhorette approaches, JES aims to reduce the uncertainty over the location of the optimum. With this strategy, the incentive to query the perceived optimum often lower than for heuristic approaches, such as EI. In cases where the surrogate model is misspecified, information- theoretic approaches risk reducing the entropy based on a faulty belief of the optimum, which can drastically impact their performance. As remedy, parallel context of AEGIS 19: with probability 7, JES will query the arg max of the posterior mean to confirm its belief of the location of the optimum. If the model is misspecified, these exploitative steps enable the algorithm to reconsider its beliefs, rather than continuing to act based on faulty ones. In Appendix C.2 show how this approach can substantially improve performance in cases of surrogate model misspecification, while having negligible impact on performance in the worst case.
utilize 7-exploit approach inspired by the
3.6 Putting it all together: The JES algorithm
For sampled set of size L, containing optimal pairs {( vi and GPs with mean and covari- ance functions (m,, (w), sf, (x)) the expression for the JES acquisition function is
axx) H Hpp D, x] ((x,ff)) [Hp[u|DU (x" x)),
(12)
1 E log(2n(0 on (æ; DU (2t, f())), I
log(22 (a:) +02)
(13)
The first term in 13 simply the entropy of a Gaussian that be computed in closed form. The second term contains both the conditioning term, which is exact, and the truncation, which is approximated described in Sec. 3.44 Algorithm outtines pseudocode for JES in its entirety.
4 Experimental evaluation
Benchmarks. We now evaluate JES on suite of diverse tasks. We consider three different types of benchmarks: samples drawn from a GP prior, commonly used synthetic test functions [66], and a collection of classification tasks on tabular data using an MLP, provided through HPOBench [10] For the GP prior tasks, the hyperparameters are known for all methods to evaluate the effect of the acquisition function in isolation. Consequently, we do not use the 7-exploit approach from Sec. 3.5

---

Algorithm JES Algorithm
1: Input: Black-box function f. input space X, size M of the initial design, max number of optimization iterations N, number of posterior MC samples L, fraction of exploit samples 7.
2: Output: Optimized design x".
3: DM < { y/ 3:)] AM
b initial design
4: for {n = M + 1,................... ,M + do
5: m(x), s² ( < FITGP(Da-1)
6: if RAND(O, 1) < then
< arg max (m(
described in Sec. 3.5
7: else
8: for 11 1.=1..... L} do (0j, v2) + TS(J)
9:
as described in Sec. 3.3
10:
p(y] U (Et (2), < UPDATEGP(02,
described in Sec. 3.3
11:
end for
12:
13: end Tn arg maxx (x)
defined in Eq. 12
14: Yn =( te, Dn + Da-1 U ((Em Unl}
observe next query
15:
end for
16:
return x=' arg x (x)
in this case (i.e., we set 0 in Algorithm D. For the synthetic and MLP tasks, we marginalize over the GP hyperparameters, and set 7 = 0.1. The hyperparameters the GP prior experiments can be found in Appendix B and ablation studies on in Appendix
Evaluation criteria. We use two types of evaluation criteria as in simple regret and inference
regret. The simple regret rn = maxæex f(x maXxe[1.x] f(x) measures the value of the best queried point so far, After query, we may infer an arg max the function, which chosen as x;
arg m m, (x) [15, 16 47). We denote the inference regret as r. maX f f(x) f Since information-theore
approaches do not necessarily seek to query the optimum, but only to know its location, inference regret characterizes how satisfying our belief of the arg max is. Notably, this metric non-monotonic, meaning that the best guess can worsen with time. We use this metric in the ideal model benchmarking setting, when sample tasks from GP with known hyperparameters. We use simple regret for the synthetic test functions, as constitutes a metric that is more robust to surrogate model misspecification. Inference regret for these tasks can be found in Appendix F For the HPOBench tasks, inference regret is unobtainable.
The experimental setup. We compare against other state-of-the-arr information-theoree ap- proaches: PES [66] and MES [47], as well as EI (21] The acquisition functions are all run in the same framework written in MATLAB, created for the original PES implementation by Hernáneez-Lobato et al. [16]. All synthetic experiments were run for 50D iterations. In the main paper, we fix the number of MC samples for MES, PES and JES to 100 each. In Appendix Di we assess the sensitivity of JES to this number and quantify the computational expense. In Appendix we provide all details on experimental setup, including the runtime tests.
4.1 GP prior samples
We consider samples from GP prior for four different dimensionalities: 2D, 4D, 6D, and 12D, with noise standard deviation of 0.1 for range of outputs spanning roughly [-10, 10). These tasks constitute an optimal setting for each algorithm, as the surrogate perfectly models the task at hand. In
Fig. 5 JES demonstrates empirically the value of the additional source of information, substantially outperforming PES and MES on all tasks.
Fig. 4 compares JES (top left) against PES, MES and EI in terms of point selection for one repetition on a two-dimensional sample task, where all runs are initialized with D + identical random samples. We observe that JES succeeds in finding all attractive regions of the search space, and queries the region around the optimum densely, which is sensible in a noisy setting. We further notice that EI (bottom right) fails to query the two circled local optima. PES (bottom left) also ignores two local optima to various degrees, and tends to circle the (perceived) optimum densely, which expensive in terms of number of evaluations. We believe this showcases shortcoming of only
7

---

Joint Entropy Search
value Entropy Search
2D sample
4D-GP sample
1.0
10-100
Lasa Regure
0.0
-03
-1.0
-1.5
-2.
65
60
80
100
1.00
150
200
6D-GP sample
12D-GP sample
Predictive Entropy Search
Expected Improsement
122
9.5
1.00
3.5-
-1.4
3.00
-1.
-0.25
Star Stration
Iteration
Figure 5: Comparison of JES, MES. PES and EI GP prior samples. We run 1000 repetitions each for 2. 4 and 6D, and 250 on 12D. Mean and 2 standard errors of log regret are displayed for cach acquisition function. The vertical dashed line shows the end of the initial design phase.
Figure 4: Comparison of queries for JES (top left), MES (top right). PES (bottom left) and EI (bottom right) on a sample of 2D GP after a 100 function evaluations. The global optimum is circled in white, and four local optima in grey. Earlier queries are colored yellow, and later queries red.
considering the density over the optimum: PES circles the optimum, but does not query its value. Lastly, MES (top right) successfully queries all attractive regions of the space, but also samples regions that are evidently poor the most densely out of the four approaches, despite information given by earlier (brighter) samples. Since JES considers the information conveyed by both MES and PES, it successfully excludes the apparent suboptimal regions of the space, finds all relevant optima, and queries these optima in a desirable manner.
We additionally evaluate the performance of all approaches on GP sample tasks that have a sub- stantial amount of noise its standard deviation roughly accounting for 10% of the total output range. We run these tasks with the GP hyper- parameters fixed priori for larger number of iterations, 125D, to display the stagnation of some approaches. While MES and PES slow down approximately at the halfway point for both tasks, JES steadily improves for the entire length of the run. This robustness to large noise magnitudes highlights the importance of intrin- sically handling noisy objectives in JES.
2D-GP sample
4D-GP sample
1.0
1.0
0.3
Log Rogrot
0.5
0.0
200 300
Reration
Figure 6: Evaluation of JES, MES, PES and EI on noisy (o² orange) GP sample tasks across 100 repeti- tions. Mcan and standard errors log regret are displayed for each acquisition function.
Task
JES-100
MES-T00
PES-100
HI 0.23 0.13
2D
1.40 0.32
1.03 0.19
17.39 4.95
4D
1.50 - 0.37
0.3
34.53 8.3
0.3 0.17
6D
1.56 = 0.39
0.37
62.92 + 13.54
0.35 0.2
Table Runtime of JES, MES, PES and EI on GP sample tasks of varying dimensionalities. JES is only marginally slower than MES, and orders of magnitude faster than PES.
In Table [ we display the runtime of each acquisition function on these tasks when marginalizing over 10 sets hyperparameters, and sampling 10 optima per set. We time each iteration from after hyperparameters have been sampled, up until (but excluding) the query of the black-box function. Thus, acquisiiiin function pre-computation and optimization are included. The runtime of JES is only marginally slower than that of MES with Gumbel sampling, while being at least an order of magnitude faster than PES for all displayed dimensionalities.
8

---

4.2 Synthetic test functions
Next, in Fig. we study the performance of JES on three optimization test functions: Branin (2D), Hartmann (3D) and Hartmann (6D). For these tasks, we follow convention [66 31 and marginalize over GP hyperparameters. On Branin, JES starts out slightly slower than MES but reaches the same performance 100 iterations; and on the two Hartmann functions, JES performs amongst the best in the beginning and clearly best in the end. We note that PES experienced numerical issues on Branin, and as such, we acknowledge that its performance should be better than what reported.
Branin
Hartmann-3
Hartmann-6
0.5
0.5
0.0
Log Regrot
-1.0
E1
1.5
-1.0
JES:
KES- 103
FE5-100
-2.5
-1.5
20
40
60
100 25
50
100
125
150
50
150
150
200
250
300
Itcrottion
Iteratioon
Iteration
Figure 7: Comparison of JES, MES, PES and EI on Branin and Hartmann-66 6, o = 0.10. Mcan and 2 standard errors of log regret displayed for cach acquisition function across 100 repetitions. The vertical dashed line represents the end the imitial design phase.
4.3 MLP tasks
Lastly, we evaluate the performance of JES on the tuning an MLP model's 4 hyperparameters for 20D iterations six datasets. These tasks are part of the OpenMI library of tasks, and the HPO benchmark is provided through the HPOBench [10] suite. We measure the best observed classification accuracy. Notably, these tasks have a large amount of noise, which causes the performance fluctuate substantially between repetitions. We observe that JES performs substantially better on two tasks, and is approximately equal in performance EI on three, with EI being superior one task. JES displays superior or equal performance to MES on all tasks, with PES lagging behind.
German Credit
Software Defects
Image Segmentation
0916
0.8050
Log Begges
2914
0.9325
0.12
0.8300
0.966
2910
0.M675
8.88
JeS-100
0.9250
Mas-202
0.362
8.88
Beraation
Iteration
Vehicle Silhouctte
Blood Transfusion
Australian Credit
0.945
0.902
0.948
Regret
0.900
0.345
0.949
0,830
0.944
0.966
0.944
0.820
0.92
0.815
0.90
40 Lteratton
Iteration
Iteration
Figure 8: Comparison of JES, MES, PES and EI six different MLP tuning tasks from the HPOBench suite. Mean and standard error of hest observed accuracy displayed for each acquisition function 100 repetitions. vertical dashed line represents the end initial design phase.
'http://www.opemml.rr/

---

5 Conclusions
We have presented Joint Entropy Search, an ieformatiionthhoreee acquisition function that considers an entirely new quantity, namely the joint density over the optimum and optimal value. By utilizing the entropy reduction from fantasized optimal observations, JES obtains simple form for the entropy reduction regarding the joint distribution. As such, the additional information considered comes with minimal computational overhead, avoids restrictive assumptions on the objective, and yields state-of-the-an performance along with superior decision-making. We believe JES to be a new go-to acquisition function for BO, and to establish new standard for subsequent Coormation-thhoree techniques.
6 Limitations and Future Work
The main contribution of this paper is to provide a novel information-theoretie acquisition function which, given sufficiently accurate model, yields impressive results. However, the non-myopic, speculative nature of information-theore fication, such as poor choice of GP kernel or GP hyperparameters. In our view, informationnthhoreee approaches are possibly more susceptible to this issue than their myopic counterparts (EI, UCB, TS). While we propose a remedy to stabilize and improve the acquisition function under model misspecifi- cation with the 7-exploit approach, this technique only serves to discover misspecification and adjust accordingly, but not to inherently fix the misspecification. We believe misspecification can only be remedied by altering the surrogate model. It is thus very promising to combine advanced modelling ceemmation-thhoeee
approaches lend them to be susceptible to model misspeci-
techniques with approach utilized in conjunction with MES by Wang and Jegelka [47]: further promising additions would be to tackle heterogeneous noise and input warping as done by HEBO
acquisition functions, as already done with the additive GP
We also note that, since JES computes the entropy reduction from conditioning on the optimal pair, it relies on some level of noise in the objective. A surrogate model with zero noise will result in an infinite information gain for every optimal pair, which (by utilizing some random tie-breaking strategy) would make JES equivalent to TS. However, if JES is be used in a completely noiseless setting, we argue that a small noise term should be added as remedy. As this is done by default in many prominent GP frameworks [13 14 45), we do not view this as major limitation of our approach. Nevertheless, improving upon this strategy would be interesting in future work.
For future work, also envision work the adaptation of JES to various different domains, such as multi-fidelity [48] and multi-objective optimization []. as well as the integration of user prior knowledge over the location of the optimum (20 to accelerate optimization.
Acknowledgments and Disclosure of Funding
Luigi Nardi was supported in part by affiliate members and other supporters of the Stanford DAWN project- Ant Financial, Facebook, Google, Intel, Microsoft, NEC. SAP, Teradata, and VMware. Carl Hvarfner and Luigi Nardi were partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. Luigi Nardi was partially supported by the Wallenberg Launch Pad (WALP) grant Dnr 2021 1.044. Frank Hutter acknowledges support through TAILOR, a project funded by the EU Horizon 2020 research and innovation programme under GA No 952215, by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) under grant number 417962828, by the state of Baden- Württemberg through bwHPC and the German Research Foundation (DFG) through grant no INST 39/963-1 FUGG, and by the European Research Council (ERC) Consolidator Grant "Deep Learning 2.0" (grant 101045765). The computations were also enabled by resources provided by the Swedish National Infrastructure for Computing (SNIC) at LUNARC partially funded by the Swedish Research Council through grant agreement no. 2018 0018-05973. Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the ERC. Neither the European Union nor the ERC can be held responsible for them.
Funded by the European Union
10

---

References
[1] S. Belakaria, A. Deshwal, and J. R. Doppa. Max-value entropy search for multi-objective bayesian optimization. Advances in neural information processing systems, 32, 2019.
[2] Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for Hyper-Parameter Optimiza- tion. In Advances in Neural Information Processing Systems (NeurlPS), volume 24. Curran Associates, Inc., 2011.
[3] Berkenkamp, A. Krause, and A. Schoellig. Bayesian optimization with safety constraints: Safe and automatic parameter tuning in robotics. Machine Learning, 06 2021. doi: 10.1007) s 0999440021-0019--
[4] S. Bochner et al. Lectures on Fourier integrals, volume 42. Princeton University Press, 1959.
[5] A. D. Bull. Convergence rates of efficient global optimization algorithms. 12:2879-2904, 201
[6] R. Calandra, N. Gopalan, A. Seyfarth, J. Peters, and M. Deisenroth. Bayesian gait optimization for bipedal locomotion. In Pardalos and M. Resende, editors, Proceedings of the Eighth International Conference on Learning and Intelligent Optimization (LJON' 14), 2014.
[7] Y. Chen, A. Huang, Z. Wang. I. Antonoglou, J. Schrittwieser, D. Silver, and N. de Freitas. Bayesian optimization in alphago. CoRR, abs/1812.06855,, 2018. URL http: //arxvv..vvv.///a .rrg/ abs bbss/181.com Abs/1812.06855
[8] A. I. Cowen-Rivers, W. Lyu, Z. Wang, R. Tutunov, J. Hao, J. Wang, and H. Bou-Ammar. HEBO: heteroscedastic evolutionary bayesian optimisation. CoRR, abs/2012.03826, 2020. URL https://arxta org/ abs/2012/ 03826
[9] G. De Ath, R. M. Everson, and J. E. Fieldsend. Asynchronous e-greedy bayesian optimisation. In C. de Campos and M. H. Maathuis, editors, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Muchine Learning Research, pages 578-588 27-30 Jul 2021.
[10] K. Eggensperger, P. Müller, N. Mallik, M. Feurer, R. Sass, A. Klein, N. Awad, M. Lindauer, and F. Hutter. HPOBench: A collection of reproducible multi-fidelity benchmark problems for HPO. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[11] A. Ejjeh, L. Medvinsky, A. Councilman. H. Nehra, S. Sharma, V. Adve, L. Nardi, E. Nurvi- tadhi, and R. Rutenbar, Hpvm2fpga: Enabling true hardware-agnostic fpga programming. In Proceedings of the 33rd IEEE International Conference on Application-speccffc Systems, Architectures, and Processors, 2022.
[12] P. I. Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv: 2018.
[13] J. R. Gardner, G. Pleiss, D. Bindel, K. Q. Weinberger, and A. G. Wilson Gpytorch: Black- box matrix-matrix gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, 2018.
[14] GPy. GPy: A gaussian process framework in python. http://github.co htt.gghhhhb..mmmmheffeeedddd GPy since 2012.
[15] Hennig and C. Schuler. Entropy search for informmatin--fffcciet global optimization. Journal of Machine Learning Research, 13(1):1809-188) June 2012. ISSN 1532-4435.
[16] M. Hernández-LLoatoo, M. W. Hoffman, and Z. Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Advances in Neural Information Processing Systems, 2014. URL
www.sseeuripssccco cttp.rrrpp.cc/pppp/////////// .dff
[17] J. M. Hernández-Looato M. Gelbart, M. Hoffman, R. Adams, and Z. Ghahramani. Predictive entropy search for bayesian optimization with unknown constraints. In International conference on machine learning, pages 1699-1707. PMLR, 2015.
11

---

[18] M. W. Hoffman and Z. Ghahramani. Output-space predictive entropy search for flexible global optimization. 2016.
[19] Hutter, H. H. Hoos, and K. Beyton-Brown Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization, 2011.
[20] C. Hvarfner, D. Stoll, A. Souza, L. Nardi, M. Lindauer, and F. Hutter. PiBO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimization. In International Conference on Learning Representations, 2022.
[21] D. Jones, M. Schonlau, and W. Welch. Efficient global optimization of expensive black box functions. 13:455-492, 1998.
[22] H. J. Kushner. A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering, 86( 1:97-106, 03 1964. ISSN 0021-9223. doi: 10.1 11151.363311)) URL htw.hhttpss///eooo
org 10. 1115/13663121.
[23] M. Mayr, F. Ahmad, K. I. Chatzilygeroudis, L. Nardi, and V. Krüger Skill-based Multi-objective Reinforcement Learning of Industrial Robot Tasks with Planning and Knowledge Integration. CoRR, abs/2203. 10033, 2022. URL httpt: org/ 10. 48550/ 2203. 10033
[24] M. Mayr, C. Hvarfner, K. Chatzilygeroudis, L. Nardi, and V. Krueger. Learning skill-based industrial robot tasks with user priors. IEEE 18th International Conference on Automation Science and Engineering, 2022. URL htttt:t/p///xiii org/ abs aaba/2200 2208 01605
[25] Mockus, V. Tiesis, and A. Zilinskas. The application of Bayesian methods for seeking the extremum. Towards Global Optimization, 2(117-129):2, 1978.
[26] H. B. Moss, D. S. Leslie, J. Gonzalez, and P. Rayson. Gibbon: General-purpose information- based bayesian optimisation. Journal of Machine Learning Research, 22(235):1 --,,, 2021. URL
http://jmlr. org/ http//apprss///2/ wttp://v///eeeeee 0120. html
[27] L. Nardi, D. Koeplinger, and K. Olukotun. Practical design space exploration. In 2019 IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 347-358. IEEE, 2019.
[28] Q P. Nguyen, B. K. H. Low, and P. Jaillet. Rectified vax-v entropy search for bayesian optimization, 2022. URL htttps://arxiv..otttt wrgg//b////2....../ 23002.
[29] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, Advances in Neural Information Processing Systems, page 1177-1184, Red Hook, NY, USA, 2007. Curran Associates Inc. ISBN 9781605603520.
[30] C. Rasmussen and C. Williams. Gaussian Processes for Machine Learning. The MIT Press, 2006.
[31] B. Ru, M. A. Osborne, M. Mcleod, and D. Granziol. Fast ieformatioonthhorrttii Bayesian optimisation. J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4384 4392. PMLR, 10-15 Jul 2018. URL ottppppooeccnngi...rpprpeeeeeee. html
[32] D. Russo and B. Van Roy. Learning to optimize via information-directtd sampling. Advances in Neural Information Processing Systems, 27, 2014.
[33] K. Šehić, A. Gramfort, J. Salmon, and L. Nardi. LassoBench: A High-Dimensional Hy- perparameter Optimization Benchmark Suite for Lasso. arXiv preprint arXiv:2111.02790. 2021.
[34] A. Shah and Z. Ghahramani. Parallel predictive entropy search for batch global optimization of expensive objective functions. Advances in neural information processing systems, 28, 2015.
[35] B. Shahriari, K. Swersky, Z. Wang, R. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148-175,0 2016.
12

---

[36] J. Sherman and W. J. Morrison. Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix. The Annals of Mathematical Statistics, 21( 127, 1950. doi: /
htt.ssts:: org/ 1tt.1/11///////77//////0000////0
[37] J. Snoek, H. Larochelle, and R. Adams. Practical Bayesian optimization of machine learning algorithms. In Bartlett, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Pro- ceedings of the 26th International Conference Advances in Neural Information Processing Systems (NeurlPS' 12), 12), pages 2960-2968, 2012.
[38] J. Snoek, O. Rippel, K. Swersky, R. Kiros, N. Satish, N. Sundaram, M. Patwary, Prabhat, and R. Adams. Scalable Bayesian optimization using deep neural networks. In F. Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning (ICML' (5), Omnipress, 2015.
volume 37, pages
[39] Springenberg, A. Klein, S. Falkner, and Hutter. Bayesian optimization with robust Bayesian neural networks. In D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, and R. Garnett, editors, Proceedings of the 30th International Conference on Advances Neural Information Processing Systems (NeurIPS' 16), 2016.
[40] N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. Information- regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 585)) 3265, May 2012. ISSN 1557-9654, doi: 10.1109//112201122180233 URL http://das doi org/ 10. 1109/TIT. 2011. 2182033
[41] S. Takeno, H. Fukuoka, Y. Tsukada, T. Koyama, M. Shiga, I. Takeuchi, and M. Karasuyama. Multi-fidelity Bayesian optimization with max-value entropy search and its parallelization. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9334-9345 PMLR, 13-18 Jul 2020. URL https://
mlr ggress/v119) 1e1.199//eeeee....m html
[42] S. Takeno, T. Tamura, K. Shitara, and M. Karasuyama. Sequential and parallel constrained max-value entropy search via information lower bound. In Chaudhuri, S. Jegelka, L. Song, C. S.Seeeesvri, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Muchine Learning, volume 162 of Proceedings of Machine Learning Research, pages 20960-20986. PMLR, 17-23 Jul 2022. URL htRpsttss://///
mlr. www.mmlrr././/../mmemm www.srrssvvvl. vv62/
takeno22a.
[43] W. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4))285-294 1933.
[44] B. Tu, A. Gandy, N. Kantas, and B. Shafei. Joint entropy search for multi-objective bayesian optimization. arXiv preprint arXiv:2210.02900 2022.
[45] J. Vanhatalo, J. Rüihimäki, J. Hartikainen, P. Jylänki, V. Tolvanen, and A. Vehtari. Gpstuff: Bayesian modeling with gaussian processes. Journal of Machine Learning Research, 14: 1175-1179, Apr. 2013. ISSN 1532-4435.
[46] J. Villemonteix. E. Vazquez, and E. Walter. An informational approach to the global optimization of expensive-to-evaluut functions. Journal of Global Optimization, 44, 12 2006. doi: 10. 1007/ s (0898-008-93544
[47] 7.. Wang and S. Jegelka. Max-value entropy search for efficient bayesian optimization. In International Conference on Machine Learning (ICML), 2017.
[48] Y. Zhang, T. N. Hoang, B. K. H. Low, and M. Kankanhalli. Information-base multi-fidelity bayesian optimization. In NewrIPS Workshop on Bayesian Optimization, 2017.
13


Reviews:
[{"review_id": "QGa9VM2QXoJ", "reviewer": "Reviewer_ms2M", "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. ", "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?\n\nOptimizing 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. \n\nI 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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.\n- The clarity of this work is very good. The motivation and most steps of the method are explained very well.\n- 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. \n\nWeaknesses / suggestions\n- 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.\n- 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.\n- 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.\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J4dwAzFf4o3", "reviewer": "Reviewer_G9Zj", "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.", "questions": "1) How are (4) and (5) equivalent? The mutual information terms are clearly different.\n2) 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.\n3) In line 101 the mutual information objective of MES differs from the one in (6). Which is correct?\n4) 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?\n5) 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.\n6) In Algorithm 1, what is the meaning of $y_n=f(x_n)+\\epsilon$? Does that mean that a random $y_n$ is sampled?\n7) 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.\n8) 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).", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nMy 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)?\n\nI 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:\n- 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.\n- l28: space missing around \"PES\"; also please check consistent typesetting of ES and PES.\n- l79: \"employ\": in my understanding, acquisition functions do not employ, but rather define this trade-off.\n- eq. (3): $y^*_{n+1}$ should be replaced by $y$, or even better by $f(x)$, since we assume a noiseless function.\n- The usage of (1) and (2) in lines 130-136 is slightly confusing, as I was briefly looking for the presumably referenced equations.\n- 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.\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HIdKlMzkOpA", "reviewer": "Reviewer_7H23", "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.", "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.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proposes another variant of entropy search. \n\n+ The intuition behind the basic idea is simple.\n+ A variety of empirical evaluations are provided. \n\nHowever, 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.\n\n- 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.\n\n- 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. \n\n- 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.\n\n- 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. \n\n- About MES, in line 103-104, the authors described\n\n> 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\n\nThis 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]). \n\n- In line 142-143, the author described\n\n> 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\n\nRelated 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)). \n\n- In line 183, the author described\n\n> 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.\n\nUnder 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.\n\n- 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. \n\n- 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.\n\n- 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)). \n\n- 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. \n\n- 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.\n\n==================================================\n Post-rebuttal \n==================================================\n\nThank 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. \n\n<1> Novelty about noise treatment \n\nThank 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).\n\n<2> Misunderstanding about incorporation of f* globally\n\nFrom the response, I consider that the authors have a fundamental misunderstanding about the discussion of the global truncation by f*.\n\nI'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).\n\nIn 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).\n\nOn 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). \n\nIn 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). \n\nThe 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.\n\nMany 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.\n\nW. C. Horrace, Some results on the multivariate truncated normal distribution, Journal of Multivariate Analysis, 2005\n\n<3> JES with a noiseless model \n\nAlthough 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. \n\n<4> Existing studies for truncation by f* in the noisy setting (y is not truncated)\n\n> 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\n> > The integral in (24) can be calculated by using numerical integration in the same way as (6).\n>\n> which indicates that the computation is not tractable, but needs approximation.\n\nI'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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-gOVF2NijlH", "reviewer": "Reviewer_Lu7F", "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^*). \n\nTo 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. \n\nIn 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.", "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?\n\n- 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?\n\n- (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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- 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.\n\n- 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.\n\n- 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.\n\nWeakness\n\nsee Questions", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept