Prediction sets capture uncertainty by predicting sets of labels rather than individual labels, enabling downstream decisions to conservatively account for all plausible outcomes. Conformal inference algorithms construct prediction sets guaranteed to contain the true label with high probability. These guarantees fail to hold in the face of distribution shift, which is precisely when reliable uncertainty quantification can be most useful. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. It estimates importance weights, then propagates uncertainty in these estimates through a Gaussian elimination algorithm to compute confidence intervals that contain the importance weights, and finally uses these intervals to construct prediction sets. We evaluate our approach on four datasets: the CIFAR-10 and ChestX-Ray image datasets, the tabular CDC Heart Dataset, and the AGNews text dataset. Our algorithm satisfies the PAC guarantee while producing smaller prediction set sizes compared to several baselines.
PAC Prediction Sets Under Label Shift
Wenwen Si Sangdon Park Insup Lee Edgar Dobriban Osbert Bastani