Distribution-Free Predictive Inference for Regression

Jing LeiMax G'SellAlessandro RinaldoRyan J. TibshiraniLarry Wasserman

article2016Journal of the American Statistical Association1,403 citations

Develops a conformal prediction framework for regression that guarantees finite-sample validity for any base estimator without distributional assumptions, introducing computationally efficient split-conformal algorithms and model-free variable importance metrics.

Listen

Modern decision-making increasingly relies on complex, high-dimensional machine learning and regression algorithms to forecast outcomes. However, standard statistical techniques for quantifying prediction uncertainty typically depend on rigid assumptions—such as correct model specification, normal error distributions, or constant variance—that rarely hold in real-world environments. When these assumptions fail, conventional prediction intervals either under-cover true outcomes or become excessively wide, introducing unquantified risk into critical operations. To resolve this problem, the article develops a general, distribution-free predictive inference framework based on conformal inference that constructs mathematically guaranteed prediction intervals around any regression algorithm without requiring restrictive distributional or model-correctness assumptions.

The article evaluates theoretical guarantees, computational trade-offs, and empirical performance across two primary conformal approaches—full conformal inference and split conformal inference—alongside a related leave-one-out jackknife technique. The analysis establishes finite-sample coverage bounds and proves that conformal prediction bands achieve near-optimal width when base models are stable and consistent. To demonstrate practical utility, the authors conduct extensive simulations spanning low-dimensional and high-dimensional settings (up to 2,000 features), including challenging scenarios with heavy-tailed errors, strong feature correlations, and heteroskedasticity. They benchmark linear regression, penalized models (lasso, elastic net, ridge), sparse additive models, and random forests, while providing an open-source R implementation package.

The findings provide strong support for conformal methodology. First, conformal prediction bands strictly achieve the nominal average coverage (for example, approximately 90% across all evaluated configurations) even when models are severely misspecified, nonlinear, or heavy-tailed, whereas standard parametric methods fail or produce overly wide intervals. Second, split conformal inference delivers virtually identical coverage to full conformal inference while drastically reducing computation time—executing in fractions of a second compared to hundreds of seconds in high-dimensional tests. Third, the width of the prediction intervals is directly governed by model accuracy: more predictive estimators yield narrower, more informative intervals. Fourth, combining multiple data splits via standard multi-split aggregation widens prediction bands due to conservative correction penalties, indicating that a single balanced split is preferable. Finally, the authors show that modifying residuals with local error-spread estimates allows the intervals to adapt to varying noise levels across the feature space, and introduce a model-free variable importance measure (leave-one-covariate-out) that reliably identifies predictive features without parametric assumptions.

These results demonstrate that organizations can reliably quantify predictive uncertainty across arbitrary black-box models without risking failure from misspecified assumptions. For operational deployment, decision-makers should adopt split conformal inference as the default standard for generating prediction intervals and evaluating model-free feature importance due to its extreme computational efficiency and robust finite-sample guarantees. Where heteroskedasticity is present, locally weighted conformal inference should be used to ensure uniform local coverage. Future work should focus on developing more efficient multi-split aggregation methods to eliminate data-splitting randomness without inflating interval length, as well as refining variable selection frameworks to address post-selection inference under data splitting.

Carnegie Mellon University computational efficiency inference marginals distribution-free predictive inference conformal inference conformal prediction sets

arXiv: 1604.04173

Paper: A tutorial on conformal prediction, Glenn Shafer et al. (2007). This tutorial introduces the foundational framework and mathematical principles of conformal prediction under exchangeability that the source directly adapts and extends to regression.
Paper: Quantile Regression Forests, Nicolai Meinshausen (2006). This paper establishes non-parametric quantile estimation using random forests, providing key background for the source's distribution-free regression and heteroskedasticity-adapting prediction bands.
Paper: Stability and Generalization, Olivier Bousquet et al. (2002). This work establishes algorithmic stability tools and leave-one-out sensitivity analyses that underpin the theoretical justifications for sample-splitting and jackknife-based predictive inference.
Paper: A survey of cross-validation procedures for model selection, Sylvain Arlot et al. (2009). This survey provides essential theoretical foundations on cross-validation and sample-splitting mechanics that inform the source's development of split conformal and out-of-sample inference.

Paper: All Models are Wrong, but Many are Useful: Learning a Variable’s Importance by Studying an Entire Class of Prediction Models Simultaneously, Aaron Fisher et al. (2018). This paper advances model-agnostic variable importance across entire hypothesis classes, extending the leave-one-covariate-out (LOCO) predictive importance perspective introduced in the source.
Paper: Replicable Conformal Prediction, Marios Papamichalis et al. (2026). This work directly addresses the sample-splitting instability inherent in split conformal prediction by developing replicable calibration protocols while preserving finite-sample coverage guarantees.
Paper: Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift, Yaniv Ovadia et al. (2019). This study comprehensively evaluates the empirical reliability of predictive uncertainty quantification when standard distribution-free exchangeability assumptions fail under real-world dataset shift.

Cover for Distribution-Free Predictive Inference for Regression

Abstract

We develop a general framework for distribution-free predictive inference in regression, using conformal inference. The proposed methodology allows for the construction of a prediction band for the response variable using any estimator of the regression function. The resulting prediction band preserves the consistency properties of the original estimator under standard assumptions, while guaranteeing finite-sample marginal coverage even when these assumptions do not hold. We analyze and compare, both empirically and theoretically, the two major variants of our conformal framework: full conformal inference and split conformal inference, along with a related jackknife method. These methods offer different tradeoffs between statistical accuracy (length of resulting prediction intervals) and computational efficiency. As extensions, we develop a method for constructing valid in-sample prediction intervals called {\it rank-one-out} conformal inference, which has essentially the same computational efficiency as split conformal inference. We also describe an extension of our procedures for producing prediction bands with locally varying length, in order to adapt to heteroskedascity in the data. Finally, we propose a model-free notion of variable importance, called {\it leave-one-covariate-out} or LOCO inference. Accompanying this paper is an R package {\tt conformalInference} that implements all of the proposals we have introduced. In the spirit of reproducibility, all of our empirical results can also be easily (re)generated using this package.

Topics

computational efficiency inference marginals probabilistic inference model free frequency bands

Keywords

distribution-free predictive inference conformal inference conformal prediction sets LOCO inference model-free variable importance prediction bands finite-sample coverage asymptotic conditional coverage

1 Introduction
1.1 Related Work
1.2 Summary and Outline
2 Conformal Inference
2.1 Conformal Prediction Sets
2.2 Split Conformal Prediction Sets
2.3 Multiple Splits
2.4 Jackknife Prediction Intervals
3 Statistical Accuracy
3.1 Comparing the Oracles
3.2 Oracle Approximation Under Stability Assumptions
3.3 Super Oracle Approximation Under Consistency Assumptions
3.4 A High-dimensional Sparse Regression Example
4 Empirical Study
4.1 Comparisons to Parametric Intervals from Linear Regression
4.2 Comparisons of Conformal Intervals Across Base Estimators
5 Extensions of Conformal Inference
5.1 In-Sample Split Conformal Inference
5.2 Locally-Weighted Conformal Inference
6 Model-Free Variable Importance: LOCO
6.1 Local Measure of Variable Importance
6.2 Global Measures of Variable Importance
7 Conclusion
References
A Technical Proofs
A.1 Proofs for
A.2 Proofs for
A.3 Proofs for
B Additional Experiments

Knowls

Knowl 1 — Full Conformal Prediction Algorithm and Finite-Sample Coverage
algorithm
Full conformal prediction is a distribution-free method that constructs a prediction interval $C_{\text{conf}}(X_{n+1})$ for a new response $Y_{n+1} \in \mathbb{R}$ given features $X_{n+1} \in \mathbb{R}^d$ , using any symmetric regression algorithm $\mathcal{A}$ on i.i.d. training data $(X_1, Y_1), \dots, (X_n, Y_n) \sim P$ .
Input: Training data $(X_i, Y_i)$ for $i = 1, \dots, n$ , miscoverage level $\alpha \in (0, 1)$ , symmetric regression algorithm $\mathcal{A}$ , query points $\mathcal{X}_{\text{new}}$ , candidate response values $\mathcal{Y}_{\text{trial}} = \{y_1, y_2, \dots\}$
Output: Prediction intervals $C_{\text{conf}}(x)$ for each $x \in \mathcal{X}_{\text{new}}$
for $x \in \mathcal{X}_{\text{new}}$ do
    for $y \in \mathcal{Y}_{\text{trial}}$ do
        Fit model on augmented data: $\hat{\mu}_y = \mathcal{A}(\{(X_1, Y_1), \dots, (X_n, Y_n), (x, y)\})$
        Compute fitted residuals: $R_{y,i} = |Y_i - \hat{\mu}_y(X_i)|$ for $i = 1, \dots, n$ , and $R_{y,n+1} = |y - \hat{\mu}_y(x)|$
        Compute rank statistic: $\pi(y) = \frac{1}{n+1} \left(1 + \sum_{i=1}^n \mathbf{1}\{R_{y,i} \le R_{y,n+1}\}\right)$
    end for
    Set $C_{\text{conf}}(x) = \{y \in \mathcal{Y}_{\text{trial}} : (n + 1)\pi(y) \le \lceil(1 - \alpha)(n + 1)\rceil\}$
end for
return $C_{\text{conf}}(x)$ for each $x \in \mathcal{X}_{\text{new}}$
If $(X_1, Y_1), \dots, (X_n, Y_n), (X_{n+1}, Y_{n+1})$ are i.i.d. draws from $P$ , the full conformal prediction set satisfies the nonasymptotic marginal validity guarantee:

$\mathbb{P}(Y_{n+1} \in C_{\text{conf}}(X_{n+1})) \ge 1 - \alpha$

Furthermore, if the absolute residuals $R_{y,i} = |Y_i - \hat{\mu}_y(X_i)|$ have a continuous joint distribution for all $y \in \mathbb{R}$ , the procedure is non-conservative with upper bound:

$\mathbb{P}(Y_{n+1} \in C_{\text{conf}}(X_{n+1})) \le 1 - \alpha + \frac{1}{n + 1}$
Knowl 2 — Split Conformal Prediction Algorithm and Finite-Sample Bounds
algorithm
Split conformal prediction separates model training from residual ranking via sample splitting, computing distribution-free prediction intervals with the computational cost of a single model fit.
Input: Data $(X_i, Y_i)$ for $i = 1, \dots, n$ (with $n$ even), nominal miscoverage level $\alpha \in (0, 1)$ , regression algorithm $\mathcal{A}$
Output: Prediction band $C_{\text{split}}(x)$ for all $x \in \mathbb{R}^d$
Randomly split $\{1, \dots, n\}$ into two equal-sized subsets $I_1$ and $I_2$ of size $n/2$
Fit model on training subset: $\hat{\mu} = \mathcal{A}(\{(X_i, Y_i) : i \in I_1\})$
Compute calibration residuals: $R_i = |Y_i - \hat{\mu}(X_i)|$ for each $i \in I_2$
Compute quantile cutoff: $d = k\text{-th smallest value in } \{R_i : i \in I_2\} \text{ with } k = \lceil(n/2 + 1)(1 - \alpha)\rceil$
return $C_{\text{split}}(x) = [\hat{\mu}(x) - d, \hat{\mu}(x) + d]$ for all $x \in \mathbb{R}^d$
For i.i.d. sample pairs $(X_1, Y_1), \dots, (X_n, Y_n), (X_{n+1}, Y_{n+1}) \sim P$ , the split conformal band satisfies:

$\mathbb{P}(Y_{n+1} \in C_{\text{split}}(X_{n+1})) \ge 1 - \alpha$

If the calibration residuals $R_i$ for $i \in I_2$ have a continuous joint distribution, the coverage is bounded above by:

$\mathbb{P}(Y_{n+1} \in C_{\text{split}}(X_{n+1})) \le 1 - \alpha + \frac{2}{n + 2}$

Additionally, split conformal prediction provides approximate in-sample coverage on the calibration split $I_2$ : there exists an absolute constant $c > 0$ such that for any $\epsilon > 0$ ,

$\mathbb{P}\left(\left| \frac{2}{n} \sum_{i \in I_2} \mathbf{1}\{Y_i \in C_{\text{split}}(X_i)\} - (1 - \alpha) \right| \ge \epsilon\right) \le 2 \exp\left(-c n^2 (\epsilon - 4/n)_+^2\right)$
Knowl 3 — Rank-One-Out Split Conformal Inference for In-Sample Prediction Intervals
algorithm
Rank-one-out (ROO) split conformal inference constructs distribution-free, finite-sample valid prediction intervals $C_{\text{roo}}(X_i)$ at all observed data points $X_1, \dots, X_n$ using two model fits and leave-one-out residual ranking across splits.
Input: Data $(X_i, Y_i)$ for $i = 1, \dots, n$ (with $n$ even), nominal miscoverage level $\alpha \in (0, 1)$ , regression algorithm $\mathcal{A}$
Output: Prediction intervals $C_{\text{roo}}(X_i)$ for each $i = 1, \dots, n$
Randomly split $\{1, \dots, n\}$ into two equal-sized subsets $I_1, I_2$
for $k \in \{1, 2\}$ do
    Fit regression estimator on split $I_k$ : $\hat{\mu}_k = \mathcal{A}(\{(X_i, Y_i) : i \in I_k\})$
    for $i \notin I_k$ do
        Compute residual $R_i = |Y_i - \hat{\mu}_k(X_i)|$
    end for
    for $i \notin I_k$ do
        Compute $d_i = m\text{-th smallest value in } \{R_j : j \notin I_k, j \ne i\} \text{ where } m = \lceil(n/2)(1 - \alpha)\rceil$
        Set $C_{\text{roo}}(X_i) = [\hat{\mu}_k(X_i) - d_i, \hat{\mu}_k(X_i) + d_i]$
    end for
end for
return $C_{\text{roo}}(X_i)$ for each $i = 1, \dots, n$
By symmetry, for each individual point $i \in \{1, \dots, n\}$ , the in-sample coverage satisfies $\mathbb{P}(Y_i \in C_{\text{roo}}(X_i)) \ge 1 - \alpha$ . For the empirical average in-sample coverage over the entire sample, McDiarmid's inequality yields absolute constant $c > 0$ such that for any $\epsilon > 0$ :

$\mathbb{P}\left(\frac{1}{n} \sum_{i=1}^n \mathbf{1}\{Y_i \in C_{\text{roo}}(X_i)\} \ge 1 - \alpha - \epsilon\right) \ge 1 - 2\exp(-c n \epsilon^2)$

If the residuals have a continuous joint distribution, the empirical coverage is two-sided bounded:

$\mathbb{P}\left(1 - \alpha - \epsilon \le \frac{1}{n} \sum_{i=1}^n \mathbf{1}\{Y_i \in C_{\text{roo}}(X_i)\} \le 1 - \alpha + \frac{2}{n} + \epsilon\right) \ge 1 - 2\exp(-c n \epsilon^2)$
Knowl 4 — Locally-Weighted Conformal Inference for Heteroskedastic Errors
model/method
Standard conformal prediction intervals have roughly constant length over the feature space $\mathbb{R}^d$ . When error variability depends on features, locally-weighted conformal inference scales the fitted residuals inversely by an estimate of the conditional error spread, producing prediction intervals with locally varying width while preserving exact distribution-free finite-sample marginal coverage.

Let $\hat{\mu}(x)$ estimate the conditional mean $\mathbb{E}[Y \mid X = x]$ and let $\hat{\rho}(x)$ estimate the conditional mean absolute deviation (MAD) $\mathbb{E}[|Y - \mu(X)| \mid X = x]$ .

In split conformal prediction, the estimators $\hat{\mu}$ and $\hat{\rho}$ are fitted on training split $I_1$ . The locally-weighted residuals on calibration split $I_2$ are defined as:

$R_i = \frac{|Y_i - \hat{\mu}(X_i)|}{\hat{\rho}(X_i)}, \quad i \in I_2$

Let $d$ be the $\lceil(n/2 + 1)(1 - \alpha)\rceil$ -th smallest value in $\{R_i : i \in I_2\}$ . The locally-weighted split conformal prediction interval at any $x \in \mathbb{R}^d$ is:

$C_{\text{split, lw}}(x) = [\hat{\mu}(x) - \hat{\rho}(x)d, \, \hat{\mu}(x) + \hat{\rho}(x)d]$

In full conformal prediction with trial point $(x, y)$ , augmented estimators $\hat{\mu}_y$ and $\hat{\rho}_y$ are fitted on $\{(X_1, Y_1), \dots, (X_n, Y_n), (x, y)\}$ , yielding locally-weighted conformity scores:

$R_{y,i} = \frac{|Y_i - \hat{\mu}_y(X_i)|}{\hat{\rho}_y(X_i)} \quad (i=1,\dots,n), \qquad R_{y,n+1} = \frac{|y - \hat{\mu}_y(x)|}{\hat{\rho}_y(x)}$
Knowl 5 — Leave-One-Covariate-Out Local Variable Importance Prediction Sets
model/method
Leave-one-covariate-out (LOCO) local variable importance provides a model-free, predictive measure of the importance of individual covariates without requiring model correctness or distributional assumptions.

Let $\hat{\mu}$ be a regression estimator fitted on data using all $d$ covariates, and let $\hat{\mu}_{(-j)}$ be the estimator fitted on the same data with the $j$ -th covariate excluded, for $j \in \{1, \dots, d\}$ . The excess prediction error of covariate $j$ at a new draw $(X_{n+1}, Y_{n+1})$ is defined as:

$\Delta_j(X_{n+1}, Y_{n+1}) = |Y_{n+1} - \hat{\mu}_{(-j)}(X_{n+1})| - |Y_{n+1} - \hat{\mu}(X_{n+1})|$

Given a valid $1 - \alpha$ conformal prediction band $C(x)$ for $Y_{n+1}$ given $X_{n+1} = x$ , the LOCO prediction interval for $\Delta_j(X_{n+1}, Y_{n+1})$ is constructed by propagating $C(x)$ :

$W_j(x) = \left\{ |y - \hat{\mu}_{(-j)}(x)| - |y - \hat{\mu}(x)| : y \in C(x) \right\}$

Because inclusion of $Y_{n+1} \in C(X_{n+1})$ implies $\Delta_j(X_{n+1}, Y_{n+1}) \in W_j(X_{n+1})$ for all $j$ , the sets $W_1, \dots, W_d$ enjoy simultaneous finite-sample marginal validity across all features without multiplicity adjustments:

$\mathbb{P}\left(\Delta_j(X_{n+1}, Y_{n+1}) \in W_j(X_{n+1}) \text{ for all } j = 1, \dots, d\right) \ge 1 - \alpha$
Knowl 6 — Leave-One-Covariate-Out Global Variable Importance Inference
theoretical result
Global LOCO inference quantifies the overall predictive importance of feature $j$ across the population distribution conditional on training data split $D_1 = \{(X_i, Y_i) : i \in I_1\}$ . Let $\Delta_j(X, Y) = |Y - \hat{\mu}_{(-j)}(X)| - |Y - \hat{\mu}(X)|$ , and let $G_j(t) = \mathbb{P}(\Delta_j(X_{n+1}, Y_{n+1}) \le t \mid D_1)$ denote its conditional cumulative distribution function.
1. Mean Excess Test Error $\theta_j = \mathbb{E}[\Delta_j(X_{n+1}, Y_{n+1}) \mid D_1]$ : Using evaluation split $D_2 = \{(X_i, Y_i) : i \in I_2\}$ of size $n/2$ , let $\hat{\theta}_j = \frac{2}{n} \sum_{i \in I_2} \Delta_j(X_i, Y_i)$ and $s_j^2$ be the sample variance of $\{\Delta_j(X_i, Y_i) : i \in I_2\}$ . An asymptotic $1 - \alpha$ confidence interval is:
$\left[ \hat{\theta}_j - \frac{z_{\alpha/2} s_j}{\sqrt{n/2}}, \, \hat{\theta}_j + \frac{z_{\alpha/2} s_j}{\sqrt{n/2}} \right]$

Testing $H_0: \theta_j \le 0$ vs $H_1: \theta_j > 0$ rejects when $\sqrt{n/2} \, (\hat{\theta}_j / s_j) > z_\alpha$ . The asymptotic convergence rate is uniform and free of feature dimension $d$ .
1. Median Excess Test Error $m_j = \text{median}(\Delta_j(X_{n+1}, Y_{n+1}) \mid D_1)$ : Nonasymptotic hypothesis tests ( $H_0: m_j \le 0$ vs $H_1: m_j > 0$ ) and confidence intervals for $m_j$ are constructed with exact finite-sample validity by applying standard nonparametric tests (the sign test requiring only continuity of $G_j$ , or the Wilcoxon signed-rank test requiring continuity and symmetry) directly to the evaluation sample $\{\Delta_j(X_i, Y_i) : i \in I_2\}$ . Multiplicity across a tested feature set $S$ is controlled by replacing $\alpha$ with $\alpha / |S|$ .
Knowl 7 — Oracle vs Super Oracle Prediction Bands and Accuracy Bound
theoretical result
Under i.i.d. regression data $(X, Y) \sim P$ where the noise $\epsilon = Y - \mu(X)$ is independent of $X$ and has symmetric density $f_0$ about 0 (Assumptions A0 and A1):
- The Super Oracle band is $C_s^*(x) = [\mu(x) - q_\alpha, \mu(x) + q_\alpha]$ , where $q_\alpha$ is the $(1 - \alpha)$ -quantile of $|\epsilon|$ . It achieves exact conditional coverage $\mathbb{P}(Y \in C_s^*(x) \mid X = x) \ge 1 - \alpha$ and has minimal expected length among all valid bands.
- The Regular Oracle band for an estimator $\hat{\mu}_n$ trained on $n$ samples is $C_o^*(x) = [\hat{\mu}_n(x) - q_{n,\alpha}, \hat{\mu}_n(x) + q_{n,\alpha}]$ , where $q_{n,\alpha}$ is the unconditional $(1 - \alpha)$ -quantile of $|Y - \hat{\mu}_n(X)|$ .
Let $\Delta_n(x) = \hat{\mu}_n(x) - \mu(x)$ , and let $F$ and $F_n$ denote the CDFs of $|\epsilon|$ and $|Y - \hat{\mu}_n(X)|$ respectively. If $f_0$ has a continuous derivative uniformly bounded by $M > 0$ , then:

$\sup_{t > 0} |F_n(t) - F(t)| \le \frac{M}{2} \mathbb{E}[\Delta_n^2(X)]$

Furthermore, if the density $f$ of $|\epsilon|$ is lower-bounded by $r > 0$ on $(q_\alpha - \eta, q_\alpha + \eta)$ for some $\eta > \frac{M}{2r} \mathbb{E}[\Delta_n^2(X)]$ , the difference in half-widths is bounded quadratically in the estimation error:

$|q_{n,\alpha} - q_\alpha| \le \frac{M}{2r} \mathbb{E}[\Delta_n^2(X)]$
Knowl 8 — Conformal Approximation of the Regular Oracle Under Stability
theoretical result
Conformal prediction bands closely approximate the Regular Oracle band $C_o^*(X) = [\hat{\mu}_n(X) - q_{n,\alpha}, \hat{\mu}_n(X) + q_{n,\alpha}]$ under sampling stability and perturbation sensitivity conditions.

Assumption A2 (Sampling Stability): For large $n$ , $\mathbb{P}(\|\hat{\mu}_n - \tilde{\mu}\|_\infty \ge \eta_n) \le \rho_n$ for some target function $\tilde{\mu}$ and sequences $\eta_n = o(1), \rho_n = o(1)$ .

Assumption A3 (Perturb-One Sensitivity): For candidate values $y \in \mathcal{Y}$ , $\mathbb{P}\left(\sup_{y \in \mathcal{Y}} \|\hat{\mu}_n - \hat{\mu}_{n,(X,y)}\|_\infty \ge \eta_n\right) \le \rho_n$ .

Under Assumptions A0, A1, A2, if the density $\tilde{f}$ of $|Y - \tilde{\mu}(X)|$ is lower bounded away from zero near its $(1 - \alpha)$ -quantile, the width $\nu_{n,\text{split}}$ of the split conformal band satisfies:

$\nu_{n,\text{split}} - 2q_{n,\alpha} = O_P(\rho_n + \eta_n + n^{-1/2})$

Under the additional assumption that the response space $\mathcal{Y}$ satisfies Assumption A3, the width $\nu_{n,\text{conf}}(X)$ of the full conformal band at $X$ satisfies:

$\nu_{n,\text{conf}}(X) - 2q_{n,\alpha} = O_P(\eta_n + \rho_n + n^{-1/2})$
Knowl 9 — Super Oracle Approximation and Asymptotic Conditional Coverage
theoretical result
A sequence of prediction bands $C_n$ has asymptotic conditional coverage at level $1 - \alpha$ if there exist sets $\Lambda_n \subseteq \mathbb{R}^d$ such that $\mathbb{P}(X \in \Lambda_n \mid \Lambda_n) = 1 - o_P(1)$ and

$\inf_{x \in \Lambda_n} |\mathbb{P}(Y \in C_n(x) \mid X = x) - (1 - \alpha)| = o_P(1)$

Assumption A4 (Consistency): $\mathbb{P}\left(\mathbb{E}_X[(\hat{\mu}_n(X) - \mu(X))^2 \mid \hat{\mu}_n] \ge \eta_n\right) \le \rho_n$ with $\eta_n = o(1), \rho_n = o(1)$ .

Under Assumptions A0, A1, and A4, if $|Y - \mu(X)|$ has density bounded away from zero near its $(1 - \alpha)$ -quantile:
1. The split conformal band satisfies $\mathcal{L}(C_{n,\text{split}}(X) \, \Delta \, C_s^*(X)) = o_P(1)$ , where $\mathcal{L}$ is the Lebesgue measure, $A \, \Delta \, B$ denotes symmetric set difference, and $C_s^*(x) = [\mu(x) - q_\alpha, \mu(x) + q_\alpha]$ is the super oracle band. Hence, $C_{n,\text{split}}$ attains asymptotic conditional coverage at level $1 - \alpha$ .
2. If in addition perturb-one sensitivity (Assumption A3) holds, the full conformal band satisfies $\mathcal{L}(C_{n,\text{conf}}(X) \, \Delta \, C_s^*(X)) = o_P(1)$ , guaranteeing asymptotic conditional coverage at level $1 - \alpha$ .
Knowl 10 — Suboptimality of Multi-Split Conformal Prediction
theoretical result
To reduce the split-dependent variance of split conformal inference, one can combine $N$ independent random splits by intersecting individual split conformal intervals constructed at Bonferroni-corrected miscoverage levels $\alpha / N$ :

$C_{\text{split}}^{(N)}(x) = \bigcap_{j=1}^N C_{\text{split}, j}(x)$

By Bonferroni's inequality, $C_{\text{split}}^{(N)}$ maintains marginal coverage of at least $1 - \alpha$ .

However, under sampling stability (Assumptions A0, A1, and A2 with $\rho_n = o(n^{-1})$ ) and continuous residual distribution $|Y - \tilde{\mu}(X)|$ , the Bonferroni inflation penalty strictly dominates the intersection shrinking effect. Consequently, with probability tending to 1 as $n \to \infty$ :

$C_{\text{split}}^{(N)}(X) \text{ is strictly wider than a single split interval } C_{\text{split}}(X)$

Therefore, aggregating multiple conformal splits via Bonferroni intersections increases prediction interval length, and a single split is theoretically preferred.
Knowl 11 — Jackknife Prediction Band Algorithm and Coverage Limitations
algorithm
The jackknife prediction method constructs prediction intervals using leave-one-out residuals.
Input: Data $(X_i, Y_i)$ for $i = 1, \dots, n$ , miscoverage level $\alpha \in (0, 1)$ , regression algorithm $\mathcal{A}$
Output: Prediction band $C_{\text{jack}}(x)$ for all $x \in \mathbb{R}^d$
Fit full estimator $\hat{\mu} = \mathcal{A}(\{(X_i, Y_i) : i = 1, \dots, n\})$
for $i = 1, \dots, n$ do
Fit leave-one-out estimator: $\hat{\mu}_{(-i)} = \mathcal{A}(\{(X_\ell, Y_\ell) : \ell \ne i\})$
Compute leave-one-out residual: $R_i = |Y_i - \hat{\mu}_{(-i)}(X_i)|$
end for
Compute cutoff $d = k\text{-th smallest value in } \{R_i : i = 1, \dots, n\} \text{ where } k = \lceil n(1 - \alpha)\rceil$
return $C_{\text{jack}}(x) = [\hat{\mu}(x) - d, \hat{\mu}(x) + d]$ for all $x \in \mathbb{R}^d$
By symmetry, the jackknife band provides exact in-sample finite-sample validity:

$\mathbb{P}(Y_i \in C_{\text{jack}}(X_i)) \ge 1 - \alpha, \quad \text{for all } i = 1, \dots, n$

However, unlike conformal methods, the jackknife fails to guarantee finite-sample out-of-sample validity $\mathbb{P}(Y_{n+1} \in C_{\text{jack}}(X_{n+1})) \ge 1 - \alpha$ . Asymptotic validity requires stringent conditions including uniform asymptotic mean squared error bounds, stability of $\hat{\mu}$ , homoskedasticity, and independence between features and noise.
Knowl 12 — Empirical Robustness of Conformal Prediction Across Model Violations
empirical result
In simulation experiments comparing standard parametric linear model prediction intervals against full conformal, split conformal, and jackknife prediction intervals across three data regimes (Setting A: linear mean, Gaussian errors; Setting B: nonlinear additive mean, heavy-tailed $t(2)$ errors; Setting C: linear mean, heteroskedastic $t(2)$ errors, correlated features) in low ( $n=100, d=10$ ) and high ( $n=500, d=490$ ) dimensions:
1. Marginal Coverage Robustness: Across all settings and all base estimators (Lasso, Elastic Net, forward stepwise, SPAM, Random Forests), conformal prediction intervals consistently achieve the nominal 90% marginal coverage ( $approx 90.0\% - 90.7\%$ ), even when the regression model is completely misspecified or errors are non-Gaussian and heteroskedastic.
2. Failure of Parametric Intervals: Parametric prediction intervals over-cover drastically (e.g., $99.8\% - 100\%$ coverage) and produce excessively wide prediction intervals (e.g., length $249.9$ vs $15.5$ for conformal with ridge regression in Setting C) when homoskedasticity or normality assumptions break down.
3. Computational vs Statistical Tradeoff: Split conformal prediction achieves coverage and interval widths comparable to full conformal prediction (e.g., in Setting A high-dimensional ridge: full conformal length $3.348$ vs split conformal length $3.380$ ), while reducing computation time by orders of magnitude ( $0.155$ seconds vs $167.19$ seconds).

Coverage note — The specific derivation verifying assumptions A2-A4 for high-dimensional lasso under restricted eigenvalue and irrepresentable conditions was omitted as it instantiates the general stability and consistency theorems.

References

1.Belloni, A., Chen, D., Chernozhukov, V., & Hansen, C. (2012). Sparse models and methods for optimal instruments with an application to eminent domain. Econometrica, 80 (6), 2369–2429.
2.Berk, R., Brown, L., Buja, A., Zhang, K., & Zhao, L. (2013). Valid post-selection inference. Annals of Statistics, 41 (2), 802–837.
3.Bickel, P. J., Ritov, Y., & Tsybakov, A. B. (2009). Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, (pp. 1705–1732).
4.Breiman, L. (2001). Random forests. Machine Learning, 45 (1), 5–32.
5.Buhlmann, P. (2013). Statistical significance in high-dimensional linear models. Bernoulli, 19 (4), 1212–1242.
6.Buja, A., Berk, R., Brown, L., George, E., Pitkin, E., Traskin, M., Zhang, K., & Zhao, L. (2014). Models as approximations: How random predictors and model violations invalidate classical inference in regression. ArXiv: 1404.1578.
7.Bunea, F., Tsybakov, A., & Wegkamp, M. (2007). Sparsity oracle inequalities for the lasso. Electronic Journal of Statistics, 1 , 169–194.
8.Burnaev, E., & Vovk, V. (2014). Efficiency of conformalized ridge regression. Proceedings of the Annual Conference on Learning Theory, 25 , 605–622.
9.Butler, R., & Rothman, E. (1980). Predictive intervals based on reuse of the sample. Journal of the American Statistical Association, 75 (372), 881–889.
10.Efroymson, M. A. (1960). Multiple regression analysis. In Mathematical Methods for Digital Computers, vol. 1, (pp. 191–203). Wiley.
11.Fithian, W., Sun, D., & Taylor, J. (2014). Optimal inference after model selection. ArXv: 1410.2597.
12.Hebiri, M. (2010). Sparse conformal predictors. Statistics and Computing, 20 (2), 253–266.
13.Javanmard, A., & Montanari, A. (2014). Confidence intervals and hypothesis testing for high-dimensional regression. Journal of Machine Learning Research, 15 , 2869–2909.
14.Lee, J., Sun, D., Sun, Y., & Taylor, J. (2016). Exact post-selection inference, with application to the lasso. Annals of Statistics, 44 (3), 907–927.
15.Lei, J. (2014). Classification with confidence. Biometrika, 101 (4), 755–769.
16.Lei, J., Rinaldo, A., & Wasserman, L. (2015). A conformal prediction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 74 (1), 29–43.
17.Lei, J., Robins, J., & Wasserman, L. (2013). Distribution free prediction sets. Journal of the American Statistical Association, 108 , 278–287.
18.Lei, J., & Wasserman, L. (2014). Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series B, 76 (1), 71–96.
19.Meinshausen, N., & Buhlmann, P. (2010). Stability selection. Journal of the Royal Statistical Society: Series B, 72 (4), 417–473.
20.Papadopoulos, H., Proedrou, K., Vovk, V., & Gammerman, A. (2002). Inductive confidence machines for regression. In Machine Learning: ECML 2002 , (pp. 345–356). Springer.
21.Ravikumar, P., Lafferty, J., Liu, H., & Wasserman, L. (2009). Sparse additive models. Journal of the Royal Statistical Society: Series B, 71 (5), 1009–1030.
22.Steinberger, L., & Leeb, H. (2016). Leave-one-out prediction intervals in linear regression models with many variables. ArXiv: 1602.05801.
23.Thakurta, A. G., & Smith, A. (2013). Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, (pp. 819–850).
24.Tian, X., & Taylor, J. (2015a). Asymptotics of selective inference. ArXiv: 1501.03588.
25.Tian, X., & Taylor, J. (2015b). Selective inference with a randomized response. ArXiv: 1507.06739.
26.Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B, 58 (1), 267–288.
27.Tibshirani, R. J., Taylor, J., Lockhart, R., , & Tibshirani, R. (2016). Exact post-selection inference for sequential regression procedures. Journal of the American Statistical Association, 111 (514), 600–620.
28.van de Geer, S., Buhlmann, P., Ritov, Y., & Dezeure, R. (2014). On asymptotically optimal confidence regions and tests for high-dimensional models. Annals of Statistics, 42 (3), 1166–1201.
29.Vovk, V. (2013). Conditional validity of inductive conformal predictors. Machine Learning, 92 , 349–376.
30.Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic Learning in a Random World. Springer.
31.Vovk, V., Nouretdinov, I., & Gammerman, A. (2009). On-line predictive linear regression. The Annals of Statistics, 37 (3), 1566–1590.
32.Wasserman, L. (2014). Discussion: A significance test for the lasso. Annals of Statistics, 42 (2), 501–508.
33.Zhang, C.-H., & Zhang, S. (2014). Confidence intervals for low dimensional parameters in high dimensional linear models. Journal of the Royal Statistical Society: Series B, 76 (1), 217–242.
34.Zou, H., & Hastie, T. (2005). Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B, 67 (2), 301–320.

Citation

MLA

Lei, J., et al. “Distribution-Free Predictive Inference For Regression”. arXiv, 2016, http://arxiv.org/abs/1604.04173v2.

APA

Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., & Wasserman, L. (2016). Distribution-Free Predictive Inference For Regression. arXiv. http://arxiv.org/abs/1604.04173v2

Chicago

Lei, J., M. G'Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman. 2016. “Distribution-Free Predictive Inference For Regression”. arXiv. http://arxiv.org/abs/1604.04173v2.

Harvard

Lei, J. et al. (2016) “Distribution-Free Predictive Inference For Regression”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1604.04173v2.

Vancouver

1. Lei J, G'Sell M, Rinaldo A, Tibshirani RJ, Wasserman L (2016) Distribution-Free Predictive Inference For Regression. arXiv

BibTeX

@article{lei2016distribution,
  title = {Distribution-Free Predictive Inference For Regression},
  author = {Lei, Jing and G'Sell, Max and Rinaldo, Alessandro and Tibshirani, Ryan J. and Wasserman, Larry},
  year = {2016},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1604.04173v2},
  eprint = {1604.04173}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Distribution-Free Predictive Inference for Regression

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Full Conformal Prediction Algorithm and Finite-Sample Coverage

Knowl 2 — Split Conformal Prediction Algorithm and Finite-Sample Bounds

Knowl 3 — Rank-One-Out Split Conformal Inference for In-Sample Prediction Intervals

Knowl 4 — Locally-Weighted Conformal Inference for Heteroskedastic Errors

Knowl 5 — Leave-One-Covariate-Out Local Variable Importance Prediction Sets

Knowl 6 — Leave-One-Covariate-Out Global Variable Importance Inference

Knowl 7 — Oracle vs Super Oracle Prediction Bands and Accuracy Bound

Knowl 8 — Conformal Approximation of the Regular Oracle Under Stability

Knowl 9 — Super Oracle Approximation and Asymptotic Conditional Coverage

Knowl 10 — Suboptimality of Multi-Split Conformal Prediction

Knowl 11 — Jackknife Prediction Band Algorithm and Coverage Limitations

Knowl 12 — Empirical Robustness of Conformal Prediction Across Model Violations

References

Citation

BibTeX

Access the Paper