ADAPTIVE EXPERIMENTAL DESIGN FOR OPTIMIZING COMBINATORIAL STRUCTURES

Aryan Deshwal

doi:10.7273/000007039

Many real-world scientific and engineering problems can be formulated as instances of goal-driven adaptive experimental design, wherein candidate experiments are chosen sequentially, with each choice informed by the outcomes of past experiments. The objective of this sequential decision-making process is to achieve a specific goal or learn about an unknown quantity of interest in a resource-efficient manner. Different goals lead to distinct instantiations of adaptive experimental design. For instance, in active learning, the goal is to iteratively select input examples to be labeled, with the goal of learning a predictor from a hypothesis class that achieves the highest accuracy with minimum number of labeled inputs. Similarly, in bandit problems (e.g., A/B testing and advertising), the learner repeatedly chooses an arm from a set of available options, aiming to maximize the cumulative reward over time. In this dissertation, we focus on another important instantiation of adaptive experimental design: expensive black-box optimization over combinatorial spaces. In this problem setting, the goal is to identify the optimal input design within a large input design space consisting of discrete or hybrid structures, where the evaluation of each input design requires performing an experiment which is expensive in terms of the consumed resources (computational or physical). For example, in materials discovery, we are commonly interested in searching the space of candidate materials for a desired property while minimizing the total resource-cost of physical lab experiments for their evaluation. Remarkably, a large number of scientific discovery and engineering design problems including biological sequence design, nanoporous materials discovery, molecule optimization, and manycore systems design can be formulated as an instance of this general problem setting. Bayesian optimization (BO) is an effective framework for tackling the challenge of expensive black-box optimization. The key idea behind BO is to learn a surrogate model from past experiments and use it intelligently select the sequence of experiments to find high-quality inputs by minimizing the number of experiments. In spite of the huge successes of BO, current approaches focus primarily on fixed-size continuous spaces and there is little principled work on combinatorial search spaces. Unlike continuous spaces, combinatorial spaces come with many unique challenges such as difficulty of defining a general representation, non-smoothness, etc. which require specialized treatment for different types of structures (e.g., sequences, graphs, permutations etc). In this thesis, we explore and address the challenges of this new problem space by developing a series of novel approaches for Bayesian optimization over combinatorial spaces. First, we develop novel Gaussian process based surrogate models for a wide variety of combinatorial structures motivated by real-world applications (e.g., high-dimensional binary/categorical spaces, hybrid inputs containing a mixture of continuous and discrete variables, varying-sized graphs, and permutations.). Second, we developed a general tool for sampling functions from GP posteriors using explicit feature maps for discrete diffusion kernels referred to as Mercer features (analogous to random fourier features). Mercer features allow us to leverage advanced decision policies to select experiments in continuous spaces for discrete spaces. Third, we develop effective search strategies for large combinatorial spaces to select the candidate input with highest utility for experimental evaluation. For binary spaces, we showed a connection between optimization of Thompson sampling acquisition function with the binary quadratic optimization and derived an efficient submodular optimization approach. For permutation spaces, we derive a tractable approach with Thompson sampling by formulating it as a quadratic assignment problem. We also developed a general learning-to-search framework that allows using machine learning to improve the accuracy of search procedures to select inputs for evaluation. This framework is applicable for any complex surrogate model and acquisition function pair.

ADAPTIVE EXPERIMENTAL DESIGN FOR OPTIMIZING COMBINATORIAL STRUCTURES

Files and links (1)

Abstract

Metrics

Details