The Label Complexity of Class-Conditional Coverage under Distribution Shift

arXiv:2607.18088v2 Announce Type: replace-cross Abstract: Conformal prediction certifies that a classifier's prediction sets cover the truth, and that certificate is marginal. Many recognition benchmarks build distribution shift into evaluation, placing disjoint conditions in the training and test splits. Under that shift the certificate stays reassuring while per class coverage fails silently: on a real cross subject skeleton benchmark marginal coverage holds near ninety percent while the worst class is covered about seventy percent and ten of sixty classes fall below eighty percent. This class specific undercoverage stays hidden behind a single reassuring marginal number. Once the shift acts jointly on covariates and labels, the target class conditional score law is unidentified, so no label free method is at once per class valid and efficient uniformly over target laws consistent with the observed source joint distribution and target covariate marginal. The per class labels needed to recover every class threshold to a given tolerance grow as the inverse square of that tolerance and the logarithm of the class count, with matching bounds for classwise threshold procedures. Pseudo labels do not shortcut it: the best prediction powered estimator gains at most a small constant factor where coverage collapses. Across three real shifts and an image corruption benchmark, source label calibration recovers much of the gap while marginal coverage holds, and stops once it breaks.

Related

• Coverage Guarantees for Pseudo-Calibrated Conformal Prediction under Distribution Shift
• Conformal Bayes under Label Shift: Post-Hoc Calibration vs. In-Training Adaptation
• Conformal Prediction Sets for Instance Segmentation

Source: arXiv cs.CV | 2026-07-28