Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration
Year: 2022

Abstract:
When facing uncertainty, decision-makers want predictions they can trust. A machine learning provider can convey confidence to decision-makers by guaranteeing their predictions are distribution calibrated — amongst the inputs that receive a predicted class probabilities vector q, the actual distribution over classes is q. For multi-class prediction problems, however, achieving distribution calibration tends to be infeasible, requiring sample complexity exponential in the number of classes C. In this work, we introduce a new notion—decision calibration—that requires the predicted distribution and true distribution to be “indistinguishable” to a set of downstream decision-makers. When all possible decision makers are under consideration, decision calibration is the same as distribution calibration. However, when we only consider decision makers choosing between a bounded number of actions (e.g. polynomial in C), our main result shows that decisions calibration becomes feasible — we design a recalibration algorithm that requires sample complexity polynomial in the number of actions and the number of classes. We validate our recalibration algorithm empirically: compared to existing methods, decision calibration improves decision-making on skin lesion and ImageNet classification with modern neural network predictors.

heading: 1 Introduction
text: Machine learning predictions are increasingly employed by downstream decision makers who have little or no visibility on how the models were designed and trained. In high-stakes settings, such as healthcare applications, decision makers want predictions they can trust. For example in healthcare, suppose a machine learning service offers a supervised learning model to healthcare providers that claims to predict the probability of various skin diseases, given an image of a lesion. Each healthcare provider want assurance that the model’s predictions lead to beneficial decisions, according to their own loss functions. As a result, the healthcare providers may reasonably worry that the model was trained using a loss function different than their own. This mismatch is often inevitable because the ML service may provide the same prediction model to many healthcare providers, which may have different treatment options available and loss functions. Even the same healthcare provider could have different loss functions throughout time, due to changes in treatment availability.
If predicted probabilities perfectly equal the true probability of the event, this issue of trust would not arise because they would lead to optimal decision making regardless of the loss function or task considered by downstream decision makers. In practice, however, predicted probabilities are never perfect. To address this, the healthcare providers may insist that the prediction function be
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
distribution calibrated, requiring that amongst the inputs that receive predicted class probability vectors q, the actual distribution over classes is q. This solves the trust issue because among the patients who receive prediction q, the healthcare providers knows that the true label distribution is q, and hence knows the true expected loss of a treatment on these patients. Unfortunately, to achieve distribution calibration, we need to reason about the set of individuals x who receive prediction q, for every possible predicted q. As the number of distinct predictions may naturally grow exponentially in the number of classes C, the amount of data needed to accurately certify distribution calibration tends to be prohibitive. Due to this statistical barrier, most work on calibrated multi-class predictions focuses on obtaining relaxed variants of calibration. These include confidence calibration (Guo et al., 2017), which calibrates predictions only over the most likely class, and classwise calibration (Kull et al., 2019), which calibrates predictions for each class marginally. While feasible, these notions are significantly weaker than distribution calibration and do not address the trust issue highlighted above. Is there a calibration notion that addresses the issue of trust, but can also be verified and achieved efficiently? Our paper answers this question affirmatively.
Our Contributions. We introduce a new notion of calibration—decision calibration—where we take the perspective of potential decision-makers: the only differences in predictions that matter are those that could lead to different decisions. Inspired by Dwork et al. (2021), we formalize this intuition by requiring that predictions are “indistinguishable” from the true outcomes, according to a collection of decision-makers.
First, we show that prior notions of calibration can be characterized as special cases of decision calibration under different collections of decision-makers. This framing explains the strengths and weakness of existing notions of calibration, and clarifies the guarantees they offer to decision makers. For example, we show that a predictor is distribution calibrated if and only if it is decision calibrated with respect to all loss functions and decision rules. This characterization demonstrates why distribution calibration is so challenging: achieving distribution calibration requires simultaneously reasoning about all possible decision tasks.
The set of all decision rules include those that choose between exponentially (in number of classes C) many actions. In practice, however, decision-makers typically choose from a bounded (or slowlygrowing as a function of C) set of actions. Our main contribution is an algorithm that guarantees decision calibration for such more realistic decision-makers. In particular, we give a sample-efficient algorithm that takes a pre-trained predictor and post-processes it to achieve decision calibration with respect to all decision-makers choosing from a bounded set of actions. Our recalibration procedure does not harm other common performance metrics, and actually improves accuracy and likelihood of the predictions. In fact, we argue formally that, in the setting of bounded actions, optimizing for decision calibration recovers many of the benefits of distribution calibration, while drastically improving the sample complexity. Empirically, we use our algorithm to recalibrate deep network predictors on two large scale datasets: skin lesion classification (HAM10000) and Imagenet. Our recalibration algorithm improves decision making, and allow for more accurate decision loss estimation compared to existing recalibration methods even under distribution shift.

heading: 2 Background

heading: 2.1 Setup and Notation
text: We consider the prediction problem with random variables X and Y , where X ∈ X denotes the input features, and Y ∈ Y denotes the label. We focus on classification where Y = {(1, 0, · · · , 0), (0, 1, · · · , 0), · · · , (0, 0, · · · , 1)} where each y ∈ Y is a one-hot vector with C ∈ N classes. 1 A probability prediction function is a map p̂ : X → ∆C where ∆C is the C-dimensional simplex. We define the support of p̂ as the set of distributions it could predict, i.e. {p̂(x)|x ∈ X}. We use p∗ : X → ∆C to denote the true conditional probability vector, i.e. p∗(x) = E[Y | X = x] ∈ ∆C , and for all c ∈ [C], each coordinate gives the probability of the class p∗(x)c = Pr[Yc | X = x].
1We can also equivalently define Y = {1, 2, · · · , C}, here we denote y by a one-hot vector for notation convenience when taking expectations.

heading: 2.2 Decision-Making Tasks and Loss Functions
text: We formalize a decision-making task as a loss minimization problem. The decision-maker has some set of available actions A and a loss function ` : Y × A → R. In this paper we assume the loss function does not directly depend on the input features X . For notational simplicity we often refer to a (action set, loss function) pair (A, `) only by the loss function `: the set of actions A is implicitly defined by the domain of `. We denote the set of all possible loss functions as Lall = {`|∀ set A and function ` : Y ×A → R}. We treat all action sets A with the same cardinality as the same set — they are equivalent up to renaming the actions. A convenient way to think about this is that we only consider actions sets A ∈ {[1], [2], · · · , [K], · · · ,N,R} where [K] = {1, · · · ,K}.

heading: 2.3 Bayes Decision-Making
text: Given some predicted probability p̂(X) on Y , a decision-maker selects an action inA. We assume that the decision-maker selects the action based on the predicted probability. That is, we define a decision function as any map from the predicted probability to an action δ : ∆C → A. and denote by all as the set of all decision functions with any set of actions all = {δ | ∀ set A and function δ : ∆C → A}. Typically a decision-maker selects the action that minimizes the expected loss (under the predicted probability). This strategy is formalized by the following definition of Bayes decision-making. Definition 1 (Bayes Decision). Choose any ` ∈ Lall with corresponding action set A and prediction p̂, define the Bayes decision function as δ`(p̂(x)) = arg infa∈A EŶ∼p̂(x)[`(Ŷ , a)]. For any subset L ⊂ Lall denote the set of all Bayes decision functions as L := {δ` | ∀` ∈ L}.

heading: 3 Calibration: A Decision-Making Perspective
text: In our setup, the decision-maker outsources the prediction task to a third-party forecaster, which returns a prediction function p̂ (e.g., an ML Prediction API). The decision maker will use p̂ and a loss function ` to make decisions. However, the forecaster does not necessarily know the loss function ` in advance, and in more challenging cases, needs to serve multiple decision-makers with different loss functions. For example, the prediction function may be trained to optimize a standard objective such as L2 error or log likelihood, then sold to decision-makers as an off-the-shelf solution.
In such a setting, the decision makers may be concerned that the off-the-shelf solution may not perform well according to their loss function. If the forecaster could predict optimally (i.e. p̂(X) = p∗(X) almost surely), then there would be no issue of trust; of course, perfect predictions are usually impossible, so the forecaster needs feasible ways of conveying trust to the decision makers. To mitigate concerns about the performance of the prediction function, the forecaster might aim to offer performance guarantees applicable to decision makers whose loss functions come from class of losses L ⊂ Lall.

heading: 3.1 Decision Calibration
text: First and foremost, a decision maker wants assurance that the Bayes decision rule δ` with p̂ gives low expected loss. Second, the decision maker wants to know how much loss is going to be incurred (before the actions are deployed and outcomes are revealed); the decision maker does not want to incur any additional loss in surprise that she has not prepared for.
To capture these desiderata we formalize a definition based on the following intuition: suppose a decision maker with some loss function ` considers a decision rule δ ∈ all (that may or may not be the Bayes decision rule), the decision maker should be able to correctly compute the expected loss of using δ to make decisions, as a function of the predictions p̂. Definition 2 (Decision Calibration). For a set of loss functions L ⊂ Lall and a set of decision rules ⊂ all, we say that a prediction p̂ is (L; )-decision calibrated (with respect to p∗) if ∀` ∈ L and δ ∈ with the same action space A 2, the computed loss (based on p̂) of δ is the same as the actual
2We require ` and δ to have the same action space A for type check reasons. Eq.(2) only has meaning if the loss ` and decision rule δ are associated with the same action space A.
loss, i.e.
EXEŶ∼p̂(X)[`(Ŷ , δ(p̂(X)))] = EXEY∼p∗(X)[`(Y, δ(p̂(X)))] (1)
In particular, we say p̂ is L-decision calibrated if it is (L; L)-decision calibrated, where L is the set of all Bayes decision rules for loss functions in L.
The left hand side of Eq.(2) is the “simulated” loss where the outcome Ŷ is hypothetically drawn from the predicted distribution. The decision maker can compute this just by knowing the input features X and without knowing the outcome Y . The right hand side of Eq.(2) is the true loss that the decision maker incurs in reality if she uses the decision rule δ. Intuitively, the definition captures the idea that the losses in L and decision rules in do not distinguish between outcomes sampled according to the predicted probability and the true probability; specifically, the definition can be viewed as an instantiation of the framework of Outcome Indistinguishability (Dwork et al., 2021).
As a cautionary remark, Eq.(2) should not be mis-interpreted as guarantees about individual decisions; Eq.(2) only looks at the average loss when X,Y is a random draw from the population. Individual guarantees are usually impossible without tools beyond machine learning (Zhao & Ermon, 2021). In addition, Definition 2 does not consider decision rules that can directly depend on X , as δ ∈ all only depends on X via the predicted probability p̂(X). Studying decision rules that can directly depend on X require tools such as multicalibration (Hébert-Johnson et al., 2018) which are beyond the scope of this paper (see related work).
In Definition 2 we also define the special notion of L-decision calibrated because given a set of loss functions L, we are often only interested in the associated Bayes decision rules L, i.e. the set of decision rules that are optimal under some loss function. For the rest of the paper we focus on L-decision calibration for simplicity. L-decision calibration can capture the desiderata we discussed above formalized in the following proposition. Proposition 1. If a prediction function p̂ is L-decision calibrated, then it satisfies ∀δ′ ∈ L EXEY∼p∗(X)[`(Y, δ`(p̂(X)))] ≤ EXEY∼p∗(X)[`(Y, δ′(p̂(X)))] (Bayes Decision Optimality) EXEŶ∼p̂(X)[`(Ŷ , δ`(p̂(X)))] = EXEY∼p∗(X)[`(Y, δ`(p̂(X)))] (Accurate loss estimation)
Bayes Decision Optimality states that the Bayes decision rule δ` is not worse than any alternative decision rule δ′ ∈ L. In other words, the decision maker is incentivized to take optimal actions according to their true loss function. That is, using the predictions given by p̂, the decision maker cannot improve their actions by using a decision rule δ′ that arises from a different loss function `′ ∈ L. Accurate loss estimation states that for the Bayes decision rule δ`, the simulated loss on the left hand side (which the decision maker can compute before the outcomes are revealed) equals the true loss on the right hand side. This ensures that the decision maker knows the expected loss that will be incurred over the distribution of individuals and can prepare for it. This is important because in most prediction tasks, the labels Y are revealed with a significant delay or never revealed. For example, the hospital might be unable to follow up on the true outcome of all of its patients.
In practice, the forecaster chooses some set L to achieve L-decision calibration, and advertise it to decision makers. A decision makers can then check whether their loss function ` belongs to the advertised set L. If it does, the decision maker should be confident that the Bayes decision rule δ` has low loss compared to alternatives in L, and they can know in advance the loss that will be incurred.

heading: 3.2 Decision Calibration Generalizes Existing Notions of Calibration
text: We show that by varying the choice of loss class L, decision calibration can actually express prior notions of calibration. For example, consider confidence calibration, where among the samples whose the top probability is β, the top accuracy is indeed β. Formally, confidence calibration requires that
Pr[Y = arg max p̂(X) | max p̂(X) = β] = β. We show that a prediction function p̂ is confidence calibrated if and only if it isLr-decision calibration, where Lr is defined by
Lr := {`(y, a) = I(y 6= a ∧ a 6= ⊥) + β · I(a = ⊥) | a ∈ Y ∪ {⊥},∀β ∈ [0, 1]}
Intuitively, loss functions in Lr corresponds to the refrained prediction task: a decision maker chooses between reporting a class label, or reporting “I don’t know,” denoted ⊥. She incurs a loss of 0 for correctly predicting the label y, a loss of 1 for reporting an incorrect class label, and a loss of β < 1 for reporting “I don’t know”. If a decision maker’s loss function belong to this simple class of losses Lr, he or she can use a confidence calibrated prediction function p̂, because the two desiderata (Bayes decision optimality and accurate loss estimation) in Proposition 1 are true for the decision maker. However, such “refrained prediction“ decision tasks only account for a tiny subset of all possible tasks that are interesting to decision makers. Similarly, classwise calibration can be characterized through decision calibration using a class of loss functions that penalizes class-specific false positives and negatives.
In this way, decision calibration clarifies the implications of existing notions of calibration on decision making: relaxed notions of calibration correspond to decision calibration over restricted classes of losses. In general, decision calibration provides a unified view of most existing notions of calibration as the following theorem shows.
Theorem 1. [Decision Calibration Generalizes Existing Notions] For any true distribution p∗, and for the loss function sets Lr,Lcr defined in Table 1, a prediction function p̂ is
• confidence calibrated iff it is Lr-decision calibrated.
• classwise calibrated iff it is Lcr-decision calibrated.
• distribution calibrated iff it is Lall-decision calibrated.
For proof of this theorem see Appendix C. In Table 1, confidence and classwise calibration are weak notions of calibration; correspondingly the loss function families Lr and Lcr are also very restricted. On the other hand, distribution calibration (i.e. E[Y | p̂(X) = q] = q,∀q ∈ ∆C) is equivalent to Lall-decision calibration. This means that a distribution calibrated predictor guarantees the Bayes decision optimality and accurate loss estimation properties as in Proposition 1 to a decision maker holding any loss functions. Unfortunately, distribution calibration is very challenging to verify or achieve. To understand the challenges, consider certifying whether a given predictor p̂ is distribution calibrated. Because we need to reason about the conditional distribution E[Y | p̂(X) = q] for every q that p̂ can predict (i.e. the support of p̂), the necessary sample complexity grows linearly in the support of p̂. Of course, for a trivial predictors that map all inputs x to the same prediction q0 (i.e. p̂(x) = q0,∀x ∈ X ) distribution calibration is easy to certify (Widmann et al., 2019), but such predictors have no practical use.
Our characterization of distribution calibration further sheds light on why it is so difficult to achieve. Lall consists of all loss function, including all loss functions ` : Y × A → R whose action space A contains exponentially many elements (e.g. |A| = 2C). The corresponding decision rules δ ∈ Lall : ∆C → A may also map ∆C to exponentially many possible values. Enforcing Definition 2 for such complex loss functions and decision rules is naturally difficult.

heading: 3.3 Decision Calibration over Bounded Action Space
text: In many contexts, directly optimizing for distribution calibration may be overkill. In particular, in most realistic settings, decision makers tend to have a bounded number of possible actions, so the relevant losses come from LK for reasonable K ∈ N. Thus, we consider obtaining decision calibration for all loss functions defined over a bounded number of actions K. In the remainder of the
paper, we focus on this restriction of decision calibration to the class of losses with bounded action space; we reiterate the definition of decision calibration for the special case of LK . Definition 3 (LK-Decision Calibration). Let LK be the set of all loss functions with K actions LK = {` | ∀A, |A| = K,∀` : Y × A → R}, we say that a prediction p̂ is LK-decision calibrated (with respect to p∗) if ∀` ∈ LK and δ ∈ LK
EXEŶ∼p̂(X)[`(Ŷ , δ(p̂(X)))] = EXEY∼p∗(X)[`(Y, δ(p̂(X)))] (2)
The key result (that we show in Section 4) is that LK-decision calibration can be efficiently verified and achieved for all predictors. Specifically, we show that the sample complexity necessary to learn LK -decision calibrated predictors depends on the number of actions K, not on the support of p̂. This is in contrast to the standard approach for establishing distribution calibration, where the sample complexity scales with the support of p̂ (which is typically exponentially in the number of classes).

heading: 4 Achieving Decision Calibration with PAC Guarantees

heading: 4.1 Approximate LK Decision Calibration is Verifiable and Achievable
text: Decision calibration in Definition 2 usually cannot be achieved perfectly. The definition has to be relaxed to allow for statistical and numerical errors. To meaningfully define approximate calibration we assume that the loss functions are bounded, i.e. no outcome y ∈ Y and action a ∈ A can incur an infinite loss. In particular, we bound ` by its 2-norm maxa‖`(·, a)‖2 := maxa √∑ y∈Y `(y, a) 2. 3
Now we can proceed to define approximate decision calibration. In particular, we compare the difference between the two sides in Eq.(2) of Definition 2 with the maximum magnitude of the loss function. Definition 4 (Approximate decision calibration). A prediction function p̂ is (L, )-decision calibrated (with respect to p∗) if ∀` ∈ L and δ ∈ L∣∣∣E[`(Ŷ , δ(p̂(X)))]− E[`(Y, δ(p̂(X)))]∣∣∣ ≤ sup
a∈A ‖`(·, a)‖2 (3)
Definition 4 is a relaxation of Definition 2: if a prediction function is (L, 0)-decision calibrated, then it is L-decision calibrated (Definition 2). The main observation in our paper is that for the set of loss functions withK actions, (LK , )-decision calibration can be verified and achieved with polynomially many samples. In addition, we achieve decision calibration without deteriorating the L2 error E[‖p̂(X)− Y ‖22]. Theorem 2 (Main Theorem, informal). There is an algorithm, such that for any predictor p̂ and given polynomially (in K,C, 1/ ) many samples, can with high probability
1. correctly decide if p̂ satisfies (LK , )-decision calibration
2. output a new predictor p̂′ that satisfies (LK , )-decision calibration without degrading the original predictions (in terms of L2 error).
Note that trivial predictors p̂(x) ≡ E[Y ],∀x satisfy (LK , 0)-decision calibration. To maintain a meaningful prediction function we also require “sharpness” which we measure by L2 error. We guarantee that the L2 error of p̂′ can only improve under post-processing; that is, E[‖p̂′(X)−Y ‖22] ≤ E[‖p̂(X) − Y ‖22]. In fact, the algorithm works by iteratively updating the predictions to make progress in L2. In addition to L2 error, empirically our recalibration algorithm also slightly improves the likelihood and accuracy. For rest of this section, we propose concrete algorithms that satisfy Theorem 2.

heading: 4.2 Verification of Decision Calibration
text: This section focuses on the first part of Theorem 2 where we certify (LK , )-decision calibration. A naive approach use samples to directly estimate (by replacing all expectations with empirical sample
3The choice of 2-norm is for convenience. All p-norms are equivalent up to a multiplicative factor polynomial in C, so our main theorem (Theorem 2) still hold for any p-norms up to the polynomial factor.
averages)
sup δ∈ LK sup `∈LK ∣∣∣E[`(Ŷ , δ(p̂(X)))]− E[`(Y, δ(p̂(X)))]∣∣∣ /(sup a∈A ‖`(·, a)‖2 ) (4)
and compare it with . Even though it might be possible to upper bound the estimation error for Eq.(4) directly, the analysis would be complex because of the multiple sup in the equation. To gain deeper insight into the problem and simplify its analysis, we will make several observations to transform this complex optimization problem to a simpler problem that resembles linear classification.
Observation 1. The first observation is that we do not have to take the supremum over LK because for any choice of δ ∈ by simple calculations we have
sup `∈LK ∣∣∣E[`(Ŷ , δ(p̂(X)))]− E[`(Y, δ(p̂(X)))]∣∣∣ supa∈A‖`(·, a)‖2 = K∑ a=1 ∥∥∥E[(Ŷ − Y )I(δ(p̂(X)) = a)]∥∥∥ 2
(5)
This statement is formally proved as part of the proof for Proposition 3 in Appendix C.2. Intuitively on the right hand side, δ partitions the probabilities ∆C based on the optimal decision ∆1 := {q ∈ ∆C , I(δ(q) = 1)}, · · · ,∆K := {q ∈ ∆C , I(δ(q) = K)}. For each partition ∆k we measure the difference between predicted label and true label on average, i.e. E[(Ŷ − Y )I(p̂(X) ∈ ∆k)].
Observation 2. We observe that the partitions of ∆C are defined by linear classification boundaries. Formally, we introduce a new notation for the linear multi-class classification functions
BK = { bw | ∀w ∈ RK×C } where bw(q, a) = I(a = arg sup
a′∈[K] 〈q, wa′〉) (6)
Note that this new classification task is a tool to aid in understanding decision calibration, and bears no relationship with the original prediction task (predicting Y from X). Intuitively w defines the weights of a linear classifier; given input features q ∈ ∆C and a candidate class a, bw outputs an indicator: bw(q, a) = 1 if the optimal decision of q is equal to a and 0 otherwise.
The following equality draws the connection between Eq.(5) and linear classification. The proof is simply a translation from the original notations to the new notations.
sup δ∈ LK K∑ a=1 ∥∥∥E[(Ŷ − Y )I(δ(p̂(X))) = a)]∥∥∥ 2 = sup b∈BK K∑ a=1 ∥∥∥E[(Ŷ − Y )b(p̂(X), a)]∥∥∥ 2
(7)
The final outcome of our derivations is the following proposition (Proof in Appendix C.2) Proposition 2. A predictor p̂ satisfies (LK , )-decision calibration if and only if
sup b∈BK K∑ a=1 ∥∥∥E[(Ŷ − Y )b(p̂(X), a)]∥∥∥ 2 ≤ (8)
In words, p̂ satisfies decision calibration if and only if there is no linear classification function that can partition ∆C into K parts, such that the average difference Ŷ −Y (or equivalently p̂(X)− p∗(X)) in each partition is large. Theorem 2.1 follows naturally because BK has low Radamacher complexity, so the left hand side of Eq.(8) can be accurately estimated with polynomially many samples. For a formal statement and proof see Appendix C.2.
The remaining problem is computation. With unlimited compute, we can upper bound Eq.(8) by brute force search over BK ; in practice, we use a surrogate objective optimizable with gradient descent. This is the topic of Section 4.4.

heading: 4.3 Recalibration Algorithm
text: This section discusses the second part of Theorem 2 where we design a post-processing recalibration algorithm. The algorithm is based on the following intuition, inspired by (Hébert-Johnson et al., 2018): given a predictor p̂ we find the worst b ∈ BK that violates Eq.(8) (line 3 of Algorithm 1); then,
we make an update to p̂ to minimize the violation of Eq.(8) for the worst b (line 4,5 of Algorithm 1). This process is be repeated until we get a (BK , )-decision calibrated prediction (line 2). The sketch of the algorithm is shown in Algorithm 1 and the detailed algorithm is in the Appendix.
Algorithm 1: Recalibration algorithm to achieve LK decision calibration. 1 Input current prediction function p̂, tolerance . Initialize p̂(0) = p̂; 2 for t = 1, 2, · · · , T until output p̂(T ) when it satisfies Eq.(8) do 3 Find b ∈ BK that maximizes ∑K a=1
∥∥E[(Y − p̂(t−1)(X))b(p̂(t−1)(X), a)∥∥ ; 4 Compute the adjustments da = E[(Y − p̂(t−1)(X))b(p̂(t−1)(X), a)]/E[b(p̂(t−1)(X), a)] ; 5 Set p̂(t) : x 7→ p̂(t−1)(x) + ∑K a=1 b(p̂
(t−1)(x), a) · da (projecting onto [0, 1] if necessary) ; 6 end
Given a dataset withN samples, the expectations in Algorithm 1 are replaced with empirical averages. The following theorem demonstrates that Algorithm 1 satisfies the conditions stated in Theorem 2. Theorem 2.2. Given any input p̂ and tolerance , Algorithm 1 terminates in O(K/ 2) iterations. For any λ > 0, given O(poly(K,C, log(1/δ), λ)) samples, with 1 − δ probability Algorithm 1 outputs a (LK , + λ)-decision calibrated prediction function p̂′ that satisfies E[‖p̂′(X)− Y ‖22] ≤ E[‖p̂(X)− Y ‖22] + λ.
The theorem demonstrates that if we can solve the inner search problem over BK , then we can obtain decision calibrated predictions efficiently in samples and computation.

heading: 4.4 Relaxation of Decision Calibration for Computational Efficiency
text: We complete the discussion by addressing the open computational question. Directly optimizing over BK is difficult, so we instead define the softmax relaxation.
B̄K = { b̄w | ∀w ∈ RK×C } where b̄w(q, a) =
e〈q,wa〉∑ a′ e 〈q,wa′ 〉
The key motivation behind this relaxation is that b̄w ∈ B̄K is now differentiable in w, so we can optimize over B̄K using gradient descent. Correspondingly some technical details in Algorithm 1 change to accommodate soft partitions; we address these modifications in Appendix A and show that after these modifications Theorem 2.2 still holds. Intuitively, the main reason that we can still achieve decision calibration with softmax relaxation is because BK is a subset of the closure of B̄K . Therefore, compared to Eq.(8), we enforce a slightly stronger condition with the softmax relaxation. This can be formalized in the following proposition. Proposition 3. A prediction function p̂ is (LK , )-decision calibrated if it satisfies
sup b̄∈B̄K K∑ a=1 ∥∥∥E[(Ŷ − Y )b̄(p̂(X), a)]∥∥∥ 2 ≤ : (9)
We remark that unlike Proposition 2 (which is an “if and only if” statement), Proposition 3 is a “if” statement. This is because Eq.(9) implies Eq.(8) but not vice versa.

heading: 5 Empirical Evaluation

heading: 5.1 Skin Legion Classification
text: This experiment materializes our motivating example in the introduction. We aim to show on a real medical prediction dataset, our recalibration algorithm improves both the decision loss and reduces the decision loss estimation error. For the estimation error, as in Definition 4 for any loss function ` and corresponding Bayes decision rule δ` we measure
loss gap := ∣∣∣E[`(Ŷ , δ`(p̂(X)))]− E[`(Y, δ`(p̂(X)))]∣∣∣ / sup
a∈A ‖`(·, a)‖2 (10)
In addition to the loss function in Figure 1 (which is motivated by medical domain knowledge), we also consider a set of 500 random loss functions where for each y ∈ Y, a ∈ A, `(y, a) ∼ Normal(0, 1), and report both the average loss gap and the maximum loss gap across the loss functions.
Setup We use the HAM10000 dataset (Tschandl et al., 2018). We partition the dataset into train/validation/test sets, where approximately 15% of the data are used for validation, while 10% are used for the test set. We use the train set to learn the baseline classifier p̂, validation set to recalibrate, and the test set to measure final performance. For modeling we use the densenet-121 architecture (Huang et al., 2017), which achieves around 90% accuracy.
For our method we use Algorithm 2 in Appendix A (which is a small extension of Algorithm 1 explained in Section 4.4). We compare with temperature scaling (Guo et al., 2017) and Dirichlet calibration (Kull et al., 2019). In this experiment, we first apply temperature scaling then apply other methods (decision calibration or Dirichlet calibration). The temperature scaling baseline corresponds to 0 decision recalibration steps in Figure 2.
Results The results are shown in Figure 2. For these experiments we set the number of actions K = 3. For other choices we obtain qualitatively similar results in Appendix B. The main observation is that decision recalibration improves the loss gap in Eq.(10) and slightly improves the decision loss. We also observe that our recalibration algorithm slightly improves top-1 accuracy (the average improvement is 0.40± 0.08%) and L2 loss (the average decrease is 0.010± 0.001) on the test set.

heading: 5.2 Imagenet Classification
text: We stress test our algorithm on Imagenet. The aim is to show that even with deeply optimized classifiers (such as inception-v3 and resnet) that are tailor made for the Imagenet benchmark and a large number of classes, our recalibration algorithm can improve the loss gap in Eq.(10).
Setup The setup and baselines are identical to the HAM10000 experiment with two differences: we use pretrained models provided by pytorch, and among the 50000 standard validation samples, we use 40000 samples for recalibration and 10000 samples for testing. Similar to the previous experiment, we randomly generate a set of 500 loss functions from normal distributions.
We additional test the performance of decision calibration under distribution drift on the ImagenetC benchmark (Hendrycks & Dietterich, 2019). We partition the Imagenet validation data into a recalibration set and a test set. We train decision calibration on the recalibration set (with no corruption), and measure performance on the test set (with corruption).
Results The results are shown in Figure 3 with additional plots in Appendix B. Decision calibration can generalize to a larger number of classes, and still provides some (albeit smaller) benefits with 1000 classes. Recalibration does not hurt accuracy and L2 error, as we observe that both improve by a modest amount (on average by 0.30% and 0.00173 respectively). We contrast decision calibration with Dirichlet calibration (Kull et al., 2019). Dirichlet calibration also reduces the loss gap when the number of classes is small (e.g. 10 classes), but is less scaleble than decision recalibration. With more classes its performance degrades much more than decision calibration. In the appendix Figure 6 and Figure 7, we further show that even under distribution drift (on the Imagenet-C) benchmark, decision calibration can improve both decision loss and decision loss estimation.

heading: 6 Related Work
text: Calibration Early calibration research focus on binary classification (Brier, 1950; Dawid, 1984). For multiclass classification, the strongest definition is distribution (strong) calibration (Kull & Flach, 2015; Song et al., 2019) but is hindered by sample complexity. Weaker notions such as confidence (weak) calibration (Platt et al., 1999; Guo et al., 2017), class-wise calibration (Kull et al., 2019) or average calibration average calibration (Kuleshov et al., 2018) are more commonly used in practice. To unify these notions, (Widmann et al., 2019) proposes F -calibration but lacks detailed guidance on which notions to use.
Individual calibration Our paper discusses the average decision loss over the population X . A stronger requirement is to guarantee the loss for each individual decision. Usually individual guarantees are near-impossible (Barber et al., 2019) and are only achievable with hedging (Zhao & Ermon, 2021) or randomization (Zhao et al., 2020).
Multi-calibration and Outcome Indistinguishability. Calibration have been the focus of many works on fairness, starting with (Kleinberg et al., 2016; Pleiss et al., 2017). Multi-calibration has emerged as a noteworthy notion of fairness (Hébert-Johnson et al., 2018; Kim et al., 2019; Dwork et al., 2019; Shabat et al., 2020; Jung et al., 2020; Dwork et al., 2021) because it goes beyond “protected” groups, and guarantees calibration for any group that is identifiable within some computational bound. Recently, (Dwork et al., 2021) generalizes multicalibration to outcome indistinguishability (OI). Decision calibration is a special form of OI.

heading: 7 Acknowledgements
text: SZ is supported in part by a JP Morgan fellowship and a Qualcomm innovation fellowship. MPK is supported by the Miller Institute for Basic Research in Science and the Simons Collaboration on the Theory of Algorithmic Fairness. TM acknowledges support of Google Faculty Award and NSF IIS 2045685. SE acknowledges support by NSF(#1651565, #1522054, #1733686), ONR (N000141912145), AFOSR (FA95501910024), ARO (W911NF-21-1-0125) and Sloan Fellowship.

Review summaries:
The paper defines a new notion of decision calibration and demonstrates that approximate $\mathcal{L}^K$ decision calibration is verifiable and achievable in practice, providing a practical algorithm for it. This is a result with practical calibration guarantees in multi-class calibration, which to my knowledge is the first achievement of this kind. The proposed method outperforms the existing calibration methods of temperature scaling and Dirichlet calibration in experiments on HAM10000 and ImageNet datasets and multiple architectures.

The paper looks at the problem of calibration for multi-class classification, with respect to downstream decision making.  The primary contribution of the paper is theoretical, providing a framework, algorithm, and analysis for decision calibration.  The decision calibration framework is intended to get around complexity issues for distribution calibration.  The authors provide some illustrative empirical evaluations to demonstrate the theoretical findings, using use cases in healthcare and image recognition.

This paper operates within the context of uncertainty quantification in classification. Naive generalization of the notion of a calibrated predictor from the binary to the multiclass setting is extremely prohibitive in terms of sample complexity (with respect to number of classes for the problem at hand). The authors introduce a novel notion --- decision calibration --- and analyze it theoretically and empirically on a set of prediction tasks.