Conformal Elicitation: Loss Minimization Controls Set Size Regret

Conformal prediction turns a probabilistic classifier into a prediction set with a prescribed coverage level, but coverage alone does not determine how useful that set is. We view expected set size at fixed marginal coverage as a downstream decision objective and ask how well ordinary probability estimation, via loss minimization, serves this objective. For conformal prediction sets induced by probability conformity scores, we prove that excess expected size over the Bayes-optimal set is at most $K^{3/2}{\alpha }^{-1}\sqrt{{\mathsf{Reg}}_{\mathsf{Brier}}(q)}$, where $K$ is the number of classes, $\alpha$ is the target miscoverage, and Reg_Brier is excess Brier loss. The guarantee requires no margin or density assumption and has sharp dependence on $K$ and $\alpha$ up to a universal constant. We also prove a more general result that bounds the gap to the minimum set size within a model class $\mathcal{F}$ using the loss improvement achievable via a family of post-processings corresponding to $\mathcal{F}$. These results suggest that standard loss minimization using a proper loss (e.g. Brier loss or log loss) can simultaneously achieve the goal of minimizing conformal set size. We run experiments to compare this method with ConfTr (Stutz et al., 2022), a previous method specifically designed for set size minimization. These experiments show, somewhat surprisingly, that loss minimization consistently achieves smaller set sizes compared to ConfTr at miscoverage level $\alpha =0.05$. These results demonstrate the power of standard proper loss minimization in providing high-quality uncertainty quantification.