Discovering Many Diverse Solutions with Bayesian Optimization

Natalie Maus, Kaiwen Wu, David Eriksson, Jacob R. Gardner

Abstract

Bayesian optimization (BO) is a popular approach for sample-efficient optimization of black-box objective functions. While BO has been successfully applied to a wide range of scientific applications, traditional approaches to single-objective BO only seek to find a single best solution. This can be a significant limitation in situations where solutions may later turn out to be intractable, for example, a designed molecule may turn out to later violate constraints that can only be evaluated after the optimization process has concluded. To address this issue, we propose rank-ordered Bayesian Optimization with trustregions (ROBOT) which aims to find a portfolio of high-performing solutions that are diverse according to a user-specified diversity measure. We evaluate ROBOT on several real-world applications and show that it can discover large sets of high-performing diverse solutions while requiring few additional function evaluations compared to finding a single best solution.

Introduction: The Need for a "Plan B"

In fields like drug discovery or engineering, the "optimal" solution found by an algorithm often fails when it hits the real world. A molecule might have the highest predicted antibiotic activity but turn out to be toxic to humans—a constraint that is often too expensive to simulate during the initial optimization phase. Standard BO is "all-or-nothing": it focuses its entire budget on finding a single global maximum. If that point is a bust, practitioners must restart the expensive search process.

While one could try to find multiple solutions, simply looking for the "top $M$ points" usually results in a cluster of nearly identical candidates. To be useful, a set of solutions must be diverse—meaning they are different enough that if one fails for a specific reason, the others are unlikely to share that same flaw. The challenge is that diversity is a moving target; whether a new point is diverse depends entirely on the points already chosen, making this a much harder problem than standard constrained optimization.

Methodology: Rank-Ordered Bayesian Optimization (ROBOT)

We introduce ROBOT (Rank-Ordered Bayesian Optimization with Trust regions), which builds on the TuRBO algorithm by using local "trust regions" to navigate high-dimensional spaces. ROBOT maintains $M$ simultaneous local optimization runs (trust regions) ranked 1 to $M$.

Conceptual overview of ROBOT's hierarchical rank-ordering and diversity constraints.

Key innovations include:

  • Hierarchical Rank-Ordering: The first trust region is unconstrained and seeks the global optimum. Every subsequent region $i$ is constrained to stay a certain "diversity distance" ($\tau$) away from the solutions found by all higher-ranked regions ($1$ to $i-1$).
  • Asymmetric Constraints: By only forcing lower-ranked regions to move away from higher-ranked ones, the algorithm ensures that the search for the absolute best solution is never hindered by the requirement for diversity.
  • Global Surrogate Model: ROBOT uses a single global Gaussian Process (specifically a Parametric GP or PPGPR). This allows all trust regions to share information, meaning a region can learn from the "failures" or "successes" of its neighbors.
  • Greedy Re-centering: At each step, the algorithm re-evaluates the best diverse set of points found so far across the entire history and moves the centers of the trust regions to these points.

Experimental Evaluation

ROBOT was evaluated on several complex, high-dimensional tasks, including Rover Trajectory Optimization (60D), Lunar Lander control policies, and Molecular Design (Guacamol Benchmark).

Performance comparison and robustness analysis on the Lunar Lander task.

Key Results

  • Near-Zero Overhead: In molecular tasks, ROBOT-100 (finding 100 solutions) converged to the global optimum almost as fast as standard BO (finding 1 solution). The "extra" evaluations used to find diverse solutions actually help refine the global model.
  • Robustness: In the Lunar Lander task, an ensemble created from 20 diverse ROBOT policies never failed to land on 200 new environments. In contrast, individual policies found by standard BO without diversity constraints occasionally crashed when faced with environmental variations.
  • Semantic Diversity: Unlike previous "quality-diversity" algorithms that define diversity simply as distance in the input space, ROBOT allows for arbitrary, user-defined diversity measures, such as molecular fingerprint similarity.

Discussion and Limitations

ROBOT demonstrates that finding 50 or 100 diverse solutions doesn't have to be 50 or 100 times harder than finding one. However, the method assumes the diversity function $\delta(x, x')$ is computationally cheap to evaluate. If calculating diversity is as expensive as the objective function itself, the overhead would increase significantly. Additionally, the user must provide a diversity threshold $\tau$; choosing an appropriate $\tau$ requires domain knowledge to ensure solutions are meaningfully diverse without making the search space infeasible.

Conclusion

ROBOT provides a robust framework for discovering a portfolio of high-performing, diverse solutions. By leveraging hierarchical constraints and a shared global model, it offers practitioners a reliable set of "backup plans" with minimal computational overhead compared to traditional single-objective Bayesian optimization.

Summary updated

Abstract

Bayesian optimization (BO) is a popular approach for sample-efficient optimization of black-box objective functions. While BO has been successfully applied to a wide range of scientific applications, traditional approaches to single-objective BO only seek to find a single best solution. This can be a significant limitation in situations where solutions may later turn out to be intractable, for example, a designed molecule may turn out to later violate constraints that can only be evaluated after the optimization process has concluded. To address this issue, we propose rank-ordered Bayesian Optimization with trustregions (ROBOT) which aims to find a portfolio of high-performing solutions that are diverse according to a user-specified diversity measure. We evaluate ROBOT on several real-world applications and show that it can discover large sets of high-performing diverse solutions while requiring few additional function evaluations compared to finding a single best solution.
BibTeX
@inproceedings{maus2023discovering,
  author = {Natalie Maus and Kaiwen Wu and David Eriksson and Jacob R. Gardner},
  title = {{Discovering Many Diverse Solutions with Bayesian Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=R37fo0ml33},
}
Figure