Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces

• URL: http://arxiv.org/abs/2009.02539v4
• Date: Sun, 1 Nov 2020 12:38:20 GMT
• Title: Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces
• Authors: Hung Tran-The, Sunil Gupta, Santu Rana, Huong Ha, Svetha Venkatesh
• Abstract summary: We propose a novel BO algorithm which expands (and shifts) the search space over iterations. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates.
• Score: 63.22864716473051
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• High dimensional Bayesian Optimization via Condensing-Expansion Projection [1.6355174910200032]
  In high-dimensional settings, Bayesian optimization (BO) can be expensive and infeasible. We introduce a novel random projection-based approach for high-dimensional BO that does not reply on the effective subspace assumption. Experimental results demonstrate that both algorithms outperform existing random embedding-based algorithms in most cases.
  arXiv  Detail & Related papers  (2024-08-09T04:47:38Z)
• Voronoi Candidates for Bayesian Optimization [2.7309692684728617]
  Many practical BO methods, particularly in high dimension, eschew a formal, continuous optimization of the acquisition function. We propose to use candidates which lie on the boundary of the Voronoi tessellation of the current design points, so they are equidistant to two or more of them. We discuss strategies for efficient implementation by directly sampling the Voronoi boundary without explicitly generating the tessellation.
  arXiv  Detail & Related papers  (2024-02-07T14:47:13Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Computationally Efficient High-Dimensional Bayesian Optimization via Variable Selection [0.5439020425818999]
  We develop a new computationally efficient high-dimensional BO method that exploits variable selection. Our method is able to automatically learn axis-aligned sub-spaces, i.e. spaces containing selected variables. We empirically show the efficacy of our method on several synthetic and real problems.
  arXiv  Detail & Related papers  (2021-09-20T01:55:43Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
  arXiv  Detail & Related papers  (2021-05-10T13:07:44Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  Our algorithm generates a sequence of finite-dimensional random subspaces of functional space spanned by a set of draws from the experimenter's Gaussian Process. Standard Bayesian optimisation is applied on each subspace, and the best solution found used as a starting point (origin) for the next subspace. We test our algorithm in simulated and real-world experiments, namely blind function matching, finding the optimal precipitation-strengthening function for an aluminium alloy, and learning rate schedule optimisation for deep networks.
  arXiv  Detail & Related papers  (2020-09-08T06:54:11Z)
• Semi-supervised Embedding Learning for High-dimensional Bayesian Optimization [12.238019485880583]
  We propose a novel framework, which finds a low-dimensional space to perform Bayesian optimization iteratively through semi-supervised dimension reduction. SILBO incorporates both labeled points and unlabeled points acquired from the acquisition function to guide the embedding space learning. We show that SILBO outperforms the existing state-of-the-art high-dimensional Bayesian optimization methods.
  arXiv  Detail & Related papers  (2020-05-29T14:37:12Z)
• Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
  In big search spaces the algorithm goes through several low function value regions before reaching the optimum of the function. One approach to subside this cold start phase is to use prior knowledge that can accelerate the optimisation. In this paper, we represent the prior knowledge about the function optimum through a prior distribution. The prior distribution is then used to warp the search space in such a way that space gets expanded around the high probability region of function optimum and shrinks around low probability region of optimum.
  arXiv  Detail & Related papers  (2020-03-27T06:18:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.