Conservative Validity

The main article on conformal prediction deduces the asymptotic conservative validity of conformal predictors from the corresponding result for smoothed conformal predictors. The following theorem asserts the conservative validity (in a non-asymptotic sense) of conformal predictors.

Theorem All conformal predictors are conservatively valid, i.e. for any exchangeable probability distribution {$P$} on {$Z^{\infty}$} there exists a probability space with two families

{$(\xi_n^{(\epsilon)}: \epsilon \in (0, 1), n = 1, 2, \ldots), (\eta_n^{(\epsilon)}: \epsilon \in (0, 1), n = 1, 2, \ldots)$}

of {0, 1}- valued random variables such that:

• for a fixed {$\epsilon$}, {$\xi_1^{(\epsilon)}, \xi_2^{(\epsilon)}, \ldots$} is a sequence of independent Bernoulli random variables with the parameter {$\epsilon$};
• for all {$n$} and {$\epsilon$}, {$\eta_1^{(\epsilon)} \le \xi_1^{(\epsilon)}$};
• the joint distribution of {$err_n^{\epsilon} (\Gamma, P), \epsilon \in (0,1), n = 1, 2, \ldots$} coincides with the joint distribution of {$\eta_n^{(\epsilon)}, \epsilon \in (0, 1), n = 1, 2, \ldots$}, where {$\text{err}_{n} ^{\epsilon}(\Gamma, P)$} is the random variable

{$\text{err}_{n} ^{\epsilon}(\Gamma, (x_1, y_1, x_2, y_2, \ldots)) := 1$} if {$y_{n+1} \notin \Gamma^\epsilon(x_1, y_1, \ldots, x_{n}, y_{n}, x_{n+1})$} ; {$0$} otherwise.

Of course, this theorem also implies the asymptotic conservative validity of conformal predictors.

Corollary All conformal predictors are asymptotically conservative, i.e., for any exchangeable probability distribution {$P$} on {$Z^{\infty}$} and any significance level {$\epsilon$},

{$\limsup_{n\to \infty} (\sum_{i=1}^{n} err_n^{\epsilon}(\Gamma, (x_1, y_1, x_2, y_2, \ldots)))/n \le \epsilon$}

with probability one.