PaperlayerView exact revision on arXiv

Source-linked AI summary

PICPIs: Prediction-Interval-Conditional Prediction Intervals

Xuelin Yang, Baihe Huang, Yilong Hou, Guido Imbens, Michael I. Jordan

arXiv:2609.25388v1stat.MLcs.AIcs.LGmath.STstat.ME

TL;DR

Marginal conformal validity does not directly assess uncertainty for a specific prediction, while fully conditional coverage given covariates is generally unattainable without strong assumptions. PICPIs condition on intervals of model predictions and require the mean outcome among predictions in each interval to lie within that interval. Inference procedures for probabilistic prediction bound marginal miscoverage by within-stratum variation of 𝑝∗(𝑋) and prediction mass not covered by PICPIs; multi-class classification has worst-case class-conditional coverage certificates.

  • Problem

    Marginal conformal validity does not directly assess uncertainty for a specific prediction, while fully conditional coverage given covariates is generally unattainable without strong assumptions.

    Source: §1 · p. 2

  • Method

    PICPIs condition on intervals of model predictions and require the mean outcome among predictions in each interval to lie within that interval.

    Source: §1 · p. 2

  • Results

    Inference procedures for probabilistic prediction bound marginal miscoverage by within-stratum variation of 𝑝∗(𝑋) and prediction mass not covered by PICPIs; multi-class classification has worst-case class-conditional coverage certificates.

    Source: §1 · p. 4

  • Takeaways & Limitations

    PICPIs provide locally adaptive uncertainty quantification for probabilistic prediction and multi-class classification without modifying the base predictor.

    Source: §7 · p. 20

    Empirical self-consistency yields narrower intervals but does not retain the theoretical population validity guarantee, and the shortest intervals are more prone to false acceptance.

    Source: §5.4 · p. 15

Abstract

from arXiv · show

A classical question in statistics is which observable quantities to condition on when drawing inferences about unobservable targets. For conformal prediction in nonparametric uncertainty quantification, standard marginal validity offers limited resolution at the prediction values on which decisions are based, and fully conditional guarantees with respect to the covariates are provably unattainable. We address this gap by introducing a prediction-based conditioning framework that we refer to as Prediction-Interval-Conditional Prediction Intervals (PICPIs). Formally, a PICPI is an interval $I$ satisfying a self-consistency condition: $$\mathbb{E} [Y \mid p(X) \in I] \in I,$$ for predictive model $p$, contextual covariate $X$, and outcome $Y$. Thus, an interval simultaneously defines a stratum of prediction values and certifies that the mean outcome in that stratum lies in the same interval. This self-consistency condition yields data-adaptive strata without altering the original prediction. Such intervals can be constructed using practical algorithms. Under regularity of the prediction distribution, the constructed intervals cover all but an arbitrarily small fraction of prediction values and have widths that decrease at rate $n^{-1/3}$, up to logarithmic factors and the prediction error. Moreover, identifying these locally calibrated intervals can, in turn, inform downstream decision-making. We derive inference procedures for PICPIs in probabilistic prediction and multi-class classification, accompanied by theoretical guarantees. Empirical results are provided that compare PICPIs with existing interval-based baselines.

1. Introduction

Conformal prediction offers marginal validity but not direct uncertainty assessment for a specific prediction, while fully conditional coverage given covariates is generally unattainable without strong assumptions. PICPIs instead condition on prediction intervals, which serve as both prediction strata and certificates of their mean outcome, with theoretical guarantees and inference procedures for probabilistic prediction and classification.

1. Introduction

  • PICPIs address the limited resolution of marginal conformal validity, while fully conditional coverage given covariates is generally unattainable without strong distributional assumptions.The proposed alternative conditions on model predictions rather than covariates.Source: §1 · p. 2
  • PICPIs condition on intervals of model predictions, requiring the mean outcome among predictions in each interval to lie within that same interval.This self-consistency condition makes each interval both a prediction stratum and a calibrated uncertainty statement for that stratum.Source: §1 · p. 2
  • Unlike fixed-bin calibration diagnostics, PICPIs identify local, data-adaptive prediction regions without forcing recalibration.The intervals can identify regions of the prediction space that are directly actionable for downstream decision-making.Source: §1 · p. 3
  • ˜O(n^-1/3) plus prediction error controls interval widths while the algorithm covers all but a user-specified prediction mass.These widths vanish when the base predictor is consistent.Source: §1 · p. 3
  • PICPIs provide inference procedures for probabilistic prediction and multi-class classification with theoretical guarantees.Probabilistic prediction has marginal miscoverage bounded by within-stratum variation of p*(X) plus uncovered prediction mass; classification has worst-case class-conditional coverage certificates and set-size optimality for a prescribed threshold, allowing data reuse.Source: §1 · p. 4

2. Definition, Algorithmic Construction, and Validity

PICPIs group predictions into intervals whose conditional mean outcome lies within the same interval. A calibration procedure constructs valid intervals, and inference selects the shortest returned interval containing a new prediction.

2. Definition, Algorithmic Construction, and Validity

  • A PICPI is an interval in prediction space that groups similar predictions and contains the group’s true underlying outcome probability.The section focuses on binary outcomes and notes that the definition extends to regression with bounded real-valued outcomes.Source: §2 · p. 4
  • The population algorithm tests discretized candidate intervals for the PICPI condition, then returns the shortest admitted interval containing the new prediction.A disjoint summary can instead be selected to maximize covered length.Source: §2 · pp. 4–5
  • The algorithm requires the empirical label average to lie inside each candidate interval with a concentration margin that grows when fewer calibration observations fall there.This margin compensates for noisier estimates in sparsely sampled intervals.Source: §2 · p. 4
  • With probability at least 1 − δ, every interval returned by Calibration is a PICPI under the population distribution.The guarantee assumes i.i.d. calibration data and a predictor fixed independently of those observations.Source: §2 · p. 5
  • The paper distinguishes population-valid intervals from an empirical version that satisfies the PICPI property under the calibration sample’s plug-in distribution.The empirical and population procedures target different measures, analogous to empirical and population CDFs.Source: §2 · p. 5

3. Properties of PICPIs

Under prediction error and regularity conditions, PICPIs cover most prediction mass while their widths shrink as the calibration sample grows. Supporting lemmas establish the interval construction, transfer bounds, and outcome-scope qualifications.

3. Properties of PICPIs

  • Under predictor error ε and λ-regularity of predicted probabilities, PICPIs cover most predictions and shrink in width as calibration sample size grows.The rate depends on ε, λ, and sample size; the theorem’s proof sketch notes that adaptive bounds using additional model structure remain open.Source: §3 · p. 6

3.1. Supporting lemmas

  • A constructive partition produces intervals with conditional means away from their boundaries, bounded lengths, and all but a δ-fraction of probability mass covered.The proof discretizes [0, 1] and builds a directed graph over bins to construct the intervals.Source: §3.1 · p. 7
  • For jointly distributed U,V over [0,1] with E[|U−V|] ≤ ε>0, for any δ>0, selected intervals have conditional expected-value discrepancy at most 2ε/δ and union mass at least 1−2δ.Source: §3.1 · p. 8
  • For bounded outcomes, the construction and finite-sample argument extend by using empirical outcome averages and affine rescaling.For unbounded outcomes, the definition can still apply when conditional expectations exist, but distribution-free concentration guarantees require additional tail or moment assumptions.Source: §3.1 · p. 8

4. Inference via PICPIs

PICPIs support prediction intervals for probabilities and label sets for multi-class classification. The resulting procedures provide marginal or class-conditional coverage guarantees, with an optimality result and a feasible same-sample certificate for label sets.

4. Inference via PICPIs

  • PICPIs support two inference tasks: interval prediction for probabilities and label-set prediction for classification.Source: §4 · p. 8

4.1. Interval prediction for probabilities

  • The marginal coverage error for a true probability interval is bounded by within-PICPI variation in true probabilities and prediction mass not covered by PICPIs.The theorem applies when the disjoint PICPIs satisfy its hypotheses; the intervals and predictor may be conditioned on when constructed independently of the test observation.Source: §4.1 · p. 9
  • Under uniform prediction error or a Lipschitz-type condition, the within-interval variation term admits explicit bounds in terms of interval lengths.With uniform error at most η, the range length is at most |I_j| + 2η.Source: §4.1 · p. 9

4.2. Label set prediction for multi-class classification

  • For multi-class label sets, PICPIs provide an exact worst-case class-conditional coverage certificate and minimize expected set size among deterministic unions of classwise intervals at prescribed coverage.The certificate is defined through worst-case class-conditional miscoverage over one-vs-rest laws satisfying the PICPI definition.Source: §4.2 · pp. 10–12
  • A feasible label-set procedure uses the same calibration sample to construct intervals and estimate their masses while retaining valid class-conditional coverage.Its finite candidate interval family permits uniform concentration control over selected intervals.Source: §4.2 · pp. 12–13

5. Experiments

Across two prediction tasks, the experiments compare PICPI-based intervals or label sets with interval-based and classification baselines. PICPI shows favorable calibration, coverage, and size tradeoffs, while empirical self-consistency trades population validity for narrower intervals.

5.1. Task 1: Interval prediction for probabilities.

  • Task 1 evaluates probability intervals using one- and 20-dimensional covariates with binary outcomes, with predictors, intervals, and evaluations formed on separate data splits.The supplied passages refer to Appendix B.3 for data-generating details.Source: §5.1 · p. 14, §5 · p. 14

5.2. Task 2: Label set prediction for multi-class classification.

  • Task 2 constructs a label set by selecting, for each class, the interval containing its predicted probability; experiments use linear-Gaussian and nonlinear-mixture softmax DGPs.The DGPs use 10 covariates and four classes, with disjoint training, calibration, and evaluation splits.Source: §5.2 · p. 14, Figure 6 · p. 18

5.3. Baselines

  • The comparisons include PICPI, simultaneous confidence intervals, split conformal, calibration-based and fixed-width binning, and conformal classification for Task 2.The baselines use distinct constructions and guarantees, including marginal coverage for split conformal and conformal classification.Source: §5.3 · p. 14

5.4. PICPIs with empirical self-consistency

  • The empirical algorithm returns intervals self-consistent on calibration data, but omitting the concentration margin removes the population-validity guarantee and leaves the shortest intervals more prone to false acceptance.Most proposed intervals satisfy the PICPI condition on held-out data; intervals of length at most 0.03 are more prone to false acceptance.Source: §5.4 · p. 15

5.5. Task 1 Results

  • In the univariate visualization, PICPI tracks the nonlinear target probability more faithfully than the two binning baselines, while split conformal is visibly conservative.With a misspecified decision-tree predictor, PICPI adjusts endpoints around score plateaus and widens intervals where calibration data reveal instability or mismatch.Source: §5.5 · pp. 16–17, Figure 5 · p. 17
  • PICPI attains the lowest calibration errors, shorter intervals than simultaneous and split conformal methods, and higher true-probability coverage than binning baselines.Table 1 compares interval length, calibration errors, and coverage across methods.Source: §5.5 · p. 17, Table 1 · p. 17

5.6. Task 2 Results

  • PICPI provides the most stable worst-class coverage relative to set size across both DGPs, while maintaining the smallest prediction sets and tracking target coverage closely.Competing methods deteriorate substantially under the nonlinear-mixture DGP; standard conformal classification has poor worst-class coverage despite marginal coverage guarantees.Source: §5.6 · pp. 17–18, Figure 6 · p. 18

6. Related Work

Conformal prediction has finite-sample marginal validity, while distribution-free fully conditional coverage is generally impossible except with vacuous sets. Related work weakens conditioning targets or studies calibration; PICPIs instead use score intervals to certify the conditional mean outcome.

Conformal prediction and conditional coverage

  • Conformal prediction provides finite-sample marginal validity under exchangeability, but distribution-free conditional coverage is impossible in the worst case except with vacuous sets.Weaker targets include Mondrian or group-conditional validity, multivalid coverage, and analyses under additional assumptions.Source: §6 · pp. 18–19

Prediction-conditioned inference

  • PICPIs condition on intervals of the model score rather than the full covariate vector, yielding score-conditional calibration intervals rather than response intervals.Theorem 3.2 studies these intervals’ shrinking widths, unlike work on response-interval length or oracle efficiency.Source: §6 · p. 19

Calibration

  • Unlike post-hoc calibration methods that modify scores, PICPI seeks data-adaptive score subsets where the conditional mean outcome lies in the same interval.Classical conformal prediction controls the event that the outcome belongs to a prediction set; PICPI applies conformal-style uncertainty quantification to the conditional mean along the score axis.Source: §6 · p. 19

Calibration and related methods

  • PICPI is a score-indexed analogue of multicalibration, using subsets of the score axis and an interval-valued guarantee rather than externally specified groups and additive error bounds.Related calibration precedents produce calibrated probabilities or probability intervals; PICPI simultaneously identifies the conditioning interval and makes its uncertainty statement.Source: §6 · p. 20

7. Conclusions

The conclusions present PICPIs as locally adaptive uncertainty quantification that leaves the base predictor unchanged and has shrinking widths under suitable regularity. The appendix fragments outline proofs of the PICPI guarantee, interval construction, and a concentration bound.

7. Conclusions

  • PICPIs provide local, data-driven uncertainty quantification without modifying the base predictor, and their widths shrink with sample size under suitable regularity conditions.The stated practical scope includes probabilistic prediction and multi-class classification with respective coverage guarantees.Source: §7 · p. 20

A.1. Proof of Theorem 2.2

  • With probability at least 1 − δ, the algorithm’s returned intervals form a set of PICPIs, using Hoeffding’s inequality and a union bound.The proof estimates conditional means on discretized intervals from empirical counts and outcomes.Source: §A.1 · p. 24

A.2. Proof of Theorem 3.2

  • The proof constructs disjoint intervals [a_i,b_i] whose conditional means of p(X), given p(X)∈[a_i,b_i], lie within endpoint margins ε1·1(a_i≠0) and ε1·1(b_i≠1); under A1∩A2, [a_j,b_j] is included in I.Source: §A.2 · pp. 25–26

A.3. Proof of Lemma 3.3

  • For the intervals in Lemma 3.3, the proof lower-bounds expected sample counts and applies a lower-tail multiplicative Chernoff bound followed by a union bound.The stated expected count is at least λcn.Source: §A.3 · pp. 27–28

A.4. Proof of Lemma 3.4

The proof discretizes the prediction range and constructs intervals from a directed graph over bins. It establishes interval mean bounds, removes intervals that fail a further property, and uses the resulting PICPIs in a coverage argument.

A.4. Proof of Lemma 3.4

  • Discretization and a directed graph over bins yield intervals whose conditional means lie within their endpoints up to ε, while truncating chains bounds discarded probability mass.The graph directs edges toward neighboring bins based on their conditional means or probability masses; constructed intervals contain a bounded number of vertices.Source: §A.4 · pp. 28, 30

A.5. Proof of Lemma 3.5

  • The proof removes intervals that fail Eq. (11); the remaining intervals satisfy Eq. (11) and Eq. (12).The argument uses that each point belongs to at most two intervals.Source: §A.5 · p. 32

A.6. Proof of Theorem 4.1

  • The Theorem 4.1 proof partitions events by intervals and uses the PICPI condition with conditional Chebyshev bounds when p*(X) lies outside an expanded interval.For a positive-mass interval, the proof defines the conditional mean of p*(X) on its event and relates it to the interval through the PICPI condition.Source: §A.6 · pp. 32–33

A.7. Proof of Theorem 4.3

The supplied proof fragments establish exactness by showing that the miscoverage numerator can attain the smaller of two bounds. They also invoke interval-conditional means and endpoint bounds in the argument.

A.7. Proof of Theorem 4.3

  • For retained intervals, the conditional mean lies in the interval by the PICPI definition, while omitted classes are associated with the uncovered event or specified intervals.The proof partitions the relevant events before bounding the miscoverage numerator.Source: §A.7 · p. 33
  • The proof bounds the numerator using endpoint constraints on interval means and establishes attainability of the lower bound as well as the upper bound.The displayed fragments identify the attainable range and state that both bounds can be attained.Source: §A.7 · pp. 34–35
  • The proof targets exactness by showing that the miscoverage numerator can attain min{U, L}.It treats cases attaining U and L, then concludes exactness in both cases.Source: §A.7 · pp. 34–35

A.8. Proof of Theorem 4.4

The proof establishes size-optimality by decomposing the global minimization into independent classwise problems and summing their minima.

A.8. Proof of Theorem 4.4

  • The objective and feasibility constraints separate by class, so the global problem decomposes into G independent classwise problems whose optimizers are S★_g(α_g).Summing the classwise minima proves the result.Source: §A.8 · p. 36

A.9. Proof of Theorem 4.5

The proof establishes simultaneous validity across classes and candidate intervals using concentration bounds. The accompanying baselines describe alternative interval or set construction procedures and the metrics used to compare them.

A.9. Proof of Theorem 4.5

  • Theorem 4.5 follows by combining simultaneous bounds over classes and candidate intervals with the event on which Algorithm 1 returns genuine disjoint PICPIs.The proof also conditions on the realized intervals so Theorem 4.3 applies to them.Source: §A.9 · pp. 36–37

B.1. Baselines

  • For Task 1, PICPI uses an ε-expansion procedure; for Task 2, classes are included when their predicted probabilities lie in acceptance regions from Algorithm 2.For Task 2, the solver selects a minimum-mass classwise subset whose plug-in two-sided certificate meets the target α.Source: §1 · p. 39, §6 · p. 40

3. Split conformal prediction.

  • Split conformal uses calibration residual quantiles, while the accompanying bin-based procedure retains bins with mass-weighted calibration error close to PICPI’s.The split conformal interval is formed around the prediction using the empirical residual quantile.Source: §3 · p. 39, §4 · p. 39

4. Calibration-based interval.

  • The calibration-based baseline reports the fixed bin containing the prediction as its interval.Source: §5 · p. 39

6. Conformal classification.

  • For Task 2, conformal classification forms a label set by thresholding class probabilities and has a marginal test-data guarantee.Its calibration set selects the threshold on point predictions.Source: §6 · pp. 39–40

2. Simultaneous confidence interval.

  • The simultaneous-confidence-interval baseline uses a Wald confidence region for the fitted parameter and includes a class when its upper endpoint meets the calibrated threshold.The confidence interval for the true conditional probability is computed using a chi-square critical value.Source: §2 · p. 39, §6 · p. 40

B.2. Metrics

  • Task 1 reports interval length, calibration errors, prediction-space coverage, and target-probability coverage; Task 2 also reports average prediction-set size.Source: §B.2 · p. 40
  • The interval ECE metrics compare interval midpoints or predictions with average target probabilities among assigned points, and relative ECE divides each method’s mean ECE by the smallest mean ECE.ECE_mid reflects midpoint centering; ECE_pred reflects alignment between grouped predictions and target probabilities.Source: §B.2 · p. 40

B.3. Setup for Task 1

The experimental setups evaluate interval methods on noisy logistic prediction and multiclass classification tasks, including correctly specified and misspecified models. Additional procedures assess interval widths and select disjoint intervals with maximum coverage.

B.3. Setup for Task 1

  • Task 1 uses noisy logistic data and evaluates coverage against the noise-free target probability, distinct from the Gaussian-averaged marginal conditional label probability.The setup uses a shared logistic-regression predictor, α=0.1, and 50 candidate bins for PICPI and the binning baselines unless otherwise stated.Source: §B.3 · p. 41
  • Empirical-mode diagnostics compare empirical- and population-mode PICPI across calibration sizes from 10^3 to 3 × 10^7, using 50 replications per size.The held-out target is the Gaussian-averaged marginal probability.Source: §B.3 · p. 42

B.4. Setup for Task 2

  • Task 2 coverage sweeps use four classes and compare a correctly specified linear-Gaussian DGP with a nonlinear-mixture DGP whose multinomial logistic working model is misspecified.The sweep covers 16 target-coverage levels, and the curves average 1,000 independent replications.Source: §B.4 · pp. 42–44

B.5. Setup for Figure 2

  • Figure 2 evaluates each interval system by the minimum width of an interval containing the target probability, assigning width 1 when no interval contains it.The procedure fits a logistic estimator, calibrates an interval collection, and evaluates it on an independent fold.Source: §B.5 · p. 44

C. Additional Algorithms

  • DisjointCalibration first enforces a maximum interval length, then uses weighted interval scheduling to select a non-overlapping subset with maximum total covered length.The scheduling procedure sorts by end time and uses dynamic programming and backtracking.Source: C. Additional Algorithms · pp. 44–45
Loading 2609.25388v1…