When Is Accuracy Evidence? A Unified Theory of Generalisation, Validation, and Information Fusion

JM Gorriz

stat.MLOct 2, 2026

When Is Accuracy Evidence? A Unified Theory of Generalisation, Validation, and Information Fusion

Authors: JM Gorriz

Organizations: Data Science and Computational Intelligence Institute University of Granada Granada, Spain · Department of Psychiatry University of Cambridge Cambridge, UK

Abstract

K-fold cross-validation (CV) is widely used as evidence of out-of-sample performance, although folds are neither independent experiments nor equally informative under heterogeneous data. Cross Upper-Bound Validation (CUBV) replaces point-wise CV accuracy by conservative upper bounds on true risk. Here we generalise CUBV through a single exponential framework in which the moment-generating function of the generalisation gap is controlled by a cumulant envelope gamma(lambda). This yields a family of risk bounds covering Hoeffding-, Bernstein-, dependency-aware, PAC-Bayesian, and heterogeneous source-fusion settings. For K-fold CV, dependence between fold-wise gaps is modelled through a joint sub-Gaussian proxy matrix. Under equicorrelation, this gives an effective number of folds, Keff = K/[1+(K-1)rho], showing that increasing K does not necessarily increase statistical evidence when folds are strongly dependent. The framework is also extended to posterior distributions over predictors and weighted multi-source fusion, where weights are selected by minimising an upper bound on future risk rather than empirical error alone. Experiments with trained linear classifiers on heterogeneous multimodal Gaussian mixtures compare K-fold CV with full-sample resubstitution plus risk correction. Bounds are evaluated by coverage and tightness. In low-dimensional small-sample settings, K-fold partitioning can increase uncertainty because individual folds under-represent minority modes, while corrected resubstitution can remain valid and tighter; this effect disappears as sample size increases. Overall, gamma-CUBV separates observed performance, uncertainty, dependence, model complexity, and confidence into explicit terms, providing a unified route from CV scores to risk statements and a principled validation criterion for heterogeneous small-sample applications such as neuroimaging.

Figures & tables

Method	Uncertainty model	Main purpose
Hoeffding-CUBV	$\gamma(\lambda)=\lambda^{2}\sigma^{2}/2$ with worst-case bounded-loss proxy	Baseline range-based concentration; recovers a standard CUBV-type upper confidence penalty.
V-CUBV / Bernstein-CUBV	Sub-gamma envelope with variance factor $v$ and scale $c$	Distinguishes models or experiments having similar mean error but different uncertainty.
Dependency-CUBV	Joint sub-Gaussian proxy matrix $\bm{\Sigma}$ for fold gaps	Accounts explicitly for overlap and dependence among K-fold experiments; introduces $K_{\mathrm{eff}}$ .
Hölder-CUBV	Fold-wise exponential envelopes combined through Hölder’s inequality	Provides a conservative construction without multiplying moment-generating functions of dependent folds.
PAC- $\gamma$ -CUBV	Exponential envelope plus $\mathrm{KL}(Q\\|P)$ complexity	Separates predictive error, model complexity, data uncertainty, and confidence.
Fusion-CUBV	Joint uncertainty matrix across information sources	Selects fusion weights by minimising an upper bound on risk rather than empirical error alone.

Table 1: Representative members of the

\gamma

-CUBV family.

Figure 1: Mean resubstitution upper risk as a function of sample size. Shaded regions denote 95% Monte Carlo confidence intervals for the estimated mean across independent evaluation repetitions. The dashed curve denotes the population risk estimated from the independent test sample. Monte Carlo confidence intervals quantify simulation uncertainty and are distinct from the $1-\delta=0.95$ generalisation confidence level defining the bounds.

	$n=50$		$n=5000$
Method	Resub.	$K$ -fold	Resub.	$K$ -fold
Hoeffding	0.381 / 0.152	0.395 / 0.165	0.239 / 0.019	0.239 / 0.019
Emp. Bernstein	0.389 / 0.160	0.406 / 0.175	0.236 / 0.016	0.237 / 0.016
MGF/Dependency	0.383 / 0.154	0.401 / 0.170	0.241 / 0.020	0.240 / 0.020
PAC-Bayes	0.600 / 0.370	0.994 / 0.762	0.264 / 0.043	0.319 / 0.097
VC-Hoeffding	1.000 / 0.771	–	0.441 / 0.221	–

Table 2: Representative results for Experiment I. Each entry reports mean upper risk / mean tightness.

Figure 2: Probability of certifying better-than-chance future risk, defined by $U<0.5$ , as a function of sample size. Shaded regions denote 95% Wilson confidence intervals for the Monte Carlo certification probability.

Figure 3: Mean population risk across the structural complexity ladder $L1$ – $L5$ for different sample sizes. Shaded regions denote 95% Monte Carlo confidence intervals. The progression from $L1$ to $L5$ produces a monotonic increase in population risk for the fixed linear classifier.

Figure 4: Mean resubstitution upper risk across structural complexity levels at $n=200$ . Shaded regions denote 95% Monte Carlo confidence intervals. The dashed curve denotes the corresponding population risk.

Method	$L1$	$L2$	$L3$	$L4$	$L5$
Bernstein	0.010 / 0.010	0.192 / 0.053	0.440 / 0.079	0.488 / 0.105	0.565 / 0.064
Hoeffding	0.087 / 0.086	0.212 / 0.072	0.435 / 0.073	0.481 / 0.098	0.555 / 0.054
MGF/Dependency	0.002 / 0.002	0.190 / 0.051	0.434 / 0.073	0.479 / 0.096	0.576 / 0.075
PAC-Bayes	0.203 / 0.203	0.327 / 0.187	0.560 / 0.188	0.620 / 0.201	0.677 / 0.177
VC-Hoeffding	0.907 / 0.907	0.999 / 0.860	1.000 / 0.638	1.000 / 0.617	1.000 / 0.499

Table 3: Representative resubstitution results for Experiment II at

n=200

. Each entry reports mean upper risk / mean tightness.

Figure 5: Probability of certifying better-than-chance future risk from the resubstitution bounds across structural complexity levels at $n=200$ . Shaded regions denote 95% Wilson confidence intervals for the Monte Carlo certification probability.

Figure 6: Mean population risk at $n=200$ as the number of mixture components increases under linear-multimodal and nonlinear-alternating geometries. Shaded regions denote 95% Monte Carlo confidence intervals.

Figure 7: Hoeffding-CUBV resubstitution upper risk at $n=200$ for linear-multimodal and nonlinear-alternating geometries. Solid curves denote mean upper risks, dashed curves denote the corresponding population risks, and shaded regions denote 95% Monte Carlo confidence intervals.

Figure 8: Probability of certifying better-than-chance future risk at $n=200$ under linear-multimodal and nonlinear-alternating geometries. Shaded regions denote 95% Wilson confidence intervals for the Monte Carlo certification probability.

Figure 9: Mean fused upper risk as a function of sample size for the five information-fusion strategies. Shaded regions denote 95% Monte Carlo confidence intervals.

Figure 10: Paired difference in fused upper risk relative to Fusion-CUBV. Positive values indicate a larger upper risk for the comparison method. Error bars denote 95% Monte Carlo confidence intervals for the paired differences.

Figure 11: Fusion-CUBV source weights at each sample size. Weights are estimated using only the calibration repetitions and frozen before evaluation. Because calibration is performed independently for each $n$ , the curves should not be interpreted as a deterministic trajectory of source relevance with sample size.

Method	$n=50$	$n=500$	$n=5000$
Uniform	0.490 / 1.000	0.424 / 0.967	0.399 / 0.900
Empirical-risk	0.533 / 1.000	0.396 / 0.967	0.366 / 1.000
Variance-only	0.490 / 1.000	0.431 / 0.933	0.400 / 0.800
Fusion-CUBV	0.484 / 1.000	0.396 / 0.967	0.366 / 1.000
Safe-Fusion-CUBV	1.000 / 1.000	1.000 / 1.000	1.000 / 1.000

Table 4: Representative results for Experiment IV. Each entry reports mean fused upper risk / empirical coverage.

Figure 12: Fusion-CUBV mean upper risk as a function of sample size for different numbers of information sources. Shaded regions denote 95% Monte Carlo confidence intervals. The near-overlap of the curves shows that the bound remains stable as progressively weaker sources are added.

Figure 13: Fusion-CUBV upper risk and corresponding population risk as the number of information sources increases at $n=200$ . Shaded regions denote 95% Monte Carlo confidence intervals for the mean upper risk.

Figure 14: Fusion-CUBV mean upper risk as a function of sample size for increasing numbers of structurally heterogeneous information sources. Shaded regions denote 95% Monte Carlo confidence intervals.

Figure 15: Mean population risk of the Fusion-CUBV predictor as a function of sample size for increasing numbers of structurally heterogeneous sources. Shaded regions denote 95% Monte Carlo confidence intervals.

Figure 16: Fusion-CUBV upper risk and corresponding population risk as the number of structurally heterogeneous sources increases at $n=200$ . Shaded regions denote 95% Monte Carlo confidence intervals for the mean upper risk.

Feature	$\widehat{R}$	$R_{\mathrm{audit}}$	$U_{H}$	$U_{B}$	$\widehat{R}_{G}(Q)$	$R_{G,\mathrm{audit}}$	$U_{PB}$
$z_{1}$	0.287	0.330	0.360	0.360	0.284	0.338	0.435
$z_{2}$	0.323	0.351	0.396	0.398	0.338	0.329	0.490
$z_{3}$	0.316	0.277	0.388	0.391	0.311	0.289	0.463
$z_{4}$	0.277	0.340	0.349	0.349	0.284	0.333	0.435
$z_{5}$	0.326	0.298	0.399	0.402	0.328	0.316	0.479
$z_{6}$	0.291	0.319	0.364	0.364	0.290	0.324	0.442

Table 5: Experiment VII: component-wise bounded discriminability using all

n=282

development subjects.

\widehat{R}

and

R_{\mathrm{audit}}

refer to the deterministic logistic classifier, whereas

\widehat{R}_{G}(Q)

and

R_{G,\mathrm{audit}}

refer to the corresponding Gibbs classifier and should therefore be compared with the PAC–Bayes upper risk

U_{PB}

. The audit cohort is not used to construct any bound.

Feature	$n_{\mathrm{cert}}^{H}$	$n_{\mathrm{cert}}^{B}$	$n_{\mathrm{cert}}^{PB}$
$z_{1}$	50	50	200
$z_{2}$	50	100	282
$z_{3}$	50	100	200
$z_{4}$	50	50	200
$z_{5}$	50	100	282
$z_{6}$	50	50	200

Table 6: First evaluated sample size at which the mean component-wise upper risk falls below

0.5

. Hoeffding and Bernstein refer to the deterministic classifier, whereas PAC–Bayes targets Gibbs risk.

Panel of Figure 17 — Figure 17: Experiment VII: sample-size dependence of bounded discriminability for latent coordinates $z_{1}$ – $z_{4}$ . Solid curves report mean upper risks and the shaded regions show empirical 10th–90th percentile bands across repeated stratified subsamples. The horizontal reference at $0.5$ denotes balanced binary chance risk. PAC–Bayes targets Gibbs risk; Hoeffding and empirical Bernstein target the deterministic classifier.

Panel of Figure 18 — Figure 18: Experiment VII: sample-size dependence of bounded discriminability for latent coordinates $z_{5}$ – $z_{8}$ . The later PAC–Bayes crossing of some coordinates illustrates that an empirical discriminative signal can appear before the available sample supports a better-than-chance upper-risk statement.

Exp.	Main factor	Configuration
I	Sample size	$n\in\{50,100,200,500,1000,2000,5000\}$ , $d=2$ , $N_{c}=4$ ; resubstitution and $K$ -fold bounds compared.
II	Structural complexity	Five-level ladder from a simple linear problem to a highly nonlinear overlapping alternating-ring problem.
III	Multimodality vs. nonlinearity	$N_{c}\in\{2,4,6,8,10\}$ ; globally linear multimodal geometry compared with alternating nonlinear geometry.
IV	Fusion rule	$M=4$ non-homogeneously sampled multimodal sources with two interlaced Gaussian modes per class; Uniform, Empirical-risk, Variance-only, Fusion-CUBV, and Safe-Fusion-CUBV compared across the Experiment-I sample-size grid.
V	Number of sources	Fusion-CUBV fixed; $M\in\{2,4,6,8,10\}$ using a nested ladder of progressively weaker/noisier views of the same subjects.
VI	Structural source heterogeneity	Fusion-CUBV fixed; $M\in\{2,4,6,8,10\}$ with additional sources having progressively different and more nonlinear class geometries.

Table 7: Summary of the synthetic experiments.

Figure 19: Representative datasets from Experiment II: (a) $L1$ , simple linear; (b) $L2$ , linear multimodal; (c) $L3$ , mildly nonlinear; (d) $L4$ , strongly nonlinear; and (e) $L5$ , highly nonlinear with substantial class overlap. The panels are generated by the same data-generating routines used in the Monte Carlo study.

Figure 20: Representative heterogeneous multimodal sources from Experiment IV. Each source contains two interlaced Gaussian modes per class. Subject labels are shared across sources, whereas the latent within-class component is sampled independently using source-specific mixture probabilities; separation, dispersion, and orientation also vary across sources. Cross-shaped markers indicate the generating component centres.

Figure 21: Representative views from the $M=10$ nested source ladder of Experiment V: (a) Source 1, the exact baseline representation; (b) Source 5, an intermediate weakened/noisy representation; and (c) Source 10, the final and weakest/noisiest representation. The subject identities and class labels are shared across all three panels.

Figure 22: Representative structurally heterogeneous sources from Experiment VI: (a) Source 1, linear with $N_{c}=2$ ; (b) Source 2, globally linearly exploitable but multimodal with $N_{c}=4$ ; (c) Source 4, alternating nonlinear geometry with $N_{c}=8$ ; and (d) Source 10, the most structurally complex alternating geometry with $N_{c}=20$ .

Figure 23: Mean bound tightness, $U-\mathcal{R}_{\mathrm{true}}$ , for resubstitution and $K$ -fold validation across sample size. Error bars are 95% Monte Carlo confidence intervals. At small $n$ , the $K$ -fold bounds are systematically wider for the three displayed constructions; the difference decreases as sample size grows.

Figure 24: Empirical $K$ -fold coverage for the dependence-aware constructions. Error bars are 95% Wilson score intervals. The dashed horizontal line marks the nominal coverage level $1-\delta=0.95$ . Safe-MGF/Dependency and Hölder-Hoeffding are conservative throughout the sweep, whereas the plug-in MGF/Dependency rule exhibits one isolated value of $0.90$ at $n=2000$ .

Explore similar work

May 25, 2026math.ST

Minimax Limits of k-Fold Cross-Validation via Majority

We study the mean-squared error of

k

-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds

k

. Despite the widespread use of cross-validation, principled guidance for choosing

k

is largely absent, mainly due to the complex dependence between fold-wise error estimates. To obtain sharp and interpretable results, we focus on the majority algorithm in binary classification, a minimal yet nontrivial empirical risk minimization procedure. We provide a fine-grained analysis of its cross-validation behavior, showing that even this simple algorithm exhibits subtle and delicate phenomena for which existing theory provides loose and even vacuous bounds. Leveraging this analysis, we introduce a minimax framework for cross-validation risk estimation and prove that no empirical risk minimization algorithm can achieve an

O(1/n)

minimax mean-squared error when the number of folds grows with the number of samples

n

; instead, a lower bound of order

Ω(\sqrt{k}/n)

is unavoidable. Our results reveal fundamental limitations of cross-validation as a data-reuse strategy, clarify gaps and inaccuracies in prior theoretical work, and position the majority algorithm as a natural benchmark that any tight analysis of cross-validation should be able to explain.

Ido Nachum, Rüdiger Urbanke, Thomas Weinberger

University of Haifa, Haifa, Israel. · EPFL, Lausanne, Switzerland.

Minimax Estimation Statistical Learning Theory

Ask PDF

Jun 10, 2026cs.LG

Crossing the Validation Crisis: Cross-Validation Reduces Benchmarking Variance Surprisingly Well

Modern machine learning progresses through empirical work, benchmarking new methods to evaluate relative performance. However, the statistical variability inherent to evaluation - exacerbated by the stochastic nature of many algorithms - often makes performance estimation unreliable due to the limited test samples available, leading to a validation crisis in which genuine advances are difficult to discern. In this work, we show that cross-validation improves markedly confidence when evaluating and comparing learning algorithm performances. We introduce the concept of sample gain, which quantifies the virtual data augmentation achieved by using multiple cross-validation splits to reduce benchmarking variance. Experiments on both synthetic and real-world datasets (histopathologic scans and NLP fine-tuning) demonstrate that multiple splits can substantially improve the reliability and stability of performance estimates, with diminishing returns often setting in later than expected. We also introduce a procedure to dynamically early-stop cross-validation by estimating from the first few folds if subsequent folds will bring large sample gains. Our findings highlight the value of pushing cross-validation on available samples to achieve robust and reliable benchmarking.

Célestin Eve, Gaël Varoquaux, Thomas Moreau

MIND Team, Université Paris-Saclay, Inria, CEA, Palaiseau, France · SODA Team, Inria, Palaiseau, France · Probabl

Benchmark Validity Variance Reduction

Ask PDF

May 18, 2026cs.CV

Lost in the Folds: When Cross-Validation Is Not a Deep Ensemble for Uncertainty Estimation

Ensemble disagreement is widely used as a proxy for epistemic uncertainty in medical image segmentation. In practice, many studies form ensembles via K-fold cross-validation (CV), yet refer to them as ``deep ensembles'' (DE). Because CV members are trained on different data subsets, their disagreement mixes seed-driven variability with data-exposure effects, which can change how uncertainty should be interpreted. We audit recent segmentation uncertainty studies and find that terminology--implementation mismatches are common. We then compare a standard 5-fold CV ensemble to a 5-member DE (fixed training set, different random seeds) under otherwise identical configurations on three multi-rater segmentation datasets spanning three modalities. We evaluate uncertainty for calibration, failure detection, ambiguity modeling, and robustness under distribution shift. DE match segmentation accuracy while improving calibration and failure detection, whereas CV ensembles sometimes correlate more strongly with inter-rater variability on the studied datasets. Thus, ensemble construction should be chosen to match the research question: DE for reliability-oriented use (e.g., selective referral/failure detection) and CV ensembles as a proxy for ambiguity. We provide a lightweight nnU-Net modification enabling DE training within the default pipeline.

Tristan Kirscher, Markus Bujotzek, Yannick Kirchhoff +5

ICube, Institut Strauss, DKFZ · ICube Laboratory, CNRS UMR-7357, University of Strasbourg, Strasbourg, France · CLCC Institut-Strauss, Strasbourg, France +6

Deep Ensembles Medical Image Segmentation Segmentation Uncertainty Estimation Uncertainty Calibration

Ask PDF