Provable Uncertainty Decomposition via Higher-Order Calibration
Authors: Gustaf Ahdritz
Aravind Gollakota
Parikshit Gopalan
Charlotte Peale
Udi Wieder
Venue: ICLR 2025 Spotlight (2025)
Keywords: uncertainty quantification
calibration
trustworthy ML
mixture learning
Primary area: learning theory
TL;DR: We provide provable guarantees for uncertainty decomposition using the new notion of higher-order calibration.

Abstract: We give a principled method for decomposing the predictive uncertainty of a model into aleatoric and epistemic components with explicit semantics relating them to the real-world data distribution. While many works in the literature have proposed such decompositions, they lack the type of formal guarantees we provide. Our method is based on the new notion of higher-order calibration, which generalizes ordinary calibration to the setting of higher-order predictors that predict _mixtures_ over label distributions at every point. We show how to measure as well as achieve higher-order calibration using access to $k$-snapshots, namely examples where each point has $k$ independent conditional labels. Under higher-order calibration, the estimated aleatoric uncertainty at a point is guaranteed to match the real-world aleatoric uncertainty averaged over all points where the prediction is made. To our knowledge, this is the first formal guarantee of this type that places no assumptions whatsoever on the real-world data distribution. Importantly, higher-order calibration is also applicable to existing higher-order predictors such as Bayesian and ensemble models and provides a natural evaluation metric for such models. We demonstrate through experiments that our method produces meaningful uncertainty decompositions in tasks such as image classification.

Published as a conference paper at ICLR 2025
PROVABLE UNCERTAINTY HIGHER-OREE CALIBRATION
DECOMPOSITION
VIA
Gustaf Ahdritz Harvard University"
Aravind Gollakota Apple
Parikshit Gopalan Apple
Charlotte Peale
Udi Wieder
Stanford University"
Apple
ABSTRACT
We give a principled method for decomposing the predictive uncertainty of a model into aleatoric and epistemic components with explicit semantics relating them to the real-world data distribution. While many works in the literature have proposed such decompositions, they lack the type of formal guarantees we pro- vide. Our method is based on the new notion of higher-order calibration, which generalizes ordinary calibration to the setting of higher-order predictors that pre- dict mixtures over label distributions at every point. We show how to measure as well as achieve higher-order calibration using access to k-snapshots, namely examples where each point has & independent conditional labels. Under higher- order calibration, the estimated aleatoric uncertainty at a point is guaranteed to match the real-world aleatoric uncertainty averaged over all points where the pre- diction is made. To our knowledge, this is the first formal guarantee of this type that places no assumptions whatsoever on the real-world data distribution. Im- portantly, higher-order calibration is also applicable to existing higher-order pre- dictors such as Bayesian and ensemble models and provides a natural evaluation metric for such models. We demonstrate through experiments that our method produces meaningful uncertainty decompositions for image classification.
INTRODUCTION
Decomposing predictive uncertainty into aleatoric and epistemic components is of fundamental im- portance in machine learning and statistical prediction (Hüllermeier & Waegeman, 2021; Abdar et al., 2021). Aleatoric (or data) uncertainty is the inherent uncertainty in the prediction task at hand, arising from randomness present in nature's data generating process, while epistemic (or model) un- certainty arises from model's 's lack of perfect knowledge about nature. Accurate estimates of these quantities are of great use to practitioners, as they allow them to understand whether the difficulty of their prediction task arises primarily from the data or their model.
As running example, consider the task of predicting based on an X-ray scan whether bone will require a cast. Suppose our model issues 50% prediction for a scan. This could occur because the scan is genuinely ambiguous. A very different scenario is one where the model is unable to decide between two diagnoses: one where a cast is unambiguously necessary and one where it is not. In both scenarios, the total predictive uncertainty the same. However, the nature of this uncertainty differs; in the first scenario, it is purely alcatoric, while in the second, it is entirely epistemic.
For any such explanation of a model's uncertainty to be trusted, it must be accompanied by some meaningful semantics telling us what it means about the real world. The canonical example of such a notion in the prediction literature is calibration, which requires that whenever our model predicts certain distribution of outcomes, In our X-ray example, a 50% prediction would calibrated if exactly half of all scans with the same prediction did ultimately require casts. But this would be regardless of which of the two
actually observe that distribution of outcomes on average.
Work done while interning Apple. Authors in alphahetical order.

---

Published as a conference paper at ICLR 2025
Snapshots from Multiple Doctor Opinions
Higher-Order Predictions
True Bayes Mixture
X
X
High aleatoric, epistemic
X
x
fx)
X
J
P
x
0.5
S--alf 0.5
X X x
1
X X
x
fx) =
M
aleatoric, high epistemic
Figure 1: An illustration of higher-order calibration using the X-ray classification example. We depict scenarios 1 and 2 on the top and bottom respectively. On the left, we have instances grouped together into one level set [x]] by the predictor. By learning from snapshots drawn from the level set in either case, we able to predict mixtures that match the true Bayes mixture f* ([x])..
scenarios above we were in. Standard calibration is purely a guarantee regarding total predictive uncertainty, and does not account for the source of uncertainty. Accordingly, ask:
Can we build a theory of calibration that lets us decompose uncertainty into epis- temic and aleatoric components and give explicit semantics for these components?
In this work we answer this question by proposing theory of higher-onder calibration, general- ization of ordinary (first-order) calibration. This theory pertains to higher-order predictors, which predict mixtures of distributions over outcomes rather than just single distributions. Thus the first scenario of the X-ray example, we might predict a mixture concentrated on the 50% distribution, while in the second might predict an equal mixture of 100% and 0% (see Figure 1). As we shall discuss, higher-order predictors arise in many settings, including in Bayesian and ensemble methods. In nutshell, a higher-order predictor is higher-order calibrated if whenever it predicts certain mixture of distributions, then we do observe that mixture of distributions over outcomes in aggregate. The main contributions of our work are as follows:
1. We propose the notion of higher-order calibration, motivated by the question of rigorously de- composing predictive uncertainty into alcatoric and epistemic components. We consider standard uncertainty decompositions from the Bayesian literature (Houlsby et al., 2011; Hofman et al., 2024; Kotelevskii & Panov, 2024) and prove that under higher-order calibration, a predictor's es- timate of its aleatoric uncertainty matches the real-world aleatoric uncertainty averaged over all points with the same prediction. Similarly, the epistemic uncertainty matches the true "variance" in real-world label distributions over such points.
2. We propose a tractable relaxation termed -order calibration, which approaches higher-order Our theory builds on and generalizes recent work by Johnson et al. (2024), which studied the k = 2 case. We show that for certain entropy functions, even small values of k: (like 2) yield provable uncertainty decomposition.
calibration for large
3. We give practical methods for achieving higher-order calibration using access to k-snapshots, namely examples with & independent conditional labels per instance, by leveraging connections to the problem of mixture learning (Li et al., 2015).
We verify that our methods yield useful decompositions real image classification tasks.
Main result: provable uncertainty decomposition. Suppose nature generates random labeled data (x. 3) E &' x D. where X is the instance space and y the label space, which in this paper we assume is discrete. Let AY be the space of probability distributions over V. Let f X + A)' map each instance x to the conditional distribution of y (x: = x). We make no assumptions about the marginal distribution the form of f*. Thus each has true aleatoric uncertainty AU" (x)) (f)(),), where H is measure of variability or entropy. Epistemic uncertainty, by contrast, will emerge as a property of our predictor. We denote random variables using boldface throughout. See Appendix A for an extended discussion of notation.
2

---

Published as a conference paper at ICLR 2025
Definition 1.1 (Higher-orte predictors and calibration). A higher-order predictor f : AAY is a function that maps each instance to a distribution over AY (the space of such mixtures denoted AAY). Let [x] {a' X: f(x') = f(z)) denote the level set of f that x lies in. Let the Bayes mixture / ([x)) E AAy be the distribution of f (x) | (ar ~ [x:]). where x ~ [x]] denotes a draw from the marginal distribution Dx restricted to [zr]. We say f is higher-order calibrated if for every
I, f(z)= = ([z)).
Higher-order calibration guarantees that our prediction fa) a proxy for the true "Bayes mixture" of ground truth distributions (a= as we range over æ: ~ [x)]. This implies that any quantity defined in terms of the predicted mixture has a "real-world" interpretation as the corresponding quantity defined in terms of the Bayes mixture. This turns out to be powerful guarantee.
We now consider the well-studied "mutual information decomposition" of predictive uncertainty (see e.g. Houlsby et al. (2011); Gal (2016)), and see what semantics it has under higher-order calibration. We state in terms of the Shannon entropy H Ay + E, given by (p) = f(z) E AAY' be the predicted mixture
Evey Py log Py. Let duced marginal distribution of when we draw p at random and then draw y P is given by p = E(p]. the centroid of т. The mutual information decomposition is as follows':
instance z. The in-
(p)
E
(p)))
H(P) E HP()
(1.1)
Predictive uncertainty PU(f2)
Alcatoric uncestainty estimate AU()=)
Epistemic uncertainty EU(fx)
Theorem 1.2 (Uncertainty decomposition under higher-order calibration). Suppose f is higher- order calibrated. Let x² = ((x)) be the Bayes mixture over the level set [r), and let p = Exp xx (p"). Then
. The aleutoric uncertuinty estimate is accurate average:
[H())] = E AU( : x) E p-n
[H("))]
E (x))
pr-ax"
* The epistemic uncertainty is exactly the average divergence of n² to the mean P.:
E EU( =x)= p-r
E [PKI (1 pr (PII )1)")
1.1 LEARNING FROM SNAPSHOTS AND ORRDER CALIBRATION
Theorem 1.2 highlights the power of higher-order calibration. But how do we achieve it or even check if predictor satisfies it? The key difficulty that for any x, we never see (x) explicitly, but only get samples drawn from it.
turns out that checking high-order calibration requires going beyond the standard learning model. To see why, returning to our X-ray example, let be the given scan, and let [x]] be all scans that also get similar 50% prediction. Assume that [xx] is large so that we never see the same image twice. In scenario 1, the set [x] consists entirely of genuinely ambiguous scans. In scenario 2, [x]] consists of an equal balance of unambiguously positive and negative cases. Then all we receive are ordinary labeled examples with single label per image, see 50-50 distribution of labels in both scenarios and and have no hope of telling them apart.
Suppose instead that for each image x, we receive 2 labels, each of them drawn independently from (xx (e.g. from consulting two independent doctors). A little thought reveals that we can now tell the two scenarios apart quite easily. Scenario I results in pairs of labels distributed uniformly over the set {00, 01, 10, 11]. whereas scenario 2 only produces either 00 or 11, but never 01 or 10.
We formalize the above intuition by augmenting the classic learning setting: we assume that we have access to k-snapshots. namely independent conditional samples ......, 3/ ~ f*( for each sample æ. There are many learning settings where one can expect to have access to k-snapshots. In crowd-sourcing settings each æ can be shown to multiple experts, each of whom answers with their own label yi We can model these y&s as independent draws from the true conditional distribution
'To avoid confusion, note that we always view as taking in an object of type A), When p is itself a random variable, i.c. a random distribution, (p)) is also random variable. "This he formalized using the outcome indistinguishability framework (Dwork al., 2021).
3

---

Published as a conference paper at ICLR 2025
(x). Here l is decided by the number of experts we can call upon. A different setting is one where we want to distill a large teacher model into a smaller student model. In this case we have oracle access to the teacher and can ask for k-snapshots for large k. Of course not every setting admits such access, for instance health outcomes which by definition occur only once per patient.
A k-snapshot of labels from Y' can be seen as a coarse representation of distribution in AY by considering its normalized histogram. A distribution over k-snapshots is thus a coarse representation of a mixture in AAY. By framing our goal as that of learning a k-snapshot predictor from k- snapshot examples, we obtain an effective way of learning an (approximate) higher-order predictor.
This naturally defines hierarchy of calibration notions, which we term - calibration, that ranges from ordinary first-order calibration when & = 1 to (full) higher-order calibration as k + oc. Our work builds on and generalizes the elegant recent work of Johnson et al. (2024), who consider the case of k 2; we discuss this further in related work. Moreover, htth -order calibration essentially reduces to ordinary first-order calibration over the extended label space of k-snapshots; the only subtlety is in the choice of metric over this space. This leads to a simple and general recipe: we can leverage any seneral-purposs procedure guaranteeing first-order calibration over this extended label space to achieve - calibration. We prove formally that h-h calibration converges to higher-order calibration at a L/vk rate (see Theorem 2.4).
We also provide a different way of achieving -orrrr calibration using a purely post-hoc routine, analogous to first-order calibration procedures such as Platt scaling. Suppose we start from an ordinary first-order calibrated model. We can consider its level set partition [-] (or more generally any desired partition [-] of the space, with [a:] denoting the equivalence class of z)) Now, higher-order calibration with respect to [-] entails exactly the following: for any given equivalence class [xr]. we need to learn the true Bayes mixture /'([z]). Thus we have reduced our problem to collection of pure mixture learning problems. This problem has been studied before in the theoretical computer science literature (Li al., 2015). We leverage these ideas to provide simple post-hoc hthh -odder calibration procedure whose sample complexity scales as | (see Theorem 2.6).
Importantly, for common choices of entropy functions (like Brier entropy), we show in Theorem 3.3 that --ddrr calibration for small & (k = 2 for Brier) suffices to approximate the uncertainty decomposition guarantees from Theorem 1.2. This relies on a key property of 1thh -dd-rr calibration that we prove: it gives good estimates of the first k moments of the Bayes mixture over the level sets (Theorem 2.5). 1.th -order calibration is thus a natural goal itself for uncertainty decomposition.
1.2 RELATED WORK
Bayesian methods and mixture- based uncertainty decompositions. The predominant modern approach to uncertainty decomposition has been the Bayesian one (see e.g. Gal (2016); Mena et al. (2021)), wherein one uses Bayesian inference to obtain for any given instance a full posterior distri- bution over a family of models, or equivalently over corresponding distributions of outcomes. In this way every Bayesian model is a higher-order predictor. A similar logic holds for ensemble models (Gal& & Ghahramani, 2016; Lakshminarayanan et al., 2017).
A number of works in the Bayesian literature have studied uncertainty decompositions based on predicted mixtures (sometimes termed second-order or higher-order distributions) (Houlshy et al., 2011; Depeweg et al., 2018; Hüllermeier & Waegeman, 2021; Malinín & Gales, 2021; Wimmer et al.. 2023; Schweighofer et al., 2023; Sale et al., 2023c;a; Kotelevskii & Panov, 2024: Hofman et al., 2024). Bayesian neural networks (Lampinen & Vehtari, 2001) and variants (Malinin& & Gales, 2018; Sensoy et al., 2018; Osband et al., 2023) can also be seen as explicit constructions of cer- tain types of parameterized higher-order predictors. We build on these works, and in particular on Hofman et al. (2024); Kotelevskii & Panov (2024), for analysis of uncertainty decompositions.
While the idea of predicting mixtures is already present in these works, they do not consider any formal semantics such calibration. The real-world semanties of Bayesian methods typically arise from the following type of asymptotic consistency guarantee (see e.g. Doob's theorem (Miller, 2018)): if the model class is well-specified (i.e. the unknown f* is realizable by the class), and Bayesian inference is computationally feasible (at least in some approximate sense), then in the
While this is limitation of our method, it is inherent to the task as just noted, if predictor is unable to separate instances in set [z], cannot distinguish between scenarios like those in the X-ray example.
4

---

Published as a conference paper at ICLR 2025
limit as the sample size grows large, the posterior becomes tightly concentrated around the true f". In practice, however, it is often very difficult (or impossible) to test that the model class is indeed well-specified, well as to perform true Bayesian inference over expressive classes. In such cases, it is not clear what semantics (if any) hold for the resulting uncertainty decomposition. This is the key gap we address with higher-order calibration. We note that higher-order calibration treated as an evaluation metric for any higher-order predictor, even if it is misspecified or poorly fit.
Pair prediction and second-order calibration. The introduced and studied by Johnson et al. (2024). Our work builds on theirs and greatly extends their notion of second-order calibration by defining the limiting notion of higher-order calibration that is implicit in their work. This allows us to view k"-order calibration as defining natural hierarchy between first-order and higher-order calibration. We believe this considerably clarifies the conceptual principles at play and also provides bridge to the Bayesian literature. We draw on recent work on calibration (Blasiok et al., 2023; Gopalan et al., 2024b;a) to provide full-fledged theory of higher-order calibration error and more. The idea of joint prediction has separately been studied by Wen et al. (2021); Osband et al. (2023); Durasov et al. (2024); Lee et al. (2024).
case of kth-order calibration was
Please see Appendix B for a full discussion of additional related work.
2 HIGHER-ORDER CALIBRATION
In this section we define higher-order and -oddr calibration full generality, and describe meth- ods for achieving them. Recall that a partition of the space X' is a collection of disjoint subsets, or cquivalence classes, whose union is the entire space. For any æ E X. we use [a] S X to refer to its equivalence class, and we use [-] as shorthand for the entire partition. The Bayes mixture over an equivalence class [z:]. denoted f ([x)), is the mixture obtained by drawing x ~ [x] (according to the marginal distribution Dx restricted to [a:) and considering f (z)) We define approximate higher- order calibration to allow for some error between the predicted distribution and the Bayes mixture, where we measure closeness between mixtures in AAV using the Wasserstein distance with respect to the & (or statistical) distance between distributions in Ay. Recall that for us ) is discrete.
Definition 2.1 (Approximate higher-order calibration). We say a higher-order predictor ʃ : AAY is e-higher-order calibrated to f wrt a partition [-] if for all x E X
f((f()), =
(ET(f(e). ((+)) (pp'' >~lllp - p" p'lli Sc.
inf
where we use [(,,, 7²) ) denote the set of all couplings of and n'.
Even with this relaxation, it is unclear how to measure higher-order calibration error, since we never get access to fr itself. As a tractable path towards this goal, we will introduce the model of learning from k-snapshots and -odder calibration.
Definition 2.2 (k-snapshots and 4thh -oder projections). A k-snapshot for x E X' is a tuple = (yi..... Bk) yk where each label y, drawn independently from fx).. For a mixture π e AAY, its -order projection is the k-snapshot distribution proje(T) E A)(k) defined as follows:
* We draw p and k-snapshot s = (y1...., by sampling k times i.i.d. from p. We output Unif (nif(y)..... (31.....
Here yok) denotes the space of such uniform distributions over snapshots (aka normalized his- tograms). Thus (A) C A) is coarsened version (with granularity 1/k) of the space AV.
In the model of learning with k-snapshots, we receive pairs (æ, 8) where x ~ Dx and E yk k-snapshot for æ, and the goal is learn a "k-snapshot predictor" that predicts a distribution over possible k-snapshots drawn from given x E X'. While this distribution could be represented directly over y* we can simplify our approach by leveraging key property of k-snapshots: the yos are each drawn iid. Consequently, the order of the tuple does not matter. Thus, instead of viewing
k-snapshot as a tuple (11, yk) E y*k, we will view it as the distribution Unif(y Us) E y1(6 C
'Throughout this paper, for simplicity we require closeness for all equivalence classes [n). A more relaxed notion would only require it to hold with high probability over equivalence classes.
5

---

Published as a conference paper at ICLR 2025
AY. The goal of k-snapshot prediction is to learn a predictor g : X + A)(()) such that for each x E X. g(x) is close to proje (z)). the true distribution of k-snapshots for x.
Viewing the space yr(k) as a subset of Ay, and hence the space Ajr(k) as subset of AAy, is an important conceptual simplification. Firstly, because g(z) E A)(R) S AAV, k-snapshot predic- tor can be directly viewed as higher-order predictor with extra effort. Secondly, it suggests non-obvious error metric for k-snapshot prediction which turns out to be the right one: we simply distance measure between two distributions over snap-
use the Wasserstein distance on AAY shots. (This is a better measure than obvious choices like viewing )(AA as a discrete space and using statistical distance. See Appendix A for some more discussion of alternative representations.) We define calibration for k-snapshot prediction analogously to the higher-order setting:
Definition 2.3 (Approximate jth-order calibration). We say a k-snapshot predictor g ::X - A)(())
is orddr calibrated wrt f" and a partition [-] if for all x E X, (1()(F), projj ([x]) S c.
2.1 KEY PROPERTIES OF TTTDER CALIBRATION
We highlight three advantages of ttth -order calibration as a relaxation of higher-order calibration.
Tractability. Verifying higher-order calibration for predictor requires knowledge of f", which is generally unknown. In contrast, 1.th -order calibration defined relative to the tthh -oder projection of f on each partition. This projection corresponds exactly the distribution we observe when collecting k-snapshots as data. Thus, -ooooder calibration can be easily verified by comparing the empirical distribution of k-snaashot data against the predictor's output distribution. This makes Athh. order calibration a practical metric for assessing predictor performance. Beyond verification, tth order calibration also comes with simple methods for achieving it, which we detail in Section 2.2.
Convergence to higher-order calibration. As one might expect, k"-order calibration for large k closely related to higher-order calibration. particular, we can precisely characterize the rate at which 1tth -odder calibration approaches higher-order calibration as k + cc. The proof can be found Appendix D.3, and follows via a concentration argument:
Theorem 2.4 -oth- calibration implies higher-order calibration. 5) If : X + AY()) is ooder calibrated with respect to partition [:]. then it is also (e + (2//((2/))) higher-rrrdr calibrated with respect to the same partition [:]-
This shows the convergence of approximate h-d-order calibration to approximate higher-order cali- bration a way that preserves the approximation error.
Moment recovery via -order calibration. At small values of kt 1 -ordorde calibration can still guarantee valuable information about the mixture distribution over each partition, if not about the higher-order calibration of predictor. In particular, - calibrated predictor gives good estimates of the first & moments of f ([x]). This should be contrasted with higher-order calibration, which tells the full distribution of ([x)). In settings where we only care about the first k moments of f ([æ]), this tells us that 1th calibration can substitute for higher-order calibration. For simplicity, we restrict the binary case, where AAY can be identified with A 1].
Theorem 2.5 (Moment estimates from -th-order calibration). Let y = [0, and let g :x +
AY(()) be -oder calibrated with respect to partition [.]. Then each x E X, we can use g(z) generate vector of moment estimates (m1....,my E R such that for each E [k].
m4
E 2~
(x)" S ie/2.
This is proved in Appendix D.4 by showing that the first moments of a mixture can be exactly recovered from the mixture's 's order projection. This allows us to get calibrated vector of pre- dictions for the first & moments from a -'h-order calibrated predictor. It implies that we can make calibrated predictions for the expectation of any low-degree polynomial with bounded coefficients evaluated on (x). This property will be useful for estimating aleatoric uncertainty using 1tth -order calibration (Theorems 3.3, E.8) and giving prediction sets with coverage guarantees (Appendix F).
'We present this theorem in simplified manner to emphasize the connections between = and higher- order calibration error. See Appendix D.2 for additional guarantees that both lower- and upper- bound the higher-order calibration error within partition in terms of the "ordrr error.

---

If this is Published as a conference paper at ICLR 2025
2.2 ACHIEVING ORRDER CALIBRATION
We present two simple methods for hith -order calibration based on common approaches for first-order calibration: minimizing proper loss, or post-procsssing the level sets of a learned predictor.
Learning directly from snapshots. Our definition of -ordrr calibration is immediately accom- panied by natural method for achieving it: view the learning problem as multiclass classification problem over the extended label space )/(A) of k-snapshots, and use any fff-the-shelf procedure that tries to achieve ordinary first-order calibration over this space when we draw true k-snapshots from nature. Perfect first-order calibration over yx() means exactly that g(x) = proj ([x]) for all x, which is equivalent to -order calibration. A simple concrete method is to minimize a proper multi- class classification loss over the label space y)(k) (such as cross entropy) over an expressive function class. This is the method followed in Johnson et al. (2024) for achieving second-order calibration.
Post-hoc calibration using snapshots. Here we describe a simple alternative way of achieving -'hdorder calibration using a pure post-processing routine which allows us to turn any ordinary first- order predictor into a higher-order calibrated predictor, thereby "cliciting" its epistemic uncertainty. This method requires only a calibration set of k-snapshots rather than a full training set.
Let us briefly recall the standard post-processing procedure for achieving first-order calibration." For partition [-], first-order calibration requires that for every x, f(z) =
be the centroid of the Bayes mixture within its partition, E (a=)] That is, we have reduced the problem to that of learning the mean label distribution over a given set [æ]. We implement this by drawing a sufficiently large sample from each set [x]] in the partition and use the empirical distribution as estimate of the true mean.
not the case, then we "patch" the prediction
Our procedure for post-hoc -od-or calibration is a very natural extension of this algorithm. Let partition [ be given (perhaps arising from an initial first-order predictor). For each equivalence class [a]] in the partition, instead of simply trying to estimate the centroid of the Bayes mixture, we will now try to learn the entire Bayes mixture (or technically its k="oorder projection projæ. ((x))) That is, we reduce to mixture learning instead of mere distribution learning. Mixture learning has been previously explored in the literature; e.g. Li al. (2015) give algorithms for learning mixtures given access to snapshots. While their methods could be applied for post-processing for higher-order calibration, their focus on learning complete mixtures rather than their xdh-order projections (as is sufficient for order calibration) leads to different guarantees and snapshot size requirements.
We present a simple post-processing algorithm for achieving -order calibration using a calibration set of l- k-snapshots from each [xr]. Our algorithm is as follows: given N k-snapshots - viewed as distributions P1, ...: PN E ()()) C AY drawn from proje. ([x)), output the empirical mixture, iee Unif(P1.-.. PNN). We can use standard concentration arguments to show that for sufficiently large N, this will give good estimate of projæ. ([z]) and hence h'"-order calibrated predictor. Theorem 2.6 (Empirical estimate of -od-or projection guarantce). Consider any x E X, and a sample pI PN E y(k) where each p; is drawn i.i.d. from (roigf(((z]) Given e > and < < 1, if N 2 (2(1)(0))
+ log(1 (1/))))/e² then we can guarantee that with probability at least 8 over the randomness of the sample we will have
(prooj ([=)), Unif (ini(pp........) S.
The proof of this theorem can be found in Appendix D.5. We note that [D>00] is exactly the number of multisets of size it that can be chosen from l items, with repeats. Thus, [)>(A) ("--))) I t and so replacing [ with e also gives the desired guarantee. In the special case binary prediction, | simplifies to just h: + 1, resulting in a bound that is linear in the size of the snapshot.
3 UNCERTAINTY DECOMPOSITIONS
Having defined higher-order and -oh-rrder calibration, we show how these notions can be leveraged to provide meaningful semantics for decomposing predictive uncertainty. Let any concave general-
Herre mean distribution calibration with respect to distributions in A for any discrete space y, hut the reader consider the hinary case for simplicity. There, distribution learning reduces to mean estimation.
7

---

Published as a conference paper at ICLR 2025
ized entropy function G AY' R be given (e.g., the Shannon entropy; see Appendix C.1 for more details). Fix point x E X, and let the predicted mixture at x be f(x) E AAV. Consider a random distribution p- f(x)) drawn from this mixture, viewed
random vector on the simplex in IR' The induced marginal distribution of y when we draw ~ f(x) and then draw ~ P is given by p Elp), the centroid of (a:). Perhaps the most studied decomposition is the "mutual information decomposition" (Houlsby et al., 2011; Gal, 2016), which we restate here. Our formulation in terms of generalized entropy follows that of Hofman et al. (2024); Kotelevskii & Panov (2024).
B(G(P)
+
Gip) -
(3.1)
Predictive uncertainty
Alcatoric uncertainty estimate
Epistemic uncertainty
The predictive uncertainty is the total entropy in random outcome y drawn marginally from m. The aleatoric uncertainty estimate is the conditional entropy in given the mixture component p. The epistemic uncertainty is precisely the mutual information between y and p: it non-negative by Jensen's inequality. It can be equivalently written variance-like quantity, Ep-a (D(p || p)], where D is the divergence associated with G (e.g.. the KL divergence for the Shannon entropy). Accordingly we define the following estimates for uncertainty.
Definition 3.1. Let G : AV' + R be concave generalized entropy function. For higher-order order predictor f X' - AAV, we define the predictive, aleatoric, and epistemic uncertainties of with respect to G as
PUa(f x)) = G( E [pl) pro((x)
AUa(f: : x) p~f(m) [G(D]
EUa(f: : x) =PUa(f : - AUo(f :z).
These quantities are meaningful mainly for higher-order predictors. Nature itself only associates pure distribution f (z) with every x, and has only true alcatoric uncertainty: G(f
=
The mutual information decomposition (Eq. (3.1)) is purely a function of our prediction and inde- pendent of nature. Under what conditions does it tell us something meaningful about true aleatoric uncertainty? It turns out that higher- oogger--rderreeee calibration is a sufficient condition: it guarantees that our estimate aleatoric uncertainty at a point x equals the average true aleatoric uncertainty over [x). Lemma 3.2. If f AAY is perfectly higher-order calibrated, then for all æ E X,
AUolf :x) EE (A)) x~1x]
This is proved in Appendix E and establishes the first part of Theorem 1.2. At first, higher-order calibration may seem like a very strong condition that just happens to provide calibrated uncertainty estimates. In fact, Theorem E.2 will show that higher-order calibration is necessary condition for a predictor to produce calibrated estimates of aleatoric uncertainty with respect all concave entropy functions. In this way we see that higher-order calibration identifies a predictor's 's epistemic uncertainty in bucketing multiple potentially different points into a single equivalence class [ar] Our estimate of aleatoric uncertainty captures the average true aleatoric uncertainty in f'(xx) and our epistemic uncertainty can be thought as the true "variance"" "9 in f (x) as æ ~ [x].
~ [x].
Uncertainty decomposition from 4h oohdrr calibration. While Lemma 3.2 draws important connection between higher-order calibration and uncertainty estimation, it does not allow for cali- bration error. Even if it did, achieving sufficiently small higher-order calibration error might require - calibration for large by Theorem 2.4. What if we can only guarantee 1.th -order calibration for reasonably small k? Is this of any use towards the goal of rigorous uncertainty decomposition?
"I the context Bayesian models, f(x) is often called the posterior predictive distribution, and p is often called the Bayesian model average (BMA).
'In general there multiple approaches to uncertainty decomposition given predicted mixture. Here focus on the mutual information decomposition. In Appendix C. we discuss other natural mixture-based de- compositions and show how they can also he endowed with meaningful semantics via higher-order calibration. II particular, it is the divergence of f'(x) for ~ [xt from the centroid [e= (f")))(((())))))))))))))))())( (a=), as formalized in Theorem 1.2 and more generally in Lemma C.I.
8

---

Published as a conference paper at ICLR 2025
We show that for the two most commonly used entropy functions, the binary Brier and Shannon entropies, the answer is yes. In fact, the former only requires k = 2. We prove a general result which applies to any uniformly continuous entropy function. The key insight is that -oh-order cali- bration provides us with good estimates of the first k moments of the Bayes mixture (Theorem 2.5). show that the Shannon entropy has good
The Brier entropy is degree 2 polynomial, whereas approximations by low-degree polynomials. A similar guarantee applies to all uniformly continuous functions via Jackson's 's theorem. Taken together, these results show that - calibration is natural and tractable goal in itself for uncertainty decomposition. We state the following theorem informally; formal statements and proofs (with sample complexity) may be found in Appendix E.3.
Theorem 3.3 (Estimating entropy functions; informal). We can obtain estimates AUG safisfying
AUG
J [AU?(=)] Se
x~1z
using only 1.hh -order calibration for the following common entropy functions G:
For Brier entropy (pr = 4p(1 p) using (c/8) se/o)-seconddorder calibration;
For Shannon entropy SSunnon (p) = -p poog p - (1 - p) log(1 - p) using e'-khh-rdes cali- bration, where c' S </ cxx)(()))) and & 2 ((1
For any uniformly continuous G with modulus of continuity we (see Definition E.3) using -'-kehorder -order calibration where e' satisfies wo(e' + (2/1(2//)) S.
4 EXPERIMENTS
In this section, we describe experiments on training higher-order calibrated models using k- snapshots. We focus the task of classifying ambiguous images using CIFAR- -OH (Peterson et al., 2019), a relabeling of the test set of CIFAR-10 (Krizhevsky, 2009). For additional experi- ments, including comparisons with other uncertainty decomposition methods, Appendix G.
CIFAR- is an image recognition dataset of 10,000 32 x 32 color images with 10 possible classes (e.g. truck, deer) and with least 50 independent human annotations per image. Thus y is the space of 10 possible entities, and for each image x E X' we treat the normalized histogram of its 250 independent ground-truti annotations as a distribution f*(x) over V In other words, (*x E AY is the uniform distribution over the independent annotations of æ. All entropy computations are done with respect this distribution. There is disagreement among annotators: the mean true alcatoric uncertainty E|AU;, [x)] = [f (x))) is 0.17 (STD 1.2), where H is the Shannon entropy.
We first train regular 1-snapshot ResNet (Zagoruyko & Komodakis, 2016) on 45,000 images from the CIFAR training set, setting aside the remaining 5, 5,000 for validation. We then apply our post-hoc calibration algorithm (see Section 2.2) CIFAR-10H, using half calibration set and the other half as a test set. For more details, see Appendix G. In this way we obtain -oddrr predictor X + ()(k), The induced marginal first-order predictor z X A)' {(x) = Ep-g(a) [p).
In this nigh-dimensional setting, instead use coarse- -ranined partition defined in terms of For each possible class (e.g. truck), we bin together all images x where g(x) takes its maximum value at that class and where that value lies in one of 10 slices of [0, 1] (e.g. [0.8, 0.9).. Thus we obtain a partition with 100 bins in total.
infeasible to compute the true level set partition of g. We
In Appendix G we report higher-order calibration error as measured by Wasserstein error e in Defi- nition 2.3. As more easily interpretable measure, we also compute the aleatoric estimation error:
Eau(z) (z) AU x) - E [AU;
(4.1)
In Figure 2, report the mean aleatoric estimation error over all images, E.g (Auu(()) As pected, predictions of aleatoric uncertainty grow more accurate as the size of the snapshots used to calibrate the model is increased, and there is a significant benefit going beyond k 2.
To illustrate the advantages of accurate estimates of aleatoric uncertainty, we include in Figure examples of images skewed most towards pure "epistemic" or "aleatoric" uncertainty. The former

---

Published as a conference paper at ICLR 2025
Snapshot 5020
Groued
04 94
Entropy companents
Figure 2: Calibrating models with k-snapshots yields accurate uncertainty decompositions. Top: Average alcatoric uncertainty estimation error (Eq. (4.1)) of calibrated CIFAR-10 models. Bottom: For three the highest-entropy equivalence classes, we depict the distribution of entropies ranging over the predicted mixture (gray) and the Bayes mixture (green). We see that the distributions and in particular the means are similar.
Figure 3: Qualitatively, accurate estimates of aleatoric uncertainty help separate unusual, poorly learned images (mostly epistemic) from genuinely ambiguous ones (mostly aleatoric). Top: CIFAR-IOH images with the highest ratio of epistemic uncertainty to aleatoric uncertainty (depicted by colored bars), estimated by well--iigher-odddrr-alirrrrdd model. Bottom: The most aleatoric images according the same model.
category mainly consists of images that unusual in some way, e.g. images of objects unusual angles, or closely cropped images. Nevertheless, all are relatively easy for humans to identify, and thus point cases where the model could be improved. The "aleatoric" images, on the other hand, include mostly low-quality or otherwise ambiguous pictures disagree. Interestingly, this section also includes few images (e.g. the fifth image, of a cat being held by human) that do not seem ambiguous per se but did in fact divide annotators. This indicates that the mixture model has learned something about alcatoric uncertainty in the label distribution not obvious to the naked eye. Such insights help practitioners fine-tune their data collection efforts.
which the annotators do in fact
CONCLUSION
This work introduces higher-order calibration rigorous framework for decomposing predictive uncertainty with clear semantics, guaranteeing that our predictor's aleatoric uncertainty estimate matches the average aleatoric uncertainty over points where the prediction is made. We also propose 1eth -odde calibration tractable relaxation, showing that even small values of k can yield meaningful uncertainty decompositions. We demonstrate both training-time and post-hoc methods for achieving 1tth ooder calibration using k-snapshots. Our method offers significant advantages over existing methods in that distribution-free tractable, and comes with strong provable guarantees.
The main limitation of our work is that achieving thth -rder calibration for any k: > 1 fundamentally requires access multiple independent labels per data instance. While this requirement satisfied in many scenarios, such as crowd-sourcing model distillation, it is not always satisfiable. Addition- ally, our sample complexity scales with | which could become prohibitive for large label spaces or larger k. Open questions for future research include: (a) techniques for reducing dependence on label size and k. (b) applications to active learning and (c) diittf---ittrbuuiion detection, and (d) formally studying the tradeoff between collecting more conditional labels versus labeled data.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to thank Kunal Talwar and Moises Goldszmidt for helpful discussions. Charlotte Peale is grateful to be supported by the Apple Scholars in AI/L PhD fellowship.
REFERENCES
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, Rajendra Acharya, et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges.
Information fusion, 76:243-299 2021. 1,
Anastasios Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511 2021. B
Emad Barsoum, Cha Zhang, Cristian Canton Ferrer, and Zhengyou Zhang. Training deep networks for facial expression recognition with crowd-sourced label distribution. In ACM International Conference on Multimodal Interaction (ICMI), 2016. G.3
Viktor Bengs, Eyke Hüllermeier. and Willem Waegeman. Pitfalls of epistemic uncertainty quantifi- cation through loss minimisation, 2022. URL https: org/ wwws//200. 06102.
B
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of dis- tance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Com- puling, pp. 1727-1740, 2023. 1.2
Clément L Canonne. A short note on learning discrete distributions. arXiv:2002.11457 2020. D.5
arXiv preprint
Michele Caprio, David Stutz,, Shuo Li, and Arnaud Doucet. Conformalized credal regions for clas- sification with ambiguous ground truth. arXiv preprint arXiv:24/ (.ti:24//.04852. (48852, 2024. B
Leonardo Cella and Ryan Martin. Validity, consonant plausibility measures, and conformal predic-
tion. International Journal of Approximate Reasoning, 141:110-134 2022. ISSN 0888-613X. doi: https://doi.orgg 10. (016/.jjar.2221..777 007.01... Probability and Statistics: Foundations and His- tory. honor Glenn Shafer.
Siu Lun Chau, Antonin Schrab, Arthur Gretton, Dino Sejdinovic, and Krikamol Muandet. Credal two-sample tests of epistemic ignorance. arXiv preprint 2XXv:2440.122211 2024. B
A. DasGupta. Fundamentals of Probability: A First Course. Springer Texts in Statistics. Springer New York, 2010. ISBN 978 1441957795. E.2
Stefan Depeweg, Miigel Seemandez-Lobatee Finale Doshi- Doshi-Velez, and Steffen Udluft. Decom- position of uncertainty in bayesian deep learning for efficient and risk-sensitive learning, In International conference on machine learning, pp. 1184-1193. PMLR, 2018 1.2
Nikita Durasov, Nik Dorndorf, Hicu Lc, and Pascal Fua. Zigzag: Universal sampling-fre free uncer- tainty estimation through two-step inference. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. 1.2
Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Outcome in- distinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 1095-1 108, 2021. 2
Yarin Gal. Uncertainty in deep learning. PhD thesis, University of Cambridge, 2016. 1, 1.2,3
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pp. 1050-1059.
PMLR, 2016. 1.2
Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. Interna- tional statistical review, 70(3):419444 435, 2002. D.1, D.2

---

Published as a conference paper at ICLR 2025
Isaac Gibbs, John Cherian, and Emmanuel Candès. Conformal prediction with conditional guar-
antees. arXiv preprint arXiv:2305. 2023,
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation.
Journal of the American statistical Association, 102(477):359-375 2007. C.I, E.2
Parikshit Gopalan, Lunjia Hu, and Guy N Rothblum. On computationally efficient multi-class cali- bration. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024a. 1.2
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, and Mihir Sing- hal. Omnipredictors for regression and the approximate rank of convex functions. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024b. 1.2
Comelia Gruber, Patrick Oliver Schenk, Malte Schierholz, Frauke Kreuter, and Göran Kauer- mann. Sources of uncertainty machine learning-a statisticians' view. arXiv preprint arXiv:2305.16703, 2023. B
Dan Hendrycks, Norman Mu, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. Augmix: A simple method to improve robustness and uncertainty under data shift. In International Conference Learning Representations, 2020. G.1
Paul Hofman, Yusuf Sale, and Eyke Hüllermeier. Quantifying aleatoric and epistemic uncertainty with proper scoring rules. arXiv preprint arXiv:2404. 12215, 2024. 1, 1.2, 3, C
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv: 2011. 1, I, 1.2, 3, C
Eyke Hüllermeier and Willem Waegeman. Alcatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine learning, 110(3)4557-506 2021. 1, 1.2, B
Daniel D. Johnson, Daniel Tarlow; David Duvenaud, and Chris J. Maddison. Experts don't 't' cheat: Learning what you don't know by predicting pairs. In International Conference on Machine Learning. Proceedings of Machine Learning Research. PMLR, 2024. 2, 1.1, 1.2, 2.2, G.I, G.2, G.3, 5
Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Moment multical- ibration for uncertainty estimation. In Conference on Learning Theory, pp. 2634-2678. PMLR, 2021. B
Mira Jürgens, Nis Meinert, Viktor Bengs, Eyke Hüllermeier, and Willem Waegeman. epis- temic uncertainty faithfully represented by evidential deep learning methods? arXiv preprint wwXiv:2402.09056, 2024. B
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. abs/1412.6980, 2014. G.1
CoRR,
Nikita Kotelevskii and Maxim Panov. Predictive uncertainty quantification via risk decompositions for strictly proper scoring rules, 2024. 1, 1.2, C
Alex Krizhevsky. Learning multiple layers of features from tiny images. Tech Report, 2009. 4
Meelis Kull and Peter Flach. Novel decompositions of proper scoring rules for classification: Score adjustment as precursor calibration. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part 15, pp. 68-85. Springer, 2015. B, C, C.4
Salem Lahlou, Moksh Jain, Hadi Nekoei, Victor Ion Butoi, Paul Bertin, Jarrid Rector-Brooks, Maksym Korablyov, and Yoshua Bengio. DEUP: Direct epistemic uncertainty prediction. arXiv preprint arXiv:2102.08500) 2021. B
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances neural information processing systems, 30, 2017. 1.2
12

---

Published as a conference paper at ICLR 2025
Jouko Lampinen and Aki Vehtari. Bayesian approach for neural networks- reviee and case studies. Neural networks, 14(3):257- 274, 2001. 1.2
Yonghoon Lee, Rina Foygel Barber, and Rebecca Willett. Distribution- inference with hierar- chical data, 2024. 1.2
Jian Li, Yuval Rabani, Leonard Schulman, and Chaitanya Swamy. Learning arbitrary statistical mixtures of discrete distributions. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pp. 743-752, 2015. 3, 1.1,
Jeremiah Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax Weiss, and Balaji Lakshmi- narayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. Advances neural information processing systems, 33:7498-7512, 2020. B
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Confer-
on Learning Representations, 2017. G.1
Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. Advances in neural information processing systems, 31, 2018. 1.2
Andrey Malinin and Mark Gales. Uncertainty estimation in autoregressive structured prediction. In International Conference on Learning Representations, 2021. 1.2, C, C.3
José Mena, Oriol Pujol, and Jordi Vitrià. A survey on uncertainty estimation in deep learning classification systems from bayesian perspective. ACM Computing Surveys (CSUR), 54(9); 1-35, 2021. 1.2
Jeffrey W Miller. A detailed treatment of doob's theorem. arXiv preprint arXiv: 1rXivv/801.031220 2018. 1.2
Zachary Nado, Neil Band, Mark Collier, Josip Djolonga, Michael W. Dusenberry, Sebastian Far- quhar, Qixuan Feng, Angelos Filos, Marton Havasi, Rodolphe Jenatton, Ghassen Jerfel, Jeremiah Liu, Zelda Mariet, Jeremy Nixon, Shreyas Padhy, Jie Ren, Tim G. Rudner, Faris Shahi, Yeming Wen, Florian Wenzel, Kevin Murphy, D. Sculley, Balaji Lakshminarayanan, Jasper Snoek, Yarin Gal, and Dustin Tran. Uncertainty baselines: Benchmarks for uncertainty & robustness in deep learning. In Bayesian Deep Learning Workshop, NeurlPS, 2021. G.1
I.P. Natanson. Constructive Function Theory, volume of Constructive Function Theory. Ungar, 1964. E.3
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. Epistemic neural networks. Advances Neural Information Processing Systems, 36:2795-2823, 2023. 1.2, G.2
Deep Shankar Pandey and Qi Yu. Learn to accumulate evidence from all training samples: theory and practice. International Conference on Machine Learning, pp. 26963-26989, PMLR, 2023.
B
Joshua Peterson, Ruairidh Battleday, Thomas Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In 2019 IEEE/CYF International Conference on Computer Vision (ICCV), pp. 9616-9625, 2019. doi: 10. 10.11091CCC.2209.00991.
Theodore Rivlin. An introduction the approximation of functions. Courier Corporation, 1981. E.7
Aaron Roth. Uncertain: Modern topics in uncertainty estimation. Unpublished Lecture Notes, pp.
2, 2.2202.
Yusuf Sale, Viktor Bengs, Michele Caprio, and Fyke Hüllermeier. Second-order uncertainty quan- tification: A distance-based approach. arXiv preprint arXiv:2312.0099) 2023a. 1.2, C
Yusuf Sale, Michele Caprio, and Eyke Höllermeier. Is the volume of credal set good measure for epistemic uncertainty? In Uncertainty in Artificial Intelligence, pp. 1795-188888 1804. PMLR, 2023b.
B
13

---

Published as a conference paper at ICLR 2025
Yusuf Sale, Paul Hofman, Lisa Wimmer, Eyke Hüllermeier, and Thomas Nagler. Second-order uncertainty quantification: Variance-basee measures. arXiv preprint arXiv:2401.00276, 2023c.
1.2, C
Kajetan Schweighofer, Lukas Aichberger, Mykyta lelanskyi, and Sepp Hochreiter. Introduc- ing an improved information-theoreiic measure of predictive uncertainty. arXiv preprint arXiv:2311.08309, 2023. 1.2, C, C.3
Murat Sensoy, Lance Kaplan, and Melih Kandemir. Evidential deep learning to quantify classifica- tion uncertainty. Advances in neural information processing systems, 31, 2018. 1.2
Telmo Silva Filho, Hao Song, Miquel Perello-Nieto, Raul Santos-Rodriguez, Meelis Kull, and Peter Flach. Classifier calibration: a survey on how to assess and improve predicted class probabilities. Machine Learning, (111))3211-326600 2023. B
Hao Song. Tom Diethe, Meelis Kull, and Peter Flach. Distribution calibration for regression. In International Conference on Machine Learning, pp. 5897-5906, PMLR, 2019, B
Flemming Topsøe. Bounds for entropy and divergence for distributions over two-element set. J. Ineq. Pure Appl. Math, 2(2), 2001. E.3
Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal. Uncertainty estimation using a single deep deterministic neural network. In International conference machine learning, pp- 9690-9700. PMLR, 2020.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29, Springer, 2005. B
Zheng Wen, Ian Osband, Chao Qin, Xiuyuan Lu, Morteza Ibrahimi, Vikranth Dwaracherla, Mo- hammad Asghari, and Benjamin Van Roy. From predictions to decisions: The importance of joint predictive distributions. arXiv preprint arXiv:2107.09224 2021. 1.2
David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests in multi-class classifi- cation: A unifying framework. Advances in neural information processing systems, 32, 2019. B
Lisa Wimmer, Yusuf Sale, Paul Hofman, Bernd Bischl, and Eyke Hüllermeier. Quantifying alcatoric and epistemic uncertainty in machine learning: Are conditional entropy and mutual information appropriate measures? In Uncertainty in Artificial Intelligence, pp. 2282 2292. PMLR, 2023. 1.2,
JE Yukich. Optimal matching and empirical measures. Proceedings of the American Mathematical Society, 107(4): 1051-1099,,, 1989. D.5
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Richard C. Wilson, Edwin R. Hancock, and William A. P. Smith (eds.), Proceedings of the British Machine Vision Conference 2016, BMVC 2016, York, UK. September 19-22, 2016. BMVA Press, 2016. 4
14

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Review of notation and preliminaries
15
B Further related work
18
C Alternative uncertainty decompositions and semanties
19
C.I Proper losses and generalized entropy functions
19
C.2 Loss-based semantics of the mutual uncertainty decomposition
21
C,3 The Total Mutual Information decomposition
22
C.4 Loss decompositions and higher-order calibration.
22
D Proofs from Section
23
D.1 Useful lemmas about Wasserstein distance
23
D.2 Sandwich bounds for k-snapshot and higher-order predictors
23
D.3 Proof of Theorem 2.4
26
D.4 Proof of Lemma 2.5
26
D.5 Proof of Theorem 2.6
29
E Proofs and discussion from Section 3
30
E.1 Proof of Lemma 3.2
30
E.2 Equivalence between perfect higher-order calibration and calibrated uncertainty estimates
30
E.3 Proofs associated with Theorem 3.3
32
F Higher-order prediction sets
37
F.1 Moment-basse prediction sets from -rder calibration
38
G Additional experiments
39
G.1 Experimental details
39
G.2 Evaluating other uncertainty estimation methods in terms of higher-order calibration
40
G.3 Comparing our higher-order calibration algorithms
40
G.4 Binary regression
41
A REVIEW OF NOTATION AND PRELIMINARIES
Notation. We denote our instance space, or domain, by N. and our outcome space by V. We will focus on discrete or categorical spaces distributions on Y by A,, and the space of (higher-order) distributions on Ay, mixtures, by AAy. The space A can be identified with the (e - ddimensional simplex, denoted Ae and viewed as subset of IR We will often think of an element of A)' as vector in A, C RC (namely with nonnegative entries summing to one). It will often be illustrative to consider the binary case y [0, 1}. where probability placed on distribution, i.c. an element of A), will typically be denoted by p. A mixture, i.e. element of AAV, will typically be denoted by
(0...., f-1--1 13. We denote the space of probability
identify Ay with single parameter in [0, 1), namely the bias, or the
We follow the convention denoting random variables using boldface. Thus given a distribution p AY, random outcome from this distribution will be denoted by y p. Similarly, given mixture π E AA), a random distribution drawn from the mixture (i.c. random mixture component drawn according to the mixture weights) will be denoted by p
15

---

Published as a conference paper at ICLR 2025
We refer to k-tuple of labels (31...... yk drawn iid from distribution p AY' as k- k-snaphho.. Since the yi are drawn iid, the order of the tuple does not matter, and we generally symmetrize the snapshot and identify it with the distribution Unif yk.) We denote the space of all such distributions or symmetrized k-snapshots by y((k) 10 Note that (*(A) AA.. The space of distributions over symmetrized k-snapshots will be denoted Ayt().
Learning setup. We model nature's data generating process as marginal distribution Dx on X paired with conditional distribution function f* X + AV, where f" describes the distribu- tion of y | z = I. We make no assumptions about Dx or the form of f Recall that we define higher-order predictor as mapping X' + AAY. Even though nature is pointwise pure distribution f* X + AY, we model f as predicting mixtures to allow it to express epistemic uncertainty.
A partition of the space X' is a collection of disjoint subsets, or equivalence classes, whose union is the entire space. For any
X, use [x]] C X' refer to its equivalence class, and we use
[] as shorthand for the entire partition. The Bayes mixture over an equivalence class [x]. denoted f ([=]) E AAY by a slight abuse of notation, is the mixture obtained by drawing æ [x] according to the marginal distribution Dxx restricted to [x]] and considering (x). That is, every x' E [<]]
contributes mixture component f (x²) to f ([xx)), with mixture weight given by the weight of x'
under Dx restricted to [zc].
note on the role of partitions. Partitions play an essential role in any formulation of calibration for supervised learning. Consider an ordinary first-order predictor f X - AY learned from the data. We view this predictor as a complete summary of all the information the algorithm has learnt. In particular, all instances x that receive the same value of f(z) (i.e., lie in the same level set) are de facto not being distinguished from one another by f. This may be because they are in fact highly similar, or because f simply has not learnt enough to distinguish between them. In fact, in this view a predictor f is exactly the same as specifying level set partition (and values for each level set) ie. a predictor and a partition are in exact one-to-one correspondence. First-order calibration states precisely that over all instances that receive the same prediction, the predicted outcome distribution matches the true marginal outcome distribution (over all such instances).
In practice, we naturally relax the level set partition to merely be an approximate level set partition, in general an even coarser partition [-] of our choice (for reasons of tractability). Nevertheless, partition should always be thought of as expressing that points in an equivalence class are "similar" each other from the point of view of the predictor. Any formulation of calibration for supervised learning thus has the following form: in aggregate over all points that are treated similarly by the predictor, the prediction is faithful to nature. Our definition of higher-order calibration takes this form as well.
Alternative oothr representations of mixtures.In this paper we have chosen to represent the -oddrr projection of mixture as a distribution over k-snapshots, treating each snapshot as uniform distribution over its elements. More generally one can work with other representations. The following are three natural ways to define the -oddrr projection of mixture that will all turn out to be equivalent for us:
1. As a k-snapshot distribution, an object in Ay*k The k-snaaphot projection of a mixture π is the k-tuple distribution arising from drawing random p ~ n. and drawing yi,...y > Yk p
iid.
2. As m'h-moment tensor, an object in (Rf)8k; The 1th -ommmennt tensor of mixture π is exactly the object #1 where न..
3. As a symmetrized k-snapshot distribution, an object in Ay(k); The symmetrized k- snapshot projection of mixture æ is the distribution arising from drawing p n, then drawing (91,..., Mk) ~ p. and considering Unif(y This is how we originally defined projeT (see Definition 2.2).
10 is equivalent the space y modulo permutations. To avoid confusion, note that here we view as random vector on the simplex, and thus these are moments of probability masses, not of the labels in ) themselves. The latter is in any case not well-defined for us since, is categorical space.
16

---

Published as a conference paper at ICLR 2025
Observe that the pmf of the k-snapshot projection of is given exactly by the -mmmeent tensor of x: that is, for any tuple (yi....,, yk) E ) the probability mass placed on it by the k-snapshot projection is
Elp Pyu. Elp ( (an......))))
Moreover, this quantity is clearly invariant to permutations of the tuple. Thus it is clear that the sym- metrized k-snapshot projection of æ contains exactly the same information as the (unsymmetrized) k-snapshot projection, just more compactly represented. To be explicit, we can pass from k- snapshot distribution to a symmetrized h-snapshot distribution by summing the probability mass over all permutations of given tuple, and distributing the weight of given symmetrized snapshot evenly over all tuples that are equivalent to it up permutation.
similarly pass from the latter to the former by
In this sense the three 1.th -order representations above of a true higher-order mixture π are all for- mally equivalent, and we can in principle refer simply to the kn-order projection proje of a with- out specifying particular representation. Notice that from proję we can also form proj, for all j k, simply by appropriate marginalization (e.g., take the marginal distribution over the first elements of each tuple).
We could formally define oohorrder calibration in terms of any of these representations. But for the purposes of this paper the symmetrized representation is by far the most convenient since it allows us to view y((k) as subset of A)
Note that in general arbitrary distribution over y* need not be the k-snapshot projection of any mixture, and similarly an arbitrary tensor in (Re)@* need not be the 1thh -ommmetett tensor of any mixture. However when these objects do arise from snapshots of some mixture т, then they are equivalent to each other.
Worked X-ray example. For illustrative purposes, we walk through our running X-ray example using fully elaborated notation. Our instance space X' is the space of X-ray scans. The outcome space y binary: possible values are "does not require cast" (0) and "requires cast" (1). Note that in general )' may be any finite label space, but binary outcome spaces offer some convenient simplifications. For example, in this case, distribution over ) can be represented by single value in [0, 1], namely the probability of "requires cast". We denote the population distribution over scans by Dx. We assume there exists an idealized conditional distribution function f X + AY, with (z) representing the idealized probability, taken over all doctors' opinions, of whether requires a cast.
A first-order predictor outputs single distribution over ) for every x, ie. single prediction for the distribution of doctors' opinions for this x. As such, it expresses a composite kind of predictive uncertainty. Even if were perfectly first-order calibrated, this would only tell us that the prediction at x matches the average opinion ranging over the level set [x) of points with the same prediction as at x. There is no way tell whether an uncertain prediction corresponds to scenario where the predictor is perfect and there is genuine disagreement in doctors' opinions (its uncertainty is mostly aleatoric), or one where the predictor itself is uncertain even if doctors are not (its uncertainty is mostly epistemic). We illustrate this problem in Figure 1. Therefore, our goal is to learn f : X + AAY, higher-orde predictor which outputs a mixture of distributions in A.'' at every x. That is, in our example it outputs a distribution over the interval [0. 1] rather than single value in [0, 1].
To obtain a calibrated higher-order predictor, we can apply one of the algorithms in Section 2.2. For concreteness we opt for the second one, which calibrates a first-order predictor post hoc. First, we train a first-order predictor 7 in the usual fashion on a training set of tuples {z,, y1) where for each i, Jt; is sampled independently from Dx and is sampled from f*(x;) (simulating an individual doctor's opinion). We use the trained predictor to compute a partition [-] over the input space. The canonical "level set partition" places any given X-ray æ in the equivalence class [x] of all other inputs that f assigns approximately the same prediction (at some desired coarseness). (For example, [x:] might correspond to all images for which the probability assigned by / lies in [0.6, 0.65).) Next, for every such class [xr] we sample calibration set ( -.., v² },E(c) of k- snapshots. Within a snapshot, each of the & labels yf (E E [k]) is sampled completely independently of the others, corresponding to asking i different doctors for their opinion on the scan. Each k- snapshot can be turned into a distribution in AY: we count the occurrences of each discrete label, turn them into histogram, and normalize it. The larger the value of k the more closely this
17

---

Published as a conference paper at ICLR 2025
distribution will resemble the ground-truti distribution f(zz). Finally, calibrate the model by replacing the model's shared prediction for each equivalence class (namely f(x)) with the uniform mixture of the k-snapshot distributions for each of the calibration set inputs that fall into that class.
The resulting predictor is our higher-order predictor f. (Technically, for finite k. f outputs discrete distributions in A) not AAY, but this approximation also improves as & grows.)
Our theory shows that, for large enough N, C, and k, this predictor will be k-th order calibrated, meaning that its estimates of epistemic and aleatoric uncertainty are guaranteed to be good approx- imations of their actual values. For a given input x. aleatoric uncertainty is estimated by measuring the average entropy of all of the k-snapshot distributions in the prediction for [ar], and approaches the true aleatoric uncertainty: the value [B[G( G) of the ground-truth label distributions for all inputs in the same equivalence class as œ. Epistemic uncertainty, by contrast, is the remainder of the predictive uncertainty (see Eq. (3.1)). It turns out to equal measure of the "variance" (more precisely the average divergence to the mean) of f* ranging over ~ [ar] (see Lemma 1.
(z)((( (=)) ~ [x]]] or the expected entropy (measured by
B FURTHER RELATED WORK
Related notions of calibration. Our notion of first-order calibration over a general discrete label space y is the same the notion of canonical or distribution calibration due to Kull & Flach (2015); Widmann et al. (2019) (see also Silva Filho et al. (2023) for a broad survey). This was extended to the regression setting ()' = R) by Song et al. (2019); Jung al. (2021). While the latter works are related to ours (especially in the binary case where Ay can be identified with [0, 1)), the key difference is that only ever observe labels in the discrete space ) and never in the continuous space AV. In the limit as snapshot size k + do (so that we effectively observe (*) with each example), higher-order calibration over y' can be thought of as reducing distribution calibration for (high-ding dinenssimnssinaa) regression over the space Ay. However, no provable guarantees are known for the latter problem, whereas we actually provide provable algorithms using only finite-length
snapshots.
Distribution-free uncertainty quantification and conformal prediction. Our techniques share a common spirit with the literature on distribution-fii frree uncertainty quantification and especially conformal prediction (Vovk et al., 2005; Angelopoulos & Bates, 2021; Cella & Martin, 2022). This literature also makes minimal assumptions about the data-generating process and provides formal frequentist guarantees, typically prioritizing prediction intervals (or sets) for the labels. Our work provides "higher-order prediction sets" for entire probability vectors conditional on an equivalence class (see Appendix F). See Jung et al. (2021); Gibbs et al. (2023) for related work on conditional coverage guarantees. A key common theme in all these works well as in ours is the of post- hoc calibration as a way of imbuing ordinary predictors with formal coverage-like guarantees; see Roth (2022) for lecture notes on the topic and (Johnson et al., 2024, Appendix C) for an extended discussion of the relationship between second-order calibration and conformal prediction.
Other notions of epistemic uncertainty. In recent years one popular alternative approach to defin- ing epistemic uncertainty is to view it as a measure of whether an instance is "out of distribution" (sec c.g. Liu al. (2020); Van Amersfoort et al. (2020)). While sometimes reasonable, we believe this is not always justifiable. We instead define our epistemic uncertainty measure based on first principles, and allow for epistemic uncertainty to occur even in-distribution.
Another formulation of epistemic uncertainty studied in Lahlou et al. (2021) is as a kind of excess risk measure, assuming an oracle estimator for aleatoric uncertainty. See also Kull & Flach (2015) for similar decompositions.
Pitfalls of uncertainty quantification via mixtures and credal sets. Mixtures (also termed second- order or higher-order probability distributions) are common tools for modeling uncertainty (e.g. in Bayesian methods). However, they have been critiqued (see e.g. Bengs et al. (2022); Pandey & Yu (2023); Jürgens et al. (2024)) on the grounds that it is unsound to learn a mixture (a "Level-2" object in AA)) using ordinary labeled examples ( ("Level-O" objects in )). We agree with this critique, and it is why instead learn Level-2 predictor from k-snapshots, i.e. multilabeled examples (which are approximations of Level-1 objects in AY). Without k-snapshots, existing approaches to using higher-order distributions fall short in various ways. Our work arguably identifies exactly how these
18

---

Published as a conference paper at ICLR 2025
approaches fall short, and proposes (a) learning from k-snapshots a principled way of learning mixtures, and (b) higher-order calibration as a principled way of ensuring that these mixtures have clear frequentist semantics.
Such concerns have also spurred research into alternative approaches that avoid mixtures, such as credal sets (see e.g. Sale et al. (2023b); Chau et al. (2024)). Credal sets are incomparable mixtures, although for many purposes a nonempty credal set of distributions functions similarly to the uniform mixture over that set, and insofar as they do, they can be miscalibrated in the sense that we propose. In concurrent work, Caprio et al. (2024) introduces a notion of calibration for credal sets similar in flavor to our own (see Appendix F in particular). Ultimately, these and other alternative formalisms make different tradeoffs in capturing subtle real-world concept, and we work with mixtures as they are natural, expressive, and, importantly, allow proving formal semantics of the type we show in this work.
Further references. The area of uncertainty quantification and decomposition is vast, and here we have only mentioned works most related to ours (to the best of our knowledge). We refer the reader to the surveys by Hüllermeier Waegeman (2021 I); Abdar et al. (2021); 1): Gruber al. (2023) as well as the related work sections of Lahlou et al. (2021); ;); Johnson et al. (2024) for much more.
C ALTERNATIVE UNCERTAINTY DECOMPOSITIONS AND SEMANTICS
Many uncertainty decompositions have been considered the literature (Houlsby et al., 201 1; Kull & Flach, 2015; Malinin & Gales, 2021: Wimmer et al.. 2023; Schweighofer et al., 2023; Sale al., 2023a;e; Kotelevskii & Panov, 2024; Hofman et al., 2024), each making different tradcoffs (see e.g. Wimmer et al. (2023) for explicit axiomatic formulation of desiderata for such decompositions). Using the unified language of generalized entropy functions and proper losses, we provide a discus- sion of some of these alternative uncertainty decompositions. We also discuss further interpretations of the components of the mutual information decomposition.
We first begin with an overview of proper losses and their associated generalized entropy functions.
C.1 PROPER LOSSES AND GENERALIZED ENTROPY FUNCTIONS
Generalized entropy funetions closely associated with proper loss functions L x AY - R, where Lyy || p) is to be interpreted as the loss incurred when we predict the distribution and observe the outcome y. We can extend these functions L : AV AY' + I expressing the overall expected loss of with respect to a true outcome distribution p" by letting L(p" p) Ey-u- [yy p)]. 12 We call the loss (strictly) proper if for all p", (strictly) minimized when p p", and strictly proper if this is the unique minimizer. Define the generalized entropy function and the generalized (Bregman) divergence respectively as
G(p") L(p" p'), D(p" || p) L(p" 1 p) G(p")
Note that in all of these expressions, the expectation is always taken wrt the first argument. The first argument is usually (although not always) interpreted the truth, and the second as the estimate or prediction.
basic and important characterization of proper losses (under mild regularity assumptions; bound- edness suffices) is the following (see (Gneiting & Raftery, 2007, Theorems 1-2 and Figure 1)): the loss (strictly) proper iff its associated generalized entropy function G is (strictly) concave, and for all p, L(- || p) is the gradient of G at p. In effect, this means that to specify a proper loss it is sufficient to specify concave generalized entropy function G: the loss and divergence can then be obtained in terms of its gradient.
The most important examples of entropy functions are:
The extension natural and consistent if view y a point distribution 1 [v] E Ay'.
Heere L(: || p) denotes the vector (L(0) || p).... L(e - 1 |l p)) E R² Moreover, technically the concave analog of subgradient (a "supergradient", equivalently an actual subgradient of -G) suffices. In any case we mainly work with strictly concave functions, where this distinction does arise.
19

---

Published as a conference paper at ICLR 2025
1. Shannon entropy, GShannon (p) EyEy Py log 1. The associated loss Lshunnon (p p') Py Evey Py log is the cross-entropy loss, and the associated divergence D Shammon (p pl)
P/
EVEy Py log Ps is precisely the KL divergence. The associated pointwise loss function is P/
the log loss, Shaamon p) log J. In the binary case, GShannon [0. 1] [0. 1] is just Pv
the binary entropy function + log + +1 p) log T-p Note that our log always has base 2 by convention.
2. Brier entropy (Bri
Ilpl (also known by many other names, including Gini impurity). The associated loss turns out to be (p || g²) = lp p'll + |p|l and the associated divergence DBrier || p') = |lp r/112 precisely the squared Eu- clidean distance. The associated pointwise loss function is (the negation of) the Brier score, LBrier(y || p) Ip - [y]]] where 1yy] denotes the indicator vector of y. In the binary case, GBrier [0, 1] + [0, 1] is given by p 2p(1 p). 14
Bregman divergences satisfy the following cosine law, a generalization of the cosine law for Eu- clidean distances:
Dip pl) = D(p 11) + D(p l1 11) + (p p', -
(C.1)
where VG(p) is the gradient of G at p. viewed as vector in IR
A note on Shannon vs Brier entropy. It is worth noting that in the binary case, the Shannon entropy GShannon (p) = plog 1 + (1 p) log T-p and the Brier entropy GBiir 4p(1 p) are very similar as functions (where for better comparison we scale GBerr by a factor of 2 so that Greir ( = GShannon (t) ) 1). They match at p 0, 7 and 1, follow a very similar shape, and differ by no more than 0.15 at any point (see Fig. 4). For most practical purposes, we recommend that practitioners consider using Brier instead of Shannon, as the benefits afforded by its simplicity largely outweigh the minor differences. In particular, the simple exact quadratic formula for GBnir means that second-order calibration already suffices to approximate true Brier entropy and with a much better sample complexity (and simpler estimator) than for Shannon (compare Corollaries E.9 and E. Unless specifically needs to approximate Shannon entropy with very small approximation error and can afford large snapshot size k, Brier will typically be the more pragmatic choice.
G(p)
G Shannon (p)
Griee (p)
0.8
0.6
0.4
0.2
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Figure 4: Comparison of Shannon and Brier binary entropy functions. Here we use the scaled version of Brier entropy, namely GBriz 4p(1 p), for better comparison.
MIn the hinary case, further scaling factor of can he used so that Ganz(()) equals Ostanon (+) 1, but this is not an essential part of the definition.
For the Brier score, VG(p) -2p, and this equation is exactly the result of expanding ||p p²1 as (p(p p') (p' ?
20

---

Published as a conference paper at ICLR 2025
C.2 LOSS-BASER SEMANTICS OF THE MUTUAL UNCERTAINTY DECOMPOSITION
Throughout this section, we fix proper loss L Ay x Ay R and its associated generalized entropy function Ay + and generalized Bregman divergence Ay x Ay - R. As reminder, for p. p" E Ay, these are defined as follows:
G(p") L(p" ll p'), D(p" I] L(p" 11 p) G(p")
Lemma C.1. Given generalized concave entropy function G : AY E and its associated proper loss L AY x Ay + R and divergence D AY x Ay - R. the following equalities hold true for any higher-order predictor f X AAY, and moreover the equalities marked with
HOC
hold whenever f is perfectly higher-order calibrated wrt the partition [-]. Let pp= [p)
p" = Ept ([a) ((a)) (p). Then,
PUa(f x)== = E prf((a)
[L(p | p)]
HOC
[[pp" [1]]
pm-ff (o=ff((]]] ([x))
EUG(J : xx)=
E p~f(a)
D F))
HOC
E (-
[Dpp" |))]
Note that the characterization of EU implies the second statement of Theorem 1.2 when G is the Shannon entropy function and thus associated divergence the KL-divergence. We give some intution on these quantities before providing the proof. The restatement of predictive uncertainty tells us that can be equivalently thought of as the average loss of the centroid wrt random mixture component, f(x) [p || p)], while epistemic uncertainty is the loss in entropy of y upon learning the mixture component p. and is precisely the (generalized) mutual information between y and p. Thus, FU : x) be directly interpreted (one-sided) variance-like quantity, reflecting the level of disagreement or dispersion among the various mixture components.
Proof. We first prove the predictive uncertainty portion:
PUc(f x)) = G(p)
L(p p)
= E [L |p]
y-p
E (Ly p)
(since p ~ I,, ~ p i is the same as y ~ D)
p~f(x) w-p
[L p))
(C.2)
p~f(x)
Under higher-order calibration, we are guaranteed that (xx is identical to f'((x)), which also im- plies p = p" Thus, when f is perfectly higher-order calibrated, we additionally have
[L( b)] p~f(m)
E [L(2" F')]
p(-f*((+))
We now move on to epistemic uncertainty. In this case, we have
EUa(f : 2) G(p)
E [G(p)]
p~f(x)
E
[L(P F)
E [G())
(by Eq. (C.2))
p~f(())
p~f(x)
E p~f(w)
[pp p)].
Once again, if ff is perfectly higher-order calibrated, it immediately follows that f(x) f(((x)) and p = p", implying
E p~f(>>
DDi
[7] =
E
DD(P" 11 [[)
p(~)+(()))
21

---

Published as a conference paper at ICLR 2025
C.3 THE TOTAL MUTUAL INFORMATION DECOMPOSITION
An alternative natural expression for EU, studied by Malinin & Gales (2021); Schweighofer et al. (2023), is obtained by replacing the divergence between random mixture component and the troid with the divergence between two random mixture components:
EUG MT
(f:z)
E DD(p |l p')l p.D'~f(a)
We refer this the "total mutual information" formulation EU, as it turns out to be the sum of the mutual information between y and (i.e. [U(f =)) and the "reverse mutual information", notion studied by Malinin & Gales (2021) where the roles of p and p are reversed compared the usual mutual information form of EU (recall Lemma C.I):
EUG (f: x) == E [D p)]. p~f(x)
The fact that EUTMI EU + EMI RMI follows from an application of the cosine law, Eq. (C.1):
EUG(f : + BUG RMM (f xz) = DD(p p)1
E
[D(p
ll p)]
p~f(x)
p~f(x)
DD p')
P-P-
= Ef
One can use the new notion of EUTMI in place of our original notion of epistemic uncertainty in the mutual information decomposition get a new notion of predictive uncertainty and new "total mutual information decomposition":
E
[L(P || P')]
E
[G())]
E
D(p ll p/)
P.p'>/(())
p~f(a))
p.p'~f(a))
Predictive uncertainty (f
Alcatoric uncertainty estimate AUa(f=)
Epistemic uncertainty (TMI) EUTM (f:r)
(C.3)
The new PUT (f x) the average pairwise loss of the mixture components wrt each other (by comparison, recall that by Eq. (C.2), our original PUa(S= : x), was the average loss of the centroid wrt a mixture component). The AUo(J x) term remains the same.
C.4 Loss DECOMPOSITIONS AND HIGHER-ORDER CALIBRATION
Higher-order order calibration also provides information about the loss incurred by a particular prediction.
We consider two potential ways of measuring the loss of a higher-order prediction f (xx) with respect
to f The first is to predict the centroid of a higher-order prediction, i.e. p = Exp (p). The
expected loss over partition [xr] incurred when predicting the centroid p is exactly
[L(p" []] P=~f-((==))
(G(p))
+ E
(D(p. ll p))
(C.4)
((m)""((m))
avg AU
avg bias
When f is higher-order calibrated, this loss decomposition becomes exactly the cnntual-ifformatinnn decomposition by Lemma C.I, have
p"~ ([o)) [L(p"
||]] PUo(f 2),
=AU AUG(f:
F
and
DiD(p' p
p)] EUa(f z).
Thus, higher-order calibration not only provides meaningful semantics for predictive, epistemic, and aleatoric uncertainty the mutual information decomposition, but also ties them to the expected loss incurred when making predictions using the centroid of (x)
22

---

Published as a conference paper at ICLR 2025
A second, slightly less natural, choice of loss measurement is the loss incurred when predict at random according to p ~ fx)):
E [p. p)] E [['("" E [D [p] P-p-
p-p p.p
When f is perfectly higher-order calibrated, these terms are exactly recovered by PU (f AUa(f z), EUG (f I)), respectively, in the total mutual information decomposition.
We can also break down Eq. (C.4) even further by making use of the notion of the "grouping loss" from Kull Flach (2015). Let p = (p--)-(()) [=]][p"] Then our "average bias" term (which they term "epistemic loss") be decomposed further as follows:
DDe" 1
1 DD(p" 1 ID.
E
p (>()(()))
P--f"(())
avg bias
grouping loss
The FOC eгrоr measures how far our mean prediction p over the [x] is from the Bayes mean p". and the grouping loss measures the inherent spread in (*(x) over [ar]. If we have first-order calibration, then the FOC error zero. we also have higher-order calibration, then the grouping loss is exactly EUa(f x))
D PROOFS FROM SECTION
D.1 USEFUL LEMMAS ABOUT WASSERSTEIN DISTANCE
We present two lemmas relating Wasserstein distance and total variation distance that will be useful in the proofs for this section.
Lemma D.I (Gibbs & Su (2002), Theorem 4), Let p1, E AY be any two distributions in AY. Then, have
W W1 P2) diam(AY)drv (p1, p2) 2drv (p (P1,
where drv(P1.P)) = Illp P2ll: 1 is the total variation distance.
The last equality of the lemma follows special case due the standard fact that the maximum l, distance between any two points in the simplex A) = A is at most two.
Lemma D.2 (Gibbs & Su (2002), remarks in definition of total variation distance), Let p1, E Ay be any distributions and ((pi,p)) be the space of couplings between these two distributions. Then,
inf Pr drv (P)(P))))) (M1.82)>7
[y1 # Y2)-
D.2 SANDWICH BOUNDS FOR k-SNAPSHOT AND HIGHER- PREDICTORS
The following lemma will lay the foundation for proving sandwich bounds relating 1tth order and higher-order calibration error:
Lemma D.3. Given any mixture क E AAY (and in particular for f*((x)) and 0, we have WI(T, F) & (2v)(.
Proof. We consider the coupling I(π, proje.) defined by first drawing p n, then drawing k-snapshot from p by taking & i.i.d. draws y..... Vt ~ p. and outputting (p, Un..(y..... 9))).
By definition of the Wasserstein distance as the infinum over all possible couplings, we have [||p Unif(y)..... y.)...
Wi (IT, projem) <
E Up.ffi ..
Expanding out definition of μ,, have that
23

---

Published as a conference paper at ICLR 2025
Wi (T. projec) v
E
[lp
pru
D
Pj
1ly
5
pmw
1/1 1l -. p.d.
1
E
Pj
1 1
p--
Uk Vapiiid
k: i=1
D
E
kpp
Σ
1l: = 5
pm
k
V
Te Liddd
1=1
(
[kp)
E Mk piidd
Σ
1 $
PrwR
k
(Jensen's 's Inequality)
Note that for any j. Σx= ( 5] is distributed as a Binomial random variable outputting the number is out of l draws from Bernoulli random variable with mean Pj. This Binomial random variable has mean kp,, and so we can re-interpret the quantity under the square root as its variance:
27
kp,
Σ Iy = 5
-1)
Var(Bin(k, = =k)) p,) S k/4.
Plugging this upper bound back into the expectation, we get
D
Wi (T,,
S E
k/4
k/4
p-x
2vh
This gives us the desired upper bound Wi(T, proje.), completing the proof.
Using the result of Lemma D.3, we get the following corollary:
Corollary D.4 (Corollary to Lemma D.3), Consider any k-snapshot predictor g : X + Ay(k) and higher-order predictor X AAy. For any x, we have
|>'
(o(x)) - S
2vk
Proof. By the triangle inequality,
Wi(g(z), proja.(()) & Wi(o(z), f(x)) (r(jf()).rroaaf(())
|
< ((() +
(Lemma D.3)
2/h
The other direction follows similarly:
((() s Wi(g(s), (W)
(triangle inequality)
|}]
(roj(()) +
(Lemma D.3)
2/h
24

---

Published as a conference paper at ICLR 2025
Thus far, we've considered cases where have fixed k-snapshot predictor and compare to higher-order predictor or its projection. Lemma D.3 also allows us to prove Lemma D.5, a sandwich bound for the distance between two higher-order predictions compared to their kth order projections:
Lemma D.5. Consider any higher-order predictors f, h X AAY. For any k >> 0 and æ E X, we have
D Vk
projxh(z)) S Wi(f(=), (r))
& Wi(projef(z)) projeh(()) +
Proof. Fix any x E X' and k > 0. We begin with the upper bound, as the proof is very short (it follows almost immediately from Lemma D.3), and then continue to the lower bound.
By Lemma D.3, we guaranteed that (f( proje(())) and W1 (proja,(x)) h(x)) are both k). Applying the triangle inequality, it follows that
upper-bounded by (2//22/))
Wi(f(z), - Wi proje. (z)) + (projaa proj,,(())) + (i h(x))
s (prooj f(r), h())) +
(Lemma D.3)
Vi
This completes the upper bound. We proceed to the lower bound, and show that (prro,.f(z) proi, (((f()),
Let = arg (er(()())))) E(p-''allll- - p'll1]. i.c. the optimal coupling of f(x) and h(x) in the context of Wasserstein distance. We use μ to construct a coupling f4 of f and projgh(x) follows. We first draw (p.p') μ. and then sample k pairs of y-values, i.idd, (1.3,),... (yr, v ~ pp,,p'), where 7(, p') is the optimal coupling of p and p' defined as
<(p p') arg min Pr by + y'). "ET(p.p') (u.rr)y
We then aggregate these k y's k-snapshots, and output the pair of distributions 9 Unif(y ys) and q' Unif(y''..... y()) This defines our coupling pk- Since ~ f and q' h(x), this is valid coupling of projg((x) and projg (xx), so it upper bounds the Wasserstein distance between these two mixtures:
W1 (x).
[lq q' [']
(g.44)pp
We will now show that
I [llq (q.4")~p
d'1b1
S
E 11pppppppl p'l
(p.p/)>p
i.c the expected distance under pairs of distributions drawn from M4 is smaller than the expected distance under pairs drawn from and thus lower-bounds (f((()) h(x)) by definition.
Expanding the definition of μık, have
E [llg q' [h]]
E (P.P Sop (v v1 ) ..... ppp dii.d
[II Unif( yk) Uni
(a.94)~<4
[2 ver(Uuif Der(Cunffly............ Unif(y ./.. )u
inf
Pr lv 7 v')
(p.p yeu (wr b..... yv. (p. ('d.d).
Where the second step follows from Lemma D.2 (note that drv (p1, P2) = 1| - P2 121112).
Among the possible couplings of Unif(y1,.... yk) and Unif(y''... ... v.)). such coupling is to draw an index ~ [k] uniformly, and then output the two y: and y corresponding to this index. This gives upper bound of
25

---

Published as a conference paper at ICLR 2025
E
llq q' [11]
E Pmy
inf [2 vEr(Unif(y) V.. M. U/. (wner)n 1y * v']l
Pr
(a
(p.P 1~p (2/1 A te (p.pp ).d.
I (p.P 1~
[2 (niii((()))
Pr
We * vill
(p.p/ ).k.
E (p.P Prpp (mn.2) J ( Lan (a ).i.t.d.
Pr(y: + v/l
by + y'1 (w
Pr
(p.p'
where the last step uses the definition of la as obtaining yı, V as independent draws from the optimal coupling of p and p'. Further simplifying, we get
2
E (a.a")~<u
d'111] S [llq
(vra)) (p. w y'l
Pr
(p.p')mu youps
y + +
Pr
pp.p jmp
(v.ar) (ppppp
1|p
p [1a]
(Lemma D.2)
(p.p')
(i(((z),
(Recall in the application of Lemma D.2 that y defined the optimal coupling of p and p' in terms of the cost d(y, y') = 1yy * s/(). The last step applies the definition of μu as the optimal cou- pling for f Wasserstein distance. We conclude that W, f pro), Wi (x)),, h(x)), completing the lower bound.
D.3 PROOF OF THEOREM 2.4
We restate the theorem for readability:
Theorem D.6 (Restatement of Theorem 2.4, Corollary to Lemma D.3: -oh-rrder calibration implies
higher-order calibration.). Let g X > ()(5) be order calibrated with respect partition [.]. Then, we can guarantee that is also (e + 2v highherrrodd calibrated with respect to the same partition [:].
Proof. The theorem follows immediately from Corollary D.4, which tells that for any x E X,
|
((()()), < proja ((x))) +
2v
ooddrr calibration tells us that Wi (i( proix < and thus the higher-order calibration emror (f is bounded by +
[
D.4 PROOF OF LEMMA 2.5
We restate the lemma for readability:
Lemma D.7 (Restatement Lemma 2.5). Let y = {0,1}. and let g X - AY be e-kh e order
calibrated with respect partition [)] Then for each x E X, we use g(x)) to generate vector
26

---

Published as a conference paper at ICLR 2025
of moment estimates (m1..... mp) R20 such that for each i [k],
2>|()] [-) ( s ie/2.
m,
The proof will make use of an intermediate lemma, which tells that the first k-moments of mixture π E AAY can be exactly reconstructed using only its hthh -oddr projection:
Lemma D.8. Consider any mixture π E A 1] and its 1th -order projection proja E A
1}. For m E [k]. let Mx,m /0, 2/k, 1} [0, be function defined as 1/k, (00,1/k, follows:
p p p2m/ m/k
Ma. (p)
otherwise
Then,
E prppojer
(Mxm(()) = [p'
pr-
Proof.
Consider the expectation of Me, under proje
Vi k
E f--projy
[M..(())
E
Mk.m
pro D B ppiid.
One way to view Mx.0 (p) is to view p 3 i/k as a snapshot with i is and - Os. M (p) gives the probability that a random permutation of this snapshot starts with m consecutive Is. Because the distribution over possible permutations of snapshots is symmetric, we can equivalently express the above expectation just the probability that random k-snapshot starts with m 1s:
E
km (D)
E
[1y), ... Um 1]]
puprroje
Yi.... p.idd
m
yil
p
yi.... Mk Papppppl p.idd.
E yMP
[y]]
(independence of y:s)
pm
E
pm
E
p-5
Thus, the expectation of Ma.m over the mixture proje v is guaranteed to be exactly the m-th moment of the higher-order mixture
Additionally, we show that each Mj.x satisfies Lipschitz condition, which will imply that evalu- ating the expectation of MG on a distribution close Wasserstein distance to projef f(xx))(())) will closely approximate the true moment.
Lemma D.9. Let MR.m be defined as in Lemma D.8. Then, for any P1, E {0, 1/k, 1}, we are guaranteed that
MM (M)m((2)) & m|p1 -pll-
Proof. We note that it suffices to show that for any consecutive p1 and pa = Pi - 1//k we have Mk. (P2) S m/k:
MM (p1)
27

---

Published as a conference paper at ICLR 2025
then it follows by telescoping that for any P1.P2 10,1/K,.... ..., 1}, assuming without loss of generality that 2 P2, we have
Mk. Mk.m (P2) S mlp1 Pal.
giving the desired bound.
There are three potential cases: either (1) MR (P1):(1))))))))))) Mk (p2) MM,m(P2) 0 (wlog), or (3) Ms. (P1) MR, (P2) 0.
> 0, (2) (p
In the last case, we trivially have [M,,((1)) Ma (P2) = = We focus on the other two cases.
Case Mk.m (P1). M.. Mk. (P2) 0. By assumption, there some
> m such that pık = i,
P2k =i-1. We use this to simplify the difference between Mr.m values:
MM (p1) ( Mk.m (P2)
=
k
m
m
We observe that for fixed m, and this quantity increasing in for i 2 m because the denom- inator is constant, and (m=1) is increasing in m. Thus, we can upper bound the difference by the difference achieved by the largest possible value of which is k:
(M MR,m (p2)
m
m k
Finally, we consider the last case:
Case 2: Ma.m (P1) > O, MR. (P2) O. Because pı p2 + 1/k, and ME. (p) is always positive for any p 2 m/ k. this case can only happen when P1 = .m/k and p2 = (m 1)/k. We calculate the difference for these values:
m
m!(k m))
Mk (p1) Mk. (P2)
k!
k
k-1
k
Thus, all consecutive differences are bounded by m/A: completing the proof.
We are now ready to prove Lemma 2.5 in full.
Proof of Lemma 2.5. At a high-level, to calculate an approximation of [f using ((x),
we will calculate E (ooggt))Ma,il and show that it is a ie/2 approximation of the 7th moment, (x))))
Consider any x E X' and E [k]. Using the triangle inequality, we upper bound the difference between our estimate and the true moment value by:
E (()g(z)
ME.(())
E [ P.~f-((x))
([x)
E
[M.
E (p)
+
E p-proj
[Mni(p)]
E D-~F ((x))
[pt]
p-proj f- ([a))
E
MR. (p)
E p-proj_ (~x)) ([x))
[My i (p)
+0
(Lemma D.8)
(
We will now Lemma D.9 to show that the remaining term is bounded by me/2.
28

---

Published as a conference paper at ICLR 2025
Let [[g(z), (rojxf(((=)))) be the space of couplings of g(x) and projæf"(xx)) We can re-express the difference in expectations as
E [P)] - (a)g(a)
E
[p']
=
E p~g((a)
Ma. (p)]
p.~f-(ax))
proproje f* ((a))
min
E
[Mxx: Mp,
p ((=))
(p.p)~>
min
E
1ipp pll
(Lemma D.9)
rEIlo(e).proii (p.p)~>
= (r) ((=)))/2
- ie/2
(1th calibration)
note that the factor of 1/2 comes in because pp- pl is 1/2 of the & distance when p and viewed as distributions over {0, 1}.
Thus, we've shown an additive error of ie/2 for estimating any moment E [k], and thus can construct a vector such moments for each E [k]] satisfying the desired guarantee.
D.5 PROOF OF THEOREM 2.6
We restate the theorem for readability:
Theorem D.10 (Restatement of Theorem 2.6, Empirical estimate of 1tth -orde projection guaran- tee). Consider any x E X, and a sample p ... ,N E y(k) where each p. is drawn i..dd from projæs Given 0 and 0 S 8 < if N guarantee that with probability at least - 8 over the randomness of the sample we will have
[lg)))))ogg()) + =lo((1/)))/&, then we can
(f(projaf"((z]] Unif(p:......P <.
As some discussion before the proof, we note that this sample complexity guarantee obtained via bounding the total variation distance between ffoj, and (ni which provides an upper bound on the Wasserstein distance. This approach reasonable for small values of k, which we consider to be the most realistic setting where k-snapshots might be obtained. When k large compared to f, we can alternatively obtain sample complexity bounds depending only on the dimensionality (roughly of the form (1)))0(0) by directly exploiting known results on the convergence of empirical measures to true measures in Wasserstein distance (Yukich, 1989).
Proof. For ease of notation, we will denote मे := Unif(p1..... PN) and x² := proje ((x)).
We first observe that by Lemma D.I, guaranteed that
Wi (f, x S 2drv (ft,
Thus, we conclude that whenever drv (x", , 7) s c/2, then we are also guaranteed that
Wi 77) e.
This reduces problem bounding the total variation distance of the empirical estimate of the discrete distribution n projj ([x]). which observe is supported on [2((k) points.
We now use a standard argument for bounding the total variation distance (see Canonne (2020) for
discussion of various approaches to this argument).
Note that the total variation distance can be alternatively expressed as
drv(m",
sup sCy
Pr E S] par"
Pr Pp p~3
Thus, ( > e/2 iff there exists some C (1)) such that Pr ip E S] Pr Prp (p E 8] e/2.
29

---

Published as a conference paper at ICLR 2025
We bound the probability that this happens for any S via union bound. Select any S S )(() and note that Prpwal (p E S] can be written as a sum of i..d. Bernoulli random variables X1, XN. all with mean Prp-x E S]. This allows to apply Hoeffding's Inequality to conclude that
N
Pr
Pr Pr > Pr (DES)+ pvn
= Pr
Σ
x;
x
+ +/2 +
N
N
1=1
exp(
--N
(Hoeffding's Inequality)
Thus, for any N 2 2(1)(()) (2) + log we are guaranteed that
p pJ Pr pre s) s 6/2
Pr
Pr p
pas
Union bounding over all 2/3)(4)
possible S, we get that
Pr|drv(r (T²", , R) e/2] Pr is C yo
s.t. Pr Pr 5] pau
Pr 1p E +| pa
I 2
2 8.
Thus, we have shown thatn N > 2(22(00 logg()))))((1)) samples are sufficient to guarantee that with probability least 1 5,
Wi (projee ([=]), Unif( ...,).N)))))))))))>>)) s
E PROOFS AND DISCUSSION FROM SECTION 3
E. PROOF OF LEMMA 3.2
We restate the lemma for readability.
Lemma E.1. (Restatement of Lemma 3.2) If > AAY is perfectly higher-order calibrated, then for all X,
AUalf :))= E x~1x]
[AU)())).
Proof. Since f(x) f ([x)) as a mixture, AfG(f:
:x)= :x)
E [G())] p--f(x)
E (aa)"
[G(p.)]= E [G(f(
= E
(x)] x~/
E.2 EQUIVALENCE BETWEEN PERFECT HIGHER-ORDER CALIBRATION AND CALIBRATED UNCERTAINTY ESTIMATES
At first sight, the ability to produce calibrated estimates of aleatoric uncertainty may appear to be merely one small consequence of higher-order calibration. But somewhat remarkably. it turns out that having accurate estimates of AU wrt all concave generalized entropy functions equivalent to higher-order calibration.
Such statement requires a definition of what entails a "concave generalized entropy function." We take the most general view possible, building on the work of Gneiting & Raftery (2007), who show that every proper loss has an associated generalized concave entropy function, and in particular every concave function G AY' + IR is associated with some proper loss (see Section C. for more in- depth discussion of proper losses and their associated entropy functions). From this point of view, the class of generalized concave entropy functions is exactly the set of all concave functions. Under this definition, we get an equivalence between calibrated estimates concave entropy functions and higher-order calibration.
30

---

Published as a conference paper at ICLR 2025
Theorem E.2. A higher-order predictor f X AAY is perfectly higher-order calibrated to f wit a partition [1] if and only if AUG(f x) = -B [ (x)) wrt all concave functions
G: A: R.
Proof. The higher-order calibration implies AUc(f x)) = [x (AU)) direction is proved in Lemma 3.2. We focus on the reverse direction.
We will leverage the notion of moment generating functions. The moment generating function of random variable X E Re is function Mx R + I defined by Mx (8) Ex [e' x]. An important property of the moment generating function is that if Mx (t) is finite for all & [-c, clé for some c > 0, then its values uniquely determine the distribution of X (DasGupta (2010), Theorem 11.8). In other words, if we have two random variables X and Y such that Mx (t) Mt < oo for E [-c, cj". then and Y must be the same distribution.
We will use this line of reasoning to show that the predicted and true mixture for some partition [at] must be the same their estimates of all concave functions are identical.
Fix some X, and consider the predicted mixture p f(x) as well as the true mixture p" ((x)..
We consider the set of functions g {Gr)ee(-1.jj where each G. Ay Ge(p) = e 6pp11
R is defined as
Note that by definition, for any / [-,,
AUG, (f = E p~f(a)
[G:(p)]
1- (1)
(E.1)
p~f(a)
and similarly
[AU (x:] = E
[G((")]]
=
E
1- --Mp- (t)
(E.2)
[ [z]
p'>ff((=))
p~=)--(=))
We make two assumptions which we will prove later:
1. Every G2 E G is concave.
2. AUg, (f x) and Ex-|>)[UU, (x)) are finite for all G2 E g.
With these two assumptions, the proof is quickly complete. In particular, if all G, are concave, then by the main assumption of our theorem, we have
AUg, (f xx)
E a-
[AUG, (x))
for all G. G. The equivalences shown in E.1 and E.2 imply that also have
Mp(t)= (p-
for all 1]., Our additional finiteness assumption implies that these moment generating functions are finite for E [],, and thus by the uniqueness of moment generating functions, we conclude that the distributions f(x) and f" ([xx) are identical. Because this holds for any x E X, we conclude that (I) is perfectly higher-order calibrated.
It remains prove our assumptions of concavity and finiteness.
We first show finiteness, which follows almost immediately because AY' bounded, and thus for any p E AY and E [-c, cf, we have t E [-c, c] and thus - E (e-9,e") Thus the expectation of e! for any random variable p AY is guaranteed to be finite.
Note that scaling by an additive constant ensure this function is non-negative on A) if we would like require that entropy functions neg-negative, without changing the result of the proof.
31

---

Published as a conference paper at ICLR 2025
We finally show concavity. Consider any G₁ and P1.P2 AV, E [0, We have
CApr + (1 A)p2) = - (Ap1+(1-A)ps
- p1
because -e
< is a concave function, we have that
- (1 -))r" 2 -Xee'pi pr - -Aje
(G((p1) + (A)
Thus, we conclude that Gp(Ap1 + (1 A)p2) 2 AGo(P1) + -P)G( and so each G5 E g is concave.
We add some additional discussion more stringent definitions of what qualifies as a generalized entropy function. Above, our only requirement was concavity, though we note that the nature of the proof suggests that this class could be further restricted to the set of continuous, concave, non- negative functions on A)
Another potential requirement for entropy functions symmetry-invariinne to permutations of the class probabilities. We highlight that requiring symmetry would break the equivalence between calibrated entropy estimates and higher-order calibration. To illustrate this, consider a simple coun- terexample:
Assume (x) has no aleatoric uncertainty for each æ, and thus assigns probability to some class i E [e]. Now, consider higher-order predictor that, for each z, predicts point mixture concentrated on a distribution that gives 100% probability to some class j E [é]. Under any symmetric entropy function, this predictor would appear to have perfect aleatoric uncertainty estimates. Both f" and the predictor assign 100% probability to a single class for each æ. However, this predictor is far from being higher-order calibrated, as it may consistently predict the wrong class for every æ E X.
E.3 PROOFS ASSOCIATED WITH THROREM 3.3
In this section, present proofs associated with the statement of Theorem 3.3. We first prove the last statement of the theorem, which follows from a general guarantee in terms of a concave entropy function's 'sss modulus of continuity.
Definition E.3 (Uniform continuity and modulus of continuity). Consider a function G Ay - R, where we view AY as a subset of R equipped with the l distance metric. We say that G is uniformly continuous if there exists function we Rzo Rzo vanishing at 0 such that for all p.p' E A,, we have
[G(p) - G(p') s wo(lp p'112).
The function Wg is called the modulus of continuity of G.
Remark E.4. Uniform continuity can be usefully thought of as relaxation of Lipschitzness. The latter is the special case where (ā) < O()). We will always be concerned with the behavior of wa for small values of 8 < 1, and in this regime we may assume without loss of generality that (G(() (6) < (6")) for some a. Moreover, we may assume that a < 1, simply because if a > 1 then 8a S 8 (for small 8). In particular, wg can be assumed WLOG be concave, non-decreasing function for small 6.
With this notation in hand, we are now ready to present the statement in full. The proof is provided in the following section (E.3.I).
Theorem F.5 (Informally stated in last point of Theorem 3.3). Consider order predictor g
X ()()) that satisfies e-kth-orde calibration with respect to a partition [.. Let G be any concave entropy function that satisfies wniform continuity with modulus of continuity wa R2o + R-z- Then, g estimate of aleatoric uncertainty with respect to G satisfies the following guarantee
for all x E X:
AUalg: : :x) F. (x)) & sole+ 1)
2/k¹
32

---

Published as a conference paper at ICLR 2025
We now move to the first two statements of Theorem 3.3, both of which follow from alterna- tive means of estimating the true aleatoric uncertainty under hthh -order calibration using polynomial approximation.
In the rest of this section we specialize to binary labels y {0, 1}. where Ay may be identified with 00, 1]. and G [0, 1] - R becomes simple real-valued function on the unit interval. We now state Jackson's 's well-known theorem from approximation theory on approximating such functions using polynomials.
Definition E.6. We say that G : [0, IR admits (d, a, -o-llyoooli approximation if there exists degree d polynomial p(t) Σi Bit such that | s for all and
sup (p(t) G(t) S a. sE(0.1]
Theorem E.7 (Jackson's theorem; see e.g. (Rivlin, 1981, Thm 1.4)). Let G : [0, 1] + E be uniformly continuous function with modulus of continuity wa. Then for any > 0, G admits
(d, (ww((()))))))))))))))))))))))()) ()), exp(O(d))) - pollyoomil approximation.
The bound on the coefficients can be shown using standard bounds on the coefficients of the Cheby- shev polynomials, but also holds more generally for any polynomial F that is bounded on the interval (see e.g. (Natanson, 1964, Cor p56)).
We now give an alternative to Theorem E.5 that can provide better emrrr guarantees for particular choices of G in regimes where k is quite small, and thus the D'' 2vR term arising in that theorem
could dominate the overall error. Recall that we are working with the binary case ( = {00 1}) for simplicity. In this case our mixture gives random variable [0, 1]. and we have the following theorem:
Theorem E.8. Let y = {0,1} and let G [0, + R be a concave generalized entropy function that has a (d, ax B'-polynomial approximation. Then, ifg X + Ay(k) is an e-k -order calibrated predictor for any k 2 d. then for each X, we can g estimate Ex-[s] (AUg(x)) (x)) to within additive error 8 = a + dBcB22
The full proof can be found in Section E.3.2. To apply this theorem, need to show that commonly used entropy functions have good polynomial approximations. We show that this is indeed the case for the examples considered earlier. The Brier entropy Gini impurity GBier( 4p(1 p) is trivial since is itself a quadratic. Hence we get the following corollary (informally stated as the first bullet point in Theorem 3.3):
Corollary E.9 (Corollary Theorems E.8 and 2.6, Estimating Brier Entropy). Let O. Let 9 X (2(2) be an secoo)-ecoodd-rrer calibrated predictor. Let Gnrier(p) 4p(1 pp) denote the Brier entropy. Then we can use g to obtain an estimate Brier such that with high probability
AUBrier Brier
[AU
Gaar (z)) Sc.
In particular, we require only N > log(2) + log(1/8))/e 2-snapshot examples from [x]] for this guarantee to hold with probability at least 1 8.
Proof. The Brier entropy presents particularly easy case of Theorem E.8 because (Biier(p) 4p(1 - p) is itself a polynomial of degree 2 with coefficients bounded in absolute value by 4.
Theorem E.8 thus guarantees that an (e/8))-secoddordd) calibrated predictor can estimate [AU (f*()))] to within an additive error of
Theorem 2.6 tells that N > 128(4 log(2) + log log(1/8))/e samples from [a] sufficient to guarantee an e/ e/8-second-ordes cadbiiirrrr giving an additive error of when estimating the aleatoric uncertainty.
calibrated prediction for [x]] with probability at least 1 - 6, thus
In the case of the Shannon entropy, we get the following corollary, captured the second statement of Theorem 3.3:
33

---

Published as a conference paper at ICLR 2025
Corollary E.10 (Corollary to Theorems E.8 and 2.5, Estimating Shannon Entropy). Let 0. Let 9 :: X'' - Ay(k) be an e' -order calibrated predictor where Z (({+) ((()))*,, and é' (xp(@(R))
Let G Shannon (p) P logg pp) log(1 P) denote the Shannon entropy. Then we can g to obtain an estimate AU Shamnon such that with high probability,
AU Shannon
E [AUG maamnnn (a)) Sc.
In particular, require only N ((log(1/6) exp(O((1/e) k-snapshot examples from [ac] for this guarantee to hold with probability at least 6.
Proof. The Shannon entropy GShamnon -p log (1 p) log(1 p) can be dealt with ing Jackson's 's theorem (Theorem E.7), which tells us that for any d 2 1, there exists degree-d polynomial F and constant C1 such that
sup [F(x)) GShamoon S Ciwa(1/d), =c(0,
and the coefficients of F bounded by exp(C2d) for some constant C2- Here we is the modulus of continuity of GShannon (Definition E.3), defined by
wa(r) sup Shannon (p) Shammon (p')l p.p' [0, Ip 1--20 p'l x)
In the case of the binary entropy function, it is easy to see that the supremum is achieved at the endpoints, e.g. at p 0,p' I, and (G)r) GStunmon (x). Now, it turns out that the binary entropy function satisfies the following useful bound (Topsøe, 2001):
GShanoon (x) < (4x(1 - x)) lu4 S 2/444
Thus, ensure Clwa (1/d) e/2, suffices to take k 2 d 2C )'d We choose the minimal snapshot size that can achieve this, and take
(C lnd
By Theorem E.8, this value of k we are guaranteed an e'-1thh-rdee calibrated predictor will give estimates of the aleatoric uncertainty with additive enror at most e/2 + Cakk /2.
Thus, there exists a constant C3 such that it suffices to have e' S موك to guarantee an error of at most Plugging this bound into Theorem 2.6 tells us that there exists constant C4 such that N > (1/e) (og(1/6) samples from [x]] are enough to guarantee that the -'h-order calibration error in that partition is at most cdsk with probability at least 1 8, thus guaranteeing that the overall additive approximation error of estimating the Shannon entropy on [x] will be at most with probability at least 1 ö.
We complete the proof by noting that ())
E.3.1 PROOF OF THEOREM E.5
We restate the theorem for readability:
Theorem E.11 (Restatement of Theorem E.5). Consider a -or-er predictor g + A3)() that satisfies e- -oder calibration with respect partition [+]. Let G be any concave entropy function that satisfies uniform continuity with modulus of continuity Wa : R200 + E20- Then, g estimate of aleatoric uncertainty with respect to G satisfies the following guarantee for all X:
|
AUglg: : x) E. [AUG(a)] S wole+ + am|(a]
20
Proof of Theorem E.5. Consider any x E X. Using the definition of aleatoric uncertainty with respect to G, we rewrite the distance between the true and estimated AU as
AUd(g x) - mn/s]
(x)] = [G(p)]
E
[G(p))
pros(x)
p**f(((a))
34

---

Published as a conference paper at ICLR 2025
Let be the optimal coupling of g(x) and f(xx]), ie.,
P
arg min "f (I)) (p."'~w' p p²1
We can rewrite the above expression in terms of μ as
AUo(g:2) :z) - E (x)]
m-(a]
E
(G(p) G(p'))
s
E
[[((p) G(p")]]
s
E
wolllp -p'll)]]
(uniform continuity of G)
S wa(
E (p.p") ya
|Ip---'lli] p'll1))
p-
(Jensen's 's Inequality Concavity of wG)
See Remark E.4 for discussion of why assume that wi is concave.
Because g is e-kth-order -rder calibrated, by Theorem 2.4, we can guarantee that it is also (e
12/1 [-
2VR
higher-order calibrated, and thus we are guaranteed that (i(g(z), ((z)) <
|]] 2v
Expanding out the definition of ei-Wasserntein distance, because μ was defined as the optimal cou- pling of g(x) and [[x)), we have
Wi (l()) =
arg min (g()) (p.z") (p.p")
E |llp pop-p"lli
p"111]
E
p'll
s +
(p.
2
We can use this upper bound to further simplify our above inequality as
AUalg:
E mm/pp [m)]
S Swal
E
[llp
p1]l
(p.P") J~p
|
S <wole+ +
2/k
giving us the desired upper bound the enror of our aleatoric uncertainty estimate. Note that the final step assumes wa is non-decreasing. We refer to Remark E,4 for a discussion of why this is reasonable assumption.
E.3.2 PROOF OF THEOREM E.8
Theorem E.12 (Restatement of Theorem E,8). Let y {0, and let G: [0, [9 be a concave generalized entropy function that has (d, -ollynooll approximations. Then, if X (y()) is an e-k">ooddr calibrated predictor for any k d, then for each X, can g estimate [=-[t|[AU to within an additive error a + dBe/
At a high-level, the proof will leverage Lemma 2.5, which tells that th order calibrated predictors can be used to obtain good estimates for the first k moments of the true bayes mixture. Because degree-d polynomial of random variable p can be computed using only the first d moments of p. we can use our moment estimates to compute any degree d < & polynomial, which will provide good estimate of aleatoric uncertainty when that polynomial closely approximates G.
Proof of Theorem E.8. Fix some r E By assumption of the theorem, G has (d, a, -oooloooooiiall approximations, This means that there exists a degree-d polynomial c(t) = Σ 3,t" such that for all i (0, d), |&| & B, and for all & [0, 1]. le(t) G(!) < a.
35

---

Published as a conference paper at ICLR 2025
The polynomial thus be used to approximate B=-[s) (zU) to within additive error of a:
E
(c(]
E [aU)(()]
E [o(s( - E (((
E [le(S(()))) - -G(
x~|a]
E [a]
2~/
a
We now want to show that we can obtain a good estimate of Ea [c[[f((((((( only with access to g- We expand out the definition of e have
[[(((
E [
(())
2~/22]
Σ 100
B E 2~
[f)')
Let mi, ... my R20 be the moment estimates of E Ez [f (x) I .... (x) respectively that are obtained from g via Lemma 2.5. Because d k. for each E [d]. the lemma guarantees that
my
E If (x) 2~
ie de/2.
(E.3)
Substituting in each of these moment estimates for |x [ (x) in the computation of e will give di dBcB/ (BeBB22addinn 2-additive approximation of [f=))]((f((
E (c([" x~(ar]
(o Σ 3,m
Σ
8 E
[-())) - 8o + Σ 3am
|3:
IE (x)) - mi
< B
E [f*()))
(33:1 S B for all i E [d]
1=1
B
de/2
(E.3)
Bdle/2.
Putting all our pieces together, we show that 3, + Σ' B,m,, which is computed only using g. gives additive d² d rappoooapooinn to E. Re (AU) By the triangle inequality,
E [AU x~
Bo Σ 3mm
[AU
|c[ (x)))
+
[x(f((x))]
Bp + Σ 8,m
/~/ < + c/2
x
im
giving the desired additive approximation.
36

---

Published as a conference paper at ICLR 2025
F HIGHER-ORDER PREDICTION SETS
In this section we describe how to obtain prediction intervals, or more generally prediction sets, from higher-order calibration. These prediction sets have the property that they capture the true (*) with a certain prescribed probability when @ is drawn conditionally at random from an equivalence class, We stress that these are not prediction sets for outcomes a particular instance, but rather higher-order prediction sets for entire ground truth probability vectors ranging over a group of in- stances; they are subsets of the simplex Ay' and not of y. In this way they provide an operational way of expressing and using our epistemic (rather than merely predictive) uncertainty." !?
Definition F.1 (Higher-order prediction set), A set 5 C A)' is said to be higher-onder prediction ser for the Bayes mixture f ([z)) with coverage 1
the following holds:
PP 2
(x) S]
The main idea is simple. If is perfectly higher-order calibrated for certain partition [] then for every æ, f(x) matches ([x]) exactly as a mixture. Thus any set that captures - a mass under f() also captures 1 mass under f ([=x):
P x
If E S]=
p(~f*(()) - P
p' E S]
P p=)(
=1-1 a.
(F.1)
In this way we can take our prediction f(x) (which in principle we have complete description of), take any set S that captures directly as a 1 prediction set for f (2:) when a ~ [ar].
of its mass (there are many natural ways of doing so), and use
This argument becomes slightly more technically involved when we have only approximate higher- order or -orde calibration. Essentially, if we only have Wasserstein closeness between f(x) and ((x]), then we need to enlarge the set S slightly in order to account for the fact that a typical draw from (xx) is slightly far from a corresponding (coupled) draw from [[x[x For intuition, consider the binary labels setting, where f(x) and f ((xx)) both reduce to distributions on [0, 1]. Suppose that the density of fIx) is exactly that of f ([x]) but just shifted by (this is a particularly simple
of e- <-Wasserstein closeness). In this case we simply need to consider an e-neighborhood of a a set under (x) obtain 1 coverage under ((x:))-
We now formalize this idea. As in the rest of the paper, we specialize to the l Wasserstein distance. Definition F2 (Neighborhood of set). Let S S Ay be subset of the simplex, regarded as probability vectors in R Then for any ō > 0, the d-neighborhood of S is all vectors with L1- distance at most from S:
AY 3p E S 1S:1ppp1111 S
Theorem E3 (Higher-order prediction sets from higher-order calibration). Let f : X - AAY be e-higher-order calibrated wrt a partition [-]. Fix any x E and let π = f(x), x = f ([x)). Then for any set S C AY and any ō > O. we have
P pp E S] SPP'' p-s
<
E
Sa)
P Ip S2d +
(F2)
pm
pat
In particular, S contains 1 a of the mass under fxx), then Ss is a prediction set for f f'x(x) with coverage at least 1 - 5.
Proof. Since f is c-higher-order calibrated, we know that (I S 6. Let be the correspond- ing optimal coupling of p, p", with marginals being n, n² respectively, and guaranteeing that
E
|llp
p' lhl c.
(D.P")~"
Letting 7 p- p" under this coupling, we see that [ [1] < e. By Markov's inequality, we have P[][n]] > 8] < e/8.
It is worth noting that this type of coverage guarantee can only be directly evaluated when we have access to the true f (a) values, or at least approximately as k-snapshots. Of course, even when we do not, the guarantee still holds mathematically.
37

---

Published as a conference paper at ICLR 2025
We now prove the left-hand inequality. We have
P(p E S] = Pppp" +n E
= (p' + E 5) A (lbl)) S 50]] P(p'" + t (1l/ > 6)]
PPp' S
Here the second term is bounded by Markov's inequality, and the first term bounded because the event (p" + E S) A (Ilmll 6) is subset of the event p' S + 6. Rearranging gives the left-hand inequality.
The right-hand inequality is very similar:
Pip" E Sal
P(p
So] [p 1 Sa) A (llll - + n Sτ) A (I[mll > 6)]
P/p S2x) +
In practical situations, expect that the parameter the one that fixed first. In this case reasonable choice is to take = 8 = Ve in the theorem above and obtain prediction sets with coverage at least 2VE.
Note that this theorem is also applicable if we only have -hhord calibration, as we can leverage Theorem 2.4 to obtain approximate higher-order calibration from approximate 1 -oder calibration.
F.I MOMENT- BASED PREDICTION SETS FROM O-HDERRER CALIBRATION
We describe slightly different way of obtaining prediction sets directly using 1thh -order cali- bration, instead of passing through higher-order calibration and using Theorem F.3 as a black box. The idea is Theorem 2.5 approximate the moments of the Bayes mixture, and directly apply a moment-based concentration inequality to the true Bayes mixture. Throughout this subsection we specialize the binary case.
We will need to slightly adapt Theorem 2.5 to approximate the central moments E[(p Epp) }
of the Bayes mixture opposed to the moments about In fact, for the purposes generating prediction sets it will be more convenient to directly bound the moments around our estimate of the mean.
Corollary F.4. Lety= 10, and let g x g A)(()) be -rder calibrated with respect partition [.]. Fix any x E X. Let (m....., mz) E Ryo be a vector of moment estimates obtained from Theorem 2.5 such that for each E [kc]
E (r())) S ie/2.
Then we can obtain 1tth central moment estimate es such that
Ck IE (() - < ke(1 + m1)² / m-(a] -=11a
Proof. For brevity, let p ~ ([x]) denote random draw from the Bayes mixture, Observe that
E E mn)
E Epp'mm
Our estimate eù naturally formed by replacing each E[p')] term by m, (taking mg 1):
k
Σ
Ck =
m,m
m.
1=0
38

---

Published as a conference paper at ICLR 2025
The error in this estimate can be bounded as follows:
1
ck Bi(p m1 m1))]
Σ
m.
- -E[pp']
mi
k
k
ic
mi
i
2
0=
ke
m
2
1=0
Ke
(1 + m1)
2
We can obtain prediction sets using simple moment-based concentration inequality.
Theorem F.S. Let y {0.1) 1). and let X' + Ay(k) be e-kth calibrated with respect to a
partition [.] Fix any X. Let c, be given. Let (m1,.-.. ,mk) and ct be as in the previous lemma (Corollary F.4). Let é' = ke(1 + m1) /2. Suppose that > is chosen such that
Ck + 1/k
8
Then the interval [m1 - 6, mn + is prediction set for ((x]) with coverage at least 1 a.
Proof. Again for brevity let p ~ ([x)) denote a random draw from the Bayes mixture. Let =' 1 (1 + m Assume for simplicity h is even (otherwise take k: 1). By Markov's 's inequality and the previous lemma, have
[ mn }1
P mil N 8)
8
+ e'
8k
a,
by our choice of
For context, it helpful consider the ideal case when and have values for all the moments up to degree k. In this case Cj is exactly [[ [[[p))]] and 8 can be set to
E
a 1/k
which is the best one can hope for using only moment based concentration.
G ADDITIONAL EXPERIMENTS
G.1 EXPERIMENTAL DETAILS
We configure our wide ResNets on CIFAR-I0 using the "Naive NN formula from Ta- ble 2 of Johnson al. (2024) and the Python implementation of the network from the package 18 (Nado et al., 2021). We use a learning rate of 3.799c-3 and relatively large weight decay of 3.656e-1. We train the model for 50 epochs with the AdamW optimizer (Kingma & Ba, 2014; Loshchilov & Hutter, 2017). For the first epoch, we warm up the learning rate and apply cosine decay thereafter. All models are trained using Aug- Mix data augmentation (Hendrycks et al., 2020) with the standard hyperparameters used in the uncertainty baselines package.
To calibrate the model for each value of k, we create k-snapshots by sampling & labels at random once for each image the calibration set. We do not sample multiple snapshots per image.
39

---

Published as a conference paper at ICLR 2025
METHOD
ALEATORIC ERROR
AcC
ENSEMBLE
0.308 0.018
0.932 + 0.004
EPINET
0.307 0.006
0.900 0.008
1SNNAPSHOT MODEL
0.501 0.006
0.912 4 0.004
2-SNAPSHOT MODEL.
0.307 0.010
0.912 + 0.004
5 3-SNAPSHOT MODEL
0.158 0.010
0.912 + 0.006
10 -O-SNPPSHTT MODEL
0.088 = 0.010
0.912 + 0.004
-DASSNAS MODEL
0.026 0.006
0.912 + 0.004
Table 1: Expected pointwise aleatoric error (Eq. 4.1) of various methods for uncertainty estimation. 95% confidence intervals are computed across 50 random resamplings of the test and calibration sets, where applicable.
G.2 EVALUATING OTHER UNCERTAINTY ESTIMATION METHODS IN TERMS OF HIGHER-ORDER CALIBRATION
While the snapshot algorithms we present in Section 2.2 provably tend towards higher-order cali- bration, they are not requirement for higher-order calibration. can in principle be achieved by any mixture model or higher-order predictor, even one trained without explicit access to snapshots at all. In this section, we measure how well-calibrated other methods for uncertainty estimation are on the CIFAR-10 image classification task.
In addition to higher-order calibrated snapshot models from our work, we evaluate the following methods:
Naive decomposition: As a sanity check, we train a 1-snapshot predictor and treat it as a naive mixture model (i.e., one that places all of its probability mass on the lone distribution output by the predictor).
Ensemble: One simple way to obtain mixture model is train N independent 1-snapshot predic- tors (let's call them fi....,JJ' JN
X' - A)) and output the uniform mixture over their predicted label distributions: g(x) (Ji (zr),-.., -.. JN Concretely, we the same network architecture calibrated in Section and, as in Johnson et al. (2024), we use N = 8.
Epinet: A popular method for uncertainty estimation is the Epinet (Osband al., 2023). In addition to regular inputs. Epinets are conditioned on an additional random vector z. By integrating over possible values of z, is possible elicit joint predictions from the network (or, in the terminology of this paper, snapshot distributions). Epinets are usually instantiated with pair of MLPs affixed to the end of a network, trained tandem with or after the main trunk. One MLP frozen at initialization; the other is not. Both are conditioned on z and the penultimate hidden state of the main network. Loosely speaking, the Epinet learns to mitigate noise introduced by the frozen MI.P with the trainable one, and it learns to do this best in regions of the input space encountered most often during training (that is to say, regions of the input space where there is least epistemic uncertainty).
We attach such MLPs to a regular 1-snapshot CIFAR-10 10 model and train both in tandem for about 20 additional epochs, using the default hyperparameters in the enn Python library 19 (Osband et al., 2023) (notably, 50-dimensional hidden layers, 20-dimensional index vectors, and 5 iidex vectors per training input) and stopping early based on loss on our validation set. Index vectors are sampled from (0, Ia), where d = 20 is the dimension of the index vectors, and then normalized. At evaluation time, we use 50 index vectors per input and treat the resulting cloud of predictions as the predicted mixture at that point. If fxx 2) is our finished epinet, then our final model is g(x) Un 21), f(, 250)) for some 2 ....... #50 ~ NN, La).
Results are given in Table We see that calibration with large snapshots is simple and effective path to strong higher-order calibration.
G.3 COMPARING OUR HIGHER-ORDER CALIBRATION ALGORITHS
In this section we compare our two algorithms for achieving higher-order calibration (namely learn- ing directly from snapshots and post-hoc calibration; see Section 2.2) on the FER+ (Barsoum et al.,
40

---

Published as a conference paper at ICLR 2025
METHOD
NO. SNAPSHOTS
ALEATORIC ERROR
ACC
LEARNING FROM SNAPSHOTS
1
0.615
0.802
POST-HOC
0.615
0.802
LEARNING FROM SNAPSHOTS
2
0.418
0.818
POST-HOC
2
0.349
0.802
LEARNING FROM SNAPSHOTS
0.369
0.823
POST-HOC
3
0.217
0,802
LEARNING FROM SNAPSHOTS
0.355
0.819
POST-HOC
4
0.139
0.802
POST-HOC
10
0.041
0.802
Table Expected pointwise aleatoric error (Eq. 4.1) of higher-order calibration algorithms (see Section 2.2 for details) evaluated on FER+.
2016) dataset. We use this rather than CIFAR- 10H for fairer comparison since the learning from snapshots algorithm requires more multi-label data be effective, and FER+ is larger dataset than CIFAR-1OH (36,000 10,000).
FER+ is a facial recognition dataset of approx. 36,000 48 x 48 grayscale images with possible classes (emotions such happy, neutral, sad, etc.), and with 10 independent human label annota- tions per image. Thus y is the space of 10 possible emotions, and for each image x E X. J (a:) is the uniform distribution over its 10 independent annotations. There is substantial disagreement among distribution over )) have a mean entropy of 0.6 natural units (STD 0.5). In this paper's terminology, this means that the mean aleatoric uncertainty E[AU; h [x]] = [f (x)) = 0.6, where H the Shannon entropy. Note that for training and further 80/10/10 train/val/test split of the dataset. For the post-hoc calibration algorithm, the calibration set is composed of half of the test set.
annotators; the annotations (when converted
evaluation
Results are given in Table At least at this model scale, it appears that the post-hoc algorithm achieves strictly better calibration on FER+ for a given number of snapshots than learning from snapshots directly. While the latter has shown promise Johnson al. (2024) and achieves non- trivial calibration, it has disadvantages compared to the former: unlike the post-hoc calibration scheme, it requires modifying the parameters of the predictor and also training an output layer of size that grows exponentially with the number of snapshots. However, note that this is not a perfect apples-to-aplle comparison as the partitions induced by the two methods are not necessarily the same.
G.4 BINARY REGRESSION
As sanity check, we verify that it is possible to create higher-order calibrated models on the syn- thetic ID binary regression task from Johnson al. (2024), which fixes specific distribution of coins p(x) and a bias distribution p(y (r) with both high- and lowfrreueecy variation. Specifically, we train the neural network defined in their Algorithm 2 to predict 1-snapshots from training set sampled from the synthetic distribution. We then sample separate calibration set of 5000 snap- shots, apply the algorithm from Section 2.2 the predictor, and finally measure e (as specified in Definition 2.3) on a third test set.
We find that, indeed, a predictor calibrated in this fashion achieves calibration error e lower than naive predictors that output uniform distributions over snapshots or the snapshot distribution that results from fair coins. 1-snapshot predictor pretrained for 10,000 batches and calibrated with 5,000 10-snapshots reaches to the maximum value of 1. we relax the condition in Definition 2.3 somewhat and exclude the noisiest 5% of the equivalence classes, the 95% percentile of error, the same model reaches 0.212 + 0.089. All 95% confidence intervals are taken over 50 resamplings of the calibration and test sets.
0.400 = 0.23: both naive baselines achieve 0.959 + 0.014, close
For a more easily interpretable measure of higher-order calibration, we also compute the mean aleatoric estimation error, as defined in Equation 4.1. See Figure 6 for results. As previously, increasing the size of the snapshots used for calibration does indeed improve estimates of aleatoric uncertainty.
41

---

Published as a conference paper at ICLR 2025
1.0
Ground truth Predicted
0.8
0.5
0.4
0.3
0.2
0.2
0.1
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5 2.0
2.5
3.0
Figure 5: The simple binary regression task from Johnson al. (2024). (Positive) inputs are drawn from normal distribution (left), and outputs determined by fixed function p(y()) (right) with low- and high- frequency components, the latter which our simple predictor 1) fails learn completely.
Snapshot
0.1
04
80
Entrrpy companents
0.2
9.2
07
1.3
04
05
Figure 6: Top: Average alcatoric uncertainty estimation error (Eq. (4.1)) of binary regression models calibrated using snapshots of increasing size. Bottom: For three the highest-entropy equivalence classes, we depict the distribution of entropies ranging over components of the predicted mixture (gray) and the Bayes mixture (green). We see that the distributions and in particular the means are similar.
42


Reviews:
[{"review_id": "Tx6c0XW1CA", "reviewer": "Reviewer_1pi3", "summary": "The authors present a new way of decomposing aleatoric and epistemic uncertainties based on second-order distributions. They claim they are the first one to provide estimates enjoying some calibration properties that they specify, and show empirically their findings.", "questions": "In Definition 1.1, you write $f^*([x]):=\\lbrace{f^*(\\mathbf{x}) | \\mathbf{x} \\sim [x] }\\rbrace$. Why is $\\mathbf{x}$ suddenly in boldface? Is it just to separate notationally the equivalence class $[x]$ from a possible element $\\mathbf{x}$ of such a class? In addition, what does $\\mathbf{x} \\sim [x]$ mean? From what you write before $[x]$ is just an equivalence class. In turn, the squiggle cannot mean \"$\\mathbf{x}$ is distributed according to $[x]$\". Do you mean that $\\mathbf{x}$ is a generic element of the equivalence class $[x]$? This becomes even more puzzling in Theorems 1.2 and 2.7, and Lemma 3.2, where expectations are taken w.r.t. $\\mathbf{x} \\sim [x]$.\n\nLines 145-146: \"Then we cannot distinguish scenario 1 from scenario 2 if all we receive are ordinary labeled examples with a single label per image\". It seems that you rediscovered the classical Fisher-Laplace paradox (see e.g. Appendix A.(i) in [1]).\n\nThe author(s) seem to be unaware of an extensive literature that studies the pitfalls of second-order distributions in quantifying and disentangling between AU and EU (see e.g. the last paragraph of [1, Section 5]). In light of this, does their method solve such shortcomings? If so, how? If not, or if only partially, it should be (i) discussed why it is still of interest to take a higher-order route, as the authors do, and (ii) compare the author's method $-$or at least introduce a discussion$-$ with others that do not suffer from these problems, such as credal-set-based uncertainty quantification (see works by Hüllermeier, Sale, Caprio, Desterke to name a few).\n\nHow does the author's notion of calibration relates to type-2 validity [2] and credal set calibration of e.g. [3]?\n\nWhy in line 270 the authors write $g:\\mathcal{X} \\rightarrow \\Delta \\mathcal{Y}^{(k)}$? That is, why is $k$ in parentheses?\n\nThe conceptual simplification in line 273 is not immediately clear to me. Predictor $g:\\mathcal{X} \\rightarrow \\Delta\\mathcal{Y}^k$ outputs a collection of $k$ probabilities over the labels in $\\mathcal{Y}$. Does your interpretation $\\Delta\\mathcal{Y}^k \\subseteq \\Delta\\Delta\\mathcal{Y}$ mean that we can see $g$ as outputting an empirical second-order distribution that gives probability $q/k$ to the elements of $\\Delta\\mathcal{Y}$, where $q$ is the number of times a specific distribution over the outputs was returned by the predictor $g$? In other words, suppose $\\mathcal{Y}=\\lbrace{1,2,3}\\rbrace$, and that $k=3$. Suppose also that $g(x)=((0.9,0.05,0.05), (0.9,0.05,0.05), (0.8,0.1,0.1))$. Then, this can be seen as an empirical second-order distribution giving probability $2/3$ to $(0.9,0.05,0.05)$, probability $1/3$ to $(0.8,0.1,0.1)$, and probability $0$ to all other elements of $\\Delta\\mathcal{Y}$. Is this what the authors mean?\n\nThe 1-Wasserstein metric is well-defined on $\\Delta\\Delta\\mathcal{Y}$ only when $\\mathcal{Y}$ is discrete. This should be mentioned.\n\nCareful in using $G$ as any concave generalized entropy function, since in the literature it usually refers to the generalized Hartley measure (see e.g. eq (27) in [4]).\n\nWhy is there not a Conclusion?\n\n---\n\n[1] https://openreview.net/forum?id=4NHF9AC5ui\n\n[2] https://www.sciencedirect.com/science/article/pii/S0888613X21001195\n\n[3] https://arxiv.org/abs/2410.12921\n\n[4] https://link.springer.com/article/10.1007/s10994-021-05946-3", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The approach is innovative, and the authors look at calibration of second-order distribution, which is still a shallow-studied subfield. The exposition is mostly clear, and the results they derive are mathematically sound.", "weaknesses": "See Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2X7Qg70USw", "reviewer": "Reviewer_HdGS", "summary": "In this paper, the authors propose a generalization of classical (first-order) calibration by introducing notions of higher-order and $k$-th order calibration. They formulate and prove theoretical guarantees that a higher-order calibrated predictor provides accurate estimates of aleatoric uncertainty (AU), and they show similar results for $k$-th order calibrated predictors. The authors demonstrate that their theoretical results hold in experiments for image classification.", "questions": "1. In lines 196-197, the authors state: \"For any given instance we now have not just a single predicted distribution over outcomes, but rather a full 'posterior predictive distribution' over such distributions. In this way every Bayesian model is a higher-order predictor.\" I want to clarify why the posterior predictive distribution is considered a higher-order predictor. Isn't it an averaged prediction (over the posterior of the weights), hence first order? A sample from the posterior predictive distribution is a label, not a categorical vector?\n\n2. In line 318, the authors propose two methods to achieve $k$-th order calibration: \"minimizing a proper loss, or post-processing the level sets of a learned predictor.\" However, it seems that in the experimental section only one strategy (the post-hoc calibration algorithm) is used. Did the authors employ the first strategy? How do these two strategies perform compared to each other?\n\n3. In line 433, the authors mention: \"our epistemic uncertainty is precisely the true “variance” in $f^*(x)$ as $x \\sim [x].$.\" I understand this informal claim, but how can we see that epistemic uncertainty indeed corresponds to the variance of the Bayesian mixture?\n\n4. In the experimental section, the examples of \"mostly epistemic\" images still resemble in-distribution samples, similar to \"soft-OOD\" scenarios (e.g., in [1]). I think that higher-order calibration helps identify these objects. However, in practice, it is common to use estimates of EU to detect \"hard-OOD\" samples, where images do not resemble in-distribution ones (e.g., training images from CIFAR-10 and testing on ImageNet samples). In this case, will higher-order calibration improve out-of-distribution detection?\n\n5. In lines 378-379, the authors state: \"Let any concave generalized entropy function $G$ be given...\" In prior works (Kotelevskii & Panov (2024) and Hofman et al. (2024)), several choices of generalized entropy are considered, including Shannon entropy and Brier score, but also the Zero-one score. The Zero-one score leads to a convex (but not strictly convex) generalized entropy. Will the necessary and sufficient conditions of being higher-order calibrated to produce calibrated estimates of AU still hold in this case?\n\n[1] Kotelevskii, N., & Panov, M. (2024). Predictive Uncertainty Quantification via Risk Decompositions for Strictly Proper Scoring Rules. arXiv preprint arXiv:2402.10727.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The main strengths of the paper are its theoretical contributions. \n\nSpecifically, it generalizes the notion of calibration by extending it to \"higher-order\" calibration. The authors show that a higher-order calibrated predictor provides correct estimates of the true AU. Moreover, they show that being higher-order calibrated is the necessary and sufficient condition for producing accurate estimates of AU, which I believe is an important theoretical result. \n\nSince in practice we can only have finitely calibrated predictors (i.e., $k$-th order calibrated predictors), the authors additionally prove results on the accuracy of AU estimates for small $k$ for different instantiations of generalized entropies.\n\nAlso, compared to the prior work of Johnson et al. (2024), one does not need to change the output layer of the model, but can use the model's architecture as it is.", "weaknesses": "I see several weaknesses in the paper, which I list below. Additionally, there are aspects I did not fully understand (which may not necessarily be weaknesses), and I will list them in the Questions section.\n\n### Structure and Text:\n\nI find the structure of the paper somewhat confusing and believe it could be improved. Specifically:\n\n- Figure 1 on page 2 is never referenced in the text. The authors might consider referencing it in the paragraph on lines 37-43, where they essentially describe it in words.\n\n- In lines 101-102, there is a section(?) titled \"Summary of main results,\" which is almost two pages long and is not actually a summary. Rather, it introduces relevant definitions / some theorems, and is too lengthy for a summary. I would suggest that the main results are presented in Sections 2 and 3, not in this section. \nThe authors might consider renaming this section to something like \"Background\" or \"Preliminaries.\"\n\n- The paper is missing a Conclusion section. Given the substantial theoretical material presented, a conclusion would help readers to get the key takeaways. For example, the authors could outline the proved results for the correctness of the AU estimate, discuss limitations, and suggest possible further research directions.\n\n- [Minor] Some parts of the Appendix are not referenced, e.g. the proof of Theorem 2.6 in Appendix D.4.\n\n\n### Missing Related Work:\n\nI believe the paper is missing references to prior work:\n\n[1] Kotelevskii, N., & Panov, M. (2024). Predictive Uncertainty Quantification via Risk Decompositions for Strictly Proper Scoring Rules. arXiv preprint arXiv:2402.10727.\n\n[2] Durasov, N., Dorndorf, N., Le, H., & Fua, P. (2022). Zigzag: Universal sampling-free uncertainty estimation through two-step inference. arXiv preprint arXiv:2211.11435.\n\nThe first reference is cited in Hofman et al. (2024) and also provides a way to decompose predictive uncertainties via proper scoring rules (which is one of the key things in the submitted paper).\n\nThe second is cited in Johnson et al. (2024) and appears to be the first work in the context of predicting pairs of labels.\n\n\n### Baseline in experiments:\n\nThe current work, as mentioned by the authors, is inspired by the initial results in Johnson et al. (2024). In their approach, they propose a Cheat NN that aims to be second-order calibrated. Using their Cheat NN requires modifying the output layer to output an $l \\times l$ matrix (where $l$ is the number of classes), which could be a limitation when $l$ is large. Nonetheless, it represents a third method [in addition to two proposed in line 318] to achieve higher (k-th) order calibration. It would be interesting to see how the proposed strategies compare to the one in Johnson et al. (2024). Including the Cheat NN as a baseline in the experiments would strengthen the paper by providing a direct comparison to existing methods. \n\n\n----\n\nOverall, I am positive about the theoretical contribution of the paper, and I am willing to significantly increase my evaluation score, given answered questions and incorporated changes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g4xdYQzOv5", "reviewer": "Reviewer_y8E9", "summary": "The authors explore the implications of higher-order calibration on decomposing the uncertainty of a predictor into aleatoric and epistemic components. In this regard they propose to approximately achieve higher-order calibration through calibrating over a finite k number of snapshots and show the convergence as k goes to infinity. This work extends the second-order calibration using pairs of labels to arbitrarily higher orders with k-snapshots. Authors validate the theoretical claims through experiments.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Presents important and interesting theoretical formalization on higher-order calibration and convergence of approximate k-order calibration to approximate higher-order calibration, preserving the mathematical rigor.\n2. The approximate k-snapshot calibration is certainly important in applying the theory in practice.\n2. The paper is well written with a comprehensive study on related works which can be very useful for a novice reader.\n3. The experiments are well motivated and demonstrate the theoretical claims made in the paper.", "weaknesses": "1. In the experiments, it is useful to mention how the estimation of these quantities of interest were done, for example the how the entropy values were computed empirically in order to get an idea on how the estimation errors of those might affect the overall uncertainty estimation.\n2. The running example can be discussed in detail in the main text or in the appendix as an aid for understanding the notation and the definitions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2sUqV7FwLq", "reviewer": "Reviewer_aa9Z", "summary": "This work provides a methodology for decomposing predictive uncertainty through calibration on the conditional distribution of the label, using ``higher-order calibration\" enabled by multiple samples from conditional distributions.", "questions": "1. Could the authors provide some background or explanation on the importance of decomposing predictive uncertainty? Specifically, how do the results of this work guide practitioners in improving prediction or predictive inference, given some data and a trained model in practice? Is the primary aim to enhance understanding of the behavior of a given model or prediction method, rather than to directly improve things?\n\n2. I was wondering if there might be any connection between this work and ``Distribution-free Inference with Hierarchical Data\" by Lee and Barber. Specifically, their work considers a similar setting with multiple label samples for each feature observation, focusing on a form of conditional predictive inference. They propose a methodology for constructing a prediction set that achieves a `second-moment coverage guarantee' and note that a 'k-th moment coverage guarantee' can be achieved similarly when the number of repeated samples exceeds k across many groups. Although the inferential targets differ in form between the two works, I feel that there may be a connection in that both works measure conditional uncertainty through higher-order moments using multiple label observations. Could the authors perhaps share their thoughts on this?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work addresses an important problem within the area of conditional predictive inference, to my understanding, and includes rigorous theoretical analysis.", "weaknesses": "I believe it would be beneficial to improve the clarity regarding the problem setting and objective in a more formal manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)