Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces

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