Efficient Calibration for Decision Making

A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot improve their outcome by post-processing a perfectly calibrated predictor. Hu and Wu (FOCS'24) use this to define an approximate calibration measure called calibration decision loss (CDL), which measures the maximal improvement achievable by any post-processing over any proper loss. Unfortunately, CDL turns out to be intractable to even weakly approximate in the offline setting, given black-box access to the predictions and labels.

We suggest circumventing this by restricting attention to structured families of post-processing functions K. We define the calibration decision loss relative to K, denoted CDL K where we consider all proper losses but restrict post-processings to a structured family K. We develop a comprehensive theory of when CDL K is information-theoretically and computationally tractable:

• Complexity characterization. The sample complexity of estimating CDL K is determined by the VC dimension of thr(K), the concept class consisting of thresholds applied to any κ ∈ K. Computationally, estimating CDL K reduces to agnostically learning thr(K). This implies that estimating CDL relative to 1-Lipschitz post-processings is informationtheoretically hard.

• Quantitative characterization. Augmenting thr(K) with indicators of intervals of the form [0, a] yields a family of weight functions K ′ such that CDL K is characterized, up to a quadratic factor, by the weighted calibration error restricted to K ′ . This significantly generalizes prior bounds that were for specific choices of K.

• Omniprediction. If thr(K) is efficiently learnable there exists a single post-processing that performs competitively with the best post-processing in K for every proper loss. Classical recalibration algorithms including the Pool Adjacent Violators (PAV) algorithm and Uniform-mass binning give similar omniprediction guarantees for natural classes of post-processings with monotonic structure.

In addition to introducing new definitions and algorithmic techniques to the theory of calibration for decision making, our results give rigorous guarantees for some widely used recalibration procedures in machine learning.