Practical Bayesian Algorithm Execution via Posterior Sampling

• URL: http://arxiv.org/abs/2410.20596v1
• Date: Sun, 27 Oct 2024 21:11:55 GMT
• Title: Practical Bayesian Algorithm Execution via Posterior Sampling
• Authors: Chu Xin Cheng, Raul Astudillo, Thomas Desautels, Yisong Yue,
• Abstract summary: PS-BAX is a simple, effective, and scalable BAX method based on posterior sampling. PS-BAX is applicable to a wide range of problems, including many optimization variants and level set estimation.
• Score: 24.795916177776856
• License:
• Abstract: We consider Bayesian algorithm execution (BAX), a framework for efficiently selecting evaluation points of an expensive function to infer a property of interest encoded as the output of a base algorithm. Since the base algorithm typically requires more evaluations than are feasible, it cannot be directly applied. Instead, BAX methods sequentially select evaluation points using a probabilistic numerical approach. Current BAX methods use expected information gain to guide this selection. However, this approach is computationally intensive. Observing that, in many tasks, the property of interest corresponds to a target set of points defined by the function, we introduce PS-BAX, a simple, effective, and scalable BAX method based on posterior sampling. PS-BAX is applicable to a wide range of problems, including many optimization variants and level set estimation. Experiments across diverse tasks demonstrate that PS-BAX performs competitively with existing baselines while being significantly faster, simpler to implement, and easily parallelizable, setting a strong baseline for future research. Additionally, we establish conditions under which PS-BAX is asymptotically convergent, offering new insights into posterior sampling as an algorithm design paradigm.

Related papers

• Batch Bayesian Optimization via Expected Subspace Improvement [0.0]
  We propose a simple and efficient approach to extend Bayesian optimization to batch evaluation. Our proposed approach can achieve near-linear speedup when compared with the sequential Bayesian optimization algorithm.
  arXiv  Detail & Related papers  (2024-11-25T09:14:09Z)
• Identifying Easy Instances to Improve Efficiency of ML Pipelines for Algorithm-Selection [0.20718016474717196]
  We propose a method for identifying easy instances which can be solved quickly using a generalist solver without any need for algorithm-selection. This saves computational budget associated with feature-computation which can then be used elsewhere in an AS pipeline.
  arXiv  Detail & Related papers  (2024-06-24T12:25:04Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO) Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
  arXiv  Detail & Related papers  (2024-02-05T02:54:50Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• 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)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• 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)
• Approximate Bayesian Computation of B\'ezier Simplices [13.105764669733093]
  We extend the B'ezier simplex model to a probabilistic one and propose a new learning algorithm of it. An experimental evaluation on publicly available problem instances shows that the new algorithm converges on a finite sample.
  arXiv  Detail & Related papers  (2021-04-10T04:20:19Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.