Adaptive Experimental Design for Optimizing Combinatorial Structures

Janardhan Rao DoppaIJCAI 2021 · DOI

TL;DR

This paper tackles the challenge of optimizing complex, discrete, or hybrid structures (like molecules or hardware designs) using expensive experiments. The authors present a framework for adaptive experimental design, primarily through Bayesian Optimization, that intelligently selects which experiments to run to find optimal solutions efficiently, saving time and resources. Their work extends traditional Bayesian Optimization to handle combinatorial spaces and multi-objective problems, with applications in areas like electronic design automation and materials science.

What Problem Does This Paper Address?

Many real-world optimization problems involve searching through vast spaces of "combinatorial structures." These structures aren't simple numbers but complex entities like sequences, trees, graphs, or combinations of discrete and continuous variables. Think about designing a new drug molecule, optimizing the placement of components on a computer chip, or finding the best mix of microbes for a microbiome. The catch is that evaluating each potential design (e.g., through a simulation or a lab experiment) is incredibly expensive, consuming significant time and resources.

Traditionally, engineers and scientists have relied on intuition and heuristic methods to navigate these spaces. This paper argues for a more principled, data-driven approach: adaptive experimental design. The core problem is how to intelligently choose which experiments to perform to maximize the information gained about the objective function, thereby finding the best solution with the fewest, most informative experiments. This is particularly challenging when dealing with discrete or hybrid search spaces, which are less amenable to standard optimization techniques.

Methods

The paper's central theme is the application and extension of Bayesian Optimization (BO) to combinatorial and hybrid spaces. BO is a powerful framework for optimizing expensive black-box functions. Its key components are:

  1. Surrogate Model: A cheap-to-evaluate statistical model (often a Gaussian Process) is built from past experimental data to approximate the expensive objective function.
  2. Acquisition Function: This function uses the surrogate model to quantify the utility of evaluating a candidate input. It balances exploration (trying new, uncertain areas) and exploitation (refining known good areas).
  3. Acquisition Function Optimizer: An algorithm to find the input that maximizes the acquisition function.

The authors highlight several novel contributions and extensions:

  • BO over Discrete Spaces: They address the challenge of defining surrogate models and acquisition function optimizers for discrete structures. Techniques like L2S-DISCO (Learning-to-Search for Discrete Structures) use a learning-to-search framework to guide combinatorial search. MerCBO (Mercer Features for Combinatorial Bayesian Optimization) leverages "Mercer features" to bridge discrete and continuous spaces, allowing the use of more sophisticated acquisition functions.
  • BO over Hybrid Spaces: For problems with mixed discrete and continuous variables, they propose HyBO, which uses additive Gaussian Process kernels based on diffusion kernels to define a principled surrogate model.
  • Multi-Objective Bayesian Optimization (MOBO): Many real-world problems require optimizing multiple conflicting objectives (e.g., performance vs. power). They introduce USeMO (Uncertainty-aware Search for Multi-Objective Optimization) and MESMO (Max-value Entropy Search for Multi-Objective Optimization), which efficiently explore the Pareto front without reducing the problem to a single objective. They also extend these to handle multi-fidelity (varying accuracy/cost of experiments) and constrained optimization.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic framework and its application to various domains, rather than specific benchmark datasets.

Key Insights and Ideas

  • Bridging Discrete and Continuous: The concept of "Mercer features" is a key insight, allowing the powerful tools developed for continuous BO to be applied to discrete and combinatorial spaces. This is a significant step towards unifying BO techniques.
  • Intelligent Search for Discrete Spaces: Simply applying continuous BO methods to discrete spaces is often inefficient. The "learning-to-search" paradigm (L2S-DISCO) offers a more adaptive and effective way to navigate these complex spaces by learning how to guide the search process.
  • Handling Conflicting Goals: Multi-objective BO is crucial for many practical applications. The proposed USeMO and MESMO methods provide principled ways to find the trade-offs between objectives, rather than forcing a single "best" solution.
  • Information Gain as a Guiding Principle: The MESMO approach, focusing on maximizing information gain about the Pareto front, is a powerful strategy for efficient multi-objective optimization, even working well with minimal computational samples.
  • The Power of Domain Knowledge: The paper emphasizes that combining domain knowledge with data-driven BO is essential for tackling complex real-world problems, particularly in areas like materials science and catalysis.

Key Results

The paper describes the development of several novel algorithms (L2S-DISCO, MerCBO, HyBO, USeMO, MESMO, and their constrained/multi-fidelity variants) and demonstrates their effectiveness in addressing the challenges of combinatorial and hybrid optimization. While specific quantitative results are not detailed in this summary, the paper indicates that these approaches have achieved "good results" and "excellent results" in various applications, leading to more efficient design optimization and accelerating research and development. The authors also proved asymptotic regret bounds for USeMO, providing theoretical guarantees for its performance.

Limitations and Future Work

The authors acknowledge several areas for future work:

  • Representations: Developing effective representations that combine domain knowledge and data is crucial for applications in catalysis and materials science.
  • Algorithmic Advancements: Further research is needed for batch BO, scalability to high-dimensional combinatorial spaces, and incorporating resource constraints.
  • Theoretical Guarantees: There's a lack of theoretical studies characterizing the efficacy of BO algorithms for discrete and hybrid spaces.
  • Benchmarks: The community needs challenging, easy-to-use benchmarks to evaluate and compare existing and new methods.
  • Declarative Languages: Developing languages to specify combinatorial spaces and constraints would facilitate adoption by domain experts.
  • Tractable Acquisition Functions: Exploring the use of random Fourier features and Mercer features for HyBO to achieve tractable acquisition function optimization is a promising direction.

Summary updated

BibTeX
@inproceedings{doppa2021adaptive,
  author = {Janardhan Rao Doppa},
  title = {{Adaptive Experimental Design for Optimizing Combinatorial Structures}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/699},
}
Figure