Prequential E-Values for Selected-GP Near-Optimality Certificates

1 Optimization and GP Certificates

• Tuning a GP kernel, radius, or inflation on the same adaptive data and certifying as if fixed can increase false-certification risk.Fixed-kernel GP-UCB-style envelopes provide valid rules under a fixed GP assumption.
• Each predeclared GP/RKHS candidate is tested with one-step-ahead residuals and deleted when its e-process crosses 1/δU.The candidate must bound the next queried configuration before its value is observed.
• The certificate uses the largest upper bound among surviving envelopes, avoiding selection of a favorably tight band.One surviving candidate with valid coverage and audit calibration is sufficient for the upper-side guarantee.
• A valid selected-point lower bound and one valid declared envelope yield certificates satisfying f(λ̂τ) ≥ f⋆ − ε with probability at least 1 − (αL + αU + δU).The envelope must have valid all-time upper coverage and a correct one-step audit null; the lower bound has failure probability at most αL.

2 GP Upper Bounds and Prequential E-Value Audits

• Each predeclared GP/RKHS candidate fixes its kernel, parameters, noise or RKHS-radius constants, and confidence inflation, then updates from the observed prefix.A valid envelope assumption makes its bound capable of covering the unqueried domain.
• One-step-ahead observations challenge each candidate, whose violation increments are multiplied into an e-process under its on-path calibration null.Large values indicate evidence against calibration; crossing 1/δU deletes the candidate, with Ville’s inequality bounding deletion probability by δU for candidates satisfying the null.
• The certificate uses the largest upper bound among surviving candidates and abstains if none survive, avoiding selection of a lucky under-covering band.Choosing the tightest fitted GP after seeing the same data would reuse a fixed-GP guarantee after conditioning on success.
• With probability at least 1 − αU − δU, a declared anchor both covers the optimum and is never deleted, so the surviving upper bound remains above the global optimum.Stopping requires the selected-point lower bound and surviving upper bound to satisfy the near-optimality condition; the lower-side error αL is then combined with the upper-side guarantee.
• The number of candidates affects computation and survivor looseness, but not the risk budget.

Experiments

• Experiments use known-optimum analytic objectives and compare methods on identical optimizer runs and selected-configuration lower bound, varying only the upper certificate; fixed-precommitment gains were 3.0 (d = 3) and 13.5 (d = 4).The fixed-precommitment results aggregate d = 3 and d = 4 experiments. On a separate 512-seed RBF length-scale stress sweep, audited and fit-then-certify power/risk pairs were 0.280/0.091 and 0.267/0.183, respectively.
• 3.0 and 13.5 additional correct certificates per additional false certificate were observed for d = 3 and d = 4, respectively, versus random fixed precommitment.In the low and middle ρ tertiles the audit turns many fixed abstentions into certificates; in the hardest tertile both methods mostly abstain.
• 0.280/0.091 versus 0.267/0.183 were the audited and fit-then-certify power/risk pairs on the 512-seed RBF stress sweep, with a risk-per-correct ratio of 0.47.Risk reduction persists across ρ tertiles; the power tradeoff appears mainly in the hardest tertile.

Discussion and limitations

• The procedure handles finite envelope families; continuous hyperparameter families require additional uniform or mixture accounting.
• With tens or hundreds of evaluations, global upper envelopes become weak beyond a few active hyperparameters because of the n^-1/d fill-distance barrier.In that regime valid outcomes often involve abstention unless lower-dimensional structure is declared or model-trusting extrapolation is accepted.
• The geometric limitation leaves global certification constrained by ambient dimension unless the declared structure is lower-dimensional or otherwise stronger.

• Choosing the best observed score creates a winner’s-curse problem for noisy comparisons [4, 15, 16].
• Weighted error budgets provide simultaneous coverage for any data-dependent returned configuration at a finite stopping time.A finite predeclared horizon is recovered by assigning zero weight after that horizon.
• The bounded-score KL lower bound is the experiment’s instantiation, and nontrivial finite-sample lower bounds require an observation assumption.Other metrics require their corresponding one-sided lower bounds.

B GP Upper Bounds and Prequential Audits

• Each envelope candidate is fixed before the run and specifies its kernel, constants, noise-tail bound, and inflation schedule.It then provides a predictable latent envelope and a noisy-score threshold for its one-step audit.
• One-step audits compare each next observation with its candidate’s threshold, accumulating violations into an e-process for screening.The audit uses claims made before the next response is observed.
• The certificate uses the largest upper bound among surviving candidates, preserving validity without selecting a favorably tight band.A fixed anchor with valid coverage and noise calibration is sufficient for the guarantee.
• The flat survivor certificate bounds the probability of any false ε-certificate by αL + αU + δU.
• The number of candidates affects computation and survivor looseness, not the risk budget; choosing the tightest survivor requires separate accounting.

C Post-Selection GP Undercoverage

• The bound applies when the stopping rule fires only if Lτ(ˆλτ) ≥ Uτ − ε and the lower side satisfies its stated guarantee.
• False-stop probability is bounded by αL plus the probability that the claimed global upper bound misses the optimum at stopping.
• The lower side contributes only its declared error budget; the remaining term is controlled by global upper-bound coverage.

D Dimension and Resolution

• Under a Lipschitz modulus, excluding a hidden ε-improvement requires fill distance h_t ≲ ε/L.The upper certificate becomes informative only when the queried set resolves the function class.
• In a d-dimensional box, Lipschitz-based exclusion requires on the order of (L diam(Λ)/ε)^d well-placed evaluations.GP/RKHS envelopes replace the Lipschitz modulus with a kernel uncertainty term but retain ambient-dimension dependence absent stronger structure.
• Without structural smoothness, no non-vacuous finite-history rule can uniformly certify global ε-optimality when an unqueried ball remains.A function can agree at every queried point yet have a hidden ε-better optimum, making the same certification event false.

E Experiment Protocol

• Each empirical comparison evaluates methods on the same ordered observation sequence and scores first certification as correct when f(λ̂_t) ≥ f⋆−ε.Objectives have known global optima; methods may abstain or certify at each prefix.
• The power/risk comparison includes prequential survivors, random fixed precommitment, and fit-then-certify, with separate settings for each baseline comparison.Fixed-precommitment comparisons use d=3,4 rows; fit-then-certify uses a separate 512-seed d=3 RBF length-scale stress sweep.
• The benchmark grid spans d∈{2,3,4}, three kernel-bump objective families, isotropic and anisotropic length scales, and finite-validation binomial observations.Unless stated otherwise, n_val=1000 and ε=0.10; resolution ρ=64^(−1/d)/ℓ_rms is used only to bin objectives.