The Label Complexity of Class-Conditional Coverage under Distribution Shift

Abstract:Standard evaluation of many recognition systems contains distribution shift by construction, since benchmarks place disjoint conditions in the training and test splits. Under such a shift, split conformal prediction keeps marginal coverage near the nominal level while per-class coverage fails silently: on a real cross-subject skeleton benchmark, marginal coverage stays near ninety percent, the worst action class is covered about seventy percent of the time, and ten of the sixty classes fall below eighty percent coverage. We characterize the cost of restoring per-class validity. First, an impossibility: once the shift acts jointly on the covariates and the labels, the target class-conditional score law is unidentified from source labels and an unlabeled target sample, so no label-free method attains per-class coverage that is at once valid and efficient. Second, we make the cost precise: per-class validity alone needs only a handful of target labels per class, while the label count necessary and sufficient for validity together with per-class efficiency grows as the inverse square of the efficiency tolerance and the logarithm of the number of classes, with matching upper and lower bounds. Third, within the evaluated prediction-powered inference family, even the most favorable use of the classifier's own pseudo-labels on an unbounded unlabeled target pool improves efficiency by at most a small constant factor where coverage collapses. Skeleton action recognition is our real-data case study. A per-class calibration using source labels alone recovers a substantial share of the per-class gap while the shift preserves marginal coverage, and stops helping exactly when marginal coverage itself breaks. Three real shifts of increasing severity trace this boundary, and the same collapse and recovery appears on a natural-image corruption benchmark, beyond any single modality.

Machine Learning (cs.LG); Computer Vision and Pattern Recognition (cs.CV)

arXiv:2607.18088 [cs.LG]

(or arXiv:2607.18088v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2607.18088 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.