cs.LGMay 21, 2026

Smoothed Elicitation Complexity for Approximate Γ-calibration of Discrete Classification Tasks

Authors: Jessica Finocchiaro, Victor Ganson, Drona Khurana

Organizations: Computer Science, Boston College · Computer Science, University of Colorado Boulder

Abstract

One prominent method of evaluating machine learning model trustworthiness is the notion of calibration. In the binary outcome setting, a probabilistic predictor is calibrated if outcomes are realized according to a model's distributional prediction, conditioned on this prediction. Straightforward extensions of binary calibration definitions to probabilistic multiclass classifiers suffer from an exponential complexity blowup as the space of predictions grows exponentially in the number of classes nn. As a remedy, Noarov and Roth (2023) propose multiclass calibration with predictions that are properties of the outcome distribution, reducing complexity from growing in the number of classes nn to the dimension dd of the property, called its elicitation complexity. Previous work on approximate property calibration is generally limited to continuous scalar properties, despite many relevant properties of interest being discrete, like the mode or rankings. We characterize the approximate property calibration of discrete properties which are strongly orderable by using Lipschitz continuous properties as an intermediary. This work is the first to our knowledge to provide approximate calibration results for discrete properties. Along the way, we characterize the Lipschitz elicitation complexity of strongly orderable discrete properties by constructing algorithms for designing these Lipschitz properties, which we prove can be post-processed to obtain the original discrete property.

Explore similar work

CardsList
Apr 23, 2026cs.LG

The Sample Complexity of Multicalibration

We study the minimax sample complexity of multicalibration in the batch setting. A learner observes nn i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most ε\varepsilon with respect to a given family of groups. For every fixed κ>0κ> 0, in the regime ∣G∣≤ε−κ|G|\le \varepsilon^{-κ}, we prove that Θ~(ε−3)\widetildeΘ(\varepsilon^{-3}) samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as Θ~(ε−2)\widetildeΘ(\varepsilon^{-2}), and shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. In contrast we observe that for κ=0κ= 0, the sample complexity of multicalibration remains Θ~(ε−2)\widetildeΘ(\varepsilon^{-2}) exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted LpL_p multicalibration metric for all 1≤p≤21 \le p \le 2, with optimal exponent 3/p3/p. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of Hu et al. (2025) to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.
Natalie Collina, Jiuyao Lu, Georgy Noarov +1
Multicalibration and CalibrationOptimal Sample ComplexitySample Complexity
AskPDF
Jun 9, 2026cs.LG

Can we trust our models? Epistemic calibration in second-order classification

Uncertainty estimation is critical for deploying machine learning models in high-stakes settings. However, classical calibration only assesses the reliability of predicted probabilities and does not evaluate whether epistemic uncertainty estimates are themselves trustworthy. This limitation is particularly relevant for second-order classification models. We introduce epistemic calibration, a principled criterion that measures whether reported epistemic uncertainty faithfully reflects the dispersion of model predictions around the ground truth. We show that epistemic calibration is a strictly stronger notion than classical calibration and captures failure modes invisible to standard metrics. We relate this work to the existing literature through an impossibility theorem that holds under the epistemic calibration hypothesis. To operationalize this concept, we propose the Expected Epistemic Calibration Error (EECE), which we prove to be a consistent estimator of a True Epistemic Calibration Error (TECE). Experiments across a broad range of uncertainty quantification methods show that epistemic calibration is a coherent and meaningful criterion and reveal substantial differences across methods, despite similar predictive performance.
Arthur Hoarau
Epistemic Uncertainty
AskPDF
Aug 4, 2026cs.LG

Sample Complexity of Multicalibration for Multilevel Properties

Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined relative to the mean, skewness relative to both mean and variance, and conditional value at risk relative to a quantile. We study multicalibration for a sequence of kk properties in which each property is identifiable once the preceding properties are fixed. This framework includes Bayes pairs but does not require the properties to arise from a single loss. For every fixed k≥2k\ge2, we establish matching upper and lower sample-complexity bounds up to logarithmic factors under regularity conditions. Even with only polylogarithmically many binary groups, achieving multicalibration error ε\varepsilon requires Ω~(ε−(k+2))\widetildeΩ(\varepsilon^{-(k+2)}) samples. Conversely, for any finite group family G\mathcal G, we give a randomized learner using O(ε−(k+2)+ε−2log⁡∣G∣)O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|) samples. Thus the sample complexity is Θ~(ε−(k+2))\widetildeΘ(\varepsilon^{-(k+2)}) for polynomial-size group families. We instantiate the theory for three canonical examples.
Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev +1
Multicalibration and CalibrationOptimal Sample ComplexitySample ComplexityBayesian
AskPDF