  Bayesian optimization (BO) is a popular technique for sequential black-box
function optimization, with applications including parameter tuning, robotics,
environmental monitoring, and more. One of the most important challenges in BO
is the development of algorithms that scale to high dimensions, which remains a
key open problem despite recent progress. In this paper, we consider the
approach of Kandasamy et al. (2015), in which the high-dimensional function
decomposes as a sum of lower-dimensional functions on subsets of the underlying
variables. In particular, we significantly generalize this approach by lifting
the assumption that the subsets are disjoint, and consider additive models with
arbitrary overlap among the subsets. By representing the dependencies via a
graph, we deduce an efficient message passing algorithm for optimizing the
acquisition function. In addition, we provide an algorithm for learning the
graph from samples based on Gibbs sampling. We empirically demonstrate the
effectiveness of our methods on both synthetic and real-world data.
