  This paper presents a novel decentralized high-dimensional Bayesian
optimization (DEC-HBO) algorithm that, in contrast to existing HBO algorithms,
can exploit the interdependent effects of various input components on the
output of the unknown objective function f for boosting the BO performance and
still preserve scalability in the number of input dimensions without requiring
prior knowledge or the existence of a low (effective) dimension of the input
space. To realize this, we propose a sparse yet rich factor graph
representation of f to be exploited for designing an acquisition function that
can be similarly represented by a sparse factor graph and hence be efficiently
optimized in a decentralized manner using distributed message passing. Despite
richly characterizing the interdependent effects of the input components on the
output of f with a factor graph, DEC-HBO can still guarantee no-regret
performance asymptotically. Empirical evaluation on synthetic and real-world
experiments (e.g., sparse Gaussian process model with 1811 hyperparameters)
shows that DEC-HBO outperforms the state-of-the-art HBO algorithms.
