  The optimization of expensive to evaluate, black-box, mixed-variable
functions, i.e. functions that have continuous and discrete inputs, is a
difficult and yet pervasive problem in science and engineering. In Bayesian
optimization (BO), special cases of this problem that consider fully continuous
or fully discrete domains have been widely studied. However, few methods exist
for mixed-variable domains and none of them can handle discrete constraints
that arise in many real-world applications. In this paper, we introduce MiVaBo,
a novel BO algorithm for the efficient optimization of mixed-variable functions
combining a linear surrogate model based on expressive feature representations
with Thompson sampling. We propose an effective method to optimize its
acquisition function, a challenging problem for mixed-variable domains, making
MiVaBo the first BO method that can handle complex constraints over the
discrete variables. Moreover, we provide the first convergence analysis of a
mixed-variable BO algorithm. Finally, we show that MiVaBo is significantly more
sample efficient than state-of-the-art mixed-variable BO algorithms on several
hyperparameter tuning tasks, including the tuning of deep generative models.
