Prediction Set

The foundational property of a conformal prediction set is the marginal coverage guarantee. For a user-specified confidence level (e.g., 95%), the probability that the true label falls within the prediction set is at least that level, averaged over the randomness in both the calibration and test data.

• Mechanism: This is achieved by calibrating a nonconformity score threshold on a held-out calibration set.
• Finite-Sample Validity: The guarantee holds for any finite sample size, not just asymptotically.
• Model-Agnostic: The guarantee is independent of the underlying model's accuracy or architecture.

Unlike Bayesian methods or Gaussian processes, conformal prediction sets do not require assumptions about the underlying data distribution. The marginal coverage guarantee holds for any distribution, provided the data points are exchangeable.

• No Normality Assumption: Works with heavy-tailed, multi-modal, or unknown distributions.
• Robust to Model Misspecification: The guarantee remains valid even if the predictive model is poorly specified or biased.
• Practical Implication: This makes prediction sets trustworthy in complex, real-world environments where data rarely follows textbook distributions.

A well-designed prediction set is adaptive: its size reflects the difficulty of the specific input. For easy, unambiguous cases, the set should be small (often a singleton). For ambiguous or novel inputs, the set expands to maintain the coverage guarantee.

• Uncertainty Quantification: The set size itself is a direct, interpretable measure of predictive uncertainty.
• Nonconformity Score Design: Adaptivity depends on the choice of nonconformity measure. A normalized score (e.g., prediction error divided by estimated variance) produces more adaptive sets.
• Example: In medical imaging, a clear X-ray yields a single diagnosis, while an ambiguous one yields a set of possible conditions.

While validity is guaranteed, efficiency measures how small the prediction sets are on average. A trivial predictor that always returns the set of all possible labels is valid but useless. The goal is the smallest set that maintains the coverage guarantee.

• Metric: Often measured by average set size or the fraction of singletons.
• Model Dependence: Efficiency depends heavily on the quality of the underlying model and the nonconformity measure.
• Trade-off: Higher confidence levels (e.g., 99% vs. 90%) produce larger, less efficient sets.

The standard marginal guarantee does not imply conditional coverage—the guarantee that coverage holds for every specific subgroup or feature value. Achieving exact conditional coverage is statistically impossible without strong distributional assumptions.

• Mondrian Conformal Prediction: A technique that applies calibration independently within pre-defined categories to achieve label-conditional coverage.
• Approximation Methods: Weighted conformal prediction and adaptive methods can approximate conditional validity.
• Practical Impact: A medical diagnostic set might have 95% coverage overall but only 80% for a specific demographic subgroup.

The standard conformal prediction framework relies on the assumption of exchangeability: the joint distribution of the calibration and test data is invariant under permutation. This is a weaker condition than the independent and identically distributed (IID) assumption.

• Violations: Time series data with temporal dependencies or data with distributional shift violate exchangeability.
• Mitigations: Adaptive conformal inference and sliding-window calibration sets can restore approximate validity in non-exchangeable settings.
• Diagnostic: Monitoring the empirical coverage over time can detect violations of the exchangeability assumption in production.