Mercer Features for Efficient Combinatorial Bayesian Optimization
- URL: http://arxiv.org/abs/2012.07762v1
- Date: Mon, 14 Dec 2020 17:58:39 GMT
- Title: Mercer Features for Efficient Combinatorial Bayesian Optimization
- Authors: Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa
- Abstract summary: 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 spaces (e.g., sequences and graphs) that occurs naturally in science and engineering applications.
The key challenge is to balance the complexity of statistical models and tractability of search to select structures for evaluation.
- Score: 32.856318660282255
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 and graphs)
that occurs naturally in science and engineering applications. A prototypical
example is molecular optimization guided by expensive experiments. The key
challenge is to balance the complexity of statistical models and tractability
of search to select combinatorial structures for evaluation. In this paper, we
propose an efficient approach referred as Mercer Features for Combinatorial
Bayesian Optimization (MerCBO). The key idea behind MerCBO is to provide
explicit feature maps for diffusion kernels over discrete objects by exploiting
the structure of their combinatorial graph representation. These Mercer
features combined with Thompson sampling as the acquisition function allows us
to employ tractable solvers to find next structures for evaluation. Experiments
on diverse real-world benchmarks demonstrate that MerCBO performs similarly or
better than prior methods. The source code is available at
https://github.com/aryandeshwal/MerCBO .
Related papers
- Poisson Process for Bayesian Optimization [126.51200593377739]
We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO)
Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
arXiv Detail & Related papers (2024-02-05T02:54:50Z) - Efficient computation of the Knowledge Gradient for Bayesian
Optimization [1.0497128347190048]
One-shot Hybrid KG is a new approach that combines several of the previously proposed ideas and is cheap to compute as well as powerful and efficient.
All experiments are implemented in BOTorch and show empirically drastically reduced computational overhead with equal or improved performance.
arXiv Detail & Related papers (2022-09-30T10:39:38Z) - Bayesian Optimization for Macro Placement [48.55456716632735]
We develop a novel approach to macro placement using Bayesian optimization (BO) over sequence pairs.
BO is a machine learning technique that uses a probabilistic surrogate model and an acquisition function.
We demonstrate our algorithm on the fixed-outline macro placement problem with the half-perimeter wire length objective.
arXiv Detail & Related papers (2022-07-18T06:17:06Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search.
Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function.
Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
arXiv Detail & Related papers (2022-07-02T16:59:37Z) - Optimizer Amalgamation [124.33523126363728]
We are motivated to study a new problem named Amalgamation: how can we best combine a pool of "teacher" amalgamations into a single "student" that can have stronger problem-specific performance?
First, we define three differentiable mechanisms to amalgamate a pool of analyticals by gradient descent.
In order to reduce variance of the process, we also explore methods to stabilize the process by perturbing the target.
arXiv Detail & Related papers (2022-03-12T16:07:57Z) - Bayesian Optimization over Permutation Spaces [30.650753803587794]
We propose and evaluate two algorithms for BO over Permutation Spaces (BOPS)
We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly.
Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for spaces.
arXiv Detail & Related papers (2021-12-02T08:20:50Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations.
We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output.
On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
arXiv Detail & Related papers (2021-04-19T17:22:11Z) - Combinatorial Bayesian Optimization with Random Mapping Functions to
Convex Polytopes [43.19936635161588]
We present a method for Bayesian optimization in a space which can operate well in a large space.
Our algorithm shows satisfactory performance compared to existing methods.
arXiv Detail & Related papers (2020-11-26T02:22:41Z) - Scalable Combinatorial Bayesian Optimization with Tractable Statistical
models [44.25245545568633]
We study the problem of optimizing blackbox functions over Relaxation spaces (e.g., sets, sequences, trees, and graphs)
Based on recent advances in submodular relaxation, we study an approach as Parametrized Submodular (PSR) towards the goal of improving the scalability and accuracy of solving AFO problems for BOCS model.
Experiments on diverse benchmark problems show significant improvements with PSR for BOCS model.
arXiv Detail & Related papers (2020-08-18T22:56:46Z) - Stepwise Model Selection for Sequence Prediction via Deep Kernel
Learning [100.83444258562263]
We propose a novel Bayesian optimization (BO) algorithm to tackle the challenge of model selection in this setting.
In order to solve the resulting multiple black-box function optimization problem jointly and efficiently, we exploit potential correlations among black-box functions.
We are the first to formulate the problem of stepwise model selection (SMS) for sequence prediction, and to design and demonstrate an efficient joint-learning algorithm for this purpose.
arXiv Detail & Related papers (2020-01-12T09:42:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.