The Label Complexity of Useful Class-Conditional Prediction Sets under Distribution Shift

Conformal prediction guarantees that prediction sets cover truth, but under distribution shift, this guarantee can mask severe class-specific undercoverage. This paper investigates the label cost required to restore per-class validity when a shift acts jointly on covariates and labels, demonstrating that no label-free method can be both valid and efficient uniformly over target laws consistent with observed source distributions.

The Core Problem

The central issue is that standard split conformal prediction guarantees marginal coverage—a single reassuring number—while the shift causes per-class coverage to collapse silently, making the failure invisible to marginal diagnostics. When the shift acts jointly on covariates and labels, the target class conditional score law is unidentified, meaning no label-free method can simultaneously be valid and efficient per class uniformly over target laws consistent with observed source joint distribution and target covariate marginal.

The Impossibility Result

Proposition 2 establishes that under a joint shift where a score separates two positive probability regions, there exist two target joint laws sharing the same covariate marginal but having different class scores quantiles by an explicit constant, meaning any label-free procedure has a performance gap. Specifically, any label-free rule attaining class c coverage ≥ 1 − α under one law satisfies an expected set size bound that is strictly worse than the oracle threshold under the other law.

The Label Complexity Bound

Theorem 1 quantifies the necessary number of per-class labels required to recover class quantile accuracy to a given tolerance. The label count grows as the inverse square of that tolerance and the logarithm of the class count. This complexity is bounded by matching bounds for classwise threshold procedures, with a rate of mc = O(ε−2 log K) per class being sufficient for simultaneous ε-accurate quantile recovery and PAC validity.

Label-Free Recovery on Real Data

The study uses skeleton action recognition as a case study, showing that source Mondrian calibration—computing a separate conformal quantile for each class from the source calibration scores in that class alone—recovers much of the gap where marginal coverage holds, achieving a substantial share of the oracle gap at a small set size cost. This recovery is observed across three real shifts and extends to natural images, suggesting this label-free method works when marginal coverage holds but stops once it breaks.

Pseudo-Label Ceiling

The paper analyzes pseudo-label estimators built from prediction-powered inference (PPI). It finds that even the most favorable pseudo label estimator gains at most a small constant factor where coverage collapses. This ceiling is specific to the evaluated control span, and unlabeled target data, even the classifier’s own pseudo labels, cannot substitute for labeled target data where recovery matters most.

Methodological Comparison

The research compares several calibration methods:

1. Split Conformal Prediction (baseline): Preserves marginal coverage but allows per-class collapse.

2. Source Mondrian (class conditional): Uses source labels to partition scores by class, providing per class marginal coverage at least the nominal level under within-class exchangeability.

3. Weighted Conformal Prediction: Restores marginal coverage under covariate shift given density ratio weights, but its use with source Mondrian's quantiles inflates sets severely.

4. Margin Abstention: A negative control that controls only a joint marginal risk and does not materially improve worst class coverage.

Conclusion

The paper concludes that no label-free method is at once valid and efficient per class uniformly over consistent target laws once the shift acts jointly on covariates and labels. The cost of achieving per-class validity requires a specific number of labels, and unlabeled data cannot improve the minimax rate of recovery. For skeleton action recognition, source Mondrian recovers much of the gap when marginal coverage holds.

The gist: No label-free method can be both valid and efficient per class uniformly over target laws consistent with observed source joint distribution and target covariate marginal when the shift acts jointly on covariates and labels.

How it works

1. The setup involves summarizing each input sequence by an SPD descriptor, which captures the temporal covariance of joint coordinates and velocities.

2. Four calibration procedures are compared: Split Conformal Prediction, Source Mondrian (class conditional), Weighted Conformal Prediction, and Margin Abstention.

3. The analysis focuses on the trade-off between validity (worst-class coverage) and efficiency (mean set size).

Key Findings Enumerated

1. Marginal coverage holds near nominal levels while per-class coverage collapses silently under cross subject shift in skeleton action recognition benchmarks, with the worst class reaching approximately seventy percent coverage.

2. The source Mondrian method recovers a substantial share of the oracle gap label-free on real data when marginal coverage holds, achieving this at a small set size cost.

Based on the scientific paper The Label Complexity of Class Conditional Coverage under Distribution Shift, here are specific, high-impact improvements for AI systems:

1. Improve Reliability in Cross-Subject/Cross-Domain Deployment (Skeleton Action Recognition Focus):

2. Enhance Robustness Against Unidentified Target Distributions (Joint Covariate and Label Shifts):

3. Develop Data-Efficient Labeling Strategies for Class Conditional Guarantees:

4. Create Adaptive, Per-Class Safety Thresholds Without Massive Label Overhead:

5. Specific Improvements and Capabilities:

6. Skeleton Action Recognition Reliability Under Distribution Shift: The system can maintain near-nominal marginal coverage (e.g., 88%) even when the worst class performance collapses (e.g., to 70%), preventing catastrophic failure across all classes simultaneously, which is a key weakness of standard methods that only monitor the overall average.

7. Robustness Against Unidentified Target Distributions: The system can operate reliably on unseen subjects or environments because it does not rely on a single target law. It identifies when the joint shift (covariates + labels) makes the target class score law unknown, flagging these scenarios explicitly rather than silently failing under a misleading marginal guarantee.

8. Data-Efficient Labeling Strategies for Class Conditional Guarantees: Instead of requiring a full set of target labels to guarantee per-class safety, the system can use a handful of per-class labels (as low as 9 for 60 classes) to define a finite, non-vacuous threshold. This minimal label requirement is sufficient to recover class quantiles within specified tolerances, drastically reducing the labeling cost compared to methods requiring full oracle supervision.

9. Create Adaptive, Per-Class Safety Thresholds Without Massive Label Overhead: The system can dynamically set a specific confidence threshold for every class based on its observed source data structure (using the Source Mondrian approach). This allows the model to assign tailored safety levels—where critical classes get tighter bounds and less critical ones get looser bounds—achieving per-class validity efficiently without needing an exponentially growing number of labels.