PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive inference with the jackknife+

Rina Foygel Barber, Emmanuel J. Candes, Aaditya Ramdas, Ryan J. Tibshirani

arXiv:1905.02928v3stat.ME

TL;DR

Predictive intervals need reliable coverage without restrictive assumptions, but the original jackknife can fail when regression is unstable. The paper introduces the jackknife+, which uses leave-one-out test-point predictions and proves worst-case coverage of 1−2α under exchangeability, while typically matching jackknife performance.

  • Problem

    The original jackknife lacks universal predictive-coverage guarantees and may under-cover when the fitted regression algorithm is unstable.

  • Method

    The jackknife+ augments leave-one-out residuals with leave-one-out predictions at the test point to account for fitted-function variability under exchangeability.

  • Results

    The jackknife+ guarantees at least 1−2α coverage in the worst case and empirically achieves approximately 1−α coverage with intervals similar in width to the jackknife.

  • Takeaways & Limitations

    The jackknife+ is recommended as a practical alternative because it retains near-target empirical performance while providing coverage guarantees without stability assumptions.

  • Takeaways & Limitations

    The original jackknife can lose predictive coverage for unstable regression algorithms, including least squares when the sample size is close to the dimension.

Abstract

from arXiv · show

This paper introduces the jackknife+, which is a novel method for constructing predictive confidence intervals. Whereas the jackknife outputs an interval centered at the predicted response of a test point, with the width of the interval determined by the quantiles of leave-one-out residuals, the jackknife+ also uses the leave-one-out predictions at the test point to account for the variability in the fitted regression function. Assuming exchangeable training samples, we prove that this crucial modification permits rigorous coverage guarantees regardless of the distribution of the data points, for any algorithm that treats the training points symmetrically. Such guarantees are not possible for the original jackknife and we demonstrate examples where the coverage rate may actually vanish. Our theoretical and empirical analysis reveals that the jackknife and the jackknife+ intervals achieve nearly exact coverage and have similar lengths whenever the fitting algorithm obeys some form of stability. Further, we extend the jackknife+ to K-fold cross validation and similarly establish rigorous coverage properties. Our methods are related to cross-conformal prediction proposed by Vovk [2015] and we discuss connections.

1 Introduction

The paper introduces jackknife+, a prediction-interval method with nonasymptotic coverage guarantees under exchangeability, addressing the original jackknife’s lack of universal guarantees. In worst cases, jackknife+ guarantees at least 1−2α coverage, while empirically the two methods often produce nearly identical intervals with coverage near 1−α.

  • Problem: Prediction intervals target probability 1−α of containing a new response while accounting for randomness in both the training data and test point.The interval is constructed around the fitted prediction for a new feature vector.
  • Motivation: Naive intervals based on training residuals typically undercover because overfitting makes those residuals smaller than errors on an unseen test point.This motivates leave-one-out residuals, which better reflect prediction after fitting on nearly the full sample.
  • Original jackknife: The original jackknife uses leave-one-out fits and residual quantiles to avoid overfitting, but lacks universal theoretical guarantees and can lose coverage for unstable algorithms.The paper notes that simulations can show extremely poor coverage for least-squares regression.
  • Contribution: Jackknife+ provides nonasymptotic coverage guarantees under exchangeability alone, with worst-case coverage of 1−2α versus possible zero coverage for the original jackknife.The guarantee applies without assumptions beyond exchangeability of the training and test data.
  • Jackknife+: Jackknife+ extends the jackknife by using leave-one-out predictions at the test point to account for variability in the fitted regression function.The method is presented as closely related to cross-conformal prediction proposed by Vovk [2015].

2 The jackknife+

The jackknife+ modifies the jackknife by centering intervals on leave-one-out test-point predictions, yielding assumption-free predictive coverage of 1−2α under exchangeability. It often matches the jackknife in practice, but retains coverage when instability causes the original jackknife to fail; jackknife-minmax restores 1−α coverage conservatively.

  • 2 The jackknife+: Jackknife+ uses leave-one-out predictions at the test point rather than the full-data prediction to account for fitted-function variability.Both methods use leave-one-out residuals, but jackknife+ centers the construction using bµ−i(Xn+1).
  • 2 The jackknife+: In practice, jackknife and jackknife+ often achieve coverage near 1−α and have nearly identical performance, but instability can make jackknife lose coverage while jackknife+ reaches the target.The intervals are expected to be similar when leave-one-out fits resemble the full-data fit, and can differ substantially when removing one point changes predictions.
  • 2 The jackknife+: The jackknife+ guarantees predictive coverage at least 1−2α without assumptions on the data distribution or regression algorithm, under exchangeable data and an order-invariant method.The theorem is stated for i.i.d. data as a special case of exchangeability, with n ≥ 2 and fixed α.
  • 2 The jackknife+: Pathological examples show the 1−2α guarantee cannot generally be improved, while no coverage guarantee is possible for the original jackknife without additional assumptions.The paper also constructs examples with vanishing coverage for jackknife+ and zero coverage for the naive method.
  • 2 The jackknife+: Jackknife-minmax removes the factor of 2 and always achieves target coverage without assumptions, but is generally too conservative in practice.It is strictly more conservative than jackknife+ for every data set.

3 CV+ for K-fold cross-validation

CV+ extends jackknife+ to K-fold cross-validation, reducing computation while preserving near-jackknife+ worst-case coverage guarantees. The section also compares CV+ with split conformal, cross-conformal, and full conformal prediction in terms of coverage, variance, interval structure, and computational cost.

  • 3 CV+ for K-fold cross-validation: K-fold CV+ requires K fitted models instead of n, but smaller training folds can produce slightly wider intervals than jackknife+.Jackknife+ is the special case K = n; CV+ models use n(1 − 1/K) training observations.
  • 3 CV+ for K-fold cross-validation: Compared with split conformal’s assumption-free 1 − α coverage, CV+ averages across all K splits to reduce variance but has a weaker theoretical guarantee.Split conformal uses one held-out subset, creating higher variance from the single split.
  • 3 CV+ for K-fold cross-validation: CV+ and symmetric cross-conformal can sometimes agree, but cross-conformal may return a disjoint union of intervals whereas CV+ always returns one interval.The proofs also establish 1 − 2α − 2/n coverage for K-fold cross-conformal at any K, with coverage at least 1 − 2α when K = n.
  • 3 CV+ for K-fold cross-validation: CV+ achieves coverage at least 1 − 2α − 2/n uniformly over every choice of K, extending meaningful guarantees to large K.The result combines the small-K bound, essentially 1 − 2α, with the new large-K guarantee, including K = n.
  • 3 CV+ for K-fold cross-validation: Full conformal prediction attains target-level coverage by exchangeability but is generally prohibitively expensive because it retrains for every test feature vector and candidate response.Special computational shortcuts exist for some models, including linear regression, ridge regression, and the Lasso.

4 Summary of coverage guarantees and computational costs

The jackknife+ is recommended because it combines nearly the jackknife’s empirical performance with rigorous ≥1 −2α coverage guarantees. Its main computational cost is n model fits, although K-fold and split methods reduce training cost.

  • Practical recommendation: The authors recommend jackknife+ because its intervals are nearly as wide and accurate as jackknife intervals while avoiding jackknife’s lack of guarantee.This empirical equivalence assumes pathological examples are avoided; both methods achieve close to the target 1 −α coverage level.
  • Computational costs: Jackknife+ requires n model-training runs, compared with one for naive and split conformal, K for K-fold methods, and ntest · ngrid for full conformal.Training cost counts runs of the regression algorithm A on datasets of size up to n.
  • Computational costs: For ntest test points, jackknife+ has model-evaluation cost ntest · n, whereas naive and jackknife-minmax use n + ntest and K-fold CV+ uses n + ntest · K.The table reports computational costs while ignoring constants.
  • Implementation considerations: Leave-one-out residuals may sometimes be computed without n refits by reweighting training residuals or exploiting random-forest structure.Examples include ordinary least squares, kernel ridge regression, kernel smoothing, thin plate splines, smoothing splines, and random forests.

5 Guarantees under stability assumptions

Stability assumptions sharpen coverage guarantees: out-of-sample stability supports near-target coverage for inflated jackknife intervals, while combining in-sample and out-of-sample stability also validates the naive interval. The distinction matters because in-sample stability controls removal of the evaluated training point, whereas out-of-sample stability concerns an independent test point.

  • In-sample stability: In-sample stability differs fundamentally from out-of-sample stability: it controls deleting the point being evaluated, whereas out-of-sample stability controls deleting a training point when predicting an independent test point.Under in-sample stability, ε inflation is effectively assumed sufficient to correct overfitting, enabling the naive interval’s coverage result when out-of-sample stability also holds.
  • Coverage guarantees: With both in-sample and out-of-sample stability, the naive interval, jackknife, jackknife+, and jackknife-minmax achieve approximately 1 − α coverage, while jackknife+ and jackknife-minmax retain guarantees without stability.The summary table reports jackknife+ coverage of 1 − 2α without stability and approximately 1 − α under either stability condition; jackknife-minmax reports 1 − α throughout.
  • Out-of-sample stability: Out-of-sample stability is sufficient for the ε-inflated jackknife and 2ε-inflated jackknife+ intervals to achieve the target coverage guarantee.The different inflation amounts are an artifact of the particular stability definition, not a meaningful difference between the methods.
  • Out-of-sample stability: If Y|X has bounded conditional density, the inflated-interval results imply that the non-inflated jackknife and jackknife+ intervals achieve coverage close to target.Bounded density limits the probability mass added by interval inflation.
  • Example: K-nearest neighbors: For K-nearest neighbors, out-of-sample stability holds with ε = 0 and ν = K/n, yielding a jackknife+ coverage lower bound without assumptions on the data distribution or prediction accuracy.The argument uses exchangeability; analogous in-sample stability generally fails because each training point is its own nearest neighbor.

6 Proof of Theorem 1

The proof bounds jackknife+ failure by identifying “strange” points through pairwise residual comparisons. A deterministic tournament bound, exchangeability, and the link between noncoverage and strangeness yield the coverage guarantee.

  • Proof setup: The comparison matrix marks when point i has a larger leave-two-out residual than point j, and strange points win at least a (1−α) fraction of comparisons.This construction is also examined by Vovk [2015, Appendix A] in analyzing failures of leave-one-out conformal methods.
  • Step 1: bounding the number of strange points: Step 1 proves deterministically that the number of strange points is less than 2α(n+1), using a tournament-style counting argument.Each strange point can lose to at most α(n+1)−1 other strange points; counting losing pairs gives the bound, following Landau’s theorem for tournaments.
  • Step 2: exchangeability of the data points: Step 2 uses exchangeability and order-invariance of the fitting algorithm to show that the test point is strange with probability at most 2α.All indices are equally likely to be strange, so the probability for the test point is bounded by the fraction of strange points; this uses the same exchangeability reasoning as conformal prediction.
  • Step 3: connecting to jackknife+: Step 3 shows that jackknife+ noncoverage implies the test point is strange, so the noncoverage probability is at most 2α.If Yn+1 falls outside the jackknife+ interval for sufficiently many indices, the defining residual comparisons place n+1 in S(A).

7 Empirical results

Across simulated and real data, jackknife+ maintains target coverage under unstable regression settings, while jackknife can substantially under-cover; under greater stability, the two methods have similar coverage and widths. Naive intervals under-cover, jackknife-minmax is conservative, and split conformal also maintains coverage in the simulation.

  • Experimental setup: The study compares seven prediction-interval methods on simulated and real data using least squares, ridge regression, random forests, and neural networks.The real-data experiments randomly sample n = 200 training points, with the remaining observations forming the test set.
  • Simulation: When d ≈ n, jackknife coverage falls to around 0.5, whereas jackknife+ continues reaching the target level at the cost of wider intervals.For d < n, jackknife and jackknife+ have nearly identical coverage and widths; instability in least squares drives the divergence near d = n.
  • Simulation: Naive intervals increasingly under-cover as d grows, jackknife-minmax is over-conservative, and full conformal has infinite intervals when d > n.For d ≥ n, naive intervals have zero width and zero coverage; full conformal coverage is one deterministically before practical truncation.
  • Simulation: In simulations, jackknife+ and split conformal are the only methods maintaining the 0.9 target coverage throughout without systematic under- or over-coverage.Figure 2 compares coverage and interval width across all methods over 50 independent trials.
  • Real-data experiments: On three real datasets, jackknife and jackknife+ achieve empirical coverage extremely close to 90% with very similar interval widths.Jackknife+ is slightly higher-coverage and wider in settings with more unstable regression methods.

8 Summary

The jackknife+ differs from the jackknife by using shifts based on leave-one-out predictions to account for possible algorithm instability. Under exchangeable samples, this yields rigorous coverage guarantees and supports jackknife+ as a practical choice, with K-fold CV+ as an alternative when computation is prohibitive.

  • The jackknife+ applies prediction shifts to account for possible algorithm instability.
  • Under exchangeable samples, the jackknife+ provides rigorous coverage guarantees without additional assumptions.
  • Empirical performance on real data makes the jackknife+ a better practical choice than the jackknife.
  • K-fold CV+ offers an attractive alternative when the jackknife+ is computationally prohibitive.

A Asymmetric jackknife+ and CV+ … B.2 Proofs for the CV+ method

The paper extends jackknife+, jackknife-minmax, and CV+ to asymmetric residual constructions while retaining coverage guarantees, and proves jackknife-minmax coverage through a modified comparison-matrix argument. It also introduces the proof framework connecting CV+ with cross-conformal prediction.

  • A Asymmetric jackknife+ and CV+: Asymmetric jackknife+ allocates total miscoverage α between right and left tails using separate signed-residual constructions for potentially skewed noise.The parameters satisfy α+ + α− = α, with α+ and α− controlling the respective tails.
  • A Asymmetric jackknife+ and CV+: Even with α− = α+ = α/2, asymmetric intervals need not equal the original methods because signed-residual distributions can remain asymmetric by chance.An asymmetric jackknife was previously considered by Steinberger and Leeb [2018], and analogous asymmetric jackknife-minmax and CV+ constructions are defined.
  • A Asymmetric jackknife+ and CV+: All coverage guarantees proved for the symmetric methods also hold for their asymmetric counterparts, including 1−2α coverage for asymmetric jackknife+ under the assumption-free setting.The proof uses separate residual matrices to bound right-tail noncoverage by α+ and left-tail noncoverage by α−.
  • B.1 Proof of jackknife-minmax (Theorem 3): The jackknife-minmax proof changes the comparison matrix so that each data point’s smallest residual is compared against the residual obtained when leaving out that point.The proof otherwise follows the three-step structure used for jackknife+: bound strange points, apply exchangeability, and connect strange points to noncoverage.
  • B.1 Proof of jackknife-minmax (Theorem 3): The modified matrix deterministically bounds the number of strange points by α(n + 1), improving the corresponding jackknife+ bound of 2α(n + 1).This bound is obtained from the matrix construction and the definition of the strange-point set S(A).
  • B Additional proofs: Exchangeability then bounds the probability that the test point is strange by α, while the interval can fail to cover only when the test point is strange.Thus the proof connects the deterministic strange-point bound to the jackknife-minmax coverage guarantee.
  • B.2 Proofs for the CV+ method: The CV+ proof section relates CV+ to cross-conformal prediction and establishes the method’s theoretical guarantees.The supplied passage announces these goals without providing the subsequent proof details.

B.2.1 Details for comparing to the cross-conformal method

This section justifies that the cross-conformal prediction set is deterministically contained in the CV+ interval and derives its coverage guarantee from a modified procedure. The modified method achieves coverage at least 1 − 2α, based on rank-based p-values and an arithmetic-mean validity result.

  • Deterministic containment: The cross-conformal prediction set is deterministically contained in the CV+ prediction interval (13).The proof uses monotonicity in the auxiliary parameter τ and order-statistic bounds for leave-fold-out predictions plus residuals.
  • Coverage guarantee: The modified K-fold cross-conformal method has predictive coverage at least 1 − 2α, as implied by Vovk et al. [2018].Vovk et al. [2018] show that the modification yields a 1 − 2α guarantee, using fold-specific p-values.
  • Coverage guarantee: Each fold-specific p-value compares the test residual with the other residuals in that fold, while τ ∼ Unif[0, 1] removes discretization.With the true test value plugged in, the rank-based p-value becomes uniformly distributed on [0, 1].
  • Coverage guarantee: The coverage result follows because an arithmetic mean of p-values is valid up to a factor of 2 for any α ∈ [0, 1], by Vovk and Wang [2012, Corollary 2].Vovk et al. [2018] cite this earlier result to establish the modified method’s coverage guarantee.

B.2.2 Proof of Theorem 4 · B.3 Proof of Theorem 5

Theorem 4’s proof establishes the K-fold coverage guarantee by extending the strange-point argument to fold-structured residual comparisons. Theorem 5 begins by introducing an oracle leave-one-out method with target 1 − α coverage, then relates inflated jackknife methods to it.

  • B.2.2 Proof of Theorem 4: The K-fold proof constructs m = n/K test points, partitions data into folds S_1, …, S_K, and treats the test points as an additional fold S_{K+1}.This setup enables the fold-specific residual and exchangeability argument used for Theorem 4.
  • B.2.2 Proof of Theorem 4: The proof defines fold-deleted regression fits, a residual matrix, and a set of “strange” points whose comparison scores exceed the threshold (1 − α)(n + 1).These objects generalize the corresponding constructions from the proof of Theorem 1.
  • B.2.2 Proof of Theorem 4: The number of strange points is deterministically bounded by 2α(n + m) + (1 − 2α)(m − 1) − 1.The bound follows by accounting for within-fold pairs that do not play comparison games.
  • B.2.2 Proof of Theorem 4: Exchangeability and fold-preserving permutations bound the probability that the test point is strange by 2α + 1 − K/n.Fold structure prevents full permutation invariance, so the proof uses permutations preserving fold membership to equalize the relevant probabilities.
  • B.2.2 Proof of Theorem 4: Noncoverage of the CV+ interval implies that the test point is strange, completing the coverage proof; the argument also yields a stronger statement for the cross-conformal prediction set.The stronger statement says that exclusion from the cross-conformal prediction set implies the test point is strange, and the jackknife+ case corresponds to n = K.
  • B.3 Proof of Theorem 5: Theorem 5 first introduces an oracle leave-one-out method that achieves the target 1 − α coverage rate despite being impossible to implement in practice.The proof then relates the ϵ-inflated jackknife and 2ϵ-inflated jackknife+ to this oracle method.

B.3.1 Oracle method … B.5.1 Proof for jackknife and naive methods

The proofs establish oracle coverage through exchangeability, then transfer it to jackknife and jackknife+ using stability bounds, while constructing pathological examples showing the limits of naive and jackknife intervals. The jackknife+ construction retains coverage in the exhibited counterexample.

  • B.3.1 Oracle method: The oracle method achieves 1 − α′ coverage because its residuals are exchangeable under i.i.d. data and a labeling-invariant algorithm.The test residual has a uniformly random rank among the oracle residuals; ties prevent replacing the first inequality with equality.
  • B.3.2 Bound for the jackknife: The jackknife proof transfers the oracle coverage result by bounding the discrepancy between oracle and jackknife intervals with out-of-sample stability and Markov’s inequality.The argument uses i.i.d. symmetry when swapping a training point with the test point.
  • B.3.3 Bound for the jackknife+: For jackknife+, the proof compares jackknife+ with jackknife at α′ = α + √ν and controls failures at either interval endpoint using stability and Markov’s inequality.A failure requires sufficiently many leave-one-out predictions to differ from the full prediction in the same direction.
  • B.4 Proof of Theorem 6: Theorem 6’s proof compares naive residuals with leave-one-out residuals and uses in-sample stability, Markov’s inequality, and Theorem 5’s coverage result.The comparison is carried out for jackknife run at level 1 − α′, with α′ = α + √ν.
  • B.5 Proof of Theorem 2: Theorem 2 is strengthened by proving coverage lower bounds even for ϵ-inflated versions of the naive and jackknife intervals, for every ϵ > 0.The section constructs pathological examples for both methods.
  • B.5.1 Proof for jackknife and naive methods: The pathological construction uses a regression algorithm returning 0 at training covariates and (1 + ϵ)n elsewhere, with X ∼ N(0, 1) and Y ≡ 0.Distinct covariates occur with probability 1, determining the leave-one-out and naive residual behavior.
  • B.5.1 Proof for jackknife and naive methods: In this example, the jackknife+ interval contains 0 at its left endpoint and therefore maintains coverage.This contrasts with the pathological behavior investigated for the jackknife and naive intervals.

B.5.2 Proof for jackknife+

This section constructs an i.i.d. example showing that jackknife+ coverage can be no higher than approximately 1 − 2α. The proof combines a bad prediction region with concentration bounds to establish the claimed coverage bound.

  • Motivation: The argument is motivated by Vovk’s exchangeable-data example [2015, Appendix A], but requires a more technical construction because the proof works under i.i.d. data.The section contrasts the intuition from that example with the stronger setting required here.
  • Proof idea: The construction makes jackknife+ fail almost surely when the test point lies in a “bad” region, which occurs with probability approximately 2α.Predictions are exact in the complementary “good” region, while systematic underestimation in the bad region causes noncoverage.
  • Formal construction: The formal construction chooses tuning parameters and an i.i.d. data distribution, then defines a regression algorithm whose leave-one-out behavior produces the bad-region failure pattern.The proof specifies the distribution, response scaling, and fitted regression function before bounding the relevant probabilities.
Loading 1905.02928v3…