  We consider the problem of optimizing hybrid structures (mixture of discrete
and continuous input variables) via expensive black-box function evaluations.
This problem arises in many real-world applications. For example, in materials
design optimization via lab experiments, discrete and continuous variables
correspond to the presence/absence of primitive elements and their relative
concentrations respectively. The key challenge is to accurately model the
complex interactions between discrete and continuous variables. In this paper,
we propose a novel approach referred as Hybrid Bayesian Optimization (HyBO) by
utilizing diffusion kernels, which are naturally defined over continuous and
discrete variables. We develop a principled approach for constructing diffusion
kernels over hybrid spaces by utilizing the additive kernel formulation, which
allows additive interactions of all orders in a tractable manner. We
theoretically analyze the modeling strength of additive hybrid kernels and
prove that it has the universal approximation property. Our experiments on
synthetic and six diverse real-world benchmarks show that HyBO significantly
outperforms the state-of-the-art methods.
