areces24a@v247@PMLR

Total: 1

#1 Two fundamental limits for uncertainty quantification in predictive inference [PDF5] [Copy] [Kimi3] [REL]

Authors: Felipe Areces, Chen Cheng, John Duchi, Kuditipudi Rohith

We study the statistical hardness of estimating two basic representations of uncertainty in predictive inference: prediction sets and calibration error. First, we show that conformal prediction sets cannot approach a desired weighted conformal coverage level—with respect to a family of binary witness functions with VC dimension d—at a minimax rate faster than O(d1/2n1/2). We also show that the algorithm in Gibbs et al. (2023) achieves this rate and that extending our class of conformal sets beyond thresholds of non-conformity scores to include arbitrary convex sets of non-conformity scores only improves the minimax rate by a constant factor. Then, under a similar VC dimension constraint on the witness function class, we show it is not possible to estimate the weighted weak calibration error at a minimax rate faster than O(d1/4n1/2). We show that the algorithm in Kumar et al. (2019) achieves this rate in the particular case of estimating the squared weak calibration error of a predictor that outputs d distinct values.

Subject: COLT.2024 - Accept