Nonmyopic Multifidelity Acitve Search

Quan Nguyen, Arghavan Modiri, Roman GarnettICML 2021 · OpenReview

Introduction

In fields like drug discovery and materials science, researchers often search for "needles in a haystack"—rare molecules or alloys with highly specific, desirable properties. Traditionally, this involves active search: sequentially picking a data point, testing it with an expensive "oracle" (like a lab experiment), and using the result to inform the next choice.

The primary bottleneck in this process is cost, as high-fidelity lab experiments are slow and expensive. However, researchers frequently have access to "low-fidelity" surrogates, such as computational simulations, which are cheap and fast but less accurate. This paper introduces MF-ENS (Multifidelity Expected Number of Successes), a novel algorithm designed to solve the multifidelity active search problem. By intelligently balancing a strict experimental budget between expensive, high-fidelity (H) tests and cheap, low-fidelity (L) tests, MF-ENS significantly boosts discovery rates. Unlike "greedy" methods that only look one step ahead, MF-ENS uses a nonmyopic, budget-aware strategy to plan for long-term success.

Methods: The MF-ENS Algorithm

The authors frame the active search problem using Bayesian decision theory. Because calculating the mathematically optimal policy is computationally intractable—requiring a lookahead through every possible future outcome—they propose MF-ENS as an efficient approximation.

Key technical components of the algorithm include:

  • Two-Stage Rollout: To decide the next query, the algorithm simulates a future scenario. It assumes that after the current query, it will perform a batch of cheap L-fidelity queries to gather information, followed by a final batch of H-fidelity queries to "collect" targets.
  • Nonmyopic Planning: By considering the remaining budget, the algorithm naturally transitions from exploration (using cheap queries to learn the landscape) to exploitation (using expensive queries on the most promising candidates).
  • Multifidelity k-NN: The standard k-nearest neighbor classifier is extended to handle data from multiple fidelities, utilizing a damping factor to account for the lower reliability of the noisy oracle.
  • Efficient Pruning: To handle massive datasets (100,000+ points), the authors implement "branch-and-bound" pruning. This allows the algorithm to skip calculating scores for points that mathematically cannot be the best next choice.
Illustration of the multifidelity query schedule where the high-fidelity oracle is slower than the low-fidelity one.

Experimental Setup

The researchers evaluated MF-ENS on three scientific discovery benchmarks:

  1. BindingDB (Drug Discovery): Searching for chemical compounds that bind to specific proteins, using 50 different protein targets and 100,000 compounds from the ZINC database.
  2. BMG (Materials Science): Searching for alloys capable of forming "Bulk Metallic Glasses," prized for their toughness, across a dataset of over 106,000 alloys.
  3. Simulated Noise: To systematically test the algorithm, they simulated low-fidelity oracles by taking true labels and "flipping" them based on a controllable noise parameter.

Key Insights and Results

MF-ENS consistently outperformed all baselines, including state-of-the-art single-fidelity methods and common multifidelity heuristics like Upper Confidence Bound (UCB).

The Value of "Cheap" Information: Even highly noisy simulations drastically improved the efficiency of expensive experiments. On the drug discovery datasets, MF-ENS found roughly 10–15% more targets than the single-fidelity baseline given the exact same high-fidelity budget. Ignoring low-fidelity data proved to be a significant missed opportunity.

Patience Pays Off: Myopic (greedy) policies tend to pick points with the highest immediate probability of being a target. MF-ENS, however, often starts by querying points it is uncertain about. This early "exploration" phase builds a robust model, leading to a much higher "catch rate" in the final stages of the search. As the budget vanishes, the algorithm becomes increasingly greedy, perfectly adapting its behavior to the remaining time.

MF-ENS initially explores points with lower probabilities, eventually overtaking greedy baselines to achieve higher overall utility.

Statistical tests (paired t-tests) confirmed that these performance gains were highly significant, returning p-values of less than $10^{-5}$ across the experiments.

Limitations and Future Work

While highly effective, the current MF-ENS model has a few limitations:

  • Synchronous Assumption: The model assumes a fixed ratio ($k$) between the speed of the two oracles. Adapting the algorithm for asynchronous queries—where experiments finish at irregular, unpredictable times—is a promising direction for future research.
  • Independence Heuristic: To keep the math tractable, the policy assumes labels are conditionally independent during the "lookahead" phase. A more complex model of label correlation could potentially yield even better results.
  • Real-world Noise: The study primarily relied on simulated noise for the low-fidelity oracle. Testing the algorithm on datasets with "natural" multifidelity labels (e.g., comparing a coarse physics simulation directly to a fine-grained one) remains an important next step for real-world deployment.

Summary updated

BibTeX
@inproceedings{nguyen2021nonmyopic,
  author = {Quan Nguyen and Arghavan Modiri and Roman Garnett},
  title = {{Nonmyopic Multifidelity Acitve Search}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=txFhi_1KfX},
}
Figure