The Label Complexity of Useful Class-Conditional Prediction Sets under Distribution Shift
Standard conformal prediction guarantees marginal coverage but fails when a distribution shift affects both data and labels, causing per-class coverage to collapse silently. The study proves no label-free method can be simultaneously valid and efficient per class under these joint shifts. It quantifies the necessary number of labels needed to restore per-class accuracy.