acceptodds
Under review as a conference paper at ICLR 2027

Non-Replacement Function Space Sampling for Bayesian Optimization

18 views

Abstract

Bayesian optimization (BO) is a probabilistic framework for optimizing expensive black-box functions through sequential decision making guided by an acquisition function. Existing acquisition strategies explicitly balance exploration and exploitation, often requiring carefully designed heuristics or hyper-parameter tuning. We introduce Non-Replacement Function Space Sampling (NRFS), achieving desired exploration-exploitation balance by prioritizing the functions that have not contributed to previous acquisition decisions, rather than relying on explicit tuning. By establishing a correspondence between each candidate and the set of functions that consider it as the corresponding optimizer, NRFS induces a principled and efficient search strategy in the design space. Empirical evaluations on a diverse set of benchmark problems demonstrate that NRFS outperforms state-of-the-art BO methods, particularly in challenging regimes that demand both global exploration and local refinement. Moreover, we provide theoretical guarantees that NRFS converges for any Lipschitz-continuous objective function, regardless of the complexity of its landscape.

Primary area:
optimization
Keywords:
Bayesian Optimization, Non-replacement Function Space Sampling (NRFS), Probability of Optimality

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_bvkGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper considers Bayesian Optimization and proposes the so-called “Probability of Optimality (PO)”, which aims to directly estimate the probability of a candidate being the global optimizer, P(x=x∗)P(x = x^*), under a Gaussian process posterior. Empirically, this probability is estimated by Monte Carlo: draw MM functions from the GP posterior, take each one's minimizer, and smooth the MM minimizers into a density (KDE in continuous space). Given that plain PO is too exploitative that can end up cluttering, they propose a Non-Replacement Function Sampling, a rejection sampling that keeps only the sampled functions whose minimum is strictly below the current best (in terms of minimization) observation and use that to form the estimation. The paper also gives an analytical surrogate by using the mean of the truncated normal distribution and shows, asymptotically with noise-free observations, in a compact domain setting, simple regret tends to zero. It also empirically compared with other acquisition functions, and plain PO on synthetic benchmarks and real-world tasks, showing competitive experiments.

Critical strengths
  • Clarity: In general the paper is very easy to follow, the idea is simple and seems to be empirically effective.
  • The paper provide a thorough literature coverage on similar topic.
Critical weaknesses

Behind the nice (maybe fancy) story, I think the main trick the paper does is essentially a rejection sampling to get rid of the over-exploitation issue of the original PO, which has already be mentioned as a limitation in the Hennig paper and hence, to me, is too straightforward (a.k.a., incremental). Hence, I do not think this work add anything new either in terms of the aforementioned perspective, or any new machinary to BO community (as it is simply sample based KDE estimation). Some other weakness considerations are:

  • Inappropriate examples: Although straightforward, I also feel the bucket function example somewhat heuristic, as function space is simply uncountable, which is to me not an appropriate example to mention there.
  • The paper does not provide any finite-sample guarantee (which to me seems also non-trivial for the method) for the original .
Questions for authors

I dont have any further questions.

2 comments

We appreciate the reviewer’s comments and acknowledgment of the clarity of our paper and the comprehensive discussion of related studies on acquisition function design. Regarding the remaining concern, we provide the following explanation in the hope that it will clearly address and clarify the reviewer’s concern.

Finite-sample guarantee

By “finite-sample guarantee for the original,” does the reviewer refer to the sampling based NRFS? If so, we agree with the reviewer that establishing a finite-sample guarantee for the sampling based NRFS is indeed non-trivial. This difficulty primarily arises because of the stochasticity in acquisition locations in BO. The number of function samples required is strongly dependent on both the dimensionality of the design space and the landscape of the objective function, with the latter being particularly difficult to characterize in a black-box setting.

Nevertheless, our non-replacement sampling strategy, conditioned on xf∗∗∉Xnx_{f^*}^*\notin X_n, ensures that previously evaluated locations are excluded from subsequent optimizer sampling. Consequently, in practical applications with a prescribed minimum resolution of the design space, the method has the finite-sample convergence guarantee. However, its convergence speed remains difficult to predict, unlike the analytical NRFS without stochasticity, for which we provide a convergence rate in Appendix A.2.4.

Inappropriate examples

Regarding the concern about the example, the bucket concept is mathematically defined in (1), so we think that the uncountability of the function space has no conflict with this definition, since a bucket serves as a categorical representation and can naturally contain an uncountable number of functions. Nevertheless, we would appreciate it if the reviewer could kindly elaborate on why this example may give readers a heuristic impression, so that we can better understand the concern and revise the presentation accordingly.

Incremental study

The core idea of NRFS is to focus on the uncertainty of the objective function given all the observations, and estimate the corresponding acquisition function under iteratively updated functional uncertainty to guide BO more effectively. An important new contribution of this work is, when estimating functional uncertainty for acquisition function design, we should account for function samples that have the possibility of representing the true objective function. To the best of our knowledge, this perspective has not been explored in previous studies, making our work conceptually distinct.

As a minor clarification, Hennig's original work does not directly use the probability of optimality as an acquisition function. Rather, it first discusses the local trapping issue of EI and PI and proposes Predictive Entropy Search (PES) to improve exploration by estimating and reducing the entropy of the optimizer distribution. Since entropy estimation and direct sampling from the optimizer distribution are fundamentally different approaches, we believe our work is conceptually distinct from Hennig's original method.

Technically, our strategy is not applying rejection sampling for acquisition function estimation. Rather, our strategy focuses on the set (bucket) of candidate objective functions which are possible to be the true objective function given all the observed queries. When estimating the acquisition function, conditional sampling is implemented within the set (bucket), avoiding sampling functions which are not possible to be the true objective, instead of randomly sampling functions from the typical GP surrogate class as done in existing BO methods.

Could you please let us know whether our response has fully or partially addressed your concerns? We would greatly appreciate any feedback or clarification you may have. Thank you for your consideration!

Reviewer_wcRXOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Non-Replacement Function Space Sampling (NRFS) for Bayesian optimization, which groups surrogate function realizations by their global optimizer locations and estimates the probability that each candidate is the global optimizer to guide the next evaluation of an expensive black-box function. Its central mechanism uses the best observed objective value as a threshold to exclude sampled functions whose optima cannot improve upon the incumbent, then selects candidates according to the optimizer distribution of the remaining functions, aiming to reduce redundant sampling while balancing exploration and exploitation. The authors additionally develop a one-step-look-ahead variant, NRFS(OSLA), and an analytical variant, NRFSA, and provide convergence and simple-regret rate analyses for the analytical acquisition function. Experiments cover synthetic functions, materials property optimization, and high-dimensional applications, with additional evaluations of batch optimization, noise robustness, and computational runtime.

Critical strengths
  1. An insightful function-space perspective: Connecting optimizer probabilities with the filtering of sampled functions provides an intuitive and interpretable approach to reducing repeated sampling in local regions while remaining closely aligned with the optimization objective.

  2. Broad empirical evaluation: The main experiments report performance and variability across 20 independent trials, while the appendix additionally examines noise robustness and per-iteration runtime, supporting an assessment of optimization quality, stability, and computational overhead.

Critical weaknesses
  1. Unclear probability conditioning: Equation (13)'s failure-probability product omits explicit conditioning on adaptive query histories and previous failures, leaving its consistency with Equation (9) and the OSLA derivation in Equation (16) unclear.

  2. Unjustified analytical connection: The M=1M=1 transition from Equation (12)'s optimality probability to Equation (17)'s truncated expectation lacks formal justification, while Theorem 1's NRFSA guarantee does not cover finite-sample, density-estimated NRFS.

  3. Incomplete mechanism ablation: Although Figure 3 compares PO and NRFS, sensitivity to MM and Parzen bandwidth is not evaluated, leaving the robustness of truncation gains to estimation choices unestablished.

Questions for authors
  1. Cumulative optimality proof: Could the authors derive Equations (13) and (16) under adaptive queries, conditioning on history and previous failures, while reconciling Equation (9)'s conditional probabilities with Equation (13)'s apparently marginal failure-probability product?

  2. Analytical reduction and convergence: Could the authors justify how M=1M=1 connects global optimality probability (12) to truncated objective expectation (17), and establish when Theorem 1 extends from NRFSA to finite-sample, density-estimated NRFS?

  3. Non-replacement ablation: Could the authors vary MM and Parzen bandwidth in Figure 3's PO–NRFS comparison, fixing initializations, evaluation budgets, and other settings, and report performance and acquisition runtime to isolate truncation from estimation effects?

3 comments

We appreciate the reviewer’s careful examination of our development of the one-step-look-ahead variant, convergence analysis, and estimation strategy, as well as the recognition of our methodological insights and comprehensive empirical evaluation. In response to the reviewer’s questions and concerns, we have added further explanations and supplementary experimental results to the revised manuscript. All updated sections are highlighted in blue in the uploaded revision for ease of reference. We would greatly appreciate it if the reviewer could take another look at these revisions.

Conditional probability

We thank the reviewer for raising this meaningful and insightful question. We agree that the distinction between the unconditional and conditional formulations deserves further clarification. Specifically, (13) is formulated under the assumption that TT observations have already been collected, such that their objective values are fixed. Accordingly, the matching events are evaluated relative to the previously observed locations and become independent events. The corresponding conditional formulation can be expressed as 1−∏t=1T[1−P(xf∗∗=xt∣xf∗∗∉Xt−1)].1-\prod_{t=1}^T\left[1-P\left(x_{f^*}^*=x_t\mid x_{f^*}^{*}\not \in X_{t-1}\right)\right]. When considering the matching probability among the previously collected observations, the conditioning can be omitted to recover (13). However, when selecting the next acquisition point, the decision must account for the previous observations, and retaining the conditional formulation explicitly incorporates this dependence into the sequential acquisition process. We will revise the corresponding discussion to clarify this distinction and avoid potential confusion.

Connection between NRFS and NRFSA

We sincerely thank the reviewer for pointing out the missing explanation of the connection between NRFS and NRFSA. In general, the relationship can be understood as follows: NRFS uses multiple function samples to estimate the quantity in (12), whereas NRFSA uses the most probable function sample among the collected samples to compute (12) directly. Specifically, NRFSA can be viewed as a special case of the original NRFS. According to (12), if we sample the most probable function realization from the truncated region, (12) can be converted to ∏x~∈X, x~∉Xn∪xH[f¨(x~)−f¨(x)]\prod_{\substack{\tilde{{x}}\in\mathcal X,\ \tilde{{x}}\notin{X_n\cup{x}}}}H[\ddot{f}(\tilde{{x}})-\ddot{f}({x})], where f¨\ddot{f} denotes a randomly sampled function realization from the truncated GP surrogate class. We then approximate this sampled function realization by the mean function f~\tilde{f} of the truncated GP, which represents its central predictive estimate. In this case, only the location with the minimum expected value has a Heaviside step function value of 1, while all other locations have a value of 0. Therefore, identifying the minimizer of (17) is equivalent to identifying the maximizer (location provides 1) of the transformed expression in (12).

Since, to the best of our knowledge, there is no well established theoretical framework specifically addressing the stochastic behavior of products of Heaviside step functions evaluated on black-box function samples over a continuous domain, we use the central predictive estimate to obtain a more tractable representation of the product and facilitate the theoretical analysis. This also clarifies the condition required for extending the theoretical results from NRFSA to NRFS, as M→∞M \to \infty, the sampled function realizations must approach the central predictive estimate, thereby establishing the connection between the two methods. We will revise the corresponding content to include these clarifications and discussions.

Effect of function sample number

We also appreciate the reviewer's suggestion to investigate the effect of MM on NRFS. These additional experiments demonstrate that, as M→∞M \to \infty, NRFS becomes less stochastic as the uncertainty arising from finite sample estimation of the optimizer distribution vanishes, exhibiting increasingly deterministic behavior similar to that of NRFSA, consistent with our theoretical analysis. We have added the corresponding results for four benchmark synthetic objective functions in the main text and Appendix A.6. Among the six test functions, the Forrester function does not exhibit a clear trend as MM increases. For the other functions, particularly the Rosenbrock function, NRFS increasingly exhibits behavior similar to NRFSA as MM grows. We observe a similar trend in the PO results. We have also reported the computational time with different MM in Appendix A.6. As expected, the computational cost increases with MM for both methods. The increase is more pronounced for NRFS than for PO, which is expected because NRFS involves truncated Gaussian sampling, requiring additional computations for CDF evaluation and inverse CDF sampling.

Bandwidth effect

Regarding the effect of bandwidth selection, we use Silverman's rule, which is an adaptive bandwidth selection method rather than a fixed bandwidth. Therefore, instead of simply investigating whether larger or smaller bandwidths perform better, we compare several commonly used bandwidth selection strategies, including Scott's rule and the Sheather Jones (SJ) method. We would be appreciated if the reviewer could refer to the detailed results in Appendix A.13. Overall, the different bandwidth selection strategies exhibit comparable performance, making it difficult to identify a universally superior choice. The only exception is the SJ method, which fails to converge on the GM problem. One possible explanation is that its bandwidth selection may provide accurate density estimates in data rich regions but perform less reliably in data sparse regions, thereby compromising the exploration capability of NRFS.

Thanks for the author's response, I have no further questions for the authors and keep my positive assessment of the paper.

Reviewer_fFg5OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Non-Replacement Function Space Sampling (NRFS), a Bayesian optimization strategy based on the posterior probability that a candidate is the global optimizer. The method groups surrogate functions according to their optimizer locations and seeks to prioritize functions whose optima have not been covered by previous evaluations. The authors formulate this mechanism through a truncated function distribution conditioned on improving upon the current best observation. They further develop a one-step-look-ahead acquisition function that combines immediate and anticipated future probabilities of identifying the optimum, as well as an analytical variant based on truncated Gaussian expectations. The paper presents a convergence analysis for the analytical variant and evaluates the proposed methods on synthetic benchmarks and materials optimization tasks, with additional experiments on batch selection, high-dimensional problems, and observation noise. The reported results suggest improved optimization performance across several tested settings.

Critical strengths
  1. Identifying the global optimizer is central to black-box optimization, and directly targeting its posterior probability is a nontrivial task. Building on existing approaches that model this distribution, NRFS introduces a non-replacement mechanism that conditions the function distribution on the possibility of further improvement and uses the resulting probability of optimality to guide acquisition. This provides an intuitive alternative to conventional acquisition criteria and offers potential for broader integration into GP-based Bayesian optimization frameworks.
  2. The formulation provides a clear interpretation of the proposed search strategy: when further improvement is needed, attention is concentrated on function hypotheses that still admit a better solution in unexplored regions. The one-step-look-ahead extension further considers both the probability of immediate success and the potential for an observation to improve the next acquisition decision. This gives the method an understandable rationale for balancing immediate optimization progress with the value of additional information.
  3. The experiments evaluate both NRFS and its one-step-look-ahead variant against a broad set of commonly used acquisition functions. The reported results show strong overall performance, with substantial improvements on several benchmarks and materials optimization tasks. Additional evaluations examine batch acquisition, higher-dimensional settings, and robustness to observation noise. Results over 20 independent runs, together with the reported variability, strengthen confidence that the observed advantages are not driven by a single favorable initialization.
Critical weaknesses

The empirical evaluation could provide broader evidence of general applicability. Although the appendix includes additional benchmarks, the main evaluation focuses on a relatively small collection of synthetic functions and materials optimization tasks. A more systematic evaluation across diverse problem classes would strengthen the empirical contribution. For example, standardized black-box optimization benchmark suites, end-to-end machine learning hyperparameter tuning, and further real-world applications. Such experiments would help establish whether the reported advantages persist across different objective structures, dimensionalities, and evaluation budgets.

Questions for authors

Please see weaknesses.

2 comments

We sincerely thank the reviewer's acknowledgement on our novel concept, clear theoretical formulation and strong empirical experimental results.

Additional results

For the additional experiments to enrich our collection of tested objectives, we have incorporated two more standardized black-box optimization benchmark functions, Styblinski Tang and Langermann, which have been used in BO studies. We included NRFS and PO as additional primary methods for comparison.

Regarding the effects of different objective function structures, we provide a brief discussion in Appendix A.4 on how landscape characteristics influence the behavior of different acquisition functions. Regarding dimensionality, we have included additional experimental results investigating performance across different dimensionalities in Appendix A.8. Regarding the effect of evaluation budgets, we consider this a valuable suggestion and an interesting direction for future research. Currently, most acquisition functions do not explicitly incorporate the available evaluation budget as a factor in their design, and therefore changing evaluation budget does not change the optimization behavior accordingly. We will investigate how to systematically incorporate evaluation budgets into acquisition function design to improve budget aware optimization performance.

Furthermore, to investigate how other experimental settings affect acquisition performance, we have added additional experiments in main text, Appendices A.6 and A.13 to examine the effects of the number of sampled functions and bandwidth selection respectively. In general, as more function samples are collected, NRFS gradually loses its stochasticity and exhibits behavior increasingly similar to NRFSA. Whether reduced stochasticity is beneficial depends on the complexity of the objective landscape. For complex objective landscapes, greater stochasticity can be advantageous to help escape from local optima, as demonstrated in Figure 15. To investigate the effect of bandwidth selection, we additionally implemented two bandwidth selection strategies, the Scott's method and Sheather Jones method, alongside the original Silverman's method. As shown in Figure 16, we observed relatively minor differences in optimization performance across these bandwidth selection strategies. This may be because different bandwidth selection methods primarily affect the shape of the estimated density function without substantially changing the locations of its maximizers.

Reviewer_fFg5OpenReview ↗

Response

I have no further questions regarding to the authors' work. I will remain my positive assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.