Abstract: Conformal Prediction is a widely studied technique to construct prediction sets of future observations. Most conformal prediction methods focus on achieving the necessary coverage guarantees, but do not provide formal guarantees on the size (volume) of the prediction sets. We first prove the impossibility of volume optimality where any distribution-free method can only find a trivial solution. We then introduce a new notion of volume optimality by restricting the prediction sets to belong to a set family (of finite VC-dimension), specifically a union of $k$-intervals. Our main contribution is an efficient distribution-free algorithm based on dynamic programming (DP) to find a union of $k$-intervals that is guaranteed for any distribution to have near-optimal volume among all unions of $k$-intervals satisfying the desired coverage property. By adopting the framework of distributional conformal prediction (Chernozhukov et al., 2021), the new DP based conformity score can also be applied to achieve approximate conditional coverage and conditional restricted volume optimality, as long as a reasonable estimator of the conditional CDF is available. While the theoretical results already establish volume-optimality guarantees, they are complemented by experiments that demonstrate that our method can significantly outperform existing methods in many settings.

Lay Summary:

Imagine trying to predict tomorrow’s weather, but instead of just saying “it will be 75°F,” you want to give a range of temperatures that is guaranteed to include the true value, say between 70°F and 80°F. This is the idea behind conformal prediction, a powerful technique that wraps predictions in a safety net of uncertainty. It ensures these ranges (or prediction sets) are statistically reliable, meaning they include the correct answer most of the time.Many existing methods provide safe prediction sets, but not necessarily efficient ones. For example, one could always predict the whole possible range of values (like “anywhere from 0°F to 100°F”), which is technically always right, but not very useful.Our work tackles this inefficiency. We first prove a fundamental limitation: any method that provides reliable prediction sets for all situations can only find a trivial solution. To get around this, we focus on structured prediction sets, specifically, using only a small number of intervals. This makes the prediction sets more concise and interpretable.We then design a new algorithm that guarantees these structured sets are as small as possible while still being statistically valid. It works even when we know very little about the data, and performs especially well when the data has multiple clusters or modes. Our experiments show that this method produces much tighter (and still reliable) prediction ranges than existing approaches.