Predictive Entropy Search for Efficient Global Optimization of Black-box Functions

José Miguel Hernández-Lobato, Matthew W. Hoffman, Zoubin Ghahramani

TL;DR

Predictive Entropy Search (PES) is a novel acquisition function for Bayesian optimization that identifies the most informative points to evaluate by maximizing the expected information gain about the global maximum. By cleverly leveraging the symmetry of mutual information, PES provides a more accurate, computationally efficient, and fully Bayesian alternative to previous information-theoretic methods like Entropy Search.

What Problem Does This Paper Address?

In many fields—from drug discovery to tuning deep learning hyperparameters—we need to optimize "black-box" functions. These are functions where we lack a mathematical formula or derivatives; we can only "query" them by running an expensive experiment or simulation that often returns noisy results.

The goal of Bayesian Optimization (BO) is to find the global maximum of such a function using as few evaluations as possible. To do this, BO uses an "acquisition function" to decide where to sample next. Traditional acquisition functions like Expected Improvement (EI) are popular but often "greedy," getting stuck in local optima. Information-theoretic approaches, which try to sample where we learn the most about the location of the global maximum ($x_*$), are theoretically superior but have historically suffered from being computationally intractable and difficult to approximate accurately.

Methods

The authors introduce Predictive Entropy Search (PES). Its core innovation lies in how it calculates the information gain.

  1. The Symmetry Trick: Standard Entropy Search (ES) tries to compute the change in the entropy of the distribution of the location of the maximum, $p(x_*|D)$. This is incredibly hard to calculate. PES uses a property of mutual information to flip the problem: instead of looking at the entropy of the location of the max, it looks at the entropy of the predictive distribution of the function value at a candidate point, conditioned on the location of the maximum.
  2. Conditioning on the Maximum: To make this work, the authors approximate what the function looks like if we knew $x_*$ was the global maximum. They use Expectation Propagation (EP) to incorporate three constraints:
  3. $x_*$ is a local maximum (zero gradient, negative definite Hessian).
  4. The value at $x_*$ is larger than all previously observed values.
  5. The value at any other point $x$ is smaller than the value at $x_*$.
  6. Sampling the Max: To estimate the expectation over $x_*$, they use Random Fourier Features (Bochner’s theorem) to create a finite-dimensional global approximation of the Gaussian Process, allowing them to sample potential global maximizers efficiently.
  7. Fully Bayesian: Unlike previous methods, PES can easily marginalize over model hyperparameters (like kernel lengthscales) using slice sampling, making it much more robust to model mismatch.

Key Insights and Ideas

  • The "Aha" Moment: The realization that $I(x_*; y) = I(y; x_*)$. It is much easier to reason about how a fixed "global maximum" constraint changes our local predictions than it is to reason about how a single new data point changes our global belief about where the maximum is.
  • Exploration vs. Greed: PES naturally encourages exploration. While EI samples where it thinks the value is high, PES samples where the "shape" of the function is most uncertain relative to the potential maximum.
  • Conditioning "Pushes" the Function: Intuitively, conditioning on $x_*$ being the maximum "pushes" the posterior mean up at $x_*$ and "pulls" it down everywhere else. PES samples at points where this "push/pull" effect (and the resulting reduction in variance) is greatest.
Comparison of RS (ground truth), ES, and PES objectives.

Key Results

The authors evaluated PES against standard baselines (EI and ES) on a diverse set of benchmarks, including synthetic functions (Branin-Hoo, Cosines, Hartmann), machine learning hyperparameter tuning, biotechnology, finance, and robotics.

  • Higher Accuracy: As seen in the objective landscapes, PES provides a significantly closer approximation to the "ground truth" information gain (calculated via expensive Rejection Sampling, or RS) than the older ES method.
  • Superior Performance: In almost all synthetic and real-world tasks, PES achieved lower "immediate regret" (the difference between the true maximum and the recommended maximum) than ES and EI.
  • Robustness to Noise: In a robot walking task, PES significantly outperformed EI, which struggled with high noise levels.
  • Bayesian Advantage: The "PES-NB" (Non-Bayesian) variant performed worse than the full PES, proving that integrating out hyperparameters is crucial for real-world performance.
Optimization performance on Branin, Cosines, and Hartmann functions.

Limitations and Future Work

  • Computational Complexity: While more efficient than ES, PES still involves Expectation Propagation and matrix inversions. The cost scales as $O(M(n+d)^3)$, where $d$ is the dimension and $n$ is the number of points. For very high-dimensional spaces or massive datasets, this could become a bottleneck.
  • Gaussian Assumptions: The current derivation relies heavily on Gaussian likelihoods and Gaussian Processes. While the authors mention the framework can be extended to non-Gaussian likelihoods, the EP approximations would become more complex.
  • Local Max Constraints: The constraints assume the non-diagonal elements of the Hessian are zero to simplify the negative-definite requirement; a more rigorous treatment of the full Hessian might yield even better results at a higher computational cost.

Summary updated

Abstract

We propose a novel information-theoretic approach for Bayesian optimization called Predictive Entropy Search (PES). At each iteration, PES selects the next evaluation point that maximizes the expected information gained with respect to the global maximum. PES codifies this intractable acquisition function in terms of the expected reduction in the differential entropy of the predictive distribution. This reformulation allows PES to obtain approximations that are both more accurate and efficient than other alternatives such as Entropy Search (ES). Furthermore, PES can easily perform a fully Bayesian treatment of the model hyperparameters while ES cannot. We evaluate PES in both synthetic and real-world applications, including optimization problems in machine learning, finance, biotechnology, and robotics. We show that the increased accuracy of PES leads to significant gains in optimization performance.
BibTeX
@inproceedings{hernandezlobato2014predictive,
  author = {José Miguel Hernández-Lobato and Matthew W. Hoffman and Zoubin Ghahramani},
  title = {{Predictive Entropy Search for Efficient Global Optimization of Black-box Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=H1Z0kKW_WS},
}
Figure