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

arXiv: https://arxiv.org/abs/2607.18088 · HTML: https://mlsanity.com/paper/2607.18088/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 43 references that are in the map.
- First posted on arXiv 20 Jul 2026.

## Builds on (most cited first, 28 of 28)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Moment Matching for Multi-Source Domain Adaptation](https://mlsanity.com/paper/1812.01754/) (2018)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Deep Hashing Network for Unsupervised Domain Adaptation](https://mlsanity.com/paper/1706.07522/) (2017)
- [NTU RGB+D: A Large Scale Dataset for 3D Human Activity Analysis](https://mlsanity.com/paper/1604.02808/) (2016)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Channel-wise Topology Refinement Graph Convolution for Skeleton-Based Action Recognition](https://mlsanity.com/paper/2107.12213/) (2021)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Cross-view Action Modeling, Learning and Recognition](https://mlsanity.com/paper/1405.2941/) (2014)
- [Class-Conditional Conformal Prediction with Many Classes](https://mlsanity.com/paper/2306.09335/) (2023)
- [Distribution-free uncertainty quantification for classification under label shift](https://mlsanity.com/paper/2103.03323/) (2021)
- [Robust Validation: Confident Predictions Even When Distributions Shift](https://mlsanity.com/paper/2008.04267/) (2020)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [PAC Prediction Sets Under Covariate Shift](https://mlsanity.com/paper/2106.09848/) (2021)
- [Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them)](https://mlsanity.com/paper/2405.06627/) (2024)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [PAC Prediction Sets Under Label Shift](https://mlsanity.com/paper/2310.12964/) (2023)
- [Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration](https://mlsanity.com/paper/2406.06818/) (2024)
- [Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage](https://mlsanity.com/paper/2502.17264/) (2025)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [Adapting Prediction Sets to Distribution Shifts Without Labels](https://mlsanity.com/paper/2406.01416/) (2024)
- [Test-time Recalibration of Conformal Predictors Under Distribution Shift Based on Unlabeled Examples](https://mlsanity.com/paper/2210.04166/) (2022)
- [Conformal Prediction Under Generalized Covariate Shift with Posterior Drift](https://mlsanity.com/paper/2502.17744/) (2025)
- [Coverage Guarantees for Pseudo-Calibrated Conformal Prediction under Distribution Shift](https://mlsanity.com/paper/2602.14913/) (2026)

## Abstract (arXiv)

Prediction sets can make deployed classifiers safer by returning several plausible labels when a single prediction is uncertain. Their value depends on classwise reliability: average coverage can meet its target while rare or difficult classes fail repeatedly. This concern is sharper after distribution shift, when calibration labels come from a source environment but reliability is needed on the target. We ask what labeled source data and unlabeled target inputs reveal about class-conditional prediction sets, and when target labels are necessary. Under unrestricted joint shift, two target laws can produce the same observable data while requiring different classwise thresholds; any label-free rule covering both must enlarge its sets on one law. We give a labeled target audit that estimates the missing quantiles with a simultaneous guarantee. Probability-scale error is invariant to increasing score transformations, and threshold recovery follows under local regularity. At fixed confidence, achieving threshold tolerance varepsilon with fixed, nonadaptive class-stratified labeled pairs has total complexity Theta(Kvarepsilon-2log K), or Theta(varepsilon-2log K) labels per class under equal allocation. Class imbalance creates a separate acquisition cost; for foreground class probabilities of order 1/K, the mixed-stream label complexity is also Theta(Kvarepsilon-2log K) at fixed confidence. Experiments on action-recognition and image shifts show that marginal coverage can conceal severe class failures and that source classwise calibration depends on the shift. The results connect the information available at deployment to the target labels needed for useful class-conditional prediction.