In automated machine learning, scientific discovery, and other applications of Bayesian optimization, deciding when to stop evaluating expensive black-box functions in a cost-aware manner is an important but underexplored practical consideration. A natural performance metric for this purpose is the cost-adjusted simple regret, which explicitly captures the trade-off between solution quality and cumulative evaluation cost. Existing stopping rules for Bayesian optimization are either heuristic, or are theoretically grounded but designed to optimize simple regret without accounting for evaluation costs; as a result, they provide no guarantees against unnecessary evaluations when costs are high. We propose a principled cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs without heuristic tuning. Our rule is grounded in a theoretical connection to state-of-the-art cost-aware acquisition functions, namely the Pandora's Box Gittins Index (PBGI) and log expected improvement per cost (LogEIPC). When paired with either acquisition function, we prove that the resulting policy satisfies a theoretical guarantee bounding the expected cost-adjusted simple regret. Across synthetic tasks and empirical benchmarks including hyperparameter optimization and neural architecture size search, pairing our stopping rule with PBGI or LogEIPC usually matches or outperforms other acquisition-function--stopping-rule pairs in terms of cost-adjusted simple regret.
Figures & tables
Figure 1: Illustration of the PBGI/LogEIPC stopping rule under a uniform-cost setting. When the cost-per-sample is large ( c(x)≡0.1 ), the minimum PBGI acquisition value exceeds the threshold (current best observed value) and the maximum LogEIPC acquisition value falls below the threshold 0.0 , indicating stopping; when the cost-per-sample is small ( c(x)≡0.0001 ), the minimum PBGI acquisition value is smaller than the threshold (current best observed value) and the maximum LogEIPC acquisition value remains above the threshold 0.0 , indicating no stopping.
Figure 2: Cost-adjusted simple regret across acquisition-stopping rule pairs in 1D and 8D Bayesian regret setting. In 1D, objective functions are sampled from a GP with a Matérn-5/2 kernel and a linear cost function scaled by λ=0.1,0.01,0.001 . The Immediate baseline is omitted at λ=0.001 due to its much higher regret (mean 0.6942, error bar [0.5314, 0.8570]). In 8D, objective functions are also drawn from a GP with a Matérn-5/2 kernel, using three cost functions scaled by λ=0.01 .
λ
Acq
Top 1
Top 2
Top 3
Large
All
Large
All
Large
All
10−3
PBGI
30.0%
25.7%
75.0%
51.4%
80.0%
60.0%
LogEIPC
40.0%
37.1%
80.0%
65.7%
80.0%
68.6%
10−4
PBGI
40.0%
28.6%
70.0%
51.4%
75.0%
60.0%
LogEIPC
60.0%
40.0%
75.0%
60.0%
85.0%
74.3%
10−5
PBGI
35.0%
20.0%
70.0%
48.6%
90.0%
74.3%
Table 1: Percentage of LCBench tasks on which our PBGI/LogEIPC stopping rule ranks in the Top- k ( k=1,2,3 ) by mean cost-adjusted simple regret among the seven non-trivial stopping rules paired with the same acquisition function. Immediate and Hindsight are excluded. Results are shown for PBGI and LogEIPC on the 20 large datasets with >10,000 instances and on all 35 datasets, for λ∈{10−3,10−4,10−5} .
Figure 3: Cost-adjusted simple regret across acquisition function–stopping rule pairs on LCBench and NATS-Bench. The objective is to minimize validation error on classification tasks, with scaled proxy runtime as evaluation cost, scaled by representative values of λ ( 10−3,10−4,10−5 for LCBench and 10−5 for NATS-Bench). For LCBench, results are normalized within each dataset and random seed, then aggregated across the 35 datasets. Both matched cost-aware combinations are competitive in aggregate, with their relative performance varying with λ . Per-dataset results and within-acquisition stopping-rule ranks are reported in Figures 19 , 20 , 21 and 1 .
Appendix figures & tables33 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Comparison of the raw and moving-averaged PBGI/LogEIPC stopping rule signals (i.e., the LogEIPC acquisition values) in Bayesian regret 8D experiments for multiple acquisition functions, with linear cost and stopping thresholds at log(0.1) , log(0.01) and log(0.001) . Left: The unaveraged signals exhibits large, high-frequency fluctuations due to the difficulty of acquisition optimization in high dimensions. Right: Applying moving average (window=20) smooths these wiggles, yielding more stable stopping signals.
Figure 5: Surface plots of cost functions over [0,1]2 : (Left) Uniform cost of 1 across domain. (Middle) Normalized linear cost increasing with the mean of x1 and x2 . (Right) Periodic cost with α=2 , β=2 , normalized by Bessel-based factor.
Figure 6: Empirical relationship between the number of model parameters and runtime for three LCBench datasets. Each subplot shows a scatter plot of actual runtime ( y -axis) against number of model parameters ( x -axis), along with a fitted linear regression line. The observed linear trend supports using 0.001 times the number of model parameters as a proxy for runtime. For Fashion-MNIST and adult , the fitted slopes are close to 0.001. The slope for higgs is slightly higher, possibly due to a few outliers.
Figure 7: Empirical relationship between the number of FLOPs and runtime for the three NATS-Bench datasets. Each subplot shows a heatmap of actual runtime ( y -axis) against number of FLOPs ( x -axis), along with a fitted linear regression line. The observed linear trend supports using α×#FLOPs+β as a proxy for runtime.
Figure 8: Evolution of per-iteration computation time (in log scale) for different stopping stopping rules when paired with six acquisition policies on the 8-dimensional Bayesian regret benchmark. Each subplot shows the average runtime (in seconds) over 50 iterations under one acquisition function—LCB, TS, LogEIPC, PBGI ( λ=10−1 ), PBGI ( λ=10−2 ), and PBGI ( λ=10−3 ). Curves correspond to four stopping criteria: our PBGI/LogEIPC stopping rule, SRGap-med, UCB–LCB, and PRB. Convergence and GSS can be applied using only the best observed value and thus require no additional computation time, thus they are omitted here. LogEIPC-med relies on the same underlying statistical computations as the LogEIPC rule, and therefore its runtime is not measured separately. The results should that PRB incurs significant computational overhead compared to other stopping rules.
Figure 9: Illustration of a single draw from a Matérn- 5/2 Gaussian process on [0,1] with lengthscale 0.1 , optimized using PBGI acquisition function under uniform cost and cost-scaling factor λ=0.01 . We compare two variants of PBGI stopping rules: the before-posterior-update (this-round) stopping rule and the after-posterior-update (next-round) stopping rule. Left: The latent objective function (solid gray) and evaluation sequences for before-posterior-update stopping (blue circles) and after-posterior-update stopping (orange crosses). The dotted blue line and the dashed orange line mark the best observed value under each respective rule. Right: Cost‐adjusted regret for each stopping rule. In this example, after-posterior-update stopping achieves strictly lower cost-adjusted regret despite performing more evaluations.
Figure 10: Comparison of simple regret of seven acquisition functions: PBGI ( λ=10−3 ), PBGI ( λ=10−4 ), PBGI ( λ=10−4 ), LogEIPC, LCB, TS, and PBGI-D on LCBench datasets, using scaled proxy runtime as evaluation cost. We can see that indeed the cost-aware PBGI and LogEIPC outperform the cost-unaware UCB and TS. PBGI-D with our recommended λ0=U/(B−C)=50/10000=0.005 is also competitive.
Dataset
Acq
Ours
LogEIPC- med
SRGap- med
UCB–LCB
GSS
Convergence
PRB
Fashion-MNIST
PBGI
0
0
0
50
0
0
0
LogEIPC
0
0
17
50
0
0
0
LCB
50
50
25
50
0
0
50
TS
30
7
0
50
0
0
6
adult
PBGI
5
0
7
44
0
0
6
LogEIPC
5
0
16
41
0
0
7
Appendix
Table 2: Number of trials (out of 50) that do not stop before iteration 200, for each acquisition–stopping rule pair. Online stopping is evaluated from iteration 20. LCBench uses λ=10−4 (first three datasets), and NATS-Bench uses λ=10−5 (last three). “Ours” denotes the PBGI/LogEIPC stopping rule.
Figure 11: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs on the Fashion-MNIST dataset. The objective function is the validation error, and the evaluation cost is the proxy runtime, scaled by λ=10−3,10−4,10−5 . Each stopping rule is evaluated on the trajectory of its paired acquisition function. The red marker shows hindsight-optimal adaptive stopping, while the minimum of the fixed-iteration curve gives the hindsight-optimal fixed iteration. These references distinguish the effects of acquisition, stopping, and cost scaling.
Figure 12: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs on the adult dataset. The objective function is the validation error, and the evaluation cost is the proxy runtime, scaled by λ=10−3,10−4,10−5 . Each stopping rule is evaluated on the trajectory of its paired acquisition function. The red marker shows hindsight-optimal adaptive stopping, while the minimum of the fixed-iteration curve gives the hindsight-optimal fixed iteration. These references distinguish the effects of acquisition, stopping, and cost scaling.
Figure 13: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs on the higgs dataset. The objective function is the validation error, and the evaluation cost is the proxy runtime, scaled by λ=10−3,10−4,10−5 . Each stopping rule is evaluated on the trajectory of its paired acquisition function. The red marker shows hindsight-optimal adaptive stopping, while the minimum of the fixed-iteration curve gives the hindsight-optimal fixed iteration. These references distinguish the effects of acquisition, stopping, and cost scaling.
Figure 14: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs on the cifar10-valid dataset. The objective function is the validation error, and the evaluation cost is the proxy runtime, scaled by λ=10−4,10−5,10−6 . Each stopping rule is evaluated on the trajectory of its paired acquisition function. The red marker shows hindsight-optimal adaptive stopping, while the minimum of the fixed-iteration curve gives the hindsight-optimal fixed iteration. These references distinguish the effects of acquisition, stopping, and cost scaling.
Figure 15: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs on the cifar100 dataset. The objective function is the validation error, and the evaluation cost is the proxy runtime, scaled by λ=10−4,10−5,10−6 . Each stopping rule is evaluated on the trajectory of its paired acquisition function. The red marker shows hindsight-optimal adaptive stopping, while the minimum of the fixed-iteration curve gives the hindsight-optimal fixed iteration. These references distinguish the effects of acquisition, stopping, and cost scaling. At λ=10−5 , GSS and Convergence have lower mean cost-adjusted regret than our rule when paired with either PBGI or LogEIPC.
Figure 16: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs on the ImageNet16-120 dataset. The objective function is the validation error, and the evaluation cost is the proxy runtime, scaled by λ=10−4,10−5,10−6 . Each stopping rule is evaluated on the trajectory of its paired acquisition function. The red marker shows hindsight-optimal adaptive stopping, while the minimum of the fixed-iteration curve gives the hindsight-optimal fixed iteration. These references distinguish the effects of acquisition, stopping, and cost scaling. At λ=10−5 , GSS and Convergence have lower mean cost-adjusted regret than our rule when paired with either PBGI or LogEIPC.
Figure 17: Comparison of cost-adjusted simple regret on three LCBench datasets with λ=10−4 , using scaled proxy runtime versus scaled actual runtime for reporting evaluation cost. Online stopping decisions use proxy runtime in both cases; Hindsight is recomputed for each reporting cost. Changing the reporting cost can alter stopping-rule rankings, as illustrated by the PBGI and LogEIPC combinations on higgs .
Figure 18: Cost-adjusted simple regret across acquisition function and stopping rule pairs under the unknown-cost setting on LCBench with λ=10−4 . The acquisition functions are PBGI, LogEIPC-exp, LCB, and TS. The primary PBGI/LogEIPC-exp stopping criterion uses the expected-cost diagnostic for every acquisition, while LogEIPC-inv-med denotes the median baseline using the inverse-cost diagnostic. The primary rule does not uniformly improve on simple baselines; on adult , its PBGI and LogEIPC-exp combinations have higher mean regret than Immediate and GSS.
Figure 19: Cost-adjusted simple regret of all 35 LCBench datasets when λ=10−3 . Light grey highlights datasets where the matched PBGI pair does not rank among the top three of the seven non-trivial stopping rules paired with the PBGI acquisition function; Immediate and Hindsight are excluded from this ranking.
Figure 20: Cost-adjusted simple regret of all 35 LCBench datasets when λ=10−4 . Light grey highlights datasets where the matched PBGI pair does not rank among the top three of the seven non-trivial stopping rules paired with the PBGI acquisition function; Immediate and Hindsight are excluded from this ranking.
Figure 21: Cost-adjusted simple regret of all 35 LCBench datasets when λ=10−5 . Light grey highlights datasets where the matched PBGI pair does not rank among the top three of the seven non-trivial stopping rules paired with the PBGI acquisition function; Immediate and Hindsight are excluded from this ranking.
Figure 22: Top-20 validation–test rank preservation for every LCBench dataset. Datasets are split into Dunder (red) and Dtop (green) based on whether the matched PBGI pair ranks among the top three PBGI-based acquisition function–stopping rule pairs formed by the seven stopping rules in S at λ=10−4 . The dashed line marks Top-20=0.5 . Datasets where the matched PBGI pair underperforms also have lower validation–test rank preservation. This association is consistent with benchmark mismatch contributing to the observed cost-adjusted regret, without establishing a causal explanation.
Figure 23: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs in the 1D Bayesian regret experiments, with cost‐scaling factor λ=10−1,10−2,10−3 and under uniform cost. The dashed line in each subplot represent fixed iteration stopping (e.g., the y-axis value of the line at iteration 50 represent the cost-adjusted regret when always stop at iteration 50 ).
Figure 24: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs in the 1D Bayesian regret experiments, with cost‐scaling factor λ=10−1,10−2,10−3 and under linear cost. The dashed line in each subplot represent fixed iteration stopping (e.g., the y-axis value of the line at iteration 50 represent the cost-adjusted regret when always stop at iteration 50 ).
Figure 25: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs in the 1D Bayesian regret experiments, with cost‐scaling factor λ=10−1,10−2,10−3 and under periodic cost. The dashed line in each subplot represent fixed iteration stopping (e.g., the y-axis value of the line at iteration 50 represent the cost-adjusted regret when always stop at iteration 50 ).
Figure 26: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs in the 8D Bayesian regret experiments, with cost‐scaling factor λ=10−1,10−2,10−3 and under uniform cost. The dashed line in each subplot represent fixed iteration stopping (e.g., the y-axis value of the line at iteration 50 represent the cost-adjusted regret when always stop at iteration 50 ).
Figure 27: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs in the 8D Bayesian regret experiments, with cost‐scaling factor λ=10−1,10−2,10−3 and under linear cost. The dashed line in each subplot represent fixed iteration stopping (e.g., the y-axis value of the line at iteration 50 represent the cost-adjusted regret when always stop at iteration 50 ).
Figure 28: Comparison of cost-adjusted simple regret across acquisition function and stopping rule pairs in the 8D Bayesian regret experiments, with cost‐scaling factor λ=10−1,10−2,10−3 and under periodic cost. The dashed line in each subplot represent fixed iteration stopping (e.g., the y-axis value of the line at iteration 50 represent the cost-adjusted regret when always stop at iteration 50 ).
Figure 29: Single-trajectory illustration of how the moving-average window size W affects the PBGI/LogEIPC stopping signal on the 8D Bayesian regret benchmark under periodic costs (seed 0, λ=10−2 ), with PBGI ( λ=10−2 ) as the acquisition function. The light grey curve is the raw αtLogEIPC , the blue curve its W -iteration trailing average, the red dashed line the stopping threshold logλ , and the green star the resulting stopping iteration. Without smoothing ( W=1 ) the rule fires early (iter. 24, regret 4.04) on a noisy dip; smoothing defers the trigger and recovers low cost-adjusted regret (iter. 119, regret 2.78 at W=20 ).
Figure 30: Single-trajectory illustration analogous to Figure 29 , with the LogEIPC acquisition function (same seed, same cost regime, λ=10−2 ). Without smoothing the rule fires at iter. 34 with regret 4.01 ; with W=20 it fires at iter. 93 with regret 2.66 .
Figure 31: Single-trajectory illustration analogous to Figure 29 , with Thompson sampling (TS) as the acquisition function. Unlike the matched-acquisition cases, smoothing here pushes the stopping iteration later (iter. 71 at W=1 vs. iter. 215 at W=20 ) without a corresponding drop in cost-adjusted regret – TS does not satisfy the expected-improvement-exceeds-cost property of Lemma 3.1 , so the PBGI/LogEIPC stopping rule has no matched guarantee for it.
Figure 32: Single-trajectory illustration analogous to Figure 29 , with LCB as the acquisition function. The raw LogEIPC signal has a clean transient: smoothing changes the stopping iteration only slightly (iter. 2 at W=1 vs. iter. 5 at W≥5 ) and the cost-adjusted regret stabilises at 2.73 for all W≥5 .
Figure 33: Effect of the moving-average window size W∈{1,5,10,20} on the average stopping iteration (blue, left axis) and the average cost-adjusted simple regret (orange, right axis) for the PBGI/LogEIPC stopping rule on the 8D Bayesian regret benchmark under periodic costs ( λ=10−2 , 50 seeds, error bars are ±2 standard errors). Each subplot fixes one acquisition function. Smoothing yields the largest cost-adjusted regret reductions for the matched PBGI and LogEIPC pairs, a smaller reduction for LCB, and no benefit for TS.
Figure 34: Aggregate ablation analogous to Figure 33 under uniform costs. Smoothing slightly reduces cost-adjusted regret for the matched PBGI and LogEIPC pairs and is roughly neutral for LCB and TS.
Figure 35: Aggregate ablation analogous to Figure 33 under linear costs. Smoothing reduces cost-adjusted regret for the matched PBGI and LogEIPC pairs and for LCB, with no benefit for TS.
Bayesian optimization is a technique for efficiently optimizing unknown functions in a black-box manner. To handle practical settings where gathering data requires use of finite resources, it is desirable to explicitly incorporate function evaluation costs into Bayesian optimization policies. To understand how to do so, we develop a previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's Box problem, a decision problem from economics. The Pandora's Box problem admits a Bayesian-optimal solution based on an expression called the Gittins index, which can be reinterpreted as an acquisition function. We study the use of this acquisition function for cost-aware Bayesian optimization, and demonstrate empirically that it performs well, particularly in medium-high dimensions. We further show that this performance carries over to classical Bayesian optimization without explicit evaluation costs. Our work constitutes a first step towards integrating techniques from Gittins index theory into Bayesian optimization.
Freeze-thaw Bayesian optimization (BO) evaluates candidates in resumable increments but usually stops at a budget or convergence test. We maximize a budget-free utility, the best observed score minus a cost per increment, with a one-step lookahead: advance the candidate with the largest expected improvement (EI) under a fixed surrogate, and stop once no EI exceeds the cost. This rule, EI stopping, never falls below stopping immediately in expected utility, yet it can stop too early. We construct a certificate, a lower bound on the value of two-step lookahead, that proves such a stop premature, and repeating this correction never lowers expected utility under the surrogate. Under the surrogate, EI stops are premature on average at low costs and lose little at high costs. On three hyperparameter optimization benchmarks, a pre-registered test finds EI stopping noninferior to the correction in most high-cost settings, while the correction gains at low costs on two of the three; more information sharing in the surrogate raises EI stopping's utility. On the surrogates of two published methods, EI stopping trades lower scores for fewer training increments. EI stopping is a simple cost-aware reference whose utility depends on the surrogate.
Long Vu, Jongseong Brad Choi, Binoy Ravindran +1
State University of New York Korea · Virginia Tech · Stony Brook University
Bayesian optimization (BO) is a widely used iterative black-box optimization method that utilizes Gaussian process (GP) surrogate models. In practice, BO is typically terminated after a fixed evaluation budget is exhausted, which can incur unnecessary cost and provides no optimality guarantee on solution quality. Recent research in developing a practical stopping criterion has made empirical progress, yet a theoretically sound stopping criterion remains a work in progress. In this work, we present provably tighter instantaneous regret bounds for GP upper confidence bound (GP-UCB) at any given iteration. Then, we propose stopping criteria for GP-UCB based on this tighter bound that ensures an ε-optimal solution with high probability 1−δ upon termination. Numerical experiments are performed to validate and demonstrate the effectiveness and efficiency of our stopping criteria.