Scalable Combinatorial Bayesian Optimization with Tractable Statistical models
We study the problem of optimizing expensive blackbox functions over combinatorial spaces (e.g., sets, sequences, trees, and graphs). BOCS (Baptista and Poloczek, 2018) is a state-of-the-art Bayesian optimization method for tractable statistical models, which performs semi-definite programming based acquisition function optimization (AFO) to select the next structure for evaluation. Unfortunately, BOCS scales poorly for large number of binary and/or categorical variables. Based on recent advances in submodular relaxation (Ito and Fujimaki, 2016) for solving Binary Quadratic Programs, we study an approach referred as Parametrized Submodular Relaxation (PSR) towards the goal of improving the scalability and accuracy of solving AFO problems for BOCS model. PSR approach relies on two key ideas. First, reformulation of AFO problem as submodular relaxation with some unknown parameters, which can be solved efficiently using minimum graph cut algorithms. Second, construction of an optimization problem to estimate the unknown parameters with close approximation to the true objective. Experiments on diverse benchmark problems show significant improvements with PSR for BOCS model. The source code is available at https://github.com/aryandeshwal/Submodular_Relaxation_BOCS .
Code (1)
Tasks
Bayesian OptimizationSimilar Papers 제목 키워드 기반
Mercer Features for Efficient Combinatorial Bayesian Optimization
Bayesian optimization (BO) is an efficient framework for solving black-box optimization problems with expensive function evaluations. This paper addresses the BO problem setting for combinatorial spaces (e.g., sequences …
Bayesian OptimizationThompson SamplingOptimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design
Bayesian optimization (BO) is a powerful framework to optimize black-box expensive-to-evaluate functions via sequential interactions. In several important problems (e.g. drug discovery, circuit design, neural architectur…
Bayesian OptimizationDrug DiscoveryNeural Architecture SearchProtein DesignScalable Bayesian inference for the generalized linear mixed model
The generalized linear mixed model (GLMM) is a popular statistical approach for handling correlated data, and is used extensively in applications areas where big data is common, including biomedical data settings. The fo…
Bayesian InferenceUncertainty QuantificationBayesian Optimization of Combinatorial Structures
The optimization of expensive-to-evaluate black-box functions over combinatorial structures is an ubiquitous task in machine learning, engineering and the natural sciences. The combinatorial explosion of the search space…
Bayesian OptimizationBIG-bench Machine LearningA Bayesian approach for prompt optimization in pre-trained language models
A prompt is a sequence of symbol or tokens, selected from a vocabulary according to some rule, which is prepended/concatenated to a textual query. A key problem is how to select the sequence of tokens: in this paper we f…
Bayesian OptimizationCombinatorial OptimizationLanguage ModellingLarge Language Model