CS Paper Radar

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

Gordei Verbii

cs.LG stat.ML ·submitted 2026-08-29 01:47 UTC · v1
theory

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.

Comment
48 pages, 22 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

cs.LG ·2026-09-23 ·Vaneet Aggarwal
theory similarity 0.60
Abstract

We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance. For convex $G$-Lipschitz losses, diameter at most $D$, a total allowance of $Q$ oracle calls, and a strict limit of $B$ calls per round, the dimension-free minimax expected regret is $Θ(GD\max\{\sqrt T,T/(1+\min\{Q,BT\})^{1/4}\})$. The lower bound applies to arbitrary randomized learners. Universal feasibility first forces each action into the hull of the supplied ball and the preceding oracle replies. A fixed-body construction then couples fresh phase directions to a shared simplex, making useful replies costly repeatedly even though all losses have a common minimizer. A counted approximate-gradient method with interleaved blocks attains the matching rate. Total-budget and strict per-round guarantees follow as special cases, including the $T^{3/4}$ rate with one call per round and the quadratic total budget needed for $\sqrt T$ regret. For prescribed smoothness $β$, an analytic construction yields a curvature-dependent lower bound and identifies the threshold above which the general characterization remains sharp.

0.16

Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancing

cs.LG ·2026-09-26 ·Joyanta Jyoti Mondal, Ibne Farabi Shihab
similarity 0.57
Abstract · 32 pages, 9 figures

Post-hoc Bayesian fine-tuning places Gaussians around trained low-rank adapters, yet a calibrated posterior does not by itself yield a useful generalization certificate. Such a posterior admits an informative PAC-Bayes certificate only when both the loss of its sampled predictors and its KL divergence from an admissible prior are small. In this research, we characterize this certification frontier for Gaussian LoRA posteriors and separate three interventions: changing the prior, changing the stochastic predictor, and changing only how its complexity is counted. First, an exact isotropic KL envelope eliminates the prior scale and yields a width threshold that excludes posterior widths before sampling, while a zero-KL floor identifies targets that no complexity reduction can reach at a measured risk bound. Second, we minimize KL in closed form over the full $GL(r)$ symmetry of the low-rank factors, leaving every sampled adapter product unchanged, and derive the noncentral objective required when the prior center is trained on an independent split. On a small-pool RoBERTa audit of 567 configurations, the recorded 64-draw summaries imply a certificate floor of $0.7298$ even with zero KL and Chernoff accounting, so reducing complexity alone cannot certify these posteriors at the recorded budgets. For a stable posterior in a controlled Gaussian-factor task, Chernoff accounting certifies risk below $0.1$ on 20 of 20 datasets with 1024 draws, whereas Hoeffding certifies none. On deliberately deformed synthetic rank-four factors, matrix balancing reduces KL by $29.3\%$ on average beyond scalar balancing without changing any prediction. Numerical split-prior scenarios make the remaining risk and complexity budgets explicit.

0.37

Target-Dependent Limits of Causal Repair: A Leading-Log Frontier in a Gaussian Model

cs.AI stat.MLcs.LG ·2026-09-30 ·Qinchuan Cheng, Jiaqi Liu, Ruixuan Xie
similarity 0.56
Abstract

Knowing how much a causal predictor could improve need not reveal the gain of the repair actually learned. We quantify this gap in a scalar Gaussian causal experiment with known intervention geometry: auxiliary data identify effect magnitude up to bounded contamination, while diagnostics identify direction. The target is the squared-loss gain of the realized trained repair relative to a fitted reference. Jointly optimizing the learner and assessor under uniform learning MSE $η$ avoids the trivial solution of making no repair. At the usual $1/k$ learning scale, every feasible learner incurs a $k^{-2}$ assessment floor, even when oracle potential is estimable at a faster rate. In the magnitude-rich regime, we characterize a sharp leading-log frontier: the assessment exponent is $\min{\ell_k,2kη_k/U}$ to first relative order, where $\ell_k=\log(1/(k^2E_k))$ and $E_k$ is auxiliary precision. A diagnostic-abstention rule attains this exponent with unknown nuisance parameters. We also bound the critical allowance window and transfer the frontier to adaptive sampling by exact Gaussian simulation. Finite-grid experiments distinguish sign-tail suppression from total MSE and expose conservative finite-budget behavior. The result isolates how the assessment target changes information requirements in this experiment; it is not a general causal identifiability claim.

0.23

Phantom Gains: Auditing Self-Improvement Against a Measured Null

cs.AI cs.CL ·2026-08-20 ·Cheng Xu, Nan Yan, Liming Chen, M-Tahar Kechadi
code/datahighly cited similarity 0.55
Abstract · Code and evaluation artifacts are available at https://github.com/chengxuphd/phantom-gains

Whether a language model has improved itself is increasingly judged not by mean accuracy but by which individual problems it gains and loses. Tracking these transitions means differencing two noisy estimates, leaving them vulnerable to measurement artifacts. Auditing three rounds of rank-$32$ LoRA self-training on Qwen3-8B against a frozen control pushed through the identical pipeline, we identify seven measurement failures, each of which inverts a reported finding when its control is absent. Several are standard practice. A ledger built on a single greedy decode manufactures capability changes on an untrained model, largely an artifact of inference batching; the expansion statistic separating acquisition from sharpening assigns that same model a rate of $0.280$. The natural threshold repair does not survive replication: estimated across the frozen comparisons such a design already contains, its null stays non-zero. We replace it with a per-problem exact test against a pooled baseline under false-discovery-rate control, which detects nothing on any held-out replicate and is unchanged under the multiple-testing rule, error rate and pool size. Applied to a ladder of arms matched in stream, volume and evaluation, the audit finds that external distillation improves problems the base model rarely reaches while three forms of self-training do not; a regression rejects this asymmetry as a by-product of distillation's larger overall gain ($p < 10^{-8}$). On the far smaller set of problems the base model never reaches, the evidence is inconclusive, while self-training corrupts problems solved at baseline at rates well above the measured floor. Transition-level auditing therefore requires a separately measured null for every statistic it reports: nulls that cost no new experiments, built from baseline replicates a multi-arm study already owns, though not from as few as most possess.

0.66

Better Policies, Worse Verifier Audits

cs.LG ·2026-10-21 ·Daniel Cieślak, Jacek Łubiński
similarity 0.54
Abstract · 53 pages, including appendices

Verifier stacks increasingly sit inside post-training and test-time compute loops. We study a specific control loop: a component verifier is evaluated on fresh policy outputs against the full success label and refreshed when that aggregate score falls. For a conjunctive target $y = F \wedge M$, its on-policy AUC is $(1-q)A_{\mathrm{own}} + qA_{\mathrm{cross}}$, where $q = \Pr[F=1 \mid y=0]$. As the policy masters $F$, $q$ can rise toward one, removing weight from $F$-failures and rewarding information about $M$. We call this on-policy audit collapse. We derive a sharp identified set, a complete-erasure threshold, and the exact point at which the audit can prefer a worse component verifier; its population optimum is the full-outcome predictor, not the component oracle. An exact oracle exhibits the collapse, a natural multi-label text control shows inversion can select a head with lower canonical $F$-AUC at the observed failure mixture, and a prediction-registered ECG study shows that acting on the audit can reduce off-policy $F$-AUC, transfer the damage to an unseen generator, and increase downstream constraint violations. Preserving own-failure support prevents the damage. Matching label-complexity bounds and a controlled-mixture audit give the corresponding repair: audit the component on its own failures, and keep those failures in the refresh distribution.

0.37

Thermodynamics of Learning: A Typed Four-Component Accounting of Memory, Fit, and Value

cs.IT cond-mat.stat-mechcs.LG ·2026-08-13 ·Akihito Sudo
similarity 0.54
Abstract · 36 pages, 3 figures, 5 tables

What a finite learning device has recorded and what will hold value for it on future tasks are not the same quantity. We develop a typed accounting for finite-state learning devices that separates four components: a training-side fit functional $Φ_{\mathrm{fit}}$, the record-correlation stock $J_{D}=I(M;D)$, an update-side search ledger $σ_{M}$, and an operational capital value $V(M;T,b)$. This value is the work gap between an informed protocol class and a blind class obtained by deleting the memory-read port and re-optimizing from scratch. (I) Separation: for every $n$, there is a device family on which record correlation and world correlation grow by $n\ln 2$ while the capital gain is exactly zero. In the $\mathrm{flat}^{*}$ regime, data-free updates never increase $V$. (II) Capitalization ledger: an exact $\mathrm{flat}^{*}$ extraction identity and a universal ledger identity give, for (F5$'$)-stable $M$-local updates under a no-discarded-record-correlation condition (f), the bound $η_{\mathrm{cap}}\le 1$ for the capitalization efficiency $η_{\mathrm{cap}}=ΔV/(k T\,σ_{M})$, together with necessary and sufficient conditions for equality. (III) Value retention: for the retention gap $L_{\mathrm{gen}}$ and retention ratio $ρ_{\mathrm{gen}}$ (the former carries no sign constraint; the latter is defined for positive training-side value and is not confined to $[0,1]$) we give a two-layer alignment domain: an exact exchange rate between value and the side-information-adjusted record fit $I(M';D\mid Y)$ without any record-side-information independence assumption, and a raw record-stock exchange rate under a joint side-information neutrality condition $(M,D)\perp Y$, whose boundary is marked by an explicit one-time-pad witness. These are statements about finite-device value retention under task-distribution shift, not a theory of statistical generalization.

0.10

Certifying Distributionally Robust Decisions from Projection Observations

cs.AI stat.MLcs.LGmath.OC ·2026-10-25 ·Pouya Ahadi, Kamran Paynabar
theory similarity 0.54
Abstract

A scalar measurement can determine a robust decision without identifying the latent covariance or every decision risk. We study finite Gaussian projection experiments with a fixed mean-plus-standard-deviation target. The observation laws define a set of indistinguishable moment models. We exhibit decisions that agree throughout that set despite unidentified risk values, and give a confidence-set certificate that returns a decision or an unresolved outcome. We prove soundness, necessary abstention for indistinguishable models with incompatible optima, and a fixed-checkpoint certification guarantee. A scalar profile reduces nonlinear risk comparisons to convex inner problems. Across seven synthetic instances, jointly calibrated moment regions give sufficient budgets 21 to 52 times explicit expected-sample information lower bounds. Separately measured stopping times are lower, with zero decision errors in 1,900 simulated streams. These comparisons do not constitute matching bounds, and the guarantees require Gaussian replication.

0.17

Selected-Risk Calibration for Feasibility at Returned Decisions

cs.LG stat.ML ·2026-11-05 ·Raghav Thind, Youran Sun, Ling Liang, Haizhao Yang
similarity 0.54
Abstract · 20 pages, 3 figures

When an optimization problem uses a surrogate constraint, a decision that is feasible for the surrogate need not be feasible for the true constraint. We propose Selected-Risk Calibration (SRC), a framework that calibrates a learned constraint against the optimizer's returned decisions for objectives drawn from a given distribution. SRC guarantees that, with probability at least $1-δ$, every margin it certifies on held-out objectives has selected risk, the probability that the returned decision is infeasible, of at most $γ$. We also show that the random-input coverage guarantee of split conformal prediction does not bound the selected risk, and that likelihood-ratio reweighting for feedback covariate shift does not apply when the learned constraint is active at the returned decision. Our experiments show that a conformal margin covering about $90\%$ of random inputs covered as few as $17\%$ of the returned decisions, and every certified margin had a violation rate below its target on unseen objectives. Moreover, at equal cost, SRC's correction had fewer or equal infeasible solutions to the baselines in 57 of 62 comparisons. The SRC framework applies to any setting in which a surrogate model chooses a decision whose feasibility can be verified for a sample of instances.

0.23