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

Gordei Verbii

Optimal Recovery	Bayesian learning
model ball $\lVert u\rVert\leq\varepsilon$ ; noise ball $\lVert e\rVert\leq\eta$	prior scale; Gaussian likelihood
regularization weight / nugget $\nu$	prior-to-noise ratio $\sigma^{2}/s^{2}$
power function (exact data)	GP posterior sd
radius of information $E_{\star}(x)$ , Eq. ( 2 )	nugget-optimized posterior variance (new, Thm. 4.1 )
conditional Chebyshev interval $I_{\varphi_{x}}(y)$	total-ambiguity robust-Bayes credible interval (Thm. 4.2 )
Occam radius $\rho_{\mathrm{oc}}$ ; conformal inflation $\kappa_{\star}\rho_{\mathrm{oc}}$	degenerate / repaired data-driven prior scale (Lem. 4.3 , Thm. 4.4 )

Appendix

Table 3: Working dictionary.

Known	Here
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 $V_{1/\mu}=\mathrm{pf}^{2}+\mathrm{wn}^{2}/\mu$ and the 6-line AM–GM attainment proof with the balance equation $\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 $2$ -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 regime	Recommended tool	Evidence
no exchangeable calibration data	OR ball $+$ Morozov	Sec. 6 , Tab. 1 , 7 , 9
exchangeable, in-distribution	split-CP (constant or normalized); the OR head is valid but wider and scores worse	Tab. 14 , Fig. 13
covariate shift, learnable target (RF CV $R^{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 energy	Tab. 2 , 19 , Fig. 1
covariate shift, poorly learnable target	a wider conformal constant ; the OR band’s per-point tail costs more than its coverage buys	Tab. 2 , Fig. 17
exploration bonus	floor for validity; shape, not scale – and check Prop. 4.5 before scaling	Prop. 4.5 , Fig. 2 , Tab. 25 , 26
any of the above, before trusting a dispersion number	measure the run-to-run floor first	Tab. 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. noise	released	Morozov	ML-II	GCV	L-curve	oracle	gain	M/o
0	$2.8\!\cdot\!10^{-2}$	$2.8\!\cdot\!10^{-2}$	$2.8\!\cdot\!10^{-2}$	$2.8\!\cdot\!10^{-2}$	$1.7\!\cdot\!10^{-2}$	$1.6\!\cdot\!10^{-2}$	$1.0\times$ [1,97]	1.71
$10^{-4}$	$1.8\!\cdot\!10^{-1}$	$1.6\!\cdot\!10^{-2}$	$1.6\!\cdot\!10^{-1}$	$1.6\!\cdot\!10^{-1}$	$2.0\!\cdot\!10^{-2}$	$1.6\!\cdot\!10^{-2}$	$11\times$ [7,18]	1.00
$3\!\cdot\!10^{-4}$	$1.1\!\cdot\!10^{-1}$	$1.7\!\cdot\!10^{-2}$	$1.1\!\cdot\!10^{-1}$	$1.1\!\cdot\!10^{-1}$	$3.7\!\cdot\!10^{-2}$	$1.6\!\cdot\!10^{-2}$	$6.7\times$ [5,14]	1.04
$10^{-3}$	$4.1\!\cdot\!10^{-1}$	$1.7\!\cdot\!10^{-2}$	$2.6\!\cdot\!10^{-1}$	$2.6\!\cdot\!10^{-1}$	$1.7\!\cdot\!10^{-2}$	$1.6\!\cdot\!10^{-2}$	$23\times$ [16,70]	1.05
$3\!\cdot\!10^{-3}$	$5.6\!\cdot\!10^{-1}$	$1.8\!\cdot\!10^{-2}$	$4.2\!\cdot\!10^{-2}$	$5.6\!\cdot\!10^{-1}$	$4.2\!\cdot\!10^{-2}$	$1.7\!\cdot\!10^{-2}$	$31\times$ [18,51]	1.03
$10^{-2}$	$1.0$	$2.2\!\cdot\!10^{-2}$	$4.5\!\cdot\!10^{-2}$	$1.0$	$1.3\!\cdot\!10^{-1}$	$2.2\!\cdot\!10^{-2}$	$42\times$ [37,57]	1.00

Appendix

Table 6: Case A at

16^{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.055

) and the whole

\lambda_{2}\leq 5

half of the grid is nearly flat, which is why every ratio against Morozov is larger here. The

\sigma=0

row is the median of five re-runs; at

16^{2}

the released weight diverges on one of them (RMSE

2.07

), which is why the noise-free gain is not

1

.

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

\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/25

noisy cells at

24^{2}

(exactly one step in

14

, two in

4

), matches it in

7/25

, and is never above it.

Figure 5:

\log_{10}(\text{rule}/\text{oracle})

per grid, with every one of the

25

cells per rule drawn as a jittered point – no outlier hidden or clipped – and a secondary axis converting to a ratio. Median ratios at

24^{2}

: released

41.2\times

, GCV

6.89\times

, ML-II

2.35\times

, L-curve

2.08\times

, Morozov

1.14\times

.

$24^{2}$ collocation (the released system’s own grid), $n=5$ groups
rel. noise	released	Morozov	ML-II	GCV	L-curve	oracle
$10^{-4}$	0.624	0.124	0.624	0.624	0.534	0.132
$3\!\cdot\!10^{-4}$	0.668	0.150	1.223	0.882	0.447	0.164
$10^{-3}$	0.427	0.242	0.923	0.576	0.607	0.129
$3\!\cdot\!10^{-3}$	0.889	0.192	0.200	0.199	0.200	0.207
$10^{-2}$	0.531	0.186	0.180	0.186	0.180	0.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

) 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

\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 .

$\lambda_{2}$	$1.49\!\cdot\!10^{4}$	$500$	$50$	$5$	$0.5$	$0.05$	$0.005$
$24^{2}$	0.110	0.075	0.031	0.042	0.033	0.064	0.036
$16^{2}$	2.102	1.089	0.192	0.021	0.006	0.003	0.006
	released	Morozov	ML-II	GCV	L-curve	oracle
Tab. 7 median $/$ own floor	$5.70$	$5.16$	$9.81$	$7.66$	$7.02$	$4.55$

Appendix

Table 8: The non-determinism floor. At

\sigma=0

the five “noise seeds” receive bit-identical data and the ALS initialization seed is fixed at

0

, so the five runs are repetitions of one computation; they nevertheless disagree. Seed-CV of test RMSE at each fixed

\lambda_{2}

,

\sigma=0

, five repetitions. This is a floor under every entry of Table 7 , it is strongly

\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

24^{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

y

. Centre: median seed-CV per rule under all four groupings – new

24^{2}

, new

16^{2}

, new pooled (

n=10

, the powered one) and the earlier CPU corpus. Right: the fixed-weight sweep against

\lambda_{2}

with the

\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

\sigma=0

curves are five re-runs on bit-identical data, so they measure solver non-determinism alone and floor every other curve.

rule	median ratio	range over the 25 cells	worst disagreement
released	1.180	$[0.373,\,12.34]$	$12.3\times$
ML-II	0.998	$[0.221,\,30.38]$	$30.4\times$
GCV	0.988	$[0.101,\,12.34]$	$12.3\times$
L-curve	0.980	$[0.221,\,4.950]$	$4.9\times$
Morozov	0.994	$\mathbf{[0.796,\,1.357]}$	$\mathbf{1.36\times}$
oracle	0.994	$[0.772,\,1.351]$	$1.35\times$

Appendix

Table 9: Cross-backend portability. The corpus of this paper (GPU session) and an earlier corpus computed on CPU share

25

noisy

24^{2}

cells at matched noise seed and level: same forcing, same

\mathrm{std}(f)=678.4431

, same

\eta=16.2826

at rel.

10^{-3}

, same

\lambda_{2}

grid, same

120

epochs. Only the backend differs. Column two is the per-cell ratio of the two corpora’s test RMSE for that rule, so

1.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-

\lambda_{2}

misfit ratio has median

0.998

– so the spread is the solve, not the draw. Over the

26

shared cells (the

25

noisy ones plus

\sigma=0

) only

6.6\%

of the

182

matched (cell,

\lambda_{2}

) RMSE pairs agree to

1\%

and only

35.7\%

to

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

50

cells drawn unclipped; the earlier CPU corpus is overlaid dashed. Right: Morozov

/

oracle on a linear axis, whose range

1.0

–

1.8

spans no decade. The two corpora agree in aggregate and disagree cell by cell; Table 9 quantifies which is which.

	$\sigma=0$	rel. $10^{-3}$
cells (seeds) $\times$ points	$3\times 144=432$	$3\times 144=432$
$\rho_{\mathrm{oc}}$ (source)	$25.0335$ (closed form)	$23.914$ (bordered Occam)
$\hat{\varepsilon}$ (all rows within $\eta$ )	$25.0494$	$18.957$
$\|\hat{\varepsilon}-\rho_{\mathrm{oc}}\|/\hat{\varepsilon}$	$0.063\%$	$26.17\%$
raw coverage (no slack)	$1.0000$ ( $0/432$ )	$1.0000$ ( $0/432$ )
$\max_{x}(\mathrm{err}-\mathrm{cert})$	$-5.10\cdot 10^{-3}$	$-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=\rho/\rho_{\mathrm{oc}}

. The GP band fails at the same 24 points in all three seeds.

\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

\sigma=0

the three seeds share one dataset – the generator leaves the data untouched when

\sigma=0

– so they differ only through solver non-determinism and the effective

n

there is one dataset; at rel.

10^{-3}

they are three independent noise draws. Level rel.

10^{-2}

was planned and is absent: the session ended inside this loop.

	$\sigma=0$			rel. $10^{-3}$
$m$	median half	width/err	tighten	median half	width/err	tighten
$1.01$	$2.180\cdot 10^{-3}$	$6.39$	$7.01$	$1.960\cdot 10^{-2}$	$13.7$	$146.7$
$1.05$	$4.923\cdot 10^{-3}$	$14.42$	$3.10$	$2.748\cdot 10^{-2}$	$21.5$	$104.6$
$1.1$	$7.047\cdot 10^{-3}$	$20.64$	$2.17$	$3.031\cdot 10^{-2}$	$23.1$	$94.9$
$1.5$	$1.719\cdot 10^{-2}$	$50.36$	$0.889$	$4.142\cdot 10^{-2}$	$28.1$	$69.4$
$2.0$	$2.664\cdot 10^{-2}$	$78.01$	$0.574$	$4.705\cdot 10^{-2}$	$33.5$	$61.1$

Appendix

Table 11: The

\rho

-inflation ladder,

\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.000

at every one of the 30 (level, seed, rung) cells and no rung was refused. At

\sigma=0

the width column obeys the parameter-free law

\mathrm{medw}(m)\propto\sqrt{m^{2}-1}

exactly (Sec. 6 ). The

\eta=0

law is verified to

4.1\!\cdot\!10^{-15}

relative on all

12

consecutive pairs and to

5.4\!\cdot\!10^{-15}

on all

4320

pointwise pair tests.

Figure 8: Case A certificates, seed 1: two slices of the evaluation grid, through the middle (

x_{2}=0.5409

) and along the boundary-adjacent ring (

x_{2}=0.05

), each at

\sigma=0

and at rel.

10^{-3}

. The delivered global certificate lies on the information radius; the

y

-conditional band tracks the actual error; the calibrated GP band is narrower at

\sigma=0

and both wider and invalid at rel.

10^{-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-\mathrm{cert}/E_{\star}

per (level, seed), log axis. Right: all

864

points, with median, IQR and the worst point of each cell marked; nothing is clipped. The ratio never exceeds

1

, its median is

0.999989

, and its worst value is

0.997273

.

Figure 10: The

\rho

-inflation ladder. (a) median conditional half-width against

m=\rho/\rho_{\mathrm{oc}}

with the exact

\eta=0

law overlaid; (b) coverage of the truth,

1.000

at every rung, against the resolution floor of a

144

-point grid; (c) the conditional-vs-global tightening, which at

\sigma=0

follows

(\hat{\varepsilon}/\rho_{\mathrm{oc}})/\sqrt{m^{2}-1}

and crosses

1

at

m=\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

\rho=1.05\rho_{\mathrm{oc}}

, whose right tail reaches

3.8\!\cdot\!10^{3}

where the recovery is accidentally exact – which is why only medians are quoted.

Figure 12: Case A at rel.

10^{-3}

, seed 1, on the

12\times 12

evaluation grid: the global certificate, the

y

-conditional half-width, the GP band, and the GP posterior-mean error with its

24

failures ringed. The global certificate and the GP band are largest on the boundary-adjacent ring; the conditional band is smallest there. The same

24

points fail in all three seeds.

dataset	$N$	$d$	source	target	distinct $y$	RF CV $R^{2}$
diabetes	442	10	sklearn load_diabetes	target	214	0.4193
concrete	1030	8	OpenML 44959	strength	938	0.3428
energy	768	8	OpenML 44960	heating_load	587	0.9651
yacht	308	6	OpenML 42370	Residuary.resistance	258	0.9954
california	1500	8	sklearn california_housing	target	1101	0.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

\leq 20

-level target is refused by the loader, the audit additionally requires

\geq 50

distinct values and a RandomForest 5-fold CV

R^{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

R^{2}=-0.3211

) as energy ; data_id=44960 carries the real heating_load .

dataset	regime	$n_{\mathrm{tr}}$	$n_{\mathrm{te}}$	$n_{c}$	level $n_{c}/(n_{c}{+}1)$	$k$	achieved $(k{+}1)/(n_{c}{+}1)$
california	iid	1200	300	300	$300/301=0.9967$	285	$286/301=0.9502$
california	shift	1050	450	262	$262/263=0.9962$	249	$250/263=0.9506$
concrete	iid	824	206	206	$206/207=0.9952$	196	$197/207=0.9517$
concrete	shift	721	309	180	$180/181=0.9945$	171	$172/181=0.9503$
diabetes	iid	353	89	88	$88/89=0.9888$	84	$85/89=0.9551$
diabetes	shift	309	133	77	$77/78=0.9872$	74	$75/78=0.9615$

Appendix

Table 13: Case B conformal calibration, recomputed from the splits this run used.

n_{c}=\max(8,\lfloor 0.25\,n_{\mathrm{tr}}\rfloor)

; the recorded level is

n_{c}/(n_{c}{+}1)

and the achieved level is

(k{+}1)/(n_{c}{+}1)

for

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

n_{c}{=}88

,

88/89

figures are exact for diabetes i.i.d.; the shift regime trains on

70\%

, giving

n_{c}{=}77

and

77/78

.

i.i.d.
arm	$n$	coverage	median half-width	interval score	penalty share
		(mean)	median [IQR]	median [IQR]	of IS (median)
DAK (released)	19	0.861	0.68 [0.44, 0.86]	2.49 [1.83, 6.29]	0.539
DAK (KL repaired)	19	0.873	0.68 [0.45, 0.90]	2.59 [1.62, 5.40]	0.465
split-CP	19	0.964	0.91 [0.61, 1.71]	2.58 [1.80, 3.74]	0.231
norm. split-CP (temp.)	19	0.961	0.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.

n

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

1

is one training standard deviation.

Figure 13: Case B width–coverage Pareto over all

38

i.i.d. and shift cells (the OR arms deliver on

37

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.852

), unlike in an earlier revision.

Figure 14: The Winkler interval score is never reported without its two parts,

\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.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{=}19$ )	shift ( $n{=}18$ )
$w_{\mathrm{int}}$ share of the band	0.338 [0.281, 0.542]	0.686 [0.543, 0.798]
$w_{\mathrm{add}}$ share of the band	0.412 [0.180, 0.447]	0.117 [0.024, 0.209]
$w_{\mathrm{obs}}$ share of the band	0.292 [0.266, 0.352]	0.182 [0.092, 0.213]
$w_{\mathrm{int}}$ (absolute)	0.828 [0.604, 0.960]	1.898 [0.981, 5.747]
$w_{\mathrm{add}}$ (absolute)	0.961 [0.291, 1.558]	0.836 [0.230, 1.630]
$w_{\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.

w_{\mathrm{int}}

is the tight OR interval,

w_{\mathrm{add}}=q

the conformal floor (constant in a cell),

w_{\mathrm{obs}}=1.96\hat{\sigma}

the noise allowance. Paired differences are median [bootstrap 95% CI of the median], Wilcoxon

p

, on the cells where all three variants delivered; the attainable

p

-floor is

2^{1-n}

(

3.8\times 10^{-6}

at

n{=}19

,

7.6\times 10^{-6}

at

n{=}18

). In the lower block “

w

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

w_{\mathrm{obs}}

, then the conformal floor

w_{\mathrm{add}}

– drawn solid for i.i.d. and dashed for shift, against the nominal

0.95

. Centre: the absolute budget

w_{\mathrm{int}}+w_{\mathrm{add}}+w_{\mathrm{obs}}

stacked for every one of the

37

delivered cells (

2

of the

39

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\%

CI. A feature-free constant band beats the delivered OR band on interval score under shift (

12/18

,

p=0.038

) and is indistinguishable from it in-distribution.

cell	$n_{\mathrm{test}}$	n $>$ cap	median half	mean half	max half	$\mathrm{ns}_{\max}$	$\kappa_{\star}$
california/shift/0/0.0	450	8	0.62	139.8	61896	0.500	40
diabetes/shift/1/0.0	133	13	1.52	25.4	830	0.370	40
diabetes/shift/1/0.1	133	10	1.07	24.1	783	0.297	40
california/shift/1/0.0	450	36	1.28	13.2	391	0.194	40
california/shift/0/0.25	450	13	0.56	6.1	516	0.337	40
concrete/shift/0/0.25	309	8	0.62	4.7	245	0.308	40

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

\eta{=}0

slice. A blow-up is a within-cell median half-width above

20

on a standardized target. The census is

0/37

; what remains is a per- point tail in

13/37

cells, listed here. n

>

cap counts test points whose OR interval exceeds

20\,\mathrm{sd}(y_{\mathrm{fit}})

;

\mathrm{ns}_{\max}

is the largest null-space share of a test functional in the cell.

featnorm	delivery	/30	median $w$	mean $w$	max $w$	(mean)	$>0.999$	IS
		refused	median [IQR] over the delivered cells			blow-up	$ns_{\max}$	median
clamp $10^{-6}$ (shipped)	all rows	18	0.641	266	$1.17\!\cdot\!10^{4}$	0.58	15/30	533
clamp $10^{-6}$	fit split	3	0.863	87.3	$8.06\!\cdot\!10^{3}$	0.56	14/30	903
drop dead	all rows	19	0.588	0.841	2.53	0.09	0/30	2.91
drop dead (v5)	fit split	4	0.818	1.9	26.2	0.12	0/30	6.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^{-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

w_{\mathrm{int}}

on a standardized target; “blow-up” is the notebook’s own criterion at threshold

20

.

scale	effect	ratio	95% CI of the median	$p$	$n$	floor
median $w_{\mathrm{int}}$	FEATNORM, fit split	$1.02$	$[1.01,\,1.04]$	$2.5\!\cdot\!10^{-5}$	26	$3\!\cdot\!10^{-8}$
	FEATNORM, all rows	$1.02$	$[1,\,1.09]$	$0.042$	11	$9.8\!\cdot\!10^{-4}$
	DELIVERY, drop dead	$0.817$	$[0.592,\,0.978]$	$9.8\!\cdot\!10^{-4}$	11	$9.8\!\cdot\!10^{-4}$
	DELIVERY, clamp	$0.893$	$[0.634,\,0.978]$	$0.027$	12	$4.9\!\cdot\!10^{-4}$
	INTERACTION	$1$	$[1,\,1.02]$	$0.32$	11	$9.8\!\cdot\!10^{-4}$
mean $w_{\mathrm{int}}$	FEATNORM, fit split	$235$	$[1.13,\,2442]$	$9.8\!\cdot\!10^{-7}$	26	$3\!\cdot\!10^{-8}$

Appendix

Table 18: Case B / S5: attribution of the width defect. Each row is a paired comparison on

\log_{10}

of the named scale, over the cells where both variants delivered; the ratio is

10^{\text{median difference}}

with the 95% bootstrap CI of the median, the Wilcoxon signed-rank

p

, the number of paired cells, and the smallest

p

attainable at that

n

. 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

{\approx}1

on every width scale: its cost is validity, not width.

Figure 18: The

2\times 2

width-defect ablation on

30

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

235

and the maximum by

2681

while moving the median by

1.02

. Delivering on all training rows is a validity defect, not a width defect: it moves the mean half-width by a factor

0.95

, the maximum by

0.99

and the within-cell median by

0.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

3

–

4

of

30

to

18

–

19

of

30

.

region: design gap $\|x\|<1$
arm	coverage	$\geq$ nom.	mean half-width	interval score
DAK $1.96\hat{\sigma}(x)$	$0.480$ [0.395, 0.588]	0/10	$0.596$ [0.589, 0.633]	$7.04$ [4.23, 18.6]
split-CP (constant)	$0.473$ [0.436, 0.689]	2/10	$0.772$ [0.578, 0.951]	$8.03$ [3.51, 12.9]
normalized split-CP	$0.473$ [0.426, 0.689]	2/10	$0.772$ [0.634, 0.967]	$7.45$ [3.46, 12.5]
constant-predictor split-CP	$0.635$ [0.625, 0.662]	0/10	$1.809$ [1.762, 1.844]	$7.29$ [6.31, 7.62]
OR band or1	$1.000$ [1.000, 1.000]	10/10	$2.804$ [1.786, 3.747]	$5.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.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

w_{\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

\alpha=0.05

against the noiseless truth.

quantity	region	single seed	ten-seed median [IQR]	min–max	verdict
split-CP coverage	gap	$0.58$	$0.473$ [0.436, 0.689]	0.243–1.000	in IQR
split-CP coverage	ind	$0.70$	$0.620$ [0.497, 0.765]	0.293–1.000	in IQR
split-CP coverage	ext	$0.43$	$0.454$ [0.411, 0.497]	0.395–0.500	in IQR
norm. split-CP coverage	gap	$0.61$	$0.473$ [0.426, 0.689]	0.270–1.000	in IQR
norm. split-CP coverage	ind	$0.72$	$0.643$ [0.517, 0.753]	0.313–1.000	in IQR
norm. split-CP coverage	ext	$0.42$	$0.467$ [0.424, 0.487]	0.408–0.539	in 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

2

of

10

seeds each, drawn at coverage

1.000

in the top-left panel. The OR band dominates on interval score in-distribution and in extrapolation while tying in the gap.

	$n$	EI	UCB	OR-LCB ( $\kappa{=}1$ )	$2{\times}$ floor	$5{\times}$ floor
Branin	7	0.14 (0.19)	0.13 (3.88)	0.20 (0.34)	0.29 (0.58)	0.26 (0.89)
Hartmann-6	7	0.70 (1.65)	0.96 (2.05)	0.96 (2.49)	0.96 (2.49)	0.96 (2.49)
Griewank	7	8.31 (20.79)	9.71 (25.49)	12.40 (22.71)	10.98 (19.98)	9.92 (19.98)
Ackley-5D	7/6	6.59 (8.95)	5.58 (9.60)	7.92 (9.60)	7.92 (9.60)	7.34 (9.60)
Levy-10D	6	4.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

23

-evaluation budget (

n_{\mathrm{init}}{=}5

then

18

BO steps), from one GPU session ( botorch 0.18.1 ,

Q{=}3

). Seed counts are uneven and are given in the

n

column: the Ackley

\kappa

arms and all Levy arms have

6

seeds, everything else has

7

; every paired test pairs only on shared seeds. All

80

(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

5

-seed values are unchanged and reported in App. C .

Benchmark	arm	$n$	median diff.	bootstrap $95\%$ CI of the median	better/worse/tied	Wilcoxon $p$	floor
Levy-10D	UCB	$6$	$+0.0000$	$[-0.0606,\,+0.0000]$	$1/0/5$	$1$	$0.03125$
Levy-10D	OR-LCB	$6$	$+0.0000$	$[-0.0606,\,+0.0000]$	$1/0/5$	$1$	$0.03125$
Levy-10D	$2{\times}$ floor	$6$	$+0.0000$	$[-0.0606,\,+0.0000]$	$1/0/5$	$1$	$0.03125$
Levy-10D	$5{\times}$ floor	$6$	$+0.0000$	$[-0.0606,\,+0.0000]$	$1/0/5$	$1$	$0.03125$
Hartmann-6	UCB	$7$	$+0.2105$	$[+0.0000,\,+0.3871]$	$0/5/2$	$0.0625$	$0.01562$
Hartmann-6	OR-LCB	$7$	$+0.2105$	$[+0.0000,\,+0.3871]$	$0/5/2$	$0.0625$	$0.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

p

attainable at that

n

(

2^{1-n}

): at the

5

seeds of the earlier revision it was

0.0625

, so no per-benchmark test could reach

0.05

by construction. The pooled rows test the per-benchmark normalized paired

\log_{10}

ratio against zero over all

33

complete blocks.

Benchmark	arm	$n$	median diff.	bootstrap $95\%$ CI of the median	better/worse/tied	Wilcoxon $p$	floor
Levy-10D	EI	$6$	$+0.0000$	$[+0.0000,\,+0.0606]$	$0/1/5$	$1$	$0.03125$
Levy-10D	UCB	$6$	$+0.0000$	$[+0.0000,\,+0.0000]$	$0/0/6$	$1$	$0.03125$
Levy-10D	$2{\times}$ floor	$6$	$+0.0000$	$[+0.0000,\,+0.0000]$	$0/0/6$	$1$	$0.03125$
Levy-10D	$5{\times}$ floor	$6$	$+0.0000$	$[+0.0000,\,+0.0000]$	$0/0/6$	$1$	$0.03125$
Hartmann-6	EI	$7$	$-0.2105$	$[-0.3871,\,+0.0000]$	$5/0/2$	$0.0625$	$0.01562$
Hartmann-6	UCB	$7$	$+0.0000$	$[+0.0000,\,+0.0000]$	$1/0/6$	$1$	$0.01562$

Appendix

Table 23: Case C, final simple regret paired against OR-LCB (

\kappa{=}1

), same conventions as Tab. 22 . The tie counts are the

\kappa

-inertness made visible:

22/33

blocks tie exactly between

\kappa{=}1

and

\kappa{=}2

,

17/33

between

\kappa{=}1

and

\kappa{=}5

, and

20/33

between

\kappa{=}2

and

\kappa{=}5

.

Benchmark	arm	$n$	median diff.	bootstrap $95\%$ CI of the median	better/worse/tied	Wilcoxon $p$	floor
Levy-10D	UCB	$6$	$+0.0000$	$[+0.0000,\,+0.5668]$	$0/1/5$	$1$	$0.03125$
Levy-10D	OR-LCB	$6$	$+0.0000$	$[+0.0000,\,+0.5668]$	$0/1/5$	$1$	$0.03125$
Levy-10D	$2{\times}$ floor	$6$	$+0.0000$	$[+0.0000,\,+0.5668]$	$0/1/5$	$1$	$0.03125$
Levy-10D	$5{\times}$ floor	$6$	$+0.0000$	$[+0.0000,\,+0.5668]$	$0/1/5$	$1$	$0.03125$
Hartmann-6	UCB	$7$	$+0.0935$	$[+0.0000,\,+0.2253]$	$1/5/1$	$0.0625$	$0.01562$
Hartmann-6	OR-LCB	$7$	$+0.0935$	$[+0.0000,\,+0.2253]$	$1/5/1$	$0.0625$	$0.01562$

Appendix

Table 24: Case C, AUC (mean regret over the

19

-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

\kappa{=}1

, and where the

\kappa{=}2

(dashed) and

\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 seeds			full	escape	UCB
Benchmark	$\mathrm{osc}(\hat{c})/\mathrm{mean}(\hat{c})$	$1{\leftrightarrow}2$	$2{\leftrightarrow}5$	$1{\leftrightarrow}5$	ladder	step	$=$ OR-LCB
Levy-10D	below the $\mu$ -grid floor	$6/6$	$6/6$	$6/6$	$6/6$	never	$6/6$
Hartmann-6	below the $\mu$ -grid floor	$7/7$	$6/7$	$6/7$	$6/7$	$9$	$5/7$
Ackley-5D	$0.0066$	$6/6$	$3/6$	$3/6$	$3/6$	$6$	$2/6$
Griewank-5D	$0.0110$	$1/7$	$3/7$	$0/7$	$0/7$	$5$	$2/7$
Branin-2D	$0.3263$	$0/7$	$0/7$	$0/7$	$0/7$	$0$	$0/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

18

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\%

intervals depend only on

k/n

(

7/7\,[0.590,1]

to

0/7\,[0,0.410]

). The dispersion column is the median over BO steps of

\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(\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

\mathrm{osc}(\hat{c})/\mathrm{mean}(\hat{c})

exceeds

10^{-6}

, and the first

\kappa

divergence always follows it.

	one step ( $n{=}9{,}018$ records)		whole trajectory ( $n{=}99$ pairs)
	argmin coincided	argmin moved	bitwise identical	differ
criterion fires	$5{,}936$	$\mathbf{0}$	$35$	$\mathbf{0}$
criterion silent	$1{,}076$	$2{,}006$	$23$	$41$

Appendix

Table 26: Prop. 4.5 tested directly. Its criterion

|\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\%

of steps and covers

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=|\Delta\kappa|\,\mathrm{osc}(c)/\Delta_{\kappa}

: exactly

1.000

in every bin below the threshold and still

0.80

–

0.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.

rel. noise	released	Morozov	ML-II	GCV	L-curve	oracle	gain	M/o
0	$4.0\!\cdot\!10^{-4}$	$4.0\!\cdot\!10^{-4}$	$4.0\!\cdot\!10^{-4}$	$4.0\!\cdot\!10^{-4}$	$1.4\!\cdot\!10^{-3}$	$4.0\!\cdot\!10^{-4}$	$1.00$	1.00
$10^{-4}$	$3.0\!\cdot\!10^{-2}$	$7.9\!\cdot\!10^{-4}$	$3.0\!\cdot\!10^{-2}$	$3.0\!\cdot\!10^{-2}$	$1.4\!\cdot\!10^{-3}$	$7.4\!\cdot\!10^{-4}$	$40\times$ [20,77]	1.12
$3\!\cdot\!10^{-4}$	$4.3\!\cdot\!10^{-2}$	$1.1\!\cdot\!10^{-3}$	$9.2\!\cdot\!10^{-3}$	$3.9\!\cdot\!10^{-2}$	$5.0\!\cdot\!10^{-3}$	$9.5\!\cdot\!10^{-4}$	$40\times$ [21,135]	1.18
$10^{-3}$	$5.3\!\cdot\!10^{-2}$	$1.9\!\cdot\!10^{-3}$	$3.8\!\cdot\!10^{-3}$	$1.2\!\cdot\!10^{-2}$	$1.3\!\cdot\!10^{-2}$	$1.7\!\cdot\!10^{-3}$	$27\times$ [14,34]	1.19
$3\!\cdot\!10^{-3}$	$1.0\!\cdot\!10^{-1}$	$4.6\!\cdot\!10^{-3}$	$4.7\!\cdot\!10^{-3}$	$3.8\!\cdot\!10^{-3}$	$4.7\!\cdot\!10^{-3}$	$3.6\!\cdot\!10^{-3}$	$23\times$ [17,94]	1.15
$10^{-2}$	$6.2\!\cdot\!10^{-1}$	$1.2\!\cdot\!10^{-2}$	$1.2\!\cdot\!10^{-2}$	$1.2\!\cdot\!10^{-2}$	$1.2\!\cdot\!10^{-2}$	$1.2\!\cdot\!10^{-2}$	$47\times$ [24,71]	1.00

dataset	$R^{2}$	$d_{\mathrm{M}}$	$n$	cov	wid	IS	cov	wid	IS	cov	wid	IS	cov	wid	IS
				split-CP			triv (constant)			OR head (R1)			OR, no floor
concrete	0.343	1.29	4	0.831	0.80	3.74	0.970	1.96	4.26	0.996	2.04	7.22	0.977	1.43	6.27
diabetes	0.419	1.25	6	0.950	2.09	4.88	0.995	2.05	4.17	1.000	3.45	26.21	0.923	1.83	24.01
california	0.740	1.39	3	0.962	1.35	3.35	0.969	2.26	4.96	1.000	3.29	111.0	0.954	1.55	108.2
energy	0.965	3.04	3	0.784	0.33	2.05	0.986	1.98	4.03	1.000	1.41	3.44	1.000	1.29	3.20
yacht	0.995	1.60	3	0.896	0.66	3.24	0.936	2.73	6.39	0.971	1.04	2.73	0.968	0.97	2.62

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

Abstract

Figures & tables

Appendix

Gaussian Process Regression

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

Adaptive Bayesian Online Learning via Expert Aggregation

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

Abstract

Gaussian Process Regression

Explore similar work

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

Adaptive Bayesian Online Learning via Expert Aggregation

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees