Cost-Aware Stopping for Freeze-Thaw Bayesian Optimization: When Does One-Step Lookahead Suffice?

Long Vu; Jongseong Brad Choi; Binoy Ravindran; Zhoulai Fu

cs.LGOct 30, 2026

Cost-Aware Stopping for Freeze-Thaw Bayesian Optimization: When Does One-Step Lookahead Suffice?

Authors: Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu

Organizations: State University of New York Korea · Virginia Tech · Stony Brook University

Abstract

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.

Figures & tables

Figure 1: Top: share of the 840 pre-registered reduced instances (Table 4 ; 40 per cell) whose EI stop (EI-S; filled, solid) and ideal H2 stopping (open, dashed) lose less than

\lambda

under GP-atJ, with three arms and two further increments per arm (green), or two arms and three increments per arm (purple); Wilson 95% intervals. Bottom:

(U_{\text{H2-S}}-U_{\text{EI-S}})/\lambda

for H2 stopping (H2-S) under each surrogate, (Tables 1 and 8 ); markers are point estimates, whiskers span the one-sided simultaneous 95% limits. A UCL below the dashed line at one means EI stopping is noninferior at

\delta=\lambda

; a lower limit above zero means H2-S gains, a UCL below zero that it loses. GP-atJ lower limits come from a two-sided band and are conservative (Appendix D.3 ). Gate shares: Table 1 .

	LCBench				PD1				ODBench
$\lambda=\delta$	Gate	H2-S $-$ EI-S	UCL	Verdict	Gate	H2-S $-$ EI-S	UCL	Verdict	Gate	H2-S $-$ EI-S	UCL	Verdict
0.0001	35%	$+0.00003$	$+0.00020$	open	40%	$+0.00135$	$+0.00273$	open	23%	$+0.00106^{\dagger}$	$+0.00205$	open
0.0002	27%	$-0.00001$	$+0.00015$	NI	43%	$+0.00358^{\dagger}$	$+0.00558$	open	19%	$+0.00089$	$+0.00186$	open
0.0005	22%	$-0.00046^{\ddagger}$	$-0.00010$	NI	31%	$+0.00041$	$+0.00097$	open	19%	$+0.00090$	$+0.00291$	open
0.001	17%	$-0.00038^{\ddagger}$	$-0.00018$	NI	20%	$+0.00064$	$+0.00206$	open	29%	$+0.00046$	$+0.00193$	open
0.002	13%	$-0.00052^{\ddagger}$	$-0.00027$	NI	10%	$+0.00104$	$+0.00274$	open	24%	$+0.00031$	$+0.00299$	open

Table 1: H2 stopping (H2-S) minus EI stopping (EI-S) under GP-atJ in the pre-registered test (Appendix E.2 ; development seeds: Table 6 ). Gate: share of episodes in which the gate opens. H2-S

-

EI-S: mean difference; † / ‡ : its two-sided simultaneous 95% band over the 21 cells lies above/below zero (Table 6 ); UCL: one-sided simultaneous 95% upper confidence limit of

\mathbb{E}[U^{\text{GP-atJ}}_{\text{H2-S}}-U^{\text{GP-atJ}}_{\text{EI-S}}]

. Verdict at

\delta=\lambda

: NI, noninferior (UCL

<\delta

); open, not established; other surrogates in Table 8 .

		FT-PFN							Deep-kernel GP
			CFBO-NT, native stop, $B=300$			ifBO, $B=300$				DyHPO, $B=300$
Bench.	$\lambda$	$\bar{\tau}_{\text{EI-S}}$	$U^{\text{FT-PFN}}_{\text{EI-S}}-U_{\text{CFBO-NT}}$	$\Delta\tilde{y}$	$\Delta\tau$	$U^{\text{FT-PFN}}_{\text{EI-S}}-U_{\text{ifBO}}$	$\Delta\tilde{y}$	$\Delta\tau$	$\bar{\tau}_{\text{EI-S}}$	$U^{\text{deep-kernel GP}}_{\text{EI-S}}-U_{\text{DyHPO}}$	$\Delta\tilde{y}$	$\Delta\tau$
LCBench	0.0001	$117$	$+0.0209^{\dagger}$	$+0.0244$	$+35$	$+0.0103^{\dagger}$	$-0.0080$	$-183$	$231$	$+0.0036^{\dagger}$	$-0.0033$	$-69$
	0.0002	$92$	$+0.0215^{\dagger}$	$+0.0276$	$+31$	$+0.0312^{\dagger}$	$-0.0104$	$-208$	$226$	$+0.0112^{\dagger}$	$-0.0036$	$-74$
	0.0005	$66$	$+0.0220^{\dagger}$	$+0.0327$	$+21$	$+0.1030^{\dagger}$	$-0.0141$	$-234$	$217$	$+0.0375^{\dagger}$	$-0.0038$	$-83$
	0.001	$47$	$+0.0318^{\dagger}$	$+0.0410$	$+9$	$+0.2348^{\dagger}$	$-0.0181$	$-253$	$207$	$+0.0885^{\dagger}$	$-0.0043$	$-93$

Table 2: Score–resource tradeoffs for EI stopping (EI-S) on published surrogates: on FT-PFN, CFBO-NT (same weights, native stop, cap

B=300

) and ifBO run to

B

; on DyHPO’s deep-kernel GP, DyHPO run to

B

\Delta\tilde{y}

\Delta\tau

: score and increment differences, EI-S minus the method;

\bar{\tau}_{\text{EI-S}}

: mean increments of EI-S; scores lie in

[0,1]

, and utility is in the same units; † / ‡ : simultaneous 95% band above/below zero; x :

\alpha_{\rm CFBO}>1

. Bands and break-even costs: Table 15 .

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Model		Bellman		Two-step certificate and policies
$S_{b}$	history state after $b$ advances	$V_{\lambda}^{\star}$ , $Q_{\lambda}^{\star}$	optimal value and action value	$g(S)$	largest available EI, augmented by $0$
$\tilde{y}(S)$	incumbent score, $\tilde{y}_{b}=\tilde{y}(S_{b})$	$\Delta_{\lambda}^{\star}(S,i)$	centered advantage of arm $i$	$A^{\rm pool}_{2,i}(S)$	pool-aware two-step advantage
$h_{\lambda}(S)$	stop-now payoff $\tilde{y}(S)-\lambda b$	$O_{i}(S)$	downstream option value	$A_{2,i}(S)$	same-arm two-step advantage
$\mathcal{I}(S)$	available arms	$\mathcal{S}_{\lambda}$ , $\mathcal{S}^{\mathrm{myo}}_{\lambda}$	Bellman and one-step stop sets	$\Gamma_{i}(S)$	switching premium $A^{\rm pool}_{2,i}-A_{2,i}$
$d(S)$	headroom $y_{\max}-\tilde{y}(S)$	$\pi_{\rm EI}$	EI stopping (EI-S)	$\underline{A}^{\rm pool}_{2,i}(S)$	certified lower enclosure
$\mathrm{EI}_{i}(S)$	one-step expected improvement	$\pi_{\rm H2}$	H2 stopping (H2-S), the certified policy	$U$	episode utility $\tilde{y}_{\tau}-\lambda\tau$

Appendix

Table 3: Notation. Section 3 defines the model and Bellman quantities, Section 4 the headroom

d(S)

and the two-step quantities and policies, and Appendix E.1 ideal H2 stopping

\pi_{2}^{\rm ideal}

		$3{\times}2$ : 3 arms, 2 increments			$2{\times}3$ : 2 arms, 3 increments
Instances	$n$	Optimal [95%]	Within $\lambda$ [95%]	Recovered [95%]	Optimal [95%]	Within $\lambda$ [95%]	Recovered [95%]
LCBench	280	74.6% [69, 79]	95.4% [92, 97]	99.8% [99.7, 100.0]	60.4% [55, 66]	77.1% [72, 82]	85.0% [77, 91]
PD1	280	71.8% [66, 77]	88.9% [85, 92]	99.6% [99, 100]	66.8% [61, 72]	79.3% [74, 84]	92.5% [87, 97]
ODBench	280	71.1% [66, 76]	85.0% [80, 89]	98.5% [98, 99]	55.4% [50, 61]	69.3% [64, 74]	81.4% [74, 87]
All	840	72.5% [69, 75]	89.8% [88, 92]	99.2% [98.9, 99.5]	60.8% [57, 64]	75.2% [72, 78]	85.5% [81, 89]
$\lambda=0.0001$	120	74.2% [66, 81]	83.3% [76, 89]	99.3% [99, 100]	51.7% [43, 60]	56.7% [48, 65]	74.3% [60, 84]

Appendix

Table 4: Pre-registered exact in-model gap of EI stopping under GP-atJ on 840 reduced instances drawn from seeds 1–50, 40 per benchmark and cost (Appendix E.1 ).

3{\times}2

: the three arms with the largest EI, two further increments each;

2{\times}3

, on the same frozen states: the two arms with the largest EI, three further increments each. Optimal: share with

V_{\lambda}^{\star}=V_{\pi_{\rm EI}}

; within

\lambda

: share with

V_{\lambda}^{\star}-V_{\pi_{\rm EI}}<\lambda

, both with Wilson 95% intervals; recovered: share of the total gap

\sum(V_{\lambda}^{\star}-V_{\pi_{\rm EI}})

that ideal H2 stopping recovers, with a 95% instance-bootstrap interval. Rows by benchmark are the pre-registered estimands; rows by cost pool the three benchmarks and are descriptive.

Bench.	$\lambda$	Upper	Gaussian part	Lower	[limit]	Verdict	Realized	[limits]	Planning law	Realized	[limits]
		Bounds under the planning law					Seeds 1–50		Seeds 51–100
LCBench	0.0001	1,509	36.9	18.4	$\geq$ 17.9	premature	+5.72	[-0.460, +14.9]	9.26	+0.232	[-0.657, +1.50]
	0.0002	2,708	30.5	11.7	$\geq$ 11.2	premature	+0.613	[-0.971, +2.64]	13.4	+8.90 †	[+1.11, +18.0]
	0.0005	1,282	34.5	7.75	$\geq$ 7.47	premature	+3.41	[-0.0253, +8.63]	2.86	-0.750 ‡ ∗	[-1.35, -0.298]
	0.001	1,538	29.8	6.86	$\geq$ 6.59	premature	-1.01	[-3.10, +0.228]	7.29	+1.02	[-0.854, +3.49]
	0.002	502	33.4	1.39	$\geq$ 1.19	open	+0.0102	[-0.410, +0.546]	3.52	-0.700 ‡	[-1.38, -0.166]

Appendix

Table 5: Full-scale bounds on the gap

V^{\star}_{\lambda}-V_{\pi_{\rm EI}}

at the 840 pre-registered first EI stops of Table 4 under GP-atJ, with all 32 arms and the recorded horizons (40 states per cell), and the long-lookahead policy

\pi_{\rm LA}

replayed on the recorded curves. Utility in units of

10^{-3}

. Upper: information-relaxation bound under the planning law, and its Gaussian part. Lower: value of

\pi_{\rm LA}

under the planning law, with its one-sided 95% Monte Carlo limit. Verdict: premature if that limit exceeds

\lambda

, near-optimal if the upper bound is below

\lambda

, open otherwise. Realized:

U_{\pi_{\rm LA}}-U_{\text{EI-S}}

on the recorded curves from the same states (seeds 1–50) and from 840 fresh first EI stops drawn the same way (seeds 51–100, whose value under the planning law is listed), with one-sided 95% task-clustered bootstrap limits; † / ‡ : lower limit above zero / upper limit below zero; ∗ : also after Holm over the 14 premature cells, the pre-registered family.

Bench.	$\lambda$	Gate	H2-S $-$ EI-S [band]	UCL	H2-S $-$ EI-S [band]
		Seeds 1–50			Pre-registered test
LCBench	0.0001	34%	$+0.00014$ [-0.00008, +0.00036]	$+0.00035$	$+0.00003$ [-0.00015, +0.00021]
	0.0002	25%	$+0.00009$ [-0.00018, +0.00035]	$+0.00034$	$-0.00001$ [-0.00017, +0.00015]
	0.0005	21%	$-0.00047$ [-0.00131, +0.00036]	$+0.00034$	$-0.00046$ [-0.00083, -0.00009] ‡
	0.001	18%	$-0.00049$ [-0.00072, -0.00025] ‡	$-0.00025$	$-0.00038$ [-0.00059, -0.00017] ‡
	0.002	12%	$-0.00042$ [-0.00080, -0.00003] ‡	$-0.00005$	$-0.00052$ [-0.00079, -0.00026] ‡

Appendix

Table 6: H2 stopping (H2-S) minus EI stopping (EI-S) under GP-atJ: on seeds 1–50, the pools of every other table (descriptive, with no tolerance attached), and the two-sided simultaneous 95% bands of the pre-registered test of Table 1 ( † / ‡ : above/below zero). Gate and UCL as in Table 1 .

Benchmark	Gate opened	Certified lower	Realized	Realized $-$ certified [band]	Realized $<0$
LCBench	2,060	+0.11	-1.71	-1.82 [-2.60, -1.13]	94%
PD1	1,199	+0.29	+6.50	+6.21 [+4.99, +7.40]	78%
ODBench	683	+0.46	+3.28	+2.81 [+0.95, +4.77]	83%

Appendix

Table 7: Calibration of the gate on the recorded curves: H2 stopping under GP-atJ on seeds 1–50, over every episode in which the gate opened. The certified lower bound is the lower enclosure of the selected arm’s depth-two advantage where the gate first opened, which under the planning law bounds the expected gain of H2 stopping over EI stopping from that state. The realized gain is

U_{\text{H2-S}}-U_{\text{EI-S}}

of the same episode. Means in units of

10^{-3}

, pooled over the seven costs; the band is a 95% seed-block bootstrap band for realized minus certified.

		$\lambda=\delta$
Surrogate	Bench.	0.0001	0.0002	0.0005	0.001	0.002	0.005	0.01
GP-at, seeds 51–100	LCBench	$+0.00036$ open	$+0.00025$ open	$+0.00002$ NI	$-0.00000$ NI	$-0.00013$ NI	$+0.00032$ NI	$-0.00030$ NI
	PD1	$+0.00701$ open	$+0.00618$ open	$+0.00060$ open	$+0.00396$ open	$+0.00452$ open	$+0.00556$ open	$+0.00422$ NI
	ODBench	$+0.00198$ open	$+0.00097$ open	$+0.00314$ open	$+0.00462$ open	$-0.00007$ NI	$+0.00115$ NI	$+0.00075$ NI
GP-a, seeds 51–100	LCBench	$+0.00033$ open	$+0.00043$ open	$-0.00016$ NI	$+0.00007$ NI	$-0.00004$ NI	$+0.00017$ NI	$+0.00007$ NI
	PD1	$+0.00674$ open	$+0.00572$ open	$+0.00125$ open	$+0.00358$ open	$+0.00605$ open	$+0.00477$ NI	$+0.00357$ NI

Appendix

Table 8: Noninferiority of EI stopping (EI-S) to H2 stopping (H2-S) at

\delta=\lambda

under GP-at (pre-registered) and GP-a (descriptive) on the fresh seeds 51–100, on the pools of Table 1 . Each cell gives the one-sided simultaneous 95% upper confidence limit (UCL) of

\Delta_{\text{H2-S}}=\mathbb{E}[U_{\text{H2-S}}-U_{\text{EI-S}}]

from the bootstrap of Appendix D.3 , one 21-column family per surrogate (10,000 replicates; seeds 2026100501 and 2026102901), and its verdict (NI: UCL

<\lambda

; open: not established). Scores lie in

[0,1]

, and the UCL is in the same units.

		$\lambda=\delta$
Surrogate	Bench.	0.0001	0.0002	0.0005	0.001	0.002	0.005	0.01
GP-atJ, seeds 1–50	LCBench	$+0.00035$ open	$+0.00034$ open	$+0.00034$ NI	$-0.00025$ NI	$-0.00005$ NI	$+0.00011$ NI	$+0.00015$ NI
	PD1	$+0.00220$ open	$+0.00505$ open	$+0.00182$ open	$+0.00245$ open	$+0.00293$ open	$+0.00291$ NI	$+0.00374$ NI
	ODBench	$+0.00147$ open	$+0.00261$ open	$+0.00236$ open	$+0.00456$ open	$+0.00229$ open	$+0.00102$ NI	$+0.00040$ NI
GP-at, seeds 1–50	LCBench	$+0.00054$ open	$+0.00024$ open	$-0.00042$ NI	$+0.00013$ NI	$+0.00011$ NI	$+0.00033$ NI	$+0.00015$ NI
	PD1	$+0.00548$ open	$+0.00574$ open	$+0.00198$ open	$+0.00486$ open	$+0.00415$ open	$+0.00434$ NI	$+0.00346$ NI

Appendix

Table 9: Noninferiority of EI stopping (EI-S) to H2 stopping (H2-S) at

\delta=\lambda

under every surrogate run with H2 stopping. Each cell gives the one-sided simultaneous 95% upper confidence limit (UCL) of

\Delta_{\text{H2-S}}=\mathbb{E}[U_{\text{H2-S}}-U_{\text{EI-S}}]

, and its verdict (NI: UCL

<\lambda

; open: not established). All limits are proper one-sided limits from the fixed-SE studentized signed-maximum seed-block bootstrap of Appendix D.3 (GP-atJ: the 21-column H2-S-minus-EI-S family of the 50-seed extension; GP-at and GP-a: their 50-seed blocks, one 21-column family per surrogate, 10,000 replicates, seed 2026091101). Every row uses seeds 1–50 on the same pools, and every verdict here is descriptive: the pre-registered fresh-seed verdicts for GP-atJ are in Table 1 , the pre-registered ones for GP-at and the descriptive ones for GP-a in Table 8 . Scores lie in

[0,1]

, and the UCL is in the same units.

Bench.	$\lambda$	$U^{\text{GP-atJ}}_{\text{EI-S}}$	GP-at $-$ GP-atJ [band]	GP-a $-$ GP-atJ [band]	$U^{\text{GP-atJ}}_{\text{EI-S}}$	GP-at $-$ GP-atJ [band]	GP-a $-$ GP-atJ [band]
		Seeds 1–50			Fresh seeds 51–100
LCBench	0.0001	$0.7627$	$-0.0006$ [-0.0011, -0.0002] ‡	$-0.0009$ [-0.0014, -0.0004] ‡	$0.7642$	$-0.0004$ [-0.0007, -0.0000] ‡	$-0.0005$ [-0.0008, -0.0002] ‡
	0.0002	$0.7544$	$-0.0013$ [-0.0017, -0.0008] ‡	$-0.0014$ [-0.0019, -0.0009] ‡	$0.7559$	$-0.0008$ [-0.0012, -0.0005] ‡	$-0.0010$ [-0.0014, -0.0007] ‡
	0.0005	$0.7372$	$-0.0021$ [-0.0030, -0.0012] ‡	$-0.0019$ [-0.0029, -0.0010] ‡	$0.7389$	$-0.0022$ [-0.0035, -0.0010] ‡	$-0.0019$ [-0.0030, -0.0007] ‡
	0.001	$0.7197$	$-0.0018$ [-0.0026, -0.0009] ‡	$-0.0026$ [-0.0036, -0.0016] ‡	$0.7212$	$-0.0014$ [-0.0023, -0.0005] ‡	$-0.0018$ [-0.0029, -0.0008] ‡
	0.002	$0.6939$	$-0.0025$ [-0.0035, -0.0015] ‡	$-0.0036$ [-0.0047, -0.0025] ‡	$0.6972$	$-0.0024$ [-0.0033, -0.0015] ‡	$-0.0032$ [-0.0042, -0.0023] ‡

Appendix

Table 10: EI stopping (EI-S) under the three surrogates, on the pools of Table 1 : its mean utility under GP-atJ, and EI-S under GP-at and under GP-a minus EI-S under GP-atJ, paired by seed, on the development seeds 1–50 and on the fresh seeds 51–100. Scores lie in

[0,1]

, and utility is in the same units. [band]: two-sided simultaneous 95% band over the 21 cells of each contrast and seed set (Appendix D.3 ; † / ‡ : above/below zero, so GP-atJ behind/ahead). Descriptive: no hypothesis was declared.

Seeds	Step	Mean	$p$ [Wilcoxon]	Pos.	Above
1–50	GP-at $-$ GP-a	$+0.0026$	$<10^{-16}$ [ $<10^{-13}$ ]	49/50	9
	GP-atJ $-$ GP-at	$+0.0032$	$<10^{-15}$ [ $<10^{-11}$ ]	47/50	14
	GP-atJ $-$ GP-a	$+0.0058$	$<10^{-21}$ [ $<10^{-14}$ ]	49/50	16
51–100	GP-at $-$ GP-a	$+0.0026$	$<10^{-14}$ [ $<10^{-13}$ ]	47/50	8
	GP-atJ $-$ GP-at	$+0.0030$	$<10^{-16}$ [ $<10^{-11}$ ]	48/50	13
	GP-atJ $-$ GP-a	$+0.0056$	$<10^{-23}$ [ $<10^{-14}$ ]	49/50	15

Appendix

Table 11: EI stopping’s utility at each step of added transient sharing (F3). Mean: the step’s EI-S utility difference averaged over the 21 cells and the 50 seed blocks;

p

: one-sample

t

-test of the 50 per-seed-block averages against zero (Wilcoxon signed-rank in brackets); Pos.: seed blocks with a positive average; Above/Below: cells whose two-sided simultaneous 95% band, over one joint family of all 63 cells of the seed set (critical values 3.32 and 3.34), lies above/below zero.

Group	$\lambda$	seeds 1–50 [band]	seeds 51–100 [band]	Tasks $+$	Cap at EI stop	No cap hit
				(seeds 1–50; 51–100)		(seeds 1–50; 51–100)
LCBench	0.0001	$+0.00014$ [-0.00009, +0.00037]	$+0.00003$ [-0.00016, +0.00021]	13/35 ; 8/35	$46.5\%$	$+0.00028$ ; $+0.00007$
LCBench	0.0002	$+0.00009$ [-0.00019, +0.00036]	$-0.00001$ [-0.00017, +0.00016]	11/35 ; 9/35	$37.4\%$	$+0.00019$ ; $+0.00005$
LCBench	0.0005	$-0.00047$ [-0.00135, +0.00040]	$-0.00046$ [-0.00084, -0.00007] ‡	8/35 ; 4/35	$24.2\%$	$+0.00002$ ; $-0.00022$
LCBench	0.001	$-0.00049$ [-0.00073, -0.00024] ‡	$-0.00038$ [-0.00060, -0.00017] ‡	5/35 ; 4/35	$10.2\%$	$-0.00051$ ; $-0.00036$
LCBench	0.002	$-0.00042$ [-0.00082, -0.00002] ‡	$-0.00052$ [-0.00080, -0.00025] ‡	6/35 ; 4/35	$0.0\%$	$-0.00042$ ; $-0.00052$

Appendix

Table 12: H2 stopping (H2-S) minus EI stopping (EI-S) under GP-atJ, split by native horizon: equal-task paired

U^{\text{GP-atJ}}_{\text{H2-S}}-U^{\text{GP-atJ}}_{\text{EI-S}}

with its two-sided simultaneous 95% fixed-task seed-block band ( † / ‡ : above/below zero), one 28-column family per seed set (critical values 3.27 and 3.24). Scores lie in

[0,1]

, and utility is in the same units. The long-horizon group holds the 3 PD1 tasks with more than 100 native checkpoints; the short-horizon group holds the other 12. “Tasks

+

” counts tasks whose 50-seed mean favors H2-S, on seeds 1–50 and 51–100. “Cap at EI stop” is the share of seed-1–50 episodes in which some configuration has consumed every recorded checkpoint when EI stops; “No cap hit” is the contrast over the group’s other episodes, pooled and without a band, on seeds 1–50 and 51–100. No verdict is attached.

		$U^{\text{GP-atJ}}_{\text{EI-S}}(\text{changed})-U^{\text{GP-atJ}}_{\text{EI-S}}(\text{primary})$				$\Delta\tau$
Bench.	$\lambda$	Noise $\times\frac{1}{4}$	Noise $\times 4$	Prior $\times\frac{1}{2}$	Prior $\times 2$	Noise $\times\frac{1}{4}$	Noise $\times 4$	Prior $\times\frac{1}{2}$	Prior $\times 2$
LCBench	0.0001	$-0.0002$	$-0.0046^{\ddagger}$	$-0.0001$	$-0.0005^{\ddagger}$	$-39.5$	$+85.1$	$-11.3$	$+14.6$
	0.0002	$+0.0020^{\dagger}$	$-0.0101^{\ddagger}$	$+0.0002$	$-0.0008^{\ddagger}$	$-29.9$	$+72.5$	$-9.8$	$+8.3$
	0.0005	$+0.0055^{\dagger}$	$-0.0245^{\ddagger}$	$+0.0025^{\dagger}$	$-0.0026^{\ddagger}$	$-18.0$	$+59.1$	$-10.0$	$+7.6$
	0.001	$+0.0081^{\dagger}$	$-0.0388^{\ddagger}$	$+0.0027^{\dagger}$	$-0.0065^{\ddagger}$	$-11.6$	$+43.9$	$-6.2$	$+7.5$
	0.002	$+0.0051^{\dagger}$	$-0.0423^{\ddagger}$	$+0.0050^{\dagger}$	$-0.0073^{\ddagger}$	$-3.9$	$+23.8$	$-5.1$	$+4.5$

Appendix

Table 13: EI stopping (EI-S) under GP-atJ with one of its settings changed, minus EI-S at the primary settings,

U^{\text{GP-atJ}}_{\text{EI-S}}(\text{changed})-U^{\text{GP-atJ}}_{\text{EI-S}}(\text{primary})

: the fresh-observation noise variance scaled by

\frac{1}{4}

4

, or both prior variances scaled by

\frac{1}{2}

2

, paired per episode on the same seeds 1–50, pools and costs. Positive values favor the changed setting. Scores lie in

[0,1]

, and utility is in the same units; † / ‡ : pointwise 95% seed-block band above/below zero.

\Delta\tau

: mean change in increments.

Bench.	$\lambda$	Primary	Noise $\times\frac{1}{4}$	Noise $\times 4$	Prior $\times\frac{1}{2}$	Prior $\times 2$	Calibrated noise
LCBench	0.0001	$+0.0006^{\dagger}$	$+0.0005$	$+0.0001$	$+0.0014^{\dagger}$	$+0.0001$	$+0.0003$
	0.0002	$+0.0013^{\dagger}$	$+0.0009^{\dagger}$	$+0.0006^{\dagger}$	$+0.0008$	$+0.0008^{\dagger}$	$+0.0002$
	0.0005	$+0.0021^{\dagger}$	$+0.0016^{\dagger}$	$+0.0014^{\dagger}$	$+0.0016^{\dagger}$	$+0.0022^{\dagger}$	$+0.0002$
	0.001	$+0.0018^{\dagger}$	$+0.0007$	$+0.0002$	$+0.0023^{\dagger}$	$+0.0019^{\dagger}$	$-0.0001$
	0.002	$+0.0025^{\dagger}$	$+0.0011^{\dagger}$	$+0.0045^{\dagger}$	$+0.0014$	$+0.0007$	$-0.0002$
	0.005	$+0.0029^{\dagger}$	$+0.0049^{\dagger}$	$+0.0008$	$+0.0040^{\dagger}$	$+0.0017$	$+0.0047^{\dagger}$

Appendix

Table 14: EI stopping (EI-S) under GP-atJ minus EI-S under GP-at,

U^{\text{GP-atJ}}_{\text{EI-S}}-U^{\text{GP-at}}_{\text{EI-S}}

, with both surrogates at the same settings: the primary settings, the noise variance scaled by

\frac{1}{4}

4

, the prior variances scaled by

\frac{1}{2}

2

, or a noise variance calibrated per task from the recorded curves of the other tasks of its benchmark. Paired per episode on the pools and seeds 1–50 of Table 1 ; scores lie in

[0,1]

, and utility is in the same units. † / ‡ : simultaneous 95% seed-block band above/below zero, over all 126 cells (critical value 3.60; Appendix D.3 ). Every seed was observed at the primary settings before these runs; no verdict is attached.

	FT-PFN			Deep-kernel GP
$\lambda$	$-$ CFBO-NT [band]	$-$ ifBO, $B$ [band]	$\lambda^{\star}$	$-$ DyHPO, $B$ [band]	$\lambda^{\star}$	$-$ EI-S on FT-PFN [band]
LCBench
0.0001	$+0.0209$ [+0.0176, +0.0241] †	$+0.0103$ [+0.0086, +0.0119] †	0.00004	$+0.0036$ [+0.0023, +0.0049] †	0.00005	$-0.0092$ [-0.0109, -0.0076] ‡
0.0002	$+0.0215$ [+0.0179, +0.0251] †	$+0.0312$ [+0.0290, +0.0334] †	0.00005	$+0.0112$ [+0.0097, +0.0127] †	0.00005	$-0.0226$ [-0.0244, -0.0207] ‡
0.0005	$+0.0220$ [+0.0174, +0.0266] †	$+0.1030$ [+0.1000, +0.1060] †	0.00006	$+0.0375$ [+0.0351, +0.0399] †	0.00005	$-0.0680$ [-0.0714, -0.0647] ‡
0.001	$+0.0318$ [+0.0236, +0.0399] †	$+0.2348$ [+0.2310, +0.2386] †	0.00007	$+0.0885$ [+0.0839, +0.0931] †	0.00005	$-0.1489$ [-0.1549, -0.1428] ‡

Appendix

Table 15: Utility valuation of EI stopping’s (EI-S) score–resource tradeoffs in Table 2 , on seeds 1–50. Entries are equal-task paired utility differences with the simultaneous 95% band over the 21 cells of each column ( † / ‡ : band above/below zero); scores lie in

[0,1]

, and utility is in the same units. On FT-PFN: EI-S minus CFBO-NT (same weights,

\alpha_{\rm CFBO}=300\lambda

) and minus ifBO run to

B=300

. On DyHPO’s deep-kernel GP: EI-S minus DyHPO run to

B

, and minus EI-S on FT-PFN.

\lambda^{\star}=\Delta\tilde{y}/\Delta\tau

is the cell-specific break-even cost against a method run to

B

, holding that cell’s outcomes fixed. For

\lambda>\lambda^{\star}

, the priced increment savings exceed the score loss in that cell; its endpoint, score and duration change across costs. x : outside the range

\alpha_{\rm CFBO}\leq 1

of Lee et al. (2025) .

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 253 papers

May 21, 2026

Regret-Based $(ε,δ)$ -optimal Stopping Criteria for Bayesian Optimization

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.

Haowei Wang, Jingyi Wang, Qiyu Wei

The University of Manchester, UK

Bayesian Optimization Optimal Stopping UCB Algorithms

Ask PDF

Jul 31, 2026

Frugal Bayesian Optimization: Scalable Surrogates for Data- and Resource-Limited Discovery

Bayesian Optimization (BO) is widely adopted for data-efficient optimization in scientific and engineering applications, yet its computational cost is rarely evaluated alongside optimization performance. Here we present a systematic, compute-aware study of BO that evaluates surrogate models along two axes: optimization quality and computational frugality. Across eight benchmark functions and nine real-world datasets spanning materials science, mechanics, robotics, chemistry, and machine learning, we benchmark four surrogate models: Gaussian Processes, Random Forests, NGBoost, and Bayesian Adaptive Spline Surfaces. We show that Gaussian Process-based BO consistently incurs the highest time and memory overhead without delivering superior optimization or sample efficiency. In contrast, scalable alternatives achieve equal or better performance at a fraction of the computational cost. Motivated by these findings, we introduce a surrogate-recommendation framework that predicts the most suitable BO surrogate from inexpensive dataset characteristics. Together, these results establish FruBO as a reproducible, compute-aware baseline for Bayesian Optimization and provide practical guidance for surrogate selection under limited computational and experimental budgets.

Panagiotis Krokidas, Christoforos Rekatsinas, Vassilis Sioros +3

Institute of Informatics and Telecommunications, National Centre for Scientific Research "Demokritos", Agia Paraskevi, Greece. · Department of Mechanical Engineering and Aeronautics, University of Patras, Patras Greece. · Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece. +4

Surrogate Modeling Bayesian Optimization

Ask PDF

Jul 5, 2026

How Many Initial Points Does Bayesian Optimization Need?

Bayesian Optimization (BO) generally begins with an initialization phase: a batch of

n_0

uninformed evaluations. The choice of

n_0

remains largely heuristic, and we empirically observe that the total cost (random initial points plus BO iterations needed to find the global optimum) is U-shaped in

n_0

, i.e., a practitioner wastes resources by selecting either too low or too high a value of

n_0

. We find this tradeoff persists across MLE, Bayesian MCMC, and exact GP hyperparameters, as well as across acquisition functions. Toward the latter, Thompson Sampling appears an exception, with both total cost and simple regret essentially

n_0

-agnostic, though higher in our experiments. We attribute this U-shape to the known boundary issue of variance-driven BO: BO burns early budget on corners of the hypercube before turning inward. We demonstrate this effect using a 3D BO trajectory where the exact hyperparameters are known. We conclude with practical recommendations: use multi-step lookahead BO where possible; otherwise use Thompson Sampling when

n_0

cannot be tuned, and a generously large

n_0

when it can.

Mujin Cheon, James Odgers, Dong-Yeun Koh +1

Korea Advanced Institute of Science & Technology (KAIST) · HayanMind Inc. · Technical University of Nuremberg (UTN) +3

Bayesian Optimization Global Optimization

Ask PDF

Abstract

Bayesian Optimization

Explore similar work

Regret-Based (ε,δ)(ε,δ)(ε,δ)-optimal Stopping Criteria for Bayesian Optimization

Frugal Bayesian Optimization: Scalable Surrogates for Data- and Resource-Limited Discovery

How Many Initial Points Does Bayesian Optimization Need?

Regret-Based $(ε,δ)$ -optimal Stopping Criteria for Bayesian Optimization