A different learning guarantee
A classifier gives a single label. Sometimes it is useful to return a set of plausible labels and control how often that set misses the true label. Split conformal prediction offers such a guarantee without requiring a correct probability model. Its guarantee concerns the joint experiment that draws the calibration sample and a future example: it does not promise that every individual or group is covered at the same rate.
Definition 11.1.1
(Nonconformity score and the calibration setting)
Let labels be . Fix a measurable, finite-valued nonconformity score independently of the calibration and test examples; larger values mean that label fits input less well. For example, a previously trained function can use . The score need not be a calibrated probability. It may be obtained from a separate training sample, provided that sample is independent of the calibration and test examples.
Let be exchangeable, conditional on any separate training data; independent identically distributed observations are a sufficient case. We need and . The calibration scores are for . The true test label is not used to construct the set.
The finite-sample rule
Definition 11.1.2
(Split conformal cutoff and prediction set)
Sort the calibration scores as and set
For a new input , return the set
The index uses , not : the unknown test score occupies one of the ranks. When , this rule uses rather than an observed finite cutoff; returning both labels is conservative and makes the rule well-defined.
Theorem 11.1.3
(Marginal coverage from exchangeable ranks)
Under the stated assumptions, . The probability averages over the calibration and test examples, conditional on any independent training data.
Proof
(Marginal coverage from the rank of the test score)
Condition on the separate training data, so the score function is fixed. Attach i.i.d. continuous tie-breakers , independent of all scores and training data, and order the pairs lexicographically. The examples are exchangeable and the tie-breakers are i.i.d., so the pairs are exchangeable; they are almost surely distinct, so the rank of the test pair among the pairs is uniform on .
If , then and the true label is covered with probability one. Otherwise . On the event the test pair is among the smallest pairs, so at most calibration pairs precede it and the th smallest calibration pair comes after it. The lexicographic order refines the order of scores, hence , that is, . The coverage probability is therefore at least . The tie-breakers are a proof device only: the rule itself keeps equality and uses no randomization.
Proof X-ray
Where exchangeability and the count $n+1$ enter
Three ingredients carry the proof. Exchangeability is used exactly once, to make the test rank uniform; nothing about the score or the data distribution is used, which is why the guarantee holds for every distribution. The tie-breakers turn a possibly tied sample into a strict ranking without changing the event of interest: the lexicographic order refines the score order, so still forces . This implication is one-sided, so ties can only make the nonrandomized set larger. The count appears because the test score is one of the ranked items; the index would calibrate against the wrong number of positions. If the score depends on the calibration data, the first ingredient fails: the pairs are then no longer exchangeable.
The guarantee is conditional on the independent training data, but generally not conditional on the realized calibration set. It is also about the true label, not a statement that each label in the set has posterior probability at least . A large set can be safe but uninformative; coverage alone does not control its size.
Proposition 11.1.4
(Exact coverage when scores have no ties)
Suppose, in addition to the assumptions above, that the scores almost surely have no ties. Then , and consequently
Proof
(Counting ranks without tie-breakers)
Without ties the rank of the test score among the scores is uniform on by exchangeability. For , if then , and if then at least calibration scores are strictly smaller than , so . Hence coverage is exactly . For the coverage is . Finally gives the lower bound and gives the upper bound.
Worked calibration
Worked example 11.1.5
(A cutoff, a set and an empty set)
Take four calibration scores and . Then and . With the score and , the candidate scores are and , so . With , the scores are and , so the set is empty. An empty prediction set is allowed by this rule; the theorem bounds its contribution to marginal miscoverage and does not rule it out at a particular input.
If instead with the same four scores, and the cutoff is . Both labels are returned. Replacing the cutoff by the largest observed score would be a different rule and would not inherit this proof at the requested level.
Worked example 11.1.6
(Exact coverage by counting ranks)
Take and . Then and . With tie-free scores the test score is equally likely to occupy any of the five ranks, and the true label is covered exactly when its rank is , or . Coverage is therefore . This lies in , as the proposition asserts, and it is slightly conservative because is not an integer.
Worked example 11.1.7
(Ties keep the rule conservative)
Suppose the score is the constant on every example, so all five scores tie. With and we get and . The test score satisfies , so the true label is covered with probability one, not merely . The rule uses and does not break ties, so with ties coverage can only exceed the tie-free value. The price is a larger set: here keeps every label whose score is .
Marginal coverage can hide a poorly covered group
Counterexample mode
Group coverage can sit far below the marginal level
Consider a deliberately simple distribution with , , and always. Define the fixed score for the true label by and ; let for both inputs. Take independent calibration examples and , so . The cutoff is one exactly when at least two calibration inputs are ; otherwise it is zero.
On a test input , the true label is covered exactly when that cutoff is one. Its conditional coverage is therefore
well below . On , the true score is always zero and coverage is one. The overall coverage is about , still above . No contradiction occurs: the theorem averages over groups. This example does not claim that this score is a useful classifier; it isolates the quantifiers in the guarantee.
When the argument stops applying
The proof needs exchangeable calibration and test examples after the score is fixed. Tuning the score or choosing after inspecting the same calibration scores can invalidate the stated rank argument. A distribution shift can also break exchangeability. Separate analysis is needed for dependence, adaptive reuse of calibration data, conditional coverage or group guarantees. Likewise, training accuracy and the probability-model quality may affect set size but are not assumptions that turn marginal coverage into a promise for every input.
Common mistake
(Using instead of in the index)
The index looks natural but undercovers. For and it gives , and with tie-free scores the coverage is . The correct index gives . The test score takes one of ranks, so the level must be computed against .
Common mistake
(Fitting the score on the calibration data)
If the function is fitted on the same examples later used for calibration, the calibration pairs are no longer exchangeable with a fresh test pair: a fitted model typically fits its own examples better than new ones, so the calibration scores run small, is too small, and the set can miss more than a fraction of new labels. Fit the score on a separate sample, as the setting requires.
Exercises and solutions
Quick check
(For and , find . With distinct exchangeable scores, what coverage does the rule have?)
Use and the tie-free proposition.
Solution · Answer
. With distinct exchangeable scores the test rank is at most with probability ; ties can make the nonrandomized set more conservative.
Quick check
(For and , what cutoff does this rule use?)
Compute and compare it with .
Solution · Answer
, so and both labels are returned.
Quick check
(If all calibration scores equal and , is a test candidate with score exactly included?)
Look at the inequality in the definition of .
Solution · Answer
Yes. Here and the rule uses , which keeps ties rather than discarding them.
Quick check
(With , does the theorem imply coverage in every subgroup?)
Recall over which randomness the probability is taken.
Solution · Answer
No. It is a marginal statement, averaged over the groups; the two-group example gives a counterexample, with coverage about on the rare group.
For a primary research treatment of split conformal marginal coverage and its assumptions, see Gibbs, Cherian and Candès, Conformal prediction with conditional guarantees, Section 2.1.