Abstract
Conformal prediction traditionally provides individual coverage guarantees, ensuring that a true label is contained within a prediction set with a user-defined probability. This paper extends this framework to "batch" scenarios, providing a joint $1-\alpha$ coverage guarantee for an entire group of unlabeled examples. By leveraging the Simes inequality and adaptive estimators, the proposed methods yield significantly narrower, more informative prediction sets than standard Bonferroni-corrected approaches and remain robust under label distribution shift.
Introduction
In many real-world machine learning applications, data arrives in structured groups or batches rather than isolated instances. Examples include sequences of frames in a video or the digits of a handwritten zip code. While standard conformal prediction can guarantee coverage for each individual element, many tasks require a joint guarantee that the entire batch is correctly captured.
The traditional approach to achieving joint coverage is the Bonferroni correction. However, Bonferroni is notoriously conservative, often resulting in prediction sets so large they lose practical utility. Furthermore, most conformal methods assume that the data distribution remains constant, failing when the proportions of classes in the test batch differ from the training data (label distribution shift).
Methodology
This paper introduces several novel methods to construct efficient batch prediction sets:
- Simes Batch Prediction: By aggregating conformal p-values using the Simes inequality, this method is mathematically proven to be "uniformly more powerful" than Bonferroni. It produces prediction sets that are always a subset of (or equal to) the Bonferroni sets.
- Adaptive Simes: This approach utilizes a Storey-type estimator to identify "easy" examples within a batch. By estimating the number of true null hypotheses, the algorithm can recycle its error budget to provide tighter bounds for more ambiguous instances.
- Estimated Likelihood Ratio Test (LRT): A computationally intensive method that works directly with non-conformity scores. While it offers the highest statistical power, it requires more processing time than p-value-based methods.
- Computational Shortcut: To overcome the exponential complexity of checking every possible label combination ($K^m$), the authors developed an algorithm that reduces complexity to $O(K \cdot m^2)$, making batch prediction feasible for practical use.
Key Results and Insights
The researchers evaluated these methods on synthetic data, the USPS handwritten digit dataset, and CIFAR-10. A central finding is the benefit of "pooled evidence": when a model is highly confident about several examples in a batch, the Simes method can use that collective evidence to be more restrictive on the remaining ambiguous examples.
In experiments with the USPS dataset, the Simes method demonstrated superior efficiency. For a batch of five digits, Simes often excluded label combinations that Bonferroni was forced to include, resulting in smaller, more precise sets of plausible sequences. Furthermore, by using "class-calibrated" p-values (Mondrian conformal prediction), the authors ensured that the $1-\alpha$ guarantee holds even under significant label distribution shift, where standard methods typically fail.
Conclusion
Batch conformal prediction using the Simes inequality provides a "free lunch" upgrade over traditional Bonferroni methods, offering tighter guarantees without requiring additional assumptions. While challenges remain in scaling these methods to extremely large batches or finding intuitive ways to summarize high-dimensional prediction sets for human users, this framework represents a significant step forward in robust uncertainty quantification for grouped data.
Summary updated