When Does Optimizing a Proper Loss Yield Calibration?
Authors: Jarosław Błasiok
Parikshit Gopalan
Lunjia Hu
Preetum Nakkiran
Venue: NeurIPS 2023 spotlight (2023)
Keywords: calibration
deep learning
theory
optimization
TL;DR: We theoretically characterize when (sub-optimally) optimizing a proper loss, as we do in DNNs, leads to a near-optimally calibrated predictor.

Abstract: Optimizing proper loss functions is popularly believed to yield predictors with good calibration properties; the intuition being that for such losses, the global optimum is to predict the ground-truth probabilities, which is indeed calibrated. However, typical machine learning models are trained to approximately minimize loss over restricted families of predictors, that are unlikely to contain the ground truth. Under what circumstances does optimizing proper loss  over a restricted family yield calibrated models? What precise calibration guarantees does it give? In this work, we provide a rigorous answer to these questions. We replace the global optimality with a local optimality condition stipulating that the (proper) loss of the predictor cannot be reduced much by post-processing its predictions with a certain family of Lipschitz functions. We show that any predictor with this local optimality satisfies smooth calibration as defined in [Kakade and Foster, 2008, Błasiok et al., 2023]. Local optimality is plausibly satisfied by well-trained DNNs, which suggests an explanation for why they are calibrated from proper loss minimization alone. Finally, we show that the connection between local optimality and calibration error goes both ways: nearly calibrated predictors are also nearly locally optimal.

When Does Optimizing a Proper Loss Yield Calibration?
Jaroslaw Blasiok Columbia University j jb44510columbe edu
Parikshit Gopalan
Apple
parik gggmail.
Lunjia Hu
Preetum Nakkiran
Stanford University lun hunjia@stanford edu
Apple preetum. nakainannnikiiiiiaaaaa...aa. com
Abstract
Optimizing proper loss functions is popularly believed to yield predictors with good calibration properties; the intuition being that for such losses, the global optimum is to predict the ground-truth probabilities, which is indeed calibrated. However, typical machine learning models are trained to approximately minimize loss over restricted families of predictors, that are unlikely contain the ground truth. Under what circumstances does optimizing proper loss over a restricted family yield calibrated models? What precise calibration guarantees does give? In this work, we provide rigorous answer to these questions. We replace the global optimality with local optimality condition stipulating that the (proper) loss of the predictor cannot be reduced much by post- post-processing its predictions with a certain family Lipschitz functions. We show that any predictor with this local optimality satisfies smooth calibration as defined in Kakade and Foster (2008) Blasiok et al. [2023b]. Local optimality is plausibly satisfied by well-trained DNNs, which suggests explanation for why they are calibrated from proper loss minimization alone. Finally, we show that the connection between local optimality and calibration error goes both ways: nearly calibrated predictors are also nearly locally optimal.
1 Introduction
In supervised prediction with binary labels, two basic criteria by which we judge the quality of
predictor are accuracy and calibration. Given samples from a distribution D on X' {0, 1} that corresponds to points from X' with binary labels
{0, 1}. we wish to learn predictor f that
assigns each æ a probability f(x) E [0, 1] that the label 1. Informally, accuracy measures how close the predictor f is to the ground-truth I (x) E[y| | Calibration (Dawid, 1982 Foster and Vohra 1998) is an interpretability notion originating from the literature on forecasting, which stipulates that the predictions of our model be meaningful as probabilities. For instance, all points where f(x) = 0.4, calibration requires the true label to be about 40% of the time, Calibration and accuracy are complementary notions: reasonably accurate predictor (which is still far from optimal) need not calibrated, and calibrated predictors (e.g. predicting the average) can have poor accuracy. The notions complementary but not necessarily conflicting; for example, the ground truth itself is both optimally accurate and perfectly calibrated.
Proper losses are central to the quest for accurate approximations of the ground truth. Informally proper loss ensures that under binary labels y drawn from the Bernoulli distribution with parameter v",
Here we focus accuracy the predictor as opposed to accuracy of classifier induced by f.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the expected loss Ey z)] is minimized at v = itself. Familiar examples include the squared loss lsq (y, 2) = (y) 10-2 2)2 and the cross-entropy loss exent v) = y log(1/e) key property of proper losses is that over the space of all predictors, the expected loss ED (e(y, [x)) is minimized by the ground truth f* which also gives calibration. However minimizing over all predictors is infeasible. Hence typical machine learning deviates from this ideal in many ways: we restrict ourselves to models of bounded capacity such as decision trees or neural nets of a given depth and architecture, and we optimize loss using algorithms like SGD, which are only expected to find approximate local minima in the parameter space, What calibration guarantees transfer to this more restricted but realistic setting?
///00++- + (1-y)
log(1/11 v)). A
The State of Calibration & Proper Losses There is folklore belief in some quarters that optimizing a proper loss, even in the restricted setting, will produce a calibrated predictor. Indeed, the user guide for scikit-learn (Pedregosa al. [001]] claims that LogisticRegression returns well calibrated predictions by default as it directly optimizes Log loss Before going further, we should point out that this statement in its full generality is just not true: for general function families C, minimizing proper loss (even globally) over C. might not result in a calibrated predictor. Even if the class C contains perfectly calibrated predictors, the predictor found by loss minimization need not be (even close to) calibrated. A simple example showing that even logistic regression can fail to give calibrated predictors is provided in Appendix
Other papers suggest a close relation between minimizing a proper loss and calibration, but stop short of formalizing quantifying the relationship. For example, in deep learning. [Lakshminarayanan itt al. [2017) states calibration can be incentivised by proper scoring rules. There is also a large body of work on post-hoc recalibration methods. The recipe here is first train a predictor via loss minimization over the training set, then compose it with a simple post-processing function chosen to optimize cross- cross-entropy on a holdout set (Platt] 1999 Zadrozny and Elkan 2002]. See for instance Platt scaling [Pltt 1999], where the post prot-procsssing functions are sigmoids, and which continues to be used in deep learning (e.g. for temperature scaling as in Guo al. (2017). Google's data science practitioner's 's guide recommends that, for recalibration methods, the calibration [objective] fibjecttieeJuunctoon function should minimize a strictly proper scoring rule [Richardson and Pospisil 202T]. In short, these works suggest recalibration by minimizing a proper loss, sometimes in conjunction with a simple family of post-processing functions. However, there are no rigorous bounds on the calibration error using these methods, nor is there justification for particular choice of post-processing functions.
Yet despite the lack of rigorous bounds, there are strong hints from practice that in certain settings, optimizing proper-loss does indeed yield calibrated predictors. Perhaps the strongest evidence comes from the newest generation of deep neural networks (DNNs). These networks are trained to minimize a proper loss (usually cross- cooss-y using SGD or variants, and are typically quite far from the ground truth, yet they turn out to be surprisingly well-calibrated. This empirical phenomenon occurs in both modern image classifiers [Minderer et al. 2021 Hendrycks* et al., 2020). and language models (Desai and Durrett 2020 OpenAl] 2023]. The situation suggests that there is key theoretical piece missing in our understanding of calibration, to capture why models can be so well-calibrated "out-of-the-box." " This theory must be nuanced: not all ways of optimizing a proper loss with DNNs yields calibration. For example, the previous generation of image classifiers were poorly calibrated [Guo et al.] [017], though the much smaller networks before them were well-calibrated [Niculescu- Miizzl and Caruana 2005). Whether DNNs are calibrated, then depends on the architecture, distribution, and training algorithm- and our theory must be compatible with this.
In summary, prior work suggests a close but complicated relationship between minimizing proper loss and calibration. On one hand, for simple models like logistic regression, proper loss minimization does not guarantee calibration. On the other hand, for DNNs, certain ways (but not all ways) of optimizing proper loss appears to yield well-calibrated predictors. The goal of our work is to analyze this phenomena from theoretical perspective f Our motivating question is: What minimal conditions on model family and training procedure guarantee that optimizing for a proper loss provably yields small calibration error?
html Log-loss is Exemt in our notation. For simplicity, we avoid generalization concerns and consider the setting where we minimize loss directly on the population distribution. This is a reasonable simplification in many learning settings with sufficient samples, such the I-epoch training of many Lane--anguage-MMrn Models..
https://sciitt- httpe/////sable/ettttteee////lla
2

---

Figure 1: Schematic depiction of the loss landscape of a proper loss on the population distribution. The red dot represents a well-calibrated predictor f. The blue curve represents all predictors {K o f E Ke} obtained by admissible post-processing of f. Since the proper loss cannot be decreased by
(the red dot is minimal point on the blue curve), the predictor f well-calibrated, even though it is not a global minimum.
1.1 Our Contributions
The main contribution of this work to identify local optimality condition for a predictor that is both necessary and sufficient to guarantee calibration. The local optimality condition requires that the loss cannot be reduced significantly through post-procsssing using a family of functions K2 that have certain Lipschitz-ness guarantees, where post-processing means applying function R [0, 1] + [0, 1] to the output of the predictor. This condition is illustrated in Figure [ it is distinct from the standard local optimality condition of vanishing gradients. We prove that predictor satisfying this local optimality condition smoothly calibrated in the sense of Kakade and Foster 20088. Gopalan al. [2022b), Blasiok al. [2023b]. Smooth calibration is consistent calibration measure that has several advantages over the commonly used Expected Calibration Error (ECE); see the discussion in Kakade and Foster [2008), [Blasiok et al. [2023b]. Quantitatively for the of the squared loss, we present a tight connection between smooth calibration error and the reduction in loss that is possible from post-pun pros-eccsssing with Kç. For other proper loss functions L, give a tight connection between post-processing with K₁ and a calibration notion we call dual smooth calibration. The fact that the connection goes both ways implies that predictor that does not satisfy our local optimality condition is far from calibrated, so we have indeed identified the minimal conditions needed ensure calibration.
Heuristically, we believe these theoretical results shed light on why modern DNNs often calibrated in practice. There are least three possible mechanisms, varying levels of formality.
Implications.
First, informally: poor calibration implies that the test loss can be reduced noticeably by post- processing with a simple function. But simple post-processings can be represented by adding a few layers to the DNN- (or continuing training) with SGD. Thus, if our DNN has been trained to the point where such easy gains are not left the table (as expect of state-of-thee oftt-of-thh-art models), then is well-calibrated.
could plausibly improve the test loss by adding few layers and re-training
The second possible mechanism follows from one way of formalizing the above heuristic, yielding natural learning algorithms that provably achieve calibration. Specifically, consider Structural Risk Minimization (SRM): globally minimizing a proper loss plus complexity regularizer, within some restricted function family. In Section 5 we prove SRM is guaranteed to produce a calibrated predictor, provided: (1) the function family is closed under post-processing and (2) the complexity regularizer grows only mildly under post-processing. If the informal "implicit regularization hypothesis" in deep learning is true, and SGD on DNNs equivalent SRM with an appropriate
camplextt--regulare Arora et al. 2019 Neyshabur al. 2014 Neyshabur 2017 Zhang et al., [021], then our results imply DNNs are well-calibrated as long as the regularizer satisfies our fairly mild assumptions.
Finally, third mechanism for calibration involves a heuristic assumption about the optimizer (SGD). Informally, for sufficiently deep network, updating the network parameters from computing the function I to computing the post-processed (K f') may be "simple" update for SGD. Thus, if it were possible to improve the loss via such simple post-processing, then SGD would have already exploited this by the end of training.
3

---

These algorithms and intuitions also suggest practical guidance: for calibration, one should optimize loss over function families that are capable of computing rich classes of post-procsssing functions.
The universality properties of most DNN architectures imply they can compute a rich family of post-processing functions with small added depth [Cybenko] [989] Lu et al. 2017 Yun et al. 2019 Zhou 2020) but the family of functions used in logistic regression (with logits restricted to being affine in the features) cannot.
Our results are consistent with the calibration differences between current and previous generation models, when viewed through the lens of generalization. In both settings, models are expected to be locally-optimal with respect to train loss [Carrell et al.] [022], since this is the explicit optimization objective. Calibration, however, requires local-optimality with respect to test loss. Previous generation image classification models were trained to interpolate on small datasets, so optimizing the train loss was very different from optimizing the test loss [e.g. Guo et al., 2017] Mukhoti et al. (020). Current generation models, in contrast, are trained on massive datasets, where optimizing the train loss is effectively equivalent to optimizing the test loss and so models are close to locally-opting with respect to both, implying calibration.
Organization. We first give technical overview of our results in Section In Section 3 prove our main result in the case of square-loss. Then in Section 4 we extend this result to a wide family of proper losses. Finally, in Section we present natural algorithms which provably achieve calibration, as consequence by our results. Additional related works are presented in Appendix A
2 Overview
In this section, we present a formal but still high-level overview of our results. We first set some notation. All our probabilities and expectations are taken with respect to a distribution D over X' x {0, 1}. A predictor a function f X' + [0. 1] that assigns probabilities to points, the ground- truth predictor is (xx = Elylz]]- A predictor is perfectly calibrated if the set A {or E [0, 1] [zylf(=) = 2) * 3 has measure 0 (i.e. (f) E A) 0). A post-processing function is a function k: : [0. 1] - 1]. A loss function is a function É {0, 1] x [0. - R. where {(y, v) represents the loss suffered when we predict v E [0, 1] and the label is y E {0, 1). Such loss is proper if when y Ber(v") is sampled from the Bernoulli distribution with parameter v", the expected loss E(E w]] is minimized at v v", and we say loss strictly proper if vz is the unique minimizer.
As warm-up, we present a characterization of perfect calibration in terms of perfect local optimally over the space of all possible (non-Lipschitz) post proseesrcsssnng functions.
Claim 2.1. For every strictly proper loss f, a predictor I is perfectly calibrated iff every post- processing function
Blcly, f())) & Blely, x(f())).
(I)
D
D
This is true, because if f is perfectly calibrated, and k arbitrary, then after conditioning on arbitrary prediction fI)) we have:
E(e(y, (()))(()))) = =]= yr-Ber(w)
[C(y r)]
[Cy k(w)),,
gerBer(v)
and (T) follows by averaging over On the other hand if is not perfectly calibrated, can improve the expected loss by taking k(v) = [xy) = u) - by the definition of the strictly proper loss, for each we will have E(f(y, (((())))[()) of Bll(s, (=)))((()) =.], and on set of positive probability the inequality will be strict.
While we are not aware of this precise claim appearing previously, statements that are similar in spirit are known; for instance, by the seminal work Foster and Vohra [1998] which characterizes calibration in terms of swap regret for the squared loss. In our language they show the equivalent Claim 2.1 for being a squared loss, and i restricted to be of the form k((wg) == Wo, so()) == e for all 7 Vg.
Claim 2.1 connects calibration to a local optimality condition over the space of all possible post- processing functions. If this is satisfied, it guarantees calibration even though the loss might be far from the global minimum. This sheds light on classes of predictors such as decision trees or branching programs, which are closed under composition with arbitrary prsc-procsssing functions,

---

since this amounts to relabelling the leaf nodes. It tells us that such models ought to be calibrated from proper loss minimization, as long as the optimization achieves fairly weak notion of local optimality.
The next step is to ask whether DNNS could satisfy similar property. Closure under arbitrary post-processing seems too strong a condition for DNNs to satisfy - we should not expect DNNs to be able to express arbitrarily discontinuous uni-variate yost-processing functions. But we do not expect or require DNNs to be perfectly calibrated, only to be close to perfectly calibrated. Measuring the distance from calibration involves subtle challenges as highlighted in the recent work of Blasiok et al. 2023b]. This leads us to the following robust formulation which significantly generalizes Claim 2.1
Using the well known relation between proper losses and Bregman divergences [Savage 1971 Gneiting and Raftery 2007]. we consider proper loss functions where the underlying convex functions satisfy certain differentiability and smoothness properties. This is a technical condition, but one that is satisfied by all proper loss functions commonly used in practice.
We only allow post-processing functions that satisfy certain Lipschitzness properties. Such func- tions are simple enough to be implementable by DNNs of constant depth. Indeed we heuristically believe that state-of-the-arr DNNs will automatically be near-optimal w.r.t. such post- post-processings. as mentioned in Section
We measure calibration distance using the notion of smooth calibration from Kakade and Foster (2008) and strengthenings of it in Gopalan et al. [002bb] Blasiok et al. [2023b] Smooth calibration plays a central role in the consistent calibration measures framework of Blasiok et al. 2023b), where is shown using duality that the smCE is linearly related with the Wasserstein distance to the nearest perfectly calibrated predictor [Blasiok et al. 2023b). In practice, there exist sample-efficient and linear-time estimators which approximate the smooth calibration error within quadratic factor Blasiok et al. 2023b].
With these notions in place, we show that the post-processing gap of a predictor, which measures how much the loss can be reduced via certain Lipschitz post-processing functions provides both an upper and a lower bound on the smooth calibration error. This result gives us robust and quantitative version of Claim 2.1] The main technical challenge in formulating this equivalence is that for general the class of post-procsssing functions that we allow and the class of smooth functions that we use to measure calibration error are both now dependent on the loss function f, they are Lipschitz over an appropriately defined dual space to the predictions defined using convex duality. In order to keep the statements simple, state our results for the special case of squared loss and cross entropy loss below, defering the full statement to the technical sections.
Squared loss. For the squared loss (sg(y, v) (y- (uy-v) 2) we define the post- post-processing gap pf to be the difference between the expected squared loss El (3. f(r)) of predictor f and the minimum expected squared loss after we post-process f(x) + f(x)) + (f()))) for some 1-Lipschitz n. The Brier score [Brier et al., 1950 Foster and Vohra 1998) uses the squared loss of a predictor as a calibration measure; pGap can be viewed as a differential version of Brier score.
Definition 2.2 (Post- PPost-proeessig gap). Let K denote the family of all post-processing functions R: [0, 1] + [0, 1] such that the update function 17(1)= = k(v) is 1-Lipschitz. For predictor f: + [o, 1] and distribution D over X x {0, 1}, we define the post-processing gap of f w.r.t D to be
PGapp(S)= = E(..,)~ Re (v. [x)) - infwek ((a.)) (v, (aay,,s(,,. (((()))))
We define the smooth calibration error smCEp(f) as in Kakade and Foster 2008
Gopalan al.
[2022b] Blasiok et al. (2023b) to be the maximum correlation between (2) and 7 (x))) over all
bounded 1-Lipschitz functions 7). Smooth calibration is a consistent measure of calibration BBlasiok
et al. 2023b]. It does not suffer the discontinuity problems of ECE (Kakade and Foster 2008
and is known to be linearly related with the Wasserstein distance to the nearest perfectly calibrated predictor (Blasiok et al. 2023b). ). In particular, it is 0 if and only if we have perfect calibration. We refer the reader to these papers for a detailed discussion of its merits.
Definition 2.3 (Smooth calibration error). Let be the family of all 1-Lipschitefuncciionsn functions v) [0 -
[-1, 1]. The smooth calibration error of predictor f X [0, 1] with respect distribution D
5

---

over X' x {0, 1 is defined as
smCEp(f) h - f()))
Our main result is quadratic relationship between these two quantities:
Theorem 2.4. For any predictor f X + [o, 1] and any distribution 'D over X x {0, 1}.
smCEp(f)² < (f) s 2mCEE(ff).
In Appendix D we show that the constants in the inequality above are optimal.
Cross-entropy loss. For the cross entropy loss bxent(u) (1, v) = -y In - (1 - y) In(1 -). we observe its close connection to the logistic loss {(v) (y. t) = In(1 + e²) yt given by the equation
Exent v) - (( (v,
(2)
where L: = In(::(1 - -)) is what we call the dual prediction corresponding to c. While a standard terminology for L. is logif, we say is the dual prediction because this notion generalizes arbitrary proper loss functions. One can conversely obtain a prediction from its dual prediction t by taking the sigmoid transformation: e = (t) == 1/(1 + e The superscript & in the logistic loss g(0) can be understood to indicate its relationship to the dual prediction and the exact meaning is made clear in Section 4 Based on (2). optimizing the cross-entropy loss Exent over predictions is equivalent to optimizing the logistic loss ((V) over dual predictions t.
Usually, neural network that aims to minimize the cross-entropy loss has a last layer that computes the sigmoid a (the binary version of softmax), so the value computed by the network before the sigmoid (the "logit") is the dual prediction. If we want to enhance the neural network by adding more layers, these layers are typically inserted before the final sigmoid transformation. It is thus more natural to consider post-processings on the dual predictions (logits) rather than the predictions themselves.
For a predictor f. we define the dual procesrocsssing gap pGap (a.11)))) (g) of its dual predictor
g(x) = (x)ff((/((1 f()))) to be the difference between the expected logistic loss E[((v) (y, g (())) of g and the minimum expected logistic loss after we post-process g(x) + g(z) + n(g(x)) for some 1-Lipschitz R + [-4, 4], where the constant 4 comes from the fact that the logistic loss is 1/4-smooth in
Definition 2.5 (Dual post-processing gap for cross-entropy loss, special case of Definition 4.4p. Let K denote the family of all post-processing functions K R - IK such that the update function n(t) := x(t) - t is 1-Lipschitz and bounded [n((t] I 4. Let ((+) be the logistic loss. Let D be distribution over X {0, (0, 1}. We define the dual post-processing gap of a function : + R to be (v.1/4)
pGap ( (g) == E(a.)~> gl (v. - infaek E(Ew) g10) (y. (y.K()())))
We define the dual smooth calibration error SmCE( (g) to be the maximum of EEly
f (n))(((())]]] over all 1/4-Lisschitz functions 77 R [-1, Like with smooth calibration, is O if and only if the predictor is perfectly calibrated.
Definition 2.6 (Dual smooth calibration for cross-entropy loss, special case of Definition 4.5). Let H. be the family of all 1/ 1/A-Lipschitz, functions 1) IR + [-1, For a function g : X - I., define (((()) for every x E X' where o is the sigmoid transformation. Let be a distribution over X' {0, 1). We define the dual calibration error of g as
predictor f X - 10, 1] such that f'xx) = (g(x))
SmCE(p../4) == SuP E(z,))~D(( - ((=))(((()))
We show a result similar to Theorem 2.4 that the dual post-processing gap and the dual smooth calibration enror are also quadratically related. Moreover, we show that a small dual smooth calibration error implies a small (standard) smooth calibration error.
Corollary 2.7 (Corollary of Thcorem 4.6 and Lemma 4.7p. Let pGap (v.1/4) (V.1111 and ( be
defined as in Definition 2.5 and Definition 2.6 2.6 the cross-entropy loss. For any function g : X RR and any distribution D over X' x [0,1),
2 cm (3.11)) < PGpppp
(v.1/4) (g) S (
(3)

---

Moreover. let predictor f: - [0. be given by f(x) [g((x)) for the sigmoid transformation o. Its (standard) smooth calibration error smCEp(f) defined in Definition 2.3 satisfies
smCEp(f) & SmCE (V.1/ (g).
(4)
The constants in the corollary above are optimal as we show in Lemmas D.3 and D.4 in the appendix.
Both results 3 and 4 generalize wide class of proper loss functions
show in Section $
Remark 2.8. In a subsequent work, Blasiok and Nakkiran (2023) proved the reverse direction of
4 for the cross-entropy loss: smCEp(f) 2 ( (,,14) (g)²). Hence both smCE(w.1/4) (g) and
PGap (w/1/4) (g) are consistent calibration measures, a notion introduced by Blasiok et al. 2023bb].
Our result shows that achieving a small dual post-processing gap when optimizing a cross-entropy is necessary and sufficient for good calibration guarantees. It sheds light on the examples where logistic regression fails to yield a calibrated predictor; in those instances the cross-entrppy loss can be further reduced by some Lipschitz post-processing of the logit. This intuitive because logistic regression only optimizes cross-entropy within the restricted class where the logit is a linear combination of the features plus bias term, and this class is closed under Lipschitz post-processing.
3 Calibration and Post-processing Gap for the Squared Loss
In this section we prove our main result Theorem 2.4 relating the smooth calibration error of predictor to its post-processing gap with respect to the squared loss.
Proof of Theurem 2.4 first prove the upper bound on pGap (f). For any x E in the definition
of pGap (Definition 2.2 b. there exists 1 1-Lipschitz function 7) [0, + [-1, such that k(O)
v + TT)) for every 0 E 00 1]. For the squared loss E,
B(e,a)~ K (f (x))) = EE(y f(x - (((())))
[E((v - ((o)) (5)
The three terms on the right hand side satisfy
E((y - [xx) B(((y, f(x)))
El(y - f(=))(((()) - smCEn(f),
[ln(s(x)) O.
Plugging these into 5 we get
Ellly, f())] - El((y, x x(f()))) - 2smCEp(f).
Since this incquality holds for any E K. we get (f) S 2smCEp(f) as desired.
Now we prove the lower bound on (f) For any 1-Lipschitz function r |0, 1] + [-1, 1], define 3 = [((y (=))))((()) E [-1, and define post-processing λ. [0, - [o. 1] such that <(V) = uroj
Bn(v)) for every E [0. 1],
where projo. () (z) is the value in [0, 1] closest to u, i.e., pr min(max(u, 0). 1). By Lemma H.2 we have E K. The expected squared loss after apply the post-processing can be bounded as follows:
E(s.)))D(((,,<(( <( (((()))) S Elyy - f(z) Bn(f(z)))
28 E[(y - ((00)))199((-((())((())a)a))))))
[())))((())) B()(S()))
= [[((v,((x))) -(3))))233+ = +
S EE((8, -23)
Re-arranging the inequality above, we have
E f()))m(((=))]3 = 32 < El((y, [())) - ([((,,([[()))) (G)
Since this inequality holds for any 1 1-Lipschitz function 7 [0. |-1, 1]. we get sm (E) (f) as desired.
In Appendix D provide examples showing that the constants in Theorem 2.4 are optimal.
7

---

4 Generalization to Any Proper Loss
When we aim to minimize the squared loss, we have shown that achieving a small post-proces post-processing gap w.r.t. Lipschitz post-processings ensures small smooth calibration error and vice versa. In this section, we extend this result to a wide class of proper loss functions including the popular cross-entropy loss.
Definition 4.1. Let V S [0, 1] be a non-emply interval. We say a loss function e: [0, x is proper if for every E V, it holds that v E argmin. Ber-BBr(t))((())) v')].
One easily verify that the squared loss Ely, u) (y w)² is proper loss function V j0, 1], and the cross entropy loss E(y, v) = y In - (1 y) In - v) is a proper loss function over V (0, 1).
turns out that if we directly replace the squared loss in Definition 2.2 with an arbitrary proper loss, we do not get a similar result as Theorem 2.4 In Appendix C we give simple example where the post-processing gap w.r.t. the cross-entropy loss can be arbitrarily larger than the smooth calibration error. Thus ideas are needed to extend Theorem 2.4 to general proper loss functions. We leverage a general theory involving correspondence between proper loss functions and convex functions [Shuford al., 1966 Saaagee 1971. Schervish] 1989 Buja et al., 2005 We provide detailed description of this theory in Appendix There we include a proof of Lemma E.4 which implies the following lemma:
R be proper loss function. For every v E V, define dual(v) == E(O, v) - ((1,)), Then there exists a convex function R such that
Lemma 4.2. Let V C 1] be a non-empty interval. Let e {0, X
fly, v) = (ddua((v) - y dual(v) for every y E {0,1] and v E V.
(6)
Moreover, if is differentiable, then (v(()) E [0, 1].
Lemma 4.2 says that every proper loss induces a convex function &b and a mapping dual: : V - R that maps prediction V S [0, 1] to its dual prediction dual(v) E IR. Our main theorem applies whenever the induced function & is differentiable, and V is X-Lipschitz (equivalently ei is X-smooth) those are relatively mild conditions that satisfied by all proper loss functions of interest.
The duality relationship between and dual(v) comes from the fact that each (v, dual(u)) pair makes the Fenchel- Young divergence induced by a conjugate pair of convex functions (y, 15 take its minimum value zero, as we show Appendix Equation (6) expresses proper loss as a function that depends on dual(r) rather than directly on v, and thus minimizing proper loss over predictions v is equivalent to minimizing a corresponding dual loss over dual predictions = dual(r):
Definition 4.3 (Dual loss). For a function vb IR + R. define dual loss function ((v) {0, x + I such that
(v, (t)) - yt for every y E (0,1) and t E R.
Consequently, if a loss function f 10, x V + R2 satisfies for some V C [0, 1] and dual: V
R. then
fly. v) e(v) dual( for every y (0, 1) and V.
The above definition of dual loss function is essentially the definition of the Fenchel- Young loss
in the literature [see e.g. Duchi et al. 2018 Blondel et al. 20200. loss function g(0) satisfying the relationship in (7) has been referred to composite loss [see e.g. Buja et al. 2005 Reid and
Williamson 2010].
For the cross cross-entropy loss f(y, v) = yy lnv (1 y) In(1 - v). the corresponding dual loss is the logistic loss g(v) (y, t) = In(1 + e²) - yt, and the relationship between a prediction E (0, 1) dual(v) E R is given by v (t) for the sigmoid transformation
and its dual prediction (t)) = e² /11 + e²).
For predictor f : X V. we define its dual g(z) dz)) w.n.t the dual loss ((0) follows:
gap by considering dual predictions
8

---

Definition 4.4 (Dual post-preee processing gap). For À O, let K5 denote the family of all post-p post-procsssing
functions R + E. such that there exists a L-Lipschitz function 1j Let 'D be a distribution
1/x, 1/ satisfying
k((t) = t+ (t) for everyt t R. Let and g be defined in Definition 4.3
over X' x {0.1}. We define the dual post- post-processing gap of function X R to be
pGapp (Gap (g) = B(2.y)=D (()) ( (())) inffee,, B(a,y)> ((0) ( k(g(z)))
Definition 4.4 is a generalization of Definition 2.2 from the squared loss to an arbitrary proper loss corresponding to a function as in (6). The following definition generalizes the definition of smooth calibration in Definition 2.3 to an arbitrary proper loss in a similar way. Here we use the fact proved in Appendix
F (equation 20 that if the function & from Lemma 4.2 for proper loss holds for any E V. where V+y(-) denotes the derivative of v. This means that Veh transforms a dual prediction to its original prediction.
:: {0, } x V - IR is differentiable, then Vib(dual(())
Definition 4.5 (Dual smooth calibration). For À let H be the family of all LiLipschitz,uunttiin n: R + [.]. Let v : + R be differentiable function with derivative V E [0. for every t e R. For a function g X + IR, define predictor f X + [0, 1] such that f(x) Vv(g(z)) for every z E X. Let D be distribution over X x {0, 13. We define the dual calibration error of to be
SmCE == SuPyEr |E(xs)>Dlyy f())))(((z))]]
In Theorem 4.6 below we state our generalization of Theorem 2.4 to arbitrary proper loss functions. Theorem 4.6 shows that achieving a small dual post-processing gap equivalent achieving a small dual calibration error. We then show in Lemma 4.7 that small dual calibration error implies a small (standard) smooth calibration error.
Theorem 4.6. Let 1p R Th. be differentiable convex function with derivative Vib(()) every & E TR. For X > 0, assume that vo is X-smooth, i.e.,
[0, for
[v((t) Ve((') S Aie -0- 1'| forevery t,
R.
(8)
Then for every y X R and any distribution D over X' (0,
smCE ()E()..))))))) (1) S ApGapp (0-))))))))))) (g) S smCE
Lemma 4.7. Let sb +R
be differentiable convex function with derivative Vy((t) (0, for
every t E R. For >> 0, assume that vb is X-smooth as in (8). For g X + R. define f X' + [0.
such that f(x = Vib(g(z)) every x E X. For a distribution 'D over {0, 1), define sm smCE (f) as in Definition Then
smCEp()) S $
We defer the proofs of Theorem 4.6 and Lemma 4.7 to Appendix and Appendix F.2 the two results, assuming vb is X-smooth, we have
Combining
smCEn(/)3/2 < ApGap (1.
This means that a small dual post-processing gap a proper loss implies a small (standard) smooth calibration error. The cross- loss E is proper loss where the corresponding v from Lemma 4.2
given by (t) = In(1 e²) and is 1 1/--smotth. Setting 1/4 in Theorem 4.6 and Lemma 4.7 we get and 4 for the cross-entropy loss.
5 Optimization Algorithms and Implicit Regularization
As simple consequences of our results, there are several natural algorithms which explicitly minimize loss, but implicitly achieve good calibration. Here, we focus on one such algorithm: structural risk minimization, and discuss additional such algorithms in Appendix G We also give informal intuitions connecting each algorithm to training DNNs in practice.
We show that structural risk minimization (SRM) on the population distribution is guaranteed output cell-calibrated predictors, under mild assumptions on the function family and regularizer. Recall, structural risk minimization considers function family equipped with some "complexity measure" F + Rzo. For example, we may take the family of bounded- width neural networks, with depth

---

as the complexity measure. SRM then minimizes proper loss, plus complexity-regulaii given by JcC
argmin (( + Au(S)- fEF D
The complexity measure ii is usually designed to control the capacity of the function family for generalization reasons, though we will not require such assumptions about μ.. Rather, only require that ju(" does not grow too quickly under composition with Lipshitz functions. That is, a(x o f) should be most constant greater than w(f), for all Lipshitz functions Now, long as the function family F is also closed under composition, SRM is well-calibrated:
Claim 5.1. Let F be class of functions f X - [0, 1] closed under composition with K, where F, E K have f E F. Let p F Rzo
define K as in Definition 2.2 That is, for be any complexity measure satisfying, for all f E FR K 1uR f) I (ff) + 1. Then the minimizer f of the regularized optimization problem
argmin T. (aal), + Xp(s).
JEF D
satisfies pGapp(f*) S X, and thus by Theorem
2.4 has small calibration error: smCEd(f*) S VX.
Proof. The proof is almost immediate. Let MSFD(f) denote Ed (f (x))] Consider the solution f and arbitrary & E K. Since o f E F, we have
MSEp(f") + \n(f)) & MSEp(K o f*) + Ap(io f*) < MSEp(K f*) + Ap(f*) + A.
After rearranging, this is equivalent to
MSED( - (SE 1*) X,
and since K E K was arbitrary, we get (f) I x. as desired.
Discussion: Implicit Regularization. This aspect of SRM connects our results to the "implicit regularization" hypothesis from deep learning theory community [Neyshabur] 2017). The implicit regularization hypothesis is an informal belief that SGD on neural networks implicitly performs minimization a coomplexity-regulriize
objective, which ensures generalization. The exact form of this complexity regularizer remains elusive, but many works have attempted to identify its structural properties (e.g. |Arora al. [2019], Neyshabur et al. 20144), Neyshabur [2017], /Zhang et al.. (202T). In this context, our results imply that if the implicit regulanization hypothesis is true, then as long as the complexity measure y doesn't increase too much from composition, the final output of SGD will be well-calibrated.
6 Conclusion
Inspired by recent empirical observations, we studied formal conditions under which optimizing a proper loss also happens to yield calibration "for free." We identified a certain local optimality condition that characterizes distance to calibration, in terms of properties of the (proper) loss landscape. Our results apply even realistic optimization algorithms, which optimize over restricted function families, and may not reach global minima within these families. In particular, our formal results suggest an intuitive explanation for why state-of-the-ar DNNs are often well-calibrated: because their test loss cannot be improved much by adding a few more layers. It also offers guidance for how one can achieve calibration simply by proper loss minimization over sufficiently expressive family of predictors.
The connection between our theoretical results and DNNs in practice is heuristic- for example, we do not have a complete proof that training a DNN with SGD on natural distributions will yield a calibrated predictor, though we have formal results that give some intuition for this. Part of the difficulty here is due to known definitional barriers [Nakkiran] 202T], which is that we would need to formally specify what "DNN" means practice (which architectures, and sizes?), what "SGD" means in practice (what initialization, learning-rate schedule, etc), and what "natural distributions" means in practice. Finally, we intuitively expect the results from our work to generalize beyond the binary label setting; we leave it to future work to formalize this intuition.
Limitations.
10

---

Acknowledgments and Disclosure of Funding
Part of this work was performed while LH was interning at Apple. LH is also supported by Moses Charikar's and Omer Reingold's Simons Investigators awards, Omer Reingold's NSF Award IIS- 1908774, and the Simons Foundation Collaboration on the Theory of Algorithmic Fairness. JB is supported by Simons Foundation.
References
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U Rajendra Acharya, al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information Fusion, 76:243-297, 2021.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Jarostaw Btasiok and Preetum Nakkiran. Smooth ECE: Principled reliability diagrams via kernel smoothing. arXiv preprint arXiv:2309.122336 2023.
Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, and Preetum Nakkiran. Loss minimization yields multicalibration for large neural networks. arXiv preprint arXiv:2304.09224, 2023a. https:ss::/ http:///ooooog///...// 480500/855//// arxiv 23004.9444
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, page 1727-1740, New York, NY, USA, 2023b. Association for Computing Machinery. ISBN 9781450399135.
Mathieu Blondel, André F. Martins, and Vlad Niculae. Learning with Fenchel-Young losses. Journal of Machine Learning Research, 21(35):1-69, 2020. URL http://jmlr org/ /atp///pes///////e v21/19-022 021.. html
Glenn W Brier et al. Verification of forecasts expressed in terms of probability. Monthly weather review, 18(1):1-3, 1950.
Andreas Buja, Werner Stuetzle, and Yi Shen. Loss functions for binary class probability estimation and classification: Structure and applications. Manuscript, 2005. URL HtRL/htps::// /tsttts://sits.... stat washington, wwwpedduuueeeeeeeeeee http///xs/Leannnnngggg wwwpiiingpppppppppppeeeeeee http://apppppppppre..ee wwwpprrsooorirgg.......p. pdf
Annabelle Carrell, Neil Mallinar, James Lucas, and Preetum Nakkiran. The calibration generalization gap. arXiv preprint arXiv:2210.0166, 2022.
Lucas Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. On double-descent in uncertainty quantification in overparametrized models. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 7089 7125. PMLR, 25-27 Apr 2023a. URL html
mlr wwtppppwee//e/eepppppppp clarteeeeeeeaare..
Lucas Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Theoretical character- ization of uncertainty in high-dimensional linear classification. Machine Learning: Science and Technology, 4(2)x02502,, jun 2023b. doi: 10.1088/263--2153/ecc11 URL https 7/dx org/ 10110000022333 21122221132/cc////
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control,
signals and systems, 2(4):303-314, 1989.
Philip Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77 (379):605-610, 1982.

---

Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 295-302. 2020.
John Duchi, Khashayar Khosravi, and Feng Ruan. Multiclass classification, information, divergence and surrogate risk. The Annals of Statistics, 46(6B):3246 - 3275, 2018, doi: 10.121417-A0S1155, URL https://dol org/ 10. 1214/17-A0S155
Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2):379-335 330,0 1998.
Yarin Gal. Uncertainty in Deep Learning. Phl) thesis, University of Cambridge, 2016.
Ira Glorus-Harris, Declan Harrison, Michael Keams,, Aaron Roth, and Jessica Sorrell. Multicalibra- tion as boosting for regression. arXiv preprint arXiv:2301. 2023.
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and esti- mation. Journal of the American Statistical Association, 102(477):55-377) 2007. doi: 10.1 10.119800162145000000000
URL https://doii org/10. 0111//0011110000000000000000
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Om- nipredictors. In Innovations in Theoretical Computer Science (ITCS' 2002), 2022a. URL
https://arxiv org/ abs/21099 05389
Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao. Low-degree multicalibration. In Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 3193-3234. PMLR, 2022b.
Parikshit Gopalan, Lunjia Hu, Michael Kim, Omer Reingold, and Udi Wieder. Loss Minimization Through the Lens Of Outcome Indistinguishabilit.. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings Informaties (LIPIes), pages 60:1-60:20, 2023a.
Parikshit Gopalan, Michael P. Kim, and Omer Reingold. Characterizing notions of omniprediction via multicalibration. CoRR, abs/2302.06726, 2023b. doi: 10448500arXx..222.0677.. URL
https://doi.org: www.:o/g.......////////// arxiv 2302 06726
Alex Graves. Practical variational inference for neural networks. Advances in neural information processing systems, 24, 2011.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the httputttttionally-dennfaaaaaaaaa masses. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018
Dan Hendrycks*, Norman Mu*, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshninarayanan. Augmix: A simple method to improve robustness and uncertainty un- der data shift. In International Conference Leurning Representations, 2020. URL https //openreviev. panpeerrviee.net/foormtt iid::dddiiS1immii
2atee/oorruddddSS-gggaaeHee 1gmrxHFvB
Lunjia Hu, Inbal Livni-Navon, Omer Reingold, and Chutong Yang. Omnipredictors for constrained optimization. arXiv preprint arXiv:2209.074633, 2022. URL httpss//:///oi org. prg//0...r 48550/ arXiv. 2749307463
Sham Kakade and Dean Foster. Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences, 1151)0 2008
Archit Karandikar, Nicholas Cain, Dustin Tran, Balaji Lakshminarayanan, Jonathon Shlens, Michael C Mozer, and Becca Roelofs. Soft calibration objectives for neural networks. Advances in Neural Information Processing Systems, 34:29768 297799. 2021.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering:
Auditing and learning for subgroup faimesss arXiv preprint arXiv:1711.05144 2017.
12

---

Meelis Kull, Telmo Silva Filho, and Peter Flach. Beta calibration: a well-founded and easily implemented improvement on logistic calibration for binary classifiers. Artificial Intelligence and Statistics, pages 623-631. PMLR, 2017.
Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks from kemee mean embeddings. In International Conference on Machine Learning, pages 2805- 2814. PMLR. 2018.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in neural information processing systems, pages 6402-6413, 2017.
Zhou Lu, Hongming Pu, Feicheng Wang. Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
David JC MacKay. Probable networks and plausible predictions-a review of practical bayesian methods for supervised neural networks. Network: computation in neural systems, 6(3):469, 1995.
Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. Advances in Neural Information Processing Systems, 34:1 1021156821115 15694, 2021.
Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip Torr, and Puneet Dokania. Calibrating deep neural networks using focal loss. Advances in Neural Information Processing Systems, 33:15288-15299, 2020.
Preetum Nakkiran. Towards an empirical theory of deep learning. PhD thesis, Harvard University, 2021.
Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint
2017.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the 2014. Alexandru Niculescu-Mizll and Rich Caruana. Predicting good probabilities with supervised learning, In Proceedings of the 22nd international conference on Machine learning, pages 625-632. ACM, 2005.
role of implicit regularization in deep learning. arXiv preprint
OpenAl. Gpt-4 technical report, 2023.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
John C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In ADVANCES IN LARGE MARGIN CLASSIFIERS, pages 61-74. MIT Press, 1999.
Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research, 1883)22387-2422, 2010. URL http://jmll wwtpg/papprrs//////rialaaa...a html
Lee Richardson and Taylor Pospisil.
Why model calibration matters, and how to
measure it, 2021. URL httph: h/www. www.fff.ccllooggleeaaaccc.eeeeee cwm comm2021/04/
html
Leonard J. Savage. Elicitation of persomal probabilitic, and expectations. Journal of the American
Statistical Association, 66(336):783-801, 1971. doi: 10. 110.008000662445999971.11000
URL
Mark J. Schervish. A general method for comparing probability assessors. The Annals of Statistics,
17(4):1856 1879, 1989. doi: (0.12/1//ss/ 17633333.. URL. httpt::tt///tt /ttees//ddooooee wog.ooooooo..... 1214/ aos aos/1176347398
13

---

Emir H. Shuford, Arthur Albert, and H. Edward Massengill. Admissible probability measurement procedures. Psychometrika, 31(2):125-145 1966. doi: 10.1000/BBF0228950.. URL https //doi.org// 100//002000//8/228955333
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequenee functions? arXiv preprint arXiv:1912.10077, 2019.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In Icml, volume 1, pages 609-616. Citeseer, 2001.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probabil- ity estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694-699 ACM, 2002.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Ding- Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787-794, 2020.
14

---

A Additional Related Works
Calibration without Bayesian Modeling. Our results show that it is formally possible to obtain cal- ibrated classifiers via pure loss minimization, without incorporating Bayesian priors into the learning process. We view this encouraging for the field of uncertainty quantification in machine learning, since it shows it is possible to obtain accurate uncertainties without incurring the computational and
conceptual overheads of Bayesian methods [Abdar al. 2021 Graves 201 2016
MacKay 1995 Gal
Calibration Methods. There have been many methods proposed to achieve accurate models that are also well-calibrated. The classic two-stage approach is to first learn accurate classifier, and then post-process for calibration (via e.g. isotonic regression or Platt scaling as in Platt [199). Zadrozny and Elkan [200T] 2002]. Niculescu-Mizil and Caruana 22005). Recent papers on neural networks also suggest optimizing for both calibration and accuracy jointly, by adding a "calibration regularizer" term -nnuuuucccnnnuginnnggg objective function [Kumar et al., [2018] Karandikar et al. 2021]. In contrast, we are interested in the setting where mossmmiiimization happens to yield calibration "out of the box", without re-calibration. There is a growing body of work principled measures
to the standard
of calibration [Kakade and Foster 2008 Gopalan et al.) 20226] Blasiok et al.) 2023b]. which we
build in our paper. [Claréé et al. 2023a analyze calibration for empirical risk minimization and
highlight the role played by regularization.
Multicalibration. There has recently been great interest in generalization of calibration known as multicalibration [Hébert-Johnson et al. 2018), see also Kearns et al. (2017]. motivated by algorithmic fairness considerations. A series of works explores the connection between multicalibration and
minimization of convex losses, through the notion of omniprediction [Gopalan et al. [022al 2023a b Hu et al. 2022 Globus-Harris et al. 2023 A tight characterization of multicalibration in terms of squared loss minimization presented in Gopalan et al. [2023b], which involves novel notion of loss minimization called swap agnostic learning. Another related result is the recent work of Blasiok et al. 2023a which shows that minimizing squared loss for sufficiently deep neural nets yields multicalibration with regard to smaller neural nets of a fixed complexity. This result is similar in flavor since it argues that lack of multicalibration points to a good way to reduce the loss, and relies on the expressive power of DNNs to do this improvement. But it goes only in one direction. Our results apply to any proper loss, and give tight characterization of calibration error. We generalize our results to multicalibration in Appendix F
B Miscalibration Example from Logistic Regression
Figure 2 gives an example of a 1-dimensional distribution for which logistic regression (on the population distribution itself) is severely mis-calibrated. This occurs despite logistic regression optimizing a proper loss. Note that the constant predictor fxx = 0.5 perfectly calibrated this example, but logistic regression encourages the solution to deviate from it in order to minimize the proper cross-entropy loss. Similar examples of logistic regression being miscalibrated are found in Kull et al. [2017).
C Post- post-processing Gap for Cross Entropy Loss
Here we show that directly replacing the squared loss in the definition of post-pracessing gap (Defini- tion (.2) with the cross-entropy loss does not give similar result Theorem [.4] Specifically, give an example where the smooth calibration error of a predictor is small but the post-processing gap w.r.t. the cross entropy loss can be arbitrarily large.
We choose X' = {wo, } and let D be the distribution over X x {0, 13 such that the marginal distribution over X' is uniform, E(n.y))D [æ| = æ 0.1 and E ((ra))=l( [Iy 21] 0.9. Consider predictor ʃ X' - [0, 1] such that f(xo) = e and f(z) = 1 for some E (0, 0.1). As - 0. it easy to verify that smCEx(f) + 0.05. However, the post- post-processing gap w.r.t. the cross-entropy loss tends to +oo because ((1,)) = f(0, 1 E) + +oo as + 0 for the cross-entropy loss f.
15

---

Distribution Regressor
Reliability Diagram
1.00
1.0 f(x)
pix g- o)
p(x y 1)
f(x logistic reg.
Bly f(x))
0:5
0.50
0.25
0.00
0.00
0.25
0.50
0.75
1.00
f(x)
Figure 2: Logistic Regression can be Miscalibrated. We illustrate a 1-dimensional distribution on which logistic regression severely miscalibrated: consider two overlapping uniform distributions, one for each class. Specifically, with probability 1/2 we have y = 0 and Unif([-3, 1]), and with the remaining probability 1/2, we have y = and x Unif([-1,3) (,) This distribution is shown on the left, as well as the optimal logistic regressor f on this distribution. In this setting, the logistic regressor is miscalibrated (as shown right), despite logistic regression optimizing proper loss. Note that the constant predictor f(z) = 0.5 is perfectly calibrated in this example, but logistic regression encourages the solution to deviate from order to minimize the proper cross-entropy loss. Similar examples of logistic regression being miscalibrated are also found in Kull et al. [2017]
D Tight Examples
We give examples showing that the constants in Theorem 2.4 and Corollary 2.7 are optimal. Specifically Lemma D.I shows that the constants in the upper bound of pGap in Theorem 2.4 are optimal, whereas Lemma D.2 shows that the constants in the lower bound of pGap are also
optimal. Lemma D.3 shows that the constants in the upper bound of pGap (w.1/4) in (3) are optimal.
Lemma D simultaneously shows that the constants in the lower bound of pGap (sh.1 ( in and
the constants in 44) are optimal.
{ao, æ1} be set of two individuals. For every E E (0. 1/4). there exists distribution D over X x {0, 1} and a predictor X - [0, such that
Lemma D.1. Let X
pGapp(J) - - whereas smCEn(J) =/22 e²
Proof. We simply choose to be the uniform distribution over ((ru, 0), (x1, 1)}. and we choose
f(zo) = 1/2 E and (x1 = 1/2 e. For any 1-Lipschitz function [0, - [1,, we have
(E(.,))D(( ly f(=))((()))( = - (1/2)
<)n(f(x:))
=
-)
Clearly, the supremum of the above quantity is e/2 x² which is achieved when (n/11/ m[1/2 = 2s. Therefore,
smCEp 8/2 -
For any predictor 8' X [0, 1] and the squared loss l, E(..y)~D f fx)) -
1 (())
(x 1)
When f((x = f(x) + (f((x) for a L-Lipschitz fwnction 7 |0,1] + [-1, 1]. the infimum of the
above quantity is achieved when +
0 and f'(x))-'((m) = 4s, and the infimum
(1/4)(1 2 P. If we choose f = instead, we get (((. (1/4)(11 -2 Therefore,
pfapp(f) (1/4)(1 - 2z)² -1)) = - -
16

---

Lemma D.2. Let X' = {zu) be set consisting of only single individual To- Let D be the uniform
distribution over X {0, 13 and for = E (0,1/2), let f X - [0, 1] be the predictor such that
f( 1/2 2 8. Then
(f) = = whereas smCEp(f) =E
Proof. For any 1-Lipschitz function n, [0. [-1.1].
((x,)>>Dly - [())) = e1n(1/2 2 +
The supremum of the quantity above over 7 is clearly E, implying that smCEp(f) c. For any predictor f" + [0, 1] and the squared loss E,
B(x,)) (' (1/2)(0- (2(2)))2 (1/2)(1 (()))))
= fx()) - (xx) +1/2
= 1/44 (f( - 1/2)2.
The infimum of the above quantity over function f' : :'' - [0. 1] satisfying f'(x) = (ff
for some 1-Lipschitz 7) [0. 1] + [-1, clearly 1/4. we choose f insteadd, we get B(xa)))(((()) f (x))] = 1/4 =². Therefore,
(Ga
- 1/4= -
Lemma D.3. Define pGap (v.1/4) and smCE as in Definition 2.5 and Definition 2.6 for the cross-entropy loss. Let X' = {zo, Φ1} be set of two individuals. For every E E (0,1/4), there exists distribution D over X {0.1) 1) and function 9 X + R such that
pGap (#.1/4) (g) 2 2e + O(a²), whereas smCE ()) = O
Proof. We simply choose D to be the uniform distribution over {(ro, 0), (z1, 1)}, and we choose g(xn) -4 and ((x) 4c. Let denote the sigmoid transformation given by (tt) e² ce/(11 + e²). The Taylor expansion of the sigmoid transformation a around / 0 is (1) = 11/2 O Thus the predictor ʃ we get from applying a to g satisfies f(x1) [(2o) = 1/2 For any
1/4-Lipschitz function 7) R + [-1, 1], we have
E(z,g)~Dly f(=)))(((z)) (1/2)
-1/22) (1/))
(1/2)(1 (())))(()))
(1/2)(1 - -(oo))
< (1/2)(1 - ((=))))((=0-)(())))]
$ (112))1/2++05) (8e)
=
This implies that smCE (1)1)) (g) S 8/2 0
For any function g' X + R and the logistic loss E(1),
E(rx))-((()))
((()) (g.g (z)) (1/2) In + e (vo)) (1/2) (112))n(1111) In ed - (z1))
(1/2) In(1 e (#0) + (1/2) In + fellee (x(())))
We use the Taylor expansion In(1 + = 1/2 ( to get
B(eay (v, (x)) ln2 + (1/4) - (c + Old' +
(9)
Consider the case when g (zo) 88 and g'(x)) = 88c Clearly, s' can be written as g'(x)
g(x) + v(((z)) for i-Lipschitz function 1) RR - (44.4]. By (9. the expected loss achieved by g'
L( (v.9 (x)) = In - 4e O
If g' =g instead, the expected loss is In 2: ( Taking the difference between the two, get
(.114) (g) > 25 + +(s3).
pGap
17

---

Lemma D.4. Define pGap pGap as in Definition for the cross- pross-ntrrppy loss. Let X = { be set consisting of only a single individual zo. Let D be the uniform distribution over & x {0,1) and
for E 122), let g X - IR. be the function such that g(zo) = 4e. Then
pGap A (g) = 2s² + O(E²), whereas
(/.1/4)
= smCEo(/)=
where f . + (0, is given by f(x) (lg(z)) the sigmoid transformatiinn a (1) = e e (1+e)).
Proof. The Taylor expansion of a around t = 0 is (t)) = +/4 0(t)). Thus f(0o) = (g((z)) 1/2 + O For any 1-Lipschitz function 17 [0, [0.1]-11-11 1-1111]
[[r,,)>> (y - [(x))(((=)) = ((0(a((())((((()))))))) = + (ft)))
The supremum of the quantity above over r is clearly O( implying that smCEp(f)
& + O(e*).
For any function g' :x [0, 1] and the logistic loss ((0))
(( (((0)) (g.g) (z)) In(1 + o (2o)) (xo)) (1/2)g (zo)
(10)
= =In(e (20)/2 + +e - - (2
The infimum of the above quantity over a function g' X - R satisfying g (z) g(x) + (()())) for some 1-Lipschitz 17 R + [-4, 4] is In2 achieved when g g0(0) = If we choose g' = instead, we get E(2,))) (((V) (y, g g(x))]
In + 28² + O(s*) by plugging the Taylor expansion
In(1 + = 2n + 1/2 + 8/ + Ott*) into TTP. Therefore,
pGap (w)1/4) (g) = 2=" + O(E))
E Proper Loss and Convex Functions
It is known that there is a correspondence between proper loss functions and convex functions (Shuford et al.) 1966 Saavage| 1971 Schervish 1989 Buja et al. 2005). Here we demonstrate this
correspondence, which is important for extending the connection between smooth calibration and prst-processing gap (Theorem 2.4p to general proper loss functions in Section 4
Definition E.1 (Sub-grate bib-ggradeent. For a function ip : V + R defined on V R. we say E R is
sub-gradie gradient of p at U E if if
p(v') 2 ((u) + (v' - b)t for every v' E EV,
or equivalently,
((v)= max (u't- ((1))
(11)
v'EV
Definition E.2 (Fenchel-Young) divergence). For a pair of functions ip : V R and vb : T I defined on V,T C R. we define the Fenchel- Cenchel-Young divergence Dip. : V x T + IR such that
(v, = p(u) + (t)) - et for every u E V and E T.
The following claim follows immediately from the two definitions above.
Claim E.3. Let vp V + R and : T R be functions defined on V,T C R. Then T is sub-gradient of sp at v E V if and only if Di 1) min Do (v', 1). Similarly, is a suu-ggradde gradi-ra of ii
if and only if D (v. = minger er D (v,((,.t)) In particular. assuming (1,, t') 2 frror every v' E V and t' E T whereas D.,,, t) = for some E V and t E T, then is sub- gradient of yp at v, and
a sub sub- gradient of ú
Lemma E.4 (Convex functions from proper loss). Let V C [0. be non-empty interval. Let E: (0, 1) x V +R be a proper loss function. For every u V. define dual(v) ((0, {(1,
There exist convex functionn ip V + R. and vb IR. + R such that
(y,,v) = (duul(v)) y dual(u)
for every y E (0, and v E V, for every v E V and E R, for every E..
(12)
(v, 2 0
(13)
D Dp dual(v)) (ual))) =
(14)
(12) (11)
0 < t/2 t
<
for every distinct 11, E IR.
(15)
18

---

Before we prove the lemma, we remark that (2) and 14
together imply the following:
fly v) =-(() (w y)dual(e)
for every y E [0, and v E V.
Proof. Any loss function e: {0. 1 x V - R. proper or not, can be written as Ely, v) = E(0, v) y (u).(v). When é is proper, it is easy to that for v, o' E V with dual(v) dual(c'), holds that ((0, v) = f(O, o'); otherwise, fly, v) is always smaller or always larger than E(y, v') for every y E {0, 1}, making it impossible for to be proper. Therefore, for proper there exists v/n T - IR such that E(0, v) (o(dual(v)) for every E V, where 7 == (dual(v) E V). Therefore.
f(y. v) ((0,,) v) ydaa(()) 2/o (dual())) dual(()).
(16)
By the assumption that is proper, for every v E EV.
argmin V'EV yerBer(t)
E
((v, = argmin (vo(dual(o')) dual(r")). e'EV
and thus
dual(e) E argmin (o(()) - vd) EE
For every E V, we define
p(v) == (ual(v) (do(uua())) max
vt - vo((t)
tET
The definition of & immediately implies the following:
Davva (u, t) 2
for every E V and t E T for every V.
(17)
D P.. (v. dual(v))
(18)
By Claim E.3 dual(v) is a sub-gradient of y at v. This proves that is convex. Now we define
+ I such that (t) w
(p() for every
R. This definition ensures that
inequality (3) holds. By Lemma H.3 th is convex function and (15) holds. Moreover, for
every E V. we have shown that dual(u) is sub-gradie grbdiert of yp at u, so by (IT). (ddual(v))
(ual(v) (pu))= = (P((dal(e)). This implies that (12) and (14) hold because of (16) and (18). O
Lemma F.5 (Proper loss from convex functions). Let V S. [0, 1] be non-empty interval. Let
p V TR, TR TR. and dual - TR. be functions satisfying 13) and 14 Define loss
function & {0, x x
in 12 Then
1. E is proper loss function;
2. &p is convex;
3. for every v e V, dual(v) is sub-gradient of up at v. and v is sub-gradient of ib at dual(v);
4. pp()) e dual(u) v(dual(v)) = Ey--Be(()) [f(y, v)];
5. if we define (t(() sup (vt v(u)). then v/ is convex and v (dual(u)) = & (dual())) for every v E V. Moreover, for any two distinct real numbers 11,
3 (12) - (41) -1
0 <
(19)
t2 t
Proof. For every u E V. equations 133 and
imply that
dual(u) v) E argmin (v)t) - ut),
tER
and thus
E argmin (u(dual(oo)) dual(
argmin E E(y, v²).
e'vv
V'EV y>BBe(())
This proves that L is proper (Item D Item follows from
133 (4p and Claim E.3 Item 2 follows
from Item 3. The first equation in Item follows from 14 and the second equation follows
from 112 For Item 5] the convexity of o and inequality
19 follow from Lemma H.3 and
g/ (duul(())) = (b(uaal( holds because w (dual(u)) dual (p)) by Item and and
(d) = dual(()) (o() by Item
19

---

Our discussion above gives a correspondence between proper loss function E: {0, x V + R and a tuple (y,, 4,, dual) satisfying (13) and (14). By Lemma E.5 yp, vp and dual satisfy B and (14), then every u E V is a sub-gradient of 1/ at dual(v). Therefore, assuming do is differentiable and using Vap: RR- - R. to denote its derivative, if dual(v) for some E V, then we can compute from t by
(t)(t).
(20)
For the cross entropy loss fly, v) y Inv - (1 - y) 1n(1 - v), we can find the corresponding
sp 4) dual and g(v) (see Definition 4.3 as follows:
(0() y>~Ber(o)
[K(y, v)] vlnv (1 v) 1n(1 v),
dual(1) ()) E(0, v) - (11, v) 1n(v/(1-1))
(t) = sup (ul ((v)) -In(1+ + +e').
=E(0.1)
g (y. t) = (t)) - yt = In(1 + =² - yt,
(logistic loss)
Vei(t) = e' e'/(1+ + e²).
(sigmoid transformation)
For the squared loss Ely. u) (y =) can find the corresponding i 19, dual and (00) follows:
(0v) B))) [C(y, v)] uu( u)² (1 r)v² v(r 1),
dual(u) = ((00 v) - (11, v) 2x 1 1,
0,
ift < -1; if -1 if 1.
(t) = sup (ut - p(()) = vE(0.1]
(L + 1)3/4,
1,
yt,
ift<-I.
(v. 1) = (()) - yt- =
(y - (I + 1)/2)2,
if - 1 $1 1.
(11 - y)t,
00 Vv((t) = (t + 1)/2,
if < -1; if - 1t
1.
ift> 1.
For the squared loss, one can alternatively choose (t)) = (t + 1)2/4 for every t E R and accordingly define g(+)) (y. t) = (y- - (t + 1)/2)² for every y E {0, 1} and t E RR This still ensures [2] and
(14) but 115 no longer holds.
F
Generalized Dual (Multi)calibration and Generalized Dual Post- Gap
Below we generalize the notions of dual post- pest-processing.g gap and dual smooth calibration error from Section[4]y replacing the Lipschitz functions those definitions with functions from general class. Here we allow the functions to not only depend on the dual prediction g(z), but also depend directly on x. With such generality, the calibration notion we consider in Definition F.2 below captures the notion of multicalibration (Hébert-Johnson et al.) 2018). We connect this generalized calibration notion with a generalized notion of post-processing gap (Definition F.T. in Theorem F:3
Definition F.1 (Generalized dual post-processing gap). Let ta and ((w) be defined as in Definition 4.3
Let W be a class of functions w : X' x IR + R. Lei 'D be a distribution over X x {0, 1}. We define the generalized dual post-prosee poot-processing gap of a function g: : X + R w.E. class W and distribution D to be
(y) gen (enGap(y. (v,W) == E(z.a)= ( (y. g(x)) inf B(..y)= (y. w(z, g(x))).
Definition F.2 (Generalized dual calibration). Let : R + R be a differentiable function. For function g: X + R. define predictor f X - R such that f(x) Ve(((z)) for every x Let
'It is possible here for f f(r) to lie outside the interval [0, 1J. in which case f is not valid predictor. However. if eh satisfies 15). then Vvb(t) [0, 1] for every i E IR and thus f(x) E [o, for every X. Also,
20

---

W be class functions w X X - R. Let DD be distribution over X {0, 1}. We define the generalized dual calibration eπror of g w.T.I. class W and distribution D to be
genCED (V,WW) (g) wew [E (v (xx)))o( (xx))]l-
Theorem F.3. Les vb + R be a differentiable convex function. For X > 0, assume that v is
X-smooth defined in (8) Let W be class of bounded functions X x I + [-1, Define W' to be the class of functions w' X - IR such that there exist w E W and 1-1/,,1/M satisfying
w'(x, 1) = + Bw((x,) for every x E X and E R. Then for every X - R and any distribution D over X x {0, 1},
senCE(s:))/ (g)²/2 < X AgenGapp ( w.. (g) S genCE ( (g).
Proof.
By the definition of g(+) in Definition 4.3
IE (v)
(y, g(x))(()))))))))))))
E
(y. (2,
(2.0)~D
Elv(o(x)) -)(())))))(()) (w' (x,) + (x
E[((((x)) (w,' (x=)((()))))))))))))))))())))( + yBw(x, (())]
(21)
By the convexity of 3 and the X-smoothness property, for every t, E ER,
V(((((( - 1) v(() +0(1) J." (T((T)dr
J. (Ve(t) + - ()) Vv((t((t -t) -
2 (t' (t'' tt²². (22)
For a E X, setting l to be g(x) and setting l' to be w' g()))(())) = g(x) + (wo(x,9(1)) for some
E W and (-12, A/),, we have
- t = (x. g(x))( - g(z) = Bw(z,g(z)).
Plugging this into
22 and defining f(x) = Vv(g(z)) = (t)(t), we have
A/2
(x) (())) S (/ (a, g(x))((()))))))))))))))) ((g(=)) S (1))) ((x)) +
2 -w(r,g(())²
Plugging this into 21 and using the fact that (wo g(x)) $ 1, we have
2
Bl(y - ((x))
2
E giv) (v.
E (a.))D
gl (y, (v,w((x,
(23)
(.,0)D
El(y f())
(24)
For any E W, choosing
3 El(y - (I))))( and choosing w' E W such that
w (I, t) = t Bu (), by
23 we have
El (F)))(( <
E (w.y)~
(v.
E (a.y)~
e (y, (y, (z,g(x))).
21
This proves that
genCE () (g) < X ggenGap (v.W") (g)
D
For any w' E W', there exists 3 E 1-1A,, and w E W such that (xx 1) = 1 + -Bw(a, 1). By
24
E
(lv) (v.
g (y,w'(x,
(R.0)>
Elly - (())
(1/A) (x)))x(z.
This proves that
X AgenGap W ('(())
(g) - genCE (g).
start from valid predictor f X + [0, 1] and define g(æ) d=))( By Lemma E.5 this ensures that f(x) ve(g(x)) assuming that (p, vt, dual) satisfy (13 and [4
21

---

F11 Proof of Theorem 4.6
We restate and prove Theorem 4.6
Theorem 4.6. Let up R - IR be differentiable convex function with derivative (i)(t) [0, for every RR For X O, assume that v X-smooth, i.e.,
[b(()) - Vv((()) S Alt 1it-t) 1'| for every 1, R.
(8)
Then for every : X + R and any distribution DD over X x {0,1),
smCE (g)2 - ApGapp (v.A) () (g) S smCE (..A) (g).
Proof. Let W be the family of all X-Lipschitz functions 7 R + [-1, 1]
and define W in
Theorem E.3
We have
genCED (w.W) genGapp (#.W") (1. (g).
(g) = smCE (1. (g),
D (g), and
(g) = pGap (19.A)
Theorem then follows immediately from Theorem
F.2 Proof of Lemma 4.7
We restate and prove Lemma
Lemma 4.7. Let tb IR - R be differentiable convex function with derivative Vvb(() E 00 fo every & RR. For X 0, assume that vé is X-smooth in (8. For g = X R, define X (0, 1]
such that ((x Vvb((())) every x E X. For a distribution 'D over x {0, }. define smCE (
in Definition 2.3 Then
smCEp(f) & SmCE (8).A) (g). D
Proof. For L-Lipschitz function [0. + [-1, define n/ R - [-1, 1] such that (/()) (t)((t)) for every t I.. For 4,to R, by the X-smoothness property of 77. (11) - 7/ (t2) = (t,)) - vVV((t2)) & (Vp(tt) V1b(t2) s A/t, - 12l-
This proves that 7/ is X-Lisschit. Therefore,
[Et..g>DD(1 f=)))(((((( = B(ay))Dl f(=))) smCC sm Taking supremum over 1 completes the proof.
G Optimization Algorithms Which Achieve Calibration
Continuing the discussion of structural risk minimization in Section [5] here we describe additional families of learning algorithms which explicitly minimize loss, but implicitly achieve good calibration.
G.1 Iterative Risk Minimization
One intuition for why state-of-the-ee art DNNs often calibrated is that they "locally optimal" (in our sense) by design. For a state-of-ther network, it were possible to improve its test loss significantly by just adding layer (and training it optimally), then the human practitioner training the DNN would have added another layer and re-trained. Thus, we expect the network eventually produced will be approximately loss-optimal with respect adding layer, and thus also with respect to univariate Lipshitz post-processings (so pGap 2 0).
This intuition makes several strong assumptions, for example, the practitioner must be able to re- train the last two layers globally optimally However, the same idea can apply in settings where optimization is tractable. We give way of formalizing this via the Iterative Risk Minimization algorithm.
We work with the following setup:
'Technically, we only require a weaker statement of the form: For all networks fa of depth d in the support of SGD outputs, if the loss of fa is then training network fat1 of depth d + will reach loss most
22

---

We are interested in models f E FF with complexity measure μ F - Z. Think of size for decision trees or depth for neural nets with a fixed architecture. We assume that F contains all constant functions and that p(c) 0 for any constant function c.
We consider post-processing functions x : [o, 1] + [0, 1] belonging to some family K, which have bounded complexity under μ.. Formally, there exists b b(K) Z such that for every f E F and & K,
p(k f) S p(f) +6
We have loss function & 10, R + + Let (f.D)
E
f(.
(..v)~>
For any complexity bound we have an efficient procedure Minp(s) that can solve the loss minimization problem over models complexity 8:
min
((f.D).
fEF
a())
The running time can grow with s. For each E, let OPT, denote the minimum of this program and let f denote the model found by Minp(s) that achieves this minimum.
We use this to present an algorithm that produces a model f which is smoothly calibrated, has loss bounded by OPT,, and complexity not too much larger than
Algorithm Local search for small pGap.
Input 8g-
Sg-
while True do f Min(s)
Min(s + b).
OPT 2 OPT, a then
Return fr.
else
h h 1.
8
+ s
end if
end while
Theorem G.1. On input 80, Algorithm which satisfies the following guarantees:
Terminates in h S 1/a steps and returns a model f E F
1. u(f) = + hb.
2. (2,, D) OPT, < OPT ho.
3. pGap(f) < a, hence smCE(J) S Va.
Proof. The bound the number of steps follows by observing that each update decreases (f D) by a. Since OPT. < OPT, < 1, this can only happen 1/a times. This also implies items (1) and (2), since each update increases the complexity by no more than 6, while decreasing the loss by at least a.
To prove claim (3), assume for contradiction that pGap(f) a. Then there exists K such that if we consider f k o then
Sf+) b, &2(f < OPT, a.
But this f provides certificate that
OPT.4 S lo(f D) < OPT; a.
Hence the termination condition not satisfied for f. by contradiction, must hold that pfap(f) & hence smCE(f) Va.
D
23

---

We now present an alternative algorithm that is close in spirit to algorithm [ but can be viewed more directly minimizing a regularized loss function. We assume access to the same minmization procedure (s) as before. We define the regularized loss
Df. = ((f.D)+ Au(f).
quantifies the tradeoff between accuracy and model complexity that we accept. In other words, accept increasing μ(J) by if it results in a reduction of at least in the loss.
Algorithm 2 Regularized loss minimization for small pGap.
[1/2]. while E {0. ... .r] do
f Min(s).
OPT, + (fz;,2)) D). end while t 4 argmin s (o....rr) OPT, As.
Return ft.
Theorem G.2. Let X = b/b. Algorithm returns a model f with p(f) = t [1/\] where
1. f argmin e (f', , D) and Ez(f. D) -PT,,
2. For any +
OPT, 2 OPT, - t)A
3. pGap(f) S a, hence smCE(f) S Va.
Proof. We claim that
min (*',, 1 PEF
This follows by taking the constant 1/2. which results in (0, D) < and μ(f) = 0. This means that the optimum is achieved for f where μ(f) s 1/x. For f such that u(f) S it is easy to see that Algorithm 2 finds the best model.
Assume that * t. By item (1), must have OPT, + S OPT, + As
Rearranging this gives the claimed bound.
Assume that ff a' a. Then there exists f' x(f) such that μ(f) s u(f) + b, but ((', (2 a'. But this means that
(()) = E(f', + Ap(s") S Ee(,DD - a' + N(H(F) +b)
=f( + (Ab-a')
<E)(f)
where the inequality holds by our choice of À = a/b. But this contradicts item (1).
Note that if we take matching Item (2) in Theorem G. The difference that we now get bound for any * When > I, item (3) upper bounds OPT, OPT, which measures how much the fg loss decreases with increased complexity. When s < t, OPT, > OPT, and item (3) lower bounds how much the loss increases when shrink the complexity of the model.
hb, then (s 0)A ha, so Item (2) in Theorem G.2 gives statement
Importance of depth. These algorithms highlight the central role of composition in function families. Specifically. if we are optimizing over function family that is not closed under univariate Lipshitz compositions (perhaps approximately), then we have no reason to expect pfap(f) ~ 0: because there could exist simple (univariate, Lipshitz) transformation which reduces the loss, but which our function family cannot model. This may provide intuition for why certain models which preceeded DNNs, like logistic regression and SVMs, were often not calibrated. Moreover, it emphasizes the importance of depth in neural-networkss depth is required to model composing Lipshitz transforms, which improves both loss and calibration.
Discussion:
24

---

G.2 Heuristic Structure of SGD
Finally, there an informal conjecture which could explain why certain DNNs in practice are calibrated, even if they are far from state-of ofate-of-the-art, Informally, if it were possible to improve the loss by simple update the network function prost-procsssing), then one may conjecture SGD would have exploited this by the end of training. That is, updating the parameters from computing "simple" update for SGD on deep-enough network,
the function f to computing (N o f) may and SGD would not leave this gain on the table by the end of training. We stress that this conjecture informal and speculative, but we consider it a plausible intuition.
H Helper Lemmas
Claim H.1. Let m,, 72 [0.1] R be two 1-Lipschitz, functions. Then max(m (v), na(v)) and (v), are also -uiipschitr,uunciions of V E [O, 1].
Proof. Fix arbitrary v, o' 1). Let i, E [1,2] be such that max(n (2), mn(()) and max(m (v'), v2(")))) = n2 (v"). .. We have
max(m (v), (u)) - max(n (v'), m2((0)) 2 (w) (0(() 2 -1u- 0'1, and max(m) (v), (2))) max(m (2)) S ())) - (v)) s 2/
This proves that mmx(m(v) v2(1)) is 1-Lipschitz. A similar argument works for min(m (v), n2 (v)).
Lemma H.2. Letry: : 1| 11,1|--11,11 be a I-Lipschitz, function. Define K : [0, 1] - 10, 1] such that <(v) = ur (o-n(()))))) every E [0, 1]. Define n/ [0, 1] + [-1, 1] such that 17 r1(v) = k(v) for every [0, 1]. Then n/ is 1-Lipschitz.
for
Proof. By the definition of ni we have k(v) = min(max(U + ((v).0), 1). Therefore, n)( min(max(17(v), -t), u). The lemma is proved by applying Claim H.l twice.
Lemma H.3. Let V S (a, b) be non-empty set. For some R, let yp V + [m, +00) be function lower bounded by m. Define vb : R + R such that (b(t) = sup ut p(u)). Then s is vv
convex convex function. Moreover, for t < 12, we have
all2 41) S (12) v((1) b(122 - -1).
Proof. For any E [0, 11, f1, 12 E R. and v E V,
v(pt1 + +1 - p)) - (v)) = p(ut - pv()) + (1 - (ut2 p(()) S pb(tz) + (1 (1-
(1-)))((ta) (t2)
Taking supremum over e V, we have
(pt + p)t2) (t)) + (1 p)2)(t)).
This proves the convexity of vb. Moreover, if (1, la E R. satisfies t < 12, then for any E V.
v4 ((u) = v/2 (pv)) + v(4 - (2) S 0l2 =(v) a(l - (2) S (b22)) al12 - 41).
Taking supremum over v V, we have
v(41) S (12) + alti - t2).
Similarly.
ut2 - (pp) = utj :p()) + utt2 (1) < pt p(v) + b(t2 - -1) < ((4))))(++(()))))
+ b(tz 61).
Taking supremum over v E V, we have
((t2) S ((1)) + b(tz - t1)
25


Reviews:
[{"review_id": "6ZXvdSciIo", "reviewer": "Reviewer_PVPP", "summary": "This paper seeks to explore and formalize the relationship between minimizing proper loss and calibration in machine learning models, particularly deep neural networks (DNNs). It presents a local optimality condition that is necessary and sufficient to ensure model calibration. The work discusses the implications of these findings on the calibration properties of modern DNNs and presents algorithms that can guarantee calibration. The paper also contrasts the differences in calibration between current and previous generation models through the lens of generalization.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "NA", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback!"}, {"review_id": "f4wxZf1qup", "reviewer": "Reviewer_6rky", "summary": "The paper provides a novel characterization of calibration as local optimality of the predictor w.r.t the global loss under post-processing of the prediction through a class of functions. The paper proves that any predictor satisfying such a condition is smoothly calibrated in the sense of [Kakade and Foster, 2008, Błasiok et al., 2023] and vice-versa. The paper further provides arguments for why such a condition should be satisfied by Deep Neural Networks (DNNs).", "questions": "- What are some complexity measures satisfying the condition in Claim 4.8?\n- What are the limitations of the definition of smooth calibration error used in the paper, especially in the context of deep neural networks?", "limitations": "Yes, the limitations have been adequately addressed. The work is theoretical in nature and does not have direct societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper is well written, with a clear structure and ideas being developed in a coherent and logical sequence.\n- The topic is of large importance in the present context of research in machine learning and has numerous implications for practical applications.\n- The authors contribute a novel perspective on the 'implicit' calibration of machine learning models without the use of algorithms designed specifically for calibration, an aspect that is not extensively explored in current literature. \n- The explicit characterization of calibration in terms of local optimality under post-processing transformations, while implicit in earlier works, appears to be novel. This equivalence could be useful for further theoretical analysis of calibration, especially for deep neural networks.\n- The proposed framework is general and does not rely on specific choices of model's architecture or data-distribution.\n- The paper provides partial explanations for the observed calibration of deep neural networks trained on large training datasets.", "weaknesses": "- **Limited technical contributions**: Claim 2.1 itself directly follows from the definition of perfect calibration. The main theoretical results in the paper are generalized formulations of Claim 2.1 to smooth calibration, lipschitz-post processing functions, and general proper losses. While these generalizations themselves are novel, their proofs involve straightforward algebra and convex analysis. Therefore, the technical and mathematical contributions of the paper are limited. The results can be strengthened from examples of non-trivial results that can be derived using the local-optimality based characterization of calibration. For deep neural networks, the present results are only suggestive and would benefit from additional details and concrete results.\n- **Missing references**:\n     - On double-descent in uncertainty quantification in overparametrized models: Lucas Clarte, Bruno Loureiro, Florent Krzakala, Lenka Zdeborova, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:7089-7125, 2023.\n     - Theoretical characterization of uncertainty in high-dimensional linear classification, Lucas Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová, Machine Learning: Science and Technology, Volume 4, Number 2\n\n    The above papers analyze calibration for empirical risk minimization and like the present paper, also highlight the role played by \n    regularization. \n\n- **Dataset size and overparameterization**: The paper does not address aspects related to generalization and the effect of the training dataset size. While modern training setups utlize large training dataset sizes and one-pass SGD, their behavior in the proportional regimes of high-dimensional inputs and parameters\nis non-trivial and not equivalent to the minimization of population loss. For instance, the above papers establish a double-descent like phenomenon for calibration for varying levels of overparametrization.\n\n- **Experiments**: In light of the limited technical contributions, the paper could benefit from experimental justification of the validity of the local optimality condition for deep neural networks in realistic training setups.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comprehensive review! Here is our response to the individual comments and questions in your review:\n\n**Re. technical contributions.** A main contribution of our work is formulating the right generalization of Claim 2.1 where 1) the notion of calibration is meaningful, and at the same time 2) the post-processings can be naturally implemented in deep neural networks that are not explicitly trained for calibration. We think these contributions should be weighed more than the technical difficulty of the proofs. Indeed, we think that the reason that such statements are not found in previous literature is because the right formulation is fairly subtle – for example, until recently it was not clear how to measure miscalibration in a reasonable way (e.g. ECE is not ideal as it's discontinuous; more in our response below re. the smooth calibration error). As an “example of non-trivial results that can be derived using the local-optimality based characterization of calibration”, our Claim 4.8 identifies the types of regularization that make structural risk minimization (SRM) produce well-calibrated predictors. A key step for establishing Claim 4.8 is using our theory to reduce the problem to determining what types of regularization make the solution to SRM satisfy the local optimality condition. In particular, our Claim 4.8 reveals that regularization plays a different role in *calibration* than it does for *generalization* – it is possible to have regularizers that work for both aspects, but it is not at all necessary.\n\n**Re. missing references and the generalization aspect.** Thank you for pointing us to these papers! In our final version, we will make sure to cite them and include a refined discussion about generalization based on them. As we mention in our submission, generalization concerns are out-of-scope for our paper – we consider only optimization aspects, by considering all quantities on the population distribution. Both generalization and optimization aspects are ultimately important to consider, but our paper focuses on only the latter.\n\n**Re. experiments.** Many existing experiments in the literature have verified that many neural networks trained via loss minimization exhibit good calibration performance. We mentioned many such examples in our submission. According to our theory, these neural networks must also satisfy the local optimality condition. That is, neural networks satisfying the local optimality condition in realistic training setups is a rather general phenomenon that has already been experimentally observed. Our contribution is drawing the connection between calibration and local optimality which gives an explanation for why previous experiments observe good calibration in models trained via loss minimization alone.\n\n**Re. complexity measures that satisfy the condition in Claim 4.8.** The size of a neural network, when multiplied by a suitable constant, satisfies the condition. This is because by the universality of neural networks, a 1-Lipschitz post-processing can be (approximately) implemented by adding a constant number of neurons to a neural network. \n\n**Re. limitations of smooth calibration error.** Recently Błasiok et al. [2023] showed that the smooth calibration error is a *consistent calibration measure*. Specifically, they showed that the smooth calibration error differs by at most a constant factor from the Wasserstein distance to perfect calibration. By definition, all consistent calibration measures are polynomially related to each other, so all our results about the smooth calibration error also hold for any consistent calibration measure, up to modifying constants in our inequalities. That is, by building our theory using the smooth calibration error, our results automatically apply to the kernel calibration error with the Laplace kernel, the interval calibration error (*modified* binned ECE with the right bin width and randomly shifted bins), and the distance to calibration itself. In contrast, the popularly used ECE and binned ECE are not consistent calibration measures and are not in general polynomially related to the distance to calibration. Błasiok et al. [2023] also showed efficient algorithms for estimating the smooth calibration error. Given the consistency, efficiency, and continuity of the smooth calibration error, perhaps a downside of it is that it is not currently used as often as the binned ECE, but this may change as people become more aware of the advantages of using a consistent calibration measure.\n\n**In conclusion:**\nIf the reviewer is satisfied with our responses, and believes this paper should appear in NeurIPS, we ask that they consider increasing their score to an Accept."}, {"review_id": "o56Dr3HKs2", "reviewer": "Reviewer_ooFk", "summary": "The paper considers calibration in binary classification when training was performed with proper losses. The authors showed that\nthe post-processing gap of a predictor, which is a maximum improvement of the loss given any 1-Lipschitz update (calibration) function,\ncould be both lower and upper bounded by a simple expression of smooth calibration error. Moreover, the authors proved that the constants used in upper and lower bounds are optimal.", "questions": "1. The derived results are valid in binary classification settings. Will it be possible, and what are the possible limitations, to obtain similar results in multiclass settings?\n\n2. Could it be said that all theoretical derivations are based on properties of Bregman divergences but in a new setting connected with calibration errors?\n", "limitations": "The limitations have been covered at the end of the paper. \n\nNo need to discuss societal impact in this paper.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper describes the connection between proper loss landscapes and calibration error improvement, which is an important and quite original problem under the current formulation.\n\nThe paper has good positioning among other papers in the field, with clear references to many studies and a detailed indication of what was their contribution.\n\nThe clarity of the paper is good.", "weaknesses": "The link with potential practical application is missing (or rather not convincing). Adding small-scale experiments to support theoretical results would be beneficial, e.g. to check whether the pre-requisites of the theoretical results are (approximately) fulfilled in practice.\n\nThe discussion and explanation of theoretical results could be improved. The current impression is that either theoretical results are not that impressive (and based mostly on properties of Bregman divergence) or that the potential impact of derived theory is oversold.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback, and for recognizing our work on an \"important and quite original problem.\" We are glad the reviewer rates our soundness, presentation, and contribution as \"good.\" We are thus unsure why the overall score is a borderline reject, but we have included our response to the individual comments and questions below. If the reviewer is satisfied with our responses, and believes this paper should appear in NeurIPS, we ask that they consider increasing their score to an Accept.\n\n**Re. practical applications.** Our theory can be viewed as a bridge connecting calibration and proper loss minimization. Calibration is a desired property in numerous practical applications, but our understanding of how to achieve calibration is generally not as profound as how to perform loss minimization. Our theory allows people to apply the machinery of loss minimization to reason about calibration, and we hope that our theory will inspire better principled approaches to calibration.\n\nHere is an immediate impact of our paper to practical application. Practitioners (using sklearn for instance) are currently encouraged to believe that solely by minimizing proper loss within a restricted family of functions, they will get calibrated predictors (see the references in our paper). We show convincingly that in this generality, the claim is false. Moreover, we identify a sufficient and necessary local optimality condition for proper loss minimization that guarantees calibration. By being aware of our corrected connection between loss minimization and calibration, practitioners can avoid false confidence in a model’s calibration and eventually build more calibrated models.\n\n**Re. multiclass settings.** Our results can be extended to the multiclass setting, but such an extension is not entirely straightforward. Even the definition of calibration in the multiclass setting is subtle. In the multiclass setting, the prediction f(x) becomes a vector that assigns a probability to each class. One way to define calibration is to condition on the entire vector f(x) (canonical calibration), whereas other ways may involve conditioning on certain coordinates of f(x) (e.g. confidence calibration conditions on the maximum coordinate). How to robustly and efficiently measure the distance to each type of calibration in the multiclass setting adds another layer of complexity, and the recent work [Błasiok et al., 2023] only answers this question for binary labels. Our theory is more easily extended to canonical calibration than confidence calibration, but confidence calibration is widely used in practice. We thus leave the important but challenging question of building a complete extension of our theory in the multiclass setting to future work. We believe this is more conducive to the community than to include in the current paper an incomplete theory for the multiclass setting that may risk being misleading.\n\n**Re. properties of Bregman divergence.** Yes, as we mention in our submission, a lot of our proof techniques are closely related to properties of the Bregman divergence and the theory of convex conjugates. A major part of our contribution is formulating the right theorems to prove, which is as important as proving those theorems. We believe that by presenting our proof techniques in such a way that they appear relatively simple in retrospect, we make our paper more easily digestible and thus potentially more impactful.\n\n**Re. experiments.** See our response to Reviewer 6rky re. experiments."}, {"review_id": "LPGB9ADFFN", "reviewer": "Reviewer_5Dzr", "summary": "This work introduces a local optimality condition for models (with respect to proper losses) based on (additive) post-processing with a 1-Lipschitz function that is necessary and sufficient for calibration. The authors also connect their results to the idea of implicit regularization, showing that structural risk minimization with an appropriate class of complexity measures achieves good calibration.", "questions": "My only question is related to my discussion under weaknesses; namely how temperature scaling type methods would fit in with Definition 2.2.", "limitations": "The authors appropriately address limitations; namely, they acknowledge that their results do not explain _why_ the optimization process for current models leads to calibrated predictors.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "## Originality\nThe introduced notion of post-processing error and its connection to (smooth) calibration is novel and useful, as it proves plausible explanations for why current SOTA deep learning models are better calibrated when compared to previous generations. Additionally, the introduced local optimality condition based on post-processing is distinct from conditions seen in optimization, but remains non-trivial since the class of post-processing functions is restricted to be 1-Lipschitz.\n\n## Quality\nThe paper is technically sound and polished; the definitions are well-motivated and simpler results are accompanied with proofs (or at least intuitive justification) in the main body of the paper.\n\n## Clarity\nThe theory is easy to follow, and the authors have done a good job of scaling the complexity of the results as the paper progresses (introducing simple examples and high-level ideas first, and generalizing later). The authors also qualitatively connect their results to recent empirical phenomena in deep learning, which is helpful for grounding the theory.\n\n## Significance\nCalibration is an increasingly important problem, and the paper provides insights into how to think about the relationship between calibration and post-processing procedures.\n", "weaknesses": "- *Experiments:* While I understand this is a theory paper, I do think it would be nice to have some experimental analysis of whether the local optimality condition is satisfied for modern architectures (i.e. simply adding an extra layer as suggested in the paper and analyzing calibration performance).\n- *Addressing Popular Post-Processing Methods:* If I understand the discussion around Definition 2.2 correctly, the post-processing operation defined does not include temperature-scaling-type techniques, since $f(x)$ includes the sigmoid operation and one would have to apply the re-scaling to the logits. If this is not the case, some clarification in this section linking the post-processing definition back to the standard post-processing approaches would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback! Here is our response to the individual comments and questions in your review:\n\n**Re. temperature scaling.** Typically temperature scaling is applied to the logits when we optimize the cross entropy loss. Thus temperature scaling is more closely related to Definition 2.5 (which uses the cross-entropy loss) instead of Definition 2.2 (which uses the squared loss). In Definition 2.5 we apply a Lipschitz post-processing $\\\\kappa$ to the **logit** g(x) (see text around Line 225). Temperature scaling, i.e., dividing the logit g(x) by a temperature parameter T > 0, is a special case of such Lipschitz post-processings as long as T is not too close to zero (we need this assumption on T to ensure Lipschitzness). Definition 2.5 also considers many other Lipschitz post-processings that cannot be expressed as temperature scaling. This is important because our logistic regression example in Appendix B shows that a small post-processing gap w.r.t temperature scalings alone does NOT imply a small calibration error.\n\nWe will include this discussion about temperature scaling in our final version.\n\n**Re. experiments.** See our response to Reviewer 6rky re. experiments."}, {"review_id": "hUGp40c1pE", "reviewer": "Reviewer_CHsP", "summary": "This paper elucidates the relationship between proper losses and calibration by providing the minimal necessary and sufficient condition for proper losses to induce calibrated models.\nThe condition, local optimality, delineates the concept that no post-processing functions can improve a proper loss anymore.\nThis is related to a specific measure of calibration called smooth calibration error, which is a kind of correlation between miscalibration and model predictions.\nThe smooth calibration error is used here because it does not suffer from a discontinuous nature, unlike the popular expected calibration error, and it naturally emerges from the Bregman divergence structure.\nBy leveraging the Bregman divergence structure of proper losses and convex analysis, a theoretical connection between the smooth calibration error and the post-processing gap (the quantitative version of the local optimality condition) is established, which indicates that minimizing the post-processing gap is necessary and sufficient to achieve sufficiently small calibration error.\nAs an implication of the theory, the authors point out a potential connection between the implicit bias regularization of DNNs and the post-processing gap so that sufficiently over-parametrized networks may achieve a small post-processing gap, leading to the current well-calibrated neural networks.\nOverall, this paper pushes the understanding of proper losses and calibration toward the context of modern neural network regimes.", "questions": "Some minor comments:\n\n- (Question) At l.261, I don't get the point of \"within the restricted class where the logit is a linear combination of the features,\" specifically, what \"the features\" mean in the current context. Could you clarify?\n- (Question) Why do you present the non-generalized dual calibration error in Section 4, unlike the generalized one in the appendix? I do not get the reason why it is useful to confine the generalization $w(x,g(x))$ to $\\\\eta(x)$.\n- (Typo) At l.75, \"depends on on the architecture\" -> \"depends on the architecture\"\n- (Typo) At l.204, a parenthesis is missing for $\\\\eta(f(x))$.", "limitations": "The authors discuss the limitations of this work at the end of the paper and point out that there is room to investigate the connection among calibration, DNN architectures, and optimization.\n\nMost of the work is theoretical, and few negative societal concerns would apply.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- A new connection between proper losses and calibration: Though the two concepts seek similar goals, they have been studied independently, and the relationship has not been understood well. The main theorem of this paper draws the connection by establishing the upper and lower bounds of the post-processing gap (related to proper losses) by the smooth calibration error (related to calibration). As far as I know, this is the first attempt to connect the two concepts. The concept of the post-processing gap is well motivated by deep neural networks (regarding the post-process as the layer addition).\n- A transparent proof: The proof of the main result (Theorem E.8) gives us a nice picture of the relationship between the calibration error and proper losses. Specifically, the proof of the bounds mostly leverages the smoothness of a function $\\\\psi$. This proof is simple and gives us an insight that the structure of $\\\\psi$ essentially governs the connection.\n- The clarity of the presentation: Though the concepts introduced in this paper are rather dense, the authors did a nice job of presenting them gradually from a conceptual level to a technical level, which helps readers who may not be familiar with those concepts understand them easily.", "weaknesses": "- Potential gaps between the theory and Guo et al. (2017): The authors argue that \"the previous generation of image classifiers were poorly calibrated [Guo et al., 2017]\" and \"state-of-the-art DNNs are often well-calibrated: because their test loss cannot be improved much by adding a few more layers.\" However, I feel that the architectures used by Guo et al. (2017) are already very deep. For example, in their pilot study (Figure 1), they chose to use a 110-layer ResNet, which would be sufficiently over-parametrized. Since Guo et al. (2017) argued that DNNs are poorly calibrated even with that number of layers, I would like to see the authors' discussion on this line.\n- Missing key references: Some results and claims in the paper are substantially related to previous works that are not mentioned in the paper. It would be great to give credit to them. For example, the dual mapping of the form $\\\\mathsf{dual}(v) := \\\\ell(0,v) - \\\\ell(1,v)$ (l. 299) is known in Eq. (47) of Buja et al. (2005); The composition of a proper loss $\\\\ell$ and the dual mapping $\\\\psi$ is known as composite losses, coined in Reid and Williamson (2010). The dual loss form in Eq. (6) and Definition 4.3 is known as the Fenchel-Young losses, and the expression was shown in Eq. (14) of Blondel et al. (2020) and Eq. (11) of Duchi et al. (2018); The convex conjugate structure $\\\\nabla\\\\psi(\\\\mathsf{dual}(v)) = v$ (l. 329) was pointed out in Figure 1 of Bao and Sugiyama (2021); Some parts of Lemma E.4 are closely related to Proposition 2 of Blondel et al. (2020).\n- Restriction to binary classification: The attention of this whole paper is restricted to binary classification, as mentioned in the conclusion. This is far more restrictive in practical situations. But I don't think this limitation undermines the impact of this paper.\n\n\n**References**\n\n- Reid and Williamson (2010) \"Composite Binary Losses\"\n- Buja et al. (2005) \"Loss Functions for Binary Class Probability Estimation and Classification: Structure and Applications\"\n- Blondel et al. (2020) \"Learning with Fenchel-Young Losses\"\n- Duchi et al. (2018) \"Multiclass Classification, Information, Divergence, and Surrogate Risk\"\n- Bao and Sugiyama (2021) \"Fenchel-Young Losses with Skewed Entropies for Class-posterior Probability Estimation'", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback! Here is our response to the individual comments and questions in your review:\n\n**Re. relation to Guo et al. (2017).**\nThanks for the great question. The issue is subtle. We discussed it in our paper (see Line 119) and would like to further elaborate below.\n\nIt is simultaneously true that:\n1. The DNNs used in [Guo et. al] are \"deep enough\"\n2. The DNNs used in [Guo et. al] can be substantially improved (w.r.t test loss), by simple post-processing.\n\nThe resolution is that the DNNs of [Guo et al.] were optimized for test *Error* (not test loss), and thus were  \"overtrained\" – they trained these DNNs for many epochs, enough to nearly interpolate the train set. This causes a high test loss, which they notice in Figure 3 of [Guo et al.]\nThe authors themselves recognize this discrepancy between error and loss: \"neural networks can overfit to NLL without overfitting to the 0/1 loss.\"\n\nIn fact, if one trains the same DNNs as Guo et al, but optimizing for test *loss* (and thus, early-stopping before the loss overfits), then the resulting networks are very well-calibrated, consistent with our theory. (We have confirmed this experimentally, and given your question, we will consider adding this experiment to the full version).\n\nOur comment about \"state-of-the-art DNNs are often well-calibrated\" holds because, these days, DNNs are trained in the \"very large data\" regime, sometimes even for just 1 epoch — so, they have a small loss-generalization gap, and don't overfit their test loss.\n(e.g. the GPT-3 tech report which includes epoch details: https://arxiv.org/abs/2005.14165 , and Figure 16 of the GPT scaling laws paper [https://arxiv.org/abs/2001.08361],  which shows plots of test vs. train loss in both early-stopped and overfitting regimes).\n\nTo rephrase, the essential difference between SOTA networks in 2017 and 2023 is: In 2017, classification networks were trained for many epochs, and thus had very high test loss (despite small test error). But in 2023, we often have so much data that we cannot afford many epochs, and thus the test loss does not overfit.\n\nWe can add this more extended discussion to the final version of our paper.\n\n**Re. missing references.** We are grateful that you point us to these references! They are very relevant and we will make sure to cite them properly in our final version. We stated in our submission that the connection between proper losses and conjugate pairs of convex functions is well known before our work. We are eager to include a more comprehensive discussion about where each specific notion/result has appeared in the literature. Your suggested references are extremely helpful for us to this end.\n\n**Re. beyond binary classification.** See our response to reviewer ooFk re. multiclass settings.\n\n**Re. features in logistic regression.** We are referring to the standard logistic regression setting where each data point (x,y) has a feature vector $x\\\\in \\\\mathbb R^d$ and a binary label $y\\\\in \\\\{0,1\\\\}$. Given a number of such data points, our goal is to learn a linear/affine function $g(x) = \\\\langle a,x\\\\rangle + b$ that maps a feature vector x to a logit g(x), after which we apply the sigmoid transformation $\\\\sigma$ to get the final prediction $\\\\sigma(g(x))\\in [0,1]$. Here the logit g(x) is restricted to the form $g(x) = \\\\langle a,x\\\\rangle + b$. That is, the logit is a linear combination of the coordinates of x plus a bias b. Each coordinate of the feature vector x is usually called a feature, so the logit is a linear combination of the features plus a bias. We will add “plus a bias” to our paper to be more accurate.\n\n**Re. presentation of generalized dual calibration error.** We choose to defer our results about generalized dual calibration error to the appendix because 1) we have limited space, and 2) we do not want our core calibration results to be diluted by the more general results. In our final version, we will add text to our main paper mentioning and pointing to the more general results in the appendices so that interested readers will not miss them."}]

Author rebuttal:

Meta-review: The contributions of this paper were appreciated in the review, and the paper was overall considered valuable for the community. The reviews presented many items towards improving the presentation of the paper which we trust the authors to take carefully into account as promised in the the discussion.
Decision: Accept (spotlight)