  Recent advances have extended the scope of Bayesian optimization (BO) to
expensive-to-evaluate black-box functions with dozens of dimensions, aspiring
to unlock impactful applications, for example, in the life sciences, neural
architecture search, and robotics. However, a closer examination reveals that
the state-of-the-art methods for high-dimensional Bayesian optimization (HDBO)
suffer from degrading performance as the number of dimensions increases or even
risk failure if certain unverifiable assumptions are not met. This paper
proposes BAxUS that leverages a novel family of nested random subspaces to
adapt the space it optimizes over to the problem. This ensures high performance
while removing the risk of failure, which we assert via theoretical guarantees.
A comprehensive evaluation demonstrates that BAxUS achieves better results than
the state-of-the-art methods for a broad set of applications.
