Bayesian Optimization of Combinatorial Structures

Abstract

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 and costly evaluations pose challenges for current techniques in discrete optimization and machine learning, and critically require new algorithmic ideas. This article proposes, to the best of our knowledge, the first algorithm to overcome these challenges, based on an adaptive, scalable model that identifies useful combinatorial structure even when data is scarce. Our acquisition function pioneers the use of semidefinite programming to achieve efficiency and scalability. Experimental evaluations demonstrate that this algorithm consistently outperforms other methods from combinatorial and Bayesian optimization.

arXiv commentPublished at International Conference on Machine Learning 2018

References in corpus (9)

• Practical Bayesian Optimization of Machine Learning Algorithms
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
• A simple sampler for the horseshoe estimator
• Improving Object Detection with Deep Convolutional Networks via Bayesian Optimization and Structured Prediction
• Raiders of the Lost Architecture: Kernels for Bayesian Optimization in Conditional Parameter Spaces
• A Tutorial on Thompson Sampling
• A Stratified Analysis of Bayesian Optimization Methods
• A Kernel for Hierarchical Parameter Spaces

Cited by in corpus (28)

• High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces
• Application of QUBO solver using black-box optimization to structural design for resonance avoidance
• Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining
• Ludwig: a type-based declarative deep learning toolbox
• Scalable Constrained Bayesian Optimization
• Bayesian Variational Autoencoders for Unsupervised Out-of-Distribution Detection
• Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces
• Max-value Entropy Search for Multi-Objective Bayesian Optimization with Constraints
• Lossy compression of matrices by black-box optimisation of mixed integer nonlinear programming
• Design Optimization of Noise Filter using Quantum Annealer
• Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
• Uncertainty aware Search Framework for Multi-Objective Bayesian Optimization with Constraints
• Achieving Robustness to Aleatoric Uncertainty with Heteroscedastic Bayesian Optimisation
• Kernels over Sets of Finite Sets using RKHS Embeddings, with Application to Bayesian (Combinatorial) Optimization
• Combinatorial 3D Shape Generation via Sequential Assembly
• Information-Theoretic Multi-Objective Bayesian Optimization with Continuous Approximations
• Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces
• NOMU: Neural Optimization-based Model Uncertainty
• Bayesian Optimization over Hybrid Spaces
• Scalable Thompson Sampling using Sparse Gaussian Process Models
• Black-box Mixed-Variable Optimisation using a Surrogate Model that Satisfies Integer Constraints
• Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework
• Bayesian Variational Optimization for Combinatorial Spaces
• Constrained Discrete Black-Box Optimization using Mixed-Integer Programming
• Mixed Variable Bayesian Optimization with Frequency Modulated Kernels
• Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions
• Weighting NTBEA for Game AI Optimisation
• Explaining Inference Queries with Bayesian Optimization