In traditional global optimization, the goal is usually framed as finding the input $x$ that produces the best output $f(x)$. Most common strategies, like Expected Improvement, are "greedy" in the sense that they look for points likely to be better than the current best. However, a powerful alternative perspective treats optimization not as a search for high values, but as an information-gathering task.
This direction, often called Information-Theoretic Bayesian Optimization or Entropy Search, focuses on reducing uncertainty about the "answer" to our problem. Instead of asking "Where is the function value high?", these methods ask "Which measurement will tell me the most about the location or value of the global optimum?"
The Shift from Values to Distributions
The foundational insight, championed by Philipp Hennig and Christian J. Schuler in Entropy Search for Information-Efficient Global Optimization, is to maintain a probability distribution over the location of the global optimum $x^*$.
In standard Bayesian Optimization, we use a Gaussian Process to model the function $f$. Entropy Search goes a step further: it uses that model to induce a distribution over where the maximum might be. The "best" next point to evaluate is the one that maximizes the Information Gain—the expected reduction in the entropy of our belief about $x^*$. This approach is often more data-efficient because it avoids over-exploring regions that are already known to be sub-optimal, even if they have high variance.
Refining the Target of Information
While searching for the location $x^*$ is principled, it is computationally expensive because $x^*$ is a $d$-dimensional vector. Researchers have since developed more efficient "targets" for information gain:
- Max-value Entropy Search (MES): Zi Wang and Stefanie Jegelka proposed shifting the focus from the location $x^*$ to the maximum value $f^*$ in Max-value Entropy Search for Efficient Bayesian Optimization. Since $f^*$ is always a 1D scalar regardless of the input dimensions, estimating its entropy is significantly faster and more robust.
- Joint Entropy Search (JES): Carl Hvarfner showed in Joint Entropy Search For Maximally-Informed Bayesian Optimization that we can get the best of both worlds. By considering the joint distribution of $(x^*, f^*)$, the algorithm uses the predicted height of a peak to narrow down its possible locations, and vice versa, leading to even faster convergence.
Bayesian Algorithm Execution
The most recent evolution of this idea moves beyond simple optimization. In many scientific fields, we don't just want the "maximum"; we want to know a property of the function that requires an algorithm to compute, such as the shortest path in a graph or the top-k ranking of items.
Willie Neiswanger and Stefano Ermon formalized this as Bayesian Algorithm Execution (BAX). In BAX, the acquisition function maximizes the mutual information between a new observation and the final output of a specific algorithm.
For example, in Targeted materials discovery using Bayesian algorithm execution, Yue Wu demonstrates that instead of hand-crafting complex math for a new problem, a scientist can simply provide a script (the algorithm) that defines their goal. BAX then automatically identifies which experiments will most quickly reveal the algorithm's result.
Applications in Human-Centric and Multi-Objective Search
Because information-theoretic methods are fundamentally about "pruning" a hypothesis space, they are uniquely suited for problems where the "measurements" are complex or come from humans:
- Preference Learning: When a human can't give a score but can say "I prefer A over B," methods like those in PrefGen by Alec Helbling use information gain to select the most "confusing" pairs to show the user, quickly bisecting the search space to find their ideal image or setting.
- Multi-objective Trade-offs: In problems with competing goals (like speed vs. cost), Amar Shah and Anoop Shah developed PESMO, which maximizes information gain about the entire Pareto frontier. This allows the optimizer to map out the entire trade-off surface rather than just finding a single point.
- Medical Diagnosis: Chitta Baral and Hong Guan applied these principles to automated differential diagnosis, where the system "interviews" a patient by selecting the medical test that maximizes the expected information gain regarding the latent disease state.
By treating every evaluation as an optimal experiment, information-theoretic approaches provide a unified framework for solving expensive black-box problems across domains as diverse as particle physics, cognitive science, and materials engineering.