Rebalancing Leave-One-Out Without Discarding Patients

Leave-one-out cross-validation trains a model on all samples but one, scores it on the held-out sample, and repeats for every sample. On small clinical cohorts it has a hidden flaw. Removing a positive case lowers the fraction of positives in the training set, and removing a negative case raises it. Regularized models pull their predictions toward that training fraction, so every held-out patient is nudged toward the wrong label. Distributional bias compromises leave-one-out cross-validation shows that this drives the area under the ROC curve (auROC) on pure-noise data well below 0.5, and that it steers hyperparameter tuning toward under-regularized models. Their fix, rebalanced leave-one-out (RLOOCV), also drops a randomly chosen patient of the opposite class from each training fold. That fix has three costs. It discards a real training sample, which hurts most when $N<20$. It adds randomness, because the result depends on which partner was dropped. And removing the randomness by averaging over all partners requires on the order of $N^2$ refits for every hyperparameter value.

We propose a deterministic alternative that keeps every patient. When sample $i$ is held out, we leave every training point in place and slightly downweight each opposite-class point, so the training set keeps exactly the full-cohort class ratio. We call this fractional rebalancing. Each fold is a weighted refit, and the weights are exactly the kind of small, smooth perturbation that the infinitesimal jackknife was built to approximate. The jackknife (IJ) is a Taylor-expansion shortcut that predicts how fitted parameters move when data weights change, using one solve against the full-data Hessian. The approximation therefore gives a closed form for the expected rebalanced fold at roughly the cost of ordinary leave-one-out. The main contribution is a bias-free, randomness-free estimator. The approximation is what makes it cheap enough to sweep regularization grids and pipeline variants. Speed alone is not the selling point, because brute force is cheap at small $N$.

Core Claim

Suppose the cohort has $n_1$ positives and $n_0$ negatives, and the held-out point $i$ is positive. The fractional-rebalancing fold uses training weights

$$w_i = 0,\qquad w_j = 1 \ \text{for other positives},\qquad w_j = 1 - \tfrac{1}{n_1}\ \text{for negatives}.$$

This restores the training class ratio to $n_1/n_0$ exactly. The symmetric rule applies when $i$ is negative.

Two facts make this useful. First, to first order, this weight change equals the average over all possible RLOOCV partners when classes are balanced, and it is a closely related deterministic version otherwise. So fractional rebalancing estimates what RLOOCV is trying to estimate, but without its sampling noise. Second, the IJ gives a closed-form estimate of the fold's parameters:

$$\hat\theta_{-i}^{\mathrm{frac}} \approx \hat\theta - H^{-1}\Big(-\nabla\ell_i - \tfrac{1}{n_1}\textstyle\sum_{j:y_j=0}\nabla\ell_j\Big).$$

Here $\hat\theta$ is the full-data fit, $H$ is the full-data Hessian of the regularized objective, and $\nabla\ell_j$ is the gradient of sample $j$'s loss at $\hat\theta$. The class-sum term is shared by all folds with a positive held-out point. The whole procedure therefore costs one Hessian factorization plus $N+2$ solves per hyperparameter value.

We claim three things. On null data this estimator returns auROC near 0.5. On simulations with known truth, it selects regularization strength at least as well as averaged RLOOCV. And its approximation error is small compared with the roughly ±15% statistical uncertainty at $N=30$ documented by Cross-validation failure: Small sample sizes lead to large error bars.

Research Program

Exact estimator. The first piece is the estimator itself, computed exactly by weighted refitting. This exact version is the ground truth for everything else. It also lets us separate two questions: whether fractional rebalancing is a better estimator, and whether the approximation is faithful to it.

Approximation strategies. The second piece compares ways of computing each fold that differ in which part of the method they borrow:

For $\ell_1$-penalized models we use proximal ACV from Approximate Cross-validation: Guarantees for Model Assessment and Selection. That method expands only the smooth loss and keeps the penalty inside a proximal step. Its $O(1/N^2)$ guarantee is stated for ordinary leave-one-out, and its authors report degradation at small $\lambda$.

Where the approximation is weakest. Our perturbation is larger than a single-point removal, because it moves the opposite class's total weight by about $n_0/n_1$ samples. So we expect higher-order terms to matter most at $N\le 30$ with weak regularization. We will measure this regime directly rather than assume it away.

Sparse models. Approximate Cross-Validation in High Dimensions with Guarantees makes Lasso approximation tractable by assuming the selected features do not change when one point is dropped. That assumption was validated only at $N=536$. Fractional reweighting changes every training weight a little, rather than one weight entirely, so it may disturb the selected feature set less than dropping a whole partner. We will measure how often the support flips under exact refits, and test whether this is true.

Uncertainty. As a secondary output, we use the same per-fold quantities to compute IJ-based uncertainty for the cross-validation estimate. We then check whether it corrects the 2–4× underestimation of fold-based standard errors reported in Cross-validation failure: Small sample sizes lead to large error bars.

Scope. The setting is regularized logistic regression on fixed features. This is the model class where small-cohort practitioners actually tune $\lambda$, and where the bias was demonstrated. Deep pipelines such as DiffMDD from DiffMDD: A Diffusion-Based Deep Learning Framework for MDD Diagnosis Using EEG motivate the problem, but they fall outside our theory. We do not claim results for them.

Baselines

Plain leave-one-out (the naive reference). This is ordinary exact LOOCV, run on the same features with the same $\lambda$ grid. It is the procedure most small-cohort papers report. The source paper documents its null auROC collapse, with a median near 0.25 on synthetic noise. Beating it means a null auROC near 0.5 and a lower excess risk of the selected $\lambda$.

Exact RLOOCV (the strongest existing method). This is the method of Distributional bias compromises leave-one-out cross-validation. On their 49 UCI datasets it raised median measured auROC from 0.74 to 0.81, and on synthetic null data it restored the expected 0.5. We run it two ways: with a single random partner over several seeds, which is how it is used, and averaged over all partners, its best-case form at $N^2$ cost. Both use the same grid and the same solver tolerance as our method.

Note that 0.81 is a measured cross-validation auROC, not true generalization. Higher is not automatically better. We therefore judge every method against held-out or simulated truth. Beating RLOOCV means three things: matching its null calibration, achieving equal or lower error against true auROC at $N<20$ (where its discarded sample should hurt), and having zero seed variance. Each must hold at a fraction of the cost of the all-partner average.

Stratified K-fold. We run stratified 5-fold and 10-fold cross-validation on identical folds of data. This is what a reviewer would tell practitioners to use. The source paper reports that stratification does not fully remove the bias when class counts do not divide evenly.

Exact fractional rebalancing. This is our estimator computed by explicit weighted refits. It isolates estimator quality from approximation quality.

Intercept-only recentering (key ablation). Here we refit only the intercept on each fold, or equivalently shift each prediction by the change in the training-set log-odds. This tests whether full reweighting buys anything over a cheaper fix.

Ordinary LOO approximated by IJ. Plain LOO computed with the same approximation as our method. This shows that the rebalancing, not the approximation, removes the bias.

Why not just…?

Why not just brute-force RLOOCV, since $N$ is small? For a single fit at $N=45$, this is a real threat, and we concede it: the speed of our method is irrelevant there. The case rests on three other things. RLOOCV with one random partner gives a different answer for every seed, and the all-partner average costs $N^2$ refits for each grid point and pipeline variant. Our estimator also never discards a patient. The experiments compare against the all-partner average directly. If it matches our estimator in accuracy and the practical cost gap is negligible on realistic grids, the contribution reduces to the deterministic estimator alone, and we will say so.

Why not just use stratified K-fold? Stratified K-fold trains on 80–90% of an already tiny cohort. The source paper also reports that stratification incompletely corrects the bias under uneven class counts. We include it on identical data. Its null auROC and its $\lambda$ selection against simulated truth will show whether that concern matters in practice.

Why not just recenter the predictions? This is the most dangerous alternative, because the bias acts mainly through the training mean. It may be enough when an unpenalized intercept absorbs the shift. It may fall short when shrinkage spreads the shift across correlated features, or when the intercept is penalized. The ablation tests exactly this. If recentering matches fractional rebalancing on null calibration and $\lambda$ selection, we will recommend recentering and drop the reweighting claim.

Why not just use AIC or BIC? These classical scores need a well-defined count of effective parameters. With $\ell_1$ penalties and more features than samples, that count is unreliable, which is the setting Approximate Cross-validation: Guarantees for Model Assessment and Selection targets. We report AIC-selected $\lambda$ in the simulations as a cheap reference only.

Proposed Experiments

Simulations. We follow the Gaussian simulation of Cross-validation failure: Small sample sizes lead to large error bars at $N\in\{12, 20, 30, 50, 100\}$, with both null and true effects, varying class imbalance, and dimensions from 20 up to well above $N$. Truth comes from a large independent test draw. We measure:

  • null auROC distribution;
  • absolute error between each estimate and true auROC;
  • excess risk of the selected $\lambda$;
  • disagreement between approximate and exact fractional folds, in parameters and in auROC;
  • seed variance;
  • wall-clock time.

Real data. We use the 49 UCI benchmarks of the RLOOCV paper, subsampled to small $N$ so that the remaining data serve as a test set. We also use cohorts that are genuinely small: Mumtaz2016 EEG ($N=64$) and Arizona2020 EEG ($N=42$) with fixed spectral features and a linear model, the Kaggle MLSP 2014 schizophrenia data, and Haxby fMRI. On these we report label-permutation null calibration and the IJ-based uncertainty against bootstrap-on-holdout truth where a holdout exists. For approximation cost and accuracy at larger scale, the reference points are the reported 14–27× speedups and errors below 2% for ProxACV in Approximate Cross-validation: Guarantees for Model Assessment and Selection. No reported result was found on Lacuna for any ACV method at $N<100$.

Decisive checks. The proposal succeeds if four conditions all hold:

  1. On null data, the approximate fractional estimator's median auROC lies within the permutation band around 0.5 at every $N$.
  2. At $N\le 20$, its error against true auROC is no worse than all-partner RLOOCV, and preferably better.
  3. Its gap from exact fractional refits is under one tenth of RLOOCV's seed standard deviation.
  4. It beats intercept recentering on $\lambda$ selection in at least the penalized-intercept and correlated-feature settings.

Any of three outcomes would sharpen or kill the idea. If first-order IJ fails condition 3 at $N=12$ but the Newton step or second-order correction passes, we have identified where higher-order corrections become necessary. If recentering ties on condition 4, the reweighting claim is dropped in favour of recentering. If condition 2 fails, the extra sample that RLOOCV discards was not costing it anything.