  The sample efficiency of Bayesian optimization(BO) is often boosted by
Gaussian Process(GP) surrogate models. However, on mixed variable spaces,
surrogate models other than GPs are prevalent, mainly due to the lack of
kernels which can model complex dependencies across different types of
variables. In this paper, we propose the frequency modulated (FM) kernel
flexibly modeling dependencies among different types of variables, so that BO
can enjoy the further improved sample efficiency. The FM kernel uses distances
on continuous variables to modulate the graph Fourier spectrum derived from
discrete variables. However, the frequency modulation does not always define a
kernel with the similarity measure behavior which returns higher values for
pairs of more similar points. Therefore, we specify and prove conditions for FM
kernels to be positive definite and to exhibit the similarity measure behavior.
In experiments, we demonstrate the improved sample efficiency of GP BO using FM
kernels (BO-FM).On synthetic problems and hyperparameter optimization problems,
BO-FM outperforms competitors consistently. Also, the importance of the
frequency modulation principle is empirically demonstrated on the same
problems. On joint optimization of neural architectures and SGD
hyperparameters, BO-FM outperforms competitors including Regularized
evolution(RE) and BOHB. Remarkably, BO-FM performs better even than RE and BOHB
using three times as many evaluations.
