  High-dimensional black-box optimisation remains an important yet notoriously
challenging problem. Despite the success of Bayesian optimisation methods on
continuous domains, domains that are categorical, or that mix continuous and
categorical variables, remain challenging. We propose a novel solution -- we
combine local optimisation with a tailored kernel design, effectively handling
high-dimensional categorical and mixed search spaces, whilst retaining sample
efficiency. We further derive convergence guarantee for the proposed approach.
Finally, we demonstrate empirically that our method outperforms the current
baselines on a variety of synthetic and real-world tasks in terms of
performance, computational costs, or both.
