Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes
This method offers a solution for researchers and practitioners dealing with black-box optimization problems where input variables are categorical or discrete, avoiding the combinatorial explosion problem often encountered with one-hot encoding.
This paper addresses the challenge of Bayesian optimization in large combinatorial spaces by proposing a random mapping function that embeds the combinatorial space into a convex polytope in a continuous space. This allows standard continuous Bayesian optimization techniques to be applied, and numerical experiments show satisfactory performance compared to existing methods.
Bayesian optimization is a popular method for solving the problem of global optimization of an expensive-to-evaluate black-box function. It relies on a probabilistic surrogate model of the objective function, upon which an acquisition function is built to determine where next to evaluate the objective function. In general, Bayesian optimization with Gaussian process regression operates on a continuous space. When input variables are categorical or discrete, an extra care is needed. A common approach is to use one-hot encoded or Boolean representation for categorical variables which might yield a combinatorial explosion problem. In this paper we present a method for Bayesian optimization in a combinatorial space, which can operate well in a large combinatorial space. The main idea is to use a random mapping which embeds the combinatorial space into a convex polytope in a continuous space, on which all essential process is performed to determine a solution to the black-box optimization in the combinatorial space. We describe our combinatorial Bayesian optimization algorithm and present its regret analysis. Numerical experiments demonstrate that our method shows satisfactory performance compared to existing methods.