Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces
This addresses a key limitation in Bayesian optimization for practitioners dealing with expensive black-box functions where the search space is not predefined, offering improved performance in synthetic and real-world tasks.
The paper tackles the problem of Bayesian optimization when the search space is unknown, proposing novel algorithms that expand and shift the search space using a hyperharmonic series, and shows theoretically that cumulative regret grows at sub-linear rates, with experiments demonstrating superiority over state-of-the-art methods.
Bayesian optimisation is a popular method for efficient optimisation of expensive black-box functions. Traditionally, BO assumes that the search space is known. However, in many problems, this assumption does not hold. To this end, we propose a novel BO algorithm which expands (and shifts) the search space over iterations based on controlling the expansion rate thought a hyperharmonic series. Further, we propose another variant of our algorithm that scales to high dimensions. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates. Our experiments with synthetic and real-world optimisation tasks demonstrate the superiority of our algorithms over the current state-of-the-art methods for Bayesian optimisation in unknown search space.