Predictive inference is free with the jackknife+-after-bootstrap

Byol Kim, Chen Xu, Rina Foygel BarberNeurIPS 2020 · OpenReview

Introduction

Ensemble learning methods, such as bagging and Random Forests, are staples of modern machine learning because they significantly improve predictive accuracy and stability. However, quantifying uncertainty for these models—specifically, creating a predictive interval guaranteed to contain a new data point with high probability—is notoriously difficult and computationally expensive.

This paper introduces the Jackknife+-after-bootstrap (J+aB), a method that provides robust, distribution-free predictive intervals using only the models already trained during the standard bootstrapping process. By leveraging "out-of-bag" samples, the authors provide a way to get valid statistical inference essentially for "free," bypassing the need for prohibitive retraining.

The Problem: The Cost of Assumption-Lean Inference

Existing techniques like Conformal Prediction or the Jackknife+ provide rigorous coverage guarantees without assuming the data follows a specific distribution (e.g., Gaussian). The catch is their computational cost: they typically require retraining the model many times, often once for every single data point in the training set.

If you are training an ensemble of 100 neural networks on a large dataset of size $n$, a naive application of the Jackknife+ to the ensemble would require $B \times n$ model fits. For large datasets or complex models, this is computationally impossible. The authors sought a way to provide the same rigorous guarantees as the Jackknife+ but at the computational cost of a single ensemble training run.

Computational Cost Comparison

As shown in the table above, the J+aB requires only $B$ calls to the regression algorithm $\mathcal{R}$ (the same as a standard ensemble), whereas the standard Jackknife+ with an ensemble requires $Bn$ fits. This makes rigorous inference accessible even for computationally heavy deep learning ensembles.

The J+aB Approach

The core innovation of the J+aB algorithm builds on two existing ideas:

  1. The Jackknife+: A method that uses leave-one-out residuals to build predictive intervals.
  2. Out-of-Bag (OOB) Estimates: In a bootstrap ensemble, each model is trained on a random subset of the data. For any specific training point $i$, there is a subset of models in the ensemble that never "saw" that point during training.

Instead of retraining new models to see how the ensemble behaves without point $i$, J+aB simply looks at the existing models where point $i$ was "out-of-bag." It aggregates only those models to create a "leave-one-out" prediction for point $i$. By calculating residuals from these OOB predictions, the algorithm constructs a predictive interval.

The authors prove that this interval provides a coverage guarantee of at least $1 - 2\alpha$ (where $1 - \alpha$ is the target) under the sole assumption that the data points are independent and identically distributed (i.i.d.). To make the math work for a rigorous proof, they introduce a clever theoretical "twist": the total number of models $B$ is treated as a random variable (specifically Binomial) to ensure the symmetry required for the theoretical guarantee.

Experiments and Key Results

The authors evaluated J+aB using three real-world datasets—Communities and Crime, BlogFeedback, and the Medical Expenditure Panel Survey (MEPS)—across three different base learners: Ridge Regression, Random Forests (RF), and Neural Networks (NN).

Empirical Coverage Results
  • Empirical Coverage: Across all datasets and models, J+aB consistently achieved empirical coverage near the 90% target (indicated by the solid black line at 0.9), despite the theoretical lower bound being more conservative ($1 - 2\alpha$).
  • Efficiency vs. Accuracy: J+aB performed nearly identically to the "gold standard" but computationally expensive J+ ENSEMBLE method in terms of coverage and interval width.
  • Benefit of Ensembling: The results confirmed that for unstable learners like Neural Networks or Random Forests, the ensembled intervals (both J+ ENSEMBLE and J+aB) were significantly more stable and precise than non-ensembled intervals (J+ NON-ENSEMBLE), proving that ensembling helps both the point prediction and the uncertainty estimate.

Limitations and Future Work

While J+aB offers a massive computational advantage, it does come with a few limitations:

  • Conservative Bounds: The theoretical guarantee ($1 - 2\alpha$) is more conservative than the empirical performance (which reliably hits $1 - \alpha$). Closing this gap theoretically remains an open challenge.
  • Sample Size Requirements: For J+aB to work, $B$ must be large enough so that every training point is "out-of-bag" for at least one model. If $B$ is too small, the OOB aggregates cannot be formed.
  • Aggregation Functions: The study primarily focused on the "mean" as the aggregation function. Future work could explore how different aggregation methods (like the median or trimmed mean) affect the stability and width of the intervals.

Ultimately, the Jackknife+-after-bootstrap demonstrates that robust, distribution-free predictive inference does not have to come at the cost of computational paralysis, offering a practical "free lunch" for practitioners using ensemble methods.

Summary updated

Abstract

Ensemble learning is widely used in applications to make predictions in complex decision problems---for example, averaging models fitted to a sequence of samples bootstrapped from the available training data. While such methods offer more accurate, stable, and robust predictions and model estimates, much less is known about how to perform valid, assumption-lean inference on the output of these types of procedures. In this paper, we propose the jackknife+-after-bootstrap (J+aB), a procedure for constructing a predictive interval, which uses only the available bootstrapped samples and their corresponding fitted models, and is therefore "free" in terms of the cost of model fitting. The J+aB offers a predictive coverage guarantee that holds with no assumptions on the distribution of the data, the nature of the fitted model, or the way in which the ensemble of models are aggregated---at worst, the failure rate of the predictive interval is inflated by a factor of 2. Our numerical experiments verify the coverage and accuracy of the resulting predictive intervals on real data.
BibTeX
@inproceedings{kim2020predictive,
  author = {Byol Kim and Chen Xu and Rina Foygel Barber},
  title = {{Predictive inference is free with the jackknife+-after-bootstrap}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=JY-2Y243NBg},
}
Figure