Practical Bayesian Algorithm Execution via Posterior Sampling

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.

Paper

References (49)

Scroll for more · 37 remaining

Similar papers

Peer review

Reviewer BTqx7/10 · confidence 3/52024-07-01

Summary

This paper proposes a new method within the Bayesian algorithm execution framework, which enables finding a target set of points in a highly efficient manner.

Strengths

The problem tackled in this paper is highly important. The proposed method is sound and shows strong improvements vs. relevant benchmarks, in particular with respect to speed and sometimes also in terms of accuracy.

Weaknesses

I don’t see any noteworthy weaknesses, but I am also not an expert in BO and related tasks (only about Bayesian inference more generally).

Questions

The word “posterior sampling” seems to mean something very specific in this paper. However, in the Bayesian literature, this term is used for a much wider set of problems, which may be confusing to some readers of this paper. I think the mention the alternative term “Thompson sampling”. Could this be a good alternative name to use in relevant places?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

I think the authors could discuss more limitations of this method. Are there any major limitations beyond the fact that the method only works for base algorithms that have a set of points as target?

Reviewer Ta955/10 · confidence 2/52024-07-11

Summary

This paper introduces a scalable posterior sampling algorithm (aka PS-BAX) in the framework of Bayesian algorithm execution (BAX). Its fundamental basis is built on a key observation that the property of interest for many tasks is a target set of points, which for many scenarios such as standard bayesian optimization and level set estimation is usually the subset of the domain of the function. The authors propose PS-BAX with two key steps at each iteration: first the algorithm computes the target set using a sampled function from a posterior of Gaussian process; then it chooses the point with highest posterior variance (or entropy). In comparison to prior work (mainly INFO-BAX) based on expected information gain (EIG), PS-BAX shows superior computational efficiency. The authors have also established the asymptotic consistency of PS-BAX assuming the target set is stable.

Strengths

The paper is well-written and the algorithm is validated through extensive and broad classes of experiments with comparisons to other methods.

Weaknesses

This paper is an incremental work on INFO-BAX, which provides an alternative method to get around the expensive EIG computations by limiting the optimization to a target set per iteration. The posterior sampling is intuitive, however, it lacks rigorous development on its connection to INFO-BAX.

Questions

1. The authors claim that PS-BAX is scalable to high dimensional problems. The experiments contain examples only up to 10 dimensions. In the gene embedding experiment, the authors applied PCA to reduce the data to 5 dimensions. I suspect the Gaussian process approximations might be problematic in high dimensions. Can you justify the feasibility of applying PS-BAX to high dimensional data in numerical experiments? 2. INFO-BAX optimizes the mutual information over the entire domain X, whereas PS-BAX optimizes over a sampled target set X_n which is a subset of X. At each iteration (especially early iterations), one can imagine INFO-BAX should select a point that’s more informative on learning the task as it’s over the entire space. However, for some experiments (e.g. Figure 4), PS-BAX performs much better than INFO-BAX for early iterations. Can you provide more intuition on such phenomena? 3. The authors also claim that the PS-BAX method is easily parallelizable as one of the attractive contributions. However, as described in the main algorithm, PS-BAX is based on sequential computation of the posterior for the Gaussian process given samples selected from earlier iterations. Can you provide more details on how it can be parallelizable?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

My major concern is that within the BAX framework minimizing the number of evaluations is of primary importance. However, PS-BAX seems to have a lower efficiency picking up points as compared to the INFO-BAX method given a limited number of iterations. The study of non-asymptotic results seems to be important to provide practical guidance as compared to asymptotic results.

Reviewer FDTf5/10 · confidence 4/52024-07-12

Summary

This paper utilizes the idea of Bayesian sampling in the Bayesian algorithm execution (BAX) framework. As claimed by the authors, this is the first extension of posterior sampling beyond the optimization setting. The idea is very simple and natural and the performance seems reasonable. While I am not familiar with the BAX literature, it seems that the theoretical justification is incorrect.

Strengths

Overall, the paper is well structured and well written.

Weaknesses

In terms of computation cost, if a Gaussian process is used, then the computation cost of posterior variance $\sigma_n(x)$ involves the inversion of a high dimensional matrix. Can you please comment on it? In terms of the theorem 1: The notation is very confusing. On the LHS ($P_n(X=\mathcal{O_ A}(f))$), $f$ is random with probability measure $P_n$. On the RHS ($1(X=\mathcal{O_ A}(f))$), $f$ becomes fixed. I suppose the author means that on the LHS, $f$ refers to the random sample, and on the RHS, $f$ refers to the true function. The proof of theorem 1 doesn't involve the prior specification or the true $f$ function, which seems incorrect. For instance, (1) if the prior distribution is a Dirac measure, then the posterior is also a Dirac measure, and the algorithm never works as the sampling repeatedly returns the same $f_n$. But it won't affect theorem 1? (2) if $f$ contains a flat region of global optimal and $\mathcal A$ aims to find optimums, (i.e., $\mathcal{O_ A}(f)$ is an uncountable set) and the Gaussian process is used, then with probability 1, $\mathcal{O_ A}(\tilde f_n)$ contains only one element for any $n$. The claimed convergence clearly doesn't hold. Theorem 2 claims that consistency fails in general, and Theorem 1 claims that consistency holds when we have the stable assumption. This implies that some restriction is necessary, and the stable assumption is a sufficient assumption, not a necessary assumption.

Questions

Please see weakness.

Rating

5

Confidence

4

Soundness

1

Presentation

3

Contribution

2

Limitations

The checklist mentions that it discusses the limitation in section 4.3, but I cannot find it.

Authorsrebuttal2024-08-13

Dear Reviewer FDTf, We sincerely thank you for taking the time to read our response and for your follow-up question. Our result is indeed a *Bayesian* posterior consistency result, and we hope our response below clarifies this. In short, you are right that $\mathbf{P}\_n$ denotes the posterior measure of $f$. You are also right that the LHS denotes a random quantity depending on the random data $\set{(x\_i, y\_i)}\_{i=1}^n$. However, $f$ on the RHS is not a function drawn from the posterior but rather a function drawn from the prior, as we explain below. Our result should be interpreted as follows. Suppose that a random function $f$ is drawn from a prior distribution $p$. This function will remain fixed throughout the entire data collection process, and the data will emanate from this fixed function in the sense that $y\_i = f(x\_i) + \epsilon\_i$. Further, suppose that $f$ is unknown to our algorithm, but the prior $p$ is known to our algorithm. Although $f$ is unknown, at each iteration $n$, our algorithm can form a posterior distribution over $f$ using the (correctly-specified) prior $p$ and the sequence of observations $\set{(x\_i, y\_i)}\_{i=1}^n$. Let $p\_n$ denote this posterior and, for any fixed $X\subset\mathcal{X}$, let $q\_n(X)$ denote the probability that $\mathcal{O}\_\mathcal{A}(f) = X$ computed from $p\_n$. Theorem 1 states that with probability one, for a function $f$ drawn from $p$, $q\_n(X)$ will converge to $1$ if $X=\mathcal{O}\_\mathcal{A}(f)$ and will converge to 0 otherwise. Consequently, our result is indeed a Bayesian posterior consistency result in the sense that the estimated posterior of $\mathcal{O}\_\mathcal{A}(f)$ converges to the Dirac measure of the ground truth. As a final note, we acknowledge that consistency results are typically stated in terms of convergence of estimators rather than convergence of posterior distributions. We chose to present the latter as it is a stronger result, but we now realize that such a result is more prone to cause confusion. As discussed in our original response, a direct corollary of Theorem 1 is that the maximum a posteriori estimator of $\mathcal{O}\_\mathcal{A}(f)$ is asymptotically consistent. We will add this corollary to our revised manuscript, along with a discussion of our result inspired by your question. We hope this explanation addresses your concern. If you have any further questions, please let us know, and we will do our best to respond within the remaining time of the discussion period. Thank you again for your valuable contribution to improving our work. Sincerely, The Authors

Reviewer FDTf2024-08-13

Thanks for the explanation. I finally understand the notation (and the meaning that the prior needs to specify the $f$ well). A better presentation of theorem 1 is needed. Personally, if you say that $f$ follows a prior distribution $p$, and present the LHS as a conditional probability conditioned on data, I could understand it quickly. I would raise my score to 5, as I think the implicit assumption of compact $\mathcal X$ is not favorable.

Authorsrebuttal2024-08-13

Dear Reviewer FDTf, We are glad to hear that our response has addressed your concern. We will revise the statement of Theorem 1 based on your feedback to enhance its clarity. Thank you again for your valuable feedback and support of our work. Sincerely, The Authors

Reviewer qVHf5/10 · confidence 3/52024-07-13

Summary

This work proposes a posterior sampling algorithm for Bayesian algorithm execution, where the goal is to infer the output of an algorithm $O$ applied to an unknown function $f$. The algorithm is simple to implement and computationally more efficient than previous works based on mutual information maximization. The authors proved the algorithm is consistent with prior probability 1, and demonstrated empirically that it has comparable and sometimes better sample efficiency than previous work while being faster computationally.

Strengths

- The problem studied is interesting and practically relevant. - The proposed method is simple, computationally efficient and empirically effective, thereby providing a robust baseline for the problem. - The paper is mostly well-written.

Weaknesses

- I am uncertain about the correctness of the consistency proof (see question section below). - A less important point is about a design choice in the algorithm: when the sampled target set has multiple point the algorithm selects the point $x$ with the highest entropy $H[f(x)]$. This does not appear to be a universally optimal choice, for example if we want to estimate a level set $\\{x: f(x)\ge A\\}$ and there exists some $x_0\in \mathcal{X}$ for which the posterior $P(f(x_0)\mid D_n)$ has a very large mean and also a large variance: in such cases $H(f(x_0))$ could be the largest among the sampled level set but there may be little uncertainty that $x_0$ lives in the true level set. In addition, there may be scenarios where we need to focus on inferring the boundary of the level set instead of reducing the uncertainty about function values in the interior.

Questions

My main question is about the proof of Theroem 1, in particular the claim on L762 that $Z\cap O_A(f)=\emptyset$ "by construction". I can see this may be true if we assume $P_\infty(O_A(f))$ always assigns positive probability to some set $X\subset \mathcal{X}$, but what if this is not the case, for example, if $P_\infty(O_A(f))$ is a distribution over bounded intervals $\subset \mathbb{R}=\mathcal{X}$ and its marginal distributions for the endpoints are atom-less? Clearly similar issues can happen if we have (for example) a GP prior with a continuous kernel and consider $P_n$ instead of $P_\infty$. There should be explanations on why the issue will not happen with $P_\infty$, or why the reasoning of L762 is still valid in the presence of such issues.

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

Yes.

Reviewer qVHf2024-08-12

quick questions

Thank you for your response. I agree my question will be addressed if we assume $\mathcal{X}$ is finite. Could you point out where the finiteness assumption is made? I also have a quick question regarding your response to Reviewer fDTf: you said > Regarding the example where "contains a flat region of global optimum and A aims to find optima… and the Gaussian process is used," we agree that consistency does not hold because the prior is not well-specified in this case. Could you explain why the prior is not well-specified in this case? Your subsequent response suggested that the issue will not appear if we restrict to prior-almost every $f$. But we can have a GP prior that assigns positive (indeed, total) mass to constant functions, in which case the example doesn't seem to be immediately ruled out by the restriction.

Authorsrebuttal2024-08-12

Dear Reviewer qVHf, Thank you for taking the time to read our response. We address your new questions in detail below. > I agree my question will be addressed if we assume $\mathcal{X}$ is finite. Could you point out where the finiteness assumption is made? As mentioned in our original response (fourth sentence of the first paragraph), we regrettably neglected to explicitly include this assumption. We apologize for this oversight. This assumption will be clearly stated in the revised version of our manuscript. > I also have a quick question regarding your response to Reviewer fDTf… Your subsequent response suggested that the issue will not appear if we restrict to prior-almost every $f$. But we can have a GP prior that assigns positive (indeed, total) mass to constant functions, in which case the example doesn't seem to be immediately ruled out by the restriction. We agree that Gaussian priors can place positive mass on constant functions. However, note that Reviewer fDTf mentions an example such that the true function “$f$ contains a flat region of global optima” and then adds that “[if a] Gaussian process is used, then with probability 1, $\mathcal{O}\_\mathcal{A}(\tilde{f}\_n)$ contains only one element…” The combination of these two statements necessarily means that Reviewer fDTf is considering an example where the prior is **not** well-specified. Indeed, if we use a Gaussian process prior such that with probability one $\arg\max\_{x\in\mathcal{X}}f$ is a singleton, this necessarily implies that, with probability one, $f$ will **not** contain a flat region of global optima. To address your concern more directly, below we show that if the prior is such that $f$ is constant with probability one and $\mathcal{O}\_\mathcal{A}(f) = \arg\max\_{x\in\mathcal{X}}f$, then asymptotic consistency holds. Although the proof is tautological, we hope it clarifies any misunderstanding. Additionally, we note that this result holds for any choice of sampling decisions $\set{x\_n}\_{n=1}^\infty$. Thus, asymptotic consistency in this specific situation not only holds for PS-BAX, but actually holds for any algorithm. **Proposition.** *Suppose the prior is such that $f$ is constant with probability one and let $\mathcal{O}\_\mathcal{A}(f) = \arg\max\_{x\in\mathcal{X}}f$, then $\lim\_{n\rightarrow\infty}\mathbf{P}(X=\mathcal{O}\_\mathcal{A}(f)) = \mathbf{1}\set{X = \mathcal{O}\_\mathcal{A}(f)}$ almost surely under the prior for any $X \subset \mathcal{X}$.* *Proof.* Since $f$ is constant with probability one, we have that $\mathcal{O}\_\mathcal{A}(f) = \mathcal{X}$ with probability one. Consequently, with probability one, $\mathbf{1}\set{X = \mathcal{O}\_\mathcal{A}(f)} = 1$ if $X=\mathcal{X}$ and $\mathbf{1}\set{X = \mathcal{O}\_\mathcal{A}(f)} = 0$ if $X\neq \mathcal{X}$. Moreover, observe that since the prior only puts mass on constant functions, the same is necessarily true for the posterior. Therefore, $\mathbf{P}\_n(\mathcal{O}\_\mathcal{A}(f) = \mathcal{X})=1$ for all $n$. This also implies that $\mathbf{P}\_n(\mathcal{O}\_\mathcal{A}(f) = X)=0$ for any $X\subset\mathcal{X}$ with $X\neq \mathcal{X}$. From the above, it follows that, for any $X \subset \mathcal{X}$, $\lim\_{n\rightarrow\infty}\mathbf{P}(X=\mathcal{O}\_\mathcal{A}(f)) = \mathbf{1}\set{X = \mathcal{O}_\mathcal{A}(f)}$ almost surely, as desired. $\square$ We hope this discussion addresses your concerns. Please let us know if any further clarification is needed. Sincerely, The Authors

Authorsrebuttal2024-08-13

Dear Reviewer qVHf, As the end of the discussion period approaches, we would greatly appreciate it if you could confirm whether our response has adequately addressed your concerns. We also encourage you to review our recent discussion with Reviewer FDTf, as it addresses similar points and may provide further clarity on the issues you have raised. If any questions remain, please let us know, and we will do our best to respond within the remaining time. If your concerns have been resolved, we kindly ask you to consider raising your rating, as this would reflect the improvements made based on your valuable feedback. Thank you again for your time and efforts in reviewing our manuscript. Sincerely, The Authors

Reviewer qVHf2024-08-13

Thank you for your response. My concerns regarding correctness seem addressed and I will update the score accordingly. The finiteness assumption is somewhat unfortunate, especially since you only have a consistency result (as opposed to rates of contraction). You mentioned there are technical challenges with discretization. Is there any other scenario where the input space has a very large cardinality (e.g. in graph-related applications) and the consistency proof could still be relevant?

Authorsrebuttal2024-08-14

Dear Reviewer qVHf, We are glad that our response has addressed your primary concern, and we sincerely thank you for raising your score. Regarding your question about our consistency result and its finiteness assumption, we would like to emphasize the following points: - Our result applies to a broad range of critical real-world applications. Indeed, many real-world problems involve large, inherently discrete input spaces. For instance, in the drug discovery application discussed in our work (Section 4.5), the input space consists of a discrete set of 5,000 gene mutations. We also recently introduced a protein engineering application formulated as a top-$k$ optimization problem with an input space of similar size (please see A2 in our response to Reviewer Ta95). Moreover, similar problems in this area can involve input spaces exceeding 100,000 elements. Real-world shortest-path problems also often feature large transportation networks with thousands of nodes. - Our result is non-trivial even when the input space is small. In practical scenarios, observations are often corrupted by noise, which means that uncertainty regarding the true identity of the target set might persist even if the entire input space is evaluated. Our consistency result, which holds under noisy observations, ensures that PS-BAX can effectively mitigate such uncertainty in the long run. - The asymptotic consistency of *adaptive* algorithms like PS-BAX is not something that can be taken for granted. In Bayesian optimization contexts, popular algorithms have been shown to lack asymptotic consistency, even in discrete input spaces (see, e.g., Astudilo et al. 2023). The absence of asymptotic consistency often comes with erratic behavior, which may hinder performance in practical scenarios. Thus, the combination of our broad empirical evaluation, demonstrating the strong performance of PS-BAX, with our asymptotic consistency result, provides compelling evidence of PS-BAX’s potential to effectively address real-world challenges. We hope this discussion clarifies the significance of our asymptotic consistency result. Thank you again for your valuable feedback and support of our work. Sincerely, The Authors **References** Astudillo, R., Lin, Z. J., Bakshy, E., & Frazier, P. (2023). qEUBO: A decision-theoretic acquisition function for preferential Bayesian optimization. In International Conference on Artificial Intelligence and Statistics (pp. 1093-1114). PMLR.

Authorsrebuttal2024-08-11

Follow-up on NeurIPS Submission Discussion

Dear reviewers, As the discussion period is underway, we wanted to follow up to ensure our response has addressed your concerns. We believe we have thoroughly addressed the points raised and would greatly appreciate it if you could confirm this. If you have any further questions, please do not hesitate to let us know. Thank you once again for your thoughtful feedback. We look forward to your response. Sincerely, The authors

Authorsrebuttal2024-08-11

Dear Area Chair, Thank you for your response and key contributions to the review process. We look forward to any further discussion that could enhance the understanding and impact of our work. Sincerely, The Authors

Reviewer FDTf2024-08-12

Dear authors, Sorry for my late reply. I have read all the rebuttals, and have a follow-up regarding theorem 1. On the LHS (i.e., the term $\mathbf P_n(X=O_A(f))$), does $\mathbf P_n$ refer to the posterior measure of $f$? That is, LHS is a RANDOM probability quantity, which depends on random data $(x_i,y_i)$ On the RHS, does $f$ still follow the posterior distribution, where the posterior distribution is random as it depends on data $(x_i,y_i)$? If so, then, theorem 1 essentially prove that the posterior distribution of $O_A(f)$ converges to a Dirac measure. In other words, theorem 1 is a posterior concerntration result (posterior distribution concentrates toward certain limit), but NOT a posterior consistency result (posterior distribution concentrates toward truth).

Authorsrebuttal2024-08-13

Dear Reviewer BTqx, Thank you once again for your thoughtful feedback and support of our work. Sincerely, The Authors

Reviewer Ta952024-08-13

Thanks for the response! The batch-based experiments make sense to me. I have raised the score to 5.

Authorsrebuttal2024-08-14

Dear Reviewer Ta95, We are glad that our response addressed your concerns, and we sincerely thank you for raising your score. Thank you again for your valuable feedback and support of our work. Sincerely, The Authors

Authorsrebuttal2024-08-14

Thank You for Your Feedback and Fruitful Discussions

Dear Reviewers, As the discussion period comes to a close, we wanted to take a moment to thank you for the active and fruitful discussions. We are glad that our responses effectively addressed your primary concerns, leading to significantly improved ratings of our work (7, 5, 5, 5). Your feedback will be carefully incorporated into our revised manuscript. Thank you once again for your valuable contributions to the review process and for supporting our work. Sincerely, The Authors

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC