Split conformal prediction

Coverage theorems. For every distribution and every symmetric $\mathcal A$ (with ties handled as in Step 1), $\mathbb P(Y_{n+1}\in C_{\rm conf}(X_{n+1}))\ge1-\alpha$, and if the fitted residuals have a continuous joint distribution, $$\mathbb P\big(Y_{n+1}\in C_{\rm conf}(X_{n+1})\big)\le1-\alpha+\frac1{n+1}.$$ Split conformal satisfies the same lower bound and, with continuous residuals, the upper bound $1-\alpha+2/(n+2)$; CQR covers with probability at least $1-\alpha$ for any quantile regression algorithm, and at most $1-\alpha+1/(|I_2|+1)$ with almost surely distinct scores, both conditionally on the fitting half. The probabilities are over all $n+1$ draws, so the guarantee is marginal over $X_{n+1}$; the lower bound is Vovk's, the upper bound is new in Lei et al. Calibrating each CQR end with its own one-sided score, $\hat q_{\alpha_{\rm lo}}(X_i)-Y_i$ and $Y_i-\hat q_{\alpha_{\rm hi}}(X_i)$, with inflated quantiles at levels $(1-\alpha_{\rm lo})(1+1/|I_2|)$ and $(1-\alpha_{\rm hi})(1+1/|I_2|)$, where $\alpha_{\rm lo},\alpha_{\rm hi}$ now denote the two tail miscoverages, guarantees each tail separately (Theorem 2): $\mathbb P\{Y_{n+1}\ge\text{lower end}\}\ge1-\alpha_{\rm lo}$ and $\mathbb P\{Y_{n+1}\le\text{upper end}\}\ge1-\alpha_{\rm hi}$, so with $\alpha=\alpha_{\rm lo}+\alpha_{\rm hi}$ the band covers with probability at least $1-\alpha$.

The test point's rank is uniform, so inverting the rank test covers. Fix the trial value at the truth, $y=Y_{n+1}$. The augmented fit treats all $n+1$ points symmetrically, so exchangeable data give exchangeable residuals, and with no ties the last one's rank is uniform on $\{1,\dots,n+1\}$: $$\mathbb P\big((n+1)\pi(Y_{n+1})\le\lceil(1-\alpha)(n+1)\rceil\big)=\frac{\lceil(1-\alpha)(n+1)\rceil}{n+1}\ge1-\alpha .$$ Nothing about $\hat\mu$ or $P$ enters; refitting with the candidate removes the naive method's bias by fitting the test point on the same footing as the others. Read as a test, $C_{\rm conf}$ keeps the $y$ that the p-value $1-\pi(y)+1/(n+1)$ for $H_0:Y_{n+1}=y$ does not reject (the paper writes $1-\pi(y)$, which is anti-conservative by $1/(n+1)$: for $n=1$ it is 0 with probability 1/2). The cost is one refit per $(x,y)$ on a grid, and the set need not be an interval.

Without ties, coverage is at most $1-\alpha+1/(n+1)$. With distinct residuals the display above is an equality, and $\lceil(1-\alpha)(n+1)\rceil/(n+1)\lt1-\alpha+1/(n+1)$. The upper bound shows that the method does not reach coverage by inflating the band; it is calibrated, and the excess $1/(n+1)$ comes from the rank being discrete. Random tie-breaking removes the continuity assumption.

Split conformal and CQR are the same argument given the first half, and the inflated quantile accounts for the unseen test score. Conditional on $I_1$ the fitted functions are fixed, so the $m=|I_2|$ calibration scores and the test score are exchangeable. The inflation lemma takes the unknown test score out of the threshold: with $k=\lceil(1-\alpha)(m+1)\rceil$, $$E_{n+1}\le E_{(k,m)}\iff E_{n+1}\le E_{(k,m+1)},$$ because inserting $E_{n+1}$ below the $k$-th smallest of $m$ values makes it at most the $k$-th smallest of $m+1$, and conversely. The right side is a quantile of all $m+1$ exchangeable scores, so the test score falls below it with probability at least $1-\alpha$, and at most $1-\alpha+1/(m+1)$ without ties; averaging over $I_1$ gives the marginal statements, and $m=n/2$ gives split conformal's $2/(n+2)$. A single fit is what makes conformal practical around the lasso, a forest or a quantile network; the cost is that only half the data are used for fitting. Removing the split's randomness by intersecting $N$ bands at level $1-\alpha/N$ is valid by Bonferroni but widens the band (Theorem 2.4, under stability with $\rho_n=o(1/n)$): the fits are within $\eta_n=o(1)$ of each other, so intersecting gains almost nothing, while by DKW each empirical $(1-\alpha/N)$ quantile stays above the $(1-\alpha)$ quantile by a fixed gap.

CQR's signed score turns coverage into one inequality, and the sign lets calibration shrink the band. Below the fitted interval $E$ is the distance to the lower end, above it the distance to the upper end, and inside it the larger of two nonpositive numbers, so $Y_{n+1}\in C(X_{n+1})\iff E_{n+1}\le Q$ and coverage depends only on the rank of one score. When the quantile model is too generous most calibration scores are negative, $Q\lt0$, and both ends move in; when it is too tight, $Q\gt0$ widens it. The correction is one additive shift at every $x$, so the band keeps the quantile model's shape. Per-tail calibration applies the inflation lemma twice and costs width (average length 1.40 to 1.58 for the network), since the symmetric version lets the miscoverage fall in whichever tail the model gets wrong.

The guarantee is marginal, and conditional coverage is out of reach without assumptions. Lei et al. cite the impossibility without proving it (Lei and Wasserman, 2014): a band with $\mathbb P(Y\in C(x)\mid X=x)\ge1-\alpha$ for almost every $x$ and every $P$ has infinite expected length at non-atom points $x_0$ of $P_X$. The proof uses a local perturbation: spread $Y$ given $X$ over a huge range on a small ball around $x_0$. No training point is likely to land in the ball, so the two sample laws are close in total variation and the band, which must cover the huge range under the perturbed law, is huge under $P$ too. Steps 6 to 8 recover conditional coverage under assumptions on the estimator.

The regression error moves the oracle width only at second order. Independence of $\varepsilon$ and $X$ writes the CDF of $|Y-\hat\mu_n(X)|$ as the noise CDF $F_0$ averaged over shifts by the fit error: $$F_n(t)=\mathbb E\big[F_0(t+\Delta_n(X))-F_0(-t+\Delta_n(X))\big].$$ In a Taylor expansion the first-order terms $\Delta_nf_0(t)$ and $-\Delta_nf_0(-t)$ cancel because the noise density is symmetric, leaving $\sup_t|F_n(t)-F(t)|\le(M/2)\mathbb E\Delta_n^2$, and the density lower bound turns this into the quantile bound. A biased fit costs width only through its mean squared error.

Under stability, the conformal width is the oracle width. A fit within $\eta_n$ of a fixed $\tilde\mu$ moves every residual by at most $\eta_n$, so every quantile involved is within $\eta_n$ of a quantile of residuals about $\tilde\mu$: the empirical calibration quantile is within $\eta_n$ of the empirical quantile of $|Y_i-\tilde\mu(X_i)|$, which is within $O_P(n^{-1/2})$ of its population value, and $q_{n,\alpha}$ is within $\rho_n/r+\eta_n$ of that value. Full conformal refits for every $y$, so it also needs perturb-one, which keeps the augmented residuals within $2\eta_n$ of residuals about $\tilde\mu$ for all trial $y$ at once and pins the width between two nearby quantiles. Since $\tilde\mu$ need not be $\mu$, stability alone makes the band as short as the fitted model allows.

A consistent fit gives the super oracle and conditional coverage in the limit. Consistency controls only the mean squared error, so split $x$-space into a small bad set where the fit is off and the rest. By Markov the bad set $B_n=\{x:|\hat\mu_n(x)-\mu(x)|\ge\eta_n^{1/3}\}$ has probability at most $\eta_n^{1/3}$; it is independent of the calibration half, so by Hoeffding only $o(n)$ calibration points fall in it, and off it the residuals about $\hat\mu_n$ and $\mu$ differ by at most $\eta_n^{1/3}$. The empirical quantile is then sandwiched between quantiles of $|\varepsilon_i|$ at levels $\alpha+o_P(1)$, and a test point lands off $B_n$ with probability tending to one, so the band converges to $\mu(X)\pm q_\alpha$. For the lasso, restricted eigenvalues give both with $\eta_n$ of order $s\sqrt{\log d/n}$, enough for split conformal; full conformal's perturb-one needs support recovery.

In-sample coverage is exact by construction, and LOCO inherits simultaneous coverage. The paper proves Theorem 5.1 with McDiarmid, but sorting gives more (not in the paper): with distinct residuals the point of rank $r$ in its half is covered exactly when $r\le m$, since the $m$-th smallest of the others is $R_{(m+1)}$ if $r\le m$ and $R_{(m)}$ otherwise. So in-sample coverage equals $2m/n\in[1-\alpha,1-\alpha+2/n]$ with probability one; my simulation (OLS, heavy-tailed heteroskedastic noise, $n=20,50,200$) returned exactly $2m/n$ in every run. Theorem 2.3 (the half-sample statement for split conformal) is deterministic for the same reason; since that coverage holds by construction, it cannot test the method, and the in-sample band serves only for display. For LOCO, if $Y_{n+1}\in C(X_{n+1})$ then $\Delta_j(X_{n+1},Y_{n+1})\in W_j(X_{n+1})$ for every $j$ at once, since each $W_j$ is an image of the same set: one event of probability $1-\alpha$ covers all $d$ intervals.

In experiments the bands keep their coverage, and CQR gives the shortest. Conformal bands are valid under misspecification, and their length tracks the model. At 90% Lei et al.'s bands covered within 2 points in every setting, including $t_2$ heteroskedastic noise and nonlinear means; at $n=500$, $d=490$ with least squares, full conformal covered 0.903 with length 8.1, against 0.867 and 24.2 for the parametric interval and 0.883 and 26.1 for the jackknife. Locally weighted bands (residuals divided by a fitted spread $\hat\sigma$) adapt only partly, because $\hat\sigma$ is fit to the fitting half's residuals, which are biased low and nearly zero for a network that almost interpolates; CQR's model is trained on the quantiles themselves, and anything done on $I_1$, such as tuning the nominal levels, does not affect validity. On eleven benchmarks at $\alpha=0.1$ average lengths were 2.24 and 2.16 for forest and network, 1.82 and 1.81 locally weighted, and 1.41 and 1.40 for CQR, all conformal methods at 89.9 to 90.3%; unconformalized quantile networks covered only 88.5% and quantile forests 92.6%, so calibration fixes both. CQR overcovered on the two Facebook datasets, which the paper attributes to ties among discrete scores, which void the upper bound. Coverage within slices of $X$, what adaptivity is meant to improve, is not measured.