Random Postprocessing for Combinatorial Bayesian Optimization

Sigma-i Co., Ltd., Tokyo, 108-0075, Japan Model-based sequential approaches to discrete "black-box" optimization, including Bayesian optimization techniques, often access the same points multiple times for a given objective function in interest, resulting in many steps to find the global optimum. Here, we numerically study the effect of a postprocessing method on Bayesian optimization that strictly prohibits duplicated samples in the dataset. We find the postprocessing method significantly reduces the number of sequential steps to find the global optimum, especially when the acquisition function is of maximum a posteriori estimation. Our results provide a simple but general strategy to solve the slow convergence of Bayesian optimization for high-dimensional problems. This process is repeated until a termination criterion is fulfilled, e.g., exhausting the predeter-1/10 In recent years, several attempts have been made to apply Bayesian optimization to highdimensional combinatorial optimization problems.