Conditional validity of inductive conformal predictors

Conformal prediction was introduced by Vovk and collaborators in 1999 as a finite-sample, distribution-free approach to set-valued prediction. Full conformal predictors can be computationally expensive, motivating inductive conformal predictors from Papadopoulos et al. Later work by Lei and Wasserman and by Lei et al. studied batch-mode behavior. This paper focuses on the gap between ICP’s unconditional validity and stronger conditional notions.

A predictor with 5% overall error could make errors 10% of the time for men and 0% for women, or behave very differently for email and spam. The paper asks which conditional guarantees can be obtained from ICP, how to obtain label-specific control, and whether exact object-conditional validity can coexist with finite, useful prediction sets in rich spaces such as R.

The paper makes three main advances. It derives PAC training-conditional validity and a sharper binomial characterization. It proposes conditional ICP, which uses an inductive taxonomy to calibrate within categories and obtains label-conditional validity. Finally, it proves a distribution-free impossibility result: exact object-conditional validity over non-atomic object spaces forces inefficient prediction sets. These results connect constructive algorithms with fundamental limits.

• �� Split l examples into m proper-training observations and n=l−m calibration observations.
• �� Define A((z_1,…,z_m),z)=Δ(y,f(x)); in the experiment, f is produced by MART and Δ is equation (16).
• �� Compute p_y=(#{i:α_i≤α_y}+1)/(n+1), then output Γε={y:p_y>ε}.
• �� Express excessive conditional error through a binomial variable B_{n,E}; Hoeffding yields exp[−2(E−ε)^2n]≤δ.
• �� For conditional ICP, define κ=K(training set,z) and compare α_y only with calibration scores having the same κ. Setting K(z)=y gives label-conditional ICP.
• �� For object-conditional impossibility, perturb the distribution on a positive-mass set of non-atoms and use total variation and Fubini arguments to derive contradiction.

The empirical study uses the UCI Spambase dataset: 4,601 emails, with email coded 0 and spam coded 1. After random permutation, 2,602 examples form the proper training set, 999 the calibration set, and 1,000 the test set. MART models the spam-versus-email log-odds. The study compares standard ICP with label-conditional ICP at ε=5%, examining p-value scatterplots and the frequencies of errors, empty predictions, and multiple-label predictions.

Proposition 1 gives unconditional error at most ε under exchangeability. Proposition 2a gives E≥ε+√(−lnδ/(2n)), while Proposition 2b replaces the conservative bound with δ≥bin_{n,E}(⌊ε(n+1)−1⌋). Proposition 3 establishes label-conditional validity. On Spambase, the 5% ICP is close to the target overall error, but label-specific statistics reveal that unconditional validity does not equalize email and spam risks. The label-conditional plots look similar linearly, with clearer differences on a logarithmic scale.

Spam filtering can separately manage the costs of misclassifying legitimate email as spam and allowing spam through. The same mechanism applies to medical diagnosis, fraud detection, content moderation, and multi-class risk screening. Deployment requires exchangeable or approximately stable data and enough calibration examples in every category; otherwise p-values become coarse and sets expand.

The guarantees rely on exchangeability or iid sampling and may degrade under temporal dependence, covariate shift, or label scarcity. More detailed taxonomies trade statistical power for fairness or local control. The object-conditional impossibility result targets exact distribution-free validity and therefore leaves room for model-based methods such as the Gauss linear model, smoothness-based local procedures, and asymptotically valid regression methods. Computationally, ICP is efficient, but calibration data are unavailable for fitting the primary model.