Optimal Distribution-Free Prediction Intervals

§ Problem Statement

Setup

Let $d \in \mathbb N$ , $\alpha \in (0,1)$ , and let $\mathcal P$ be the class of all Borel probability distributions on $\mathbb R^d \times \mathbb R$ . For any $P \in \mathcal P$ , draw i.i.d. pairs $(X_1,Y_1),\dots,(X_n,Y_n),(X_{n+1},Y_{n+1}) \sim P$ , where $X_i \in \mathbb R^d$ and $Y_i \in \mathbb R$ . A (possibly randomized) prediction-interval procedure is a measurable map sending $(X_1,Y_1),\dots,(X_n,Y_n)$ and a test covariate $x$ to an interval $\widehat C_n(x)=[L_n(x),U_n(x)]\subseteq\mathbb R$ , with length $|\widehat C_n(x)|:=U_n(x)-L_n(x)$ .

Finite-sample marginal validity under exchangeability at level $1-\alpha$ is

\inf_{P\in\mathcal P}\mathbb P_P\!\big(Y_{n+1}\in \widehat C_n(X_{n+1})\big)\ge 1-\alpha.

Define

\mathcal R_n(\widehat C_n;\alpha):=\sup_{P\in\mathcal P}\mathbb E_P\!\big[|\widehat C_n(X_{n+1})|\big],\qquad \mathcal R_{n,\mathrm{unres}}^*(\alpha):=\inf_{\widehat C_n\ \text{marginally valid}}\mathcal R_n(\widehat C_n;\alpha).

For unrestricted $\mathcal P$ , the objective is degenerate: $\mathcal R_{n,\mathrm{unres}}^*(\alpha)=\infty$ (equivalently, no finite uniform expected-length guarantee over all Borel laws).

Unsolved Problem

Pose and solve the minimax question on a restricted class $\mathcal P_\Theta\subset\mathcal P$ (e.g., moment/tail, noise, smoothness, or shape constraints):

\mathcal R_{n,\Theta}^*(\alpha):=\inf_{\widehat C_n\ :\ \inf_{P\in\mathcal P_\Theta}\mathbb P_P(Y_{n+1}\in\widehat C_n(X_{n+1}))\ge 1-\alpha} \ \sup_{P\in\mathcal P_\Theta}\mathbb E_P\!\big[|\widehat C_n(X_{n+1})|\big].

Determine sharp rates/constants of $\mathcal R_{n,\Theta}^*(\alpha)$ in $(n,\alpha,d,\Theta)$ and whether computationally efficient procedures attain them.

Now separate conditional targets:

Exact conditional coverage (known impossible distribution-free):

\forall P\in\mathcal P,\ \forall x\in\operatorname{supp}(P_X):\ \mathbb P_P\!\big(Y_{n+1}\in\widehat C_n(X_{n+1})\mid X_{n+1}=x\big)\ge 1-\alpha.

Relaxed conditional coverage, e.g. $(\delta,\alpha)$ -approximate conditional coverage:

\forall P\in\mathcal P_\Theta,\ \forall A\in\sigma(X)\ \text{with }P_X(A)\ge\delta:\ \mathbb P_P\!\big(Y_{n+1}\in\widehat C_n(X_{n+1})\mid X_{n+1}\in A\big)\ge 1-\alpha.

Characterize minimax-optimal length under such relaxed conditional criteria (or other precisely specified local/averaged variants) and compare conformal-type procedures to minimax lower bounds.

See Vovk et al. (2005) for conformal prediction, Lei & Wasserman (2014), Romano et al. (2019), Barber et al. (2021), and Gibbs & Candès (2021).

§ Discussion

Loading discussion…

§ Significance & Implications

Distribution-free predictive inference is central in statistics and machine learning. Conformal methods provide finite-sample marginal validity under exchangeability, but practical guarantees depend on finite-sample score calibration choices (typically conservative at the $1/(n+1)$ scale due to quantile discretization/tie handling). Exact conditional coverage is impossible without additional assumptions, so the key frontier is sharp efficiency and computational optimality under explicit structural restrictions and under well-defined relaxed conditional targets.

§ Known Partial Results

Lei et al. (2014): Unrestricted minimax objective under only distribution-free marginal validity is degenerate: the worst-case expected length over all Borel laws is infinite, so meaningful minimax analysis requires restricting $\mathcal P$ .
Vovk et al. (2005): conformal prediction gives finite-sample marginal validity under exchangeability (with finite-sample calibration/discretization caveats).
Lei & Wasserman (2014): early distribution-free prediction-band constructions and analysis for nonparametric regression settings.
Romano et al. (2019): conformalized quantile regression with finite-sample marginal validity under exchangeability.
Barber et al. (2021): exact conditional coverage is impossible distribution-free except with vacuous/very wide intervals.
Gibbs & Candès (2021): adaptive conformal methods for certain distribution-shift regimes, outside exact conditional guarantees.