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

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

Problem Statement
Bayesian Optimization (BO) is a standard technique for optimizing expensive black-box functions, relying on acquisition functions (AFs) to balance exploration and exploitation. Two dominant paradigms exist:

1. Expected Improvement (EI): A heuristic-based AF that maximizes the expected improvement over the current best observed value. It is computationally efficient and widely used but is often viewed as fundamentally distinct from information-theoretic methods.
2. Information-Theoretic AFs (e.g., Max-value Entropy Search - MES): These methods aim to reduce uncertainty about the location or value of the global optimum using entropy-based measures. While theoretically grounded, they are often considered distinct from EI due to differing underlying philosophies.

The prevailing perspective in the BO community treats EI and information-theoretic AFs as separate methodologies. This paper challenges that view, arguing that a deeper theoretical connection exists between them that has been previously unrecognized.

Methodology: Variational Entropy Search (VES)
The authors introduce Variational Entropy Search (VES), a unified theoretical framework that interprets EI as a variational inference approximation of the information-theoretic Max-value Entropy Search (MES).

• Theoretical Unification: The framework establishes a lower bound for the MES acquisition function using the Barber-Agakov (BA) bound. By defining a variational family $Q$ to approximate the conditional density $p(y^* | D_t, y_x)$ (where $y^*$ is the global maximum value), the authors derive an Entropy Search Lower Bound (ESLBO).
• Recovering EI: When the variational family $Q$ is restricted to exponential distributions, the ESLBO maximization yields a solution identical to the standard Expected Improvement (EI). This proves that EI is a special case of MES under a specific variational approximation.
• VES-Gamma: Recognizing that the exponential distribution is too rigid to capture the true structure of $p(y^* | D_t, y_x)$ (which is often non-monotonic), the authors propose VES-Gamma. This new AF uses a Gamma distribution as the variational family. The Gamma distribution generalizes the exponential distribution, allowing for a more flexible approximation that better captures the density's shape.
• Optimization: The VES-Gamma algorithm employs an Expectation-Maximization (EM) style approach. It iteratively:
  1. Estimates the parameters ($k, \beta$) of the Gamma distribution that maximize the ESLBO for a fixed candidate point $x$.
  2. Updates the candidate point $x$ to maximize the ESLBO given the current parameters.
     The parameters $k$ and $\beta$ are determined automatically via derivative analysis and regularization, dynamically balancing the components of the objective function.

Key Contributions

1. Unified Framework: The introduction of the VES framework, which demonstrates that EI is a variational approximation of MES, thereby unifying two previously distinct acquisition function paradigms.
2. Novel Acquisition Function: The proposal of VES-Gamma, an AF that inherits the performance strengths of EI while incorporating information-theoretic principles through a more flexible Gamma variational approximation.
3. Comprehensive Evaluation: Extensive empirical evaluations across low- and high-dimensional synthetic benchmarks, Gaussian Process (GP) samples, and real-world problems.

Results
The paper evaluates VES-Gamma against EI, MES, and other state-of-the-art methods (such as UCB and LogEI) across diverse benchmarks:

• Synthetic Benchmarks: On functions like Branin, Levy, Hartmann, and Griewank, VES-Gamma consistently performs competitively. It achieves the best performance on Branin and Hartmann, while matching or slightly outperforming EI on Levy and Griewank.
• GP Samples: In experiments with 100-dimensional GP priors, VES-Gamma significantly outperforms both EI and MES for smaller length scales ($\ell = 0.05, 0.1, 0.25$), where EI and MES tend to converge to suboptimal solutions.
• Real-World Benchmarks: On high-dimensional problems (60D Rover, 124D Mopta08, 180D Lasso-DNA, 388D SVM), VES-Gamma demonstrates robust performance. It significantly outperforms all other methods on the SVM benchmark and ranks among the top performers on Mopta08 and Lasso-DNA.
• Theoretical Validation: A Kolmogorov-Smirnov test confirms the empirical equivalence between VES-Exp (the exponential variant) and EI, with passing rates exceeding 90% across various benchmarks.

Significance and Claims
The paper claims that the VES framework provides a novel theoretical insight: the most popular acquisition function (EI) is not fundamentally distinct from information-theoretic methods but is rather a specific variational approximation of them.

By bridging these perspectives, the authors present VES-Gamma as a robust, versatile acquisition function that effectively balances the strengths of both EI (performance and simplicity) and MES (uncertainty reduction). The results suggest that VES-Gamma is a strong candidate for diverse optimization problems, particularly in high-dimensional settings where traditional methods may struggle. The authors note that while VES-Gamma incurs a higher computational cost per iteration than EI or MES, this is often negligible compared to the cost of evaluating expensive black-box functions in real-world applications. Future work is identified as exploring alternative variational distributions and extending the framework to noisy settings.