A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization

A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization

Speakers: Nuojin Cheng, Leonard Papenmeier, Stephen Becker, Luigi Nardi

Conference: ICML 2025

YouTube: https://slideslive.com/39044071

Overview

This talk introduces a groundbreaking unified framework, Variational Entropy Search (VES), that bridges the conceptual and practical gap between two of the most prominent acquisition functions in Bayesian Optimization (BO): Expected Improvement (EI) and Max Value Entropy Search (MES). Presented by Nuojin Cheng and Leonard Papenmeier, with co-authors Stephen Becker and Luigi Nardi, the work reinterprets EI not merely as an intuitive heuristic focused on immediate gains, but as a specific variational approximation of MES, an information-theoretic approach aimed at reducing uncertainty about the function's global maximum.

The significance of this research is profound. By revealing the underlying connection between EI and MES, the authors provide a deeper theoretical understanding of why EI has been so empirically successful. More importantly, this unification is not just an academic exercise; it serves as a foundational insight for developing a new generation of more powerful and flexible acquisition functions. The talk showcases VES-Gamma, a novel acquisition function derived from this framework, demonstrating its superior performance across a diverse set of synthetic and real-world black-box optimization problems, particularly excelling in scenarios with challenging function landscapes.

Background

▶ Watch: Introduction to Bayesian Optimization and its steps (0:00)

Bayesian Optimization (BO) is a powerful strategy for optimizing expensive, black-box functions, widely used in hyperparameter tuning, experimental design, and robotics. It operates iteratively through a three-step cycle. First, based on a few initial observations of the unknown function, a probabilistic surrogate model is constructed, typically a Gaussian Process (GP). This model not only estimates the function's value but also quantifies the uncertainty associated with those estimates. Second, an acquisition function (denoted as $\alpha$) is employed to guide the selection of the next point to sample. The acquisition function strategically balances exploration (sampling in uncertain regions to reduce overall uncertainty) and exploitation (sampling near current high-value regions to improve the observed maximum). The point $x$ that maximizes this acquisition function is then chosen. Finally, the true black-box function is evaluated at this selected point, the result is added to the observations, and the cycle repeats.

Among the myriad of acquisition functions, two stand out for their distinct philosophies and widespread use:

1. Expected Improvement (EI): This is arguably the most classic and widely adopted acquisition function. Its objective is straightforward and intuitive: at each iteration, EI seeks the point $x$ that is expected to yield the largest improvement over the current best observed function value, denoted as $y_t^*$. Mathematically, it integrates the potential improvement weighted by the probability of that improvement occurring, making it a greedy yet effective heuristic.

1. Max Value Entropy Search (MES): In contrast to EI's focus on immediate value improvement, MES takes an information-theoretic approach. Its goal is to select the next sampling point $x$ that will maximally reduce the uncertainty about the function's global maximum value, $y^$, which is treated as a random variable. The underlying principle is to gain as much information as possible about the location of the true optimum. While conceptually elegant, the direct computation of MES, particularly the entropy of $y^$, presents significant computational challenges due to its complex integral form.

Despite their individual successes and distinct theoretical underpinnings, the relationship between EI and MES has historically been unclear. They originate from different schools of thought—value-based heuristics versus information theory—leaving practitioners and researchers without a unified understanding of their respective strengths and the conditions under which one might be preferred over the other. This lack of a cohesive framework has limited the potential for systematic development of new, more robust acquisition functions that could potentially combine the benefits of both approaches.

Key Findings

▶ Watch: Introducing Variational Entropy Search (VES) framework (2:20)

The central contribution of this work is the introduction of Variational Entropy Search (VES), a novel framework that fundamentally unifies Expected Improvement (EI) and Max Value Entropy Search (MES). The core insight is that EI can be reinterpreted as a specific variational approximation of MES. This discovery is formalized through several key findings:

1. EI as a Variational Approximation of MES: The most profound finding is the mathematical equivalence established between maximizing a specific Entropy Search Lower Bound (ESLBO) derived within the VES framework and maximizing the standard EI acquisition function. Specifically, under noiseless observation conditions, when the variational distribution Q is chosen from the family of shifted exponential distributions, the ESLBO simplifies such that its maximization becomes identical to maximizing EI scaled by a positive constant $\lambda$. This is encapsulated in Theorem 32, which states that maximizing this particular ESLBO is mathematically equivalent to maximizing standard EI. This provides a new, deeper understanding of why EI is so effective in practice: its intuitive value-based heuristic is implicitly performing an information-theoretic optimization.

1. Derivation of VES-Gamma for Enhanced Flexibility: Building upon the foundational insight that EI is a variational approximation, the authors developed VES-Gamma. This acquisition function leverages a richer, more flexible variational family—the Gamma distribution—instead of the simpler exponential distribution used to derive EI. This increased flexibility allows VES-Gamma to better approximate the true distribution of $y^*$, leading to more nuanced and effective exploration-exploitation trade-offs. Crucially, the hyperparameters of the Gamma distribution (k and beta) are not set manually but are automatically evaluated at each step with uniquely determined closed-form solutions, simplifying its practical application.

1. Superior or On-Par Performance Across Diverse Benchmarks: Experimental evaluations demonstrate that VES-Gamma consistently performs on par with or significantly outperforms existing state-of-the-art acquisition functions like EI and MES across a wide array of benchmarks. This includes low-dimensional synthetic functions (e.g., Hartmann, Branin), high-dimensional real-world problems (e.g., MOPTA08, SVM), and challenging Gaussian process sample paths, particularly those with very short length scales where EI often struggles due to numerical instability or inherent limitations. This empirical validation underscores the practical utility and robustness of the VES framework and its derived acquisition functions.

1. Addressing Short Length Scale Challenges: A notable discovery is VES-Gamma's ability to effectively optimize problems characterized by much shorter length scales in Gaussian Process models. In these scenarios, the function can exhibit rapid changes, making optimization challenging. Traditional EI often becomes competitive only on longer length scales (e.g., 0.5), whereas VES-Gamma demonstrates strong performance even at very short length scales (e.g., 0.05), indicating its superior capability in navigating complex, highly non-linear landscapes.

Technical Deep Dive

▶ Watch: Profound takeaway: EI is a variational approximation of MES (5:45)

The Variational Entropy Search (VES) framework reframes the challenging problem of computing the entropy of the function's maximum value, $y^$, central to MES. The core idea is to approximate the intractable true distribution of $y^$ with a simpler, tractable variational distribution Q. By doing so, the problem of maximizing MES is converted into maximizing a variational lower bound of the MES acquisition function, which the authors term the Entropy Search Lower Bound (ESLBO). This is a standard approach in variational inference.

The process begins by assuming noiseless observations, which simplifies the support of $y^$. The main challenge with MES is the direct computation of $H(y^)$, the entropy of $y^$. To circumvent this, a variational distribution $Q(y^)$ is introduced to approximate the true posterior distribution of $y^$, $p(y^|D)$, where $D$ represents the observed data. The goal then becomes to maximize the ESLBO with respect to both the parameters of $Q$ and the next sampling point $x$ iteratively.

To build intuition for selecting an appropriate family for $Q$, the authors make two key observations about the true $y^*$ distribution:

1. The true maximum $y^$ must be at least as large as both the predicted function value at the new point $x$, $y(x)$, and the current best observation $y_t^$. This is because under noiseless conditions, the probabilistic surrogate model (Gaussian Process) must pass through the observed points. Therefore, $y^ \ge \max(y(x), y_t^)$.
2. While $y^$ could theoretically be much larger, its high-density region is likely concentrated just above this lower bound $\max(y(x), y_t^)$.

These observations guide the choice of $Q$.

VES-Exponential: Unifying EI and MES

The first instantiation of VES, VES-Exponential, selects $Q$ from the family of exponential distributions, shifted to start at the known lower bound $\max(y(x), y_t^)$. An exponential distribution is a single-parameter family, which respects the intuition that the density of $y^$ is concentrated just above the current maximum.

When this specific exponential distribution is plugged into the ESLBO formula and simplified, a remarkable result emerges: the ESLBO expression breaks down into three components:

1. A term solely related to the variational parameter $\lambda$ of the exponential distribution.
2. A constant term independent of the choice of $x$.
3. The Expected Improvement (EI) acquisition function, scaled by $\lambda$.

This implies that if $\lambda$ is fixed to be a positive value, maximizing this particular ESLBO is mathematically equivalent to maximizing the standard EI acquisition function. Furthermore, the authors demonstrate that an optimal $\lambda$ can be found in closed-form by simple derivative analysis of the formula. This structural property guarantees that if an Expectation-Maximization (EM) algorithm is applied to maximize the ESLBO, it will converge in just two steps.

This leads directly to Theorem 32, which rigorously formalizes this connection: under noiseless conditions, maximizing the specific ESLBO derived with a shifted exponential variational distribution is mathematically equivalent to maximizing the standard EI acquisition function. This theorem provides the profound insight that EI, a seemingly intuitive value-based heuristic, is in fact implicitly performing information-theoretic optimization as a variational approximation of MES.

VES-Gamma: Enhanced Flexibility

Recognizing that the true density of $y^*$ is not always monotonically decreasing—a characteristic assumed by the exponential distribution—the authors developed VES-Gamma. This variant introduces more flexibility by choosing $Q$ from the Gamma distribution family, parameterized by $k$ (shape) and $\beta$ (rate). The Gamma distribution is a richer family capable of modeling a wider variety of density shapes.

When the Gamma distribution is used to derive the ESLBO for VES-Gamma, the resulting expression is more complex than that for VES-Exponential. However, it still contains the familiar EI term, indicating its lineage from the unified framework. A key advantage of VES-Gamma is that the hyperparameters $k$ and $\beta$ do not need to be hand-tuned. Instead, they can be automatically evaluated at each optimization step, as they also possess uniquely determined closed-form solutions. This automatic adaptation of the variational distribution's parameters allows VES-Gamma to better fit the true $y^*$ distribution, leading to more robust and effective acquisition.

Surrogate Model and Numerical Stability

The underlying probabilistic surrogate model utilized throughout the experiments is a Gaussian Process (GP), a standard choice in Bayesian Optimization. For specific benchmarks, a Matérn 5/2 kernel is employed, known for producing functions that are twice differentiable, offering a good balance between smoothness and expressiveness.

Regarding numerical stability, especially when comparing against EI, the authors clarify that for EI benchmarks, they employed the numerically more stable LogEI acquisition function. This detail is crucial because standard EI can suffer from numerical issues, particularly on functions with short length scales, which could artificially depress its performance. By using LogEI, the comparison with VES-Gamma is made on a more level playing field, highlighting the inherent strengths of the proposed method rather than mere numerical artifacts.

Experimental Setup & Results

▶ Watch: Introducing VES-Gamma for enhanced flexibility (6:05)

The evaluation of VES-Exponential and VES-Gamma was comprehensive, spanning a diverse set of benchmarks designed to test performance across various problem characteristics, dimensions, and complexities. Comparisons were primarily made against the two foundational acquisition functions: Expected Improvement (EI) and Max Value Entropy Search (MES). The metric used for evaluating optimization performance was simple regret, defined as the difference between the best observed function value and the true best function value; lower values indicate better performance. Additionally, runtime was tracked for synthetic benchmarks to assess computational overhead.

Benchmarks

The experiments were conducted on three categories of problems:

1. Low-Dimensional Synthetic Benchmarks: Four well-known synthetic functions were used: Levy, Griewank, Hartmann, and Branin. These functions are commonly used in optimization research due to their known global optima and varying degrees of multi-modality and ruggedness.

1. High-Dimensional Real-World Problems:

• Rover: A 2D trajectory planning problem where the goal is to find a path between start and end points while avoiding obstacles.
• MOPTA08: A complex engineering optimization problem focused on reducing the mass of a car chassis. It involves 124 design variables and 68 black-box constraints, which were incorporated as soft constraints into the objective function.
• Lasso-DNA: A microbiology classification problem solved using weighted Lasso regression, where the goal is to find optimal regularization parameters.
• SVM: A hyperparameter optimization task for a Support Vector Machine classifier on the CT slice dataset, aiming to find the best configuration for classification performance.

1. Gaussian Process Sample Paths: To evaluate performance on functions with varying degrees of smoothness and complexity, 100-dimensional Gaussian Process sample paths were generated. A Matérn 5/2 kernel was used, and the length scales were varied significantly: 0.05, 0.1, 0.25, and 0.5 (from top left to bottom right in the presentation's visual aids). This specifically tests the acquisition function's ability to handle functions with rapid changes (short length scales) versus smoother variations (longer length scales).

Key Results

1. Runtime Performance:

• VES-Gamma (and presumably VES-Exponential) was found to be approximately one order of magnitude slower than EI and MES on synthetic benchmarks. This increased runtime is attributed to the alternating optimization process required for VES, which iteratively finds the best sampling point $x$ and the optimal variational parameters ($k$ and $\beta$ for Gamma, or $\lambda$ for Exponential).

1. Performance on Low-Dimensional Synthetic Benchmarks:

• On Levy and Griewank, VES-Gamma performed as well as EI, indicating competitive performance on these standard test functions.
• On Hartmann and Branin, VES-Gamma achieved a considerably lower simple regret than both EI and MES, demonstrating its superior ability to locate the optimum on these more challenging multi-modal landscapes.

1. Performance on High-Dimensional Real-World Problems:

• Rover: VES-Gamma performed similarly to EI, while MES showed the best overall performance. This suggests that for certain trajectory optimization tasks, an information-theoretic approach directly targeting uncertainty reduction might still hold an edge.
• MOPTA08: VES-Gamma and EI exhibited similar strong performance, significantly outperforming MES by a wide margin. This highlights the effectiveness of the EI-like component within VES-Gamma for complex, constrained, high-dimensional problems.
• Lasso-DNA: Again, VES-Gamma and EI performed similarly and both outperformed MES.
• SVM: VES-Gamma delivered a strong performance, outperforming both EI and MES by a considerable margin, showcasing its effectiveness in hyperparameter optimization.

1. Performance on Gaussian Process Sample Paths (Varying Length Scales):

• This experiment revealed a significant advantage for VES-Gamma. It demonstrated the ability to optimize problems with much shorter length scales (e.g., 0.05, 0.1).
• In contrast, Expected Improvement (EI) only became competitive on longer length scales (e.g., 0.5). This indicates that VES-Gamma is more robust to highly complex, rapidly changing function landscapes, where the GP surrogate model's predictions can be highly localized and challenging for traditional EI to navigate. The authors suggest that the Monte Carlo aspects of their acquisition function, which can lead to less flat acquisition surfaces, might contribute to its strong performance on short length scale problems, potentially mitigating some of the numerical issues known with analytic EI in such scenarios.

In summary, the experimental results consistently position VES-Gamma as a highly competitive, if not superior, acquisition function, especially on complex synthetic and real-world problems, and critically, on functions exhibiting fine-grained structure (short length scales). The primary trade-off is its increased computational cost compared to traditional EI and MES.

Practical Implications

▶ Watch: VES-Gamma outperforms on Hartmann and Branin benchmarks (7:50)

The introduction of the Variational Entropy Search (VES) framework and the subsequent development of VES-Gamma carry several significant practical implications for practitioners, infrastructure teams, model builders, and deployers working with Bayesian Optimization:

1. Deeper Understanding and Justification for EI's Effectiveness: The most profound implication is the revelation that Expected Improvement (EI) is not just a heuristic but a specific variational approximation of Max Value Entropy Search (MES). This provides a robust theoretical foundation for EI's widespread empirical success. Practitioners can now understand that when using EI, they are implicitly performing an information-theoretic optimization to reduce uncertainty about the global maximum, albeit with a simpler variational family. This deeper understanding can guide more informed choices in algorithm selection.

1. Systematic Framework for Developing New Acquisition Functions: VES offers a principled, systematic methodology for deriving novel and potentially more powerful acquisition functions. By exploring different variational families (beyond exponential and Gamma), researchers and developers can design acquisition functions tailored to specific problem characteristics or computational constraints. This moves beyond ad-hoc design to a more structured approach, potentially accelerating innovation in BO.

1. Improved Performance for Challenging Optimization Problems: VES-Gamma has demonstrated superior or on-par performance across a wide range of benchmarks, particularly excelling in scenarios involving highly non-linear functions and those with short length scales. This means that for complex hyperparameter optimization tasks, black-box engineering design problems, or any application where the objective function is expensive and difficult to model, VES-Gamma offers a strong candidate for achieving better optimization outcomes with fewer function evaluations. This can lead to significant cost savings and faster convergence to optimal solutions.

1. Trade-offs: Performance vs. Computational Cost: A critical practical consideration is the increased computational overhead of VES-Gamma, which is approximately an order of magnitude slower than EI and MES. For very expensive black-box functions where each evaluation takes hours or days, this additional computation for the acquisition function might be negligible. However, for functions that are relatively inexpensive to evaluate, or when running BO on a large scale, this slowdown could be a limiting factor. Infrastructure teams and model deployers must weigh the benefits of improved optimization performance against the increased computational resources and time required per BO iteration.

1. Current Limitations and Future Directions for Robustness: The current theoretical analysis of VES is limited to noiseless scenarios. In many real-world applications, observations are inherently noisy, which can significantly impact the performance of BO algorithms. This limitation means that while VES-Gamma performs well in current benchmarks, its direct applicability to noisy environments without further theoretical extension is not guaranteed. Practitioners need to be aware of this and await future work that addresses noisy observations. The authors acknowledge this as a key area for future research, along with exploring techniques like variable projection to reduce the computational overhead.

In essence, VES provides both a retrospective understanding of past successes and a prospective blueprint for future advancements in Bayesian Optimization. It empowers practitioners with more effective tools, while also highlighting important trade-offs and areas for continued research and development to make these powerful methods even more robust and widely applicable.

Key Takeaways

• Unified Framework: The Variational Entropy Search (VES) framework successfully unifies Expected Improvement (EI) and Max Value Entropy Search (MES), two distinct philosophies in Bayesian Optimization.
• EI as Variational Approximation: A core finding is that EI is mathematically equivalent to a specific variational approximation of MES, providing a deeper information-theoretic understanding of EI's practical effectiveness.
• VES-Gamma for Enhanced Performance: By using a more flexible Gamma distribution as the variational family, VES-Gamma systematically improves upon EI, offering superior or on-par performance across diverse synthetic and real-world benchmarks.
• Robustness to Short Length Scales: VES-Gamma demonstrates a significant advantage in optimizing functions with very short length scales, outperforming EI which struggles in such highly complex, rapidly changing landscapes.
• Computational Trade-off: While offering performance benefits, VES-Gamma introduces an increased computational cost, being approximately an order of magnitude slower than EI and MES due to its iterative alternating optimization procedure.
• Noiseless Assumption: The current theoretical analysis of VES is limited to noiseless observations, indicating a need for future research to extend the framework's applicability to common real-world noisy scenarios.

About the Speaker(s)

The talk on "A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization" was a collaborative effort by Nuojin Cheng, Leonard Papenmeier, Stephen Becker, and Luigi Nardi. Nuojin Cheng introduced the theoretical underpinnings of the Variational Entropy Search (VES) framework and its connection to Expected Improvement. Leonard Papenmeier subsequently presented the implementation details and comprehensive experimental results of VES-Gamma across various benchmarks. As co-authors and presenters at ICML 2025, they are researchers actively contributing to advancements in Bayesian Optimization and machine learning.