Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bayesian OptimisationSimilar Papers 제목 키워드 기반
Graph Agnostic Causal Bayesian Optimisation
We study the problem of globally optimising a target variable of an unknown causal graph on which a sequence of soft or hard interventions can be performed. The problem of optimising the target variable associated with a…
Bayesian OptimisationBayesian OptimizationBayesian Optimistic Optimisation with Exponentially Decaying Regret
Bayesian optimisation (BO) is a well-known efficient algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from $\mathcal{O}(\frac{logN…
Bayesian OptimisationTheoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters
Bayesian optimisation has gained great popularity as a tool for optimising the parameters of machine learning algorithms and models. Somewhat ironically, setting up the hyper-parameters of Bayesian optimisation methods i…
Bayesian OptimisationGaussian Processesparameter estimationTime-Varying Gaussian Process Bandits with Unknown Prior
Bayesian optimisation requires fitting a Gaussian process model, which in turn requires specifying prior on the unknown black-box function -- most of the theoretical literature assumes this prior is known. However, it is…
Bayesian OptimisationInformation-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
We study agents acting in an unknown environment where the agent's goal is to find a robust policy. We consider robust policies as policies that achieve high cumulative rewards for all possible environments. To this end,…