More Like this

1. Quality-Weighted Vendi Scores And Their Application To Diverse Experimental Design

   Nguyen, Quan; Dieng, Adji_Bousso (July 2024, MLR)

   Experimental design techniques such as active search and Bayesian optimization are widely used in the natural sciences for data collection and discovery. However, existing techniques tend to favor exploitation over exploration of the search space, which causes them to get stuck in local optima. This collapse problem prevents experimental design algorithms from yielding diverse high-quality data. In this paper, we extend the Vendi scores—a family of interpretable similarity-based diversity metrics—to account for quality. We then leverage these quality-weighted Vendi scores to tackle experimental design problems across various applications, including drug discovery, materials discovery, and reinforcement learning. We found that quality-weighted Vendi scores allow us to construct policies for experimental design that flexibly balance quality and diversity, and ultimately assemble rich and diverse sets of high-performing data points. Our algorithms led to a 70%–170% increase in the number of effective discoveries compared to baselines. 

   more » « less
2. Nonmyopic Multifidelity Acitve Search

   Nguyen, Q; Modiri, A; Garnett, R (January 2021, Proceedings of Machine Learning Research)

   null (Ed.)

   Active search is a learning paradigm where we seek to identify as many members of a rare, valuable class as possible given a labeling budget. Previous work on active search has assumed access to a faithful (and expensive) oracle reporting experimental results. However, some settings offer access to cheaper surrogates such as computational simulation that may aid in the search. We propose a model of multifidelity active search, as well as a novel, computationally efficient policy for this setting that is motivated by state-of-the-art classical policies. Our policy is nonmyopic and budget aware, allowing for a dynamic tradeoff between exploration and exploitation. We evaluate the performance of our solution on real-world datasets and demonstrate significantly better performance than natural benchmarks. 

   more » « less
3. Cost effective active search

   Jiang, Shali; Moseley, Benjamin; Garnet, Roman (January 2019, Advances in Neural Information Processing Systems)

   We study a special paradigm of active learning, called cost effective active search, where the goal is to find a given number of positive points from a large unlabeled pool with minimum labeling cost. Most existing methods solve this problem heuristically, and few theoretical results have been established. We adopt a principled Bayesian approach for the first time. We first derive the Bayesian optimal policy and establish a strong hardness result: the optimal policy is hard to approximate, with the best-possible approximation ratio lower bounded by Ω(n^0.16). We then propose an efficient and nonmyopic policy using the negative Poisson binomial distribution. We propose simple and fast approximations for computing its expectation, which serves as an essential role in our proposed policy. We conduct comprehensive experiments on various domains such as drug and materials discovery, and demonstrate that our proposed search procedure is superior to the widely used greedy baseline. 

   more » « less
4. Collective Progress: Dynamics of Exit Waves

   https://doi.org/10.1086/724321  

   Cetemen, Doruk; Urgun, Can; Yariv, Leeat (September 2023, Journal of Political Economy)

   We introduce a framework for studying collective search by teams. Discoveries are correlated over time and governed by a Brownian path, where search speed is jointly controlled. Agents individually choose when to cease search and implement their best discovery. We characterize equilibrium and optimal policies. Search speeds are constant within active alliances and depend on complementarities between members. A drawdown stopping boundary governs each agent’s search termination. The consequent exit waves, whereby possibly heterogeneous agents cease search simultaneously, exhibit deterministic sequencing but stochastic timing. We highlight environments with lower than optimal equilibrium speeds and search durations, and different exit waves. 

   more » « less
5. Adaptive Experimental Design with Temporal Interference: A Maximum Likelihood Approach

   Glynn, Peter W; Johari, Ramesh; Rasouli, Mohammad (January 2020, Advances in neural information processing systems)

   Suppose an online platform wants to compare a treatment and control policy (e.g., two different matching algorithms in a ridesharing system, or two different inventory management algorithms in an online retail site). Standard experimental approaches to this problem are biased (due to temporal interference between the policies), and not sample efficient. We study optimal experimental design for this setting. We view testing the two policies as the problem of estimating the steady state difference in reward between two unknown Markov chains (i.e., policies). We assume estimation of the steady state reward for each chain proceeds via nonparametric maximum likelihood, and search for consistent (i.e., asymptotically unbiased) experimental designs that are efficient (i.e., asymptotically minimum variance). Characterizing such designs is equivalent to a Markov decision problem with a minimum variance objective; such problems generally do not admit tractable solutions. Remarkably, in our setting, using a novel application of classical martingale analysis of Markov chains via Poisson's equation, we characterize efficient designs via a succinct convex optimization problem. We use this characterization to propose a consistent, efficient online experimental design that adaptively samples the two Markov chains. 

   more » « less