A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization
Authors: Nuojin Cheng
Leonard Papenmeier
Stephen Becker
Luigi Nardi
Venue: ICML 2025 oral (2025)
Keywords: Bayesian optimization
Entropy search
Variational inference
Acquisition function
Primary area: probabilistic_methods->bayesian_models_and_methods
TL;DR: We propose a unified framework that bridges entropy search and expected improvement, enhancing expected improvement for improved performance.

Abstract: Bayesian optimization is a widely used method for optimizing expensive black-box functions, with Expected Improvement being one of the most commonly used acquisition functions. In contrast, information-theoretic acquisition functions aim to reduce uncertainty about the function’s optimum and are often considered fundamentally distinct from EI. In this work, we challenge this prevailing perspective by introducing a unified theoretical framework, Variational Entropy Search, which reveals that EI and information-theoretic acquisition functions are more closely related than previously recognized. We demonstrate that EI can be interpreted as a variational inference approximation of the popular information-theoretic acquisition function, named Max-value Entropy Search. Building on this insight, we propose VES-Gamma, a novel acquisition function that balances the strengths of EI and MES. Extensive empirical evaluations across both low- and high-dimensional synthetic and real-world benchmarks demonstrate that VES-Gamma is competitive with state-of-the-art acquisition functions and in many cases outperforms EI and MES.

A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization
Nuojin Cheng* Leonard Papenmeier
Stephen Becker
Luigi Nardi 2.3
Abstract
sition function (AF) a X' - R. An effective AF must bal- ance the inglorationeexlloitttion trade-off, where exploita- tion prioritizes sampling points predicted by the surrogate to yield high objective values, while exploration targets re- gions with the potential to uncover even better values.
Bayesian optimization is widely used method for optimizing expensive black-box functions, with Expected Improvement being one of the most commonly used acquisition functions. In contrast, information-theoreti acquisition func- tions aim to reduce uncertainty about the func- tion's optimum and are often considered fun- damentally distinct from EL In this work, we challenge this prevailing perspective by intro- ducing a unified theoretical framework, Varia- tional Entropy Search, which reveals that El and information-theoortic acquisition functions are more closely related than previously recognized. We demonstrate that EI can be interpreted as a variational inference approximation of the pop- ular information-theoree named Max-value Entropy Search. Building on this insight, we propose VEm-Gamma, novel acquisition function that balances the strengths of El and MES. Extensive empirical evalua- tions across both low- and high-dimensional syn- thetic and real-world benchmarks demonstrate that
Expected Improvement (EI) (Mockus 1998) is one of the most widely used AFs, valued for its simple formula- tion, computational efficiency, and strong empirical perfor- mance. The core idea behind EI is to maximize the ex- pected improvement over the current best observed value, which typically requires a noise-free assumption. More re- cently, (Villemonteix et al. 2009 |Hennig & Schuler 2012)) have introduced the concepts of information-theoorticc AFs, which represents a paradigm shift in Bayesian optimiza- tion. Unlike EI, which focuses on directly maximizing po- tential improvement, information-theored AFs aim to re- duce uncertainty about the function f's optimal position and/or value, often through entropy-based measures. Due to their fundamentally different underlying philosophies and selection criteria, El and information-thooredt AFs widely regarded distinct methodologies within the BO community (Hennig et al. 2022).
acquisition function,
Despite their apparent differences, we argue that EI and information-theoortic AF's share deeper theoretical connec- tions than previously recognized. Understanding this rela- tionship is crucial, provides novel insights into design- ing new acquisition functions. By unifying the perspectives of both sides, introduce VES-Gamma. fectively balances their strengths, resulting in robust AF that adapts well to diverse optimization problems. VES- Gamma inherits the performance of El while incorporating Eformation-theoretii considerations.
is competitive with state-of- the-art acquisition functions and in many cases outperforms EI and MES.
AF that ef-
1. Introduction
Bayesian optimization (BO) a widely used technique for maximizing black-box functions. Given a function X TR., BO iteratively refines probabilistic surro- gate of f. typically a Gaussian process (GP), and selects the next evaluation point accordingly. At each iteration, the next sampling point determined by maximizing an acqui-
In summary, we make the following key contributions:
Equual contribution 'Department of Applied Mathematics, University of Colorado Boulder 'Department of Computer Sci- ence, Lund University "DBuune. Correspondence to: Nuojin Cheng <Nuojin. Seegiin,Chenggee Chwen@@coloraooooooooooooooooooo colooraoo.du>>.
1. We introduce the Variational Entropy Search (VES) framework which shows that EI can be interpreted as special case of the popular information-theerrtie ac- quisition function Max-value Entropy Search (MES). This unified theoretical perspective reveals that these two types of AFs are more closely related than previ- ously recognized.
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Unified Framework for Entropy Search and Expected Improvement
2. We propose VES-Gamma as an intermediary between El and MES, incorporating information-theorete prin- ciples while maintaining El's strength in performance.
that its evaluation reduces uncertainty regarding the opti- mal points of the objective function. This uncertainty is quantified using differential entropy, defined as Hi][]] == E log p(y)]. Similarly, the conditional entropy is ex- pressed as [y][ = Hz y) - -H(
3. We provide an extensive evaluation across diverse set of low- and high-dimensional synthetic, GP sam- ples, and real-world benchmarks, demonstrating that consistently performs competitively and, in many cases, outperforms both El and MES.
The first iitommttion-thooeee AF for BO is Entropy Search (ES) (Hennig & Schuler, 2012), which is formu- lated as:
Orgs (rgs(:)) = [= [D.] Bp(ua| (P,)
[H Dt, Um]]
(2)
2. Background and Related Work
Here, the random variable x represents the location of the maximum.
2.1. Gaussian Processes
A Gaussian process is a stochastic process that models unknown function. It is characterized by the property that any finite set of function evaluations follows a multivariate Gaussian distribution. Assuming that f has a zero mean, a Gaussian process is uniquely determined by the current observations D, == {(x,, Ne, M== and the kernel func- tion k(x, æ²). Given these, at stage t, the predicted mean of Ye a new point x is pe(x)
Predictive Entropy Search (PES) (Hemández-Lobato al. 2014) offers reformulation of ES that is computationally more efficient:
OPes (x) = Hil[y D.] - Ep(a (D.) [May Dr, x<)) "]]]- (3)
Since directly estimating the entropy with x" is expen- sive, following the PES format, Max-value Entropy Search (MES) (Wang & Jegelka 2017) introduced alternative approach that focuses reducing the differential entropy of the ID maximum value y":
(x(x)"((,) 'y:. and the predicted covariance between points and x' is Cov.(a, (x) = x(x, x²) <=( (K.) (xr" where [N(())] = k(x,,)), yylss = ye.. and [K]ka =
k(x;, R;)); see Rasmussen et al. (2006) for more details.
aMES (x) Hly" Di] Epis= (D.) HHy""
Des yeel
2.2. Acquisition Functions
Hyu De
Bpl D,)
H [B De, v"]l (4)
closed-form
non-closed-form
Various acquisition functions (AFs) have been proposed to
balance exploration and exploitation in optimization tasks, each tailored to different problem characteristics and as- sumptions. These include Probability of Improvement (PI),
Unlike MES and its subsequent extensions (Hvarfner et al.
2022
Takeno et al. 2002) which approximate p(ya
D.. )r) using truncated Gaussian, we focus on directly
Expected Improvement (EI) (Mockus 1998 Jones et al.
estimating p(y" De, Vv) via variational inference.
1998). Upper Confidence Bound (UCB) (Srinivas al.
2010) Knowledge Gradient (KG) (Frazier et al.
20088), and
2.3. Related Work
information-theorrtic AFs /Villemonteix et al.
2009 Hen-
nig & Schuler 2012 Hernández- et al.
2014 Wang 2022). Be-
Variational Inference and Evidence Lower Bound. Variational Inference (VI) is widely used technique in Bayesian modeling to approximate intractable posterior distributions (Paisley et al.) 2012] Hoffman et al. 2013) Kingma & Welling, 2014). It relies on maximizing the Evidence Lower Bound (ELBO) to approximate the log- likelihood log p(z) in the presence of latent variables z.
& Jegelkal [2017] (017] Hyarfner et 2002 et al.
low, we discuss two types of acquisition functions relevant
to this study.
Expected Improvement. Expected Improvement (EI) is one of the most commonly used acquisition functions and formulated as follows:
The log-likelihood can decomposed as follows:
(x)( = Ep(x. (D)) [ax vi
vi,
(1)
log 2 Byy(z)
log
[p(0 z)p(z)
(5)
((2)
where oi is the maximum observed value Di, and Epc.) denotes the expectation with respect to the predictive den-
where p(z) a fixed prior distribution, and g(z) is a vari- ational approximation to the true posterior p(z #). The ELBO is formally defined as:
sity p(-). The -y term the end can be dropped since it is constant with respect to x.
((( x2)p(2)
ELBO(p(@ =x) = Ex(z)) log
Cnoormation-Thooretf AFs. Information-theore AFs form a family of methods designed to select x such
q(2)
(6)
2

---

A Unified Framework for Entropy Search and Expected Improvement
Probablistic Surrogate Conditoone
Observations One Sample (v. xx)
ply (phyyd Denshy Samples
voriance
Eperarta derrater (0/(A.
Tuncion
nauur Dt
Sample
140
030
2
Figure 1. MES aims to optimize x such that the entropy (averaged over all Uu) of the maximum values ply" Di, ) is reduced. The left figure illustrates noiseless Gaussian process conditioned on the observations Dr with three points (black crosses) and sample Yn at = drawn from p(y== (D)) (red star). The mid and right panels illustrate the density p(y" De, Va) (blue curves). When p(y" Ma) is approximated using an exponential distribution (green dashed curve), this leads to the VES-Exp AF that is equivalent to EL. Furthermore, VES- Gamma, which approximates p(y" 'Dt, yn) using a Gamma distribution (red dash-dot curve), leads to a more accurate approximation and a generalized version of EI.
By maximizing the ELBO, VI indirectly maximizes the log-likelihood log p()), thereby improving the quality of the posterior approximation. In many applications, such as variational autoencoders (VAEs) (Kingma & Welling] 2014] and variational diffusion (Kingma et al. 2021). both the conditional likelihood p( x) and the variational distribution g(z) are parameterized using neural networks. Since both the expectation reference probability and the term inside the ELBO are parameterized, one common strategy is to estimate the gradient using finite Monte Carlo samples and the reparameterization trick to optimize the parameters. We adopt this approach, which enables effi- cient gradient-based optimization and has been widely ap- plied in the BO community (Wilson et al. 2017).
contrast, MES derives an explicit approximation (Wang & Jegelka 2017 Eq. 6). which was later interpreted as a vari- ational inference formulation by Takeno al. (2020). This variational perspective has since been extended to multi- objective optimization (Qing et al.) (023). However, this approximation scheme lacks flexibility in tuning the varia- tional distributions. Furthermore, to the best of our knowl- edge, most MES-based methods focus on approximating p(ya 9", De). An exception is Ma et al. (2023), which approximates p(y" I De, Yw) using Gaussian distribu- tion. While this approach provides computational advan- tages, the inherent symmetry of the Gaussian distribution does not align with the properties of y".
3. Variational Entropy Search
Improving the Expected Improvement. It is widely recognized that EI can be prone to over-exploitation (Qin
3.1. Entropy Search Lower Bound
eet al. 2017 Berk et al.] 2019] De Ath et al.) (2021). To mitigate this issue, [Hoffman et al.) (2011) and Kan- dasamy et al. (2020) propose to use portfolio of AFs, which assigns probabilities to different AFs at each step.
The idea behind our Variational Entropy Search (VES) framework is to maximize variational lower bound of MES with a predetermined family of densities to approx- imate ply" Dr,Væ), Since we assume noiseless obser- vations, the support is [max[ trated in Figure [[] The lower bound is formalized in Theo- rem 3.1 and proven in Appendix A.
Snoek et al. (2012) proposed a fully-Bayen BByyssin treatment on El to improve empirical performance. Another ap- proach is Weighted El (WEI), which adaptively adjusts the weights of the components within the El acquisition func- tion (Sobester et al. 2005 Benjamins et al., 2023). Simi- larly, Qin et al. (2117) suggest "weakening" El using sub- optimal points suggested by the AF to mitigate its over- exploitative behavior. However, these methods are primar- ily based on heuristics. Furthermore, -nformation-thhorrtiic acquisition functions are often excluded from these design enhancements, as they are generally considered distinct from heuristic AFs such PI, EI, UCB, KG.
+o0). VES is illus-
Theorem 3.1. The MES acquisition functton in Eq. (4) ad-
heres to the Barber-Agakov (BA) bound (Barber & Agakov 2004 Poole et al. 2019) and can be bounded from below as follows:
OXMES (x) = Hly" [Da] - Epcua (D.)
[Hly De, Mer]
2 Hly" [D:] + Ep(t' un (P.) [log g(1" | Des Um))
Entropy Approximation in Information- AFs. Estimating entropy in information-theorelt acquisition functions is computationally expensive and typically re- quires approximation techniques. Methods such as ES and PES employ sampling- based approaches, including Markov chain Monte Carlo and expectation propagation. In
where q'ys | Des Ve) is any chosen density function that is absolutely continuous with respect to p(y" V..
Since the first term on the right-hand side of Eq. 7 Hly D.J, is independent of both q and æ. we can omit it. This leads us to define the remaining term as the Entropy Search
3

---

A Unified Framework for Entropy Search and Expected Improvement
Lower Bound (ESLBO):
Theorem 3.2. When the family Desp is selected as in
Eq. 9 and the function is noiseless, ESLBO in Eq.
ESLBO((;; q) == Ppper We D.) [og T(y" Dr, Wm)]
turns into
(8)
ESLBO(æ; A) log À - A Bp(o-Ip.)bl
where ply", ym D,) represents joint density, which can be sampled using Gaussian process path sam- pling (Hernández-Lobato et al. 2014 Wang & Jegelka 2017).
(10)
+ A pluaalD.) Imax(yan Man wi
ET
To optimize aMEs(a), we adopt the VI approach (Paisley al. 2012), indirectly maximizing OMMSS (a:) by instead maximizing ESLBO. To ensure computational feasibility, the VI method constrains the density q predefined fam- ily Q. When parameterizing q within Q, the problem be- comes tractable by solving for and æ iteratively, as de- tailed in Algorithm[]
Maximizing ESIBO((;; X) in Eq. (10) with respect to x and À yields the same æ solution as the maximization of EI in Eq. ①
The key idea behind the proof is that, following Algo- rithm [ the ESLBO in Eq. (10) always converges within two iterations. Regardless of the positive value of X, the value of x that maximizes ESLBO(a;; X) remains the same, Consequently, starting from an arbitrary initial point (9), positive (1) is derived, ensuring that ESLBO reaches its maximum value in the next iteration.
Notably, this procedure, known as expectation maximiza- tion (EM), is analogous to maximizing the ELBO in Eq. 5 We conclude our discussion by summarizing the correspondence between ESLBO and ELBO in Table
Theorem 3.2 reveals that EI can be viewed as special case of MES, giving a new information-theorehe interpre- tation of the most popular acquisition function in use to- day. However, the exponential distribution has fairly rigid parametric form that does not capture the characteristies of p(y" Dr, Vw)- Figure I (right) shows example of the structural limitations of the exponential density in green. We generate 1000 samples from an example distribution p(y" Dr. Un), and observe that it significantly deviates from an exponential distribution. Specifically, the density of ply" DD. yu) non-monotonic, exhibiting a peak be- fore decreasing near max v/ (approximately 1.55), while exponential distributions necessarily monotonic.
Algorithm 1 VES Framework
Input: Observations D,, variational family Q, number of inner iteration N
Output: Next sampling location 2[+1
1: initialize #:+1
2: for 1: do
3: q!") + arg @ ESLBO(# (n-1);
4: 2,+1 + arg max ESLBO(E1+11)
(n)
5: end for
(N) 6: return 2+1
3.2. EI Through the Lens of the VES Framework
This observation motivates the need to enrich the varia- tional distributions Q to allow more flexibility. A natu- ral extension is to use a Gamma distribution, which is a generalization of the exponential distribution. The Gamma density approximation in the previous example is shown in red in Figure [ (right). The next section introduces VES- Gamma, which is more general AF that extends VES-Exp and its equivalent El acquisition function.
In this section, we aim to establish an explicit connection between the VES and acquisition functions, allowing us to see EI through the lens of VI approximation of the commaationnthoorttice MES AF. We define Q as the set of all exponential density functions, 2exp: parameterized by the A > O exponential density parameter and with sup- port bounded from below by max(Nas vt }. The variational density function q is given by
3.3. VES-Gamma: A Generalization of EI
q(8 (De, Vai A) = de - 1) ( }
VES-Gamma defines Q as the Gamma distribution param- eterized by k, B > 0 with its support bounded from below by max v The variational density is
(9)
For noiseless observations, the indicator function 1y ( always equals one and can be omit- ted. Plugging in q from Eq. (9) into the ESLBO (Eq. (8) yields new X-parameterized AF. Since this AF stems from the exponential distribution, we name it VES-Exp. Theorem shows that the next sampling point generated from VES-Exp within Algorithm|] will be the same as for the EI AF; the theorem is proven in Appendix A.2
q De. Yzy k. 9)
(y" mmx (Ya vI k-
r(k)
x e Bly" - -ax-mmmxvv....mm VV. y (v
(11)
where I(.) denotes the Gamma function. The noise-free assumption allows us to omit the indicator function, and

---

A Unified Framework for Entropy Search and Expected Improvement
Table I. Comparison of key aspects between the ELBO and ESLBO approaches.
Property
ELBO Approach
ESLBO Approach
Primary Variable
p( x) g(2) (L
æ q'y" Me D.) ESLBO a))
Variational Variable
Lower Bound Formulation
the ESLBO is reformulated as
Plot of log(k) yu()
10a
ESLBO(#; 3) = k log 3 - log (A) + (A: 1) um (D.) [log (v" max Ve })
lag(k) - ((())
100
(12)
(B.()
Eyv== D.) mmx (yas Vi }]
10
EI
10-2
The ESLBO in Eq. 112 serves as the primary objective in the VES-Gamma algorithm. Eq. 12) consists of five terms, with the last term being the EI AF in Eq. ① scaled by multiplicative factor. The two hyperparameters, k and 3, originally part of the Gamma distribution, dynamically balance different components of the objective. In partic- ular, when = 1, the Gamma distribution reduces to an exponential distribution, making the ESLBO Eq. (12 equivalent Eq. (1O). In the following section, we discuss the approach for determining values for I and B.
10-3
0
100
200
300
400
500
k
Figure 2. Plot of log k - (1k) for [0, 500]. The function
strictly decreasing and asymptotically approaches zero
log k - (k) log E[ + Eloog 2g] we solve the follow-
ing optimization problem:
min (k)) + > 1)
(14)
Auto-determination of Tradeoff' Hyperparameters. For any fixed I, the global maximum of the ESLBO in Eq. T2) with respect to k and 33 uniquely exists, as can be demonstrated through derivative analysis. Taking the par- tial derivatives of ESLBO Eq. [12 and setting them to zero, we obtain:
where À is regularization parameter which is set to 1 in our experiments.
With this analysis, the value k is determined by minimiz- ing Eq. (14) using Brent's method (Brent 2013), where ex- pectations of 2 are estimated via Monte Carlo sampling from p(v", Vn (D.). Once k is obtained, the correspond- ing f follows as:
Ö log (k)
k
log 3
[log 2n1 = 0,
[2 = O.
Ōk
B
where the random variable = = "² max m J. Substituting the second equation into the first yields:
k
3
(15)
log & (b) log B[ R[log =t],
(13)
Notably, the weighting parameters K and 8 are location- dependent, = itself varies with æ. The VES-Gamma algorithm, which incorporates these principles, is detailed
where (bk = 0 log ( ak is the digamma func- tion (Abramowitz et al., 1988), which can be efficiently ap- proximated as a series. By Jensen's 's inequality, log B[=]] Ellog = 2 0. Since log k ((k) is strictly decreas- ing and approaches zero asymptotically (see Figure(]. the root Eq. (13). kig exists uniquely-excep in the de- generate case where 2 is deterministic. In the practical implementation, we apply a clamping function to ensure that the term log k (kk) does not become zero, and we employ a regularization mechanism to keep the resulting root k close to 1. Specifically, we use L2 regulariza- tion when solving log k - (k) = E[>] - E[log =*] since the unregularized version is unstable, presumably due widely flat landscape. In particular, for g(k)
in Algorithm 2
Although we provide both a theoretical justification and a practical implementation for the VES-Gamma AF, deeper interpretation of the ESLBO Eq. (12) remains an open research question. Due the complex non-linear structure of Eq. (12, it is currently uncertain if there is a clear and straightforward interpretation of the various terms and the overall expression. As an example, we hypothesize that the third term acts as an "anti-El" component, steering the DES-Gamma solution away from the El recommendation to promote diversity, with the values of B and kn dynam- ically balancing its influence. Investigating this hypothesis
5

---

A Unified Framework for Entropy Search and Expected Improvement
Algorithm 2 VES-Gamma
the GP using a 9/2-Matérn kernel with automatic relevance determination (ARD) and dimensionality-sean scale prior (Hvarfner et al., 2024). Following the theo- retical assumption in the VES framework, we only focus on experiments with noise-free observations. Although all benchmarks are noiseless, we allow the GP to accommo- date potential non-stationarity or discontinuities in the un- derlying function.
Input: Sample set Dr, number of inner iterations N
length-
Output: Next sampling location #++1
(0) 1: initialize 2++1
2: for n =1: do
3: Evaluate values of I. [=0] and [log (=+) by sam-
pling p(y", M/ D:) given - 4141 (n-1)
4: Solve k(m) from Eq. 13
5: Solve 3(m) from Eq. 15
Each experiment is repeated 10 times estimate average performance, with results reported mean + one stan- dard deviation. For problems with dimension less than 50, we run 100 iterations, otherwise 1000 iterations are computed. For numerical stability in VES-Gant TES-Gamma, we apply clamping: = = max y² max (Ve: V/ }}. The expectation in Eq. (12) is estimated via pathwise con- ditioning (Wilson al.] (22TT) using 128 posterior sam- ples. Additionally, the number of inner iterations N in Algorithm 2 is set to 5, with early stopping applied if (n - x (x)) < d 10-s, where d denotes the prob- lem dimension. We implement
6: Update xi+1 <- arg maxe ESLBO(a; k(*), g(m)
(n)
defined in Eq. 12
7: end for (N)
8: return (+1
Table 2. Average duration of a BO loop for each AF. We mea- sure the runtime on the Branin, Levy, and Hartmann bench- marks and average over benchmarks, BO iterations, and 10 ran- dom restarts. For N = 5 outer repetitions, VES has a higher runtime than the other acquisition functions.
and our other
AF
average time per BO iteration
experiments using BoTorch (Balandat et al., 2020). We always compare against LogEI (Ament et al. 2023 and
1.627s 0.916)))
use El and LogEI interchangeably. The code Is available in http:///gghbbbcomm/AOOllwttttttt -eaac-
MES VES
1.120s (744
10.910s (+.3333
Benchmarks. To evaluate VES, we consider three dis- tinet categories of benchmark problems: synthetie bench- marks, GP samples, and real-world optimization tasks.
and further elucidating the role of each term within ESLBO will be the focus of future research.
For synthetic benchmarks, we examine commonly used functions that are diverse in dimensionality and landscape complexity. Specifically, we evaluate the 2-dimensional Branin, the 4-dimensional Levy, the 6-dimensional Ha Hartmann, and the 8-dimensional Gr ewank k functions. These benchmarks ies and provide controlled testbeds for algorithmic compar- isons (Surjanovic & Bingham).
Computational Cost of VES-Gamma. Implementing in Algorithm 2 is computationally intensive. The number of inner iterations, N. must be sufficiently large for convergence, and each inner iteration requires es- timating E 2e. by sampling a large number of y". Conse- quently, the overall BO loop takes significantly more time 5. How- ever, since black-box function evaluations are often expen- sive, the additional computational cost of VES- VES-Gamma is not major bottleneck in many real-world applications.
widely utilized in optimization stud-
than and MES, as shown in Table 2 for
For GP sample benchmarks, we draw from a GP prior with v = 55/2 Matérn kernel. These experiments examine the impact of varying length scales (E {0.5, 1,2)) and di- mensionalities (d (2, 50, 100}) on algorithmic perfor- mance.
4. Results
4.1. Experimental Setup
For real-world scenarios, we utilize set of bench- marks reflecting practical high-dimensional problems. These include the 60-dimensional Rover problem (Wang) et al. 2018), the 124-dimensional soft-constrained Mopta08 (Jones 2008) benchmark introduced in Eriksson & Jankowiak (2021). the 180-dimensional Lasso-Dae problem from LassoBench (šehić et al. 2022). and the 388- 388-dimensional SVM benchmark, also introduced Eriksss son & Jankowiak (2021). These tasks represent optimiza- tion challenges in engineering design, machine learning, and computational biology.
We employ a consistent Gaussian Process (GP) hyper- parameter and prior setting across all benchmarks and acquisition functions, evaluating Bayesian optimization (BO) performance using the simple regret r(t) = f" (ax Um. where f = max (xx) When f is unknown, we instead report the negative best func- tion value, max Ve.,-
To warm-start the optimization process, we initialize with 20 random samples drawn uniformly from X' and model
6

---

A Unified Framework for Entropy Search and Expected Improvement
Due to space constraints, additional experiments are pro- vided in Appendix B
Table 3. Silmogorov-Smirmoy two-sample test passing he- tween VES-Ex/ Exp and EI for various benchmarks. More details about p-vuues are available in Figure Bj in the appendix.
4.2. Comparing VES-Exp and EI
Passing Rate (%)
Kolmogorov-Smirnov Test. After establishing the theo- retical equivalence of VES-Exp and El in Section 3.2 we aim to validate this equivalence in our practical implemen- tation. To this end, we employ the Kolmogorov-Smimoo (KS) two-sample test with a significance level of a = 5% to assess statistical similarity. The two samples consist of function values evaluated by each acquisition function (AF) across 10 repeated trials, i.e (t) == [ where y denotes the function evaluation at step / in the i-th trial. The null hypothesis states that the function evaluations from VES-Ex and EI originate from the same distribution.
Branin (d =
94.00
Hartmann (d = 6)
99.80
Rover (d 60)
92.60
Mopta08 (d 124)
93.20
Prior (d = 2)
93.60
Prior (d = 50)
94.60
On Branin,
achieves the best performance, with MES and El lagging behind. For Levy, VES-Gamma and EI are effectively tied for the best results, with MES showing slightly worse performance. On the Hartmann function, VES- FES-Gamma outperforms all other methods, Fi- nally, for the Gr ewank function, VES-Gamma and El once again demonstrate similar performance, significantly outperforming MES.
We collect function values for all 500 iterations and con- sider a test successful (pass) for each iteration if the null hypothesis not rejected. We include six differ- ent benchmarks spanning low-dimensional synthetic prob- lems to high-dimensional real-world scenarios. Additional implementation details on KS test are presented in Ap- pendix C
Overall, these results highlight the robustness of VES- Gamma across diverse synthetic benchmarks, consistently ranking among the top-performing methods.
Empirical Equivalence Results Figure illustrates the function values obtained by VES-Exp and EI, while T reports the passing rates of the KS test across six bench- marks. The results show that all passing rates exceed 90%, with the Hartmann benchmark achieving the highest pro- portion of accepted tests.
GP Samples. Here, we study problem instances where the GP can be fitted without model mismatch. To this end, we sample realizations from an isotropic 100-dimensional GP prior with varying length scale & 0.05, 0.1, 0.25, 0.5, using the same 6/2-Matérn covariance function for the GP prior and the GP we fit the observations.
Several factors explain the remaining discrepancies be- tween VES-Exp and El. First, since both acquisition func- tions are non-convex, their optimization may yield different next sampling points It+1 due to variations in initializa- tion. Second, VES methods employ clamping mechanism to ensure that = remains numerically positive, which in- troduces a dependency between y" and æ. In practice, this violates the assumptions used in the proof in (A.2 We also employed Log-EI (Ament et al., 2023) instead of El in our experiment, which may also explain the differ- ence. Finally, while EI has a closed-form expression, VES- Exp relies on Monte Carlo estimation, introducing numeri- cal inexactness and potential discrepancies.
Figure 5 shows the optimization performance on the 100- dimensional GP prior samples. For & 0.05, 0.1, 0.25, VES-Gamma outperforms El and MES by a wide margin. EI and MES converge to a suboptimal solution. Only for = 0.5 does EI reach the same quality as VES- VES-Gamma, outperforming MES.
Real-World Benchmarks. Figure presents the perfor- mance of VES-Gamma, EI, and MES across four real- world optimization problems: the 60-dimensional Rover trajectory optimization, the 124-dimensional M0pt vehicle optimization, the 180-dimensional weighted Lasso-DNA regression, and the 388 388-dimensional SVM hy- perparameter tuning benchmarks.
4.3. Performance of VES-Gamma
Synthetic Test Functions. Figure 4 illustrates the per- formance of various methods, including MES, EI, and VES-Gamma, across four synthetic benchmark functions: Branin (d = 2), Levy (d = 4), Hartmann (d = 6), and Gri ewank (d = 8). The metric shown is the loga- rithm of the best value (or simple regret), averaged over 10 independent runs.
Consistent with previous observations, VES-Gamma de- livers strong performance, significantly outperforming all other acquisition functions on the SVM benchmark. It also ranks among the top-performing methods, alongside EI, on the Mopta08 and Lasso-DNA benchmarks. On the Rover problem, VES- DES-Gamma performs comparably to EI, while MES achieves the best results in this scenario.
7

---

A Unified Framework for Entropy Search and Expected Improvement
Branin (d
Hartmann (d'= 6)
Branin (d = 2)
Levy (d = 4)
function value
10a
simple regret
10a
10
10-2
0
Hartmann (d 6)
Griewank (d 8)
Rover (d 60)
Mopta08 (d= 124)
10a
function value
30
10
simple
10a
20
400
10-3
10a
50
75
100
25
50
75
100
200
iteration
Iteration
GP sample (d= 2, 1)
GP sample
UCB
(d = 50, == 1)
VES-Gamma
function value
Figure 4. VES-Gamma, EI, and MES the synthetic Branin
0
-5-
(d = 2). Levy (d = 4), Hartmann = 6), and Gri Granwank (d 8) benchmark functions. Average log simple regret: VES- Gamma performs best on Branin and Hartmann, and competitive Levy and Grlewank.
-10
200
400
200
400
iteration
iteration
Exp-Exp
EI
Figure 3. Function values observed cach BO iteration for the El and VES-Exp acquisition functions.
Limitations and future work. While the Gamma distri- bution offers flexibility, future work will explore alterna- tive variational distributions to enhance the adaptability of VES-Gamma. Another key direction is improving compu- tational efficiency. Additionally, extending the theoretical framework to noisy settings remains an open challenge, re- quiring adaptations in variational inference account for stochastic density supports.
MES exhibits mixed performance across the benchmarks, achieving the best results on Rover but falling behind on the 88 and SVM problems.
Overall, TES-Gamma demonstrates robust and consis- tent performance across all benchmarks, establishing itself versatile and reliable acquisition function for high- dimensional real-world optimization problems.
A Acknovledgements
5. Conclusion
This project was partly supported by the Wallenberg Al, Autonomous Systems, and Software program (WASP) funded by the Knut and Alice Wallenberg Founda- tion, the AFOSR awards FA9550-20-1-0138, with Dr. Fariba Fahroo the program manager, DOE award DE- SC0023346, and by the US Department of Energy's 's Wind Energy Technologies Office. The computations were en- abled by resources provided by the National Academic In- frastructure for Supercomputing in Sweden (NAISS), par- tially funded by the Swedish Research Council through grant agreement no. 2022-06725
In this work, we introduce Variational Entropy Search (VES), a unified framework that bridges Expected Im- provement (EI) and information theoretic acquisition func- tions through a variational inference approach. We demon- strate that El can be interpreted as special case of Max- value Entropy Search (MES), revealing a deeper theoretical connection between these two widely used methodologies in Bayesian optimization. Building on this insight, we pro- pose VES-Gamma, a novel acquisition function that dy- namically balances the strengths of and MES. Compre- hensive benchmark evaluations across a diverse set of low- and nigh-dimensional optimization problems highlight the robust and consistently high performance of VES- Gamma. These results underscore the potential of the VES frame- work as a promising foundation for developing more adap- tive and efficient acquisition functions in Bayesian opti- mization.
Impact Statement
This paper presents work that aims to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
8

---

A Unified Framework for Entropy Search and Expected Improvement
GP sample (d 100, / 0.05)
GP sample
Rover (d = 60)
Mopta08 (d 124)
(d = 100, / 0.1)
20
350
best value
best va value
300
10
250
-10
-10
Lasso-DNM RINO-DNAAAA (d = 180)
SVM (d = 388)
GP sample (d 100, 0.25)
GP sample
0.350
(d = 100, 0.5)
best value
0.2
best value
0.325
0.300
0.1
-10
-10
0
250
500
750
1000
250
500 iteration
750
1000
500 iteration
750
250
1000
iteration
iteration
UCB
EI
UCB VES-Gamma
MES
VES-Gamma
MES
Figure 6. Performance curves (best function value up to each it- eration). VES-Gamma outperforms all other AFs SVM and performs well on the other problems.
Figure 5. Performance curves (best values up each iteration). VES- EES-Gamma shows superior performance on all but one problem where it performs as good as El.
Brent, R. P. Algorithms for minimization without deriva- tives. Courier Corporation, 2013.
References
Abramowitz, M., Stegun, I. A., and Romer, R. H. Hand- book of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 1988.
De Ath, G., Everson, R. M., Rahat, A. A., and Field-
send, J. E. Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation. ACM Transactions on Evolutionary Learning and Optimization, 1(1):1-22, 2021.
Ament, S., Daulton, S., Eriksson, D., Balandat, M., and Bakshy, E. Unexpected Improvements to Expected Im- provement for Bayesian Optimization. Advances in Neu- ral Information Processing Systems, 36:20577-20612, 2023.
Eriksson, D. and Jankowiak, M. High-Dimensione Bayesian Optimization with Sparse Axis- Axis-Aligned Sub- spaces. In Uncertainty in Artificial Intelligence, pp. 493- 503. PMLR, 2021.
Balandat, M., Karrer, B., Jiang, D., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A frame- work for efficient Monte-Carlo Bayesian optimization. Advances in Neural Information Processing Systems, 33: 21524-21538, 2020.
Frazier, P. I., Powell, W. B., and Dayanik, S. A Knowledge- Gradient Policy for Sequential Information Collection. SIAM Journal on Control and Optimization, 47(5): 2410-2439, 2008
Barber, D. and Agakov, F. The IM Algorithm: A varia- tional approach to Information Maximization. Advances in Neural Information Processing Systems, 16(320):201, 2004.
Golub, G. H. and Pereyra, V. The differentiation of pseudo- inverses and nonlinear least squares problems whose variables separate. SIAM Journal on Numerical Anal- ysis, 10(2):413-43,, 1973.
Benjamins, C., Raponi, E., Jankovic, A., Doerr, C., and Lindauer, M. Self-Adjusting Weighted Expected Im- provement for Bayesian Optimization. In International Conference on Automated Machine Learning, pp. 6-1. PMLR, 2023.
Hennig, and Schuler, C. J. Entropy Search for Information-Fffiiee Global Optimization. Journal of Machine Learning Research, 13(6), 2012.
Hennig, P., Osborne, M. A., and Kersting, H. P. Proba- bilistic Numerics: Computation as Machine Learning. Cambridge University Press, 2022.
Berk, J., Nguyen, V., Gupta, S., Rana, S., and Venkatesh, S. Exploration Enhanced Expected Improvement for Bayesian Optimization. In Machine Learning and Knowledge Discovery in Databases: European Con- ference, ECML PKDD 2018, Dublin, Ireland, Septem- ber 10-14, 2018, Proceedings, Part II 18, pp. 621-637. Springer, 2019.
Hemmnnezz-Lobtoo J. M., Hoffman, M. W., and Ghahra- mani, Z. Predictive Entropy Search for Efficient Global Optimization of Black-box Functions. Advances in Neu- ral Information Processing Systems, 27, 2014.

---

A Unified Framework for Entropy Search and Expected Improvement
Hoffman, M., Brochu, E., and de Freitas, N. Portfolio Allo- cation for Bayesian Optimization. In Proceedings of the Twenty-Sevene Conference on Uncertainty in Artificial Intelligence, pp. 327-336, 2011.
Paisley, J., Blei, D., and Jordan, M. Variational Bayesian
Inference with Stochastic Search. In Proceedings of the International Conference on Machine Learning, 2012.
Poole, B., Ozair, S., Van Den Oord, A., Alemi, A., and Tucker, G. On Variational Bounds of Mutual Informa- tion. In International Conference Machine Learning, pp. 5171-5180. PMLR, 2019.
Hoffman, M. D., Blei, D. M., Wang, and Paisley, J. Stochastic Variational Inference. Journal of Machine Learning Research, 2013.
Hvarfner, C., Hutter, F., and Nardi, L. Joint Entropy Search for Maximally Informedd Bayesian Optimization. Ad- vances in Neural Information Processing Systems, 35: 11494-11506, 2022.
Poon, C. and Peyré, Smooth over-parameterizer solvers for non non-smooth structured optimization. Mathematical Programming, 201(1):97-952,, 2023.
Qin, C., Klabjan, D., and Russo, D. Improving the Ex- pected Improvement Algorithm. Advances in Neural In- formation Processing Systems, 30, 2017.
Hvarfner, C., Hellsten, E. O., and Nardi, L. Vanilla Bayesian Optimization Performs Great in High Dimen- sions. In Salakhutdinov. R., Kolter, Z.. Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 20793- 20817. PMLR, 21-27 Jul 2024.
Qing, J., Moss, H. B., Dhaene, T. and Couckuyt, I. [PF] Parallel Feasible Pareto Frontier Entropy Search for Multi-Objective Bayesian Optimization. In 26th International Conference on Artificial Intelligence and Statistes (AISTATS) 2023, volume 206, pp. 2565- 2588, 2023.
Jones, D. R. Large-Scale Multi-Disciplinary Mass Opti- mization in the Auto Industry. In MOPTA 2008 Confer- ence (20 August 2008), 2008.
Rasmussen, C. E., Williams, C. K., et al. Gaussian Pro- cesses for Machine Learning, volume Springer, 2006.
Šehic. K., Gramfort, A., Salmon, J., and Nardi, L. Las- soBench: A High-Dimensional Hyperparameter Opti- mization Benchmark Suite for Lasso. In International Conference on Automated Machine Learning, pp. 2-1.
Jones, D. R., Schonlau, M., and Welch, W. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-492, 1998.
PMLR, 2022.
Kandasamy, K., Vysyaraju, K. R., Neiswanger, W., Paria, B., Collins, C. R., Schneider, J., Poczos, B., and Xing, E. P. Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Drag- onfly. Journal of Machine Learning Research, 21(81): 1-27, 2020.
Snoek, J., Larochelle, H., and Adams, R. P. Practi- cal Bayesian Optimization of Machine Learning Algo- rithms. In Pereira, F., Burges, C., Bottou, L., and Wein- berger, (eds.), Advances in Neural Information Pro- cessing Systems, volume 25. Curran Associates, Inc., 2012.
Kingma, D., Salimans, T., Poole, B., and Ho, J. Variational diffusion models. Advances in Neural Information Pro- cessing Systems, 34:21696-21707, 2021.
Sóbester, A., Leary, S. J., and Keane, A. J. On the Design of Optimization Strategies Based on Global Response Sur- face Approximation Models. Journal of Global Opti- mization, 33:31-59, 2005.
Kingma, D. and Welling, M. Auto- aaco-Enn Variational Bayes. In Bengio, Y. and LeCun, Y. (eds.), 2nd Inter- national Conference on Learning Representations, ICLR 2014, Bansf, AB, Canada, April 14- 16, 2014, Conference Track Proceedings, 2014.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In Proceedings of the International Conference on Machine Learning, 2010.
Ma, H., Zhang, T., Wu, Y., Calmon, F. P., and Li, N. Gaussian Max- Max-Value Entropy Search for Multi-Agent Bayesian Optimization. In 2023 IEEF/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 10028-10035. IEEE, 2023.
Surjanovic, S. and Bingham, D. Virtual library of sim- ulation experiments: Test functions and datasets, op- timization test problems. Ittps: //wp:://wwwww.. sfu.ca/ ssuurjes wwwprjjnoooppiiiio htmlll Accessed: 2024-09-01.
Mockus, J. The application of Bayesian methods for seek- ing the extremum. Towards global optimization, 2:117, 1998.
Takeno, S., Fukuoka, H., Tsukada, Y., Koyama, T., Shiga, M., Takeuchi, I,, and Karasuyama, M. Multi-fidelity
10

---

A Unified Framework for Entropy Search and Expected Improvement
Bayesian Optimization with Max-value Entropy Search and its Parallelization. In International Conference Machine Learning, pp. 9334-9345, PMLR, 2020.
Takeno, S., Tamura, T., Shitara, K., and Karasuyama, M. Sequential and Parallel Constrained Max-value Entropy Search via Information Lower Bound. In Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learn- ing Research, pp. 20960-20986. PMLR, June 2022.
Tu, B., Gandy, A., Kantas, N., and Shafei, B. Joint En- tropy Search for Multi-objective Bayesian Optimization. Advances in Neural Information Processing Systems, 35: 9922-9938, 2022.
Villemonteix, J., Vazquez, E., and Walter, E. An informa- tional upproach to the global optimization of expensive- to-evaluate functions. Journal of Global Optimization, 44:509-534, 2009.
Wang, Z. and Jegelka, Max-value Entropy Search for Efficient Bayesian Optimization. In International Con- ference on Machine Learning, pp. 3627-3635. PMLR, 2017.
Wang, Z., Gehring, C., Kohli, P., and Jegelka, Batched Large-scale Bayesian Optimization in High-dimensional Spaces. In International Conference on Artificial Intelli- gence and Statistics, pp. 745-754. PMLR, 2018.
Wilson, J. T., Moriconi, R., Hutter, F., and Deisenroth, M. P. The Reparameterization Trick for Acquisition Functions. In NIPS Workshop Bayesian Optimiza- tion, 2017. URL 1o ptppppprs/201//3...
Wilson, J. T., Borovitskiy, V., Terenin, A., Mostowsky, P., and Deisenroth, M. P. Pathwise Conditioning of Gaus- sian Processes. Journal of Machine Learning Research, 22(105):1-47, 2021.

---

A Unified Framework for Entropy Search and Expected Improvement
A. Proofs
A.1. ESLB Proof
The MES acquisition function in Eq. (4) can be lower bounded as follows,
Proof.
OMME (x) Hlyy" Di] p(v== D. ).) Hyy De, V/el
Hly" Dj] + Ep the (D.) (og(p(s"
De,
log plu"
Di. yv 19(3"
De, De.Bee) Mee)
Hly (D. E Pl Man (Dx)
40y Dr, (w)
IHly""
Di + E plv uo (D.) [lg(a(v")
De, Me))l + plea (D.) (RR (plv" Des Bw))l(() Des Ux))]
Hy"
D. E we (D:) log(g(v" (D: Va))).
where the KI. divergence DKL (p()))l(<())))) = Ep(a) [log((())/(z))))- The inequality is tight and only
Epina (llus/P.)le D.I (p(s") DD. Ve))ll(3" De. Ve))] O. which implies p(y" Dr. ve) qlv" De, Uw) for all yo De. 0
A.2. VES-Exp and EI Algorithmic Equivalence
Theorem 3.2 is proved follows:
Proof. By restricting the variational distributions to exponential distributions, we slightly abuse the input notations of ESLBO in g and define:
ESLBO(A, x)
Epis" .ve (.)) [log (A exp (-A(y" m 28 }))) log AEp(2 (D.) [1v" max yee vi }) log A X Bp DJ) Do)""") + Ploe (D.) [max (Va Ve 3
(16)
Beginning with an arbitrary initial value x (0), we determine the corresponding parameter
A
(17)
E Ea " (D.) [(v" max (Mm,o), vE]
which derived by taking the derivative of (16) and letting it equal zero. With X fixed, ESLBO() produces the same result as EI acquisition function in (I. We then compute (2) based on (1) following (17). Regardless of the specific value of (2)) the ESLBO function consistently yields the same result, <(1) This consistency ensures that
the VES iteration process converges in single step. The final outcome, represented (ax(1, (2)), indicates that the
corresponding q(y" Va. D:) is the closest approximation to p(y" Va. Di) within Leep (in the sense that minimizes their KI. divergence).
B. Additional Experimental Results
In this section, we evaluate VES-Gamma (Algorithm) on additional benchmarks.
12

---

A Unified Framework for Entropy Search and Expected Improvement
B.1. Synthetic Test Functions
Ackley (d
Michalewicz (d 10)
Lasso-High (d 300)
Lasso-Hard (d 1000)
best value
10a
40
60
10
100
40
x
10
20
10-1
10
20
10
10
0
50
100
100
500
1000
500 iteration
1000
iteration
iteration
iteration
MES
UCB
VES-Gamma
Figure 7. Performance plots for EI, MES, and VES-Gamma on additional synthetic benchmark functions. VES-Gamma shows robust performance throughout the bank.
Figure 7 shows the performance of the different acquisition functions, EI, MES, and VES-Gamma, on additional synthetic benchmark functions: the Ackley and Mi Michalewics oz test functions and the Lasso-Han High and Lasso-Hard bench- marks (Sehić et al. 2022). On the 1000-dimensional Lasso-Hae Hard problem, VES-Gamma ran into a timeout after 48 hours. Therefore, we plot the mean up the minimum number of iterations performed across all repetitions. VES-Gamma demonstrates robust performance across the benchmarks, outperforming all other acquisition functions Ack Ackley, MES on Mi cwwlewiawi.c cz, and performing similarly to the other acquisition functions on the Lasso benchmarks. VES-Gamma and MES perform considerably worse than TES-Gamma, especially on the more high-dimensional problems.
C. Kolmogorov-Smirnov Test Statistic
The Kolmogorov- Smimmov (KS) two-sample test non-parametric statistical method used to determine whether two samples are drawn from the same continuous distribution. It compares their empirical cumulative distribution functions (ECDFs) and calculates a test statistic that quantifies their maximum difference. Given two independent samples as function evaluations from VES-Exp (X1, X2...., Xx,) } and from EI (Y1, Y2...., Yng }, their ECDFs are defined as:
1 B1
1
82
Fx
2 I(X <x), Fy(x)
I(Y, S x),
71
n2
where I(.) is the indicator function, equal to the condition is true and 0 otherwise. The KS test statistic given by:
D = ==sup (xx()) Fy
where sup, denotes the supremum over all possible values of æ. This statistic measures the maximum absolute difference between the ECDFs the two samples.
Statistical Hypotheses.
The hypotheses for the KS test are defined as:
Null hypothesis (Ho): (x = Fy (x) for all x (the two samples come from the same distribution).
Alternative hypothesis (H.): Fx (x) f Fy (x) for at least one x (the two samples come from different distributions).
To test these hypotheses, the test p-value is solved using the Kolmogorov- survival function:
7i 1212
D)
Prest Qks
Ri + 122
13

---

A Unified Framework for Entropy Search and Expected Improvement
where (ks()) represents the survival function of the Kolmogorov distribution:
(xs(=)=2 = 2-1 2k
26
Alternativel,, the significance level = 0.05 can be tested using the critical value:
Do.05 23 In (0.025)
T1 n22
11
If D Do.os, reject the null hypothesis and consider it failure (not pass).
Detailed p-values for VES-Exp and EI Comparison. We present the p-values obtained from the experiments detailed in Section 4.2 These results are illustrated in Figure It is observed that for the majority of the sample pairs, the calculated p-values are substantially above the 5% significance level.
branin2
rover
prior sampls 2d Isl
parto
p-dda
pvskes
10
heermmenn
mopte00
prier sample
352
19.2
12.
152
p-value
p-value
pivouue
Figure 8. Distribution of p-values for 500 sample pairs generated using the El and VES-Exp acquisition functions.
D. VES-Gamma Computational Acceleration
Table 2 highlights the higher computational cost of VES methods compared to El and MES. However, observe that a technique known as Variable Projection (VarPro) GGllb & Pereyra 1973 Poon & Peyré 2023) can be leveraged to accelerate the computation of VES under certain conditions, which VES-Gamma satisfies.
The key idea behind VarPro is that when the function ESLBO has specific structure,
max (S: k) max at
max ESIBBO k) k3
(18)
((x)
and the solution to maxi,9 ESLBO((;; k 3) is unique, then (px) is differentiable, with
d θ p(x)=
ESLBO((z, kg 82).
(19)
dx dx
14

---

A Unified Framework for Entropy Search and Expected Improvement
where kt and 3 are the unique values that maximize ESLBO.
Following the proof in Eq. (3). we establish that the solutions Kg and 8r are unique. This confirms that it is feasible to implement the VarPro strategy to accelerate the computation of
eliminating the need for the iterative scheme in Algorithm 1 This ongoing work aims to reduce the computational cost of TES-Gamma to level comparable to El and
MES.
15


Reviews:
[{"review_id": "XPKqRfn7N5", "reviewer": "Reviewer_VbQ5", "summary": "This paper introduces \"Variational Entropy Search\" (VES), a unified theoretical framework that reveals a previously unrecognized connection between Expected Improvement (EI) and information-theoretic acquisition functions in Bayesian optimization. The authors demonstrate that EI, traditionally considered distinct from information-theoretic methods, can be interpreted as a variational lower bound on the Max-value Entropy Search (MES) acquisition function when using an exponential distribution as the variational distribution.\n\nBuilding on this theoretical insight, the authors propose VES-Gamma, a novel acquisition function that employs a Gamma distribution (which generalizes the exponential distribution) to approximate the maximum value distribution. This approach creates an intermediary between EI and MES that balances their respective strengths. The ESLBO (Entropy Search Lower Bound) objective in VES-Gamma includes EI as one of its components, with additional terms that dynamically adjust the exploration-exploitation trade-off.\n\nThrough empirical evaluations across low and high-dimensional synthetic benchmarks, GP samples, and real-world problems, the authors claim that VES-Gamma performs competitively with and can even outperform both EI and MES.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your support for this work. \n> the substantial computational cost disparity between VES (53.17s per iteration) versus EI/MES (~1-1.6s) limits practical applicability; the timeout issues on very high-dimensional problems (e.g., 1000D Lasso-Hard);\n\nTo address computational efficiency, we are investigating a *Variable Projection* (VarPro) method from the numerical optimization [1,2]  literature, which allows us to efficiently optimize ESLBO without compromising on performance. VarPro enables this problem reformulation: \n\n$$\\max_{\\boldsymbol{x}, k, \\beta}\\text{ESLBO}(\\boldsymbol{x}; k, \\beta) = \\max_{\\boldsymbol{x}}\\underbrace{\\max_{k, \\beta}\\text{ESLBO}(\\boldsymbol{x}; k, \\beta)}_{\\phi(\\boldsymbol{x})},$$\n\nUnder the condition that the optimal $k^\\ast$ and $\\beta^\\ast$ exist uniquely, the function $\\phi(\\boldsymbol{x})$ remains differentiable with\n$$\\nabla_{\\boldsymbol{x}}\\phi(\\boldsymbol{x}) = \\frac{\\partial \\text{ESLBO}(\\boldsymbol{x}; k^\\ast, \\beta^\\ast)}{\\partial \\boldsymbol{x}}.$$\nVarPro requires $k^\\ast$ and $\\beta^\\ast$ to be unique. While this is true for the Gamma distribution, it may no longer hold when extended to other distributions.\n\n[1] Golub, G. H. and Pereyra, V. The differentiation of pseudoinverses and nonlinear least squares problems whose variables separate. SIAM Journal on Numerical Analysis, 10(2):413–432, 1973\n\n[2] Poon, C. and Peyré, G. Smooth over-parameterized solvers for non-smooth structured optimization. Mathematical Programming, 201(1):897–952, 2023.\n\n> and the restriction to noiseless settings\n\nWe recognize that observation noise plays a crucial role in Bayesian optimization. The primary reason for assuming noiseless observations in this work is that our theoretical framework relies on this assumption. Specifically, we assume that the support of $p(y^\\ast \\mid D_t, y_x)$ is $[\\max\\{y_x, y^\\ast_t\\}, +\\infty)$, which may no longer hold if $y_x$ is noisy. \n\nWe also note that EI and MES, the acquisition functions most closely related to VES, were derived under a noise-free assumption. Furthermore, many real-world problems really are noiseless, including the benchmarks considered in our paper. Adapting VES to handle observation noise is a promising avenue for future research, and we plan to explore this direction in subsequent work.", "claims_and_evidence": "The paper's claims appear to be supported by both theoretical derivations and empirical evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria in this paper are well-aligned with its theoretical contributions and practical goals. The VES framework employs mathematically sound variational methods to establish the connection between EI and MES, while VES-Gamma represents a natural theoretical extension. The evaluation approach is appropriate, using simple regret as the performance metric and directly comparing against the most relevant baselines (EI and MES). The benchmark selection is reasonably comprehensive, spanning synthetic functions (Branin, Levy, Hartmann, Griewank), GP samples with varying length scales, and real-world problems (Rover, Mopta08, Lasso-DNA, SVM) across dimensions from 2D to 388D. This diverse test suite provides sound evidence for both the theoretical claims and practical performance benefits of the proposed approach.", "theoretical_claims": "I examined the two primary theoretical claims in the paper: Theorem 3.1 (ESLB Proof) and Theorem 3.2 (VES-Exp and EI Equivalence). Both proofs appear mathematically sound, though I note that this theoretical equivalence depends on the noiseless observation assumption, which the authors acknowledge as a limitation. The proof legitimately establishes the connection, though its practical applicability has the constraints noted by the authors. The mathematical development of both theorems appears correct and follows established techniques from variational inference.", "experimental_designs_or_analyses": "The paper employs a sound experimental methodology, evaluating algorithms across diverse benchmarks that span synthetic functions (Branin, Levy, Hartmann, Griewank), GP samples with varying dimensionality (2D to 100D), and complex real-world problems (Rover, Mopta08, Lasso-DNA, SVM) with dimensions up to 388D. The experimental protocol follows good practices including: consistent GP hyperparameter settings across all methods, proper warm-starting with 20 random samples, repeated trials (10 per experiment) with statistical reporting, and appropriate metrics (simple regret). The authors also carried out a Kolmogorov-Smirnov test validation of the theoretical equivalence between VES-Exp and EI that showed high passing rates (>90%) across all benchmarks. \n\nA few concerns worth highlighting: the substantial computational cost disparity between VES (53.17s per iteration) versus EI/MES (~1-1.6s) limits practical applicability; the timeout issues on very high-dimensional problems (e.g., 1000D Lasso-Hard); and the restriction to noiseless settings. However, these limitations are transparently acknowledged by the authors, and the overall experimental design remains sound and supports the paper's claims.", "relation_to_broader_scientific_literature": "The paper bridges a conceptual gap in Bayesian optimization by revealing that Expected Improvement and information-theoretic approaches like Max-value Entropy Search are variations of the same underlying framework rather than distinct methodologies. This theoretical unification challenges conventional wisdom in the field, where these approaches have been treated as separate paradigms, while also delivering a practical payoff through VES-Gamma, which leverages this insight to balance exploration and exploitation more effectively than either approach alone.", "essential_references_not_discussed": "No essential references appear to be missing", "other_strengths_and_weaknesses": "A notable weakness is the significant computational overhead of VES-Gamma (53.17s per iteration versus 1.63s for EI), which could limit its practical adoption despite performance gains. Additionally, the framework currently only addresses noiseless settings, an important limitation that the authors acknowledge needs addressing in future work.", "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": "", "extra_scores": {}}, {"review_id": "GwTgibdeHC", "reviewer": "Reviewer_MhFN", "summary": "The paper looks at Bayesian Optimization (BO) and tries to connect two types of acquisition functions that people have always thought of as different approaches. On one side, we have Expected Improvement (EI), which mostly focuses on exploitation by picking points that are likely to be better than what we've already found. On the other side, there are information-theoretic methods like Entropy Search and Max value Entropy Search (MES) that focus more on exploration by reducing uncertainty about where the optimum might be.\n\nWhat the authors do here is come up with a method called Variational Entropy Search (VES) that shows EI and MES are actually related. They prove that EI is basically a special case of MES when viewed through this variational inference lens. The math involves using the Barber-Agakov bound for mutual information and showing that with a particular choice of variational distribution, you get exactly the EI formula.\n\nThey also introduce VES-Gamma, which uses a Gamma distribution as the variational family. This new acquisition function can behave like EI or MES depending on the situation, so it's more flexible.\n\nThey tested VES-Gamma on a bunch of problems - toy functions, GP samples, and some real-world optimization tasks. The results show VES-Gamma generally works as well as or better than both EI and MES. It did particularly well on a 388-dimensional SVM hyperparameter tuning problem, and was among the top performers on a 124-dimensional vehicle design problem and a 180-dimensional Lasso feature selection task. So it seems to handle both low and high-dimensional problems pretty well.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the detailed comments and support on this work. Due to word limit constraints we will give brief answers:\n\n> High computational cost\n\nWe are investigating the VarPro method, as detailed in our response to reviewer VbQ5. \n\n> EGO and Snoek et al.\n\nWe will include them in the Related Work section.\n\n> How the variational parameters adapt\n\nWe agree that visualizing the evolution of $k$ and $\\beta$ would provide valuable insight, but it's challenging since their values depend on the query point $x$, which changes at each iteration. Simply showing their values at each step wouldn't effectively capture the trends.\n\nWe have put considerable effort into understanding VES-Gamma's mechanics and tried to formalize our findings into a theorem. However, we acknowledge the difficulty of doing so rigorously and will continue exploring this in future work.\n\n> More baseline\n\nDue to rebuttal time constraints, we focus on generating results using synthetic functions for UCB-0.1 and KG: https://ibb.co/4n0Nxpnv. We met numerical issues running PES and are working on fixing it.\n\n>  Why Gamma distribution \n\nWe chose the Gamma distribution because it is a generalization of the exponential distribution and it is characterized by a limited degree of freedom. We also tested the generalized Gamma distribution, but its extra flexibility prevents solving for $k$ and $\\beta$ in closed form.\n\nRegarding the impact of $k$ and $\\beta$ on exploration vs. exploitation, we hypothesize that larger $k$ promotes exploration by weakening the EI term. However, we lack strong numerical or theoretical evidence, suggesting that there is no simple relationship.\n\n> VES-Gamma-Sequential\n\nApologies for the confusion. We initially included VES-Gamma-Sequential as a potential extension of VES-Gamma but later decided to remove it due to unresolved issues. Some references were mistakenly left in the appendix, which we will remove in the final version.\n\n> Handling noise\n\nThe noiseless assumption is critical to our theoretical analysis, as detailed in our response to reviewer VbQ5.\n\n> Future direction of variational approach\n\nExtending the current work to include other acquisition functions and exploring the noisy setting, batch, multi-fidelity, and multi-objective optimization are promising future research directions.\n\n> Code release\n\nYes\n\n> Sensitivity analysis\n\nWe conducted ablation studies on two key parameters: the clamping threshold for $z_{\\boldsymbol{x}}^\\ast$ and the number of samples used to estimate the expectation. The results can be found at https://ibb.co/RpY4MXbQ and https://ibb.co/v4dsvNh4, respectively. Each experiment was repeated 10 times to compute the uncertainty bars. The findings indicate that VES-Gamma is relatively robust to variations in these parameters.\n\n> EI and VES-Exp equivalence with noise\n\nUnfortunately, in noisy settings, the current theory breaks down. Alternative approaches will be necessary to address this issue.\n\n> VES to PES\n\nThe challenge is selecting a flexible variational family that captures the characteristics of $x^\\ast$ while remaining computationally feasible. Due to the multi-modality of $x^\\ast$, a Gaussian or Beta mixture may be needed, but handling the ESLBO with a mixture density is complex. This poses a major challenge in extending VES to PES, though we remain optimistic about future research on this!\n\n> Rover problem\n\nWhile it is difficult to draw a definitive conclusion, we observe that all three methods fall within the uncertainty bounds. We will conduct additional repetitions to assess whether MES's superiority is statistically significant.\n\n> KS tests p-values \n\nMore p-value details of benchmarks are available: https://ibb.co/WpkPJqWq. This information will also be included in the appendix of the final version.\n\n> VES for KG\n\nIt is possible. The main challenge lies in designing a suitable variational family for the Knowledge Gradient acquisition function.\n\n> What problems for VES\n\nWe observe that VES-Gamma performs better in high-dimensional problems, and we believe it is well-suited for solving such problems with expensive function evaluations.", "claims_and_evidence": "The authors claim EI is actually just a special case of MES, viewed through their variational framework. They back this up with math derivations and a theorem that shows when you use an exponential variational distribution, their proposed bound optimization gives the same query point as EI. The math checks out, though it only works for noiseless observations.\n\nThey introduce VES-Gamma as a new acquisition function that tries to get the best of both EI and MES. It uses a Gamma distribution variational family (which includes exponential as a special case, so it can recover EI) but adds more flexibility to better match the true maximum value distribution. Their experiments show VES-Gamma does well - often better than both EI and MES across different test problems.\n\nFor empirical results, they've got performance curves and statistical tests showing VES-Gamma is at least competitive with, and frequently better than, both EI and MES across their benchmarks. The experimental data supports their claims pretty well. They're honest about limitations though - they note that for the Rover problem, VES-Gamma only performs about as well as EI, not beating MES.", "methods_and_evaluation_criteria": "Proposed Method:\nI think the variational inference approach to maximize the lower bound of information gain is pretty novel and makes good sense. They managed to transform that complicated nested expectation in MES into something more tractable by alternating between optimizing the variational distribution and query point. Using the Gamma family for the variational distribution seems reasonable given its flexibility in capturing the true distribution of the maximum value.\n\nEvaluation Benchmarks:\nThe experiments look good - they cover a nice range of benchmarks from low-dimensional synthetic functions to GP samples and some challenging high-dimensional real-world problems. This gives me confidence that they've tested their method under different conditions.\n\nMetrics and Procedure:\nThey're using standard metrics (simple regret/best-found value) and their experimental procedures seem appropriate - multiple trials, consistent initialization, and scaling iteration counts with dimensionality. The comparison with EI and MES baselines strengthens their findings.\n\nComparative Baselines:\nWhile they focus mainly on EI and MES (which makes sense given their paper's goals), it might have been nice to see comparisons with other methods like PES or UCB for more context.", "theoretical_claims": "I think the derivation of the variational lower bound on the MES objective looks solid - they used the Barber-Agakov bound which makes sense here. This gives them a good theoretical foundation for connecting information-based acquisition functions to variational inference approaches.\n\nTheir main theoretical result (Theorem 3.2) shows that when you use an exponential variational distribution, their method gives you exactly the same thing as EI. The math checks out, and they even verified this empirically with a Kolmogorov-Smirnov test, which is nice. Note that this only works in the noiseless setting though.\n\nFor the VES-Gamma part, they don't give us a formal theorem, but the intuition makes sense - moving from exponential to Gamma distribution lets the method capture more complex behaviors in the true distribution. The experiments back this up, so I'm convinced even without a formal proof here.", "experimental_designs_or_analyses": "The experiments are quite thorough, with tests on lots of different benchmarks. This shows the method works well in both simple and complex high-dimensional problems.\n\nAs for reproducibility, they've done a good job describing their setup - they include details about GP model settings, how they initialized everything, how many iterations they ran, and they averaged results over multiple runs. All this makes it much easier for others to reproduce their work.\n\nThe way they analyze their results seems fair to me. They're upfront about when VES-Gamma does better than other methods and when it just matches them. They also talk about runtime, showing they understand there's a computational tradeoff with their approach.\n\nI like that they used proper statistical tests (like the Kolmogorov-Smirnov test) to compare VES-Exp and EI. This gives more weight to their theoretical claims.\n\nThe main downsides I see are the high computational cost of their method and that they only tested in noiseless settings. That said, they do justify these limitations by pointing out that in typical BO applications, function evaluations are usually so expensive that the extra computational overhead isn't a big deal.", "relation_to_broader_scientific_literature": "The paper does a good job connecting two approaches that have been separate in BO for a while - the EI stuff and the information theory stuff. This unifying view is pretty novel and hasn't really been laid out clearly before.\n\nThe authors aren't working in a vacuum here - they're clearly building on previous research like Entropy Search, Predictive Entropy Search, and MES, and they bring in ideas from variational inference. Their work fits well within the field and they cite all the important papers in BO you'd expect.\n\nThey mostly focus on EI and MES in their comparisons, but they do mention other methods like GP-UCB and Knowledge Gradient in the related work section. What's nice is that instead of just heuristically combining different acquisition functions like some other work, their framework gives a more principled way to unify these approaches.", "essential_references_not_discussed": "The paper covers most of the important papers on EI, MES, and variational methods. They've cited the key works in these areas. But I think they could have mentioned the original EGO paper and maybe Snoek et al. (2012) which talks about practical BO implementation. Adding these wouldn't be essential but would help place their work better in the historical development of Bayesian optimization methods.", "other_strengths_and_weaknesses": "Strengths:\nI think the paper has several strong points. First, it's quite original - connecting EI and information-theoretic acquisition functions through this variational framework is a fresh take that nobody's really done before. This is actually a pretty significant conceptual contribution to the field.\n\nThe theoretical unification work they did and their VES-Gamma algorithm looks promising for future BO research, especially for those high-dimensional problems that are so challenging. I can see this influencing both theoretical work and practical applications going forward.\nThe writing is solid - well-structured with clear explanations and they backed everything up with detailed experiments. It's easy to follow their reasoning throughout.\n\nFinally, seeing how well their method performs on those tough high-dimensional tasks makes me think this could be really useful for real-world optimization problems where function evaluations are expensive.\n\nWeaknesses:\nThere are some limitations worth noting. The computational complexity is a big one - VES-Gamma takes more compute than EI and MES, which might make people hesitant to use it unless they can optimize it further.\n\nI found it limiting that they only tested in noiseless settings. They should extend this to noisy scenarios to make their case stronger.\nThey claim VES-Gamma dynamically balances exploration and exploitation, but don't really show us how the variational parameters adapt during the optimization process. More insight into this mechanism would help understand what's happening under the hood.\n\nWhile focusing on EI and MES makes sense, they could have included more baseline comparisons like PES, GP-UCB, or Knowledge Gradient for a more comprehensive evaluation. That would give us a better sense of where this method sits in the broader landscape.", "other_comments_or_suggestions": "More intuition about why Gamma vs. Exponential:\nThe paper should explain better why you chose the Gamma distribution and how its parameters actually balance exploration vs exploitation in practice.\n\nWhat about VES-Gamma-Sequential?:\nYou should add a short explanation of the sequential variant in the main paper - it's only in the supplement now, which isn't ideal.\n\nHandling noise?:\nThe paper only deals with noiseless settings. You should at least discuss how you might extend this to noisy observations, which is a limitation right now.\n\nFuture directions:\nHave you thought about applying your variational approach to other acquisition functions in BO? Or maybe extending to batch or multi-fidelity settings? \n\nCode release:\nWill you release your implementation for reproducibility?\n\nSensitivity analysis:\nI'd like to see some analysis of how sensitive VES-Gamma is to its hyperparameters. This would help practitioners know what to expect.", "questions_for_authors": "I'm curious about how you'd handle noisy settings with VES. Would your EI equivalence still work, or would you need a different approach?\n\nDid you look at how VES-Gamma compares to PES? Do you think your variational approach could work with PES too?\n\nWhy Gamma distribution? Did you try other variational families, and how much does performance change if you use something else?\n\nCould you show us more about how the variational parameters actually change during optimization? It would help understand how it balances exploration and exploitation in practice.\n\nFor the Rover problem, why did VES-Gamma only match EI when MES did better? Any insights on that?\n\nVES-Gamma seems computationally heavy. Any ideas on making that inner optimization loop faster?\n\nWhat were the actual numbers from your KS tests comparing VES-Exp and EI? Some p-values or pass rates would be helpful.\n\nDo you think this variational approach could work for other acquisition functions like Knowledge Gradient?\n\nGiven the computational cost, what real-world problems would benefit most from VES-Gamma, especially in high dimensions?", "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": "", "extra_scores": {}}, {"review_id": "xoRS6tbglW", "reviewer": "Reviewer_Ru8G", "summary": "The paper derives a novel variational inference scheme for optimizing the Max-value Entropy Search acquisition function in Bayesian optimization. Interestingly, for a particular choice of variational distribution, the classic Expected Improvement acquisition function shows up as a special case, thus showing it to be an approximation of MES, something not previously known. An additional MES approximation, called VES-Gamma, is developed and shows promising performance as an acquisition function.\n\n## update after rebuttal\nNo change, score already Accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support. \n\n> There is a paragraph in 4.2 describing discrepancies between VES-Exp and EI. Is the EI being used here the LogEI? Earlier in the paper it said LogEI was being used, and used interchangeably with EI. If so that would be another discrepancy potentially worth noting. Would VES-Gamma benefit from a similar strategy to improve optimize-ability?\n\nThank you for bringing this up. For the comparative analysis with VES-Exp, we used log-EI instead of EI, which could impact their empirical performance differences. We will clarify this in the final draft.\n\nApplying a similar strategy from log-EI to VES-Gamma might be possible, but the exact approach remains unclear. We plan to explore this further in future work.\n\n> If there is any commentary on the seemingly larger variance on the Hartmann6 problem that would be interesting to provide.\n\nWe believe this is due to a local optimum of the Hartmann6 function. This was discussed recently in [1].\n\n[1] Battiti, Roberto, and Mauro Brunato. \"Pushing the Limits of the Reactive Affine Shaker Algorithm to Higher Dimensions.\" arXiv preprint arXiv:2502.12877 (2025).\n\n> What are the options for improving the runtime?\n\nTo address computational efficiency, we are investigating a \\textit{Variable Projection} (VarPro) method from the numerical optimization [2,3]  literature, which allows us to efficiently optimize ESLBO without compromising on performance. VarPro enables this problem reformulation: \n\n$$\\max_{\\boldsymbol{x}, k, \\beta}\\text{ESLBO}(\\boldsymbol{x}; k, \\beta) = \\max_{\\boldsymbol{x}}\\underbrace{\\max_{k, \\beta}\\text{ESLBO}(\\boldsymbol{x}; k, \\beta)}_{\\phi(\\boldsymbol{x})},$$\n\nUnder the condition that the optimal $k^\\ast$ and $\\beta^\\ast$ exist uniquely, the function $\\phi(\\boldsymbol{x})$ remains differentiable with\n$$\\nabla_{\\boldsymbol{x}}\\phi(\\boldsymbol{x}) = \\frac{\\partial \\text{ESLBO}(\\boldsymbol{x}; k^\\ast, \\beta^\\ast)}{\\partial \\boldsymbol{x}}.$$\nVarPro requires $k^\\ast$ and $\\beta^\\ast$ to be unique. While this is true for the Gamma distribution, it may no longer hold when extended to other distributions. \n\n[2] Golub, G. H. and Pereyra, V. The differentiation of pseudoinverses and nonlinear least squares problems whose variables separate. SIAM Journal on Numerical Analysis, 10(2):413–432, 1973\n\n[3] Poon, C. and Peyré, G. Smooth over-parameterized solvers for non-smooth structured optimization. Mathematical Programming, 201(1):897–952, 2023.", "claims_and_evidence": "The paper does a thorough and rigorous job of supporting its claims that (1) EI is a variational approximation to MES, and (2) we can use the framework to develop other novel acquisition functions that perform well.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, that EI is a variational approximation for MES using an exponential distribution as the variational distribution.", "experimental_designs_or_analyses": "The empirical evaluation of the methods is satisfactory.", "relation_to_broader_scientific_literature": "The paper provides a satisfactory review of acquisition functions and the connections with information-based approaches.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The main strength of the paper is the finding that EI is equivalent to a particular variational approximation to MES. This was not obvious to me and I found it to be very insightful and interesting. I expect other people in the BO community will also be interested to see this.\n\nThe further use of the variational approximation framework to derive VES-Gamma was interesting, and I think the fact that it performs only moderately better than MES but at significantly higher computational cost is fine because it was the theoretical insight that is most valuable in the paper.", "other_comments_or_suggestions": "There is a paragraph in 4.2 describing discrepancies between VES-Exp and EI. Is the EI being used here the LogEI? Earlier in the paper it said LogEI was being used, and used interchangeably with EI. If so that would be another discrepancy potentially worth noting. Would VES-Gamma benefit from a similar strategy to improve optimize-ability?\n\nIf there is any commentary on the seemingly larger variance on the Hartmann6 problem that would be interesting to provide.", "questions_for_authors": "What are the options for improving the runtime?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work develops a variational inference approach to approximating a lower bound of Max-value Entropy Search (MES).  The authors demonstrate a novel connection between the classic EI acquisition function and MES (under the exponential variational distribution).  Reviews all found the work to be novel, insightful, and theoretically sound.  The authors demonstrate the performance of the acquisition function empirically through simulation studies on a variety of test problems of varying dimensionality.  The computational cost of the AF (and perhaps, ambiguous performance relative to other SoTA methods like Joint-Entropy Search) limit its practical use, the contribution remains clear.

The reviewers raised a number of points that are important to discuss in the CR, including discussion of limitations wrt noisy observations.  As discussed in the paper and in the reviews, the work would be more compelling if the computational cost were lower—the authors appear to have identified a promising numerical approach which I hope they are able to leverage.  Finally, additional comparisons with other AFs and perhaps the addition of a few more test problems can help readers understand where the empirical performance stacks up.
Decision: Accept (oral)