Stopping Bayesian Optimization with Probabilistic Regret Bounds

Authors: james t wilson
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:32:33

Abstract: Bayesian optimization is a popular framework for efficiently tackling black-box search problems. As a rule, these algorithms operate by iteratively choosing what to evaluate next until some predefined budget has been exhausted. We investigate replacing this de facto stopping rule with criteria based on the probability that a point satisfies a given set of conditions. We focus on the prototypical example of an $(\epsilon, \delta)$-criterion: stop when a solution has been found whose value is within $\epsilon > 0$ of the optimum with probability at least $1 - \delta$ under the model. For Gaussian process priors, we show that Bayesian optimization satisfies this criterion under mild technical assumptions. Further, we give a practical algorithm for evaluating Monte Carlo stopping rules in a manner that is both sample efficient and robust to estimation error. These findings are accompanied by empirical results which demonstrate the strengths and weaknesses of the proposed approach.

Main paper: 
 introduction: 
 In the real world, we are often interested in finding high-quality solutions to black-box problems. Many of these problems are not only expensive to solve but difficult to reason about without extensive background knowledge-such as discovering new chemicals [17] , designing better experiments [48] , or configuring machine learning algorithms [42] .A common approach is therefore to construct models for these problems and use them to predict real-world outcomes. In recent years, Bayesian optimization (BO) has emerged as a leading approach for accomplishing these tasks. Precise definitions vary, but BO methods are frequently characterized by their use of probabilistic models to guide the search for good solutions. The idea is for these models to provide distributions over the performance of competing alternatives, which can then be used to simulate the usefulness of evaluating different things. For a recent review, see Garnett [16] .Despite the success of these algorithms, an ongoing issue for practitioners has been the continued lack of interpretable stopping rules. The vast majority of BO runs proceed until a predetermined budget (e.g., a number of evaluations or amount of resources) is exhausted. We highlight two likely reasons for this trend and then give a brief prospective for model-based alternatives. The first reason is that stopping rules often revolve around quantities like optimums that are difficult to work with, even when defined under a model. The second is that even the best models sometimes go astray; and, if the model is bad, then model-based stopping is liable to stop much too soon or far too late. To avoid potential disappointment, let us say upfront that this work addresses the former challenge and only provides mild commentary on the latter. We will revisit this topic in the closing sections.At the same time, we argue there is much to be gained by using models to help us decide whether a given solution is "good-enough" for its intended purpose [40] . One benefit of model-based stopping is its ability to adapt to the data. Sometimes, we will get lucky and stumble upon good solutions early on. Other times, our progress will be slow. If the model captures these events, then stopping can be tailored to each run. Another benefit of model-based stopping is its ability to simplify the user experience by asking us to specify what we wish to find instead of how much we wish to spend.The basic idea we pursue is that, if we can simulate whether a solution is good-enough, then we can stop once we find one that probably is. We focus on a prominent example of this framework, but stress that much of what follows holds for different choices of models and conditions. In particular, we investigate the setting where the user deems a solution sufficient if its performance is within ϵ > 0 of the optimum with probability at least 1 -δ under the model. Our primary contributions are to: i) combine recent work on scalable sampling techniques with algorithms for cost-efficient statistical testing; ii) show how the resulting estimators can be used as the basis for robust stopping rules; and, iii) introduce the first model-based stopping rule for BO with convergence and performance guarantees (up to model error).The remaining text is organized as follows. Section 2 presents notation background material. Section 3 introduces the proposed stopping rule and evaluation strategy. Section 4 analyzes this algorithm's convergence and correctness. Finally, Section 5 investigates its empirical performance under idealized and realistic circumstances. 
background: 
 We use boldface symbols to indicate vectors (lowercase) and matrices (uppercase). Given a sequence (a i ), we denote a n = [a 1 , . . . , a n ] ⊤ . Likewise, for a function f : X → R, we use the shorthand f (X n ) = [f (x 1 ), . . . f (x n )] ⊤ . By minor abuse of notation, we sometimes treat, e.g., X n as a set.We focus on the task of sequentially querying a function f : X → R in order to find a point x ∈ X whose value f (x) is within ϵ > 0 of the supremum. Such a point is said to be ϵ-optimal if this condition holds and (ϵ, δ)-optimal if it holds with probability at least 1 -δ. Throughout, we write (x t ) for the sequence of query locations.At any given time t ∈ N 0 , our understanding of the target function's behavior is driven by domain knowledge and any data that we have already collected. We combine this information with the help of a Bayesian model by placing a prior on f and defining an observation model. Different types of models are eligible and techniques introduced in the sequel simply require that we are able to simulate the chosen stopping conditions (e.g., ϵ-optimality). We focus on the most popular family of models in this setting: Gaussian processes.A Gaussian process (GP) is a random function f : X → R such that, for any finite set X ⊆ X , the random variable f (X) ∈ R |X| is Gaussian in distribution. We write f ∼ GP(0, k) for a centered GP with covariance k : X × X → R and model observations as function values corrupted by independent Gaussian noise, i.e. y(X t ) | f (X t ) ∼ N f (X t ), γ 2 I . Conditional on y(X t ), we therefore believe that f is distributed as f t ∼ GP(µ t , k t ), where Λ = k(X t , X t ) + γ 2 I is used to defineEQUATIONFinally, we assume that X is compact and that µ t and k t are both continuous so their limits are attained on X . Among other things, this assumption allows us to write s t ∈ arg max x∈St µ t (x) for a preferred solution at time t, where S t is either the set of evaluated points X t or the search space X .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The primary limitation of the proposed is that it relies on an underlying model being well-calibrated. This issue is clearly discussed at prominent locations in the text, such as the introduction and experiments section.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • 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. 
method: 
 Suppose Bayesian optimization terminates at time t ∈ N 0 and returns a point x ∈ X as the solution.Our regret for having returned this point is defined as the distance between f (x) and the optimum. Under the model f t , this (simple) regret manifests as a random variableEQUATIONGiven a regret bound ϵ > 0 and a risk tolerance δ > 0, we would like to stop searching once we have found a point so that r t (x) ≤ ϵ with probability at least 1 -δ and refer to this stopping rule as a probabilistic regret bound (PRB). Probabilities of this sort are usually intractable and we will therefore estimate them via sampling. To this end, we denote the probability that a point x is Risk Tolerance δ1 1 1 1 1 1 1.99 1 1 1 1 1 1. 93 Figure 1 : Overview of PRB stopping behavior when f : [0, 1] 2 → R is drawn from a model with noise variance γ 2 = 10 -4 . Regret bounds ϵ > 0 dictate how close f (x) must be to the optimum f * for x ∈ X to be satisfactory. Tolerances δ > 0 upper bound the chance of returning an unsatisfactory point. Left: Percent of runs that stopped before time T = 128. Middle: Percent of stopped runs that returned ϵ-optimal points. Right: Median number of trials performed by stopped runs.ϵ-optimal and an associated Monte Carlo estimator byEQUATIONwhere r i t (x) is the i-th independent draw of the model-based regret (2). We will shortly explore how to construct estimators Ψ n t (x) and use them to decide whether Ψ t (x) is above or below a level λ ∈ R in a manner that is both cost efficient and robust to estimation errors. First, however, let us introduce some basic terminology that will help us reason about potential failure modes.We will say the estimator produces a false positive if Ψ n t (x) ≥ λ > Ψ t (x) and a true positive ifΨ n t (x) ≥ λ ∧ Ψ t (x) ≥ λ.Since either scenario may lead to an unsatisfactory solution, the level λ that we compare against must exceed 1 -δ. Accordingly, let δ mod and δ est be nonzero probabilities such that δ mod + δ est ≤ δ. By defining λ = 1 -δ mod , we will use δ mod to limit the chance that a point x is not ϵ-optimal even though Ψ n t (x) produced a true positive. Conversely, we will use δ est to control the probability of encountering a false positive (see Section 3.2). This pattern guarantees that if Ψ n t (x) ≥ λ, then x is ϵ-optimal with probability at least 1 -δ under the model.Algorithm 1 BO with Monte Carlo PRB 1: input data D ∈ (X × R) T0 , limit T ∈ N, and parameters ϵ, δ mod , δ est > 0 2: (δ t est ) ← getSchedule δ (δ est , T -T 0 ) 3: for t = T 0 , . . . , T do 4: f ← getModel(D) 5: C ← getCandidates(f, D) 6: Z ← MC-PRB(C; f, ϵ, δ mod , δ t est ) 7: if max Z ≥ 1 -δ mod then 8: break 9:x ← getNextQuery(f, D)10: D ← D ∪ {(x, y(x))} 11: return x i ∈ C : Z i = max ZAlgorithm 1 sketches a typical BO loop with the proposed stopping rule. At each iteration, we obtain a model for the data. We then select candidate solutions C ⊆ X and estimate their probabilities of being ϵoptimal under the model. If an estimate is greater than 1 -δ mod , then the corresponding point satisfies the stopping conditions with probability at least 1 -δ and we terminate; otherwise, we press on.The rest of this section examines two key questions: how to simulate model-based regrets r t (x) when |X | is large (or infinite) and how to avoid false positives due to estimation error. Appendix A explores related topics such as how to choose C and schedule δ t est . Figure 1 shows how the proposed algorithm behaves for different choices of ϵ and δ. Data was generated by running BO a hundred times and sampling r t (s t ) a thousand times per step using the strategy from Section 3.1. Stopping decisions were then made by comparing estimators Ψ n t (s t ) with λ = 1 -δ mod , where δ mod = δ /2. These results do not take advantage of the testing paradigm introduced in Section 3.2, but accurately reflects the algorithm's behavior. In particular, we see that the number of function evaluations performed by each run automatically adapts to the definition of (ϵ, δ)-optimality. f t (x), f t (x) | f t (x) ≤ f * t , or f t (x) | f t (x) ≤ f * t ∧ f t (x * t ) = f * t where f * t and x * t ∈ arg max x∈X f t (x)were jointly sampled.This section describes how to simulate whether a point x ∈ X satisfies the chosen stopping conditions.For PRB, this amounts to sampling Bernoulli random variables 1(r t (x) ≤ ϵ). We propose to generate this term by maximizing draws of f t . When dealing with parametric models, function draws are obtained by sampling parameter vectors. For GPs, analogous logic may be enacted by using a parametric approximation to the prior [52] , as outlined below. This approximate sampling step is necessary because the time complexity for exactly simulating f t (X) scales cubically in |X|.Let ϕ : X → R m be a finite-dimensional feature map so that, ∀x,x ′ ∈ X , ϕ(x) ⊤ ϕ(x ′ ) ≈ k(x, x ′ ).Note that feature maps of this sort are readily available for many popular covariance functions [37, 52] .Equipped with such a map, we may approximate a prior f ∼ GP(0, k) with a Bayesian linear modelEQUATIONLetting Λ = k(X t , X t ) + γ 2 I and ε ∼ N (0, γ 2 I), this linear model may be used to generate draws from an approximate posterior by sampling w from the prior and using Matheron's rule to write [51] EQUATIONFor each draw of f t , the remaining problem is now to evaluate 1(r t (x) ≤ ϵ). We suggest using multi-start gradient ascent. In our case, we performed an initial random search to identify promising starting locations and then used a quasi-Newton method [28] to optimize. A helpful insight is that we do not need to find f * t per se. Rather, it suffices to determine whether there exists a pointx ′ ∈ X such that f t (x ′ ) -f t (x) > ϵ.This property can be exploited to accelerate simulating 1(r t (x) ≤ ϵ); however, its benefits wane as Ψ t (x) increases because r t (x) ≤ ϵ implies that no such point x ′ exists.The right panel of Figure 2 compares different estimators for Ψ t . For simplicity, assume that f t is sample continuous so that it almost surely attains its supremum on X . The goal of this plot is to highlight challenges inherent to conditioning on the maximum. We not only need to upper bound f t , but also account for the point(s) at which the maximum is achieved. This explains why the red estimatorE x * t ,f * t [P(f * t -f t (x) ≤ ϵ | f t (x * t ) = f * t , f t (x) ≤ f * t )] outperforms the orange one E f * t [P(f * t -f t (x) ≤ ϵ)], while the green one E f * t [P(f * t -f t (x) ≤ ϵ | f t (x) ≤ f * t )] fails to do so. We opted to avoid these issues by sampling f t (x) jointly with f * t rather than marginalizing it out. The resulting blue estimator is seen to more accurately follow the gold standard shown in black.Lastly, it should be said that the suggested sampling procedure introduces a yet-to-be-determined amount of error in practice, since draws of f t are not only approximate but non-convex. Initial results suggest these errors are small (see Figure 2 ), however we leave this as a topic for future investigation. CDFs of Ψ n t when optimizing draws from known priors GP(0, k) in two, four, and six dimensions with noise variance γ 2 = 10 -6 (solid, •) or γ 2 = 10 -2 (dashed, ×). PRB parameters were set to ϵ = 0.1 and δ mod = δ est = 2.5%. Right: Runtimes for Algorithm 2 using the generative strategy from Section 3.1 and a (wall) time limit of roughly one thousand seconds.This section discusses the general problem of using samples to decide whether the expectation of a random variable Z ∈ {0, 1} exceeds a level λ ∈ [0, 1]. For PRB, λ = 1 -δ mod and each evaluation of the stopping rule corresponds to a unique Z = 1(r t (x) ≤ ϵ). We will show how to make probably-correct decisions using a minimal number of samples n ∈ N. In doing so, we first discuss confidence intervals for E[Z] based on a collection of i.i.d. draws Z n = {z i : i = 1 . . . , n}.There are many techniques for generating intervals that contain E[Z] with (coverage) probability at least 1 -δ est . Clopper & Pearson [13] gave an exact recipe for constructing confidence intervals for Bernoulli random variables Z asEQUATIONwhere B denotes the beta quantile function and k = n i=1 z i is the number of successes in n draws. It is also possible to take a Bayesian by placing a prior on E [Z] . Differences between this Bayesian approach and (6) were observed to be minimal however, so we opted to avoid modeling E[Z]. For further discussion, see Appendix A.1.Given an estimate Z n =1 n n i=1 z i and a confidence interval I n = CI(Z n ; δ est ), it follows thatEQUATIONIf I n collapses to a point as n → ∞, then there exist sample sizes such that λ ̸ ∈ I n , whereupon the conclusion from (7) holds with probability at least 1 -δ est . 1 Said differently, we can lower bound the probability that we correctly decide whether E[Z] ≥ λ by generating enough draws of Z. With these details in mind, we now review an algorithm for adaptively choosing n ∈ N in order to make probably-correct decisions using as few samples as possible-which is crucial when simulating Z is computationally intensive as in Section 3.1.The general idea of Algorithm 2 is to perform a series of tests (each using more samples than the last), until a confidence interval for E[Z] is narrow enough for a decision to be made. To better understand this, start by defining two sequences: sample sizes (n j ) and risk tolerances (d j ). The sizes should be increasing, while the tolerances should be positive and satisfy ∞ j=1 d j ≤ δ est . Next, imagine that we generate draws of Z in batches of size n j -n j-1 , where n 0 = 0. At each round of sampling j, we construct an interval I nj that contains E[Z] with probability at least 1 -d j . If λ ̸ ∈ I nj , we use Z nj to decide whether E[Z] ≥ λ. Otherwise, we proceed to the next iteration. f i ← getSample(f ) 8: f i * ← sup x∈X f i (x) 9: Z ← Z ∪ 1(f i * -f i (x) ≤ ϵ) 10: if 1 -δ mod ̸ ∈ CI(Z, d j ) then 11:break 12: return Average(Z) Per (7) , this algorithm only makes an incorrect decision if the final interval fails to contain E [Z] . By definition of (d j ) and the union bound however, the chance of any interval not containing E[Z] is at most δ est . Hence, the algorithm makes the correct decision with probability at least 1 -δ est .Algorithm 2 was inspired by bandit methods, such as Mnih et al. [33] and references contained therein, who previously studied how concentration inequalities can be used to iteratively test whether , then the chance of encountering a false positive at any step is bounded from above by δ est . Consequently, the decision to stop will be correct with probability at least 1 -δ est .P Z n -E[Z] ≤ ϵ E[Z] ≥ 1-δ est .We followed Mnih et al. [33] by defining d t j = j -α (α-1) α δ t est and n j = ⌈β j-1 N ⌉. We set α = 1.1 so that (d t j ) decayed slowly, β = 1.5 such that (n j ) grew reasonably quickly, and N = 64 because smaller starting values took longer to run. These choices impact the algorithm's runtime, not its validity. Using a geometric schedule for (n j ) prevents (d t j ) from rapidly shrinking due to a large number of tests being performed with very few samples. In exchange, this schedule can lead to nearly β times too many samples being requested.The left panel of Figure 3 shows how many samples Algorithm 2 used to decide whether E[Z] ≥ λ for Z ∼ Bern(p). As p → 1, the distance between Z n and λ tends to increase and decisions can be made with wider confidence intervals constructed using fewer draws. As δ est → 1, these intervals shrink and decisions can similarly be made using fewer samples. The middle panel visualizes the empirical CDF of estimates Ψ n t from BO experiments described in Section 5. For most of a typical BO run's life cycle, these estimates are far from λ = 1 -δ mod so decisions can be made efficiently. This pattern is reflected in the rightmost panel, which illustrates the savings provided by Algorithm 2.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
analysis: 
 We show that Bayesian optimization with the PRB stopping rule terminates under mild assumptions. Further, we prove that the given algorithm is correct in the sense that it returns an (ϵ, δ)-optimal point under the model. We begin by discussing the assumptions made throughout this section, which are:A1. The search space X = [0, 1] D is a unit hypercube. A2. There exists a constant L k > 0 so that, ∀x, x ′ ∈ X , |k(x, x) -k(x, x ′ )| ≤ L k ∥x -x ′ ∥ ∞ .A3. The sequence of query locations (x t ) is almost surely dense in X .A1 and A2 guarantee it is possible for the maximum posterior variance to become arbitrarily small given a finite number of observations. Note that if hyperparameters change over time, we only require that the (best) Lipschitz constant L k and noise variance γ 2 do not grow without bounds as t → ∞. Combined with these assumptions, A3 implies that, for any C > 0, there exists a time T ∈ N 0 such that, ∀t ≥ T , max x∈X k t (x, x) ≤ C with probability one. More generally, A3 is necessary to ensure convergence when all we known is that X is compact and f is continuous [45] .When A1 and A2 hold, popular strategies often produce almost surely dense sequences (x t ). For instance, Vazquez & Bect [47] proved Probability of Improvement [25] and Expected Improvement [38] exhibit this behavior for many covariance functions k when f is directly observed. In Appendix B, we show that this result holds for continuous acquisition functions that value informative queries over unambiguous ones. This family includes well-known acquisition functions such as Knowledge Gradient [15] , Entropy Search [20] , and variants thereof [21, 49] . Finally, dense sequences can be guaranteed by introducing a small chance for queries to be selected at random from an appropriately chosen distribution [44] .We first prove that points which maximize the posterior mean eventually satisfy the PRB criterion and then use this result to demonstrate convergence and correctness. Proposition 1. Under assumptions A1-A3 and for all regret bounds ϵ > 0 and risk tolerances δ > 0, there almost surely exists T ∈ N 0 so that, at each time t ≥ T , every s t ∈ arg max x∈X µ t (x) satisfiesEQUATIONSketch. We sketch the proof below and provide full details in Appendix B for details. Consider the centered processg t (•) = [f t (•) -f t (s t )] + [µ t (s t ) -µ t (•)]. Since the second term is nonnegative, g * t = sup x∈X g t (x) ≥ r t (s t ) = f * t -f (s t )and it suffices to upper bound the probability thatg * t ≥ ϵ. For ϵ > E(g * t ), such a bound may be constructed by using the Borell-TIS inequality [8, 46] to writeEQUATIONSince E(g * t ) and ( 9) both vanish as σ t decreases, the claim holds so long as lim t→∞ σ t = 0. □ Similar ideas can be found in Grünewälder et al. [18] , who proved that the expected supremums of centered process like g t go to zero as (x t ) becomes increasingly dense in X . In Appendix B, we extend this result to the setting where observations are corrupted by i.i.d. Gaussian noise and combine it with the Borell-TIS inequality to show the probability that r t (s t ) ≥ ϵ vanishes. We also give a simple corollary for the case where solutions s t belong to X t . Next, we show that BO not only stops when Algorithm 2 is used to evaluate the proposed rule but does so correctly. Proposition 2. Suppose assumptions A1-A3 hold. Given a risk tolerance δ > 0, define nonzero probabilities δ mod and δ est such that δ mod + δ est ≤ δ and let (δ t est ) be a positive sequence so that ∞ t=0 δ t est ≤ δ est . For any regret bound ϵ > 0, if Algorithm 2 is run at each step t ∈ N 0 with tolerance δ t est to decide whether a point s t ∈ arg max x∈X µ t (x) satisfies the stopping criterionEQUATIONthen BO almost surely terminates and returns an (ϵ, δ)-optimal solution under the model.Proof. By Proposition 1, there almost surely exists an S ∈ N 0 so that t ≥ S =⇒ Ψ t (s t ) ≥ 1-δ mod . Further, because Ψ n t (s t ) is unbiased, there exist times t ≥ T at which Algorithm 2 produces true positivesΨ n t (s t ) ≥ 1 -δ mod ∧ Ψ t (s t ) ≥ 1 -δ mod .Hence, BO stops with probability one. If BO terminates at time T ∈ N 0 , then the probability that s T is not ϵ-optimal is less than or equal to δ mod in the event of a true positive and one otherwise. Since false positives Ψ n t (s t ) ≥ 1 -δ mod > Ψ t (s t ) occur with probability at most δ est , it follows that s T is ϵ-optimal with probability at least 1 -δ.In summary, we can design statistical tests to mitigate the risk of premature stopping due to random fluctuations in Monte Carlo estimators like Ψ n t . Moreover, we can schedule these tests to ensure that points which pass them are sufficiently likely (under the model) to satisfy our stopping conditions. If the model is correct, we can therefore guarantee that a satisfactory solution is returned with high probability. Provided that one or more points almost surely satisfy the rule as t → ∞, this result holds if we can simulate whether solutions are satisfactory and bound the error in the resulting estimator. 
experiments: 
 To shed light on how our algorithm behaves in practice, we conducted a series of experiments. Focal questions here included: i) how does PRB perform in comparison to existing stopping rules, ii) how do these rules respond to different types of problems, and iii) what is the impact of model mismatch.Experiments were performed by first running BO with conservatively chosen budgets T ∈ N. We then stepped through each saved run with different stopping rules to establish stopping times and terminal performance. This paradigm ensured fair comparisons and reduced compute overheads. We performed a hundred independent BO runs for all problems other than hyperparameter tuning for convolutional neural networks (CNNs) on MNIST [14] , where only fifty runs were carried out. Table 1 : Median stopping times and success rates when seeking (ϵ, δ)-optimal points on X = [0, 1] D given an upper limit of T ∈ N function evaluations. For GP objectives, number beside each name specify noise levels γ2 . Superscripts † indicate that model or stopping rule parameters were given by an oracle. For each problem, non-oracle methods that returned ϵ-optimal points at least 1 -δ percent of the time using the fewest function evaluations are shown in blue.Despite the general notation of the paper, all problems were defined as minimization tasks. Additional details and results can be found in Appendices C and D, respectively; and, code is available online at https://github.com/j-wilson/trieste_stopping.Each BO run was tasked with finding an ϵ-optimal point with probability at least 1 -δ = 95%. On the Rosenbrock-4 fine-tuning problem, we used a regret bound ϵ = 10 -4 . For CNNs, we aimed to be within ϵ = 0.5% of the best test error (i.e., misclassification rate) seen across all runs, namely 0.62%. Likewise, when fitting XGBoost classifiers [12] for income prediction [7] , we sought to be within 1% of the best found test error of 12.89%. For all other problems, we set ϵ = 0.1.For PRB, we divided δ evenly between δ est and δ mod . Since experiments were carried out using preexisting BO runs that each began with five random trials and ended at times T , we employed a constant schedule δ t est = 1 T -5 δ est for risk tolerances at steps t ∈ N 0 . Parameter schedules for Algorithm 2 are discussed in Section 3.2.As a practical concession, we limited each run of Algorithm 2 to a thousand draws of f t and used the resulting estimate to decide whether to stop-even if the corresponding confidence interval was not narrow enough to afford guarantees. Results under this setup were consistent with preliminary experiments in which Algorithm 2 was run using a fifteen minute time limit. Finally, when optimizing draws from GP priors in six dimensions with noise γ 2 = 10 -2 , we evaluated PRB once every five steps to expedite these experiments.We tested several baselines, some of which were granted access to information that would usually be unavailable (indicated by a dagger †). We summarize these as follows 2 : B1. Oracle † : stops once an ϵ-optimal point has been evaluated. B2. Budget † : stops after a fixed number of trials chosen by an oracle for each problem.B3. Acq [23, 35] : stops when the acquisition value of the next query is negligible. B4. ∆CB [29] : stops once the gap between confidence bounds is less-equal to C > 0, i.e.max x∈X UCB t (x) -max x ′ ∈Xt LCB t (x ′ ) ≤ C [U/L]CB t (x) = µ t (x) ± β t k t (x, x)B5. ∆ES [22] : stops when an upper bound on E(f * t ) -E(f * t-1 ) drops below a level.B1 is the optimal stopping rule, but requires perfect information for f . Likewise, B2 is the optimal fixed budget for each problem. These budgets were defined post-hoc as the minimum number of trials such that at least 95% percent of runs returned ϵ-optimal points (where possible).The remaining methods are all model-based and stop when target quantities are sufficiently small. For the chosen acquisition function (see Appendix C.3), B3 can be interpreted as the expected improvement in solution quality given an additional trial, i.e. E yt+1 max x∈Xt+1 µ t+1 (x) -µ t+1 (s t ) . Unfortunately, neither this quantity nor the change in the expected supremum used by B5 lend themselves to interpretation in terms of (ϵ, δ)-optimality. B4 does admit such an interpretation for appropriate choice of constant β t [43] ; however, these constants are often difficult to obtain in practice however, so we followed [29] by defining β t = 2 5 log Dt 2 π 2 /6δ . To combat these issues, we gave baseline methods a competitive advantage by retroactively assigning cutoff values to ensure they achieved the desired success rate when optimizing draws from the model (denoted GP † ). Specifically, cutoff values for B3-B5 were obtained by dividing regret bounds ϵ by the smallest powers of two for which this condition held-explicitly: 2 15 , 2 3 , and 2 4 (respectively). Note that, in the absence of this fine tuning, these methods either proved unreliable or failed to stop within the allotted time depending on whether thresholds were too large or too small. For completion, additional results using ϵ as the cutoff value for B4 and B5 are presented in Appendix D.The main results of this section are shown in Table 1 and key findings are discussed below.When optimizing functions drawn from known GP priors, denoted GP † , the proposed stopping rule performed exactly as advertised and consistently returned (ϵ, δ)-optimal solutions. Moreover, PRB often requiring the fewest function evaluations. This result is not surprising when comparing with methods like B4 because an unbiased estimate to P(r t (x) ≤ ϵ) should exceed a level faster than a corresponding lower bound. In many cases, PRB achieved a higher success rate than the fixed budget oracle using a comparable or smaller number of trials. These gains occur because model-based stopping is able to exploit patterns in the data collected by individual runs.Elsewhere, we observe that B4 struggled to terminate when faced with moderate noise levels γ 2 = 10 -2 . This pathology likely emerges because, similar to alternative estimators discussed in Section 3.1, the method does not fully account for dependencies between f * t and f t (x). As an extreme example, B4 may fail to terminate when a point x ∈ X t simultaneously maximizes upper and lower confidence bounds, despite the fact that r t (x | x * t = x) = 0. Not surprisingly, BO runs that took longer to query an ϵ-optimal point took longer to stop. However, the correlation between these terms paled in comparison to that of stopping times and α-quantiles of regrets incurred by uniform random points (approximately, 0.35 vs. -0.75). Said differently, PRB stopped faster when f * was an outlier. This pattern suggests that the one-step optimal strategy from Appendix C.3 is better at finding optimal solutions than verifying them. Future works may therefore wish to pursue stopping-aware approaches along the lines of McLeod et al. [32] or Cai et al. [11] .In the real world, the high-level assumptions that govern how the model behaves (i.e., its hyperparameters) are tuned online as additional data is collected using Type-II maximum likelihood. We are therefore interested in seeing how discrepancies between the model and reality influence stopping behavior.Results here were similar to the synthetic setting, albeit with some blemishes. Interestingly, the most glaring example of the risks posed by model mismatch occurred on the popular Hartmann-6 test function. Here, 33% of BO runs overestimated the objective function's smoothness and converged to a local minimum of -3.20 rather than the global minimum of -3.32. It is worth noting, however, that if ϵ = 0.1 had been slightly larger, all stopping rules would have succeeded in at least 95% of cases (see Appendix D). Along similar lines, models occasionally underestimated the kernel variance when optimizing draws from GP priors and stopped prematurely.These results also indicate that both hyperparameter tuning problems (CNN and XGBoost) were fairly easy and this may have masked potential failure modes. The fixed budget oracle's performance demonstrates that there was still room for model-based stopping rules to fail, but we nevertheless recommend that these results be taken with a grain of salt.In additional experiments, we indeed found that it was easy to construct cases where poor model fits led to poor stopping behavior. This vulnerability was large due to our choice of hyperpriors (see Appendix C.1), which were purposefully broad and uninformative. Overall, we argue that these results are both highly encouraging and also highlight the importance of uncertainty calibration. Potential remedies for this issue are discussed below.Based on these findings, we suggest that model-based stopping be used with more conservative priors that, e.g., favor smaller lengthscales and larger variances. Alternatively, calibration issues may be alleviated by marginalizing over hyperparameters [41] or utilizing more expressive models. These options help reduce the risk of overly confident models leading to premature stopping. Along the same lines, we recommend using a large fixed budget as an auxiliary stopping rule to avoid cases where poor model fits cause the algorithm to converge very slowly (see Appendix A.3 for discussion). 
conclusion: 
 To the best of our knowledge, results presented here are among the first of their kind for Bayesian optimization. We have given a practical algorithm for verifying whether a set of stopping conditions holds with high probability under the model. For the proposed stopping rule, we have further shown that the algorithm correctly terminates under mild technical conditions. If data is generated according to the model, we can therefore guarantee that BO is likely to return a satisfactory solution.The methods we have shared are largely generic. Echoing the introduction, if you can simulate it then you can use it for stopping. While this approach is not without limitations, we believe that it will ultimately allow others to design stopping rules as they see fit. To the extent that it does, model-based stopping may one day become as common place as model-based optimization. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Details are provided in the text or in supplementary material.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: Extended results are reported in Appendix D.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• 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). 
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: The proposed methods do not lend themselves to this type of misuse.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: The content of this paper was either created by the authors for use herein. Borrowed material has been cited.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: [NA]Justification: No assets have been released at this time.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. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: Not relevant.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: Not relevant.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• 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: This section aims to fill in some of the gaps left by Section 3 by providing further details for various subproblems and design choices encountered in practice.As discussed in the text, given a random variable Z ∈ R, there are different ways of generating intervals I n ⊆ R that contain the true parameter E[Z] with (nominal) coverage probability 1 -δ est .For Bernoulli random variables, Clopper-Pearson intervals (6) are a classic approach to this problem. This method is said to be "exact" because (instead of relying on the central limit theorem) it uses the fact that X = n i=1 Z i follows a Binomial distribution, where Z i is the i-th independent copy of Z. This method is also conservative: its (true) coverage probability is greater than or equal to 1 -δ est .Alternatively, one can take a Bayesian approach by placing a prior on success rate p ∈ [0, 1] of the Binomial random variable X ∼ Bin(n, p). If this prior is chosen to be a Beta distribution p ∼ Beta(α, β), then the posterior is conjugate and we have p | X ∼ Beta(α + X, β + n -X). Sensible choices include Jeffreys prior Beta( 1 /2, 1 /2) and the uniform prior Beta(1, 1).The equal-tailed, Bayesian credible interval is obtained by taking the δest /2 and 1 -δest /2 quantiles of p | X. Unlike those of Clopper-Pearson, these intervals are not inherently conservative. Indeed, Clopper-Pearson intervals contain Jeffreys intervals [9] . This property is sometimes desirable, since it may mean that fewer samples are required to make a decision. In Bayesian optimization, however, one typically assumes that evaluating f is far more expensive than simulating it. We therefore opted to use the more conservative choice.Lastly, it should be said that bounds on estimation errors can also be obtained when Z is not Bernoulli. For example, previous works [4, 33, 6] proposed to use an empirical Bernstein bound to generate confidence intervals for random variables Z ∈ [a, b], defined here asEQUATIONwhereZ n = 1 n n i=1 z i and S 2 n = 1 n n i=1 Z n -z i 2denote the empirical mean and variance.While conservative, the resulting intervals Z n ± ∆ n decay much faster than, e.g., their Hoeffdinginequality-based counterparts when S n is much smaller than b -a.Figure 4 illustrates how each of the methods discussed above perform in the context of Algorithm 2.Per Algorithm 1, Algorithm 2 may be evaluated in parallel on a set of candidates C ⊆ X . This confers certain advantages, such as the ability to share draws of f t and, hence, f * t between points x ∈ C. However, we must divide risk tolerance δ t est by cardinality |C| to retain the union bound. Hence, Algorithm 2 may be slow when C is large. We should therefore chose C with care.If solutions must belong to the set of previously evaluate points, X t , then we suggest to defineEQUATIONsince the excluded points can safely be ignored. Empirically, we found that this heuristic usually eliminates all but a few points.If solutions may be chosen freely on X , we instead recommend that C be constructed using one of the alternative estimators from Section 3.1 (all of which are differentiable). In particular, we recommend using gradient-based methods to maximize the average ofEQUATIONover multiple draws of f * t and x * t ∈ arg max x∈X f t (x), where µ t+1 and k t+1 are the posterior mean and variance of f t given an additional observation f (x * t ) = f * t and Φ denotes the standard normal cumulative distribution function. The resulting set of points can then be tested using Algorithm 2.Where possible, we recommend using a (conservatively chosen) budget T ∈ N for BO. This mean we suggest using PRB together with a fixed budget. Doing so not only ensures that the algorithm stops in a reasonable amount of time, but allows one to use a constant schedule δ t est = δest T -T0 , where T 0 ∈ N denotes the starting time. Note that this is how experiments from Section 5 were run.If no such budget is available, then we recommend adopting a strategy similar to Algorithm 2 by only evaluating the stopping rule at certain steps t. For example, one may employ a geometric sequence of potential stopping times (t i ), analogous to sample sizes (n j ), and defineEQUATIONlike d j t from Section 3.2. This practice ensures that δ t est does not decay too quickly.The main results of this section are as follows.i. Proposition 4 shows that a family of acquisition functions produce dense sequences (x t ). ii. Lemma 6 proves that variances vanish as X t becomes increasingly dense in X . iii. Lemma 9 bounds the expected supremum of f ∼ GP(0, k) in terms of its maximum variance. iv. Proposition 1 and Corollary 10 show that the PRB stopping criterion almost surely converges. v. Proposition 2 proves that BO with the PRB rule terminates and returns an (ϵ, δ)-optimal solution.Many of the findings presented here and discussed previously borrow heavily from earlier works. Where appropriate, we attribute credit at the beginning of each proof. Definition 3. Kernel k : X × X → R has the no-empty-ball property [47] if, for any sequence (x t ), the posterior variance Var[f (x) | f (X t )] at a point x ∈ X goes to zero as t → ∞ if and only if x is an adherent point of {x t : t ≥ 0}. Proposition 4. Let f ∼ GP(0, k) be a prior over functions on a compact space X ∈ R D and V t : X → R be a continuous acquisition function for f t . If k is a continuous kernel that admits the no-empty-ball property andEQUATIONthen the sequence(x t ) of points x t ∈ arg max x∈X V t (x) is dense in X .Proof. Follows immediately from [47] . Without loss of generality, suppose V t (x) is non-negative and equals zero if and only if k t (x, x) = 0. Let (x at ) and (x bt ) be subsequence of (x t ) that converge to an accumulation point z ∈ X and write α t = max{a i : a i ≤ t} and β t = max{b i : b i ≤ t}. Then,EQUATIONSince (x at ) and (x bt ) both converge to z and k is assumed continuous, (16) goes to zero as t → ∞.Consequently, V at (x at ) and, therefore, V t (x t ) must also vanish as t → ∞ [47, Proposition 12] . By definition of x t , it follows that lim t→∞ max x∈X k t (x, x) = 0. The no-empty-ball property now gives the result.Proposition 5. Let X ⊆ R D be convex and suppose that X ⊆ X generates an ε-cover of X . For every x ∈ X and ρ ≥ ε, the intersection of the set X and the ball B(x, ρ) = {x ′ ∈ X : ∥x -x ′ ∥ ∞ ≤ ρ} generates a 2ε-cover of B(x, ρ).Proof. Consider the ball B(x, r) with radius r = ρ -ε. Since X is convex, for every point a ∈ B(x, ρ) there exists a b ∈ B(x, r) such that ∥a -b∥ ∞ ≤ ε. Moreover, because X generates an ε-cover of X , for every point b ∈ B(x, r) there exists a c ∈ X so that ∥b -c∥ ∞ ≤ ε, which implies that c ∈ B(x, ρ). It follows by the triangle inequality that for every point a ∈ B(x, ρ) there exists a pair of points b, cEQUATIONwhich completes the proof.Lemma 6. Under assumptions A1 and A2, ifEQUATIONwhereκ ε (x) = 4L k ρ(ε)k(x, x) -L 2 k ρ(ε) 2 η(ε) + γ 2 k(x, x) [k(x, x) + 2L k ρ(ε)]η(ε) + γ 2is given in terms of η(ε) = max{1, ρ(ε) /4ε} D and ρ(ε) = ε ε for any 0 < ε < 1.Proof. This result extends Lederer et al. [26, Theorem 3.1] , who showed that, for all 0 ≤ ρ ≤ k(x,x) /L k ,EQUATION)where |B ρ (x)| is the cardinality of the set B ρ (x) = B(x, ρ) ∩ X. We would like to convert this upper bound into a function of 0 ≤ ε ≤ 1. To this end, begin by noticing that the bound (19) increases monotonically on 0 ≤ ρ ≤ k(x,x) /L k and decreases monotonically on n = |B ρ (x)| ∈ N 0 . Substituting ρ(ε) for ρ and η(ε) for n therefore yields a valid bound so long as ρ ≤ ρ(ε) ≤ k(x,x) /L k and 0 ≤ η(ε) ≤ n. For clarity, note that ρ(ε) defines the radius of a ball around x and η(ε) denotes the minimum possible number of elements from X that lie within this ball.Starting with the latter, lower bounds on the cardinality of B ρ (x) may be obtained from the fact that X is assumed to generate an ε-cover of X . By Proposition 5, it follows that B ρ (x) generates a 2ε-cover of B(x, ρ). Accordingly, |B ρ (x)| must be greater-equal to the minimum number of points required to construct such a cover. Under the ∥•∥ ∞ norm, the ε-covering number of a ballEQUATIONis given byEQUATION)This number is minimized when B(•, ρ) is placed in a corner, such as B(0, ρ) = [0, ρ] D . ChoosingEQUATIONtherefore ensures that η(ε) lower bounds the cardinality of every B ρ (•). Note that there are two factors of two at play here: one accounts for the fact that B ρ (•) is only guaranteed to provide a 2ε-cover of B(•, ρ), and the other accounts for the fact that the corner balls are up to 2 D times smaller than other balls with the same radius.Turning our attention to the choice of function ρ(ε), some desiderata come into focus. First, we require ρ(ε) ≥ ε so that every B ρ (•) is nonempty. Second, we desire lim ε→0 + ρ(ε) = 0 because the resulting posterior variance bound will increase monotonically in ρ(ε). Lastly, we want the ratio of ρ(ε) to ε to diverge to infinity as ε approaches zero from above so that lim ε→0 + η(ε) = ∞. Based on these criteria, a convenient choice whenEQUATIONIn summary, the claim follows by expressing ρ as a function of ε and using it to lower bound |B ρ (•)| with η(ε):EQUATION)Proposition 7. For any choice of constants a > 0, b ≥ 0, c ≥ 0,EQUATION)Proof. This proof ammends Grünewälder et al. [18, Appendix A] .EQUATIONNext, define auxiliary functionsf (u) = log u -1 /a g(ε) = ε ξb a (27)such that f (g(ε)) = log ξ 1 /a bε -1 /a and use them to integrate by substitution asEQUATION)The Cauchy-Schwarz inequality now givesg(c) 0 -log(u)du ≤ g(c) 0 du 1 /2 - g(c) 0 log(u)du 1 /2 = c ξb a 1 -log c ξb a . (29)Hence, the claim followsEQUATION)Remark 8. For comparison with Grünewälder et al. [18] , if b a = 2c then Proposition 7 givesEQUATIONwhich matches their reported result. Lemma 9. Let f ∼ GP(0, k) be a Gaussian process with anEQUATION)Proof. This proof paraphrases parts of Grünewälder et al. [18, Section 4.3] .Massart [30, Theorem 3.18] proved that the expected supremum of f is upper bounded byEQUATIONwhere N (X , d k , ε) is defined as the ε-packing number-i.e. the largest number of points that can be "packed" inside of X without any two points being within ε of one another-under the canonical pseudo-metric3 EQUATION)We may use (33) by upper bounding the right-hand side with a known quantity. We will bound the ϵ-packing number N (X , d k , ε), translate this bound from the d k pseudo-metric to the infinity norm, and then integrate the result.The first step follows immediately from the fact that the ε-packing number is smaller than the ε 2covering number-defined as the minimum number of balls B(•, ε2 ) required to cover X . The second is accomplished by using Lipschitz continuity of k to show that the squared pseudo-metricEQUATION)It follows that, for any set X ⊆ X ,EQUATION)An ε 2 /8L k -cover under the infinity norm therefore guarantees an ε /2-cover under d k . The former may be constructed from a grid of uniformly spaced points with elements at intervals of ε 2 /4L k . This grid will consist of 4L k rε -2 D points assuming X = [0, r] D , meaning thatEQUATION)To complete the proof, use Proposition 7 with a = 1 2 , b = 4L k r, and c = σ to show thatEQUATION)Proposition 1. Under assumptions A1-A3 and for all regret bounds ϵ > 0 and risk tolerances δ > 0, there almost surely exists T ∈ N 0 so that, at each time t ≥ T , everyEQUATION)Proof. Consider the centered processEQUATIONEQUATIONEQUATIONand, therefore,EQUATIONWe would now like to use the Borell-TIS inequality [8, 46] to show that: if ϵ > E(g * t ), thenEQUATIONwhere σ t = max x∈X k t (x, x) and 2σ t appears in the denominator (rather than σ t ) because max x∈X c t (x, x) ≤ 4σ 2 t . Since ( 43) is an increasing, continuous function of both σ t ≥ 0 and 0 ≤ E(g * t ) < ϵ, the claim will hold if these quantities vanish as the (global) fill distance h t = max x∈X min 1≤i≤t ∥x -x i ∥ ∞ goes to zero.The former result is an immediate consequence of Lemma 6. Regarding the latter, f t (s t ) -µ t (s t ) is a centered random variable. It follows by linearity of expectation thatEQUATIONNext, denote the canonical pseudo-metric at time t byEQUATION)This pseudo-metric is non-increasing in t. To see this, let β = k(x t+1 , x) -k(x t+1 , x ′ ) and writeEQUATION)As t increases, points therefore become closer together under the d kt pseudo-metric. For this reason, the posterior ε-packing number N (X , d kt , ε) is less-equal to the prior ε-packing number N (X , d k , ε). By Lemma 9, we now haveEQUATION)From here, note that ( 47) is an increasing, continuous function of σ t that vanishes as σ t → ∞. By Lemma 6, the same is true of σ t as a function of h t . As a result, (43) becomes arbitrarily small as h t → 0 and there exists a constant h * > 0 such that this upper bound is less-equal to δ whenever h t ≤ h * . Finally, since (x t ) is almost surely dense in X , there almost surely exists a timeEQUATION)Corollary 10. Suppose assumptions A1-A3 hold and that there exists a constant ϵ ′ > 0 so thatEQUATION)with probability one, where s t ∈ arg max x∈Xt µ t (x). Then, for every ϵ > ϵ ′ and δ ∈ (0, 1], there almost surely exists a time T ∈ N such that, for all t ≥ T ,EQUATION)Proof. Per ( 49), there almost surely exists an S ∈ N such that t ≥ S =⇒ max x∈X µ t (x)µ t (s t ) ≤ ϵ ′ . Proposition 1 therefore implies there almost surely exists a T ≥ S so thatEQUATIONwhich completes the proof.The assumption that the posterior mean approaches its maximum on (x t ) protects against adversarial cases where-no matter how densely we observe f -there is always an x ∈ X \ X t so that µ t (x) exceeds µ t (s t ) by at least ϵ. Note that (49) becomes a necessary condition when δ < 1 2 . Nevertheless, it is unclear how to ensure this condition without making stronger assumptions for f and (x t ). One can use A2 and the Cauchy-Schwarz inequality to show that the posterior mean is Lipschitz continuous [27] ; but, its Lipschitz constant may continue to grow as t → ∞, so (49) may not hold.Experiments were run using a combination of GPFlow [31] and Trieste [36] . Runtimes reported in Figure 3 were measured on an Apple M1 Pro Chip using an off-the-shelf build of TensorFlow [1] .We employed Gaussian process priors f ∼ GP(µ, k) with constant mean functions µ(•) = c and Matérn-5 /2 covariance functions equipped with ARD lengthscales.True When optimizing functions drawn from GP priors, we set the prior mean to zero and used unit variance kernels with lengthscalesℓ i = 1 4 √ D.Noise variances are reported alongside results.MAP When optimizing black-box functions, we employed broad and uninformative hyperpriors. Let [X ] i = [a i , b i ] be the range of the i-th design variable, q t : [0, 1] → R be the empirical quantile function of y at time t, and ν t = Var y t-1 be the empirical variance of observations y t-1 = {y(x 1 ), . . . , y(x t-1 )}. Our hyperpriors are then as follows:Name Distribution Parameters Constant Mean Uniform(a, b) a = q t (0.05) b = q t (0.95) Log Kernel Variance Uniform(a, b) a = log(10 -1 ν t ) b = log(10ν t ) Log Noise Variance Uniform(a, b) a = log(10 -9 ν t ) b = log(10ν t ) i-th Lengthscale LogNormal(µ, σ) µ = 1 2 (b i -a i ) σ = 1Note that we directly parameterize certain hyperparamters in log-space and that, e.g., log(θ) ∼ Uniform(a, b) is not the same as θ ∼ LogUniform(e a , e b ). 1 , but where ϵ is used as the cutoff value for ∆CB and ∆ES.Problem D T Oracle † Budget † Acq ∆CB ∆ES PRB GP † 10 -This section provides an in-depth breakdown of experiments presented in the body. Results for each problem are presented in the order they appeared in Table 1 .In each of the following table, we report statistics for each of the following metrics:1. Succeeded: whether or not an ϵ-optimal point was returned. 2. Terminated: whether or not the stopping rule kicked in prior to reaching upper limit T .3. Stopping Time: the number of function evaluations requested. 4. Regret: latent values sup x∈X f (x) -f (s t ) where s t ∈ arg max x∈Xt µ t (x) is a maximizer of the posterior mean at the time of stopping; reported in log 10 scale. 5. Excess Regret: latent values sup x∈X f (x) -f (s t ) + ϵ for runs where regrets exceeded ϵ; reported in log 10 scale.For the final three metrics, medians and interquartile ranges are shown alongside the mean. Similar to the preceding section, results for ∆CB and ∆ES are reported using ϵ as the cutoff values to give a better picture of how these methods perform in the absence of post-hoc calibration. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).We may that assume P(λ = E[Z]) = 0. Here, E[Z] = Ψt(x) is only random prior to observing y(Xt).Note that these descriptions do not account for the presence of a link function (see Appendix C.2).While d k has most of the properties of a proper metric, d k (x, x ′ ) = 0 need not always imply x = x ′ [2]. 


Decision: The paper introduces a novel stopping criterion for Bayesian optimization based on probabilistic regret bounds. The core novelty is a model-based stopping rule that leverages Monte Carlo estimators to decide when to terminate the optimization process, ensuring that the solution meets a predefined regret threshold with high confidence. The theoretical justification is strong, and the empirical results demonstrate the method's potential across a variety of benchmark problems.

Despite the strengths, there are concerns regarding the practical applicability of the method, particularly when modeling assumptions do not hold perfectly. Reviewer cuEF specifically raised concerns about the method's utility in real-world settings, where the alignment between the objective function and the model might not always be guaranteed. These concerns are valid and should be addressed in future revisions to ensure the method's broader applicability.

One point of note is that the idea of using a model to determine when to stop has some precedence in BO literature (e.g., https://arxiv.org/abs/1806.07555), which also deals with using models to estimate stopping conditions while acknowledging model mismatch. This similarity is worth mentioning as it shows that the concept of model-based stopping has been explored in different contexts.

During the discussion phase, reviewers acknowledged the technical contribution of the paper, though some practical concerns remain. Given these factors, the paper is leaning towards acceptance, provided there is room for further refinement, particularly in clarifying its practical significance and addressing concerns around real-world deployment.

Reviews: review: paper_summary: paper_summary: This paper proposes estimators for Bayesian optimisation stopping rules backed by theoretical guarantees. The stopping criterion estimators are probably approximately correct (PAC) and derived from sample-based estimates of algorithm’s simple regret according to a Gaussian process model. Experiments complement the theoretical findings on benchmark problems involving synthetic-data benchmarks and hyper-parameter tuning problems.
strength_weakness: strength_weakness: * Some important details of the methodology are not clear, as the description tends to be quite verbose with a lack of technical details. It is not very clear how Algorithm 1 applied within the BO loop, for example.
* Scalability limitations are not discussed.
questions: questions: * In Algorithm 1, what exactly is $Z$, given the dependence of $\Psi$ on $\mathbf{x}$?
* It’s not clear how gradients are applied to evaluate the regret-bound indicators, as suggested in line 110. The sampled functions are likely to be non-convex. So, even if running gradient descent from the given $\mathbf{x}$ does not lead to a point $\mathbf{x’}$ satisfying $f_t(\mathbf{x’}) - f_t(\mathbf{x}) > \epsilon$, there’s no guarantee that elsewhere on the search space this would not be achieved.
* What was the runtime for the algorithms in the experiments reported in Table 1? Since the PRB strategy requires multiple samples from the GP at each iteration, it seems to me that the cost of running the algorithm ramps up quite fast. So it’d be good to compare the PRB runtimes against the baselines’ to have an idea of how much more computational resources are required by attempting an early stopping strategy.
* What was the feature map $\boldsymbol{\phi}$ used for the experiments?
* What is $D$ in the definition of $\beta_t$ in line 270?
* Hartmann, Rosenbrock and Branin are classic synthetic test functions for optimisation algorithms. So why are they included under a section labeled “Results on real problems”? That can be somewhat misleading, as we’d usually refer to “real problems” as cases involving real data or challenging application scenarios attached to a real-world application (e.g., complex physics simulators for scientific problems).
* Scalability limitations are not discussed. For instance, the proposed PRB estimator is based on optimisation over samples from a GP, and finding their optima should become harder and harder as the dimensionality of the space grows. Are there useful approximations that could be applied without hurting the theoretical guarantees by too much? Also, the algorithm could be adapted to work with sparse GP models, especially sparse spectrum GPs, given the feature-based approximations for sampling in Eq. 4. However, I’ve missed a discussion on how to adapt the algorithm to scenarios involving large amounts of data (e.g., batch BO).
limitations: limitations: Some limitations are discussed in the main text, while other issues, such as scalability, might not have been addressed, as mentioned above.
paper_summary: paper_summary: This paper addresses the challenge of determining when to stop a Bayesian optimization process. Traditional methods rely on exhausting a predefined budget, but this work proposes an alternative approach based on probabilistic criteria as a stopping criterion.
Key Contributions:
New Stopping Criterion: The paper introduces a stopping criterion based on the probability that a solution is within a certain threshold ($\epsilon$) of the optimal solution with high confidence (1 - $\delta$). This criterion is more adaptive and user-friendly compared to traditional budget-based stopping rules.
Theoretical Guarantees: The authors prove that Bayesian optimization satisfies this new stopping criterion under mild technical assumptions for Gaussian process priors.
Practical Algorithm: This paper presents a practical algorithm for evaluating the stopping rules using Monte Carlo estimators. This algorithm is designed to be robust against estimation errors.
The paper provides empirical results demonstrating the effectiveness and limitations of the proposed approach.
strength_weakness: strength_weakness: N/A
questions: questions: Assumption 3 (A3), which requires the sequence of query locations $(\vec{x}_t)$ to be almost surely dense in the search space $\mathcal{X}$. Is this assumption practical in the high-dimensional data ?
limitations: limitations: N/A
paper_summary: paper_summary: This paper develops a $(\varepsilon,\delta)$ stopping criterion for Bayesian optimization algorithms.  The authors propose a probabilistic regret bound estimator, which is constructed through sampling the function and find the maximum points of these samples,  to decide when to stop the algorithm. They also give the theoretical analysis of this estimator and show their results in the numerical experiments.
strength_weakness: strength_weakness: My concern is about the Assumption A.3, which is not a common assumption in BO field. This assumption, as you mentioned, is true for a generalized EI in [1]. However, it is still unknown if this assumption is held in a noisy case, and I am also not agree with that the Knowledge gradient is in the form of generalized EI defined in [1]. I think the UCB algorithm with a fix coefficient will never satisfiy this assumption. As a result, the theoretical analysis is restricitive and only suitable for several specific acquisition functions.




[1] Convergence properties of the expected improvement algorithm with fixed mean and covariance functions.
questions: questions: * I didn't understand the right figure in Fig 2. Do you mean that you change the posterior distribution for orange, green and red line through conditioning on the partial information of real optima?

* How to decide the oracle budget in the experiment section? As the budget is chosen by an oracle, why sometimes the budget may be worse than other methods?
limitations: limitations: They adequately addressed the limitations.
paper_summary: paper_summary: The paper introduces a Monte-Carlo-based stopping criterion for Bayesian optimization tasks, which has been neglected in the Bayesian optimization literatures. The authors provide a generic algorithm that can be tailored to Bayesian optimization setting and establish theoretical results and demonstrate numerical performances.
strength_weakness: strength_weakness: The paper's writing can be improved significantly. Although the paper introduces the most generic version of the algorithm as in Algorithm 1, to be actually used in the BO setting, one needs to calibrate parameters $(\delta^t_{est})_{t\in \mathbb{N}}$ that are highly nontrivial. Instead of presenting algorithm 1, readers would benefit more by seeing the algorithm directly targeted to the Bayesian optimization setting. Or perhaps it would be better if authors title the paper more broadly and consider applications beyond the Bayesian optimization. Section 3.2, in particular, needs to be modified to clarify its connection to the Bayesian optimization setting. A proper description of parameter scheduling and end-to-end algorithmic description would make the paper more solid and appreciated by a wider audience.
questions: questions: 1. The regret defined in (2) is not a simple regret, and it does not accurately measure the performance of the optimization as the objective function $f$ is not used, but instead a sequence of objective functions $(f_t)_{t \in \mathbb{N}}$, which vary over time, is considered. Can you clarify what the regret means in this case? It seems it makes more sense to stop the BO algorithm when $f(x^*) - f(x_t) \le \epsilon$ with probability at least $1-\delta$. In the later parts of the manuscript, $f_t$ seems to be a sample path, and if this is the case, algorithms like GP-TS would easily satisfy the condition, which authors refer to as probabilistic regret bound, in the early stage of the algorithm. Such a condition would be virtually non-informative. 

2. In line 110, the authors claim that for each draw of $f_t$, the indicator can be evaluated using gradients. Can you elaborate more on this?
limitations: limitations: Not applicable.

Comments: title: Re^4
Re^3: model misspecification
Re: Re: on model misspecification
Re: on model misspecification
On model misspecification
Regarding model mismatch
Response to the authors
Reply to follow-up questions
Discussion period
comment: Thank you for your input! Please humor a quick reply.

In the noise-free setting, we believe to have shown (either in the text or in follow-up discussion here) that PRB converges for most acquisition functions (AFs). The only well-know exception we are aware of is UCB with a fixed $\beta$ parameter. At the risk of being overly pedantic: this is technically a bandit method and therefore falls outside the scope our work. 

Regarding inconsistencies, assumptions A1-A3 could be communicated earlier in the text. We have not done so because they are only required for our technical analysis. Our algorithm can be used with any search strategy, but convergence can only be guaranteed if additional assumptions are made. This is unavoidable for stopping rules like PRB, since we need to protect against degenerate cases where, e.g., only a single point is ever queried.

Finally, we agree with your comment that we should show results for more than one AF. This is a good suggestion. We actually did run some experiments early on with different AFs for standard problem like Branin; and, these were consistent with results reporting in the text. We did/do not have the compute resources to run all of our experiments with multiple AFs, but are happy to add experiments that illustrate how our method interacts with different strategies.

We ask you to reconsider not to revising your score, but respect your decision either way.
Since technical misunderstandings on the regret have been resolved, I changed the score. 

However, I think the current work is still yet to be considered for publication unless there is more concrete guidance on bridging model-based regret with the actual discrepancy.
Like what you've said, we view our work as more of a step in the right direction than a final solution. It is vital that readers understand both the strength and weaknesses of methods such as ours in order to make informed decisions. Thank you for stressing this point. We will provide extended discussion of this topic regardless of whether or not you choose to adjust your score.
Thanks for the comment as well. 

I think this paper has many interesting technical works that could be potentially useful in developing stopping rules for Bayesian optimization. However, to make my stance clearer, what I find more appropriate is to make sure the stopping criterion reflects how close the output of the algorithm is to the optimum of the objective function. As the authors clarified in the response, the stopping criterion would be appropriate without model misspecification, however, since a substantial number of BO applications fall into the misspecified model setting, if one develops a model-based stopping criterion, one must also provide a diagnostics/heuristics to guide practitioners to safely use tools. Currently, I find descriptions in Section 5.3 are insufficient. If the authors are willing to provide more down-to-earth guidance on the choice of a number of iterations to make sure the posterior Gaussian process can provide a reasonable stopping criterion for the deterministic black-box optimization in the manuscript, I am willing to raise the score a bit.
Thank you for your continued input!

> your stopping rule only makes sense, when the objective function is a realization of the posterior Gaussian process, however, many numerical examples you provide, e.g., Branin, Hartman, Rosenbrock fall into the RKHS assumption setting. In theory, these functions are too smooth to be considered to be a sample path of the posterior Gaussian process. In practice, unless, you run the algorithm long enough, your draws of the posterior Gaussian process cannot even approximate these objective functions.

Our method only requires that uncertainty for the true function becomes sufficiently small. If the true function is smoother than the GP sample paths, then our method may be conservative. Our analysis still shows that the proposed stopping rule will converge however (under appropriate assumptions). Further, our applied results suggest that it does so efficiently.

> your stopping rule is based on the posterior Gaussian process, and these posteriors can be significantly different from the objective functions with a few data points, as mentioned before. Then the stopping criterion with such a misspecified posterior GP is completely meaningless. How can you make sure that the objective function is at least somewhat close to some sample path of the posterior GP? Unless there is guidance on this, I am not convinced how to utilize this stopping criterion. 

To our knowledge, there is no way of avoiding this. If we compare with the frequentist/bandit setting where one assumes that $f$ has bounded RKHS norm $B$, then the same issue emerges if we underestimate $B$. There is simply no free lunch.
Thanks for the prompt response and for addressing my latest concerns. I'd expect the authors to revise the text considering these and the issues raised by other reviewers. In its current form, there are quite a few (mainly) clarity related issues, but I believe the paper still brings a valuable contribution to the BO community and that its main issues have been addressed in the discussion. Therefore, I'm happy to raise my score.
Based on my understanding of your previous response, the main concern I have is the utility of the algorithm which relies on unrealistically strong assumptions. To be clearer, 1) your stopping rule only makes sense, when the objective function is a realization of the posterior Gaussian process, however, many numerical examples you provide, e.g., Branin, Hartman, Rosenbrock fall into the RKHS assumption setting. In theory, these functions are too smooth to be considered to be a sample path of the posterior Gaussian process. In practice, unless, you run the algorithm long enough, your draws of the posterior Gaussian process cannot even approximate these objective functions. In addition, 2) your stopping rule is based on the posterior Gaussian process, and these posteriors can be significantly different from the objective functions with a few data points, as mentioned before. Then the stopping criterion with such a misspecified posterior GP is completely meaningless. How can you make sure that the objective function is at least somewhat close to some sample path of the posterior GP? Unless there is guidance on this, I am not convinced how to utilize this stopping criterion. In a nutshell, although I am not opposed to developing a model-based stopping rule, it must reflect practical Bayesian optimization applications and the current methodology doesn't seem to do so.
We are surprised to see that your review has pivoted to focusing on model misspecification and request you discuss this matter with your fellow reviewers. Our (potentially biased) view is that we have been very upfront about this issue. Here is some evidence to support this claim:
- We state in the abstract that our goal is to find an $\epsilon$-optimal point with probability at least $1 - \delta$ _under the model_.

- We reinforce this point in the introduction by discussing how model misspecification is one of two key issues that has likely impeded the development of model-based stopping rules; and, we explicitly tell the reader on line 31 that our work only provides "mild commentary" on this topic.
- We qualify statments by saying "under the model" or "according to the model" more than 10 times in the main text.
- We refer to (2) as the "model-based regret" on line 81.
- The explanation of our main convergence result, Proposition 2, says: "If the model is correct, we can therefore promise to return a satisfactory solution with high probability."

- Model mismatch is the focus of Section 5.3.

- In our conclusion, we say: "If data is generated according to the model, we can therefore guarantee that BO is likely to return a satisfactory solution."

To be clear, our intention is not to say that your dissatisfaction is unwarranted. We fully agree that model misspecification is a major issue. At the same time, we argue that we (as a community) can only make progress on model-based stopping if we do so incrementally. To our knowledge, our contributions are more than incremental:
- We are the first to provide actual performance guarantees (even if they are defined under a model).
- Our convergence results are much more general than any preceding work.
- We demonstrate significantly superior empirical performance.

If you disagree, then please explain why or point to related works that have done a better job.
Thank you for providing a detailed response to my question. I appreciate the clarification regarding the practicality of Assumption 3 (A3) for high-dimensional problems. Your explanation about the role of smoothness of the function $f$ relative to the size of  $\mathcal{X}$ is insightful. The discussion on the choice of norm and its equivalence in finite-dimensional spaces, as well as the importance of the kernel-induced distance, is particularly helpful.
The usage does not really convince me of the model-based regret. Although Bayesian optimization algorithms endow probabilistic structure to the objective function, it often just serves as an intermediate assumption to derive an algorithm. The algorithm itself has a strong performance guarantee under model misspecification (e.g., objective function in the RKHS). If one must use such model-based regret, this paper needs to emphasize the importance of correct model specification and explicitly state the limitation in the misspecified model setup. In practice, there are a substantial number of successful BO examples with model misspecifications. I don't find then the framework provided in this paper attractive or practical. Therefore, I will retain my score.
Thanks again for your input. In future versions, the main text will clearly discussed the following details.


**How is $Z$ define?**

There is one $Z$ for each point at which we evaluated the proposed stopping rule. We evaluated this rule on all previously queried points $\mathbf{x} \in \mathbf{X}_t$ that satisfied a pruning condition
$P(f_t(\mathbf{s}_t) - f_t(\mathbf{x}) \ge \epsilon) \le \delta_m$, which checks if $\mathbf{x}$ would satisfy our stopping rule if $\mathbf{s}_t$ was assumed to uniquely maximize $f_t$. If this condition does not hold, then $\mathbf{x}$ cannot satisfy the rule. We also divided $\delta_e^t$ by the number of test points at step $t$ to retain the union bound (line 168). This information is given in Appendix B (as vaguely hinted by line 171), but we should have done a better job here.


**Figure 3**

Only the left subplot uses toy Bernoulli random variables. The middle and right columns show  actual empirical CDFs and runtimes for the PRB rule from our experiments, i.e. $Z$ was sampled by running multi-start gradient ascent on draws of $f_t$. This is why, for example, costs can be seen to increase with dimensionality. Since our initial submission, we have found that these runtimes can be further accelerated by using different concentration inequalities.
Thanks for the response and the clarifications. Here are a few follow-up questions, as I'm still confused about some details.

> 1. The random variable $Z$ is introduced on line 128 and its definition in the specific context of PRB is given on line (134).

Yes, but $Z$'s definition in line 134 is still dependent on some $\mathbf{x} \in \mathcal{X}$, which is not clear. Would the $\mathbf{x}$ at which $Z$ is evaluated correspond to $\mathbf{s}_t$ in Proposition 1?

> 3. Runtimes are shown on the right in Figure 3.

As far as I understand from reading the caption in Figure 3, those runtimes are calculated from sampling Bernoulli random variables mimicking the $Z$'s which would be calculated for PRB estimates. However, within a BO loop, those $Z$'s would require samples from a GP (followed by multi-start gradient descent) to be evaluated, which apparently is not the case in Figure 3. So, to me, it seems that those runtime estimates are not indicative of the actual runtime of estimating PRB within a BO loop.
I'd like to thank the authors for their response and for clarifying several issues.

I think the analysis process you provided is correct, but it still cannot reduce my doubts about the theoretical part. There are no assumptions about Aq in the algorithm description, but there are many limitations in the theoretical section, which makes the algorithm and theory in the article inconsistent. This paper still has potential for improvements such as providing some experiments about the stopping criterion on different Aq, so I will not change the score.
Dear reviewers,

Thank you all for your contributions during the review period. Please take a look at the authors' responses and I look forward to a fruitful discussion on this submission in the next few days!

Best regards, 
AC for Submission 18743