When optimizing an expensive black-box function—whether tuning a machine learning model's hyperparameters or designing a physical airfoil—we rely on a surrogate model (typically a Gaussian Process) to guide our search. The core challenge lies in the acquisition function: the mathematical policy that decides exactly where to sample next based on the surrogate's predictions.
Traditional acquisition functions, such as Expected Improvement (EI) or Upper Confidence Bound (UCB), operate on a local, greedy heuristic. They look for points that are expected to immediately outperform the current best observed value. While intuitive, this local focus can cause the optimization process to stall in sub-optimal regions.
Information-theoretic acquisition functions reframe the entire objective of sequential optimization. As reviewed by Jin et al., instead of asking "where can we find a higher value?", these methods ask "what point will tell us the most about the global optimum?". By treating the global optimum as a hidden, latent variable, they select evaluation points that maximize the mutual information between the next observation and the optimum itself. This is equivalent to maximizing the expected reduction in the entropy (uncertainty) of the optimum's distribution.
The Core Intuition: Global Uncertainty Reduction
To understand why this works, imagine trying to find the highest peak in a mountain range hidden by thick fog. A greedy strategy like EI is akin to walking uphill from your current position; you will quickly find the top of the nearest hill, but you might miss a massive peak just one valley over.
An information-theoretic strategy, by contrast, aims to clear the fog across the entire mountain range as efficiently as possible. Contal et al. demonstrated that targeting this global uncertainty reduction provides powerful theoretical guarantees, outperforming standard heuristics by scaling exploration adaptively based on information already gathered.
By prioritizing points that yield the highest information gain about the global maximum, the algorithm naturally balances exploration and exploitation. As shown by Hernández-Lobato et al., this global perspective prevents the optimization process from converging prematurely on local optima, a chronic failure mode for greedy strategies.
The Computational Bottleneck of Input-Space Search
The earliest formulations of this idea, such as Entropy Search and Predictive Entropy Search (PES) developed by Hernández-Lobato et al., focused on the location of the global maximizer, denoted as $x^*$. They measured how much a candidate observation would shrink the probability density of $x^*$'s coordinates.
This approach is highly effective for global exploration. For instance, Hoffman demonstrated that tracking the entropy of $x^*$ allows algorithms to navigate complex search spaces effectively even before a single feasible solution is identified, making it ideal for heavily constrained problems. It has been successfully deployed to minimize physical trials when tuning robotic controllers (Marco et al.) and to coordinate parallel batches of experiments (Shah et al.).
However, calculating the entropy of $x^*$ requires approximating a probability distribution over the entire input space. As the dimensionality of the input space grows, sampling or approximating the distribution of $x^*$ becomes an intractable computational burden. The algorithm can end up spending more time computing where to sample next than it takes to run the actual expensive black-box evaluation.
Shifting Focus to the Output Space
To bypass this curse of dimensionality, researchers introduced a clever mathematical twist: instead of measuring information gain about where the optimum is ($x^*$), measure information gain about what the optimum value is ($f^*$). This paradigm is known as Max-value Entropy Search (MES).
As Ru et al. and Moss et al. explain, shifting the target to the function's maximum value collapses the entropy calculation from a high-dimensional input space down to a simple, one-dimensional integral in the output space.
Input-Space Entropy Search (PES):
[Candidate Point x] ---> Computes Entropy of Location x* (High-Dimensional Integral)
Output-Space Entropy Search (MES):
[Candidate Point x] ---> Computes Entropy of Value f* (1D Integral)
Why does knowing the maximum value $f^*$ help us find the optimum location? Intuitively, knowing the peak value heavily constrains the possible shapes of the objective function. If the surrogate model learns that the global maximum value is likely around a high threshold, any input region whose predicted upper bound is lower than that threshold can be immediately discarded. This allows the algorithm to rule out vast swaths of the search space implicitly, achieving the same exploratory benefits as input-space searches at a fraction of the computational cost.
Scaling to Multi-Objective Optimization
The elegance of the output-space paradigm becomes even more apparent when scaling to multi-objective optimization (MOO), where the goal is to find the Pareto front—the set of optimal trade-offs between conflicting objectives (e.g., maximizing engine performance while minimizing fuel consumption).
Early information-theoretic multi-objective methods like PESMO, introduced by Hernández-Lobato et al., targeted the entropy of the Pareto optimal set of inputs. Just like single-objective PES, this suffered from severe scaling issues in high-dimensional design spaces.
By shifting the information metric to the output space, Belakaria et al. developed MESMO, which calculates entropy reduction directly on the estimated Pareto front of objective values. Because the number of competing objectives is typically much smaller than the number of raw input parameters, this approach completely decouples the optimization overhead from the input dimensionality.
The authors (Deshwal et al.; Deshwal et al.) formalized this into a unified Output Space Entropy (OSE) framework. By evaluating how much a candidate point reduces uncertainty about the boundary of the Pareto front, the search process focuses entirely on mapping out the global trade-off structure. Suzuki et al. further refined this by deriving closed-form solutions for entropy within the objective space, eliminating the need for computationally unstable approximations and making the framework practical for complex engineering applications.
Synergistic Uncertainty Reduction: Joint Entropy Search
While output-space methods are computationally efficient, focusing exclusively on either the location $x^*$ or the value $f^*$ leaves valuable information on the table. To capture the full picture, Hvarfner et al. proposed Joint Entropy Search (JES), which considers the joint probability density of both the optimal input location and the optimal function value $(x^*, f^*)$ simultaneously.
The intuition behind JES is deeply synergistic:
- Knowing the predicted height of a peak ($f^*$) helps narrow down its possible coordinates ($x^*$).
- Knowing the likely coordinates of the peak ($x^*$) helps pin down its height ($f^*$).
By simultaneously reducing uncertainty about both variables, JES avoids the exploratory blind spots of focusing on either variable in isolation. This joint consideration provides a more comprehensive measure of global uncertainty, making the optimization process highly robust against noise while remaining computationally efficient.
This joint paradigm represents the modern frontier of the field, having been successfully extended by Fernández-Sánchez et al. to handle complex real-world scenarios that simultaneously involve multiple objectives, unknown constraints, and multi-fidelity evaluations.
Key Foundational Work
Entropy Search for Information-Efficient Global Optimization (2011) — contributed 2 concept elements to this direction.
A framework for optimization under limited information (2013) — contributed 2 concept elements to this direction.