Amortized Bayesian Optimization over Discrete Spaces

Kevin Swersky, Yulia Rubanova, David Dohan, Kevin MurphyUAI 2020

Introduction

Bayesian Optimization (BO) is a powerful framework for optimizing expensive black-box functions, particularly in scientific domains like protein engineering and molecular design. In these fields, evaluating a single candidate (e.g., a protein sequence) often requires costly and time-consuming laboratory experiments. BO addresses this by building a surrogate "oracle" model to estimate the function's landscape and using an acquisition function (AF) to identify the most promising next points to sample.

However, a significant bottleneck arises in discrete search spaces, such as strings of amino acids. Unlike continuous spaces where gradients can be used to maximize the AF, discrete spaces typically rely on "memoryless" methods like Evolutionary Algorithms (EA) or random search. These traditional solvers start from scratch in every round of BO, ignoring valuable information learned about the search space in previous iterations.

Methodology: The Deep Evolution Solver

To overcome the limitations of traditional discrete solvers, the authors propose the Deep Evolution Solver (DES). Instead of relying on random mutations, DES employs a neural network—specifically a Temporal Convolutional Network (TCN)—to predict which specific edits (such as character swaps) will most effectively improve a sequence's acquisition function score.

Schematic of the Deep Evolution inner loop, where a policy network predicts mutations to maximize the acquisition function.

The system operates through a reinforcement learning framework. The policy network is trained online using the REINFORCE algorithm, where the "reward" is defined as the improvement in the AF value following the predicted edits. To handle uncertainty, the surrogate model consists of an ensemble of Deep Neural Networks that provide both mean and variance estimates for the target function.

Amortization and the "Warm-Start"

The core innovation of this work is Amortized Bayesian Optimization (ABO). In standard BO, the inner solver is reset at the start of every round. In ABO, the weights of the DES policy network are preserved across rounds. This "warm-starting" allows the policy to become an expert on the specific problem landscape over time. As the outer BO loop progresses, the solver navigates the search space with increasing efficiency, finding high-quality candidates for the expensive oracle much faster than a solver starting from a random initialization.

Experimental Evaluation

The researchers evaluated ABO on two distinct discrete optimization tasks:

  1. Alternating Chain: A synthetic problem requiring the discovery of a string of alternating numbers, which serves as a challenging test for local search algorithms.
  2. Protein Contact Map (Potts Model): A real-world task focused on finding protein sequences that minimize folding energy based on the 5P21 protein from the Protein Data Bank. String lengths ranged from 20 to 100 characters.

Results and Discussion

ABO demonstrated significant performance leads over traditional baselines, particularly as the complexity of the search space increased. On the Protein 5P21 task, the warm-started DES reached high-value solutions in fewer than 50 iterations, whereas standard evolutionary methods required over 200 iterations to achieve comparable quality.

Performance of Deep Evolution vs. Regularized Evolution across successive outer loop iterations. Note how the Deep Evolution policy (blue) improves its starting efficiency as it 'remembers' previous rounds.

Key findings include:

  • Higher Maxima: For a length-100 Alternating Chain, ABO achieved a maximum reward of 78.33, significantly outperforming the 30.33 achieved by a standard Single Mutant Walker.
  • Efficiency: The amortization strategy allows the inner loop to converge on high-AF candidates rapidly, reducing the total computational effort required to find global optima.
  • Robustness: By learning a stochastic policy over a population, DES avoids the local optima that often trap greedy hill-climbing methods in complex protein landscapes.

Conclusion and Future Work

Amortized Bayesian Optimization represents a significant step forward in discrete black-box optimization. By treating the inner loop solver as a learnable policy rather than a static algorithm, ABO leverages the correlation between successive acquisition functions to accelerate discovery.

Future research may address the risk of the solver overfitting to an inaccurate surrogate model early in the BO process. Additionally, expanding the action space of the policy network to include complex mutations like transpositions or crossovers could further enhance the solver's exploratory capabilities.

Summary updated

BibTeX
@inproceedings{swersky2020amortized,
  author = {Kevin Swersky and Yulia Rubanova and David Dohan and Kevin Murphy},
  title = {{Amortized Bayesian Optimization over Discrete Spaces}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
}
Figure