Practical Bayesian Algorithm Execution via Posterior Sampling

Authors: chu xin cheng
raul  astudillo
thomas  desautels
yisong  yue
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 21:12:26

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.

Main paper: 
 introduction: 
 Many real-world problems can be cast as estimating a property of a black-box function with expensive evaluations. Bayesian optimization (BO) [1] has focused on the case where the property of interest is the function's global optimum. Similarly, level set estimation [2] deals with the problem of estimating the subset of points above (or below) a user-specified threshold.In many cases, an algorithm to compute the property of interest is available, which we refer to as the base algorithm. However, this algorithm typically requires more evaluations than are feasible in practice and cannot be used directly. Instead, evaluation points must be carefully selected through other means. Similar to BO and level set estimation, the Bayesian algorithm execution (BAX) framework selects evaluation points using two key components: (1) a Bayesian probabilistic model of the function and (2) a sequential sampling criterion that leverages this model to choose new points for evaluation [3] .Existing approaches to BAX rely on expected information gain (EIG) as the criterion for selecting which points to evaluate [3] . However, maximizing the EIG presents a significant computational Algorithm 1 PS-BAX Require: p(f ) (prior), D 0 (initial dataset), A (base algorithm), N (number of iterations).1: for n = 1 : N do 2:Sample fn from p(f | D n-1 )3:Apply algorithm A on fn to obtain X n = O A ( fn ) //E.g., run A on the final posterior mean introduce a straightforward algorithm applicable to these diverse settings, providing a robust baseline for future exploration. Furthermore, our approach benefits from recent advances in probabilistic modeling tools [33] [34] [35] , paving the way for applying these tools to a broader range of problems. 
bayesian algorithm execution via posterior sampling: 
 Problem Setting Our work takes place within the Bayesian algorithm execution (BAX) framework introduced by [3] . The goal is to estimate O A (f ), the output of a base algorithm A applied to a function f : X → R. We assume that f is expensive to evaluate, which means that employing A directly on f is infeasible (as it would require evaluating f too many times). Instead, we select the points at which f is evaluated sequentially, aided by a probabilistic model described below. We specifically focus on problems where the property of interest can be encoded by a set O A (f ) ⊂ X, which we term the target set. As we shall see later, our framework encompasses a wide range of problems, including BO2 , level-set estimation, shortest-path finding on graphs, and top-k estimation, with applications to topographic estimation and drug discovery.Probabilistic Model Similar to many probabilistic numerical methods, our algorithm relies on a probabilistic model encoded by a prior distribution over f , which we denote by p. Although our framework is more general and can be used with other priors, we assume for concreteness that f follows a Gaussian process (GP) prior [36] . Let D n-1 = {(x k , y k )} n-1 k=1 denote the data collected after n -1 evaluations of f . We assume these evaluations are corrupted with i.i.d. Gaussian noise, i.e., y k = f (x k ) + ϵ k , where ϵ 1 , . . . , ϵ n-1 are i.i.d. with common distribution N (0, σ 2 ), and σ 2 is a non-negative scalar. Under these assumptions, the posterior distribution over f given D n-1 , denoted by p(f | D n-1 ), is again a GP whose mean and covariance functions can be computed in closed form using the classical GP regression equations.INFO-BAX and its Shortcomings Before introducing our algorithm, we briefly comment on prior work based on the expected information gain (EIG) [3] . Succinctly, the INFO-BAX approach proposed by [3] selects at each iteration the point that maximizes the expected entropy reduction between the function's value at the evaluated point and O A (f ). Evaluating an expectation is generally difficult, and one often resorts to Monte Carlo sampling. Moreover, computing the EIG specifically requires expensive calculations of conditional posterior distributions and entropy. These computational issues are also present in similar information-theoretic acquisition functions proposed in the classic BO setting. However, for BAX tasks, the computation burden of EIG can be much more pronounced if |O A (f )| is large. This occurs, for example, in the level set estimation setting, where O A (f ) can be comprised of a large number of points. We defer a more detailed discussion of the computation of the EIG to Appendices A and B .To overcome the computational limitations of EIG-based approaches, we introduce a simple strategy based on posterior sampling, which we term PS-BAX. For ease of exposition, we only describe the fully sequential version of our algorithm and defer the batched (parallelized) version to Appendix C. Our algorithm is summarized in Algorithm 1. PS-BAX is comprised of two steps, detailed below. (green region) (this is the set of inputs where the green line is above the threshold), the variance of p(f | D n-1 ) (green line, bottom row), and the next point to evaluate selected by PS-BAX x n ∈ X n (input marked by the vertical red line). The key step is computing the target set X n using the sampled function fn , which generalizes posterior sampling for standard BO.1. We sample a target set X n ⊂ X according to the posterior probability thatX n = O A (f ) (lines 2-3 in Algorithm 1). This can be achieved by drawing a sample from the posterior over f , denoted by fn (line 2), and then setting X n = O A ( fn ) (line 3). 2. We select the point in the sampled target set X n with maximal uncertainty or entropy:x n ∈ argmax x∈Xn H[f (x)|D n ] (line 4 in Algorithm 1). For a Gaussian posterior, x n can be equivalently selected using the maximal posterior standard deviation:x n ∈ argmax x∈Xn σ n (x), where σ n (x) is the posterior standard deviation of f (x).Note that the second step is unnecessary in standard BO, since X n is typically a singleton.Depiction for Level Set Estimation Figure 1 depicts an iteration of PS-BAX for the level-set estimation problem, where O A (f ) := {x ∈ X | f (x) > τ }, for a user-specified value of τ . Line 3 of Algorithm 1 returns a target set X n based on where the sampled function fn (green line in Figure 1 ) is above the threshold τ (green region in Figure 1 ). Line 4 of Algorithm 1 then chooses the point x n ∈ X n that has maximal uncertainty (red line in Figure 1 ). In the standard BO setting where A is computing the maximizer of f , the target region X n is simply a singleton point where the sampled f has highest value (and Line 4 in Algorithm 1 is not necessary).Discussion We now provide an intuitive explanation of why one might expect PS-BAX to perform well. In the standard BO setting, posterior sampling is known to deliver excellent performance [20, 37] and enjoys strong theoretical guarantees [18, 20] . Like in the BO setting, the intrinsic goal of posterior sampling in our setting is to balance exploration and exploitation. In our case, this means selecting points for which, according to our probabilistic model, membership in the target set is still highly uncertain among the likely candidates. To achieve this, the first step of PS-BAX selects a random set X n , according to the probability of this set being the target set, in the same vein as traditional posterior sampling in the BO setting (the set of likely candidates). Unlike in BO, however, the target set is, in principle, comprised of several points, and thus, we must come up with a criterion to choose one. To overcome this, the second step simply selects the point with the highest uncertainty among points in X n , which is a standard strategy in the active learning literature [38] .Computational Efficiency PS-BAX requires running A only once on a single sample of f , contributing to its practicality and scalability. Furthermore, similar to posterior sampling in the standard BO setting, PS-BAX avoids the need to maximize an acquisition function over X, a process that is computationally expensive because it involves calculating the expected value of quantities like information gain. As demonstrated in our experiments, this makes PS-BAX significantly faster than INFO-BAX [3] , particularly in problems where either O A (f ) or X are large.Convergence of PS-BAX A natural question is under which conditions is PS-BAX able to find the target set given enough evaluations. We address this question below. Before stating our results, we introduce a definition related to the characterization of problems where PS-BAX converges. Definition 1. A target set estimated by an algorithm A is said to be complement-independent if, for any pair of functions f, f ′ :X → R, it holds that O A (f ) = O A (f ′ ) whenever there exists a set S such that O A (f ) ∪ O A (f ′ ) ⊂ S and f (x) = f ′ (x) for all x ∈ S.Many target sets of interest, such as a function's optimum or level set, are complement-independent. Indeed, the value of f at points that are not the optimum or that do not lie in the level of interest do not influence these properties. Theorem 1 below shows that PS-BAX enjoys Bayesian posterior concentration, provided the target set of interest is complement-independent. Intuitively, this result means that if f is drawn from the prior used by our algorithm (i.e., the prior is well-specified), then, with probability one, the posterior will concentrate around the true target set. Corollary 1 gives an asymptotically consistent estimator of the target set. Finally, we also show there are problems where the target set is not complement-independent and PS-BAX is not asymptotically consistent in Theorem 2. The proofs of these results can be found in Appendix D. Theorem 1. Suppose that X is finite and that the target set estimated by A is complement-independent. If the sequence of points {x n } ∞ n=1 is chosen according to the PS-BAX algorithm, then, for each X ⊂ X, lim n→∞ P n (O A (f ) = X) = 1{O A (f ) = X} almost surely for f drawn from the prior. Corollary 1. Suppose the assumptions of Theorem 1 hold, and let T n ∈ argmax X⊂X P n (O A (f ) = X). Then, for f drawn from the prior, we have T n = O A (f ) for all sufficiently large n almost surely. Theorem 2. There exists a problem instance (i.e., X, a Bayesian prior over f , and A) such that if the sequence of points {x n } ∞ n=1 is chosen according to the PS-BAX algorithm, then there is a set X ⊂ X such that lim n→∞ P n (O A (f ) = X) = 1/2 almost surely for f drawn from the prior.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: See Section 4.3 and Appendix. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
numerical experiments: 
 We evaluate the performance of PS-BAX on eight problems across four problem classes. For each problem class, we specify the base algorithm used. We compare the performance of PS-BAX against INFO-BAX [3] and uniform random sampling over X (Random). When available, we also include an algorithm from the literature specifically designed for the problem class. Additional implementation details of the algorithms are described in Appendix E. In all experiments, an initial dataset is generated by sampling 2(d + 1) inputs uniformly at random from X, where d denotes the dimensionality of X. Following this initialization, each algorithm sequentially selects additional batches of points. Unless stated otherwise, the batch size is set to q = 1. The performance of each algorithm is determined by applying A on µ n , the posterior mean of f given D n and subsequently computing a suitable performance metric on O A (µ n ). Each experiment was replicated 30 times, with plots showing mean performance plus and minus 1.96 standard errors. Code to reproduce our experiments is available at https://github.com/RaulAstudillo06/PSBAX. Summary of Findings Overall, we find that PS-BAX is always competitive with and sometimes significantly outperforms INFO-BAX across all of our experiments. Additionally, as shown in Table 1 , PS-BAX can be orders of magnitude faster in wall-clock runtime. PS-BAX outperforms INFO-BAX on five out of eight problems, offering particularly large improvements in the Local Optimization and DiscoBAX problem classes. Moreover, in the Local Optimization and Level Set Estimation problems, PS-BAX also outperforms algorithms from the literature specifically designed for such problem classes. On the simpler problems, such as those in the Top-k problem class, PS-BAX is competitive with INFO-BAX while still being significantly faster.We explore the performance of our algorithm in the local optimization setting, where A is a classic optimization algorithm, i.e., an algorithm designed for optimization problems where f (and potentially its gradients) can be evaluated at a large number of points. Examples of such algorithms include evolutionary algorithms [39] , trust-region methods [40] , and many gradient-based optimization algorithms [41, 42] . This setting reduces to the classical BO setting if A can recover the global optimum of f . In such case, the INFO-BAX reduces to the classical predictive entropy search acquisition function [16] when computed exactly and to the joint entropy search acquisition function [43] under the approximation proposed by [3] that we use in our experiments. PS-BAX, in turn, reduces to the classical posterior sampling strategy used in BO [20] . However, due to its practical relevance and the lack of an empirical comparison between joint entropy search and posterior sampling, we still include this setting in our experiments. We also use this setting to illustrate nuances that arise when choosing a base algorithm.In our experiments, we use a gradient-based optimization method as a base algorithm instead of an evolutionary algorithm as pursued by [3] . Gradient-based methods typically exhibit faster convergence than their gradient-free counterparts. However, they are often infeasible if gradients cannot be obtained analytically and instead are obtained, e.g., via finite differences. Since in most applications, analytic gradients of f are unavailable, directly applying such methods on f is infeasible. However, PS-BAX and INFO-BAX can make use of gradient-based methods thanks to the availability of gradients of most probabilistic models used in practice, including GPs.We consider the Hartmann and Ackley functions, with input dimensions of 6 and 10, respectively, as test functions. Both functions have many local minima and are standard test functions in the BO literature. For Ackley, we set the batch size to q = 2. As a performance metric, we report the log10 inference regret, given by log 10 (f * -f (x * n )), where x * n is obtained by applying A on µ n . The results of these experiments are depicted in Figure 2 . As a baseline, we also include the Level set estimation involves finding all points in X with f (x) > τ , for a user-specified threshold value τ . This task arises in applications such as environmental monitoring, where a mobile sensing device detects regions with dangerous pollution levels [2] , and topographic mapping, where the goal is to infer the portion of a geographic area above a specified altitude using limited measurements [44] .For both problems considered in our work, X is finite; therefore, the base algorithm A simply ranks all objective values and returns the points where the function value exceeds the threshold.We evaluate the algorithms on a synthetic problem (the 2-dimensional Himmelblau function) and a real-world topographic dataset, consisting of 87 × 61 height measurements from a large geographic area around Auckland's Maunga Whau volcano [44] . The threshold τ is set to the 0.55 quantile of all function values in the domain for both problems. An illustration of single runs on the topographic problem over 100 iterations for both INFO-BAX and PS-BAX is shown in Figure 4 .The performance metric used is the F1 score, defined byEQUATIONwhere T P , F P , and F N represent true positives, false positives, and false negatives, respectively. The results of this experiment are shown in Figure 3 . As an additional baseline specifically designed for level set estimation, we include the popular LSE algorithm proposed by [2] . PS-BAX demonstrates strong performance, outperforming all benchmarks in the topographic mapping problem.We consider the top-k estimation setting, where X is a finite (but potentially large) set, and the goal is to identify the k points with the largest values of f (x). In this scenario, the base algorithm evaluates f at all points in X and returns the k best points. Following [3] , we use as performance metric the Jaccard distance between the estimated output S n = O A (µ n ) and the ground truth optimal set S * , defined byEQUATIONWe consider two test problems. The first problem uses 3-dimensional Rosenbrock function, a standard benchmark in the optimization literature. The input space is obtained by taking a uniform grid of 1,000 points over [-2, 2] 3 . For this problem we set k = 4.The second problem is a real-world top-k (k = 10) selection task in protein design, where the goal is to maximize stability fitness predictions for the Guanine nucleotide-binding protein GB1, given different sequence mutations in a target region of 4 residues [45] . GB1 is well-studied by biologists, and its domain is known to be highly rugged, dominated by "dead" variants with very low fitness scores [46] . There are 20 4 possible combinations, with 20 amino acids and 4 positions, and we represent the input space X as one-hot vectors in an 80-dimensional space. To avoid excessive runtimes, we randomly sample 10,000 points from the original dataset. Due to the high dimensionality, vast input space, and sparse fitness landscape, this dataset poses significant challenges for standard GP models. Therefore, we use a deep kernel GP [47] as our probabilistic model. Given the dataset's size, we perform batched evaluations with batch size of q = 4 for both PS-BAX and INFO-BAX.The results of these experiments are shown in Figure 5 . In both problems, PS-BAX performs comparably to INFO-BAX, with both algorithms significantly outperforming Random. As a final application, we consider the DiscoBAX problem setting from [29] in the context of drug discovery, where the task is to identify a set of optimal genomic interventions to determine suitable drug targets. Formally, let X represent a pool of genetic interventions, and for each x ∈ X, let f (x) denote an in vitro phenotype measurement correlated with the effectiveness of genetic intervention x.The effectiveness of the intervention is assumed to be f (x) + η(x), where η(x) captures noise and other exogenous factors not reflected in the in vitro measurement. Following the setup in [29] , we simulate η using a GP with mean 0 and an RBF covariance function. The goal is to identify a small set of genomic interventions in X that maximize an objective function balancing two characteristics: high expected change in the target phenotype and high diversity to maximize success in subsequent stages of drug development. This is formalized in [29] as the following optimization problem:EQUATIONwhere k is the desired size of the intervention set. This problem aims to find a set of interventions S such that the best-performing intervention in S has the highest expected effectiveness (over η).Solving Equation 3 exactly is challenging due to its combinatorial nature, even if could evaluate f many times, but a computationally efficient approximation is possible by leveraging the submodularity of the objective function. For more details on the base algorithm, we refer the reader to [29] .Following [29] , we use the tau protein assay [48] and interferon-gamma assay [49] datasets from the Achilles project [50] . Originally, the gene embeddings in this dataset are represented as 808dimensional vectors, and a Bayesian MLP is used as the probabilistic model instead of a GP. To reduce dimensionality, we preprocess the dataset using Principal Component Analysis (PCA) and then fit a GP to the lower-dimensional representation. Additionally, we truncate the dataset to the 5000 genes with the highest intervention values to ensure computational feasibility in our experiments. The results of these experiments are shown in Figure 6 . PS-BAX significantly outperforms INFO-BAX, whose performance is only marginally better than that of Random. Figure 6 : Results for DiscoBAX [29] , showing the regret between the solution found by applying a greedy submodular optimization algorithm to the objective in Equation 3 and the solution obtained from applying the same algorithm over the posterior mean instead of the true function. Both problems are based on the Achilles dataset [50] , with the left panel presenting results for the tau protein assay [48] and the right panel showing results for the interferon-gamma assay. In both cases, PS-BAX significantly outperforms INFO-BAX, which performs only marginally better than Random.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: A thorough discussion of the details of our empirical evaluation can be found in Section 5 and Appendix. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusion: 
 Many real-world problems involve estimating the output of a base algorithm applied to a black-box function with costly evaluations. While the INFO-BAX algorithm proposed by [3] offers a solution, it faces practical limitations. In response, we introduced PS-BAX, a novel posterior sampling strategy built upon the observation that, in many cases, the algorithm's output can be characterized as a target set of input points. Our experiments demonstrate that PS-BAX is not only competitive with previous approaches but also significantly faster to compute. Moreover, we established conditions under which PS-BAX is asymptotically convergent.Looking ahead, our approach provides a pathway to extend the success of Bayesian optimization to a broader range of problems, potentially unlocking new and impactful applications. Additionally, PS-BAX serves as a robust baseline for future research aimed at developing tailored strategies for specific domains. Furthermore, our findings offer new perspectives on posterior sampling algorithms and their application scope, suggesting several promising avenues for future exploration in this area. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: The dataset used in our simulated exoskeleton design is discussed in Section 5.3. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Given a Gaussian process posterior, we analyze the computational complexity of selecting the next evaluation point for both PS-BAX and INFO-BAX. Our analysis excludes the cost of generating a sample from the posterior, which is fixed and depends only on the number of Fourier features used. We also assume that the cost of evaluating such a sample at any given point is 1, as is the cost of evaluating the posterior mean and covariance. Additionally, we assume that the function domain X is discrete with |X| = N , the algorithm output has a fixed cardinality |O A (f )| = M , the number of execution paths to approximate the posterior entropy is L, and running the algorithm on any input function requires P evaluations. As we show next, the computational cost of INFO-BAX can be significantly higher than that of PS-BAX when N , M , or L is large.For PS-BAX, the complexity is O(P + M ), reflecting the cost of running the algorithm once on a single function sample and maximizing the posterior variance over the sampled target set. For INFO-BAX, the complexity isO (P + M 3 + N • M 2 ) • L .For each function sample, we need to execute the algorithm (P ), condition on M new points to compute the conditional entropy (M 3 ), and evaluate the posterior variance of the fantasized model on N points (N • M 2 ). This process is repeated for L function samples.In this section, we discuss extensions of the PS-BAX and INFO-BAX algorithms to the batch setting, where at each iteration, we generate q new points for evaluation, denoted by x n,1 , . . . , x n,q . These extensions are inspired by batch versions of the posterior sampling algorithm [20] and the joint entropy search acquisition function [43] from BO. Figure 7 illustrates the performance of PS-BAX under various batch sizes in two of our test problems.Batch PS-BAX We extend PS-BAX to the batch setting, following the approach proposed by [20] . For a batch size of q, we draw q independent samples from the posterior on f , denoted by f1 , . . . , fq , and define the set X n = ∪ q i=1 O A ( fn,i ). We then select the points x n,1 , . . . , x n,q ∈ X n iteratively by choosing the point in X n with the highest posterior entropy, conditioned on the previously selected points, as follows:x n,1 = argmax x∈Xn H[f (x) | D n ],. . .x n,q = argmax x∈Xn H[f (x) | D n ∪ {x n,1 , . . . , x n,q-1 }]Batch INFO-BAX INFO-BAX can be naturally extended to the batch setting by considering the EIG over a batch of q points. However, directly optimizing the EIG in this scenario involves optimizing over X q , which is usually computationally prohibitive. To address this, we use a greedy optimization approach. Specifically, we select x n,1 , . . . , x n,q iteratively by maximizing the EIG conditioned on the previously selected points, as follows:x n,1 = argmax x∈X H[y x | D n ] -E[H[y x | D n , O A (f )] | D n ],. . .x n,q = argmax x∈X H[y x | D n ∪ {x n,1 , . . . , x n,q-1 }] -E[H[y x | D n ∪ {x n,1 , . . . , x n,q-1 }, O A (f )] | D n ∪ {x n,1 , . . . , x n,q-1 }].We begin by introducing the following notation. Let F n denote the σ-algebra generated by D n-1 , and let F ∞ denote the minimal σ-algebra generated by the sequence {F n } ∞ n=1 . We denote the conditional probability measures induced by F n and F ∞ as P n and P ∞ , respectively. INFO-BAX (q = 1) PS-BAX (q = 1)INFO-BAX (q = 2) PS-BAX (q = 2)INFO-BAX (q = 4) PS-BAX (q = 4) Before proving Theorem 1, we establish an auxiliary lemma. Both Lemma 1 and Theorem 1 assume the prior distribution and likelihood discussed in Section 3. In particular, this implies that for each x ∈ X, the posterior distribution of f (x) given F n is Gaussian, with mean and standard deviation denoted by µ n (x) and σ n (x), respectively. Lemma 1. Suppose that X is finite, and letS ∞ = {x ∈ X : ∃ X ⊂ X s.t. x ∈ X ∧ P ∞ (O A (f ) = X) > 0}.Then, both S ∞ and the image of f over this set are F ∞ -measurable.Proof. Clearly, the set S ∞ is F ∞ -measurable. Thus, it suffices to show that for eachx ∈ S ∞ , f (x) is F ∞ -measurable.Let x ∈ S ∞ . By definition, there exists a subset X ⊂ X such that P ∞ (O A (f ) = X) > 0. Moreover, a standard martingale argument shows that lim n→∞ P n (O A (f ) = X) = P ∞ (O A (f ) = X) almost surely. Consequently, there exists ϵ > 0 such that P n (O A (f ) = X) > ϵ for all sufficiently large n, implying that the event X n = X occurs infinitely often.It is not hard to see that σ n (x) → 0 as n → ∞ if x is selected infinitely often. Furthermore, since x n = argmax x ′ ∈Xn σ n (x ′ ), X is finite, and X n = X occurs infinitely often, it follows that σ n (x ′ ) → 0 as n → ∞ for each x ′ ∈ X, and in particular for x. By Proposition 2.9 in [51] , it follows thatµ n (x) → f (x). Since µ n (x) is F ∞ -measurable for each n, it follows that f (x) is F ∞ -measurable for each x ∈ S ∞ .Theorem 1. Suppose that X is finite and that the target set estimated by A is complement-independent. If the sequence of points {x n } ∞ n=1 is chosen according to the PS-BAX algorithm, then for each X ⊂ X,lim n→∞ P n (O A (f ) = X) = 1{O A (f ) = X} almost surely for f drawn from the prior. Proof. Recall that lim n→∞ P n (O A (f ) = X) = P ∞ (O A (f ) = X) almost surely. Thus, it remains to show that P ∞ (O A (f ) = X) = 1{O A (f ) = X} almost surely.Let S ∞ be defined as in Lemma 1. Since X is finite, by the definition of S ∞ , it follows that P ∞ (O A (f ) ⊂ S ∞ ) = 1. Moreover, by the law of iterated expectation, it also holds thatP(O A (f ) ⊂ S ∞ ) = 1.Since O A (f ) is complement-independent, it is fully determined by the values of f over S ∞ whenever O A (f ) ⊂ S ∞ . By Lemma 1, we know that both S ∞ and the image of f over this set are F ∞measurable. Therefore, for any fixed X ⊂ X, we have{O A (f ) = X} ∩ {O A (f ) ⊂ S ∞ } ∈ F ∞ , and hence, P ∞ (O A (f ) = X, O A (f ) ⊂ S ∞ ) = 1{O A (f ) = X}1{O A (f ) ⊂ S ∞ }.A (f ) ⊂ S ∞ ) = P ∞ (O A (f ) ⊂ S ∞ ) = 1, we conclude that P ∞ (O A (f ) = X) = 1{O A (f ) = X} almost surely.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.To reduce to standard BO, one can define the target set OA(f ) as the points x ∈ X that maximize f , i.e., OA(f ) = argmax x∈X f (x) (often a singleton set). 


Decision: This paper considers the Bayesian optimization execution framework, deriving a simple yet effective and scalable posterior sampling algorithm with both theoretical and empirical validation. All reviewers agreed that the proposed algorithm is interesting and valuable. In the meantime, we do received concerns in the soundness of the theory of this paper about the consistency proof and the boundedness assumption. After several rounds of interactions between reviewers and authors, the main concerns have been well addressed and so the consensus was made to accept this paper. 

In the final version of this paper, the authors are required to improve the clarity of this paper in 
- clearer notation definitions;
- explicitly present the boundedness assumption and discuss its limitation and necessarity of having this assumption
- clarify the consistency result in theorem 1.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Please see weakness.
limitations: limitations: The checklist mentions that it discusses the limitation in section 4.3, but I cannot find it.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: 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?

Comments: title: Thank You for Your Feedback and Fruitful Discussions
quick questions
Received.
Follow-up on NeurIPS Submission Discussion
comment: 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
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
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.
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?
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
Thanks for the response! The batch-based experiments make sense to me. I have raised the score to 5.
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
Dear Reviewer BTqx,

Thank you once again for your thoughtful feedback and support of our work.

Sincerely,

The Authors
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.
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
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).
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
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.
Thanks. I will keep my (positive) score.
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
Thanks for your summary of key comments and responses. Every paper will be seriously treated and fully discussed.
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