stat.MLAug 29, 2026

Optimal Recovery Meets Bayesian Learning: Where Worst-Case Bounds Pay Off

Authors: Gordei Verbii

Organizations: Independent Researcher

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Worst-case Optimal Recovery (OR) and Bayesian learning describe the same Gaussian-quadratic-Hilbert problems in two vocabularies. We sharpen the correspondence - the radius of information equals a nugget-optimized GP posterior variance and is attained by the posterior mean at a closed-form balance nugget - and measure, inside three published Bayesian systems, where the worst-case side pays. The ledger is two-sided: the losses instruct as much as the wins. Morozov calibration tracks a test-access oracle within 1.001.00-1.19×1.19\times where σσ-blind rules fail, is 4.94.9-6.3×6.3\times more reproducible across noise draws (p=0.002p=0.002-0.0040.004), and is the only deployable rule whose selection survives a change of backend (1.36×1.36\times against 1212-30×30\times for the released weight, ML-II and GCV); tight certificates cover at the information-theoretic floor with no numerical slack. But on exchangeable data split-conformal beats the OR head on interval score, a water-filling prior adds nothing without an oracle noise hint, and under covariate shift the OR band keeps coverage on every dataset yet loses interval score to split-conformal, and to a feature-free constant band, on most cells; what pays is not shift but shift on a learnable target, which a training-free audit statistic predicts before any model is fitted. In Bayesian optimization the certified width is a validity floor whose scalar inflation we prove inert under a checkable margin condition and check at every step. Inertness is graded, not binary, and in the size of the inflation as much as in the objective: κ=2κ{=}2 is inert wherever κ=5κ{=}5 is and on more cells besides, while κ=5κ{=}5 moves half the Ackley seeds and every Griewank seed. Exploration is a shape problem, not a scale one. The design rule: match the guarantee tool to the data regime, and audit the regime first.

Figures & tables

rel. noisereleasedMorozovML-IIGCVL-curveoraclegainM/o
04.0 ⁣⋅ ⁣10−44.0\!\cdot\!10^{-4}4.0 ⁣⋅ ⁣10−44.0\!\cdot\!10^{-4}4.0 ⁣⋅ ⁣10−44.0\!\cdot\!10^{-4}4.0 ⁣⋅ ⁣10−44.0\!\cdot\!10^{-4}1.4 ⁣⋅ ⁣10−31.4\!\cdot\!10^{-3}4.0 ⁣⋅ ⁣10−44.0\!\cdot\!10^{-4}1.001.001.00
10−410^{-4}3.0 ⁣⋅ ⁣10−23.0\!\cdot\!10^{-2}7.9 ⁣⋅ ⁣10−47.9\!\cdot\!10^{-4}3.0 ⁣⋅ ⁣10−23.0\!\cdot\!10^{-2}3.0 ⁣⋅ ⁣10−23.0\!\cdot\!10^{-2}1.4 ⁣⋅ ⁣10−31.4\!\cdot\!10^{-3}7.4 ⁣⋅ ⁣10−47.4\!\cdot\!10^{-4}40×40\times [20,77]1.12
3 ⁣⋅ ⁣10−43\!\cdot\!10^{-4}4.3 ⁣⋅ ⁣10−24.3\!\cdot\!10^{-2}1.1 ⁣⋅ ⁣10−31.1\!\cdot\!10^{-3}9.2 ⁣⋅ ⁣10−39.2\!\cdot\!10^{-3}3.9 ⁣⋅ ⁣10−23.9\!\cdot\!10^{-2}5.0 ⁣⋅ ⁣10−35.0\!\cdot\!10^{-3}9.5 ⁣⋅ ⁣10−49.5\!\cdot\!10^{-4}40×40\times [21,135]1.18
10−310^{-3}5.3 ⁣⋅ ⁣10−25.3\!\cdot\!10^{-2}1.9 ⁣⋅ ⁣10−31.9\!\cdot\!10^{-3}3.8 ⁣⋅ ⁣10−33.8\!\cdot\!10^{-3}1.2 ⁣⋅ ⁣10−21.2\!\cdot\!10^{-2}1.3 ⁣⋅ ⁣10−21.3\!\cdot\!10^{-2}1.7 ⁣⋅ ⁣10−31.7\!\cdot\!10^{-3}27×27\times [14,34]1.19
3 ⁣⋅ ⁣10−33\!\cdot\!10^{-3}1.0 ⁣⋅ ⁣10−11.0\!\cdot\!10^{-1}4.6 ⁣⋅ ⁣10−34.6\!\cdot\!10^{-3}4.7 ⁣⋅ ⁣10−34.7\!\cdot\!10^{-3}3.8 ⁣⋅ ⁣10−33.8\!\cdot\!10^{-3}4.7 ⁣⋅ ⁣10−34.7\!\cdot\!10^{-3}3.6 ⁣⋅ ⁣10−33.6\!\cdot\!10^{-3}23×23\times [17,94]1.15
10−210^{-2}6.2 ⁣⋅ ⁣10−16.2\!\cdot\!10^{-1}1.2 ⁣⋅ ⁣10−21.2\!\cdot\!10^{-2}1.2 ⁣⋅ ⁣10−21.2\!\cdot\!10^{-2}1.2 ⁣⋅ ⁣10−21.2\!\cdot\!10^{-2}1.2 ⁣⋅ ⁣10−21.2\!\cdot\!10^{-2}1.2 ⁣⋅ ⁣10−21.2\!\cdot\!10^{-2}47×47\times [24,71]1.00
Table 1: Case A: median test RMSE over 5 noise seeds per rule at 24224^{2} collocation (shared λ2\lambda_{2} grid); gain == released // Morozov, median [min,max] of the per-cell ratio; last column the median per-cell Morozov // oracle ratio. The σ=0\sigma=0 row is the median of five re-runs (the solver is not run-to-run deterministic, Table 8 , App. D ), where the Morozov branch reduces to arg⁡min⁡\arg\min misfit and returns the released weight in 5/55/5 runs, so its gain is exactly 11 .
    split-CPtriv (constant)OR head (R1)OR, no floor
datasetR2R^{2}dMd_{\mathrm{M}}nncovwidIScovwidIScovwidIScovwidIS
concrete0.3431.2940.8310.803.740.9701.964.260.9962.047.220.9771.436.27
diabetes0.4191.2560.9502.094.880.9952.054.171.0003.4526.210.9231.8324.01
california0.7401.3930.9621.353.350.9692.264.961.0003.29111.00.9541.55108.2
energy0.9653.0430.7840.332.050.9861.984.031.0001.413.441.0001.293.20
yacht0.9951.6030.8960.663.240.9362.736.390.9711.042.730.9680.972.62
Table 2: Case B under covariate shift, per dataset: the ledger the pooled numbers hide. Coverage, width and IS are means over that dataset’s shift cells – width the within-cell median half-width, IS the Winkler score at α=0.05\alpha=0.05 , lower better – because the per-point tail lives in the mean. R2R^{2} is the training-free RandomForest 5-fold audit statistic of Table 12 (App. E ), computed before any model is fitted; dMd_{\mathrm{M}} is the median Mahalanobis shift severity; nn is the number of shift cells the dataset contributes, and on diabetes the two OR columns rest on 55 of the 66 , the OR arms having refused on diabetes/shift/0/0.5 . Bold marks the lowest interval score among the four arms shown ; on energy and yacht the full nine-arm ledger contains arms that score lower still (Table 14 , App. E ). The coverage the OR head wins over split-CP on all 55 datasets is the only universal win here; on california its interval score is destroyed by a per-point tail (Table 16 ) that costs or1_nf almost as much.
Figure 1: Case B gap task, ten seeds. (a) the six bands on seed 77 – the median seed of the ten on κ⋆\kappa_{\star} , on qcpq_{cp} and on every region width, its qcp=0.8395q_{cp}=0.8395 being the paper’s single-seed ±0.84\pm 0.84 – the OR band’s ten-seed envelope in grey, the vertical range truncated for legibility; the DAK band, both conformal variants and the constant-predictor band are flat. (b) half-width profiles on a log axis, all ten seeds, every half-width in full: the OR band pinches on the data and inflates through the gap and the extrapolation, against the marked 1.96σ^1.96\hat{\sigma} and 1.96σtrue1.96\sigma_{\mathrm{true}} . On the seed drawn the learner overestimates the known noise by 1.62×1.62\times ( 0.3180.318 against 0.1960.196 ), ten-seed median 1.76×1.76\times , which is where the in-distribution width comparison of Table 20 goes.
Figure 2: κ\kappa -inertness is graded rather than binary; one point per benchmark ×\times κ\kappa -pair. (a) Ordering the benchmarks by radius dispersion, the identity fraction is monotone non-increasing for every κ\kappa pair. (b) Both dependences – on dispersion and on ∣Δκ∣|\Delta\kappa| – collapse onto the single dimensionless covariate x=∣Δκ∣⋅osc(c^)/mean(c^)x=|\Delta\kappa|\cdot\mathrm{osc}(\hat{c})/\mathrm{mean}(\hat{c}) , the axis broken across the eight empty decades separating the saturated benchmarks from the rest. Bars are Clopper–Pearson 95%95\% intervals. Two readings need care: the counts drawn are regret-trajectory identity, marginally weaker than the action-level counts of Table 25 (App. F ); and the two left-most dispersion values, printed under the benchmark names inside the shaded saturated band, are O(μlo)O(\mu_{\mathrm{lo}}) grid artifacts and not measurements, shown only to place those benchmarks at the left end of the ordering and never to be compared with each other (see text and Rem. A.4 ).
Appendix figures & tables44 assets

Supplementary material from the paper’s appendix.

Appendix

Optimal RecoveryBayesian learning
model ball ∥u∥≤ε\lVert u\rVert\leq\varepsilon ; noise ball ∥e∥≤η\lVert e\rVert\leq\etaprior scale; Gaussian likelihood
regularization weight / nugget ν\nuprior-to-noise ratio σ2/s2\sigma^{2}/s^{2}
power function (exact data)GP posterior sd
radius of information E⋆(x)E_{\star}(x) , Eq. ( 2 )nugget-optimized posterior variance (new, Thm. 4.1 )
conditional Chebyshev interval Iφx(y)I_{\varphi_{x}}(y)total-ambiguity robust-Bayes credible interval (Thm. 4.2 )
Occam radius ρoc\rho_{\mathrm{oc}} ; conformal inflation κ⋆ρoc\kappa_{\star}\rho_{\mathrm{oc}}degenerate / repaired data-driven prior scale (Lem. 4.3 , Thm. 4.4 )
Appendix
Table 3: Working dictionary.
KnownHere
Two-ellipsoid value problem; linearity of optimal recovery; S-procedure exactness ( Micchelli and Rivlin, 1977 ; Melkman and Micchelli, 1979 ; Foucart and Liao, 2024a ; Foucart and Liao, 2024b ) ; optimal parameter within the regularization family ( Foucart and Liao, 2023 ) ; Morozov’s principle ( Morozov, 1966 ; Engl et al., 1996 )Bayesian packaging ( 2 ) as nugget-optimized posterior variance; the identity V1/μ=pf2+wn2/μV_{1/\mu}=\mathrm{pf}^{2}+\mathrm{wn}^{2}/\mu and the 6-line AM–GM attainment proof with the balance equation μ⋆=ε wn/(η pf)\mu_{\star}=\varepsilon\,\mathrm{wn}/(\eta\,\mathrm{pf}) ; per-functional delivered certificate == radius as an implementation invariant
Γ\Gamma -minimax collapses to minimax under total ambiguity ( Berger, 1985 ; Vidakovic, 2000 ) ; Chebyshev-center computation ( Foucart and Liao, 2024b ) ; OUQ programs ( Owhadi et al., 2013 )The per-functional credible-interval reading with certified 22 -parameter dual, exact-row elimination and pencil-fast evaluation; positioning as a drop-in band for learned features
Split conformal prediction ( Vovk et al., 2005 ; Lei et al., 2018 ; Gibbs and Candès, 2021 )Occam-degeneracy lemma (why data-driven radii collapse); conformal calibration of the model-ball radius via nested bands, with the saturation-to-additive-floor fallback
Appendix
Table 4: Provenance ledger for Sec. 4 .
Data regimeRecommended toolEvidence
no exchangeable calibration dataOR ball ++ MorozovSec. 6 , Tab. 1 , 7 , 9
exchangeable, in-distributionsplit-CP (constant or normalized); the OR head is valid but wider and scores worseTab. 14 , Fig. 13
covariate shift, learnable target (RF CV R2≳0.95R^{2}\gtrsim 0.95 )OR shape for coverage, and drop the conformal floor, which is a net loss on interval score; on a proper score a conformal constant can still win, as split-CP does on energyTab. 2 , 19 , Fig. 1
covariate shift, poorly learnable targeta wider conformal constant ; the OR band’s per-point tail costs more than its coverage buysTab. 2 , Fig. 17
exploration bonusfloor for validity; shape, not scale – and check Prop. 4.5 before scalingProp. 4.5 , Fig. 2 , Tab. 25 , 26
any of the above, before trusting a dispersion numbermeasure the run-to-run floor firstTab. 8 , 9
Appendix
Table 5: The design rule in one table: the regime label alone is not enough, and the cheap audit that decides between the two shift rows costs one random forest and no model fit. Every float the Evidence column cites lives in an appendix except Tab. 1 , 2 and Fig. 1 , 2 (Case A: App. D ; Case B: App. E ; Case C: App. F ).
rel. noisereleasedMorozovML-IIGCVL-curveoraclegainM/o
02.8 ⁣⋅ ⁣10−22.8\!\cdot\!10^{-2}2.8 ⁣⋅ ⁣10−22.8\!\cdot\!10^{-2}2.8 ⁣⋅ ⁣10−22.8\!\cdot\!10^{-2}2.8 ⁣⋅ ⁣10−22.8\!\cdot\!10^{-2}1.7 ⁣⋅ ⁣10−21.7\!\cdot\!10^{-2}1.6 ⁣⋅ ⁣10−21.6\!\cdot\!10^{-2}1.0×1.0\times [1,97]1.71
10−410^{-4}1.8 ⁣⋅ ⁣10−11.8\!\cdot\!10^{-1}1.6 ⁣⋅ ⁣10−21.6\!\cdot\!10^{-2}1.6 ⁣⋅ ⁣10−11.6\!\cdot\!10^{-1}1.6 ⁣⋅ ⁣10−11.6\!\cdot\!10^{-1}2.0 ⁣⋅ ⁣10−22.0\!\cdot\!10^{-2}1.6 ⁣⋅ ⁣10−21.6\!\cdot\!10^{-2}11×11\times [7,18]1.00
3 ⁣⋅ ⁣10−43\!\cdot\!10^{-4}1.1 ⁣⋅ ⁣10−11.1\!\cdot\!10^{-1}1.7 ⁣⋅ ⁣10−21.7\!\cdot\!10^{-2}1.1 ⁣⋅ ⁣10−11.1\!\cdot\!10^{-1}1.1 ⁣⋅ ⁣10−11.1\!\cdot\!10^{-1}3.7 ⁣⋅ ⁣10−23.7\!\cdot\!10^{-2}1.6 ⁣⋅ ⁣10−21.6\!\cdot\!10^{-2}6.7×6.7\times [5,14]1.04
10−310^{-3}4.1 ⁣⋅ ⁣10−14.1\!\cdot\!10^{-1}1.7 ⁣⋅ ⁣10−21.7\!\cdot\!10^{-2}2.6 ⁣⋅ ⁣10−12.6\!\cdot\!10^{-1}2.6 ⁣⋅ ⁣10−12.6\!\cdot\!10^{-1}1.7 ⁣⋅ ⁣10−21.7\!\cdot\!10^{-2}1.6 ⁣⋅ ⁣10−21.6\!\cdot\!10^{-2}23×23\times [16,70]1.05
3 ⁣⋅ ⁣10−33\!\cdot\!10^{-3}5.6 ⁣⋅ ⁣10−15.6\!\cdot\!10^{-1}1.8 ⁣⋅ ⁣10−21.8\!\cdot\!10^{-2}4.2 ⁣⋅ ⁣10−24.2\!\cdot\!10^{-2}5.6 ⁣⋅ ⁣10−15.6\!\cdot\!10^{-1}4.2 ⁣⋅ ⁣10−24.2\!\cdot\!10^{-2}1.7 ⁣⋅ ⁣10−21.7\!\cdot\!10^{-2}31×31\times [18,51]1.03
10−210^{-2}1.01.02.2 ⁣⋅ ⁣10−22.2\!\cdot\!10^{-2}4.5 ⁣⋅ ⁣10−24.5\!\cdot\!10^{-2}1.01.01.3 ⁣⋅ ⁣10−11.3\!\cdot\!10^{-1}2.2 ⁣⋅ ⁣10−22.2\!\cdot\!10^{-2}42×42\times [37,57]1.00
Appendix
Table 6: Case A at 16216^{2} collocation, same protocol and the same five noise seeds (median test RMSE over 5 seeds). The coarse grid is discretization-limited rather than noise-limited: the oracle RMSE barely moves with σ\sigma (exponent 0.0550.055 ) and the whole λ2≤5\lambda_{2}\leq 5 half of the grid is nearly flat, which is why every ratio against Morozov is larger here. The σ=0\sigma=0 row is the median of five re-runs; at 16216^{2} the released weight diverges on one of them (RMSE 2.072.07 ), which is why the noise-free gain is not 11 .
Figure 3: Case A parameter-choice rules, both collocation grids. Median test RMSE against relative noise for all six rules with the interquartile band over the five noise seeds, log–log, and dotted horizontals marking each rule’s own σ=0\sigma=0 median. ML-II and GCV are pinned to the released weight at low noise and release it only at high noise, which is the non-monotonicity their negative fitted exponents record; Morozov and the oracle share a clean positive slope.
Figure 4: Selected data-fit weight against noise level, median with interquartile band and all five individual cells, log–log; the seven admissible grid values are drawn as faint horizontals so the offset between Morozov and the oracle can be counted directly. Morozov sits at least one grid step below the oracle in 18/2518/25 noisy cells at 24224^{2} (exactly one step in 1414 , two in 44 ), matches it in 7/257/25 , and is never above it.
Figure 5: log⁡10(rule/oracle)\log_{10}(\text{rule}/\text{oracle}) per grid, with every one of the 2525 cells per rule drawn as a jittered point – no outlier hidden or clipped – and a secondary axis converting to a ratio. Median ratios at 24224^{2} : released 41.2×41.2\times , GCV 6.89×6.89\times , ML-II 2.35×2.35\times , L-curve 2.08×2.08\times , Morozov 1.14×1.14\times .
rel. noisereleasedMorozovML-IIGCVL-curveoracle
24224^{2} collocation (the released system’s own grid), n=5n=5 groups
10−410^{-4}0.6240.1240.6240.6240.5340.132
3 ⁣⋅ ⁣10−43\!\cdot\!10^{-4}0.6680.1501.2230.8820.4470.164
10−310^{-3}0.4270.2420.9230.5760.6070.129
3 ⁣⋅ ⁣10−33\!\cdot\!10^{-3}0.8890.1920.2000.1990.2000.207
10−210^{-2}0.5310.1860.1800.1860.1800.186
Appendix
Table 7: Case A run-to-run stability: seed coefficient of variation (CV) of test RMSE, per rule. Convention: within a (grid, noise level) group, the sample standard deviation over the five noise seeds (ddof =1=1 ) divided by their mean; the median rows are medians over groups and the ratio rows divide by Morozov’s. Lower is more reproducible; bold marks the lowest value among the five deployable rules. The oracle column reads the test set: it is a reference, not a competitor. Five seeds make each CV a coarse dispersion estimate, so the claim rests on the ordering and the ratios, not on the third digit. The σ=0\sigma=0 level is excluded from the CV because it measures solver non-determinism rather than noise sensitivity; it is reported separately in Table 8 .
λ2\lambda_{2}1.49 ⁣⋅ ⁣1041.49\!\cdot\!10^{4}5005005050550.50.50.050.050.0050.005
24224^{2}0.1100.0750.0310.0420.0330.0640.036
16216^{2}2.1021.0890.1920.0210.0060.0030.006
 releasedMorozovML-IIGCVL-curveoracle 
Tab. 7 median // own floor5.705.705.165.169.819.817.667.667.027.024.554.55 
Appendix
Table 8: The non-determinism floor. At σ=0\sigma=0 the five “noise seeds” receive bit-identical data and the ALS initialization seed is fixed at 00 , so the five runs are repetitions of one computation; they nevertheless disagree. Seed-CV of test RMSE at each fixed λ2\lambda_{2} , σ=0\sigma=0 , five repetitions. This is a floor under every entry of Table 7 , it is strongly λ2\lambda_{2} -dependent, and it is largest exactly at the released weight, the worst-conditioned point of the grid. The last row normalizes each rule’s median noisy seed-CV at 24224^{2} by the floor at that rule’s own median operating point: the ordering of Table 7 survives, its absolute magnitudes do not. No two of the five seven-point RMSE curves coincide at either grid.
Figure 6: Case A run-to-run stability. Left: per-(grid, level) seed-CV for all six rules at both grids, log yy . Centre: median seed-CV per rule under all four groupings – new 24224^{2} , new 16216^{2} , new pooled ( n=10n=10 , the powered one) and the earlier CPU corpus. Right: the fixed-weight sweep against λ2\lambda_{2} with the σ=0\sigma=0 solver-only floor overlaid, which is the only place the fixed-weight concession and the non-determinism floor can be read together. The σ=0\sigma=0 curves are five re-runs on bit-identical data, so they measure solver non-determinism alone and floor every other curve.
rulemedian ratiorange over the 25 cellsworst disagreement
released1.180[0.373, 12.34][0.373,\,12.34]12.3×12.3\times
ML-II0.998[0.221, 30.38][0.221,\,30.38]30.4×30.4\times
GCV0.988[0.101, 12.34][0.101,\,12.34]12.3×12.3\times
L-curve0.980[0.221, 4.950][0.221,\,4.950]4.9×4.9\times
Morozov0.994[0.796, 1.357]\mathbf{[0.796,\,1.357]}1.36×\mathbf{1.36\times}
oracle0.994[0.772, 1.351][0.772,\,1.351]1.35×1.35\times
Appendix
Table 9: Cross-backend portability. The corpus of this paper (GPU session) and an earlier corpus computed on CPU share 2525 noisy 24224^{2} cells at matched noise seed and level: same forcing, same std(f)=678.4431\mathrm{std}(f)=678.4431 , same η=16.2826\eta=16.2826 at rel. 10−310^{-3} , same λ2\lambda_{2} grid, same 120120 epochs. Only the backend differs. Column two is the per-cell ratio of the two corpora’s test RMSE for that rule, so 1.001.00 would be exact reproduction. This is one of only two tables in the paper that mix corpora, because the corpus is its variable. The data are the same on both machines – the per- λ2\lambda_{2} misfit ratio has median 0.9980.998 – so the spread is the solve, not the draw. Over the 2626 shared cells (the 2525 noisy ones plus σ=0\sigma=0 ) only 6.6%6.6\% of the 182182 matched (cell, λ2\lambda_{2} ) RMSE pairs agree to 1%1\% and only 35.7%35.7\% to 5%5\% ; Morozov and the oracle are the two rules whose selected model nonetheless survives the move.
Figure 7: Left: released // Morozov gain against noise, log–log, per grid, with the per-level min–max band and every one of the 5050 cells drawn unclipped; the earlier CPU corpus is overlaid dashed. Right: Morozov // oracle on a linear axis, whose range 1.01.0 – 1.81.8 spans no decade. The two corpora agree in aggregate and disagree cell by cell; Table 9 quantifies which is which.
 σ=0\sigma=0rel. 10−310^{-3}
cells (seeds) ×\times points3×144=4323\times 144=4323×144=4323\times 144=432
ρoc\rho_{\mathrm{oc}} (source)25.033525.0335 (closed form)23.91423.914 (bordered Occam)
ε^\hat{\varepsilon} (all rows within η\eta )25.049425.049418.95718.957
∣ε^−ρoc∣/ε^|\hat{\varepsilon}-\rho_{\mathrm{oc}}|/\hat{\varepsilon}0.063%0.063\%26.17%26.17\%
raw coverage (no slack)1.00001.0000 ( 0/4320/432 )1.00001.0000 ( 0/4320/432 )
max⁡x(err−cert)\max_{x}(\mathrm{err}-\mathrm{cert})−5.10⋅10−3-5.10\cdot 10^{-3}−8.84⋅10−1-8.84\cdot 10^{-1}
Appendix
Table 10: Case A certificates, per noise level: 3 seeds, 144 evaluation points per seed (432 pooled). Coverage is of the true solution; widths are medians over points, then medians over seeds; brackets are the seed range. m=ρ/ρocm=\rho/\rho_{\mathrm{oc}} . The GP band fails at the same 24 points in all three seeds. ρoc\rho_{\mathrm{oc}} is the boundary-exact Occam radius used for the conditional band, ε^\hat{\varepsilon} the all-rows radius used for the global certificate. At σ=0\sigma=0 the three seeds share one dataset – the generator leaves the data untouched when σ=0\sigma=0 – so they differ only through solver non-determinism and the effective nn there is one dataset; at rel. 10−310^{-3} they are three independent noise draws. Level rel. 10−210^{-2} was planned and is absent: the session ended inside this loop.
 σ=0\sigma=0rel. 10−310^{-3}
mmmedian halfwidth/errtightenmedian halfwidth/errtighten
1.011.012.180⋅10−32.180\cdot 10^{-3}6.396.397.017.011.960⋅10−21.960\cdot 10^{-2}13.713.7146.7146.7
1.051.054.923⋅10−34.923\cdot 10^{-3}14.4214.423.103.102.748⋅10−22.748\cdot 10^{-2}21.521.5104.6104.6
1.11.17.047⋅10−37.047\cdot 10^{-3}20.6420.642.172.173.031⋅10−23.031\cdot 10^{-2}23.123.194.994.9
1.51.51.719⋅10−21.719\cdot 10^{-2}50.3650.360.8890.8894.142⋅10−24.142\cdot 10^{-2}28.128.169.469.4
2.02.02.664⋅10−22.664\cdot 10^{-2}78.0178.010.5740.5744.705⋅10−24.705\cdot 10^{-2}33.533.561.161.1
Appendix
Table 11: The ρ\rho -inflation ladder, ρ=m ρoc\rho=m\,\rho_{\mathrm{oc}} . Each entry is the median over 3 seeds of the within-cell median over 144 points; brackets give the seed range where it is wider than the last digit shown. Coverage of the truth is 1.0001.000 at every one of the 30 (level, seed, rung) cells and no rung was refused. At σ=0\sigma=0 the width column obeys the parameter-free law medw(m)∝m2−1\mathrm{medw}(m)\propto\sqrt{m^{2}-1} exactly (Sec. 6 ). The η=0\eta=0 law is verified to 4.1 ⁣⋅ ⁣10−154.1\!\cdot\!10^{-15} relative on all 1212 consecutive pairs and to 5.4 ⁣⋅ ⁣10−155.4\!\cdot\!10^{-15} on all 43204320 pointwise pair tests.
Figure 8: Case A certificates, seed 1: two slices of the evaluation grid, through the middle ( x2=0.5409x_{2}=0.5409 ) and along the boundary-adjacent ring ( x2=0.05x_{2}=0.05 ), each at σ=0\sigma=0 and at rel. 10−310^{-3} . The delivered global certificate lies on the information radius; the yy -conditional band tracks the actual error; the calibrated GP band is narrower at σ=0\sigma=0 and both wider and invalid at rel. 10−310^{-3} , where it is violated at the circled points. The fixed- μ\mu two-term baseline of an earlier revision is not stored in this run’s per-point arrays and is not drawn.
Figure 9: Attainment as a distribution, not a median. Left: empirical CDF of the pointwise shortfall 1−cert/E⋆1-\mathrm{cert}/E_{\star} per (level, seed), log axis. Right: all 864864 points, with median, IQR and the worst point of each cell marked; nothing is clipped. The ratio never exceeds 11 , its median is 0.9999890.999989 , and its worst value is 0.9972730.997273 .
Figure 10: The ρ\rho -inflation ladder. (a) median conditional half-width against m=ρ/ρocm=\rho/\rho_{\mathrm{oc}} with the exact η=0\eta=0 law overlaid; (b) coverage of the truth, 1.0001.000 at every rung, against the resolution floor of a 144144 -point grid; (c) the conditional-vs-global tightening, which at σ=0\sigma=0 follows (ε^/ρoc)/m2−1(\hat{\varepsilon}/\rho_{\mathrm{oc}})/\sqrt{m^{2}-1} and crosses 11 at m=2m=\sqrt{2} . Six series: two noise levels by three seeds; no rung was refused.
Figure 11: The width // error premium of the conditional band. Left: the median premium per rung, six series. Right: its pointwise distribution at the delivered ρ=1.05ρoc\rho=1.05\rho_{\mathrm{oc}} , whose right tail reaches 3.8 ⁣⋅ ⁣1033.8\!\cdot\!10^{3} where the recovery is accidentally exact – which is why only medians are quoted.
Figure 12: Case A at rel. 10−310^{-3} , seed 1, on the 12×1212\times 12 evaluation grid: the global certificate, the yy -conditional half-width, the GP band, and the GP posterior-mean error with its 2424 failures ringed. The global certificate and the GP band are largest on the boundary-adjacent ring; the conditional band is smallest there. The same 2424 points fail in all three seeds.
datasetNNddsourcetargetdistinct yyRF CV R2R^{2}
diabetes44210sklearn load_diabetestarget2140.4193
concrete10308OpenML 44959strength9380.3428
energy7688OpenML 44960heating_load5870.9651
yacht3086OpenML 42370Residuary.resistance2580.9954
california15008sklearn california_housingtarget11010.7401
Appendix
Table 12: Case B dataset audit ( S0 ), run before any training and hard-failing. Every source is pinned by data_id ; a categorical or ≤20\leq 20 -level target is refused by the loader, the audit additionally requires ≥50\geq 50 distinct values and a RandomForest 5-fold CV R2>0.05R^{2}>0.05 . All five datasets pass, so none is excluded. The previous corpus regressed OpenML data_id=1472 column V8 (Glazing Area Distribution, 6 levels, CV R2=−0.3211R^{2}=-0.3211 ) as energy ; data_id=44960 carries the real heating_load .
datasetregimentrn_{\mathrm{tr}}nten_{\mathrm{te}}ncn_{c}level nc/(nc+1)n_{c}/(n_{c}{+}1)kkachieved (k+1)/(nc+1)(k{+}1)/(n_{c}{+}1)
californiaiid1200300300300/301=0.9967300/301=0.9967285286/301=0.9502286/301=0.9502
californiashift1050450262262/263=0.9962262/263=0.9962249250/263=0.9506250/263=0.9506
concreteiid824206206206/207=0.9952206/207=0.9952196197/207=0.9517197/207=0.9517
concreteshift721309180180/181=0.9945180/181=0.9945171172/181=0.9503172/181=0.9503
diabetesiid353898888/89=0.988888/89=0.98888485/89=0.955185/89=0.9551
diabetesshift3091337777/78=0.987277/78=0.98727475/78=0.961575/78=0.9615
Appendix
Table 13: Case B conformal calibration, recomputed from the splits this run used. nc=max⁡(8,⌊0.25 ntr⌋)n_{c}=\max(8,\lfloor 0.25\,n_{\mathrm{tr}}\rfloor) ; the recorded level is nc/(nc+1)n_{c}/(n_{c}{+}1) and the achieved level is (k+1)/(nc+1)(k{+}1)/(n_{c}{+}1) for k=min⁡(nc−1,⌈0.95(nc+1)⌉−1)k=\min(n_{c}{-}1,\lceil 0.95(n_{c}{+}1)\rceil{-}1) , the order statistic the code takes. The two are not equal, and the difference is the quantile convention, not a bug. The paper’s nc=88n_{c}{=}88 , 88/8988/89 figures are exact for diabetes i.i.d.; the shift regime trains on 70%70\% , giving nc=77n_{c}{=}77 and 77/7877/78 .
armnncoveragemedian half-widthinterval scorepenalty share
  (mean)median [IQR]median [IQR]of IS (median)
i.i.d.
DAK (released)190.8610.68 [0.44, 0.86]2.49 [1.83, 6.29]0.539
DAK (KL repaired)190.8730.68 [0.45, 0.90]2.59 [1.62, 5.40]0.465
split-CP190.9640.91 [0.61, 1.71]2.58 [1.80, 3.74]0.231
norm. split-CP (temp.)190.9610.90 [0.62, 1.77]2.60 [1.82, 3.77]0.201
Appendix
Table 14: Case B, v5 corrected corpus (39 cells: 5 datasets ×\times {i.i.d., shift} ×\times 2 seeds ×\times noise grid, plus one shiftcol anchor cell). Coverage is a mean over cells (bounded quantity); width and interval score are median [IQR] over cells, and the width column is the within-cell median half-width, not the mean — the mean is reported separately in Table 16 because it is the statistic the remaining tail lives in. nn is the number of cells the arm delivered on: the OR arms refuse on two cells (empty consistent set) and or2 was run on diabetes only. Targets are standardized, so a half-width of 11 is one training standard deviation.
Figure 13: Case B width–coverage Pareto over all 3838 i.i.d. and shift cells (the OR arms deliver on 3737 of them; each panel prints its own counts). Split-CP and normalized split-CP sit at the smallest valid widths in-distribution; the constant-predictor band and the OR head both over-cover at larger width; the miscalibrated DAK arms cluster bottom-left. The pure-interval ablation is now on-scale (coverage 0.8520.852 ), unlike in an earlier revision.
Figure 14: The Winkler interval score is never reported without its two parts, IS=2w+(2/α)⋅miss\mathrm{IS}=2w+(2/\alpha)\cdot\text{miss} . Left and centre: the median over cells of the width part and of the miss penalty, stacked per arm, i.i.d. and shift, with the penalty’s percentage of the score printed above each bar. Right: the penalty share of every individual cell, all nine arms, circles i.i.d. and squares shift, with the per-arm median as a bar. The OR head’s score is pure width – its penalty share is 0.0000.000 in both regimes – and the per-arm medians drawn in the right panel are the last column of Table 14 .
 i.i.d. ( n=19n{=}19 )shift ( n=18n{=}18 )
wintw_{\mathrm{int}} share of the band0.338 [0.281, 0.542]0.686 [0.543, 0.798]
waddw_{\mathrm{add}} share of the band0.412 [0.180, 0.447]0.117 [0.024, 0.209]
wobsw_{\mathrm{obs}} share of the band0.292 [0.266, 0.352]0.182 [0.092, 0.213]
wintw_{\mathrm{int}} (absolute)0.828 [0.604, 0.960]1.898 [0.981, 5.747]
waddw_{\mathrm{add}} (absolute)0.961 [0.291, 1.558]0.836 [0.230, 1.630]
wobsw_{\mathrm{obs}} (absolute)0.662 [0.435, 0.922]0.620 [0.417, 0.674]
Appendix
Table 15: Case B width budget of the OR head, and what each component buys. wintw_{\mathrm{int}} is the tight OR interval, wadd=qw_{\mathrm{add}}=q the conformal floor (constant in a cell), wobs=1.96σ^w_{\mathrm{obs}}=1.96\hat{\sigma} the noise allowance. Paired differences are median [bootstrap 95% CI of the median], Wilcoxon pp , on the cells where all three variants delivered; the attainable pp -floor is 21−n2^{1-n} ( 3.8×10−63.8\times 10^{-6} at n=19n{=}19 , 7.6×10−67.6\times 10^{-6} at n=18n{=}18 ). In the lower block “ ww buys” is the paired change from dropping that component: Δ\Delta width is the within-cell median half-width and Δ\Delta IS the interval score.
Figure 15: The OR band’s width budget, and what each component buys. Left: the three OR variants in (median half-width, coverage) space, with one arrow per component – adding the noise allowance wobsw_{\mathrm{obs}} , then the conformal floor waddw_{\mathrm{add}} – drawn solid for i.i.d. and dashed for shift, against the nominal 0.950.95 . Centre: the absolute budget wint+wadd+wobsw_{\mathrm{int}}+w_{\mathrm{add}}+w_{\mathrm{obs}} stacked for every one of the 3737 delivered cells ( 22 of the 3939 refused), sorted within regime. Right: the same budget as shares, median over cells. The OR interval is a third of the band in-distribution and two-thirds under shift.
Figure 16: Case B coverage per arm and per dataset, all three regimes drawn (circle i.i.d., square shift, cross shiftcol ) with a separate nominal-level guide for each; every cell is shown, and a cross at the foot marks the two cells on which the OR arm refused. Coverage is the one column the OR head wins on all five datasets under shift ; Table 2 shows what it costs.
Figure 17: The referee-proof baseline. Paired differences of the constant-predictor conformal band against the OR head, its no-floor ablation and split-CP, on interval score and on median half-width, in both regimes; every cell is drawn and coloured by dataset, with the median difference and its bootstrap 95%95\% CI. A feature-free constant band beats the delivered OR band on interval score under shift ( 12/1812/18 , p=0.038p=0.038 ) and is indistinguishable from it in-distribution.
cellntestn_{\mathrm{test}}n >> capmedian halfmean halfmax halfnsmax⁡\mathrm{ns}_{\max}κ⋆\kappa_{\star}
california/shift/0/0.045080.62139.8618960.50040
diabetes/shift/1/0.0133131.5225.48300.37040
diabetes/shift/1/0.1133101.0724.17830.29740
california/shift/1/0.0450361.2813.23910.19440
california/shift/0/0.25450130.566.15160.33740
concrete/shift/0/0.2530980.624.72450.30840
Appendix
Table 16: Case B blow-up census under the corrected configuration, i.e. with FEATNORM=drop and OR_DELIVERY=fit and OR_ETA_INFLATE=refuse on the exact η=0\eta{=}0 slice. A blow-up is a within-cell median half-width above 2020 on a standardized target. The census is 0/370/37 ; what remains is a per- point tail in 13/3713/37 cells, listed here. n >> cap counts test points whose OR interval exceeds 20 sd(yfit)20\,\mathrm{sd}(y_{\mathrm{fit}}) ; nsmax⁡\mathrm{ns}_{\max} is the largest null-space share of a test functional in the cell.
  refusedmedian [IQR] over the delivered cellsblow-upnsmax⁡ns_{\max}median
featnormdelivery/30median wwmean wwmax ww(mean)>0.999>0.999IS
clamp 10−610^{-6} (shipped)all rows180.6412661.17 ⁣⋅ ⁣1041.17\!\cdot\!10^{4}0.5815/30533
clamp 10−610^{-6}fit split30.86387.38.06 ⁣⋅ ⁣1038.06\!\cdot\!10^{3}0.5614/30903
drop deadall rows190.5880.8412.530.090/302.91
drop dead (v5)fit split40.8181.926.20.120/306.85
Appendix
Table 17: Case B / S5: the 2x2 width-defect ablation. Thirty shift cells (4 datasets ×\times 3 seeds ×\times 2–4 noise levels), four head variants per cell built on one trained model, so the comparison isolates the head. featnorm ∈\in {clamp 10−610^{-6} as shipped, drop dead columns}; delivery ∈\in {all rows as shipped, fit split only}. A refused delivery has an empty consistent set and is not a width measurement: refusals are reported as a rate and excluded from the width quantiles. Half-widths are wintw_{\mathrm{int}} on a standardized target; “blow-up” is the notebook’s own criterion at threshold 2020 .
scaleeffectratio95% CI of the medianppnnfloor
median wintw_{\mathrm{int}}FEATNORM, fit split1.021.02[1.01, 1.04][1.01,\,1.04]2.5 ⁣⋅ ⁣10−52.5\!\cdot\!10^{-5}263 ⁣⋅ ⁣10−83\!\cdot\!10^{-8}
 FEATNORM, all rows1.021.02[1, 1.09][1,\,1.09]0.0420.042119.8 ⁣⋅ ⁣10−49.8\!\cdot\!10^{-4}
 DELIVERY, drop dead0.8170.817[0.592, 0.978][0.592,\,0.978]9.8 ⁣⋅ ⁣10−49.8\!\cdot\!10^{-4}119.8 ⁣⋅ ⁣10−49.8\!\cdot\!10^{-4}
 DELIVERY, clamp0.8930.893[0.634, 0.978][0.634,\,0.978]0.0270.027124.9 ⁣⋅ ⁣10−44.9\!\cdot\!10^{-4}
 INTERACTION11[1, 1.02][1,\,1.02]0.320.32119.8 ⁣⋅ ⁣10−49.8\!\cdot\!10^{-4}
mean wintw_{\mathrm{int}}FEATNORM, fit split235235[1.13, 2442][1.13,\,2442]9.8 ⁣⋅ ⁣10−79.8\!\cdot\!10^{-7}263 ⁣⋅ ⁣10−83\!\cdot\!10^{-8}
Appendix
Table 18: Case B / S5: attribution of the width defect. Each row is a paired comparison on log⁡10\log_{10} of the named scale, over the cells where both variants delivered; the ratio is 10median difference10^{\text{median difference}} with the 95% bootstrap CI of the median, the Wilcoxon signed-rank pp , the number of paired cells, and the smallest pp attainable at that nn . featnorm rows are clamp // drop at the delivery named after the comma; delivery rows are all rows // fit split at the feature rule named after the comma; interaction is (clamp all // fit) // (drop all // fit). The clamp defect does not live in the median half-width; it lives in the mean, the maximum and the interval score. The delivery axis is a factor ≈1{\approx}1 on every width scale: its cost is validity, not width.
Figure 18: The 2×22\times 2 width-defect ablation on 3030 shift cells, four head variants per cell built on one trained model. The feature-scale clamp is the width defect and it acts on the tail: it multiplies the within-cell mean half-width by 235235 and the maximum by 26812681 while moving the median by 1.021.02 . Delivering on all training rows is a validity defect, not a width defect: it moves the mean half-width by a factor 0.950.95 , the maximum by 0.990.99 and the within-cell median by 0.820.82 – never by an order of magnitude on any scale, against the clamp’s three – and instead empties the consistent set, taking the refusal rate from 33 – 44 of 3030 to 1818 – 1919 of 3030 .
armcoverage≥\geq nom.mean half-widthinterval score
region: design gap ∣x∣<1|x|<1
DAK 1.96σ^(x)1.96\hat{\sigma}(x)0.4800.480 [0.395, 0.588]0/100.5960.596 [0.589, 0.633]7.047.04 [4.23, 18.6]
split-CP (constant)0.4730.473 [0.436, 0.689]2/100.7720.772 [0.578, 0.951]8.038.03 [3.51, 12.9]
normalized split-CP0.4730.473 [0.426, 0.689]2/100.7720.772 [0.634, 0.967]7.457.45 [3.46, 12.5]
constant-predictor split-CP0.6350.635 [0.625, 0.662]0/101.8091.809 [1.762, 1.844]7.297.29 [6.31, 7.62]
OR band or11.0001.000 [1.000, 1.000]10/102.8042.804 [1.786, 3.747]5.615.61 [3.57, 7.49]
Appendix
Table 19: Case B / S6: the 1D design-gap task at ten seeds. Median [IQR] over the ten seeds; every arm, every region. Nominal split-conformal level 13/14=0.928613/14=0.9286 , achieved on 10/10 seeds. The OR arms were recorded on 10/10 seeds (no refusals); or1_nf is omitted because the conformal add-on waddw_{\mathrm{add}} is exactly zero on every seed, which makes it identical to or1 . “ ≥\geq nom.” counts seeds whose coverage of the truth reaches the nominal level. Interval score at α=0.05\alpha=0.05 against the noiseless truth.
quantityregionsingle seedten-seed median [IQR]min–maxverdict
split-CP coveragegap0.580.580.4730.473 [0.436, 0.689]0.243–1.000in IQR
split-CP coverageind0.700.700.6200.620 [0.497, 0.765]0.293–1.000in IQR
split-CP coverageext0.430.430.4540.454 [0.411, 0.497]0.395–0.500in IQR
norm. split-CP coveragegap0.610.610.4730.473 [0.426, 0.689]0.270–1.000in IQR
norm. split-CP coverageind0.720.720.6430.643 [0.517, 0.753]0.313–1.000in IQR
norm. split-CP coverageext0.420.420.4670.467 [0.424, 0.487]0.408–0.539in range
Appendix
Table 20: Case B / S6: which single-seed number survives ten seeds. Left, the single-seed value from the earlier corpus; right, the ten-seed distribution of the same quantity recomputed from the corrected v5 corpus. “in IQR” means the single-seed value lies inside the interquartile range of the ten seeds; “in range” means it lies inside the observed min–max but outside the IQR; “outside” means it lies outside the observed range altogether. This is the second of the paper’s two deliberately cross-corpus tables: the left column is one run of the earlier corpus and the right column is this run.
Figure 19: Case B gap task by region over ten seeds: coverage of the truth and interval score for every arm in the design gap, in-distribution and in extrapolation. Every seed is plotted. The OR band is the only arm that reaches the nominal level in extrapolation on any seed; in the gap split-CP and normalized split-CP reach it on 22 of 1010 seeds each, drawn at coverage 1.0001.000 in the top-left panel. The OR band dominates on interval score in-distribution and in extrapolation while tying in the gap.
 nnEIUCBOR-LCB ( κ=1\kappa{=}1 )2×2{\times} floor5×5{\times} floor
Branin70.14 (0.19)0.13 (3.88)0.20 (0.34)0.29 (0.58)0.26 (0.89)
Hartmann-670.70 (1.65)0.96 (2.05)0.96 (2.49)0.96 (2.49)0.96 (2.49)
Griewank78.31 (20.79)9.71 (25.49)12.40 (22.71)10.98 (19.98)9.92 (19.98)
Ackley-5D7/66.59 (8.95)5.58 (9.60)7.92 (9.60)7.92 (9.60)7.34 (9.60)
Levy-10D64.47 (9.17)4.47 (9.17)4.47 (9.17)4.47 (9.17)4.47 (9.17)
Appendix
Table 21: Case C: median (worst) final simple regret at the same 2323 -evaluation budget ( ninit=5n_{\mathrm{init}}{=}5 then 1818 BO steps), from one GPU session ( botorch 0.18.1 , Q=3Q{=}3 ). Seed counts are uneven and are given in the nn column: the Ackley κ\kappa arms and all Levy arms have 66 seeds, everything else has 77 ; every paired test pairs only on shared seeds. All 8080 (benchmark, arm, seed) trajectories this corpus shares with the earlier CPU corpus are bitwise identical to it, so the added seeds extend rather than overturn the earlier entries. or_full and or_ei were not in this run; their 55 -seed values are unchanged and reported in App. C .
Benchmarkarmnnmedian diff.bootstrap 95%95\% CI of the medianbetter/worse/tiedWilcoxon ppfloor
Levy-10DUCB66+0.0000+0.0000[−0.0606, +0.0000][-0.0606,\,+0.0000]1/0/51/0/5110.031250.03125
Levy-10DOR-LCB66+0.0000+0.0000[−0.0606, +0.0000][-0.0606,\,+0.0000]1/0/51/0/5110.031250.03125
Levy-10D2×2{\times} floor66+0.0000+0.0000[−0.0606, +0.0000][-0.0606,\,+0.0000]1/0/51/0/5110.031250.03125
Levy-10D5×5{\times} floor66+0.0000+0.0000[−0.0606, +0.0000][-0.0606,\,+0.0000]1/0/51/0/5110.031250.03125
Hartmann-6UCB77+0.2105+0.2105[+0.0000, +0.3871][+0.0000,\,+0.3871]0/5/20/5/20.06250.06250.015620.01562
Hartmann-6OR-LCB77+0.2105+0.2105[+0.0000, +0.3871][+0.0000,\,+0.3871]0/5/20/5/20.06250.06250.015620.01562
Appendix
Table 22: Case C, final simple regret paired against EI. Seed counts are uneven, so each row pairs only on the seeds both arms have. “Better/worse/tied” counts seeds on which the row arm ends below/above/exactly at EI; an exact tie is a bitwise-identical trajectory. “Floor” is the smallest two-sided Wilcoxon pp attainable at that nn ( 21−n2^{1-n} ): at the 55 seeds of the earlier revision it was 0.06250.0625 , so no per-benchmark test could reach 0.050.05 by construction. The pooled rows test the per-benchmark normalized paired log⁡10\log_{10} ratio against zero over all 3333 complete blocks.
Benchmarkarmnnmedian diff.bootstrap 95%95\% CI of the medianbetter/worse/tiedWilcoxon ppfloor
Levy-10DEI66+0.0000+0.0000[+0.0000, +0.0606][+0.0000,\,+0.0606]0/1/50/1/5110.031250.03125
Levy-10DUCB66+0.0000+0.0000[+0.0000, +0.0000][+0.0000,\,+0.0000]0/0/60/0/6110.031250.03125
Levy-10D2×2{\times} floor66+0.0000+0.0000[+0.0000, +0.0000][+0.0000,\,+0.0000]0/0/60/0/6110.031250.03125
Levy-10D5×5{\times} floor66+0.0000+0.0000[+0.0000, +0.0000][+0.0000,\,+0.0000]0/0/60/0/6110.031250.03125
Hartmann-6EI77−0.2105-0.2105[−0.3871, +0.0000][-0.3871,\,+0.0000]5/0/25/0/20.06250.06250.015620.01562
Hartmann-6UCB77+0.0000+0.0000[+0.0000, +0.0000][+0.0000,\,+0.0000]1/0/61/0/6110.015620.01562
Appendix
Table 23: Case C, final simple regret paired against OR-LCB ( κ=1\kappa{=}1 ), same conventions as Tab. 22 . The tie counts are the κ\kappa -inertness made visible: 22/3322/33 blocks tie exactly between κ=1\kappa{=}1 and κ=2\kappa{=}2 , 17/3317/33 between κ=1\kappa{=}1 and κ=5\kappa{=}5 , and 20/3320/33 between κ=2\kappa{=}2 and κ=5\kappa{=}5 .
Benchmarkarmnnmedian diff.bootstrap 95%95\% CI of the medianbetter/worse/tiedWilcoxon ppfloor
Levy-10DUCB66+0.0000+0.0000[+0.0000, +0.5668][+0.0000,\,+0.5668]0/1/50/1/5110.031250.03125
Levy-10DOR-LCB66+0.0000+0.0000[+0.0000, +0.5668][+0.0000,\,+0.5668]0/1/50/1/5110.031250.03125
Levy-10D2×2{\times} floor66+0.0000+0.0000[+0.0000, +0.5668][+0.0000,\,+0.5668]0/1/50/1/5110.031250.03125
Levy-10D5×5{\times} floor66+0.0000+0.0000[+0.0000, +0.5668][+0.0000,\,+0.5668]0/1/50/1/5110.031250.03125
Hartmann-6UCB77+0.0935+0.0935[+0.0000, +0.2253][+0.0000,\,+0.2253]1/5/11/5/10.06250.06250.015620.01562
Hartmann-6OR-LCB77+0.0935+0.0935[+0.0000, +0.2253][+0.0000,\,+0.2253]1/5/11/5/10.06250.06250.015620.01562
Appendix
Table 24: Case C, AUC (mean regret over the 1919 -point trajectory) paired against EI; conventions as in Tab. 22 . AUC is reported as a second ordering because final regret ignores the path; the two orderings disagree on three of five benchmarks.
Figure 20: Case C median regret per benchmark, panels ordered by radius dispersion at the final acquisition – the two saturated benchmarks sit below the certifier’s μ\mu -grid floor, so their order between themselves is arbitrary (Rem. A.4 ); all arms share the initial design. Line widths are chosen so that a bitwise-identical overlay is visible: the thick pale halo is κ=1\kappa{=}1 , and where the κ=2\kappa{=}2 (dashed) and κ=5\kappa{=}5 (dotted) arms sit inside it the trajectories agree element for element. Seed counts are printed in each panel.
Figure 21: Case C per-seed final regret; every seed is plotted, nothing is clipped, the black bar is the median. Each grey polyline is one seed followed across the five arms, so a horizontal segment is an exact tie in final regret; on this corpus every such tie is also a bitwise-identical trajectory (Table 23 ), which the plot itself cannot show. The ties fill the κ\kappa columns on Hartmann-6 and Levy-10D and vanish on Branin.
  action-inert seedsfullescapeUCB
Benchmarkosc(c^)/mean(c^)\mathrm{osc}(\hat{c})/\mathrm{mean}(\hat{c})1↔21{\leftrightarrow}22↔52{\leftrightarrow}51↔51{\leftrightarrow}5ladderstep== OR-LCB
Levy-10Dbelow the μ\mu -grid floor6/66/66/66/66/66/66/66/6never6/66/6
Hartmann-6below the μ\mu -grid floor7/77/76/76/76/76/76/76/7995/75/7
Ackley-5D0.00660.00666/66/63/63/63/63/63/63/6662/62/6
Griewank-5D0.01100.01101/71/73/73/70/70/70/70/7552/72/7
Branin-2D0.32630.32630/70/70/70/70/70/70/70/7000/70/7
Appendix
Table 25: κ\kappa -inertness, measured at the action level: a κ\kappa pair is inert on a seed iff the two arms select the same candidate at every one of the 1818 BO iterations. We measure the action path and not the regret trajectory because the regret trajectory is a running minimum and can be bitwise identical while the arms acquire different points. The independent unit is the seed; the three κ\kappa pairs within a seed are not independent, since identity is an equivalence relation, so we do not pool them, and Clopper–Pearson 95%95\% intervals depend only on k/nk/n ( 7/7 [0.590,1]7/7\,[0.590,1] to 0/7 [0,0.410]0/7\,[0,0.410] ). The dispersion column is the median over BO steps of osc(c^)/mean(c^)\mathrm{osc}(\hat{c})/\mathrm{mean}(\hat{c}) ; on the top two rows the radius minimizer is pinned to the lower end of the certifier’s μ\mu grid and the recorded value is an O(μlo)O(\mu_{\mathrm{lo}}) artifact of that grid rather than a property of the objective (Rem. A.4 ), which is why it is written as a bound. The escape column is the first BO iteration at which osc(c^)/mean(c^)\mathrm{osc}(\hat{c})/\mathrm{mean}(\hat{c}) exceeds 10−610^{-6} , and the first κ\kappa divergence always follows it.
 one step ( n=9,018n{=}9{,}018 records)whole trajectory ( n=99n{=}99 pairs)
 argmin coincidedargmin movedbitwise identicaldiffer
criterion fires5,9365{,}9360\mathbf{0}35350\mathbf{0}
criterion silent1,0761{,}0762,0062{,}00623234141
Appendix
Table 26: Prop. 4.5 tested directly. Its criterion ∣Δκ∣ osc(c)<Δκ|\Delta\kappa|\,\mathrm{osc}(c)<\Delta_{\kappa} was evaluated and compared with what the acquisition actually did, at every BO iteration of every arm and seed (left) and over whole trajectories (right). The proposition is sufficient , so the boldface cell – criterion fires, argmin moves – is the only cell that could refute it; it is empty in both tests. The criterion is conservative rather than tight: it fires on 65.8%65.8\% of steps and covers 84.7%84.7\% of the steps on which invariance actually occurred.
Figure 22: Prop. 4.5 tested against what the acquisition actually did. (a) The one-step confusion table over every BO iteration of every arm and seed; the outlined cell is the only one that could refute a sufficient condition and it is empty. (b) Observed argmin-invariance against the margin ratio r=∣Δκ∣ osc(c)/Δκr=|\Delta\kappa|\,\mathrm{osc}(c)/\Delta_{\kappa} : exactly 1.0001.000 in every bin below the threshold and still 0.800.80 – 0.830.83 just above it, which is how conservative the bound is. (c) Every benchmark-by- κ\kappa -pair cell lies on or above the diagonal: the criterion never over-claims, only under-claims. (d) The same test at whole-trajectory resolution.
More in this topic

Gaussian Process Regression

Gaussian process regression uses kernel-defined distributions over functions to make predictions and quantify uncertainty from observed data.

See all 110 papers

Explore similar work

CardsList
Aug 9, 2026

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.

Ibne Farabi Shihab, Adria Binte Habib

Department of Computer Science, Iowa State University, USA · Department of Computer Science & Engineering, Independent University of Bangladesh, Bangladesh

Minimax Estimation
AskPDF
Jul 22, 2026

Adaptive Bayesian Online Learning via Expert Aggregation

Bayesian online learning promises uncertainty-aware prediction on data streams, but its performance hinges on inferential choices, including learning rates, prior distributions and variational families, which are usually fixed before seeing the stream. We address this by treating Bayesian update rules as experts and aggregating the Bayesian experts according to sequential predictive losses. We prove that the resulting aggregate competes with the best expert in hindsight at an aggregation cost determined by how each expert's per-round performance is evaluated. We instantiate the framework in online conformal inference and Gaussian process regression. The conformal inference application yields a smoothed Bayesian counterpart of adaptive conformal inference with long-run randomized coverage, while the Gaussian process application gives an oracle inequality in cumulative predictive Kullback-Leibler risk and adaptation to unknown Hölder smoothness up to logarithmic factors. Experiments show that the aggregate tracks strong experts without oracle expert selection.

Jungbin Jun, Ilsang Ohn

Department of Statistics Inha University Incheon, 22212, South Korea

Bayesian InferenceAdaptive Conformal Inference
AskPDF
Oct 12, 2026

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

Existing cumulative regret guarantees for Bayesian optimization (BO) do not necessarily characterize the quality of the algorithm's final output. This gap is critical under noisy evaluations, where the goal is to return a single high-quality recommendation. To address it, we introduce efficient exploration strategies that can be incorporated into any BO procedure by occasionally replacing the acquisition query with an exploration query. To validate this approach, we bound the Gaussian process posterior standard deviation over the search space via the fill distance of the queries, which measures the largest region left unexplored. We then use this result to derive upper bounds on the inference regret, i.e., the gap between the global optimum and the function value at the algorithm's returned point. Empirically, these exploration strategies improve the final recommendations of existing BO algorithms on synthetic benchmarks, hyperparameter optimization, and a control task.

Hwanwoo Kim, Jungwoo Hong, Kyungjae Lee

Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University

Gaussian Process BanditsBayesian OptimizationRegret MinimizationExploration-Exploitation TradeoffMulti-Armed Bandits
AskPDF