The Label Complexity of Class-Conditional Coverage under Distribution Shift
This paper establishes label complexity bounds for class-conditional coverage under distribution shift, showing pseudo labels cannot fully recover class thresholds without target labels.
Key Findings
Methodology
The paper analyzes the joint effect of covariate and label shift on the identifiability of class-conditional score laws. It proves that, under such shift, no label-free method can simultaneously guarantee per-class validity and efficiency across all target laws consistent with the source distribution. The authors derive tight bounds on the number of target labels needed to recover class thresholds within a given tolerance, showing this grows with the inverse square of the tolerance and the logarithm of the number of classes. They utilize SPD geometry, log Euclidean distances, and Mondrian calibration strategies, combining theoretical proofs with empirical validation on skeleton action recognition and image corruption benchmarks, demonstrating the limited benefit of pseudo labels in coverage collapse scenarios.
Key Results
- In the NTU-60 cross-subject skeleton dataset, marginal coverage remains near 90%, but worst-class coverage drops to about 70%, with 10 out of 60 classes below 80%. Target labels significantly improve class coverage, approaching 89%, while pseudo labels provide at most an 8% boost in coverage where collapse occurs.
- Theoretical bounds show that the label count needed to recover class thresholds within a specified tolerance scales as \(\sim \varepsilon^{-2} \log K\), where \(K\) is the number of classes. No label-free method can achieve uniform per-class validity and efficiency under joint shift, emphasizing the necessity of target labels.
- Empirical results confirm that pseudo labels, even when generated from the model itself, cannot fully mitigate coverage collapse under severe distribution shifts, highlighting the fundamental limits imposed by the identifiability problem.
Significance
This work clarifies the limitations of label-free calibration methods in real-world scenarios involving distribution shift. It underscores the importance of target labels for reliable class-conditional coverage, influencing the design of robust uncertainty quantification techniques. The theoretical bounds provide a benchmark for future methods, guiding efforts to develop more efficient calibration strategies that balance label costs and coverage guarantees, especially in high-stakes applications like healthcare and autonomous systems.
Technical Contribution
The paper introduces a formal impossibility result for label-free per-class coverage under joint shift, deriving the minimal label complexity needed for class threshold recovery. It combines geometric insights from SPD manifolds with statistical analysis, establishing tight bounds that match in both upper and lower limits. The integration of Mondrian and weighted calibration strategies, along with the analysis of pseudo label limitations, advances the theoretical understanding of distributionally robust conformal prediction, setting a new standard for the field.
Novelty
This is the first rigorous proof demonstrating the fundamental impossibility of achieving both per-class validity and efficiency without target labels under joint distribution shift. The derivation of label complexity bounds that depend logarithmically on the number of classes and quadratically on the inverse tolerance is novel. Additionally, applying SPD geometry to class-conditional conformal prediction and analyzing pseudo label effectiveness in this context represent significant innovations that extend the theoretical landscape of uncertainty quantification.
Limitations
- The analysis assumes the shift acts on the joint distribution with certain geometric properties, which may not cover all real-world scenarios involving complex or dependent shifts.
- Computational costs of geometric and calibration procedures may limit scalability to very high-dimensional data or large class sets.
- Pseudo labels offer limited improvements under severe shift, indicating the need for more robust unsupervised or semi-supervised calibration methods in future work.
Future Work
Future research should explore broader classes of distribution shifts, including dependent and nonparametric models. Developing scalable algorithms for class-conditional calibration on high-dimensional data, possibly leveraging deep geometric learning, is crucial. Extending theoretical results to multi-source and dynamic environments, as well as designing adaptive pseudo-labeling strategies that better handle severe shifts, are promising directions to enhance the robustness and efficiency of conformal prediction in real-world applications.
AI Executive Summary
This paper addresses a fundamental challenge in uncertainty quantification under distribution shift: how many target labels are necessary to guarantee reliable class-conditional coverage? Traditional conformal prediction offers marginal coverage guarantees, but in real-world scenarios—such as skeleton action recognition or image corruption—these guarantees can be misleading, as class-specific coverage may silently deteriorate. The authors rigorously analyze the problem, proving that under joint covariate and label shift, the class-conditional score law becomes unidentifiable from source data alone. This impossibility result implies no label-free method can universally ensure per-class validity and efficiency across all target distributions compatible with the source.
Building on this insight, the authors derive tight bounds on the number of target labels required to recover class thresholds within a specified tolerance. They show that this number scales quadratically with the inverse of the tolerance and logarithmically with the number of classes, establishing fundamental limits on label efficiency. To support their theoretical findings, the paper employs SPD geometry, log Euclidean distances, and Mondrian calibration strategies, demonstrating their effectiveness on real datasets. Empirical experiments on NTU-60 and image corruption benchmarks reveal that while source label calibration can recover much of the class-specific coverage gap, pseudo labels—generated by the model itself—offer limited improvements once coverage collapses.
Overall, the study highlights the critical importance of target labels for reliable class-conditional coverage in shifted distributions. It provides a rigorous framework for understanding the label costs involved and sets a benchmark for future calibration methods. The results have broad implications for deploying uncertainty-aware models in high-stakes applications, emphasizing that without sufficient target supervision, achieving both validity and efficiency remains fundamentally impossible in complex shift scenarios. Despite the limitations, this work paves the way for more robust, geometry-informed calibration strategies and encourages further exploration into semi-supervised approaches for distributionally robust uncertainty quantification.
Deep Dive
Glossary
Distribution Shift (分布偏移)
指模型在训练和测试数据的统计分布不一致，影响模型性能。In the paper, it refers to changes affecting covariates and labels simultaneously.
Conformal Prediction (符合预测)
一种提供置信保证的统计方法，确保预测集覆盖真实值。In this context,保证边际覆盖率。
SPD Geometry (对称正定矩阵几何)
描述SPD矩阵空间的几何结构，用于定义距离和平均值。In the paper,用于类别条件分数的几何距离计算。
Mondrian Calibration (蒙德里安校准)
基于类别划分的局部校准策略，为每个类别单独设定阈值。用于实现类别条件覆盖。
Pseudo Labels (伪标签)
由模型预测生成的标签，用于无标签校准，但在偏移严重时效果有限。
Log Euclidean Distance (对数欧几里得距离)
SPD矩阵空间中的距离度量，结合对数变换，便于几何操作。
Joint Shift (联合偏移)
同时影响协变量和标签分布的偏移类型，难以通过无标签方法校准。
Open Questions Unanswered questions from this research
- 1 如何在更复杂的偏移模型中保证类别条件覆盖的有效性仍是未解难题，特别是在高维或依赖性偏移场景中。
- 2 现有方法在极端偏移或多源偏移环境下的理论和实践表现仍有限，未来需探索更鲁棒的无标签校准策略。
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.