Simultaneous Confidence Bands for Cross-Validation Curves at the Cost of One Fit per Setting

When practitioners tune a regularization strength by cross-validation, they look at a curve: estimated error for each of dozens of settings. They then pick the lowest point and report its value as the model's expected error. That reported number has two problems. The first is that it is optimistic, because the minimum of many noisy estimates is biased low. The second is that its error bar is too narrow, because the folds share most of their training data. These are the multiple-comparisons problem and the cross-validation fold-correlation problem. Both are well studied separately. Fixing them together is either expensive, through nested or repeated cross-validation with full refits, or limited to special cases. Exact selective inference (p-values computed conditional on which model was picked) covers only linear models with Gaussian noise.

We propose to compute one object cheaply: an estimated influence matrix. It records how much each data point moves the cross-validation estimate at each candidate setting. It includes both the point's direct effect as a held-out example and its indirect effect as a training point shared across folds. The indirect effect comes from approximate cross-validation, which uses a one-time Hessian, a matrix of second derivatives of the training loss. From this matrix we draw a Gaussian multiplier bootstrap of the maximum standardized deviation along the whole curve. The result is a confidence band that holds simultaneously for every setting, so it remains valid for whichever setting is chosen. Because neighbouring settings are highly correlated, the band should be far narrower than a Bonferroni correction while keeping coverage that naive fold-based error bars lose.

Core Claim

For regularized empirical risk minimizers fit along a hyperparameter path, a band built from approximate-cross-validation influence estimates gives valid simultaneous coverage. That coverage carries over to the error of the selected configuration. The total cost is roughly one fit per configuration plus one Hessian factorization, not $K$ or $n$ refits.

The new ingredient is the explicit training-overlap term. Write $\hat R_j$ for the $K$-fold estimate at configuration $j$ and $R_j$ for its target. We take the target to be the expected test error of the model trained at $j$, checked against a large untouched holdout. We use the linearization

$$\hat R_j - R_j \approx \frac{1}{n}\sum_{i=1}^n \Big[\underbrace{\ell_j(z_i) - \bar\ell_j}_{\text{held-out effect}} \;+\; \underbrace{g_{j,-k(i)}^\top H_{j}^{-1}\nabla \ell_j(z_i)}_{\text{effect as a training point}}\Big] \equiv \frac1n\sum_i \psi_{ij}.$$

Here $\ell_j(z_i)$ is point $i$'s loss under setting $j$, and $\bar\ell_j$ is its mean. $H_j$ is the training-loss Hessian. $g_{j,-k(i)}$ is the average held-out loss gradient over the folds in which point $i$ was a training point. Under loss stability the second term vanishes asymptotically. That is why Cross-validation Confidence Intervals for Test Error can ignore it. In finite samples, this term is the between-fold covariance $\gamma$ that No Unbiased Estimator of the Variance of K-Fold Cross-Validation proved cannot be estimated without assumptions. We do not contradict that no-go result. We supply the assumption it says is necessary, smoothness of the fitted model, and spend it through the Hessian. The simultaneous band is $\hat R_j \pm c_\alpha \hat s_j$. Here $\hat s_j$ is the column standard deviation of $\psi$ divided by $\sqrt n$, and $c_\alpha$ is the $(1-\alpha)$ quantile of $\max_j |\sum_i \xi_i \psi_{ij}| / (n \hat s_j)$ over Gaussian multipliers $\xi_i$.

Research Program

The method reuses existing approximation machinery. The Hessian-based leave-out shift comes from A Swiss Army Infinitesimal Jackknife. That paper computes one Hessian and then approximates arbitrary leave-out refits by linear solves. For L1 penalties and graphical lasso we use the proximal variant from Approximate Cross-validation: Guarantees for Model Assessment and Selection. That work showed approximation error of order $1/n^2$ uniformly along the path and 14x to 27x speedups, but it attached no uncertainty or selection correction to its choices. When the inner solver is stopped early, we use Iterative Approximate Cross-Validation, which tracks leave-out iterates along gradient descent. These papers supply the method. None of them builds intervals.

The theoretical work has two parts. The first proves that the approximation error of the influence-based matrix enters the band's coverage at higher order than the sampling noise. This is the open question in the file's Gap 1: whether approximate refits silently bias the fold-covariance estimate. The second is a Gaussian approximation for the maximum over a correlated path, in which the effective number of comparisons depends on the correlation decay across settings rather than on the grid size.

We also build a diagnostic, because curvature collapse is the known failure mode. Multiple-Comparison Testing for Cross-Validation Path Optimization Benchmarks: A Hessian-Mismatch Diagnostic for Holm--Bonferroni Failure Modes traced its significant results on Adult and Covertype to a degenerate, saturated Hessian. Its cheap early proxy had a 100% false-positive rate. We will flag settings where $H_j$'s smallest eigenvalue, estimated by a few Lanczos iterations, falls below a threshold. At flagged settings we fall back to a small number of exact refits. We will report how often this happens.

The scope is regularized generalized linear models, kernel ridge and kernel logistic regression, and graphical lasso. Deep networks and trees lack the smoothness the Hessian step needs, and we will not claim them.

Baselines

The naive reference point is the standard error computed across $K$ fold scores, applied pointwise with no multiplicity correction. Inference for the Generalization Error showed that the related resampled t-test is "dangerously liberal" well above its nominal 10% level. Cross-Validation: What Does It Estimate and How Well Does It Do It? reports nominal 90% naive intervals dropping to 70% coverage. We expect it to undercover pointwise and much worse at the selected point.

The strongest pointwise competitor is the all-pairs variance estimator of Cross-validation Confidence Intervals for Test Error. That paper reports nominal 95% coverage on Higgs and FlightDelays with the narrowest intervals among valid methods, and concentration-inequality intervals over 90 times wider. We apply it two ways: pointwise, and with a Bonferroni correction over the $M$ settings. This gives a strong, simple selection-valid comparator.

The strongest selection-aware competitor is nested cross-validation as in Cross-Validation: What Does It Estimate and How Well Does It Do It?, which restored roughly nominal coverage at an order of magnitude more fits. We run it with exact refits. We also run it with the inner loop replaced by approximate cross-validation, so its compute matches ours.

On the linear-Gaussian global-null setting ($n=50$, $p=100$) we include Selective inference after cross-validation, whose conditioned p-values were exactly uniform.

Fairness requires the same pieces across every method: the same splits, the same hyperparameter grid, the same Hessian, and the same wall-clock budget. Ground truth is the error on a large untouched holdout.

Two ablations isolate the key ingredients. One drops the training-overlap term, which reduces our method to a joint version of Bayle et al. The other replaces the max-bootstrap with Bonferroni over the same $\hat s_j$.

Beating the baselines means the following. Our band must match the coverage of Bonferroni-on-Bayle at the selected setting while being clearly narrower. It must match nested cross-validation's coverage at a fraction of its exact-refit cost. Selection-adjusted coverage at the chosen setting has no reported result on Lacuna for any of these benchmarks, so the baseline numbers will come from our own runs.

Why not just…?

Why not just use a corrected resampled t-test with Holm or Bonferroni over the grid? This is the honest default. Nadeau and Bengio's correction handles overlap with a fixed ratio $n_2/n_1$, and Holm handles multiplicity. It treats dozens of nearly identical settings as separate hypotheses, so it pays for $M$ comparisons when the effective number may be three or four. The fixed ratio also ignores how stable each setting actually is. If the max-bootstrap band is not clearly narrower than this on smooth paths, the joint-covariance idea has failed. The Bonferroni ablation tests exactly this.

Why not just run nested cross-validation? Nested cross-validation is a real threat. It directly estimates the error of "tune, then refit." With approximate inner loops it could also be cheap. Two concerns remain. Its own interval still needs a fold-correlation correction. And Estimating the Maximum Expected Value: An Analysis of (Nested) Cross Validation and the Maximum Sample Average found cross-validation-based maximum estimates so variable that the plain biased maximum sometimes had lower mean squared error. We run the compute-matched approximate nested variant. If it matches our coverage and width, we will report that the band adds only the per-setting picture, not better inference.

Why not just hold out a fresh test set? A fresh test set removes both problems at the price of data. We Need to Talk about Standard Splits and A Honest Cross-Validation Estimator for Prediction Performance document how unstable single splits are at small $n$; on Bike Sharing at $n=80$, the naive split error was 2050 versus 1925 for shrinkage. We include a holdout using the same number of examples as a reference. We expect it to give valid but wider intervals in the small-$n$ regimes where cross-validation is used at all.

Proposed Experiments

The first experiment is a coverage study against large-holdout ground truth. We subsample small training sets from HIGGS, Covertype, Adult and Bike Sharing, at sizes from 80 to 5,000, and repeat 500 times. Each repetition fits L2- and L1-logistic or ridge paths over 50 settings. We record pointwise coverage, simultaneous coverage, coverage at the selected setting, band width and fits used.

The second experiment uses the graphical lasso gene-expression sets (Leukemia, Lymph, Arabidopsis). Ground truth there comes from expensive exact repeated cross-validation, and we test whether the speedups reported for proximal approximate cross-validation survive once intervals are added.

The third experiment uses the kernel regression collection from Fast cross-validation via sequential testing (bank, kin, pumadyn). For kernel ridge, exact leave-out formulas give a clean check of the approximation term.

The decisive checks come next. The ablation without the training-overlap term should undercover at small $n$ and converge to our method as $n$ grows, which is the direct empirical signature of $\gamma$. The curvature diagnostic should predict, before inference, the settings where coverage breaks. We expect these at small regularization and on saturated data like Covertype, where Yu and Deng measured a mismatch index near $10^{-3}$.

Finally, we redo Yu and Deng's 11-dataset solver comparison, replacing paired t-tests with our joint intervals. We report which of their two surviving rejections persist. A negative outcome would also be informative: coverage that fails even where the Hessian is well conditioned would mean the linearization, not the curvature, is the bottleneck.