Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization

• URL: http://arxiv.org/abs/2210.10199v1
• Date: Tue, 18 Oct 2022 22:41:00 GMT
• Title: Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization
• Authors: Samuel Daulton, Xingchen Wan, David Eriksson, Maximilian Balandat, Michael A. Osborne, Eytan Bakshy
• Abstract summary: optimizing black-box functions of discrete (and potentially continuous) design parameters is a ubiquitous problem in scientific and engineering applications. We propose using probabilistic re parameterization (PR) to maximize the expectation of the acquisition function (AF) over a probability distribution. PR is complementary to (and benefits) recent work and naturally generalizes to settings with multiple objectives and black-box constraints.
• Score: 29.178417789839102
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimizing expensive-to-evaluate black-box functions of discrete (and potentially continuous) design parameters is a ubiquitous problem in scientific and engineering applications. Bayesian optimization (BO) is a popular, sample-efficient method that leverages a probabilistic surrogate model and an acquisition function (AF) to select promising designs to evaluate. However, maximizing the AF over mixed or high-cardinality discrete search spaces is challenging standard gradient-based methods cannot be used directly or evaluating the AF at every point in the search space would be computationally prohibitive. To address this issue, we propose using probabilistic reparameterization (PR). Instead of directly optimizing the AF over the search space containing discrete parameters, we instead maximize the expectation of the AF over a probability distribution defined by continuous parameters. We prove that under suitable reparameterizations, the BO policy that maximizes the probabilistic objective is the same as that which maximizes the AF, and therefore, PR enjoys the same regret bounds as the original BO policy using the underlying AF. Moreover, our approach provably converges to a stationary point of the probabilistic objective under gradient ascent using scalable, unbiased estimators of both the probabilistic objective and its gradient. Therefore, as the number of starting points and gradient steps increase, our approach will recover of a maximizer of the AF (an often-neglected requisite for commonly used BO regret bounds). We validate our approach empirically and demonstrate state-of-the-art optimization performance on a wide range of real-world applications. PR is complementary to (and benefits) recent work and naturally generalizes to settings with multiple objectives and black-box constraints.

Related papers

• Information-Theoretic Safe Bayesian Optimization [59.758009422067005]
  We consider a sequential decision making task, where the goal is to optimize an unknown function without evaluating parameters that violate an unknown (safety) constraint. Most current methods rely on a discretization of the domain and cannot be directly extended to the continuous case. We propose an information-theoretic safe exploration criterion that directly exploits the GP posterior to identify the most informative safe parameters to evaluate.
  arXiv  Detail & Related papers  (2024-02-23T14:31:10Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• 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)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models. We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling. We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
  arXiv  Detail & Related papers  (2022-09-27T07:58:25Z)
• Batch Bayesian Optimization via Particle Gradient Flows [0.5735035463793008]
  We show how to find global optima of objective functions which are only available as a black-box or are expensive to evaluate. We construct a new function based on multipoint expected probability which is over the space of probability measures.
  arXiv  Detail & Related papers  (2022-09-10T18:10:15Z)
• Surrogate modeling for Bayesian optimization beyond a single Gaussian process [62.294228304646516]
  We propose a novel Bayesian surrogate model to balance exploration with exploitation of the search space. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret.
  arXiv  Detail & Related papers  (2022-05-27T16:43:10Z)
• Sparse Bayesian Optimization [16.867375370457438]
  We present several regularization-based approaches that allow us to discover sparse and more interpretable configurations. We propose a novel differentiable relaxation based on homotopy continuation that makes it possible to target sparsity. We show that we are able to efficiently optimize for sparsity.
  arXiv  Detail & Related papers  (2022-03-03T18:25:33Z)
• Risk-averse Heteroscedastic Bayesian Optimization [45.12421486836736]
  We propose a novel risk-averse heteroscedastic Bayesian optimization algorithm (RAHBO) RAHBO aims to identify a solution with high return and low noise variance, while learning the noise distribution on the fly. We provide a robust rule to report the final decision point for applications where only a single solution must be identified.
  arXiv  Detail & Related papers  (2021-11-05T17:38:34Z)
• Approximate Bayesian Optimisation for Neural Networks [6.921210544516486]
  A body of work has been done to automate machine learning algorithm to highlight the importance of model choice. The necessity to solve the analytical tractability and the computational feasibility in a idealistic fashion enables to ensure the efficiency and the applicability.
  arXiv  Detail & Related papers  (2021-08-27T19:03:32Z)
• Trusted-Maximizers Entropy Search for Efficient Bayesian Optimization [39.824086260578646]
  This paper presents a novel trusted-maximizers entropy search (TES) acquisition function. It measures how much an input contributes to the information gain on a query over a finite set of trusted maximizers.
  arXiv  Detail & Related papers  (2021-07-30T07:25:07Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)

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.