Optimal Recovery Meets Bayesian Learning: Where Worst-Case Bounds Pay Off
stat.ML, cs.LG
Submitted: 2026-08-29
Updated: 2026-08-29
Comments: 48 pages, 22 figures
Code: https://github.com/FrankHuang24/ALAS-BO
License: http://creativecommons.org/licenses/by/4.0/
The gist: Worst-case Optimal Recovery (OR) and Bayesian learning describe the same Gaussian-quadratic-Hilbert problems in two vocabularies.
Terminology
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.00 - 1.19 times where σ-blind rules fail, is 4.9 - 6.3 times more reproducible across noise draws (p=0.002 - 0.004), and is the only deployable rule whose selection survives a change of backend (1.36 times against 12 - 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 is inert wherever κ = 5 is and on more cells besides, while κ = 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.
Sources
- Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
- Nonlinear Optimal Recovery in Hilbert Spaces
- Optimal recovery of linear operators from information of random functions
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Efficient quadratic entropy with distance sketches
- Embedding-Bias in Conditional Independence Testing
- From Log-Odds to Shapley Values: An Explanatory Geometry for the Weighted Naive Bayes Classifier