Scalable Combinatorial Bayesian Optimization with Tractable Statistical models
arXiv:2008.08177
Abstract
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 .
15 pages, 12 figures
References in corpus (8)
- Practical Bayesian Optimization of Machine Learning Algorithms
- A Tutorial on Bayesian Optimization
- Bayesian optimization for materials design
- Max-value Entropy Search for Efficient Bayesian Optimization
- Predictive Entropy Search for Multi-objective Bayesian Optimization
- A General Framework for Multi-fidelity Bayesian Optimization with Gaussian Processes
- Combinatorial Bayesian Optimization using the Graph Cartesian Product
- Arch2030: A Vision of Computer Architecture Research over the Next 15 Years
Cited by in corpus (5)
- Max-value Entropy Search for Multi-Objective Bayesian Optimization with Constraints
- Information-Theoretic Multi-Objective Bayesian Optimization with Continuous Approximations
- Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces
- Bayesian Optimization over Hybrid Spaces
- Explaining Inference Queries with Bayesian Optimization